Explications de l'algorithme de tracé de lignes de Bresenham

Pour représenter une ligne sur un écran composé de pixels, il faut allumer les pixels passant le plus près possible de la ligne idéale :

Sur ce schéma, on suppose que chaque case représente un pixel, s'il est grisé c'est qu'il est allumé.

La droite (AB) est la droite idéale. Le problème est celui-ci : comment savoir quels pixels allumer pour s'approcher le plus possible de la droite idéale ?

La première solution qui vient à l'esprit est de calculer la distance verticale entre le pixel et la droite idéale et d'allumer le pixel pour lequel l'erreur est inférieure à 0.5. Par exemple, considérons la droite d'équation y=ax+b avec a=1/3 :

Pour le premier pixel, bien entendu, il n'y a aucune erreur, mais pour le deuxième, l'erreur est égale à 0.33 (a) et au troisième, l'erreur est 0.66, ce qui est supérieur à 0.5, donc on allume le pixel au-dessus.

À chaque pixel, l'erreur augmente de a et lorsqu'elle est supérieure à 0.5, on allume le pixel du dessus, et l'erreur devient minorée de 1. Voilà un code qui dessinerait une ligne selon cette règle :

void ligne(short x1,short y1,short x2,short y2)
{
    float erreur,a;
    short dx,dy,x,y;
    dx = x2 - x1 ;
    dy = y2 - y1 ;
    a = dy / dx ;
    err = 0 ;
    for(x = x1 , y = y1 ; x < x2 ; x++)
    {
        AffichePixel(x,y);

        err += a ;
        if(err > 0.5)
        {
            err -= 1 ;
            y++ ;
        }

        x++ ;
    }
}

Bien sûr, cette fonction ne permet que de tracer une ligne dont la distance sur x est plus grande que celle sur y et il faut aussi que les coordonnées passées en argument respectent ces deux conditions : x1<x2 et y1<y2.

Le gros problème de cet algorithme, si on recherche la vitesse, c'est qu'il utilise deux nombres à virgule flottante pour stocker a et err.
En fait, voici les opérations faites sur la variable err :

 - err += dy/dx
 - err > 1/2
 - err -= 1

Et si on est obligé d'utiliser des nombres à virgule flottante, c'est simplement à cause de la division par dx. Il faut supprimer cette division pour pouvoir stocker err dans un entier. La solution consiste à multiplier par dx à chaque opération, ce qui transforme les opérations précédentes par :

 - err += dx*dy/dx <=> err += dy
 - err > dx*1/2 <=> err > dx/2
 - err -= dx*1 <=> err -= dx

Voilà, avec ça on peut utiliser des entiers.

Une deuxième optimisation qui permettrait de gagner un petit peu de rapidité (mais c'est vraiment infime par rapport à ce qu'on vient de gagner en supprimant l'utilisation des float) serait de tester simplement le signe de err plutôt que de le comparer avec dx/2 à chaque fois. Pour cela, c'est très simple, il suffit d'initialiser la valeur de err à -dx/2 au lieu de 0.

Une autre optimisation, puisqu'on connaît à l'avance la longueur de la ligne sur x, consisterait à ne pas comparer à chaque cycle la valeur courante de x avec la valeur de x2, mais simplement à décrémenter à chaque cycle pendant tout le tracé de la ligne une variable qui est initialisée avec la longueur de la ligne sur x.

La dernière optimisation, est de remplacer la division par deux par un décalage de bits vers la droite.

Voici ce qu'est devenu l'algorithme du début :

void ligne(short x1,short y1,short x2,short y2)
{
    short err, a, dx, dy;

    dx = x2 - x1 ;
    dy = y2 - y1 ;
    err = -dx>>1 ;
    x2 -= x1 ;

    do
    {
        AffichePixel(x1,y1);

        err += dy ;
        if(err > 0)
        {
            err -= dx ;
            y1++ ;
        }

        x1++ ;
    }while(x2--);
}

Cet algorithme est maintenant devenu très rapide puisqu'il n'utilise que des entiers et ne requiert que des additions et soustractions (aucune multiplication ni division). Les dernières optimisations consisteraient à afficher le pixel directement dans la fonction, cela permettrait de ne pas avoir à recalculer l'adresse du pixel à allumer à chaque cycle puisqu'on se déplace d'un pixel à chaque fois, mais ces optimisations ne font plus vraiment partie de l'algorithme de tracé, donc je ne les implémente pas ici.

L'algorithme juste au-dessus permet toujours de ne tracer qu'un seul type de lignes, ces lignes doivent remplir ces conditions : dx>dy, x1<x2, y1<y2.
Pour pouvoir tracer toutes les lignes possibles, il faut gérer tous les cas. Gérer les cas où x1>x2 ou bien ceux où y1>y2 n'est pas très compliqué, il suffit simplement de décrémenter x ou y au lieu de les incrémenter, et de vérifier qu'on prend bien la valeur absolue de x2 après l'opération x2 -= x1 ;.
Pour tracer les lignes où dy>dx, il faut réfléchir un peu plus. En fait, il faut voir le problème comme lorsque dx était supérieur à dy : on doit évoluer sur y en incrémentant/décrémentant y à chaque pixel et calculer l'erreur sur x, et incrémenter ou décrémenter x quand l'erreur devient trop importante. Pour calculer l'erreur, il faut savoir de combien elle augmente à chaque pixel. Elle augmente de dx/dy. Après, c'est comme précédemment, pour éviter la division par dy, on multiplie tout par dy, etc...

Dernières optimisations :
Normalement, avec cet algo le traçage de ligne est très rapide, mais si c'est encore un peu trop lent, vous pouvez toujours détecter des cas particuliers comme lorsque la ligne est verticale ou horizontale, ou bien si le coefficient directeur est égal à 1...

Voilà, c'est la fin de cet article sur le traçage de ligne selon l'algorithme de Bresenham.
Pour tout info complémentaire ou remarque constructive, mailez-moi : julien.rf@wanadoo.fr

    Julien RF (aka jackiechan).