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.
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.
Initialisation des suites :
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.
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'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 - dX ≤ 2dY - 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 :
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.)