* * *
Programmation : Polygones
* * *

 Salut! Après les points, les lignes, aujourd'hui vous avez droit aux polygones! Polygones convexes, connectes, auto-intersectants... Voyons les différentes méthodes pour tracer un polygone :


Algorithme Naïf

 Pour faire simple (et pas rapide!), on peut, pour chaque point de l'écran, tester son appartenance au polygone. Pour savoir si un point appartient à un polygone, c'est très simple : il suffit de tracer une demi droite (d'origine ce point), et de compter le nombre d'intersection avec les arêtes du polygone. Si ce nombre d'intersection est pair, alors le point est en dehors du polygone (la demi-droite rentre et sort du polygone : donc on est à l'extérieur). Par contre si ce nombre est impair, alors on se trouve dans le polygone, et on peut afficher le point avec la couleur du polygone. Cet Algorithme est très gourmand en temps, mais peu en espace. De plus il est assez simple à coder (pour demi- droite prend la demi-droite horizontal, et compter les intersections : facile), et donc pas d'exemple! Mais en contre partie, il permet de traiter tous les types de polygone :

concave :
si on suit une droite, on peut sortir, puis ensuite rentrer à nouveaux dans le polygone.
convexe :
c'est l'inverse de concave.
connexe :
le polygone est d'un seul tenant, c'est à dire qu'il n'est pas composé de 2 partie séparée.
non connexe :
c'est l'inverse de connexe
auto-intersectant :
le polygone a des arêtes qui se coupent entre elles.
non auto-intersectant :
le polygone n'a pas d'arêtes qui se coupent.


Algorithme de Lucas

 Dans la famille des algorithmes généralistes, il y a l'algorithme de Lucas. Le principe de cet algorithme est le suivant : on trace dans une mémoire annexe les arêtes constituant le polygone. Lors de ce traçage, on affecte à chaque points un code qui a pour signification : soit le changement de contexte (en passe de l'intérieur à l'extérieur du polygone, ou inversement), soit le non changement de contexte (le point doit être colorié, mais il ne provoque pas de changement de contexte). Ensuite vient la phase de traçage proprement dite, et là pour chaque ligne, on la parcours de la gauche vers la droite (ou inversement) (Rq. : au début de chaque ligne, le flag intérieur est à faux, car on est à l'extérieur du polygone), et on test pour chaque point, si l'on change de contexte (alors on inverse le flag intérieur), si le point est à afficher (quand il n'y a pas de changement de contexte ou qu'il doit être affiché), si il n' y a rien à faire...


 Au premier abord, ce codage des points peut semble lourd, mais prenons le cas d'une arête horizontale (cas particulier), l'ensemble des points doit être affiché, mais on ne sort pas du polygone (ni on n'y rentre). De même sur des pointes :

    /\  <- ceci est une pointe de polygone
   /  \
  /    \

 il n'y a pas de changement de contexte, mais le point doit être colorié. Il y a aussi le cas où deux arêtes se croisent, les arêtes qui affiche plusieurs points sur la même ligne etc...


 Bon voici l'algorithme :
* remplissage d'une tache : algorithme de Lucas
* on fournit la succession des points du polygone

pour i=1 pas 1 jusqu'a largeur faire
     pour j = 1 pas 1 jusqu'a hauteur faire
          image_travail  (i,j)=0              * effacement  de  l'écran  de fait                                     * travail
fait

* la première arête ne doit pas être horizontale
* car on stocke le sens de déplacement pour détecter les pointes
lp= premier_sommet;
l = sommet_suivant;      * pseudo fonction qui retourne le sommet suivant
tant que Y(lp)=Y(l) faire
     lp=l;
     l=sommet_suivant;
fait

* parcours du contour de la tache
upl=y(lp)upl);       * changement de sens
          segment (x(l), y(l), x(m), y(m), pointe);
          upl=upm;
     fsi
     l=m;
     ilyasommet=m<>lp;
fait

* inscription de la surface
pour j=1 pas 1 jusqu'a hauteur faire
     interieur=faux;               * on commence toujours à l'extérieur du
                                   * polygone
     pour i=1 pas 1 jusqu'a largeur faire
          si image_travail(i,j)=1
          alors
               interieur=!interieur;    * changement de contexte
               image(i,j)=couleur;      * affiche du point
          sinon
               si interieur ou (image_travail(i,j)=2)
                    alors image(i,j)=couleur;
          fsi
     fait
fait

 Il reste encore l'algorithme de traçage de segment. J'ai réutilisé celui de l'interpolation linéaire du précédent article. Il y a une petite modification : lorsque l'on trace des segments ou x croit plus vite que y (dx>dy), il faut que 1 point de la ligne courante indique un changement de contexte (ici on prend le premier) :

     0000000122000       on remarque que l'on rentre ou l'on sort du
     0000012200000       polygone une seule fois, et que les autres points
     0000120000000       de l'arête sont correctement tracé
     0012200000000

          1 : changement de contexte
          2 : point à afficher, sans changement de contexte

 Une petite remarque : lorsque l'on trace les arêtes, on teste si l'ancien point est égale à 1, si il est égal à 1, alors on le passe a 2, car si il y a deux changement de contexte, c'est comme si il n'y en avait pas.

 Les inconvénients majeurs de cet algorithme sont :
gourmand en espace mémoire :
il faut un écran de travail
gourmand en temps :
le traçage du polygone à partir de l'écran de travail est long
les tests prennent du temps

 Améliorations :
 En plus de ces améliorations, on peut aussi améliorer le code, surtout en passant en mode à plan, et en utilisant (peut-être, je n'ai pas encore essayé) le blitter (cf. article PFM No9 sur les sprites). Ces dernières améliorations seront aussi valable pour l'algorithme de balayage ligne par ligne qui suit :


Algorithme de balayage ligne par ligne

 Cet algorithme est un peu plus complexe a mettre en oeuvre (mais qui a peur de la complexité, surtout en assembleur?), mais surtout extrêmement rapide, et peu gourmand en mémoire (le rêve?). Le principe de cet algorithme est le suivant : calculer toutes les arêtes qui sont en intersection avec la ligne de balayage courante. En utilisant le fait qu'un polygone est continu, l'ensemble de arêtes qui sont en intersection avec la ligne de balayage courante, va évoluer par soustraction de l'ensemble des arêtes qui se termine sur cette ligne de balayage, et par addition de l'ensemble des arêtes qui débutent sur la ligne suivante. Ensuite il suffit de trier les intersections suivant les x croissants, de les regrouper 2 par 2, et de tracer les lignes horizontales entres deux intersections.

 Laissez macérer, et revenez dans quelque heures/minutes/secondes (suivant la vitesse du cerveau) pour découvrir l'algorithme :

* remplissage en balayage ligne par ligne

* constitution de la liste des arêtes
* i.e. : élimination des arêtes horizontales
*        orienter les arêtes
*        tri sur les y croissants
fin_aretes_triees=aretes_triees    * ensemble des arêtes triées vide
pour chaque arête faire
     si arete horizontale
     alors
                              * ne pas la ranger : rien a faire
     sinon
          si arete mal_orientee alors orienter arête
                              * l'insérer dans la liste des arêtes
          arete_courante = aretes_triees
          tant que arete_courante<>fin_aretes_triees faire
          quand arete_courante=fin_aretes_triees sortir par plus_d_arete
          si arete fin_aretes_triees  ou  fin_intersection <> intersection faire
* constitution de la liste des intersections
si arete_courante <> fin_aretes_triees alors
     tant que ligne_courante=debut d'arete_courante faire
          calcul et initialisation des différents paramètres de l'intersection
          ajout  à  la liste des intersections (tri par  insertion  cf.  tri précédent)
                    * le tri se fait d'abord sur les x croissants
                    * en cas d'égalité, on tri sur les pentes croissantes
          arete_courante = arete_suivante
     fait
fsi

* traçage
pour chaque couple d'intersection faire
     traçage du segment horizontal
fait

* élimination des intersections et calcul des nouvelles coordonnées
pour chaque intersection faire
     si hauteur de l'intersection = 0 alors
          élimination de l'intersection par écrasement
                    * l'arête suivante est l'arête courante
     sinon
          calcul de la prochaine coordonnées x de l'intersection
                    * pour ce calcul,  on prend ajoute la partie entière  de * l'addition de la pente et de l'accumulateur
                    * le nouvel accumulateur devient la partie décimale  de * l'addition
          décrémentation de la hauteur de l'intersection
     fsi
fait

fait

 Inconvénients :

 Amélioration :

 Et voilà la fin de cet article (qui mériterait d'être plus long), qui traitait du remplissage de polygone en assembleur, sans une ligne d'assembleur! Dans le prochain article nous verrons l'ombrage de Gouraud et peut-être de Phong.

Golio Junior