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

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de tracé de segment de Xiaolin Wu de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme de tracé de segment — Un algorithme de tracé de segment est un algorithme utilisé en infographie pour tracer approximativement un segment de droite sur des média graphiques discrets. Sur les média discrets, tels que les écrans ou les imprimantes avec une définition… …   Wikipédia en Français

  • Algorithme De Tracé De Segment — Un algorithme de tracé de segment est un algorithme utilisé en infographie pour tracer approximativement un segment de droite sur des média graphiques discrets. Sur les média discrets, tels que les écrans ou les imprimantes avec une définition… …   Wikipédia en Français

  • Algorithme de trace de segment — Algorithme de tracé de segment Un algorithme de tracé de segment est un algorithme utilisé en infographie pour tracer approximativement un segment de droite sur des média graphiques discrets. Sur les média discrets, tels que les écrans ou les… …   Wikipédia en Français

  • Crénelage — Pour les articles homonymes, voir repliement. Le crénelage (ou crènelage) ou repli de spectre (Aliasing en anglais) est un phénomène qui peut se produire lors du traitement numérique d un signal, lorsque des fréquences qui ne sont pas… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”