Algorithme de tracé de segment fenêtré de Hadrien Flammang

Un algorithme de tracé de segment fenêtré permet de ne tracer d'un segment que la partie qui est visible dans une zone rectangulaire (fenêtre).
La version proposée ici est basée sur l'algorithme de Bresenham.

Rappel sur le tracé d'un segment selon l'algorithme de Bresenham.

On veut tracer un segment du point A de coordonnées (x1,y1), au point B de coordonnées (x2,y2).
Il s'agit d'approcher un segment de droite défini dans un plan mathématique par une suite de pixels allumés sur un dispositif d'affichage.
Les pixels étant contraints à des coordonnées entières, et, à part dans certains cas triviaux, il y aura des erreurs d'arrondi.
Posons dX = x2-x1 et dY = y2-y1, et plaçons nous dans le cas où dX ≥ dY > 0, c'est-à-dire dans le premier octant.


En vert, les pixels qui sont allumés pour rester au plus près du segment mathématique, en rouge.


Dans le premier octant, l'abscisse des pixels est incrémentée à chaque itération alors que l'ordonnée peut rester inchangée.
Tout le problème est de déterminer quand l'ordonnée doit être incrémentée pour minimiser l'erreur avec le segment mathématique.
Pour le résoudre, on définit 3 variables qui vont varier tout au long du tracé du segment : X, Y et S.
X et Y représentent respectivement, l'abscisse et l'ordonnée du pixel courant.
S correspond à l'erreur d'arrondi commise au pixel courant.
Quand cette valeur dépasse un certain seuil, il est temps d'incrémenter l'ordonnée.

L'algorithme de Bresenham peut alors se résumer à trois suites Xn, Yn et Sn qui se définissent mutuellement :

Initialisation des suites :

X0 = x1
Y0 = y1
S0 = 2dY - dX

Récursion :

Xn+1 = Xn + 1
Si Sn ≥ 0
Alors
Yn+1 = Yn + 1
Sn+1 = Sn + 2dY - 2dX
Sinon
Yn+1 = Yn
Sn+1 = Sn + 2dY

On s'arrète quand on a atteint le pixel d'abscisse x2.

On voit ici que le test se fait sur le signe de S : si S est négatif, on n'incrémente pas Y.

Le fenêtrage

Le fenêtrage consiste a n'allumer les pixels d'un segment que s'ils sont à l'interieur d'un rectange (fenêtre).

Ici, en bleu, les pixels qui doivent être allumés. Le segment entre dans la fenêtre en A' et en sort en B'.

Il existe plusieurs algorithmes permettant de réaliser le fenêtrage.
Pour la plupart, ils consistent à calculer les points A' et B', puis à lancer un tracé de segment classique entre ces 2 points.


Après calcul des points d'entrée et sortie, les pixels allumés (en jaune) ne se supperposent pas exactement aux originaux (en bleu).

Cette technique a une contrainte qui peut poser problème : les pixels qui vont être "allumés" ne sont pas ceux qui l'auraient été si le segment avait été tracé dans son intégralité.
Un algorithme "idéal" devrait allumer exactement les mêmes pixels.
Ceci est réalisable de manière triviale en lançant le calcul des pixels du segment total mais en testant l'appartenance de chaque pixel à la fenêtre.
Malheureusement les performances d'un tel algorithme seraient lamentables.

L'algorithme de Hadrien Flammang

L'idée est de calculer Xn, Yn, et Sn à l'endroit où le segment entre dans la fenêtre, puis de lancer le tracer de segment avec ces valeurs initiales.
De cette façon, les pixels allumés seront exactement les mêmes que si le segment avait été entièrement tracé (c'est-à-dire comme si on avait itéré n fois à partir de X0, Y0, et S0).
Cherchons en un premier temps à calculer Sn, et nous verrons que Xn et Yn viennent rapidement.
Pour comprendre comment on résout le problème, il faut remarquer qu'à chaque itération S est incrémenté de 2dY, et que s'il était positif ou nul, il est en plus décrémenté de 2dX.
Donc, la plus grande valeur que peut prendre Sn est atteinte losque Sn-1 = -1.
Dans ce cas, Sn = Sn-1 + 2dY = 2dY - 1, sauf peut-être à l'initialisation.
Mais S0 = 2dY - dX2dY - 1 puisque dX ≥ 1, donc 2dY - 1 est bien la plus grande valeur possible de S.
De la même façon, la plus petite valeur de Sn est atteinte lorsque Sn-1 = 0 car alors Sn = 2dY - 2dX, et S0 = 2dY-dX > 2dY - 2dX.
Nous savons donc maintenant que Sn varie dans l'intervalle [ 2dY - 2dX ; 2dY - 1 ], c'est-à-dire qu'il peut prendre 2dX valeurs distinctes au maximum.

Essayons donc de calculer Sn : supposons que n points aient été tracés et qu'il y ait eu x pas en Y, c'est-à-dire que S a été n fois incrémenté de 2dY et x fois décrémenté de 2dX.
On a donc : Sn = S0 + n.2dY - x.2dX = 2dY - dX + 2.n.dY - 2.x.dX.
Or, nous savons que Sn ne peut prendre que 2dX valeurs distinctes, il est donc clair qu'une seule valeur de x convient (le facteur de x étant justement 2dX).
Prenons donc le cas où Sn prend sa plus grande valeur, et déduisons-en x : Sn = 2dY - dX + 2.n.dY - 2.x.dX = 2dY-1.
On trouve x = ( 2.n.dY - dX + 1) div 2dX.
Sachant que d'une façon générale (A div B)*B = A - (A mod B), il vient :

Sn = ( 2.n.dY + dX ) mod 2dX + 2dY - 2dX

Par un raisonnement similaire, on trouve Yn = Y0 + ( 2ndY + dX ) div 2dX + 2dY - 2dX, et trivialement Xn = X0 + n.
Il peut être utile aussi de calculer n à partir de Xn et Yn : n = Xn - X0, ou encore n = ( 2dX( Yn - Y0 ) - dX - 1 ) div 2dY + 1.

Voyons maintenant, comment, à partir de ces formules, il va être possible de calculer tous les paramètres de l'algorithme de Bresenham, au point d'entrée dans la fenêtre.

Soient xmin et xmax les limites en X de la fenêtre, et ymin et ymax les limites en Y.
Nous allons énumérer les tests à effectuer pour établir la position du segment par rapport à la fenêtre, et déterminer s'il y a lieu xd, yd et sd, les valeurs initiales des suites X, Y et S.
(Les tests doivent être executés dans l'ordre où ils sont donnés.)

Si x1 > xmax ou x2 < xmin
Alors
<le segment est entièrement en dehors de la fenêtre.> (1)
Sortie

Si y1 > ymax ou y2 < ymin
Alors
<le segment est entièrement en dehors de la fenêtre.> (2)
Sortie

Si (x1 < xmin) et ((y1 + ( 2(xmin - x1).dY + dX) div 2dX ≥ ymin) ou (y1 ≥ ymin))
Alors
Si (y1 + ( 2( xmin - x1 )dY + dX ) div 2dX) ≥ ymax
Alors
<le segment est entièrement en dehors de la fenêtre.> (3)
Sinon
<le segment entre dans la fenêtre par la gauche.> (4)
n ← xmin-x1
xd ← xmin
yd ← y1 + ( 2ndY + dX ) div 2dX
sd ← ( 2ndY + dX ) mod 2dX + 2dY - 2dX

Si y1 < ymin
Alors
Si x1 + ( 2dX( ymin - y1 ) - dX - 1 ) div 2dY + 1 > xmax
Alors
<le segment est entièrement en dehors de la fenêtre.> (5)
Sinon
<le segment entre dans la fenêtre par le bas.> (6)
n ← ( 2dX( ymin - y1 ) - dX - 1 ) div 2dY + 1
xd ← x1 + n
yd ← ymin
sd ← ( 2ndY + dX ) mod 2dX + 2dY - 2dX
Sinon
<le premier point du segment est dans la fenêtre.> (7)
xd ← x1
yd ← y1
sd ← 2dY - dX


Les différents cas de segments discriminés ici.

Détermination de xf, l'abscisse du dernier point à tracer :
Si y2 > ymax et ( x2 ≤ xmax ou (y1 + 2dY(xmax - x1) + dX) div 2dX > ymax)
Alors
n ← ( 2dX( ymax - y1 ) - dX - 1 ) div 2dY
xf ← x1 + n
Sinon
Si x2 > xmax
Alors
xf ← xmax
Sinon
xf ← x2

Il ne reste plus qu'à lancer l'algorithme de Bresenham pour tracer le segment du point (xd,yd) jusquà ce qu'il atteigne le point d'abscisse xf, avec l'erreur initiale Sd :

x ← xd
y ← yd
s ← sd
Tant que ( x ≤ xf )
AllumerPixel( x,y )
x ← x + 1
Si s ≥ 0
Alors
y ← y + 1
s ← s + 2dY - 2dX
Sinon
s ← s + 2dY