Algorithme de tracé de segment de Bresenham - Définition

Introduction

L’algorithme de tracé de segment de Bresenham est un algorithme développé par Bresenham en mai 1962, alors qu’il travaillait dans un laboratoire informatique d’IBM et cherchait à piloter un traceur attaché à une console texte. Cet algorithme a été présenté à la convention de l’ACM en 1963, puis publié en 1965 dans la revue IBM Systems Journal.

L’algorithme détermine quels sont les points d’un plan discret qui doivent être tracés afin de former une approximation de segment de droite entre deux points donnés. Cet algorithme est souvent utilisé pour dessiner des segments de droites sur l’écran d’un ordinateur ou une image calculée pour l’impression. Il est considéré comme l’un des premiers algorithmes découverts dans le domaine de la synthèse d'image.

Utilisations

Le principe du calcul est largement documenté et a depuis été repris pour tracer de façon incrémentale n’importe quelle courbe conique (cercle, ellipse, arc, parabole, hyperbole) ou courbes de Bézier grâce aux propriétés de leur fonction polynomiale de définition, dont les dérivées permettent de calculer les orientations de segments élémentaires avec de simples opérations entières. On peut même l’adapter à l’approximation de courbes dont on ne connaît qu’un développement limité (dont on ne prendra que les premiers termes de faible degré), utilisable avec une bonne précision sur un domaine suffisant par rapport à la résolution (sinusoïdes, exponentielles, puissances non entières).

L’algorithme est également facilement adaptable au calcul de courbes et surfaces dans un espace discret de plus de 2 dimensions (notamment pour le pilotage de machines outils). Même en deux dimensions seulement, on peut discrétiser avec cet algorithme une courbe avec une fonction de lissage prenant en compte l’erreur commise entre deux points candidats afin d’ajuster leur couleur, l’erreur incrémentale étant convertible en coefficient de transparence, ce qui permet de conserver la graisse (épaisseur visuelle) d’une courbe tout en limitant l’effet d’escalier (crénelage).

Cet algorithme intervient aussi dans le lissage de rendus de textures 2D appliquées sur des surfaces d’une scène 3D où la texture subit des réductions ou agrandissements. On l’emploie aussi pour le lissage d’agrandissements photographiques, ou pour l’interpolation de couleurs intermédiaires sur une échelle discrète.

Algorithme général optimisé

La généralisation de l’algorithme de base au tracé de vecteurs de direction quelconque est obtenue par simple symétrie.

L’algorithme est ici développé et optimisé dans chacun des huit octants. Toutefois, afin de s’assurer que les mêmes pixels seront toujours tracés pour deux vecteurs identiques mais de direction opposée, on inversera les cas limites où un déplacement diagonal est à égalité avec un déplacement droit, en choissant la diagonale quand le vecteur est orienté vers la gauche (abscisses décroissantes) plutôt que vers la droite (abscisses croissantes) comme dans le cas simplifié ci-dessus :

      procédure tracerSegment(entier x1, entier y1, entier x2, entier y2) est        déclarer entier dx, dy;                si (dx ← x2 - x1) ≠ 0 alors          si dx > 0 alors            si (dy ← y2 - y1) ≠ 0 alors              si dy > 0 alors                // vecteur oblique dans le 1er quadran                                si dx ≥ dy alors                  // vecteur diagonal ou oblique proche de l’horizontale, dans le 1er octant                  déclarer entier e ;                  dx ← (e ← dx) × 2 ; dy ← dy × 2 ;  // e est positif                  boucler sans fin  // déplacements horizontaux                    tracePixel(x1, y1) ;                    interrompre boucle si (x1 ← x1 + 1) = x2 ;                    si (e ← e - dy) < 0 alors                      y1 ← y1 + 1 ;  // déplacement diagonal                      e ← e + dx ;                    fin si ;                  fin boucle ;                sinon                  // vecteur oblique proche de la verticale, dans le 2nd octant                  déclarer entier e ;                  dy ← (e ← dy) × 2 ; dx ← dx × 2 ;  // e est positif                  boucler sans fin  // déplacements verticaux                    tracePixel(x1, y1) ;                    interrompre boucle si (y1 ← y1 + 1) = y2 ;                    si (e ← e - dx) < 0 alors                      x1 ← x1 + 1 ;  // déplacement diagonal                      e ← e + dy ;                    fin si ;                  fin boucle ;                fin si ;                              sinon  // dy < 0 (et dx > 0)                // vecteur oblique dans le 4e cadran                                si dx ≥ -dy alors                  // vecteur diagonal ou oblique proche de l’horizontale, dans le 8e octant                  déclarer entier e ;                  dx ← (e ← dx) × 2 ; dy ← dy × 2 ;  // e est positif                  boucler sans fin  // déplacements horizontaux                    tracePixel(x1, y1) ;                    interrompre boucle si (x1 ← x1 + 1) = x2 ;                    si (e ← e + dy) < 0 alors                      y1 ← y1 - 1 ;  // déplacement diagonal                      e ← e + dx ;                    fin si ;                  fin boucle ;                sinon  // vecteur oblique proche de la verticale, dans le 7e octant                  déclarer entier e ;                  dy ← (e ← dy) × 2 ; dx ← dx × 2 ;  // e est négatif                  boucler sans fin  // déplacements verticaux                    tracePixel(x1, y1) ;                    interrompre boucle si (y1 ← y1 - 1) = y2 ;                    si (e ← e + dx) > 0 alors                      x1 ← x1 + 1 ;  // déplacement diagonal                      e ← e + dy ;                    fin si ;                  fin boucle ;                fin si ;                              fin si ;            sinon  // dy = 0 (et dx > 0)                            // vecteur horizontal vers la droite              répéter                tracePixel(x1, y1) ;              jusqu’à ce que (x1 ← x1 + 1) = x2 ;                          fin si ;          sinon  // dx < 0            si (dy ← y2 - y1) ≠ 0 alors              si dy > 0 alors                // vecteur oblique dans le 2nd quadran                                si -dx ≥ dy alors                  // vecteur diagonal ou oblique proche de l’horizontale, dans le 4e octant                  déclarer entier e ;                  dx ← (e ← dx) × 2 ; dy ← dy × 2 ;  // e est négatif                  boucler sans fin  // déplacements horizontaux                    tracePixel(x1, y1) ;                    interrompre boucle si (x1 ← x1 - 1) = x2 ;                    si (e ← e + dy) ≥ 0 alors                      y1 ← y1 + 1 ;  // déplacement diagonal                      e ← e + dx ;                    fin si ;                  fin boucle ;                sinon                  // vecteur oblique proche de la verticale, dans le 3e octant                  déclarer entier e ;                  dy ← (e ← dy) × 2 ; dx ← dx × 2 ;  // e est positif                  boucler sans fin  // déplacements verticaux                    tracePixel(x1, y1) ;                    interrompre boucle si (y1 ← y1 + 1) = y2 ;                    si (e ← e + dx) ≤ 0 alors                      x1 ← x1 - 1 ;  // déplacement diagonal                      e ← e + dy ;                    fin si ;                  fin boucle ;                fin si ;                              sinon  // dy < 0 (et dx < 0)                // vecteur oblique dans le 3e cadran                                si dx ≤ dy alors                  // vecteur diagonal ou oblique proche de l’horizontale, dans le 5e octant                  déclarer entier e ;                  dx ← (e ← dx) × 2 ; dy ← dy × 2 ;  // e est négatif                  boucler sans fin  // déplacements horizontaux                    tracePixel(x1, y1) ;                    interrompre boucle si (x1 ← x1 - 1) = x2 ;                    si (e ← e - dy) ≥ 0 alors                      y1 ← y1 - 1 ;  // déplacement diagonal                      e ← e + dx ;                    fin si ;                  fin boucle ;                sinon  // vecteur oblique proche de la verticale, dans le 6e octant                  déclarer entier e ;                  dy ← (e ← dy) × 2 ; dx ← dx × 2 ;  // e est négatif                  boucler sans fin  // déplacements verticaux                    tracePixel(x1, y1) ;                    interrompre boucle si (y1 ← y1 - 1) = y2 ;                    si (e ← e - dx) ≥ 0 alors                      x1 ← x1 - 1 ;  // déplacement diagonal                      e ← e + dy ;                    fin si ;                  fin boucle ;                fin si ;                              fin si ;            sinon  // dy = 0 (et dx < 0)                            // vecteur horizontal vers la gauche              répéter                tracePixel(x1, y1) ;              jusqu’à ce que (x1 ← x1 - 1) = x2 ;                          fin si ;          fin si ;        sinon  // dx = 0          si (dy ← y2 - y1) ≠ 0 alors            si dy > 0 alors                            // vecteur vertical croissant              répéter                tracePixel(x1, y1) ;              jusqu’à ce que (y1 ← y1 + 1) = y2 ;                          sinon  // dy < 0 (et dx = 0)                            // vecteur vertical décroissant              répéter                tracePixel(x1, y1) ;              jusqu’à ce que (y1 ← y1 - 1) = y2 ;                          fin si ;          fin si ;        fin si ;        // le pixel final (x2, y2) n’est pas tracé.      fin procédure ;      

Notes :

• Ci-dessus, les assignations sont parfois regroupées au sein des expressions qui en réutilisent la valeur assignée. Si le langage utilisé ne le permet pas, il suffit d'effectuer les assignations internes dans des instructions d’assignation préalables séparées, et de relire cette variable dans l’expression contenante.
• Les primitives graphiques tracePixel(x₁, y₁) sont regroupées ci-dessus pour tracer dans la boucle interne des segments horizontaux (cas du premier octant ci-dessus) ou verticaux (second octant), et peuvent être regroupées en un seul appel (il suffit de compter le nombre de passages dans la boucle interne, et d’effectuer le tracé de segment horizontal (ou vertical) en sortie de cette boucle.