Krzywe Béziera

Gdy spytamy grafika komputerowego czy inżyniera co to są krzywe Béziera, spotkamy się z odpowiedzią, że występują one w programach graficznych albo programach typu CAD. Mało kto jednak wie, jak skonstruować te krzywe. A ich teoria matematyczna nie jest trudna, ale bardzo ciekawa. Zapraszam do lektury.

Krzywe Béziera są powszechnie stosowane w praktyce inżynierskiej, programach graficznych i w samym przetwarzaniu obrazów. Nie są w matematyce wynalazkiem wiekowym. Wprowadził je francuski inżynier Pierre Bézier w latach 60-tych XX stulecia. Pierwotnie projektował z ich pomocą nadwozia samochodów marki Renault. Warto więc poznać te krzywe od kuchni.

Pewna ciekawa równość

Rozpocznijmy od przypomnienia wzoru dwumianowego Newtona. Niech \(n\in\NN\) oraz \(a,b\in\RR.\) Wtedy\[(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k},\]gdzie\[\binom{n}{k}=\frac{n!}{k!(n-k)!}\]to tzw. współczynniki dwumianowe. Zastosujmy ten wzór dla \(a=t\) oraz \(b=1-t\). Wtedy oczywiście \((a+b)^n=1^n=1.\) Dlatego\[\sum_{k=0}^n\binom{n}{k}t^k(1-t)^{n-k}=1.\]Składniki tej sumy nazywamy wielomianami Bernsteina:\[B_{n,k}(t)=\binom{n}{k}t^k(1-t)^{n-k}.\]Występują one m. in. w jednym z dowodów twierdzenia aproksymacyjnego Weierstrassa (mówiącego, że każda funkcja ciągła w przedziale \(\langle a,b\rangle\) jest granicą jednostajnie zbieżnego ciągu wielomianów). Dla przykładu niech \(n=3\). Wtedy\begin{align*}B_{3,0}(t)&=\binom{3}{0}t^0(1-t)^{3-0}=(1-t)^3,\\[1ex]B_{3,1}(t)&=\binom{3}{1}t^1(1-t)^{3-1}=3t(1-t)^2,\\[1ex]B_{3,2}(t)&=\binom{3}{2}t^2(1-t)^{3-2}=3t^2(1-t),\\[1ex]B_{3,3}(t)&=\binom{3}{3}t^3(1-t)^{3-3}=t^3.\\\end{align*} Interesować nas będą dwie własności wielomianów Bernsteina.

  1. Jeśli \(0\xle t\xle 1\), to \(B_{n,k}(t)\xge 0.\)
  2. \(\displaystyle\sum_{k=0}^n B_{n,k}(t)=1.\)

Są one kluczowe w konstrukcji krzywej Béziera.

Otoczka wypukła zbioru punktów

Ucząc się szkolnej geometrii poznajemy pojęcie zbioru wypukłego. Jest to taki zbiór, że jeśli dowolnie wybierzemy dwa jego punkty, to odcinek je łączący jest w nim zawarty. Podstawowe płaskie figury wypukłe to koło, prostokąt, wielokąt wypukły (będący częścią wspólną skończenie wielu półpłaszczyzn). Niech teraz \(A_0(x_0,y_0),\ A_1(x_1,y_1),\dots,A_n(x_n,y_n)\) będą punktami płaszczyzny. Istnieje dokładnie jeden wielokąt wypukły, którego wierzchołkami są niektóre (niekoniecznie wszystkie) z tych punktów. Nazywamy go otoczką wypukłą (ang. convex hull) zbioru punktów \(\{A_0,A_1,\dots,A_n\}.\) Każdy punkt \(P(x,y)\) tej otoczki można zapisać w następujący sposób:\begin{equation}\label{eq:1}\tag{1}\left\{\begin{aligned}x&=t_0x_0+t_1x_1+\dots+t_nx_n,\\y&=t_0y_0+t_1y_1+\dots+t_ny_n,\end{aligned}\right.\end{equation}gdzie \(t_0,t_1,\dots,t_n \in\langle 0,1\rangle\) spełniają warunek \(t_0+t_1+\dots+t_n=1.\) Współczynniki \(t_0,t_1,\dots,t_n\) zależą od współrzędnych punktów \(A_0,A_1,\dots,A_n\) oraz od współrzędnych samego punktu \(P\). Dla przykładu, jeśli \(t_0=t_1=\dots=t_n=\dfrac{1}{n+1},\) to punkt\[P\left(\frac{x_0+x_1+\dots+x_n}{n+1},\frac{y_0+y_1+\dots+y_n}{n+1}\right)\]nazywamy barycentrum zbioru punktów \(\{A_0,A_1,\dots,A_n\}\). Jeśli mamy tylko dwa punkty \(A_0,A_1\), to otoczka wypukła zbioru \(\{A_0,A_1\}\) jest odcinkiem o końcach \(A_0,A_1,\) a barycentrum jest jego środkiem.

Na rysunku wprowadzającym do artykułu zacieniowany wielokąt jest otoczką wypukłą zbioru punktów zaznaczonych na czerwono.

Krzywa Béziera

Wprowadzone powyżej wielomiany Bernsteina oraz otoczka wypukła posłużą nam do określenia krzywej Béziera oraz wskazania jej podstawowych własności. Niech znów będą dane punkty \(A_0(x_0,y_0),\ A_1(x_1,y_1),\dots,A_{n-1}(x_{n-1},y_{n-1}),A_n(x_n,y_n)\). Punkt \(A_0\) to początek, punkt \(A_n\) to koniec krzywej Béziera, zaś pozostałe punkty \(A_1,\dots,A_{n-1}\) nazwiemy punktami kontrolnymi. Jak zobaczymy później, mają one wpływ na kształt krzywej.

Niech \(P(x,y)\) będzie dowolnym punktem krzywej Béziera. Współrzędne \(x,y\) opisujemy równaniem parametrycznym:\begin{equation}\tag{2}\label{eq:2}\left\{\begin{aligned}x&=B_{n,0}(t)x_0+B_{n,1}(t)x_1+\dots+B_{n,n-1}(t)x_{n-1}+B_{n,n}(t)x_n,\\y&=B_{n,0}(t)y_0+B_{n,1}(t)y_1+\dots+B_{n,n-1}(t)y_{n-1}+B_{n,n}(t)y_n,\end{aligned}\right.\end{equation}gdzie \(t\in\langle 0,1\rangle.\) Porównajmy to równanie z równaniem \eqref{eq:1}. Występujące tu współczynniki \(B_{n,k}(t)\) (gdzie \(k=0,1,\dots,n-1,n\)), czyli wielomiany Bernsteina, są nieujemne i sumują się do jedynki. Oznacza to, że punkt \(P(x,y)\) leży w otoczce wypukłej zbioru punktów \(\{A_0,A_1,\dots,A_{n-1},A_n\}.\) Tak więc cała krzywa Béziera zawiera się w otoczce wypukłej zbioru definiujących ją punktów. Ponadto dla \(t=0\) otrzymujemy \(x=x_0,y=y_0\), czyli współrzędne punktu \(A_0\), zaś dla \(t=1\) otrzymujemy \(x=x_n,y=y_n\), czyli współrzędne punkty \(A_n.\) Dlatego krzywa Béziera przechodzi przez punkty \(A_0,A_n\) i sensownie jest nazwać je odpowiednio początkiem i końcem. Jak powiedziałem, pozostałe punkty są punktami kontrolnymi i na ogół krzywa Béziera nie przechodzi przez nie (chyba, że – dla przykładu – wszystkie punkty, tzn. początek, koniec i punkty kontrolne, leżą na jednej prostej, co nie jest ciekawym przypadkiem, bo wtedy sama krzywa Béziera jest odcinkiem).

Podsumujmy własności krzywej Béziera o początku \(A_0\), końcu \(A_n\) i punktach kontrolnych \(A_1,\dots,A_{n-1}.\)

  1. Określa ją równanie parametryczne \eqref{eq:2}, w którym występują wielomiany Bernsteina.
  2. Przechodzi przez początek i koniec, a punkty kontrolne decydują o jej kształcie.
  3. Zawiera się w otoczce wypukłej zbioru punktów \(\{A_0,A_1,\dots,A_{n-1},A_n\}.\)

Stwierdziłem, że punkty kontrolne decydują o kształcie krzywej Béziera. Zobaczymy to analizując kilka rysunków. Niech początkiem będzie punkt \(A_0(0,0)\), a końcem punkt \(A_4(4,0).\)

  1. Punkty kontrolne \(A_1(1,4),A_2(2,4),A_3(3,4).\)
  2. Punkty kontrolne \(A_1(1,4),A_2(2,1),A_3(3,4).\)
  3. Na kształt krzywej Béziera wpływa też zmiana kolejności punktów kontrolnych. Zobaczmy, co się stanie, gdy punkty z poprzedniego przykładu zapiszemy kolejności \(A_3(3,4),A_1(1,4),A_2(2,1).\)

Płaszczyzna to za mało

Jak łatwo zauważyć analizując równanie \eqref{eq:2}, podobnie można zdefiniować krzywą Béziera w przestrzeni trójwymiarowej, a także w przestrzeni wielowymiarowej. Jest to jedynie kwestia dopisania kolejnych współrzędnych. Wszystkie opisane powyżej własności pozostają w mocy.

Wszechobecność matematyki

Krzywe Béziera zostały wprowadzone nie przez matematyka, a przez inżyniera. Jednak Pierre Bézier musiał doskonale znać matematykę, aby w ogóle wpaść na pomysł opisu parametrycznego \eqref{eq:2}. Widzimy jak bardzo potrzeba nam matematyki w wielu dziedzinach nauki, a więc i życia. Informatyka, sztuka inżynierska, statystyka (więc i nauki społeczne garściami z niej czerpiące), nauki przyrodnicze i wiele innych byłyby znacznie uboższe, gdyby nie wspomagała ich królowa. Dlatego nie pytaj, młody człowieku, kiedy przydadzą Ci się sinus czy cosinus albo wzory skróconego mnożenia. Jeśli chcesz coś znaczyć jako inżynier czy inny badacz, czym prędzej rozpocznij naukę matematyki.

Napisz komentarz