====== Zadanie ======
Parametrické křivky, Lagrange, Hermite, Bezier, Coons, NURBS. Spojitost, změna stupně, podmínky pro hladké navázání. (PB009, PA010)

====== Vypracovanie ======

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é//.

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

**Implicitne** zadaná krivka je vyjadrená rovnicou <math>F(x,y) = 0</math>. 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, viď PA166.)

**Parametrický** tvar krivky ju chápe ako dráhu pohybúceho sa bodu, ktorého súradnice sú funkciami parametru <math>t</math>, teda času, a vyjadruje sa rovnicami <math>x = x(t)</math>, <math>y = y(t)</math> a <math>z = z(t)</math>. Čas je z intervalu <math>t \in <t_{min}, t_{max}></math>, najčastejšie volený v rozsahu <math>t \in <0, 1></math>. 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 <math>Q(t) = [x(t), y(t), z(t)]</math>, alebo //**vektorová rovnica**// <math>\vec{q}(t) = (x(t), y(t), z(t))</math>.
//**Dotykový vektor** (tečný vektor)// v bode <math>Q(t_{0})</math> je určený deriváciami parametricky vyjadrenej krivky po zložkách v tvare <math>\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)</math>. Rovnica //**dotyčnice** (tečny)// v danom bode má tvar <math>P(u) = Q(t_{0}) + u.\vec{q'}(t_{0})</math>. Vektor <math>\vec{q'}(t)</math> 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 =====

Základným druhom parametrických kriviek používaných v počítačovej grafike sú krivky //**polynomiálne**//.

<math>Q_{n}(t) = a_{0} + a_{1}(t) + ... + a_{n}(t)^{n}</math>

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ť <math>C^{2}</math> spojitosť. 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í.

Parametricky zadaná kubika má tvar
<math>x(t) = a_{x}t^{3} +  b_{x}t^{2} +  c_{x}t +  d_{x},</math>\\
<math>y(t) = a_{y}t^{3} +  b_{y}t^{2} +  c_{y}t +  d_{y},</math>\\
<math>z(t) = a_{z}t^{3} +  b_{z}t^{2} +  c_{z}t +  d_{z}</math>,
čo môžeme v maticovom tvare zapísať ako
<math>Q(t) = \mathbf{T}.\mathbf{C} = \begin{bmatrix}t^{3} & t^{2} & t & 1\end{bmatrix}.\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}</math>
a jej dotykový vektor <math>\vec{q'}(t)</math> získame deriváciou vektoru <math>\mathbf{T}</math>, teda <math>\vec{q'}(t) = \frac{d}{dt}\mathbf{T}.\mathbf{C} = \begin{bmatrix}3t^{2} & 2t & 1 & 0\end{bmatrix}.\mathbf{C}</math>.
V prípade kubík môžeme maticu rozpísať do súčinu <math>\mathbf{C} = \mathbf{M}.\mathbf{G}</math>, kde <math>\mathbf{M}</math> je //**bázová matica**// a <math>\mathbf{G}</math> je //**vektor geometrických podmienok**//, ktorý obsahuje konkrétne parametre ovplyvňujúce tvar krviky (riadiace body a dotykové vektory). Súčin <math>\mathbf{T}.\mathbf{M}</math> 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 <math>t</math>. Hodnota parametru potom určuje uplatnenie podmienky buď na začiatku krivky, vo vnútornom priebehu, alebo má najväčší vplyv na koncovú časť.
<math>Q(t) = \mathbf{T}.\mathbf{M}.\mathbf{G} = \begin{bmatrix}t^{3} & t^{2} & t & 1\end{bmatrix}.\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}.\begin{bmatrix}G_{1} \\ G_{2} \\ G_{2} \\ G_{4}\end{bmatrix}</math>

===== Interpolačné krivky =====

Zá
kladným spôsobom ako interpolovať funkciu zadanú v diskrétnych bodoch je použiť //**Langrangeov interpolujúci polynóm**// (po česky //interpolační//).

{{:mgr-szz:in-gra:lag_inter_1.jpg?350|Lagrangeova interpolácia}}

Nevýhodou je nutnosť prepočítať všetky //bázické polynómy//, ak sa rozhodneme pridať ďalší uzlový bod. Uveďme si príklad výpočtu Lagrangeovho polynómu 2. stupňa.

{{:mgr-szz:in-gra:lag_inter_2.jpg?400|Lagrangeova interpolácia - príklad}}

Po výpočte **príkladu** získavame krivku zadanú polynómom <math>P(t) = P_{0}.\left(\frac{t^{2} - 3t + 2}{2}\right) - P_{1}.\left(t^{2} - 2t\right) + P_{2}.\left(\frac{t^{2} - t}{2}\right)</math>.

==== 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 <math>P_{0}</math>, <math>P_{1}</math> a dvomi dotykovými vektormi <math>\vec{p'}_{0}</math>, <math>\vec{p'}_{1}</math>. 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.

{{ http://upload.wikimedia.org/wikipedia/commons/thumb/6/61/HermiteBasis.svg/300px-HermiteBasis.svg.png?300|Kubické Hermitovské polynómy}}

Predpis pre výpočet Hermitovskej kubiky má tvar
<math>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)</math>,
kde dostávame tzv. //**kubické Hermitovské polynómy**// (Hermitovské polynómy 3. stupňa)
<math>F_{1}(t) = 2t^{3} - 3t^{2} + 1</math> (červený),
<math>F_{2}(t) = -2t^{3} + 3t^{2}</math> (modrý),
<math>F_{3}(t) = t^{3} - 2t^{2} + t</math> (zelený),
<math>F_{4}(t) = t^{3} - t^{2}</math> (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ť <math>C^{1}</math> je zaručená totožnosťou koncových bodov a identitou dotykových vektorov v týchto bodoch či spojitosť <math>G^{1}</math> docielime lineárnou závislosťou dotykových vektorov (viď spojitosť kriviek). Hermitovské kubiky sú aj základom animačných kriviek //Kochanek-Bartels// (viď otázka 13-gra).

===== 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// <math>n</math>//-tého stupňa// sú určené <math>n + 1</math> bodmi riadiaceho polynómu <math>P_{i}</math>. 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ú.

<math>Q(t) = \sum_{i=0}^{n} P_{i}B_{i}^{n}(t)</math>

Základom Bézierových kriviek sú //**Bernsteinove polynómy**// <math>n</math>//-tého stupňa//.

{{:mgr-szz:in-gra:bernstein.jpg?350|Bernsteinove polynómy}}

Medzi vlastnosti Bernsteinovych polynómov patrí ich nezápornosť (1), súčet váh vždy 1 (3), teda výsledná krivky bude ležať v konvexnej obálke 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 <math>t</math>. Na druhom obrázku vidíme **príklad** výpočtu a schému výpočtu bodu Bézierovej kubiky v čase <math>t = 2/3</math>.

{{:mgr-szz:in-gra:deCastel_1.jpg?350 |Algoritmus deCasteljau}}
{{:mgr-szz:in-gra:deCastel_2.jpg?300 |Výpočet deCasteljau}}
{{:mgr-szz:in-gra:deCastel_3.jpg?400|Zhrnutie deCasteljau}}

//**Bézierova kubika**// je určená 4 bodmi <math>P_{0}</math>, <math>P_{1}</math>, <math>P_{2}</math> a <math>P_{3}</math> (zápis kubiky <math>P(t)</math> 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 <math>\vec{p'}(0) = 3(P_{1} - P_{0})</math> a <math>\vec{p'}(1) = 3(P_{3} - P_{2})</math>. 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.

==== 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 <math>C^{2}</math> 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**//.

{{ :mgr-szz:in-gra:bspline_1.jpg?200|Kubické Coonsove polynómy}}

//Uniformný neracionálný B-splajn// nazývame tiež //**Coonsova kubika**//. Je určená 4 riadiacimi bodmi <math>P_{0}</math>, <math>P_{1}</math>, <math>P_{2}</math> a <math>P_{3}</math>. 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 <math>t = 0</math> 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 <math>P_{1}</math> trojuholníka určeného prvými 3 bodmi (teda <math>P_{0}</math>, <math>P_{1}</math> a <math>P_{2}</math>). Takisto aj koncový bod krivky (na obrázku je krivka zaznačená ako segment <math>Q_{3}</math>) v čase <math>t = 1</math> leží v tretine ťažnice pri <math>P_{2}</math> trojuholníka určeného bodmi <math>P_{1}</math>, <math>P_{2}</math> a <math>P_{3}</math>.

//**Coonsov B-spline**// vzniká naväzovaním Coonsových kubík, je teda určená 4 a viacerými bodmi (<math>n \geq 4</math>). Skladá sa potom z <math>n - 3</math> segmentov. Každý segment <math>Q_{i}</math> je určený bodmi <math>P_{i-3}</math>, <math>P_{i-2}</math>, <math>P_{i-1}</math> a <math>P_{i}</math>. 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 <math>C^{2}</math> spojité.

{{:mgr-szz:in-gra:bspline_2.jpg?350|Coonsov B-spline}}

Medzi dôležité vlastnosti B-spline kriviek patrí invariancia (nemennosť) voči otočeniu, posunutiu a zmene mierky. B-spline leží celý v konvexnej obálke 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 <math>P_{i}</math>, zmení sa tvar štyroch segmentov <math>Q_{i}</math>, <math>Q_{i+1}</math>, <math>Q_{i+2}</math> a <math>Q_{i+3}</math>.

==== 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 <math>t</math> 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 <math>P_{0},..., P_{n}</math> riadiaceho polygónu, rádom <math>k</math> (kde najvyšší stupeň polynómu je <math>k - 1</math>) a //uzlovým vektorom// <math>(t_{0},..., t_{n+k})</math>, ktorý je tvorený postupnosťou neklesajúcich reálnych čísel -- uzlových hodnôt.

{{:mgr-szz:in-gra:nurbs_1.jpg?400|NURBS}}

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

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 konvexnej obálke 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.

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.

===== Spojitosť =====

{{ :mgr-szz:in-gra:gra5-spoj1.jpg?300|Ilustrácia parametrickej spojitosti}}

Predpokladajme, že <math>Q_{1}(t)</math> a <math>Q_{2}(t)</math> su dve časti (//segmenty//) jedinej krivky <math>Q(t)</math> spojenej v bode <math>Q_{1}(t) = Q_{2}(t)</math> 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 <math>Q(t)</math> je triedy <math>C^{n}</math>, ak má vo všetkých bodoch spojité derivácie podľa parametru <math>t</math> do rádu <math>n</math>. Označenie <math>C^{n}</math> sa nazýva //**parametrická spojitosť stupňa n**//.

  * <math>C^{0}</math> -- dva segmenty sú //spojito// naviazané, ak je koncový bod prvého segmentu počiatočným bodom segmentu druhého
  * <math>C^{1}</math> -- 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
  * <math>C^{2}</math> -- analogicky je požadovaná rovnosť vektoru prvej a druhej derivácie

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

{{ :mgr-szz:in-gra:gra5-spoj2.jpg?300|Porovnanie geometrickej a parametrickej spojitosti}}

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

  * <math>G^{0}</math> -- 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 <math>G^{0} = C^{0}</math>)
  * <math>G^{1}</math> -- ak sú <math>G^{0}</math> spojité a súčasne sú dotykové vektory segmentov súhlasne kolineárne, teda platí <math>\vec{q'_{1}}(1) = k.\vec{q'_{2}}(0); k > 0</math>

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 <math>G^{1}</math> sa nemení skokom smer pohybu, môže sa ale zmeniť jeho rýchlosť (krivka je vizuálne hladká). Spojitosť <math>G^{1}</math> je "skoro rovnaká" ako <math>C^{1}</math>, ale zaručiť spojitosť <math>G^{1}</math> je oveľa jednoduchšie ako <math>C^{1}</math>. Môžme povedať, že <math>C^{1} \Rightarrow G^{1}</math>, ale výnimku tvorí prípad, kedy vektor rýchlosti v mieste spojenia dvoch segmentov je <math>(0,0,0)</math>. Opačná implikácia neplatí, pretože geometrická spojitosť nepostihuje rýchlosť a zrýchlenie pohybu.

(Rozpisovaním presných rovníc jednotlivých derivácií vás tu nechcem zaťažovať. Nie je v nich nič, čo by sa nedalo takto elegantne slove popísať. V prípade záujmu viď slajdy PB009 uvedené v použitých zdrojoch.)

{{:mgr-szz:in-gra:gra5-spoj3.jpg?250 |Príklady spojitosti kriviek}}

(Tento obrázok ze zo slajdov predmetu PB009. Myslím si ale, že tretí príklad je chybne. Možno sa tým chcelo ukázať, že vektory majú rovnakú veľkosť, rozhodne ale nemajú rovnaký smer, takže parametrická spojitosť prvého stupňa tam byť nemôže. Keď tak ma, prosím, opravte. ;-))


====== Použité zdroje ======

ŽÁRA, Jiří., BENEŠ, Bedřich., SOCHOR, Jiří., FELKEL, Petr. //Moderní počítačová grafika//. Brno, CZ: Computer Press, 2004. 612 s. ISBN 80-251-0454-0.

SOCHOR, Jiří. Študijné materiály k predmetu "PB009 Základy počítačové grafiky". //Křivky v počítačové grafice// [online]. Brno, CZ: Masarykova univerzita, 2013.