
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 :
- au lieu de travailler sur tout l'écran on peut se limiter au rectangle englobant le polygone, pour le traitement
- si l'on prend des polygones convexe, connexe et non auto-intersectant, on peut au lieu de tracer dans un écran de travail, stocker les coordonnées x des segments
horizontaux, et ensuite lors du traçage ne tracer que ces segments horizontaux (en veillant à faire attention au sens de traçage).
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 :
- la complexité de l'algorithme
- pas de polygone auto-intersectant (mais je vous laisse le plaisir de rectifier ce petit problème, il suffit de rajouter un tri sur les intersections après l'élimination
(ou pendant))
- Attention à la gestion de la mémoire (listes de taille inconnue)
- Attention à la durée des tris (passer en tri fusion? cf Falk'mag 4 : article sur les tris) : c'est la seule limite de cet algorithme!
Amélioration :
- hypothèse sur les polygones -> moins de test -> routine plus rapide!
Par ex. : si le polygone est un triangle : le tri sur les arêtes est très simple, convexe : seulement deux intersections simultanées....
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