Génération de ligne
L'algorithme de Bresenham est utilisé pour tracer une ligne entre deux points (X1,Y1) et (X2,Y2) sur une grille (écran) de manière entière, c'est-à-dire en utilisant uniquement des entiers, sans calculs à virgule flottante.
Il est très efficace pour :
- Dessiner des lignes droites en 2D.
- Éviter les erreurs de précision liées aux nombres flottants.
- Fournir un résultat rapide pour le rendu graphique.
Principe général
Une ligne peut avoir deux types de pente :
- Pente < 1 (ligne plus horizontale que verticale) : on avance pixel par pixel en X et on ajuste Y selon une erreur cumulative.
- Pente ≥ 1 (ligne plus verticale que horizontale) : on avance pixel par pixel en Y et on ajuste X selon une erreur cumulative.
L'algorithme de Bresenham utilise une variable Delta (erreur) pour décider quand incrémenter l'autre coordonnée.
Variables principales :
- DeltaX = |X2 - X1| : largeur de la ligne.
- DeltaY = |Y2 - Y1| : hauteur de la ligne.
- Delta : erreur cumulée pour décider du changement de l'autre coordonnée.
- A_inc et B_inc : incréments utilisés pour ajuster Delta.
- DirectionIncrementation : +1 ou -1, selon que la ligne va vers la droite ou la gauche.
Cas particulier : ligne horizontale
Si Y1 = Y2 :
|
SI Y2 = Y1 ALORS Afficher Ligne Horizontale (X1, Y1, X2), Couleur FIN SI |
C'est un cas simple : on peut dessiner tous les pixels de X1 à X2 à la même hauteur Y1.
Cas général : pente < 1 ou pente ≥ 1
Pente ≥ 1 (ligne plus verticale)
Condition :
| SI Abs(X2 - X1) < Abs(Y2 - Y1) ALORS |
On parcourt Y (axe principal) de Y1 à Y2.
On ajuste X uniquement quand l'erreur cumulative dépasse un seuil.
Étapes :
- Si Y1 ≥ Y2, on échange les points pour avancer toujours de bas en haut.
- On définit la direction pour X (DirectionIncrementation = +1 ou -1).
- On calcule les deltas et l'erreur initiale :
|
DeltaY ← Y2 - Y1 DeltaX ← Abs(X2 - X1) Delta ← 2 × DeltaX - DeltaY A_inc ← 2 × (DeltaX - DeltaY) B_inc ← 2 × DeltaX |
On parcourt Y, on ajuste X selon Delta :
|
J ← X1 Afficher Pixel(J, Y1), Couleur BOUCLE POUR I ← Y1+1 JUSQU'A Y2 SI Delta ≥ 0 ALORS J ← J + DirectionIncrementation Delta ← Delta + A_inc SINON Delta ← Delta + B_inc FIN SI Afficher Pixel(J, I), Couleur FIN BOUCLE |
Pente < 1 (ligne plus horizontale)
Sinon :
| SINON |
- On parcourt X (axe principal) de X1 à X2.
- On ajuste Y uniquement quand l'erreur cumulative dépasse un seuil.
Étapes :
- Si X1 > X2, on échange les points pour avancer toujours de gauche à droite.
- On définit la direction pour Y (DirectionIncrementation = +1 ou -1).
- On calcule les deltas et l'erreur initiale :
|
DeltaX ← X2 - X1 DeltaY ← Abs(Y2 - Y1) Delta ← 2 × DeltaY - DeltaX A_inc ← 2 × (DeltaY - DeltaX) B_inc ← 2 × DeltaY |
On parcourt X, on ajuste Y selon Delta :
|
J ← Y1 Afficher Pixel(X1, J), Couleur BOUCLE POUR I ← X1+1 JUSQU'A X2 SI Delta ≥ 0 ALORS J = J + DirectionIncrementation Delta ← Delta + A_inc SINON Delta ← Delta + B_inc FIN SI Afficher Pixel(I, J), Couleur FIN BOUCLE |
Version complète du pseudo-code finalisé
Voici l'algorithme complet de la ligne de Bresenham :
|
MODULE Ligne(variable X1 , variable Y1 , variable X2, variable Y2 , variable Couleur ) SI Y2 = Y1 ALORS Afficher Ligne Horizontale ( X1 , Y1 , X2 ), Couleur SINON SI Abs ( X2 ← X1 ) < Abs( Y2 - Y1) ALORS SI Y1 > Y2 ALORS ECHANGER X1 , X2 ECHANGER Y1 , Y2 FIN SI SI X2 > X1 ALORS Direction Incrémentation ← 1 SINON Direction Incrémentation ← -1 FIN SI Delta Y ← Y2 - Y1 Delta X ← Abs ( X2 ← X1 ) Delta ← Delta X x 2 ← Delta Y A inc ← ( Delta X ← Delta Y ) x 2 B inc ← Delta X x 2 J ← X1 Afficher Pixel ( X1 , Y1 ), Couleur I ← Y1 + 1 BOUCLE FAIRE TANT QUE I <= Y2 SI Delta >= 0 ALORS J ← J + Direction Incrémentation Delta ← Delta + A inc SINON Delta ← Delta + B inc FIN SI Afficher Pixel( J , I ), Couleur I ← I + 1 FIN BOUCLE FAIRE TANT QUE SINON SI Y1 > Y2 ALORS ECHANGER X1 , X2 ECHANGER Y1 , Y2 FIN SI SI Y2 > Y1 ALORS Direction Incrémentation ← 1 SINON Direction Incrémentation ← -1 FIN SI Delta X ← X2 ← X1 Delta Y ← Abs ( Y2 ← Y1 ) Delta ← ( Delta Y x 2 ) - Delta X A inc ← ( Delta Y ← Delta X ) x 2 B inc ← Delta Y x 2 J ← Y1 Afficher Pixel ( X1, Y1 ), Couleur I ← X1 + 1 BOUCLE FAIRE TANT QUE I <= X2 SI Delta >= 0 ALORS J ← J + Direction Incrémentation Delta ← Delta + A inc SINON Delta ← Delta + B inc FIN SI Afficher Pixel ( I, J ), Couleur I ← I + 1 FIN SI FIN SI FIN SI |
Dernière mise à jour : Dimanche, 1er février 2026