REPREZENTAREA CURBELOR  SI A SUPRAFETELOR

1 . Introducere

In grafica de calculator sunt necesare tehnici prin care utilizatorul poate genera curbe cu aspectul dorit .

Exemple: aplicatii AUTOCAD pentru proiectarea caroseriilor automobilelor, fuselaje de avion etc .

Suntem in cautarea unor tehnici care:

pot genera curbe de o varietate cat mai mare

utilizatorul poate transmite usor calculatorului intentiile sale

sa permita verificarea rapida a apartenentei unui punct la curba

sa faciliteze gasirea intersectiei cu alta curba

Ecuatii implicite

ex

f(x,y)=x²+ y²- r²=0 . (1)

nu sunt convenabile in forma respectiva pentru trasare . De exemplu, avand coordonata curenta, x₀, obtinem

(2)

In plus, pentru ca exista o foarte mare varietate de curbe posibile, vom avea nevoie de un numar imans de reprezentari (ecuatii) diferite .

Reprezentari parametrice

ex .

x=rcos(u), (3)

y=rsin(u),

sunt mai convenabile pentru trasare . Mai mult, permit calculul derivatelor locale de o maniera mai directa si mai intuitiva . Derivata intai exprima viteza de variatie pe directia de crestere a parametrului, adica de-a lungul curbei:

(4)

De exemplu, pentru u=0 avem valorile (0, r), ceea ce indica faptul ca pentru moment x este constant si y se schimba, deci curba merge intr-o directie verticala . Prin comparatie, pentru forma implicita, avem

(5)

In punctul (r,0), corespunzator lui u=0, avem derivata , o valoare cu tratarea careia calculatoarele au unele dificultati .

Forma de reprezentare implicita, desi neadecvata pentru trasare, are proprietatea dezirabila de a permite verificarea facila a apartenetei unui punct oarecare la curba sau calculul intersectiei curbelor . Reprezentarea parametrica are insa o serie de avantaje ce precumpanesc . Curbele de forme complexe sunt reprezentate in grafica de calculator ca o colectie de segmente de curba de complexitate moderata . Fiecare segment este reprezentat cu ajutorul unui polinom . Ansamblul este o curba polinomiala pe portiuni . Uzual gradul polinomului de aproximare nu depaseste valoarea 3 . Un polinom de gradul trei este o forma suficient de generala pentru putea asigura cu usurinta doua cerinte fundamentale: continuitatea de ordinul zero (punctele de capat, in care se imbina segmentele coincid) si continuitatea de ordinul intai (tangentele in punctele de imbinare coincid) . Conditia a doua nu este intotdeauna necesara, dar este dorita de cele mai multe ori, astfel incat utilizatorul sa nu perceapa imbinarile dintre segmente . De exemplu, poligonul permite o reprezentare a curbei liniara pe portiuni, corespunzatoare unui poligon de ordinul intai si nu asigura continuitatea de ordinul doi .

Ecuatiile parametrice ale unei curbe sunt de forma:

                                     (6)

In cazul particular al reprezentarii prin polinoame de ordinul trei, ecuatiile iau forma:

                      (7)

Mai concis, folosind notatiile vectoriale:

                             (8)

si

                                  (9)

putem rescrie ecuatiile (7) in forma concisa

.                            (10)

Orice polinom de grad n poate fi scris in forma din ecuatiile (7) . Polinomul este definit unic de coeficientii sai, p_i . Polinoamele de gradul n (ordinul n+1) formeaza un spatiu vectorial, de dimensiunea n+1, in care

u , u¹, u², . , uⁿ

reprezinta o baza (baza de putere) . Functiile b_i(u)=uⁱ reprezinta functiile de baza, ce pot fi definite cu ajutorul veectorilor de baza . Pentru cazul particular de interes n=3, acestia sunt:

Se poate vedea usor ca sunt liniar independenti .

Cu toate ca baza de putere ofera cea mai simpla, directa si intuitiva modalitate de reprezentare a unui polinom, ea nu este unica baza pe care o putem folosi si nici macar cea mai convenabila pentru grafica de calculator . Impedimentul principal consta in faptul ca, pentru a se genera o curba de forma dorita, este relativ dificil de anticipat valorile necesare ale coeficientilor p_i . Pentru o baza oarecare, ecuatia (10) se poate rescrie in forma:

.

2 . Proprietati utile ale bazelor

Majoritatea bazelor utilizate curent in grafica de calculator poseda doua proprietati importante:

• proprietatea invelisului convex
• proprietatea invariantei la transformarile afine

Proprietatea invelisului convex

Ecuatia (11) poate fi interpretata in felul urmator: fiecare punct de pe curba reprezinta o medie ponderata a punctelor p_i, pe care le vom denumi puncte de control . Invelisul convex al punctelor de control este poligonul convex de arie minima ce cuprinde toate punctele de control in interiorul sau pe conturul sau . Este poligonul care s-ar obtine plasind o bada elastica in jurul punctelor de control . Acesta include poligonul de control, al carui interior este redat umbrit in (fig . 1) .

fig . 1

Proprietatea invelisului convex consa in faptul ca forma generata se afla in interiorul invelisului convex daca:

                                (12)

adica, functiile de baza au suma identic egala cu 1 si sunt nenegative pe intervalul de definitie (uzual u apartine intervalului [0,1]) .

Invarianta le transformari afine

Transformarile afine includ translatia, rotatia si scalarea .

Prprietatea invariantei la transformarile afine consta in faptul ca figura generata de punctele de control care au suferit o transformare afina corespunde transformarii afine a figurii corespunzatoare punctelor initiale . Notand transformarea afina cu Φ(), proprietatea enuntata presupune ca

.           (13)

Proprietatea este deoasebit de utila in manipularea curbelor (de exemplu in animatie), deoarece nu este necesar sa efectuam transformarea pentru fiecare punct al curbei ci numai pentru punctele de control, utilizand apoi rutinele obisnuite de trasare a curbei .

Observatie

O curba reprezentata parametric prin punctele ei de control poate fi redata cu o rezolutie oricat de mare este necesara . Daca aceeasi curba ar fi reprezentata ca o mini-imagine, rezolutia ar fi limitata de formatul imaginii . Desigur exista si pentru imagini posibilitatea de crestere a rezolutiei prin tehnici ce folosesc interpolarea, dar rezultatele pentru curbe nu sunt totdeauna cele asteptate . Astfel, prin cresterea rezolutiei, o linie cu grosime de un pixel poate deveni o linie cu grosime mai mare de un pixel .

3 . Curbe Bézier

Functiile de baza ale unei curbe Bézier de gradul n sunt:

              (14)

Pentru gradul 3, utilizat cel mai frecvent in grafica de calculator, functiile de baza Bézier (fig . 2) sunt:

.                    (15)

O curba Bézier de gradul trei se scrie:

           (16)

(0<u<1) .

Care este avantajul fata de formularea din ecuatia (10)?

Fig . 2

In primul rand, observam ca

r(0)=p_0,    (17)

r(1)=p_3,  (18)

deci curba Bézier trece prin primul si prin ultimul punct de control .

Pentru a vedea semnificatiile celorlalte doua puncte de control, derivam curba in raport cu u:

.(19)

Rezulta ca:

r'(0)=3(p_1─ p₀)_,    (20)

r'(1)=3(p_3─ p₂) _.    (21)

Dezvoltarea functiei in serie Taylor in jurul punctului u=t se scrie:

r (t+h)= r(t)+hr'(t),   (22)

ceea ce arata ca r'(t) este directia tangentei in punctul u=t . Prin urmare, directia tangentei in punctul initial este 3(p_1─ p₀), adica directia dreptei ce uneste primele doua puncte de control (multiplicarea vectorului cu factorul 3 nu schimba directia) . Ecuatia (22) mai sugereaza faptul ca, pe masura ce punctul de control p₁ este mai indepartat de p₀, curba inainteaza mai mult pe directia tangentei in origine . O interpretare similara exista si pentru tangenta in punctul final .

Functiile Bézier respecta conditiile (12), pentru ca functiile de baza sunt de fapt termenii dezvoltarii binomului ((1-u)+u)ⁿ . Prin urmare, ele poseda si proprietatea invelisului convex .

In concluzie, punctele de control pot fi utilizate de o maniera simpla pentru asigurarea continuitatii de ordinul zero si unu ale unei curbe compuse din segmente Bézier de ordinul trei . Ordinul trei este suficient de ridicat pentru a permite o mare varietate de curbe, in general nesimetrice . Totodata, curbele generate sunt netede, o proprietate dorita de cele mai multe ori .

4 . Algoritmul Casteljau

Functiile de baza Bézier de un anumit ordin se pot obtine prin interpolarea liniara a functiilor de rang inferior, conform ecuatiei:

,                           (23)

ceea ce se poate verifica usor, folosind ecuatia (14) .

In consecinta, un punct de pe curba, situat la coordonata u, poate fi generat recursiv, folosind urmatorul algoritm:

1. Punctele initiale sunt chiar punctele de control:

,

i=0,1,,n - r,

r=0 . // semnifica iteratia

u se initializeaza cu valoarea dorita, in intervalul 0-1 .

2. Pentru r=1,2,,n, se determina succesiv punctele:

.                     (24)

Se observa ca:

fiecare punct nou se obtine prin interpolarea liniara a doua puncte consecutive din iteratia precedenta

le fiecare iteratie, numarul punctelor calculate se reduce cu unul

Interesant este faptul ca ultimul punct care se obtine, este =r(u) si este pe curba!

Cititorul este invitat sa verifice afirmatia pentru n=3, folosind calculul recursiv indicat de algoritm . O ilustrare grafica a algoritmului Casteljau pentru u=1/2 se da in figura 3 .

Fig . 3

Se poate demonstra ca punctul final obtinut divide curba Bézier in doua curbe Bézier (subdiviziune) ale caror puncte de control sunt chiar , respectiv , ce au fost deja calculate . In consecinta, este posibila trasarea curbei folosind subdiviziunea recursiva . Costul de calcul pentru fiecare punct nou este de numai patru medii ponderate . Daca se alege u=1/2, multiplicarile pot fi evitate: impartirea cu doi se poate implementa ca o operatie de deplasare la dreapta cu o unitate( operatorul >>1 in limbajul C) . Noile puncte de control ale celor doua segmente se reduc la:

Solutia este extrem de convenabila si pentru o eventuala implementare hardware . Algoritmul se termina cand invelisul convex al poligonului de control Bézier este suficient de plat pentru a se putea aproxima segmentul curent de curba cu o dreapta, care se traseaza .

Algoritmul Casteljau este un punct forte major al reprezentarii Bézier a curbelor . El are insa si o importanta teoretica . Pentru ca interpolarea liniara este invarianta la transfomrarea afina, algoritmul demonstreaza faptul ca reprezentarea Bézier are proprietatea invariantei la transformari afine .

5 . Formularea matriciala a curbelor Bézier

O conventie alternativa pentru a specifica o curba Bézier este cu ajutorul matricii Bézier si a vectorilor bazei de putere:

.     (25)

De precizatat, ca vectorii r si p sunt vectori-linie in formularea de mai sus . Functiile de baza Bézier cubice se obtin din produsul primelor doua matrici in ecuatia (25) .

Formularea matriciala a curbelor Bézier este utila in urmatoarele doua situatii:

implementarea hardware la reprezentarea in alta baza

conversia intre baze

De ce sa folosim si alte baze?

la reprezentarea Bézier modificarea unui singur punct de control afecteaza alura intregii curbe

reprezentarea Bézier nu are flexibilitatea necesara in unele aplicatii, de exemplu nu permite sinteza operativa a unor curbe cu colturi (ca in figura 4)

Fig . 4

Tema

P1 .

Triunghiul cu varfurile V_i(x,y)=

Se roteste cu 30^o in jurul lui V₁ . Calculati centroidul triunghiului rezultant .

P2 .

Gasiti directia tangentei in punctul (4,1) la curba Bézier definita de punctele de control .

P3 . Folosind algoritmul Casteliau, aflati coordonatele punctului corespunzator parametrului u = 0,4 .

P4 . Gasiti rezultatul filtrului median 3x3 in centrul imaginii I .

P5 . Gasiti rezultatul filtrului binomial 3x3 in centrul imaginii I .

P6 . Gasiti histograma nivelurilor de gri pentru imaginea I . Pe baza histogramei, calculati nivelul mediu de gri .