Algorithmique de |
|||||||||||||||||||
DESSIN DES OBJETS BASIQUES Segments Cercles Ellipses
REMPLISSAGE
|
Dessin 2D des objets de base Algorithmes de tracé de segments Algorithme de base pour beaucoup de traitements de l'Informatique Graphique:
Cet algorithme doit être efficace car "mis à toutes les sauces". On désire tracer un segment entre deux points (xi,yi) et (xf,yf) de R2. Ce tracé est effectué sur un écran bitmap (composé d'une matrice de n x m pixels carrés). -> Le segment doit être discrétisé (rasterisé). Problème: Quels pixels doit-on tracer? Trois impératifs:
On trace 1+max(abs(xi-xf),abs(yi-yf)) pixels. Si abs(xi-xf) < abs(yi-yf), on trace un pixel et un seul par ligne interceptant le segment, sinon on trace un pixel et un seul par colonne interceptant le segment.
Tracé de segments par l'équation cartésienne On pose comme hypothèse simplificatrice: xf > xi, yf >= yi et (xf-xi) >= (yf-yi). Tous les autres cas peuvent s'y rapporter. -> Le coefficient directeur de la droite passant par les deux sommets est positif ou nul et inférieur ou égal à 1. On utilise l’équation cartésienne de la droite: y = a x + b avec a = et b = yi - a xi
void ligne(int xi,int yi,int xf,int yf) { Caractéristiques:
Bresenham pour le tracé de segments Algorithme incrémental en x et en y On pose de nouveau les hypothèses: xf > xi, yf >= yi, xf - xi > yf - yi. -> On allume un pixel en chaque abscisse entière x de xi à xf. -> On utilise une variable pour stocker une estimation de la différence (positive ou négative) entre l'ordonnée entière (utilisée pour l’affichage raster) et l'ordonnée réelle calculable sur le segment continu.
void ligne(int xi,int yi,int xf,int yf) { Le dernier pixel allumé a pour coordonnées (xf,yf) car dx/2+dy*dx est la valeur totale de ce qui a été accumulé dans cumul au cours de l'exécution. -> = dy est le nombre de fois où y a été incrémenté de 1. -> L’ordonnée du dernier pixel allumé est yi + dy = yf. Caractéristiques Plus grande complexité algorithmique. Rapidité due à l'utilisation exclusive d'entiers courts (valeurs maximales de l'ordre de la résolution de l'écran -> petites valeurs) et d'opérateurs arithmétiques simples sur ces entiers (additions, soustractions, décalages binaires et comparaisons). Algorithme adapté pour le tracé de tout segment Utilisation de deux variables xinc et yinc pour gérer des incréments de 1 ou -1 pour x variant de xi à xf et y variant de yi à yf.
Deux parties alternatives dans l'algorithme:
en fonction de la pente du segment.
void ligne(int xi,int yi,int xf,int yf) { Exemple d'exécution On souhaite tracer le segment (3,2)-(18,11).
Bresenham pour le tracé de cercles
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 points (0,r) et (,). Un pixel sera allumé sur chaque colonne d'abscisse comprise entre 0 et .
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 portion d'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 alternatif d'algorithme du midpoint). 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. -> Si f(x,y) < 0, P est dans le cercle, sinon il est à l'extérieur. Première alternative : 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 alternative : 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.
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 selon la technique suivante:
-> On obtient une définition récurrente incrémentale 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écurence étant définie, la condition d'arrêt étant fixée, on connaît maintenant totalement la définition récurrente de d.
On peut écrire une fonction de tracé d'un arc de cercle où le rayon r est un paramètre entier placé en entête.
void arcDeCercle(int r) { Exemple d'exécution
Cette fonction pourra ensuite être adaptée (au moyen de symétries) pour tracer un cercle complet. Le tracé d'ellipses Un algorithme incrémental de tracé d'ellipses basé sur une technique du midpoint peut être défini. 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éalisera 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.
void ellipse(long a,long b) {
Le clipping (découpage) Définition Clipping écran: Traitement permettant de réduire le dessin d'un objet graphique à une région de l'écran.
Cette région est classiquement un rectangle mais peut être de toute autre forme. Exemple: Clipping de 2 segments à l'intérieur d’un rectangle. Clipping dans un rectangle à bords horizontaux et verticaux (fenêtre): Traitement de base de l'Informatique Graphique -> Nécessité d'efficacité. Cohen-Sutherland pour le clipping d'un segment à l’intérieur d’un rectangle Algorithme 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 indiquant la position (x,y) du sommet par rapport aux quatre droites définissant le rectangle de clipping (xmin, xmax)-(ymin, ymax):
Dans deux cas on sait si un segment de coordonnées (xi,yi)-(xf,yf) est traçable car entièrement ou pas du tout à l’intérieur du rectangle (xmin,ymin)-(xmax,ymax):
Dans un autre cas on sait qu'un segment de coordonnées (xi,yi)-(xf,yf) est partiellement à l’intérieur du rectangle (xmin,ymin)-(xmax,ymax):
Dans tous les autres cas, on ne peut pas conclure (cas (4) ci-dessous). Principe de l'algorithme A partir du segment s initial, on déplace les extrémités de s vers les droites AB, BD, AC ou CD définissant le rectangle de clipping ABDC autant de fois qu'il le faut pour établir que s ainsi modifié est entièrement extérieur à ABDC (cas (3)) ou que s ainsi modifié appartient entièrement à ABDC (cas (1)).
Au cours de l'exécution, chaque fois qu’il est établi qu'un code d'une extrémité n'est pas égal à 0000, on déplace
cette extrémité pour qu'elle vienne rejoindre l'une des droites AB, BD, AC ou CD. Ainsi, on en change le code.
Ces modifications sont réalisées itérativement jusqu'à pouvoir conclure.
Cet algorithme de clipping peut assez facilement être adapté au clipping de segments de droite à l'intérieur d'un polygone convexe quelconque. Algorithme
procedure clip(Point2D p1,Point2D p2,fenetre f) { Définition Ligne brisée 2D: Courbe polygonale 2D définie par une suite non circulaire de points reliés par des segments. Polygone 2D: Surface 2D bordée par une suite circulaire de points reliés par des segments. Remplissage d’un polygone convexe Remplissage trame après trame en commençant du sommet inférieur et en remontant les trames tout en gérant le parcours des suites de faces droite et gauche.
Suite gauche: B, A, F, E Suite droite: B, C, D, E Remplissage d’un polygone éventuellement concave
Principe Processus de remplissage traçant les trames internes au polygone les unes à la suite des autres. Chaque trame interceptera un nombre paire n de cotés du polygone. Après tri en x des n intersections Pi (1 <= i <= n), on tracera des segments entre chaque couple de coordonnées (P2*j-1,P2*j) avec 1 <= j <= .
Mise en œuvre Une liste chaînée LCA permet de gérer une suite de cotés actifs. Cette liste indiquera 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 points intersections.
LCA pour la trame 7
LCA pour la trame 13 Création d’une structure intermédiaire SI contenant les informations qui seront nécessaires à la gestion de LCA. SI est un tableau de listes chaînées. Pour chaque coordonnée y, on stocke l’ensemble des cotés c du polygone tels que y est l'ordonnée minimale ymin des deux extrémités de c. (1) En parcourant SI on pourra savoir quels cotés devront entrer dans LCA pour telle ou telle ordonnée. (2) Pour gérer le retrait des cotés de LCA, on mémorise l'ordonnée maximale de chaque coté. On stocke aussi pour chaque coté: - l’inverse 1/a de son coefficient directeur (incrément en x pour un déplacement unitaire en y), - l’abscisse xmin correspondant à ymin. Les listes de SI sont triées par ordre croissant de xmin, puis pour deux xmin 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
Procedure remplirPolygone(Polygone p) Remplissage d'une zone définie par une couleur Définition On entend par zone définie par une couleur: (1) un ensemble connexe maximum de pixels de même couleur, (2) un ensemble connexe maximum de pixels dont la couleur n'est pas une couleur définie (couleur du bord de la zone)
Cas (1): Chacune des zones grise, noire et blanche. Cas (2): L'union des zones grise et noire vis à vis de la zone blanche. Le remplissage est réalisé à partir d'un pixel germe. Un premier algorithme Principe 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 L'implantation est naturellement récursive. c est la couleur de tracé. lim est la couleur limite.
void remplissage(int x,int y,Couleur c,Couleur lim) { 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). Un deuxième algorithme Principe Le remplissage est effectué suite horizontale maximale de pixels après suite horizontale à partir d'un pixel germe initial. A chaque itération:
... Algorithme pour le remplissage d'une zone bordée L'implantation 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.
void remplissage(int xx,int yy,int c,int lim) { |