Divizarea curbelor de forma libera

Divizarea curbelor de forma libera

Divizarea recursiva a curbelor este o metoda de a obtine punctele prin care poate fi aproximata o curba parametrica si se poate aplica si pentru determinare intersectiei unei curbe parametrice cu un alt obiect (dreapta, curba, suprafata etc.). Se foloseste metoda injumatatiriilor succesive pana cand segmentele de curba ajung sa satisfaca un anumit criteriu dependent de aplicatie (segmentele de curba pot fi aproximate prin segmente de dreapta sau printr-un singur pixel).

Fie o curba parametrica cubica:

C(u) = U*M*G , unde

U = [u³ u² u 1] cu 0 <= u <= 1;

M specifica curba

G este vectorul transpus al punctelor de control.

Curba este divizata recursiv in punctul de mijloc, u=0.5

Fie C₁ si C₂ cele 2 jumatati de curba rezultate din divizarea curbei C :

C₁(u₁) = C(u₁/2) si C₂(u₂)= C(0.5 + u₂/2)

Atunci avem:

C₁(u₁) = U * S₁ * M * G

Dorim ca C₁ sa aiba o forma similara cu C deci :

C₁(u₁) = U * M * G₁

Obtinem :

U * S₁ * M * G = U * M * G₁ => G₁ = M^-1 * S₁ * M * G

Notam H₁ = M^-1 * S₁ * M  si deci, G₁ = H₁ * G

H₁ este matricea de decupare pentru prima jumatate a curbei. Ea permite calcularea coeficientilor geometrici ai primei jumatati de curba plecand de la coeficientii curbei originale.

Matricea H_2, pentru a doua jumatate de curba, se obtine inlocund in ecuatia curbei originale pe u cu (1 + u₂)/2.

C₂(u₂) = C((1 + u₂)/2) = [u₂³ u₂² u₂ 1] * S₂ * M * G

=U * M * G_2,

H₂ = M^-1 * S₂ * M , G₂ = H₂ * G

Divizarea cubicelor Bezier (particularizare)

Calculam H₁, H₂ particularizand matricea M la matricea Bezier:

Stiind ca  H₁ = M_B^-1 * S₁ * M_B =>

H₂ = M_B^-1 * S₂ * M_B    =>

Fie P₀, P₁, P₂, P₃ punctele de control ale curbei originale si

G = [P₀ P₁ P₂ P₃] rezulta:

G1 = H1*G  si G2 = H2*G, unde G1 si G2 sunt vectorii punctelor de control pentru prima jumatate si a 2-a jumatate a curbei :

G₁ = [R₀ R₁ R₂ R₃] ;

Calculul punctelor de control pentru jumatatile curbei este alcatuit doar din adunari si impartiri la puteri ale lui doi.

Acelasi rezultat se obtine astfel:

Atunci :

pentru C₁ : G₁ = [P₀ A D F]

pentru C₂ : G₂ = [F E C P₃]

unde A este mijlocul segmentului P0-P1, B este mijlocul segmentului P1-P2, etc.

Divizarea cubicelor BSpline(particularizare)

Fie P₀, P₁, P₂, . P_n punctele de control care determina curba si C_i (u) segmentul de curba definit de intervalul P_i-1, P_i, P_i+1, P_i+2. Se efectuaza divizarea fiecarui segment de curba C_i (u). Pentru acesta se inlocuieste M cu matricea de baza BSpline.

Un segment de curba Bspline cubica poate fi convertit intr-o curba Bezier cubica si apoi divizata curba Bezier (calculele sunt mai simple!)

Conversie BSpline - Bezier

Fie curba BSpline C_S = U * M_S * G_S.

Vrem sa obtinem curba C_B = U * M_B * G_B corespondenta.

Rezulta M_S * G_S = M_B * G_B => punctele de control pentru curba echivalenta Bezier

G_B = M_B^-1 * M_S * G_S

Procedura de conversie poate fi aplicata oricarui alt tip de curba cubica.

Divizarea suprafetelor Bezier

Pentru a diviza o suprafata Bezier folosim rezultatele obtinute la divizarea curbelor. Divizarea se face recursiv, de fiecare data in punctul u=0.5, w=0.5.

Suprafata initiala, S, se divide in S₁, S₂, S₃, S₄ astfel:

Daca P este matricea punctelor de control pentru suprafata S, atunci, P_1, P_2, P_3, P₄, matricile punctelor de control pentru S_{1 ,} S_{2 ,} S_{3 ,} S₄ se calculeaza astfel:

Pentru divizarea unui segment de suprafata B-spline bicubica se poate recurge la conversia sa intr-o suprafata Bezier bicubica. 

Conversia de la bicubica BSpline la bicubica Bezier

Forma generala a unui petic bicubic (nu neaparat BSpline) este :

p(u,w) = U * M * S * M^T * W

unde S este matricea punctelor de control care definesc peticul de suprafata.

Pentru bicubica Bezier:

p(u,w) = U * M_B * S_B * M_B^T * W

Impunand conditia:

M * S * M^T = M_B * S_B * M_B^T   rezulta

S_B = M_B^-1 * M * G* [M_B^-1 * M]^T , punctele de control care definesc aceeasi suprafata, dar ca suprafata Bezier

Notam A= M_B^-1 * M , deci  

S_B = A * G* A^T;

Pentru bicubica Bspline, M este :

iar A rezulta: