Rozdział 2 – Wprowadzenie – 2/2 Trójkąty Beziera

Trójkąty Beziera

Współrzędne barycentryczne

Jako pierwszy współrzędne barycentryczne wprowadził Moebius w 1827 roku.
definicja:
Niech T będzie trójkątem z wierzchołkami A,B,C w płaszczyźnie uv. Dowolny punkt $P \in T$ można wyrazić jednoznacznie jako kombinację liniową wierzchołków tego trójkąta P=rA+sB+tC ; dodatkowo, aby była to kombinacja barycentryczna wymaga się aby r+s+t=1. Współczynniki r,s,t noszą nazwę współrzędnych barycentrycznych punktu P w zależności od A, B i C. Dla punktu należącego do trójkąta są spełnione własności :
$r \in [0,1], s \in [0,1], t \in [0,1]$
Uwaga:
Będę często przestawał rozróżniać między punktem a jego współrzędnymi barycentrycznymi – będę mówił po prostu o “punkcie (r,s,t)”

Jeśli tylko dane są dowolne cztery punkty A,B,C i P , zawsze można wyznaczyć współrzędne barycentryczne r,s,t dla P;
równości:
$\left\{\begin{matrix}[l]
P = r \cdot A+s \cdot B+t \cdot C\\
r+s+t=1
\end{matrix}\right . $
mogą być przedstawione jako układ trzech równań liniowych dla trzech niewiadomych r,s,t .
Rozwiązanie można uzyskać przez zastosowanie wzorów Cramera :
$r = \frac{pole(P,B,C)}{pole(A,B,C)}$
$s = \frac{pole(A,P,C)}{pole(A,B,C)}$
$t = \frac{pole(A,B,P)}{pole(A,B,C)}$
Wymagają one liczenia wyznaczników:
$
Pole(A,B,C) = \frac{1}{2} \cdot
\begin{vmatrix}
A_x & B_x &C_x \\
A_y & B_y &C_y \\
1 & 1 & 1
\end{vmatrix}
$
gdzie
$Det = A_x B_y + B_x C_y + C_x A_y – A_y B_x – B_y C_x – C_y A_x$
Zauważmy, że aby wzory były dobrze zdefiniowane – pole trójkąta (A,B,C) musi się różnić od 0, co oznacza, że A,B i C nie mogą leżeć na jednej linii.

Współrzędne barycentryczne są afinicznie niezmienne:
Niech P ma barycentryczne współrzędne r,s,t w zależności od punktów A,B,C. Odwzorowujemy wszystkie cztery punkty na inny zbiór przez odwzorowanie afiniczne. Wtedy P ma te same barycentryczne współrzędne r,s,t w zależności od A , B , C.

Dowolne trzy niewspółliniowe punkty A,B,C definiują układ współrzędnych barycentrycznych na płaszczyźnie. Punkty wewnątrz trójkąta mają nieujemne współrzędne barycentryczne, podczas gdy pozostałe mają niektóre współrzędne barycentryczne ujemne.
Możemy użyć współrzędnych barycentrycznych do definiowania liniowej interpolacji. Przyjmijmy, że mamy dane trzy punkty $P_1,P_2,P_3 \in R^3$. Wtedy punkt zadany wzorem:
$P = P(r,s,t) = r P_1+s P_2+t P_3$ (gdzie $r+s+t=1$)
leży w płaszczyźnie rozpiętej przez $P_1,P_2,P_3$
Odwzorowanie z $R^2$ do $R^3$ jest nazywane liniową interpolacją.
Ponieważ $r+s+t=1$, możemy interpretować r,s,t jako współrzędne barycentryczne P względem $P_1,P_2,P_3$ .
Możemy również interpretować r,s,t jako współrzędne barycentryczne punktu w $R^2$ względem pewnego trójkąta $A,B,C \in R^2$. Wtedy powyższy wzór może być interpretowany jako odwzorowanie trójkąta $A,B,C \in R^2$ na trójkąt $P_1,P_2,P_3 \in R^3$.
Trójkąt A,B,C nazwiemy trójkątem dziedziny.
Uwaga: aktualne położenie lub kształt trójkątnej dziedziny jest zupełnie nie związany z definicją liniowej interpolacji (oczywiście musimy wymagać, aby był niezdegenerowany).Ponieważ możemy interpretować r,s,t jako współrzędne barycentryczne zarówno dla 2 lub 3 wymiarów, to pociąga za sobą, że liniowa interpolacja jest odwzorowaniem afinicznym .

Wielomiany Bernsteina

W przypadku dwóch zmiennych wielomiany Bernsteina Bi,j,k są definiowane przez:
\scalebox{1.2}{$B^n_{i,j,k}(u) = \binom{n}{i,j,k}r^is^jt^k = \frac{n!}{i!j!k!}r^is^jt^k$} gdzie r+s+t=1
Definiujemy dodatkowo
$B^n_{i,j,k}(u) = 0$
jeśli pewne (i,j,k) są ujemne.
Wykresy niektórych funkcji Bernsteina:

Wielomiany te mają własności analogiczne do własności wielomianów jednej zmiennej. Dokładniej:
1)
$\sum_{\substack{i+j+k=n\\ i,j,k \geqslant 0}}B^n_{i,j,k}(r,s,t) = 1$

2)
$B^n_{r,s,t} \geqslant 0$ dla $r,s,t \in [0;1]$

3)
$B^n_{i,j,k}(u)= rB^{n-1}_{i-1,j,k} (u)+ sB^{n-1}_{i,j-1,k} (u) + tB^{n-1}_{i,j,k-1} (u); i+j+k = n$

Jest to wzór rekurencyjny, który wynika z definicji i z użycia równości:
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Jako przykład wielomian Bernsteina stopnia 4 pokazany jest na schemacie:
$
\begin{matrix}
&&&& s^4 &&&& \\
&&& 4s^3t && 4rs^3 &&& \\
&& 6s^2t^2 && 12rs^2t && 6r^2s^2 && \\
& 4st^3 && 12rst^2 && 12rst^2 && 4r^3s& \\
t^4 && 4rt^3 && 6r^2t^2 && 4r^3t && r^4
\end{matrix}
$

Trójkąty Beziera

De Casteljau wprowadził trójkąty Beziera w 1959 r. Zauważmy, że są one bardziej “naturalnym” uogólnieniem krzywych Beziera na powierzchnie niż płatki produktów tensorowych. [4]
Dla funkcji 2 stopnia 2 zmiennych jest 6 parametrów:
$x^2,x,1,y^2,y,xy$
dla 3 stopnia 10 parametrów:
$
\begin{matrix}
&&&1\\
&& x && y\\
& x^2 && xy && y^2 \\
x^3 && x^2y && xy^2 && y^3
\end{matrix}
$

czyli dla n suma stopni dla x i y nie może przekraczać n; oznacza to np. że jeżeli w pewnym równaniu zapisanym przy pomocy bazy wielomianowej występuje $x^2+y^2$ można je przekonwertować na bazę Bernsteina dla stopnia co najmniej 4.
Liczba parametrów=1/2(n+1)(n+2) i jest równa liczbie współczynników w trójkąta Beziera .
Trójkątny płat $(u,v) \in T$ powierzchni Beziera definiuje się następująco:
$S(u,v)=\sum_{\substack{i+j+k=n\\i,j,k\geqslant 0}}P_{i,j,k}B^n_{i,j,k}(r,s,t)$
gdzie $P_{i,j,k}$ są danymi punktami kontrolnymi, a $B_{i,j,k}$ wielomianami Bernsteina postaci:
$B^n_{r,s,t}=\frac{n!}{i!j!k!}r^is^jt^k$

Powierzchnia Beziera definiowana w obszarze trójkątnym jest określona 1/2(n+1)(n+2) punktami $P_{i,j,k}$ i odpowiadającymi im składnikami wielomianu.

Z dwóch pierwszych własności wielomianów Bernsteina wynika, że trójkątny płatek Beziera leży wewnątrz powłoki wypukłej swoich punktów kontrolnych, a trzecia własność jest podstawą algorytmu obliczania wartości S(u,v) – algorytmu de Casteljau dla trójkątów Beziera, za pomocą którego można dzielić trójkąt na części. (Zheng [17] i Zhou [18] omawiają warunki na wypukłość trójkątów Beziera )

Zmiana Baz

Dla wielomianu stopnia n mamy (n+1)(n+2)/2 współczynników i tyle samo punktów liczy siatka kontrolna na trójkącie.
Przykładowo, dla wielomianu stopnia n=2 mamy współczynniki:
$
\begin{matrix}
&& 1 && \\
& x && y & \\
x^2 && xy && y^2
\end{matrix}
$
natomiast siatka punktów kontrolnych ma postać:
$
\begin{matrix}
&& a_{00} && \\
& a_{01} && a_{10} & \\
a_{02} && a_{11} && a_{20}
\end{matrix}
$
Aby przetransformować współczynniki bazy wielomianowej na siatkę punktów kontrolnych czy odwrotnie, potrzebna jest znacznie większa macierz niż w przypadku krzywych – musi być to macierz N x N gdzie N=(n+1)(n+2)/2. Powstaje problem kolejności współczynników – dla jednego wymiaru macierz transformowała bazę typu $1,x,x^2,x^3,…$ na kolejne współczynniki bazy Bernsteina; \textit{tutaj należałoby dzielić na sekcje}: najpierw 1, potem x,y ; następnie $x^2,xy,y^2$ itd.. Powstaje baza składająca się z $(n+1)^2$ bloków. Spróbuję tu wyprowadzić macierz przekształcenia dla stopnia n = 2:
(dla trójkąta mającego wierzchołki : (0,0),(0,1),(1,0) )
f(x,y) = a00(1-x-y)2 + a012(1-x-y)x + a02x2 + a102(1-x-y)y + a112xy + a20y2 = x2(a00-2a01+a02) + 2xy(a00-a01-a10+a11) + 2x(a01-a00) + y2(a00-2a10+a20) + 2y(a10-a00) + a00
1: a00
x: 2(a01-a00)
y: 2(a10-a00)
x2: a00-2a01+a02
xy: 2(a00-a01-a10+a11)
y2: a00-2a10+a20
Jeżeli chodzi o kolejność współczynników aij, również dzielę je na sekcje: w pierwszej występuje tylko a00, w drugiej a01 i a10, w trzeciej a02, a11 i a20 itd. Ogólnie w sekcji numer n+1 będą współczynniki aij, dla których i+j = n.
Powstaje macierz:
$
\left|\begin{array}{c|cc|ccc}
1 & 0 & 0 & 0 & 0 & 0 \\
\hline
-2 & 2 & 0 & 0 & 0 & 0 \\
-2 & 0 & 2 & 0 & 0 & 0 \\
\hline
1 & -2 & 0 & 1 & 0 & 0 \\
2 & -2 & -2 & 0 & 2 & 0 \\
1 & 0 & -2 & 0 & 0 & 1 \\
\end{array}\right|
$
Dla stopnia 3 będziemy mieli macierz:
$
\left|\begin{array}{c|cc|ccc|cccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
-3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
-3 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
3 & -6 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\
6 & -6 & -6 & 0 & 6 & 0 & 0 & 0 & 0 & 0 \\
3 & 0 & -6 & 0 & 0 & 3 & 0 & 0 & 0 & 0 \\
\hline
-1 & 3 & 0 & -3 & 0 & 0 & 1 & 0 & 0 & 0 \\
-3 & 6 & 3 & -3 & -6 & 0 & 0 & 3 & 0 & 0 \\
-3 & 3 & 6 & 0 & -6 & -3 & 0 & 0 & 3 & 0 \\
-1 & 0 & 3 & 0 & 0 & -3 & 0 & 0 & 0 & 1 \\
\end{array}\right|
$
Do przeliczania z bazy wielomianowej na bazę Bernsteina będziemy potrzebowali macierzy odwrotnych:
dla 2:
$
\left|\begin{array}{c|cc|ccc}
1 & 0 & 0 & 0 & 0 & 0 \\
\hline
1 & 1/2 & 0 & 0 & 0 & 0 \\
1 & 0 & 1/2 & 0 & 0 & 0 \\
\hline
1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1/2 & 1/2 & 0 & 1/2 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 \\
\end{array}\right|
$

dla n=3:
$
\left|\begin{array}{c|cc|ccc|cccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
1 & 1/3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1/3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline
1 & 2/3 & 0 & 1/3 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1/3 & 1/3 & 0 & 0/3 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 2/3 & 0 & 0 & 1/3 & 0 & 0 & 0 & 0 \\
\hline
1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
1 & 2/3 & 1/3 & 1/3 & 1/3 & 0 & 0 & 1/3 & 0 & 0 \\
1 & 1/3 & 2/3 & 0 & 1/3 & 1/3 & 0 & 0 & 1/3 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\
\end{array}\right|
$
Tutaj prawidłowość tworzenia takich macierzy staje się widoczna dopiero od n=4 czy nawet 5.

Algorytm tworzenia tego typu macierzy korzystający z trójkąta Pascala:

procedure MakePascal;
var i,j:integer;
begin
 Pascal[0,0]:=1;
 for i:=1 to stopien do
 begin
  Pascal[i,0]:=1;
  for j:=1 to i-1 do Pascal[i,j]:=Pascal[i-1,j-1]+Pascal[i-1,j];
  Pascal[i,i]:=1;
 end;
end;

procedure MakeMac;
var i,j:integer;
    x0,y0,x1,y1,delta0,delta1:integer;
    wartosc:real;
begin
  for y0:=0 to stopien do
  for x0:=0 to stopien do
  begin
   delta0:=y0-x0;
   if delta0>=0 then
    for y1:=0 to y0 do
    for x1:=0 to x0 do
    begin
        delta1:=y1-x1;
        if (delta1>=0)and(delta1<=delta0) then
            wartosc:=pascal[stopien,delta0]*pascal[stopien-delta0,x0]*
                    pascal[x0,x1]*pascal[delta0,delta1]

            else wartosc:=0;
        if odd(delta0) then wartosc:=-wartosc;
        Mac[round(y0*(y0+1)/2+y1),round(x0*(x0+1)/2+x1)]:=wartosc;
    end{for x1};
  end{for x0};
end;

procedure MakeMacOdw;
var i,j:integer;
    x0,y0,x1,y1,delta0,delta1:integer;
    wartosc:real;
begin
  for y0:=0 to stopien do
  for x0:=0 to stopien do
  begin
   delta0:=y0-x0;
   if delta0>=0 then
    for y1:=0 to y0 do
    for x1:=0 to x0 do
    begin
        delta1:=y1-x1;
        if (delta1>=0)and(delta1<=delta0) then
            wartosc:=1/pascal[y0,y1]*pascal[delta0,delta1]
                      /pascal[stopien,y0]*pascal[stopien-x0,stopien-y0]
            else wartosc:=0;
        Mac[round(y0*(y0+1)/2+y1),round(x0*(x0+1)/2+x1)]:=wartosc;
    end{for x1};
  end{for x0};
end;

(notka: S. Lodha i R. Goldman [9] podają swoje algorytmy na konwersję wielomianów wyrażonych w różnych bazach : wielomianowej i Beziera .)

Algorytm de Casteljau

Algorytm de Casteljau wyznaczania punktów trójkątnego płata powierzchni Beziera jest zupełnie analogiczny do algorytmu dla krzywych, a główne różnice występują w notacji. M.in. algorytm dla krzywych używa powtarzającej się liniowej interpolacji, również w przypadku trójkątów jest ona używana. (Jankowski [8] )
Dane: trójkątna tablica punktów $P_{i,j,k} \in R^2$
Siatka punktów kontrolnych ma strukturę trójkąta. W przypadku stopnia = 4, siatka kontrolna składa się z:
$
\begin{matrix}
& & & & P_{040} \\
& & &P_{031} & &P_{130} \\
& &P_{022} & &P_{121} & &P_{220} \\
&P_{013} & &P_{112} & & P_{211}& & P_{310} \\
P_{004} & &P_{103} & &P_{202} & & P_{301} & & P_{400}
\end{matrix}
$
Zauważmy, że wszystkie indeksy sumują się do 4, W ogólności, siatka kontrolna posiada 1/2(n+1)(n+2) wierzchołków.
Algorytm:

  1. Oblicz współrzędne barycentryczne (r,s,t) punktu (u,v) rozwiązując układ 3 równań liniowych

    rA+sB+tC = [u,v]
    r+s+t = 1
    {pierwsza równość rozkłada się na dwie}

  2. Dla wszystkich i,j,k>=0, takich, że i+j+k=n, podstaw $P^0_{i,j,k} = P_{i,j,k}$
  3. Dla m=1,2,…,n
    dla wszystkich i,j,k>=0, takich że i+j+k=n-m oblicz
    $P^m_{i,j,k} =rP^{m-1}_{i+1,j,k} +sP^{m-1}_{i,j+1,k} + tP^{m-1}_{i,j,k+1} $

Dowodzi się , że
$S(u,v) = P^n_{0,0,0}$

Mówiąc obrazowo : gdy mamy wielomian stopnia n, wtedy siatka kontrolna liczy 1/2(n+1)(n+2) wierzchołków i $n^2$ trójkątów siatki; dla n=3 siatka kontrolna składa się z 9 trójkątów, z czego wybieramy co drugi trójkąt i na podstawie danych r,s,t liczymy wierzchołki; wierzchołki obliczone na podstawie 6 wybranych trójkątów tworzą siatkę następnej warstwy; w przypadku algorytmu dla krzywych tworzyliśmy kolejne kolumny na podstawie poprzednich, tutaj tworzymy kolejne warstwy trójkątnych siatek o zmniejszających się rozmiarach; na podstawie ostatniej warstwy możemy obliczyć pojedynczy wierzchołek, którego wartość będzie równa wartości funkcji dla r,s,t,;
Podobnie jak to miało w miejsce w przypadku krzywych Beziera, algorytm de Casteljau można zastosować do podziału trójkątnego płatu na fragmenty.
Algorytm de Casteljau dla trójkątnych płatków jest bezpośrednim uogólnieniem odpowiedniego algorytmu dla krzywych. Tam oprócz tego, że otrzymaliśmy wartość funkcji dla danego parametru, dodatkowo otrzymywaliśmy punkty kontrolne dla dwóch krzywych. Tutaj można otrzymać punkty kontrolne dla trzech podtrójkątów , które powstają przez podział bazowego trójkąta w miejscu odpowiadającym współrzędnym barycentrycznym r,s,t.

W algorytmie dla krzywych można było wybrać punkty, które stanowiły punkty kontrolne dwóch podkrzywych . Tutaj można z kolejnych warstw wybrać punkty, które będą stanowiły siatkę punktów kontrolnych dla nowopowstałego podtrójkąta . Z każdej warstwy wybieramy punkty leżące na krawędzi, tworzą one kolejne warstwy siatki kontrolnej szukanego trójkąta. W ten sposób algorytm de Casteljau pozwala dzielić powierzchnie na mniejsze fragmenty i traktować je osobno.

Bazując na algorytmie de Casteljau możemy dostać wiele własności trójkątów Beziera:
\textit{Afiniczna niezmienność}: ta własność bierze się z tego, że liniowa interpolacja jest odwzorowaniem afinicznym oraz, że algorytm de Casteljau używa wyłącznie liniowej interpolacji.
\textit{Własność powłoki wypukłej} – jest zagwarantowana, ponieważ dla $0<=r,s,t<=1$ każdy $P^m_{i,j,k}$ jest wypukłą kombinacją poprzedniego $P^{m-1}_{i,j,k}$. Krzywe brzegowe trójkątnego płatka są określone przez brzegowe punkty kontrolne (mające co najmniej jedno zero w indeksie). Dla przykładu punkt na krzywej brzegowej $P_n(r,0,t)$ jest generowany przez
\scalebox{1.2}{$P^m_{i,j,k}(r,0,t) = rP^{m-1}_{i+1,j,k} + tP^{m-1}_{i,j,k+1} $} ; r+t=1

Jeżeli punkt podziału wybierzemy na krawędzi trójkąta, wtedy jeden z podtrójkątów zdegeneruje się do odcinka.

Gdy wybierzemy jako punkt podziału środek najdłuższej krawędzi otrzymamy algorytm bisekcji będący szczególnym przypadkiem algorytmu de Casteljau .
Interesujący, ze względu na upraszczanie się obliczeń, jest przypadek, kiedy trójkąt prostokątny (w dodatku równoramienny) dzielimy przez środek najdłuższej krawędzi.

Jeżeli trójkąt prostokątny jest zorientowany równolegle do układu współrzędnych, upraszcza to dodatkowo obliczenia, ale aby własność ta była zachowana, należy jeszcze podzielić powstałe trójkąty; w ten sposób trójkąt dzielimy od razu na cztery podtrójkąty; ma to również tę zaletę, że podtrójkąty mają średnicę dokładnie dwa razy mniejszą od trójkąta bazowego.

W. Boehm [2] przedstawia algorytmy Haase’go i de Casteljau podziału krzywych oraz algorytm na podział trójkątów Beziera. R Goldman prezentuje również [6] różne sposoby podziału trójkątnego płata na fragmenty. Boehm i Farin w swoim “Letter to editor” [3] krótko opisują trzy różne sposoby podziału trójkąta Beziera. Pierwszym jest sposób opisany powyżej, czyli podział trójkąta jednym wierzchołkiem. Drugi sposób pozwala na obliczenie siatki dla podtrójkąta, którego dwa wierzchołki znajdują się w dowolnym miejscu wewnątrz bazowego trójkąta, a trzeci wierzchołek w wierzchołku bazowym. Dla tego przypadku wymagane jest policzenie dwukrotnie większej liczby warstw. Trzeci sposób pozwala wyliczyć siatkę dla dowolnego podtrójkąta zawartego w trójkącie bazowym. Jego wadą jest wielka złożoność obliczeniowa: w przypadku podziału jednym wierzchołkiem, do wyliczenia jego wartości należało obliczyć n warstw, z których można było wybrać wartości innych punktów kontrolnych; tutaj dla każdego punktu kontrolnego musimy obliczyć n warstw.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *