L'algorithme de Bresenham

(Traduction et remaniement de http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html)
[Introduction|Bresenham pour l'octant 1|Amélioration de l'algorithme|Les autres octants]

Introduction

Le but de l'algorithme de Bresenham est de tracer un segment de droite en utilisant uniquement les points d'une grille discrète comme dans la figure ci-dessous:
[]
Pour ce faire 8 cas sont distingués, suivant la pente de la droite et le sens dans lequel le segment est dessiné. Ces 8 cas divise le plan euclidien en 8 zone appelées octants:

L'octant 1

Considérez le tracer d'une droite de pente m avec 0<=m<=1 sur une grille entre les points (x1,y1) et (x2,y2) tels que x1<x2, c'est à dire le cas de l'octant 1.

Si on considère qu'à chaque pas de l'algorithme de traçage on incrémente x, après avoir tracé un point en  (x,y), l'algorithme doit déterminer quel sera le prochain point affiché et il y a pour cela 2 possibilités:

Ainsi, travaillant dans le premier octant positif du plan, tracer une droite devient un problème de décision avec deux possibilités à chaque étape.

Nous pouvons tracer un diagramme de la situation après que l'algorithme ait affiché le point (x,y) :

Après avoir dessiné le point (x,y), l'algorithme doit faire un compromis entre ce que l'on veut dessiner et ce que la résolution de la grille permet réellement de dessiner. Habituellement le point (x,y) est déjà une erreur, le point réel sur la droite n'étant pas accessible sur la grille. Ainsi nous associons une erreur d'ordonnée ε à pour chaque abscisse x car l'ordonnée réelle devrait être y+ε. Cette erreur se trouvera dans l'intervalle [-0.5,+0.5[.

En passant de x à x+1, on augmente la valeur de l'ordonnée (mathématique) d'une quantité égale à la pente de la droite:  m. Nous choisirons donc de tracer (x+1,y) si la différence entre cette nouvelle ordonnée et y est inférieure à 0,5, c'est à dire si:

y+ε+m < y+0.5

Autrement nous tracerons (x+1,y+1). En faisant ainsi nous réduisons au minimum l'erreur globale entre le segment de droite mathématique et le tracé de ce segment.

L'erreur résultant de ce nouveau point peut maintenant être considéré comme le nouvel ε, ceci nous permettra de répéter pour le prochain point sur la droite, celui pour lequel l'abscisse est x+2.

La nouvelle valeur de l'erreur peut adopter une de deux valeurs possibles, selon le choix du point tracé. Si (x+1,y) est choisi, la nouvelle valeur de l'erreur est donnée par:

ε ← (y+&epsilon+m)-y

Autrement elle est:

ε ← (y+&epsilon+m)-(y+1)

On obtient ainsi l'algorithme suivant:

ε ← 0; y ← y1; x ← x1;
TantQue x ≤ x2 faire
dessiner (x,y)
Si ( &epsilon+m < 0.5 ) alors
  ε ← ε + m
Sinon
   y ← y+1; ε ← ε + m -1
FinSi
x ← x+1
FinTantQue

Amélioration de l'algorithme pour l'octant 1

Cet algorithme utilise des variables à virgule flottante. Pour éviter cela (les tests en nombre entiers étant plus efficaces), en posant

Δx = x2-x1
Δy = y2-y1
sachant que m=Δy/Δx, on manipule quelque peu l'expression du test en multipliant par 2 et par Δx pour obtenir:
2ε&Deltax+2Δy < Δx

Toutes les quantités de cette inégalité sont maintenant entières.

En posant ε'=εΔx, le test devient:

2(ε'+Δy) < Δx

Les règles de mise à jour pour l'erreur sur chaque étape peuvent également être adaptées à ε':

ε ← ε + m ⇔ ε' ← ε' + Δy
ε ← ε + m-1 ⇔ ε' ← ε' + Δy - Δx
L'algorithme avec le test n'utilisant que des nombres entiers est donc:
Δx ← x2-x1; Δy ← y2-y1;
ε' ← 0; y ← y1; x ← x1;
TantQue x ≤ x2 faire
dessiner (x,y)
Si ( 2(&epsilon'+&Deltay) < Δx ) alors
  ε' ← ε' + Δy
Sinon
   y ← y+1; ε' ← ε' + Δy - Δx
FinSi
x ← x+1
FinTantQue

Remarques sur l'amélioration de l'algorithme:

Voici une implémentation en C++ de l'algorithme de Bresenham pour des segments de droite dans le premier octant: 

    void octant1(Screen &s,
              unsigned x1, unsigned y1,
              unsigned x2, unsigned y2,
              unsigned char colour )
    {
      int dx  = x2 - x1,
          dy  = y2 - y1,
          y   = y1,
          eps = 0;
    
      for ( int x = x1; x <= x2; x++ )  
      {
        s.Plot(x,y,colour);
        eps += dy;
        if ( (eps << 1) >= dx )  
        {
          y++;  eps -= dx;
        }
      }
    }

Cette fonction n'utilise que des nombres entiers positifs, utilise le décalage à gauche pour la multiplication et élimine des opérations superflues par l'utilisation rusée du eps variable.

Cette implémentation est inachevée, elle ne vérifie pas que les paramètres correspondent bien au tracage d'un segment de droite dans le premier octant

Les autres octants

Exercice: Donnez l'algorithme pour l'octant 6.