Elemente de grafica de calculator - Cercuri

Elemente de grafica de calculator  - Cercuri

Ecuatia unui cerc ce trece prin origine:

Daca centrul este in (x_c, y_c), se face o translatie, definita prin

Forma (1.4) nu este adecvata pentru trasare. De exemplu, dand valori lui x, pentru a gasi y trebuie rezolvata o ecuatie de gradul doi, trebuie verificat daca solutiile sunt reale etc.

Forma diferentiala a ecuatiei cercului:

2xdx+2ydy=0, sau

Incrementul ε se alege invers proportional cu raza r.

Forma discreta a ecuatiei:

Problema: traseaza o spirala, pentru ca

Solutie: Se modifica ecuatiile (1.7), in forma

Se poate arata (ca exercitiu) ca raza ramane constanta in acest caz.

.1. Algoritmul DDA pentru cerc

Se obtine urmatorul algoritm DDA pentru cerc. Algoritmul exploateaza simetria cercului si traseaza simultan cate 8 puncte. De fapt se genereaza doar un octant (intre 45⁰ si 90⁰).

cercDDA int x_c, int y_c, int r)

} // end cercDDA()

put8pix int x, int y, int x_c, int y_c )

2. Metoda rotatiei

Se porneste de la ecuatiile parametrice ale cercului:

Un punct rotit in sens trigonometric cu unghiul θ are coordonatele:

Pentru trasarea cercului, se alege un unghi incremental θ foarte mic.

Observatie privind implementarea

Apelul repetat al functiilor trigonometrice (lente) poate fi simplu evitat.

Se precalculeaza

a cos(θ), b=sin(θ), rezultand apoi algoritmul in forma:

Algoritmul ce rezulta este similar celui DDA.

Exercitiu: scrieti o functie pentru trasarea cercului prin metoda rotatiei.

3. Algoritmul Bresenham pentru cerc

Conduce la operatii exclusiv cu numere intregi.

Genereaza de fapt un octant, ca si DDA, restul rezulta prin simetrie.

Porneste tot de la punctul maxim superior, de coordonate x=0, y=r.

Coordonata x se incrementeaza la fiecare pas. Coordonata y se decrementeaza numai la unii pasi. Trebuie gasita conditia pentru decrementarea lui y. Apar situatiile posibile din figura 2:

P_n este punctul curent, A, B, puncte succesoare candidat. Pentru P(x,y) notam f(x,y)=f(P).

Observam ca f(P)<0 in interiorul cercului, f(P)=0 pe cerc si f(P)>0 in exteriorul cercului.

Pentru situatiile a) si b) succesorul punctului P_n trebuie sa fie punctul A, mai apropiat de cerc decat B (y nu se incrementeaza). Pentru situatiile d) si e), succesorul trebuie sa devina punctul B. Situatia din c) este cea mai complicata, succesori putind fi atat A, cat si B. Trebuie ales punctul cel mai apropiat de cerc. Acesta este A daca f(A) < -f(B), respectiv daca f(A)+f(B) <0. Observam ca aceeasi inegalitate este valabila si pentru situatiile a) si b). Semnul inegalitatii se schimba pentru situatiile cand optiunea ideala este pentru punctul B. Rezulta urmatoarea regula simpla: y se decrementeaza (se alege B) daca

S= f(A)+f(B) <0.

Fig. 2

Interesant este faptul ca suma S poate fi evaluata recursiv, fara operatii de ridicare la putere, presupuse de ecuatia (1.4) a cercului. Formula de calcul este dependenta de directia de deplasare de la pasul precedent. Apar doua situatii (v. figura 3):

I)         S≥0, deplasare orizontala,

II)       S<0, deplasare oblica (orizontala si verticala)

Cazul I:

S_n  = (x_n+1)²+y_n²-r²+(x_n+1)²+(y_n-1)²-r²,

S_n+1  = (x_n+2)²+y_n²-r²+(x_n+2)²+(y_n-1)²-r² si rezulta

S_n+1=S_n+4x_n+6.

Cazul II:

S_n  = (x_n+1)²+y_n²-r²+(x_n+1)²+(y_n-1)²-r²,

S_n+1  = (x_n+2)²+(y_n-1)²-r²+(x_n+2)²+(y_n-2)²-r² si rezulta

S_n+1=S_n+4(x_n- y_n)+10.

La pornire, x_n=0, y_n=r si S_n=1+r²- r²+1+(r-1)²-r²= 3-2r.

Rezulta urmatorul algoritm (in cod C++)

// algoritmul Bresenham pentru cerc

cercBresenham( int x_c, int y_c, int r )

x++;

}

if x==y)

put8pix( x, y, x_c, y_c );

} // end cercBresenham()