Krzywa Béziera

Przykładowa krzywa Béziera

Krzywa Béziera (wym. /'be.zje.ra/) – parametryczna krzywa powszechnie stosowana w programach do projektowania inżynierskiego CAD (MicroStation), projektowania grafiki komputerowej (Corel Draw, Adobe Illustrator, Inkscape), do reprezentowania kształtów znaków w czcionkach komputerowych (TrueType, METAFONT, Type1) i systemach przetwarzania grafiki (PostScript, MetaPost) oraz w grafice wektorowej (np. format SVG).

Krzywe Béziera zostały niezależnie opracowane przez Pierre'a Béziera, francuskiego inżyniera firmy Renault, oraz Paula de Casteljau, pracującego dla konkurencyjnej firmy Citroën. Prace nad krzywymi prowadzone były przez obu naukowców od początku lat 60. XX w., ale przez długi okres objęte ścisłą tajemnicą służbową. Dopiero pod koniec lat 60. pojawiły się pierwsze ogólnodostępne publikacje Pierre Béziera przedstawiające jego koncepcje, natomiast prace de Casteljau koncern Citroen ukrywał jeszcze przez kilka lat – pierwsze wzmianki o nim pojawiają się dopiero w 1971, gdy prace Béziera były znane od dawna. Do rozpowszechnienia się krzywych Béziera znacząco przyczynił się A. R. Forrest artykułem Interactive interpolation and approximation by Bezier polynomials opublikowanym w 1972 roku w branżowym piśmie The Computer Journal.

Krzywe Béziera są krzywymi parametrycznymi, tzn. każda współrzędna punktu krzywej jest pewną funkcją liczby rzeczywistej będącej wspomnianym parametrem; aby określić krzywą na płaszczyźnie potrzebne są dwie funkcje, aby określić krzywą w przestrzeni – trzy, itd. Ze względu na rodzaj tych funkcji mówi się o krzywych wielomianowych oraz krzywych wymiernych. Powszechnie stosuje się również krzywe złożone z kawałków gładko połączonych krzywych wielomianowych bądź wymiernych, tzw. krzywych B-sklejanych (także: krzywych gładkich).

Niezależnie od rodzaju krzywej, na jej przebieg wpływa łamana kontrolna, określona za pomocą punktów kontrolnych, których liczba jest zwykle niewielka. Ta cecha bardzo ułatwia pracę interakcyjną, bowiem człowiek w naturalny sposób może ustalać położenie punktów i łatwo korygować błędy.

Podstawowe wiadomości

Przykład wielomianowej krzywej Béziera 14. stopnia

• Krzywe wielomianowe są powszechnie stosowane. W praktyce wykorzystuje się krzywe niskich stopni, opisywane niewielką liczbą punktów kontrolnych. Najpowszechniej stosowane są krzywe drugiego stopnia (trzy punkty kontrolne, np. fonty TrueType) lub trzeciego (cztery punkty kontrolne, np. fonty Type1, METAFONT, SVG, cała gama różnych pakietów graficznych); rzadziej stosuje się krzywe wyższych stopni. Krzywe wielomianowe są również dostępne w wielu bibliotekach programistycznych, np. OpenGL, Java2D, Tcl. Krzywe niskich stopni są wygodniejsze w użyciu, łatwiejsze w realizacji są różne algorytmy związane z takimi krzywymi np: obcinanie, wyznaczanie przecięć z innymi krzywymi, wyznaczanie ekstremów itp.

• Krzywe wymierne mają nad krzywymi wielomianowymi jedną zasadniczą przewagę: można za ich pomocą reprezentować wszystkie krzywe stożkowe, w szczególności okręgi, elipsy i ich wycinki, co ma fundamentalne znaczenie w projektowaniu wspomaganym komputerowo. Krzywe wielomianowe mogą okręgi i elipsy zaledwie aproksymować, co jednak nie jest wadą w zastosowaniach rysunkowych, gdzie dokładność nie jest priorytetem.

Zarówno krzywe wielomianowe, jak i wymierne cechuje jedna wspólną niedogodność – trudno za pomocą jednej krzywej przedstawiać skomplikowane kształty. Można co prawda dodawać nowe punkty kontrolne, ale to powoduje, że kontrola kształtu jest mocno utrudniona, przemieszczenie bowiem jednego punktu wpływa na całą krzywą, a ponadto im wyższy stopień, tym zmiana położenia punktów kontrolnych jest mniej widoczna (mówiąc obrazowo, trzeba punkty przemieszczać na duże odległości, aby odniosło to jakiś widoczny skutek). Z tego względu powszechnie stosuje się krzywe B-sklejane, które oferują lokalną kontrolę kształtu – na skutek przemieszczenia jednego punktu kontrolnego zmianie ulegnie tylko jego bliskie otoczenie. Krzywe B-sklejane są to takie krzywe, które składają się z fragmentów krzywych bądź to wielomianowych, bądź wymiernych (względnie niskiego stopnia), natomiast matematyczne równania opisujące taką krzywą gwarantują, iż w punktach połączenia różnych fragmentów krzywa będzie gładka. Szczególną popularność zyskały wymierne krzywe oraz powierzchnie B-sklejane, znane jako NURBS.

Podstawy matematyczne

Krzywe wielomianowe

Dane są punkty kontrolne $p_0, \ldots, p_n$ w liczbie $n+1$.

Kształt krzywej Béziera opisują wielomiany, dla których przyjęto dziedzinę $[0,1]$. Stopień wielomianu wprost zależy od liczby punktów kontrolnych – wynosi $n$ (liczba punktów kontrolnych minus jeden). Wielomiany są zwykle przedstawiane w bazie wielomianów Bernsteina (oznaczane jako $B_i^n(t)$, bądź w literaturze anglojęzycznej $B_{i,j}(t)\;$). Wielomiany bazowe Bernsteina są wygodne w tym sensie, że punkty kontrolne są w naturalny sposób współczynnikami takiego wielomianu – nie trzeba dokonywać dodatkowych przeliczeń.

Dowolny punkt na krzywej jest opisywany zależnością:

$p(t) = \sum_{i=0}^n p_i B^n_i(t) \quad \textrm{dla\ } t \in [0,1],$

np. krzywą dwuwymiarową opisuje para wielomianów:

$(x,y) = \left(\sum_{i=0}^n x_i B^n_i(t), \sum_{i=0}^n y_i B^n_i(t)\right)$

Punkt $p(t)$ można również znaleźć za pomocą algorytmu de Casteljau.

Przykład dwuwymiarowej krzywej Béziera 4. stopnia i wielomiany X(t) i Y(t), które ją tworzą. Kolorem niebieskim zaznaczono punkty kontrolne, szarym narysowane są wykresy wielomianów bazowych Bernsteina przemnożonych przez współrzędne punktów kontrolnych.

Cechy charakterystyczne wielomianowych krzywych Béziera:

• Krzywa interpoluje punkty kontrolne (tj. $p(0)=p_0$ i $p(1)=p_n$), a przybliża pozostałe.
• Krzywa ma własność otoczki wypukłej, tzn. dla $t \in [0,1]$ punkt $p(t)$ leży w otoczce wypukłej punktów kontrolnych $p_0, \ldots, p_n$.
• Konstrukcja krzywej jest niezmiennicza względem przekształceń afinicznych, tzn. krzywa wyznaczona z przekształconych punktów kontrolnych jest taka sama jak krzywa po tym przekształceniu.
• Pojedyncza krzywa ma nieskończenie wiele reprezentacji – dla krzywej opisywanej przez $n$ punktów kontrolnych można wskazać taki ciąg punktów kontrolnych w liczbie $n+k$ ($k=1,\ldots$), które opisują dokładnie tę samą krzywą. Taka procedura wyznaczania dodatkowych punktów nosi nazwę podnoszenia stopnia (ang. degree elevation). W praktyce stosuje się jednak krzywe możliwie niskich stopni, natomiast zwiększanie ilości punktów kontrolnych służy do konwersji między różnymi krzywymi.

Wadą wielomianowych krzywych Béziera jest to, że nie można za ich pomocą reprezentować krzywych stożkowych, okręgów, elips, itd. Tej wady pozbawione są wymierne krzywe Béziera.

Wielomianowe krzywe Béziera trzeciego stopnia

Krzywa Béziera trzeciego stopnia

Najczęściej używane są krzywe trzeciego stopnia leżące na płaszczyźnie. Definiując krzywą trzeciego stopnia określa się 4 punkty $A$, $B$, $C$ i $D$ (na rysunku odpowiednio $P_0, P_1, P_2, P_3$), których położenie wyznacza przebieg krzywej. Krzywa ma swój początek w punkcie $A$ i skierowana jest w stronę punktu $B$. Następnie zmierza w stronę punktu $D$ dochodząc do niego od strony punktu $C$. Odcinek $\overline {AB}$ jest styczny do krzywej w punkcie $A$, natomiast odcinek $\overline {CD}$ jest styczny w punkcie $D$

Krzywą Béziera trzeciego stopnia określa następujące równanie:

$P(t) = A (1-t)^3 + 3 B t(1-t)^2 + 3 C t^2 (1-t) + D t^3\;$     dla $0 \le t \le 1\;$.

czyli:

$P_x(t) = A_x (1-t)^3 + 3 B_x t(1-t)^2 + 3 C_x t^2 (1-t) + D_x t^3\;$

$P_y(t) = A_y (1-t)^3 + 3 B_y t(1-t)^2 + 3 C_y t^2 (1-t) + D_y t^3\;$

Alternatywny zapis macierzowy:

$P(t) = \left[A, B, C, D\right] \cdot \left[\begin{matrix}-1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0\end{matrix}\right] \cdot \left[\begin{matrix}t^3 \\ t^2 \\ t \\ 1 \end{matrix}\right]$

Krzywa ma swój początek w punkcie $A$ ($t=0$) i koniec w punkcie $D$ ($t=1$) .

Krzywą Béziera trzeciego stopnia można też opisać następującym układem równań dla $A=(x_0, y_0), B=(x_1, y_1), C=(x_2, y_2), D=(x_3, y_3)\colon\;$

$x_{(t)}=a_xt^3 + b_xt^2 + c_xt + x_0\;$

$x_1 = x_0 + \frac {c_x} {3}$

$x_2 = x_1 + \frac {c_x + b_x} {3}$

$x_3 = x_0 + c_x + b_x + a_x\;$

$y_{(t)} = a_yt^3 + b_yt^2 + c_yt + y_0\;$

$y_1 = y_0 + \frac {c_y} {3}\;$

$y_2 = y_1 + \frac {c_y + b_y} {3}\;$

$y_3 = y_0 + c_y + b_y + a_y\;$

Zdefiniowane w ten sposób wzory mogą zostać odwrócone tak, by otrzymać zmienne kierunkowe (są one stałe dla każdej krzywej Béziera):

$c_x = 3 (x_1 - x_0)\;$

$b_x = 3 (x_2 - x_1) - c_x\;$

$a_x = x_3 - x_0 - c_x - b_x\;$

$c_y = 3 (y_1 - y_0)\;$

$b_y = 3 (y_2 - y_1) - c_y\;$

$a_y = y_3 - y_0 - c_y - b_y\;$

Wymierne krzywe Béziera

Wymierne krzywe Béziera

Wymierna krzywa Béziera to rzut środkowy wielomianowej krzywej Béziera zdefiniowanej we współrzędnych jednorodnych na płaszczyznę $W=1$. Tak samo dane jest $n+1$ punktów kontrolnych.

Jeśli przestrzeń jednorodna jest $k+1$-wymiarowa, wówczas do opisu krzywej potrzebne jest tyleż wielomianów. Dowolny punkt krzywej wielomianowej jest dany jako $P(t) = (X(t), Y(t), \ldots, W(t))$. Po przejściu na współrzędne kartezjańskie (rzucie środkowym $P(t)$ na płaszczyznę $W=1$) otrzymuje się $k$ wyrażeń wymiernych, a punkt na tej płaszczyźnie dany jest wzorem $p(t) = \left(\frac{X(t)}{W(t)}, \frac{Y(t)}{W(t)}, \ldots \right)$.

Jeśli $W(t)=\textrm{const}$ to krzywa jest wielomianowa - mówiąc nieformalnie krzywe wielomianowe to specjalny przypadek krzywych wymiernych.

Dowolny punkt na krzywej wymiernej dany jest wzorem:

$p(t) = \frac{\sum_{i=0}^n w_i p_i B^n_i(t)}{\sum_{i=0}^n w_i B^n_i(t)} \qquad t \in [0,1]$

Gdzie $w_i$ to współrzędna W, jednak częściej nazywana jest wagą punktu kontrolnego.

Aby wyznaczyć punkt na krzywej można także posłużyć się algorytmem de Casteljau albo wariantem dla krzywych wymiernych lub wielomianowych.

Atuty w stosunku do wielomianowych krzywych Béziera są następujące:

• mogą reprezentować wszystkie krzywe stożkowe, co ma znaczenie w zastosowaniach CAD;
• rzut perspektywiczny krzywej wymiernej jest zawsze krzywą wymierną, podczas gdy rzut perspektywiczny krzywej wielomianowej nie musi być krzywą wielomianową, co ma znaczenie w grafice komputerowej;
• wagi $w_i$ pozwalają na lepszą kontrolę nad kształtem krzywej.

Krzywe B-sklejane

Krzywe B-sklejane składają się z fragmentów wielomianowych bądź wymiernych krzywych Béziera, najczęściej niskiego stopnia ($n$). Dla krzywej B-sklejanej parametr $t$ również należy do przedziału $[0,1]$. Przedział ten jest dzielony na podprzedziały, a liczby określające ich granicę nazywane są węzłami (ang. knot). Kolejne węzły mogą być sobie równe, tworząc w ten sposób puste podprzedziały – nie jest to błąd.

Jeśli węzłów jest $m+1$ ($u_0, \ldots, u_m$), a stopień wielomianów jest równy $n$, to do określenia krzywej potrzebne jest $m-n$ punktów kontrolnych, zaś liczba krzywych, które składają się na całość, wynosi $m-2n$. Sklejane krzywe są zdefiniowane na przedziale $[u_n, u_{m-n}]$, nie na $[0,1]$.

Dowolny punkt na krzywej B-sklejanej jest dany wzorem, który wynika z algorytmu Mansfielda-de Boora-Coxa:

$p(t) = \sum_{i=0}^{m-n-1} p_i N_i^n(t) \quad \textrm{dla\ }t \in [u_n, u_{m-n}],\;$

gdzie $N_i^n$ to unormowane funkcje B-sklejane stopnia $n$.

Krzywe B-sklejane mają następujące zalety w stosunku do krzywych wielomianowych i wymiernych:

• Lokalna kontrola kształtu – przemieszczanie jednego punktu kontrolnego wpływa na niewielkie otoczenie tego punktu, najwyżej $n$ sąsiednich krzywych.
• Możliwość dowolnego rozmieszczania węzłów daje lepszą i większą kontrolę nad kształtem krzywej. Dodatkowo jeśli węzły pokrywają się, tzn. istnieją puste podprzedziały, uzyskuje się "ostre" (nie gładkie) połączenia.
• W łatwy sposób można wstawiać nowe węzły (ang. knot insertion), dzięki czemu proces modelowania jest prostszy.

Szczególne znaczenie i popularność zyskały wymierne krzywe B-sklejane (NURBS), łączące zalety zwykłych krzywych wymiernych z wymienionymi wyżej.

Bibliografia

• Przemysław Kiciak: Podstawy modelowania krzywych i powierzchni: zastosowania w grafice komputerowej. Warszawa: Wydawnictwa Naukowo-Techniczne, 2000. ISBN 83-204-2464-X. 
• James D Foley, Andries van Dam, Steven K Feiner, John F Hughes, Richard L Phillips: Wprowadzenie do grafiki komputerowej. Jan Zabrodzki (tłumaczenie). Warszawa: Wydawnictwa Naukowo-Techniczne, 1995. ISBN 83-204-1840-2. 

Zobacz też

• lista krzywych
• Płaty Béziera

Linki zewnętrzne

• Interaktywny applet Javy obrazujący krzywe Béziera