Geometrické modelování

RNDr. Jan Paseka, CSc. 23. března 1998

2

Úvod

Tento učební text je založen na monografii ţGeometrické modelování� autorů S. Abramowského a H. Müllera. Zároveň využívá texty českých autorů jako jsou např. ţPočítačová grafika� autorů Jiřího Žáry a kolektiv, ţAlgoritmy počítačové grafiky� autorů Jiřího Žáry a Jiřího Sochora a standartního matematického textu ţPlochy ve výpočetní technice� Ladislava Drse.

4

Obsah

1 Geometrické modelování a základní transformace 7 1 Aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Části počítačové geometrie . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Grafické znázornění . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4 Posunutí, otáčení a změna měřítka v rovině . . . . . . . . . . . . . . . 9 5 Maticové vyjádření a homogenní souřadnice . . . . . . . . . . . . . . 9 6 Další rovinné transformace . . . . . . . . . . . . . . . . . . . . . . . . 12 7 Lineární prostorové transformace . . . . . . . . . . . . . . . . . . . . 14 8 Promítací metody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Bézierova metoda 21 1 Křivky a plochy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Bézierovy křivkové segmenty . . . . . . . . . . . . . . . . . . . . . . . 22 3 Racionální křivky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4 Plochy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.1 Čtyřúhelníkové Bézierovy segmenty . . . . . . . . . . . . . . . 36 4.2 Trojúhelníkové Bézierovy segmenty . . . . . . . . . . . . . . . 39 4.3 Racionální plošné Bézierovy segmenty . . . . . . . . . . . . . . 42

5 Vyšší dimenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3 Kritéria kvality 45 1 Implicitní vyjádření . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2 Metody analýzy prostřednictvím diferenciální geometrie . . . . . . . . 47

2.1 Křivky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2 Plochy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4 Metoda B-splinů 67 1 Splinové a B-splinové funkce . . . . . . . . . . . . . . . . . . . . . . . 67 2 B-spline křivky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3 B-spline plochy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4 B-spline metoda a Bézierova metoda . . . . . . . . . . . . . . . . . . 77 \underline{6 OBSAH}

5 Racionální B-spline metoda (NURBS) . . . . . . . . . . . . . . . . . . 80 6 Přehled k B-spline metodě . . . . . . . . . . . . . . . . . . . . . . . . 81

5 Interpolace a aproximace 83

1 Interpolace s křivkami . . . . . . . . . . . . . . . . . . . . . . . . . . 83 1.1 Interpolace pomocí polynomů . . . . . . . . . . . . . . . . . . 84 1.2 Interpolace pomocí spline-křivek . . . . . . . . . . . . . . . . . 88 1.3 Geometrické spline-křivky . . . . . . . . . . . . . . . . . . . . 95

Kapitola 1

Geometrické modelování a základní transformace

Geometrické modelování se zabývá s počítačově podporovaným návrhem a s manipulací geometrických tvarů (forem). Z hlediska informatiky jsou geometrické tvary popsány datovými strukturami, se kterými lze manipulovat pomocí příslušných operátorů. V definici datové struktury se často zpětně odkazuje na reprezentaci geometrických tvarů, která vznikla v matematice. Jako příklad lze uvést parametrickou reprezentaci křivek a ploch nebo popis geometrického objektu jako množiny nulových hodnot nějakého systému rovností nebo nerovností – tzv. implicitní reprezentace.

1 Aplikace

Geometrické modelování nalezlo použití v mnoha odvětvích jako jsou např. strojírenství, architektura, geografie a geologie, biologie, počítačová animace a lékařství. V rámci těchto aplikací je geometrie pouze jednou z vícero komponent, jež navzájem spoluvytvářejí vhodný model. Tento model je základem pro numerickou simulaci nebo výrobu, jejichž efektivita je závislá na manipulovatelnosti a přesnosti geometrického modelu. Dá se říci, že geometrický tvar tvoří kostru modelu a tím spojuje všechny ostatní komponenty.

2 Části počítačové geometrie

Geometrické modelování lze rozdělit do různých oblastí, jež vznikly z různých směrů nahlížení na geometrii. Jedním z nejvypracovanějších odvětví je modelování pomocí diferenciální geometrie. Diferenciální geometrie se zabývá analýzou geometrických tvarů pod zorným úhlem diferenciálního počtu. Přitom jsou zkoumány aspekty křivosti a vzdálenosti křivek a ploch. Zejména se pak jedná o především návrh tvarů, které vzhledem ke své hladkosti musí splňovat zvláštní požadavky. Příkladem je např. karosérie či povrch automobilů nebo listy rostlin. Popis a posouzení kvality navržených diferenciálně geometrických modelů jsou prováděny pomocí pojmů diferenciální geometrie. Takovýmito postupy jsou např. metoda Beziérových polynomů resp. metoda B-splinů resp. interpolační metody. Mimo těchto metod orientovaných na paramatrické vyjádření získávají na významu i metody, které používají implicitní reprezentaci.

V kombinatorickém modelování se geometrické tvary skládají ze základních prvků jako jsou body, křivky, části roviny a polyedrů. V závislosti na přípustných operacích lze mluvit o modelech buňkových rozkladů, množinových modelech, Minkowského modelech, iterovaných dílčích modelech a modelech založených na gramatice. Speciálním případem kombinatorické geometrie je geometrie bodového rozkladu, která se zabývá geometrickým modelováním bodového rozkladu (rasterizací). Přitom je geometrický tvar reprezentován jako množina rastrových prvků nějakého rastrovaného univerza. Tento druh geometrie je používán hlavně u digitálního zpracování dat. Příkladem jsou rastrové obrázky a jejich třídimenzionální analogie – voxely.

3 Grafické znázornění

Podstatným pomocným prostředkem geometrického modelování je grafické znázornění. Za tímto účelem je potřebné efektivní převedení geometrického modelu do obrazového (grafického) znázornění. Grafické zpracování dat poskytuje pro různé datové typy přizpůsobené znázorňovací algoritmy počínaje od abstraktního znázornění křivek až po realisticky působící znázornění třídimenzionálních objektů.

V grafickém zpracování dat rozlišujeme mezi křivkově orientovanými a rastrově orientovanými metodami znázornění. Důležitým křivkově orientovaným znázorňovacím přístrojem jsou perový a jiné druhy plotrů. Plotry jsou schopny nakreslit prakticky libovolnou křivku.

U rastrové grafiky sestává reprezentace z matice pixelů. U černobílé rastrové grafiky je obrazový bod buď černý nebo bílý. Znázorňovací přístroje černobílé rastrové grafiky jsou maticové a laserové tiskárny. Podstatná charakteristika kvality je rozlišení. Rozlišení je udáváno buď jako počet obrazových bodů na jednotku délky nebo jako celkový počet řádků a sloupců obrazové matice.

U barevné rastrové grafiky se rozlišuje mezi systémy s paletami barev a plně barevnými systémy. Pixely systému s paletami barev reprezentují hodnoty z pomocné tabulky barev (palety), což je vektor z hodnot barev, který obsahuje potřebné barvy obsažené ve znázorňovaném obraze. Obvykle pracuje systém s paletami barev s 256 tabulkovými zápisy. Tímto způsobem je jeden pixel reprezentován 8 bity = 1 Byte pro index své barvy v tabulce. Zápisy barev odpovídají často paletě z 2^{24} barev. Zápis do palety proto potřebuje 24 bitů. Barvy se obvykle kódují v tzv. RGB-modelu. Tímto způsobem máme k dispozici vždy 8 bitů pro červenou, zelenou a modrou. V případě plně barevného systému se pro každý obrazový bod uloží jeho vlastní barevná hodnota.

4 Posunutí, otáčení a změna měřítka v rovině

Transformace se v grafických systémech objevují ve dvou souvislostech. Jednak se používají při změně souřadných soustav (nejčastěji jde o posunutí a změně měřítka), jednak při změně polohy a tvaru jednotlivých částí obrázku. Za základní transformace považujeme posunutí, změnu měřítka a otáčení.

Posunutí (translace) je přemístění objektu z jedné pozice do druhé. Bod o souřadnicích (x, y) je přesunut do bodu (x′, y′) přičtením délek posunutí T_{x} a T_{y} k původním souřadnicím:

\begin{aligned}x′ & = & T_{x} + x, \\ y′ & = & T_{y} + y. \end{aligned}

Dvojice délek (T_{x}, T_{y}) definuje vektor posunutí.

Transformace objektu po kruhové dráze se nazývá otáčení (rotace). Je určena úhlem otáčení θ a středem otáčení S = (x_{S}, y_{S}). Tuto transformaci vyjadřuje soustava rovnic

x′ = (x − x_{S})cosθ − (y − y_{S})sinθ + x_{S},
y′ = (x − x_{S})sinθ − (y − y_{S})cosθ + y_{S}.

Transformace, pomocí které lze změnit velikost objektu, se nazývá změna měřítka. Je pak vyjádřena soustavou rovnic

\begin{aligned}x′ & = & xS_{x}, \\ y′ & = & yS_{y}, \end{aligned}

kde (S_{x}, S_{y}) je vektor měřítek.

5 Maticové vyjádření a homogenní souřadnice

Základní transformace a jejich kombinace jsou využívány v mnoha aplikacích. Při kresbě obrazů, které jsou vytvářeny z množiny jednodušších základních tvarů, je nutno každý tvar posunout, otočit a změnit jeho velikost tak, aby správně zapadl do celku. Posloupnost transformací by se mohla provádět krok za krokem. Souřadnice bodů určujících objekt by byly nejprve podrobeny transformaci změna měřítka, poté otáčení a nakonec posunutí do žádané polohy. Mnohem výhodnější je však vypočítat žádané koncové souřadnice z původních souřadnic přímo pomocí násobení matic.

Při práci s maticemi je vhodné vyjádřit bod pomocí homogenních souřadnic. Dvojici souřadnic (x, y) zapíšeme jako trojici [x_{h} y_{h} h], kde:

\begin{aligned}x_{h} & = & xh, \\ y′ & = & yh. \end{aligned}

Parametr h se nazývá homogenizační faktor a jeho hodnota se volí nejčastěji h = 1. Každá dvourozměrná pozice má potom homogenní souřadnice ve tvaru [x_{h} y_{h} h].

Při použití homogenních souřadnic můžeme základní transformační rovnice vyjádřit pomocí násobení matic. Ačkoliv zpracováváme body v dvourozměrném prostoru, čtvercové transformační matice jsou řádu 3 z toho důvodu, aby bylo možno provádět také posunutí.

Dříve uvedené transformační rovnice můžeme zapsat v přehledném maticovém tvaru:

P′ = P M,

kde P′ = [x′ y′ 1] a P = [x y 1] jsou matice typu 1 × 3 představující souřadnice bodů. Čtvercová matice M je matice transformace.

Pro čtvercovou matici posunutí se vzdálenostmi posunu T_{x} a T_{y} zavedeme označení T (T_{x}, T_{y}):

T (T_{x}, T_{y}) = [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ T_{x} & T_{y} & 1 \end{matrix} ] .

Zavedeme také inverzní matici T^{−1} vyjadřující posunutí opačným směrem:

T^{−1}(T_{x}, T_{y}) = [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ −T_{x} & −T_{y} & 1 \end{matrix} ] .

Pro otáčení podle počátku souřadnicové soustavy zavedeme transformační matici R(θ):

R(θ) = [ \begin{matrix}cosθ & sinθ & 0 \\ − sinθ & cosθ & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Inverzní matice R^{−1}(θ) popisuje otáčení obráceným směrem:

R^{−1}(θ) = [ \begin{matrix}cosθ & − sinθ & 0 \\ sinθ & cosθ & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Podobně vytvoříme matici S(S_{x}, S_{y}) pro změnu měřítka a matici S^{−1}(S_{x}, S_{y}) k ní inverzní:

S(S_{x}, S_{y}) = [ \begin{matrix}S_{x} & 0 & 0 \\ 0 & S_{y} & 0 \\ 0 & 0 & 1 \end{matrix} ] ,

S^{−1}(S_{x}, S_{y}) = [ \begin{matrix}\frac{1}{S_{x}} & 0 & 0 \\ 0 & \frac{1}{S_{y}} & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Maticová reprezentace je běžný způsob implementace základních transformací v grafických systémech. Každou posloupnost transformací můžeme vyjádřit pomocí složené transformační matice, získané ze základních transformačních matic. Vytvoření složené transformační matice se nazývá skládání matic.

Dvě postupná posunutí můžeme provést tak, že nejprve složíme matice posunutí a potom aplikujeme výslednou složenou matici na souřadnice bodů. Jsou-li dána dvě postupná posunutí T (T_{x_{1}}, T_{y_{1}}) a T (T_{x_{2}}, T_{y_{2}}), spočítáme složenou matici jako

\begin{aligned}T & = & [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ T_{x_{1}} & T_{y_{1}} & 1 \end{matrix} ] [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ T_{x_{2}} & T_{y_{2}} & 1 \end{matrix} ] \\ & = & [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ T_{x_{1}} + T_{x_{2}} & T_{y_{1}} + T_{y_{2}} & 1 \end{matrix} ] . \end{aligned}

Je vidět, že transformace posunutí jsou aditivní. Podobně ze součtových vzorců obdržíme

T = [ \begin{matrix}cosθ & sinθ & 0 \\ − sinθ & cosθ & 0 \\ 0 & 0 & 1 \end{matrix} ] [ \begin{matrix}cosη & sinη & 0 \\ − sinη & cosη & 0 \\ 0 & 0 & 1 \end{matrix} ]

= [ \begin{matrix}cos(θ + η) & sin(θ + η) & 0 \\ − sin(θ + η) & cos(θ + η) & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Skládáme-li matice změny měřítka, výsledná matice ukazuje, že kdybychom ztrojnásobili velikost objektu dvakrát po sobě, výsledný objekt by byl devětkrát větší než objekt původní:

\begin{aligned}T & = & [ \begin{matrix}S_{x_{1}} & 0 & 0 \\ 0 & S_{y_{1}} & 0 \\ 0 & 0 & 1 \end{matrix} ] [ \begin{matrix}S_{x_{2}} & 0 & 0 \\ 0 & S_{y_{2}} & 0 \\ 0 & 0 & 1 \end{matrix} ] \\ & = & [ \begin{matrix}S_{x_{1}}S_{x_{2}} & 0 & 0 \\ 0 & S_{y_{1}}S_{y_{2}} & 0 \\ 0 & 0 & 1 \end{matrix} ] . \end{aligned}

Použijeme-li transformační matice pro posunutí a otáčení, můžeme vytvořit složenou matici pro otáčení vzhledem ke vztažnému bodu (x_{S}, y_{S}) složením tří transformací. Nejprve jsou všechny souřadnice posunuty tak, aby se vztažný bod dostal do počátku souřadnicové soustavy. Ve druhém kroku se objekt otáčí kolem počátku a nakonec jsou souřadnice posunuty tak, aby se vztažný bod vrátil do své původní polohy. Tato posloupnost je maticově popsána takto

M = T^{−1}(T_{x_{S}}, T_{y_{S}})R(θ)T (T_{x_{S}}, T_{y_{S}}).

Skládáním různých transformací docílíme různých změn polohy a tvaru objektů. Například měřítek S_{x} a S_{y}, která určují změny velikosti pouze ve směrech x a y, lze použít pro změnu měřítka objektů v libovolném směru s pomocí transformace otáčení. Připomeňme dále, že násobení matic je asociativní operace, která není obecně komutativní. Jen v některých případech je násobení dvou transformačních matic komutativní. Platí to zejména pro dvě následné speciální transformace téhož druhu (otáčení kolem počátku, rovnoměrná změna měřítka). Kombinace otáčení a posunutí však komutativní není.

6 Další rovinné transformace

Základní transformace jako posunutí, změna měřítka a otáčení jsou implementovány ve většině grafických systémů. Některé systémy obsahují navíc několik dalších transformací vhodných pro určité aplikace. Dvě takové transformace jsou zrcadlení a zkosení (střih).

Zrcadlení je transformace, která vytváří zrcadlový obraz objektu vzhledem k ose zrcadlení. Například pro zrcadlení objektů podle osy x se použije transformační matice změny měřítka, ve které však budou S_{x} = 1 a S_{y} = −1:

Z_{x} = [ \begin{matrix}1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Tato transformace zachovává souřadnice x, ale ţpřevrátí� souřadnice y. Podobně zrcadlení podle osy y převrátí souřadnice x a zachová souřadnice y:

Z_{y} = [ \begin{matrix}−1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Další typ zrcadlení převrací souřadnice x a y podle počátku souřadnicové soustavy. Osa zrcadlení je v takovém případě kolmá na rovinu xy a prochází počátkem. Odpovídající transformační matice má tvar

Z_{xy} = [ \begin{matrix}−1 & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Matici zrcadlení podle obecné osy, případně obecného vztažného bodu, vytvoříme skládáním transformačních matic pro posunutí, otáčení a zrcadlení podle souřadnicové osy či počátku. Inverzní matice Z^{−1} je vždy totožná s danou maticí Z.

Zkosení (kroucení, střih) způsobuje deformace tvarů. Výsledek transformace vyvolává dojem, jako kdyby objekty byly složeny z mnoha vrstev, které jsou po sobě posouvány. Dvě základní transformace jsou zkosení ve směru x a zkosení ve směru y. Pro zkosení ve směru x se používá transformační matice:

SH_{x} = [ \begin{matrix}1 & 0 & 0 \\ SH_{x} & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Inverzní matice zkosení má tvar:

SH_{x}^{−1} = [ \begin{matrix}1 & 0 & 0 \\ −SH_{x} & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] .

Za parametr SH_{x} můžeme volit jakákoliv reálná čísla. Transformace mění pouze souřadnice x, souřadnice y zůstávají nezměněny. Každý bod objektu je posunut ve vodorovném směru o vzdálenost úměrnou souřadnici y.

Podobná matice může být použita pro zkosení ve směru y:

SH_{y} = [ \begin{matrix}1 & SH_{y} & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] .

7 Lineární prostorové transformace

Podobně jako v dvojrozměrném případě umožňují třídimenzionální (3D) transformace modifikovat objekty a měnit jejich polohu a orientaci v prostoru. Pro transformaci objektů v prostoru lze použít obdobné transformace jako v rovině. Transformace popíšeme pomocí matic 4 × 4 s využitím homogenních souřadnic. Každému bodu o souřadnicích (x, y, z) přiřadíme čtveřici [x_{w} y_{w} z_{w} w], kde w je libovolné nenulové reálné číslo. Tato čtveřice bude představovat homogenní souřadnice bodu.

Transformace posunutí změní polohu objektu beze změny tvaru a orientace objektu. Pomocí transformační matice

Pro čtvercovou matici posunutí se vzdálenostmi posunu T_{x}, T_{y} a T_{z} zavedeme označení T (T_{x}, T_{y}, T_{z}):

T (T_{x}, T_{y}, T_{z}) = [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ T_{x} & T_{y} & T_{z} & 1 \end{matrix} ] .

Zavedeme také inverzní matici T^{−1} vyjadřující posunutí opačným směrem:

T^{−1}(T_{x}, T_{y}, T_{z}) = [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ −T_{x} & −T_{y} & −T_{z} & 1 \end{matrix} ] .

Při otáčení v rovině stačí určit střed otáčení a úhel otáčení. U prostorové transformace však musíme zadat osu otáčení a úhel otočení okolo této osy nebo určit otočení jiným jednoznačným způsobem.

Uvažujme nejprve jednodušší případ, kdy osa otáčení splývá s některou ze souřadnicových os. Nejprve sestavíme transformační matici pro otočení okolo osy z o úhel θ. Tato matice má tvar: Pro otáčení podle počátku souřadnicové soustavy zavedeme transformační matici R(θ):

R_{z}(θ) = [ \begin{matrix}cosθ & sinθ & 0 & 0 \\ − sinθ & cosθ & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] .

Podobně lze určit i matice pro otočení okolo osy x, resp. y:

R_{x}(θ) = [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & cosθ & sinθ & 0 \\ 0 & − sinθ & cosθ & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] , R_{y}(θ) = [ \begin{matrix}cosθ & 0 & sinθ & 0 \\ 0 & 1 & 0 & 0 \\ − sinθ & 0 & cosθ & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] .

Trransformační matice pro otočení v prostoru okolo libovolné osy získáme složením jednodušších transformací.

Nechť je osa otáčení určena body A = [x_{1}w, y_{1}w, z_{1}w, w] a B = [x_{2}w, y_{2}w, z_{2}w, w]. Nejprve vytvoříme matici M, která přemístí osu otáčení do některé ze souřadnicových os (nechť je to např. osa z). Libovolný bod p otáčeného objektu bude transformován do bodu pM. Potom provedeme transformaci R_{z}(θ) o úhel θ, bod p se přemístí do bodu pMR_{z}(θ). Nakonec otočený bod transformujeme zpět (osa otáčení se z osy z přemístí do původní polohy) pomocí transformace M^{−1} na výsledný bod:

pMR_{z}(θ)M^{−1}.

Matici M můžeme zkonstruovat např. takto:

1. Transformací posunutí T (T_{−x_{1}}, T_{−y_{1}}, T_{−z_{1}}) přemístíme A = [x_{1}w, y_{1}w, z_{1}w, w] do počátku.

2. Určíme polární souřadnice druhého koncového bodu po posunutí tj. bodu B′ = [(x_{2}−x_{1})w, (y_{2}−y_{1})w, (z_{2}−z_{1})w, w]. Polární souřadnice bodu B′ jsou B′_{polar} [r, ω_{1}, ω_{2}].

3. Provedeme otočení okolo souřadnicové osy z o úhel −ω_{1}. Odpovídající matici rotace označíme R_{z}(−ω_{1}). Transformovaná osa otočení leží nyní v rovině xz.

4. Provedeme otočení okolo souřadnicové osy y o úhel −ω_{2}. Odpovídající matici rotace označíme R_{y}(−ω_{2}). Transformovaná osa otočení splyne s osou z.

Matice M je tedy definována:

M = T (T_{−x_{1}}, T_{−y_{1}}, T_{−z_{1}})R_{z}(−ω_{1})R_{y}(−ω_{2}).

Inverzní matice odpovídá složení zpětných transformací

M^{−1} = R_{y}(ω_{2})R_{z}(ω_{1})T (T_{x_{1}}, T_{y_{1}}, T_{z_{1}}).

Výsledná transformace R_{obecná} je dána maticí

R_{obecná} = MR_{z}(θ)M^{−1}.

Podobně jako v dvojrozměrném případě vytvoříme matici S(S_{x}, S_{y}, S_{z}) pro změnu měřítka a matici S^{−1}(S_{x}, S_{y}, S_{z}) k ní inverzní:

S(S_{x}, S_{y}, S_{z}) = [ \begin{matrix}S_{x} & 0 & 0 & 0 \\ 0 & S_{y} & 0 & 0 \\ 0 & 0 & S_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] ,

S^{−1}(S_{x}, S_{y}, S_{z}) = [ \begin{matrix}\frac{1}{S_{x}} & 0 & 0 & 0 \\ 0 & \frac{1}{S_{y}} & 0 & 0 \\ 0 & 0 & \frac{1}{S_{z}} & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] .

Transformace zkosením deformuje transformovaný objekt. Jako příklad uvedeme zkosení ve směru roviny xy. Transformační matice pro zkosení je:

SH_{xy} = [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ SH_{x} & SH_{y} & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] .

Analogické matice platí i pro zkosení v jiných rovinách. Uvedené transformace lze libovolně kombinovat a vytvářet transformace zrcadlení, souměrnosti apod.

8 Promítací metody

Ideální způsob vytvoření obrazu trojrozměrného objektu na dvourozměrné ploše obrazovky či výkresu není jednoznačně stanoven. V technických odvětvích dávají konstruktéři přednost vybraným pohledům na objekty (půdorys, nárys, bokorys), pro obecný pohled volí různé typy rovnoběžného promítání, které sice neodpovídá skutečnosti, ale je vhodné pro případná odměřování délek či úhlů. Architekti naopak používají téměř výlučně středové promítání, ve kterém se vzdálenější objekty jeví menšími tak, jak je tomu ve skutečnosti.

Připomeňme si, že vyjádříme-li bod o souřadnicích (x, y, z) pomocí homogenních souřadnic jako P = [x_{h}, y_{h}, z_{h}, h], můžeme jeho transformaci na bod P′ = [x′_{h}, y′_{h}, z′_{h}, h] maticově vyjádřit jako:

P′ = P [ \begin{matrix}A_{xx} & A_{yx} & A_{zx} & P_{x} \\ A_{xy} & A_{yy} & A_{zy} & P_{y} \\ A_{xz} & A_{yz} & A_{zz} & P_{z} \\ T_{x} & T_{y} & T_{z} & 1 \end{matrix} ] ,

kde koeficienty A_{ij} jsou používány pro vyjádření otáčení, změnu měřítka a zkosení, koeficienty T_{i} vyjadřují posunutí a koeficienty P_{i} vyjadřují projekci.

Pojmem promítání (projekce) budeme označovat transformaci, která převede body z trojrozměrného prostoru do prostoru dvojrozměrného. Prakticky to znamená, že jedna ze souřadnic (nejčastěji z) nabyde konstantní (nulové) hodnoty, takže ji bude možno vynechat.

Připomeňme dále, že promítací paprsek je přímka vedená promítaným bodem, jejíž směr závisí na zvolené promítací metodě. Průmětna je pak rovina v prostoru, na kterou dopadají promítací paprsky.

V následujícím budeme většinou předpokládat, že průmětna je shodná s rovinou xy, což umožní jednoduchým způsobem (zanedbáním souřadnice z) vykreslit výsledný obraz. Tento předpoklad není omezující - libovolnou průmětnu je možno transformovat pomocí otočení a posunutí tak, aby splynula s rovinou xy. Stejné transformace je pochopitelně nutno použít i na všechny promítané body v prostoru.

Uvedený postup je běžný ve většině grafických systémů. Jednotná poloha průmětny totiž dovoluje zjednodušit podstatným způsobem řadu algoritmů řešících viditelnost a stínování.

Podle směru promítacích paprsků se promítací metody rozdělují na:

1. Rovnoběžné promítání, při kterém jsou všechny promítací paprsky rovnoběžné. Výsledkem je obraz, který zachovává relativní rozměry prostorových objektů, ale nemá přirozený vzhled.

2. Středové promítání (perspektivní). Při něm všechny paprsky procházejí jedním bodem - středem promítání. Ve výsledném obrazu se úsečky vzdálené více od středu promítání zobrazí jako kratší než stejně dlouhé úsečky bližší.

Středové promítání

Uvažme následující případ - projekci bodu P = (x, y, z) na bod P′ = (x′, y′, z_{0}) v průmětně π. Přitom pozorovatel je v daném případě v počátku souřadného systému a projekční rovina je kolmá na osu z. Na základě trojúhelníkové podobnosti vidíme, že

x′ = x\frac{z_{0}}{z} , y′ = y \frac{z_{0}}{z} .

Vzdálené body za průmětnou jsou při zobrazení zmenšeny, objekty v průmětně zachovávají velikost a objekty před průmětnou se na obraze zvětší. Transformační předpis v homogenních souřadnicích má tvar

[x′, y′, z′, w′] = [x, y, z, 1] [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & \frac{1}{z_{0}} \\ 0 & 0 & 0 & 1 \end{matrix} ] = [x, y, z, \frac{z}{z_{0}}].

To znamená, že můžeme vyjádřit středové (perspektivní) promítání pomocí lineární transformace. Pokud uvažujeme umístění pozorovatele v bodě z = z_{0} a projekční rovinu umístíme do počátku souřadného systému (tj. ji ztotožníme s rovinou xy), pak

x′ = x\frac{z_{0}}{z + z_{0}} = \frac{x}{1 + \frac{z}{z_{0}}} , y′ = y \frac{z_{0}}{z + z_{0}} = \frac{y}{1 + \frac{z}{z_{0}}} .

Maticový tvar této transformace je

[x′, y′, z′, w′] = [x, y, z, 1] [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{z_{0}} \\ 0 & 0 & 0 & 1 \end{matrix} ] = [x, y, z, \frac{z}{z_{0}}].

Přitom

[ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{z_{0}} \\ 0 & 0 & 0 & 1 \end{matrix} ] = [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & \frac{1}{z_{0}} \\ 0 & 0 & 0 & 1 \end{matrix} ] [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] ,

tj.

P_{per} = T_{per}P_{par} .

Perspektivní projekci podle matice P_{per} můžeme chápat jako perspektivní transformaci objektů maticí T_{per} a následnou paralelní projekci do zvolené průmětny vyjádřenou maticí P_{par} . Transformace T_{per} zachovává body v rovině z = 0 beze změny. To platí i pro obrazové body [1, 0, 0, 0] a [0, 1, 0, 0] na ose x nebo na ose y. Rovnoběžky ve směru os x nebo y zůstanou rovnoběžné. Bod v nekonečnu na ose z tj. [0, 0, 1, 0] je transformován do bodu [0, 0, 1, \frac{1}{z_{0}}] neboli [0, 0, z_{0}, 1]. To znamená, že všechny rovnoběžky s osou z procházejí po středové (perspektivní) transformaci bodem [0, 0, z_{0}, 1]. Tento bod se nazývá úběžník. Pokud projekční rovina protíná 2 nebo 3 osy souřadného systému, pak odpovídající perspektivní transformace určí 2 nebo 3 úběžníky na příslušných osách. V souladu s tím používáme pojmenování dvoubodová nebo tříbodová perspektiva. Pokud protíná průmětna osy souřadného systému v úběžnících (−x_{0}, 0), (0, −y_{0}, 0), (0, 0, −z_{0}), perspektivní transformaci popíšeme maticí

T_{perxyz} = [ \begin{matrix}1 & 0 & 0 & \frac{1}{x_{0}} \\ 0 & 1 & 0 & \frac{1}{y_{0}} \\ 0 & 0 & 0 & \frac{1}{z_{0}} \\ 0 & 0 & 0 & 1 \end{matrix} ] .

Rovnoběžné promítání

Nejjednodušší typ rovnoběžného promítání je promítání do některé z rovin x = x_{0}, y = y_{0}, z = z_{0} ve směru příslušné osy kolmé na zvolenou promítací rovinu - průmětnu. Velmi často budou x_{0}, y_{0} nebo z_{0} = 0, průmětnou bude některá z rovin yz, xz nebo yz. Projekci popíšeme jednoduchou transformací v homogenních souřadnicích:

[x′, y′, z′, w′] = [x, y, z, 1] [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & z_{0} & 1 \end{matrix} ] .

Skupina projekcí ve směru hlavních os do průměten v hlavních rovinách xy, xz a yz, která zahrnuje nárys a podle potřeby bokorysy, půdorys (pohled shora), spodní pohled a pohled zezadu, se nazývá Mongeova projekce. Mongeovo promítání je speciálním příkladem kolmého promítání. Promítací paprsky jsou kolmé na průmětnu.

Axonometrie

Axonometrické kolmé promítání používá projekční roviny, které nejsou rovnoběžné s hlavními osami, tj. průmětna protíná 2 nebo nejčastěji všechny 3 hlavní osy. Axonometrické kolmé promítání zachovává rovnoběžnost promítnutých hran, změní úhly mezi hranami. Pokud průmětna protne hlavní osy ve stejné vzdálenosti, pak v průmětu lze měřit a porovnávat vzdálenosti – zkreslení vydáleností je totiž ve všech směrech promítnutých os stejné. Tato projekce se nazývá izometrie. Matice izometrického zobrazení má tvar:

M_{izo} = [ \begin{matrix}− cos30^{∘} & − sin30^{∘} & 0 & 0 \\ cos30^{∘} & − sin30^{∘} & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] .

Kosoúhlé promítání

Kosoúhlý průmět získáme promítnutím bodů do průmětny ve směru, který není kolmý k průmětně. Uvažme kosoúhlé promítání bodu (x_{1}, y_{1}, z_{1}) promítacím paprskem do polohy (x_{2}, y_{2}) v průmětně. Kolmý průmět bodu je přitom označen jako (x_{k}, y_{k}). Promítací paprsek svírá úhel α s úsečkou v průmětně, která je určena body (x_{2}, y_{2}) a (x_{k}, y_{k}). Tato úsečka má délku L a svírá úhel θ s vodorovným směrem v průmětně. Při uvedeném značení vyjádříme souřadnice bodu (x_{2}, y_{2}) pomocí x_{k}, y_{k}, L a θ jako

\begin{aligned}x_{2} & = & x_{k} + L cosθ, \\ y_{2} & = & y_{k} + L sinθ. \end{aligned}

Pro definici směru promítání stačí zvolit velikosti úhlů θ a α. Obvyklé hodnoty jsou 30^{∘} a 45^{∘}, které umožňují kombinovaný pohled na přední, boční a vrchní stranu krychle, jejíž stěny jsou rovnoběžné se souřadnicovými osami. Délku L vyjádříme pomocí z_{1} a úhlu α

tanα = \frac{z}{L} = \frac{1}{L_{1}},

kde délka L_{1} je ţnormalizovaná� délka L pro případ z_{1} = 1. Po úpravě L = z_{1}L_{1} zapíšeme předchozí rovnice pro kosoúhlé promítání ve tvaru

\begin{aligned}x_{2} & = & x_{k} + z_{1}(L_{1} cosθ), \\ y_{2} & = & y_{k} + z_{1}(L_{1} sinθ). \end{aligned}

Odtud již snadno odvodíme tvar matice kosoúhlého promítání

M_{koso} = [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ L_{1} cosθ & L_{1} sinθ & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] .

Tato matice vyjadřuje současně i pravoúhlé promítání, pokud je L_{1} = 0, což nastává právě při velikosti úhlu α = 90^{∘}. Kosoúhlé promítání má tedy nenulové hodnoty L_{1}. Všimněme si, že matice M_{koso} je podobná matici zkosení. Kosoúhlé promítání lze skutečně provést jako zkosení (smyk) ve směru roviny xy a kolmé promítnutí do této roviny. Protože při zkosení je posun souřadnic x a y, ležících v téže rovině rovnoběžné s xy, úměrný velikosti z, zachovává toto promítání úhly, vzdálenosti a rovnoběžky v dané rovině. Úhel α lze sice volit libovolně, v praxi se však nejčastěji používají dvě základní hodnoty:

• Kavalírní promítání je charakterizováno hodnotou tanα = 1, tedy α = 45^{∘}. Všechny úsečky kolmé k průmětně jsou promítány bez zkreslení.

• Kabinetní promítání má tanα = 2. To nastává pro úhel o přibližné velikosti α = 63, 4^{∘}. Všechny úsečky kolmé k průmětně jsou kráceny na polovinu a výsledný průmět vypadá poměrně přirozeně. .

Bézierova metoda

Bézierovu metodu lze přiřadit k diferenciálně geometrickému modelování. Jsou takto navrhovovány hladké křivky, plochy a tělesa reprezentované parametricky. Navržené geometrické tvary jsou popsány pomocí polynomů. Použijeme však reprezentaci, kde Bernsteinovy polynomy tvoří bázi. Koeficienty jsou pak geometricky odvoditelné parametry.

1 Křivky a plochy

Hladké tvary jako silueta vázy, karosérie automobilu nebo vybroušený diamant lze matematicky popsat po,ocí křivek, ploch nebo těles.

Definice. Parametrická reprezentace křivky v R^{d}: souřadnice bodů p křivky jsou funkce jedné proměnné:

p = k(t), k : P → R^{d}, t ∈ P ⊆ R.

P je přitom interval, např. [0, 1] a nazývá se parametrický obor křivky.

Kruh je např. v rovině x − y popsán jako:

x = cost, y = sint, t ∈ [0, 2π].

a šroubovice v prostoru jako:

x = sint, y = cost, z = t, t ∈ R.

Podobně jako pro křivky, lze parametricky definovat plochu jako obraz dvoudimenzionálního intervalu:

Definice. Parametrická reprezentace plochy v R^{3}: souřadnice x, y, z bodů p plochy jsou funkce jedné proměnné:

p = ( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}x(u, v) \\ y(u, v) \\ z(u, v) \end{matrix} ) = f(u, v), (u, v) ∈ P ⊆ R^{2},

kde x, y, z : P → R, f : P → R^{3}, P je interval, např. [0, 1] × [0, 1] a nazývá se parametrický obor plochy.

Příkladem plochy je

x = \frac{u^{2} + v^{2}}{3u^{2} + 2v^{2}} , y = \frac{u}{3u^{2} + 2v^{2}} , z = \frac{u · v}{3u^{2} + 2v^{2}} , (u, v) ∈ (0, 1] × (0, 1].

Křivky v R^{2} resp. plochy v R^{3} lze reprezentovat v mnoha případech explicitně:

Definice. Explicitní reprezentace křivky v R^{2}: y-ová souřadnice bodů p křivky je funkce proměnné x:

p = (x, y), y = f(x) s f : P → R, P ⊆ R.

Explicitní reprezentace plochy v R^{3}: z-ová souřadnice bodů p plochy je funkce proměnných x, y:

p = (x, y, z), z = f(x, y) s f : P → R, P ⊆ R^{2}.

2 Bézierovy křivkové segmenty

Množství možností umožňující nám si vyjádřit křivky a plochy závisí na třídě použitých funkcí. Při volbě této třídy je důležitou vedlejší podmínkou algoritmická manipulovatelnost s těmito funkcemi. Jako důležitá třída se ukázaly polynomy:

Definice. Polynomiální křivkový segment v R^{d} má tvar:

p(t) := ∑_{i=0}^{n}a_{i}t^{i}, t ∈ [0, 1], a_{i} ∈ R^{d}.

Tvar polynomiální křivky v této reprezentaci je určen koeficienty a_{i}. Výpočtově lze tento polynom reprezentovat těmito koeficienty. Tyto koeficienty však nejsou vhodné pro použití v grafickém systému. Souvislost mezi křivkou a koeficienty je málo intuitivní. To lze odstranit Bézierovou metodou.

Bézierova metoda používá reprezentaci polynomů s vhodnějšími řiditelnými parametry. Bézierovy křivky jsou zadány posloupností bodů b_{i}, i = 0, 1, …, n. Tyto body se nazývají Bézierovy kontrolní body. Spojení Bézierových bodů v daném pořadí definuje Bézierův kontrolní polygon. Vycházeje z Bézierova polygonu, jsou křivkové body určeny podle následujícího předpisu:

Algoritmus. (de Casteljau) Vstup: Bézierovy body b_{0}, b_{1}, …, b_{n}, parametrická hodnota t^{∗} ∈ [0, 1]. Výstup: Bod křivky b(t^{∗}).

BEGIN

FOR i := 0 TO n DO b_{i}^{0} := b_{i};

FOR j := 1 TO n DO

FOR i := j TO n DO b_{i}^{j} := (1 − t^{∗}) · b_{i−1}^{j−1} + t^{∗} · b_{i}^{j−1};

b(t^{∗}) := b_{n}^{n}

END.

Casteljauův algoritmus nám poskytuje souvislost mezi kontrolním polygonem a výslednou křivkou. Abychom mohli určit bod křivky určený parametrem t^{∗}, budou hrany Bézierova polygonu rozděleny v poměru t^{∗} : (1 − t^{∗}) a výsledné body spojeny tahem polygonem. S tímto o jeden bod kratším tahem se postupuje obdobně až zbude pouze jeden bod. To je hledaný křivkový bod b(t^{∗}). Tímto Casteljauovým algoritmem definovaná křivka se dá popsat jako

b(t) := ∑_{i=0}^{n}b_{i}B_{i}^{n}(t), t ∈ [0, 1], b_{i} ∈ R^{d},

kde B_{i}^{n}(t) jsou níže definované Bernsteinovy polynomy.

Definice. Bernsteinovy polynomy stupně n jsou tvaru:

B_{i}^{n}(x) = (\begin{matrix}n \\ i \end{matrix})x^{i}(1 − x)^{n−i}, i = 0, …, n.

Křivky v této reprezentaci se nazývají Bézierovy křivkové segmenty.

Definice. Bézierův křivkový segment v R^{d} je tvaru:

b(t) := ∑_{i=0}^{n}b_{i}B_{i}^{n}(t), t ∈ [0, 1], b_{i} ∈ R^{d}.

Souvislost mezi Casteljauovým algoritmem a Bézierovými křivkovými segmenty lze formálně zapsat následovně:

b_{i}^{j}(t) := ∑_{k=0}^{j} b_{i−j+k} B_{k}^{j}(t), j = 0, …, n, i = j, …, n, t ∈ [0, 1].

Důkaz lze provést indukcí. Totiž

b_{i+1}^{j+1} (t)= (1 − t)b_{i}^{j}(t) + tb_{i+1}^{j} (t)
= (1 − t) ∑_{k=0}^{j} b_{i−j+k} B_{k}^{j}(t) + t ∑_{k=0}^{j} b_{i+1−j+k} B_{k}^{j}(t)
= (1 − t)b_{i−j}B_{0}^{j}(t) + ∑_{k=1}^{j} ((1 − t)b_{i−j+k} B_{k}^{j}(t) + tb_{i−j+k} B_{k−1}^{j}(t)) + tb_{i+1} B_{j}^{j}(t)
= (1 − t)b_{i−j}B_{0}^{j}(t) + ∑_{k=1}^{j} b_{i−j+k} B_{k}^{j+1} (t) + tb_{i+1} B_{j}^{j}(t)
= b_{i−j}B_{0}^{j+1} (t) + ∑_{k=1}^{j} b_{i−j+k} B_{k}^{j+1} (t) + b_{i+1} B_{j+1}^{j+1} (t)
= ∑_{k=0}^{j+1} b_{i−j+k} B_{k}^{j+1} (t)

Věta 2.1 Vlastnosti Bernsteinových polynomů 1. \underline{Rozklad jednotky:}Součet Bernsteinových polynomů stupně n je 1:

∑_{i=0}^{n}B_{i}^{n}(x) = ∑_{i=0}^{n}(\begin{matrix}n \\ i \end{matrix})x^{i}(1 − x)^{n−i} = (x + 1 − x)^{n} = 1.

2. \underline{Pozitivita:}Bernsteinovy polynomy jsou v intervalu [0, 1] nezáporné: B_{i}^{n}(x) ≥ 0, i = 0, …, n, x ∈ [0, 1].

3. \underline{Maximum:}B_{i}^{n}(x) nabývá svého maxima v intervalu [0, 1] v bodě \frac{i}{n}, i = 0, …, n.

4. \underline{Sumace:}

∑_{i=0}^{n}iB_{i}^{n}(x) = n · x.

5. \underline{Symetrie:}
B_{i}^{n}(x) = B_{n−i}^{n}(1 − x), i = 0, …, n.

6. \underline{Rekurze:} Pro i = 0, …, n platí

B_{i+1}^{n+1} (x) = \frac{(n + 1)!}{(i + 1)!(n − i)!} x^{i+1} (1 − x)^{n−i}
= [\frac{n!(i + 1)}{(i + 1)!(n − i)!} + \frac{n!(n − i)}{(i + 1)!(n − i − 1)!(n − i)} ] x^{i+1} (1 − x)^{n−i}
= xB_{i}^{n}(x) + (1 − x)B_{i+1}^{n} (x).

Je tedy Bernsteinův polynom stupně n + 1 konvexní kombinací dvou Bernsteinových polynomů stupně n.

7. \underline{Derivace:} Pro i = 1, …, n − 1 platí

\frac{d}{dx}B_{i}^{n}(x) = \frac{n(n − 1)!}{i!(n − i)!} (i · x^{i−1}(1 − x)^{n−i} − (n − i) · x^{i}(1 − x)^{n−1−i})
= n · (B_{i−1}^{n−1}(x) − B_{i}^{n−1}(x)).

8. \underline{Integrace:}

∫_{0}^{1} B_{i}^{n}(x) = \frac{1}{n + 1} .

Důkaz. Snadné cvičení.

Třída všech polynomů stupně nejvýše n nad reálnými čísly tvoří vektorový podprostor dimenze n+1 s obvykle definovaným sčítáním polynomů a násobení polynomu skalárem. Při dané bázi sestávající z polynomů

{e_{0}(x), …, e_{n}(x)}

lze každý polynom zapsat jako lineární kombinaci

∑_{i=0}^{n}λ_{i}e_{i}(x),

kde λ_{i} jsou skaláry. Vedle známých bázé z monomů tj. z polynomů e_{i}(x) = x^{i}, i = 0, …, n tvoří bázi i Bernsteinovy polynomy, přičemž e_{i}(x) = B_{i}^{n}(x), i = 0, …, n. Máme tedy následující důsledek:

Věta 2.2 Bernstein-Bézierova reprezentace Každý polynomiální křivkový segment p(t) = ∑_{i=0}^{n} a_{i}t^{i} lze zapsat jako Bézierův křivkový segment

b(t) = ∑_{i=0}^{n}b_{i}B_{i}^{n}(t),

a to následovně

b_{i} = ∑_{k=0}^{i} (\begin{matrix}i \\ k \end{matrix} )(\begin{matrix}n \\ k \end{matrix})^{−1}a_{k}.

Důkaz. Dosazením za b_{i} do b(t). Totiž

b(t) = ∑_{i=0}^{n} b_{i}B_{i}^{n}(t) = ∑_{i=0}^{n} ∑_{k=0}^{i} (\begin{matrix}i \\ k \end{matrix} )(\begin{matrix}n \\ k \end{matrix})^{−1}a_{k}B_{i}^{n}(t)
= ∑_{k=0}^{n} a_{k} ∑_{i=k}^{n} (\begin{matrix}i \\ k \end{matrix} )(\begin{matrix}n \\ k \end{matrix})^{−1}B_{i}^{n}(t)
= ∑_{k=0}^{n} a_{k} ∑_{i=k}^{n} (\begin{matrix}i \\ k \end{matrix} )(\begin{matrix}n \\ k \end{matrix})^{−1}(\begin{matrix}n \\ i \end{matrix})t^{i}(1 − t)^{n−i}
= ∑_{k=0}^{n} a_{k} ∑_{i=k}^{n} (\begin{matrix}n − k \\ i − k \end{matrix} )t^{i}(1 − t)^{n−i}
= ∑_{k=0}^{n} a_{k}t^{k} ∑_{j=0}^{n−k} (\begin{matrix}n − k \\ j \end{matrix} )t^{j}(1 − t)^{n−k−j}
= ∑_{k=0}^{n} a_{k}t^{k} ∑_{j=0}^{n−k} B_{j}^{n−k}(t) = ∑_{k=0}^{n} a_{k}t^{k} = p(t).

Zároveň platí

Věta 2.3 Vlastnosti Bézierových křivkových segmentů

1. \underline{Chování v koncových bodech:}Kontrolní polygon a křivkový segment mají stejný počáteční a koncový bod. První a poslední segment kontrolního polygonu je tečný ke křivce. Ostatní Bézierovy bodu nejsou interpolovány, pouze aproximovány.

2. \underline{Vlastnost konvexního obalu:}Křivkový segment leží v konvexním obalu Bézierových bodů. Zejména tedy leží i v konvexním obalu Bézierova polygoniálního tahu.

3. \underline{Vliv kontrolních bodů:}b_{i} má největší vliv na b(t) v případě, že t = i/n.

4. \underline{Omezené kolísání:} Žádná přímka neprotíná Bézierův křivkový segment častěji než odpovídající Bézierův polygoniální tah (variation diminishing property).

Důkaz. Chování koncových bodů a tvrzení o vlivu kontrolních bodů plyne bezprostředně z geometrické podoby Bernsteinových polynomů. Vliv Bernsteinova polynomu v bodě je maximální právě tehdy, když v něm Bernsteinův polynom nabývá maximum. Důkaz vlastnosti konvexního obalu vyplývá okamžitě z Casteljauova algoritmu výpočtu křivkového bodu b(t) ze zadaných kontrolních bodů. Konvexní obal množiny bodů je nejmenší konvexní množina ji obsahující. S každými dvěma Bézierovými body je zde obsažena i jejich spojovací úsečka. To samé platí pro všechny ostatní spojovací úsečky a zejména tedy pro výsledek b(t). Důkaz vlastnosti omezeného kolísání bude proveden později.

Časová náročnost Casteljauova algoritmu je O(n^{2}). Využitím vhodné reprezentace lze křivkové body spočítat snadnou modifikací známého Hornerova schématu vyhodnocení hodnoty polynomu v čase O(n).

Protože však Casteljauův algoritmus je numericky opravdu stabilní (v důsledku toho, že pracujeme pouze s konvexními kombinacemi vstupních dat) a v určitých situacích lze využít mezivýpočtů, je jeho menší efektivita relativizována.

Algoritmus. (Bézier-Horner) Vstup: Bézierovy body b_{0}, b_{1}, …, b_{n} ∈ R^{d}, parametrická hodnota t^{∗} ∈ [0, 1].

Výstup: Bod b(t^{∗}) Bézierova křivkového segmentu b.

BEGIN

IF t^{∗} ≤ \frac{1}{2} THEN

2. BÉZIEROVY KŘIVKOVÉ SEGMENTY  27

BEGIN b := b_{n}; FOR i := 1 TO n DO b := b · (i/(n − i + 1)) · (t^{∗}/(1 − t^{∗})) + b_{n−i}; b := (1 − t^{∗})^{n} · b;

END

ELSE

BEGIN b := b_{0}; FOR i := 0 TO n − 1 DO b := b · ((n − i)/(i + 1)) · ((1 − t^{∗})/t^{∗}) + b_{i}; b := (t^{∗})^{n} · b;

END;

b(t^{∗}) := b END. Věta 2.4 Korektnost Bézier-Hornerova algoritmu Bézier-Hornerův algoritmus je korektní tj. jeho výsledek splývá s výsledkem Casteljauova algoritmu. Důkaz. Věnujme se případu t^{∗} ≤ \frac{1}{2} (případ t^{∗} > \frac{1}{2} se ukáže analogicky). Označme výsledek v i-tém kroku příkazu FOR jakožto b^{i} a zároveň položme b^{0} = b_{n}, přičemž pro i = 1, …, n evidentně platí

b^{i} = b_{n−i} + ∑_{j=n−i+1}^{n} b_{j} (\frac{t^{∗}}{1 − t^{∗}})^{i+j−n} \frac{(n + 1 − j) · . . . · i}{(n + 1 − i) · . . . · j} .

Totiž snadno vidíme, že opravdu b^{1} = b_{n−1} + b_{n} (\frac{t^{∗}}{1−t^{∗}}) \frac{1}{n}. Indukcí pak obdržíme

b_{n−i−1} + b^{i} (\frac{t^{∗}}{1−t^{∗}}) \frac{i + 1}{n − i}  =
b_{n−i−1} + ∑_{j=n−i+1}^{n} b_{j} (\frac{t^{∗}}{1−t^{∗}})^{i+1+j−n} \frac{(n + 1 − j) · . . . · (i + 1)}{(n + 1 − i − 1) · . . . · j} + b_{n−i} (\frac{t^{∗}}{1−t^{∗}}) \frac{i + 1}{n − i} =
b_{n−i−1} + ∑_{j=n−(i−1)+1}^{n} b_{j} (\frac{t^{∗}}{1−t^{∗}})^{(i+1)+j−n} \frac{(n + 1 − j) · . . . · (i + 1)}{(n + 1 − (i + 1)) · . . . · j}  = b^{i+1} .

Věta 2.5 Rozdělení Bézierových křivkových segmentů Každý bod b(t^{∗}), t^{∗} ∈ [0, 1], rozděluje Bézierův křivkový segment do dvou dílčích křivek. Tyto dílčí křivky jsou opět Bézierovy křivkové segmenty stejného stupně. Jejich Bézierovy body jsou určeny pomocnými body

b_{0}^{0}, b_{1}^{1}, …, b_{n}^{n}

resp.

b_{n}^{n}, b_{n}^{n−1}, …, b_{n}^{0}

Casteljauova algoritmu pro bod t^{∗}.

Důkaz. Označme c(t) Bézierův křivkový segment s Bézierovými body b_{0}^{0}, b_{1}^{1}, …, b_{n}^{n} resp. d(t) Bézierův křivkový segment s Bézierovými body b_{n}^{n}, b_{n}^{n−1}, …, b_{n}^{0}. Stačí zřejmě ověřit, že c(t) = b(tt^{∗}) a d(t) = b(t + (1 − t)t^{∗}) pro všechna t ∈ [0, 1].

Přitom máme

\begin{aligned}c(t) = ∑_{i=0}^{n} b_{i}^{i}B_{i}^{n}(t) & = & ∑_{i=0}^{n} ∑_{k=0}^{i} b_{k}B_{k}^{i}(t^{∗})B_{i}^{n}(t) \\ & = & ∑_{k=0}^{n} b_{k} ∑_{i=k}^{n} B_{k}^{i}(t^{∗})B_{i}^{n}(t). \end{aligned}

Dokažme, že pro všechna k, 0 ≤ k ≤ n

∑_{i=k}^{n}B_{k}^{i}(t^{∗})B_{i}^{n}(t) = B_{k}^{n}(tt^{∗}).

Zřejmě však

∑_{i=k}^{n} B_{k}^{i}(t^{∗})B_{i}^{n}(t) = ∑_{i=k}^{n} (\begin{matrix}i \\ k \end{matrix} )(t^{∗})^{k}(1 − t^{∗})^{i−k}(\begin{matrix}n \\ i \end{matrix})t^{i}(1 − t)^{n−i}
= (t^{∗})^{k} \frac{n!}{k!} ∑_{i=k}^{n} \frac{1}{(i − k)!(n − i)!}(1 − t^{∗})^{i−k}t^{i}(1 − t)^{n−i}
= (tt^{∗})^{k} \frac{n!}{k!(n − k)!} ∑_{i=k}^{n} \frac{(n − k)!}{(i − k)!(n − k − (i − k))!}(1 − t^{∗})^{i−k}t^{i−k}(1 − t)^{n−i}
= (tt^{∗})^{k}(\begin{matrix}n \\ k \end{matrix}) ∑_{j=0}^{n−k} (\begin{matrix}n − k \\ j \end{matrix} )(t − tt^{∗})^{j}(1 − t)^{(n−k)−j}
= (tt^{∗})^{k}(\begin{matrix}n \\ k \end{matrix})(t − tt^{∗} + 1 − t)^{n−k}
= (tt^{∗})^{k}(\begin{matrix}n \\ k \end{matrix})(1 − tt^{∗})^{n−k} = B_{k}^{n}(tt^{∗}).

Algoritmus na rozdělení Bézierových křivkových segmentů lze obdržet snadnou modifikací Casteljauova algoritmu. Konvexní obaly kontrolních bodů obou dílčích segmentů nám všeobecně poskytují lepší aproximaci než původní konvexní obal. Iterujeme-li postupně s t^{∗} = 1/2, obdržíme postupně jemnější polygoniální tah z Bézierových segmentů. V limitním přechodu pak obdržíme Bézierovu křivku.

Geometrické modelování s Bézierovým segmenty se často děje pomocí interaktivní manipulace s Bézierovými body. Za jistých podmínek se ukazuje, že požadovaný tvar je se zvoleným počtem bodů nedosažitelný. Následující věta nám ukazuje, jakým způsobem je možno přidat další kontrolní body, aniž by se nám změnila již vytvořená křivka.

Věta 2.6 Zvýšení stupně Bézierových křivkových segmentů Buď dáno n + 1 kontrolních bodů b_{0}, …, b_{n} ∈ R^{d} Bézierova křivkového segmentu. Bézierův křivkový segment s n + 2 kontrolními body b_{0}^{∗}, …, b_{n+1}^{∗} tak, že

b_{0}^{∗} := b_{0},
b_{i}^{∗} := α_{i}b_{i−1} + (1 − α_{i})b_{i}, α_{i} := i/(n + 1), i = 1, …, n,
b_{n+1}^{∗} := b_{n},

splývá s Bézierovým křivkovým segmentem o n + 1 kontrolních bodech, tj. platí

∑_{i=0}^{n}b_{i}B_{i}^{n}(t) = ∑_{i=0}^{n+1} b_{i}^{∗}B_{i}^{n+1} (t).

Důkaz. Zřejmě platí

∑_{i=0}^{n+1} b_{i}^{∗}B_{i}^{n+1} (t) =
= b_{0}^{∗}B_{0}^{n+1} (t) + ∑_{i=1}^{n} B_{i}^{n+1} (t)[α_{i}b_{i−1} + (1 − α_{i})b_{i}] + b_{n}^{∗}B_{n+1}^{n+1} (t)
= b_{0}(1 − t)^{n+1} + \frac{1}{n+1} b_{0}(\begin{matrix}n + 1 \\ 1 \end{matrix} )t(1 − t)^{n}+

∑_{i=1}^{n−1} b_{i} [\frac{i+1}{n+1} B_{i+1}^{n+1} (t) + (1 − \frac{i}{n+1} )B_{i}^{n+1} (t)] +

b_{n} [t^{n+1} + (1 − \frac{n}{n+1} )(n + 1)t^{n}(1 − t)]
= b_{0}(1 − t)^{n} [(1 − t) + t] + t^{n}b_{n} [t + (1 − t)] +

∑_{i=1}^{n−1} t^{i}(1 − t)^{n−i}b_{i} [(\begin{matrix}n \\ i \end{matrix})t + (\begin{matrix}n \\ i \end{matrix})(1 − t)]

= ∑_{i=0}^{n} b_{i}B_{i}^{n}(t).

Algoritmus na zvýšení stupně Bézierových křivkových segmentů se chová analogicky jako první krok Casteljauova algoritmu, ale s jinými, proměnnými dělícími poměry. Časová náročnost zvýšení stupně segmentu o n + 1 kontrolních bodech je O(n).

Algoritmus na zvýšení stupně Bézierových křivkových segmentů nám umožní zjistit ohraničené kolísání Bézierových křivkových segmentů. Zvolíme-li totiž posloupnost míst dotyku na libovolné křivce, pak polygoniální tah, který tímto spojením vznikne, protíná libovolnou zadanou přímku ne častěji než daná křivka. V případě Bézierových segmentů je kontrolní polygoniální tah právě zadaná křivka. Polygoniální tah vzniklý zvýšením stupně protíná podle výše zmíněného pozorování zadanou přímku ne častěji než předchozí polygoniální tah. Iterací obdrží posloupnost polygoniálních tahů, která konverguje k zadané křivce a pro kterou každý polygoniální tah neprotíná zadanou přímku častěji než jeho předchůdce.

Pomocné body vypočítané Casteljauovým algoritmem se ukázaly při rozdělení Bézierových segmentů jako užitečné. Zejména platí

Věta 2.7 Derivace Bézierových segmentů

1. \underline{Derivace:} p-tá derivace Bézierova segmentu b(t) v bodě t^{∗} je určena vztahem

\frac{d^{p}}{dt^{p}} b(t^{∗}) = \frac{n!}{(n − p)!} ∑_{i=0}^{n−p}Δ^{p}b_{i} · B_{i}^{n−p}(t^{∗}) = \frac{n!}{(n − p)!}Δ^{p}b_{n−p}^{n−p},

kde

Δ^{0}b_{i} := b_{i},
Δ^{p}b_{i} := Δ^{p−1}b_{i+1} − Δ^{p−1}b_{i}, i = 0, …, n − p,
Δ^{0}b_{i}^{j}(t^{∗}) := b_{i}^{j}(t^{∗}),
Δ^{p}b_{i}^{j}(t^{∗}) := Δ^{p−1}b_{i+1}^{j} (t^{∗}) − Δ^{p−1}b_{i}^{j}(t^{∗}), i = j, …, n − p.

Přitom jsou b_{i}^{j}(t^{∗}) pomocné body vypočítané Casteljauovým algoritmem v bodě t^{∗}.

2. \underline{Vyšší derivace v koncových bodech:}p-té derivace v koncových bodech jsou zadány vztahy

\frac{d^{p}}{dt^{p}} b(0) = \frac{n!}{(n − p)!}Δ^{p}b_{0},
\frac{d^{p}}{dt^{p}} b(0) = \frac{n!}{(n − p)!}Δ^{p}b_{n−p},

a závisí tímto pouze na b_{0}, …, b_{p} případně b_{n−p}, …, b_{n}.

3.

Bézierovy body jakožto funkce derivací v koncových bodech:

b_{i} = ∑_{k=0}^{i} (\begin{matrix}i \\ k \end{matrix} )\frac{n!}{(n − p)!} \frac{d^{k}}{dt^{k}} b(0)

= ∑_{k=0}^{n−i}(−1)^{k}(\begin{matrix}n − i \\ k \end{matrix})\frac{(n − k)!}{n!} \frac{d^{k}}{dt^{k}} b(1).

Důkaz. Pro p = 0 máme

\frac{d^{0}}{dt^{0}}b(t) = b(t) = ∑_{i=0}^{n}b_{i}B_{i}^{n}(t)
= ∑_{i=0}^{n}Δ^{0}b_{i} · B_{i}^{n}(t).

Důkaz pro derivace vyššího stupně plyne indukcí vůči p. Druhou rovnost lze obdržet v důsledku záměnnosti Δ^{p} se sumací.

Derivace v koncových bodech obdržíme po dosazení do bodu 1. Třetí tvrzení lze obdržet po dosazení výrazů z bodu 1.

Další výhodou je, že můžeme z pomocných bodů b_{i}^{j} zjistit derivace v bodě t^{∗}. Platí například b′(t^{∗}) = n · (b_{n}^{n−1}(t^{∗}) − b_{n−1}^{n−1}(t^{∗})).

Věta 2.8 Integrování Bézierových segmentů Integrál Bézierova segmentu je opět Bézierův segment se stupněm o jednotku vyšším. Můžeme přitom nové Bézierovy body psát jako lineární kombinaci původních:

∫ b(t)dt = ∫ b_{0}B_{0}^{n}(t) + … + b_{n}B_{n}^{n}(t)dt
= b_{0}^{∗}B_{0}^{n+1} (t) + … + b_{n+1}^{∗} B_{n+1}^{n+1} (t),

kde b_{0}^{∗} je integrační konstanta a platí

b_{i}^{∗} := \frac{1}{n + 1} · ∑_{j=0}^{i−1}b_{j} + b_{0}^{∗}, i = 1, …, n + 1.

Určitý integrál určený celým segmentem je pak těžiště

∫_{0}^{1} b(t)dt = \frac{1}{n + 1} (b_{0} + b_{1} + … + b_{n})

Bézierových bodů.

Důkaz. Viz cvičení.

3 Racionální křivky

Při modelování vzniká často nutnost aplikovat na křivky určité transformace. Například jde o vzájemný posun dvou segmentů podle předem určeného vzoru. Často používané transformace jsou lineární nebo afinní zobrazení.

Definice. Afinní zobrazení bodu p do bodu \overline{p} je tvaru:

\overline{p} = Ap + t,

přičemž A je matice typu d × d, t ∈ R^{d} a p, \overline{p} ∈ R^{d}. Speciální případy v R^{2}:

• Translace:

\overline{p} = (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) · p + t,

• Změna měřítka:

\overline{p} = (\begin{matrix}a & 0 \\ 0 & b \end{matrix}) · p,

• Rotace:

\overline{p} = (\begin{matrix}cosϕ & − sinϕ \\ sinϕ & cosϕ \end{matrix}) · p.

Afinní obraz \overline{k}(t) křivky k(t) v afinním zobrazení \overline{p} = Ap + t je definován jako \overline{k}(t) = Ak(t) + t. Lze dokázat, že, aplikujeme-li afinní zobrazení na kontrolní body Bézierova křivkového segmentu a pak z nich sestrojím křivkový segment, dostaneme totéž, jako když na Bézierův křivkový segment aplikujeme výše uvedené afinní zobrazení.

Věta 3.1 Afinní transformace Bézierových křivkových segmentů Buď \overline{p} = Ap + t afinní zobrazení, b(t) = b_{0}B_{0}^{n}(t) + … + b_{n}B_{n}^{n}(t) Bézierův křivkový segment, \overline{b}(t) jeho afinní transformace v zadaném zobrazení. Pak je

\overline{b}(t) = \overline{b}_{0}B_{0}^{n}(t) + … + \overline{b}_{n}B_{n}^{n}(t),

kde

\overline{b}_{i} = Ab_{i} + t

Důkaz. Dosazením.

Obtížnější je ale případ projekce:

Definice. Perspektivistická projekce v normálním tvaru je zobrazení

\overline{p} = \frac{(\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) · p}{(0 0 1) · p}, p ∈ R^{3}, \overline{p} ∈ R^{2},

to znamená, že projekce je provedena vzhledem k počátku jako dohlednému bodu na rovinu z = 1.

Vzhledem k projekci v normálním tvaru se třírozměrný Bézierův křivkový segment b(t) = b_{0}B_{0}^{n}(t) + … + b_{n}B_{n}^{n}(t) zobrazí na

\overline{b}(t) = \frac{b̂_{0}B_{0}^{n}(t) + … + b̂_{n}B_{n}^{n}(t)}{b̂_{0}B_{0}^{n}(t) + … + b̂_{n}B_{n}^{n}(t)} ,

přičemž b̂_{i} jsou utvořeny z prvních dvou složek b_{i} a b̂_{i} z poslední složky. Tato křivka není obecně polynomiální křivka a proto ji nelze reprezentovat jak Bézierův křivkový segment. Používání lomených racionálních funkcí místo polynomů nám dopomůže k nápravě.

Definice. Lomená racionální funkce d proměnných je definována vztahem

r(x_{1}, x_{2}, …, x_{d}) = \frac{p(x_{1}, x_{2}, …, x_{d})}{q(x_{1}, x_{2}, …, x_{d})},

přičemž p a q jsou polynomy v d proměnných.

Mnoho výhodných vlastností polynomů platí rovněž pro lomené racionální funkce. Obdržíme pak

Definice. Racionální křivkový segment v R^{d} je určen vztahem

r(t) = \frac{a_{0}t^{0} + … + a_{n}t^{n}}{α_{0}t^{0} + … + α_{n}t^{n}} , a_{i} ∈ R^{d}, α_{i} ∈ R, t ∈ [0, 1].

Racionální Bézierův křivkový segment v R^{d} je definován pomocí vztahu

b(t) = \frac{β_{0}b_{0}B_{0}^{n}(t) + … + β_{n}b_{n}B_{n}^{n}(t)}{β_{0}B_{0}^{n}(t) + … + β_{n}B_{n}^{n}(t)} , b_{i} ∈ R^{d}, β_{i} ∈ R, β_{i} > 0, t ∈ [0, 1].

Koeficienty b_{i} jsou opět kontrolní body. Každému kontrolnímu bodu je navíc přiřazena váha β_{i}. Váha β_{i} ovládá atraktivitu kontrolního bodu.

Můžeme racionální Bézierovy křivkové segmenty v R^{d} považovat za perspektivistickou projekci obyčejných Bézierových křivkových segmentů v R^{d+1} , přičemž se bude promítat vzhledem k počátku do roviny x_{d+1} = 1. Pro racionální Bézierův křivkový segment b(t) definujeme Bézierův křivkový segment b^{∗}(t) jakožto

b^{∗}(t) = (\begin{matrix}b̂(t) \\ β(t) \end{matrix}) := ∑_{j=0}^{n} (\begin{matrix}β_{j}b_{j} \\ β_{j} \end{matrix} )B_{j}^{n}(t).

b^{∗}(t) má tedy Bézierovy body (\begin{matrix}β_{j}b_{j} \\ β_{j} \end{matrix} ) a přechází vzhledem ke zmíněné perspek-

tivistické projekci do b(t).

Množina racionálních Bézierových segmentů je uzavřená vzhledem k perspektivistické projekci.

Možnost reprezentace racionálních Bézierových segmentů jako projekce obyčejných Bézierových segmentů má za důsledek, že lze známé vlastnosti pro Bézierovy segmenty přenést na racionální Bézierovy segmenty:

Věta 3.2 Vlastnosti racionálních Bézierových křivkových segmentů

1. \underline{Chování v koncových bodech:}Kontrolní polygon a křivkový segment mají stejný počáteční a koncový bod. První a poslední segment kontrolního polygonu je tečný ke křivce. Ostatní Bézierovy bodu nejsou interpolovány, pouze aproximovány.

2. \underline{Vlastnost konvexního obalu}Křivkový segment leží v konvexním obalu Bézierových bodů. Zejména tedy leží i v konvexním obalu Bézierova polygoniálního tahu.

3. \underline{Vliv kontrolních bodů}b_{i} má největší vliv na b(t) v případě, že t = i/n.

4. \underline{Omezené kolísání}Pro kladné váhy žádná přímka neprotíná racionální Bézierův křivkový segment častěji než odpovídající Bézierův polygoniální tah (variation diminishing property).

Důkaz. Bezprostředně projekcí Bézierova křivkového segmentu v R^{d+1} .

Připustíme-li i záporné váhy β_{i}, ztratíme částečně výše uvedené vlastnosti. Zároveň lze bez problémů převést dřívější algoritmy pro racionální segmenty. Algoritmus se provede pro obyčejný Bézierův segment v R^{d+1} a následně se uskuteční projekce. Tento postup je možný pro de-Casteljauův algoritmus, dělení, zvýšení stupně a derivaci.

Stejně jako u obyčejných Bézierových segmentů se racionální Bézierův segment rozdělí do dvou dílčích křivek bodem b(t^{∗}). Dílčí křivky jsou pak racionální Bézierovy segmenty stejného stupně. Bézierovy body a váhy získáme z vnitřních pomocných bodů Casteljauova algoritmu pro bod t = t^{∗}. Pro první dílčí křivku jsou to

b_{0}^{0}, b_{1}^{1}, …, b_{n}^{n},
β_{0}^{0}, β_{1}^{1}, …, β_{n}^{n},

a pro druhou dílčí křivku jsou to

b_{n}^{n}, b_{n}^{n−1}, …, b_{n}^{0},
β_{n}^{n}, β_{1}^{n−1}, …, β_{n}^{0}.

Stejně jako obyčejné Bézierovy segmenty lze reprezentovat racionální Bézierovy segmenty o n + 1 Bézierových bodech beze změny tvaru křivky jako racionální Bézierovy segmenty o n + 2 Bézierových bodech. Nové Bézierovy body a váhy lze získat jako konvexní kombinaci dvou starých Bézierových bodů popř. vah:

\begin{aligned}b(t) & = & \frac{β_{0}b_{0}B_{0}^{n}(t) + … + β_{n}b_{n}B_{n}^{n}(t)}{β_{0}B_{0}^{n}(t) + … + β_{n}B_{n}^{n}(t)} \\ & = & \frac{β_{0}^{∗}b_{0}^{∗}B_{0}^{n+1} (t) + … + β_{n+1}^{∗} b_{n}B_{n+1}^{n+1} (t)}{β_{0}B_{0}^{n+1} (t) + … + β_{n}^{∗}B_{n+1}^{n+1} (t)} , \end{aligned}

s novými Bézierovy body a váhami

b_{i}^{∗} = b_{i}^{1} · (\frac{n + 1 − i}{n + 1} ) , i = 1, …, n, b_{0}^{∗} = b_{0}^{0}, b_{n+1}^{∗} = b_{n}^{0},

β_{i}^{∗} = β_{i}^{1} · (\frac{n + 1 − i}{n + 1} ) , i = 1, …, n, β_{0}^{∗} = β_{0}^{0}, β_{n+1}^{∗} = β_{n}^{0},

Racionální Bézierovy segmenty nám na rozdíl od obyčejných Bézierovových segmentů dovoluje modelovat kuželové řezy. Přesná reprezentace takovýchto křivek s obyčejnými Bézierovými segmenty není možné.

Věta 3.3 Racionálních reprezentace kuželových řezů Buďte β_{0} = β_{1} = 1. Pak racionální Bézierův segment stupně dva tvaru

b(t) = \frac{β_{0}b_{0}B_{0}^{2}(t) + β_{1}b_{1}B_{1}^{2}(t) + β_{2}b_{2}B_{2}^{2}(t)}{β_{0}B_{0}^{2}(t) + β_{1}B_{1}^{2}(t) + β_{2}B_{2}^{2}(t)}

je

• Elipsovitý segment, pokud β_{1} < 1,

• Parabolický segment, pokud β_{1} = 1,

• Hyperbolický segment, pokud β_{1} > 1.

Důkaz. Cvičení.

4 Plochy

Bézierovy techniky se dají jednoduše přenést na plochy. Namísto jednodimenzionálního kontrolního polygoniálního tahu se používají dvoudimenzionální kontrolní sítě. Kontrolní síť je kombinatoricky vzato pravidelná mříž, jejíž počet bodů určuje polynomiální stupeň výsledné plochy. Přitom se používají mříže s ohraničením o třech resp. čtyřech vrcholech. V dalším nejprve popíšeme čtyřúhelníkové Bézierovy segmenty, následovně trojúhelníkové Bézierovy segmenty.

4.1 Čtyřúhelníkové Bézierovy segmenty

Kontrolní síť čtyřúhelníkového Bézierovova segmentu je určena (n + 1) · (m + 1) Bézierovými kontrolními body b_{i,j}, i = 0, …, n, j = 0, …, m. Dva Bézierovy b_{i,j}, b_{k,l} body jsou spojeny hranou, pokud (i, j) = (k ± 1, l) nebo (i, j) = (k, l ± 1).

Definice. Čtyřúhelníkový Bézierův segment v R^{3} je tvaru:

b(u, v) := ∑_{i=0}^{n} ∑_{j=0}^{m}b_{i,j} · B_{i}^{n}(u) · B_{j}^{m}(v), u, v ∈ [0, 1], b_{i,j} ∈ R^{3}.

Mnoho vlastností Bézierových křivkových segmentů lze přenést na čtyřúhelníkové Bézierovy segmenty. Uvážíme-li vnitřní součty

b_{i}(v) := ∑_{j=0}^{m}b_{i,j} · B_{j}^{m}(v), i = 0, …, n,

obdržíme systém Bézierovových segmentů v prostoru. Zejména pak

b(u, v) = ∑_{i=0}^{n}b_{i}(v) · B_{i}^{n}(u).

Pro pevnou hodnotu v = v^{∗} se opět jedná o Bézierův segment, který má kontrolní body b_{i}(v^{∗}), i = 0, …, n. Bod b(u^{∗}, v^{∗}) lze spočítat tak, že nejprve zjistíme použitím Casteljauova algoritmu na kontrolní polygoniální tahy b_{i,j}, j = 0, …, m a v = v^{∗} bod b_{i}(v^{∗}). Na kontrolní polygoniální tah b_{i}(v^{∗}), i = 0, …, n opětovně aplikujeme Casteljauův algoritmus pro u = u^{∗}. Výsledkem je hledaný bod roviny b(u^{∗}, v^{∗}).

Algoritmus. (de Casteljau, pro čtyřúhelníkové Bézierovy segmenty) Vstup: (n + 1) · (m + 1) Bézierových kontrolních bodů b_{i,j}, i = 0, …, n, j = 0, …, m, u^{∗}, v^{∗} ∈ [0, 1]. Výstup: Bod roviny b(u^{∗}, v^{∗}) určený Bézierovými kontrolními body b_{i,j}, i = 0, …, n, j = 0, …, m. Postup:

\underline{4. PLOCHY 37}

1. Spočtěme c_{i} := ∑_{j=0}^{m} b_{i,j} · B_{j}^{m}(v^{∗}), i = 0, …, n, podle Casteljauova algoritmu, i = 0, …, n.

2. Spočtěme b(u^{∗}, v^{∗}) = ∑_{i=0}^{n} c_{i} · B_{i}^{n}(u^{∗}).

Z výše uvedeného pak máme následující tvrzení:

Věta 4.1 Vlastnosti čtyřúhelníkových Bézierových segmentů

1. \underline{Vlastnost konvexního obalu:}Body b(u, v) leží v konvexním obalu definujících Bézierových bodů.

2. \underline{Vliv kontrolních bodů:}Bézierův bod b_{i,j} má největší vliv na segment b(u, v) v případě, že (u, v) = (i/n, j/n).

3. \underline{Chování v okrajových křivkách:}Okrajové body kontrolní sítě jsou Bézierovy body hraničních křivek rovinného segmentu.

4. \underline{Planarita:} Bézierova rovinná část je rovina právě tehdy, když Bézierova kontrolní část tvoří rovinnou mřížku.

5. \underline{Plochové křivky:}Obraz přímky v rovině určené u − v na ploše je polynomiální křivka stupně nejvýše m + n.

Důkaz. Cvičení.

Tvrzení o omezeném kolísání nelze bezprostředně převést z křivek na plochy. Není totiž obtížné zadat kontrolní síť a přímku tak, že rovina je přímkou protnuta, nikoliv však kontrolní síť.

Časová náročnost de Casteljauova algoritmu pro čtyřúhelníkové Bézierovy segmenty je O(m^{2} · n + n^{2}), pokud postupujeme nejprve v m−směru a pak v n−směru. Přirozeně lze však vyhodnocení provést pomocí Hornerova schematu. Časová náročnost je pak O(m · n + n). Casteljauův algoritmus pro čtyřúhelníkové Bézierovy segmenty lze použít stejně jako pro křivky na rovinné rozdělení:

Věta 4.2 Rozdělení čtyřúhelníkových Bézierových segmentů Buďte b_{i,j}^{k} body, které obdržíme Casteljauovým algoritmem pro křivky b_{i}(v) := ∑_{j=0}^{n} b_{i,j}B_{j}^{m}(v) při volbě v = v^{∗}. Čtyřúhelníkové Bézierovy segmenty

b_{l}(u, v) := ∑_{i=0}^{n} ∑_{j=0}^{m}b_{i,j}^{j} · B_{i}^{n}(u) · B_{j}^{m}(v), u, v ∈ [0, 1],

b_{r}(u, v) := ∑_{i=0}^{n} ∑_{j=0}^{m}b_{i,j}^{m−j} · B_{i}^{n}(u) · B_{j}^{m}(v), u, v ∈ [0, 1],

rozkládají segment

b(u, v) := ∑_{i=0}^{n} ∑_{j=0}^{m}b_{i,j} · B_{i}^{n}(u) · B_{j}^{m}(v)

do dvou dílčích segmentů podél křivky b(u, v^{∗}).

Důkaz. Plyne bezprostředně z odpovídající věty pro Bézierovy křivky.

Také zde vede iterativní dělení k posloupnosti sítí, která konverguje k ploše. Protože pro dílčí segmenty platí rovněž vlastnost konvexního obalu, lze konstruovat rozdělení plochy s požadovanou přesností.

Abychom získali jemnější kontrolu Bézierovy plochy, lze zvýšit počet kontrolních bodů, aniž se sama plocha změní. Tento postup je založen na zvýšení stupně Bézierových křivkových segmentů. Abychom opět získali kontrolní body čtyřúhelníkové sítě, musíme zvýšit počet řádků resp. počet sloupců o jednotku. Za tímto účelem pro pevné i = i^{∗} uvažujeme b_{i^{∗},j} jako kontrolní body Bézierova segmentu a provedeme pro ně zvýšení stupně. To postupně provedeme pro i^{∗} = 0, …, n. Hodnota m se přitom zvýší o jednotku.

Věta 4.3 Zvýšení stupně čtyřúhelníkových Bézierových segmentů Buď dáno (n + 1) · (m + 1) kontrolních bodů b_{0,0}, …, b_{n,m} ∈ R^{3} čtyřúhelníkového Bézierova segmentu. Čtyřúhelníkový Bézierův segment s (n + 1) · (m + 2) kontrolními body b_{0,0}^{∗}, …, b_{n,m+1}^{∗} tak, že

b_{i,0}^{∗} := b_{i,0},
b_{i,j}^{∗} := α_{j}b_{i,j−1} + (1 − α_{j})b_{i,j}, α_{j} := j/(m + 1), j = 1, …, m,
b_{i,m+1}^{∗} := b_{i,m},

splývá s čtyřúhelníkovým Bézierovým segmentem o (n+1)·(m+1) kontrolních bodech, tj. platí, že plocha

b(u, v) := ∑_{i=0}^{n} ∑_{j=0}^{m}b_{i,j} · B_{i}^{n}(u) · B_{j}^{m}(v)

je totožná s plochou

b^{∗}(u, v) := ∑_{i=0}^{n} ∑_{j=0}^{m+1} b_{i,j}^{∗} · B_{i}^{n}(u) · B_{j}^{m+1} (v).

Důkaz. Plyne bezprostředně z odpovídající věty pro Bézierovy křivky.

4.2 Trojúhelníkové Bézierovy segmenty

V praxi se často vyskytují rovinné části, které nelze pomocí kontrolních bodů čtyřúhelníkové sítě přirozeně modelovat. V těchto případech lze použít rovinné části, které jsou definovány pomocí kontrolních bodů trojúhelníkové sítě. Kontrolní síť trojúhelníkových kontrolních segmentů je určena pomocí (n + 1) · (n + 2)/2 Bézierových kontrolních bodů b_{i,j,k}, 0 ≤ i, j, k, i + j + k = n. Dva Bézierovy body b_{i,j,k}, b_{p,q,r} jsou spojeny hranou sítě, pokud (i, j, k) = (p ± 1, q ± 1, r) nebo (i, j, k) = (p, q ± 1, r ± 1) nebo (i, j, k) = (p ± 1, q, r ± 1).

Pro n = 3 obdržíme například trojúhelník

030

021 120
012 111 210
003 102 201 300.

Definice. Trojúhelníkový Bézierův segment v R^{3} je tvaru:

b(u, v) := ∑ ; \begin{matrix}i, j, k ≥ 0 \\ i + j + k = n \end{matrix} b_{i,j,k} · B_{i,j,k}^{n}(u, v, 1 − u − v),

u, v ∈ [0, 1], u + v ≤ 1, b_{i,j,k} ∈ R^{3},

kde B_{i,j,k}^{n}(x, y, z) jsou zobecněné Bernsteionovy polynomy tvaru

B_{i,j,k}^{n}(x, y, z) := \frac{n!}{i!j!k!}x^{i}y^{j}z^{k},

0 ≤ i, j, k, i + j + k = n, 0 ≤ x, y, z ≤ 1, x + y + z = 1.

Trojúhelníkový tvar má rovněž obor parametru (u, v): 0 ≤ u, v, u + v ≤ 1. Zobecněné Bernsteinovy polynomy, které slouží jako váhové funkce pro Bézierovy body, mají nejdůležitější vlastnosti obyčejných Bernsteinových polynomů:

Věta 4.4 Vlastnosti Bernsteinových polynomů

1. \underline{Rozklad jednotky:}Součet zobecněných Bernsteinových polynomů stupně n je 1:

n ; ∑ ; \begin{matrix}i, j, k ≥ 0 \\ i + j + k = n \end{matrix} B_{i,j,k}^{n}(x, y, z) = 1.

pro 0 ≤ x, y, z ≤ 1, x + y + z = 1.

2. \underline{Pozitivita:} Zobecněné Bernsteinovy polynomy jsou v množině S_{3} = \{(u, v, 1 − u − v) : 0 ≤ u, v, u + v ≤ 1} nezáporné:

B_{i,j,k}^{n}(x, y, z) ≥ 0, (x, y, z) ∈ S_{3}.

3. \underline{Maximum:} B_{i,j,k}^{n}(x, y, z) nabývá svého maxima v množině S_{3} v bodě (\frac{i}{n}, \frac{j}{n}, \frac{k}{n}), i, j, k ≥ 0, i + j + k = n.

4. \underline{Rekurze:} Pro i, j, k ≥ 0, i + j + k = n platí

B_{i,j,k}^{n}(x, y, z) = xB_{i−1,j,k}^{n−1}(x, y, z) + yB_{i,j−1,k}^{n−1}(x, y, z) + zB_{i,j,k−1}^{n−1}(x, y, z).

Je tedy Bernsteinův polynom stupně n konvexní kombinací tří Bernsteinových polynomů stupně n − 1.

Důkaz. Snadné cvičení.

Věta 4.5 Vlastnosti trojúhelníkových Bézierových segmentů

1. \underline{Vlastnost konvexního obalu:}Body b(u, v) leží v konvexním obalu definujících Bézierových bodů, zejména tedy v konvexním obalu kontrolní sítě.

2. \underline{Chování v hraničních křivkách:}Okrajové křivky rovinného segmentu jsou Bézierovy segmenty.

3. \underline{Plochové křivky:}Obraz přímky v rovině určené u − v na ploše je polynomiální křivka stupně nejvýše n.

Důkaz. Cvičení.

Názornější než formální definice je Casteljauův algoritmus pro trojúhelníkové Bézierovy segmenty. Ten pak počítá stále se zmenšující trojúhelníkové sítě řádu n − 1, n − 2, …, 0. Poslední síť odpovídá bodu plochy. Korektnost algoritmu spočívá stejně jako pro Bézierovy segmenty na rekurzivitě zobecněných Bernsteinových polynomů.

Algoritmus. (de Casteljau, pro trojúhelníkové Bézierovy segmenty)

Vstup: Bézierovy body b_{i,j,k}, i, j, k ≥ 0, i + j + k = n, parametrická hodnota (u^{∗}, v^{∗}).

Výstup: Bod křivky b(u^{∗}, v^{∗}).

Postup:

FOR i := 0 TO n DO b_{i}^{0} := b_{i}; FOR j := 1 TO n − i DO BEGIN k := n − i − j; b_{i,j,k}^{0} := b_{i,j,k} END; FOR l := 1 TO n DO FOR i := 1 TO n − l DO FOR j := 1 TO n − l − i DO BEGIN k := n − l − i − j; b_{i,j,k}^{l} := u^{∗} · b_{i+1,j,k}^{l−1} + v^{∗} · b_{i,j+1,k}^{l−1} + (1 − u^{∗} − v^{∗}) · b_{i,j,k+1}^{l−1} END b(u^{∗}, v^{∗}) := b_{n}^{0,0,0} END.

Pro pomocné body b_{i,j,k}^{l} platí

b_{i,j,k}^{l} = ∑_{i^{∗}+j^{∗}+k^{∗}=l} b_{i+i^{∗},j+j^{∗},k+k^{∗}}^{0} · B_{i^{∗},j^{∗},k^{∗}}^{l}(u^{∗}, v^{∗}, 1 − u^{∗} − v^{∗}),

což se snadno ukáže indukcí vzhledem l. V indukčním kroku se použije rekurentní formule pro zobecněné Bernsteinovy polynomy. Pro l = n pak máme, že b_{0,0,0}^{n} je hledaný bod plochy. Odtud pak dostáváme korektnost Casteljauova algoritmu. Časová náročnost algoritmu je O(n^{3}). Paměťová náročnost je omezena O(n^{2}), protože pro pevnou hodnotu l musí být v paměti obsaženy pouze pomocné body b_{i,j,k}^{l} a b_{i,j,k}^{l−1}. Někdy je vhodné použít Hornerovo schema.

Věta 4.6 Rozdělení trojúhelníkových Bézierových segmentů Množinu u − vparametrů uvažovanou jako trojúhelník [(0, 0), (0, 1), (1, 0)] lze pomocí pevně zvoleného parametru (u^{∗}, v^{∗}) rozložit na tři trojúhelníky tak, že postupně jej spojíme s vrcholy (0, 0), (0, 1), (1, 0). Část plochy nad každým z těchto trojúhelníků lze opět reprezentovat jako trojúhelníkový Bézierův segment. Bézierovy body těchto dílčích ploch vzniknou z pomocných bodů, jež lze spočítat použitím Casteljauova algoritmu na bod (u^{∗}, v^{∗}), a sice podle následujícího schématu.

• Pro trojúhelník [(0, 0), (u^{∗}, v^{∗}), (0, 1)] obdržíme kontrolní body b_{0,j,n−i−j}^{i}, 0 ≤ i ≤ n, 0 ≤ j ≤ n − i.

• Pro trojúhelník [(0, 0), (u^{∗}, v^{∗}), (1, 0)] obdržíme kontrolní body b_{n−i−j,j,0}^{i}, 0 ≤ i ≤ n, 0 ≤ j ≤ n − i.

• Pro trojúhelník [(0, 1), (u^{∗}, v^{∗}), (1, 0)] obdržíme kontrolní body b_{j,0,n−i−j}^{i}, 0 ≤ i ≤ n, 0 ≤ j ≤ n − i.

Důkaz. Cvičení.

Věta 4.7 Zvýšení stupně trojúhelníkových Bézierových segmentů Buď dáno (n + 1) · (n + 2)/2 kontrolních bodů b_{i,j,k} ∈ R^{3}, 0 ≤ i ≤ n, 0 ≤ j ≤ n − i, k = n − i − j trojúhelníkového Bézierova segmentu řádu n. Trojúhelníkový Bézierův segment řádu n + 1 s novými (n + 2) · (n + 3)/2 kontrolními body b_{i,j,k}^{∗} ∈ R^{3}, 0 ≤ i ≤ n + 1, 0 ≤ j ≤ n + 1 − i, k = n + 1 − i − j tak, že

b_{i,j,k}^{∗} := \frac{1}{n + 1} (i · b_{i−1,j,k} + j · b_{i,j−1,k} + k · b_{i,j,k−1}) ,

splývá s trojúhelníkovým Bézierovým segmentem o (n + 1) · (n + 2)/2 kontrolních bodech, tj. platí, že plocha

b(u, v) := ∑ ; \begin{matrix}i, j, k ≥ 0 \\ i + j + k = n \end{matrix} b_{i,j,k} · B_{i,j,k}^{n}(u, v, 1 − u − v)

je totožná s plochou

b^{∗}(u, v) := ∑ ; \begin{matrix}i, j, k ≥ 0 \\ i + j + k = n + 1 \end{matrix} b_{i,j,k}^{∗} · B_{i,j,k}^{n+1} (u, v, 1 − u − v).

Důkaz. Cvičení.

4.3 Racionální plošné Bézierovy segmenty

Převedením racionální reprezentace křivek na případ ploch obdržíme

Definice. Racionální čtyřúhelníkový Bézierův segment v R^{3} je tvaru:

b(u, v) := \frac{∑_{i=0}^{n} ∑_{j=0}^{m} β_{i,j}b_{i,j} · B_{i}^{n}(u) · B_{j}^{m}(v)}{∑_{i=0}^{n} ∑_{j=0}^{m} β_{i,j} · B_{i}^{n}(u) · B_{j}^{m}(v)}

u, v ∈ [0, 1], β_{i,j} ≥ 0, b_{i,j} ∈ R^{3}.

Kontrolní síť čtyřúhelníkového Bézierovova segmentu je určena (n + 1) · (m + 1) Bézierovými kontrolními body b_{i,j} a jejich vahami β_{i,j} ≥ 0, i = 0, …, n, j = 0, …, m.

Definice. Racionální trojúhelníkový Bézierův segment v R^{3} je tvaru:

b(u, v) := \frac{∑_{i+j+k=n} β_{i,j,k}b_{i,j,k} · B_{i,j,k}^{n}(u, v, 1 − u − v)}{∑_{i+j+k=n} β_{i,j,k} · B_{i,j,k}^{n}(u, v, 1 − u − v)},

β_{i,j,k} ≥ 0, u, v ∈ [0, 1], u + v ≤ 1, b_{i,j,k} ∈ R^{3}.

Racionální Bézierův segment lze chápat jako perspektivistickou projekci Bézierova

segmentu v R^{4} vzhledem ke kontrolním bodům (\begin{matrix}β_{i,j}b_{i,j} \\ β_{i,j} \end{matrix} ) na rovinu x_{4} = 1. Známé

vlastnosti Bézierových segmentů jako jsou vlastnost konvexního obalu a rovněž ostatní obvyklé algoritmy lze proto přímo převést na racionální Bézierovy plošné segmenty. Pro záporné volby se tyto vlastnosti částečně nezachovávají.

5 Vyšší dimenze

Jak čtyřúhelníková tak trojúhelníková konstrukce se dají zobecnit do vyšších dimenzí:

Definice. d-dimenzionální čtyřúhelníkový Bézierův segment v R^{m} je tvaru:

x(u_{1}, …, u_{d}) := ∑_{i_{1}=0}^{n_{1}} ∑_{i_{2}=0}^{n_{2}} … ∑_{i_{d}=0}^{n_{d}} b_{i_{1},i_{2},...,i_{d}} · B_{i_{1}}^{n_{1}}(u_{1}) · B_{i_{2}}^{n_{2}}(u_{2}) . . . · B_{i_{d}}^{n_{d}}(u_{d}),

u_{1}, u_{2}, …, u_{d} ∈ [0, 1], n_{1}, n_{2}, …, n_{d} ∈ N.

Kontrolní síť čtyřúhelníkového Bézierovova segmentu je určena (n + 1) · (m + 1) Bézierovými kontrolními body b_{i,j} a jejich vahami β_{i,j} ≥ 0, i = 0, …, n, j = 0, …, m.

Definice. d-dimenzionální trojúhelníkový Bézierův segment v R^{m} je tvaru:

x(u_{0}, …, u_{d}) := ∑_{i_{0}+i_{1}+...+i_{d}=n} b_{i_{0},i_{1},...,i_{d}} · B_{i_{0},i_{1},...,i_{d}}(u_{0}, u_{1}, …, u_{d}),

u_{0}, u_{1}, …, u_{d} ∈ [0, 1], u_{0} + u_{1} + … + u_{d} = 1, b_{i,j,k} ∈ R^{m},

kde B_{i_{0},i_{1},...,i_{d}}(u_{0}, u_{1}, …, u_{d}) jsou zobecněné Bernsteionovy polynomy tvaru

B_{i_{0},i_{1},...,i_{d}}(u_{0}, u_{1}, …, u_{d}) := \frac{n!}{i_{0}!i_{1}! … i_{d}!}u_{0}^{i_{0}}u_{1}^{i_{1}} … u_{d}^{i_{d}},

0 ≤ i_{0}, i_{1}, …, i_{d}, i_{0} + i_{1} + … + i_{d} = n.

Algoritmy platné pro plochy lze dokázat podobně dokázat také pro tyto formy. Mimoto lze navíc vytvořit hybridní d−dimenzionální segmenty, kde namísto křivek lze použít d_{i}-dimenzionální trojúhelníkové Bézierovy segmenty.

44  Bézierova metoda

Kritéria kvality

Bézierova metoda představuje názorný a účinný nástroj zejména pro interaktivní modelování křivek a ploch. Modelování takovýchto forem se děje obecně s estetickými nebo technickými zadanými úkoly. Technické zadané úkoly jsou např. minimalizace odporu vzduchu nebo maximalizace tuhosti. Takovéto úkoly lze geometricky vyjádřit pomocí výroků jako ţkřivka nemá být rozkolísaná�, ţplocha nemá být vyboulená�. Tyto lze pak přesně vyjádřit pomocí pojmů diferenciální geometrie jako jsou křivost a torze. V následujícím zavedeme nejdůležitější pojmy diferenciální geometrie. Dále uvedeme postupy sloužící ke grafickému vyjádření těchto veličin, jež nám umožní rychlé vizuální posouzení kvality navrženého tvaru.

1 Implicitní vyjádření

V předcházející kapitole jsme uvažovali křivky a plochy v parametrické reprezentaci. Mimo to, diferenciální geometrie používá jiný způsob vyjádření, tzv. implicitní vyjádření.

Definice. Implicitní vyjádření křivky v R^{2} (rovinné křivy) je nulová množina funkce F, tj.

F (x, y) = 0 pro F : R^{2} → R.

Implicitní vyjádření plochy v R^{3} je nulová množina funkce F, tj.

F (x, y, z) = 0 pro F : R^{3} → R.

Implicitní vyjádření křivky v R^{3} je průnik dvou implicitně definovaných ploch určených funkcemi F a G, tj.

F (x, y, z) = 0, G(x, y, z) = 0 pro F, G : R^{3} → R.

46  Kritéria kvality

Příklad implicitně definované křivky v rovině je

x^{3} − y^{3} = 0.

Přímka v prostoru je implicitně průnik dvou (různých) rovin, např.

y + 5x + 6 = 0, z + 8x + 7 = 0.

Jednotková koule má implicitní reprezentaci

x^{2} + y^{2} + z^{2} = 1.

Důležitým případem implicitně reprezentovatelných křivek jsou kuželosečky. Kuželosečku obdržíme jako průnik roviny s kuželem. Rozlišujeme tři základní typy: elipsa, hyperbola a parabola. V normálním tvaru mají následující reprezentaci:

• elipsa x^{2}/a^{2} + y^{2}/b^{2} = 1,

• hyperbola x^{2}/a^{2} − y^{2}/b^{2} = 1,

• parabola y^{2} = 2px. Obecně lze kuželové řezy popsat pomocí rovnic tvaru

a · x^{2} + b · y^{2} + c · x · y + d · x + e · y + f.

Koule je příklad kvadriky. Kvadriky jsou plochy v prostoru odpovídající kuželovým řezům v rovině. Získáme je jako nulové množiny rovností tvaru

a · x^{2} + b · y^{2} + c · z^{2} + d · x · y + e · x · z + f · y · z + g · x + h · y + i · z + j = 0, tj. tyto se reprezentují pomocí kvadratické rovnosti, z čehož vzniklo jejich jméno. Počet typů je mnohonásobně větší než pro kuželové řezy:

• Kužel:

• Dvojdílný hyperboloid:

• Jednodílný hyperboloid:

• Elipsoid:

• Eliptická válcová plocha:

• Eliptický paraboloid:

• Hyperbolický paraboloid:

• Hyperbolická válcová plocha:

• Parabolická válcová plocha:

x^{2}/a^{2} + y^{2}/b^{2} − z^{2} = 0 x^{2}/a^{2} − y^{2}/b^{2} − z^{2} = 1 x^{2}/a^{2} + y^{2}/b^{2} − z^{2} = 1 x^{2}/a^{2} + y^{2}/b^{2} + z^{2} = 1 x^{2}/a^{2} + y^{2}/b^{2} = 1 x^{2}/a^{2}+y^{2}/b^{2}+2cz = 0 x^{2}/a^{2}−y^{2}/b^{2}+2cz = 0 x^{2}/a^{2} − y^{2}/b^{2} = 1 x^{2}/a^{2} − 2by = 0

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

47

Bohatství tvarů implicitní reprezentace se zvýrazní pomocí geometrické interpretace. Křivku získáme pomocí průniku formy z = F (x, y) v explicitním tvaru v třídemenzionálním prostoru definované plochy s rovinou x − y. V závislosti na tvaru plochy se může křivka rozpadnout do vícero dílčích křivek, dílčí křivky mohou jít do nekonečna nebo mohou být uzavřené. Obecně se zdá být souvislost mezi výslednou křivkou a matematicky formálním vyjádřením neprůhlednější než při parametrickém vyjádření. Nejsnáze ji můžeme obdržet analýzou plochy z = F (x, y).

Vhodnost způsobu vyjádření závisí na způsobu aplikace. Explicitní a parametrické vyjádření jsou vhodná, pokud má být křivka vykreslena. Implicitní vyjádření křivky je snadno pochopitelnější jako průnik roviny a plochy. V tomto tvaru je zejména jednoduchý ţtest incidence bod na křivce�, protože stačí pouze dosadit souřadnice bodu a testovat na rovnost 0.

Většina modelovacích technik používá parametrické vyjádření.

2 Metody analýzy prostřednictvím diferenciální geometrie

V této kapitole představíme elementární pojmy popisu a analýzy křivek a ploch. K popisu rovinné křivky v okolí pevně zvoleného bodu uvažujeme lineární a kvadratické aproximace, což vede k pojmům jako jsou tečna, normála, zakřivení a poloměr zakřivení. Pro prostorové křivky vznikne doprovázející trojice skládající se z tečny, normál a binormál v daném bodě křivky.

Považujeme-li pro analýzu ploch lineární aproximace v okolí pevně zvoleného bodu plochy, získáme tečnou rovinu a normálový vektor. Pro měření vzdáleností na ploše zavedeme první základní formu, zakřivení v ploše probíhajících křivek může být studováno pomocí druhé normální formy. Plocha je určena šesti funkcemi koeficientů prvního a druhého základního tvaru, a ty musí navíc splňovat jisté okrajové podmínky – Gaussovu rovnici a Mainardi-Codazziho rovnici – až na shodnost. To je obsah hlavní věty teorie ploch.

2.1 Křivky

Připomeňme, že dvě křivky p_{1} a p_{2} třídy C^{r} mají ve společném bodě x styk řádu j, jestliže existují takové jejich lokální parametrizace k_{1}(t) a k_{2}(t) tak, že k_{1}(t_{0}) = k_{2}(t_{0}) = x a

\frac{d^{i}k_{1}}{dt^{i}} (t_{0}) = \frac{d^{i}k_{2}}{dt^{i}} (t_{0})

pro všechna i = 0, 1, …, j.

Pro zkoumání chování křivek ţv malém� si zvolíme libovolný, ale pevný bod na křivce a uvažujeme aproximaci křivky v okolí bodu pomocí přímek a kruhů. Základem aproximace je měření vzdálenosti pevně zvoleného bodu podél křivky. To nás vede na pojem tzv. ţdiferenciálu oblouku�.

Definice. Diferenciál oblouku je

• při explicitní reprezentaci y = f(x) rovinné křivky:

ds = \sqrt{1 + (\frac{df}{dx})^{2} dx} ,

• při parametrické reprezentaci k(t) = (x(t), y(t)) rovinné křivky:

ds = \sqrt{x^{′2} + y^{′2}} dt = ||k′||, k′(t) = (x′, y′) = (\frac{dx}{dt}, \frac{dy}{dt}).

Délka oblouku je

∫_{a}^{b} ds.

Při parametrické reprezentaci pak dostaneme

∫_{a}^{b} ds = ∫_{a}^{b} \sqrt{x^{′2} + y^{′2}} dt.

To lze snadno dokázat tak, že zvolíme rozdělení (t_{i}) intervalu [a, b], uvažujeme aproximaci

\begin{aligned}& ∑_{i} ^{\frac{\sqrt{(x(t_{i+1} )−x(t_{i}))^{2}+(y(t_{i+1} )−y(t_{i}))^{2}}}{t_{i+1} −t_{i}}} · (t_{i+1} − t_{i}) \\ = & ∑_{i} \sqrt{(\frac{x(t_{i+1} )−x(t_{i})}{t_{i+1} −t_{i}} )^{2} + (\frac{y(t_{i+1} )−y(t_{i})}{t_{i+1} −t_{i}} )^{2}} · (t_{i+1} − t_{i}) \end{aligned}

délky oblouku a limitu zjemnění.

Danou křivku lze parametrizovat mnoha způsoby. Jednou ze snadno pochopitelných možností je vzít za parametr délku oblouku. Mluvíme pak o přirozené parametrizaci:

Definice. Přirozená parametrizace: Křivky vyjádřené pomocí parametrické reprezentace tak, že jako parametr je brána délka křivky, tj. každému dílčímu intervalu odpovídá díl křivky téže délky. Derivace podle délky oblouku se označuje tečkou nad znakem křivky:

k̇(s) := \frac{d}{ds}k(s).

Parametrizace pomocí délky oblouku je důležitý teoretický pomocný prostředek. Platí např.

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

49

Věta 2.1 Přirozeně parametrizované křivky Buď t parametr libovolné parametrizace, s parametr přirozené parametrizace. Pak platí:

1. \frac{ds}{dt} = ||k′(t)||,

2. k̇(s) = \frac{k′(t)}{||k′(t)||},

3. 1 = ||k̇(s)||,

4. k^{.} ⊥ k^{..}.

Důkaz. První tvrzení plyne derivací funkce s(t) = ∫_{t_{0}}^{t} ||k′(x)||dx. Tvrzení 2 plyne z 1. Totiž k′(t) = \frac{dk}{dt} = \frac{dk}{ds} \frac{ds}{dt} = k̇(s) · ||k′(t)||. Tvrzení 3 plyne bezprostředně z 2 a tvrzení 4 obdržíme derivováním vztahu x^{.}(s)^{2}+ y^{.} (s)^{2} = 1 odvozeného z 3. Pak máme

2· x^{.} (s)· x^{..} (s) + 2· y^{.} (s)· y^{..} (s) = 0.

Parametrizace vzhledem k délce k oblouku není obvykle v praxi realizovatelná. Používá se pak aproximace podle délky polygoniálního přiblížení křivky.

Definice. Tečna ke křivce k v R^{d} v bodě křivky p je limita sečny křivky k mezi body p a q, q → p. Jinak řečeno, tečna ke křivce k v R^{d} v bodě je přímka, která má s křivkou v daném bodě styk 1. řádu.

Pro diferenciovatelnou funkci F : R^{3} → R se definuje gradient ∇F (někdy i δF) jako ∇F := (F_{x}, F_{y}, F_{z}), F_{x}, F_{y}, F_{z} jsou parciální derivace F. Zejména jde spočítat směrnici tangenty prostorových křivek:

Věta 2.2 Výpočet směrnicového vektoru tečny

• Při implicitní reprezentaci F (x, y, z) = 0, G(x, y, z) = 0 v prostoru platí:

t = ∇F × ∇G = (| \begin{matrix}F_{y} & F_{z} \\ G_{y} & G_{z} \end{matrix} | , − | \begin{matrix}F_{x} & F_{z} \\ G_{x} & G_{z} \end{matrix} | , | \begin{matrix}F_{x} & F_{y} \\ G_{x} & G_{y} \end{matrix} |) ,

• Při parametrické reprezentaci x = x(t), y = y(t), z = z(t) v prostoru:

t = (x′, y′, z′).

Důkaz. Pro odvození výpočtu směrového vektoru tečny pro implicitní reprezentaci křivky předpokládáme lokálně existenci parametrické reprezentace g(t) křivky řezu. Platí pak

F (g(t)) = 0  ∇F · g′ = 0,

⟹

G(g(t)) = 0  ∇G · g′ = 0.

Tečný vektor g′ je tedy kolmý jak k ∇F tak k ∇G a je tedy určen až na násobek jakožto vektorový součin ∇F × ∇G. Vztah pro tečný vektor pro parametrické vyjádření plyne limitním přechodem sečen k tečně.

Definice. Křivost je odchylka křivky od přímky, tj.

κ = lim_{p̂q→0} \frac{φ}{p̂q}.

p̂q přitom označuje délku části křivky určené p a q, φ úhel mezi tečnami v p a q. Oskulační kružnice v bodě p je limitou kružnic, určenými třemi body p, q, r ležícími na křivce, přičemž p leží mezi q a r, q → p a r → p. Jinak řečeno, oskulační kružnice v bodě křivky je taková kružnice, která má s křivkou v daném bodě styk 2. řádu.

Věta 2.3 Výpočet křivosti a oskulační kružnice

1. \underline{Křivost:}

• při implicitní reprezentaci F (x, y) = 0 v rovině:

κ = \frac{| \begin{matrix}F_{xx} & F_{xy} & F_{x} \\ F_{yx} & F_{yy} & F_{y} \\ F_{x} & F_{y} & 0 \end{matrix} |}{(F_{x}^{2} + F_{y}^{2})^{\frac{3}{2}}},

• při explicitním vyjádření y = f(x) v rovině:

κ = \frac{f′′}{(1 + (f′)^{2})^{\frac{3}{2}}} ,

• při parametrické reprezentaci x = x(t), y = y(t) v rovině:

κ = \frac{| \begin{matrix}x′ & y′ \\ x′′ & y′′ \end{matrix} |}{(x′^{2} + y′^{2})^{\frac{3}{2}}} ,

• při parametrické reprezentaci x = x(t), y = y(t), z = z(t) v prostoru:

κ^{2} = \frac{(x′^{2} + y′^{2} + z′^{2}) · (x′′^{2} + y′′^{2} + z′′^{2}) − (x′x′′ + y′y′′ + z′z′′)^{2}}{(x′^{2} + y′^{2} + z′^{2})^{3}} .

2.

Poloměr ρ oskulační kružnice:

ρ = \frac{1}{κ}.

3.

Střed oskulační kružnice:

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

51

• při implicitní reprezentaci F (x, y) = 0 v rovině:

c = ( \begin{matrix}x \\ y \end{matrix} ) + \frac{(F_{x}^{2} + F_{y}^{2})}{| \begin{matrix}F_{xx} & F_{xy} & F_{x} \\ F_{yx} & F_{yy} & F_{y} \\ F_{x} & F_{y} & 0 \end{matrix} |} · ( \begin{matrix}F_{x} \\ F_{y} \end{matrix} )

• při explicitním vyjádření y = f(x) v rovině:

c = ( \begin{matrix}x \\ y \end{matrix} ) + \frac{(1 + (f′)^{2})}{f′′} · ( \begin{matrix}−f′ \\ 1 \end{matrix} ) ,

• při parametrické reprezentaci x = x(t), y = y(t) v rovině:

c = ( \begin{matrix}x \\ y \end{matrix} ) + \frac{(x′^{2} + y′^{2})}{| \begin{matrix}x′ & y′ \\ x′′ & y′′ \end{matrix} |} · ( \begin{matrix}−y′ \\ x′ \end{matrix} ) .

Důkaz. Uvažme normované tečny t(t) o délce 1 na místech t a t + Δt. Pro úhel φ sevřený těmito tečnami platí

sin(\frac{φ}{2}) = \frac{||t(t + Δt) − t(t)||}{2} .

Odtud pak plyne:

κ = lim_{p̂q→0} \frac{φ}{p̂q}
= lim_{p̂q→0} 2\frac{φ}{2}/(2 sin(\frac{φ}{2})) · \frac{||t(t+Δt)−t(t)||}{Δt} · \frac{1}{p̂q/Δt}
= 1 · ||t′(t)|| · 1/s′(t).

Pro křivku k(t) = ( \begin{matrix}x \\ y \end{matrix} ) v parametrickém vyjádření obdržíme s pomocí vztahů

t = k′_{\sqrt{k′∗k′}} ,
t′ = −\frac{k′∗k′′}{(k′∗k′)^{\frac{3}{2}}} + _{\frac{1}{(k′∗k′)^{\frac{3}{2}}}} k′′,

||t′||^{2} = ^{\frac{(k′∗k′)(k′′∗k′′)−(k′∗k′′)^{2}}{(k′∗k′)^{2}}},
s′(t) = \sqrt{k′ ∗ k′}

vztah

κ = \sqrt{(k′ ∗ k′)(k′′ ∗ k′′) − (k′ ∗ k′′)^{2}} ; (k′ ∗ k′)^{\frac{3}{2}}

pro zakřivení. Pro prostorové křivky lze pak pomocí vektorového součinu psát

κ = \frac{||k′ × k′′||}{(k′ ∗ k′)^{\frac{3}{2}}}.

Vztah pro střed oskulační kružnice je obecně tvaru

c = p + \frac{1}{κ} · \frac{1}{||n||} · n,

kde p je bod křivky, κ zakřivení a n normála.

V každém bodě p prostorové křivky lze až na singulární vyjímky definovat tři navzájem kolmé vektory. Každý z těchto vektorů je normálou nějaké roviny procházející bodem p.

Definice. Průvodní trojhran (Frenetův trojhran) prostorové křivky k je pravostranný souřadný systém, který sestává z následujících jednotkových směrových vektorů: Normovaný tečný vektor t: Tečný vektor obdržíme jako limitu sečen. Zejména platí

t =k^{.} .

Hlavní normála n: Hlavní normála je normovaný vektor ve směru středu oskulační kružnice. Přitom

n = \frac{k^{..}}{|| k^{..} ||}.

Binormála b: Binormála je kolmá na tečný vektor a na hlavní normálu. Zřejmě

b = t × n.

Definice. Roviny k průvodnímu trojhranu prostorové křivky:

Normálová rovina: je kolmá k tečnému vektoru. Má tedy rovnici

t · x = a.

Rektifikační rovina: je kolmá k hlavní normále. Její rovnice je

n · x = b.

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

53

Křivka zůstává (v nějakém ϵ-okolí) v poloprostoru rektifikované roviny, a to v poloprostoru, který obsahuje střed oskulační kružnice. Hlavní normála směřuje do tohoto poloprostoru. Oskulační rovina b: je kolmá k binormále. Obdržíme ji jako limitu rovin procházejících třemi sousedními body křivky. Rovnice oskulační roviny má tvar

b · x = c.

Na rozdíl od rovinných křivek mají prostorové křivky k dispozici další dimenzi. Zatímco zakřivení měří změnu odchylky od tečny, je torze míra pohybu křivky z roviny.

Definice. Torze jakožto míra pro odchylky křivky od rovinné křivky je vyjádřena jako

τ = lim_{p̂q→0} \frac{||Δb||}{p̂q} .

Přitom Δb je rozdíl binormál v bodech p a q.

Věta 2.4 Výpočet torze Pro křivku při parametrické reprezentaci x = x(t), y = y(t), z = z(t) v prostoru platí

τ = \frac{ρ^{2}}{(x^{′2} + y^{′2} + z^{′2})^{3}} · | \begin{matrix}x′ & y′ & z′ \\ x′′ & y′′ & z′′ \\ x′′′ & y′′′ & z′′′ \end{matrix} | .

Důkaz. Vztah pro torzi při parametrickém vyjádření k : R → R^{3} plyne z

τ = lim_{_{Δs}→0} ||\frac{Δb}{Δs} || = || b^{.} ||,
b = t × n =k^{.} ×\frac{k^{..}}{\sqrt{k^{..}∗k^{..}}},
b^{.} = − \frac{k^{..}∗k^{...}}{(k^{..}∗k^{..})^{\frac{3}{2}}} (k^{.} × k^{..}) + \frac{1}{\sqrt{k^{..}∗k^{..}}} k^{.} × k^{...} .

Přitom k^{.} × k^{...} lze psát jako lineární kombinaci

k^{.} × k^{...} = \frac{k^{...}∗(k^{.}×k^{..})}{k^{..}∗k^{..}} k^{..} +\frac{k^{...}∗k^{..}}{(k^{.}×k^{..})∗(k^{.}×k^{..})}(k^{.} × k^{..})
= \frac{k^{...}∗(k^{.}×k^{..})}{k^{..}∗k^{..}} k^{..} +\frac{k^{...}∗k^{..}}{(k^{.}∗k^{..})^{2}} (k^{.} × k^{..}).

k^{.}, k^{..} a k^{.} × k^{..}. Zároveň lze využít, že k^{.} a k^{..} jsou navzájem kolmé a || k^{.} || = 1. Obdržíme tedy:

b^{.} = (\frac{(k^{.}×k^{..})∗k^{...}}{(k^{..}∗k^{..})^{\frac{3}{2}}})· k^{..}= | k^{.}, k^{..}, k^{...} | (\frac{k^{..}}{(k^{..}∗k^{..})^{\frac{3}{2}}} )
|| b^{.} || = \frac{|k^{.},k^{..},k^{...}|}{(k^{..}∗k^{..})}.

Vyjdeme-li v poslední formuli z derivace podle délky oblouku k derivaci funkce k podle libovolného parametru t, obdržíme po několika přeformulováních hledaný vztah

z τ = || b^{.} ||.

Tyto tři vektory doprovodné trojice t, n a b jsou navzájem kolmé a tedy generují celý prostor. Můžeme tedy zejména každý vektor, zejména pak i derivace t^{.}, n a b vyjádřit jako jejich lineární kombinace. To lze vyjádřit Frenetovými vzorci. Lze ukázat, že tyto koeficienty závisí pouze na křivosti a torzi. K tomu je potřeba následujícího tvrzení:

Věta 2.5 O ortonormálním repéru. Předpokládejme, že pomocí vektorových funkcí

m_{1} = m_{1}(t), m_{2} = m_{2}(t), m_{3} = m_{3}(t), t ∈ J

jsou pro každé t ∈ J definovány tři jednotkové navzájem kolmé vektory (o nich říkáme, že tvoří tzv. ortonormální repér). Vypočtěme funkce m^{.}_{1}= m^{.}_{1}(t), m^{.}_{2}= m^{.}_{2}(t), m^{.}_{3}= m^{.}_{3}(t), t ∈ J a zapišme je jako lineární kombinace funkcí m_{1}, m_{2}, m_{3} takto:

m^{.}_{1} = a_{11}m_{1}+ a_{12}m_{2}+ a_{13}m_{3},
m^{.}_{2} = a_{21}m_{1}+ a_{22}m_{2}+ a_{23}m_{3},
m^{.}_{3} = a_{31}m_{1}+ a_{32}m_{2}+ a_{33}m_{3},

kde a_{ij} jsou reálné funkce definované na intervalu J. Potom matice koeficientů a_{ij} je pro každé t ∈ J antisymetrická, tj. má tvar

( \begin{matrix}0 & a_{12} & a_{13} \\ a_{21} & 0 & a_{23} \\ a_{31} & a_{32} & 0 \end{matrix} ) .

Důkaz. Připomeňme, že pro každé t ∈ J tvoří hodnoty vektorových funkcí m_{1}, m_{2}, m_{3} bázi vektorového zaměření prostoru R^{3}, a tedy výše uvedené vyjádření existuje a je jednoznačné.

Ukážeme, že a_{11} = 0. Evidentně,

\begin{aligned}ṁ_{1} · m_{1} & = & a_{11} \\ m_{1} · m_{1} & = & 1 \\ 2ṁ_{1} · m_{1} & = & 0. \end{aligned}

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

55

Zejména tedy a_{11} = 0. Analogicky, a_{22} = 0, a_{33} = 0.

Ukážeme, že a_{12} = −a_{21}. Platí,

ṁ_{1} · m_{2} = a_{12}, ṁ_{2} · m_{1} = a_{21}.

Zřejmě m_{1} · m_{2} = 0. Derivováním zjistíme, že ṁ_{1} · m_{2} + ṁ_{2} · m_{1} = 0.

Odtud již plyne, že a_{12} = −a_{21}. Obecně platí a_{ij} = −a_{ji}.

Frenetovy vzorce lze považovat za systém diferenciálních rovnic pro t, n a b:

Věta 2.6 Frenetovy vzorce, Hlavní věta teorie křivek.

ṫ =  κ · n
ṅ = −κ · t  +τ · b
ḃ =  −τ · n ,

kde t je normovaný tečný vektor, n je normovaný normálový vektor, b je normovaný binormálový vektor, κ je křivost a τ torze.

Důkaz. Víme, že ṫ= κ · n a že ḃ = −τ · n. Zbývající část plyne z předchozí věty.

Důležitým výsledkem diferenciální geometrie je skutečnost, že křivost a torze jsou charakteristické veličiny prostorové křivky a tato je jimi jednoznačně popsaná:

Věta 2.7 Hlavní věta teorie křivek Zadáním funkcí κ a τ je prostorová křivka určena jednoznačně až na shodnost a lze ji vypočíst jakožto řešení Frenetových diferenciálních rovnic.

Důkaz. Viz diferenciální geometrie.

Závěrem tohoto odstavce se budeme věnovat rovinným křivkám. V rovině si můžeme vyjádřit tečný směr a normálový směr následovně:

Věta 2.8 Tečna a normála pro rovinné křivky

1.

Tečna má rovnici

• při implicitním vyjádření F (x, y) = 0:

t = (−F_{y}, F_{x}),

• při explicitním vyjádření y = f(x):

t = (1, f′), • při parametrickém vyjádření x = x(t), y = y(t) :

t = (x′, y′).

2.

Normála má rovnici

• při implicitním vyjádření F (x, y) = 0:

n = (F_{x}, F_{y}),

• při explicitním vyjádření y = f(x):

t = (−f′, 1),

• při parametrickém vyjádření x = x(t), y = y(t) :

t = (−y′, x′).

Důkaz. Tečný vektor obdržíme při parametrickém vyjádření jako limitu vektorové funkce

( \frac{x(t+Δt)−x(t)}{Δt} ; \frac{y(t+Δt)−y(t)}{Δt} ) ,

normálový vektor záměnou složek a změnou jednoho znaménka. U implicitního vyjádření se předpokládá existence lokálního parametrického vyjádření x = x(t), y = y(t) tak, že F (x(t), y(t)) = 0 a následně derivováním F_{x}x′(t)+F_{y}y′(t)) = 0, je tedy (F_{x}, F_{y}) vektor kolmý na tečný vektor (x′, y′).

Připomeňme si následující pojmy:

Definice. Inflexní bod: bod křivky, ve kterém konkávnost přechází z jedné strany křivky na druhou tj. takový bod, že jím procházející tečna ke křivce v něm má s křivkou styk 2. řádu.

Vrchol: bod křivky, ve kterém křivost nabývá minima nebo maxima.

Dvojnásobný bod: bod křivky, ve kterém se křivka sama protíná.

Izolovaný bod: bod křivky, který vyhovuje rovnici křivky a zároveň leží ţmimo� křivku.

Bod obratu: bod křivky, ve kterém tečný vektor změní svou orientaci.

Bod doteku: dvojnásobný bod křivky, se shodným tečným vektorem.

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

57

Bod lomu: bod nespojitosti tečného vektoru.

Bod zlomu: bod nespojitosti každého parametrického vyjádření křivky.

Asymptotický bod : bod křivky, kolem kterého se křivka nekonečněkrát obtáčí a je libovolně blízko.

Věta 2.9 Nutné podmínky pro inflexní body rovinných křivek

• při implicitním vyjádření F (x, y) = 0:

| \begin{matrix}F_{xx} & F_{xy} & F_{x} \\ F_{yx} & F_{yy} & F_{y} \\ F_{x} & F_{y} & 0 \end{matrix} | = 0,

• při explicitním vyjádření y = f(x):

f′′ = 0,

• při parametrickém vyjádření x = x(t), y = y(t) :

| \begin{matrix}x′ & y′ \\ x′′ & y′′ \end{matrix} | = 0.

Důkaz. V udaném bodu má křivost nulový průchod. To je nutná podmínka proto, že střed oskulační kružnice mění stranu křivky.

2.2 Plochy

Tečná rovina plochy v bodě je rovina, která nejlépe aproximuje plochu v okolí tohoto bodu. Normála v bodě plochy je normála tečné roviny. K jejich výpočtu je třeba derivace prvního řádu:

Věta 2.10 Výpočet tečné roviny v bodě p = (x^{∗}, y^{∗}, z^{∗}):

• při implicitním vyjádření F (x, y) = 0, x = (x, y, z) :

▽F (p) · (x − p) := (F_{x}(p), F_{y}(p), F_{z}(p)) · ( \begin{matrix}x − x^{∗} \\ y − y^{∗} \\ z − z^{∗} \end{matrix} ) = 0,

• při explicitním vyjádření z = f(x, y):

z − f(x^{∗}, y^{∗}) = (f_{x}(x^{∗}, y^{∗}), f_{y}(x^{∗}, y^{∗})) · ( \begin{matrix}x − x^{∗} \\ y − y^{∗} \end{matrix} ) ,

• při parametrickém vyjádření p = f(u, v), x = (x, y, z):

|x − f(u^{∗}, v^{∗}) f_{u}(u^{∗}, v^{∗}) f_{v}(u^{∗}, v^{∗})| = 0.

Důkaz. Uvažme křivky na ploše, které jsou zadány jako zobrazení k z parametrického oboru křivky (⊆ R) do parametrického oboru plochy (⊆ R^{2}). Zkoumejme tečny takovýchto křivek. V případě implicitně zadaných ploch máme

F (k(t)) = 0⟹ ▽F · k′ = 0.

Gradient ▽F je pak kolmý na tečné vektory křivek plochy a je tedy normálou tečné roviny.

U parametricky zadaných ploch lze tímto přístupem zjistit, že můžeme vyjádřit tečné vektory všech křivek plochy jako lineární kombinaci parciálních derivací f_{u}(u^{∗}, v^{∗}) a f_{v}(u^{∗}, v^{∗}), a tedy tyto směrové derivace generují tečnou rovinu. Pro každý bod x v tečné rovině bodu p je x−p rovněž lineárně závislé na směrových derivacích, což lze vyjádřit udanou podmínkou pro determinant.

Věta 2.11 Výpočet normálových vektorů

• Normála při implicitním vyjádření F (x, y, z) = 0 :

n = ▽F = (F_{x}, F_{y}, F_{z}),

• normála při explicitním vyjádření z = f(x, y):

n = (f_{x}, f_{y}, −1),

• normála při parametrickém vyjádření x = f(u, v) = (x(u, v), y(u, v), z(u, v)):

n = f_{u} × f_{v} = (| \begin{matrix}y_{u} & z_{u} \\ y_{v} & z_{v} \end{matrix} | , − | \begin{matrix}x_{u} & z_{u} \\ x_{v} & z_{v} \end{matrix} | , | \begin{matrix}x_{u} & y_{u} \\ x_{v} & y_{v} \end{matrix} | , ) .

Důkaz. Cvičení.

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

59

S pomocí tzv. první základní formy je možné měřit délky na plochách. Uvažme plochu s parametrickým vyjádřením f : R^{2} → R^{3} a část křivky k : [a, b] → R^{2}, tzn. zobrazení parametrického oboru plochy k(t) = (u(t), v(t)), u, v : [a, b] → R. Délka části křivky (k(t)), t ∈ [a, b] zadaného jako

s = ∫_{a}^{b} ||\frac{d}{dt}f(k(t))||dt
= ∫_{a}^{b} ||f_{u} · u′ + f_{v} · v′||dt
= ∫_{a}^{b} \sqrt{f_{u} ∗ f_{u} · u^{′2} + 2f_{u} ∗ f_{v} · u′ · v′ + f_{v} ∗ f_{v} · v^{′2}} dt.

Pro nekonečně malou část ds pak platí

ds^{2} = f_{u} ∗ f_{u} · du^{2} + 2f_{u} ∗ f_{v} · du · dv + f_{v} ∗ f_{v} · dv^{2}

Pravá strana rovnosti se nazývá první základní forma plochy.

Definice. První základní forma (1FF): pro plochu v parametrickém vyjádření x = f(u, v) = (x(u, v), y(u, v), z(u, v)) je první základní forma definovaná jako funkce R^{4} → R, kde

(u, v, du, dv) ↦ E · du^{2} + 2F · dudv + G · dv^{2},

s metrickými koeficienty

\begin{aligned}E & := & f_{u} ∗ f_{u} & = & x_{u}^{2} + y_{u}^{2} + z_{u}^{2}, \\ F & := & f_{u} ∗ f_{v} & = & x_{u}x_{v} + y_{u}y_{v} + z_{u}z_{v}, \\ G & := & f_{v} ∗ f_{v} & = & x_{v}^{2} + y_{v}^{2} + z_{v}^{2}. \end{aligned}

Pro kouli

f(u, v) = ( \begin{matrix}r sinu · cosv \\ r sinu · sinv \\ r cosu \end{matrix} )

například platí

E = r^{2}, F = 0, G = r · sin^{2} u.

Věta 2.12 Délka oblouku Buď dána plocha f(u, v). Pro diferenciál oblouku ds křivky na této ploše ve směrech du, dv platí

ds^{2} = E · du^{2} + 2F · dudv + G · dv^{2}.

Důkaz. Standardní tvrzení diferenciální geometrie.

Za účelem analýzy křivosti ploch se zkoumá křivost křivek probíhajících v ploše. Uvažujeme-li např. velkou kružnici probíhající na kouli, je pak střed koule také středem oskulační kružnice křivky. Pro bod p této plochy ukazuje normála plochy do stejného směru jako vektor křivosti křivky. Skalární součin obou vektorů je roven poloměru křivosti této křivky. Při libovolných plochách a křivkách na ploše to už nebude tento případ – skalární součin normály plochy a vektoru křivosti je roven křivosti pronásobené s kosinem úhlu sevřeného normálou plochy a vektorem zakřivení. Buďte

f(u, v)  plocha v parametrickém vyjádření,
n_{f}(u, v)  normála plochy,
k(s)  křivka v ploše v parametrickém vyjádření tak, že

k(s) je přirozeně parametrizovatelná,

κ  křivost plošné křivky
κ · n_{k} = \frac{d^{2}}{ds^{2}}f(k(s)) druhá derivace křivky, tj. křivostí vynásobená hlavní

normála, která ukazuje ve směru středu křivosti

Φ  úhel sevřený normálou plochy a vektorem křivosti.

Aplikujeme-li

n_{f}f_{u} = (f_{u} × f_{v})/||(f_{u} × f_{v})|| · f_{u} = 0,
n_{f}f_{v} = (f_{u} × f_{v})/||(f_{u} × f_{v})|| · f_{v} = 0,

obdržíme pak

κ cosΦ = κ · n_{f}n_{k} = \frac{d^{2}}{ds^{2}}n_{f}f(u(s), v(s))
= n_{f} · (f_{uu} u^{.}^{2} +2f_{uv} u^{.}v^{.} +f_{vv} v^{.}^{2} +f_{uu} u^{..} +f_{vv} v^{..})
= n_{f}f_{uu} u^{.}^{2} +2n_{f}f_{uv} u^{.}v^{.} +n_{f}f_{vv} v^{.}^{2} .

Násobením ds^{2} získáme

κ · n_{f}n_{k}ds^{2} = n_{f}f_{uu} u^{.}^{2} du^{2} + 2n_{f}f_{uv} u^{.}v^{.} dudv + n_{f}f_{vv} v^{.}^{2} dv^{2}.

Výraz na pravé straně, rovněž funkce u, v, du, dv je tzv. druhá základní forma plochy:

Definice. Druhá základní forma (2FF): Pro plochu s parametrickým vyjádřením f(u, v) je druhá základní forma funkce R^{4} → R s

(u, v, du, dv) ↦ L · du^{2} + 2 · M · dudv + N · dv^{2},

přičemž metrické koeficienty L, M, N jsou definovány následovně:

\begin{aligned}L & := & nf_{uu}, \\ M & := & nf_{uv}, \\ N & := & nf_{vv}. \end{aligned}

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

61

Přitom n je normála plochy (f_{u} × f_{v})/||(f_{u} × f_{v})||.

Věta 2.13 Geometrická interpretace druhé základní formy Druhá základní forma určuje odchylku dh sousedních bodů plochy f(u + du, v + dv) od tečné roviny v bodě roviny f(u, v):

dh = \frac{1}{2}2FF+ o(du^{2} + dv^{2}).

Přitom dh je složka odchylky ve směru normály tečné roviny.

Důkaz. Pro odvození geometrické interpretace druhé základní formy budeme považovat druhou základní formu za součin derivace druhého řádu ve směru (du, dv) s normálami ploch:

2FF = n · f_{uu}du^{2} + 2f_{uv}dudv + f_{vv}dv^{2}.

Provedeme-li Taylorův rozvoj f v bodě (u, v), obdržíme

f(u + du, v + dv) = f(u, v) + (f_{u}du + f_{v}dv)
+\frac{1}{2}(f_{uu}du^{2} + 2f_{uv}dudv + f_{vv}dv^{2})
+o(du^{2} + dv^{2}).

Protože máme nf_{u} = 0 = nf_{v} a

dh = n · (f(u + du, v + dv) − f(u, v)),

obdržíme bezprostředně dokazované tvrzení.

Věta 2.14 Výpočet druhé fundamentální formy Buď f(u, v) = (x(u, v), y(u, v), z(u, v)). Pak platí

\begin{aligned}L & = & \frac{1}{\sqrt{EG−F^{2}}} · | \begin{matrix}x_{uu} & y_{uu} & z_{uu} \\ x_{u} & y_{u} & z_{u} \\ x_{v} & y_{v} & z_{v} \end{matrix} | , \\ M & = & \frac{1}{\sqrt{EG−F^{2}}} · | \begin{matrix}x_{uv} & y_{uv} & z_{uv} \\ x_{u} & y_{u} & z_{u} \\ x_{v} & y_{v} & z_{v} \end{matrix} | , \\ N & = & \frac{1}{\sqrt{EG−F^{2}}} · | \begin{matrix}x_{vv} & y_{vv} & z_{vv} \\ x_{u} & y_{u} & z_{u} \\ x_{v} & y_{v} & z_{v} \end{matrix} | . \end{aligned}

Důkaz. Formule pro výpočet druhé základní formy lze získat z koeficientů E, F, G první základní formy

||n||^{2} = ||f_{u} × f_{v}|| = (f_{u} ∗ f_{u}) · (f_{v} ∗ f_{v}) − (f_{u} ∗ f_{v}) · (f_{u} ∗ f_{v}) = EG − F^{2}.

Prostorové křivky jsou určeny dvěma funkcemi - křivostí a torzí - a to až na shodnost. Křivku obdržíme jako řešení systému diferenciálních rovnic - Frenetových rovnic, ve kterém jsou derivace průvodního trojhranu vyjádřeny jako lineární kombinace trojhranu samého, přičemž koeficienty lineární kombinace závisí na křivosti a torzi.

Podobná situace nastává u ploch. Roli křivosti a torze přebírají koeficienty první a druhé základní formy. V rozporu s křivostí a torzí nelze tyto koeficienty zcela volně zvolit, nýbrž musí splňovat jisté okrajové podmínky. K jejich splnění uvažujme trojhran sestávající s směrových derivací f_{u}, f_{v} a vnější normály n = f_{u} × f_{v}/||f_{u} × f_{v}||, tzv. trojhran plochy. Každý vektor, zejména také derivace druhého řádu lze vyjádřit jako lineární kombinaci trojhranu plochy:

Věta 2.15 Gaussovy formule Máme

f_{uu} = Γ_{11}^{1}f_{u} + Γ_{11}^{2}f_{v} + c_{11}n^{∗},
f_{uv} = Γ_{12}^{1}f_{u} + Γ_{12}^{2}f_{v} + c_{12}n^{∗},
f_{vv} = Γ_{22}^{1}f_{u} + Γ_{22}^{2}f_{v} + c_{22}n^{∗},

kde Γ_{ij}^{k}, 1 ≤ i, j, k ≤ 2 jsou Christoffelovy symboly druhého stupně

Γ_{11}^{1} = (E_{u}G − 2F F_{u} + E_{v}F)/(2g),
Γ_{12}^{1} = (E_{v}G − F G_{u})/(2g),
Γ_{22}^{1} = (−F G_{v} + 2F_{v}G − GG_{u})/(2g),
Γ_{21}^{1} = Γ_{12}^{1},
Γ_{11}^{2} = (E_{u}F − 2F F_{u} + EE_{v})/(2g),
Γ_{12}^{2} = (EG_{u} − E_{u}F)/(2g),
Γ_{22}^{2} = (EG_{u} − 2F F_{v} + F G_{u})/(2g),
Γ_{21}^{2} = Γ_{12}^{2},

přičemž

g = EG − F^{2}, c_{11} = L, c_{12} = L, c_{22} = N.

Důkaz. Viz diferenciální geometrie.

Připomeňme, že při vhodné indexaci jsou Christoffelovy symboly prvního stupně Γ_{ij,k} skalární součin druhé a první derivace, např. Γ_{12,1} = f_{uv} ∗ f_{u}.

Rovněž parciální derivace normály plochy lze vyjádřit jako lineární kombinaci trojhranu plochy:

Věta 2.16 Weingartenovy formule Máme

n_{u}^{∗} = r_{1}f_{u} + r_{2}f_{v} + r_{3}n^{∗},
n_{v}^{∗} = s_{1}f_{u} + s_{2}f_{v} + s_{3}n^{∗},

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

63

kde

\begin{matrix}r_{1} = (F M − GL)/g, & r_{2} = (F L − EM)/g, & r_{3} = 0, \\ s_{1} = (F N − GM)/g, & s_{2} = (F M − EN)/g, & s_{3} = 0 \end{matrix}

a g = EG − F^{2}.

Důkaz. Viz diferenciální geometrie.

Na funkci f klademe požadavek trojnásobné spojité diferencovatelnosti. Pak z věty o záměně pořadí derivování obdržíme, že musí platit

f_{uuv} = f_{uvu} a f_{vvu} = f_{uvv}.

Dosadíme-li do Gaussových formulí, obdržíme dvě vektorové rovnice o proměnných f_{uu}, f_{uv}, f_{vv}, n_{u}, n_{v}. Aplikujeme-li Gaussovy a Weingartenovy formule, získáme dvě vektorové rovnice o proměnných f_{u}, f_{v}, n z trojhranu plochy,

α_{1k}f_{u} + α_{2k}f_{v} + α_{3k}n^{∗} = 0, α_{ik}R, k ∈ {1, 2}.

Z lineární nezávislosti vektorů trojhranu plochy obdržíme α_{ik} = 0, 1 ≤ i ≤ 3, 1 ≤ k ≤ 2. Dostaneme pak následujících šest podmínek:

Věta 2.17 Gaussovy rovnice Platí

α_{11}= 0 ⟺ F · b/g = (Γ_{12}^{1})_{u} − (Γ_{11}^{1})_{v} + Γ_{12}^{1}Γ_{12}^{2} − Γ_{11}^{1}Γ_{22}^{1},
α_{12}= 0 ⟺ −E · b/g = (Γ_{12}^{2})_{u} − (Γ_{11}^{2})_{v} + Γ_{12}^{2}(Γ_{12}^{2} − Γ_{11}^{1}) + Γ_{12}^{1}Γ_{11}^{2} − Γ_{11}^{2}Γ_{22}^{2},
α_{21}= 0 ⟺ G · b/g = (Γ_{22}^{1})_{u} − (Γ_{12}^{1})_{v} + Γ_{12}^{1}(Γ_{22}^{2} − Γ_{12}^{1}) − Γ_{12}^{2}Γ_{22}^{1} + Γ_{11}^{1}Γ_{22}^{1},
α_{22}= 0 ⟺ F · b/g = (Γ_{22}^{2})_{u} − (Γ_{12}^{2})_{v} + Γ_{12}^{1}Γ_{12}^{2} − Γ_{22}^{1}Γ_{11}^{2},

kde g = EG − F^{2} a b = LN − M^{2}.

Důkaz. Viz diferenciální geometrie.

Věta 2.18 Mainardi-Codazziho rovnice Platí

α_{13} = 0 ⟺ L_{v} − M_{u} = Γ_{12}^{1}L + (Γ_{12}^{2} − Γ_{11}^{1})M − Γ_{11}^{2}N,
α_{23} = 0 ⟺ M_{v} − N_{u} = Γ_{22}^{1}L + (Γ_{22}^{2} − Γ_{12}^{1})M − Γ_{12}^{2}N.

Důkaz. Viz diferenciální geometrie.

Můžeme pak formulovat hlavní větu teorie ploch:

Věta 2.19 Hlavní věta teorie ploch - Bonnet Buďte dány tři reálné funkce E, F, G s druhými spojitými derivacemi definované na nějakém okolí v R^{2} a tři reálné funkce L, M, N s prvními spojitými derivacemi definované na stejném okolí. Splňují-li tyto funkce Gaussovy a Mainardi-Codazziho rovnosti a platí-li EG − F^{2} > 0, existuje až na shodnost jednoznačně určená část plochy, která má třetí spojité derivace, tak, že E, F, G, K, M, N jsou koeficienty obou základních forem.

Důkaz. Viz diferenciální geometrie.

Z této věty například plyne, že nemůže existovat žádné izometrické zobrazení koule do roviny, protože první základní formy jsou odlišné. To je pak důležitý výsledek např. pro kartografii.

Zároveň platí pro křivost κ rovinných křivek

κ cosΦ = \frac{2FF}{ds^{2}} = \frac{2FF}{1FF}.

Pro křivky na ploše, jejichž vektor křivosti je rovnoběžný normálou plochy (Φ = 0), je pak křivost rovna

\overline{κ} = \frac{2FF}{1FF}.

Tato křivost se nazývá normálová křivost plochy. Ta závisí pouze na směru tečny, definované pomocí \frac{du}{dv}. Zvolíme-li směr tečen pevně, ale povolíme-li libovolný úhel Φ mezi vektorem křivosti křivky a normálou plochy, platí pro poloměry zakřivení, že

ρ = \overline{ρ} cosΦ, \overline{ρ} = \frac{1}{\overline{κ}}.

Protože střed oskulační kružnice křivky na ploše obdržíme ze vztahu

f + ρn_{k},

máme pak, že oskulační kružnice na kouli má střed

f + \overline{ρ}n_{f}^{∗},

a poloměr \overline{ρ}. To je obsaženo v Meusnierově větě:

Věta 2.20 Meusnierova věta Oskulační kružnice plošné křivky f(k(s)) se stejným tečným směrem t leží na kouli se středem f + \overline{ρ}n_{f}^{∗}, a poloměrem \overline{ρ} = \frac{2FF}{1FF}.

Důkaz. Viz diferenciální geometrie.

Protože normálovou křivost závisí pouze na směru tečny t, lze se omezit pro zkoumání normálové křivosti na ţjednoduché� křivky na ploše s tímto směrem tečny. Vybereme tzv. normální křivky řezu, které vzniknou průsekem roviny určené tečným vektorem t a normálami plochy n_{f} s plochou. Její vektor křivosti ukazuje ve směru normál plochy. Pro křivost \overline{κ} platí

\overline{κ} = \frac{2FF}{1FF}
= \frac{L · du^{2} + 2 · M · dudv + N · dv^{2}}{E · du^{2} + 2F · dudv + G · dv^{2}}
= \frac{L· u^{.}^{2} +2 · M· u^{.}v^{.} +N· v^{.}^{2}}{E· u^{.}^{2} +2F · u^{.}v^{.} +G· v^{.}^{2}} .

2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE

65

Abychom mohli zjistit normálovou křivost, provedeme parciální derivace podle u^{.}

a v^{.}:

\begin{aligned}\frac{\overline{κ}}{u^{.}} & = & 0 & ⟺ & (L − \overline{κ}E) u^{.} +(M − \overline{κ}F) v^{.} & = & 0 \\ \frac{\overline{κ}}{v^{.}} & = & 0 & ⟺ & (M − \overline{κ}F) u^{.} +(N − \overline{κ}G) v^{.} & = & 0. \end{aligned}

Protože však \overline{κ} závisí pouze na směru u^{.} / v^{.}, extrém nastává i pro λ · (u^{.}, v^{.}), pokud nastává v bodě (u^{.}, v^{.}). Výše uvedená lineární rovnice nemá tedy jediné řešení, tj.

| \begin{matrix}L − \overline{κ}E & M − \overline{κ}F \\ M − \overline{κ}F & N − \overline{κ}G \end{matrix} | = 0.

Definice. Gaussova křivost K je určena vztahem

K := \frac{L · N − M^{2}}{E · G − F^{2}}.

Střední křivost H je určena vztahem

H := \frac{−2 · F · M + (E · N + G · L)}{2 · (E · G − F^{2})} .

Pak lze poslední podmínku z 2.20 zapsat jako

\overline{κ}^{2} − 2 · H · \overline{κ} + K = 0.

Diskriminant této kvadratické rovnice je vždy větší nebo roven nule. Rovnice má vždy dva různé nebo jeden dvojitý reálný kořen. Má-li dva různé reálné kořeny, jedná se o minimální a maximální křivost v bodě plochy. Má-li jeden dvojnásobný reálný kořen, jedná se o středový bod, ve kterém jsou všechny křivosti stejné. Řešení kvadratické rovnice nám dává

Věta 2.21 Hlavní křivosti Tzv. hlavní křivosti, extrémy normálové křivosti \overline{κ}, jsou určeny vztahem

\begin{aligned}κ_{max} & := & H + \sqrt{H^{2} − K}, \\ κ_{min} & := & H − \sqrt{H^{2} − K}. \end{aligned}

Hlavní křivosti nám určují určité směry tečny křivky normálového řezu. Označujeme je jako směry hlavních křivostí. Plošné křivky, jejichž křivost v každém bodě křivky je rovna κ_{max} resp. κ_{min}, se nazývají čáry křivosti. Čáry křivosti pro κ_{max} resp. κ_{min} tvoří dva systémy ortogonálních plošných křivek.

66  Kritéria kvality

Metoda B-splinů

Bézierova metoda má alespoň dvě nevýhody:

• žádná lokální kontrolovatelnost: Změna Bézierova bodu nebo váhy u racionálního tvaru změní celý segment. To ztíží jemné zharmonizování návrhu.

• vysoký stupeň polynomu: Při komplexních tvarech je potřeba větší počet Bézierových bodů. S každým Bézierovovým bodem se zvýší stupeň polynomu o jeden stupeň. Polynomy vyšších stupňů zvyšují početní náročnost a počet numerických nepřesností.

Řešení, které je nasnadě, sestává z toho, že komplexní tvary složíme z jednodušších dílů, tj. z těch s nižším stupněm. Tento postup je základem metody B-splinů. Ukazuje se dokonce, že Bézierova metoda je zvláštním případem metody B-splinů. Prakticky všechny výhodné vlastnosti Bézierovy metody v geometrickém modelování se přenáší na její zobecnění. Navíc se zbavíme jmenovaných nevýhod Bézierovy metody.

1 Splinové a B-splinové funkce

Funkce, které jsou po částech složené z polynomů a ve společných bodech jsou dostatečně mnohokrát diferencovatelné, označujeme jako polynomiální spliny:

Definice. Polynomiální splinová funkce: Buďte x_{0} ≤ x_{1} ≤ … ≤ x_{k}, x_{i} ∈ R. Funkce S se nazývá splinová funkce stupně d ∈ N resp. řádu d + 1, jsou-li splněny následující podmínky:

1. S je polynom stupně d v každém dílčím intervalu [x_{i}, x_{i+1} ], 0 ≤ i < k.

2. S ∈ C^{(d−1)}[x_{0}, x_{k}].

Vektor ξ := (x_{0}, x_{1}, …, x_{k}) se nazývá uzlový vektor B-spline funkce. Funkce složené po částech z polynomů, které nesplňují druhou podmínku, se nazývají také subspline funkce. Při použití B-spline metody se Bernsteinovy polynomy B_{i}^{n} nahradí speciálními B-spline funkcemi N_{i}^{m}.

Definice. Buď ξ = (x_{0}, x_{1}, …, x_{k}) uzlový vektor. B-spline funkce je definována jako

N_{i}^{0}(x) := \{ \begin{matrix}1 & pro x ∈ [x_{i}, x_{i+1} ), \\ 0 & jinak, \end{matrix} i = 0, …, k − 1.

N_{i}^{n}(x) := \frac{x − x_{i}}{x_{i+n} − x_{i}} · N_{i}^{n−1}(x) + \frac{x_{i+n+1} − x}{x_{i+n+1} − x_{i+1}} · N_{i+1}^{n−1}(x),
0 ≤ i ≤ k − n − 1, 1 ≤ n ≤ k − 1, \frac{0}{0} := 0.

Od komponent uzlového vektoru je požadována pouze monotonie, nikoliv silná monotonie. Pro případ, že x_{i+n} − x_{i} = 0 definujeme výsledek dělení 0 jako 0.

Spočtěme B-spline funkce pro uzlový vektor ξ = (0, 0, 0, 1, 2, 3, 4, 4, 4). Výpočet lze provést následovně:

N_{0}^{0}(x) = 0
N_{1}^{0}(x) = 0

N_{2}^{0}(x) = \{ \begin{matrix}1, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{3}^{0}(x) = \{ \begin{matrix}1, & x ∈ [1, 2] \\ 0, & jinak \end{matrix}

N_{4}^{0}(x) = \{ \begin{matrix}1, & x ∈ [2, 3] \\ 0, & jinak \end{matrix}

N_{5}^{0}(x) = \{ \begin{matrix}1, & x ∈ [3, 4] \\ 0, & jinak \end{matrix}

N_{6}^{0}(x) = 0
N_{7}^{0}(x) = 0

N_{0}^{1}(x) = 0
N_{1}^{1}(x) = \{ \begin{matrix}1 − x, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{2}^{1}(x) = \{ \begin{matrix}x, & x ∈ [0, 1] \\ 2 − x, & x ∈ [1, 2] \\ 0, & jinak \end{matrix}

N_{3}^{1}(x) = \{ \begin{matrix}x − 1, & x ∈ [1, 2] \\ 3 − x, & x ∈ [2, 3] \\ 0, & jinak \end{matrix}

N_{4}^{1}(x) = \{ \begin{matrix}x − 2, & x ∈ [2, 3] \\ 4 − x, & x ∈ [3, 4] \\ 0, & jinak \end{matrix}

N_{5}^{1}(x) = \{ \begin{matrix}x − 3, & x ∈ [3, 4] \\ 0, & jinak \end{matrix}

N_{6}^{1}(x) = 0

N_{0}^{2}(x) = \{ \begin{matrix}(1 − x)^{2}, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{1}^{2}(x) = \{ \begin{matrix}(2x · (1 − x) + x · (2 − x))/2, & x ∈ [0, 1] \\ (2 − x)^{2}/2, & x ∈ [1, 2] \\ 0, & jinak \end{matrix}

N_{2}^{2}(x) = \{ \begin{matrix}x^{2}/2, & x ∈ [0, 1] \\ (x · (2 − x) + (3 − x) · (x − 1))/2, & x ∈ [1, 2] \\ (3 − x)^{2}/2, & x ∈ [2, 3] \\ 0, & jinak \end{matrix}

N_{3}^{2}(x) = \{ \begin{matrix}(x − 1)^{2}/2, & x ∈ [1, 2] \\ ((x − 1) · (3 − x) + (4 − x) · (x − 2))/2, & x ∈ [2, 3] \\ (4 − x)^{2}/2, & x ∈ [3, 4] \\ 0, & jinak \end{matrix}

N_{4}^{2}(x) = \{ \begin{matrix}(x − 2)^{2}/2, & x ∈ [2, 3] \\ (4 − x) · (3x − 8)/2, & x ∈ [3, 4] \\ 0, & jinak \end{matrix}

N_{5}^{2}(x) = \{ \begin{matrix}(x − 3)^{2}, & x ∈ [3, 4] \\ 0, & jinak \end{matrix}

Pro uzlový vektor sestávající ze dvou hodnot, 0 a 1, jež mají stejný počet výskytů, tj.

τ = (0, 0, …, 0, 1, 1, …, 1),

kde 0 se vyskytuje (n+1)−krát a 1 se vyskytuje rovněž (n+1)−krát, splývají B-spline funkce v intervalu [0, 1] s Bernsteinovými polynomy:

N_{i}^{n} = B_{i}^{n}.

Pro n = 2 platí

N_{0}^{0}(x) = 0
N_{1}^{0}(x) = 0

N_{2}^{0}(x) = \{ \begin{matrix}1, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{3}^{0}(x) = 0
N_{4}^{0}(x) = 0
N_{0}^{1}(x) = 0

N_{1}^{1}(x) = \{ \begin{matrix}1 − x, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{2}^{1}(x) = \{ \begin{matrix}x, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{3}^{1}(x) = 0

N_{0}^{2}(x) = \{ \begin{matrix}(1 − x)^{2}, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{1}^{2}(x) = \{ \begin{matrix}2x · (1 − x) & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

N_{2}^{2}(x) = \{ \begin{matrix}x^{2}, & x ∈ [0, 1] \\ 0, & jinak \end{matrix}

Věta 1.1 Vlastnosti B-spline funkcí

1. \underline{Nosné intervaly:}Nosný interval N_{i}^{n} je [x_{i}, x_{i+n+1} ), tj.

N_{i}^{n}(x) = 0 pro x ∉ [x_{i}, x_{i+n+1} ).

2. \underline{Rozklad jednotky:}Součet B-spline funkcí stupně n je 1:

∑_{i=0}^{k−n−1}N_{i}^{n}(x) = 1, x ∈ [x_{n}, x_{k−n}).

3. \underline{Pozitivita:}B-spline funkce jsou v intervalu [x_{i}, x_{i+n+1} ] nezáporné:

N_{i}^{n}(x) ≥ 0, 0 ≤ i ≤ k − n − 1, 1 ≤ n ≤ k − 1, x ∈ [x_{i}, x_{i+n+1} ].

4. \underline{Ekvidistantní uzlový vektor:}Pro ekvidistantní uzlový vektor τ = (0, 1, …, k) jsou funkce N_{i}^{m}(x) až na posun podél osy parametrů identické:

N_{i}^{n}(x) = N_{i}^{n+1} (x + 1), i = 0, 1, …, k − n − 2.

5. \underline{Derivace:} Jsou-li uzly x_{i} navzájem různé, pak N_{i}^{n} ∈ C^{n−1}, je tedy (n − 1)-krát spojitě diferencovatelná. Vyskytne-li se uzel x_{i} s násobností l_{j}, zmenší se stupeň derivovatelnosti B-spline funkce v bodě x_{i}, platí tedy N_{i}^{n} ∈ C^{n−l_{j}}.

6. \underline{Výpočet derivací:}Buď f(x) = ∑_{i=0}^{k−n−1} a_{i} · N_{i}^{n}. Pak pro derivace platí:

\begin{aligned}f^{(j)}(x) & = & ∑_{i=0}^{k−n−1} a_{i}^{(j)} · N_{i}^{n−j}, kde \\ a_{i}^{(j)} & = & \{ \begin{matrix}a_{i} & j = 0 \\ (n − j) · (a_{i}^{(j−1)} − a_{i−1}^{(j−1)})/(x_{i+n−j} − x_{i}) & j > 0, \end{matrix} i ≥ 0, \\ a_{−1}^{(j)} & = & 0 pro j ≥ 0. \end{aligned}

Důkaz. Snadné cvičení.

2 B-spline křivky

B-spline křivky se formálně reprezentují podobně jako Bézierovy segmenty, přičemž Bernsteinovy polynomy nahradíme B-spline funkcemi daného stupně. Abychom zachovali chování podobné Bézierovým křivkovým segmentům, je třeba speciální volby uzlového vektoru. Definujeme pak dvě varianty, otevřené B-spline křivky s libovolnými konečnými body a uzavřené B-spline křivky, pro které splývají počáteční a koncový bod.

Definice. Otevřená B-spline křivka má tvar

b(t) := ∑_{i=0}^{m}d_{i}N_{i}^{n}(t), t ∈ [t_{0}, t_{m+1} ], d_{i} ∈ R^{d},

kde N_{i}^{n}(t) jsou B-spline funkce příslušející k uzlovému vektoru tvaru τ = (t_{0}, …, t_{n+m+1} ), t_{0} = … = t_{n}, t_{m+1} = … = t_{n+m+1} a kontrolními body d_{i} ∈ R^{d}. Uzavřená B-spline křivka má tvar

b(t) := ∑_{i=0}^{m}d_{i}\overline{N}_{i}^{n}(t), t ∈ [t_{0}, t_{m+1} ], d_{i} ∈ R^{d},

\overline{N}_{i}^{n}(t) := \{ \begin{matrix}N_{i}^{n}(t), & t ∈ [t_{i}, t_{m+1} ], \\ N_{i}^{n}(t − t_{0} + t_{m+1} ), & t ∈ [t_{0}, t_{i}], \end{matrix} i = 0, …, m,

kde N_{i}^{n}(t) jsou B-spline funkce příslušející k uzlovému vektoru tvaru τ = (t_{0}, …, t_{n+m+1} ), t_{m+2} := t_{m+1} +(t_{1}−t_{0}), …, t_{n+m+1} := t_{n+m} +(t_{n} −t_{n−1}), a kontrolními body d_{i} ∈ R^{d}. Kontrolní body d_{i} ∈ R^{d} se rovněž nazývají de Boorovy body. Spojení skrz de Boorovy body se nazývá de Boorův polygoniální tah.

Věta 2.1 Vlastnosti B-spline křivek

1. \underline{Chování v koncových bodech:}Volba uzlů v případě otevřené B-spline křivky zaručuje, že kontrolní polygon a křivka mají stejný počáteční a koncový bod.

2. \underline{Vlastnost konvexního obalu:}B-spline křivka leží v konvexním obalu de Boorových bodů. Zejména tedy leží i v konvexním obalu de Boorova polygoniálního tahu.

3. \underline{Omezené kolísání:} Žádná přímka neprotíná B-spline křivku častěji než odpovídající B-spline polygoniální tah (variation diminishing property).

4. \underline{Lokálnost:}Změna jednoho kontrolního bodu změní křivku nejvýše lokálně, tj. při změně kontrolního bodu d_{i} se změní b(t) pouze pro t ∈ [t_{i}, t_{i+n+1} ).

5. \underline{Vícenásobné podpůrné body}přitahují křivku. Diferencovatelnost v takovýchto bodech se snižuje, a podle velikosti násobku lze vytvořit dokonce hroty.

6. \underline{Části přímek}jsou vytvořeny pomocí kolineárních podpůrných bodů.

Důkaz. Chování B-spline křivek v koncových bodech lze získat z tvaru B-splinů při dané volbě kontrolních vektorů. Stejně jako pro Bernsteinovy polynomy je nenulová hodnota nabývána pouze prvním a posledním v koncích intervalů. Vlasnost lokálnosti plyne z omezeného nosného intervalu B-splinů, tzn. oboru, ve kterém jsou nenulové. Zhruba lze říci, že obor křivky, který se změní při manipulaci s jedním de Boorovým bodem, je tím menší, čím větší je rozdíl mezi stupněm n a počtem m kontrolních bodů.

Důkaz vlastnosti konvexního obalu vyplývá okamžitě z de Boorova algoritmu výpočtu bodů ležících na nějaké B-spline křivce. De Boorův algoritmus se podobá Casteljauovu algoritmu výpočtu křivkového bodu b(t) ze zadaných kontrolních bodů. Tento pak spočíval na rekurentním vztahu pro Bernsteinovy polynomy. De Boorův algoritmus je založen na odpovídajícím vztahu pro B-spline funkce.

Algoritmus. (de Boor) Vstup: m + 1 kontrolních bodů d_{0}, d_{1}, …, d_{m}, spline stupeň n, uzlový vektor τ pro otevřenou (uzavřenou) B-spline křivku, parametrická hodnota t^{∗} ∈ [t_{0}, t_{m+1} ]. Výstup: Bod křivky b(t^{∗}).

Postup pro otevřené B-spline křivky

BEGIN

vypočtěte index i tak, že t_{i} ≤ t^{∗} < t_{i+1} , 0 ≤ i ≤ m

FOR j := 0 TO n DO

FOR l := i − n + j TO i DO IF j = 0 THEN d_{l}^{0} := d_{l} ELSE BEGIN t_{l}^{j} := (t^{∗} − t_{l})/(t_{l+n+1−j} − t_{l}); d_{l}^{j} := (1 − t_{l}^{j}) · d_{l−1}^{j−1} + t_{l}^{j} · d_{l}^{j−1} END;

b(t^{∗}) := d_{i}^{n}

END.

Postup pro uzavřené B-spline křivky

BEGIN

vypočtěte index i tak, že t_{i} ≤ t^{∗} < t_{i+1} , 0 ≤ i ≤ m

FOR j := 0 TO n DO l := i − n + j − 1; REPEAT IF l < 0 THEN BEGIN l := l + m + 1; t^{∗} := t^{∗} − t_{0} + t_{m+1} END ELSE IF l ≥ m + 1 THEN BEGIN l := l − m − 1; t^{∗} := t^{∗} + t_{0} − t_{m+1} END; IF j = 0 THEN d_{l}^{0} := d_{l} ELSE BEGIN

t_{l}^{j} := (t^{∗} − t_{l})/(t_{l+n+1−j} − t_{l});

d_{l}^{j} := (1 − t_{l}^{j}) · d_{(l−1)mod (m+1)}^{j−1} + t_{l}^{j} · d_{l}^{j−1}

END; UNTIL l = i; END; b(t^{∗}) := d_{i}^{n}

END.

Časová náročnost de Boorova algoritmu je O(n^{2} + m). Závisí tedy kvadraticky jen na obvykle malém B-spline stupni n a lineárně na počtu (m + 1) de Boorových kontrolních bodů. To je výhodnější, než při de Casteljauově algoritmu, jehož časová náročnost závisí kvadraticky na počtu kontrolních bodů.

Také v případě B-spline křivek je relativně jednoduše možmé vsunout nové kontrolní de Boorovy body bez změny podoby křivky. Abychom mohli přidat nový uzel násobnosti r a tím odpovídajícně zvýšit počet kontrolních bodů, doplníme nejprve uzlový vektor o r-násobný uzel t^{∗}. Buďte t_{l}, t_{l+1} uzly, mezi které vsuneme t^{∗}. Použitím pomocných bodů d_{i}^{j}, jež vzniknou provedením de Boorova algoritmu pro hodnotu t = t^{∗}, obdržíme nový kontrolní polygon nahrazením dílčího kontrolního polygonu

d_{l−n}, d_{l−n+1} , …, d_{l} starého kontrolního polygonu dílčím polygonem

d_{l−n} = d_{l−n}^{0}, d_{l−n+1}^{1} , …, d_{l−n+r}^{r} , …, d_{l}^{r}, …, d_{l}^{0}.

Věta 2.2 Vložení kontrolních bodů v B-spline křivkách Buď τ = (t_{0}, …, t_{n+m+1} ) uzlový vektor nějaké B-spline křivky, t^{∗} ∈ [t_{l}, t_{l+1} ), d_{0}, …, d_{m} kontrolní de Boorovy body B-spline křivky b(t). Buď \overline{τ} = (\overline{t}_{0}, …, \overline{t}_{n+m+r+1} ), r ≤ n definován jako

\begin{aligned}\overline{t}_{j} & := & t_{j}, & j = 0, …, l, \\ \overline{t}_{l+j} & := & t^{∗}, & j = 1, …, r, \\ \overline{t}_{l+j+r} & := & t_{l+j} , & j = 1, …, n + m − l + 1, \end{aligned}

a kontrolní de Boorovy body \overline{d}_{0}, \overline{d}_{1}, …, \overline{d}_{m+r} jakožto

\overline{d}_{j}  := d_{j},  j = 0, …, l − n − 1,
\overline{d}_{l−n+j}  := d_{l−n+j}^{j} , j = 0, …, r,
\overline{d}_{l−n+r+j} := d_{l−n+r+j}^{r} , j = 1, …, n − r,
\overline{d}_{l+j}  := d_{l}^{r−j},  j = 1, …, r,
\overline{d}_{l+r+j}  := d_{l+j} ,  j = 1, …, m − l.

Pak splývá B-spline křivka \overline{b}(t) pro uzlový vektor \overline{τ} se zadanou křivkou b(t).

Důkaz. Cvičení.

Algoritmus pro vložení kontrolních bodů v B-spline křivkách lze snadno odvodit z předchozí věty. Časová náročnost vložení jednoho kontrolního bodu násobnosti r je O(rn + m).

3 B-spline plochy

Techniku B-splinů lze stejnou konstrukcí jako u čtyřúhelníkových Bézierových segmentů rozšířit na plochy.

Definice. Zadáno: Kontrolní de Boorova síť čtyřúhelníkové B-spline plochy je určena (k+1)·(l+1) de Boorovými kontrolními body d_{i,j} ∈ R^{3}, i = 0, …, k, j = 0, …, l, stupně m a n, uzlové vektory μ = (u_{0}, …, u_{m+k+1} ), ν = (v_{0}, …, v_{m+k+1} ), jež splňují stejná kriteria jako pro otevřené nebo uzavřené křivky. B-spline plocha v R^{3} je tvaru:

x(u, v) := ∑_{i=0}^{k} ∑_{j=0}^{l}d_{i,j} · N_{i}^{m}(u) · N_{j}^{n}(v), u, v ∈ [u_{0}, u_{k+1} ) × [v_{0}, v_{l+1} ).

Stejně jako pro čtyřúhelníkové Bézierovy segmenty lze vypočítat body na ploše vícenásobnou aplikací algoritmu pro výpočet bodů na křivkách odpovídajícího typu:

Algoritmus. (de Boorův algoritmus pro B-spline plochy) Vstup: Kontrolní de Boorova síť čtyřúhelníkové B-spline plochy určená (k+1)·(l+1) de Boorovými kontrolními body d_{i,j} ∈ R^{3}, i = 0, …, k, j = 0, …, l, stupni m a n, uzlovými vektory μ = (u_{0}, …, u_{m+k+1} ), ν = (v_{0}, …, v_{m+k+1} ) a parametrické hodnoty u^{∗} a v^{∗}. Výstup: bod x(u^{∗}, v^{∗}) na ploše. Postup:

1. Vypočtěte d_{j} := ∑_{i=0}^{k} d_{i,j} · N_{i}^{m}(u^{∗}) podle de Boorova algoritmu pro křivky, j = p − n, …, p, v_{p} ≤ v^{∗} < v_{p+1} .

2. Vypočtěte x(u^{∗}, v^{∗}) := ∑_{j=0}^{l} d_{j} ·N_{j}^{n}(u^{∗}) podle de Boorova algoritmu pro křivky.

Časová náročnost de Boorova algoritmu pro B-spline plochy je O(n·m^{2}+n^{2}+k+l).

Věta 3.1 Vlastnosti B-spline ploch

1. \underline{Parametrické linie:} Parametrické linie (u=const. resp. v =const.) jsou B-spline křivky s de Boorovými kontrolními body

d_{j} := ∑_{i=0}^{k}d_{i,j} · N_{i}^{m}(u) resp. d_{i} := ∑_{j=0}^{l}d_{i,j} · N_{j}^{n}(v)

2. \underline{Lokálnost:} Změna jednoho kontrolního de Boorova bodu d_{i,j} změní plochu nejvýše lokálně, tj. při změně kontrolního bodu d_{i,j} se změní x(u, v) pouze pro (u, v) ∈ [u_{i},_{i+m+1} ) × [v_{j},_{j+n+1} ). Zejména tedy část plochy parametrizovatelná (u, v) ∈ [u_{i},_{i+m+1} ) × [v_{j},_{j+n+1} ) je ovlivnitelná pouze kontrolními de Boorovými body d_{i−m,j−n}, …, d_{i,j}.

3. \underline{Zjemnění kontrolní sítě:}nové uzlové linie lze vytvořit tak, že se aplikuje algoritmus pro vložení nových uzlů do křivek na každý řádek resp. sloupec de Boorovy kontrolní sítě.

4. \underline{Konvergence ke ploše:}při iteraci algoritmu pro vložení nových uzlů jsou vytvářeny de Boorovy kontrolní sítě, které konvergují k ploše.

Důkaz. Přenesením odpovídajících tvrzení pro křivky.

4 B-spline metoda a Bézierova metoda

Křivka, která je po částech složená z Bézierových segmentů, se označuje jako Bézierova křivka. Bézierovy segmenty se přitom vhodně přeparametrizuje, abychom mohli obdržet jednotně průchozí parametrický interval výsledné křivky. Změna parametrizace nezmění nic na vlastnostech Bézierových segmentů. Při použití Casteljauova algoritmu se namísto s poměrem t : (1 − t) pracuje s poměrem

\frac{t − t_{k}}{t_{k+1} − t_{k}} : \frac{1 − (t − t_{k})}{t_{k+1} − t_{k}}.

Definice. Zadáno: Kontrolní body b_{k,i} ∈ R^{d}, k = 0, …, m, i = 0, …, n, uzlový vektor τ = (t_{0}, …, t_{m+1} ). Bézierova křivka R^{d} je tvaru:

b(u) := ∑_{i=0}^{n}b_{k,i} · B_{i}^{n}(\frac{t − t_{k}}{t_{k+1} − t_{k}}), t ∈ [t_{k}, t_{k+1} ), k = 0, …, m

tj. skládá se po částech z Bézierových křivkových segmentů.

Protože se B-spline křivky skládají po částech z polynomiálních křivek a tyto lze vyjádřit jako Bézierovy křivkové segmenty, lze B-spline křivky vyjádřit jakožto Bézierovy křivky. Následující věta nám ukazuje možnost určení Bézierových bodů z de Boorových kontrolních bodů.

Věta 4.1 Reprezentace B-spline křivek jakožto Bézierových křivek Buď dána otevřená B-spline křivka

b(t) := ∑_{i=0}^{m}d_{i}N_{i}^{n}(t), t ∈ [t_{0}, t_{m+1} ], d_{i} ∈ R^{d},

s uzlovým vektorem tvaru τ = (t_{0}, …, t_{n+m+1} ), t_{0} = … = t_{n}, t_{m+1} = … = t_{n+m+1} . Buď \overline{τ} uzlový vektor, který vznikne vložením uzlů tak, že každý uzel má násobnost n + 1, tj. \overline{τ} = (\overline{t}_{0}, …, \overline{t}_{(m−n+2)(n+1)−1} ), kde

\begin{aligned}\overline{t}_{j} & := & t_{j}, & j = 0, …, n, \\ \overline{t}_{l(n+1)+j} & := & t_{n+l} , & l = 1, …, m − n, j = 0, …, n, \\ \overline{t}_{(m−n+1)(n+1)+j} & := & t_{m+j+j} , & j = 0, …, n, \end{aligned}

Dále buďte \overline{d}_{j} ∈ R^{d}, j = 0, …, (m − n + 1) · (n + 1) − 1, de Boorovy kontrolní body, vytvořené algoritmem pro vložení kontrolních bodů v B-spline křivkách, a

b_{k,i}  := \overline{d}_{k(n+1)+i} , k = 1, …, m − n, i = 0, …, n.

Pak platí

b(t) := ∑_{i=0}^{n}b_{k,i} · B_{i}^{n}(\frac{t − t_{n+k}}{t_{n+k+1} − t_{n+k}} ), t ∈ [t_{n+k} , t_{n+k+1} )], k = 0, …, m − n,

tj. B-spline křivku lze vyjádřit jakožto Bézierovu křivku.

Důkaz. V důkazu se použije, že Bernsteinovy polynomy jsou reprezentovatelné jako B-spline funkce nad nějakým uzlovým vektorem, jehož uzly nabývají pouze dvou hodnot, a to stejně často. Zvýšením násobnosti každého uzlu uzlového vektoru dané B-spline křivky na n + 1 pomocí algoritmu na vložení se převedou ty dané B-spline funkce, které leží v dané křivce, na Bernsteinovy polynomy na odpovídajících nosných intervalech. Protože tvar křivky se přitom nezmění, obdržíme vyjádření B-spline křivky jakožto Bézierovy křivky.

Algoritmicky lze transformaci provést použitím de Boorova algoritmu. Algoritmus na reprezentaci B-spline křivky jakožto Bézierovy křivky plyne bezprostředně z předchozí věty.

Rozklad B-spline křivky na Bézierovy segmenty nám poskytuje hladký přechod odpovídající B-spline křivce mezi Bézierovými segmenty a rovněž odpovídajícími Bézierovými křivkovými segmenty. Bézierovy body navzájem proti sobě působících křivkových segmentů nejsou proto nezávislé. Pro C^{p}-přechod lze tuto souvislost vyjádřit následovně:

Věta 4.2 C^{p}-přechod mezi Bézierovými segmenty Bézierova křivka

b(t) := ∑_{i=0}^{n}b_{k,i} · B_{i}^{n}(\frac{t − t_{k}}{t_{k+1} − t_{k}}), t ∈ [t_{k}, t_{k+1} )], k = 0, …, m

je právě tehdy p-krát spojitě diferencovatelná, když (t_{k+1} − t_{k})^{−r}Δ^{r}b_{k,n−r} = (t_{k+2} − t_{k+1} )^{−r}Δ^{r}b_{k,n−r}, r = 0, …, m, přičemž Δ^{0}b_{k,i} := b_{k,i}, Δ^{j}b_{k,i} := Δ^{j−1}b_{k,i+1} − Δ^{j−1}b_{k,i}, j ≥ 1.

Důkaz. Tvrzení plyne bezprostředně z věty o reprezentaci derivací Bézierových křivkových segmentů v druhé kapitole.

Jsou-li Bézierovy body k-tého segmentu dány, je pak určeno prvních p+1 Bézierových bodů okrajovými podmínkami jednoznačně. Lze je pak spočítat Casteljauovým algoritmem pro t = (t_{k+2} − t_{k+1} )/(t_{k+1} − t_{k}). Bézierovy body mimo okruh vlivu okrajových podmínek lze volně volit.

Každou Bézierovu křivku lze pak obráceně reprezentovat jako B-spline křivku. Uzly můžeme získat jakožto odpovídající znásobení hranic intervalu, de Boorovy body odpovídají Bézierovým bodům. Při derivaci vyššího řádu lze zadat úspornější reprezentaci Bézierovy křivky jakožto B-spline křivky. Pro kubické Bézierovy křivky platí:

Věta 4.3 (Transformace kubických Bézierových křivek do B-spline vyjádření) Buď

b(t) = ∑_{i=0}^{3}b_{k,i} · B_{i}^{n}(\frac{t − t_{k}}{t_{k+1} − t_{k}}), t ∈ [t_{k}, t_{k+1} )], k = 0, …, m

kubická C^{2}-Bézierova křivka. Pak splývají de Boorovy body

d_{0}  := b_{0,0},
d_{1}  := b_{0,1},
d_{j+1} := b_{j−1,2} + \frac{(t_{j+1} − t_{j})}{(t_{j} − t_{j−1})} · (b_{j−1,2} − b_{j−1,1})
= b_{j,2} + \frac{(t_{j}−t_{j−1})}{(t_{j+1} −t_{j})} · (b_{j,1} − b_{j,2}), j = 1, …, m,
d_{m+2} := b_{m,2},
d_{m+3} := b_{m,3},

s Bézierovou křivkou pro danou kubickou B-spline křivku s uzlovým vektoerm \overline{τ} := (\overline{t}_{0}, \overline{t}_{1}, …, \overline{t}_{m+7} ,), kde

\begin{aligned}\overline{t}_{j} & := t_{0}, & j = 0, …, 3, \\ \overline{t}_{3+j} & := t_{j}, & j = 0, …, m, \\ \overline{t}_{m+4+j} & := t_{m+1} , & j = 0, …, 3. \end{aligned}

Důkaz. Cvičení.

Analogicky jako pro křivky lze skládat Bézierovy plošné segmenty. Vzájemné spojení dvou plošných segmentů se provádí podél společné okrajové křivky. Jak pro trojúhelníkové tak pro čtyřúhelníkové segmenty jsou tři resp. čtyři hraniční křivky Bézierovy křivkové segmenty, které jsou určeny třemi resp. čtyřmi okrajovými polygoniálními tahy kontrolní sítě. Spojitý přechod mezi oběma plochami se dosáhne právě tehdy, když oba odpovídající okrajové polygoniální tahy splývají. Tento okrajový polygoniální tah je kontrolní polygoniální tah společné okrajové křivky.

Požadavek C^{p}-přechodu lze pro čtyřúhelníkové Bézierovy plošné části redukovat na požadavek pro C^{p}-přechod mezi Bézierovými segmenty:

Věta 4.4 C^{p}-přechod mezi čtyřúhelníkovými Bézierovými segmenty Nechť je dána část plochy příslušející k b_{i,j}, i = −n, …, 0, j = 0, …, m parametrizovaná přes [u_{0}, u_{1}] × [v_{0}, v_{1}] a část plochy příslušející k b_{i,j}, i = 0, …, n, j = 0, …, m parametrizovaná přes [u_{1}, u_{2}] × [v_{0}, v_{1}] tak, že obě jsou složeny podél parametru u = u_{1}. Výsledná plocha je v dané parametrické reprezentaci právě tehdy p-krát spojitě diferencovatelná, jestliže všechny Bézierovy křivkové segmenty pro kontrolní body

b_{i,j^{∗}}, i = −n, …, 0,

a

b_{i,j^{∗}}, i = 0, …, n,

vykazují C^{p}-přechod pro u = u_{1}, j^{∗} = 0, …, m.

Důkaz. Využitím odpovídajících tvrzení pro Bézierovy křivkové segmenty.

5 Racionální B-spline metoda (NURBS)

Stejně jako Bézierovy křivky lze B-spline křivky zobecnit na racionální B-spline křivky, které lze rovněž opět pojímat jako projekce obyčejných B-spline křivek z prostoru dimenze o jednotku většího. Formálně definujeme:

Definice. Zadáno: m + 1 kontrolních bodů d_{0}, d_{1}, …, d_{m} ∈ R^{3}, (m + 1) vah δ_{i} > 0, i = 0, …, m, spline stupeň n, uzlový vektor τ = (τ_{0}, τ_{1}, …, τ_{n+m+1} ) pro otevřenou (uzavřenou) B-spline křivku. Racionální B-spline křivka (NURBS-křivka): má tvar

b(t) := \frac{∑_{i=0}^{m} δ_{i}d_{i}N_{i}^{n}(t)}{∑_{i=0}^{m} δ_{i}N_{i}^{n}(t)}, t ∈ [t_{0}, t_{m+1} ].

Zkratka NURBS znamená Non Uniform Rational B-Splines. Non Uniform znamená, že uzlový vektor je jako doposud libovolně volitelný. Racionální B-spline křivku pro d−dimenzionální de Boorovy body d_{i} lze uvažovat jako perspektivní projekci vzhledem k počátku na rovinu x_{d} = 1 obyčejné B-spline křivky

b^{∗}(t) = (\begin{matrix}b̂(t) \\ δ(t) \end{matrix}) := ∑_{i=0}^{m}(\begin{matrix}δ_{i}d_{i} \\ δ_{i} \end{matrix} )N_{i}^{n}(t)

k d + 1-dimenzionálním de Boorovým bodům (\begin{matrix}δ_{i}d_{i} \\ δ_{i} \end{matrix} ).

Věta 5.1 Vlastnosti racionálních B-spline křivek

1. \underline{Lokálnost:}Změna jednoho kontrolního bodu změní křivku nejvýše lokálně, tj. při změně kontrolního bodu d_{i} se změní b(t) pouze pro t ∈ [t_{i}, t_{i+n+1} ).

2. \underline{Vlastnost konvexního obalu:}B-spline křivka b(t) leží v konvexním obalu de Boorových bodů d_{i}.

3. \underline{Omezené kolísání:} Žádná přímka neprotíná B-spline křivku častěji než odpovídající B-spline polygoniální tah (variation diminishing property).

4. \underline{Výpočet křivkových bodů:}Aplikací de Boorova algoritmu na projektivní tvar a následnou projekcí.

Důkaz. Bezprostřední.

Rovněž u B-spline ploch s třídimenzionálními kontrolními body lze racionální formu považovat jako perspektivní projekci ţobyčejného tvaru� s čtyřdimenzionálními kontrolními body:

Definice. Zadáno: Uzlové vektory μ = (u_{0}, u_{1}, …, u_{m+k+1} ) pro B-spline funkce N_{i}^{m}(u) a ν = (v_{0}, v_{1}, …, v_{n+l+1} ) pro B-spline funkce N_{j}^{n}(u), (k + 1) · (l + 1) kontrolních bodů d_{i,j} ∈ R^{3}, váhy δ_{i,j} > 0, i = 0, …, k, j = 0, …, l, stupně m a n. Racionální B-spline plocha: má tvar

b(t) := \frac{∑_{i=0}^{k} ∑_{j=0}^{l} δ_{ij}d_{ij}N_{i}^{n}(u)N_{j}^{m}(v)}{∑_{i=0}^{k} ∑_{j=0}^{l} δ_{ij}N_{i}^{n}(u)N_{j}^{m}(v)}, (u, v) ∈ [u_{0}, u_{k+1} ) × [v_{0}, v_{l+1} ).

Platí:

Věta 5.2 Vlastnosti racionálních B-spline ploch

1. \underline{Vlastnost konvexního obalu:}B-spline plocha b(u, v) leží v konvexním obalu de Boorových bodů d_{ij}.

2. \underline{Výpočet bodů plochy:}Aplikací de Boorova algoritmu na směr u- a v- v R^{4} a následnou projekcí.

Důkaz. Analogicky jako u racionálních Bézierových segmentů a racionálních B-spline křivek.

6 Přehled k B-spline metodě

Spline funkce se používají zejména v numerické matematice. Tedy obvykle učebnice numerické matematiky obsahují úvod do teorie splinů. B-spline křivky a plochy patří ke standardní látce diferenciálně geometrického modelování a věnují se jim všechny učebnice z této oblasti.

Jeden z možných pohledů na B-spline funkce, který umožní tento pojem dále zobecnit je považovat je za průměty (stíny) transparentního polyedru. Můžeme tedy reprezentovat B-spline funkci N_{i}^{m} jakožto transparentní stín simplexu v R^{m+1} v jednodimenzionálním podprostoru. Přitom bod v jednodimenzionálním podprostoru patří ke stínu, pokud jím procházející nadrovina protíná simplex. Síla stínu je pak objem řezu nadroviny a simplexu. Pro m = 1 jsou nadroviny přímky. Projekce pak odpovídá obvyklé rovnoběžné projekci, síla stínu délky části přímky obsažené v simplexu.

Místo jednodimenzionálního podprostoru lze rovněž vybrat dvoudimenzionální podprostor. Simplexy lze nahradit jinými polyedry.

Jiný přístup k Bézierově metodě a metodě B-splinů je polární reprezentace polynomů. Ke každé polynomiální křivce p : R → R^{d}, p(t) = ∑_{i=0}^{n} a_{i}t^{i}, existuje jednoznačně určené symetrické multiafinní zobrazení p̂ : R^{n} → R^{d} tak, že

p = p̂(t, …, t),

totiž

p̂(x_{1}, …, x_{n}) = ∑_{i=0}^{n}a_{i}(\begin{matrix}n \\ i \end{matrix})^{−1}σ_{i}(x_{1}, …, x_{n})

kde σ_{i}(x_{1}, …, x_{n}) jsou elementární symetrické polynomy tvaru

σ_{i}(x_{1}, …, x_{n}) := ∑_{1≤k_{1}<...<k_{i}≤n}x_{k_{1}} · . . . · x_{k_{i}}, i = 0, …, n.

Zobrazení f : R → R^{d} se nazývá afinní, jestliže

f(∑_{i=1}^{m}a_{i}x^{i}) = ∑_{i=1}^{m}a_{i}f(x^{i})

pro všechna x_{1}, …, x_{n} ∈ R a pro všechna a_{1}, …, a_{n} ∈ R taková, že ∑_{i=1}^{m} a_{i} = 1. Zobrazení f : R^{m} → R^{d} se nazývá multiafinní, jestliže zobrazení f(c_{1}, …, c_{j−1},., c_{j+1} , …, c_{n}) : R → R^{d} je afinní pro všechna c_{1}, …, c_{j−1}, c_{j+1} , …, c_{n} ∈ R, tj. je ve všch komponentách afinní. Lze pak dokázat, že lze i-tý Bézierův bod b_{i} reprezentovat pomocí křivky p jakožto

b_{i} = p̂(0, …, 0, 1, …, 1),

přičemž prvních n − i argumentů je rovno 0, zbývající argumenty jsou rovny 1. Pro B-spline křivky p(t) = ∑_{i=0}^{m} d_{i}N_{i}^{n}(t) nad uzlovým vektorem (t_{0}, …, t_{m+n+1} ) buď b̂_{j}(t) polární tvar polynomiální křivky, která vznikne omezením na neprázdný interval [t_{j}, t_{j+1} ). Pak můžeme l-tý kontrolní bod d_{l}, j − n ≤ l ≤ j, reprezentovat jako

d_{l} = b̂_{j}(t_{l+1} , …, t_{l+n} ), l = j − n, …, j.

Polární reprezentace nám umožní uniformní pohled na Bézierovu metodu a Bspline metodu společně s dalšími omezeními.

Interpolace a aproximace

U interpolace se jedná o to, abychom z předem zadaných částí jistého tvaru doplnili celkový tvar. Například mohou být zadány jednotlivé body, které se mají spojit (proložit) křivkou. Při aproximaci se předpokládá, že zadané části nemusí patřit nutně pouze ke konstruovanému tvaru. Měly by však mu být co nejvíce možno přiblíženy.

Aplikací je interaktivní geometrické modelování. Křivka je pak jednoznačně určena posloupností zadaných opěrných bodů a interpolačním postupem. Manipulací bodů lze křivku převést do požadovaného tvaru. To odpovídá postupu při Bézierově a Bspline technikám, s tím rozdílem, že při interpolaci jsou kontrolní body místa dotyku a tím leží na křivce.

Jinou podstatnou aplikaci v souvislosti s geometrickým modelováním nachází interpolační a aproximační metody při shromažďování dat. Siluetu výrobku lze převzít do modelovacího systému, který ţohmatáním� zjistí posloupnost signifikantních bodů a převezme ji do počítače. Z těchto bodů se pak vypočte úplná silueta interpolací nebo aproximací.

1 Interpolace s křivkami

Buď dána posloupnost bodů p_{0}, p_{1}, …, p_{m} ∈ R^{d}. Hledáme křivku spojující výše uvedené body. Body se rovněž nazývají místa dotyku. Protože by měly tyto body ležet libovolně, je vhodné pracovat s křivkou v parametrické reprezentaci.

Abychom mohli provést interpolaci v parametrické reprezentaci, přiřadíme každému bodu křivky p_{i} hodnotu parametru t_{i}. Parametrické hodnoty musí splňovat podmínku t_{i} < t_{i+1} , i = 0, …, m − 1. Hodnota t_{0} definuje začátek požadovaného parametrického intervalu, t_{m} jeho konec. Jinak lze body t_{i} zvolit zcela libovolně.

Definice. Zadáno: Opěrné body (t_{j}, p_{j}), t_{j} ∈ R, p_{j} ∈ R^{d}, j = 0, …, m, t_{j} < t_{j+1} . Interpolační křivka v parametrické reprezentaci: je křivka k(t),

k : R → R^{d}, t ∈ [t_{0}, t_{m}],

kde

k(t_{i}) = p_{i}

pro všechna i.

Příkladem takovéto interpolace je interpolace pomocí tahů úsečkou, tj.

k(t) = p_{i} + \frac{t − t_{i}}{t_{i+1} − t_{i}} · (p_{i+1} − p_{i}), t ∈ [t_{i}, t_{i+1} ], i = 0, …, m − 1.

Křivka je sice spojitá, ale v místech dotyku není hladká.

1.1 Interpolace pomocí polynomů

Polynomiální křivky nám dovolí hladkou interpolaci daných opěrných míst. Lze je v názorné formě vytvořit pomocí Lagrangeových polynomů.

Definice. Zadáno: Body x_{j} ∈ R, j = 0, …, m, x_{j} < x_{j+1} . Lagrangeův polynom stupně m: je tvaru

L_{i}^{m}(x) = \frac{∏_{j=0,...,m,j≠i} (x − x_{j})}{∏_{j=0,...,m,j≠i} (x_{i} − x_{j})}, i = 0, …, m.

Lagrangeovy polynomy jsou společně s momomiálními polynomy a Bernsteinovými polynomy další známý příklad pro polynomiální bázi. Obdržíme pak

Věta 1.1 Polynomiální interpolace, Lagrangeův interpolační vzorec Buď dáno m + 1 opěrných míst p_{0}, p_{1}, …, p_{m} ∈ R^{d}, parametr t_{i} ∈ R pro p_{i}, i=0, …, m, t_{i} < t_{i+1} . Polynomiální křivka

p(t) = ∑_{i=0}^{m}p_{i}L_{i}^{m}(t),

kde L_{i}^{m}(x) jsou Lagrangeovy polynomy stupně m příslušející bodu t_{i}, i = 0, …, m, interpoluje zadanou posloupnost bodů. Je jednoznačně určena, tzn. jediná polynomiální křivka s touto vlastností.

Důkaz. p(t) je zřejmě polynomiální křivka stupně m. p(t) interpoluje zadanou posloupnost bodů, protože

L_{i}^{m}(t) = δ_{ij} = \{ \begin{matrix}1, & i = j, \\ 0, & i ≠ j \end{matrix} i, j = 0, …, m.

Kdyby tato interpolace nebyla jednoznačná, byl by rozdíl dvou polynomiálních křivek polynomiální křivka maximálního stupně m. Protože rozdíl má alespoň m + 1 kořenů t_{0}, …, t_{m}, je roven identicky 0, tj. odtud plyne jednoznačnost.

Další práce s takto interpolovanou křivkou v geometrickém modelovacím systému vyžaduje obvykle přechod k jiné bázi, např. monomiální bázi x^{i} nebo Bernsteinově bázi B_{i}^{n}(x).

Věta 1.2 Transformace Lagrangeova vyjádření do monomiálního vyjádření Buď p(x) := ∑_{i=0}^{m} p_{i}L_{i}^{m}(x) polynom v Lagrangeově reprezentaci, L_{i}^{m}(x) jsou Lagrangeovy polynomy stupně m příslušející bodu x_{i}, i = 0, …, m. Pak je p(x) := ∑_{i=0}^{m} a_{i}x^{i}, kde

( \begin{matrix}a_{0} \\ a_{1} \\ … \\ a_{m} \end{matrix} ) := ( \begin{matrix}1 & x_{0} & x_{0}^{1} & … & x_{0}^{m} \\ 1 & x_{1} & x_{1}^{1} & … & x_{1}^{m} \\ … & … & … & … \\ 1 & x_{m} & x_{m}^{1} & … & x_{m}^{m} \end{matrix} )^{−1} ( \begin{matrix}p_{0} \\ p_{1} \\ … \\ p_{m} \end{matrix} ) .

Důkaz. Plyne bezprostředně z interpolační podmínky.

U křivek je tuto transformaci aplikovat na každou souřadnici. Transformační matice v neinvertovaném tvaru se nazývá Vandermondova matice.

Casteljauův algoritmus slouží u Bézierovy metody k tomu, abychom vypočetli k zadané parametrické hodnotě odpovídající křivkový bod. Analogický algoritmus podobného tvaru platí také pro Lagrangeovo vyjádření:

Algoritmus. (Aitkenova polynomiální interpolace) Vstup: Opěrné body (t_{j}, p_{j}), t_{j} ∈ R, p_{j} ∈ R^{d}, j = 0, …, m, t_{j} < t_{j+1} , parametrická hodnota t^{∗} ∈ [t_{0}, t_{m}]. Výstup: Bod křivky p(t^{∗}).

BEGIN

FOR i := 0 TO m DO p_{i}^{0} := p_{i};

FOR j := 1 TO m DO

FOR i := j TO m DO

p_{i}^{j} := \frac{t_{i} − t^{∗}}{t_{i} − t^{i−j}} · p_{i−1}^{j−1} + \frac{t^{∗} − t_{i−j}}{t_{i} − t^{i−j}} · p_{i}^{j−1};

p(t^{∗}) := p_{m}^{m}

END.

Časová náročnost Aitkenova algoritmu je O(m^{2}). Následující algoritmus podle Newtona má tu výhodu, že po předzpracovávající době O(m^{2}) lze spočítat bod křivky pro libovolnou hodnotu parametru v čase O(m).

Algoritmus. (Newtonova polynomiální interpolace) Vstup: Opěrné body (t_{j}, p_{j}), t_{j} ∈ R, p_{j} ∈ R^{d}, j = 0, …, m, t_{j} < t_{j+1} . Výstup: (m + 1) koeficientů p_{i}^{i}, i = 0, …, m, z kterých lze pro libovolnou parametrickou hodnotu t^{∗} ∈ [t_{0}, t_{m}] vypočíst bod křivky p(t^{∗}). Předzpracování:

BEGIN

FOR i := 0 TO m DO p_{i}^{0} := p_{i};

FOR j := 1 TO m DO

FOR i := j TO m DO

p_{i}^{j} := (p_{i}^{j−1} − p_{i−1}^{j−1})/(t_{i} − t^{i−j})

END;

Vyhodnocení:

BEGIN

FOR j := m − 1 TO 0 DO p_{j}^{j} := p_{j+1}^{j+1} · (t^{∗} − t_{j}) + p_{j}^{j};

p(t^{∗}) := p_{0}^{0}

END.

Vektory p_{i}^{j} se rovněž označují jako dělené diference.

Častým záměrem při interpolaci je zachycení zadané křivky, jejíž podoba je je dána geometricky, ale ne formálním popisem. Interpolační křivka splývá v kontrolních bodech se zadanou křivkou, obecně ne však všude. Následující věta nám charakterizuje kvalitu aproximace pro polynomiální interpolaci:

Věta 1.3 Aproximační chování polynomiální interpolace Buďte dány body (x_{i}, p_{i}), i = 0, …, m, p_{i} ∈ R, p(x) = ∑_{i=0}^{m} p_{i}L_{i}^{m} odpovídající interpolační polynom. Dále buď f ∈ C^{n}[x_{0}, x_{n}], f(x_{i}) = p_{i}, i = 0, …, m, funkce s omezenou (n + 1)-ní derivací:

|f^{n+1} (x)| ≤ M pro x ∈ [x_{0}, x_{n}].

Pak platí

|f(x) − p(x)| ≤ \frac{M}{(n + 1} )! · |(x − x_{0}) · . . . · (x − x_{n})|.

Důkaz. Jedná se o standardní tvrzení z numerické matematiky.

Zjemnění dělení opěrných bodů nemusí nutně vést k lepší aproximaci. Při neobratné volbě posloupnosti opěrných bodů není zaručena stejnoměrná konvergence k aproximované funkci. Ke každé dané posloupnosti opěrných bodů v intervalu [a, b] existuje f ∈ [a, b] tak, že příslušná posloupnost {p_{n}} polynomů nekonverguje stejnoměrně na [a, b] k f.

Opačně lze však dosáhnout při vhodné volbě opěrných bodů stejnoměrnou konvergenci. Ke každé funkci f ∈ C[a, b] existuje posloupnost opěrných bodů v intervalu [a, b] tak, že příslušná posloupnost {p_{n}} interpolačních polynomů konverguje stejnoměrně na intervalu [a, b] k f.

Na začátku této kapitoly zůstala konkrétní volba parametru pro opěrné body otevřená. Křivka vzniklá při interpolaci závisí na parametrizaci, tj. na volbě hodnot parametrů t_{i} v opěrných bodech p_{i}. Jednou možností je stejnoměrné rozdělení intervalu parametrů, tedy pro interval parametrů [0, 1] pomocí hodnot t_{i} = i/m, i = 0, …, m. Nevýhodné na této volbě je, že části křivek s co možná silně rozdílnou délkou jsou definovány na intervalech parametrů stejné délky. To pak může vést k silně kolísajícím křivkám. Proto také je vidět na interpolačních polynomech s větším počtem opěrných bodů, tzn. o něco více než 5, charakter vlnění. Křivka obsahuje změny, které neodpovídají citem hladké interpolaci zadaných bodů.

Vhodnější je parametrizace vzhledem ke délce křivky. To lze odůvodnit tím, že ve vzorci

κ = \sqrt{(k′ ∗ k′)(k′′ ∗ k′′) − (k′ ∗ k′′)^{2}} ; (k′ ∗ k′)^{\frac{3}{2}}

pro zakřivení je jmenovatel = 1, takže malé nebo velké hodnoty derivace, které by mohly vyvolat kolísání zakřivení, jsou vyloučeny.

Pro odhad délky křivky je obvyklé použít euklidovskou vzdálenost dvou za sebou následujících bodů. Pak obdržíme

t_{0} = 0, t_{i} = \frac{∑_{j=0}^{i−1} ||p_{j+1} − p_{j}||}{∑_{j=0}^{m−1} ||p_{j+1} − p_{j}||}, i > 0.

Na základě takto obdržené vhodnější interpolační křivky lze provést odhad vyššího řádu, abychom iterativně ještě lépe přiblížili parametrizaci dle délky křivky.

Další možností oládání interpolačního chování je zvážení dodatečné informace. Při Hermiteovské interpolaci máme k dispozici derivace v opěrných bodech, tedy pro parametrické vyjádření máme tečné vektory:

Věta 1.4 Hermiteovská interpolace Buď dáno m + 1 opěrných míst p_{0}, p_{1}, …, p_{m} ∈ R^{d} s derivacemi p′_{0}, p′_{1}, …, p′_{m} ∈ R^{d}, parametr t_{i} ∈ R pro p_{i}, i=0, …, m, t_{i} < t_{i+1} . Polynomiální křivka

p(t) = ∑_{i=0}^{m}p_{i}A_{i}^{m}(t) + p′_{i}B_{i}^{m}(t),

kde

\begin{aligned}A_{i}^{m}(t) & := & (1 − 2 · L_{i}^{m}′(t_{i})(t − t_{i})) · L_{i}^{m}(t)^{2}, \\ B_{i}^{m}(t) & := & (t − t_{i}) · L_{i}^{m}(t)^{2}, \end{aligned}

L_{i}^{m}(t) jsou Lagrangeovy polynomy stupně m příslušející bodu t_{i}, i = 0, …, m, interpoluje zadanou posloupnost bodů a derivací.

Důkaz. Viz numerická matematika.

Hermiteovskou interpolaci lze považovat za zobecnění Lagrangeovy interpolace: v obou případech se k interpolované informaci vhodně váženě přičítá. Váhové funkce se neprojeví ve všech opěrných místech a v 0-té a 1-ní derivaci mimo příslušné opěrné místo, kde nabývají hodnotu 1, tedy

\begin{aligned}A_{i}^{m}(x_{j}) & = & δ_{ij}, & B_{i}^{m}(x_{j}) & = & 0, \\ A_{i}^{m}′(x_{j}) & = & 0, & B_{i}^{m}(x_{j}) & = & δ_{ij}, & 0 ≤ i, j ≤ m. \end{aligned}

Při vhodné volbě tečných vektorů lze křivku zlepšit. Křivka však reaguje opravdu citlivě.

1.2 Interpolace pomocí spline-křivek

Abychom zamezili zvlnění interpolačních polynomů, přejdeme k pouze po částech polynomiální interpolaci, přičemž jsou požadovány hladké přechody mezi různými polynomy, tzn. použijeme spliny. Dále se snažíme zamezit obtížím při numerickém vyhodnocení v případě mnoha opěrných bodů.

Definice. Otevřená interpolující splinová křivka: Buďte dáno n + 1 bodů p_{i} ∈ R^{d} s hodnotami parametrů t_{i} ∈ R, t_{0} ≤ t_{1} ≤ … ≤ t_{n}, i = 0, …, n, t_{0} ≤ t_{1} ≤ … ≤ t_{n}. Křivka p(t), t ∈ [t_{0}, t_{n}], p : [t_{0}, t_{n}] → R^{d}, se nazývá otevřená interpolující splinová křivka stupně m ∈ N, jsou-li splněny následující podmínky:

1. p(t) je polynom stupně m v každém dílčím intervalu [t_{i}, t_{i+1} ], 0 ≤ i < n.

2. p(t) ∈ C^{(m−1)}[t_{0}, t_{k}].

3. p(t_{i}) = p_{i}, i = 0, …, n.

Uzavřená interpolující splinová křivka: Buďte dáno n + 1 bodů p_{i} ∈ R^{d} s hodnotami parametrů t_{i} ∈ R, t_{0} ≤ t_{1} ≤ … ≤ t_{n}, i = 0, …, n, t_{0} ≤ t_{1} ≤ … ≤ t_{n}. Křivka p(t), t ∈ [t_{0}, t_{n}], p : [t_{0}, t_{n}] → R^{d}, se nazývá uzavřená interpolující splinová křivka stupně m ∈ N, jsou-li splněny následující podmínky:

1. p(t) je polynom stupně m v každém dílčím intervalu [t_{i}, t_{i+1} ], 0 ≤ i < n.

2. p(t) ∈ C^{(m−1)}[t_{0}, t_{k}].

3. p(t_{i}) = p_{i}, i = 0, …, n.

4. p′(t_{0}) = p′(t_{n}), …, p^{(m−1)}(t_{0}) = p^{(m−1)}(t_{n}).

Otevřená interpolující křivka není jednoznačná. Pro d · (nm + n) koeficientů polynomiálních segmentů spline křivky existuje pouze d·((n−1)m+n+1) lineárních rovnic, které obdržíme z definic 2 a 3, takže nám zbude ještě d · (m − 1) stupňů volnosti.

Při interpolujících kubických spline-křivkách se používají polynomy stupně 3, jež interpolují n + 1 opěrných bodů (t_{i}, p_{i}). Podle poznámky z posledního odstavce odstavce zůstanou ještě dva stupně volnosti. Ty jsou obvykle svázány zadáním hodnot p_{0}′, p_{n}′ pro derivaci v hranicích intervalu.

Věta 1.5 Koeficienty kubických spline-křivek. Buď

p_{i} := a_{i} + b_{i}(t − t_{i}) + c_{i}(t − t_{i})^{2} + d_{i}(t − t_{i})^{3}, t ∈ [t_{i}, t_{i+1} ],

i-tý polynomiální křivkový segment interpolující kubické spline-křivky p(t), Δ_{i} := t_{i} − t_{i−1}, i = 1, …, n. Pak lze koeficienty a_{i}, b_{i}, c_{i}, d_{i} vypočítat následovně:

1. a_{i} := p_{i}, i = 0, 1, …, n.

2. Koeficienty c_{i} získáme jako řešení lineárního systému rovnic

\underline{pro otevřené interpolující spline-křivky} :

A ( \begin{matrix}c & 0 \\ c & 1 \\ c & 2 \\ … \\ c & n−1 \\ c & n \end{matrix} ) = ( \begin{matrix}3\frac{(p_{1}−p_{2})}{Δ_{1}} − 3p_{0}′ \\ 3\frac{(p_{2}−p_{1})}{Δ_{2}} − 3\frac{p_{1}−p_{0}}{Δ_{1}} \\ 3\frac{(p_{3}−p_{2})}{Δ_{3}} − 3\frac{(p_{2}−p_{2})}{Δ_{2}} \\ … \\ 3\frac{(p_{n}−p_{n−1})}{Δ_{n}} − 3\frac{(p_{n−1}−p_{n−2})}{Δ_{n−1}} \\ 3\frac{(p′ − 3p_{n} − p_{n−1})}{Δ_{n}} \end{matrix} ) ,

90  Interpolace a aproximace

A = ( \begin{matrix}2Δ_{1} & Δ_{1} & 0 & & & 0 \\ Δ_{1} & 2(Δ_{1} + Δ_{2}) & Δ_{2} \\ 0 & Δ_{2} & 2(Δ_{2} + Δ_{3}) & Δ_{3} \\ & & & Δ_{n−1} & 2(Δ_{n−1} + Δ_{n}) & Δ_{n} \\ 0 & & & 0 & Δ_{n} & 2Δ_{n} \end{matrix} ) ,

\underline{pro uzavřené interpolující spline-křivky} :

A ( \begin{matrix}c & 0 \\ c & 1 \\ c & 2 \\ … \\ c & n−2 \\ c & n−1 \end{matrix} ) = ( \begin{matrix}3\frac{(p_{1}−p_{2})}{Δ_{1}} − 3\frac{(p_{n}−p_{n−1})}{Δ_{n}} \\ 3\frac{(p_{2}−p_{1})}{Δ_{2}} − 3\frac{p_{1}−p_{0}}{Δ_{1}} \\ 3\frac{(p_{3}−p_{2})}{Δ_{3}} − 3\frac{(p_{2}−p_{2})}{Δ_{2}} \\ … \\ 3\frac{(p_{n−1}−p_{n−2})}{Δ_{n−1}} − 3\frac{(p_{n−2}−p_{n−3})}{Δ_{n−2}} \\ 3\frac{(p_{n}−p_{n−1})}{Δ_{n}} − 3\frac{(p_{n−1}−p_{n−2})}{Δ_{n−1}} \end{matrix} ) ,

A = ( \begin{matrix}2(Δ_{1} + Δ_{n}) & Δ_{1} & 0 & & & Δ_{n} \\ Δ_{1} & 2(Δ_{1} + Δ_{2}) & Δ_{2} \\ 0 & Δ_{2} & 2(Δ_{2} + Δ_{3}) & Δ_{3} \\ 0 & ⋮ & ⋮ & ⋮ \\ 0 & & & Δ_{n−2} & 2(Δ_{n−2} + Δ_{n−1}) & Δ_{n−1} \\ Δ_{n} & & & 0 & Δ_{n−1} & 2(Δ_{n−1} + Δ_{n}) \end{matrix} ) .

3. b_{i} := \frac{p_{i+1} −p_{i}}{Δ_{i+1}} − \frac{Δ_{i+1} 3}{(} c_{i+1} + 2c_{i}), i = 0, …, n − 1.

4. d_{i} := \frac{c_{i+1} −c_{i}}{3Δ_{i+1}}, i = 0, …, n − 1. Důkaz. Z požadavku interpolace body (t_{i}, p_{i}) a dvojité spojité diferencovatelnosti přechodů v hraničních bodech t_{i} obdržíme

p_{i}(t_{i}) = p_{i}
p_{i}(t_{i}) = p_{i−1}(t_{i})
p_{i}^{,}(t_{i}) = p_{i−1}^{,}(t_{i})
p_{i}^{,,}(t_{i}) = p_{i−1}^{,,}(t_{i})

Zejména tedy obdržíme

a_{i} = p_{i}(t_{i}) = p_{i}.

Koeficienty a_{i} lze tedy bezprostředně spočítat, koeficienty b_{i} a d_{i} lze určit jakožto funkci koeficientů c_{i}. Koeficienty c_{i} obdržíme řešením lineárního systému rovnic s tridiagonální maticí. Dosazením z výše uvedených rovností obdržíme

p_{i} = p_{i−1} + b_{i−1} · Δ_{i} + c_{i−1} · Δ_{i}^{2} + d_{i−1} · Δ_{i}^{3}.

Zderivujeme-li p_{i}, obdržíme

b_{i} = b_{i−1} + 2c_{i−1} · Δ_{i} + 3d_{i−1} · Δ_{i}^{2}.

Zderivujeme-li p_{i} dvakrát, obdržíme

2c_{i} = 2c_{i−1} + 6d_{i−1} · Δ_{i},
d_{i−1} = \frac{c_{i}−c_{i−1}}{3Δ_{i}},

tj. koeficienty d_{i} závisí na koeficientech c_{i}.

Máme tedy

p_{i} = p_{i−1} + b_{i−1} · Δ_{i} + c_{i−1} · Δ_{i}^{2} + \frac{c_{i}−c_{i−1}}{3Δ_{i}} · Δ_{i}^{3}.

Výše uvedené lze psát jako

b_{i} = \frac{p_{i+1} −p_{i}}{Δ_{i+1}} − \frac{Δ_{i+1}}{3} (c_{i+1} + 2c_{i} ),

a tedy koeficienty b_{i} závisí na koeficientech c_{i}.

Podobně obdržíme

b_{i} − b_{i−1} = Δ_{i} · (c_{i−1} + c_{i} ).

Dosadíme-li pak do této rovnice za b_{i} a b_{i−1}, obdržíme

Δ_{i} c_{i−1} + 2(Δ_{i} + Δ_{i+1} )c_{i} + Δ_{i+1} c_{i+1}  = 3\frac{p_{i+1} −p_{i}}{Δ_{i+1}} − 3\frac{p_{i}−p-1_{i}}{Δ_{i}}.

V posledním případě se jedná o systém d · (n + 1) lineárních rovnic o d · (n + 1) neznámých c_{0}, …, c_{n}.

Obě chybějící rovnice obdžíme z okrajových podmínek pro hraniční body. V případě otevřených spline-křivek plyne z

\begin{aligned}p_{0}^{,}(t_{0}) & = & p_{0}^{,}, \\ p_{n−1}^{,}(t_{n}) & = & p_{n}^{,} \end{aligned}

první výše uvedený systém rovnic.

V případě uzavřených spline-křivek plyne z

\begin{aligned}p_{0}(t_{0}) & = & p_{n}(t_{n}), \\ p_{0}^{,}(t_{0}) & = & p_{n}^{,}(t_{n}), \\ p_{0}^{,,}(t_{0}) & = & p_{n}^{,,}(t_{n}) \end{aligned}

druhý výše uvedený systém rovnic.

V obou případech je matice systému rovnic pro c_{i} tridiagonální a diagonálně dominantní. Proto lze tento systém rovnic vyřešit pomocí Gaussova algoritmu bez hledání pivota se složitostí O(n) na spotřebu času a paměti.

Zároveň lze dokázat, že kubické spline-křivky mají požadovaný charakter zvlněnosti:

Věta 1.6 Interpolační chování spline-křivek Ze všech křivek k ∈ C^{2}[t_{0}, t_{n}], jež splňují interpolační podmínku

k(t_{j}) = p_{j}, j = 0, 1, …, n, k′(t_{0}) = p′_{0}, k′(t_{n}) = p′_{n},

kubická spline-křivka minimalizuje hodnotu integrálu

∫_{t_{0}}^{t_{n}}k′′(t) ∗ k′′(t)dt.

Důkaz. Plyne bezprostředně zobecněním odpovídajícího tvrzení pro jednodimenzionální případ z numerické matematiky.

Tato minimalizační vlastnost se nazvývá ţMinimum Norm Property�. Při parametrizaci podle délky oblouku platí pro křivost κ křivky

κ = \sqrt{k′′ ∗ k′′}.

Hodnota integrálu v předchozí větě odpovídá v tomto případě střední kvadratické křivosti, která se minimalizuje kubickou spline-křivkou.

Podobně jako hermiteovská interpolace pomocí polynomů, lze splinovou interpolaci provést pro předem zadané hodnoty derivací:

Definice. Buďte dáno 2(n + 1) bodů p_{i}, p′_{i} ∈ R^{d} s hodnotami parametrů t_{i} ∈ R, t_{0} ≤ t_{1} ≤ … ≤ t_{n}, i = 0, …, n. Interpolující hermiteovská splinová křivka: interpoluje body (t_{i}, p_{i}, p′_{i}), je otevřená nebo uzavřená spline-křivka 5. stupně, pro niž navíc platí otevřená hermiteovská splinová křivka:

p′′(t_{0}) = 0, p′′(t_{n}) = 0,

uzavřená hermiteovská splinová křivka:

p(t_{0}) = p(t_{n}), p′(t_{0}) = p′(t_{n}),
p′′(t_{0}) = p′′(t_{n}), p′′′(t_{0}) = p′′′(t_{n}).

Pro výpočet hermiteovských splinových křivek je potřeba určit 6dn koeficientů. Tím, že jsou zadány funkční hodnoty a hodnoty prvních derivacích v bodech dotyku, obdržíme 2d(n+1) lineárních rovnic v koeficientech. Z požadavku spojitého přechodu první až čtvrté derivace ve vnitřních bodech dotyku t_{1}, …, t_{n−1} obdržíme 4d(n − 1) rovnic, takže nám zbude ještě 2d stupňů volnosti, které je nutno omezit dodatečnými podmínkami.

Věta 1.7 Výpočet hermiteovských spline-křivek. Buď

p_{i} := a_{i} + b_{i}(t − t_{i}) + c_{i}(t − t_{i})^{2} + d_{i}(t − t_{i})^{3} + e_{i}(t − t_{i})^{4} + f_{i}(t − t_{i})^{5}, t ∈ [t_{i}, t_{i+1} ],

i-tý polynomiální křivkový segment interpolující hermiteovské spline-křivky p(t), Δ_{i} := t_{i} − t_{i−1}, i = 1, …, n, Δ_{n+1} = Δ_{1}. Pak platí: \underline{pro otevřené hermiteovské spline-křivky} :

1. a_{i} := p_{i}, i = 0, 1, …, n.

2. b_{i} := p′_{i}, i = 0, 1, …, n.

3. Koeficienty c_{i} získáme jako řešení lineárního systému rovnic

c_{0} = c_{n} = 0,
−\frac{c_{i−1}}{Δ_{i}} + 3(Δ_{i}^{−1} + Δ_{i+1}^{−1} )c_{i} − \frac{c_{i+1}}{Δ_{i+1}} =
10 (\frac{a_{i+1} −a_{i}}{Δ_{i+1}^{3}} − \frac{a_{i}−a_{i−1}}{Δ_{i}^{3}} )+ 4 (\frac{b_{i−1}}{Δ_{i}^{2}} − \frac{3}{2}(Δ_{i+1}^{−2} + Δ_{i}^{−2})b_{i} − \frac{b_{i+1}}{Δ_{i+1}^{2}} )

s Δ_{i} = t_{i} − t_{i−1}, i = 1, …, n − 1.

4. d_{i} := 10\frac{a_{i+1} −a_{i}}{Δ_{i+1}^{3}} − 2\frac{2b_{i+1} +3b_{i}}{Δ_{i+1}^{2}} + \frac{c_{i+1} −3c_{i}}{Δ_{i+1}^{1}}, i = 0, …, n − 1.

94  Interpolace a aproximace

5. e_{i} := \frac{b_{i+1} −b_{i}}{2Δ_{i+1}^{3}} − \frac{c_{i}}{Δ_{i+1}^{2}} + \frac{d_{i+1} +5d_{i}}{4Δ_{i+1}^{1}} , i = 0, …, n − 1.

6. f_{i} := \frac{c_{i+1} −c_{i}}{10Δ_{i+1}^{3}} − \frac{3d_{i}}{10Δ_{i+1}^{2}} − \frac{3e_{i}}{5Δ_{i+1}^{1}} , i = 0, …, n − 1.

\underline{pro uzavřené hermiteovské spline-křivky} : 1. a_{i} := p_{i}, i = 0, 1, …, n, a_{n+1} := a_{1}.

2. b_{i} := p′_{i}, i = 0, 1, …, n, b_{n+1} := b_{1}.

3. Koeficienty c_{i} získáme jako řešení lineárního systému rovnic

c_{n} := c_{0}, c_{n+1} := c_{1},

−\frac{c_{2}}{Δ_{2}} + 3(Δ_{1}^{−1} + Δ_{2}^{−1})c_{1} − \frac{c_{n}}{Δ_{1}} =
10 (\frac{a_{2}−a_{1}}{Δ_{2}^{3}} − \frac{a_{1}−a_{0}}{Δ_{1}^{3}} )+ 4 (\frac{b_{0}}{Δ_{1}^{3}} − \frac{3}{2}(Δ_{2}^{−2} + Δ_{1}^{−2})b_{1} − \frac{b_{2}}{Δ_{2}^{2}} ) ,
−\frac{c_{1}}{Δ_{1}} + 3(Δ_{n}^{−1} + Δ_{1}^{−1})c_{n} − \frac{c_{n−1}}{Δ_{n}} =
10 (\frac{a_{1}−a_{n}}{Δ_{1}^{3}} − \frac{a_{n}−a_{n−1}}{Δ_{n}^{3}} )+ 4 (\frac{b_{n−1}}{Δ_{n}^{3}} − \frac{3}{2}(Δ_{1}^{−2} + Δ_{n}^{−2})b_{n} − \frac{b_{1}}{Δ_{1}^{2}} ) ,
−\frac{c_{i−1}}{Δ_{i}} + 3(Δ_{i}^{−1} + Δ_{i+1}^{−1} )c_{i} − \frac{c_{i+1}}{Δ_{i+1}} =
10 (\frac{a_{i+1} −a_{i}}{Δ_{i+1}^{3}} − \frac{a_{i}−a_{i−1}}{Δ_{i}^{3}} )+ 4 (\frac{b_{i−1}}{Δ_{i}^{3}} − \frac{3}{2}(Δ_{i+1}^{−2} + Δ_{i}^{−2})b_{i} − \frac{b_{i+1}}{Δ_{i+1}^{2}} ) ,

i = 1, …, n − 2.

4. d_{i} := 10\frac{a_{i+1} −a_{i}}{Δ_{i+1}^{3}} − 2\frac{2b_{i+1} +3b_{i}}{Δ_{i+1}^{2}} + \frac{c_{i+1} −3c_{i}}{Δ_{i+1}^{1}}, i = 0, …, n − 1, d_{n} := d_{n−1} − 2\frac{b_{n}−b_{n−1}}{Δ_{n}^{2}} + 2\frac{c_{n}+c_{n−1}}{Δ_{n}^{1}} .

5. e_{i} := \frac{b_{i+1} −b_{i}}{2Δ_{i+1}^{3}} − \frac{c_{i}}{Δ_{i+1}^{2}} + \frac{d_{i+1} +5d_{i}}{4Δ_{i+1}^{1}} , i = 0, …, n − 1.

6. f_{i} := \frac{c_{i+1} −c_{i}}{10Δ_{i+1}^{3}} − \frac{3d_{i}}{10Δ_{i+1}^{2}} − \frac{3e_{i}}{5Δ_{i+1}^{1}} , i = 0, …, n − 1.

Důkaz. Engeln-Müllges, Reutter (1990).

1.3 Geometrické spline-křivky

U doposud uvažovaných spline-křivek byla požadována pro hladké přechody mezi částí křivek shoda derivací až k jistému řádu n, tedy C^{n}-spojitost celkové křivky. Hodnoty derivace jsou závislé na konkrétní parametrizaci křivky a tedy se nejedná o geometrické veličiny. Pro charakterizaci hladkosti nabídneme v následujícím dvě další možnosti – vizuální spojitost n-tého stupně (řádu) a spojitost geometrických invariantů jako jsou zakřivení a torze. Ty jsou pak nezávislé na parametrizaci - jedná se tedy o geometrické veličiny.

Definice. Řekneme, že křivka má vizuální spojitost n-tého stupně (řádu), jestliže existuje C^{n}-spojitá parametrizace křivky. Dále řekneme, že křivka má spojitou křivost (spojitou torzi), jestliže κ (τ) je spojitá funkce.

Platí pak

Věta 1.8 Vizuální spojitost, křivost a torze. Pro křivku v R^{3} je vizuální spojitost stupně n ekvivalentní s tím, že κ ∈ C^{n−2} a τ ∈ C^{n−3}.

Důkaz. Pottmann (1988).

Geometrické spline-křivky vznikají složením z polynomiálních dílčích křivek tak, že výsledná křivka je spojitá odpovídajícně výše definovaným pojmům. Pro určení geometrických spline-křivek musíme odvodit stejně jako u obyčejných spline-křivek podmínky v bodech spojení.

Uvařujeme-li křivku k ve dvou parametrizacích k(t) a k( t) = k(ϕ(t)) v okolí bodu

t_{0} tak, že k( t_{0}) = k(ϕ(t_{0})), pak platí

\begin{aligned}\overline{k}(t_{0}) & = & k(ϕ(t_{0})), \\ \overline{k}′(t_{0}) & = & ϕ′(t_{0})k′(ϕ(t_{0})), \\ \overline{k}′′(t_{0}) & = & ϕ′′(t_{0})k′(ϕ(t_{0})) + ϕ′^{2}(t_{0})k′′(ϕ(t_{0})). \end{aligned}

Požadavek vizuální spojitosti druhého řádu v bodě spojení t_{i} mezi dvěma dílčími polynomy lze psát jako

\begin{aligned}k(t_{i}−) & = & k(t_{i}+), \\ k′(t_{i}−) & = & β_{1}k′(t_{i}+), \\ k′′(t_{i}−) & = & β_{2}k′(t_{i}+) + β_{1}^{2}k′′(t_{i}+). \end{aligned}

Tyto vztahy použijeme v následujícím příkladu interpolující geometrické splinekřivky – tzv. ν-splinu. Pro ν-spline-křivky požadujeme shodu prvních derivací v bodech dotyku mezi dílčími polynomy (β_{1} = 1) a vytváří odpovídající geometrický požadavek druhého řádu.

Definice. ν-spline-křivka Buď dáno n + 1 bodů p_{i} ∈ R^{d} s hodnotami parametrů t_{i} ∈ R, t_{0} ≤ t_{1} ≤ … ≤ t_{n} spolu hodnotami napětí ν_{i}, i = 0, …, n. Křivka p(t), t ∈ [t_{0}, t_{n}], p : [t_{0}, t_{n}] → R^{d} se nazývá ν-spline-křivka, jestliže platí:

1. p(t) je kubický polynom v každém dílčím intervalu [t_{i}, t_{i+1} ], 0 ≤ i < n.

2. p_{i}(t_{i+1} ) = p_{i+1} (t_{i+1} ), i = 0, …, n − 1.

3. p′_{i}(t_{i+1} ) = p′_{i+1} (t_{i+1} ), i = 0, …, n − 1, tj. p ∈ C^{1}[t_{0}, t_{n}].

4. p′′_{i}(t_{i+1} −) = p′′_{i+1} (t_{i+1} +) − ν_{i+1} p′_{i}(t_{i+1} ), i = 0, …, n − 1.

Dále je potřeba, aby byla splněna jedna z následujících okrajových podmínek:

• Okrajová podmínka pro otevřené ν-spline-křivky:

p′(t_{0}) = p_{0}′, p′(t_{n}) = p_{n}′,  (5.1)

• Okrajová podmínka pro přirozené ν-spline-křivky:

ν_{0}p′(t_{0}) − p′′(t_{n}+) = 0, ν_{n}p′(t_{n}) + p′(t_{n}−) = 0,  (5.2)

• Okrajová podmínka pro uzavřené ν-spline-křivky:

p(t_{0}) = p(t_{n}), p′(t_{0}) = p′(t_{n}), p′′(t_{0}+) − p′′(t_{n}−) = (ν_{0} + ν_{n})p′(t_{0}) = 0.  (5.3)

Poznamenejme, že ν_{i} jsou dodatečné stupně volnosti pro ovlivnění křivky, tzv. parametry pnutí. Jsou-li všechny parametry pnutí rovny 0, obdržíme obvyklé kubické interpolující spline-křivky. Necháme-li pnutí ν_{i} a ν_{i+1} sousedních kontrolních bodů růst do nekonečna, konverguje pak spline k přímkovému segmentu, který spojuje spolu sousední kontrolní body. Necháme-li pnutí všech kontrolních bodů růst do nekonečna, konverguje pak spline k polygoniálnímu tahu, který spojuje kontrolní body.

Věta 1.9 Spojitost křivosti ν-spline-křivek ν-spline-křivky mají spojitou křivost.

Důkaz. Pro d = 3 plyne tvrzení z věty 1.8. Pro libovolné d plyne tvrzení, kde

a^{−} := p_{i}′(t_{i+1} −), b^{−} := p_{i}′′(t_{i+1} −),
a^{+} := p_{i}′(t_{i+1} +), b^{+} := p_{i}′′(t_{i+1} +), (5.4)

z výpočtu

κ_{t_{i+1} −} = ^{\sqrt{(a^{−}∗a^{−})(b^{−}∗k^{−})−(a^{−}∗b^{−})^{2}} ; (a^{−}∗a^{−})^{\frac{3}{2}}}

= ^{\sqrt{(a^{+} ∗a^{+} )((b^{+} −ν·a^{+} )∗(b^{+} −ν·a^{+} ))−(a^{+} ∗b^{+} )^{2}} ; (a^{−}∗a^{−})^{\frac{3}{2}}}

= ^{\sqrt{((a^{+} ∗a^{+} )(b^{+} ∗b^{+} )−(a^{+} ∗b^{+} )^{2})} ; (a^{−}∗a^{−})^{\frac{3}{2}}}
= κ_{t_{i+1} +} .

(5.5)

Pro výpočet koeficientů ν-spline-křivek je účelné reprezentovat dílčí polynomy p_{j}(t) nad hermiteovskou bází. Hermiteovská báze je tvořena Hermiteovými polynomy.

Definice. Hermiteovy polynomy jsou tvaru:

\begin{aligned}H_{0}(x) & := & 2x^{3} − 3x^{2} + 1, & H_{1}(x) & := & −2x^{3} + 3x^{2}, \\ \overline{H_{0}}(x) & := & x^{3} − 2x^{2} + 1, & \overline{H_{1}}(x) & := & x^{3} − x^{2}. \end{aligned}  (5.6)

Tyto polynomy mají tu vhodnou vlastnost, že ony zrovna tak jejich derivace nabývají v krajních bodech intervalu [0, 1] hodnot 0, 1:

\begin{aligned}H_{0}(0) & = & 1, & H_{0}(1) & := & 0, & H_{0}′(0) & = & 0, & H_{0}(1) & := & 0, \\ H_{1}(0) & = & 0, & H_{1}(1) & := & 1, & H_{1}′(0) & = & 0, & H_{1}(1) & := & 0, \\ \overline{H_{0}}(0) & = & 0, & \overline{H_{0}}(1) & := & 0, & \overline{H_{0}}′(0) & = & 1, & \overline{H_{0}}′(1) & := & 0, \\ \overline{H_{1}}(0) & = & 0, & \overline{H_{1}}(1) & := & 0, & \overline{H_{1}}′(0) & = & 0, & \overline{H_{1}}′(1) & := & 1. \end{aligned}  (5.7)

Hermiteovy polynomy obdržíme hermiteovskou interpolací výše uvedených bodů.

Věta 1.10 Výpočet ν-spline-křivek. Buď dány body dotyku (t_{i}, p_{i}), p_{i} ∈ R^{d} a body pnutí ν_{i}, i = 0, …, n. Dále buď

\begin{aligned}Δ_{i} & := & t_{i} − t_{i−1}, \\ a_{i} & := & Δ_{i+1}^{−1} , \\ d_{i} & := & 3 (p_{i−1}(−a_{i−1}^{2}) + p_{i}(a_{i−1}^{2} − a_{i}^{2}) + p_{i+1} (a_{i}^{2})) . \end{aligned}  (5.8)

Pak lze j-tý dílčí polynom p_{j}(t) interpolující ν−spline-křivky reprezentovat následovně:

p_{j}(t) = H_{0}(s) · p_{j} + H_{1}(s) · p_{j+1} + h_{j}\overline{H_{0}(s)} · p′_{j} + h_{j}\overline{H_{1}(s)} · p′_{j+1} ,  (5.9)

kde

s := \frac{t − t_{j}}{Δ_{j+1}},

přičemž můžeme neznámé p′_{0}, p′_{1}, …, p′_{n} získat jakožto řešení systému lineárních rovnic:

1. Okrajové podmínky 5.1:

A ( \begin{matrix}p & ′1 \\ p & ′2 \\ … \\ p & {′ \atop n−2} \\ p & n−1 \end{matrix} ) = ( \begin{matrix}d_{1} − a_{0}p′_{1} \\ d & 2 \\ … \\ d & n−2 \\ d_{n−1} − a_{0}p′_{n} \end{matrix} ) ,

A = ( \begin{matrix}a_{0} + a_{1} + \frac{ν_{0}}{2} & a_{1} \\ a_{1} & a_{1} + a_{2} + \frac{ν_{1}}{2} & a_{2} \\ & & & a_{n−3} & a_{n−3} + a_{n−2} + \frac{ν_{n−2}}{2} & a_{n−2} \\ & & & & a_{n−2} & a_{n−2} + a_{n−1} + \frac{ν_{n−1}}{2} \end{matrix} ) ,

\underline{pro uzavřené interpolující spline-křivky} :

A ( \begin{matrix}c & 0 \\ c & 1 \\ c & 2 \\ … \\ c & n−2 \\ c & n−1 \end{matrix} ) = ( \begin{matrix}3\frac{(p_{1}−p_{2})}{Δ_{1}} − 3\frac{(p_{n}−p_{n−1})}{Δ_{n}} \\ 3\frac{(p_{2}−p_{1})}{Δ_{2}} − 3\frac{p_{1}−p_{0}}{Δ_{1}} \\ 3\frac{(p_{3}−p_{2})}{Δ_{3}} − 3\frac{(p_{2}−p_{2})}{Δ_{2}} \\ … \\ 3\frac{(p_{n−1}−p_{n−2})}{Δ_{n−1}} − 3\frac{(p_{n−2}−p_{n−3})}{Δ_{n−2}} \\ 3\frac{(p_{n}−p_{n−1})}{Δ_{n}} − 3\frac{(p_{n−1}−p_{n−2})}{Δ_{n−1}} \end{matrix} ) ,

A = ( \begin{matrix}2(Δ_{1} + Δ_{n}) & Δ_{1} & 0 & & & Δ_{n} \\ Δ_{1} & 2(Δ_{1} + Δ_{2}) & Δ_{2} \\ 0 & Δ_{2} & 2(Δ_{2} + Δ_{3}) & Δ_{3} \\ 0 & ⋮ & ⋮ & ⋮ \\ 0 & & & Δ_{n−2} & 2(Δ_{n−2} + Δ_{n−1}) & Δ_{n−1} \\ Δ_{n} & & & 0 & Δ_{n−1} & 2(Δ_{n−1} + Δ_{n}) \end{matrix} ) .

2. b_{i} := \frac{p_{i+1} −p_{i}}{Δ_{i+1}} − \frac{Δ_{i+1} 3}{(} c_{i+1} + 2c_{i}), i = 0, …, n − 1.

3. d_{i} := \frac{c_{i+1} −c_{i}}{3Δ_{i+1}}, i = 0, …, n − 1. Důkaz. Zřejmé.