Krivky a plochy

Dávid Pál

28. júna 2003

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

Časť I

Krivky

Za krivky budeme považovať zobrazenie C : I → E^{2} prípadne C : I → 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ť.

1 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: ^{1}

H_{0}^{3}(t) = 2t^{3} − 3t^{2} + 1  (1)
H_{1}^{3}(t) = t^{3} − 2t^{2} + t  (2)
H_{2}^{3}(t) = t^{3} − t^{2}  (3)
H_{3}^{3}(t) = −2t^{3} + 3t^{2}  (4)

Ak máme teraz dva body V_{0}, V_{1} a dva vektory u_{0}, u_{1}, tak potom krivka

H(t) = V_{0}H_{0}^{3}(t) + u_{0}H_{1}^{3}(t) + u_{1}H_{2}^{3}(t) + V_{1}H_{3}^{3}(t),  pre t ∈ [0, 1]  (5)

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.

1Stupňa najviac 3 nutne existujú len a práve tieto.

2 Beziérove krivky

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

2.1 Bernsteinove polynómy

k-ty (0 ≤ k ≤ n) Bernesteinov polynóm^{2} n-tého stupňa je

B_{k}^{n}(t) = \binom{n}{k}t^{k}(1 − t)^{n−k}.  (6)

Za ich definičný obor budeme brať interval [0, 1].

Tu sú polynómy pre malé n.

• Pre n = 0 je jediný taký polynóm B_{0}^{0} konštatne rovný 1.

• Pre n = 1 sú dva

B_{0}^{1}(t) = 1 − t, B_{1}^{1}(t) = t.

• Pre n = 2 sú tri

B_{0}^{2}(t) = (1 − t)^{2}, B_{1}^{2}(t) = 2t(1 − t), B_{2}^{2}(t) = t^{2}.

• Pre n = 3 sú štyri

B_{0}^{3}(t) = (1 − t)^{3}, B_{1}^{3}(t) = 3t(1 − t)^{2}, B_{2}^{3}(t) = 3t^{2}(1 − t), B_{3}^{3}(t) = t^{3}.

Doležité je vedieť zderivovať taký Bernsteinov polynóm.

\begin{aligned}[B_{k}^{n}(t)]′ & = [\binom{n}{k}t^{k}(1 − t)^{n−k}]′ \\ & = \binom{n}{k}kt^{k−1}(1 − t)^{n−k} − \binom{n}{n − k}(n − k)t^{k}(1 − t)^{n−k−1} \\ & = n\binom{n − 1}{k − 1}t^{k−1}(1 − t)^{n−k−1} − n\binom{n − 1}{n − k − 1}t^{k−1}(1 − t)^{n−k−1} \\ & = n [\binom{n − 1}{k − 1}t^{k−1}(1 − t)^{n−k−1} − \binom{n − 1}{k}t^{k−1}(1 − t)^{n−k−1}] \\ & = n [B_{k−1}^{n−1}(t) − B_{k}^{n−1}(t)] \end{aligned} (7)

V tomto vzorci (ale aj prípadne hocikde neskôr) pre k mimo rozsahu 0, 1, …, n berieme B_{k}^{n}(t) konštatne nulový. Dôvod je ten, že vtedy je (resp. sa kladie) \binom{n}{k} = 0.

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

2Občas zvyknú volať aj Beziérove bázicé funkcie.

• Ich hodnoty sú v intervale [0, 1], teda presnejšie

B_{k}^{n}(t) ∈ [0, 1],  pre t ∈ [0, 1].  (8)

• Súčet všetkých n + 1 polynómov dáva dokopy konštatnú jednotku

B_{0}^{n}(t) + B_{1}^{n} + ⋯ + B_{n}^{n}(t) = ∑_{k=0}^{n} \binom{n}{k}t^{k}(1 − t)^{k} = ((1 − t) + t)^{n} = 1.  (9)

• Sú to unimodálne (jednohrbé) funkcie s jediným maximov v bode t = k/n (pre n > 0).

• Tvoria bázu polynómov nanajvýš n-tého stupňa.

• Spĺňajú rekurenciu

B_{k}^{n+1} (t) = tB_{k−1}^{n}(t) + (1 − t)B_{k}^{n}(t).  (10)

2.2 Beziérove krivky

Keď máme daných n + 1 bodov V_{0}, V_{1}, …, V_{n} v euklidovskej rovine E^{2} alebo priestore E^{3}, tak definujeme Beziérovu krivku n-tého stupňa

B^{n}(t) = ∑_{k=0}^{n}B_{k}^{n}(t)V_{k},  pre t ∈ [0, 1].  (11)

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{aligned}[B^{n}(t)]′ & = [∑_{k=0}^{n}B_{k}^{n}(t)V_{k}]′ \\ & = ∑_{k=0}^{n}[B_{k}^{n}(t)]′V_{k} \\ & = n ∑_{k=0}^{n}(B_{k−1}^{n−1}(t) − B_{k}^{n−1})V_{k} \\ & = n ∑_{k=0}^{n−1} B_{k}^{n−1}(t)(V_{k+1} − V_{k}) \end{aligned}  (12)

Z tohto a vlastností Bernsteinových polynómov nám plynie, že

• Krivka leží celá v konvexnom obale svojich riadiacich vrcholov.

• Má pseudolokálne riadenie. Teda keď pohnem nejakým vrcholom, tak sa ”podstatne zmení” len kúsok okolo neho.

• Krivka sa dotýka spojnice svojich dvoch prvých a dvoch posledných riadiacich bodov.

2.3 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}, …, V_{n}, označíme ich prefíkane ako body nultej generácie

V_{0}^{0} := V_{0}, V_{1}^{0} := V_{1}, …, 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_{0}^{n} ntej 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:

V_{k}^{r} = (1 − t)V_{k}^{r−1} + tV_{k+1}^{r−1},  pre r < 0 ≤ n, 0 ≤ k ≤ n − r.  (13)

Tento reku–rere ^{3} sa nazýva 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

V_{k}^{r} = ∑_{j=0}^{r}B_{j}^{r}(t)V_{k+j}  (14)

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} …, V_{0}^{n} a pravej V_{0}^{n}, V_{1}^{n−1}, V_{2}^{n−2} …, V_{n}^{0}. (Sú to dosť otravne dlhé výpočty. Lepšie je si to načrtnúť na papier a uveriť.)

2.4 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}, …, V_{n}. Skonštruujeme riadiace vrcholy W_{0}, W_{1}, …, 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

W_{i} = \frac{i}{n + 1} V_{i−1} + (1 − \frac{i}{n + 1} )V_{i}.  (15)

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.)

3Ako nám učiteľka matematiky na gymnáziu vysvetlila, že rekurencia je od rekurere, čo znamená kráčat spät.

2.5 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}, …, 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 riacionálna Beziérova krivka je

B^{n}(t) = \frac{∑_{k=0}^{n} B_{k}^{n}(t)w_{i}V_{i}}{∑_{k=0}^{n} B_{k}^{n}(t)w_{i}},  pre t ∈ [0, 1]  (16)

Racionálne sa volajú preto, že sú podielom dvoch polynómov.^{4}

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_{i}x_{i}, w_{i}y_{i}, w_{i}z_{i}, w_{i}]. (Toto možno chápať aj ako homogénne súradnice pôvodných bodov, lebo [w_{i}x_{i}, w_{i}y_{i}, w_{i}z_{i}, w_{i}] ≡ [x_{i}, y_{i}, z_{i}, 1].)

B^{n}(t) = ∑_{k=0}^{n}B_{k}^{n}(t)U_{i} = ∑_{k=0}^{n}B_{k}^{n}(t) [\begin{matrix}w_{i}x_{i} \\ w_{i}y_{i} \\ w_{i}z_{i} \\ w_{i} \end{matrix}] = [\begin{matrix}∑_{k=0}^{n} B_{k}^{n}(t)w_{i}x_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i}y_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i}z_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i} \end{matrix}]  (17)

Potom táto krivka chápaná ako 3D krivka je racionálnu Beziérou krivkou

B^{n}(t) = [\begin{matrix}∑_{k=0}^{n} B_{k}^{n}(t)w_{i}x_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i}y_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i}z_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i} \end{matrix}] ≡ \frac{1}{∑_{k=0}^{n} B_{k}^{n}(t)w_{i}} [\begin{matrix}∑_{k=0}^{n} B_{k}^{n}(t)w_{i}x_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i}y_{i} \\ ∑_{k=0}^{n} B_{k}^{n}(t)w_{i}z_{i} \\ 1 \end{matrix}] = \frac{∑_{k=0}^{n} B_{k}^{n}(t)w_{i}V_{i}}{∑_{k=0}^{n} B_{k}^{n}(t)w_{i}}

(18)

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 Bsplajnových plôch. Idea a vzorce je vždy tá istá ako tu, takže sa tým nebudem viac špeciálne zaoberať.

3 B-splajny

3.1 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.

4Presnejšie každá súradnica zvlášť je podielom dvoch polynómov.

Najprv máme nejaké prirodzené číslo m a neklesajúcucu postupnosť m + 1 reálnych čísel t_{0} ≤ t_{1} ≤ ⋯ ≤ 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 B-splajnovú bázickú funkciu N_{k}^{d}(t) stupňa d. Pre stupeň nula je

N_{k}^{0}(t) = \begin{cases}1, & t ∈ [t_{k}, t_{k+1} ) \\ 0, & inak \end{cases},  pre 0 ≤ i ≤ m − 1.  (19)

Pre vyššie stupne ich definujeme rekurentne

N_{k}^{d}(t) = \frac{t − t_{k}}{t_{k+d} − t_{k}} N_{k}^{d−1}(t) + \frac{t_{k+d+1} − t}{t_{k+d+1} − t_{k+1}} N_{k+1}^{d−1}(t),  (20)

pre 0 ≤ i ≤ 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_{0}^{d}, B_{1}^{d}, …, B_{n}^{d}, 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):

• Sú nezáporné. N_{i}^{d}(t) je kladná na intervale (t_{i}, t_{d+1} ); tento interval sa nazýva nosič (angl. support). Sú unimodálne (jednohrbé).

• Funkcie stupňa d sa na intervale [t_{d}, t_{m−d}] sa sčítajú na konštatnú jednotku. Teda

N_{0}^{d}(t) + N_{1}^{d}(t) + ⋯ + N_{n}^{d}(t) = ∑_{k=0}^{n}N_{k}^{d}(t) = 1,  pre t ∈ [t_{d}, t_{m−d}]. (21)

• 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}).

• Tvoria vektorový priestor dimenzie n + 1.

3.2 Vektorový priestor bázických funckií

TODO

3.3 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}, …, 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í

m = n + d + 1.  (22)

B-splajnovou krivkou (skrátene B-splajnom) rozumieme krivku

N^{d}(t) = ∑_{k=0}^{n}V_{k}N_{k}^{d}(t),  pre t ∈ [t_{d}, t_{m−d}].  (23)

Jej základné vlastnosti sú:

• Lokálne riadenie, teda, keď pohnem riadiacim vrcholom, tak sa zmení naozaj len kúsok krivky. (TODO: Ktorý kúsok presne.)

• 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} , …, V_{i}.

• O spojitosti platí to, čo pre bázické funkcie.

3.4 De Boorov algoritmus

Idea je podobná ako u Casteljauovho algoritmu. Povedzme, že chceme krivku vyčísliť v bode t ∈ [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} , …, V_{i}. (Je ich d + 1.) Označíme ich, ako body nultej generácie V_{i−d}^{0}, V_{i−d+1}^{0} , …, V_{i}^{0}. Následne generujeme body ďalších generácií takto:

V_{k}^{r} = (1 − α)V_{k}^{r−1} + αV_{k+1}^{r−1},  (24)

kde

α = .  (25)

TODO

3.5 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).^{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

3.6 Böhmov algoritmus vkladania uzla

TODO

5Š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).

3.7 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

N^{d}(t) = \frac{∑_{k=0}^{n} N_{k}^{d}(t)w_{i}V_{i}}{∑_{k=0}^{n} N_{k}^{d}(t)w_{i}}  (26)

Občas sa tieto krivky volajú tiež NURBS (Non-Uniform Rational B-Spline). (Non-Uniform značí to, že uzlový vektor (postupnosť) nie je pravidelný.)

Časť II

Plochy

Plocha je podobne ako plocha, zobrazenie S : D → E^{3}, kde D je nejaká oblasť (podmnožina) ℝ^{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{∂S(u,v)}{∂u} a \frac{∂S(u,v)}{∂v} boli (ako vektory) v ľubovoľnom bode krivky lineárne nezávislé.

4 Beziérove plochy

Ide o tenzorovo-súčinovú plochu. Máme sieť (mriežku) (m+1)×(n+1) riadiacich vrcholov V_{i,j}, (0 ≤ i ≤ m, 0 ≤ j ≤ n). Potom Bezierova plocha stupňa m × n je

B^{m,n}(u, v) = ∑_{i=0}^{m} ∑_{j=0}^{n}V_{i,j}B_{i}^{m}(u)B_{j}^{n}(v),  pre u, v ∈ [0, 1].  (27)

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) × (n + 1) pôvodných riadiacich vrcholov V_{i,j}^{0,0} generácie 0, 0. V každej ďalšej generácii sa zmenšuje strana štvorca o jedna, až kým nedostaneme jediný vrchol.

V_{i,j}^{r,r} = (1−u, u) (\begin{matrix}V_{i,j}^{r−1,r−1} & V_{i,j+1}^{r−1,r−1} \\ V_{i+1,j}^{r−1,r−1} & V_{i+1,j+1}^{r−1,r−1} \end{matrix}) (\begin{matrix}1 − v \\ v \end{matrix}) , 0 < r ≤ n, 0 ≤ i, j ≤ n−r

(28)

Samozrejme nemusíme mať oba horné indexy (generácie) rovnaké a môžeme rátať všeobecnejšie

V_{i,j}^{p,q} = (1 − u, u) (\begin{matrix}V_{i,j}^{p−1,q−1} & V_{i,j+1}^{p−1,q−1} \\ V_{i+1,j}^{p−1,q−1} & V_{i+1,j+1}^{p−1,q−1} \end{matrix}) (\begin{matrix}1 − v \\ v \end{matrix}) ,

pre 0 < p ≤ m, 0 < q ≤ n, 0 ≤ i ≤ m − p, 0 ≤ j ≤ n − q. (29)

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}

B^{m,n}(u, v) = \frac{∑_{i=0}^{m} ∑_{j=0}^{n} w_{i,j}V_{i,j}B_{i}^{m}(u)B_{j}^{n}(v)}{∑_{i=0}^{m} ∑_{j=0}^{n} w_{i,j}B_{i}^{m}(u)B_{j}^{n}(v)},  pre u, v ∈ [0, 1]. (30)

5 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

{(u, v, w) | u, v, w ≥ 0, u + v + w = 1}.  (31)

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 ≥ 0.

Ďalej máme trojuholníkovú sieť \binom{n+2}{2} riadiacich vrcholov (trocha haluzne indexovanú) V_{i,j,k} (i, j, k ≥ 0, i + j + k = n). Potom Beziérov trojuholník stupňa n je

B^{n}(u, v, w) = ∑_{\begin{matrix}i+j+k=n \\ i,j,k≥0 \end{matrix}} \frac{n!}{i!j!k!}u^{i}v^{j}w^{k}V_{i,j,k}.  (32)

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 \binom{n+2}{2}). V každom ďalšom kroku sa tento rád zmenší o jedna podľa vzorca

V_{i,j,k}^{r} = uV_{i+1,j,k}^{r−1} +vV_{i,j+1,k}^{r−1} +wV_{i,j,k+1}^{r−1} ,  pre i+j+k = n−r, i, j, k ≥ 0.  (33)

Nakoniec bod V_{0,0,0}^{n} je bodom plochy, t.j. V_{0,0,0}^{n} = 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_{i,j,0}^{k}, druhého V_{i,0,k}^{j} a tretieho V_{0,j,k}^{i}, pričom i + j + k = n, i, j, k ≥ 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í.

6 B-splajnové plochy

Zase len trápna tenzoro-súčinová plocha, verná kópia Beziérovej plochy. ^{6} Máme dva uzlové vektory u_{0} ≤ u_{1} ≤ … u_{p} (pre smer u) a v_{0} ≤ v_{1} ≤ … v_{q} (pre smer v) Máme sieť (mriežku) (m + 1) × (n + 1) riadiacich vrcholov V_{i,j}, (0 ≤ i ≤ m, 0 ≤ j ≤ n). A stupne plochy r, s. Čísla p, m, r a q, n, s spĺňajú rovnosti

p = m + r + 1,  (34)
q = n + s + 1.  (35)

Potom B-splajnová plocha stupňa r × s je

N^{r,s}(u, v) = ∑_{i=0}^{m} ∑_{j=0}^{n}V_{i,j}N_{i}^{r}(u)N_{j}^{s}(v), (u, v) ∈ [u_{r}, u_{p−r}] × [v_{s}, v_{q−s}]. (36)

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}

N^{r,s}(u, v) = \frac{∑_{i=0}^{m} ∑_{j=0}^{n} w_{i,j}V_{i,j}N_{i}^{r}(u)N_{j}^{s}(v)}{∑_{i=0}^{m} ∑_{j=0}^{n} w_{i,j}N_{i}^{r}(u)N_{j}^{s}(v)}.  (37)

7 Priamkové plochy

8 Jendoduchá Coonsova záplata

Máme štyri krivky v priestore X(u, 0), X(u, 1), X(0, v) a X(1, v).^{7} Tieto štyri kryvky musia byť také, aby v poradí prvá, tretia, druhá, štvrtá tvorili uzavretú krivku.^{8} Našou úlohou je zostrojiť nejakú (rozumnú) plochu X(u, v), X : [0, 1]× [0, 1] → 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).

6Trochu tu dochádza abeceda.

7Označenie je na prvý pohľad dosť zavádzajúce a zmätočné, ale takto sa to bežne všade píše.

8Naše označenie si vlastne vynucuje.

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{matrix}X(0, 0) & X(0, 1) \\ X(1, 0) & X(1, 1) \end{matrix}) (\begin{matrix}1 − v \\ v \end{matrix}) .

Výsledná Coonsova plocha je potom

X(u, v) = X_{C}(u, v) + X_{D}(u, v) − X_{CD}(u, v).  (38)

9 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. 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_{0}^{3}(v)X(u, 0) + H_{1}^{3}(v)X_{v}(u, 0) + H_{2}^{3}(v)X_{v}(u, 1) + H_{3}^{3}(v)X(u, 1).

Podobne v pre druhý smer

X_{D}(u, v) = H_{0}^{3}(u)X(0, v) + H_{1}^{3}(u)X_{u}(0, v) + H_{2}^{3}(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_{0}^{3}(u), H_{1}^{3}(u), H_{2}^{3}(u), H_{3}^{3}(u)) (\begin{matrix}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{matrix}) (\begin{matrix}H_{0}^{3}(v) \\ H_{1}^{3}(v) \\ H_{2}^{3}(v) \\ H_{3}^{3}(v) \end{matrix})

Výsledná bikubická Coonsova záplata bude

X(u, v) = X_{C}(u, v) + X_{D}(u, v) − X_{CD}(u, v).  (39)