Krzywa Béziera

Z Wikipedii

Krzywa Béziera – (czytaj: „krzywa bezjera”) parametryczna krzywa powszechnie stosowana w programach do projektowania inżynierskiego CAD (Microstation), projektowania grafiki komputerowej (Corel Draw, Adobe Illustrator, GIMP, Inkscape), do reprezentowania obrysów znaków w fontach 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 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., 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 ukrywał Citroen 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 – każda współrzędna punktu krzywej jest pewną funkcją liczby rzeczywistej – parametru; żeby określić krzywą na płaszczyźnie potrzebne są dwie funkcje, żeby 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 – krzywe B-sklejane (także krzywe gładkie).

Niezależnie od rodzaju krzywej na jej przebieg wpływa łamana kontrolna określona za pomocą punktów kontrolnych; liczba punktów kontrolnych 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 w łatwy sposób korygować błędy.

Spis treści

1 Podstawowe wiadomości
2 Podstawy matematyczne
3 Program rysujący wielomianowe krzywe Béziera
4 Ciekawostki
5 Bibliografia
6 Zobacz też
7 Linki zewnętrzne

[edytuj] Podstawowe wiadomości

Krzywe wielomianowe są powszechnie stosowane, w praktyce wykorzystuje się krzywe niskich stopni, opisywane niewielką liczbą punktów kontrolnych. Najpowszechniej drugiego stopnia (trzy punkty kontrolne, np. fonty TrueType) lub trzeciego stopnia (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. Ogólnie biorąc krzywe niskich stopni są wygodniejsze w użyciu, łatwiejsze w realizacji są różne algorytmy związane z krzywymi (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 aż wielką wadą np. 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, bowiem przemieszczenie 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).

Dlatego powszechnie stosuje się krzywe B-sklejane, które oferują lokalną kontrolę kształtu – przemieszczając jeden punkt kontrolny zmianie ulegnie tylko jego bliskie otoczenie. Krzywe B-sklejane są to takie krzywe, które składają się z kawałkó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łączenie tych kawałków krzywa będzie gładka. Szczególną popularność zyskały wymierne krzywe (oraz powierzchnie) B-sklejane, znane jako NURBS.

[edytuj] Podstawy matematyczne

[edytuj] 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 Beziera 4-tego 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 (aproksymuje) 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.

[edytuj] 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ślamy 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 równaniem (dla $A = (x 0, y 0), B = (x 1, y 1), C = (x 2, y 2), D = (x 3, y 3)$ ):

x (t) = a x t 3 + b x t 2 + c x t + 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 y t 3 + b y t 2 + c y t + 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 \times (x_1 - x_0)$

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

a x = x 3 - x 0 - c x - b x

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

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

a y = y 3 - y 0 - c y - b y

[edytuj] Wymierne krzywe Béziera

Zobacz więcej w osobnym artykule: Wymierna krzywa 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) = 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, albo wielomianowych).

Atuty w stosunku do wielomianowych krzywych Beziera:

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.

[edytuj] Krzywe B-sklejane

Zobacz więcej w osobnym artykule: Krzywa B-sklejana.

Krzywe B-sklejane składają się z kawałkó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 - 2 n$ . 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.

[edytuj] Program rysujący wielomianowe krzywe Béziera

Program przedstawiony poniżej potrafi narysować krzywe Béziera dowolnego stopnia, został napisany w jezyku Python. Domyślnie punkty kontrolne są losowane, przy jednym uruchomieniu generowane jest kilka krzywych. Liczbę krzywych, liczbę punktów kontrolnych i rozdzielczość obrazu można ustawić zmieniając wartości odpowiednich zmiennych.

Krzywa Béziera 14. stopnia (wygenerowana przez program)

# -*- coding: iso-8859-2 -*-
# 
# Program rysuje dowolną liczbę krzywych Beziera dowolnego stopnia.
# Do uruchomienia wymaga biblioteki PIL (Python Imaging Library).
 
newton_cache = {} # pamięć podręczna dla wyników funkcji newton
def Newton(n,k):
     '''Funkcja oblicza wartość symbolu Newtona'''
     global newton_cache
     if (n,k) not in newton_cache:
         # licznik = n*(n-1)*...*(n-k+1)
         licznik = 1
         for i in xrange(n-k+1, n+1):
             licznik *= i
 
         # mianownik = k!
         mianownik = 1
         for i in xrange(1, k+1):
             mianownik *= i
 
         newton_cache[(n,k)] = licznik/mianownik
 
     return newton_cache[(n,k)]
 
def B(n,i,t):
     '''
     Funkcja oblicza wartość wielomianu bazowego Bernsteina dla
     zadanego parametru t.
     '''
     return Newton(n,i) * (t**i) * (1.0-t)**(n-i)
 
def Bezier2D(punkty_kontrolne, k):
     '''
     Funkcja przybliża dwuwymiarową krzywą Beziera za pomocą łamanej
     złożonej z k segmentów. Zwraca listę wierzchołków łamanej.
 
     punkty_kontrolne - lista punktów kontrolnych: [(x0,y0), ..., (xn,yn)]
     k                - ilość segmentów
     '''
 
     n  = len(punkty_kontrolne)-1 # stopień krzywej Beziera
 
     # funkcja obliczająca współrzędne (x,y) punktu krzywej dla zadanego t
     def p(t):
         '''
         x = \sum_{i=0}^n x_i B^n_i(t)
         y = \sum_{i=0}^n y_i B^n_i(t)
         '''
         x = 0.0
         y = 0.0
         for i in xrange(n+1):
             x += punkty_kontrolne[i][0]*B(n,i,t)
             y += punkty_kontrolne[i][1]*B(n,i,t)
         return (x,y)
 
     dt = 1.0/k # krok parametru t
     return [p(i*dt) for i in xrange(k+1)]
 
# program główny
if __name__ == '__main__':
     import Image
     import ImageDraw
 
     # parametry programu
     n = 15              # liczba punktów kontrolnych (stopień krzywej+1)
 
     rozdzielczosc = 600 # rozdzielczość obrazów
     k = 200             # liczba segmentów łamanej przybliżającej krzywą
     l = 10              # liczba obrazów generowanych przy jednym
                         # uruchomieniu programu
 
     image = Image.new("RGB", (rozdzielczosc, rozdzielczosc))
     draw  = ImageDraw.Draw(image)
     from random import randint as R
 
     for i in xrange(l):
         print "Tworzenie krzywej %d z %d" % (i+1, l)
         # 1. Wylosowanie n punktów kontrolnych
         punkty_kontrolne = [(R(0,rozdzielczosc), R(0,rozdzielczosc)) for _ in xrange(n)]
 
         # 2. Wyznaczenie łamanej p przyliżającą krzywą Beziera
         p = Bezier2D(punkty_kontrolne, k)
 
         # 3. Rysowanie krzywej:
         # 3a. wyczyszczenie obrazu (kolorem białym)
         draw.rectangle( [0,0, rozdzielczosc,rozdzielczosc], fill="#fff")
 
         # 3b. rysowanie łamanej kontrolnej (w kolorze jasnoszarym)
         draw.line(punkty_kontrolne, fill="#ccc")
 
         # 3c. zaznaczenie niebieskimi kółkami punktów kontrolnych
         r = 2 # promień
         for (x,y) in punkty_kontrolne:
             draw.ellipse([x-r,y-r, x+r,y+r], fill="#00f")
 
         # 3d. rysowanie krzywej Beziera (w kolorze czerownym)
         draw.line(p, fill="#f00")
 
         # 4. Zapisanie obrazu do pliku
         image.save("Krzywa-Beziera_%03d_%04d.png" % (n,i), "PNG")

[edytuj] Ciekawostki

Krzywa Béziera to wygaszacz ekranu w Windows XP.

[edytuj] 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 Freiner, John F Hughes, Richard L Phillips: Wprowadzenie do grafiki komputerowej. Jan Zabrodzki (tłumaczenie). Warszawa: Wydawnictwa Naukowo-Techniczne, 1995. ISBN 83-204-1840-2.

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Interaktywny applet Javy obrazujący krzywe Béziera

Kategorie: Grafika komputerowa • Krzywe

We provide Linux to the World