Algorithmes de base

Algorithme de Bresenham

L’algorithme de Bresenham permet de tracer des lignes. Etant donné un segment de droite allant d’un point de depart x1; y1 (entiers) `a un point d’arrivée x2; y 2 (entiers) dans la grille, la question est : quels pixels noircir ? En eﬀet, un ´echantillonnage du segment fournit en g´en´eral des valeurs non entieres. Il faut une m´ethode de choix des pixels qui garantisse la continuit´e du segment, la plus grande rectitude possible ainsi qu’un temps de calcul faible. La figure 1 repr´esente un tel segment.
Si la pente de la droite est inf´erieure `a 1, alors nous devons allumer un et un seul pixel par colonne entre x1 et x2. Notez que ce n’est pas le cas pour les lignes. Nous pourrions donc ´ecrire le programme suivant :
Calcul par l’´equation de droite y = mx + b
dy = y2-y1;
dx = x2-x1;
m = dy/dx;
b = y1-m*x1;
for (x=x1; x<=x2; x++) {
y=m*x+b;
plot(x,round(y));
}
Voyons maintenant les am´eliorations successives aboutissant `a un programme optimis´e. En particulier, on d´esire ´eviter les calculs en virgule flottante pour ne traiter que des entiers.
Calcul de y par incr´ement
dy = y2-y1;
dx = x2-x1;
m = dy/dx;
y = y1; /* <———— */
for (x=x1; x<=x2; x++) {
plot(x,round(y));
y=y+m; /* <———— */
}
Simplification de l’arrondi
dy = y2-y1;
dx = x2-x1;
m = dy/dx;
y = y1;
f = 0; /* <———— */
for (x=x1; x<=x2; x++) {
plot(x,y);
f=f+m; /* <———— */
if (f>0.5) { /* <———— */
y = y+1;
f = f-1; /* <———— */
}
}
Suppression de la division par dx
dy = y2-y1;
dx = x2-x1;
y = y1;
f = 0;
3
for (x=x1; x<=x2; x++) {
f=f+dy; /* <———— */
plot(x,y);
if (f>(dx/2)) { /* <———— */
y = y+1;
f = f-dx; /* <———— */
}
}
Suppression de la division par 2
dy = y2-y1;
dx = x2-x1;
y = y1;
f = 0;
for (x=x1; x<=x2; x++) {
plot(x,y);
f=f+2*dy; /* <———— */
if (f>dx) { /* <———— */
y = y+1;
f = f-2*dx; /* <———— */
}
}
Tester le signe au lieu de comparer
dy = y2-y1;
dx = x2-x1;
y = y1;
f = -dx; /* <———— */
for (x=x1; x<=x2; x++){
plot(x,y);
f=f+2*dy;
if (f>0) /* <———— */
y = y+1;
f = f-2*dx;
}
}
Ne modifier f qu’une seule fois par passage dans la boucle
dy = y2-y1;
dx = x2-x1;
y = y1;
f = -dx;
for (x=x1; x<=x2; x++) {
plot(x,y);
if (f>0) {
y = y+1;
f = f + 2*(dy-dx); /* <———— */

1 Grilles
2 Algorithme de Bresenham
3 Remplissage de polygones
3.1 Cas du rectangle
3.2 Cas generale
3.3 Traitement des couleurs
4 Tracés dans OpenGL