PrograZine #7 - Une courbe qui n'est pas gauche: LA DROITE

[ edito | sommaire | contribution | contacts ]

[>Une courbe qui n'est pas gauche: LA DROITE<]

Olivier Pécheux
opecheux@multimania.com

>0) Introduction

LIEN

>I) Les exigences des tracés informatiques

LIEN

jamais d'utilisation de réels ni sous forme flottante, ni sous forme virgule fixe (même pour le tracé de cercle que nous verrons dans un prochain article). La virgule flottante utilise le coprocesseur et est plus lent que le calcul d'entiers. En virgule fixe, on fait des calculs d'entiers; mettons que sur 32 bits, on utilise les 16 bits de poids forts pour donner la partie entière et les 16 bits de poids faibles pour la partie fractionnaire. Je ne les utiliserai pas car ce n'est pas très facile pour un début: J'en parlerais peut être un jour.

l'utilisation des multiplications sera réduite au maximum car l'instruction est relativement longue.

le nombre de calculs sera réduit le plus possible

>II) Le segment de droite défini par deux points

>II.1) Variables de calcul

deltaX = x2 - x1
deltaY = y2 - y1

>II.2) Les premières droites

x1<x2

y1<y2

deltaX>deltaY

>II.3) Les belles droites

Il faut dessiner une belle droite!


                               *** < (x2,y2)
                         ******
                   ******
             ******
          ***
          ^ (x1,y1)

Il ne doit pas y avoir de trous


                ***
         *** ***    <- il va y avoir un problème!
      ***

Les points de départ et d'arrivé doivent être dessinés

Il ne doit pas y avoir 2 points dans un même colonne


                       ****
                  *******
             *******
          ****

Les marches doivent être régulières


             ****
          ***

>III) L'algorithme de Bresenham

>III.1) Le départ

>III.2) Points suivants


                         ***
                   ******
             ******
          ***

>III.3) Calcul avec des réels

Pour dessiner un nouveau point:

J'incrémente x de 1

J'incrémente erreur de deltaY/deltaX

L'erreur doit être inférieure à un demi-pixel

On ne montera jamais deux fois car justement on a choisi des droites qui montent peu (deltaX>=deltaY).

Pour dessiner une droite:

Initialiser:
- deltaX=x2-x1
- deltaY=y2-y1
- erreur=0
- (x,y)=(x1,y1)

Dessiner (x,y)

Si x=x2 c'est fini

Incrémenter x de 1

Incrémenter erreur de deltaY/deltaX

Si erreur>0,5 alors
- incrémenter y
- decrémenter erreur de 1

revenir à l'étape 2)

>III.4) Calcul avec des entiers

Ne jamais utiliser des réels!

au départ erreur vaut 0

on l'incrémente de deltaY/deltaX

on teste si elle est supérieure à 0,5

on la décrémente de 1

au départ erreur vaut 0/2.deltaX

on l'incrémente de 2.deltaY/2.deltaX

on la décrémente de 2.deltaX/2.deltaX

au départ erreur vaut 0

on l'incrémente de 2.deltaY

on teste si elle est supérieur à deltaX

on la décrémente de 2.deltaX

Pour dessiner une droite:

Initialiser:
- deltaX=x2-x1
- deltaY=y2-y1
- erreur=0
- (x,y)=(x1,y1)

Dessiner (x,y)

Si x=x2 c'est fini

Incrémenter x de 1

Incrémenter erreur de 2.deltaY

Si erreur>deltaX alors
- incrémenter y
- decrémenter erreur de 2.deltaX

revenir à l'étape 2)

>III.5) Le test

Quel est le bon test?

supérieur à un demi-pixel?

supérieur ou égal à un demi-pixel?

** **

>III.6) Le chiffre 2.

erreur est assigné à 0

on incrémente erreur de deux_deltaY

on teste si erreur est > ou >= à deltaX

on décrémente erreur de deux_deltaX

erreur est assigné à 0

on incrémente erreur de deltaY

on teste si erreur est > ou >= à deltaX_sur_deux

on décrémente erreur de deltaX

Si deltaX est impair?

          erreur > ou >= deltaX

          erreur > deltaX

          2 n > 2 p +1

          2 n > 2 p

erreur est assigné à 0

on incrémente erreur de deltaY

on teste si erreur est > à deltaX_sur_deux

on décrémente erreur de deltaX

Pour dessiner une droite:

Initialiser:

deltaX=x2-x1

deltaY=y2-y1

deltaX_sur_deux=deltaX/2 (par défaut, décalage par exemple)

erreur=0

(x,y)=(x1,y1)

Dessiner (x,y)

Si x=x2 c'est fini

Incrémenter x de 1

Incrémenter erreur de deltaY

Si erreur>deltaX_sur_deux alors
- incrémenter y
- decrémenter erreur de deltaX

revenir à l'étape 2)

>III.7) La comparaison

Que peut-on améliorer?

Pour dessiner une droite:

Initialiser:
- deltaX=x2-x1
- deltaY=y2-y1
- erreur=-deltaX/2 (par décalage)
- (x,y)=(x1,y1)

Dessiner (x,y)

Si x=x2 c'est fini

Incrémenter x de 1

Incrémenter erreur de deltaY

Si erreur>0 alors
- incrémenter y
- decrémenter erreur de deltaX

revenir à l'étape 2)

>III.8) Bresenham est mort, vive Martin

>IV) Algorithme de Martin

>IV.1) Première astuce de Martin: une seule addition

Incrémenter erreur de deltaY

decrémenter erreur de deltaX

On va trop loin! On ne peut pas savoir si il faut ajouter deltaY ou deltaY_moins_deltaX que si on fait la comparaison, or pour faire la comparaison, il faut avoir fait l'addition!

Pour dessiner une droite:

Initialiser:
- deltaX=x2-x1
- deltaY=y2-y1
- deltaX_moins_deltaY=deltaX-deltaY
- erreur=deltaY-deltaX/2
- (x,y)=(x1,y1)

Dessiner (x,y)

Si x=x2 c'est fini

Incrémenter x de 1

Si erreur>0 alors
- incrémenter y
- décrémenter erreur de deltaX_moins_deltaY
sinon incrémenter erreur de deltaY

revenir à l'étape 2)

>IV.2) Deuxième astuce de Martin: brûler la chandelle par les deux bouts

Que peut-on améliorer?

Oui, mais si deltaX est impair?


              *** < (6,1)
          ***
          ^(0,0)

si x>x' c'est fini

si x=x' (on peut assi tester si deltaX est pair) on ne dessine qu'un seul des deux points (n'importe lequel en fait).

Pour dessiner une droite:

Initialiser:
- deltaX=x2-x1
- deltaY=y2-y1
- deltaX_moins_deltaY=deltaX-deltaY
- erreur=deltaY-deltaX/2
- (x,y)=(x1,y1) et (x',y')=(x2,y2)

Dessiner (x,y) et (x',y')

Si x<=x' c'est fini

Incrémenter x, décrémenter x'

Si erreur>0 alors
- incrémenter y, décrémenter y'
- décrémenter erreur de deltaX_moins_deltaY
sinon incrémenter erreur de deltaY

revenir à l'étape 2)

>V) Martin est mort vive ???

>VI) Toutes les droites quelconques

Et les droites qui descendent? Et celle qui montent beaucoup? Et celles qui vont dans l'autre sens?

               ^y
          \  3 | 2  /
           \   |   /
            \  |  /
          4  \ | /  1
              \|/    
          -----*----->x
              /|\    
          5  / | \  8
            /  |  \  
           /   |   \ 
          /  6 | 7  \

vers la gauche, la droite, le haut, le bas, 4 directions obliques. L'algorithme de Martin fonctionne mais avec une erreur toujours nulle (obliques) ou toujours négative (verticales et horizontales). Il vaut mieux utiliser un algorithme spécifique.

les 8 directions obliques. Pour l'instant je n'ai parlé que de la direction nº1.

>VI.1) Directions 1 et 2

>VI.2) Les directions opposées

>VI.3) Directions 1 et 8

>VI.4) Ma méthode c'est la meilleure!

ligne_horizontale(x1,x2,y)

ligne_verticale(x,y1,y2)

ligne_oblique(x,y,delta) (je ne l'ai pas fait, c'est si exceptionnel!)

ligne(x1,y1,x2,y1)

>VII) Conclusion

Ce document est la propriété de Olivier Pécheux. La rédaction ainsi que l'auteur déclinent toutes résponsabilité vis-a-vis des conséquences que pourrait entrainer le contenu de cet article.