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

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

L'algorithme de tracé de segment fenêtré de Hadrien Flammang permet de ne tracer d'un segment que la partie qui est visible dans une zone rectangulaire (fenêtre). Il est basé sur l'algorithme de Bresenham.


On veut tracer un segment du point de coordonnées (x1,y1), au point de coordonnées (x2,y2). 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. 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 :

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

Rappel sur le principe de l'algorithme de Bresenham

Tracé d'un segment dans un espace discret. (0,0) est au coin bas gauche, ordonnées montantes

Il s'agit d'approcher un segment de droite défini dans un plan mathématique par une suite de pixels sur un dispositif d'affichage. Les pixels étant contraints à des coordonnées entières, et à part dans des cas triviaux, on va commettre une erreur d'arrondi. Dans le cas particulier où nous nous sommes placés (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. La valeur de Sn représente l'erreur d'arrondi pour le n-ème pixel. Quand cette valeur dépasse un certain seuil c'est qu'il est temps d'incrémenter l'ordonnée. D'où le test sur S qui conditionne l'incrémentation de Y.

Le fenêtrage

Segment tracé dans son intégralité

Le problème du fenêtrage se pose quand on ne veut tracer d'un segment que la partie qui est visible dans une fenêtre. Il existe plusieurs algorithmes permettant de réaliser le fenêtrage.[1]

Segment fenêtré : après calcul des points d'entrée et sortie, les pixels allumés ne sont pas exactement les mêmes

Pour la plupart, ils consistent à calculer le point d'entrée et de sortie du segment dans la fenêtre 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" allumerait 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)

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

 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

Détermination de xf, l'abscisse d 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'à tracer le segment du point (xd,yd) jusquà ce qu'il atteigne le point d'abscisse xf, avec l'erreur initiale S :

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

  1. Algorithmes de fenêtrage (line clipping)
  • Portail de l’informatique Portail de l’informatique
  • Portail de la géométrie Portail de la géométrie
Ce document provient de « Algorithme de trac%C3%A9 de segment fen%C3%AAtr%C3%A9 de Hadrien Flammang ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de tracé de segment fenêtré de Hadrien Flammang de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme De Tracé De Segment — Un algorithme de tracé de segment est un algorithme utilisé en infographie pour tracer approximativement un segment de droite sur des média graphiques discrets. Sur les média discrets, tels que les écrans ou les imprimantes avec une définition… …   Wikipédia en Français

  • Algorithme de trace de segment — Algorithme de tracé de segment Un algorithme de tracé de segment est un algorithme utilisé en infographie pour tracer approximativement un segment de droite sur des média graphiques discrets. Sur les média discrets, tels que les écrans ou les… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”