Algorithme de tracé de segment de Xiaolin Wu
# 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 ($\Delta x>\Delta y$). Pour l'étendre à toutes les lignes, inversez les coordonnées x et y quand $\Delta x<\Delta y$ (comme pour l'algorithme de Bresenham). Cette implémentation n'est valide que pour x ≥ 0 et y ≥ 0.

## 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).
