Bonjour à tous.
Dans ce petit tutorial en deux temps, je vais vous expliquer le principe du
"Wu drawing". Derrière ce terme barbare se cache un système de
pixel-plot (l'affichage à l'écran pixel par pixel) très intéressant, car relativement optimisé, et permettant de dessiner des formes avec un *vrai* anti-aliasing (le faux étant de moyenner chaque pixel par ses voisins, lourd en calcul, et ne faisant que du flou au final).
Le principe est très facile à comprendre:
subdiviser chaque pixel de l'écran en plusieurs "sub-pixel" (généralement 4 ou 16),
afficher notre forme dans ce sous-système, et enfin
moyenner pour l'affichage final. Cela implique bien sûr un peu plus de ressources, mais l'esthétique générale y gagne énormément.
Nous commencerons dans ce premier tutorial par traiter le cas simple et indispensable de l'affichage de lignes de Wu.
Dans un second tutorial à venir, nous généraliserons le principe à tout type de forme.
Première partie: les lignes de Wu
Tracer une ligne est l'élément de base du pixel plot. L'algorithme le plus utilisé est celui de
Bresenham.
Petit rappel:En 1962, Bresenham nous pond un algorithme permettant de tracer des
lignes de pixels uniquement avec des entiers, et sans division ni multiplication. Il faut préciser qu'à l'époque, multiplier a par b équivalait à faire x = ((a<b) ? a : b) additions, plutôt lourd pour de grand chiffres.
Le principe est extrêmement simple: on définie une variable dépendant de la pente de la droite, qui est incrémentée à chaque itération. Si cette variable dépasse une certaine valeur, qui dépend elle aussi de la pente de la droite, on change de ligne/colonne suivant le cas.
Voilà une fonction qui permet d'afficher une ligne de Bresenham de (xi, yi) à (xf, yf) avec la couleur c:
//------------------------------------------------------------------------------
void drawBresLine(int xi, int xf, int yi, int yf, int c, uint16 *vram)
/* Affiche une ligne de Bresenham */
//------------------------------------------------------------------------------
{
// Definition des variables
int i, cumul;
int x = xi, y = yi;
// Decalage en x et y
int dx = xf-xi, dy = yf-yi;
// Incrementation ou decrementation?
int xinc = (dx>0) ? 1 : -1;
int yinc = (dy>0) ? 1 : -1;
if(dx<0) dx = -dx;
if(dy<0) dy = -dy;
// Affichage du 1er pixel
vram[(y<<8)+x] = RGB15(c,c,c);
// Cas d'une droite plutot horizontale
if (dx>dy)
{ cumul = dx>>1;
for (i=1; i<=dx ;i++)
{ x += xinc;
cumul += dy;
if (cumul>=dx) {cumul -= dx; y += yinc;}
vram[(y<<8)+x] = RGB15(c,c,c);
}
}
// Cas d'une droite plutot verticale
else
{ cumul = dy>>1;
for (i=1; i<=dy; i++)
{ y += yinc;
cumul += dx;
if (cumul>=dy) {cumul -= dy; x += xinc;}
vram[(y<<8)+x] = RGB15(c,c,c);
}
}
}
Rien de bien compliquer dans ce code. Notez que pour simplifier au maximum, je n'ai pas tenu compte des débordements.
On remarquera juste la séparation des cas, toutefois symétriques, droite plutôt horizontale / plutôt verticale.
Dans l'exemple d'une droite plutôt horizontale, les x sont parcourus un par un, et pour chaque boucle la variable cumul est incrémentée du décalage en y. Lorsqu'elle devient supérieure au décalage en x, elle est ramené à une valeur viable, et l'affichage est (in/dé)crémenté d'un pixel en y.
Pour ceux qui voudraient prolonger leur expérience avec sieur Bresenham, sachez sa technique peut être adaptée pour afficher les cercles, ellipses, hyperboles, etc...
La technologie avançant, et les floating point apparaissant sur nos ordis, un certain
Xiaolin Wu réfléchit à un nouvel algorithme pour tracer des lignes de pixels, parce que Bresenham c'est chouette, c'est optimisé, mais c'est moche
L'idée de Wu fut de
subdiviser chaque pixel en plusieurs entités, les "sub-pixels", pour ainsi palier au 1 ou 0 du pixel éclairé ou pas. En gros, le principe consiste à déterminer la proportion du morceau de droite dans chaque pixel, et d'éclairer le pixel en fonction. Nous allons donc faire ce qu'on appelle de la discrétisation.
Une image valant mieux qu'un beau discours...:
Chaque carré représente un pixel vrai. En haut, une ligne par l'algorithme de Bresenham. Vous remarquerez que chaque pixel est soit blanc, soit noir suivant qu'il soit traversé par la ligne ou non.
La discrétisation de la ligne est présentée au milieu. Ici, j'ai choisi une discrétisation de 16, c'est-à-dire que chaque pixel vrai est subdivisé en 16*16 = 256 sub-pixels. En général, on travaille avec une discrétisation de 4, 16 ou 256 (certains doivent déjà comprendre pourquoi
).
Le jeu va ici consister à trouver la valeur en y des intersections entre notre ligne blanche et chaque petite ligne rouge verticale qui se situe au milieu de chaque pixel vrai.
Cette valeur, dans ce cas un pourcentage sur 256, est directement lié à la proportion de droite contenue dans chacun des pixels vrais.
Par exemple ici: la première ligne rouge croise la ligne blanche à un tier de la hauteur du pixel vrai. Celà signifie aussi que la fraction de droite comprise dans le pixel du haut est de 33%, ou 85/256. Donc, le pixel du haut sera éclairé à 33%, et celui du bas à 66%, puisque la somme des 2 doit faire 100%.
Pour une droite blanche, ça se traduit par:
vram[(y<<8)+x] = RGB15( 85/256, 85/256, 85/256);
vram[((y+1)<<8)+x] = RGB15(170/256, 170/256, 170/256);
En appliquant ce principe à chaque pixel en x, on obtient la droite du bas, nettement plus jolie que celle du haut, car anti-aliasée de manière naturel.
Notez que les valeurs d'éclairage correspondent directement à un niveau de transparence, c'est-y pas beau?
J'en entends néanmoins quelques-uns crier au scandale: "Une division, c'est mal! Des floating point, c'est très mal!".
Je leur répondrai:
"Et les goto alors?"... euh, non, c'est pas ça... merde, où est mon texte..? Ha, voilà: "Oui, c'est mal, mais nous allons tout simplifié tranquillement".
Bref, voici la fonction que j'utilise pour tracer des lignes de Wu de (x1,y1) à (x2,y2), simplifiée car les points initiaux et finaux sont des entiers. Il est cependant très facile de passer à des fixed point pour qu'une droite puisse commencer "entre" des pixels:
//------------------------------------------------------------------------------
static inline void drawWuLine(int x1, int x2, int y1, int y2, uint16 *vram)
/* Affiche une ligne de Wu */
//------------------------------------------------------------------------------
{
// Declaration des variables
int xf, yf, grad;
int x = 0, y = 0;
u8 c = 31; // Ligne blanche
u8 c1, c2;
// Ligne horizontale
if (abs(x2-x1)>abs(y2-y1))
{
if (x1>x2) {swapInt(&x1, &x2); swapInt(&y1, &y2);}
grad = div32((y2-y1)<<8, (x2-x1));
yf = (y1<<8)+(grad>>1);
for (x=x1; x<=x2; x++)
{
c2 = (c*(yf&255))>>8;
c1 = 31-c2;
vram[((yf>>8)<<8)+x] = RGB15(c1,c1,c1);
vram[(((yf>>8)+1)<<8)+x] = RGB15(c2,c2,c2);
yf += grad;
}
}
// Ligne verticale
else
{
if (y1>y2) {swapInt(&x1, &x2); swapInt(&y1, &y2);}
grad = div32((x2-x1)<<8, (y2-y1));
xf = (x1<<8)+(grad>>1);
for (y=y1; y<=y2; y++)
{
c2 = (c*(xf&255))>>8;
c1 = 31-c2;
vram[(y<<8)+(xf>>8)] = RGB15(c1,c1,c1);
vram[(y<<8)+(xf>>8)+1] = RGB15(c2,c2,c2);
xf += grad;
}
}
}
Plusieurs remarques pour commencer:
- Les cas horizontaux et verticaux sont à nouveau séparés, mais symétriques.
- Encore une fois je n'ai pas tenu compte des effets de bord, à vous de rajouter des conditions aux cas où les lignes sortiraient de l'écran
- Ce code ne vaut que pour les lignes blanches et l'affichage se fait en 16bit. Si vous voulez mettre de la couleur, il faut remplacer c par trois variables, une pour chaque composante R,G, B.
- On travaille en fixed point 8bit pour éviter les float, précision largement suffisante.
- Seulement une division et x2-x1 ou y2-y1 multiplications. Comme tout se fait en hardware, les différences de vitesse entre cet algo et celui de Bresenham sont négligeables.
Rentrons dans le code un peu plus en détail, en se basant sur les droites horizontales:
if (x1>x2) {swapInt(&x1, &x2); swapInt(&y1, &y2);}Une simple inversion éventuelle des points finaux et initiaux pour pouvoir incrémenter correctement
grad = div32((y2-y1)<<8, (x2-x1));
yf = (y1<<8)+(grad>>1);
Le calcul (qui fâche
) de la pente de la droite, grad, qui correspond à la valeur d'incrémentation de y pour chaque x, puis de yf, hauteur du point d'intersection de notre droite avec le milieu du pixel, d'où le +(grad>>1).
c2 = (c*(yf&255))>>8;
c1 = 31-c2;
Pour chaque boucle, définition du pourcentage de droite dans le pixel du haut (le &255 c'est seulement pour ramener la valeur entre 0 et 255), puis déduction de celui dans le pixel du bas (on remarquera que c1+c2 = 31, donc éclaraige à 100% pour les 2 pixels).
vram[((yf>>8)<<8)+x] = RGB15(c1,c1,c1);
vram[(((yf>>8)+1)<<8)+x] = RGB15(c2,c2,c2);
Ecriture des 2 pixels sur l'écran.
Et enfin incrémentaion de xf.
Si vous désirez en savoir plus, je vous conseille cette page (en anglais) qui explique en détails les lignes de Wu:
http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htmPour conclure, une petite démo accompagnée de son code source afin de comparer par vous-même la différence entre Bresenham et Wu.
http://will0thewisp.free.fr/DS/WuLines/WuLines.ds.gbahttp://will0thewisp.free.fr/DS/WuLines/WuLines.ndshttp://will0thewisp.free.fr/DS/WuLines/main.c
J'espère que ça vous a plus
Rendez-vous dans quelque temps pour des nouvelles aventures au pays du Wu Drawing
Merci EvilSpoon pour la relecture
