trans_algo_2d_td

5/11/2018 trans_algo_2d_td - slidepdf.com

http://slidepdf.com/reader/full/transalgo2dtd 1/44

RemplissageClassification 2D

Algorithmes fondamentaux 2D

Christian Nguyen

Departement d’informatiqueUniversite de Toulon et du Var

3 novembre 2009

Christian Nguyen Algorithmes fondamentaux 2D

http://find/

http://goback/




Introduction

Lorsqu’une primitive graphique doit etre affichee, elle subit uncertain nombre de transformations :

1 elle est fenetree,

2 elle est projetee,

3 elle est discretisee,

4 elle est “coloriee”.

A chaque fois qu’une image est creee ou modifiee, ces algorithmessont invoques. Ils doivent donc etre particulierement efficaces.


http://find/

http://goback/




IntroductionObjets manipules

On se limite aux polygones. En effet, dans l’espace discret toutobjet peut etre approxime par un polygone.

Celui-ci sera defini par la suite des sommets qui le caracterisent,suivant un sens de parcours trigonometrique ou horaire. Ce sens deparcours permet d’orienter la frontiere du polygone.

Afin de pouvoir distinguer interieur et exterieur d’un polygone, il

faut preciser le type de connexite : d ou i .


http://find/

http://goback/




Plan

1 Remplissage

2 Classification 2D


http://find/

http://goback/




RemplissageDans l’espace discret

Zone definie par un ensemble de pixels.Ces pixels definissent soit une surface (coloriage), soit un contourferme (remplissage).

Coloriage : pixel initial (appele germe ) appartenant a la surface,

puis application d’un algorithme recursif qui examine les 8 pixelsvoisins, determine si la limite de zone est atteinte et applique lacouleur choisie (backtracking ).


R li

http://find/

http://goback/




RemplissageDans l’espace discret

Remplissage : germe, exploration des voisins droites et gauches dugerme afin de parvenir au contour.

Une fois la frontiere G-D determinee, trace d’un segmenthorizontal et poursuite de l’algorithme pour tous les pixels situesau dessus et en dessous de la ligne qui vient d’etre tracee.

Le processus se termine lorsque tous les pixels examines sont situes

sur le contour.


R li

http://find/

http://goback/




RemplissageApproche geometrique

Travail dans l’espace objet, polygones decrits par leurs sommets.Calculs geometriques prenant en compte l’espace discret danslesquels les objets seront representes.

Parcours du polygone par une ligne de balayage (scan-line ) et

calcul des intersections de cette ligne avec les aretes du polygoneen arithmetique entiere et incremental grace a la notion decoherence spatiale (d’aretes) et temporelle (de lignes).


Remplissage

http://find/

http://goback/




RemplissageApproche geometrique

Algorithme pour une ligne de balayage :1 trouver les intersections de la ligne de balayage avec les aretes

concernees,2 trier les points d’intersection par abscisses croissantes. Cas

particuliers :

une intersection qui a des coordonnees non entieres, onraisonne alors en fonction de la parite du nombred’intersectionsune intersection qui a des coordonnees entieres mais unsommet partage par deux aretes, on ne prend en compte un

sommet que lorsqu’il est le sommet “bas” d’une arete,arete horizontale auquel cas on ne prend pas en compte sessommets.

3 tracer une ligne de pixels entre chaque couple de pointsd’intersection.


Remplissage

http://find/

http://goback/




RemplissageCoherence d’arete

Amelioration sensible des calculs des points d’intersectionligne-arete.

Une partie des aretes est concernee par ce calcul d’intersection achaque ligne de balayage et beaucoup d’aretes intersectees par laligne de balayage a l’etape courante le seront encore a l’etapesuivante.

Le calcul d’intersection de la nouvelle ligne avec une arete peut seresumer par la formule :

x i +1 = x i + 1p , y i +1 = y i + 1

Pour eviter les calculs fractionnaires on conserve l’expression de lapente sous la forme (∆y , ∆x ) et on les compare pour savoir quand

et comment changer d’abscisse.Christian Nguyen Algorithmes fondamentaux 2D

Remplissage

http://find/

http://goback/




RemplissageCoherence de ligne de balayage

Utilisation d’une “table des aretes actives” (TAA), liste d’aretes,triees par abscisses d’intersection croissantes et modifiee enfonction de la ligne de balayage :

si y = y max alors l’arete est enleveesi y = y min − 1 alors l’arete est ajoutee

Chaque element de cette liste sera de la forme :

x inter y max pente (N, D) suivant→

Mise a jour efficace avec une “table des aretes” (TA), dont leselements sont tries par y min croissante (sans les areteshorizontales) :

y min x min y max pente (N, D) suivant→


Remplissage

http://find/

http://goback/




RemplissageCoherence de ligne de balayage

1

A(2,3)

B(7,1)

C(13,5)

D(13,11)

E(7,7)

F(2,9)

3

7 3 -2/5 7 5

13 11

7 9 -5/2 7 11 3/2

2 9

7

5

3/2BCAB

AF

CD

EF ED

8

8

Fig.: Un polygone et sa TA


Remplissage

http://find/

http://goback/



p gClassification 2D

RemplissageAlgorithme

Algorithme Remplissage Geometrique(pol )donnees

pol : polygonevariables

TA, TAA : listes d’aretesy, Ymax : entiersajout : booleen


Remplissage

http://find/

http://goback/



Classification 2D

RemplissageRemplissage par motif

On distingue deux methodes :

pendant la discretisation par balayage : dans l’espace reel parrapport a la primitive graphique ou dans l’espace ecran auquelcas la primitive joue le role de region transparente laissantapparaıtre le motif,

avant la discretisation par balayage : definition d’un masquerectangulaire associee a la primitive (0 pour la primitive, 1

pour le reste), operateur ET pour le masque puis operateur OUpour la primitive.


Remplissage

http://find/

http://goback/



Classification 2D

Plan

1 Remplissage

2 Classification 2D


RemplissageCl ifi i 2D

http://find/

http://goback/



Classification 2D

Classification 2DClassification point/droite

Soient P 1(x 1, y 1, h1) et P 2(x 2, y 2, h2). Une droite δ passant par cesdeux points est donnee par :

δ : det (P ,P 1,P 2) =x x 1 x 2y y 1 y 2h h1 h2

= 0

x (y 1h2 − h1y 2) + y (h1x 2 − h2x 1) + h(x 1y 2 − y 1x 2) = 0


RemplissageCl ifi ti 2D

http://find/

http://goback/



Classification 2D

Classification 2DClassification point/droite

+

−

P

P1

P2

D

Un point sera a gauche (resp. a droite) d’un segment oriente joignant deux points P 1 et P 2 ssi det (P ,P 1,P 2) > 0 (resp.

det (P ,P 1,P 2) < 0).

Un point appartiendra au contour si det (P ,P 1,P 2) = 0.



http://find/

http://goback/



Classification 2D

Classification 2DClassification point/contour

Dans le cas des polygones convexes , on se ramene a uneclassification point/droite.

P est a l’interieur (resp. a l’exterieur) du polygone si ∀i (resp. ∃i ),det

(P ,

P 1,

P 2) > 0 (resp.

det (

P ,

P 1,

P 2) < 0).

P

Si+1

Si

−

+



http://find/

http://goback/



Classification 2D

Classification 2DAlgorithme

Algorithme ClassificationPointPolygone( pt , poly )donnees

pt : pointpoly : polygone oriente

variablescontinuer : booleeni : entierpos : reel



http://find/

http://goback/



Classification 2D

Classification 2DL’algorithme de Shamos

Classement d’un grand nombre de points par rapport a un memecontour. Complexite est en O (log n) mais avec un pretraitement enO (n) qui consiste a decomposer le polygone en secteursangulaires :

S1

S2

S3

Si+1

Si

P

q

α1

α2 axe de référence

Calcul de l’angle Θ = S 1qP puis recherche dichotomique dusecteur auquel appartient P . Soit (S i ,S i +1) l’arete de ce secteur, ilne reste plus qu’a classer P par rapport a cette arete.



http://find/

http://goback/



Classification 2D

Classification 2DPoint/polygone concave

L’algorithme des “angles capables” permet de determiner laposition d’un point sauf si celui-ci appartient au contour.

Calcul de tous les angles Θi = S i PS i +1 et de leur somme. SiN i =1 Θi ≃ 2Π alors P se situe a l’interieur du polygone sinon siN i =1 Θi ≃ 0 alors P est a l’exterieur.

Couteux du fait de l’utilisation de fonctions trigonometriques.



http://find/

http://goback/



Polygones concavesAlgorithme des “angles capables”

Algorithme ClassificationPointPolygone( pt , poly )donnees

pt : pointpoly : polygone oriente

variablesi : entiers

α : reelconstantesPRECISION = 1.0e-1

i ←− 0tantque (i < poly .nb som) faire

α ←− α + CalculAngle(pt, poly.pt[i], poly.pt[(i+1)%poly.nb som])i ←− i+1

ftq

si (−PRECISION < α < PRECISION ) alorsretourner EXT

sinonretourner INT

fsi



http://find/

http://goback/



Classification 2DPoint/polygone concave

Autre solution : adapter l’algorithme “scan-line”.

Calcul de la parite du nombre d’intersections entre le point

considere et la table des aretes.

Si ce nombre est pair alors le point est a l’exterieur sinon il est al’interieur.

Cas particuliers (point appartenant a la droite support d’une arete,

. . .) augmentant la complexite initiale, en O (n).



http://find/

http://goback/



Classification 2DSegment/segment

Methode parametrique naturelle et efficace. Soient deux segmentsde droites definis par (A, B) et (C, D). Un point intersection de cesdeux segments sera solution du systeme :

x A + t 1(x B − x A) = x C + t 2(x D − x C )y A + t 1(y B − y A) = y C + t 2(y D − y C )

soit

t 1(x B − x A) + t 2(x C − x D ) = x C − x A

t 1(y B − y A) + t 2(y C − y D ) = y C − y A

Le determinant de ce systeme (de Cramer) est : det =(x B − x A)(y C − y D )− (x C − x D )(y B − y A).



http://find/

http://goback/



Classification 2DSegment/segment

Algorithme Classification segment/segment(A, B , C , D )donnees

A, B , C , D : pointsvariables

det : reel

det ←− (x B − x A)(y C − y D )− (x C − x D )(y B − y A)si (det = 0) alors

segments paralleles ou colineaires

sinont 1 = ((x C − x A)(y C − y D )− (x C − x D )(y C − y A))/det t 2 = ((x B − x A)(y C − y A)− (x C − x A)(y B − y A))/det

si (t 1 > 1 ou t 1 < 0 ou t 2 > 1 ou t 2 < 0) alorspas d’intersection

sinonsi (t 1 = 0 (resp. t 1 = 1)) alors

intersection au point A (resp. B)sinon

si (t 2 = 0 (resp. t 2 = 1)) alorsintersection au point C (resp. D)

sinon

x i = x A + t 1 (x B − x A)y i = y A + t 1 (y B − y A)

fsifsi

fsifsi



http://find/

http://goback/



Classification 2DD’un ensemble de segments

La classification d’un ensemble de segments necessite une methodeefficace.

La methode de Bentley et Ottmann recherche dans une famillefinie de segments, par balayage du plan, les paires qui se coupent.Toutes les insertions effectuees dans l’algorithme se font parabscisse ou ordonnee croissante.

A noter cependant que cet algorithme est bien connu pour etretres sensible aux erreurs numeriques.



http://find/

http://goback/



Classification 2DD’un ensemble de segments

E

B

D

C

A

lPtx = A0, B 0, C 0, D 0, i 2, C 1, i 3, i 4, E 0, D 1, i 1, A1,

i 5, E 1, B 1

lSeg = A, BA, BCA, DBCA, DCBA, DBA, BDA, BAD, EBAD,

EBA, EAB, EB, BE, B



http://find/

http://goback/



Classification d’un ensemble de segments

Algorithme ClassificationEnsembleSegments(tseg )

donneestseg : tableau des N segmentsvariables

lPtx : liste de points (associes a un type)lSeg : liste de liste d’identificateurs des segments ⊲ tries par ord. croissantes

x 0 : couple (abscisse, type)

lPtx ←− tri par abscisses croissantes des 2N sommetsinitialiser lSeg avec le 1er segment correspondant au 1er point de lPtx

pt ←− 1er point de lPtxtantque (non fin(lPtx )) faire

cas (type(pt)) deDEBUT :inserer dans lSeg par ord. croissante le segment de sommet pt

⊲ par intersections des segments de lSeg avec x = pt

si (dans lSeg ce segment coupe ses voisins) alorsinserer le(s) point(s) d’intersection dans lPtx (par abs. croissantes)

fsi

FIN :si (dans lSeg les voisins de ce segment se coupent) alors

inserer le point d’intersection dans lPtx (par abs. croissantes)fsienlever ce segment de lSegINTERSECTION :echanger les positions des segments concernes dans lSegsi (les segments nouvellement adjacents dans lSeg se coupent) alors

inserer dans lPtx les points d’intersection (par abs. croissantes)

fsifcas←−



http://find/

http://goback/



Fenetrage (clipping)De segments

Plusieurs cas se presentent :

Le fenetrage des points extremites repondent au critere :x min ≤ x ≤ x max

y min ≤ y ≤ y max



http://find/

http://goback/



ClippingDe segments

Resolution d’equations : comporte trop de calculs et de tests (testdes points extremites, intersection avec les 4 droites definissant lafenetre, test d’appartenance des points d’intersection a la fenetre,...).

Fenetrage de Cohen-Sutherland (1970) : base sur la notion de“controle de regions”, test les points extremites pour determiner sile segment peut etre accepte, retraite ou rejete.

Le plan de fenetrage est divise en 9 regions, chacune d’ellescomportant un code sur 4 bits, correspondant a des inegalitesstrictes et autorisant des tests d’appartenance efficaces.



http://find/

http://goback/



ClippingDe segments

N S E O

si les deux extremites sont a 0000 alors le segment est

totalement visible.si le ET logique applique aux deux points extremites d’unsegment est different de 0 alors le segment peut etre rejete.

sinon, on prend l’un des sommets exterieur (il y en a au moins

un) et a partir du premier bit rencontre a 1, on determine lepoint d’intersection avec un cote de la fenetre.

on reitere ainsi le processus jusqu’a ce que les deux codes dechacun des sommets soient a 0000.



http://find/

http://goback/



ClippingDe segments

Algorithme FenSeg(seg , fen)donnees

seg : @segmentfen : fenetre

variablesreg 1, reg 2 : entiersd : droite



http://find/

http://goback/



ClippingDe polygones

L’algorithme de Sutherland-Hodgman (1974) consistefondamentalement a parcourir le polygone dans le senstrigonometrique.

0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 01 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 10 00 00 00 00 00 00 00 00 00 01 11 11 11 11 11 11 11 11 11 1



( )

http://find/

http://goback/



Antialiasing (anticrenelage)

Les algorithmes de generation de traces ont un probleme commun :la creation de bords creneles.

Cet effet indesirable est du au passage du continu au discret : c’est

donc un probleme d’echantillonnage (traitement du signal).

Les techniques misent en œuvre pour reduire cet effet sont connussous le nom d’anticrenelage (antialiasing ) et les primitives (ou lesimages) produites en utilisant ces techniques sont dites

anticrenelees.



A i li i

http://find/

http://goback/



AntialiasingAugmentation de la resolution

Le nombre de crenelures est deux fois plus important mais les sautssont de taille deux fois moindre.

En multipliant par deux la resolution horizontale et vertical d’un

terminal, il est necessaire de quadrupler le cout en memoire, labande passante de la memoire et le temps de discretisation.



A i li i

http://find/

http://goback/



AntialiasingFull Scene Antialiasing

On calcule l’image avec une definition virtuelle plus elevee quecelle du dispositif d’affichage, puis on moyenne les couleurs despixels obtenus pour l’affichage dans une resolution plus basse.

La discretisation se fait a une frequence superieure, multiple de lafrequence cible, c’est le surechantillonnage. Une ponderation estensuite effectuee sur les echantillons ainsi obtenus :

p (x , y ) =n

i =1

w i p i (x , y )

avec generalement w i = 1/n (moyenne uniforme).



A ti li i

http://find/

http://goback/




Application directe au cas n = 4 : on effectue quatre rendussuccessifs avec un leger decalage spatial, puis on effectue un calculde moyenne pour chaque pixel du buffer d’accumulation (aresolution superieure).



A ti li i

http://find/

http://goback/




Moyenne avec ponderation (judicieuse) [Crow] : a une resolutionvirtuelle triple, on utilise le filtre passe-bas bidimensionnel suivant :

1 2 12 4 21 2 1

Ainsi, des surfaces egales donnent une intensite differente enfonction de la distance entre le centre du pixel et la surface.



A ti li i

http://find/

http://goback/



AntialiasingHigh Resolution Antialiasing

nVIDIA : surechantillonnage dont les echantillons influencentplusieurs pixels. Cette methode est plus economique, car on neprend en compte que deux echantillons en moyenne par pixel, etmeilleure que la methode precedente.



Antialiasing

http://find/

http://goback/



AntialiasingEchantillonnage non pondere de surface

Un segment trace a une largeur non nulle, variable le long de satrajectoire (sauf horizontalement et verticalement).

Dans l’espace discret un segment est un rectangle (d’une certaine

largeur) recouvrant partiellement de nombreux pixels, ceux-cicontribuant pour un certain pourcentage.

Du point de vue calculatoire, il est avantageux de considerer lagrille comme une succession de pixels juxtaposes. L’intensite

attribuee a chaque pixel depend du pourcentage de surfacerecouvert par le segment.



Antialiasing

http://find/

http://goback/



AntialiasingEchantillonnage non pondere de surface



Antialiasing

http://find/

http://goback/



AntialiasingEchantillonnage pondere de surface

Plus une aire est pres du centre de la primitive, plus elle a unecontribution elevee.

Soit W (x , y ) une fonction de ponderation, on calcule l’intensite I

d’un pixel comme suit :

I =

aire

W (x , y )dxdy

Rechercher l’integrale de cette fonction de ponderation revient achercher le volume d’intersection d’un cone avec le pixel.



Antialiasing

http://find/

http://goback/



AntialiasingEchantillonnage pondere de surface



Antialiasing

http://find/

http://goback/



AntialiasingPrecalcule de Gupta-Sproull

Le calcul precedent peut se ramener a celui du calcul de la surface

d’un cercle recouvert par une bande : table pre-calculee des valeursd’intensite en fonction de la distance.

Prise en compte des calculs de distance dans l’algorithme deBresenham.



Antialiasing

http://find/

http://goback/



AntialiasingPrecalcule de Gupta-Sproull

Table de Gupta-Sproull pour 8 valeurs :

Ponderation Pas Distance

[0, 1/8] 0 (noir) [1.4, 2]

[1/8, 2/8] 1 [1.2, 1.4][2/8, 3/8] 2 [1.08, 1.2]

[3/8, 4/8] 3 [1, 1.08]

[4/8, 5/8] 4 [0.92, 1]

[5/8, 6/8] 5 [0.8, 0.92]

[6/8, 7/8] 6 [0.6, 0.8]

[7/8, 1] 7 (blanc) [0, 0.6]


http://find/

http://goback/

Documents

trans_algo_2d_td