Algorithme de tracé de segment de Xiaolin Wu

L'algorithme de tracé de segment de Xiaolin Wu est un algorithme permettant de tracer des courbes non-crénelées qui a été présenté dans l'article An Efficient Antialiasing Technique de Juillet 1991 issue de Computer Graphics ainsi que dans l'article Fast Antialiasing de juillet 1992 issue du journal du docteur Dobb.

L'algorithme de Bresenham trace des lignes extrêmement rapidement, mais n'est pas conçu pour l'anticrénelage. En plus de cela, il ne gère pas le cas où les points de bout de ligne ne sont pas situés exactement sur la grille de pixel. L'approche naïve pour dessiner des lignes sans crénelage prend énormément de temps, mais l'algorithme de Wu est assez rapide (tout en restant plus lent que l'algorithme de Bresenham). La base de l'algorithme est de dessiner des paires de pixels chevauchant la ligne, colorée selon leur proximité. Les pixels de bout de ligne sont traités séparément.

Une extension de l'algorithme pour les cercles a été présentée par Wu dans Graphics Gems II. Tout comme l'algorithme de tracé de segment de Wu est un remplaçant de l'algorithme de tracé de segment de Bresenham, celui de tracé de cercle de Wu est un remplaçant de l'algorithme de tracé de cercle de Bresenham.

Implémentation en pseudo-code

Ci-dessous, le pseudo-code de l'algorithme dans le cas où la ligne est presque horizontale (Δx > Δy). Pour l'étendre à toutes les lignes, inversez les coordonnées x et y quand Δx < Δy (comme pour l'algorithme de Bresenham). Cette implémentation n'est valide que pour x ≥ 0 et y ≥ 0.

fonction plot(x, y, c):
    dessine le pixel (x, y) avec la luminosité c (avec 0 ≤ c ≤ 1)

fonction ipart(x):
    return partie entière de x

fonction round(x):
    return ipart(x + 0.5)

fonction fpart(x):
    return partie fractionnaire de x
 
fonction rfpart(x):
    return 1 - fpart(x)

fonction drawLine(x1,y1,x2,y2):
    dx = x2 - x1
    dy = y2 - y1

    si abs(dx) > abs(dy):
        // gère les lignes « horizontales »
        si x2 < x1:
            inverser x1, x2
            inverser y1, y2
        fin-si
        gradient = dy / dx

        // gère le premier point de bout de ligne
        xend = round(x1)
        yend = y1 + gradient * (xend - x1)
        xgap = rfpart(x1 + 0.5)
        xpxl1 = xend  // sera utilisé dans la boucle principale
        ypxl1 = ipart(yend)
        plot(xpxl1, ypxl1, rfpart(yend) * xgap)
        plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap)
        intery = yend + gradient // première intersection avec y pour la boule principale

        // gère le second point de bout de ligne
        xend = round(x2)
        yend = y2 + gradient * (xend - x2)
        xgap = fpart(x2 + 0.5)
        xpxl2 = xend  // sera utilisé dans la boucle principale
        ypxl2 = ipart(yend)
        plot(xpxl2, ypxl2, rfpart(yend) * xgap)
        plot(xpxl2, ypxl2 + 1, fpart(yend) * xgap)

        // boucle principale
        pour x de xpxl1 + 1 à xpxl2 - 1:
            plot(x, ipart(intery), rfpart(intery))
            plot(x, ipart(intery) + 1, fpart(intery))
            intery += gradient
        répéter
    sinon:
         // gère les lignes « horizontales » en inversant le rôle de x et y
    fin-si
fin-fonction

Référence

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Xiaolin_Wu's_line_algorithm » (voir la liste des auteurs)

Liens externes

• Tracé de ligne anti-aliasé sur le site de ClearAlgo

• Portail de l’algorithmique
• Portail de l’imagerie numérique