* * *
Programmation : Assembleur
* * *

Fénêtrage


 On continue la découverte de la synthèse d'image, avec le fenêtrage de segment et de polygone en 2 dimensions, pour ce numéro. Le fenêtrage permet d'afficher un objet (segment, polygone, cercle, ...) dans une fenêtre donnée (rectangle simple, ou polygone convexe), sans que ce dernier ne déborde de cette dernière. Par exemple, si je prend les fenêtres GEM, leurs contenus est fenêtré (on dit aussi clippé) lors de l'affichage, ainsi la routine qui s'occupe de dessin de leur contenu, ne s'occupe pas de savoir si ce qu'elle affiche déborde ou pas de la fenêtre. Dans le cas de projection 3D, il se peut que le résultat d'un calcul ne se trouve pas dans l'écran (coordonnées négative, ou trop importante). Et au lieu de l'afficher n'importe ou en mémoire, il parrait plus judicieux de n'afficher que la partie qui se trouve dans l'écran. En général on gagne en robustesse (surtout, on evite ainsi de se balader dans la mémoire), et en rapidité (un peu), le rêve? Un peu, mais il y a aussi des problèmes de complexitée d'algorithme (pour les plus poussé), et aussi que l'algorithme de fenêtrage n'est pas identique suivant l'objet graphique (segment, polygone, ...). Bon commençons par le plus simple, le fenêtrage de segment :


Fenêtrage de segment


 Il existe différente méthode pour fenêtré un segment dans un polygone donné, suivant la nature du polygone, ainsi que la méthode pour déterminé la ou les nouvelles extrémités du segment fenêtré. On ne verra que la méthode la plus simple (à mon gout, mais tous les gout sont dans la nature!) et de plus, sur un cas de fenêtre particulier (sniff, me direz-vous? Pas de prise de tête!). C'est un algorithme réentrant, c'est à dire que pour chaque coté de la fenêtre, on va fenêtré le segment. Par exemple pour un rectangle dont les cotés sont verticaux et horizontaux, et bien on va "clippé" le segment par le côté gauche, droit, haut et bas. Pour un polygone plus complexe (mais toujours convexe!), le résonnement reste le même (clipping suivant tous les côtés du polygone). Bon voyons, comment le fenêtrage s'effectue. Pour un sgement, il y a 4 cas à considérer :


¦ 1 * ¦ ¦ * 1 ¦ *----+----* ¦ ¦ ¦ ¦ ¦ 1 ¦ 2 ¦ ¦ ¦ ¦ *---+---* ¦ 2 * ¦ ¦ * 2 2 ¦ 1

partie partie
invisible visible

 le segment est :
partiellement visible totalement totalement partiellement
-> clipping ! invisible visible visible
-> clipping !
 l'extrémité 1 du segment est le début du segment. Les cas de segment invisible et visible ne posent pas de problème, il s'agit de conserver ou non le segment entier, dans l'ensemble des segments à afficher. Le problème des segments partiellement visible vient du fait qu'il faut calculer le point d'intersection avec le bord. Pour cela il y a deux grande méthode. La première qui n'est pas implémenté dans l'exemple est la recherche dichotomique. Le principe est le suivant, on coupe le segment en 2, puis on fenêtre les deux segments résultant. Suivant les cas, un segment serat partiellement visible et l'autre totalement visible/invisible. Pour le segment partiellement visible, on le recoupe en deux, et ainsi de suite. Lorsque l'on arrive à un segment de longueur 1, on sait si il est visible ou invisible, et donc on termine l'algorithme à ce niveau. Le problème avec cet algorithme est la multiplication du nombre de segment, il y a peut-être moyen de regrouper les segments produits en un seul segment, mais cela complique nettement l'algorithme! Les avantages (et oui il y en a!), ce sont la simplicité et la rapidité (pour un pas de l'itération), car cet algorithme n'utilise pas de division (je rapelle que les division par 2 en binaire se font par décalage à gauche -> très rapide!), et est facilment applicable. L'autre méthode pour calculer l'intersection avec le bord de la fenêtre est la méthode brutale, qui consiste à calculer l'équation de la droite du segment et à calculer l'intersection. Un petit raffinement consiste à ne pas calculer l'équation de la droite (y=ax+b), mais simplement la pente, et à calculer la différence (en x ou en y, suivant les côtés), qu'il faut appliquer pour tomber sur le point d'intersection :


Partie invisible Partie visible
¦ 2
¦ *
¦ /
¦ /
¦/
/ * <- point d'intersection
¦ /¦
¦ / ¦
Dy ¦ / ¦
¦ / ¦
\ * ¦
y 1 ¦
^ \____/
¦ Dx
+-> x

 Dans cet exemple, on connait Dx (car la coordonnée en x du point d'intersection est égale à la coordonnée en x du côté d'intersection), donc pour connaitre Dy, il suffit de calculer la pente (P=(y2-y1)/(x2-x1)), et de multiplier cette dernière par Dx pour obtenir Dy. En suite on ajoute Dy à la coordonnée y du point 1, et on obtient la coordonnée y du point d'intersection. Pour le cas d'une intersection avec un segment horizontal, il suffit de prendre l'inverse de la pente (P'=(x2-x1/(y2-y1)), et de multiplier par Dy pour obtenir Dx.  Donc l'algorithme de fenêtrage d'un segment par une fenêtre rectangulaire aux côtés horizontaux et verticaux est le suivant :

Pour tous les segments
Fenêtrage par le bord gauche
Fenêtrage par le bord droit
Fenêtrage par le bord haut
Fenêtrage par le bord bas
Si le segment est toujours visible, l'afficher

 Le programme d'exemple (cp_2ds_s.s) trace un segment par VBL, une extrémité du segment est centré sur le centre de la fenêtre de clipping, et l'autre extrémité est tiré au hasard (fonction random du système), on clippe le segment obtenu et on l'affiche (si possible). L'algorithme pour le clipping par un côté est toujours le même, on regarde si la première extrémité est visible, si oui, on regarde si la seconde l'est également; dans le cas des deux extrémités visible, il n'y a pas de clipping, dans le cas ou seule extrémité est visble, il y a clipping, et on calcul donc l'intersection. Si le segment n'est pas visible, on passe bêtement au prochain.

 Il se peut que si un segment est coupé plusieurs fois, on va calculé plusieurs fois la pente du segment (ou son inverse), de plus lors de l'affichage, la pente est aussi calculé, donc une optimisisation possible est de calculer au début la pente, et donc de conserver cette valeur tout au long du traitement. Le clipping de polygone est assez similaire, mais présente des difficultés suplémentaires :

Fenêtrage de polygone convexe


 Le fenêtrage d'un polygone suit le même principe : c'est à dire que l'on va fenêtrer par tous les côtés de la fenêtre sucessivement. Le problème qui se posent est le suivant : certain clipping vont produire plus de segments que d'autre. De même certain segment du polygone de départ ne seront pas dans le polygone clippé. 4 cas sont encore possibles :

¦ 1 * ¦ ¦ * 1 ¦
*----+----* ¦ ¦ ¦ ¦ ¦
1 ¦ 2 ¦ ¦ ¦ ¦ *---+---*
¦ 2 * ¦ ¦ * 2 2 ¦ 1

partie partie
invisible visible

Variation du nombre de segment :
+1 -1 0 0

 Le premier cas est interréssant, car bien qu'a première vu le segment ne fait que se transformer, il y a ajout de deux segments dans la liste des segments. Ainsi il ne faut pas oublié le segment qui suit le bord de la fenêtre de clipping et qui doit être ajouté :

¦ /
¦ / 1er segment
¦/
* <- premier point d'intersection
/¦ \
/ ¦ ¦
/ ¦ ¦
/ ¦ ¦
* ¦ ¦ segment ajouté au polygone 2nd segment
\ ¦ ¦
\ ¦ ¦
\ ¦ ¦
\¦ /
* <- second point d'intersection 3ième segment !
¦\
¦ \
¦ \

 Pour bien gérer ce genre de problème, il suffit de conserver la liste des sommets du polygone au lieu des arêtes du polygone. Ainsi lors que l'on rencontre un cas 1, il suffit d'ajouter à la liste des sommets du polygone le point d'intersection et le point d'arrivé du segment. Dans un cas 4, il suffit simplement d'ajouter le point d'intersection à la liste des sommets. Pour un cas 2 (segment totalement invisible), il faut supprimer les sommets de la liste, et dans un cas 3 (totalement visible), il suffit de laisser le dernier sommets du segment, car le premier est déjà ajouté lors du tratment du segment précédent! L'algorithme se trouve résumé dans les lignes ci- dessus. Le source d'exemple (cp_2d_p.s) se charge simplement d'appeler les routines clip_gauche, clip_droit, clip_haut, clip_bas puis d'afficher le polygone. Ces différentes routines ne sont pas très compliqué et s'inspire du code pour le clipping de segment.

 Une optimisation possible est la suivante : puisque l'on élimine les segment horizontaux lors de l'affichage, il peut s'avérer inutile de les générer lors du clipping avec des bords horizontaux. De même le pré-calcul des pentes peut s'avérer utile pour le clipping de polygone.

 Et voici la fin de ce cours article sur le clipping. Il existe d'autre méthode pour des clipping plus généraliste (fenêtre concave, polygone concave, ....), mais pour un utilisation courante (en 3D), l'essentiel est là. Bon code et bonne lecture !



Golio Junior