Algorithmique de |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
DESSIN DES
OBJETS BASIQUES Segments Cercles Ellipses
REMPLISSAGE
|
0. Problématique
Comme dans nombre de domaines de l'informatique, l'informatique graphique fait appel à un certain nombre d'algorithmes de base
utilisés de façon directe ou indirecte pour l'implantation d'autres algorithmes. Le bon fonctionnement de ces algorithmes est
requis tout autant que leur fonctionnement optimal compte tenu des caractéristiques propres des dispositifs matériels sur lesquels
ils sont exécutés (en particulier processeurs nombreux, mais simples et développés spécifiquement). L'optimisation
de ces algorithmes est donc un but en soi. 1. Dessin 2D des objets de base 1.1. Tracé de segments de droite
Le tracé de segments de droite est l'algorithme de base pour beaucoup de traitements de l'informatique graphique : Cet algorithme doit être efficace car "mis à toutes les sauces".
Problème : On désire tracer un segment entre deux points (xi,yi) et (xf,yf) de R2.
Question : Quels pixels doit-on tracer ?
Trois impératifs:
- On doit obtenir les meilleures performances possibles. Compte tenu de ces impératifs et du fait qu'un segment de droite est tracé (coefficient directeur constant) et pas un autre type de courbe, 1+max(abs(xi-xf),abs(yi-yf)) pixels sont tracés. C'est à dire, si abs(xi-xf) < abs(yi-yf), un pixel et un seul par ligne interceptant le segment est tracé, sinon un pixel et un seul pixel par colonne interceptant le segment est tracé.
1.1.1. Tracé de segments par l'équation cartésienne On souhaite tracer le segment de droite qui va du pixel de coordonnées (xi,yi) au pixel de coordonnées (xf,yf).
On pose comme hypothèse simplificatrice : xf > xi, yf >= yi et (xf-xi) >= (yf-yi). Tous les autres cas peuvent s'y rapporter.
L’équation cartésienne de la droite est utilisé : y = a x + b avec a et b réels calculés de la façon
suivante : a =
et b = yi - a xi L'algorithme de tracé du segment de droite allant du pixel de coordonnées (xi,yi) au pixel de coordonnées (xf,yf) peut être implanté de la façon suivante :
/* Trace un segment de droite entre le pixel */ Il a été construit sur la base d'une itération x de xi à xf avec calcul au moyen de l'équation cartésienne, pour chaque x, de la coordonnée y entière et allumage du pixel de coordonnées (x,y).
Caractéristiques :
L'algorithme est d'une grande simplicité algorithmique. 1.1.2. Tracé de segments par algorithme Bresenham (algorithme du point milieu, algorithme du mid-point) On souhaite tracer le segment de droite qui va du pixel de coordonnées (xi,yi) au pixel de coordonnées (xf,yf). On souhaite pouvoir n'utiliser que des variables entières et des opérations simples : addition, soustraction, tests. L'algorithme de Brésenham est un algorithme incrémental en x et en y, c'est à dire que la position d'un pixel tracé est directement calculée à partir de la position du pixel tracé immédiatement avant lui. En l'occurrence, les incréments sont unitaires en x et en y car, comme on trace en 8-connexité, on trace toujours le pixel suivant parmi les 8 voisins du précédent. L'algorithme va donc utiliser deux variables entières x et y respectivement initialisées à xi et xf, et faire varier ces deux variables pour qu'elles prennent successivement les valeurs correspondant à tous les pixels à tracer, pour finir bien entendu avec x=xf et y=yf.
On pose de nouveau les hypothèses : xf > xi, yf >= yi, xf - xi > yf - yi. Toutes les autres situations peuvent s'y rapporter. Algorithme (langage C)
/* Trace un segment de droite entre le pixel */
Remarque : Le descriptif de fonctionnement donné ci-dessus n'est pas une preuve du bon fonctionnement de l'algorithme,
c'est à dire du fait qu'il trace bien un segment de droite. Il ne s'agit que d'une explication concrête de son fonctionnement. Exercice : Prouver que le dernier pixel tracé est bien le pixel de coordonnées (xf,yf). Solution Caractéristiques La complexité algorithmique apparente de l'algorithme de Bresenham est plus importante que l'algorithme utilisant directement l'équation cartésienne. L'objectif de rapidité due à l'utilisation exclusive d'entiers et d'opérateurs arithmétiques simples sur ces entiers (additions, soustractions, décalages binaires et tests comparaisons) est atteint. L'objectif de simplification de l'architecture matérielle due à l'utilisation exclusive d'entiers courts (valeurs maximales de l'ordre de la résolution de l'écran -> petites valeurs) et à la limitation des opérations utilisées sur ces entiers est atteint. Algorithme adapté pour le tracé de tout segment
La généralisation de l'algorithme ci-dessus à toutes les situations de placement relatif des pixels de coordonnées
(xi,yi) et (xf,yf) demande deux évolutions.
(2) L'algorithme est implanté en deux parties alternatives dont les exécutions sont arbitrées en fonction des valeurs relatives
de abs(xf-xi) et abs(yf-yi) :
/* Trace un segment de droite entre le pixel */ Exemples d'exécution
On souhaite tracer le segment (3,2)-(18,11).
1.2. Tracé de cercle par algorithme de Bresenham On désire tracer un arc de cercle de centre O et de rayon r circonscrit au deuxième octant du plan.
On trace un arc de pixels entre les pixels de coordonnées (0,r) et (,). Principe de l'algorithme
Comme dans le cadre de l'algorithme de Bresenham pour le tracé de segments, le tracé du cercle est réalisé incrémentalement : Si un pixel est allumé en position (x,y), le prochain pixel sera obligatoirement soit en position (x+1,y) soit en position(x+1,y-1) (tangente au cercle de coefficient directeur compris entre 0.0 et -1.0 sur notre arc).
L'algorithme est basé sur l'étude, pour chaque colonne de pixels, de la position (vis à vis du cercle continu : au dessus ou en dessous) du point intermédiaire entre les deux pixels superposés candidats définis ci-dessus qui encadrent le cercle (d'oú le nom d'algorithme du mid-point aussi utilisé pour cet algorithme). Si ce point intermédiaire est situé dans le cercle, le pixel allumé sera le pixel (x+1,y) situé en dehors du cercle (cas du pixel E1 ci-dessous). Sinon, le pixel (x+1,y-1) situé à l'intérieur du cercle est allumé (cas du pixel E2 ci-dessous).
L'idée de l'algorithme est donc de définir la "position" de chaque point intermédiaire de façon incrémentale, colonne de pixels après colonne de pixels.
La position d'un point P de coordonnées (x,y) vis à vis du cercle continu est établie à partir de l'équation
cartésienne f(x,y) = x2 + y2 - r2. Première possibilité : L'obtention d'un résultat négatif pour cette équation (cercle rouge ci-dessous) pour un point intermédiaire M conduit au choix du pixel extérieur E. Le prochain point intermédiaire sera situé en ME, c'est à dire un pixel à droite de M.
Seconde possibilité : Un résultat positif (cercle vert ci-dessus) conduit au choix du pixel intérieur SE, et au prochain point intermédiaire MSE situé un pixel à droite et un pixel plus bas que M. Définition récurente de l'algorithme P = (xp,yp) est la position d'un pixel allumé. La variable d (évaluant la position du point intermédiaire vis à vis du cercle) calculée à partir de P est
(1) Si d est inférieur à 0, E est choisi. Le prochain point intermédiaire est alors ME et la nouvelle valeur de d est calculée de la manière suivante :
(2) Si d est supérieur à 0, SE est choisi. Le prochain point intermédiaire est MSE et la nouvelle valeur de d est calculée de la manière suivante :
-> On obtient une définition incrémentale (récurrente) de d n'utilisant que des entiers (coordonnées des pixels). La première valeur de d est obtenue à partir de la position (0,r) pour un premier point intermédiaire de position placée en (1,r-). -> d = dinit = 1 + r2 - r + - r2 = - r. -> en entier: d = dinit = 1 - r. Sitôt que l'algorithme conduit à une valeur xp >= yp, son exécution est arrêtée car la diagonale est atteinte. Les conditions initiales étant connues, la récurrence étant définie, la condition d'arrêt étant fixée, on connaît maintenant totalement la définition récurrente de d. Implantation Le tracé d'un arc de cercle réduit au second octant centré sur l'origine où le rayon r est un paramètre entier placé en entête est réalisé par la fonction suivante :
/* Trace un arc de cercle de rayon r,
*/ Exemples d'exécution
Cette fonction pourra ensuite être adaptée (au moyen de symétries) pour tracer un cercle complet.
1.3. Tracé d'ellipses Un algorithme incrémental de tracé d'ellipses basé sur une technique du midpoint peut être défini sur des principes voisins de ceux utilisés pour le segment de droite et l'arc de cercle. Le travail est plus complexe par le fait que le tracé à l'intérieur d'un quadrant n'est plus symétrique par rapport à la diagonale.
L'algorithme réalise le tracé en deux passes consécutives pour un quadrant. Par exemple pour le quadrant 1, une passe avec un pixel par colonne pour la région 1 et une passe avec un pixel par ligne pour la région 2. La limite entre ces deux régions est le point où la pente est de -1.
/* Trace un arc d'ellipse de demi-axe
*/
2. Clipping (découpage) Définition
Clipping écran : Traitement permettant de réduire le dessin d'un objet graphique à une région de l'écran. Exemple : Clipping de 2 segments à l'intérieur d’un rectangle.
Le clipping dans un rectangle à bords horizontaux et verticaux, typiquement une fenêtre, est un des traitements de base de l'informatique graphique. Son implantation impose l'efficacité d'exécution. Une démarche consistant à calculer tous les pixels qui devraient être afficher sans clipping et n'afficher réellement que ceux qui sont dans le rectangle est donc inenvisageable. Le clipping se présentera donc comme un prétraitement consistant à déterminer la (ou les) partie de l'objet qui devra réellement être affichée et à l'afficher. Algorithme de Cohen-Sutherland pour le clipping d'un segment à l’intérieur d’un rectangle Cet algorithme est basé sur la détection d’un certain nombre de configurations de placement d'un segment relativement à un rectangle.
On associe à chacune des deux extrémités du segment un code défini sur quatre valeurs pseudo booléennes permettant de repérer la position (x,y) du
sommet par rapport aux 2 droites verticales et aux 2 droites horizontales définissant le rectangle de clipping (xmin, xmax)-(ymin, ymax) :
Dans deux situations on sait si un segment de coordonnées (xi,yi)-(xf,yf) est entièrement à l'intérieur ou entièrement à l'extérieur
du rectangle (xmin,ymin)-(xmax,ymax) :
Dans une autre situation on sait qu'un segment de coordonnées (xi,yi)-(xf,yf) est partiellement à l’intérieur du rectangle
(xmin,ymin)-(xmax,ymax) : Dans toutes les autres situations, on ne peut pas conclure (cas (4) en rose ci-dessous). On ne sait même pas si on aura à tracer quelque chose ou non.
Principe de l'algorithme A partir du segment S initial, les extrémités de S sont déplacées sur la droite sous-tendue par S vers les droites AB, BD, AC ou CD définissant le rectangle de clipping ABDC. Le but est de transformer S de façon qu'il devienne entièrement extérieur à ABDC (cas (3)) ou entièrement intérieur à ABDC (cas (1)). Le nombre de déplacements nécessaires n'est pas connu a priori. Dans le cas où les deux extrémités sont déjà dans ABDC, il n'y a même aucun déplacement à faire. L'algorithme est donc construit sur une boucle de type "tant que" dont la condition de continuation est que le segment S n'est ni en situation (1) ni en situation (3) vis à vis de ABCD. Dans cette boucle, chaque fois qu’il est établi qu'un code d'une extrémité présente un 1, on déplace cette extrémité pour qu'elle vienne rejoindre celle des droites AB, BD, AC ou CD qui correspond au 1 trouvé. Ainsi, on change le code de cette extrémité avec pour éventuelle conséquence la fin de la boucle. Exemples
La figure ci-dessus présente les deux segments S1 de P1i à P1f (en rose) et S2 de P2i à p2f (en orange) à clipper dans le rectangle ABDC. Les valeurs élémentaires des codes sont traitées de gauche à droite. Le traitement de S1 commence avec P1i et P1f de codes respectifs 1010 et 0101 qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. L'extrémité P1i possède un code différent de 0000 et est donc déplacée. Son code présente un 1 en position 1, P1i est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite verticale AC en position (1) rose. Son code devient 0000. P1i et P1f ont maintenant 0000 et 0101 pour codes respectifs qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. Le code de P1i est égal à 0000, on passe donc au traitement de P1f. Son code présente en 1 en position 2, P1f est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite verticale BD en position (2) rose avec pour code 0001. P1i et P1f ont maintenant 0000 et 0001 pour codes respectifs qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. Le code de P1f présente en 1 en position 4, P1f est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite horizontale AB en position (3) rose avec pour code 0000. P1i et P1f ont maintenant 0000 et 0000 pour codes respectifs qui sont tous deux égaux à 0000. On peut donc tracer le segment de droite qui va du point (1) rose au point (3) rose. Trois changements de position auront été nécessaires. A noter : Le point (0) vert n'a pas eu à être atteint. Le traitement de S2 commence avec P2i et P2f de codes respectifs 0001 et 1000 qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. L'extrémité P2i possède un code différent de 0000 et est donc déplacée. Son code présente un 1 en position 4, P2i est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite horizontale AB en position (1) orange avec pour code 1000. P2i et P2f ont maintenant 1000 et 1000 pour codes respectifs qui ont un 1 commun en position 1. On peut donc conclure que le segment S2 originel était entièrement en dehors de ABDC et qu'il n'y a donc rien à tracer. Un seul changement de position aura été nécessaire. A noter : Le point (0) cyan n'a pas eu à être atteint. Algorithme (pseudo langage C)
/* Trace le segment de droite allant du pixel p1 */
Remarque
Cet algorithme de clipping peut assez facilement être adapté au clipping de segments de droite à l'intérieur d'un polygone convexe quelconque. 3. Remplissage 2D de type "FillPoly" Définitions Ligne brisée 2D : Ligne polygonale 2D définie par une suite non circulaire de points reliés par des segments de droite. Polygone 2D : Surface 2D bordée par une suite circulaire de points reliés par des segments de droite. Polygone 2D convexe : Polygone 2D tel que, quels que soient 2 points Pi et Pf qu'il contient, il est possible de rélier Pi et Pf par un segment de droite sans sortir du polygone.
3.1. Remplissage d’un polygone 2D convexe L'opération de remplissage dont on parle ici désigne l'opération consistant à déterminer et afficher tous les pixels situés à l'intérieur du polygone traité. On connait la liste ordonnée des positions de ses sommets. Pour les polygones convexe, le remplissage peut être réalisé trame horizontale de pixels après trame horizontale de pixels en commençant du sommet inférieur et en remontant les trames jusqu'au sommet supérieur tout en gérant le parcours des suites de faces gauche et droite pour déterminer les abscisses xi et xf des deux pixels gauche et droit extrêmes sur chaque trame.
La suite gauche de sommets est B, A, F, E. La suite droite de sommets est B, C, D, E. 3.2. Remplissage d’un polygone 2D éventuellement concave
Principe
Tout comme pour le remplissage d'un polygone convexe, le remplissage d'un polygone concave est réalisé en traçant les trames horizontales
de pixels internes au polygone les unes à la suite des autres en partant de la trame la plus basse (correspondant au sommet le plus bas) pour
finir avec la trame la plus haute (sommet le plus haut).
Difficulté : L'algorithme nécessite un tri, ce qui nuit à sa scalabilité. Mise en œuvre
Une liste chaînée (nommée LCA ci-dessous) permet de gérer la suite des cotés actifs en cours de remontée des trames. Cette liste indique
quels sont les cotés ayant une intersection avec la trame en cours de traitement. Elle est mise à jour à chaque avancée
d’une trame au cours de l’exécution de l’algorithme. Elle est triée en permanence par ordre croissant des abscisses
x des pixels intersections. Chaque enregistrement de cette liste contient deux informations supplémentaires permettant d'en faciliter la gestion
: Exemples : Ci-dessous les valeurs de LCA pour les trames 7 et 13 avec pour chaque coté actif, de haut en bas, la valeur ymax, la valeur x et la valeur 1.0/a.
Pour faciliter la gestion de la liste des cotés actifs, un prétraitement est réalisé sur les cotés visant à les précalculer et à les placer dans
une structure intermédiaire (nommée SI ci-dessous). Celle-ci est un tableau de listes chaînées où pour chaque coordonnée y est stocké l’ensemble
des cotés c du polygone tels que y est l'ordonnée minimale ymin des deux extrémités de c. Ainsi, en parcourant SI
au cours de la remontée des trames, on pourra savoir quels cotés devront entrer dans LCA pour telle ou telle ordonnée. Pour chaque
coté, les valeurs ymax, 1.0/a sont stockées dans les zones idoines. La zone x est affectée avec la valeur x correspondant à ymin (y dans la structure
intermédiaire). Les listes de SI sont triées par ordre croissant de x, puis pour deux x identiques, par ordre croissant de la valeur 1/a.
Ce tri a pour but de faciliter le déplacement des cotés vers LCA car cet ordre de classement devra être respecté dans
LCA.
Algorithme (pseudo langage)
/* Remplit le polygone p avec la couleur c */
Définition
On entend par zone de pixels définie par une couleur :
Dans le cas (1) le remplissage est réalisé à partir d'un pixel germe de coordonnées (x,y) dont la couleur détermine la couleur
de la tache à remplir. 4.1. Un premier algorithme Principe Un algorithme récursif est implanté permettant de réaliser l'exploration/remplissage de la zone à colorier. Au cours du remplissage, à chaque fois qu'un pixel devant être rempli est parcouru, on le remplit, puis on lance récursivement l'algorithme sur les pixels qui lui sont connexes. Algorithme pour le remplissage d'une zone bordée (langage C) L'implantation est naturellement réalisée sous la forme d'une fonction récursive. gx et gy sont les coordonnées du pixel germe. c est la couleur de tracé. lim est la couleur limite. L'implantation est réalisée en 4-connexité.
/* Remplit la zone de pixels connexes definie */ Problème : L'utilisation de la récursivité entraîne très fréquement des problèmes de dépassement de capacité de la pile du programme si les zones remplies sont trop grandes (ce qui conduit à une profondeur de récursivité trop grande). Dans le pire des cas, la profondeur de la récursivité est égale au nombre de pixels de la tache à remplir. 4.2. Un deuxième algorithme Principe Le remplissage est effectué itérativement trame horizontale maximale de pixels après trame horizontale maximale de pixels à partir d'un pixel germe initial.
Plus précisément, une pile PG de pixels germes est gérée dans laquelle est initialement placé le pixel germe de départ. Ensuite tant qu'il existe
encore au moins un pixel germe dans la pile : Exemple
Algorithme sans récursivité pour le remplissage d'une zone bordée L'implantation sans récursivité nécessite la définition d'une pile de positions de germes. L'algorithme prend la forme d'une boucle exécutée tant que la pile n'est pas vide. Les paramètres de l'algorithme sont les coordonnées gx et gy du germe, la couleur limite lim et la couelur de tracé c.
/* Remplit la zone de pixels connexes definie */ |