Tracé de ligne anti-aliasé 1/2

Par David CHARDONNET le 2 Mars 2010

Introduction

Voici le premier article de mon blog que je dédie aux diverses techniques de programmation. Nous allons utiliser le langage Pascal de Delphi pour illustrer notre propos, mais comme il est autant question d’algorithmique ici que de code, cette application peut se retranscrire en tout autre langage.

Le problème à résoudre

Nous allons nous intéresser ici à un problème que je rencontre dans le rafraîchissement d’un ancien logiciel freeware que j’avais développé en Delphi il y a quelques années: Brazil Fractal Builder. Ce logiciel permet de construire des objets fractals de type IFS. En clair ça vous permet de concevoir des dessins qui respectent la géométrie fractale, avec un assez bon niveau de contrôle sur ce que vous faites. C’est un peu comme du Lego à l’utilisation, on manipule des carrés qui sont des briques de base de la construction.

Voilà quelques exemples d’objets fractals IFS, parce qu’un bon dessin ça en dit toujours plus long qu’un terme en jargon incompréhensible:

Et il se trouve que pour dessiner ces trois images, on conçoit des cartes de transformations avec le concepteur, et les trois cartes de transformations correspondant respectivement aux images précédentes ressemblent à ceci:

Et c’est au niveau des cartes de transformations que je souhaite améliorer l’affichage. En effet lorsqu’on agrandit les cartes de transformation, la routine de tracé de lignes que j’utilise est basique et fait du crénelage (aussi appelé aliasing en anglais), ce qui nuit à l’esthétique du dessin. Voyez vous-même (cliquez sur l’image pour voir la brisure des lignes):

Début de solution

J’ai donc décidé d’implémenter une routine de tracé de ligne anti-aliasé dans ma bibliothèque graphique. Je ne veux pas réinventer la roue, donc, en faisant quelques recherches sur le web, j’ai trouvé quelques algorithmes, mais c’est plus particulièrement l’algorithme de tracé de segment de Xiaolin Wu, qui dispose d’un article sur Wikipédia avec du pseudo-code qui m’intéresse. Il a l’air d’être rapide, selon les informations que je dispose, et le clavier commence à me démanger rien que d’y penser.

Pseudo-code:

  1. function plot(x, y, c) is
  2. plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)
  3.  
  4. function ipart(x) is
  5. return integer part of x
  6.  
  7. function round(x) is
  8. return ipart(x + 0.5)
  9.  
  10. function fpart(x) is
  11. return fractional part of x
  12.  
  13. function rfpart(x) is
  14. return 1 – fpart(x)
  15.  
  16. function drawLine(x1,y1,x2,y2) is
  17. dx = x2 – x1
  18. dy = y2 – y1
  19. if abs(dx) < abs(dy) then
  20. swap x1, y1
  21. swap x2, y2
  22. end if
  23. if x2 < x1
  24. swap x1, x2
  25. swap y1, y2
  26. end if
  27. gradient = dy / dx
  28. // handle first endpoint
  29. xend = round(x1)
  30. yend = y1 + gradient * (xend – x1)
  31. xgap = rfpart(x1 + 0.5)
  32. xpxl1 = xend  // this will be used in the main loop
  33. ypxl1 = ipart(yend)
  34. plot(xpxl1, ypxl1, rfpart(yend) * xgap)
  35. plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap)
  36. intery = yend + gradient // first y-intersection for the main loop
  37. // handle second endpoint
  38. xend = round (x2)
  39. yend = y2 + gradient * (xend – x2)
  40. xgap = fpart(x2 + 0.5)
  41. xpxl2 = xend  // this will be used in the main loop
  42. ypxl2 = ipart (yend)
  43. plot (xpxl2, ypxl2, rfpart (yend) * xgap)
  44. plot (xpxl2, ypxl2 + 1, fpart (yend) * xgap)
  45. // main loop
  46. for x from xpxl1 + 1 to xpxl2 – 1 do
  47. plot (x, ipart (intery), rfpart (intery))
  48. plot (x, ipart (intery) + 1, fpart (intery))
  49. intery = intery + gradient
  50. end function

On trouve aussi l’information suivante sur Wikipédia:

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.

Au boulot!

Cet algorithme nécessite quelques adaptations pour pouvoir répondre à tous les cas de figure d’un tracé de ligne comme celui que je souhaite utiliser. En effet, il s’agit d’un algorithme élémentaire auquel il manque

Nous détaillerons ces points un peu plus loin….

Première traduction brute du code en Pascal:

  1. //****************************************************************************
  2. //
  3. //
  4. //
  5. //****************************************************************************
  6. function wu_ipart(x:double):integer;
  7. begin
  8.   result := floor(x);
  9. end;
  10.  
  11. //****************************************************************************
  12. //
  13. //
  14. //
  15. //****************************************************************************
  16. function wu_fpart(x:double):double;
  17. begin
  18.   result := frac(x);
  19. end;
  20.  
  21. //****************************************************************************
  22. //
  23. //
  24. //
  25. //****************************************************************************
  26. function wu_rfpart(x:double):double;
  27. begin
  28.   result := 1 – wu_fpart(x);
  29. end;
  30.  
  31. //****************************************************************************
  32. //
  33. //
  34. //
  35. //****************************************************************************
  36. procedure wu_swap(var a:integer;var b:integer);
  37. var temp:integer;
  38. begin
  39.   temp:=a;
  40.   a:=b;
  41.   b:=temp;
  42. end;
  43.  
  44. //****************************************************************************
  45. //
  46. //
  47. //
  48. //****************************************************************************
  49. function wu_round(x:double):integer;
  50. begin
  51.   result := floor(x + 0.5);
  52. end;
  53.  
  54. //****************************************************************************
  55. //
  56. // Pour le test, on a utilisé du noir sur un fond blanc alors que dans la
  57. // logique de l’algorithme le parametre c est la luminosité ce qui dénote
  58. // une logique de blanc sur fond noir c’est pour ça qu’on utilise (1.0-c)
  59. // et on multiplie ensuite par 255 pour obtenir une valeur octet [0;255]
  60. //
  61. //****************************************************************************
  62. procedure CHiColor.wu_plot(x, y:integer; c:double);
  63. var coul:byte;
  64. begin
  65.   coul:=floor(255.0*(1.0-c));
  66.   putpixel(x,y,coul,coul,coul);
  67. end;
  68.  
  69. //****************************************************************************
  70. //
  71. //  Fonction qui permet de tracer les lignes "presque horizontales"
  72. //
  73. //****************************************************************************
  74. procedure CHiColor.wu_drawLine(x1,y1,x2,y2:integer);
  75. var dx:double;
  76.     dy:double;
  77.     gradient:double;
  78.     xend:double;
  79.     yend:double;
  80.     xgap:double;
  81.     xpxl1:integer;
  82.     ypxl1:integer;
  83.     xpxl2:integer;
  84.     ypxl2:integer;
  85.     intery:double;
  86.     x:integer;
  87. begin
  88.   dx := x2 – x1;
  89.   dy := y2 – y1;
  90.   if (abs(dx) > abs(dy)) then       // Test inversé car
  91.   begin                             //
  92.     //  wu_swap(x1,y1);             // ce code ne fonctionne pas
  93.     //  wu_swap(x2,y2);             // on conserve uniquement le code qui
  94.     //end;                          // fonctionne
  95.     if (x2 < x1) then
  96.     begin
  97.       wu_swap(x1,x2);
  98.       wu_swap(y1,y2);
  99.     end;
  100.     gradient := dy / dx;
  101.  
  102.     // handle first endpoint
  103.  
  104.     xend := wu_round(x1);
  105.     yend := y1 + gradient * (xend – x1);
  106.     xgap := wu_rfpart(x1 + 0.5);
  107.     xpxl1 := round(xend);  // this will be used in the main loop
  108.     ypxl1 := wu_ipart(yend);
  109.     wu_plot(xpxl1, ypxl1, wu_rfpart(yend) * xgap);
  110.     wu_plot(xpxl1, ypxl1 + 1, wu_fpart(yend) * xgap);
  111.     intery := yend + gradient; // first y-intersection for the main loop
  112.  
  113.     // handle second endpoint
  114.  
  115.     xend := round (x2);
  116.     yend := y2 + gradient * (xend – x2);
  117.     xgap := wu_fpart(x2 + 0.5);
  118.     xpxl2 := round(xend);  // this will be used in the main loop
  119.     ypxl2 := wu_ipart (yend);
  120.     wu_plot (xpxl2, ypxl2, wu_rfpart (yend) * xgap);
  121.     wu_plot (xpxl2, ypxl2 + 1, wu_fpart (yend) * xgap);
  122.  
  123.     // main loop
  124.     for x := xpxl1 + 1 to xpxl2 – 1 do
  125.     begin
  126.       wu_plot (x, wu_ipart (intery), wu_rfpart (intery));
  127.       wu_plot (x, wu_ipart (intery) + 1, wu_fpart (intery));
  128.       intery := intery + gradient;
  129.     end;
  130.   end;
  131. end;

Dans ce code on retrouve strictement les noms des fonctions et les noms de variables du code d’origine. Seulement, après test, il s’avère qu’une partie du code n’est pas fonctionnelle et elle a été retirée. tous les noms de fonction ont été préfixés par « wu_ » afin de les différencier des fonctions déjà existantes dans Delphi (par exemple round() existe déjà dans Delphi, il fallait les différencier).

Le nom de la classe de ma librairie graphique est CHiColor, et on utilise la méthode putpixel qui affiche un point de couleur.

Premier test de la fonction

  1. procedure TForm1.Button1Click(Sender: TObject);
  2. var i:integer;
  3. begin
  4.   HiColor.nettoyer_et_afficher(255,255,255);
  5.  
  6.   // L’ancienne fonction de dessin de ligne
  7.   HiColor.Line(10,10,100,30,0,0,0);
  8.  
  9.   // Presque horizontal
  10.   HiColor.wu_drawLine(10,15,100,35);
  11.  
  12.   HiColor.afficher;
  13. end;

A l’exécution de ce test on obtient l’affichage suivant (après zoom):

On peut constater que l’effet d’escalier de la ligne du dessus n’est plus présent dans la ligne du dessous. L’algorithme fonctionne donc. C’est encourageant, mais on est limité aux lignes « presques horizontales ».

Presque vertical

C’est le moment de se servir de la recommandation de wikipédia:

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.

On rectifie donc le code de la procédure de cette façon:

  1. //****************************************************************************
  2. //
  3. //
  4. //
  5. //****************************************************************************
  6. function wu_rfpart(x:double):double;
  7. begin
  8.   result := 1frac(x);
  9. end;
  10.  
  11. //****************************************************************************
  12. //
  13. //
  14. //
  15. //****************************************************************************
  16. procedure wu_swap(var a:integer;var b:integer);
  17. var temp:integer;
  18. begin
  19.   temp:=a;
  20.   a:=b;
  21.   b:=temp;
  22. end;
  23.  
  24. //****************************************************************************
  25. //
  26. //
  27. //
  28. //****************************************************************************
  29. function wu_round(x:double):integer;
  30. begin
  31.   result := floor(x + 0.5);
  32. end;
  33.  
  34. //****************************************************************************
  35. //
  36. // Pour le test, on a utilisé du noir sur un fond blanc alors que dans la
  37. // logique de l’algorithme le parametre c est la luminosité ce qui dénote
  38. // une logique de blanc sur fond noir c’est pour ça qu’on utilise (1.0-c)
  39. // et on multiplie ensuite par 255 pour obtenir une valeur octet [0;255]
  40. //
  41. //****************************************************************************
  42. procedure CHiColor.wu_plot(x, y:integer; c:double);
  43. var coul:byte;
  44. begin
  45.   coul:=floor(255.0*(1.0-c));
  46.   putpixel(x,y,coul,coul,coul);
  47. end;
  48.  
  49. //****************************************************************************
  50. //
  51. //  Fonction qui permet de tracer les lignes noires anti-aliasées sur un fond blanc
  52. //
  53. //****************************************************************************
  54. procedure CHiColor.wu_drawLine(x1,y1,x2,y2:integer);
  55. var dx:double;
  56.     dy:double;
  57.     gradient:double;
  58.     xend:double;
  59.     yend:double;
  60.     xgap:double;
  61.     ygap:double;
  62.     xpxl1:integer;
  63.     ypxl1:integer;
  64.     xpxl2:integer;
  65.     ypxl2:integer;
  66.     interx:double;
  67.     intery:double;
  68.     x:integer;
  69.     y:integer;
  70. begin
  71.   dx := x2 – x1;
  72.   dy := y2 – y1;
  73.   if (abs(dx) > abs(dy)) then
  74.   begin
  75.     //——————–
  76.     // Presque horizontal
  77.     //——————–
  78.     if (x2 < x1) then
  79.     begin
  80.       wu_swap(x1,x2);
  81.       wu_swap(y1,y2);
  82.     end;
  83.     gradient := dy / dx;
  84.  
  85.     // handle first endpoint
  86.  
  87.     xend := wu_round(x1);
  88.     yend := y1 + gradient * (xend – x1);
  89.     xgap := wu_rfpart(x1 + 0.5);
  90.     xpxl1 := round(xend);  // this will be used in the main loop
  91.     ypxl1 := floor(yend);
  92.     wu_plot(xpxl1, ypxl1, wu_rfpart(yend) * xgap);
  93.     wu_plot(xpxl1, ypxl1 + 1, frac(yend) * xgap);
  94.     intery := yend + gradient; // first y-intersection for the main loop
  95.  
  96.     // handle second endpoint
  97.  
  98.     xend := round (x2);
  99.     yend := y2 + gradient * (xend – x2);
  100.     xgap := frac(x2 + 0.5);
  101.     xpxl2 := round(xend);  // this will be used in the main loop
  102.     ypxl2 := floor(yend);
  103.     wu_plot (xpxl2, ypxl2    , wu_rfpart (yend) * xgap);
  104.     wu_plot (xpxl2, ypxl2 + 1, frac  (yend) * xgap);
  105.  
  106.     // main loop
  107.     for x := xpxl1 + 1 to xpxl2 – 1 do
  108.     begin
  109.       wu_plot (x, floor (intery)    , wu_rfpart (intery));
  110.       wu_plot (x, floor (intery) + 1, frac  (intery));
  111.       intery := intery + gradient;
  112.     end;
  113.   end
  114.   else
  115.   begin
  116.     //——————
  117.     // Presque vertical
  118.     //——————
  119.     if ( y2 < y1 ) then
  120.     begin
  121.       wu_swap(x1, x2);
  122.       wu_swap(y1, y2);
  123.     end;
  124.  
  125.     gradient := dx / dy;
  126.  
  127.     // handle first endpoint
  128.  
  129.     yend := wu_round(y1);
  130.     xend := x1 + gradient*(yend – y1);
  131.     ygap := wu_rfpart(y1 + 0.5);
  132.     ypxl1 := round(yend);    // this will be used in the main loop
  133.     xpxl1 := floor(xend);
  134.     wu_plot(xpxl1, ypxl1    , wu_rfpart (xend) * ygap);
  135.     wu_plot(xpxl1, ypxl1 + 1, frac  (xend) * ygap);
  136.     interx := xend + gradient;    // first x-intersection for the main loop
  137.  
  138.      // handle second endpoint
  139.  
  140.     yend := wu_round(y2);
  141.     xend := x2 + gradient*(yend – y2);
  142.     ygap := frac(y2 + 0.5);
  143.     ypxl2 := round(yend);   // this will be used in the main loop
  144.     xpxl2 := floor(xend);
  145.     wu_plot(xpxl2, ypxl2    , wu_rfpart (xend) * ygap);
  146.     wu_plot(xpxl2, ypxl2 + 1, frac  (xend) * ygap);
  147.  
  148.     // main loop
  149.     for y := ypxl1 + 1 to ypxl2 – 1 do
  150.     begin
  151.       wu_plot(floor(interx)    , y, wu_rfpart (interx));
  152.       wu_plot(floor(interx) + 1, y, frac  (interx));
  153.       interx := interx + gradient;
  154.     end;
  155.   end;
  156. end;

On a rajouté un bloc de code pour gérer les lignes presque verticales.

Vous noterez par ailleurs que j’ai éliminé les fonctions wu_fpart et wu_ipart pour les remplacer par les fonctions frac et floor dans le code.

Après test, on obtient ce résultat:

La couleur et le respect du fond

Vous admettrez qu’une touche de couleur nous ferait le plus grand bien. Mais il faut aussi penser qu’avec ce système de dessin, le fond de l’image n’est pas respecté. Voyez ce test sur un fond rouge:

Donc pour être tout-terrain, notre fonction doit prendre en compte la ou les couleurs du fond sur lequel elle est utilisée. On va donc porter l’accent sur la fonction wu_plot qui est la clé du problème.

  1. //****************************************************************************
  2. //
  3. //
  4. //
  5. //
  6. //
  7. //
  8. //****************************************************************************
  9. procedure CHiColor.wu_plot(x, y:integer; c:double;r,v,b:byte);
  10. var resultat_r,resultat_v,resultat_b:byte;
  11.     fond_r,fond_v,fond_b:byte;
  12. begin
  13.   // On lit la couleur du pixel sur lequel on va dessiner
  14.   getpixel(x,y,fond_r,fond_v,fond_b);
  15.  
  16.   // On calcule le mélange des couleurs du fond et de la ligne
  17.   resultat_r:=floor(fond_r*(1.0-c)+c*r);
  18.   resultat_v:=floor(fond_v*(1.0-c)+c*v);
  19.   resultat_b:=floor(fond_b*(1.0-c)+c*b);
  20.  
  21.   putpixel(x,y,resultat_r,resultat_v,resultat_b);
  22. end;
  23.  
  24. //****************************************************************************
  25. //
  26. //  Fonction
  27. //
  28. //——————————————————————————
  29. procedure CHiColor.wu_drawLineX(x1,y1,x2,y2:integer;r,v,b:byte);
  30. var dx:double;
  31.     dy:double;
  32.     gradient:double;
  33.     xend:double;
  34.     yend:double;
  35.     xgap:double;
  36.     ygap:double;
  37.     xpxl1:integer;
  38.     ypxl1:integer;
  39.     xpxl2:integer;
  40.     ypxl2:integer;
  41.     interx:double;
  42.     intery:double;
  43.     x:integer;
  44.     y:integer;
  45. begin
  46.   dx := x2 – x1;
  47.   dy := y2 – y1;
  48.   if (abs(dx) > abs(dy)) then
  49.   begin
  50.     //——————–
  51.     // Presque horizontal
  52.     //——————–
  53.     if (x2 < x1) then
  54.     begin
  55.       wu_swap(x1,x2);
  56.       wu_swap(y1,y2);
  57.     end;
  58.     gradient := dy / dx;
  59.  
  60.     // handle first endpoint
  61.  
  62.     xend := wu_round(x1);
  63.     yend := y1 + gradient * (xend – x1);
  64.     xgap := wu_rfpart(x1 + 0.5);
  65.     xpxl1 := round(xend);  // this will be used in the main loop
  66.     ypxl1 := floor(yend);
  67.     wu_plot(xpxl1, ypxl1, wu_rfpart(yend) * xgap,r,v,b);
  68.     wu_plot(xpxl1, ypxl1 + 1, frac(yend) * xgap,r,v,b);
  69.     intery := yend + gradient; // first y-intersection for the main loop
  70.  
  71.     // handle second endpoint
  72.  
  73.     xend := round (x2);
  74.     yend := y2 + gradient * (xend – x2);
  75.     xgap := frac(x2 + 0.5);
  76.     xpxl2 := round(xend);  // this will be used in the main loop
  77.     ypxl2 := floor(yend);
  78.     wu_plot (xpxl2, ypxl2    , wu_rfpart (yend) * xgap,r,v,b);
  79.     wu_plot (xpxl2, ypxl2 + 1, frac  (yend) * xgap,r,v,b);
  80.  
  81.     // main loop
  82.     for x := xpxl1 + 1 to xpxl2 – 1 do
  83.     begin
  84.       wu_plot (x, floor (intery)    , wu_rfpart (intery),r,v,b);
  85.       wu_plot (x, floor (intery) + 1, frac  (intery),r,v,b);
  86.       intery := intery + gradient;
  87.     end;
  88.   end
  89.   else
  90.   begin
  91.     //——————
  92.     // Presque vertical
  93.     //——————
  94.     if ( y2 < y1 ) then
  95.     begin
  96.       wu_swap(x1, x2);
  97.       wu_swap(y1, y2);
  98.     end;
  99.  
  100.     gradient := dx / dy;
  101.  
  102.     // handle first endpoint
  103.  
  104.     yend := wu_round(y1);
  105.     xend := x1 + gradient*(yend – y1);
  106.     ygap := wu_rfpart(y1 + 0.5);
  107.     ypxl1 := round(yend);    // this will be used in the main loop
  108.     xpxl1 := floor(xend);
  109.     wu_plot(xpxl1, ypxl1    , wu_rfpart (xend) * ygap,r,v,b);
  110.     wu_plot(xpxl1, ypxl1 + 1, frac  (xend) * ygap,r,v,b);
  111.     interx := xend + gradient;    // first x-intersection for the main loop
  112.  
  113.      // handle second endpoint
  114.  
  115.     yend := wu_round(y2);
  116.     xend := x2 + gradient*(yend – y2);
  117.     ygap := frac(y2 + 0.5);
  118.     ypxl2 := round(yend);   // this will be used in the main loop
  119.     xpxl2 := floor(xend);
  120.     wu_plot(xpxl2, ypxl2    , wu_rfpart (xend) * ygap,r,v,b);
  121.     wu_plot(xpxl2, ypxl2 + 1, frac  (xend) * ygap,r,v,b);
  122.  
  123.     // main loop
  124.     for y := ypxl1 + 1 to ypxl2 – 1 do
  125.     begin
  126.       wu_plot(floor(interx)    , y, wu_rfpart (interx),r,v,b);
  127.       wu_plot(floor(interx) + 1, y, frac  (interx),r,v,b);
  128.       interx := interx + gradient;
  129.     end;
  130.   end;
  131. end;

Vous pouvez constater qu’on a rajouté dans wu_plot:

Le paramètre c jouant sur l’intensité de la couleur de la ligne sur le pixel concerné:

Un petit test, en variant la couleur de fond nous prouve le bon fonctionnement de tout ça:

Voir la suite – Tracé de ligne anti-aliasé 2/2

Si vous avez apprécié cet article, s'il vous plait, prenez le temps de laisser un commentaire ou de souscrire au flux afin de recevoir les futurs articles directement dans votre lecteur de flux.

Commentaires

[...] Voir le début de l’article – Tracé de ligne anti-aliasé 1/2 [...]

Laisser un commentaire

(requis)

(requis)