# 5. Křivky a povrchy (90%)
###### tags: `grafika`, `PB009`, `PA010`

:::warning
* Implicitní a parametrické reprezentace
* Interpolace a aproximace
* Bézierovy křivky, B-spline křivky, NURBS, Coonsovy křivky a pláty
* Cn, Gn spojitost, podmínky spojitosti pro po částech definované funkce
* **Povrchy tvořené rekurzivním dělením polygonů** *Niečo tam je ale nie je to dokonalé*
:::

## Implicitné a parametrické vyjadrenie
### Krivky
Krivky sú obyčajne v počítači reprezentované ako sústava parametrov nejakej rovnice, ktorá je následne generatívne zobrazovaná. Toto vyjadrenie môže byť v podstate trojaké – *explicitné, implicitné a parametrické*.
:::success

**Explicitne** zadaná krivka je vyjadrená **funkciou** $y = f(x)$ a býva orientovaná v **smere** rastúceho $x$. Takto však môžu byť vyjadrené **len** krivky, ktoré sú **zároveň funkciami**, teda jednej hodnote z definičného oboru $x$ zodpovedná jedna funkčná hodnota $y$.

**Implicitne** zadaná krivka je vyjadrená **rovnicou** $F(x,y) = 0$. Táto reprezentácia je pomerne **ťažko zobraziteľná**, pretože neumožňuje postupný výpočet krivky. (Tieto krivky sú základom tzv. level set metód v spracovaní obrazu)

**Parametrický** tvar krivky ju chápe ako **dráhu pohybúceho sa bodu**, ktorého **súradnice sú funkciami parametru** $t$, teda času, a vyjadruje sa **rovnicami** $x = x(t)$, $y = y(t)$ a $z = z(t)$. Čas je z intervalu $t \in <t_{min}, t_{max}>$, najčastejšie volený v rozsahu $t \in <0, 1>$.
* Výhodou parametrického zápisu krivky je možnosť **zachytiť priebeh**, kedy krivka prechádza viackrát v rôznych časových okamihoch rovnakými bodmi v priestore (môže sa skrížiť, uzavieť a podobne).
* Uvedenými parametrickými funkciami je určená buď **bodová rovnica krivky** $Q(t) = [x(t), y(t), z(t)]$, alebo **vektorová rovnica** $\vec{q}(t) = (x(t), y(t), z(t))$.
:::

> **Dotykový vektor** (tečný vektor) v bode $Q(t_{0})$ je určený **deriváciami parametricky vyjadrenej krivky** po zložkách v tvare $\vec{q}(t_{0}) = (x'(t_{0}), y'(t_{0}), z'(t_{0})) = \left(\frac{dx(t_{0})}{dt}, \frac{dy(t_{0})}{dt}, \frac{dz(t_{0})}{dt}\right)$.
> **Rovnica dotyčnice** (tečny) v danom bode má tvar $P(u) = Q(t_{0}) + u.\vec{q'}(t_{0})$. Vektor $\vec{q'}(t)$ sa nazýva **smerový vektor priamky**.
> **Parametrická reprezentácia ľahko vyjadruje dotyčnice ku krivke, čo sa využíva pri skladaní kriviek** (viac v časti o spojitosti kriviek).

#### **Parametrické krivky**
> [color=#449750] <span style="color: black"> Základným druhom parametrických kriviek používaných v počítačovej grafike sú krivky **polynomiálne**.
>
>* <span style="color: black"> $Q_{n}(t) = a_{0} + a_{1}(t) + ... + a_{n}(t)^{n}$
>
> <span style="color: black"> Výhodou je, že polynomiálne krivky vieme ľahko vyčísliť a sú jednoducho diferencovateľné. Z nich často skladáme krivky po častiach polynomiálne, ktorých segmenty sú polynomiálnymi krivkami.
Najčastejšie používame **krivky 3. stupňa** – **kubiky**. *(Pri nich vieme napríklad zaručiť $C^{2}$ spojitosť.)*
>
> <span style="color: black"> Parametricky zadaná kubika má tvar
$$x(t) = a_{x}t^{3} + b_{x}t^{2} + c_{x}t + d_{x},
\\y(t) = a_{y}t^{3} + b_{y}t^{2} + c_{y}t + d_{y},
\\z(t) = a_{z}t^{3} + b_{z}t^{2} + c_{z}t + d_{z}$$
> <span style="color: black"> čo môžeme v maticovom tvare zapísať ako:
> <span style="color: black"> $$Q(t) = \mathbf{T \cdot C} = \begin{bmatrix}t^{3} & t^2 & t & 1\end{bmatrix} \cdot
\begin{bmatrix}
a_x & a_y & a_z \\
b_x & b_y & b_z \\
c_x & c_y & c_z \\
d_x & d_y & d_z \\
\end{bmatrix}
$$
> a jej dotykový vektor $\vec{q'}(t)$ získame deriváciou vektoru $\mathbf{T}$, teda $$\vec{q'}(t) = {d \over dt}\mathbf{T}.\mathbf{C} = \begin{bmatrix}3t^{2} & 2t & 1 & 0\end{bmatrix}\cdot\mathbf{C}$$
V prípade kubíku môžeme maticu rozpísať do súčinu $\mathbf{C} = \mathbf{M} \cdot \mathbf{G}$, kde $\mathbf{M}$ je bázová matica a $\mathbf{G}$ je vektor geometrických podmienok, ktorý obsahuje konkrétne parametre ovplyvňujúce tvar krviky (riadiace body a dotykové vektory). Súčin $\mathbf{T}\cdot \mathbf{M}$ potom definuje polynomiálnu bázu (skupinu polynómov), ktorá je spoločná pre všetky krivky určitého typu. Tieto polynómy spolu s násobenými geometrickými podmienkami sa uplatňujú ako premenlivé váhy riadené parametrom $t$. Hodnota parametru potom určuje uplatnenie podmienky buď na začiatku krivky, vo vnútornom priebehu, alebo má najväčší vplyv na koncovú časť.
> <span style="color: black"> $$Q(t) = \mathbf{T \cdot M \cdot G} = \begin{bmatrix}t^{3} & t^2 & t & 1\end{bmatrix} \cdot
\begin{bmatrix}
m_{11} & m_{12} & m_{13} & m_{14} \\
m_{21} & m_{22} & m_{23} & m_{24} \\
m_{31} & m_{32} & m_{33} & m_{34} \\
m_{41} & m_{42} & m_{43} & m_{44} \\
\end{bmatrix} \cdot
\begin{bmatrix}
G_1\\
G_2 \\
G_3\\
G_4\\
\end{bmatrix}
$$
>
> <span style="color: black"> Modelovanie týchto kriviek prebieha pomocou definovania tzv. riadiacich bodov. Existujú **2 spôsoby interpretácie** riadiacich bodov – **interpolácia** a **aproximácia**. Krivka generovaná pri interpolácií prebieha danými bodmi, avšak pri aproximácií je tvar krivky riadiacimi bodmi len určený, prechádzať nimi ale nemusí.

### Povrchy
Vyjadrenie plochy môže byť podobne ako u krivky len s doplnením ďalšej dimenzie – *explicitné, implicitné a parametrické*.
:::success
**Explicitne** zadaná plocha je vyjadrená **funkciou** $z = f(x,y)$.

**Implicitne** zadaná plocha je vyjadrená **rovnicou** $F(x,y,z) = 0$ (podrobnejšie v časti o implicitných plochách).

**Parametrickým** vyjaderním plochy $Q(u,v)$ je **bodová rovnica** dvoch parametrov $u$ a $v$ nadobúdajúcich hodnoty z intervalu $<0,1>$, ktorá je zadaná ako $Q(u,v) = [x(u,v), y(u,v), z(u,v)]$.
:::

> **Dotykový vektor** (tečný vektor) $\vec{q_{u}}(u,v)$ v smere parametru u k ploche Q(u,v) a dotykový vektor $\vec{q_{v}}(u,v)$ v smere parametru v sú určené vzťahmi
$$\vec{q_{u}}(u,v) = \frac{\partial Q(u,v)}{\partial u} = \left(\frac{\partial x(u,v)}{\partial u}, \frac{\partial y(u,v)}{\partial u}, {\partial z(u,v) \over \partial u}\right) \\
\vec{q_{v}}(u,v) = \frac{\partial Q(u,v)}{\partial v} = \left(\frac{\partial x(u,v)}{\partial v}, \frac{\partial y(u,v)}{\partial v}, {\partial z(u,v) \over \partial v}\right)$$
>
>Rovnica **dotykovej roviny** (tečné roviny) je určené ako $$T(r,s) = Q(u,v) + r.\vec{q_{u}} + s.\vec{q_{v}}; \ r,s \in R$$
>
> **Normálu** (kolmicu) k ploche v bode $Q$ určíme ako normalizovaný vektorový súčin dotykových vektorov, teda $$\vec{n} = \frac{\vec{q_{u}} \times \vec{q_{v}}}{|\vec{q_{u}} \times \vec{q_{v}}|}$$

### Implicitné povrchy
Implicitné vyjadrenie plochy tvorí alternatívu k povrchu definovanom pomocou polygónov alebo parametrických plátov. Výhodou je napríklad kompaktnejšia reprezentácia či jednoduchšie sledovanie lúča (paprsku). Výpočet sledovania lúča je ale časovo náročný, rovnako je náročné aj zobrazovanie plochy v reálnom čase. Väčšina zobrazovacích metód v konečom dôsledku aj tak prevádza implicitné plochy na parametrické vyjadrenie alebo rovinné plošky, tzv. **polygonizácia implicitných plôch.**

Funkcia $f(x,y,z)$ priraďuje každému bodu v priestore nejakú skalárnu hodnotu a definuje teda skalárne pole. Nami hľadaný objekt je **izoplocha**, teda množina bodov s rovnakou funkčnou hodnotou. Ak $f = 0$, bod leží na povrchu plochy. Ak $f < 0$ alebo $f > 0$, možeme hovoriť, že bod leží vo vnútri (alebo vonku) objektu ohraničeného plochou, no ktorá hodnota označuje čo, už závisí na konkrétnom kontexte.

Normály povrchu sú obvykle určené gradientom príslušnej funkcie, teda $\nabla f(x,y,z) = \left(\frac{df}{dx}, \frac{df}{dy}, \frac{df}{dz}\right)$.

Medzi implicitné povrchy zaraďujeme **blobby** objekty (kvapky) od J. Blinna, **metaballs** či **soft objects** od Wyvilla.

Príkladom implicitnej plochy (množiny bodov P v trojrozmernom priestore) je guľová plocha zadaná implicitnou rovnicou $Q(P) = x^{2} + y^{2} + z^{2} = r^{2}$.

Implicitné plochy môžu byť reprezentované aj takzvanými dištančnými povrchmi (viď zoznam na obrázku).
___
## Interpolace a aproximace
### Interpolace - Definícia
V geometrii znamená interpolace prokládání daných (změřených) bodů křivkou, konstrukce křivky, která danými body prochází.

:::success
Mějme funkci $f(x)$, jejíž hodnota je známa v bodech $f(x_{0}), {\displaystyle f(x_{1})}, ... ,{\displaystyle f(x_{n})}$. Interpolace znamená nalezení funkční hodnoty $f(x)$ pokud platí, že $x_0 < x < x_{n}$.
:::

### Aproximace - Definícia
Aproximace (přiblížení, odhad) je nepřesné, ale věrné vyjádření nějaké entity, nejčastěji čísla nebo funkce. K využití aproximace se přistupuje tehdy, když pro analytické řešení není dostatek informací, nebo to je příliš náročné na provedení. I v případě, kdy je přesné vyjádření známé, může aproximace být užitečná — poskytnutím dostatečně přesného řešení a zároveň podstatným snížením složitosti problému.

> Plochy sa zadávajú riadiacimi bodmi a bázovými funkciami. Väčšinou sa používajú plochy aproximačné. Interpolácia vo viac ako dvoch dimenziách je náročná a vyžaduje rozsiahle výpočty. Interpolačná plocha $P_{ij}$ má $(m + 1) \times (n + 1)$ bodov. Interpoláciou vektorovým polynómom je možné plochu zapísať ako $\vec{P}(u,v) = \sum_{i=0}^{m} \sum_{j=0}^{n} b_{ij} \cdot u^{i} \cdot v^{j}$.
>
> Na aproximačné vyjadrenie plôch sa používajú tzv. 12-vektorový Hermitovský plát alebo 16-vektorový (obsahuje navyše 4 skrutové vektory v každom rohu plátu).

---
### Interpolačné Krivky
Základným spôsobom ako **interpolovať funkciu** zadanú **v diskrétnych bodoch** je použiť **Langrangeov interpolačný polynóm**.

Lagrangeovy polynomy:
$$L_i^m(t) = {\Pi_{j=0...m; \ j \ne i}(t-t_j) \over \Pi_{j=0...m; \ j \ne i}(t_i-t_j)}, \ i=1...m$$

> Věta: Dáno m+1 bodú $P_0,P_1,...,P_m \in \mathcal R^d$, a parametry $t_i \in \mathcal R, t_i < t_{i+1}$, $\ i = 0, ..., m-1$
>
> Polynom $P(t) = \sum_{i=0}^m P_iL_i^m (t)$ jednoznačne interpoluje danú množinu bodov $P_i$

Nevýhodou je nutnosť prepočítať všetky bázické polynómy, ak sa rozhodneme pridať ďalší uzlový bod.

> [color=#7D2FAA] **Príklad** výpočtu Lagrangeovho polynómu 2. stupňa.
>
> 

**Hermite**
Najznámejšie interpolačné krivy používané v počítačovej grafike sú **Hermitovské krivky**, hlavne Hermitovské kubiky (tiež aj Fergusonove kubiky). Sú určené dvoma riediacimi bodmi $P_{0}, P_{1}$ a dvomi dotykovými vektormi $\vec{p'}_{0}, \vec{p'}_{1}$. Body určujú začiatočný a koncový bod krivky, smer a veľkosť vektorov jej vyklenutie. Čím je vektor väčší, tým viac sa k nemu krivka primkýna. Ak sú obidva vektory nulové, jedná sa vlastne o úsečku.

**Kubické Hermitovské polynómy**
Predpis pre výpočet Hermitovskej kubiky má tvar
$$Q(t) = \begin{bmatrix}t^{3} & t^{2} & t & 1\end{bmatrix}.\begin{bmatrix}2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0\end{bmatrix}.\begin{bmatrix}P_{0} \\ P_{1} \\ \vec{p'}_{0} \\ \vec{p'}_{1}\end{bmatrix} = \\ = P_{0}.F_{1}(t) + P_{1}.F_{2}(t) + \vec{p'}_{0}.F_{3}(t) + \vec{p'}_{1}.F_{4}(t),$$
kde dostávame tzv. kubické **Hermitovské polynómy** (Hermitovské polynómy 3. stupňa)
$F_{1}(t) = 2t^{3} - 3t^{2} + 1$ (červený),
$F_{2}(t) = -2t^{3} + 3t^{2}$ (modrý),
$F_{3}(t) = t^{3} - 2t^{2} + t$ (zelený),
$F_{4}(t) = t^{3} - t^{2}$ (cyan).


Výhoda týchto kubík sa prejavuje pri ich nadväzovaní, keďže dotykové vektory v koncových bodoch sú priamo súčasťou definície. Napr. spojitosť $C^{1}$ je zaručená totožnosťou koncových bodov a identitou dotykových vektorov v týchto bodoch či spojitosť $G^{1}$ docielime lineárnou závislosťou dotykových vektorov (viď spojitosť kriviek). Hermitovské kubiky sú aj základom animačných kriviek Kochanek-Bartels.

---
### Aproximačné Krivky
**Béziér**

Bézierove krivky sa používajú častejšie na modelovanie v dvoch rozmeroch, napríklad pri definícii fontov. Bézierove krivky $n$-tého stupňa sú určené $n + 1$ bodmi riadiaceho polynómu $P_{i}$. Medzi vlastnosti patrí, že zmenou polohy jedného riadiaceho bodu dôjde k zmene tvaru celej krivky. Preto sa krivky často delia na segmenty nižšieho stupňa (napr. kubiky), ktoré sa postupne naväzujú.
$$Q(t) = \sum_{i=0}^{n} P_{i}B_{i}^{n}(t)$$
Základom Bézierových kriviek sú **Bernsteinove polynómy** $n$-tého stupňa.

Medzi **vlastnosti** Bernsteinovych polynómov patrí
* **nezápornosť** (1)
* **súčet váh vždy 1** (3), teda výsledná krivky bude ležať v konvexnom obale bodov riadiaceho polynómu.
* **Rekurentná definícia** (2) vychádza z lineárnej kombinácie polynómov nižšieho stupňa.

Na konštrukciu Bézierovej krivky sa používa rekurzívny **algoritmus deCasteljau**. Vstupom algoritmu sú riadiace body polygónu. Výstupom je bod krivky v určitom čase $t$. Na druhom obrázku vidíme príklad výpočtu a schému výpočtu bodu Bézierovej kubiky v čase $t = {2\over3}$.


**Bézierova kubika** je určená 4 bodmi $P_{0}, P_{1}, P_{2}$ a $P_{3}$ (zápis kubiky $P(t)$ vidíme na druhom obrázku). Popisujú ju 4 Bernsteinove polynómy 3. stupňa (vidíme ich graficky znázornené na obrázku s vlastnosťami Bernsteinových polynómov). Zaujímavé sú dotykové vektory $\vec{p'}(0) = 3(P_{1} - P_{0})$ a $\vec{p'}(1) = 3(P_{3} - P_{2})$. Z tohto vzťahu pre dotykové vektory je totiž zrejmý jednoduchý a priamočiary prevod medzi Bézierovou kubikou a kubikou v Hermitovskej reprezentácii.


**deCasteljau a beziérova kubika**

Zhrnutie deCasteljau algoritmu

#### **B-spline, Coons**

Prirodzený spline je po častiach polynomiálna krivka, ktorá interpoluje svoje riadiace body. Prirodzený kubický spline sa skladá z polynomiálnych kriviek 3. stupňa a vo svojich uzloch je $C^{2}$ spojitý.

V počítačovej grafike sa najčastejšie používa ale **B-spline**, ktorý nie je prirodzený (interpolačný), ale jedná sa o **krivku aproximačnú**. Poznáme dva základné typy – uniformný neracionálny a neuniformný racionálny.

**Kubické Coonsove polynómy**
Uniformný neracionálný B-splajn nazývame tiež **Coonsova kubika**.
* **Vlastnosti Cooonsovych kubík**
Je určená 4 riadiacimi bodmi $P_{0}, P_{1}, P_{2}$ a $P_{3}$. Priebeh bázových polynómov Coonsových kubík môžeme vidieť na obrázku.
Segment takejto krivky teda na rozdiel od Bézierových kriviek neprechádza krajnými bodmi svojho riadiaceho polygónu.
Dosedením $t = 0$ do maticového zápisu (vidíme ho na obrázku) zistíme, že krivka začína v bode ležiacom v jednej tretine ťažnice pri $P_{1}$ trojuholníka určeného prvými 3 bodmi (teda $P_{0}, P_{1}$ a $P_{2}$). Takisto aj koncový bod krivky (na obrázku je krivka zaznačená ako segment $Q_{3}$) v čase $t = 1$ leží v tretine ťažnice pri $P_{2}$ trojuholníka určeného bodmi $P_{1}, P_{2}$ a $P_{3}$.

Coonsov B-spline vzniká naväzovaním Coonsových kubík, je teda určená 4 a viacerými bodmi $(n \geq 4)$. Skladá sa potom z $n - 3$ segmentov. Každý segment $Q_{i}$ je určený bodmi $P_{i-3}, P_{i-2}, P_{i-1}$ a $P_{i}$. Koncový bod jedného segmentu a ziačiatočný bod ďalšieho segmentu majú rovnaké prvé a druhé derivácie, teda Coonsove krivky sú v uzloch $C^{2}$ spojité.


Medzi dôležité **vlastnosti B-spline kriviek** patrí invariancia (**nemennosť**) voči **otočeniu, posunutiu a zmene mierky**. B-spline leží celý v konvexnom obale určenej jeho riadiacimi bodmi. Zmenou polohy niektorého z riadiacich bodov sa zmení len tá časť krivky, ktorá je týmto bodom určená. Ak posunieme bod $P_{i}$, zmení sa tvar štyroch segmentov $Q_{i}, Q_{i+1}, Q_{i+2}$ a $Q_{i+3}$.

#### NURBS
**Neuniformné racionálne B-spline krivky** sú zovšeobecnením vyššie uvedených B-spline kriviek. Neuniformné sú ale preto, lebo vzdialenosť uzlov v zmysle parametru t nemusí byť konštantná. Racionálne znamená, že body sú reprezentované svojimi homogénnymi súradnicami. Krivka NURBS je určená minimálne 4 bodmi $P_{0},..., P_{n}$ riadiaceho polygónu, rádom $k$ (kde najvyšší stupeň polynómu je $k - 1$) a uzlovým vektorom ($t_{0},..., t_{n+k}$), ktorý je tvorený postupnosťou neklesajúcich reálnych čísel – uzlových hodnôt.

V zápise **NURBS** krivky je $w_{i}$ váha i-tého bodu riadiaceho polygónu a $B_{i,k}(t)$ sú normalizované B-spline bázové funkcie. Pre váhu $w = 0$ krivku stredný riadiaci bod neovplyvňuje (je z nej úsečka), váhe $w = 1$ zodpovedá prípad neracionálnej krivky. So zvyšujúcou váhou sa krivka k riadiacemu bodu stále viac primkýna. Pri $w = \infty$ krivka bodom prechádza a dochádza tak k strate spojitosti. Podmienka nezápornosti váh zaručuje umiestnenie krivky v konvexnom obale.

**NURBS B-splajny (wi=1,T={0,1,2,..})**

Podobne ako u Bézierových kriviek a Bernsteinových polynómov majú aj NURBS polynómy analogické vlastnosti ako nezápornosť či to, že výsledná krivka bude ležať v konvexnomo obale bodov riadiaceho polynómu. Rekurentná definícia vychádza z lineárnej kombinácie dvoch polynómov nižších stupňov. Tento rekurentný vzťah je základom Cox-deBoorovho algoritmu na výpočet bodov NURBS krivky, ktorý je zovšeobecnením algoritmu deCasteljau pre spline krivky s neuniformnou parametrizáciou.

**DeBoorův alg. – vyčíslení NURBS **

Základom kriviek NURBS je to, že umožňujú presne definovať kuželosečky a to za pomoci spomínaných váhových koeficientov. Medzi vlastnosti kriviek ďalej patrí invariancia voči transformáciam a voči rovnobežnému stredovému premietaniu.

**Kuželosečka pomocou NURBS**

**Kružnica zo 7 bodov**

---
### Interpolačné a parametrické povrchy
Plochy sa zadávajú riadiacimi bodmi a bázovými funkciami. **Väčšinou sa používajú plochy aproximačné**. Interpolácia vo viac ako dvoch dimenziách je náročná a vyžaduje rozsiahle výpočty. Interpolačná plocha $P_{ij}$ má $(m + 1) \times (n + 1)$ bodov. Interpoláciou vektorovým polynómom je možné plochu zapísať ako $\vec{P}(u,v) = \sum_{i=0}^{m} \sum_{j=0}^{n} b_{ij} \cdot u^{i}\cdot v^{j}$

Na aproximačné vyjadrenie plôch sa používajú tzv. 12-vektorový Hermitovský plát alebo 16-vektorový (obsahuje navyše 4 skrutové vektory v každom rohu plátu).

### Plochy zadané okrajom - Interpolačné


**Riešenie sústavy rovníc**

Plochy môžu byť zadané aj pomocou všetkých kriviek určujúcich okraj, napr. 4 v prípade štvoruholníkového plátu.

**Bilineárna Coonsova plocha** je jednoznačne určená štyrmi krivkami $P(u,0), P(u,1), P(0,v)$ a $P(1,v)$, ktoré musia tvoriť uzavretý okraj budúceho plátu.
Rovnica, ktorá určuje bilineárnu **Coonsovu plochu** sa dá zjednodušene zapísať v tvare $[1-u,-1,u].\mathbf{C}\cdot [1-v,-1,v]^{T} = 0$, kde bod uprostred matice $\mathbf{C}$ je hľadaným riešením tejto implicitnej rovnice. Na výpočet bilineárnej plochy však slúži explicitné vyjadrenie tejto rovnice, ktoré môžeme vidieť na obrázku spolu s grafickým znázornením výpočtu. Zásadným problémom plochy je, že zo zadaného okraja nie je možné jednoducho vyjadriť priečne dotykové vektory a teda nie je ľahké vytvoriť hladké spojenie dvoch takýchto plátov.


**Bikubická plocha** je rovnako určená štyrmi krivkami, ale popísaná vzťahom $[F_{1}(u),-1,F_{2}(u)].\mathbf{C}.[F_{1}(v),-1,F_{2}(v)]^{T} = 0$, kde dané funkcie predstavujú **Hermitovské polynómy:** $F_{1}(t) = 2t^{3} - 3t^{2} + 1$ a $F_{2}(t) = -2t^{3} + 3t^{2}$. Pre rovnaké dôvody ako v predchádzajúcom prípade, ani tieto plochy sa nepoužívajú na plátovanie so spojitou prvou deriváciou.

Až **všeobecná bikubická plocha** umožňuje hladké naväzovanie plátov, keďže je pri nej potrebné zadávať aj dotykové vektory podľa okraja. Okrem 4 spomínaných kriviek ju preto určujú aj priečne vektory pozdĺž okrajov ==$\vec{p_{v}}(u,0), \ \vec{p_{v}}(u,1), \ \vec{p_{u}}(0,v)$ a $\vec{p_{u}}(1,v)$==. Ďalej je tiež určená uzlami v jednotlivých rohoch, teda vektormi $\vec{t}(0,0), \ \vec{t}(0,1), \ \vec{t}(1,0)$ a $\vec{t}(1,1)$.
Vzťah pre všeobecnú bikubickú plochu je rozšírený o ďalšie dva Hermitovské polýnómy tretieho stupňa $F_{3}(t) = t^{3} - 2t^{2} + t, \ F_{4}(t) = t^{3} - t^{2}$ a implicitná rovnica plochy má tvar $[F_{3}(u),F_{1}(u),-1,F_{2}(u),F_{4}(u)]\cdot \mathbf{C} \cdot [F_{3}(v),F_{1}(v),-1,F_{2}(v),F_{4}(v)]^{T} = 0$.

### Aproximačné povrchy (plochy)

**Bézierove plochy**

Bézierove plochy používajú niektoré modelovacie systémy k reprezentácii povrchu telies, pretože sú ľahko diferencovateľné, jednoducho sa modelujú a tiež je pomerne ľahko môžné vypočítať priesečník s lúčom. Tieto plochy sú vlastne špeciálnym prípadom zložitejšej reprezentácie povrchov pomocou NURBS.

Na obrázku vidíme definíciu Bézierovej plochy, kde bázové funkcie $B_{i}^{m}$ a $B_{j}^{n}$ predstavujú Bernsteinove polynómy $m$-tého (resp. $n$-tého) stupňa.


Bézierova plocha pri zmene jedného riadiaceho bodu zmení celý svoj tvar. Táto vlastnosť je nevýhodná, a preto sa plochy plátujú. Pre napojenie plátov so spojitosťou nultého stupňa musíme zabezpečiť stotožnenie riadiacich bodov, ktoré určujú príslušnú stranu. Na obrázku vidíme príklad napojenia s geometrickou spojitosťou prvého stupňa $(G^{1})$, ktorá vzniká vtedy, ak sú priečne dotykové vektory lineárne závislé.

Metódou na zobrazovanie Bézierových plôch je polygonizácia založená na princípe rekurzívneho delenia (patch splitting), pričom sa využíva algoritmus deCasteljau.

**B-spline plochy**
Pre modelovanie sú B-spline plochy oveľa výhodnejšie, pretože sa naväzujú omnoho jednoduchšie než Hermitovské alebo Bézierove pláty. B-spline plochy $n$-tého stupňa totiž zaručujú $C^{n-1}$ spojitosť vo všetkých svojich bodoch. ďalšou výhodou je, že zmenou jedného riadiaceho bodu zmeníme vždy iba časť danej plochy.


Medzi vlastnosti B-spline plochy patrí:

* celá plocha leží v konvexnom obale svojich riadiacich bodov,
* pri zmene riadiaceho bodu sa zmenia iba pláty, ktoré sú ním určené
* plocha síce všeobecne neprechádza krajnými bodmi plochy, je to ale možné dosiahnuť násobnými riadiacimi bodmi
* sú invariantné k lineárnym transformáciam (otočenie, posun, zmena mierky, skosenie)

**NURBS plochy**
**Neuniformné racionálne B-spline plochy** sú zovšeobecnením B-spline plôch a predstavujú dnes štandard v priemyslovom modelovaní. Umožňujú definovať širokú škálu plôch, napr. voľne tvarovateľné plochy na báze racionálnych polynómov (free form surfaces) alebo plochy založené na priamkách a kuželosečkách. Aj ich vznik datujeme do polovice 20. storočia pre potreby presnej matematickej reprezentácie tvaru karosérie áut, trupu lodí či lietadiel.

Z definície, $N_{i}^{k}(u)$ a $N_{j}^{l}(v)$ sú normalizované B-spline bázové funkcie (k, l sú stupne polynómu) a $\omega_{i,j}$ sú váhy jednotlivých bodov (homogénne súradnice) riadiace siete $\mathbf{P}$. Váhy podobe ako v prípade kriviek určujú vplyv riadiaceho bodu na plochu, pričom so zvyšujúcou sa hodnotou váhy sa plocha k bodu primkýna. Podobne ako Bézierove plochy, aj NURBS sú invariantné k lineárnym transformáciam a vďaka racionalite sú naviac invariantné aj k perspektívnej projekcii.

O plochách NURBS hovoríme aj v prípade modelovacej techniky zvanej **šablónovanie** (sweeping), kde patria napríklad:

* **translačné šablónovanie** - obrys je ľubovoľný a trajektória, po ktorej je obrys ťahaný je úsečka, dostávame tzv. priamkové plochy popísané vzťahom Q(u,v) = (1-u).P(0,v) + u.P(1,v), typy translačného šablónovania sú – po úsečke s nemeniacou sa profilovou krivkou (extruded surface), po úsečke medzi danými profilmi (ruled surface) a poťahovanie (skinning),
* **rotačné šablónovanie** - obrys je ľubovoľný a trajektória, po ktorej je obrys ťahaný je kružnica alebo jej časť – toto teleso je možné získať aj rotáciou okolo osi, výsledkom je rotačná plocha (viď obrázok),
* **všeobecné šablónovanie** - obrys i trajektória je ľubovoľná, získavame zovšeobecnenú valcovú plochu.

---

## Cn, Gn spojitost, podmínky spojitosti pro po částech definované funkce

Predpokladajme, že $Q_{1}(t)$ a $Q_{2}(t)$ su dve časti (segmenty) jedinej krivky $Q(t)$ spojenej v bode $Q_{1}(t) = Q_{2}(t)$ nazývanom uzol (knot). Spojitosť (continuity) je možné zjednodušene označiť ako spôsob napojenia týchto dvoch segmentov v uzle.

Hovoríme, že $Q(t)$ je triedy $C^{n}$, ak má vo všetkých bodoch spojité derivácie podľa parametru $t$ do rádu $n$. Označenie $C^{n}$ sa nazýva **parametrická spojitosť stupňa** $n$.

* $C^{0}$ – dva segmenty sú spojito naviazané, ak je koncový bod prvého segmentu počiatočným bodom segmentu druhého
* $C^{1}$ – ak dotykový (tečný) vektor v koncovom bode prvého segmentu je rovný dotykovému vektoru druhého segmentu v jeho počiatočnom bode
* $C^{2}$ – analogicky je požadovaná rovnosť vektoru prvej a druhej derivácie

Čím vyššia je spojitosť, tím dlhšiu „dobu“ (v zmysle parametru t) oba segmenty akoby sledujú rovnaký smer. Zjavne platí vzťah $C^{n+1} \Rightarrow C^{n}$, teda napr. ak je krivka spojitá $C^{2}$, tak je spojitá aj $C^{1}$. Bod sa pohybuje po spojitej dráhe a v bode $C^{0}$ môže skokom meniť smer pohybu, rýchlosť i zrýchlenie. V bode $C^{1}$ nemôže skokom zmeniť smer pohybu a veľkosť rýchlosti, v bode $C^{2}$ sa nemôže zmeniť ani zrýchlenie.

Hladkosť naviazania môžeme posudzovať tiež podľa tzv. **geometrickej spojitosti** stupňa $n$ označovanej $G^{n}$. Najčastejšie sa používajú spojitosti $G^{0}$ a $G^{1}$.

* $G^{0}$ – ak je koncový bod prvého segmentu totožný s počiatočným bodom druhého segmentu (osobne si myslím, že môžeme tvrdiť, niečo v zmysle $G^{0} = C^{0}$)
* $G^{1}$ – ak sú $G^{0}$ spojité a súčasne sú dotykové vektory segmentov súhlasne kolineárne, teda platí $\vec{q'_{1}}(1) = k.\vec{q'_{2}}(0); \ k > 0$ (majú rovnaký smer, nie nutne veľkosť)
* $G^{2}$ – ak sú $G^{1}$ spojité a súčasne sú dotykové vektory rovnaké (smer i veľkosť)

Táto spojitosť nezaručuje totožnosť dotykových vektorov (tečných vektorů), ale len dotyčníc (tečen). Jednoducho vektory majú zhodný smer, nie však veľkosť. V bode $G^{1}$ sa nemení skokom smer pohybu, môže sa ale zmeniť jeho rýchlosť (krivka je vizuálne hladká). Spojitosť $G^{1}$ je „skoro rovnaká“ ako $C^{1}$, ale zaručiť spojitosť $G^{1}$ je oveľa jednoduchšie ako $C^{1}$. Môžme povedať, že $C^{1} \Rightarrow G^{1}$, ale výnimku tvorí prípad, kedy vektor rýchlosti v mieste spojenia dvoch segmentov je $(0,0,0)$. Opačná implikácia neplatí, pretože geometrická spojitosť nepostihuje rýchlosť a zrýchlenie pohybu.


---
## Povrchy tvořené rekurzivním dělením polygonů
Delenie polygónov robíme v prípade, keď chceme povrch objektu zjemniť, vyhladiť.
* Kedy zastaviť delenie polygónov?
* Buď keď je polygón menší ako pixel
* Alebo keď už nie je čas na ďalšie delenie
* hry, prispôsobenie sa HW

Delenie povrchov je v počítačovej grafike technika, pri ktorej sa vytvára z jednej plôšky alebo polygónu viac plôšok. Touto technikou získame jemnejší povrch. Prvýkrát bola predstavená spoločnosťou Pixar v krátkom animovanou filme s názvom Geri’s Game.

Na začiatku schéma vezme povrch alebo akýkoľvek model vytvorený z trojuholníkov, štvoruholníkov alebo viacuholníkov. Tento začiatočný povrch voláme kontrolná sieť. Potom je táto sieť rozdelená na základe sady pravidiel. Pravidlá sa líšia od jedného delenia k druhému. Určujú koľko nových vrcholov bude pridaných do kontrolnej siete a na akú pozíciu budú posunuté. Následne sa tento nový povrch stane novou hladšou kontrolnou sieťou pre ďalšiu iteráciu delenia. Po každej iterácii dostávame jemnejší povrch pridaním vrcholov a nových plôšok. Nevýhodou je pri vyšších iteráciách veľký počet vrcholov, ktoré môžu zapríčiniť spomalenú odozvu v reálnom čase. V počítačovej grafike sa pre delenie povrchov používa termín Surface subdivision. V súčasnej dobre sa rozsiahlo používajú v 3D modelovaní a animácii.

**Pravidlá delenia**
Pravidlo delenia je predpis ktorý priraďuje skupine vrcholov rozsiahlejšiu skupinu vrcholov. Deliaca schéma má dva typy pravidiel topologické a váhové.

* Topologické udávajú ako získame graf vylepšeného objektu z grafu objektu vstupného tým, že generujeme nové vrcholy, hrany a plôšky.
* Váhové špecifikujú ako vypočítať pozíciu nových vrcholov na základe interpolácie medzi vrcholmi vstupného povrchu.

**Spojitosť delenia Cn**
Je stupeň parametrické spojitosti krivky v danom bode. Je to jedna z charakteristík deliacich schém. n nám hovorí koľko derivácii je spojitých.

**Valencia vrcholu a výnimočné vrcholy**
Valencia, stupeň vrcholu označuje počet hrán ktoré do vrcholu zasahujú. Regulárne vrcholy schémy voláme tie, ktorých je vyprodukovaných najviac počas delenia a majú tú istú valenciu. Hocijaké iné vrcholy nazývame výnimočné. To aké majú tieto vrcholy efekt na výslednú plochu, záleží na deliacej schéme. Niekedy nastanú problémy keď chceme analyzovať lmitu povrchu v blízkosti týchto výnimočných vrcholov. Väčšina schém neprodukuje výnimočné vrcholy počas delenia, a tak ich počet je daný kontrolnou sieťou, ktorú dostaneme na vstupe na začiatku delenia.

**Typy delenia**
**Aproximačné schémy delenia**
- pri tomto type delenia sa pozície vrcholov upravia tak ako budú najlepšie vyhovovať novému povrchu
* Catmull-Clark - delenie ktoré sa dá použiť na hocijaký typ povrchu. Po prvej iterácii vždy vzniknú štvorsteny. Generovaný povrch je C2 spojitý, všade až na výnimočné vrcholy. Tento typ delenia je v súčasnej dobe najviac používaný v 3D aplikáciách a animácii.
* Doo-Sabin - dokáže spracovať ľubovoľnú topológiu. Môže vytvárať nove plôšky s ľubovolným počtom vrcholov.
* Loop - pracuje iba na povrchoch poskladaných z trojuholníkov, a po každej iterácii vzniknú iba trojuholníky. V súčasnej dobe sa moc nepoužíva.
* Sqrt3

**Interpolačné schémy delenia**
- pri interpolácii sa od vrcholov vyžaduje aby zodpovedali pôvodným pozíciám
* Butterfly (Motýľ)
* MidEdge
* Doo-sabin