Algorithmes de tracé de segments de droites

P, Q \in \mathbb{Z}^2

Problème: étant donné deux points P et Q de coordonnées entières, afficher le segment de droite PQ. C'est à dire, déterminer les pixels approximant le segment et donnant l'impression visuelle.

Rappel: Droite de pente k passant par un point M_0 = \left(x_0 \atop y_0 \right) et de vecteur directeur \vec{v}=\left(u \atop v\right).

  • y=kx+b
  • b=y0 - k * x0 = l'ordonnée en x0

Droite de pente k passant par P=\left( x_1 \atop x_2 \right), Q=\left(x_2 \atop y_2\right)

y = k \cdot x+c \quad\text{avec}\quad k = \frac{y_2 - y_1}{x_2 - x_1} \quad\text{ et }\quad \begin{pmatrix}0\\ c\end{pmatrix}=\begin{pmatrix}x_1\\ y_1\end{pmatrix}+\beta \begin{pmatrix}x_2-x_1 \\ y_2 - y_1 \end{pmatrix}
\begin{eqnarray} x_1 +\beta\cdot x_2- \beta\cdot x_1 & = & 0\\ x_1 = 0 & \Rightarrow & c=y_1 \\ \beta & = & - \frac{x_2-x_1}{x_1} \\ c & = & y_1 - \frac{x_2-x_1}{x_1} \left(y_2 - y_1\right) \\ y & = & \frac{y_2 - y_1}{x_2 - x_1}\cdot x +y_1 - \frac{x_2-x_1}{x_1} \left(y_2 - y_1\right) \\ y - y_1 & = & \frac{\Delta y}{\Delta x}\cdot x - \frac{\Delta x}{x_1} \left(y_2 - y_1\right) \\ \end{eqnarray}

Calculs en virgules flottantes

AfficheSegmentFloat( P point, Q point, c code_couleur){
  delta_x = Q.x - P.x;
  delta_y = Q.y - P.y;
  if (delta_x==0) pente=0 else pente=delta_y/delta_x;
  decalage = P.y - pente * P.x;
/* on suppose que le segment a une pente entre 0 et 1 et on affiche un pixel par colonne */
  if (delta_x >0 && delta_x >= delta_y){
    for (x=P.x, x<=Q.x, 1) 
      {
      y = round(x * pente + decalage);
      AffichePixel(x,y);
      }
  }
}

Lorsque la pente est de 1 à + infini on affiche un pixel par ligne.

  • on peut améliorer cet algorithme en travaillant de manière incrémentale
    y_{k+1} = \frac{\Delta y}{\Delta x}\left(x+1\right) + c = \frac{\Delta y}{\Delta x}\cdot + c + \frac{\Delta y}{\Delta x} = y_{k} + \frac{\Delta y}{\Delta x}

; et en utilisant l'arithmétique entière, mais comment faire?

Algorithme de Bresenham

L'idée fondamentale est qu'à chaque transition de xc à xc+1=xc+1 dans le premier octant, on choisit entre yc+1=yc (on ne change pas de ligne) et yc+1=yc+1 (on change de ligne). Il convient de trouver une bonne règle pour prendre cette décision à chaque x.

La préconisation est de prendre le pixel dont le décalage (ou distance) vertical de la vraie ligne est le (ou la) moindre.

  • pour yc : d1=m(xc+1)+b-yc
  • pour yc+1 : d2=yc +1 - m(xc+1)-b
  • Si D=d1-d2 est positive, d2 est moindre et on choisit yc+1
  • Si D=d1-d2 est négative, d1 est moindre et on choisit yc
  • Or, si on développe D et multiplie par \Delta x >0 puisqu'on est dans le premier octant par hypothèse,
    \begin{eqnarray}D & =& d1-d2\\ & = & \left[\frac{\Delta y}{\Delta x}\left(x_c + 1\right) + b - y_c\right] - \left[y_c+1 -\frac{\Delta y}{\Delta x}\left(x_c + 1\right)-b \right] \\ & = & \frac{\Delta y}{\Delta x}\left(x_c + 1\right) + b - y_c - y_c-1 +\frac{\Delta y}{\Delta x}\left(x_c + 1\right)+b \\ & = & 2\times\left[\frac{\Delta y}{\Delta x}\left(x_c + 1\right) + b - y_c \right] -1 \\ d_c=\Delta x \times D & = & 2\times\left[\Delta y\left(x_c + 1\right) + b\times\Delta x - y_c \times\Delta x\right] -\Delta x \end{eqnarray}
  • Notons que presque tous ces termes sont des entiers puisque x_1,y_1,x_2,y_2 sont des entiers; mais b?
  • Calcul incrémentale de dc+1:
    • si dc < 0, d1 < d2 et on choisit yc. Donc d_{c+1} = 2\Delta y \left(x_c + 1 + 1\right) - 2 y_c \Delta x - \Delta x +2b\Delta x = d_c + 2\Delta y
    • di dc >0, d1 > d2 et on choisit yc+1. Donc d_{c+1} = 2\Delta y \left(x_c + 1 + 1\right) - 2 (y_c +1) \Delta x - \Delta x +2b\Delta x = d_c + 2\Delta y - 2\Delta x

Premier Pas

Au premier pas, la valeur initiale de dc est calculée:

\begin{eqnarray} d_c(1) & = & 2\Delta y \left(x_1 +1\right) - 2y_1 \Delta x - \Delta x + 2b \Delta x \\ & = & 2\Delta y + 2x_1 \Delta y - 2y_1 \Delta x - \Delta x + 2b \Delta x \\ & = & 2\Delta y - \Delta x + 2\left[x_1 \Delta y - y_1 \Delta x + b \Delta x\right] \\ & = & 2\Delta y - \Delta x + 2\Delta x \left[\underbrace{x_1 \frac{\Delta y}{\Delta x} + b - y_1 }_{=0} \right] \\ & = & 2\Delta y - \Delta x \end{eqnarray}

Algorithme

x=x1;y=y1;
delta_x = x2 - x1; delta_y = y2 - y1;
d = 2*delta_y - delta_x;
incr1 = -2* delta_x;
incr2 = 2*delta_y;
for (i=0; i<=delta_x; i++) {
  AffichePixel(x,y,couleur);
  if (d>= 0) {y=y+1;d=d+incr1;}  
  x=x+1;
  d=d+incr2;

Remarques

  1. Reste à généraliser cet algorithme aux autres octants en TP
  2. il est incrémental et en entiers (donc rapide) mais il est dur de calculer les intersections avec d'autres figures, ou même de “deviner” si un pixel est allumé ou non sans dérouler l'algorithme! Bonne nouvelle : il existe une “droite arithmétique” passant par les mêmes P et Q et les points de cette droite sont ceux du segment discret 8-connexe obtenus par l'algorithme de Bresenham.

Droite Arithmétique

La droite arithmétique passant par P=\left(x_1,y_1\right), Q=\left(x_2,y_2\right) avec \left(\Delta x = x_2 - x_1 \gt 0\right)\quad \& \quad \left(\Delta y = y_2-y_1\geq 0\right) \quad \& \quad \left(\Delta y \leq \Delta x\right) est \displaystyle \left\{ \left(x,y\right)\in\mathbb{Z}^2 | y=y_1+\lfloor \frac{\left(x-x_1\right)\Delta y + \frac{\Delta x}{2}}{\Delta x}\rfloor\right\}

Algorithme de Lucas

Précondition : premier octant (comme d'hab)

delta_x = Q.x - P.x; delta_y = Q.y - P.y;
r = floor(delta_x/2);
y = y1;
pour x = x1 à x2 par 1 faire
  afficher (x,y,couleur);
  r=r+delta_y;
  if (r>= delta_x) {y=y+1; r=r-delta_x;}

Autres Octants

Octant Delta X Delta Y Pentes Que faire
1 + + 0 à 1 Cas “standard”
2 + + 1 à infini inverser rôles de x et y
3 - +
4 - +
5 - -
6 - -
7 + - - infini à -1
8 + - 0 à -1

Navigation


 
m1ilc/fain_segments.txt · Dernière modification: 2010/01/08 13:05 par suitable