% kodovania wincp-1250
%

\documentclass{article}
\usepackage{slovak,graphics,amsmath}
\usepackage{amssymb}

\begin{document}

\title{Krivky a plochy}
\author{Dávid Pál}
\maketitle

Toto som spísal učiac sa na štátnice z grafiky.

\part{Krivky}

Za krivky budeme považovať zobrazenie $C: I \to E^2$ prípadne $C: I \to E^3$,
kde $I$ je nejaký interval. Zvyčajne sa požaduje, aby $C(t)$ mala dostatočne veľa derivácií (najlepšie všetky)
a aby jej prvá derivácia nebola nulová (nulový vektor). Tieto dve požiadavky sa skrátene volajú hladkosť a regulárnosť.

\section{Hermitova krivka}
Na úvod začneme nejakou ľahkou krivkou.

Chceme zostrojiť polynóm s predpísanou funkčnou hodnotou v bode $0$, deriváciu v bode $0$, 
deriváciu v bode $1$ a funkčnou hodnotou v bode $1$, ako na to? Zostrojíme štyri kubické polynómy, 
také, že prvý polynóm bude mať funkčnú hodnotu v bode 0 rovnú jedna a zvyšné tri vlastnosti nulové.
Druhý bude mať druhú vlastnosť jedna a zvyšné nulové, atď. Také polynómy sú tieto: \footnote{Stupňa najviac 3 nutne existujú len a práve tieto.}
\begin{eqnarray}
H^3_0(t) &=&2t^3 - 3t^2 + 1 \\
H^3_1(t) &=& t^3 - 2t^2 + t \\
H^3_2(t) &=& t^3 - t^2 \\
H^3_3(t) &=& -2t^3 + 3t^2
\end{eqnarray}

Ak máme teraz dva body $V_0,V_1$ a dva vektory $u_0,u_1$, tak potom krivka
\begin{equation}
H(t) = V_0 H^3_0(t) + u_0 H^3_1(t) + u_1 H^3_2(t) + V_1 H^3_3(t), \qquad \text{pre } t \in [0,1]
\end{equation}
má tú vlastnosť, že začína v bode $V_0$, končí v bode $V_1$, derivácia (dotyčnica) v bode $0$ je
$u_0$ a derivácia v bode 1 je $u_1$. Táto krivka sa nazýva Hermitova alebo Nielsonova.

\section{Beziérove krivky}

Tieto krivky vymyslel Pierre Bezier (1910--1999) pre francúzsku automobilku Renault.

\subsection{Bernsteinove polynómy}

$k$-ty ($0 \le k \le n$) \emph{Bernesteinov polynóm}\footnote{Občas zvyknú volať aj Beziérove bázicé funkcie.} 
$n$-tého stupňa je
\begin{equation}
B^n_k(t) = {n \choose k} t^k(1-t)^{n-k}.
\end{equation}
Za ich definičný obor budeme brať interval $[0,1]$.

Tu sú polynómy pre malé $n$.
\begin{itemize}
\item Pre $n=0$ je jediný taký polynóm $B_0^0$ konštatne rovný $1.$
\item Pre $n=1$ sú dva $$B^1_0(t)=1-t,\quad B^1_1(t) = t.$$
\item Pre $n=2$ sú tri $$B^2_0(t)=(1-t)^2,\quad B^2_1(t) = 2t(1-t), \quad B^2_2(t)=t^2.$$
\item Pre $n=3$ sú štyri $$B^3_0(t)=(1-t)^3, \quad B^3_1(t) = 3t(1-t)^2, \quad  B^3_2(t)=3t^2(1-t), \quad B^3_3(t)=t^3.$$
\end{itemize}

Doležité je vedieť zderivovať taký Bernsteinov polynóm.
\begin{equation}
\begin{split}
[B^{n}_k(t)]^\prime  	&= \left[{n \choose k} t^k(1-t)^{n-k}\right]^\prime 				\\
		&= {n \choose k}kt^{k-1}(1-t)^{n-k} - {n \choose n-k}(n-k)t^k(1-t)^{n-k-1}	\\
		&= n{n-1 \choose k-1}t^{k-1}(1-t)^{n-k-1} - n{n-1 \choose n-k-1}t^{k-1}(1-t)^{n-k-1} \\
		&= n\left[{n-1 \choose k-1}t^{k-1}(1-t)^{n-k-1} - {n-1 \choose k}t^{k-1}(1-t)^{n-k-1}\right] \\
		&= n\left[B^{n-1}_{k-1}(t) - B^{n-1}_k(t) \right] \\
\end{split}
\end{equation}
V tomto vzorci (ale aj prípadne hocikde neskôr) pre $k$ mimo rozsahu $0,1,\dots,n$ berieme $B^n_k(t)$ konštatne nulový.
Dôvod je ten, že vtedy je (resp. sa kladie) ${n \choose k}=0$.

O Bernsteinových polynómoch platí niekoľko faktov, ktoré stoja za reč:

\begin{itemize}
\item Ich hodnoty sú v intervale $[0,1]$, teda presnejšie 
\begin{equation}
B^n_k(t) \in [0,1], \qquad \text{pre } t \in [0,1].
\end{equation}
\item Súčet všetkých $n+1$ polynómov dáva dokopy konštatnú jednotku
\begin{equation}
B^n_0(t) + B^n_1 + \dots + B^n_n(t) = \sum_{k=0}^n {n \choose k}t^k(1-t)^k  = ((1-t)+t)^n = 1.
\end{equation}
\item Sú to unimodálne (jednohrbé) funkcie s jediným maximov v bode $t=k/n$ (pre $n>0$).
\item Tvoria bázu polynómov nanajvýš $n$-tého stupňa.
\item Spĺňajú rekurenciu
\begin{equation}
B^{n+1}_k(t) = tB^n_{k-1}(t) + (1-t)B^n_k(t).
\end{equation}
\end{itemize}

\subsection{Beziérove krivky}

Keď máme daných $n+1$ bodov $V_0, V_1, \dots, V_n$ v euklidovskej rovine $E^2$ alebo priestore $E^3$, tak definujeme
\emph{Beziérovu krivku} $n$-tého stupňa
\begin{equation}
B^n(t) = \sum_{k=0}^n B^n_k(t) V_k, \qquad \text{pre } t \in [0,1].
\end{equation}

Keď sa to poderivuje, tak máme jej dotyčnicu v ľubovoľnom bode. Využijeme vyššie vyrátanú deriváciu Bersteinovho polynómu.
\begin{equation}
\begin{split}
[B^n(t)]^\prime	&= \left[\sum_{k=0}^n B^n_k(t) V_k \right]^\prime 			\\
		&= \sum_{k=0}^n [B^n_k(t)]^\prime V_k 					\\
		&= n\sum_{k=0}^n (B^{n-1}_{k-1}(t)  - B^{n-1}_k) V_k 			\\
		&= n\sum_{k=0}^{n-1} B^{n-1}_k(t) (V_{k+1} - V_k) 			\\
\end{split}
\end{equation}

Z tohto a vlastností Bernsteinových polynómov nám plynie, že
\begin{itemize}
\item Krivka leží celá v konvexnom obale svojich riadiacich vrcholov.
\item Má pseudolokálne riadenie. Teda keď pohnem nejakým vrcholom, tak sa "podstatne zmení" len kúsok okolo neho.
\item Krivka sa dotýka spojnice svojich dvoch prvých a dvoch posledných riadiacich bodov.
\end{itemize}

\subsection{Casteljauov algoritmus}
Je to algoritmus na vyčíslovanie (a následné vykreslenie) Bezierovej krivky pre nejakú hodnotu parametra $t$.
Samozrejme ide to robiť aj priamo dosadením do vzorca, ale toto je zábavnejšie, numericky stabilnejšie,
ba čo viac vieme tak ľahko krivku rozdeliť na dve.

Postup je nasledovný: Je dané nejaké fixné $t$, v ktorom rátame bod krivky. Na začiatku máme $n+1$ riadiacich vrcholov
$V_0, V_1, \dots, V_n$, označíme ich prefíkane ako body nultej generácie 
$$V_0^0 := V_0, \quad V_1^0 := V_1, \quad \dots, \quad V_n^0 := V_n.$$
Z nich skonštruujeme body prvej generácie, tých už bude len $n$. Následne body druhej, tých bude len $n-1$, atď.
Až nakoniec dostaneme jediný bod $V^n_0$ $n$-tej generácie. Tento bod je bodov Beziérovej krivky, teda $B^n(t) = V_0^0$.
Tu je rekurentný vzorec, ako rátať body $r$-tej generácie:
\begin{equation}
V_k^r = (1-t)V_k^{r-1} + tV_{k+1}^{r-1}, \qquad \text{pre } r<0\le n, \quad  0\le k \le n-r.
\end{equation}
Tento reku--rere
\footnote{Ako nám učiteľka matematiky na gymnáziu vysvetlila, že rekurencia je od rekurere, čo znamená kráčat spät.} 
sa nazýva \emph{Casteljauov algoritmus}.

To, že platí $B^n(t) = V_0^0$, teda $V_0^0$ je bodom krivky sa dokáže z toho
ľubovolný vrchol v ľubovoľnej generácii vieme vyjadriť pomocou pôvodných riadiacich vrcholov
\begin{equation}
V_k^r =  \sum_{j=0}^r B^r_j(t)V_{k+j}
\end{equation}
Toto sa hravo dokáže indukciou a použitím vlastností kombinačných čísel.

Krivka sa nám sekne v našom bode $t$ na dve časti. Obe sú to polynomické krivky a preto sú zapísateľné ako Bezierove krivky.
Dá sa dokázať, že riadiacimi vrcholmi ľavej časti sú vrcholy $V_0^0, V_0^1, V_0^2 \dots, V_0^n$
a pravej $V_0^n, V_1^{n-1}, V_2^{n-2} \dots, V_n^0$.
(Sú to dosť otravne dlhé výpočty. Lepšie je si to načrtnúť na papier a uveriť.)

\subsection{Zvyšovanie stupňa}

Toto slúži na to, keď chceme  pridať ďalší riadiaci vrchol bez toho, aby sme zmenili tvar krivky.
S viac riadiacimi vrcholmi môžme potom krivku lepšie a jemnejšie meniť.

Funguje to asi takto: Máme Beziérovu krivku $B(t)$ stupňa $n$ definovanú $n+1$
riadiacimi bodmi $V_0, V_1, \dots, V_n$.  Skonštruujeme riadiace vrcholy $W_0,
W_1, \dots, W_{n+1}$, také, že Beziérova krivka nimi určená, bude totožná s
našou $B(t)$.
Evidentne musí $W_0=V_0$ a $W_{n+1}=V_n$, zvyšné body sa dorátajú podľa nasledovného vzorca
\begin{equation}
W_i = \frac{i}{n+1}V_{i-1} + \left(1 - \frac{i}{n+1}\right)V_i.
\end{equation}
Dôkaz je priamočiare dosedenie a následné uťapakanie.
(To, že to principiálne muselo ísť vyjadriť, vyplýva z toho, polynóm stupňa najviac $n$ je aj polynómom stupňa najviac 
$n+1$ a z toho, že Bernsteinove polynómy tvoria bázu.)

\subsection{Racionálne Beziérove krivky}
Ide o zovšeobecnenie Beziérových kriviek. Majme riadiace body v priestore (t.j. v $E^3$) $V_0,V_1,\dots,V_n$ ako 
u klasických Beziérových kriviek. Navyše pridáme každému bodu pridáme váhu $w_i$, reálne (najlepšie kladné) číslo.
Potom \emph{riacionálna} Beziérova krivka je 
\begin{equation}
B^n(t) = \frac{\sum_{k=0}^n B^n_k(t) w_i V_i}{\sum_{k=0}^n B^n_k(t) w_i}, \qquad \text{pre } t \in [0,1]
\end{equation}
Racionálne sa volajú preto, že sú podielom dvoch 
polynómov.\footnote{Presnejšie každá súradnica zvlášť je podielom dvoch polynómov.}

Nech riadiace vrcholy povôdné riadiace vrcholy $V_i$ mali súradnice $V_i=[x_i,y_i,z_i]$.
Uvažujeme klasickú Beziérovu 4D krivku s riadiacimi vrchlolmi $U_i=[w_ix_i,w_iy_i,w_iz_i,w_i]$.
(Toto možno chápať aj ako homogénne súradnice pôvodných bodov, lebo $[w_ix_i,w_iy_i,w_iz_i,w_i] \equiv [x_i,y_i,z_i,1]$.)
\begin{equation}
B^n(t) = \sum_{k=0}^n B^n_k(t) U_i = \sum_{k=0}^n B^n_k(t) 
\begin{bmatrix}w_i x_i \\ w_i y_i \\ w_i z_i \\ w_i\end{bmatrix}	
=
 \begin{bmatrix} 
 \sum_{k=0}^n B^n_k(t) w_i x_i \\
 \sum_{k=0}^n B^n_k(t) w_i y_i \\
 \sum_{k=0}^n B^n_k(t) w_i z_i \\
 \sum_{k=0}^n B^n_k(t) w_i \\
 \end{bmatrix} 
\end{equation}
Potom táto krivka chápaná ako 3D krivka je racionálnu Beziérou krivkou
\begin{equation}
B^n(t) =
 \begin{bmatrix} 
 \sum_{k=0}^n B^n_k(t) w_i x_i \\
 \sum_{k=0}^n B^n_k(t) w_i y_i \\
 \sum_{k=0}^n B^n_k(t) w_i z_i \\
 \sum_{k=0}^n B^n_k(t) w_i \\
 \end{bmatrix} 
\equiv 
 \frac{1}{\sum_{k=0}^n B^n_k(t) w_i}
 \begin{bmatrix} 
 \sum_{k=0}^n B^n_k(t) w_i x_i \\
 \sum_{k=0}^n B^n_k(t) w_i y_i \\
 \sum_{k=0}^n B^n_k(t) w_i z_i \\
 1
 \end{bmatrix} 
= \frac{\sum_{k=0}^n B^n_k(t) w_i V_i}{\sum_{k=0}^n B^n_k(t) w_i}
\end{equation}

Inak sa na racionálnu krivku možno dívať ako na stredový priemet (so stredom v počiatku) do nadroviny $w=1$
($w$ je štvrtá súradnica v 4D). Prakticky (napr. v OpenGL) sa to ráta tak, že tú krivku rátame 4D ako bežnú
Beziérovu krivku a nakoniec to predelíme štvrtou súradnicou. 
(Alebo ani nepredelíme a rovno pošleme do OpenGL v homogénnych súradniciach.)

Defacto každá krivka alebo aj plocha, ktorá je definovaná len pomocou riadiacich vrcholov existuje aj racionálnej verzii.
Toto platí minimálne pre Beziérove krivky a plochy (vrátane Beziérovho trojuholníka), B-splajnov a B-splajnových plôch.
Idea a vzorce je vždy tá istá ako tu, takže sa tým nebudem viac špeciálne zaoberať.

\section{B-splajny}
\subsection{B-splajnové bázické funkcie}
B-splajnové bázické funkcie sú pre B-splajny asi to, čo pre Beziérove krivky
Bernsteinove polynómy. Sú ale o dosť komplikovanejšie, a hlavne nie sú to polynómy ale zlepeniny polynómov.

Najprv máme nejaké prirodzené číslo $m$ a neklesajúcucu postupnosť $m+1$ reálnych čísel $t_0 \le t_1 \le
\dots \le t_m$. Táto postupnosť sa nazýva uzlový vektor (dĺžky $m$). Ak sa nejaké číslo vyskytuje v postupnosti viackrát
hovoríme, že uzol je násobný, počet výskytov uzla voláme jeho násobnosťou.
Na tomto uzlovom vektore definujeme $i$-tu \emph{B-splajnovú bázickú funkciu} $N^d_k(t)$ stupňa $d$.
Pre stupeň nula je 
\begin{equation}
N^0_k(t) = 
\begin{cases}
1, & t \in [t_k, t_{k+1}) \\
0, & \text{inak} \\
\end{cases}, \qquad \text{pre } 0\le i \le m-1.
\end{equation}
Pre vyššie stupne ich definujeme rekurentne
\begin{equation}
N^d_k(t) = \frac{t-t_k}{t_{k+d}-t_k}N^{d-1}_k(t) + \frac{t_{k+d+1}-t}{t_{k+d+1}-t_{k+1}}N^{d-1}_{k+1}(t),
\end{equation}
 pre  $0\le i \le m-d-1$.
Ak by v definícii v niektorom zlomku v menovateli vyšla nula (kvôli násobnosti uzlov), tak ten zlomok chápeme ako nulový.

Stupňa $d$ je ich $m-d$ a číslujeme ich $B^d_0, B^d_1, \dots, B^d_n$, kde $n=m-d-1$.
Definičným oborom funckií stupňa $d$ je interval $[t_d, t_{m-d}]$.

Tieto funkcie majú kopec zaujímavých vlastností (niektoré sú podobné ako u Bernsteinových polynómov):
\begin{itemize}
\item Sú nezáporné. $N^d_i(t)$ je kladná na intervale $(t_i, t_{d+1})$; tento
interval sa nazýva \emph{nosič} (angl. support).  Sú unimodálne (jednohrbé).
\item Funkcie stupňa $d$ sa na intervale $[t_d,t_{m-d}]$ sa sčítajú na konštatnú jednotku. Teda
\begin{equation}
N^d_0(t) + N^d_1(t) + \dots + N^d_n(t) = \sum_{k=0}^n N^d_k(t) = 1, \qquad \text{pre } t \in [t_d, t_{m-d}].
\end{equation}
\item Sú to čiastkovo polynomické funckie (príslušného stupňa). V neuzlovom bode sú hladké a
v uzlove s násobnosťou $r$ sú spojité rádu $d-r$ (trieda $C^{d-r}$).
\item Tvoria vektorový priestor dimenzie $n+1$.
\end{itemize}

\subsection{Vektorový priestor bázických funckií}
TODO

\subsection{B-splajnové krivky}
Idea je rovnaká ako u Beziérových kriviek, len namiesto Bernsteinových polynómov použijeme B-splajnové bázické funckie.
Teda máme $n+1$ riadiach vrcholov $V_0, V_1, \dots, V_n$ v nejakom Euklidovovskom priestore (rovina alebo priestor),
uzlový vektor dĺžky $m$ a na ňom definované bázické funkcie stupňa $d$, pričom platí
\begin{equation}
m=n+d+1.
\end{equation}
\emph{B-splajnovou krivkou} (skrátene \emph{B-splajnom}) rozumieme krivku
\begin{equation}
N^d(t) = \sum_{k=0}^n V_k N^d_k(t), \qquad \text{pre } t \in [t_d, t_{m-d}].
\end{equation}

Jej základné vlastnosti sú:
\begin{itemize}
\item Lokálne riadenie, teda, keď pohnem riadiacim vrcholom, tak sa zmení naozaj len kúsok krivky.
(TODO: Ktorý kúsok presne.)
\item Silná vlastnosť konvexného obalu, teda kúsok krivky od $[t_i, t_{i+1})$ 
leží v konvexnom obale bodov $V_{i-d}, V_{i-d+1}, \dots, V_i$.
\item O spojitosti platí to, čo pre bázické funkcie.
\end{itemize}

\subsection{De Boorov algoritmus}

Idea je podobná ako u Casteljauovho algoritmu.  
Povedzme, že chceme krivku vyčísliť v bode $t \in [t_i, t_{i+1}]$. 
Vezmeme tie riadiace vrcholy, ktoré majú na tento kúsok vplyv. To sú $V_{i-d}, V_{i_d+1}, \dots, V_i$.
(Je ich $d+1$.) Označíme ich, ako body nultej generácie $V_{i-d}^0, V_{i-d+1}^0, \dots, V_i^0$.
Následne generujeme body ďalších generácií takto:
\begin{equation}
V_k^r = (1-\alpha) V_k^{r-1} + \alpha V_{k+1}^{r-1}, 
\end{equation}
kde 
\begin{equation}
\alpha = .
\end{equation}
TODO

\subsection{Voľba uzlov}
Ak chceme, aby B-splajn začínal v bode $V_0$ a končil v bode $V_n$, tak musíme vhodne zvoliť uzlový vektor.
Menovite prvý a posledný uzol treba zvoliť s násobnosoťou $d$. Zvyšné uzly môžme zvloliť v pravidlených rozostupoch.
Teda napr. pre $m=9,d=3$ (a teda $n=5$) vyzerá taký uzlový vektor napr. 
takto $(0,0,0,1,2,3,4,5,5,5)$.\footnote{Škálovanie a posun sú dovolené.
Takže rovnako dobrý je aj uzlový vektor $(5,5,5,5.1,5.2,5.3,5.4,5.5,5.5,5.5)$. }
(Toto defacto je najbežnejší uzlový vektor.)

Občas chceme dostať uzavretú krivku (teda krivku, ktorá začína a končí v tom istom bode).
TODO

\subsection{B\"ohmov algoritmus vkladania uzla}
TODO

\subsection{Racionálne B-splajny}
Ide o zovšeobecnenie B-splajnových kriviek. Uvažujme všetko tak ako u normálnych B-splajnov, 
ale navyše každému riadiacemu $V_i$ vrcholu pridajme váhu $w_i$. Potom racionálnym B-splajnom je 
\begin{equation}
N^d(t) = \frac{\sum_{k=0}^n N^d_k(t) w_i V_i}{\sum_{k=0}^n N^d_k(t) w_i}
\end{equation}
Občas sa tieto krivky volajú tiež NURBS (Non-Uniform Rational B-Spline).
(Non-Uniform značí to, že uzlový vektor (postupnosť) nie je pravidelný.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%      P L O C H Y       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\part{Plochy}
Plocha je podobne ako plocha, zobrazenie $S:D \to E^3$, kde $D$ je nejaká oblasť (podmnožina) $\mathbb R^2$.
Opäť požadujeme hladkosť a regulárnosť $S(u,v)$. Hladkosť značí, tak ako u kriviek dostatočne (najlepšie nekonečne)
veľa derivácií. Regulárnosť v tomto prípade značí, že prvé parciálne derivácie $\frac{\partial S(u,v)}{\partial u}$
a $\frac{\partial S(u,v)}{\partial v}$ boli (ako vektory) v ľubovoľnom bode krivky lineárne nezávislé.

\section{Beziérove plochy}
Ide o tenzorovo-súčinovú plochu. 
Máme sieť (mriežku) $(m+1) \times (n+1)$ riadiacich vrcholov $V_{i,j}$, ($0 \le i \le m, 0 \le j \le n$).
Potom Bezierova plocha stupňa $m \times n$ je
\begin{equation}
B^{m,n}(u,v) = \sum_{i=0}^m \sum_{j=0}^n V_{i,j} B^m_i(u) B^n_j(v), \qquad \text{pre } u,v \in [0,1].
\end{equation}

Vlastnosti to má naskrze podobné ako Beziérova krivka (konvexný obal, pseudolokálne riadenie.)
Štyri krajné krivky $B^{m,n}(u,0)$, $B^{m,n}(u,1)$, $B^{m,n}(0,v)$ a $B^{m,n}(1,v)$ sú Beziérovými krivkami
určené riadiacimi bodmi $V_{i,0}$, resp. $V_{i,n}$, resp. $V_{0,j}$, resp. $V_{m,j}$.
Vo všeobecnosti smerové $u$-krivky a $v$-krivky sú (nejakými) Beziérovými krivkami. 
Derivácie treba rátať parciálne, zvlášť podľa $u$ a zvlášť podľa $V$.

Existuje dvojrozmerný Casteljaou pre túto plochu.
Pre jednoduduchosť predpokladajme, že platí $m=n$. Idea je tá istá ako v jednorozmernom prípade:
Máme fixné $u,v$. Na začiatku máme štvorcovú sieť $(n+1) \times (n+1)$ pôvodných riadiacich vrcholov
$V^{0,0}_{i,j}$ generácie $0,0$.
V každej ďalšej generácii sa zmenšuje strana štvorca o jedna, až kým nedostaneme jediný vrchol.
\begin{equation}
V^{r,r}_{i,j} = (1-u, u) 
\begin{pmatrix}
V^{r-1,r-1}_{i,j} & V^{r-1,r-1}_{i,j+1} 	\\ 
V^{r-1,r-1}_{i+1,j} & V^{r-1,r-1}_{i+1,j+1} 	\\
\end{pmatrix}
\begin{pmatrix} 1-v \\ v \end{pmatrix},	
\quad 0<r\le n,\ 0 \le i,j \le n-r
\end{equation}
Samozrejme nemusíme mať oba horné indexy (generácie) rovnaké a môžeme rátať všeobecnejšie
\begin{multline}
V^{p,q}_{i,j} = (1-u, u) 
\begin{pmatrix}
V^{p-1,q-1}_{i,j} & V^{p-1,q-1}_{i,j+1} 	\\ 
V^{p-1,q-1}_{i+1,j} & V^{p-1,q-1}_{i+1,j+1} 	\\
\end{pmatrix}
\begin{pmatrix} 1-v \\ v \end{pmatrix},	
\\
\text {pre } 0<p\le m,\ 0<q\le n,\ 0 \le i \le m-p,\ 0\le j \le n-q.
\end{multline}
Dá sa to dokonca voľne zamieňať s jednorozmerným Casteljauom náhodne v
ľuvolnom zo smerov $u,v$ (resp. prvý, druhý index) a meniť tak v jednom kroku len jeden z horných indexov.

Racionálna verzia je o tom istom, len sa vrcholom pridajú váhy $w_{i,j}$
\begin{equation}
B^{m,n}(u,v) = \frac{\sum_{i=0}^m \sum_{j=0}^n w_{i,j}V_{i,j} B^m_i(u) B^n_j(v)}
{\sum_{i=0}^m \sum_{j=0}^n w_{i,j} B^m_i(u) B^n_j(v)}, \qquad \text{pre } u,v \in [0,1].
\end{equation}

\section{Beziérov trojuholník}
Tu je hrozná finta, plocha nebude definovaná nad obĺžnikom, ale nad trojuholíkom. 
Presnejšie ako definičný obor berieme nasledovnú množinu trojíc
\begin{equation}
\{(u,v,w)\ |\ u,v,w \ge 0,\ u+v+w=1 \}.
\end{equation}
Najlepšie si je to predstaviť takto: Máme v rovine trojuholník $A,B,C$, potom každý bod $X$ roviny
vieme napísať ako barycentrickú kombináciu bodov $A,B,C$, teda $X=uA+vB+wC$. Nás bude (za bežných okolností) 
ale trápiť len vnútro trojoholíka $A,B,C$ takže sa obdedzíme len na konvexné kombinácie t.j. $u,v,w\ge0$.

Ďalej máme trojuholníkovú sieť ${n+2 \choose 2}$ riadiacich vrcholov (trocha haluzne indexovanú) $V_{i,j,k}$ ($i,j,k\ge0$, $i+j+k=n$). Potom Beziérov trojuholník stupňa $n$ je
\begin{equation}
B^n(u,v,w) = \sum_{\substack{i+j+k=n \\ i,j,k \ge 0}} \frac{n!}{i!j!k!} u^i v^j w^k V_{i,j,k}.
\end{equation}
Tri krajné krivky sú Beziérovými krivkami príslušných krajných riadiacich vrcholov.

Existuje aj Casteljauov algorimtus pre tento trojuholník. 
Funguje asi takto: Máme nejaké fixné $(u,v,w)$, v ktorom chceme zrátať bod plochy. Máme body nultej generácie
tvoriace trojuholníkovú sieť rádu $n$ (t.j. je ich ${n+2 \choose 2}$). V každom ďalšom kroku sa tento rád zmenší
o jedna podľa vzorca 
\begin{equation}
V^r_{i,j,k} = uV^{r-1}_{i+1,j,k} + vV^{r-1}_{i,j+1,k} + wV^{r-1}_{i,j,k+1}, \qquad \text{pre } i+j+k=n-r,\ i,j,k\ge0.
\end{equation}
Nakoniec bod $V^n_{0,0,0}$ je bodom plochy, t.j. $V^n_{0,0,0} = B^n(u,v,w)$.

Platí tiež (podobne ako pre Beziérove krivky), že Casteljau nám vygeneruje aj nové riadiace vrcholy troch menších
trouholníkov stýkajúcich sa vo vyrátanom bode. Riadiacimi vrcholmi prvého sú body $V^k_{i,j,0}$, druhého $V^j_{i,0,k}$
a tretieho $V^i_{0,j,k}$, pričom $i+j+k=n$, $i,j,k \ge 0$.

O Beziérovom trojohulníku sa dá toho povedať ešte hrozne veľa. 
Napr. o derivácii v ľubovoľnom smere alebo o hladkom spájaní trojuholníkov.

Existuje aj racionálnu verzia, ktorú si iste každý rád domyslí.

\section{B-splajnové plochy}
Zase len trápna tenzoro-súčinová plocha, verná kópia Beziérovej plochy.
\footnote{Trochu tu dochádza abeceda.}
Máme dva uzlové vektory $u_0 \le u_1 \le \dots u_p$ (pre smer $u$) a $v_0 \le v_1 \le \dots v_q$ (pre smer $v$)
Máme sieť (mriežku) $(m+1) \times (n+1)$ riadiacich vrcholov $V_{i,j}$, ($0 \le i \le m, 0 \le j \le n$).
A stupne plochy $r,s$. Čísla $p,m,r$ a $q,n,s$ spĺňajú rovnosti
\begin{eqnarray}
p&=&m+r+1,\\
q&=&n+s+1.
\end{eqnarray}
Potom B-splajnová plocha stupňa $r \times s$ je
\begin{equation}
N^{r,s}(u,v) = \sum_{i=0}^m \sum_{j=0}^n V_{i,j} N^r_i(u) N^s_j(v), 
\quad (u,v) \in [u_r,u_{p-r}] \times [v_s,v_{q-s}].
\end{equation}
Dvojrozmerný De Boorov algoritmus som nikde nevidel a ani nesnažil vymyslieť, tak sa môžte posnažiť sami.
Racionálna verzia je podobná, vrcholom len pridáte váhy $w_{i,j}$
\begin{equation}
N^{r,s}(u,v) = \frac{\sum_{i=0}^m \sum_{j=0}^n w_{i,j} V_{i,j} N^r_i(u) N^s_j(v)}
{\sum_{i=0}^m \sum_{j=0}^n w_{i,j} N^r_i(u) N^s_j(v)}.
\end{equation}

\section{Priamkové plochy}

\section{Jendoduchá Coonsova záplata} 

Máme štyri krivky v priestore $X(u,0)$, $X(u,1)$, $X(0,v)$ a
$X(1,v)$.\footnote{Označenie je na prvý pohľad dosť zavádzajúce a zmätočné, ale takto sa to bežne všade
píše.} Tieto štyri kryvky musia byť také, aby v poradí prvá, tretia, druhá,
štvrtá tvorili uzavretú krivku.\footnote{Naše označenie si vlastne vynucuje.} Našou úlohou je zostrojiť nejakú (rozumnú)
plochu $X(u,v), X:[0,1] \times [0,1] \to E^3$, ktorej by tieto štyri krivky
boli krajnými krivkami.

Začneme najprv jednoducho, vezmeme priamkovú plochu určenú prvou a druhou krivkou:
$$X_C(u,v) = (1-v)X(u,0) + vX(u,1).$$
Podobne možno zobrať priamkovú plochu určenú treťou a štvrtou krivkou:
$$X_D(u,v) = (1-u)X(0,v) + uX(1,v).$$
Ideálne by bolo ich nejako skombinovať. Na to, ako to urobiť, prišiel pán Coons. 
Myšlienka je taká, že ich ščítame a od toho odpočítame bilenárny interpolant štyroch rohov $X(0,0)$, $X(0,1)$,
$X(1,0)$ a $X(1,1)$. Ten bilineárny interpolant $X_{CD}$ vyzerá takto:
$$X_{CD}(u,v) = (1-u,u) \begin{pmatrix} X(0,0) & X(0,1) \\ X(1,0) & X(1,1) \end{pmatrix} 
\begin{pmatrix} 1-v \\ v \end{pmatrix}.
$$
Výsledná Coonsova plocha je potom 
\begin{equation}
X(u,v) = X_C(u,v) + X_D(u,v) - X_{CD}(u,v).
\end{equation}

\section{Bikubická Coonsova záplata}

Situácia je podobná ako u jednoduchej Coonsovej záplate.  Navyše však máme
predpísané aj priečne derivácie (tzv. \emph{stuhy}) pozdĺž hrničných kriviek.
Teda okrem kriviek $X(u,0)$, $X(u,1)$, $X(0,v)$ a $X(1,v)$ sú dané
aj derivácie v priečnom smere na ne $X_v(u,0)$, $X_v(u,1)$, $X_u(0,v)$ a $X_u(1,v)$.

Idea je podobná ako pri jednoduchej záplate. Najpr zostrojíme pomocou Hermitovej krivky
plochu $X_C(u,v)$, ktorá interpoluje prvú a druhú krivku a má priečne derivácie v smere $v$
na krajoch $X_v(u,0)$, $X_v(u,1)$
$$X_C(u,v) = H^3_0(v) X(u,0) + H^3_1(v)X_v(u,0) + H^3_2(v)X_v(u,1) + H^3_3(v)X(u,1).$$
Podobne v pre druhý smer
$$X_D(u,v) = H^3_0(u) X(0,v) + H^3_1(u)X_u(0,v) + H^3_2(u)X_u(1,v) + H^3_3(u)X(1,v).$$
Nakoniec ešte odčítame bikubický interpolant $X_{CD}(u,v)$:
$$X_{CD}(u,v) = 
(H^3_0(u),H^3_1(u),H^3_2(u),H^3_3(u))
\begin{pmatrix}
X(0,0) 		& X_v(0,0) 	& X_v(0,1) 	& X(0,1) 	\\
X_u(0,0)	& X_{uv}(0,0)	& X_{uv}(0,1) 	& X_u(0,1) 	\\
X_u(1,0)	& X_{uv}(1,0)  	& X_{uv}(1,1)	& X_u(1,1) 	\\
X(1,0) 		& X_v(1,0) 	&  X_v(1,1) 	& X(1,1)	\\
\end{pmatrix}
\begin{pmatrix}
H^3_0(v) \\ H^3_1(v) \\ H^3_2(v) \\ H^3_3(v)
\end{pmatrix}
$$
Výsledná \emph{bikubická Coonsova záplata} bude
\begin{equation}
X(u,v) = X_C(u,v) + X_D(u,v) - X_{CD}(u,v).
\end{equation}


\end{document}