Réaliser des dessins anti-aliasés

Introduction du cours

Salut à tous!

Vous avez remarqué que la SDL par défaut ne propose que des fonctionnalités de bas niveau. Lorsque j'ai codé plusieurs de mes projets, j'ai eu besoin de tracer des lignes, etc. Je me suis retrouvé à coder par moi-même pas mal de fonctions géométriques de base car je n'ai pas trouvé de bibliothèque qui permette directement de le faire (mis à part OpenGL, mais c'est un peu violent si on veut juste faire un trait ! ).

Alors, vous allez me dire "Pour tracer un trait, 2 secondes suffisent !", ce qui n'est pas faux (quoique… ^^ ). Mais là, l'intérêt est que le tout est anti-aliasé / anticrénelé!

Même si le fait de les coder m'a aidé à progresser, franchement c'est beaucoup de galère ; alors, plutôt que de garder ce travail uniquement pour moi, je vais vous le présenter ici.

Le code est commenté en anglais (eh oui, c'est le langage de l'informatique… et surtout parce que je l'ai fait pour un projet en anglais). Il va falloir vous y habituer, car tout est en anglais, et entre autres les documentations !

Je n'ai pas réussi à faire quelque chose d'efficace pour tracer des arcs de cercle (pour l'instant), donc si quelqu'un y arrive, je serai plus qu'heureux de l'ajouter ici, afin de compléter la bibliothèque !

L'anti-aliasing

Dans cette partie d'introduction, nous allons voir le principe de l'anti-aliasing.

Avant

On voit clairement un effet d'escalier sur les traits. Plus on se rapproche de 0° ou de 90°, plus c'est flagrant… Et c'est pas beau ! Voyons comment régler ça :

Après

Là, si vous vous approchez un peu de votre écran, vous voyez qu'au bord des escaliers, il y a une sorte de dégradé… c'est ça l'anti-aliasing (ou anticrénelage) !

Le problème de crénelage vient du fait qu'un écran d'ordinateur présente les images de manière discrète et non continue, donc quand la ligne ne passe pas exactement sur un pixel mais entre 2, la couleur du trait est appliquée sur 1 des 2 pixels uniquement.

Pour empêcher cela, pour une droite de 1 px de large, on trace toujours 2 pixels de large et on va répartir la couleur de la droite et du fond entre ces 2 pixels.

Par exemple, si l'on souhaite placer un pixel noir sur un fond blanc dans le repère (x;y) à la position (5;3.48), on va placer :

• un pixel à la position (5;3) avec 48 % de noir et 52 % (100 % moins 48 %) de blanc => 100 % de couleur ;

• un pixel à la position (5;4) avec 52 % (100 % moins 48 %) de noir et 48 % de blanc => 100 % de couleur.

On a bien 100 % de noir et 100 % de blanc au total sur les 2 pixels, ainsi que 100 % de couleur par pixel. On a bien la même "quantité" de blanc et de noir que celle que l'on aurait si la ligne était passée sur un seul pixel et qu'on avait laissé le pixel d'à côté blanc. On a donc toujours bien l'illusion que la droite fait un pixel de large.

On remarque immédiatement que cette méthode est relativement lourde gourmande en ressources, car il y est question de transparence, de mélange de couleurs et de flottants. Néanmoins, sur des ordinateurs plutôt modestes, j'ai utilisé ma bibliothèque pour faire des traits qui étaient attachés à la souris (donc beaucoup de "retraçages") et cela marchait sans souci…

SDL et les pixels

Nous allons à présent voir comment travailler les pixels de votre fenêtre SDL à la main. Tout se résume dans ce code :

*((Uint32*)(map->pixels) + x + y * map->w) = color;

map étant la surface, x la position en x, et y, bien évidemment, la position en y (voir le cours de M@teo si besoin). En gros, dans le SDL, une surface est un grand tableau de 1 ligne et "largeur*hauteur" colonnes, où pour chaque case on associe une couleur (codée sur 32 bits). Pour récupérer la couleur en x;y, on doit donc aller à la colonne x + y*largeur (car elle n'est pas stockée dans une matrice 2D de dimensions x;y !).

Le code, que j'ai donné en haut, set la valeur de couleur au pixel concerné. On pourrait faire l'inverse pour récupérer la couleur :

color_ptr = *((Uint32*)(map->pixels) + x + y * map->w); color = *color_ptr;

… mais généralement, on souhaite avoir les composantes RGBA de la couleur, on préfèrera donc comme suit :

SDL_GetRGBA(*((Uint32 *)map->pixels + x + y * map->w),map->format,r,g,b,a);

Au final, on obtient les routines suivantes pour interagir facilement sur les pixels :

// Size of a point #define POINT_SIZE 4 // Sets a pixel on x,y position on a color on the map: // If the position is out of map, nothing is done // Returns: void void setPixel(int x, int y, Uint32 color, SDL_Surface *map) { if(x>0 && y>0 && x<map->w && y<map->h) *((Uint32*)(map->pixels) + x + y * map->w) = color; } // Getter for a pixel color on x,y position on the map // The r, g, b, a pointer are set to the red, green, blue and alpha value of the pixel // If the position is out of map, nothing is done // Returns: void void getPixelColor(int x, int y, SDL_Surface *map, Uint8 *r, Uint8 *g, Uint8 *b, Uint8 *a) { if(x>0 && y>0 && x<map->w && y<map->h) SDL_GetRGBA(*((Uint32 *)map->pixels + x + y * map->w),map->format,r,g,b,a); } // Sets a point on x,y position on the map on a color, of the map // Point's size if 2*POINT_SIZE // If the position is out of map, nothing is done // Returns: void void setPoint(int x, int y, Uint32 color, SDL_Surface *map) { int i,j; for(i=-POINT_SIZE;i<=POINT_SIZE;i++) for(j=-POINT_SIZE;j<=POINT_SIZE;j++) setPixel(x+i, y+j, color, map); } Tracer une droite anti-aliasée

On va enfin appliquer le principe d'anticrénelage que l'on a vu précédemment pour tracer une droite.

Le petit point épineux que je vous avais caché jusque-là (eh oui, sinon cela serait bien trop simple…), c'est que la méthode que j'ai présentée en haut (sur 2 pixels), ne marche que pour une pente inférieure à 45° ! :-°

Pourquoi ? Eh bien regardez avec attention l'image que j'avais présentée (je la remets) :

La droite a une pente < 45° et les 2 pixels sont verticaux…
Si la pente est > 45° (rotation de 90° de mon image), mes 2 pixels devront être horizontaux !

Donc, chaque fois que vous voudrez anti-aliaser quelque chose, il faudra toujours faire attention à la pente, ou autrement dit à la dérivée : toujours une dérivée inférieure à 1 (en valeur absolue).

D'où les 2 cas suivants pour notre droite :

void line_trace(int x1, int y1, int x2, int y2, Uint32 color, SDL_Surface *map) { int xd, yd; xd = (x2-x1); yd = (y2-y1); if (abs(xd) > abs(yd)) // The line angle is smaller than 45° { ... } else { ... }

Pour anti-aliaser, vous avez vu qu'il faut la partie après la virgule pour en déduire le pourcentage de couleur de chaque pixel… Pour éviter de réécrire plusieurs fois le même code, voici quelques petites fonctions de mise en bouche qui retournent la fraction ou 1 - la fraction (prenez-les comme telles, c'est cadeau, on va voir leur utilité dans un instant - quel suspense tout de même !).

// Switchs the values of the x and y integers // Returns: void void int_switch(int* x, int* y) { int t = *x; *x = *y; *y = t; } // Returns the fractionary part of the x float // Returns: the frav value (float) [0,1] float frac(float x) { return x - (int)x; } // Returns the missing part to 1 from the fract. part of the x float // Returns: the invfrac value (float) [0,1] float invfrac(float x) { return 1 - frac(x); }

Et enfin, la partie à proprement parler d'anti-aliasing, où il va vous falloir :

• récupérer les composantes de la couleur du trait ;

• récupérer les composantes de la couleur du fond actuel (x;y) ;

• calculer la couleur en fonction de chacun des pourcentages ;

• blitter les 2 pixels.

Alors à partir de maintenant, vous devriez y arriver tout seuls ; comme je suis vraiment trop bon, je vous tiens vraiment la main jusqu'au bout… mais revers de la médaille, cela va peut-être être un peu redondant pour certains !

Récupérer les composantes de la couleur du trait

On a vu la fonction dans l'intro, mais pour ceux qui auraient déja oublié, il s'agit de SDL_GetRGBA…

// Getting the r,g,b,a values of the specified color SDL_GetRGBA(color,map->format,&r1,&g1,&b1,&a1); Récupérer les composantes de la couleur du fond actuel (x;y)

On a créé la fonction juste avant (si, si : pour ceux qui dorment dans le fond, dans l'intro !), donc jusque-là tout va bien !

// Getting the color of current (background) pixel getPixelColor(x, (int)yf, map, &r2,&g2,&b2,&a2); Calcul de la couleur en fonction de chacun des pourcentages + "blittage"

Comme nous l'avons vu sur le petit dessin, il faut utiliser 2 pixels côte à côte. Prenons un exemple : mon pixel devrait tomber à une position en y de 56.38 (x quelconque), on va donc travailler avec les pixels 56 et 57.

Sur mon pixel 56, je vais appliquer 38 % (soit 0.38 en channel alpha) de couleur du trait et, comme il faut bien compléter à 100 %, 1-0.38 = 0.62 de couleur de fond. Puis on mixe les 2. Pour mixer les 2, on utilise une fonction de la SDL qui à partir des composantes RGBA donne la couleur (l'inverse de SDL_GetRGBA), qui est… tada ! : SDL_MapRGBA (eh oui, même pas SDL_SetRGBA… Comme quoi, même en informatique, y a du suspense !).

Sur mon pixel 57, je vais appliquer 1-0.38 soit 0.62 de couleur du trait (comme ça, j'ai toujours 100 % de la couleur du trait) et, comme il faut bien compléter à 100 % la couleur du pixel , 1-0.62 = 0.38 de couleur de fond. Puis on mixe les 2.

Avec une formule mathématique, on aurait :

Citation : Mathématiques

$frac_y = y - E(y)$
(partie fractionnaire, avec E() partie entière !).

$couleur(x;E(y)) = couleur1(x;E(y)).frac_y+ couleur2(x;E(y)).(1-frac_y)$
(la fraction de la couleur 1 et le complément pour la couleur 2).

$couleur(x;E(y)+1) = couleur1(x;E(y)+1).(1-frac_y)+ couleur2(x;E(y)+1).frac_y$
(le complément de la couleur 1 utilisée ci-dessus puis le complément pour la couleur 2).

Et pour finir, on set les 2 pixels (avec la fonction maison codée avant !).

Bon : cette fois, je ne cache pas le code, car c'est un peu plus compliqué ! ;)

// For the antialising 2 pixels are drawn, one on top (x,y+1), the other below (x,y) // The color is a mix of: // - the color of background // - the color of the line // The amount of each color (bg & line color), on the 2 pixels is 100% (e.g. 10% on one, 90% on the other) r=(Uint8)(frac(yf)*r1+invfrac(yf)*r2); g=(Uint8)(frac(yf)*g1+invfrac(yf)*g2); b=(Uint8)(frac(yf)*b1+invfrac(yf)*b2); a=(Uint8)(frac(yf)*a1+invfrac(yf)*a2); colorAA1=SDL_MapRGBA(map->format,r,g,b,a); // Color for pixel one (x,y+1) r=(Uint8)(frac(yf)*r2+invfrac(yf)*r1); g=(Uint8)(frac(yf)*g2+invfrac(yf)*g1); b=(Uint8)(frac(yf)*b2+invfrac(yf)*b1); a=(Uint8)(frac(yf)*a2+invfrac(yf)*a1); colorAA2=SDL_MapRGBA(map->format,r,g,b,a); // Color for the 2nd pixel (x,y) // Blitting setPixel(x, (int)yf, colorAA2, map); setPixel(x, (int)yf+1, colorAA1, map);

À présent, reste à trouver la quantité de couleur (le frac(yf) dans le bout de code au-dessus) ; c'est le 0.38 dans l'exemple… En fait, tout simplement, on part de notre condition de départ, à savoir x = x1 et y = y1, et, dans la boucle suivante, on cherche à savoir quelles coordonnées devront avoir ces points…

Pour x, c'est facile, c'est x+1, mais pour y ? Toujours la dérivée ! y => y+grad, où grad est la pente.

Il ne reste plus qu'à coder le tout !

Vous avez cherché ? Alors voilà, au final, en bouclant, ce qu'on obtient.

// Traces an antialiased line from x1,y1 to x2,y2 on the specified color, on the map, with the dotted method // Returns: void void line_trace(int x1, int y1, int x2, int y2, Uint32 color, SDL_Surface *map, int dotted) { int xd, yd, x, y, to_dot = 0; float grad,xf,yf; Uint8 r1,g1,b1,a1,r2,g2,b2,a2,r,g,b,a; Uint32 colorAA1,colorAA2; // Getting the r,g,b,a values of the specified color SDL_GetRGBA(color,map->format,&r1,&g1,&b1,&a1); xd = (x2-x1); yd = (y2-y1); if (abs(xd) > abs(yd)) // The line angle is smaller than 45° { if (x1 > x2) // Because of the FOR, going from the smallest to the greatest value { int_switch(&x1, &x2); int_switch(&y1, &y2); xd = (x2-x1); yd = (y2-y1); } grad = (float)yd/(float)xd; // Line slope yf = (float)y1+grad; // Start and arrival points setPixel(x1, y1, color, map); setPixel(x2, y2, color, map); for (x = x1+1; x <= x2; x++) { if((!dotted || (to_dot%dotted)) && x>0 && x<map->w && yf>0 && yf<map->h) // If not outside of the map surface { // Getting the color of current (background) pixel getPixelColor(x, (int)yf, map, &r2,&g2,&b2,&a2); // For the antialising 2 pixels are drawn, one one top (x,y+1), the other below (x,y) // The color is a mix of: // - the color of background // - the color of the line // The amount of each color (bg & line color), on the 2 pixels is 100% (e.g. 10% on one, 90% on the other) r=(Uint8)(frac(yf)*r1+invfrac(yf)*r2); g=(Uint8)(frac(yf)*g1+invfrac(yf)*g2); b=(Uint8)(frac(yf)*b1+invfrac(yf)*b2); a=(Uint8)(frac(yf)*a1+invfrac(yf)*a2); colorAA1=SDL_MapRGBA(map->format,r,g,b,a); // Color for pixel one (x,y+1) r=(Uint8)(frac(yf)*r2+invfrac(yf)*r1); g=(Uint8)(frac(yf)*g2+invfrac(yf)*g1); b=(Uint8)(frac(yf)*b2+invfrac(yf)*b1); a=(Uint8)(frac(yf)*a2+invfrac(yf)*a1); colorAA2=SDL_MapRGBA(map->format,r,g,b,a); // Color for the 2nd pixel (x,y) // Blitting setPixel(x, (int)yf, colorAA2, map); setPixel(x, (int)yf+1, colorAA1, map); } to_dot++; yf += grad; // Go to next point (x => x+1 / yf => yf + grad) } } else // Same thing if the line angle is greater the 45° { if (y1 > y2) { int_switch(&x1, &x2); int_switch(&y1, &y2); xd = (x2-x1); yd = (y2-y1); } grad = (float)xd/(float)yd; xf = (float)x1+grad; setPixel(x1, y1, color, map); setPixel(x2, y2, color, map); for (y = y1+1; y <= y2; y++) { if((!dotted || (to_dot%dotted)) && xf>0 && xf<map->w && y>0 && y<map->h) { getPixelColor((int)xf, y, map, &r2,&g2,&b2,&a2); r=(Uint8)(frac(xf)*r1+invfrac(xf)*r2); g=(Uint8)(frac(xf)*g1+invfrac(xf)*g2); b=(Uint8)(frac(xf)*b1+invfrac(xf)*b2); a=(Uint8)(frac(xf)*a1+invfrac(xf)*a2); colorAA1=SDL_MapRGBA(map->format,r,g,b,a); r=(Uint8)(frac(xf)*r2+invfrac(xf)*r1); g=(Uint8)(frac(xf)*g2+invfrac(xf)*g1); b=(Uint8)(frac(xf)*b2+invfrac(xf)*b1); a=(Uint8)(frac(xf)*a2+invfrac(xf)*a1); colorAA2=SDL_MapRGBA(map->format,r,g,b,a); setPixel((int)xf, y, colorAA2, map); setPixel((int)xf+1, y, colorAA1, map); } ...