Tracé de ligne anti-aliasé 2/2

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

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

Pas encore de commentaire.

Laisser un commentaire

(requis)

(requis)