Bézierova křivka

Představme konkrétní parametrickou křivku, která vychází z předpisu $$P(t)=w_0(t)P_0+w_1(t)P_1+w_2(t)P_2+...+w_n(t)P_n$$ kde $w$ jsou váhové funkce a $P$ vstupní body.

Ukázka a vlastnosti

Pro křivku definovanou čtyřmi body ve 2D, dostaneme $$P_x(t)=w_0(t)P_{0,x}+w_1(t)P_{1,x}+w_2(t)P_{2,x}+w_3(t)P_{3,x}$$ $$P_y(t)=w_0(t)P_{0,y}+w_1(t)P_{1,y}+w_2(t)P_{2,y}+w_3(t)P_{3,y}$$ Křivka definovaná čtyřmi body se nazývá křivka třetího stupně. Připomeňme, že parametr $t$ nabývá hodnot $<0;1>$. Bézierova křivka třetího stupně může vypadat třeba takto


Vstupní čtyři body zadává uživatel a jejich změnou je schopen docílit změny výsledné křivky. Při editaci je třeba mít na paměti tři základní vlastnosti

1. křivka nikdy neopustí konvexní obal definovaný vstupními body
2. křivka bude vždy procházet prvním a posledním bodem
3. směr křivky v koncových bodech je určen sousedními body

V článku se budu odkazovat na konkrétní vlastnost použitím jejího pořadí v seznamu výše.

Váhové funkce

Ze vzorců výše vyplývá, že krom zadaných vstupních bodů budeme potřebovat ještě funkce $w_i$. Tyto funkce jsou generovány z Bernsteinových polynomů, které jsou definovány jako $$w_k(t)=\binom{n}{k}(1-t)^{n-k}(t)^k$$ kde $n$ je počet stupňů výsledné křivky. Počet stupňů se pak rovná počtu řídících bodů mínus jedna. Vypočítejme tedy funkce $w_i$ pro křivku třetího stupně (čtyři řídící body) $$\begin{array}{lcl} w_0(t)&=&\binom{3}{0}(1-t)^{3-0}(t)^0= \\ &=&1(1-t)^3\cdot1= \\ &=&(1-t)^3 \\ \end{array}$$ $$\begin{array}{lcl} w_1(t)&=&\binom{3}{1}(1-t)^{3-1}(t)^1= \\ &=&3(1-t)^2t^1= \\ &=&3(1-t)^2t \\ \end{array}$$ $$\begin{array}{lcl} w_2(t)&=&\binom{3}{2}(1-t)^{3-2}(t)^2= \\ &=&3(1-t)^1t^2= \\ &=&3(1-t)t^2 \\ \end{array}$$ $$\begin{array}{lcl} w_3(t)&=&\binom{3}{3}(1-t)^{3-3}(t)^3= \\ &=&1(1-t)^0t^3= \\ &=&1t^3= \\ &=&t^3 \\ \end{array}$$ a vynesme je pro názornost do grafu

Příklad

Zkusme dle obecného vztahu výše, postupně vypočítat Bézierovu křivku pro následující čtyři body

P	x	y
0	0	0
1	30	50
2	60	50
3	90	0

Dosadíme pro $x$ $$P_x(t)=(1-t)^3\cdot0+3(1-t)t^2\cdot30+3(1-t)^2t\cdot60+t^3\cdot90$$ a pro $y$ $$P_y(t)=(1-t)^3\cdot0+3(1-t)t^2\cdot50+3(1-t)^2t\cdot50+t^3\cdot0$$ Po úpravách pak dostáváme $$\begin{align*} P_x(t)&=30\cdot3(1-t)t^2+60\cdot3(1-t)^2t+90t^3 \\ P_y(t)&=50\cdot3(1-t)t^2+50\cdot3(1-t)^2t \end{align*}$$ Zkusme vypočítat hodnoty $x$ a $y$ pro bod v čase $t=0$ $$\begin{array}{lcl} P_x(0)&=&30\cdot3(1-0)0^2+60\cdot3(1-0)^2\cdot0+90\cdot0^3= \\ &=&30\cdot3\cdot1\cdot0+60\cdot3\cdot1\cdot0+90\cdot0= \\ &=&0+0+0= \\ &=&0 \\ P_y(0)&=&50 \cdot 3(1-0)0^2+50\cdot3(1-0)^20= \\ &=&50\cdot3\cdot1 \cdot 0+50\cdot3\cdot1\cdot0= \\ &=&0+0= \\ &=&0 \\ \end{array}$$ a přidejme také výpočet pro čas $t=1$ $$\begin{array}{lcl} P_x(1)&=&30 \cdot 3(1-1)1^2+60 \cdot 3(1-1)^2 \cdot 1+90 \cdot 1^3= \\ &=&30 \cdot 3\cdot0 \cdot 1+60 \cdot 3\cdot0+90\cdot1= \\ &=&0+0+90= \\ &=&90 \\ P_y(1)&=&50\cdot3(1-1)1^2+50 \cdot 3(1-1)^2 \cdot 1= \\ &=&50\cdot3 \cdot 0 \cdot 1+50\cdot3\cdot0\cdot1= \\ &=&0+0= \\ &=&0 \\ \end{array}$$ Jak vidíme, dostali jsme první bod výsledné křivky $[0,0]$ a poslední $[90,0]$. Toto koresponduje s 2. vlastností Bézierových křivek, tedy že první bod musí odpovídat bodu $P_0$ a poslední bodu $P_{n-1}$. Stejným způsobem vypočítáme hodnoty pro $x$ a $y$ na celém intervalu $t$.

Implementace

Algoritmus má pár zvláštností, které můžou být v rozporu s naší individuální představou. Pseudokód pro výpočet křivky třetího stupně může vypadat takto

d = 0.01;

for(t = 0, t <= 1; t = t + d) {
   w0 = (1-t)*(1-t)*(1-t)
   w1 = 3*(1-t)*(1-t)*t
   w2 = 3*(1-t)*t*t
   w3 = t*t*t;

   x = w0*P0x + w1*P1x + w2*P2x + w3*P3x;
   y = w0*P0y + w1*P1y + w2*P2y + w3*P3y;

   putPixel(x, y);
}

Narážíme na problém - nejsme schopni spočítat všechny hodnoty na intervalu od 0 do 1! Pracujeme v diskrétním prostoru, což pro nás znamená použití určitého kroku. Vypočítáme tedy množinu bodů s krokem definovaným v proměnné d a ty vykreslíme na obrazovku. Nedostaneme krásnou křivku jako na obrázcích výše, ale více či méně separovaných bodů. Nabízí se řešení nastavit d dostatečně malé. Tento způsob nebude uspokojivě fungovat z několika důvodů. Pokud bude d příliš malé, budeme počítat hodnoty pro menší velikost, než je šířka pixelu na obrazovce. Pokud bude příliš velké, budou nám vznikat díry. Například pro d=0.2 dostaneme hodnoty pro pouhých šest bodů ${0, 0.2, 0.4, 0.6, 0.8, 1}$. Jako optimální řešení volíme spojení dvou bezprostředně za sebou následujících bodů úsečkou.

d = 0.01;
predchozi_x = x0;
predchozi_y = y0;

for(t = 0, t <= 1; t = t + d) {
   w0 = (1-t)*(1-t)*(1-t)
   w1 = 3*(1-t)*(1-t)*t
   w2 = 3*(1-t)*t*t
   w3 = t*t*t;

   x = w0*P0x + w1*P1x + w2*P2x + w3*P3x;
   y = w0*P0y + w1*P1y + w2*P2y + w3*P3y;

   line(predchozi_x, predchozi_y, x, y);

   predchozi_x = x;
   predchozi_y = y;
}

Při zvolení vhodného d si tuto aproximaci můžeme dovolit, protože i oblouček můžeme diskrétně chápat jako spojení více krátkých úseček.

Literatura a odkazy

KOLCUN, A. Základy počítačovej grafiky. Učební texty, Ostrava 2006.
ŽÁRA, J.; SOCHOR, J.; BENEŠ, B.; FELKEL, P. Moderní počítačová grafika. Computerpress, Brno 2004.

http://lubovo.misto.cz/_MAIL_/curves/ - pěkné zpracování tématiky v češtině, včetně appletů
http://herakles.zcu.cz/education/zpg/cviceni.php?no=11 - materiály ze Zápodočeské Univerzity v Plzni, také interaktivní
http://processingjs.nihongoresources.com/bezierinfo/ - spousta dalších informací a detailů (anglicky)
http://en.wikipedia.org/wiki/B%C3%A9zier_curve