Petrisor - Bazele Mate Mat Ice Ale Graficii Pe Calculator

download Petrisor - Bazele Mate Mat Ice Ale Graficii Pe Calculator

of 38

Transcript of Petrisor - Bazele Mate Mat Ice Ale Graficii Pe Calculator

Capitolul 1 Bazele matematice ale computer graphicsVersiunea iunie 1999

1.1

Elemente de algebr liniar a a

Spatiul Rn (n = 2, 3) cu structura sa dubl, de spatiu vectorial i a s spatiu an, este fundamental pentru modelarea geometric. a Dei vom dezvolta tehnici de modelare geometric 3D, deseori algos a ritmii implicati folosesc vectori i puncte dintr-un spatiu de dimensiune s n, arbitrar. De aceea reamintim cteva elemente de algebr liniar ce a a a a se folosesc pe parcursul expunerii. Fie V un spatiu vectorial real. O baz acest spatiu este un sistem a n ordonat de vectori liniar independenti, B = (e1 , e2 , . . . , en ), ce genereaz a spatiul V , adic orice vector v V se exprim ca o combinatie liniar a a a unic a vectorilor e1 , e2 , . . . , en : a v = x1 e1 + x2 e2 + + xn en , xi R (1.1)

Scalarii x1 , x2 , . . . , xn se numesc coordonatele sau componentele vectorului v baza B. n Se demonstreaz c dac V exist o baz format din n vectori, a a a n a a a atunci orice alt baz are acelai numr de vectori. Numrul de vectori a a s a a dintr-o baz d dimensiunea spatiului V . a a Exemplul 1 Spatiul vectorial real V = Rn = {(x1 , x2 , . . . , xn )| xi R}. Baza canonic acest spatiu este B = (e1 , e2 , . . . , en ), unde ei = (0, 0 . . . a n 1, . . . , 0), cu 1 pozitia i. In cazul particular n = 3 se folosete i notatia n s s i := e1 , j := e2 , k := e3 .

2

E. Petrior s

Bazele matematicii ale gracii pe calculator

Exemplul 2 : Spatiul vectorial real al functiilor polinoamiale de grad mai mic sau egal cu n: P(R) = {p : R R | p(t) = a0 + a1 t + an tn , ai R} (1.2)

Baza canonic acest spatiu este B = {1, t, t2 . . . , tn }, deci dimensiunea a n spatiului este n + 1. Fie V un spatiu vectorial real de dimensiune n i B = (e1 , e2 , . . . , en ), s B = (e1 , e2 , . . . , en ) dou baze acest spatiu. Exprimnd vectorii bazei a n a B functie de vectorii bazei B: n n

ei =j=1

aij ej , i = 1, n

(1.3)

se asociaz celor dou baze o matrice ptratic TBB , ce are pe coloana i a a a a (i = 1, 2 . . . n) coordonatele vectorului ei baza B: n a11 a21 an1 a12 a22 an2 TBB = . (1.4) . . . . . . . . . . . a1n a2n ann Matricea TBB se numete matricea de trecere de la baza B la B . s Dac un vector xat v V se descompune dup vectorii celor dou a a a baze: v = x1 e 1 + x2 e 2 + + xn e n v = x1 e 1 + x2 e 2 + + xn e n , (1.5) (1.6)

atunci ntre cele dou seturi de coordonate ale lui v exist relatia: a a x1 x1 x x2 2 (1.7) . = TBB . . . . . xn xn modelarea geometric se folosesc functii polinomiale denite In a n special pe [0, 1], care a nu se exprim baza canonic (scrierea polins a n a nomial uzual) ci baza Bernstein: a a nn n n B = (B0 , B1 . . . . , Bn ),

(1.8)

Elemente de algebr liniar a a

3

i i unde Bin (t) = Cn ti (1 t)ni , t [0, 1], i = 0, 1, . . . , n, Cn ind combinri de n elemente luate cte i. a a cazul particular n = 3, avem: In 3 B0 (t) 3 B1 (t) 3 B2 (t) 3 B3 (t)

= = = =

0 C3 (1 t)3 = 1 3t + 3t2 t3 1 C3 t(1 t)2 = 3t 6t2 + 3t3 2 C3 t2 (1 t) = 3t2 3t3 t3 .

(1.9)

Astfel matricea de trecere de la baza Bernstein la baza canonic B = a (1, t, t2 , t3 ) este: 1 0 0 0 3 3 0 0 TBB = (1.10) 3 6 3 0 1 3 3 1 Pe parcursul expunerii tehnicilor de modelare geometric, manipulare i a s vizualizare a obiectelor computationale create, vom deni noi tipuri de variabile i macrouri. s Pentru a declara vectori din Rn denim tipul de date Vector ca un pointer la double: typedef double *Vector; Dimensiunea spatiului din care considerm un Vector devine ex a plicit cnd alocm memorie pentru el. Alocarea se poate realiza folosind, a a a de exemplu, macroul: #define aloca_vector(nume_v,n)\ if(NULL==((nume_v)= ((double *)\ calloc(n,sizeof(double)))))\ exit(fprintf(stderr," alocare esuata (nume_v) \n")) (Caracterul backslash \ indic faptul c denitia continu pe linia urma a a a toare). Pe lng alocare se testeaz i dac aceasta a euat sau nu. a a as a s Secventa: Vector v; aloca_vector(v,3); denete un vector din R3 (dac a fost inclus ierul header adecvat). s a s Denim de asemenea i tipul Matrice: s typedef double **Matrice;

4

E. Petrior s

Bazele matematicii ale gracii pe calculator

Includem continuare codul C pentru cteva functii ce descriu open a ratii cu vectori i matrici. s Functia vector_copiaza copiaz un vector alt vector: a n void vector_copiaza(Vector v, Vector w, int n) { while( --n >= 0 ) w[n] = v[n]; } scalar_vector nmultete un vector cu un scalar: s void scalar_vector(Vector v, double scalar, Vector rez, int n) { while( --n >= 0 ) rez[n] = scalar*v[n]; } vector_aduna adun doi vectori: a void vector_aduna(Vector v1, Vector v2, Vector suma, int n) { while( --n >= 0 ) suma[n]=v1[n]+v2[n]; } vector_scade scade doi vectori: void vector_scade(Vector v1, Vector v2, Vector dif, int n) { while( --n >= 0 ) dif[n]=v1[n]-v2[n]; } Functiile urmtoare opereaz asupra matricilor. prealabil denim a a In macroul: #define aloca_array(nume, tip, nr) \ if (NULL == ((nume) = (tip *) \ malloc ((unsigned) ((nr) * sizeof(tip))))) \ exit(fprintf(stderr," alocare esuata (nume) \n"))

Elemente de algebr liniar a a

5

care aloca nr locatii de memorie pentru un pointer la tip i testeaz s a dac alocarea a euat sau nu. a s Functia creeaza_matrice creeaz o matrice ptratic de tip n n i a a a s elemente 0: Matrice creeaza_matrice(int n) { Matrice M; int lin; aloca_array(M, Vector, n); for(lin = 0; lin < n; lin++) aloca_vector(M[lin],n); return(M); } free_matrice elibereaza zona de memorie alocat unei matrici: a void free_matrice(Matrice M, int n) { int lin; if(M != NULL) { for(lin = 0; lin < n; lin++) free(M[lin]); free(M); } } void produs_matrici(Matrice A, Matrice B, Matrice C, int n) /* Calculeaza produsul a doua matrici patratice */ { int i, j, k; double total; for(i= 0; i< n; i++)

6

E. Petrior s

Bazele matematicii ale gracii pe calculator

{ for(j = 0; j < n; j++) { for(k = 0, total = 0.0; k < n; k++) total += A[i][k] * B[k][j]; C[i][j] = total; } } } void transpusa_matrice(Matrice M, Matrice Mt, int n) { int i, j; for(i= 0; i< n; i++) for(j = 0; j < n; j++) Mt[i][j] = M[j][i]; } Produsul scalar a doi vectori v = (x1 , x2 , . . . , xn ), w = (y1 , y2 , . . . , yn ) din Rn se denete prin: sn

vw =i=1

xi y i

(1.11)

Perechea (Rn , ) se numete spatiu vectorial euclidian. s double produs_scalar(Vector v, Vector w, int n) { double prod = 0.0; while(0 0, i norma egal cu 1. s s a s a Astfel: v v0 = . (1.13) v Functia C norma_vector calculeaz norma unui vector: a double norma_vector(Vector v, int n) { double suma = 0.; while(--n >=0) suma += v[n] * v[n]; return(sqrt(suma)); } versor calculeaz versorul unui vector. Cum calculul versorului se a n mparte vectorul la norma sa, testm a nainte de artire ordinul de mp prealabil denim: mrime al normei. In a #define epsilon 1e-6 Dac norma este mai mic dect eps, vectorul este interpretat ca vectorul a a a nul. void versor(Vector v, Vector v0,int n) { double norm; norm=norma_vector(v,n); if(norm< epsilon) { fprintf(stderr,"\n Vector de norma 0"); exit(1); } else scalar_vector(v,1./norm,v0,n); } Avnd denit functia produs_scalar o putem utiliza denirea proa a n dusului unei matrici ptratice cu o matrice coloan (un Vector): a a

8

E. Petrior s

Bazele matematicii ale gracii pe calculator

void produs_matrice_vector(Matrice A, Vector x, Vector b, int n) { int i; for(i = 0;i < n;i++) b[i] = produs_scalar(A[i], x, n); } Denitia 1.1.1 Doi vectori v, w Rn al cror produs scalar este egal a cu zero se numesc vectori ortogonali. O baz B = (u1 , u2 , . . . , un ) Rn ai crei vectori sunt ortogonali doi a a cte doi, adic ui uj = 0 i = j, i ui = 1, i = 1, n, se numete baz a a s s a ortonormat. a Dac B, B sunt dou baze ortornormate, atunci matricea de trecere a a T = TBB este o matrice ortogonal, adic veric relatia: a a a T T = T T = In (1.14)

Aceast relatie implic c determinantul unei matrici ortogonale este a a a det(T ) = 1 i c inversa unei matrici ortogonale coincide cu transpusa s a sa: T 1 = T . spatiul vectorial R3 In nzestrat cu produsul scalar (1.11) se denete s produsul vectorial a doi vectori v(x1 , x2 , x3 ), w(y1 , y2 , y3 ), notat v w. Si anume, vectorul v w, este vectorul cu proprietatea c produsul su a a 3 scalar cu orice vector u(z1 , z2 , z3 ) R , coincide cu produsul mixt al vectorilor v, w, u, notat (v w u): (v w)u = (v w u) = x1 x2 x3 y1 y2 y3 z1 z2 z3 (1.15)

Coordonatele vectorului v w baza canonic se obtin din dezn a voltarea determinantului formal: vw = e1 e2 e3 x1 x2 x3 y1 y2 y3 = x1 x2 x1 x3 x2 x3 e e + e y1 y2 3 y1 y3 2 y2 y3 1 (1.16) Functia produs_vectorial implementeaz aceste calcule: a

Elemente de algebr liniar a a

9

void produs_vectorial(Vector v, Vector w, Vector produs) { produs[0] = v[1]*w[2] - v[2]*w[1]; produs[1] = v[2]*w[0] - v[0]*w[2]; produs[2] = v[0]*w[1] - v[1]*w[0]; } Produsul vectorial a doi vectori este anticomutativ: v w = w v (1.17)

i vectorul v w este ortogonal pe v i w. s s Baza canonic (care este ortonormat) se comport fat de produsul a a a a vectorial astfel: e1 e2 = e3 e2 e3 = e1 e3 e1 = e2 (1.18)

Dou baze B, B din Rn pentru care determinantul matricii de trecere a de la o baz la alta este pozitiv, det(TBB ) > 0, se numesc baze la fel a orientate. O baz ortonormat B = (u1 , u2 , u3 ) din spatiul Rn care este a a la fel orientat ca baza canonic se numete baz dreapt sau pozitiv a a s a a 3 orientat. Problema construirii unei baze R , pozitiv orientat, are a n a o deosebit important modelarea geometric i computer graphics. a a n a s Propozitia urmtoare este foarte util construirea unei astfel de baze: a a n Propozitia 1.1.1 Baza ortonormat B = (u1 , u2 , u3 ) din R3 este o baz a a dreapt dac i numai dac este vericat una din relatiile: a as a a u1 u 2 = u3 u2 u 3 = u1 u3 u 1 = u2 . (1.19)

Demonstratie: Presupunem c baza B este o baz dreapt. Din pro a a a prietile produsului vectorial rezult c u1 u2 = u3 , = 0. Conform at a a ipotezei, det(TBB ) > 0 (bazele ind ortonormate, det(TBB ) = 1). Cum det(T ) = det(T ), rezult c produsul mixt (u1 u2 u3 ) = 1 i prin a a s urmare (u3 )u3 = 1, adic = 1 i deci u1 u2 = u3 . a s Reciproc, presupunem c u1 u2 = u3 . Atunci (u1 u2 u3 ) = a (u1 u2 )u3 = ||u1 u2 ||2 > 0, adic baza B este pozitiv orientat. a a

10 E. Petrior s

Bazele matematicii ale gracii pe calculator

Cu alte cuvinte o baz ortonormat din R3 care se comport fat de a a a a produsele vectoriale a doi cte doi vectori, la fel ca baza canonic, este a a baz dreapt. a a

1.2

Notiuni de geometrie an a

Spatiul de lucru modelarea geometric este spatiul punctual an eu n a 3 clidian E . De aceea reamintim cteva notiuni i rezultate de geometrie a s an, care vor folosite prezentarea metodelor de modelare a curbelor a n i suprafetelor de form liber. s a a Considerm spatiul vectorial Rn ale crui elemente le interpretm a a a simultan ca puncte i vectori. Oricrei perechi de puncte (a, b) Rn Rn s a asociem vectorul ab := b a. Notm prin A : Rn Rn Rn aplicatia i a care realizeaz aceast corespondenta. Spunem c A denete o structur a a a s a n n an pe R . Spatiul an ndimensional A este denit de perechea a (Rn , A). Elementele sale sunt puncte. Din relatia ab := b a, rezult a c b = a + v, cu v = ab. Prin urmare are sens suma dintre un punct i a s un vector, rezultatul ind un punct, adic a + v este unicul punct b cu a proprietatea c ab = v. a Un reper cartezian spatiul an An , este denit de un punct x n o, numit originea reperului i o baz B = (e1 , e2 , . . . , en ) spatiul s a n Rn . Notm un reper cartezian prin : R = (o; e1 , e2 , . . . , en ). Dat a ind un punct p Rn , vectorul are o unic exprimare baza B: op a n = n x e . Numerele reale din nuplul (x , x , . . . , x ) se numesc op 1 2 n i=1 i i coordonatele punctului p relativ la reperul R. Fixnd un reper cartezian a R = (o; e1 , e2 , . . . , en ) spatiul an An , putem identica spatiul vecton rial Rn cu spatiul an An prin bijectia: w Rn o + w An (1.20)

Dat ind un sistem de puncte {p1 , p2 , . . . , pm } din An i m numere reale s 1 , 2 , . . . , m , astfel at m i = 1, combinatia de puncte: nc i=1 1 p1 + 2 p2 + + m pm (1.21) are sens geometric, reprezentnd un punct. a Intr-adevr, exprimnd 1 = a a 1 2 m , combinatia de puncte devine: (1 2 m )p1 + 2 p2 + m pm = p1 + 2 (p2 p1 ) + + m (pm p1 ) = p1 + 1 p2 + + 1m p pp (1.22)

Notiuni de geometrie an a

11

Cum operatia punct plus vector are sens, rezult c exist un unic punct a a a p astfel at: nc p = p1 + 1 p2 + + 1m = p pp (1.23) 1 p1 + 2 p2 + + m pm Denitia 1.2.1 Fie {p1 , p2 , . . . , pm } un sistem nit de puncte din An . Punctul p An pentru care exist scalarii i , i = 1, m, m i = 1, a i=1 astfel at nc p = 1 p1 + 2 p2 + + m pm (1.24) se numete combinatie an sau baricentric a punctelor pi , i = 1, m. s a a Denitia 1.2.2 Sistemul de puncte {p0 , p2 , . . . , pm } din An cu propri etatea c cel putin un punct al sistemului se poate exprima ca o combinaa ie an a celorlalte puncte se numete sistem an dependent. Sistemul t a s se numete an independent dac nu este dependent sau este constituit s a dintr-un singur punct. Pentru a verica dependenta sau independenta unui sistem de puncte folosim rezultatul dat de : Propozitia 1.2.1 Sistemul de puncte {p0 , p2 , . . . , pm } din An este an dependent dac i numai dac sistemul de vectori 0, i = 1, m, din Rn as a p i p este liniar dependent. Demonstratie: Presupunem c sistemul de puncte este format din punc a te distincte, an dependente i prin urmare cel putin un punct, s zicem s a pm , se poate exprima ca o combinatie an a celorlate puncte: am1

pm = 0 p0 + 1 p1 + + m1 pm1 , i R,i=0

i = 1

(1.25)

Aceast relatie este echivalent cu: a a pm = (1 1 m1 )p0 + 1 p1 + + m1 pm1 , sau = p + + p0 pm m1 p0 pm1 1 p0 1 (1.26) (1.27)

Ipoteza c sistemul considerat, punctele sunt distincte, ne asigur c a n a a relatia (1.27) cel putin un scalar este nenul, deci vectorii sunt liniar n dependenti.

12 E. Petrior s

Bazele matematicii ale gracii pe calculator

Reciproc, presupunem c vectorii (0 p1 , . . . , 0 pm1 ) sunt liniar dea p p pendenti, adic exist scalarii 1 , . . . , m1 , nu toti nuli, astfel at s a a nc a avem relatia: 1 0 p1 + 2 0 p2 + + 0m = 0 p p pp (1.28) Dac := 1 + 2 + + m = 0, atunci relatia (1.28) este echivalent a a cu: 1 m p0 = p1 + + pm , (1.29) adic punctele pi , i = 0, m, sunt an dependente. a Dac 1 + 2 + + m = 0, atunci cum cel putin un i este nenul, a putem presupune, de exemplu, c 1 = 0. Astfel 1 = 2 m i a s relatia (1.28) este echivalent cu: a p1 = 2 m p2 pm , 1 1 (1.30)

adic p1 este o combinatie an de puncte. a a Drept consecint, un sistem de n + 1 puncte an independente din An , a (p0 , p1 , . . . , pn ) denete o baz B = (0), i = 1, n Rn . s a p i p n Denitia 1.2.3 Un sistem ordonat de n + 1 puncte an independente din An se numeste reper an. Fie Ra = (a0 , a1 , . . . , an ) un reper an i p un punct arbitrar, dar xat s n ), i = 1, n, constituie o baz Rn , vectorul A . Cum vectorii (a0 ai n a n p se exprim mod unic ca o combinatie liniar a vectorilor bazei: a0 a n a p = x + + x a , x R, i = 1, n, a0 1 a0 a1 n a0 n i sau echivalent: p = (1 x1 xn )a0 + x1 a1 + xn an , (1.32) (1.31)

adic punctul p se exprim mod unic ca o combinatie baricentric a a a n a punctelor ce denesc reperul an. Dup aceast prezentare general s particularizm aceste notiuni a a a a a i rezultate de geometrie an la cazurile de interes pentru modelarea s a geometric: A2 , respectiv A3 . a Capitolul 11 vom avea nevoie, pentru denirea peticelor triunghiuIn lare de suprafata Bzier, de coordonatele baricentrice ale unui punct din e

Notiuni de geometrie an a

13

A2 relativ la un reper an Ra = (t1 , t2 , t3 ). Aria compactului triunghiular de vrfuri t1 , t2 , t3 este: a 1 aria(t1 , t2 , t3 ) = 2 1 1 1 t11 t21 t31 , t12 t22 t32 (1.33)

unde (ti1 , ti2 ), i = 1, 3 sunt coordonatele punctelor ti relativ la un reper cartezian xat A2 . Deoarece n 1 1 1 t11 t21 t31 t12 t22 t32 = 1 0 0 t11 t21 t11 t31 t11 , t12 t22 t12 t32 t12 (1.34)

valoarea pozitiv sau negativ a determinantului aduce o informatie a a n 2 plus despre orientarea bazei (t1 t2 , t1 t3 ) din R : dac aria(t1 , t2 , t3 ) este a pozitiv (negativ), atunci baza este pozitiv (negativ) orientat. a a a n a Propozitia 1.2.2 Fie Ra = (t1 , t2 , t3 ) un reper an A2 , ale crui puncte au relativ la un reper cartezian xat coordonatele: (ti1 , ti2 ), i = 1, 3. Coordonatele baricentrice ale unui punct u A2 , relativ la reperul an Ra sunt: 1 (u) = aria(u, t2 , t3 ) aria(t1 , u, t3 ) aria(t1 , t2 , u) , 2 (u) = , 3 (u) = aria(t1 , t2 , t3 ) aria(t1 , t2 , t3 ) aria(t1 , t2 , t3 ) (1.35)

Demonstratie: Punctul u are o unic scriere ca i combinatie baricen a s tric a punctelor t1 , t2 , t3 : a3

u = 1 (u)t1 + 2 (u)t2 + 3 t3 , i R,i=1

i = 1

(1.36)

Dac relativ la reperul cartezian xat, punctul u are coordonatele (u1 , a u2 ), atunci coordonatele baricentrice ale punctului u sunt solutiile sis temului liniar: 1 + 2 + 3 = 1 1 t11 + 2 t21 + 3 t31 = u1 (1.37) 1 t12 + 2 t22 + 3 t32 = u2

14 E. Petrior s

Bazele matematicii ale gracii pe calculator

Determinantul sistemului este: 2aria(t1 , t2 , t3 ) = 1 1 1 t11 t21 t31 t12 t22 t32 (1.38)

Cum aceste puncte sunt an independente, ele sunt necoliniare, deci aria(t1 , t2 , t3 ) = 0 i sistemul are solutia unic: s a 1 (u) = aria(u, t2 , t3 ) aria(t1 , u, t3 ) aria(t1 , t2 , u) , 2 (u) = , 3 (u) = aria(t1 , t2 , t3 ) aria(t1 , t2 , t3 ) aria(t1 , t2 , t3 ) (1.39)

Fie a0 , a1 dou puncte distincte An . Orice combinatie baricentric a a n a acestor dou puncte, p = (1 t)a0 + ta1 , t R, este un punct apartinnd a a dreptei (a0 a1 ), ce contine cele dou puncte (dreapta (a0 a1 ), este imaginea a lui R prin aplicatia r : R An , r(t) = a0 + t ). Observm c a 1 a a 0a r(0) = a0 , r(1) = a1 . Denitia 1.2.4 Submultimea punctelor dreptei (a0 a1 ), notat [a0 , a1 ] i a s denit prin: a [a0 , a1 ] = {p An | p = (1 t)a0 + ta1 , t [0, 1]} (1.40)

se numete segment de extremiti a0 , a1 sau interpolantul an al celor s at dou puncte a O notiune simpl, dar foarte important generarea cubicelor spline i a a n s interpolarea spline cubic, este raportul care un punct p divide un a n segment [a, b]. Propozitia 1.2.3 Fiind date punctele distincte a, b An , pentru ecare punct p L, p = b, exist un scalar unic r R, astfel at = rpb. a nc ap Demonstratie: Un punct p L se exprim mod unic ca o combinatie a n baricentric a punctelor a, b: p = a + b, , R, + = 1. Astfel a putem scrie: ( + )p = a + b, ceea ce este echivalent cu = pb, ap Ipoteza p = b ne asigur c = 0, i deci = rpb, cu r = . a a s ap Denitia 1.2.5 Fie a, b dou puncte distincte din An i p L, astfel a s = r Numrul real r se numete raportul care punctul p nct ap a pb. a s n divide sau mparte segmentul [a, b].

Notiuni de geometrie an a

15

Observm c dac raportul r > 0, punctul p apartine segmentului deschis a a a (a, b), iar dac r < 0, atunci p L [a, b]. a Propozitia 1.2.4 Dac punctul p divide segmentul [a, b] raportul a n = 1, atunci: p= a+ b (1.41) + + Demonstratie: Conform ipotezei, = pb, sau formele echiva ap n lente = pb, respectiv, (p a = (b p). Astfel rezult c: ap a a p= a+ b + + (1.42)

Ca o regul, ce va des aplicat Capitolul 3, retinem c: a a n a

Dac p = (1 )a + b, R \ {1}, atunci a raportul care punctul p n mparte segmentul [a, b] este r =

1

i reciproc, s Dac p a mparte segmentul [a, b] raportul r = = 1, n a+ b atunci p = + +

continuare prezentm notiunea de baz din geometria computatiIn a a onal, convexitatea. a

16 E. Petrior s

Bazele matematicii ale gracii pe calculator

1.2.1

Multimi convexe An n

Denitia 1.2.6 O submultime nevid C An cu proprietatea c o a a dat cu dou puncte a0 , a1 C contine i segmentul [a0 , a1 ] se numete a a s s multime convex. a Simbolic, denim convexitatea prin una din formele echivalente: a0 , a1 C (1 t)a0 + ta1 C, t [0, 1] (1.43) a0 , a1 C 0 a0 + 1 a1 C, 0 , 1 0, 0 + 1 = 1 (1.44) Evident, c multimea C An este convex dac i numai dac oricare a a as a ar sistemul nit de puncte {a1 , a2 , . . . , am } C, orice combinatie bari centric cu coecienti pozitivi a punctelor ai , i = 1, m: a m

1 a1 + + m am , i 0,i=1

i = 1

(1.45)

Fig. 1.1: Multime convex A2 (stnga) i multime neconvex (dreapta). a n a s a

Denitia 1.2.7 Fie {a1 , a2 , . . . , am } un sistem nit de puncte din An . Un punct p An ce se exprim ca o combinatie baricentric cu coecienti a a pozitivi, a punctelor ai , i = 1, m:m m

p=i=1

i ai , i 1,i=1

i = 1

(1.46)

se spune c este o combinatie convex a punctelor ai , i = 1, m. a a

apartine multimii C.

Notiuni de geometrie an a

17

Este un simplu exercitiu s artm c intersectia C, C = iI Ci , a a aa a oricrei familii (Ci )iI de multimi convexe din An este o multime convex. a a as a Denitia 1.2.8 Infurtoarea convex a unei submultimi A An este a n intersectia tuturor multimilor convexe din A ce contin multimea A. Cu alte cuvinte aurtoarea convex a multimii A An este cea mai nfs a a mic multime convex din An ( sensul relatiei ), ce contine multimea a a n cele ce urmeaz notm cu I(A) aurtoarea convex a multimii A. In a a nfs a a A. Propozitia 1.2.5 Fie A1 , A2 An i A = A1 A2 . Atunci: s I(A) = I(I(A1 ) A2 ). (1.47)

Demonstratie: Deoarece A1 A2 I(A1 ) A2 , rezult c I(A) a a I(I(A1 ) A2 ). Pe de alt parte, I(A) este o multime convex ce contine a a pe I(A1 ) i pe A2 , deci I(A1 ) A2 I(A), adic s a I(I(A1 ) A2 ) I(I(A)) = I(A). concluzie, I(A) = I(I(A1 ) A2 ). In modelarea geometric prin curbe i suprafete Bzier sau Bspline inIn a s e tervine aurtoarea convex a unui numr nit de puncte: nfs a a a {b0 , b1 , . . . , bm }. as a Propozitia 1.2.6 Infurtoarea convex a multimii de puncte a {b0 , b1 , . . . , bm } (1.49) (1.48)

coincide cu multimea tuturor combinatiilor convexe ale acestor puncte, adic: am m

I(b0 , b1 , . . . , bm ) = {p A | p =i=0

n

i pi , i 0,i=0

i = 1} (1.50)

Demonstratie: Fie Cm = {p An | p = m i pi , i 0, m i = i=0 i=0 1}. Dac p, q Cm , atunci se veric prin calcul direct c i (1 )p + a a as q Cm , deci Cm este multime convex. Mai mult multimea Cm contine a toate punctele bi , i = 0, m, pentru c: a bi = 0b0 + + 1bi + + 0bm (1.51)

18 E. Petrior s

Bazele matematicii ale gracii pe calculator

Cum I(b0 , b1 , . . . , bm ) este cea mai mic multime convex ce contine a a punctele bi , i = 0, m, rezult c I(b0 , b1 , . . . , bm ) Cm . a a Reciproc, s artm c Cm I(b0 , b1 , . . . , bm ). a aa a Demonstrm aceast incluziune prin inductie asupra numrului de a a a puncte: Pentru m = 1, e p C1 . Rezult c exist [0, 1] astfel at a a a nc p = (1 )b0 + b1 , adic p [b0 , b1 ]. Cum segmentul [b0 , b1 ] este a cea mai mic multime convex ce contine punctele b0 , b1 , rezult c a a a a [b0 , b1 ] = I(b0 , b1 ), deci C1 I(b0 , b1 ). Presupunem c Cm1 I(b0 , b1 , . . . , bm1 ) i aceast ipotez s a s n a a a demonstrm c i Cm I(b0 , b1 , . . . , bm ). Pentru aceasta vom arta c a as a a aurtoarea convex a multimii A = I(b0 , b1 , . . . , bm1 ) {bm } coinnfs a a cide cu reuniunea tuturor segmentelor [q, bm ], unde q parcurge multimea I(b0 , b1 , . . . , bm1 ). Notm a [q, bm ]. (1.52) B :=qI(b0 ,...,bm1 )

Orice multime convex ce contine multimea A, contine i multimea B. a s consecinta pentru a arta c I(A) = B, este sucient s artm c B In a a a aa a este convex. a Fie a, c B. Atunci exist q1 , q2 I(b0 , . . . , bm1 ) astfel at a nc a [bm , q1 ] i c [bm , q2 ]. Excluznd cazurile banale care a, c s a n coincid cu bm sau respectiv cu q1 , q2 , avem: a = (1 )bm + q1 , 0 < < 1 c = (1 )bm + q2 , 0 < < 1 Deoarece un punct p [a, c] admite exprimarea: p = 1 a + 2 c, 1 , 2 0, 1 + 2 = 1, avem innd seama de (1.53) c: t a a p = (1 )bm +1 q1 +2 q2 , unde = 1 +2 i 0 < < 1. (1.56) s 2 1 q1 + q2 . d ind o combinatie convex a punctelor a q1 , q2 I(b0 , b1 . . . , bm1 ), rezult c d I(b0 , b1 . . . , bm1 ). Astfel a a Fie punctul d := p = (1 )bm + d, (1.57) (1.55) (1.53) (1.54)

Notiuni de geometrie an a

19

adic p [bm , d]. a concluzie am artat c dac a, c B, atunci orice punct p din [a, c] In a a a apartine multimii B, adic [a, c] B i deci B este multime convex. a s a Prin urmare: I(I(b0 , b1 , . . . , bm1 ) {bm }) = B (1.58) Conform relatiei (1.47) avem: I (I(b0 , b1 , . . . , bm1 ) {bm }) = I(I(b0 , b1 , . . . bm1 )) {bm } = I(b0 , b1 , . . . , bm ) (1.59)

sfrit s artm c Cm I(b0 , b1 , . . . , bm ). In a s a a a a Fie p Cm . Rezult c exist i 0, i = 0, m, m i = 1, astfel a a a i=0 at p = m i bi . Notm cu := 0 + 1 + + m1 i e nc a s i=0 q= 0 1 m1 b0 + b1 + + bm1 Cm1 I(b0 , . . . , bm1 ). (1.60)

Astfel p = q + (1 )bm1 [q, bm1 ] B. Conform celor de mai sus, rezult c p I(b0 , . . . bm ). a a Pentru un numr redus de puncte relatia a I(I(b0 , . . . , bm1 ) {bm }) = I(b0 , . . . , bm1 , bm ) (1.61)

ne ajut s intuim rapid cine este aurtoarea lor convex. De exema a nfs a a n plu, avnd {b0 , b1 , b2 } A , I(b0 , b1 ) = [b0 , b1 ], iar I(b0 , b1 , b2 ) = a qI(b0 ,b1 ) [q, b2 ] (Fig.1.2). Deci aurtoarea convex a multimii {b0 , b1 , b2 } este multimea nfs a a avnd drept frontier triunghiul de vrfuri b0 , b1 , b2 . a a a Relatia I(I(b0 , . . . , bm1 ) {bm }) = I(b0 , . . . , bm1 , bm ) st la baza a algoritmilor de determinare a aurtorii convexe a unei multimi nite nfs a de puncte din A2 sau A3 [ORourke, 1994].

1.2.2

Aplicatii ane

Denitia 1.2.9 O aplicatie : An Am care pstreaz combinatiile a a baricentrice, adic: a (a + b = (a) + (b), a, b An , i , R, + = 1, s (1.62) se numete aplicatie an. s a

20 E. Petrior s

Bazele matematicii ale gracii pe calculator

Fig. 1.2: aurtoarea convex a trei puncte. Infs a a

Propozitia 1.2.7 Aplicatia : An Am este an dac i numai a a s n m dac exist aplicatia liniar T : R R astfel at pentru orice punct a a a nc o An arbitrar, dar xat, (p) = T ( + (o), p An . op) (1.63)

Demonstratie: Presupunem c aplicatia este an. Fixm punc a a a n tul o A i notm o = (o). Astfel spatiul vectorial Rn este s a n corespondenta bijectiv cu multimea vectorilor { | p An }. Denim a op aplicatia T : Rn Rm prin T ( = o (p). S artm c T este op) a aa a aplicatie liniar, adic: a a T ( = T ( op) op), R, p An i s T ( + = T ( + T ( op oq) op) oq), p, q An (1.64) (1.65)

Pentru aceasta e punctele p, q An , astfel at = R. nc oq op, Aceast ultim relatie este echivalent cu: q o = (p o), adic, a a a a q = (1 )o + p. Prin urmare (q) = (1 )(o) + (q) sau echivalent o (q) = o (p), adic T ( = T ( a oq) op). 1 1 1 Fie acum a, p, q An astfel at a = p + q, adic = + nc a oa op 2 2 2 1 1 oq. Atunci (a) = 1 (p) + 1 (q) sau echivalent (a) o = 2 ((p) 2 2 2 1 o ) + 1 ((q) o ), adic o (a) = 1 o (p) + 2 o (q), sau a T ( = a nc oa) 2 2 1 T ( + 1 T ( Cum am demonstrat deja c T este omogen, rezult op) oq). a a a c T este aditiv, deci aplicatie liniar. a a a2 2

Notiuni de geometrie an a

21

Din relatia de denitie a aplicatiei T , rezult c (p) = T ( a a op)+(o). n Reciproc, presupunem c exist aplicatia liniar T : R Rm astfel a a a n + (o), p An . at pentru orice punct o A xat, (p) = T (op) nc Prin calcul direct se veric imediat c aplicatia este an. a a a concluzie o aplicatie an : An Am este unic determinat de o In a a n pereche de puncte corespondente o, o i o aplicatie liniar T : R Rm . s a T se numete partea liniar a aplicatiei ane. s a Relativ la dou repere carteziene xate An , respectiv Am , dac a n a n un punct arbitrar p A are coordonatele (xi ), i = 1, n, iar (p), coordonatele (Xj ), j = 1, m, atunci notnd cu (bj ), j = 1, m coordonatele a punctului (o) (o ind originea reperului din An ) avem:n

Xj =k=1

ajk xk + bj , j = 1, m,

(1.66)

unde (ajk ), j = 1, m, k = 1, n, este matricea prtii liniare T relativ la a baza reperului din spatiul An . Detaliat, expresia analitic a unei aplicatii ane este a (x1 , x2 , . . . , xn ) = (X1 , X2 , . . . , Xm ), unde: X1 X2 . . . Xm a11 a21 . . . a12 a22 . . . a1n . . . a2n . ... . . x1 x2 . . . xn b1 b2 . . . bm (1.68) (1.67)

=

+

am1 am2 . . . amn

a a Denitia 1.2.10 O nform an pe spatiul an Ad este o aplicatie d d d : A A . . . A R, care este an ecare variabil: a n an

(p1 , . . . , 1 qi1 + 2 qi2 , . . . , pn ) = 1 (p1 , . . . , qi1 , . . . , pn ) + 2 (p1 , . . . , qi2 , . . . , pn ) . qi1 , qi2 Ad , i = 1, n, 1 , 2 R, 1 + 2 = 1. nforma an este simetric dac a a a (p(1) , . . . , p(i) , . . . , p(n) ) = (p1 , . . . , pi , . . . , pn ), pentru orice permutare a indicilor (1, 2, . . . , n). Vom reveni asupra nformelor ane Capitolul 6. n

(1.69)

(1.70)

22 E. Petrior s

Bazele matematicii ale gracii pe calculator

1.2.3

Elemente de geometrie euclidian a

continuare considerm spatiul an ndimensional, avnd spatiul vecIn a a n acest contorial subiacent R , nzestrat cu produsul scalar (1.11). In text ((Rn , ), A) se noteaz En i se numete spatiul an euclidian n a s s dimensional. Toate rezultatele stabilite spatiul An sunt valabile i n s n n spatiul E , dar plus avem notiuni i rezultate noi denite cu ajutorul n s produsului scalar. En este spatiu metric relativ la distanta denit prin: a d(a, b) := ab , a, b En . (1.71) Un reper ortornormat En este denit de un punct x o, numit n origine i o baz ortornomat B = (e1 , e2 , . . . , en ). Notm reperul prin s a a a R = (o, B). Reperului ortornormat R i se asociaz sistemul de axe a ortogonale oxi , i = 1, n, oxi = {p E3 | = ei , > 0}. op modelarea geometric, cel mai adesea curbele i suprafetele se raIn a s porteaz la repere ortonormate din spatiul de modelare E3 . a implementrile ce urmeaz, declarm un punct din En ca un Vector. In a a a

Fig. 1.3: Sisteme de axe E2 asociate unui reper drept, respectiv stng. n a

Un reper ortornormat drept(strmb) En este un reper care baza a n n corespunztoare este la fel (opus) orientat ca baza canonic din Rn . a a a In 2 cazul particular al lui E dac reperul ortornormat R = (o; (u1 , u2 )) este a drept, adic determinantul matricii de trecere de la baza canonic la baza a a (u1 , u2 ) este pozitiv, atunci sistemul de axe ox1 x2 asociat reperului R este astfel at ox2 se obtine din ox1 printr-o rotatie de centru o sens nc n trigonometric cu /2 (vezi Fig. 1.3). Rezult atunci c reperul asociat a a ecranului unui PC cu originea o, coltul stnga-sus, axa ox1 avnd n a a directia colt stnga suscolt dreapta-sus, iar ox2 colt stnga-suscolt a a

Notiuni de geometrie an a

23

stnga-jos nu este un reper drept, ci unul strmb (vezi Fig.1.3, dreapta). a a Fig.1.4 sunt aate dou sisteme de axe de coordonate E3 , primul In s a n drept i cel de-al doilea strmb (adic rotind burghiul perpendicular s a a pe planul x1 ox2 , sensul de la ox1 spre ox2 , acesta n nainteaz sens a n opus lui ox3 ).

Fig. 1.4: Sisteme de axe E3 asociate unui reper drept, respectiv stng. n a

Fiind date reperele ortonormate: R = (o; (e1 , e2 , e3 )), R = (o ; (e1 , e2 , e3 )), (1.72)

cu sistemele de axe asociate ox1 x2 x3 , respectiv ox1 x2 x3 , i tiind c puncs s a tul o are relativ la reperul R coordonatele (x0 , x0 , x0 ), relatiile dintre 1 2 3 coordonatele (x1 , x2 , x3 ), respectiv (x1 , x2 , x3 ), ale unui punct arbitrar a raportat la cele dou repere sunt: a xi = xi x0 , i = 1, 2, 3 i (1.73)

Calculul coordonatelor punctului a noul reper R este realizat de n secventa: Vector Op, a, b; /* a contine coordonatele in reperul R, iar b in R Op este originea noului reper*/ vector_scade(a, Op,b,3); cazul care E2 se consider reperul ortonormat strmb R = In n n a a (E; u1 , u2 ) asociat ecranului unui calculator, de axe Ex1 x2 i relativ la s a acest sistem punctul o are coordonatele (x0 , x0 ), atunci considernd repe2 1 ntre rul drept R = (o; u1 , u2 ), cu sistemul de axe ox1 x2 (vezi Fig.1.5),

24 E. Petrior s

Bazele matematicii ale gracii pe calculator

Fig. 1.5: Sistemul de axe al ecranului i un sistem drept, cu originea pe ecran. s

coordonatele (x1 , x2 ) ale unui pixel p, cu 0 x1 pixxM, 0 x2 pixyM ((pixxM + 1) (pixyM + 1) este rezolutia ecranului), i coordo s natele (x1 , x2 ) ale acestuia relativ la R exist relatiile a x1 = x1 + x0 1 0 x2 = x2 x2

procesul de manipulare i vizualizare a obiectelor computationale In s n din E , n = 2, 3, se aplic acestora transformri geometrice, adic transa a a formri care au ca efect schimbarea pozitiei i a dimensiunii obiectului. a s Transformrile cele mai folosite sunt transformrile ane, adic aplicatii a a a ane cu partea liniar nedegenerat (matricea prtii liniare este nesingua a a lar). a Dac En este raportat la reperul ortonormat R, avnd sistemul de axe a a asociat, oxi , i = 1, n, atunci o transformare an A : En En are relaa tiv la reperul dat expresia analitic (x1 , x2 , . . . , xn ) = (X1 , X2 , . . . , Xn ), a unde: X = Ax + b, X = [X1 , X2 , . . . , Xn ] , x = [x1 , x2 , . . . , xn ] , A este matricea nesingular a prtii liniare a aplicatiei ane, iar b(b1 , b2 , . . . , bn ) a a En . Detaliat, avem: X1 X2 . . . Xn = a11 a21 . . . a12 a22 . . . . . . a1n a2n . . . x1 x2 . . . xn + b1 b2 . . . bn . (1.75)

an1 an2 ann

(1.74)

Notiuni de geometrie an a

25

Dac det(A) > 0, atunci aplicatia A conserv orientarea denit de a a a baza reperului R, sensul c transform aceast baz n a a a a ntr-o baz la fel a orientat. cele ce urmeaz considerm doar astfel de transformri. a In a a a O aplicatie an are general efect deformator asupra obiectului a n computational. Prezint interes pentru manipularea obiectelor compu a tationale, doar transformrile rigide i cele de scalare. a s Denitia 1.2.11 Transformarea an Sr : En En , r > 0, care relativ a la reperul R = (o; B) are proprietatea c Sr (o) = o i Sr p = q, unde a s = r se numete omotetie an de centru o i factor r, sau scalare oq op s a s de factor r. Partea liniar a unei aplicatii de scalare este T (v) = r v, v Rn . Dac a a 0 < r < 1, Sr se numete scalare contractiv, iar dac r > 1, scalare s a a expansiv. Scalrile se folosesc pentru reducerea/mrirea dimensiunilor a a a obiectului computational. Practic un obiect este transformat de Sr ntrunul asemenea cu el, factorul de asemnare ind r (vezi Fig. 1.6). a

Fig. 1.6: Efectul scalrii S0.5 asupra unui poligon. a

computer graphics se numete scalare i aplicatia an S : En En In s s a care relativ la sistemul de axe oxi , are expresia analitic S(x1 , . . . , xn ) = a (r1 x1 , . . . , rn xn ), ri > 0, i = 1, n. Transformrile rigide (nedeformatoare) sunt cele ce conserv lungia a mile i unghiurile. Ele se numesc transformri izometrice. s a

26 E. Petrior s

Bazele matematicii ale gracii pe calculator

O transformare an este izometric dac i numai dac matricea a a a s a prtii liniare asociate, A, este ortogonal. a a continuare dm expresia analitic a principalelor transformri izoIn a a a metrice: 1. Translatia pe directia i sensul vectorului v Rn , (n = 2, 3) este s n n aplicatia tv : E E , denit prin tv (p) = p + v, p En . a 2. Rotatia jurul unei axe a sistemului ortogonal ox1 x2 x3 . Rotatia de n centru o jurul axei oxi sens pozitiv (de la oxi spre oxi+1 , i, i + 1 n n i calculate modulo 3), cu unghiul de msur , R : E3 E3 , are relativ la a a i sistemul ox1 x2 x3 expresia analitic: R (x1 , x2 , x3 ) = (X1 , X2 , X3 ), unde a X1 1 0 0 x1 1 X2 = 0 cos sin x2 , pentru rotatia R (1.76) X3 x3 0 sin cos X1 cos 0 sin X2 = 0 1 0 X3 sin 0 cos X1 cos sin 0 X2 = sin cos 0 X3 0 0 1 x1 2 x2 , pentru rotatia R x3 x1 3 x2 , pentru rotatia R x3 (1.77)

(1.78)

Functia genereaza_matrice_rot genereaz una din matricile de ro a tatie, functie de optiunea utilizatorului exprimat prin codul axei de n a rotatie: x, y sau z. O dat generat matricea de rotatie rmne a a a a s se efectueze a nmultirea matricii respective cu matricea coloan a co a ordonatelor punctului cruia i se aplic rotatia. a a void genereaza_matrice_rot(char axa, double teta, Matrice R) { // teta este unghiul de rotatie in RADIANI! double s, c; s = sin(teta); c = cos(teta); switch(axa){ case x: R[0][0] = 1; R[0][1] = 0; R[0][2] = 0; R[1][0] = 0; R[1][1] = c; R[1][2] = -s; R[2][0] = 0; R[2][1] = s; R[2][2] = c; break; case y: R[0][0] = c; R[0][1] = 0; R[0][2] = s;

Notiuni de geometrie an a

27

R[1][0] = 0; R[1][1] = 1; R[1][2] = 0; R[2][0] = -s; R[2][1] = 0; R[2][2] = c; break; case z: R[0][0] = c; R[0][1] = -s; R[0][2] = 0; R[1][0] = s; R[1][1] = c; R[1][2] = 0; R[2][0] = 0; R[2][1] = 0; R[2][2] = 1; break; default: fprintf(stderr,"\n cod axa incorect"); exit(1); } } Fig. 1.7: Constructia reperului intermediar pentru generarea rotatiei arbi trare.

Pentru vizualizarea complet a unui obiect computational se rea curge la animatie, rotind obiectul jurul unei axe arbitrare (nu neaprat n a o ax a sistemului relativ la care este raportat obiectul). a Pentru a deni sistemul de axe ox1 x2 x3 o rotatie ce conserv orin a entarea ( sens pozitiv), de unghi , centru o i ax de directie i sens n s a s v(a1 , a2 , a3 ) = 0 se procedeaz astfel (Fig.1.7): a a a a se testeaz dac vectorul v este nenul. Dac v = 0 rotatia nu se poate deni; caz contrar: n s se construiete un reper ortonormat drept R de origine o, cu baza ortonormat B = (u1 , u2 , u3 ), astfel at u3 s e versorul lui v a nc a 0 a n (notnd v3 = v, rezult c u3 = v3 , adic axa de rotatie va a a a noul sistem de axe ox1 x2 x3 asociat lui R axa a treia, ox3 ).

28 E. Petrior s

Bazele matematicii ale gracii pe calculator

Dac a1 = 0 i/sau a2 = 0 se alege v1 (a2 , a1 , 0) ca directie a s pentru ox1 (evident v1 v3 ). Se trece la calculul lui v2 . Dac a1 = a2 = 0, dar a3 = 0 se ia v1 (1, 0, 0). a se calculeaz v2 : Pentru ca baza ortogonal (v1 , v2 , v3 ) s e a a a dreapt se ia v2 = v3 v1 . a0 se calculeaz versorii: ui = vi , ui = (ai1 , ai2 , ai3 ), i = 0, 1, 2, 3. a

se constituie matricea de trecere TBB de la baza baza canonic B a la baza B : a11 a21 a31 (1.79) TBB = a12 a22 a32 a13 a23 a33 se determin expresia analitic a rotatiei jurul axei de directie v a a n relativ la sistemul initial de axe. Si anume, relativ la sistemul aso ciat reperului R rotatia are expresia: R(x1 , x2 , x3 ) = (X1 , X2 , X3 ), unde: X1 cos sin 0 x1 X2 = sin cos 0 x2 (1.80) X3 0 0 1 x3 Cum a relatia dintre coordonatele (x1 , x2 , x3 ), (x1 , x2 , x3 ) ale ns unui punct (adic coordonatele vectorului su de pozitie) rapora a tat la reperul initial, respectiv, reperul nou construit, este: x1 x1 x1 x1 x2 = TBB x2 x2 = TBB x2 (1.81) x3 x3 x3 x3 a rezult c rotatia raportat la sistemul ox1 x2 x3 asociaz punctului a a a (x1 , x2 , x3 ), punctul (X1 , X2 , X3 ), unde cos sin 0 x1 X1 X1 X2 = TBB X2 = TBB sin cos 0 x2 = x3 X3 0 0 1 X3 (1.82) cos sin 0 x1 cos 0 TBB x2 = TBB sin (1.83) x3 0 0 1

Notiuni de geometrie an a

29

Functia matrice_rotatie_arbitrara implementeaz calculele de mai a sus: void matrice_rotatie_arbitrara(double teta, Vector v, Matrice R) { double norm; Vector v1,v2,u1,u2,u3; Matrice T, Tt, R3,H; // Tt = transpusa matricii T // de trecere de la //noua baza la baza canonica aloca_vector(v1,3); aloca_vector(v2,3); aloca_vector(u1,3); aloca_vector(u2,3); aloca_vector(u3,3); T=creeaza_matrice(3); Tt=creeaza_matrice(3); H=creeaza_matrice(3); norm=norma_vector(Vector v, int n); if(norm < epsilon) { fprintf(stderr,"\n vector nul"); exit(1); } if(fabs(v[0])> epsilon || fabs(v[1])> epsilon) { v1[0]=-v[1]; v1[1]=v[0]; v1[2]=0.; } else { v1[0]=1; v1[1]=0.; v1[2]=0.; } produs_vectorial(v,v1,v2); versor(v1,u1,3); versor(v2,u2,3); versor(v,u3,3); vector_copiaza(u1,Tt[0],3); vector_copiaza(u2,Tt[1],3);

30 E. Petrior s

Bazele matematicii ale gracii pe calculator

vector_copiaza(u3,Tt[2],3); genereaza_matrice_rot(z, teta, R); transpusa_matrice(Tt,T,3); produs_matrici(T,R,H,3); produs_matrici(H,Tt,R,3); free_matrice(T,3); free_matrice(Tt,3); free_matrice(H,3); } Uneori suntem interesati s generm E3 , relativ la reperul ortonor a a n mat R = (o; B), o rotatie de centru c = o, ax v = 0 i unghi . a s In acest caz se consider un nou reper R = (c; B), se determin coordoa a natele punctelor p ale obiectului computational relativ la acest reper apelnd functia vector_scade(p,c,pp,3); i apoi se aplic punctelor a s a pp rotatia arbitrar calculnd pr = R(pp), unde matricea de rotatie se a a determin apelnd functia: matrice_rotatie_arbitrara(teta,v,R). a a Punctelor pr obtinute dup rotatie, li se calculeaz coordonatele repe a a n rul initial: vector_aduna(rp,c,q,3);

1.2.4

Proiectii graca 3D n

Vizualizarea unui corp 3D se realizeaz prin proiectarea acestuia pe un a continuare vom simula matematic mecanismul vederii. Din plan. In punct de vedere zic, vederea cu un singur ochi nseamn proiectarea a obiectelor 3D pe un plan cu ajutorul unei lentile. Creierul este apoi, mai mult sau mai putin, capabil s reconstruiasc obiectele spatiu, adic s a a n a a estimeze distanta dintre obiecte prin comparatii de mrimi sau umbre. a In graca pe calculator se folosesc dou tipuri de proiectii: proiectii paralele a i proiectia perspectiv. Ambele tipuri de proiectii se denesc matematic s a ca aplicatii P : E3 E2 . E2 se identic cu un plan din E3 , numit a plan de proiectie. Proiectia paralel presupune o directie de proiectie denit de vectorul a a v R3 , v = 0. Fiecrui punct a E3 i se asociaz planul punctul a a n a = P(a), determinat astfel at vectorul aa s e coliniar i de acelai nc a s s sens cu v, adic aa = v, > 0. a functie de unghiul pe care-l face directia de proiectie cu planul de In proiectie avem dou tipuri de proiectii a 1. proiectie ortograc cnd v ; a a

Notiuni de geometrie an a

31

2. proiectie oblic caz contrar. a n Dac v este unul din vectorii bazei canonice din R3 sau opusul unui a astfel de vector, atunci proiectia ortograc de vector v realizeaz re a a spectiv vederi sus/jos, fata/spate, lateral dreapta/stnga a obiectului a 3D. Aceste proiectii conserv paralelismul i distantele. a s Proiectia central de centru E i plan E3 este o aplicatie P : a s 3 2 3 E E , care asociaz oricrui punct a E punctul de intersectie a a a al dreptei (Ea) cu planul . Centrul de proiectie este interpretat ca ochiul observatorului, fotografului, sau locatia camerei de luat vede ri. Proiectia central sau a proiectia perspectiv este cel mai mult a nc a folosit graca pe calculator, deoarece creeaz imagini mai realiste a n a (mai aproape de realitate) dect proiectia paralel. a a continuare prezentm modul de realizare a proiectiei perspective a In a unui obiect computational 3D. Ideea de baz este urmtoarea: obiectul a a ce urmeaz s e supus proiectiei este raportat la un sistem ortogonal de a a axe, numit sistemul lumii reale. Relativ la acest sistem se pozitioneaz a centrul de proiectie (observatorul). Observatorului i se asociaz un reper a ortonormat propriu i se raporteaz apoi obiectul relativ la acest reper. s a Perpendicular pe axa de observare se plaseaz la o anumit distanta, a a planul de proiectie. Proiectia perspectiv avnd ca centru observatorul, a a asociaz ecrui punct al obiectului, punctul de intersectie cu planul de a a proiectie al razei de observare ce pornete de la observator spre punctul s vizat al obiectului. Prezentm continuare, etapele realizrii proiectiei perspective. Fie a n a O = {Mi (xi1 , xi2 , xi3 ), i = 1, . . . , N } un obiect computational raportat la reperul ortonormat drept R = (o; B = (e1 , e2 , e3 )), avnd sistemul de a axe ox1 x2 x3 . Presupunem c paralelipipedul minim ce include obiectul a caz contrar determinm centrul geometric c al contine originea o. In a obiectului ca ind punctul de coordonate (xc , xc , xc ), unde 1 2 3 xc = j xmin + xmax j j , j = 1, 2, 3, 2 (1.84)

unde xmin = min(xij ), iar xmax = max(xij ), i = 1, . . . , N , j = 1, 2, 3. j j Apoi raportm obiectul la reperul R = (c; B), sensul c determinm a n a a coordonatele ecrui punct al obiectului computational relativ la acest a reper. Printr-o eventual renumire a punctului c, considerm obiectul raa a portat la reperul R = (o; B).

32 E. Petrior s

Bazele matematicii ale gracii pe calculator

etapa urmtoare dm pozitia observatorului E coordonate sferice In a a n (, , ), unde: reprezint distanta de la observator la originea o a reperului obieca tului; s a este latitudinea observatorului pe sfera de centru o i raz , adic msura radiani a unghiului dintre oE i planul x1 ox2 . a a n s (/2, /2); este longitudinea punctului E, adic dac E este proiectia punca a tului E pe planul x1 ox2 , = ms(ox1 , oE ). [0, 2). a Coordonatele carteziene ale observatorului se determin din relatiile dina tre coordonatele sferice i carteziene ale unui punct: s x1 = cos cos x2 = sin cos x3 = sin (1.85)

Functia sferic_cartezian calculeaz coordonatele carteziene ale unui a punct, functie de cele sferice: n void sferic_cartezian(Vector sferic, Vector x) { x[0]=sferic[0]*cos(sferic[2])*cos(sferic[1]); x[1]=sferic[0]*sin(sferic[2])*cos(sferic[1]); x[2]=sferic[0]*sin(sferic[1]); } Observatorului E i se asociaz un reper ortonormat strmb, R = a a (E; B ), B = (u1 , u2 , u3 ), numit reper de observare. Si anume, u3 este versorul directiei i sensului vectorului Eo (adic versorul directiei de ob s a servare), iar u1 , respectiv u2 , sunt versorii tangenti E la cercul paralel, n respectiv la meridianul prin E, de pe sfera de raz a observatorului a (Fig.1.8). Notnd cu r vectorul de pozitie al observatorului, a r(, , ) = ( cos cos , sin cos , sin ), u1 , u2 , u3 sunt versorii asociati vectorilor r , r , rrho . Dar, r = ( sin cos , cos cos , 0) r = ( cos sin , sin sin , cos ) r = ( cos sin , sin cos , sin ) (1.87) (1.86)

Notiuni de geometrie an a

33

Astfel u1 = ( sin , cos , 0) u2 = ( cos sin , sin sin , cos ) (1.88)

Versorul u3 calculm mai rapid coordonate carteziene ca ind u3 = l a n Eo . Eo Fie Ex1 x2 x3 sistemul de axe asociat reperului observatorului. Directia i sensul de observare este cel al axei Ex3 . s Fig. 1.8: Meridianul i cercul paralel pe sfera observatorului. Sistemul de s axe asociate observatorului E.

Pentru a calcula coordonatele sistemul observator ale unui punct n a, ce are relativ la reperul R coordonatele (x1 , x2 , x3 ), se parcurg dou a etape: a 1. se calculeaz coordonatele (X1 , X2 , X3 ) ale lui a relativ la reperul R1 = (E; (e1 , e2 , e3 )): Xi = xi xE , i (1.89)

unde xE , i = 1, 3, sunt coordonatele carteziene ale observatorului i E relativ la reperul initial R, al obiectului computational;

34 E. Petrior s

Bazele matematicii ale gracii pe calculator

2. se calculeaz coordonatele observator ( sistemul observatorului) a n (x1 , x2 , x3 ), ale punctului a, ce are reperul R1 coordonatele (X1 , n X2 , X3 ): X1 x1 x2 = TBB X2 . (1.90) X3 x3 Matricea TBB este calculat de functia matrice_observator: a

void matrice_observator(Vector sferic,Matrice Tt) { Vector u1,u2,u3,E; double fi,teta; fi=sferic[1]; teta=sferic[2]; aloca_vector(u1,3); aloca_vector(u2,3); aloca_vector(u3,3); aloca_vector(E,3); u1[0]=-sin(teta); u1[1]=cos(teta); u1[2]=0.; u2[0]=-cos(teta)*sin(fi); u2[1]=sin(teta)*sin(fi); u2[2]=cos(fi); sferic_cartezian(sferic,E); scalar_vector(E,-1,E,3); versor(E,u3,3); vector_copiaza(u1,Tt[0],3); vector_copiaza(u2,Tt[1],3); vector_copiaza(u3,Tt[2],3); } Cunoscnd coordonatele obiectului computational reperul obsera n vatorului se realizeaz mai rapid proiectia perspectiv. Si anume, la a a distanta d > 0 de observator, perpendicular pe directia de observare

Notiuni de geometrie an a

35

Ex3 se consider planul imagine , care se raporteaz la sistemul de a a axe E X1 X2 , ce se obtine proiectnd ortogonal pe acest plan axele a Ex1 , Ex2 , ale sistemului observatorului. Aplicatia P : E3 , unde E3 este raportat la sistemul observatoru lui, iar la sistemul precizat mai sus, asociaz punctului p intersectia a 0 0 0 0 0 dreptei (Ep) cu planul . P(x1 , x2 , x3 ) = (X1 , X2 ). Ecuatiile dreptei (Ep) sunt: x1 x10 x x0 x x0 = 2 0 2 = 3 0 3 (1.91) x10 x2 x3 Intersectnd aceast dreapt cu planul de ecuatie x3 = d, obtinem X1 = a a a x10 x20 d i X2 = 0 d. Functia urmtoare realizeaz proiectia perspectiv: s a a a x30 x3 Fig. 1.9: Proiectia perspectiv a unui punct p, raportat la sistemul de axe al a observatorului, Ex1 x2 x3 ; ox1 x2 x3 este sistemul de coordonate relativ la care se raporteaz initial punctul p. a

void pr_perspectiva(Vector M, Vector PM, double d) { // M[3], iar PM[2] int c;

36 E. Petrior s

Bazele matematicii ale gracii pe calculator

if(fabs(M[2])>epsilon) { for(c=0;c