1

Tracé de ligne anti-aliasé 1/2

Posté par admin
le 2 mars, 2010

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 := 1 – frac(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

Graphisme
0

Tracé de ligne anti-aliasé 2/2

Posté par admin
le 2 mars, 2010

Par David CHARDONNET le 2 Mars 2010

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

Est-on satisfait de notre code?

Eh bien non, pas tout à fait si on y regarde de plus près. Il y a deux cas aux limites qui n’ont pas été vérifiés: lorsque les lignes sont horizontales ou verticales. Et dans ce cas, on commet le pire: la division par zéro!! Et là, c’est le drame, votre programme plante, et l’utilisateur a un message qu’il ne comprend pas, et déteste encore plus son ordinateur.

Cette petite négligence nous donne l’opportunité d’améliorer sensiblement les performances de notre algorithme pour ces deux cas aux limites.

  1. //********************************************************************
  2. //
  3. //  Fonction de tracé de pixel avec transparence (alpha-blending)
  4. //
  5. //********************************************************************
  6. procedure CHiColor.putpixel_alpha(x, y:integer; alpha:double;r,v,b:byte);
  7. var resultat_r,resultat_v,resultat_b:byte;
  8.     fond_r,fond_v,fond_b:byte;
  9. begin
  10.   // On lit la couleur du pixel sur lequel on va dessiner
  11.   getpixel(x,y,fond_r,fond_v,fond_b);
  12.  
  13.   // On calcule le mélange des couleurs du fond et de la ligne
  14.   resultat_r:=floor(fond_r*(1.0-alpha)+alpha*r);
  15.   resultat_v:=floor(fond_v*(1.0-alpha)+alpha*v);
  16.   resultat_b:=floor(fond_b*(1.0-alpha)+alpha*b);
  17.  
  18.   putpixel(x,y,resultat_r,resultat_v,resultat_b);
  19. end;
  20.  
  21. //********************************************************************
  22. //
  23. //  Fonction de tracé de ligne anti-aliasee
  24. //  selon l’algorithme de  Xiaolin Wu
  25. //
  26. //********************************************************************
  27. procedure CHiColor.wu_drawLine(x1,y1,x2,y2:integer;r,v,b:byte);
  28. var dx:double;
  29.     dy:double;
  30.     gradient:double;
  31.     xend:double;
  32.     yend:double;
  33.     xgap:double;
  34.     ygap:double;
  35.     xpxl1:integer;
  36.     ypxl1:integer;
  37.     xpxl2:integer;
  38.     ypxl2:integer;
  39.     interx:double;
  40.     intery:double;
  41.     x:integer;
  42.     y:integer;
  43. begin
  44.   dx := x2 – x1;
  45.   dy := y2 – y1;
  46.   if (dx=0) then
  47.   begin
  48.     //—————–
  49.     // Ligne verticale
  50.     //—————–
  51.     for y:=min(y1,y2) to max(y1,y2) do
  52.     begin
  53.       putpixel(x1,y,r,v,b);
  54.     end;
  55.   end
  56.   else if (dy=0) then
  57.   begin
  58.     //——————-
  59.     // Ligne horizontale
  60.     //——————-
  61.     for x:=min(x1,x2) to max(x1,x2) do
  62.     begin
  63.       putpixel(x,y1,r,v,b);
  64.     end;
  65.   end
  66.   else
  67.   begin
  68.     if (abs(dx) > abs(dy)) then
  69.     begin
  70.       //——————–
  71.       // Presque horizontal
  72.       //——————–
  73.       if (x2 < x1) then
  74.       begin
  75.         wu_swap(x1,x2);
  76.         wu_swap(y1,y2);
  77.       end;
  78.       gradient := dy / dx;
  79.  
  80.       // premiere extremite
  81.  
  82.       xend := wu_round(x1);
  83.       yend := y1 + gradient * (xend – x1);
  84.       xgap := wu_rfpart(x1 + 0.5);
  85.       xpxl1 := round(xend);  // ceci sera utilisé dans la boucle principale
  86.       ypxl1 := floor(yend);
  87.       putpixel_alpha(xpxl1, ypxl1, wu_rfpart(yend) * xgap,r,v,b);
  88.       putpixel_alpha(xpxl1, ypxl1 + 1, frac(yend) * xgap,r,v,b);
  89.       intery := yend + gradient; // premiere intersection-y pour la boucle principale
  90.  
  91.       // seconde extremite
  92.  
  93.       xend := round (x2);
  94.       yend := y2 + gradient * (xend – x2);
  95.       xgap := frac(x2 + 0.5);
  96.       xpxl2 := round(xend);  // ceci sera utilisé dans la boucle principale
  97.       ypxl2 := floor(yend);
  98.       putpixel_alpha (xpxl2, ypxl2    , wu_rfpart (yend) * xgap,r,v,b);
  99.       putpixel_alpha (xpxl2, ypxl2 + 1, frac  (yend) * xgap,r,v,b);
  100.  
  101.       // boucle principale
  102.       for x := xpxl1 + 1 to xpxl2 – 1 do
  103.       begin
  104.         putpixel_alpha (x, floor (intery)    , wu_rfpart (intery),r,v,b);
  105.         putpixel_alpha (x, floor (intery) + 1, frac  (intery),r,v,b);
  106.         intery := intery + gradient;
  107.       end;
  108.     end
  109.     else
  110.     begin
  111.       //——————
  112.       // Presque vertical
  113.       //——————
  114.       if ( y2 < y1 ) then
  115.       begin
  116.         wu_swap(x1, x2);
  117.         wu_swap(y1, y2);
  118.       end;
  119.  
  120.       gradient := dx / dy;
  121.  
  122.       // premiere extremite
  123.  
  124.       yend := wu_round(y1);
  125.       xend := x1 + gradient*(yend – y1);
  126.       ygap := wu_rfpart(y1 + 0.5);
  127.       ypxl1 := round(yend);    // ceci sera utilisé dans la boucle principale
  128.       xpxl1 := floor(xend);
  129.       putpixel_alpha(xpxl1, ypxl1    , wu_rfpart (xend) * ygap,r,v,b);
  130.       putpixel_alpha(xpxl1, ypxl1 + 1, frac  (xend) * ygap,r,v,b);
  131.       interx := xend + gradient;    // premiere intersection-x pour la boucle principale
  132.  
  133.       // seconde extremite
  134.  
  135.       yend := wu_round(y2);
  136.       xend := x2 + gradient*(yend – y2);
  137.       ygap := frac(y2 + 0.5);
  138.       ypxl2 := round(yend);   // ceci sera utilisé dans la boucle principale
  139.       xpxl2 := floor(xend);
  140.       putpixel_alpha(xpxl2, ypxl2    , wu_rfpart (xend) * ygap,r,v,b);
  141.       putpixel_alpha(xpxl2, ypxl2 + 1, frac  (xend) * ygap,r,v,b);
  142.  
  143.       // boucle principale
  144.       for y := ypxl1 + 1 to ypxl2 – 1 do
  145.       begin
  146.         putpixel_alpha(floor(interx)    , y, wu_rfpart (interx),r,v,b);
  147.         putpixel_alpha(floor(interx) + 1, y, frac  (interx),r,v,b);
  148.         interx := interx + gradient;
  149.       end;
  150.     end;
  151.   end;
  152. end;

Donc vous constaterez que j’ai renommé la fonction wu_plot en putpixel_alpha, parce que dans un souci de clarté, il faut appeler les choses par leur nom. Et cette fonction nous fait bien un affichage de pixel en transparence donc en “alpha-blending”. Le paramètre c gérant la transparence, est renommé alpha. De cette façon, nous pourrons réutiliser cette fonction pour nos autres opérations transparentes.

On a aussi traité en particulier les lignes horizontales et verticales. Dans ce cas précis on n’a pas besoin d’alpha-blending, étant donné que l’on recouvre tous les pixels à 100%, on n’a pas d’effet d’escalier à gérer et on utilise alors putpixel qui sera dans ces conditions plus appropriée et plus rapide que wu_plot .

Optimisons

Vous savez sans doute que pour bien optimiser, on s’attaque en premier aux opérations qui se répètent le plus pour réduire leur temps d’exécution. C’est ce qu’on va faire ici avec la fonction qu’on utilise le plus: putpixel_alpha. On suppose que notre fonction putpixel est déjà optimisée.

On s’aperçoit qu’il est possible d’accélérer putpixel_alpha sur les formules de mélange:

La formule  fond_r*(1.0-alpha)+alpha*r utilise 2 multiplications une soustraction et une addition

Avec un peu d’algèbre de base on peut regrouper cette formule en  alpha*(r-fond_r)+fond_r qui utilise une multiplication une addition et une soustraction

On a alors économisé une multiplication, qui est, au niveau de microprocesseur, une opération plus coûteuse que les additions et soustractions.

Tout ça pour une multiplication me direz-vous? Oui mais n’oublions pas que sur le tracé d’une ligne nécessitant le tracé de 300 pixels par exemple, on aura économisé 300 multiplications juste pour cette ligne. Et puis en cette époque de surpuissance des matériels, il faut quand même savoir économiser les ressources machine, c’est aussi ça l’écologie.

  1. //********************************************************************
  2. //
  3. //  Fonction de tracé de pixel avec transparence (alpha-blending)
  4. //
  5. //********************************************************************
  6. procedure CHiColor.putpixel_alpha(x, y:integer; alpha:double;r,v,b:byte);
  7. var resultat_r,resultat_v,resultat_b:byte;
  8.     fond_r,fond_v,fond_b:byte;
  9. begin
  10.   // On lit la couleur du pixel sur lequel on va dessiner
  11.   getpixel(x,y,fond_r,fond_v,fond_b);
  12.  
  13.   // On calcule le mélange des couleurs du fond et de la ligne
  14.   resultat_r:=floor(alpha*(r-fond_r)+fond_r);
  15.   resultat_v:=floor(alpha*(v-fond_v)+fond_v);
  16.   resultat_b:=floor(alpha*(b-fond_b)+fond_b);
  17.  
  18.   putpixel(x,y,resultat_r,resultat_v,resultat_b);
  19. end;

Votre chef de projet veut encore optimiser??

Ah, les chefs, ils en veulent toujours trop, et ils ne vous donnent jamais assez de temps pour tout faire. Bon alors ce que je propose c’est qu’on rogne un peu sur la lisibilité du code et qu’on réintègre les petites fonctions à l’intérieur de la grosse. Ca épargnera quelques appels de fonctions ce qui aura pour effet de gagner quelques cycles machine ainsi que de réduire l’utilisation de la pile. C’est peu, mais une librairie, c’est toujours mieux lorsqu’elle est légère.

Les fonctions wu_rfpart wu_round, et wu_swap vont être éliminées. (pour les programmeurs en C ou C++, la fonction swap existe en natif, donc oubliez celle-là).


  1. //********************************************************************
  2. //
  3. //  Fonction de tracé de ligne anti-aliasee
  4. //  selon l’algorithme de  Xiaolin Wu
  5. //
  6. //********************************************************************
  7. procedure CHiColor.wu_drawLine(x1,y1,x2,y2:integer;r,v,b:byte);
  8. var dx:double;
  9.     dy:double;
  10.     gradient:double;
  11.     xend:double;
  12.     yend:double;
  13.     xgap:double;
  14.     ygap:double;
  15.     xpxl1:integer;
  16.     ypxl1:integer;
  17.     xpxl2:integer;
  18.     ypxl2:integer;
  19.     interx:double;
  20.     intery:double;
  21.     x:integer;
  22.     y:integer;
  23.     temp:integer;
  24. begin
  25.   dx := x2 – x1;
  26.   dy := y2 – y1;
  27.   if (dx=0) then
  28.   begin
  29.     //—————–
  30.     // Ligne verticale
  31.     //—————–
  32.     for y:=min(y1,y2) to max(y1,y2) do
  33.     begin
  34.       putpixel_notest(x1,y,r,v,b);
  35.     end;
  36.   end
  37.   else if (dy=0) then
  38.   begin
  39.     //——————-
  40.     // Ligne horizontale
  41.     //——————-
  42.     for x:=min(x1,x2) to max(x1,x2) do
  43.     begin
  44.       putpixel_notest(x,y1,r,v,b);
  45.     end;
  46.   end
  47.   else
  48.   begin
  49.     if (abs(dx) > abs(dy)) then
  50.     begin
  51.       //——————–
  52.       // Presque horizontal
  53.       //——————–
  54.       if (x2 < x1) then
  55.       begin
  56.         // Echange de x1 et x2
  57.         temp:=x1;
  58.         x1:=x2;
  59.         x2:=temp;
  60.         //————-
  61.         // Echange de y1 et y2
  62.         temp:=y1;
  63.         y1:=y2;
  64.         y2:=temp;
  65.       end;
  66.       gradient := dy / dx;
  67.  
  68.       // premiere extremite
  69.  
  70.       xend := floor(x1+0.5);
  71.       yend := y1 + gradient * (xend – x1);
  72.       xgap := (1.0-frac(x1 + 0.5));
  73.       xpxl1 := round(xend);  // ceci sera utilisé dans la boucle principale
  74.       ypxl1 := floor(yend);
  75.       putpixel_alpha(xpxl1, ypxl1, (1.0-frac(yend)) * xgap,r,v,b);
  76.       putpixel_alpha(xpxl1, ypxl1 + 1, frac(yend) * xgap,r,v,b);
  77.       intery := yend + gradient; // premiere intersection-y pour la boucle principale
  78.  
  79.       // seconde extremite
  80.  
  81.       xend := round (x2);
  82.       yend := y2 + gradient * (xend – x2);
  83.       xgap := frac(x2 + 0.5);
  84.       xpxl2 := round(xend);  // ceci sera utilisé dans la boucle principale
  85.       ypxl2 := floor(yend);
  86.       putpixel_alpha (xpxl2, ypxl2    , (1.0-frac(yend)) * xgap,r,v,b);
  87.       putpixel_alpha (xpxl2, ypxl2 + 1, frac(yend) * xgap,r,v,b);
  88.  
  89.       // boucle principale
  90.       for x := xpxl1 + 1 to xpxl2 – 1 do
  91.       begin
  92.         putpixel_alpha (x, floor (intery)    , 1.0-frac(intery),r,v,b);
  93.         putpixel_alpha (x, floor (intery) + 1,   frac(intery),r,v,b);
  94.         intery := intery + gradient;
  95.       end;
  96.     end
  97.     else
  98.     begin
  99.       //——————
  100.       // Presque vertical
  101.       //——————
  102.       if ( y2 < y1 ) then
  103.       begin
  104.         // Echange de x1 et x2
  105.         temp:=x1;
  106.         x1:=x2;
  107.         x2:=temp;
  108.         //————-
  109.         // Echange de y1 et y2
  110.         temp:=y1;
  111.         y1:=y2;
  112.         y2:=temp;
  113.       end;
  114.  
  115.       gradient := dx / dy;
  116.  
  117.       // premiere extremite
  118.  
  119.       yend := floor(y1+0.5);
  120.       xend := x1 + gradient*(yend – y1);
  121.       ygap := 1.0-frac(y1 + 0.5);
  122.       ypxl1 := round(yend);    // ceci sera utilisé dans la boucle principale
  123.       xpxl1 := floor(xend);
  124.       putpixel_alpha(xpxl1, ypxl1    , (1.0-frac (xend)) * ygap,r,v,b);
  125.       putpixel_alpha(xpxl1, ypxl1 + 1, frac  (xend) * ygap,r,v,b);
  126.       interx := xend + gradient;    // premiere intersection-x pour la boucle principale
  127.  
  128.       // seconde extremite
  129.  
  130.       yend := floor(y2+0.5);
  131.       xend := x2 + gradient*(yend – y2);
  132.       ygap := frac(y2 + 0.5);
  133.       ypxl2 := round(yend);   // ceci sera utilisé dans la boucle principale
  134.       xpxl2 := floor(xend);
  135.       putpixel_alpha(xpxl2, ypxl2    , (1.0-frac (xend)) * ygap,r,v,b);
  136.       putpixel_alpha(xpxl2, ypxl2 + 1, frac  (xend) * ygap,r,v,b);
  137.  
  138.       // boucle principale
  139.       for y := ypxl1 + 1 to ypxl2 – 1 do
  140.       begin
  141.         putpixel_alpha(floor(interx)    , y, (1.0-frac (interx)),r,v,b);
  142.         putpixel_alpha(floor(interx) + 1, y, frac  (interx),r,v,b);
  143.         interx := interx + gradient;
  144.       end;
  145.     end;
  146.   end;
  147. end;

On a un peu perdu en lisibilité du code, mais on ne peut pas tout avoir. Le chef de projet devrait être content à présent. On arrêtera là les optimisations, parce qu’on peut aller très loin.

Le clipping par Cohen-Sutherland

On aimerait que ce soit fini, mais non, il nous reste encore le clipping ou fenêtrage, qui nous permettra de tracer une ligne sans faire planter lamentablement notre application. C’est souvent utile lorsque les extrémités sont calculées par un programme, et que les limites sont parfois en dehors de la zone de dessin et qu’on veut que le bout de ligne qui doit être affiché s’affiche quand même.. Elle fait appel à la procédure de tracé de ligne précédemment écrite et c’est donc cette nouvelle fonction qui devra être appelée par le programme utilisateur.

  1. //**********************************************************************
  2. //
  3. //  Algorithme de Cohen-Sutherland pour le clipping de lignes
  4. //
  5. //**********************************************************************
  6. procedure CHiColor.lineclip(x0,y0,x1,y1:double;r,g,b:byte);
  7. type edge = (GAUCHE,DROITE,BAS,HAUT);
  8.      outcode = set of edge;
  9. var accept,done:boolean;
  10.     outcode0,outcode1,outcodeOut:outcode;
  11.     x,y:double;
  12.     dx,dy:double;
  13. begin
  14.   x:=0.0;
  15.   y:=0.0;
  16.  
  17.   accept:=false;
  18.   done:=false;
  19.   //————————————————-
  20.   outcode0:=[];
  21.   if      (y0 > m_ymax_phys) then outcode0:=[BAS]
  22.   else if (y0 < m_ymin_phys) then outcode0:=[HAUT];
  23.   if      (x0 > m_xmax_phys) then outcode0:=outcode0+[DROITE]
  24.   else if (x0 < m_xmin_phys) then outcode0:=outcode0+[GAUCHE];
  25.   //————————————————-
  26.   outcode1:=[];
  27.   if      (y1 > m_ymax_phys) then outcode1:=[BAS]
  28.   else if (y1 < m_ymin_phys) then outcode1:=[HAUT];
  29.   if      (x1 > m_xmax_phys) then outcode1:=outcode1+[DROITE]
  30.   else if (x1 < m_xmin_phys) then outcode1:=outcode1+[GAUCHE];
  31.   //————————————————-
  32.   repeat
  33.     // Intérieur de la fenêtre – >  On trace directement
  34.     if ((outcode0=[]) and (outcode1=[])) then
  35.     begin
  36.       accept:=true;
  37.       done:=true;
  38.     end
  39.     else
  40.     // Même demi-plan extérieur – >  rien a dessiner
  41.     if (outcode0*outcode1) <> [] then
  42.     begin
  43.       done:=true;
  44.     end
  45.  
  46.     else
  47.     begin
  48.       //————————————
  49.       if (outcode0 <> []) then
  50.         outcodeOut:=outcode0
  51.       else
  52.         outcodeOut:=outcode1;
  53.       //————————————
  54.       dx:=x1-x0;
  55.       dy:=y1-y0;
  56.       //————————————
  57.       if BAS in outcodeOut then
  58.       begin
  59.         x:=x0+dx*(m_ymax_phys-y0)/dy;
  60.         y:=m_ymax_phys;
  61.       end
  62.       //————————————
  63.       else if HAUT in outcodeOut then
  64.       begin
  65.         x:=x0+dx*(m_ymin_phys-y0)/dy;
  66.         y:=m_ymin_phys;
  67.       end;
  68.       //————————————
  69.       if DROITE in outcodeOut then
  70.       begin
  71.         x:=m_xmax_phys;
  72.         y:=y0+dy*(m_xmax_phys-x0)/dx;
  73.       end
  74.       //————————————
  75.       else if GAUCHE in outcodeOut then
  76.       begin
  77.         x:=m_ymin_phys;
  78.         y:=y0+dy*(m_xmin_phys-x0)/dx;
  79.       end;
  80.       //————————————
  81.       if (outcodeOut = outcode0) then
  82.       begin
  83.         x0:=x;
  84.         y0:=y;
  85.  
  86.         outcode0:=[];
  87.         if      (y0 > m_ymax_phys) then outcode0:=[BAS]
  88.         else if (y0 < m_ymin_phys) then outcode0:=[HAUT];
  89.         if      (x0 > m_xmax_phys) then outcode0:=outcode0+[DROITE]
  90.         else if (x0 < m_xmin_phys) then outcode0:=outcode0+[GAUCHE];
  91.       end
  92.       else
  93.       begin
  94.         x1:=x;
  95.         y1:=y;
  96.  
  97.         outcode1:=[];
  98.         if      (y1 > m_ymax_phys) then outcode1:=[BAS]
  99.         else if (y1 < m_ymin_phys) then outcode1:=[HAUT];
  100.         if      (x1 > m_xmax_phys) then outcode1:=outcode1+[DROITE]
  101.         else if (x1 < m_xmin_phys) then outcode1:=outcode1+[GAUCHE];
  102.  
  103.       end;
  104.       //————————————
  105.  
  106.     end;
  107.   until done;
  108.  
  109.   if (accept) then
  110.   begin
  111.     wu_drawLine(trunc(x0),trunc(y0),trunc(x1),trunc(y1),r,g,b);
  112.   end;
  113. end;

Voilà, je pense que nous avons fait le tour du problème, et j’espère que l’article vous a plu. N’hésitez pas à me faire part de vos commentaires, remarques, améliorations,  je m’efforcerai d’y répondre dans un temps raisonnable.

David CHARDONNET, ClearAlgo

Graphisme