
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