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 (x₁,y₁), au point B de coordonnées (x₂,y₂).
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, il y aura des erreurs d'arrondi (à part dans certains cas triviaux).

Posons dX = x₂-x₁ et dY = y₂-y₁, 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 X_n, Y_n et S_n qui se définissent mutuellement :

Initialisation des suites :


    X₀ = x₁

    Y₀ = y₁

    S₀ = 2dY - dX

Récursion :




    
    X_n+1 = X_n + 1

    Si S_n ≥ 0

    Alors


    
    Y_n+1 = Y_n + 1

    S_n+1 = S_n + 2dY - 2dX

    

    Sinon

    
    Y_n+1 = Y_n

    S_n+1 = S_n + 2dY

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

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).

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

Il existe plusieurs algorithmes permettant de réaliser le fenêtrage.
Pour la plupart, ils consistent à calculer les points A' et B', puis à tracer le segment qui les relie.

Mais après calcul des points d'entrée et sortie, on constate que les pixels allumés (en violet) ne se supperposent pas exactement aux originaux (en vert).
Un algorithme optimal devrait allumer exactement les mêmes pixels.
Ceci est réalisable de manière triviale en lançant le calcul du segment total, tout en testant l'appartenance de chaque pixel à la fenêtre.
Mais ce serait au prix de piètres performances.

L'algorithme optimal

L'idée est de calculer X_n, Y_n, et S_n à 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 X₀, Y₀, et S₀).

Cherchons en un premier temps à calculer S_n, et nous verrons que X_n et Y_n viennent rapidement.

Pour calculer directement la valeur de S_n (sans calculer les termes de 0 à n-1),
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 S_n est atteinte losque S_n-1 = -1.
Dans ce cas, S_n = S_n-1 + 2dY = 2dY - 1, sauf peut-être à l'initialisation.
Mais S₀ = 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 S_n est atteinte lorsque S_n-1 = 0 car alors

S_n
    = 2dY - 2dX

, et S₀ = 2dY-dX > 2dY - 2dX.
Nous savons donc maintenant que S_n varie dans l'intervalle [ 2dY - 2dX ; 2dY - 1 ], c'est-à-dire qu'il peut prendre 2dX valeurs distinctes au maximum.

Essayons donc de calculer S_n : supposons que

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 : S_n = S₀ + n.2dY - x.2dX = 2dY - dX + 2.n.dY - 2.x.dX.
Or, nous savons que S_n 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ù S_n prend sa plus grande valeur, et déduisons-en x :

S_n = 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 :

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

Par un raisonnement similaire, on trouve

Y_n = Y₀ + ( 2ndY
        + dX ) div 2dX + 2dY - 2dX

, et trivialement

X_n = X₀
            + n

.
Il peut être utile aussi de calculer n à partir de X_n et Y_n : n = X_n - X₀, ou encore n = ( 2dX( Y_n - Y₀ ) - 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 x_min et x_max les limites en X de la fenêtre, et y_min et y_max 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 x_d, y_d et s_d, les valeurs initiales des suites X, Y et S.
(Les tests doivent être executés dans l'ordre.)


    Si x₁ > x_max ou x₂ < x_min

    Alors

<le segment est entièrement en dehors de la fenêtre (cas 1)>
Sortie


    Si y₁ > y_max ou y₂ < y_min

    Alors

<le segment est entièrement en dehors de la fenêtre (cas 2).>
Sortie


    Si (x₁ < x_min) et ((y₁ + ( 2(x_min
            - x₁).dY + dX) div 2dX ≥ y_min) ou (y₁ ≥ y_min))

    Alors


    Si (y₁ + ( 2( x_min - x₁ )dY + dX ) div 2dX) ≥ y_max

    Alors

<le segment est entièrement en dehors de la fenêtre (cas 3).>
Sortie

Sinon

<le segment entre dans la fenêtre par la gauche (cas 4).>


    n ← x_min-x₁

    x_d ← x_min

    y_d ← y₁ + ( 2ndY + dX ) div 2dX

    s_d ← ( 2ndY + dX ) mod 2dX + 2dY - 2dX

    Sortie


    Si y₁ < y_min

    Alors


    Si x₁ + ( 2dX( y_min - y₁ ) - dX - 1 ) div 2dY + 1 > x_max

Alors

<le segment est entièrement en dehors de la fenêtre (cas 5).>
Sortie

Sinon

<le segment entre dans la fenêtre par le bas (cas 6).>


    n  ← ( 2dX( y_min - y₁ ) - dX - 1 ) div 2dY + 1

    x_d ← x₁ + n

    y_d ← y_min

    s_d ← ( 2ndY + dX ) mod 2dX + 2dY - 2dX

    Sortie

Sinon

<le premier point du segment est dans la fenêtre (cas 7).>


    x_d ← x₁

    y_d ← y₁

    s_d ← 2dY - dX

    Sortie

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

Détermination de x_f, l'abscisse du dernier point à tracer :


    Si y₂ > y_max et ( x₂ ≤ x_max
        ou (y₁ + 2dY(x_max - x₁) + dX) div 2dX > y_max)

    Alors


    n ← ( 2dX( y_max - y₁ ) - dX - 1 ) div 2dY

    x_f ← x₁ + n

Sinon


    Si x₂ > x_max

    Alors


    x_f ← x_max

Sinon

x_f ← x₂

Il ne reste plus qu'à lancer l'algorithme de Bresenham pour tracer le segment du point (x_d,y_d) avec l'erreur initiale S_d,
jusqu'à ce qu'il atteigne le point d'abscisse x_f :


    x ← x_d

    y ← y_d

    s ← s_d

    Tant que ( x ≤ x_f )


    AllumerPixel( x,y )

    x ← x + 1

    Si s ≥ 0

    Alors


    y ← y + 1

    s ← s + 2dY - 2dX

Sinon

s ← s + 2dY

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

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

Le fenêtrage

L'algorithme optimal

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