Kilka słów o krzywych Béziera

03.06.2009 - Paweł Woźny

Grafika komputerowa jest jednym z ciekawszych działów informatyki. O jej przydatności nie trzeba Was pewnie przekonywać (szczególnie tych, którzy sporo czasu spędzają przy grach komputerowych). Dziś trudno już wyobrazić sobie grafika, projektanta, twórcę filmów animowanych czy efektów specjalnych, który może obyć się bez komputera i zaawansowanych programów graficznych. Często metody i algorytmy wykorzystywane do tworzenia na ekranie komputera realistycznie wyglądających obiektów, scen czy animacji są bardzo skomplikowane. Istnieją jednak i takie, które są proste do zrozumienia, a mimo to pozwalają na uzyskanie ciekawych efektów. Do podstawowych narzędzi grafiki komputerowej zalicza się m.in. krzywe i powierzchnie Béziera, które są przez grafików często wykorzystywane w ich codziennej pracy.

W artykule tym zajmiemy się krzywymi Béziera. Wybierzmy $n+1$ punktów na płaszczyźnie, powiedzmy $\mathbf{W}_0$ , ${\bf W}_1,\ldots,{\bf W}_n$ . Krzywą Béziera (ang. Bézier curve) ${\bf P}:[0,1] \rightarrow \mathbb R^2$ dla tych punktów definiujemy następującym wzorem:

$\mathbf{P}(t)=B^n_0(t)\mathbf{W}_0+B^n_1(t)\mathbf{W}_1+\ldots+B^n_n(t)\mathbf{W}_n\qquad(0\leq t\leq 1).$

Punkty $\mathbf{W}_0, \mathbf{W}_1,\ldots,\mathbf{W}_n$ nazywamy punktami kontrolnymi (ang. control points) krzywej $\mathbf{P}$ , a $n$ — jej stopniem.

Musimy teraz wyjaśnić użyte oznaczenia. W podanym wzorze $B^n_k(t)$ $(k=0,1,\ldots,n)$ oznacza $k$ -ty wielomian Bernsteina stopnia $n$ (ang. $k$ th Bernstein polynomial of degree $n$ ),

$B^n_k(t)=\binom{n}{k}t^k(1-t)^{n-k},$

natomiast $\displaystyle \binom{n}{k}$ $(n,k\in\mathbb N)$ jest tzw. symbolem Newtona (ang. binomial coefficient),

$\binom{n}{k}=\frac{n!}{k!(n-k)!},$

gdzie $m!$ (czytamy: $m$ silnia; ang. $m$ th factorial) jest iloczynem kolejnych liczb naturalnych od $1$ do $m$ $(m=1,2,\ldots)$ , a $0!=0$ . I tak np.

$5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120,\qquad \binom{7}{4}=\frac{7!}{4!\cdot 3!}=35,\qquad B^{8}_3(t)=\binom{8}{3}t^3(1-t)^5.$

Wykresy wielomianów Bernsteina stopnia 5 widać na animacji 1.

Animacja 1.

Wydaje się to skomplikowane. Zróbmy więc prosty przykład. Przyjmijmy $n=4$ oraz

$\mathbf{W}_0=(0,0),\quad\mathbf{W}_1=(0,4),\quad\mathbf{W}_2=(2,5),\quad\mathbf{W}_3=(8,4),\quad\mathbf{W}_4=(4,0).$

Krzywa Béziera odpowiadająca podanym punktom wyraża się zatem wzorem

$\begin{array}{l}\mathbf{P}(t)=B^4_0(t)\mathbf{W}_0+B^4_1(t)\mathbf{W}_1+B^4_2(t)\mathbf{W}_2+B^4_3(t)\mathbf{W}_3+B^4_4(t)\mathbf{W}_4=\\[1.25ex] \qquad=\binom{4}{0}t^4\mathbf{W}_0+\binom{4}{1}t^3(1-t)\mathbf{W}_1+\binom{4}{2}t^2(1-t)^2\mathbf{W}_2+\binom{4}{3}t(1-t)^3\mathbf{W}_3+\binom{4}{4}(1-t)^4\mathbf{W}_4,\end{array}$

a jej wykres można zobaczyć na rysunku 1. Dla danego $t\in[0,1]$ , $\mathbf{P}(t)$ jest punktem na płaszczyźnie. Przyjmijmy $t=\frac{1}{3}$ , wtedy $\mathbf{P}(\frac{1}{3})=(\frac{116}{81},\frac{280}{81})$ , bo

$\begin{array}{l}\mathbf{P}(t)=B^4_0\left(\frac{1}{3}\right)\mathbf{W}_0+B^4_1\left(\frac{1}{3}\right)\mathbf{W}_1+B^4_2\left(\frac{1}{3}\right)\mathbf{W}_2+B^4_3\left(\frac{1}{3}\right)\mathbf{W}_3+B^4_4\left(\frac{1}{3}\right)\mathbf{W}_4=\\[1.25ex] \qquad=\frac{16}{81}(0,0)+\frac{32}{81}(0,4)+\frac{8}{27}(2,5)+\frac{8}{81}(8,4)+\frac{1}{81}(4,0)=\\[1.25ex] \qquad=\left(\frac{16}{81}\cdot0+\frac{32}{81}\cdot0+\frac{8}{27}\cdot2+\frac{8}{81}\cdot8+\frac{1}{81}\cdot4,\frac{16}{81}\cdot0+\frac{32}{81}\cdot4+\frac{8}{27}\cdot5+\frac{8}{81}\cdot4+\frac{1}{81}\cdot0\right)=\\[1.25ex] \qquad=\left(\frac{116}{81},\frac{280}{81}\right).\end{array}$

Rysunek 1.

Krzywe Béziera mają wiele ciekawych własności. Krzywa $\mathbf{P}$ zaczyna się w punkcie $\mathbf{W}_0$ , bo $\mathbf{P}(0)=\mathbf{W}_0$ , a kończy — w punkcie $\mathbf{W}_n$ , bo $\mathbf{P}(1)=\mathbf{W}_n$ . Cała krzywa znajduje się w otoczce wypukłej (ang. convex hull) swoich punktów kontrolnych, tj. w najmniejszym wielokącie wypukłym zawierającym punkty $\mathbf{W}_0$ , $\mathbf{W}_1,\ldots,\mathbf{W}_n$ , co można zaobserwować na animacji 2. (zobacz też zadanie 3.). Własność ta ma duże znaczenie praktyczne. Pozwala ona bowiem stwierdzić w jakim obszarze znajduje się wykres krzywej. Wykorzystuje się to np. przy sterowaniu robotami pracującymi w halach fabrycznych. Ruch ich ramion jest często opisany właśnie krzywymi Béziera. Wykorzystując własność otoczki wypukłej można roboty zaprogramować tak, aby mieć pewność, że nie dojdzie do kolizji ich ramion.

Animacja 2.

Dla danego $t\in[0,1]$ , wartość $\mathbf{P}(t)$ oblicza się algorytmem de Casteljau wyznaczając punkty pomocnicze W[i,k] $(i=0,1,\ldots,n;\ k=0,1,\ldots,n-i)$ w następujący sposób rekurencyjny:

for k from 0 to n
W[0,k]:= $\mathbf{W}_k$

for i from 1 to n
for k from 0 to n-i
W[i,k]:=(1-t)*W[i-1,k]+t*W[i-1,k+1]

Wtedy $\mathbf{P}(t)=$ W[0,0].

Dla $i=1$ podany algorytm wyznacza $n$ punktów W[1,k] (bo $k$ zmienia się od $0$ do $n-1$ ), dla $i=2$ natomiast $n-1$ punktów W[2,k] (tym razem $k$ zmienia się od 0 do $n-2$ ), przy $i=3$ , obliczamy $n-2$ punkty W[3,k], itd. Można sprawdzić, że liczba punktów pomocniczych wyznaczanych przez algorytm de Casteljau wynosi $\displaystyle \frac{n(n+1)}{2}$ . Tak więc liczba wykonanych instrukcji przypisania (:=) oraz operacji arytmetycznych (+, -, *) jest proporcjonalna do $n^2$ . Informatycy powiedzą, że złożoność (ang. complexity) tego algorytmu wynosi $n^2$ . Co oznacza, że koszt jego wykonania rośnie proporcjonalnie do kwadratu liczby punktów kontrolnych krzywej Béziera.

Co prawda, wartość $\mathbf{P}(t)$ można wyznaczać szybciej (tj. proporcjonalnie do $n$ ; patrz zadanie 2.), jednak algorytm de Casteljau jest często stosowany z innych względów. Ma on bowiem wiele ważnych własności (nie będziemy się nimi teraz zajmować) oraz ciekawą interpretację geometryczną. Spróbuj ją dostrzec oglądając animację 3., na której pokazano jak stosując wspomniany algorytm wyznaczono wartość $\mathbf{P}(\frac{1}{3})$ .

Animacja 3.

Do narysowania krzywej Beziera można oczywiście wykorzystać komputer. Aby to zrobić wyznaczamy punkty

$\mathbf{P}_0:=\mathbf{P}(t_0),\quad \mathbf{P}_1:=\mathbf{P}(t_1),\quad\ldots,\quad \mathbf{P}_M:=\mathbf{P}(t_M),$

gdzie

$t_i:=\frac{i}{M}\qquad (i=0,1,\ldots,M),$

a $M$ jest dostatecznie duże (np. 100). Następnie, zamiast dokładnego wykresu krzywej $\mathbf{P}$ , na ekranie monitora rysujemy łamaną powstałą z połączenia ze sobą kolejno punktów $\mathbf{P}_0, \mathbf{P}_1,\ldots, \mathbf{P}_M$ .

Jak już wspomniałem na początku, krzywe Béziera są jednym z najczęściej używanych przez grafików komputerowych narzędziem. Przy ich pomocy można w prosty sposób modelować różne obiekty. Przeważnie używa się krzywych Béziera niewielkiego stopnia, a umiejętnie je łącząc uzyskuje się skomplikowane sceny. Animacja 4. pokazuje jak przy pomocy trzech krzywych narysować brzydkie kaczątko.

Animacja 4.

Na rysunku 2. widać kaczuszkę składającą się z 32 krzywych Béziera (punkty kontrolne wszystkich krzywych widoczne są na rysunku 3.).

Rysunek 2.

Rysunek 3.

Zachęcam do napisania programu, który pozwoli wykreślać krzywe Béziera. Można zacząć od prostego rozwiązania, polegającego na tym, że użytkownik podaje punkty kontrolne krzywej (lub krzywych) w pliku tekstowym. Ci z Was, którzy biegle już programują mogą pokusić się o przygotowanie aplikacji, która będzie łatwiejsza w obsłudze, np. punkty kontrolne będą wskazywane przy pomocy myszki, będzie je można dodawać, przesuwać, usuwać itp. Następnie wykorzystajcie swój program np. do wymodelowania karoserii wymarzonego samochodu, rysowania kaczuszek czy opracowania własnych krojów czcionek. Miłej zabawy!

Zadania

Udowodnij, że

$(a)\ \displaystyle B^n_k(x)\geq0$ dla $x\in[0,1]$ ,

$(b)\ \displaystyle B^n_0(x)+B^n_1(x)+\ldots+B^n_n(x)=1$ dla każdego $x\in\mathbb R$ .
Rozważmy wielomian $w$ podany w postaci naturalnej (potęgowej), tzn.
$w(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0.$
Bez trudu uzasadnisz, że dla danego rzeczywistego $x$ , wartość $w(x)$ można obliczać za pomocą następującego algorytmu Hornera:

w[n]:= $a_n$

for k from n-1 downto 0
w[k]:=w[k+1]*+ $a_k$

Wtedy $w(x)=$ w[0].

Wykorzystaj algorytm Hornera do opracowania metody wyznaczania punktu na krzywej Béziera stopnia $n$ , którego złożoność jest proporcjonalna do $n$ .
Zaproponuj algorytm wyznaczania otoczki wypukłej punktów $\mathbf{W}_0, \mathbf{W}_1,\ldots,\mathbf{W}_n\in\mathbb R^2$ . Jaką złożoność ma Twój algorytm?