Geometrické modelování RNDr. Jan Paseka, CSc. 16. prosince 2009 2 Úvod Tento učební text je založen na monografii "Geometrické modelování" autorů S. Abramowského a H. Miillera. Zároveň využívá texty českých autorů jako jsou např. "Počítačová grafika" autorů Jiřího Žáry a kol., "Algoritmy počítačové grafiky" autorů Jiřího Žáry a Jiřího Sochora a standardního matematického textu "Plochy ve výpočetní technice" Ladislava Drse. 3 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.................. 13 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........................... 41 4 Plochy................................. 50 4.1 Ctyřúhelníkové Bézierovy segmenty............. 50 4.2 Trojúhelníkové Bézierovy segmenty............. 56 4.3 Racionální plošné Bézierovy segmenty............ 60 5 Vyšší dimenze............................. 61 3 Kritéria kvality 63 1 Implicitní vyjádření.......................... 63 2 Metody analýzy prostřednictvím diferenciální geometrie...... 65 2.1 Křivky............................. 65 2.2 Plochy............................. 76 4 Metoda B-splinů 85 1 Splínové a B-splinové funkce..................... 85 2 B-spline křivky............................ 91 3 B-spline plochy............................ 95 4 B-spline metoda a Bézierova metoda................ 96 5 Racionální B-spline metoda (NURBS)................ 99 6 Přehled k B-spline metodě...................... 101 5 6 OBSAH 5 Interpolace a aproximace 103 1 Interpolace s křivkami ........................103 1.1 Interpolace pomocí polynomů................104 1.2 Interpolace pomocí spline-křivek...............108 1.3 Geometrické spline-křivky..................114 Kapitola 1 Geometrické modelování a základní transformace Geometrické modelování se zabývá počítačově podporovaným návrhem a 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áni pomoci 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á především o 7 8KAPIT0LA 1. GEOMETRICKÉ MODELOVÁNÍ A ZÁKLADNÍ TRANSFORMACE 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 parametrické 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 (raste-rizací). 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 znazorňovacím přístrojem jsou peřový 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 224 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ů 4. POSUNUTÍ, OTÁČENÍ A ZMĚNA MĚŘÍTKA V ROVINĚ 9 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ěnu 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í Tx a Ty k původním souřadnicím: X ' 1 v' = Ty + y. Dvojice délek (Tx,Ty) definuje vektor posunutí. Transformace objektu po kruhové dráze se nazývá otáčení (rotace). Je určena úhlem otáčení 9 a středem otáčení S = (x s, y s)- Tuto transformaci vyjadřuje soustava rovnic x' = (x — xs)cos9 — (y — ys)sm9 + xs, y' = {x - xs)slii9 + (y - ys)cos9 + ys. Transformace, pomocí které lze změnit velikost objektu, se nazývá změna měřítka. Je vyjádřena soustavou rovnic v1 = ySy, kde (Sx, Sy) 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 [xh, yh, h], kde: lOKAPITOLA 1. GEOMETRICKÉ MODELOVÁNÍ A ZÁKLADNÍ TRANSFORMACE Vh = xh, = yh. 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 [xh 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' = PM, kde P' = [x' y' 1] a P = [xyl] jsou matice typu 1x3 představující souřadnice bodů. Čtvercová matice M. je matice transformace. Pro čtvercovou matici posunutí se vzdálenostmi posunu Tx a Ty zavedeme označení T(Tx,Ty): "10 0 T(T*,Ty) = 0 1 T T 0 1 Zavedeme také inverzní matici T l vyjadřující posunutí opačným směrem: T-\Tx,Ty) = 1 0 -T 0 1 -T 0 o 1 Pro otáčení podle počátku souřadnicové soustavy zavedeme transformační matici 71(9): cos U - sin/ 0 smť cos/ 0 0 0 1 K(0) = Inverzní matice 1Z~1{9) popisuje otáčení obráceným směrem: n-\e) -- COSI sin/ 0 — smi cosö 0 0 0 1 Podobně vytvoříme matici S(SX, Sy) pro změnu měřítka a matici S 1(SX, Sy) k ní inverzní: " Sx 0 0 <-> (SX, by) 0 o Sy 0 0 1 5. MATICOVÉ VYJÁDŘENÍ A HOMOGENNÍ SOUŘADNICE 11 ó (Jx7 Jy) — _j_ O O O O by O O 1 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(Txl,Tyi) a T(TX2,Ty2), spočítáme složenou matici jako r i o o o i o T T l 1 0 o 0 1 o T T l ±X2 ±V2 ^ 1 0 T Xl o 1 T T J-x2 J-y-í T ± 7 2/2 o o 1 Je vidět, že transformace posunutí jsou aditivní. Podobně ze součtových vzorců obdržíme n = cos U - sin/ 0 sin 9 0 COS0 0 0 1 cos r] sin r\ 0 - sin r] cos r] 0 0 0 1 cos(9 + rj) sin(6l + rj) 0 - sin(6l + rj) cos(9 + rj) 0 0 0 1 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í: S = SX1 0 0 0 Syi 0 0 0 1 s X2 d 3 0 Uy2 0 0 0 1 0 0 0 V2 0 " 0 1 12KAPIT0LA 1. GEOMETRICKÉ MODELOVANÍ A ZÁKLADNÍ TRANSFORMA CE 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 (xs,ys) 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-\Txs,Tys)K{6)T(Txs,Tys). Skládáním různých transformací docílíme různých změn polohy a tvaru objektů. Například měřítek Sx a Sy, 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 Sx = 1 a Sy - ■1: ^x 1 0 0 0-10 0 0 1 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: Zy — -10 0 0 1 o 0 0 1 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 -1 0 0 0 -1 0 0 0 1 7. LINEÁRNI PROSTOROVÉ TRANSFORMACE 13 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~l 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: •SHX 1 0 0 SHX 1 0 0 0 1 Inverzní matice zkosení má tvar: S7Í„ = 1 0 0 -SHX 1 0 0 0 1 Za parametr SHX 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: SHi, 1 SHy 0 0 0 1 0 0 1 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 x 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 [xw, yw, zw, w], kde w je libovolné nenulové reálné číslo. Tato čtveřice bude představovat homogenní souřadnice bodu. Transformace posunuti změní polohu objektu beze změny tvaru a orientace objektu. Pro čtvercovou matici posunutí se vzdálenostmi posunu Tx, Ty a Tz zavedeme UKAPITOLA 1. GEOMETRICKÉ MODELOVÁNÍ A ZÁKLADNÍ TRANSFORMACE označení T(Tx,Ty, Tz): 1 v,-* X) J- y j J- z ) 1 0 o J- x o 1 o 0 0 1 Tz 0 0 0 1 Zavedeme také inverzní matici T l vyjadřující posunutí opačným směrem: -* v,-* X) -*- y j J- z ) 1 0 o — -L T. 0 1 o 0 0 1 -Tz. 0 0 0 1 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řadných os. Nejprve sestavíme transformační matici pro otočení okolo osy z o úhel 9. Tato matice má tvar: Pro otáčení podle počátku souřadné soustavy zavedeme transformační matici 71(9): nz{9) = cos f - sin( 0 0 sm( cosi 0 0 0 o 1 o Podobně lze určit i matice pro otočení okolo osy x, resp. y: Tlx{9) = 1 0 0 COS0 0 — sin 6 0 0 0 sin ť cos( 0 0 0 o 1 ny{9) = cos 9 0 - sin 6 0 0 sin 9 1 0 0 cos 9 0 0 Transformač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 = [xiw,yiw,ziw,w] &B = [x2W,i/2W,Z2W,w]. Nejprve vytvoříme matici J\4, 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 1ZZ{9) o úhel 9, bod P se přemístí do bodu PM.7ZZ(9). Nakonec otočený bod transformujeme zpět (osa otáčení se z osy z přemístí do původní polohy) pomocí transformace M.~x na výsledný bod: PMnz(9)M-\ Matici Ai můžeme zkonstruovat např. takto: 7. LINEÁRNI PROSTOROVÉ TRANSFORMACE 15 1. Transformací posunutí T(T_X1, T_yi, T_Z1) přemístíme A = [x\W, y\W, Z\W, w] do počátku. 2. Určíme polární souřadnice druhého koncového bodu po posunutí tj. bodu B' = [(x2 — Xi)w, (y2 — yi)w, (z2 — Zi)w,w\. Polární souřadnice bodu B' isou B'polJr,ui,u2]. 3. Provedeme otáčení okolo souřadné osy z o úhel —üJ\. Odpovídající matici rotace označíme lZz(—Ui). Transformovaná osa otáčení leží nyní v rovině xz. 4. Provedeme otáčení okolo souřadné osy y o úhel — U2- Odpovídající matici rotace označíme TZy(—U2)- Transformovaná osa otáčení splyne s osou z. Matice A4 je tedy definována: M = TiT-^T-^T-zjKzi-uúKyi-uJz). Inverzní matice odpovídá složení zpětných transformací M-1 =Ky(uj2)Kz(uj1)T(TXl,Tyi,TZl). Výsledná transformace 7Zobecná je dána maticí zobecní = MKz(e)M~l. Podobně jako v dvojrozměrném případě vytvoříme matici S(SX, Sy, Sz) pro změnu měřítka a matici S~1(SX, Sy, Sz) k ní inverzní: ô(bx, by, bz) ó (bx, by, bz) — Transformace zkosení deformuje transformovaný objekt. Jako příklad uvedeme zkosení ve směru roviny xy. Transformační matice pro zkosení je: Sx 0 0 0 0 by 0 0 0 0 sz 0 0 0 0 1 - J_ &x 0 0 0 0 1 Sy 0 0 0 0 1 sz 0 0 0 0 1 sn xy 1 0 0 0 0 10 0 SHX S Hy 1 0 0 0 0 1 Analogické matice platí i pro zkosení v jiných rovinách. Uvedené transformace lze libovolně kombinovat a vytvářet transformace zrcadlení, souměrnosti apod. 16KAPIT0LA 1. GEOMETRICKÉ MODELOVÁNÍ A ZÁKLADNÍ TRANSFORMACE A -ríxx A -ríyx A -rízx p 1 x A -ríxy A A si-zy Py A -ríxz A si-yz Azz Pz T -L X T ±y T ± z 1 8 Promítací metody Ideální způsob vytvoření obrazu trojrozměrného objektu na dvojrozmě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 = [xh,yh,Zh,h], můžeme jeho transformaci na bod P' = [x'h, y'h, z'h, h] maticově vyjádřit jako: P' = P kde koeficienty Aíj jsou používány pro vyjádření otáčení, změnu měřítka a zkosení, koeficienty T» vyjadřují posunutí a koeficienty Pí 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) nabude 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řeáové 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žší. 8. PROMÍTACÍ METODY 17 Středové promítání Uvažme následující případ - projekci bodu P = (x, y, z) na bod P' = (x',y',z0) v průmětně tt. 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 / Zo i Zq x =x—,y =y—. z z Vzdálené objekty 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,l] 10 0 0 0 10 0 o o i i Zo 0 0 0 0 = [x,y,z,—]. Zo 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ě (0, 0, —zo) a projekční rovinu umístíme do počátku souřadného systému (tj. ztotožníme ji s rovinou xy), pak x x- zo X z + zo l + fo Maticový tvar této transformace je ■ y =y zo z + z0 y Přitom " 1 0 0 0 y1 z\ w'] = [x,y,z,l] 0 1 0 0 . o 0 0 0 0 0 1 Zo 1 = [x,y z, — . Zo i 0 0 0 " ' 1 0 0 0 " " 1 0 0 0 " 0 0 0 1 0 0 0 0 0 0 1 Zo 1 = 0 0 . 0 1 0 0 1 0 0 0 1 Zo 1 0 0 0 1 0 0 0 0 0 0 0 1 ) T > per = T V ■*■ per' 3 ar * tj- Perspektivní projekci podle matice Vpei můžeme chápat jako perspektivní transformaci objektů maticí Tpei a následnou paralelní projekci do zvolené průmětny vyjádřenou maticí Vpai. Transformace Tpei 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 18KAPIT0LA 1. GEOMETRICKÉ MODELOVÁNÍ A ZÁKLADNÍ TRANSFORMACE na ose z tj. [0,0,1,0] je transformován do bodu [0,0,1,^-] neboli [0,0,zo,l]-To znamená, že všechny rovnoběžky s osou z procházejí po středové (perspektivní) transformaci bodem [0,0, z0,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í dvouúběžníková nebo tříúběžníková perspektiva. Pokud protíná průmětna osy souřadného systému v líbeznících (—x0,0,0), (0,—y0,0), (0, 0, —z0), perspektivní transformaci popíšeme maticí T -Lperxyz Xo 0 0 0^ 0 0 0 1 1 o o 0 1 o Rovnoběžné promítání Nejjednodušší typ rovnoběžného promítání je promítání do některé z rovin x = Xo, y = yo, z = Zo ve směru příslušné osy kolmé na zvolenou promítací rovinu -průmětnu. Velmi často budou x0, j/o nebo z0 = 0, průmětnou bude některá z rovin xy, xz nebo yz. Projekci popíšeme jednoduchou transformací v homogenních souřadnicích: [x',y',z',w'} = [x,y,z,l] 10 0 0 0 10 0 0 0 0 0 0 0 zo 1 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í vzdá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: 8. PROMÍTACÍ METODY 19 sin 30° 0 0 sin 30° 0 0 1 0 0' 0 0 1 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 (xi,yi,Zi) promítacím paprskem do polohy (x2,y2) v průmětně. Kolmý průmět bodu je přitom označen jako (xk,yk)- Promítací paprsek svírá úhel a s úsečkou v průmětně, která je určena body (£2,2/2) a (xk,Dk)- Tato úsečka má délku L a svírá úhel 9 s vodorovným směrem v průmětně. Při uvedeném značení vyjádříme souřadnice bodu (^2,2/2) pomocí xk, yk, L a # jako X2 = Xk + Lcos9, ÍJ2 = yk + Lún9. Pro definici směru promítání stačí zvolit velikosti úhlů 9 a. 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\ a úhlu a z 1 tan a = — = —, Li Li\ kde délka Li je "normalizovaná" délka L pro případ z\ = 1. Po úpravě L = Z\L\ zapíšeme předchozí rovnice pro kosoúhlé promítání ve tvaru X2 = Xk + Z\(Li cos 9), 2/2 = yk + zi(Lism9). Odtud již snadno odvodíme tvar matice kosoúhlého promítání 1 0 0 0" M ° 10 0 koso~ Lx cos9 LjsinÖ 0 0 ' 0 0 0 1 _ Tato matice vyjadřuje současně i pravoúhlé promítání, pokud je L\ = 0, což nastává právě při velikosti úhlu a = 90°. Kosoúhlé promítání má tedy nenulové hodnoty Li. 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 a lze sice volit libovolně, v praxi se však nejčastěji používají dvě základní hodnoty: M, cos 30° cos 30° 0 0 20KAPITOLA 1. GEOMETRICKÉ MODELOVANÍ A ZÁKLADNÍ TRANSFORMA CE • Kavalírní promítání je charakterizováno hodnotou tana = 1, tedy a = 45°. Všechny úsečky kolmé k průmětně jsou promítány bez zkreslení. • Kabinetní promítání má tana = 2. To nastává pro úhel o přibližné velikosti a = 63,4°. Všechny úsečky kolmé k průmětně jsou kráceny na polovinu a výsledný průmět vypadá přirozeně. Kapitola 2 Bézierova metoda Bézierovu metodu lze přiřadit k diferenciálně geometrickému modelování. Jsou takto navrhová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 pomocí křivek, ploch nebo těles. Definice. Parametrická reprezentace křivky v R : souřadnice bodů p křivky jsou funkce jedné proměnné: p = k(í),k : P^Rd,tE PCR. P je přitom interval, např. [0,1] a nazývá se parametrický obor křivky. Kruh je např. v rovině xy popsán jako: x = cost, y = siní, t E [0, 2ir]. a šroubovice v prostoru jako: x = sin t, y = cos t, z = t, t E R. Podobně jako pro křivky, lze parametricky definovat plochu jako obraz dvou-dimenzionálního intervalu: 21 22 KAPITOLA 2. BÉZIEROVA METODA Definice. Parametrická reprezentace plochy v R3: souřadnice x, y, z bodů p plochy jsou funkce jedné proměnné: x(u,v) \ y(u,v) =i(u,v), (u,v) E P C R2, z(u,v) J kde x, y, z : P —► R, f : P —► R3, P je interval, např. [0,1] x [0,1] a nazývá se parametrický obor plochy. Příkladem plochy je u ~|~ v u tí ' v x= 3^T^' y = ^T^' z = ^T^' {u>v) e (0'1] x (0'1]- Křivky v R2 resp. plochy v R3 lze reprezentovat v mnoha případech explicitně: Definice. Explicitní reprezentace křivky v R2: y-ová souřadnice bodů p křivky je funkce proměnné x: p=(x,y), y = f(x)sf:P^R, PCR. Explicitní reprezentace plochy v R3: z-ová souřadnice bodů p plochy je funkce proměnných x,y: p=(x,y,z), z = f(x,y)sf:P^R, PCR2. 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 Rd má tvar: n p(í) := J]a,ť, t e [0,l],a,GRd. í=0 Tvar polynomiální křivky v této reprezentaci je určen koeficienty a». 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ů hi,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: 2. BÉZIEROVY KŘIVKOVÉ SEGMENTY 23 Algoritmus, (de Casteljau) Vstup: Bézierovy body b0, b>i,..., bn, parametrická hodnota ť E [0,1]. Výstup: Bod křivky b(í*). BEGIN FOR % := 0 TO n DO b° := bi5 FOR j :=lTOn DO FOR % := j TO n DO h{ := (1 - ť) ■ hjr{ +1* ■ hj~l-b(ť) := K 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 ť : (l — ť) a výsledné body spojeny polygoniálním tahem. S tímto o jeden bod kratším tahem se postupuje obdobně, až zbývá pouze jeden bod. To je hledaný bod křivky b(í*). Tímto Casteljauovým algoritmem definovaná křivka se dá popsat jako n b(t):=5>ť5T(t), í G [0,1], b,GRd, í=0 kde Bf(ť) jsou níže definované Bernsteinovy polynomy. Definice. Bernsteinovy polynomy stupně n jsou tvaru: Křivky v této reprezentaci se nazývají Bézierovy křivkové segmenty. Definice. Bézierův křivkový segment v Rd je tvaru: n b(t):=Y,*>iB?(t), t G [0,1], b,GRd. í=0 Souvislost mezi Casteljauovým algoritmem a Bézierovými křivkovými segmenty lze formálně zapsat následovně: j b{(t) := Y,hi-J+kBl(t), j = 0,...,n,i = j,...,n,te[0,l]. fc=0 24 KAPITOLA 2. BÉZIEROVA METODA Důkaz lze provést indukcí. Totiž bí+í(t)=(l - t)bj(í) + íb^-xíí) = (1 - *) ELo *>i-i+kB3k(t) + t ELo hl+l_3+kBi(t) = (1 - t)b^B30(t) + thl+lB]{t)+ ELi((l - t)bt_3+kBi(t) + íbť_i+fcBŽ-i(*)) = (1 - í)bw^(í) + ELi bť_i+fcBŽ+1(*) + rbmi^(í) =b,_J^+1(í) + ELi ht.J+kBÍ+\t) + b^Bj+ÍW -ELo hi-3+kBí (t) Věta 2.1 Vlastnosti Bernsteinových polynomů 1. Rozklad jednotky: Součet Bernsteinových polynomů stupně n je 1: n n / \ 5>ror) = £ (" W(i -*rť = (x+1 -xr = i. í=0 í=0 2. Pozitivita: Bernsteinovy polynomy jsou v intervalu [0,1] nezáporné: Bi(x) > 0, i = 0,...,n, a; G [0,1]. 3. Maximum: Bf(x) nabývá svého maxima v intervalu [0,1] v bodě ^, i = 0,... ,n. 4- Sumace: £*£?(*) n ■ x. í=0 5. Symetrie: B™{x) = Bnn_l(l-x), i = 0,...,n. 6. Rekurze: Pro i = 0,..., n platí B&ix) = («+1)1 ,H-l (i + l)\(n-i)\ n\(i + 1) xl+L(l-x)r n\(n — i) (i + l)\(n-i)\ (i + l)\(n - i - l)\(n - i) = xB:(x) + (1-x)B?+1(x). xl+L(l-x)r Je tedy Bernsteinuv polynom stupně n + 1 konvexní kombinaci dvou Bernsteinových polynomů stupně n. 2. BÉZIEROVY KŘIVKOVÉ SEGMENTY 25 7. Derivace: Pro i = 1,..., n — 1 platí -r-£f(z) = nÍU ~ M' (i ■ x'-Hl - x)n~l -in-i)- xHl - x)n~1-1) dx lK ' %\{n-%)\ v \ ) \ ) \ ) i = n-(Bl-11(x)-Br1(x)). 8. Integrace: B?(x) n + 1 Důkaz. (1.) Rozepsáním podle definice Bernsteinových polynomů stupně n a úpravou podle binomické věty dostáváme uvedený vztah: 5>T0r) = Y, ( " ) ^(1 - XT'* =(x + l-xT=l. í=0 í=0 ^ (2.) Podle definice Bernsteinových polynomů stupně n: B?{x)=[ni)x\l-x)n-t,i = 0,...,n, ale ( . ) > 0 A x% > 0 A (1 — x)n % > 0 pro x E [0,1].Dohromady tedy: B?{x)= ( n% )x\l-x)n-l>0,z = 0,...,n. (3.) Víme, že funkce f(x) může mít v bodě xo maximum, je-li f(xo)' = 0 nebo, jeli xq krajním bodem intervalu, na kterém extrém hledáme. Protože funkce B™{x) je spojitá na intervalu [0,1], zcela jistě zde má jak maximum tak minimum. Z její nenulovosti vyplývá, že funkční hodnota maxima bude rovněž nenulová. Rozlišme tedy případy: ► proi = 0 : B%(x) = (!J )x°(l - x)n = (1 - x)n x07 nabývá maximum na [0,1] v x = 0 = - (klesající funkce), ► pro i = n : B™(x) = ( )xn(l — x)T nabývá maximum na [0,1] v x = 1 = - (rostoucí funkce), 26 KAPITOLA 2. BÉZIEROVA METODA ► pro i = 1,... ,n — 1: v x = 0 a, x = 1 je B™(x) = 0, derivujeme na (0,1): (B?(x))> n xl(l — x)T ix% (1 — x)n % — xz(n — i)(l — x)n % l] xl(l — x)T n—t / % n—i x l—x, = 0 i_ __ n—t x l—x = 0 x(l—x) n " i i i Dohromady B™(x) nabývá svého maxima v intervalu [0,1] v bodě ±,i = 0,...,n. (4.) Podle definice Bernsteinových polynomů stupně n, úpravou a substitucí j i- 1: 5>T0r) = £ %-,-----------XTTľX í=0 !-^ (n — i)W. (1 - xf- = Y m í=0 = n ■ x ■ ^(n-i)\(i- 1)! i=i x\l-x)r {U 1)! -xl-\l-x)n-1 ^ (n - i)\(i - ľ)ľ j=0 X- "■ /^ _ 1 . . ale podle vlastnosti (1.) platí Yl ( A )xj(l — x)n~1~j = 1, dohromady: X>5T0r) = n • x í=0 i=o V J EÍ";1)^!-^) ra-1-J' = n • x. (5.) Rozepsáním podle definice Bernsteinových polynomů stupně n a úpravou obou stran zvlášť dostáváme: B?(x) n x\l - x)' n — % B:_t(x) = (nA(i-x)n-*(i-(i-x)T-^ = r)x\i-x) tedy, že: B?(x) = B^x). (6.) Podle definice Bernsteinových polynomů stupně n a úpravou n+ 1 i + l 2. BÉZIEROVY KŘIVKOVÉ SEGMENTY 27 n n i + lj' BZ$(x)=(ni+l)x«1(l-x)n-i = n i + l xl+\l-x)r X n i^{l-x)n-* + {l-x)-{i^l}x*í{l-x) = xB?{x) + {l-x)BL1{x)- n TI—í—1 (7.) Podle definice Bernsteinových polynomů stupně n, derivováním a úpravami: ► pro i = 0: (BS(x))' x°(l-x)r -n\ „ )x°(l - x)n l n(l — x)n l -nB™-\x) vztah platí (n.B^1 nedefinované položme rovno 0), ► pro i = n: (££(*))' = n xn(l — x)r n n — 1 n\ -, )x" n — l = nx TI—l ^(l - x)n-l-(n-l) = nBnnZ{(x) vztah platí (—n.B™ x nedefinované položme rovno 0), ► pro 1 < i < n — 1: WW = n x\l-x)r [i ■ xl-\l - x)n-1 -(n-i)- x\l - x)n-1-1] n\ ixl-L(l-x)r ni = n i\(n — i)\ n(n — 1)! (i-l)\(n- 1- (i + l))! n- 1 i í-i ] )xl-L(l-x)r i\(n — i)\ xl-\l-x) n — 1 n {n-í)x\l-x)n-1-1 1-i n(n-l)\ i\(n — 1 — i)\ x\l - xf-1-1 x\\ - x) TI—1 —í = n-[BU(x)-Br\x)}. 28 KAPITOLA 2. BÉZIEROVA METODA (8.) Nejprve dokážeme pro i = n: B™(x)dx xn(l - x) dx = / xndx x i ro+l n+ 1 o n+ 1 Uvažme vlastnost (7.) a rovnost, která platí pro derivaci, zintegrujme: d dx BrL(x) = (n+l)-[Bl1(x)-BUx)] \Bn+1(rWl ale W^)}\ n+ 1 i n+ 1 x (1 - x)^1"1 [P(l - i)«+i-í _ 0i(i _ 0)ra+1"í] = 0 : BU(x) - / B?(x) = 0 BU(x) = / B?{x). Platí-li vztah JQ B™(x)dx = ^- pro i, pak tedy platí i pro i — 1 (indukční krok). My ovšem víme, že platí pro i = n. Celkově tedy platí pro i = 0,..., n. I Třída všech polynomů stupně nejvýše n nad reálnými čísly tvoří vektorový podprostor vektorového prostoru reálných funkcí 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ů {e0(»,... ,en(x)} lze každý polynom zapsat jako lineární kombinaci y^yXjej(x), í=0 kde Xi jsou skaláry. Vedle známých baží z monomů tj. z polynomů ei(x) = x\ i = 0, ... , n tvoří bázi i Bernsteinovy polynomy, přičemž ei(x) = Bf(x), i = 0, ..., n. Máme tedy následující důsledek: 2. BÉZIEROVY KŘIVKOVÉ SEGMENTY 29 Věta 2.2 Bernstein-Bezierova reprezentace Každý polynomiální křivkový segment p(í) = Eľ=o a*^ ^ze zaPsat Jak° Bézierův křivkový segment b(t) = 5>ť£TO, í=0 a to následovně fc=o v y v -i afc. Důkaz. Dosazením za b» do b(í). Totiž b(t) = EL,bť5?(í) = E^oEU(fc)(fc) Ww - ELo a,Etfc (;)(:) "^) - ELoafcEtfcí;)(:)_1(:)^-^ = ELo^Et^ľ^í^i-í)^ = Efc=oa*í*Eřofc(nTfc)ť(l-í)»-^ = ELo ^fc E;:0fc ^rfc(í) = ELo ^fc = p(í). i Zároveň platí Věta 2.3 Vlastnosti Bézierových křivkových segmentů 1. Chováni 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 body nejsou interpolovaný, pouze aproximovány. 2. 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. Vliv kontrolních bodů: b» má největší vliv na b(í) v případě, že t = i/n. 4- 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 30 KAPITOLA 2. BÉZIEROVA METODA nabývá maxima. Důkaz vlastnosti konvexního obalu vyplývá okamžitě z Cas-teljauova algoritmu výpočtu bodu křivky b (í) ze zadaných kontrolních bodů. Konvexní obal množiny bodů je nejmenší konvexní množina, která ji obsahuje. 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(í). Důkaz vlastnosti omezeného kolísání bude proveden později. I Časová náročnost Casteljauova algoritmu je 0(n2). Využitím vhodné reprezentace lze křivkové body spočítat snadnou modifikací známého Hornerova schématu vyhodnocení hodnoty polynomu v čase 0(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 b0, bi,... , bn E Rd, parametrická hodnota ť E [0,1]. Výstup: Bod b(í*) Bézierova křivkového segmentu b. BEGIN IF ť < \ THEN BEGIN b := bn; FOR i := 1 TO n DO b := b • (i/(n - i + 1)) • (í*/(l - ť)) + bra_í; b := (1 -ť)n-b; END ELSE BEGIN b := b0; FOR % := 0 TO n - 1 DO b := b • ((n - i)/{i + 1)) • ((1 - ť)/ť) + bi; b:=(ŕ*)ra-b; 2. BEZIEROVY KŘIVKOVÉ SEGMENTY 31 END; b(f) := 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 ŕ* < \ (případ ŕ* > \ se ukáže analogicky). Označme výsledek v i-tém kroku příkazu FOR jakožto b* a zároveň položme b = b m přičemž pro i = 1,..., n evidentně platí 4—n_»'_i_i v / n / -/■* \ i+j—n j=n—i-\-l í* A 1 ť y+J~n(n+i-j).....% (n+l-i).....j' Totiž snadno vidíme, že opravdu b1 = bra_i+bra (jz^) ^. Indukcí pak obdržíme bra_,_! + b* (^ ͱl n — % u / t* \i+i+j-n (n + 1 - j).....(i + 1) , u /nul. V-, -U Vra V-, í * \--r^-rj->- y/t-r -ĺ jj y- T -i; , i U„_í_i -T 2^j=n-i+lu3 \l-t*) (n+l_j_l).....j "•" u™-* Vl-Í*7 n_j i , Vn , / t« x(i+l)+J-n (n + 1 - j).....(j + 1) _ ,i+i Dra_t_! + ^=n-(i+l)+l DJ 11-í* J (n + 1 _ (j + 1)).....j - D • ' Věta 2.5 Rozdělení Bézierových křivkových segmentů Každý bod b(í*); ť E [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 Bezierovy křivkové segmenty stejného stupně. Jejich Bezierovy body jsou určeny pomocnými body bu b1 bn u0,u1, . . . ,un resp. bn hn~l b° "ni n i ■ ■ ■ i "n Casteljauova algoritmu pro bod ť. Důkaz. Označme c(í) Bézierův křivkový segment s Bézierovými body bg, b},... , hrr resp. d(í) Bézierův křivkový segment s Bézierovými body b™, b™_1,... , b°. Stačí zřejmě ověřit, že c(í) = b(tť) a d(í) = b (ŕ + (1 - ť)ť) pro všechna t E [0,1]. Přitom máme = ELo^EtkBi(ť)Bm. 32 KAPITOLA 2. BEZIEROVA METODA Dokažme, že pro všechna k, 0 < k < n Y/Bl(ť)B:(t) = Bnk(tť). i=k Zřejmě však Tľ%=kBi{ť)B'm = ^mm-ít* m^i-t)' _ (+*\kn\ V^ra - \l ) u 2^i=. 1 k\ ^i=k {i-k)\{n-%)\ (1 — í*)*-*í*(l — í)T = (tť) *\k n\ En i=h (n - k)\(i - t*y-kr-k(i - ty k\{n-k)\^=k [i - k)\{n - k - [i - k))\ 3 = (tť)* [ l) TľjZo (n ;, k ) (* - ***)'(! - í)(ra-fc)-J n (tť)k[ ) (t - tť + 1 - ť)n~k n (tť)k ( ' ) (1 - tť)n~k = Bl(tť). Podobně víme n I n—i d(t) = Y.hn~iB'm = J2\Y.h-^Bk~\ť) b?(t) í=0 í=0 \k=0 n /n—i i=0 \fc=0 / „ / \ j = 0 \ 0-<> Algoritmus na zvýšení stupně Bezierový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 0{n). Algoritmus na zvýšení stupně Bezierových křivkových segmentů nám umožní zjistit ohraničené kolísání Bezierový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 2. BÉZIEROVY KŘIVKOVÉ SEGMENTY 35 případě Bezierových segmentů je kontrolní polygonialm tah právě zadaná křivka. Polygonialm 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í polygonialm tah. Iterací obdržíme posloupnost polygoniálních tahů, která konverguje k zadané křivce a pro kterou každý polygonialm 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í Bezierových segmentů jako užitečné. Zejména platí Věta 2.7 Derivace Bezierových segmentů 1. Derivace: p-tá derivace Bézierova segmentu b(í) v bodě ť je určena vztahem dp ni n—p , Mt*) = , dt? (n-p)\ ^Apbi-B?-p(ť) ni í=0 (n—p)! Apb::?(ť), kde A°b, Apb, A°bí(ť) A^(ť) = bí, = Ap~lbl+1 - Ap-lbt, i = 0,...,n-p, = H(ť), = A^+1(ť)-A^(ť), i = j,...,n-p. Přitom jsou b\{ť) pomocné body vypočítané Casteljauovým algoritmem v bodě ť. 2. Vyšší derivace v koncových bodech: p-té derivace v koncových bodech jsou zadány vztahy íh{0) = <^APb«' dp í?' a závisí tímto pouze nab0,... ,bp případně bn_p,..., bn. 3. Bézierovy body jakožto funkce derivací v koncových bodech: U = fc=0 n—i i\(n- k)\ dk n\ dtk b(0) E(-d' kfn- i\(n — k)\ dk fc=0 k n\ dtk b(l). 36 KAPITOLA 2. BÉZIEROVA METODA Důkaz. Pro p = 0 máme dt° b(í) = b(t) = £>£?(*) í=0 Y^^-But). í=0 Důkaz pro derivace vyššího stupně plyne indukcí vůči p. Druhou rovnost lze obdržet v důsledku záměnnosti Ap se sumací. Podrobněji pak máme Matematickou indukcí: a)p = 1. Využijeme vztahu ftBf(x) = n{B^{x) - B™~l(x)). 6(t) = 5>5T(t)]' dt í=0 TI—1 -mi - t)n~l + J2b^B?-i (*) - sr_1(í)]+bnnť-1 í=l yn—l(i\CL i \ i r>n—li = niBS-'it)^ - bo) + Brl(t)(b2 -b1) + ... + BZltitWn-! - 6n_2) + ^ľí(í)(6n - 6n_i)] Pro p = 1 tedy tvrzení platí. b) Předpokládejme, že tvrzení platí pro p. Dokážeme, že platí pro p + 1. r]P+1 d n! !^ ! ŕ _ \\ n-p-1 , n' V([n P)U] £ A\A^)Brp-\t) (n — p)\ (n — p — 1)! *—' dŕP+1 v ' dV(n-p)\ . n—p—í - y ^%Brp-\t) (n-p-l). l=0 2-žw) = (4öiAP&nw Matematickou indukcí. a)p = 1. Vycházíme z důkazu první části věty pro p = 1. 2. BEZIEROVY KŘIVKOVÉ SEGMENTY 37 7 n b(t) = [YJkB-(t)}> dt í=0 TI—1 -mi - t)n~l + J2b^B?-i^ - sr_1(*)]+wra_1 yn—l /_l\ í-l t \ , r>n—li = niBS^mh - bo) + B'i{t){b2 -bl) + ... + ^(íX&n-i - &„_2) + ^ľí(*)(6n - &n-l)] = «[(ß?-1^! + Br\t)b2 + ■■■+ BZll(t)bn) - (Brl(t)bo+bt1^! + • • •+5^í(í)6»-i)] = n{bnn-l-bnn-_\) Pro p = 1 tedy tvrzení platí. b)Předpokládejme, že tvrzení platí pro p, dokážeme, že platí i pro p + 1. T-^-6(í) = -f h N,Apfe^(r)] (n — p)! n' At:!+1(í)-A^::%) (n — p — 1)! n- A^^(í) (n — p — 1)! Derivace v koncových bodech obdržíme po dosazení do bodu 1. Podrobněji pak n—p Um r^y^APb.B^U*) = Um ^^A^Wl - ť) = ra! Apb (n-Py. u° n—p t —>1 j=Q t —>1 n—p — Ijm nl APT b, Rn~p(t*) — nl Apb 3.část: Bezierovy body jakožto funkce derivací v koncových bodech Nejprve dokažme pro i = 0 : b0 : b0 = b(0) 38 KAPITOLA 2. BÉZIEROVA METODA Předpokládejme, že tvrzení platí pro i a dokazujeme pro i + 1. Předpoklad: b; = j^( l )Afcb0 Protože Jjrb(O) = (ra"fc-,, Afcb0, můžeme si pravou stranu rovnice napsat jako: fc=o v 7 což si můžeme rozdělit na tři části. Dále využijeme toho, že: At+1b0 = A*^ — A*b0 f(^1)A*b„ = b„ + 5:((*)A^+(fc:i)A^)+A-bI-A-bI1 fc=0 v ' k=\ Pozn. (*) =b*+yík - i)Akh°+A'bi" A'b°= fc=l \ ' (zde po přeindexování dostaneme:) = b, + YJCk) Afc+lb°+A*bi ~ A*bo fc=0 ^ ' = bt + Y,(k) (A"bl - Afcb°) + A'bl - A*b° = b* + b*+1 - b* = b*+1 fc=0 což jsme chtěli dokázat. ad (*) - úprava binomických výrazů: i\ ( i \ i\ i\ k J \k-lj k\{i-k)\ (k - l)\(i - k + 1)\ i\(i - k + 1)\ + i\k\ i\(i-k + l + k) (i + iy fi + 1 Důkaz pro b, = E("l)fc D^ŠH^ (i - k)\(k - i)\k(i - k + 1) (i-k + l)\k\ k\(i-k + l)\ \ k Í \ (ra-fc)! dk i U i n\ dtk fc=0 \K J Opět matematickou indukcí vzhledem k n. Nejdříve ukažme, že tvrzení platí pro i = n b. = g(_D*Í!^*)í * b(i) = (-i)^A-b. = b. fc=0 2. BEZIEROVY KRIVKOVÉ SEGMENTY 39 Nyní předpokládejme, že tvrzení platí pro i a dokazujeme pro i + 1 Předpoklad: fc=0 ' fc=0 Vezměme si pravou stranu rovnice pro i + 1: fc=0 ^ \ k ) n\ dtk ra-(í+l) E (-D'( i—n 'i + l\{n-k)\ n\ y k J n\ (n-k)ľ -A bra_í_i — Sumu si rozdělíme na tři části a opět použijeme (*): = bra + ^(^) + ^ + 1))Afcbra_fc-(-l)W+1b__1 = Využíváme také toho, že b(l) = bn, což jsme dostali po dosazení p = 0 do vzorce z 2. části věty. bn + Y,(l)^k^n-k + Y,(k- i) Akhn-k - (-l^+'bn-i-l = fc=l v ' fc=l bn + J](-l)fc(^) Afcbra_fc + J](-l)fc(fc 1 A Afcbra_fc - (-l)*(A*bra_t - A^.^) fc=i ^ ' fc=i ^ ' bn.% + J](-l)fc(k %_ \Afcbra_fc - (-l)Wbra_, + (-lfAVj.! fc=i ^ ' fc=0 ^ ' bn-i^í-^rfc) (Afcbn-fc-l - Afcbra_fc) - (-l)Wbra_, + (-lj'A'b^! fc=0 ^ ' bn.l + J2(-^k(l)^n-k-i-Í2(l)Ak^ i—(\ \ / í.—n V / \ «; / fc=0 v 7 fc=0 = bra_j + b(n_i)_j — bra_j = b(n_(j_|_i) 40 KAPITOLA 2. BÉZIEROVA METODA což jsme chtěli dokázat. Pozn. : Afcbra_fc_! = Afcb( •»(n-l)-fc protole platí: fc=0 po výměně n za n — 1 dostaneme: u—n V / i.—n V / fc=0 Třetí tvrzení lze obdržet po dosazení výrazů z bodu 1. I Další výhodou je, že můžeme z pomocných bodů b\ zjistit derivace v bodě ť. Platí například b\ť) = n- (K~\ť) - b™z\(ť)). Věta 2.8 Integrování Bezierových segmentů Integrál Bezierova segmentu je opět Bézierův segment se stupněm o jedničku vyšším. Můžeme přitom nové Bézierovy body psát jako lineární kombinaci původních: íb(t)dt = [b0BZ(t) + --- + bnBZ(t)dt = b*0B-+1(t) + --- + K+1B^l(t), kde bg je integrační konstanta a platí 1 l~l b* :=—— -Vbj + b*, i = l,...,n+l. n+1 z—' Určitý integrál určený celým segmentem je pak těžiště ŕ i / b{t)dt = —— (b0 + bi + • • • + bra) Jo n+1 Bezierových bodů. Důkaz. Podle věty o derivaci Bezierových segmentů máme n+1 n n (ĚKBF1®)' =(n+l) J>*+1 - bi)Bnk(t) = 5>fc2£(t) = b(í). fc=0 fc=0 fc=0 3. RACIONÁLNÍ KRIVKY 41 Použitím věty 2.1, 8., která nám říká, že J0 B%(ť)dt = ^j-j- dostáváme 1 Ti 1 Ti / b(t)dt = x>fc / Bnk(t)dt = Y,hk- -í-, ^ fc=o ^ fc=o n + l což jsme potřebovali dokázat.I 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árni nebo afinní zobrazení. Definice. Afinní zobrazení bodu p do bodu p je tvaru: p = Ap + t, přičemž A je matice typu d x d, t E Rd a p, p G Rd. Speciální případy v R2: • Translace: P=(J j)-P + t, • Změna měřítka: a 0\ o b -p' • Rotace: cos (p — sin (p sin (p cos (p P- Afinní obraz k(í) křivky k(í) v afinním zobrazení p = Ap + t je definován jako k(í) = Ak(í) +t. Lze dokázat, že, aplikujeme-li afinní zobrazení na kontrolní body Bézierova křivkového segmentu a pak z nich sestrojíme 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 Bezierových křivkových segmentů Buď p = Ap +1 afinní zobrazení, b(í) = bo-So (*) + ''' + bn-ß™(i) Bézierův křivkový segment, b(í) jeho afinní transformace v zadaném zobrazení. Pak je b(t) = b0B's(t) + ---+bnB':(t), kde bi = Abi + t 42 KAPITOLA 2. BÉZIEROVA METODA Důkaz. Označme p = b(í), kde b(í) = ELo bfc ' ^k (*)• Obdržíme pak: Ah(t) + t = A(ELob^(í)) + t = (EL^bfc-^(í)) + t = ELo(^bfc + t)B>m = ELo bfc2£(t) = b(í). I Obtížnější je ale případ projekce: Definice. Perspektivistická projekce v normálním tvaru je zobrazení 1 0 oN 0 1 0 / p -----------(------, peR,pe R , 0 0 1) -p 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(í) = b0-E>o (ŕ) + • • • + hnB™(t) zobrazí na přičemž bj jsou utvořeny z prvních dvou složek bj a 6» 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 x _ P\Xli X2, • • • , X(i) TyX\, X2, • • • , X(l) ž Ň~ j q{xi,x2,...,xd) přičemž p a q jsou polynomy 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 Rd je určen vztahem Racionální Bézierův křivkový segment v Rd je definován pomocí vztahu U(A ßohoBZ(t) + ---+ßnbnBZ(t) 3. RACIONÁLNÍ KRIVKY 43 Koeficienty bj 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. Racionální Bézierovy křivkové segmenty v Rd můžeme považovat za perspek-tivistickou projekci obyčejných Bezierovych křivkových segmentů v Rd+1, přičemž se bude promítat vzhledem k počátku do roviny Xd+i = 1- Pro racionální Bézierův křivkový segment b(í) definujeme Bézierův křivkový segment b*(í) jakožto b*M=C!:]):=gft'h(ť)- b* (t) má tedy Bézierovy body í J„ 3 J a přechází vzhledem ke zmíněné per- spektivistické projekci do b(í). Množina racionálních Bezierovych segmentů je uzavřená vzhledem k perspek-tivistické projekci. Možnost reprezentace racionálních Bezierovych segmentů jako projekce obyčejných Bezierovych 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 Bezierovych křivkových segmentů 1. Chováni v koncových bodech: Kontrolní polygon a racionální 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 body nejsou interpolovaný, pouze aproximovány. 2. Vlastnost konvexního obalu Křivkový segment leží v konvexním obalu Bezierovych bodů. Zejména tedy leží i v konvexním obalu Bézierova polygoniálního tahu. 3. Vliv kontrolních bodů bj nemá obecně největší vliv na b(í) v případě, že t = i/n. 4- 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 Rd+1. Uvažme racionální Bézierův křivkový segment: h() = ß0b0B'S(t) + ...+ßnbnB'Z(t) U ßoBZ(t) + ...+ßnBn(t) čitatele označíme u{t) a jmenovatele v(t). Platí 44 KAPITOLA 2. BEZIEROVA METODA u'(ť)v(ť) - u(t)v'(t) Pro počáteční bod dokážeme b! - b0 b'(0) Ibi - b '0 Podle věty 2.7 platí u'(O) = n(Abi-A)bo) v'(0) = n(A-A)) Dále platí u(0) = ß0b0 v(0) = ßo Tedy b'(0) n(Abi - /30b0) • y(Q) - u(0) ■ n(ß1 - ß0) v2(0) n/?oAbi - ™/3obo + n/3oAbo - nß%b0 n/?i(bi - b0) A) Dosazením dostáváme b'(0) ra/?l(bi-bo) l|b'(0)|| ra/?l(bi-bo) 1 1 /?o 1 1 bi -b0 Ibi -b0 Pro koncový bod dokážeme 3. RACIONÁLNÍ KRIVKY 45 Podle věty 2.7 platí bn - bra_i _ b'(l) Ibn-b^H ~ ||b'(l)| u'{\) = n(ßnbn - /3ra_ibra_i) v'(l) = n(ßn-ßn_x) Dále platí u(l) = ßnbr, v{l) = ßn Tedy b'(l) n(ßnbn - /3ra_ibra_!) • v(l) - u(l) • n(ßn - ßn_i) v2(l) nß2nhn - nßnßn-ibn_i + nß2nhn - nßnßn-ibn ß2 nßn-i(bn - bra_i) ßn Dosazením dostáváme , ,/1-, ra/3n_i(bn-bn_i) b (1) _ -ß-n _ bn - bra_! |b'(l)|| \\nßn-i(i;.-M|| H^-b^l I I Pri I I Dále dokažme vlastnost 2. Vycházejme z definice konvexního obalu: n conv(x) = { í=0 i(x) = {N Cüj.Xi : N čuj = 1, cüi > 0, Xi G x} Chceme tedy dokázat, že : b(í) G conv(b0, ....,bn) 46 KAPITOLA 2. BÉZIEROVA METODA Tedy : b*(t) G conv.((ßo*°\......, (ßn*n )) b*(ŕ) G conv.(ßibi) b* (í) = S^í-A-bj, J]o!í = 1, cuí > O í=0 n b* (t) = Y^oti.ßi n h(t) = W; = -™-----= E^^-b, 'M T,aj-ßj i=o T,aj-ßj 3 = 0 3 = 0 J2®i-ßi Ale : ^-------= 1 3=0 A tím je důkaz hotov. 3. Vliv kontrolních bodů: Bézierův křivkový segment je tvaru: Y] 3a 3 .£>""(£) j=o\ Pi J n Jeho projekcí dostávám výraz : L-\í----------- Úpravou dostáváme výraz: J' 3-----.b7 Eft-B?(*) i=0 Maximum záleží pouze na výrazech, kde se vyskytuje t, tedy výraz ßj můžeme vynechat a výraz B^it) dát do jmenovatele a potom hledáme maximum výrazu: i _ i E ft. I . ) .ti-J.il-tr-i-^-i) jrßi( . ).(j^)i-J i=o \ l I i=o \ l ' Tedy hledám minimum výrazu :EA-( • )-(i~t) í=o V V L-\i-j 0 < -~zrt < oo Označíme si -^- jako a a výraz zderivujeme podle a a položíme roven 0, abychom zjistili extrém (minimum) : ffr.rY(i-3)^-3-1 = o 3. RACIONÁLNÍ KRIVKY 47 Existuje Cü0, pro které je f(a0) rovna nule: j > i ->■ - A existuje jediné, neboť funkce je spojitá a rostoucí. j = 0: Ö -^2+1 = 0 a2 = l, a = l, a E (0,oo) Dosadíme za a : a = -^ =>l = 2ŕ=^ŕ=| Tedy pro j = 1 věta platí. Ale zkusme jinou volbu: ßo = 2> A = 2' A = 2 : /(a) = |cü + 2o! + 1 /(a) = -io!2 + 2 Tedy obecně se t nerovná -. I Připustíme-li i záporné váhy ßi} ztratíme částečně výše uvedené vlastnosti. Zároveň lze bez problémů provést dřívější algoritmy pro racionální segmenty. Algoritmus se provede pro obyčejný Bézierův segment v Rd+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 (ŕ*). 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 = ť. Pro první dílčí křivku jsou to 48 KAPITOLA 2. BÉZIEROVA METODA KM, HO ) Hl i a pro druhou dílčí křivku jsou to bn bn~l b° "ni n i ■ ■ ■ i "ni on on-1 oO Hn i Hl i • • • i Hn' Stejně jako obyčejné Bezierovy segmenty lze reprezentovat racionální Bezierovy segmenty o n + 1 Bezierových bodech beze změny tvaru křivky jako racionální Bezierovy segmenty o n + 2 Bezierových bodech. Nové Bezierovy body a váhy lze získat jako konvexní kombinaci dvou starých Bezierových bodů popř. vah: h(í) ßobQBS(t) + ---+ßnbnB2(t) [) ß0B™(t) + ---+ßnB™(t) ß*0b*0B'S+\t) + ---+ß*n+1bnB:X1i(t) ßoBr\t) + ---+ß*n+lE:x\{t) ' s novými Bezierovy body a váhami b* = b,1 • í i J , i = 1,..., n, b* = b°, b*n+l = b°, ß* = ßl ■ ( ^j"' y i = 1, • • •, n, ßl = ß°0, ß*n+! = ßl, Racionální Bezierovy segmenty nám na rozdíl od obyčejných Bézierovových segmentů dovolují 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 ßo = ß\ = 1. Pak racionální Bézierův segment stupně dva tvaru () = ßob0B20(t) + Abi^(ŕ) + ß2b2B22(t) U ß0B2(t) + ß.BJit) + ß2Bl(t) je • Elipsovitý segment, pokud ß\ < 1, • Parabolický segment, pokud ß\ = 1, bn ■ ■ ■ i "ni ■ ■ ■ i Hn i • Hyperbolický segment, pokud ß\ > 1. 3. RACIONÁLNÍ KRIVKY 49 Důkaz. Dosadíme do vztahu ßQ = ß2 = l b0ßo2(*)+Abiß?(i) + b2ß22(i) b(í) Blit) + ß^lit) + Blit) Z definice Bernsteinova polynomu stupně n dosadíme za B?(t) = í . )ťl(l t)n~\ i=0,...,n b0(l-t)2 + 2ß1b1t(l-t) + b2t2 b(t) (l-t)2 + 2ß1t(l-t)+t2 Podle Věty 3.1. platí, že, použijeme-li afinní zobrazení na kontrolní body Bezierova křivkového segmentu a pak z nich sestrojíme křivkový segment, dostaneme totéž, jako když uvedené zobrazení aplikujeme na Bézierův křivkový segment. Můžeme tedy, bez ztráty na obecnosti, umístit body b0 a b2 na osu x symetricky podle počátku souřadnic M, tj. střed úsečky b0b2. Průsečík přímky Mb\ s racionálním Bézierovým segmentem označme X. Vypočteme hodnotu b(í) pro t = 0, 5: b(0,5) = b_o , ft b i , b_2 4 "*" 2 "*" 4 I _l_ Ěl _l_ I 4 "I" 2 "t" 4 Protože jsme body b0 a b2 umístili navzájem symetricky vzhledem k počátku souřadnic, platí: b0 = —b2 b(0'5) = TTÄ ^ bpj = 1 + A b(0, 5) =X a zároveň body M, X, b\ leží na téže přímce. Dosazením dostáváme: MX íl 50 KAPITOLA 2. BÉZIEROVA METODA Dále využijeme větu z teorie kuželoseček (učební texty Janyška, Sekaninová, Analytická teorie kuželoseček a kvadrik, V. 18.4), která říká, že každou kuželosečku lze zadat jako množinu bodů roviny, které mají od dané přímky a daného bodu ležící mimo přímku konstantní poměr vzdáleností k > 0. Ověření, že se jedná v našem případě skutečně o kuželosečku, nechávám na čtenáři. Pro elipsu je k < 1, pro parabolu je k = 1 a pro hyperbolu je k > 1. Dosazením a úpravou nyní dostaneme: ßl \MX\ ßl-1 ßl(l-k~1)-ßl = l ßik~l = 1 ßi = k => ßi < 1 Pro ßi < 1 je tedy racionální Bézierův segment elipsovitý (ßi = 1 je parabola a pro /3i > 1 je hyperbola). I 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 ctyřúhelníkové Bézierovy segmenty, následovně trojúhelníkové Bézierovy segmenty. 4.1 Ctyřú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 bjj, i = 0,..., n, j = 0,... , m. Dva Bézierovy body bij, hk>i jsou spojeny hranou, pokud (i,j) = (k±l, l) nebo (i, j) = (k,l±l). Definice. Ctyřúhelníkový Bézierův segment v R3 je tvaru: n m b(u,v) := Y,Y,h^ ' B?^ ' ^"»> u>v G [°> ^'b« G R3- i=0 j=0 Mnoho vlastností Bézierových křivkových segmentů lze přenést na ctyřúhelníkové Bézierovy segmenty. Uvážíme-li vnitřní součty m bi(v):= Y,*>U-&T(v)> i = 0,...,n, 3=0 4. PLOCHY 51 obdržíme systém Bézierovových segmentu v prostoru. Zejména pak n b(u,v) = Y,^(v)-B?(u). í=0 Pro pevnou hodnotu v = v* se opět jedná o Bézieruv segment, který má kontrolní body bj(i>*), i = 0,...,n. Bod h(u*,v*) lze spočítat tak, že nejprve zjistíme použitím Casteljauova algoritmu na kontrolní polygoniální tahy hitj, j = 0,..., m a v = v* bod bj(i>*). Na kontrolní polygoniální tah bj(i>*), i = 0,..., n opětovně aplikujeme Casteljauuv algoritmus pro u = u*. Výsledkem je hledaný bod roviny h(u*,v*). Algoritmus, (de Casteljau, pro čtyřúhelníkové Bézierovy segmenty) Vstup: (n + 1) • (m + 1) Bézierovy ch kontrolních bodů hitj, i = 0,... ,n, j = 0,... ,m, u*,v* E [0,1]. Výstup: Bod roviny h(u*,v*) určený Bézierovými kontrolními body bjj, i = 0,...,n, j = 0,...,m. Postup: 1. Spočtěme c» := ^JLo ^íj ' B^(v*), i = 0,... ,n, podle Casteljauova algoritmu, i = 0,... ,n. 2. Spočtěme b(u*,v*) = Eľ=o cí ' Bľ(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. Vlastnost konvexního obalu: Body h(u, v) leží v konvexním obalu definujících Bézierových bodů. 2. Vliv kontrolních bodů: Bézierův bod bitj má největší vliv na segment h(u, v) v případě, že (u,v) = (i/n,j/m). 3. 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- Planarita: Bézierova rovinná část je rovina právě tehdy, když Bézierova kontrolní část tvoří rovinnou mřížku. 5. 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. 52 KAPITOLA 2. BÉZIEROVA METODA 1. Bod b (tí, v) leží v konvexním obalu definujících Bezierových bodů. Z definice víme, že n m b(u,v) = Y^y»-B^(u)-Bľ(v)'u'v G M.btf G R3, kde ßf'(x) = í • ) -^-(1 — x)n~% pro i = 0,..., n, x e [0,1] G R a bjj jsou Bézierovy body. Stačí dokázat, že koeficienty uvedeného součtu splňují n,m l>BUu).Bf(v)>0a Y, B?(v)B?(v) = l í=lj=l Již víme, že n m í=i j=\ odkud tvrzení plyne okamžitě. 2. Bézierův bod bý- má největší vliv na segment h(u, v) v případě, že (u, v) = (^, ^). Koeficient u bodu bý- je Bf(u).B™(v), který je definován jako ^ (m>) .u\(l - u)n-\v3.(l - v)m~3. Hledáme takové body u,v, pro které tento výraz nabude svého maxima. Budeme jej tedy derivovat podle příslušných proměnných u,v. Začneme derivováním podle u: , .i.uz-\(l - u)n-\v3.{l - v)m~] %) \ 3 n) (m].ui.(n-i).(l-u)n-i-1.vj.(l-v)m-j = Vytkneme výrazy, které jsou společné oběma sčítancům n \ ( m \ „,i íi _ „,\m-i ^,i-1 í^ _ v,\n-i-1 Obecně je .v3.{I - v)m-3.ul-\{\ - u)n-l-\[i.{\ -u)+ u.{n -i)]=0 % ) \ 3 J .v3.(l-v)m-3.ul-L.(l-uY % I \ 3 ' 4. PLOCHY 53 ve vnitřních bodech intervalu [0,1] kladný, tedy : [i — iu + un — ui] = 0 i + un = 0 i u = — n Určení v se provede analogicky. Nutně ze spojitosti funkce B™(u).B™(v) vyplývá existence maxima na uzavřeném intervalu [0,1] x [0,1]. Přitom maximum nemůže nastat na okraji čtverce tedy musí nastat na množině (0,l)x(0,l). Ověřme dále poslední tvrzení. Pro přímku ležící v rovině u — v platí u = kv + q. Zobrazením této přímky dostaneme polynom v proměnné v: n m f (v) = b(kv + q,v) = Y,Y,b« ' B^kv + ^ ' Si» = í=0 j=0 J2Í2^4l)v3{1~vr~3(l){kv+q)t{1~kv~qr~l Vidíme, že v dosáhne po roznásobení v první části výrazu stupně nejvýše j + (m — j) = m, kv a tedy v dosáhne v druhé části výrazu stupně nejvýše i + (n — i) = n. Nejvyšší stupeň křivky je tedy m + n. I 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 0{m2 ■ n + n2), pokud postupujeme nejprve v m—směru a pak v n—směru. Přirozeně lze však vyhodnocení provést pomocí Hornerova schématu. Časová náročnost je pak 0(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£ • body, které obdržíme Casteljauovým algoritmem pro křivky bj(i>) := ^"=0 hitjB1Jl{v) při volbě v = v*. Čtyřúhelníkové Bézierovy segmenty n m c(u,v) := £ZX- • B{(u) ■ B?(v), u,v G [0,1] i=0 j=0 n m d(u,v) :=£$>£"'' • B{(u) ■ B?(v), u,v G [0,1] í=0 j=0 54 KAPITOLA 2. BÉZIEROVA METODA rozkládají segment n m b(u,v):=J2Y.h^-Bľ(u)-B™(v) í=0 j=0 do dvou dílčích segmentu podél krivky h(u,v*). Důkaz. Víme, že n m í=0 j=0 To se podle definice rovná n Y,čt(v)B'nu), í=0 kde m čt(v) = Y,H,JBT(v). i=o K dokázání tvrzení stačí zřejmě dokázat rovnost čtyřúhelníkových segmentů c(u,v) a h(u,vv*), respektive d(u,v) a h(u,v + (1 — v)v*). Podle definice čtyřúhelníkových segmentů platí, že n m n b(u,vv*) := £Ebť>u*) • B?(u) ■ Bf{v) = J>(OT*)St» í=0 j=0 i=0 n c(u,v) = Y,^(v)BUu) í=0 tzn. potřebujeme ověřit rovnost n n í=0 í=0 Z toho vyplývá, že stačí dokázat rovnost b^vv*) = či(v). Ale čj(i>) jsou kontrolní body Bézierových křivkových segmentů, které jsme dostali rozdělením jednotlivých Bézierových křivkových segmentů podle bodů hi(v) konkrétní volbou v = v*. Naše rovnost tedy plyne přímo z dělení Bézierových křivkových segmentů. Stejným způsobem dokážeme i rovnost d(u,v) a h(u,v + (1 — v)v*). Totiž b(u,v + (l-v)v*) = Y,toY,7=oW'3(v + (l-v)v*)-Bnu)-B™(v) 4. PLOCHY 55 kde di(v) = Y^T=o^>m~:'JíJ-B™(v). Stačí ověřit rovnosti n n 5>(t; + (1 - v)v')B?(u) = Y,Mv)B?(u) i=0 í=0 bt(v + (l-v)v*)=ďt(v) a to jsou opět rovnosti příslušných křivkových segmentů.I 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^j jako kontrolní body Bezierova 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ů b0)o, • • •, bra;TO G R3 čtyřúhelníkového Bezierova segmentu. Ctyřúhelníkový Bézierův segment s (n + 1) • (m + 2) kontrolními body bo o,..., b* m+1 tak, že b* b* — bí;0, = Cüjbjj.i + (1 - aj)bitj, aj := j/(m + 1), j = 1,... ,m, = b, Ji,mi splývá s čtyřúhelníkovým Bézierovým segmentem o (n + 1) • (m + 1) kontrolních bodech, tj. platí, že plocha n m b(u,v):=Y,Y,h^-Bľ(u)-B™(v) i=0 j=0 n m+1 je totožná s plochou b*(u,v) :=J2Y, hh ■ Bľ(u) ■ BT+»- í=0 j=0 Důkaz. Plyne bezprostředně z odpovídající věty pro Bézierovy křivky. I 56 KAPITOLA 2. BÉZIEROVA METODA 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 segmentuje určena pomocí (n+l)-(n+2)/2 Bézierových kontrolních bodů bÍJ;fc, 0 < i, j,k, i+j + k = n. Dva Bézierovy body bíj,fc, bpgí. jsou spojeny hranou sítě, pokud (i,j,k) = (p ± l,q ± l,r) nebo (i,j,k) = {p,q±l,r±l) nebo (i,j,k) = {p±l,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 R3 je tvaru: b(u,v) := Y^ hiJ,k- BiJík(u,v,l-u-v), i,j,k > 0 i + j + k = n u,v e [0, í\,u + v < l,bi,j,k e R3, kde B™jk(x,y,z) jsou zobecněné Bernsteinovy polynomy tvaru Til j-*í,j,k\x> y>z) ■ -i -i; ix y z' 'J' iljlkl 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 zobecněných Bernsteinových polynomů 1. Rozklad jednotky: Součet zobecněných Bernsteinových polynomů stupně n je 1: n Yl Bh,Áx,y^) = l- i,j,k > 0 i + j + k = n pro 0 < x, y, z < 1, x + y + z = 1. 4. PLOCHY 57 2. Pozitivita: Zobecněné Bernsteinovy polynomy jsou v množině S'3 = {(u,v, 1 — ti — v) : O < tí, v, u + v < 1} nezáporné: Btj,ÁxiViz) > °> (x,y,z) E S3. 5. Maximum: B™jk(x, y, z) nabývá svého maxima v množině S3 v bodě (^, ^, ^), i,j,k>0, i + j + k = n. 4- Rekurze: Pro i, j, k > O, i + j + k = n platí Bh,Áx> y>z) = xB7-Lk(x> y>z) + yBU\k(x> y>z) + zBľj,l-Ax> y>z)- Je tedy Bernsteinův polynom stupně n konvexní kombinací tří Bernstei-nových polynomů stupně n — 1. Důkaz. Snadné cvičení.l Věta 4.5 Vlastnosti trojúhelníkových Bézierových segmentů 1. 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. Chování v hraničních křivkách: Okrajové křivky rovinného segmentu jsou Bezierovy segmenty. 3. 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. 1. Zřejmé. 2. Ukažme tedy, že okrajové křivky rovinného segmentu jsou Bezierovy segmenty. Zřejmě množiny parametrů, které odpovídají okrajům, jsou {(u,0) :u E [0,1]}, {(0,v) : v E [0,1]} a {(u,l - u) : u E [0,1]}. Počítejme b(u, 0) = T,i,j,k>Q,i+j+k=n \l,kBľ,3,k(U> 0, 1 - M) = Y,i,k>0,i+k=n hi,0,kB?flík(u, 0,1 -U) = T,0<í0,i+j+k=n hi,J,kBi,j,k(Q> v,l-v) = EJ)fc>0J+fc=n hO,l,kBo,3,fc(0, V,l-V) = Eo-i5jra(«)- b(u,l-u) = T,i,3,k>o,i+j+k=n hi,j,kBitjík(u, 1 - u, 0) = T,íd>0,í+j=n hí,i,0B?J,o(u, 1 - U, 0) = Y^O 0,i + j + k = n, parametrická hodnota (u*, v*). Výstup: Bod křivky b(u*,v*). Postup: BEGIN FOR i:=0TOíiDO; FOR j:=0TOn-«DO BEGIN k := n — i — j; "i,j,k := "i,j,k'i END; FOR (:=lTOnDO FOR i:=0TOn-IDO FOR j:=0TOn-I-iDO BEGIN k := n — l — i — j; H,j,k ■= u* ■ bi+Lfc + v* ■ h\~3l+i,k + (1 - m* - v*) ■ h\-lk+l-END; b{u*,v*):=bZ0fl END. 4. PLOCHY 59 Lemma 4.6 Pro pomocné body b^ • fc de Casteljauova algoritmu pro trojúhelníkové Bézierovy segmenty platí íl __ \ A i O r>l í * * -i * *\ Gi,j,k ~~ / y Dí+í*j+j*,fc+fc* ' ^í*,j*,k*\u ,V,l — U — V ). i*+j*+k*=l Důkaz. Budeme postupovat matematickou indukcí vzhledem k /: Nejprve ukážeme tvrzení pro / = 0. Zřejmě i 0 __ k __ \ A i 0 rjO / * * -i * *\ Gi,j,k ~~ Díj',fc ~~ / j Gí+í*,j+j*,k+k* ' ^í*,j*,k*\u ,V , 1 — U — V ), i*+j*+k*=0 protože suma na pravé straně se sčítá pouze pro jediný sčítanec (volba i* = j* = k* = 0). Dále víme, že bod b' -fc můžeme pro / > 1 zapsat takto: h\>hk = u* ■ h\-+\^k + v* • b^1;fc + (1 - u* - v*) • b^+1, přičemž n — l = i + j + k Tento výraz můžeme rozepsat podle indukčního předpokladu: bU = «; • btiJ;fc + v* ■ Wr^hk + (1 - u* - v*) • b^ = U ■ Z^i*+j*+k*=l-l "i+l+i*,j+j*,k+k* ' Bi*,j*,k*\u ,v A~u — v ) + V* ' Z^i*+j*+k*=l-l °i+i*,j+l+j*,k+k* ' Bi*,j*,k*\u*>v*> í — U* — V*) + (1-u*- v*) ■ Ei*+j*+fc*=i-i h^,3+r,k+i+k* ■ Blř^ik.{u*,v*, 1-u*- v*). Pro / = n pak máme, že bg 0 0 je hledaný bod plochy. Odtud pak dostáváme korektnost Casteljauova algoritmu. Časová náročnost algoritmu je 0(n3). Paměťová náročnost je omezena 0(n2), protože pro pevnou hodnotu / musí být v paměti obsaženy pouze pomocné body bÍJ;fc a b~^k. Někdy je vhodné použít Hornerovo schema. Věta 4.7 Rozdělení trojúhelníkových Bézierových segmentů Množinu u— v-parametrú 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 jej postupně 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 pro 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 bt0jín_i_j, 0 < i < n, 0 < j < n — i. • Pro trojúhelník [(0,0), (u*,v*), (1,0)] obdržíme kontrolní body b^_j • -0; 0 < i < n, 0 < j < n — i. 60 KAPITOLA 2. BEZIEROVA METODA • Pro trojúhelník [(0,1), (u*, v*), (1,0)] obdržíme kontrolní body b*-0 j -; 0 < i < n, 0 < j < n — i. Důkaz. Cvičení. I Věta 4.8 Zvýšení stupně trojúhelníkových Bezierových segmentů Buď dáno (n + 1) • (n + 2)/2 kontrolních bodů bÍJ;fc eR3,0 0 i + j + k = n je totožná s plochou b* (u, v) := Yl hh,k ■ B?lk(u>v> í-u-v), i, j, k > 0 i+j+k=n+l Důkaz. Cvičení. I 4.3 Racionálni 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 R3 je tvaru: ,, , =EtoEJ"LoA,AJ-i?r(^)-i?» [U,V)' ZLoE7=ofr,rB?(u)-BT(v) u,ve [0,1], Aj >0, b„GR3. Kontrolní síť čtyřúhelníkového Bézierovova segmentu je určena (n + 1)- (m+1) Bézierovými kontrolními body bij a jejich vahami ßij > 0, i = 0,..., n, j = 0,... ,m. 5. VYŠŠÍ DIMENZE 61 Definice. Racionální trojúhelníkový Bézierův segment v R3 je tvaru: h(u,v) : Eí+i+fc=nßi,j,hbi,j,k ■ B?jík(u,v,l-u-v) Ei+J-+fc=n ßi,3,k ■ Bľ,j,k(U> V,l-U-V) ßi,i,k > 0, u, v e [0,1], u + v < 1, bij,fc G R3. Racionální Bézierův segment v R3 lze chápat jako perspektivistickou projekci Bézierova segmentu v R4 vzhledem ke kontrolním bodům í %'l. ÍJ J na rovinu x4 = 1. Známé vlastnosti Bezierový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, (^-dimenzionální čtyřúhelníkový Bézierův segment v Rm je tvaru: x(«i, •..,«*):= Ě E ■■■ E b'iA.....^ • B£M ■ B?M ■■■■ ^ľ/M, J1=0 »2=0 *d=0 ui,u2,... ,ud G [0,l],ni,n2,... ,nd G N. Kontrolní síť čtyřúhelníkového Bézierovova segmentu je určena (ni + 1) • (ri2 + 1) • ... (na + 1) Bézierovými kontrolními body bíl;.. yid a jejich vahami ßiyj > 0, i = 0,...,n,j = 0,...,m. Definice, (^-dimenzionální trojúhelníkový Bézierův segment v Rm je tvaru: x(tí0, . . . , Ud) '■= / y ^>i0,i-i,...,id ' -Sio,ii,...,id('uO) uli ■ ■ ■ i ud)i io+h-\----\-id=n,io,---,id>0 Uo,uu. ..,ude [0,l],uo + Ui-\--------Vud = l,bíl;...)íd G R"\ kde Bi0yily_yid(ua,Ui,... ,Ud) jsou zobecněné Bernsteionovy polynomy tvaru Til -Dío,íi,---,*d(M0) Mi, ... , ud) := || ~iu0 ul ■ ■ ■ ud i Iq\1\\ . . . ld\ 0 < i0, H, ■ ■ ■ , id, io + H H--------Yid = n. 62 KAPITOLA 2. BÉZIEROVA METODA Algoritmy platné pro plochy lze podobně dokázat také pro tyto formy. Mimo to lze navíc vytvořit hybridní d—dimenzionální segmenty, kde namísto křivek lze použít dí-dimenzionální trojúhelníkové Bezierovy segmenty. Kapitola 3 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. Diferenciální geometrie používá jiný způsob vyjádření, tzv. implicitní vyjádření Definice. Implicitní vyjádření křivky v R2 (rovinné křivý) je nulová množina funkce F, tj. F(x,y) = 0 pro F : R2 ->■ R. Implicitní vyjádření plochy v R3 je nulová množina funkce F, tj. F(x, y,z) = 0 pro F : R3 ->■ R. Implicitní vyjádření křivky v R3 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 : R3 ->■ R. Příklad implicitně definované křivky v rovině je 63 64 KAPITOLA 3. KRITÉRIA KVALITY 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 x2 + y2 + z2 = 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 x2/a2 + y2/b2 = 1, • hyperbola x2/a2 — y2/b2 = 1, • parabola y2 = 2px. Obecně lze kuželové řezy popsat pomocí rovnic tvaru a-x2 + b-y2 + c-x-y + d-x + e-y + f = 0. 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-x2 + b-y2 + c-z2 + d-x-y + e-x-z + f-y-z + g-x + h-y + i-z + j = 0, tj. reprezentují se pomocí kvadratické rovnosti, z čehož vzniklo jejich jméno. Počet typů je mnohonásobně větší než pro kuželové řezy: • Kužel: x2/a2 + y2/b2 — z2 = 0 • Dvojdílný hyperboloid: x2/a2 — y2/b2 — z2 = 1 • • • Jednodílný hyperboloid: x2/a2 + y2/b2 — z2 = 1 Elipsoid: x2/a2 + y2/b2 + z2 = 1 Eliptická válcová plocha: x2/a2 + y2/b2 = 1 • Eliptický paraboloid: x2/a2+y2/b2+2cz = 0 • Hyperbolický paraboloid: x2/a2—y2/b2+2cz = 0 • Hyperbolická válcová plocha: x2/a2 — y2/b2 = 1 • Parabolická válcová plocha: x2/a2 — 2by = 0 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES 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 z = 0. V závislosti na tvaru plochy se může křivka rozpadnout do více 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. Uvaž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 p1 a p2 třídy Cr mají ve společném bodě x styk řádu j, jestliže existují takové jejich lokální parametrizace ki(í) a k2(r) tak, že ki(í0) = k2(ío) = x a (fki _ (fk2 . . 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ů. 66 KAPITOLA 3. KRITÉRIA KVALITY 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 = \l l + [ — ) dx, dx J • při parametrické reprezentaci k(í) = (x(t),y(t)) rovinné křivky: ds = y/** + tf*dt=n k'(t) = (x',y') = (^,f )• Délka oblouku je ŕ / ds. Ja Při parametrické reprezentaci pak dostaneme ds= v^'2 + v'2dt. Ja Ja To lze snadno dokázat tak, že zvolíme rozdělení (ti) intervalu [a, b], uvažujeme aproximaci Y^ \?(x(ti+i)-x(ti))2+(y(ti+i)-y(tj))2 ,. , x l^í ü^=ü lři+i - «) X^ (x(ti+1)-x(ti)\ . (y(ti+i)-y(ti)\ /, , s -i^i y ^ ti+1-ti ) + (, ti+1-ti ) ■ C*í+i - U) 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: t(.) := lk(.). Parametrizace pomocí délky oblouku je důležitý teoretický pomocný prostředek. Platí např. 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES Věta 2.1 Přirozeně parametrizované křivky Buď t parametr libovolné parametrizace, s parametr přirozené parametrizace. Pak platí: í- 1 = 11^)11, 3. l = ||k(s)||, 4. ki_k. Důkaz. První tvrzení plyne derivací funkce s(t) = Jt | |k'(x) | \dx. Tvrzení 2 plyne z 1. Totiž k'(í) = f = f § = k(s) • ||k'(í)||. Tvrzení 3 plyne bezprostředně z 2 a tvrzení 4 obdržíme derivováním vztahu i(s)2+ V (s)2 = 1 odvozeného z 3. Pak máme 2- x (s)- x (s) + 2- y (s)- ý (s) = 0.1 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 Rd 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 Rd v bodě je přímka, která má s křivkou v daném bodě styk 1. řádu. Pro diferenciovatelnou funkci F : R3 —► R se definuje gradient VF (někdy i 8F) jako VF := (Fx, Fy, Fz), Fx, Fy, Fz 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) t = VF x VG = Fy G„ Fz Gx GT Fz Gz 0 v prostoru platí: F F ± ry ± 7, GT G,, • Při parametrické reprezentaci x = x{ť), 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(í) křivky řezu. Platí pak F(g(í)) = 0 VF • g' = 0, 0. G(g(í)) = 0 VG • g' Tečný vektor g' je tedy kolmý jak k VF tak k VG a je tedy určen až na násobek jakožto vektorový součin VF x VG. Vztah pro tečný vektor pro parametrické vyjádření plyne limitním přechodem sečen k tečně.I 68 KAPITOLA 3. KRITERIA KVALITY Definice. Křivost je odchylka křivky od přímky, tj. i- ^ k = nm -z^z ■ pq^o pq pq přitom označuje délku části křivky určené p a q, p ú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 qar, q->par^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. Křivost: • při implicitní reprezentaci F(x,y) = 0 v rovině: K A XX A xy -í1X A yx 1 yy Fy " X Fy 0 3 ) 2 (^2 + F*) • při explicitním vyjádření y = f{x) v rovině: I" (l + (/')2)*' • při parametrické reprezentaci x = x(t),y = y{t) v rovině: x1 y1 K x" y" (x'2 + y'2)l při parametrické reprezentaci x = x(t),y = y{t), z = z{t) v prostoru: ix'2 + y'2 + z'2) ■ {x"2 + y"2 + z"2) - {x'x" + y'y" + z'z")2 K (x'2 + y'2 + z'2)3 2. Poloměr p oskulační kružnice: p= -. K 3. Střed oskulační kružnice: 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES při implicitní reprezentaci F{x,y) = O v rovině: {F2X + ŕ?) • při explicitním vyjádření y = f(x) v rovině: A XX A xy "x A yx 1 2/2/ Fy " X ^ 0 (i + (/'r) /-/' /" V i při parametrické reprezentaci x = x(t),y = y{t) v rovině: (x'2 + y'2) f -y' x' y' x" y" x Důkaz. Uvažme normované tečny t (í) o délce 1 na místech t a t + Aŕ. Pro úhel ip sevřený těmito tečnami platí p _ ||t(t + At)-t(t)|| S1IV_ 2 Odtud pak plyne: k = lim pq^o pq - lim— 2^/í2sinmV H^+^-tfflH . ^} = l.||ť(í)||-l/a'(í). Pro křivku k(í) vztahů x v t ť v parametrickém vyjádření obdržíme s pomocí k' Vk'+k'' k'*k" , ] (k'*k'y _ (k,*k,)(k"*k"j-(k,*k" -k", k'*k'^ ' (k'*k'Y s'(t) = AM? vztah k = ll\2 (k7 * k') (k" * k") - (k' * k") (k' * k') 70 KAPITOLA 3. KRITÉRIA KVALITY pro zakřivení. Pro prostorové křivky lze pak pomocí vektorového součinu psát _ ||k'xk"|| (k'*k')* ' Vztah pro střed oskulační kružnice je obecně tvaru 1 1 c = P + ~ ' TTTT ' n) k ||n|| kde p je bod křivky, k zakřivení a n normála. I V každém bodě p prostorové křivky lze až na singulární výjimky 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 (Prenetův trojhran) prostorové křivky k je pravotočivý 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 k n = —-—. II kll Binormála b: Binormála je kolmá na tečný vektor a na hlavní normálu. Zřejmě b = t x 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. Křivka zůstává (v nějakém e-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. 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GE0METRIE71 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 y l|Ab|| r = nm ———• pq^o pq Přitom Ab 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í T = (x'2 + y'2 + z'2)3 x y z x" y" z" x'" y'" z'" Důkaz. Vztah pro torzi při parametrickém vyjádření k : R i Ab i k r = linier- Jl^ll = IIb t x n =k x b = k*k k*k Vk*k (k x k) 1 Vk*k k x k. 'x' R3 plyne z Zde t je normovaný tečný vektor a platí t = k = | y ) , n je hlavní normála .ž, x\ a platí n = -J^-ň = jAt I y I , křivku k uvažujeme jako funkci délky oblouku s. \k\\ |k| \..\ Z toho vyplývá: b = t x n = k x k 1 \k\\ \\k\ První souřadnice výše uvedeného výrazu má tvar: ý ž x ž x y y z i x z 1 x y y z y z yz-yz yz-yz 72 KAPITOLA 3. KRITÉRIA KVALITY Derivace této souřadnice dopadne následovně: (y z + yz — y ž — ýž) pil — (y z — ýž) 2 [x x + ý y + z z) 2 pil (x2 + ý2 + ž2) y v ž "ž y y ž ž \k\\ \h\\ (x x +ýy + z z) . n . , k x k k x k •• ... první souřadnice výrazu —p-r-----------—3—(k, k) Přitom k x k lze psát jako lineární kombinaci k*k kxk = ^&^k + k*k (kxk)*(kxk) (k x k) = kiík2ík)k+J^(kxk). k*k (k*k)2 k, k a k x k. Zároveň lze využít, že k a k jsou navzájem kolmé a || k Obdržíme tedy: = 1. b b (í^).k=|k,k,k (k*k)2 |k,k,k| k*k (k*k)í Vyj déme-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 r = 11 b 11 .| Tyto tři vektory doprovodné trojice t,n a b jsou navzájem kolmé a tedy generují celý prostor. Můžeme tedy 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í tvrzení: Věta 2.5 O ortonormálním repéru. Předpokládejme, že pomoci vektorových funkcí mi = mi(í), m2 = m2(ť), m3 = m3(í), t E J 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES jsou pro každé t E J definovány tři jednotkové navzájem kolmé vektory (o nich říkáme, že tvoři tzv. ortonormální repérj. Vypočteme funkce mp mi (ŕ), m2= m2 (ŕ), m3= m3 (ŕ), t E J a zapišme je jako lineárni kombinace funkcimi, m2, m3 mi = aiimi+ai2m2+ai3m3, m2 = a2imi+a22m2+a23m3, m3 = a3imi+a32m2+a33m3, kde ciij jsou reálné funkce definované na intervalu J. Potom matice koeficientů ciij je pro každé t E J antisymetrická, tj. má tvar (0 aí2 «i3 \ «2i 0 a23 . «31 «32 0 J Důkaz. Připomeňme, že pro každé t E J tvoří hodnoty vektorových funkcí mi, m2, m3 bázi vektorového zaměření prostoru R3, a tedy výše uvedené vyjádření existuje a je jednoznačné. Ukážeme, že au = 0. Evidentně, mi • mi = cín mi • mi = 1 2mi • mi = 0. Zejména tedy au = 0. Analogicky, a22 = 0, a33 = 0. Ukážeme, že ai2 = —a2i- Platí, mi • m2 = «12, m2 • mi = a2\. Zřejmě mi • m2 = 0. Derivováním zjistíme, že riii • m2 + m2 • mi = 0. Odtud již plyne, že au = —«21- Obecně platí a^ = —a^. I 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. t = k ■ n ň = —k ■ t +r • b b = —r•n , kde t je normovaný tečný vektor, n je normovaný normálový vektor, b je normovaný binormálový vektor, k je křivost a r torze. Důkaz. Víme, žet = K-nažeb = —r n. Zbývající část plyne z předchozí věty. I 74 KAPITOLA 3. KRITÉRIA KVALITY 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ě popsána: Věta 2.7 Hlavní věta teorie křivek Zadáním funkci k a r je prostorová křivka určena jednoznačně až na shodnost a lze ji vypočíst jakožto řešeni Frenetových diferenciálních rovnic. Důkaz. Viz diferenciální geometrie. I 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 = {~-Ty, ľ x)) • při explicitním vyjádření y = f (x): t =(!,/'), • 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 = (Fx,Fy), • při explicitním vyjádření y = f (x): t = (-/', 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 x(t+Ať)-x(t) Aí y(t+Ať)-y(t) Aí 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 (ť), y = y (ť) tak, že F (x (ť), y (ť)) = 0 a následně derivováním Fxx'(t) + Fyy'{t) = 0, je tedy (Fx, Fy) vektor kolmý na tečný vektor (x',y').\ 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIE75 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 dotyku: Dvojnásobný bod křivky, se shodným tečným vektorem. 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: = 0, 1 XX A xy F x: 1 yx 1 yy Fy "x Fy 0 • při explicitním vyjádření y = f (x): f" = o, • při parametrickém vyjádření x = x{t), y = y (t) : x y x" y" 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. I 76 KAPITOLA 3. KRITÉRIA KVALITY 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 boáě p = (x*,y*,z*): • při implicitním vyjááření F(x,y) = 0, x = (x, y, z) : VF(p).(x-p):=(^(p),F,(p),F,(p)). I y-y* | = 0, n z - z* • při explicitním vyjááření z = f (x, y): • při parametrickém vyjááření p = f(u,v), x = (x,y,z): |x-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 (C R) do parametrického oboru plochy (C R2). Zkoumejme tečny takovýchto křivek. V případě implicitně zadaných ploch máme F(k(r)) = 0^ VF • k' = 0. Gradient VF 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í fu(u*,v*) a fv(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 danou podmínkou pro determinant. I Věta 2.11 Výpočet normálových vektorů • Normála při implicitním vyjááření F(x, y, z) = 0 : n = VF=(Fx,Fy,Fz), • normála při explicitním vyjááření z = f(x,y): n= (fx,fy,-l), 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES normála při parametrickém vyjádřením. = f(u,v) = (x(u,v),y(u,v),z(u,v)): n *u X tv Vu Zu %u Zu %u Vu Vv Zv i Xv Zv i Xv Vv Důkaz. Cvičení. I 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 : R2 —► R3 a část křivky k : [a, b] —► R2, tzn. zobrazení parametrického oboru plochy k(í) = (u(t),v(t)), u,v : [a, b] —► R. Délka části křivky (k(í)), t E [a, b] zadaného jako « = fZHWMdt = £\\fu-u' + fv-v'\\dt = £ Vfu * f« • u'2 + 2ÍU *fv-u>-v> + fv*fv- v'2dt. Pro nekonečně malou část ds pak platí ds2 = fu * fu • du2 + 2íu * ív ■ du ■ dv + fv * fv ■ dv2 Pravá strana rovnosti se nazývá první základní forma plochy. Definice. První základní forma (IFF): 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 R4 —► R, kde (u, v, du, dv) i—► E ■ du2 + 2F • dudv + G ■ dv2, s metrickými koeficienty E F G Například pro kouli t« * t« I« * Id In * In •ť u ' y u ' zu, XUXV ~t~ yuyv i ZUZV, Xv ' V v ' Zv ■ r srn u • cos v í{u,v) = ( r sin u • sin v r cos u platí E = rz,F = Q,G = r-únzu. Věta 2.12 Délka oblouku Buď dána plocha í{u,v). Pro diferenciál oblouku ds křivky na této ploše ve směrech du, dv platí ds2 = E ■ du2 + 2F • dudv + G ■ dv2. Důkaz. Standardní tvrzení diferenciální geometrie. I 78 KAPITOLA 3. KRITÉRIA KVALITY 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 í{u,v) plocha v parametrickém vyjádření, Uf(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 křivost plošné křivky, k ■ nk = J^ä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. n/fu = {la x lu)/\\{la x Q\\ ■ fu = 0, nffy = (fu x fv)/\\(fu x f;)11 • f; = o, Aplikuj eme-li obdržíme pak kcos$ = K-nfnk = ^ nf í(u(s), v (s)) = nf • {íuu u +2íuv uv +ívv v +íuu u +ívv v) = nffMít u +2nff^ uv +nfívv v . Násobením ds2 získáme k ■ nfnk(is2 = nffj^ u du2 + 2nffut) uv dudv + nff^ v dv2. Výraz na pravé straně ( rovněž funkce u, v, du, dv) je tzv. druhá základni forma plochy: Definice. Druhá základní forma (2FF): Pro plochu s parametrickým vyjádřením f(u,v) je druhá základni forma funkce R4^Rs (ti, v, du, dv) i—► L ■ du2 + 2 • M ■ dudv + iV • dv2, přičemž metrické koeficienty L, M, N jsou definovány následovně: L M N nf, nf, nf um ■UV] Přitom n je normála plochy {íu x f^)/||(fu x fj, 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES Věta 2.13 Geometrická interpretace druhé základní formy Druhá základní forma určuje odchylku dh sousedních bodů plochy í{u + du,v + dv) od tečné roviny v bodě roviny f(u,v): dh= -2FF+o(du2 + dv2). 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 • íuudu2 + 2íuvdudv + fvvdv2. Provedeme-li Taylorův rozvoj f v bodě (u,v), obdržíme i(u + du, v + dv) = f(u, v) + {íudu + ívdv) +\{íuudu2 + 2iuvdudv + ívvdv2) +o(du2 + dv2). Protože máme níu = 0 = n£„ a dh = n • (i{u + du, v + dv) — f(u,v)), obdržíme bezprostředně dokazované tvrzení. I Věta 2.14 Výpočet druhé fundamentální formy Buď f(tt, v) = (x(u,v), y(u,v), z(u,v)). Pak platí L M N Veg- -F2 í Veg- -F2 í Veg-f2 Xuu yuu Zv/a Xu Vu Zu Xv Vv Zv %uv Vuv Zuv %u Vu Zu Xv Vv Zv Xvv yvv Zvv Xu Vu Z"a Xv Vv Zv 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 = ||fM x f,|| = {íu * Q • (f, * f.) - % * f.) • % * f.) = EG- F2. | 80 KAPITOLA 3. KRITÉRIA KVALITY 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 - Fre-netový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í fu, í„ a vnější normály n = íu x ftf/llfu x f^H, 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 t-u-u = i UM* ' L íi^ ' Curi , luv = r12fít + r12fü + ci2n*, fvv = r22f.u + r22f„ + c22w, kde rf-, 1 < i, j, k < 2 jsou Christoffelovy symboly druhého stupně Ylu = (EuG-2FFu + EvF)/(2g), T\2 = (EvG-FGu)/(2g), r22 = (-FGv + 2FvG-GGu)/(2g), r1 - r1 1 21 — L 12' T2n = {EuF-2FFu + EEv)/{2g), Y\2 = (EGu-EuF)/(2g), T222 = (EGu-2FFv + FGu)/(2g), r2 - r2 1 21 — L 12' pricemz g = EG - F , en = L, c12 = L, c22 = N. Důkaz. Viz diferenciální geometrie. I Připomeňme, že při vhodné indexaci jsou Christoffelovy symboly prvního stupně Tijtk skalární součin druhé a první derivace, např. T^i = fuv * f«- 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* = rif^ + raf^ + rsn*, n* = Sifu + s2fv + s3n*, Ku P n = (FM-GL)/g, r2 = (FL-EM)/g, r3 = 0, si = (FN-GM)/g, s2 = (FM - EN)/g, s3 = 0 ag = EG-F2. 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES 1 Důkaz. Viz diferenciální geometrie. I 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 '-v/av '-v/wa "• '-vva '-v/uv Dosadíme-li do Gaussových formulí, obdržíme dvě vektorové rovnice o proměnných fmt, fuv, f™, nu, n-v Aplikujeme-li Gaussovy a Weingartenovy formule, získáme dvě vektorové rovnice o proměnných fu, fc, nz trojhranu plochy, alkfu + a2iSu + cü3fcn* = 0, aikR, k E {1,2}. Z lineární nezávislosti vektorů trojhranu plochy obdržíme Cüjfc = 0, 1 < i < 3, 1 < k < 2. Dostaneme pak následujících šest podmínek: Věta 2.17 Gaussovy rovnice Platí an=o ^ F-b/g = (^„-(rh^ + rkna-rhrk, «12=0 <*=► -E-b/g = (a-ía + M-rp + M-rj^, cü2i=o -<=>- G-b/g = (r22)« — (r12)t, + r12(r22 — r12) — r12r22 + rnr22, a22=0 ^ F-b/g = (r222)u-(r22)v + r\2r22-rl22r2n, kdeg = EG- F2 ab = LN- M2. Důkaz. Viz diferenciální geometrie.l Věta 2.18 Mainardi-Codazziho rovnice Platí a13 = 0 ^ Lv-Mu = Y\2L + (T22 - Y\X)M - T2nN, «23 = o ^ mv-nu = t122l + (t222-t\2)m-t22n. Důkaz. Viz diferenciální geometrie.l Můžeme pak formulovat hlavní větu teorie ploch: Věta 2.19 Hlavní věta teorie ploch - Bonnet Buďte dány tří reálné funkce E, F,G s druhými spojitými derivacemi definované na nějakém okolí v R2 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 — F2 > 0, existuje až na shodnost jednoznačně určená část plochy, která má třetí spojité derivace, tak, že E, F,G,L, M,N jsou koeficienty obou základních forem. Důkaz. Viz diferenciální geometrie.l 82 KAPITOLA 3. KRITÉRIA KVALITY 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 k rovinných křivek 2FF 2FF KCOS$ = ^ = lFF- Pro křivky na ploše, jejichž vektor křivosti je rovnoběžný s normálou plochy ($ = 0), je pak křivost rovna __ 2FF ""iff' Tato křivost se nazývá normálová křivost plochy. Ta závisí pouze na směru tečny, definované pomocí ^. 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 p = pcos$,p = =. Protože střed oskulační kružnice křivky na ploše obdržíme ze vztahu f+pnk, máme pak, že oskulační kružnice na kouli má střed f+prif, a poloměr p- 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řeáem f + prij, a poloměrem p = jpp- Důkaz. Viz diferenciální geometrie.l Protože normálová 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 rif s plochou. Její vektor křivosti ukazuje ve směru normál plochy. Pro křivost Ti platí k - 2FF K - IFF = L ■ du2 + 2 • M ■ dudv + N ■ dv2 E ■ du2 + 2F ■ dudv + G ■ dv2 L- u +2 • M- uv +N- v2 E- u +2F- uv +G- v2 2. METODY ANALÝZY PROSTŘEDNICTVÍM DIFERENCIÁLNÍ GEOMETRIES Abychom mohli zjistit normálovou křivost, provedeme parciální derivace podle ii a v: ? = 0 ^^ (L-kE)u+(M-kF) v = 0, ? = 0 ^^ (M-7íF)tí+(Ař-7íG) ú = 0. Protože však k závisí pouze na směru u / v, extrém nastává i pro A • (u,v), pokud nastává v bodě (u,v). Výše uvedená lineární rovnice nemá tedy jediné řešení, tj. L - k E M-HF M-HF N-kG 0. Definice. Gaussova křivost K je určena vztahem L-N -M2 K := E ■ G - F2 ' Střední křivost H je určena vztahem _ -2 • F ■ M + (E ■ N + G ■ L) :~ 2 • (E ■ G - F2) ' Pak lze poslední podmínku z 2.20 zapsat jako K2-2-H-K + K = 0. Diskriminant této kvadratické rovnice je vždy větší nebo roven nule. Rovnice má vždy dva různé nebo jeden dvojnásobný 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. hlavni křivosti, extrémy normálové křivosti k, jsou určeny vztahem Kmax ■= H + \JE2 - K, Kmin := H - \JE2 - K. 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 nmax resp. n,mini se nazývají čáry křivosti. Cáry křivosti pro nmax resp. Kmin tvoří dva systémy ortogonálních plošných křivek. 84 KAPITOLA 3. KRITÉRIA KVALITY Kapitola 4 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 Splínové 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í splíny: Definice. Polynomiální splinová funkce: Buďte x0 < X\ < ■ ■ ■ < Xk, Xí E R. Funkce S se nazývá splinová funkce stupně d E 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í,Xí+i], 0 < i < k. 2. SeC(d-V[x0,xk]. 85 86 KAPITOLA 4. METODA B-SPLINŮ Vektor £ := (x0, xí}..., 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™ nahradí speciálními B-spline funkcemi N™1. Definice. Buď £ = (xo,X\,... ,Xk) uzlový vektor. B-spline funkce je definována jako N?(x) := j J V™jt:e[xi,xi+1), i = 0)_)k_h N?(x) := rX - %. ■ Nr\x) + T^+"+1 ~ X 1 • N^ix), 1 v ' %i+n — Xi % v ' Xi+n+1 — Xl+\ %+í y ' 0 < i < k - n - 1,1 < n < k - 1,^ := 0. Od komponent uzlového vektoru je požadována pouze monotonie, nikoliv silná monotonie. Pro případ, že Xi+n — Xi = 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(x) = 0 N°(x) = 0 ív2°(x) = (1' XG[0'1} 10, jinak ivj(x) = í1' ;r€|1'2) 10, jinak ^ Ji. «[2,3) 10, jinak můj1-xei3A) I 0, jinak N°6(x) = 0 N°(x) = 0 1. SPLÍNOVÉ A B-SPLINOVÉ funkce 87 N*(x) = Nl(x) = Nl2{x) = Nl3(x) = Nl(x) = Nl5(x) = N16(x) = N2(x) = Nl{x) = X Xq o .N»(x) X\ — Xo ^—^.N^x) X2 — X\ ^—^-.N^(x) X3 - X2 X2 X Q .N\{x) = 0 X2 — X\ ^^-.N°(x) X3 - X2 ^^.N°3(x) X4 — x 3 1- -x, x G [0, 1) 0, jinak X, x G [0, 1) 2- -x, x e [1,2) 0, jinak X X3-.N°3(x) + ^-^-.N°(x) X4 — X% X5 *-í'4 X X4-.N°4(x) + ^-^.N°5(x) X§ Jb^. ^^^.N°5(x) Xq X5 Xq X5 1, x G [1,2) xe [2,3) jinak x G [2,3) xe [3,4) jinak x G [3,4) jinak ^—^.N°(x) + ^—í-.JV°(:z) Xj — Xß Xg — Xj ^—^.N^x) + ^—^.Nl(x) X2 — Xo X3 — X\ X Xl-.Nl(x) + ^—^-.N\{x) = 0 N22(x) N23(x) = X3 — X\ X X2 ,j\, s X4 — X2 X4 — X2 ^^.Nl{x) x5 -x3 (1-x)2, a; G [0,1) 0, jinak x(l — x) + \x{2 — x) -- \{2 - x){2 - x) = \{2 - xf 0, 3 2 2 ( 1 IT2 2 ' 2x, XG [0,1) xe [1,2) jinak |x(2-x) + §(x- l)(3-x) |(3-x)(3-x) = §(3-x)2, -x 3x 3 2' X G [O, 1) xe [1,2) xg [2,3) jinak £5 -x3 .^(x) + >Áj Q lAj Xß — X4 ■ N\{x) 1'\{x - l)(x - 1) = \{x - l)2, ±(x - 1)(3 -x) + \{A - x)(x - 2) = -x2 + 5x |(4-x)(4-x) = |(4-x)2, 11 2 ' ,0, XG [1,2) xe [2,3) xg [3,4) jinak 88 KAPITOLA 4. METODA B-SPLINŮ Nl(x) x X4 ■ Nl(x) Xj x .N&x) Xß — X4 Xj — X5 \{x - 2) {x - 2) = \(x - 2)2, \{x - 2)(4 - x) + (4 - x)(x - 3) = O, 3 2 2 lOz- 16, x G [2,3) x G [3,4) jinak iV52(x) x - - x5 Xj - - x5 x - - x0 ■Nfa) + X8 X3 — Xq .N2(x) x8 -X4 'iN^=\t3)2' x X 4 X \ .N2(x) 7-3 x(l - x)2 + \{2 - x)(|x2 + 2x) = jx" ^-2x + 2) = -\x3 + \x2 9-2 = { \(2-x)(^-2x + 2) = 2 3x x x e [3,4) jinak ÖX « X G [O, 1) x G [1,2) jinak JVfOr) = ^1 A7-2/ \ , ^5 x 4 x 2 -.iVí (x) + X X5 - X2 ■N22{x) q l r\X ~p LíXj \~ o 10 X i r\X x í x 1-3 6x 11 r3 12"° 3-2 2 ' 3^ 2V2 2x + 2) + |(3-x)(-x2 + 3x 2 |(3-x)(f-3x + |)- ^3 ' 3-2 9 O, 3 2 2X X XT3 12 ^ 9 " 2' 3x2 tX 2' X G [O, 1) X G [1,2) x G [2,3) jinak iV|(x) = x £5 - £2 ' 1 12 _ T1 — o^ ■N2(x) + X Xß X 3 .N2(x) 1-3 6 ' |x(-x2 + 3x - f) + |(4 - £)(%- - x + i) = "^X^-^- óX ~r xj "r- "š v ^) v *^ "^ ~2~; |(4 - x)(4 - 4x + 8) = -|x3 + 2x2 - 8x -O, 2 2 2x2 ix2 2x^ lOz 2 3' 22 3 ' 32 3 ' X G [0,1) X G [1,2) x G [2,3) x G [3,4) jinak ^) = S-^) + ^-4-N2(x) Hx-i)(- X+ -) - u, u, , x -r 2; 6 2 ' 2 n) + |(4-x)(f 1^.3 gX 1^.2 2X 3^ "A " 3 !|(x - 1)(4 - 4x + 8) + |(4 - x)(-|x2 O, x w|(*) a;—a?4 2:7—1E4 " •^IW + ÍT.ÍV62(X) 1 6' 2x + 2) = - ___Z_o~3 -1- 4t^ __ —T -1- — lOx- - 16) : - 11^.3 _ 19 2 , 09- _ 104 x e [1,2) x G [2,3) x G [3,4) jinak |(x-2)(^-2x + 2) 1^.3 4x 3-2 2 3x-2, {|(x - 2)(-§x-2 + lOz - 16) + (4 - x)(x2 -6x + 9) O, 1^.3 4x 33-2 2 x x G [2,3) 51a;+ 52, x G [3,4) jinak 1. SPLÍNOVÉ A B-SPLINOVE funkce 89 Pro uzlový vektor sestávající ze dvou hodnot, 0 a 1, jež mají stejný počet výskytů, tj. r=(0,0,...,0,l,l,...,l), 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ýnii polynomy: N? = B?. Pro n = 2 platí N°(x) N%(x) N°s(x) N°(x) N* {x) Nl(x) N}(x) Nl3(x) N* {x) N? (x) N! (x) = 0 1, x e [0,1) 0, jinak = 0 1 -x, x G [0,1) 0, jinak x, x E [0,1) 0, jinak (l-x)2, x e [0,1) 0, jinak 22ľ-(l-2ľ) x G [0,1) 0, jinak x2, x G [0,1) 0, jinak 90 KAPITOLA 4. METODA B-SPLINŮ Věta 1.1 Vlastnosti B-spline funkcí 1. Nosné intervaly: Nosný interval N™ je [xi,Xi+n+\), tj. N™(x) = 0 pro x g [xi}xi+n+i). 2. Rozklad jednotky: Součet B-spline funkci stupne n je 1: k—n—l y N™ (x) = 1, x E [xn,Xk-n),pokud k — n — 1 > 0. í=0 3. Pozitivita: B-spline funkce jsou v intervalu [xi,Xi+n+\) nezáporné: Niix) >0,0 n \(n- j) ■ (a?-1} - a£^)/(xt+n_3 - Xi) j > 0, * " U' (i) a_[ = 0 pro j > 0. Důkaz. Snadné cvičení. Dokažme například: 1. Nosné intervaly: Důkaz provedeme matematickou indukcí. i) pro n = 0 platí: N°(r) = ) X ^ \XiiXi+l) 0 jinak. Takže ihned vidíme, že pro x ^ [xí,xi+n+i) je N™ (x) = 0 ii) Předpokládáme, že tvrzení platí pro n — 1, a dokážeme, že platí pro n. Vime, že: 2. B-SPLINE KRIVKY 91 N™ 1(x) = O pro x g [xi,xi+n) a N'^{x) = 0 pro x g [xi+i,xi+n+i). Tedy N?(x) = Tx - x\ ■ N?-1 {x) + rXt+n+l ~X ■ N?-?{x) = 0 + 0 = 0 % v ' %i+n — Xí * ^ > Xi+n+1 — Xi+1 %+í v ' pro X f: [Xi, Xi+n+i). 3. Pozitivita: Důkaz opět provedeme matematickou indukcí, i) pro n = 0 platí: Q/s.J 1 £ G [Xi, Xi-\-l) 1 ^ ' ~ "• 0 jinak. Pro x ležící v daném intervalu tedy tvrzení platí. ii) Předpokládáme, že tvrzení platí pro n — 1, a dokážeme, že platí pro n. Víme, že: N™~l(x) > 0 pro x G [xi,xi+n) a N'^{x) > 0 pro x G [xí+i,xí+ra+i). Tedy ^?(*) = XX+~-X- ■ K'1^) + xS'ľľ-^^l • ^"l1^) ^ 0 Pr° X e [^'^+n+l)- ' 2 B-spline křivky B-spline křivky se formálně reprezentují podobně jako Bezierovy 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 m b(í) := ^diiVr(í), t G [ío, Wi], dt G Rd, í=0 kde N™(t) jsou B-spline funkce příslušející k uzlovému vektoru tvaru r = (ío, • • •, tn+m+i), ío = • • • = tn, tm+i = ■ ■ ■ = tn+m+i a kontrolními body d» G Rd. Uzavřená B-spline křivka má tvar b(í) := J]dJV"(í), í G [ío,Wi], d, G Rd í=0 92 KAPITOLA 4. METODA B-SPLINU kde N™{t) jsou B-spline funkce příslušející k uzlovému vektoru tvaru r = (í0, • • •, tn^ tm+2 ■= Wi + (*i — *o), • • • , tn+m+i ■= tn+m + (tn - ín_i), a kontrolními body d, G Rd. Kontrolní body dj G Rd se rovněž nazývají de Boorovy body. Spojení de Boo-rových bodů se nazývá de Boorův polygoniální tah. Věta 2.1 Vlastnosti B-spline křivek 1. Chováni 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. Vlastnost konvexního obalu: B-spline křivka leží v konvexním obalu de Bo-orových bodů. Zejména tedy leží i v konvexním obalu de Boorova poly-goniálního tahu. 3. 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- Lokálnost: Změna jednoho kontrolního bodu změní křivku nejvýše lokálně, tj. při změně kontrolního bodu dj se změní b(í) pouze pro t G [íí,íí+ri+i)- 5. 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. Čá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 bodů. Stejně jako pro Bernsteinovy polynomy je nenulová hodnota nabývána pouze prvním a posledním v koncích intervalů. Vlastnost 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 bodu křivky b (ŕ) 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. I Algoritmus, (de Boor) Vstup: m + 1 kontrolních bodů d0, di,... , dm, spline stupeň n, uzlový vektor r pro otevřenou (uzavřenou) B-spline křivku, parametrická hodnota ť G [to,tm+i\. 2. B-SPLINE KŘIVKY 93 Výstup: Bod křivky b(í*). Postup pro otevřené B-spline křivky BEGIN vypočtěte index i tak, že ti < ť < ti+i, 0 < i < m FOR j := 0 TO n DO FOR/ :=i-n + jTOiDO IF j = 0 THEN tf := di ELSE BEGIN tf ■= (ť - ti)/(ti+n+i_j - U); df:=(l-ť?'). dřJ+í?.df-1; END; b(ť) := d?; END. Postup pro uzavřené B-spline křivky BEGIN vypočtěte index i tak, že ti < ť < ti+i, 0 < i < m FOR j := 0 TO n DO BEGIN / := i — n + j — 1; REPEAT IF / < 0 THEN BEGIN / := / + m + 1; ť := ť - t0 + Wi; END; ELSE IF / > m + 1 THEN 94 KAPITOLA 4. METODA B-SPLINŮ BEGIN / := / - m - 1; ť := ť + t0 - tm+1; END; IF j = O THEN d? := dt ELSE BEGIN t\ := (ť - ti)/{ti+n+i-j - ti); dj := (1 - tj) ■ dJ^)mod(m+1) + tj ■ df1; END; UNTIL / = i; END; b(ť) := d"; END. Časová náročnost de Boorova algoritmu je 0(n2 + 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žné 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ícím způsobem zvýšit počet kontrolních bodů, doplníme nejprve uzlový vektor o r-násobný uzel ť. Buďte ti, ti+\ uzly, mezi které vsuneme t*. Použitím pomocných bodů dj, jež vzniknou provedením de Boorova algoritmu pro hodnotu t = t*, obdržíme nový kontrolní polygon nahrazením dílčího kontrolního polygonu di-n, di_n+i,... , di starého kontrolního polygonu dílčím polygonem r\ — r\° A1 Ar Ar r\° U-l-n — ^l-ni už-ra+H • • • ) už-ra+r' • • • ) už ) • • • ) už • Věta 2.2 Vložení kontrolních bodů v B-spline křivkách Buď t = (t0,... ,tn+m+i) uzlový vektor nějaké B-spline křivky, ť E [ti,ti+i), d0,..., dm kontrolní de Boorovy body B-spline křivky b (ŕ). Buď ť = (t0,..., tn+m+r+i), r < n definován jako 3 — tj, 3 = 0,. .,/, 1+3 = ť, J = h- ■,r, l+j+r = tl+j, J = h- . ,n + m l + l, 3. B-SPLINE PLOCHY 95 a kontrolní de Boorovy body d0, di,..., dm+r jakožto d, = dj, J = o,. . ,1 — n - 1 dl-n+j - dJ 3 = o,. -,r, *-*l—n-\-r-\-j dr 3 = 1,- . ,n — r, d|+i - dr_i 3 = 1,- -,r, dl+r+j = dW 3 = 1,- . ,m — l. Pak splývá B-spline křivka h (t) pro uzlový vektor r se zadanou křivkou b(í). Důkaz. Cvičení. I 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 0(rn + ni). 3 B-spline plochy Techniku B-splinů lze stejnou konstrukcí jako u čtyřúhelníkových Bezierových segmentů rozšířit na plochy. Definice. Zadáno: Kontrolní de Boorova síť čtyřúhelníkové B-spline plochy je určena (k +1) • (/ +1) de Boorovými kontrolními body ditj E R3, i = 0,..., k, j = 0,..., /, stupně man, uzlové vektory ß = (u0,..., tw+fc+i), v = (v0,..., vn+i+i), jež splňují stejná kriteria jako pro otevřené nebo uzavřené křivky. B-spline plocha v R3 je tvaru: x(u,v) := ^^dí;i • N™{u) ■ N™(v), u,v E [u0,um+i) x [v0,vn+i). i=0 j=0 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á (fc+ 1) • (/ + 1) de Boorovými kontrolními body ditj E R3, i = 0,..., k, j = 0,..., /, stupni man, uzlovými vektory ß = (u0,... ,um+k+i), v = (v0,..., i>n+z+i) a parametrické hodnoty u* a v*. Výstup: bod plochy x.(u*,v*). Postup: 96 KAPITOLA 4. METODA B-SPLINŮ 1. Vypočtěte ď,- := J2i=0 ditj ■ N™(u*) podle de Boorova algoritmu pro křivky, j =p-n,...,'p,vp]d„.iV» í=0 j=0 2. Lokálnost: Zména jednoho kontrolního de Boorova bodu ditj změní plochu nejvýše lokálně, tj. při změně kontrolního bodu ditj se změní x.(u,v) pouze pro (u,v) E [ui,i+m+i) x [vj,j+n+i). Zejména tedy část plochy parametrizo-vatelná (u,v) E [ui,i+m+i) x [vj,j+n+\) je ovlivnitelná pouze kontrolními de Boorovými body dí_mj_ra; ...; did. 3. 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- 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. I 4 B-spline metoda a Bezierova metoda Křivka, která je po částech složená z Bezierových segmentů, se označuje jako Bezierova křivka. Bezierovy segmenty si přitom vhodně přeparametrizujeme, abychom obdrželi jednotně průchozí parametrický interval výsledné křivky. Změna parametrizace nezmění nic na vlastnostech Bezierových segmentů. Při použití Cas-teljauova algoritmu se namísto s poměrem t : (1 — t) pracuje s poměrem t-tk _l-(t-tk) tk+i — t k ífc+i — ífc 4. B-SPLINE METODA A BÉZIEROVA METODA 97 Definice. Zadáno: Kontrolní body b^ G Rd, k = 0,..., m, i = 0,..., n, uzlový vektor r = (í0)- • • ,tm+i). Bézierova křivka Rd je tvaru: n t-t b(u) :=Jlbk>i-B?{-------k—), t E [tk,tk+1),k = 0,...,m iťo tk+l - tk 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 Bezierovy křivkové segmenty, lze B-spline křivky vyjádřit jakožto Bezierovy 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 m b(í) := ^diiVr(í), t G [ío, Wii d, G Rd, í=0 s uzlovým vektorem tvaru r = (t0,... ,tn+m+i), t0 = ■ ■ ■ = tn, tm+\ = ■ ■ ■ = tn+m+i- Buď Ť uzlový vektor, který vznikne vložením uzlů tak, že každý uzel má násobnost n + 1, tj. ř = (t0,... ,t{m-n+2){n+\)-i), kde 3 tj, 3 = = o,. .,n, l(n+l)+j = tn+l i 1 = = !,-• . ,m - -n,j = = 0,.. .,n, (m—ti+1)(ti+1)+j tm+j+j i 3 = = o,. .,n, Dále buďte dj G Rd, 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 bfc,i := dfc(n+i)+j, k=l,...,m-n,i = 0,...,n. Pak platí n t-t b(ť) := ^bM • B™(----------^------), t G [tn+k,tn+k+i],k = 0,...,m-n, tj. každou B-spline křivku lze vyjádřit jakožto Bézierovu křivku. Důkaz. V důkazu využijeme toho, že Bernsteinovy polynomy jsou reprezentova-telné 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 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 Bezierovy křivky. | 98 KAPITOLA 4. METODA B-SPLINŮ Algoritmicky lze transformaci provést použitím de Boorova algoritmu. Algoritmus na reprezentaci B-spline křivky jakožto Bezierovy křivky plyne bezprostředně z předchozí věty. Rozklad B-spline křivky na Bezierovy 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. Bezierovy body navzájem proti sobě působících křivkových segmentů nejsou proto nezávislé. Pro Cp-přechod lze tuto souvislost vyjádřit následovně: Věta 4.2 Cp-přechod mezi Bézierovými segmenty Bézierova křivka n t — tk b(í) := yVi • ß?(-------k—), t e [tk,tk+l],k = 0,...,m iťo tk+l - tk je právě tehdy p-krát spojitě diferencovatelná, když platí (tk+i — tk)~rArbktn_r = (tk+2-tk+i)~rArbktn-r, r = 0,...,m, přičemž klademe A°bM := bk>i, AJbM := A^bfc.i+i-A^bfc.i, j>l. Důkaz. Tvrzení plyne bezprostředně z věty o reprezentaci derivací Bézierových křivkových segmentů v druhé kapitole. I Jsou-li Bezierovy body fc-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 = (tk+2 — ífc+i)/(ífc+i — tk). Bezierovy 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 Boo-rovy body odpovídají Bézierovým bodům. Při derivaci vyššího řádu lze zadat úspornější reprezentaci Bezierovy křivky jakožto B-spline křivky. Pro kubické Bezierovy křivky platí: Věta 4.3 (Transformace kubických Bézierových křivek do B-spline vyjádření) Buď 3 t-t b(í) = J>M • 5?(-------k-), t E [tk,tk+1],k = 0, kubická C2-Bézierova křivka. Pak splývají de Boorovy body do := bo,o, di := b0,i, dj+i := bj_i)2 + ^ -t-J) ' (k-7-1-2 ~ bJ-1-1) = hjt2 + §J^y • (bJ;i - bj>2), j = 1, • • •, m, dm+2 := bTO;2, dm+3 := bTO;3, ,m 5. RACIONÁLNI B-SPLINE METODA (NURBS) 99 s Bézierovou křivkou pro danou kubickou B-spline křivku s uzlovým vektorem ř := (ío, *i, - - - ,tm+7,), kde t_3+j Důkaz. Cvičení. I 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 Cp-přechodu lze pro čtyřúhelníkové Bézierovy plošné části redukovat na požadavek pro Cp-přechod mezi Bézierovými segmenty: Věta 4.4 Cp-přechod mezi čtyřúhelníkovými Bézierovými segmenty Nechť je dána část plochy příslušející k bij, i = —n,..., 0; j = 0,..., m parametrizovaná přes [uo,u\] x [^c^i] a část plochy příslušející k bij, i = 0,...,n, j = 0,..., m parametrizovaná přes [1/1,1/2] x [vo, v\] tak, že obě jsou složeny podél parametru u = u\. 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 bij*,i = -n,...,0, a bij*, i = 0,...,n, vykazují Cp-přechod pro u = u\, j* = 0,..., m. Důkaz. Využitím odpovídajících tvrzení pro Bézierovy křivkové segmenty. I 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: = lQ, J = V,...,Ó, = tj, j = 0,...,m, = í„,_i_i. 7 = 0.....3. 100 KAPITOLA 4. METODA B-SPLINŮ Definice. Zadáno: m + 1 kontrolních bodů d0, d1;..., dm G R3, (m + 1) vah 8i > 0, i = 0,... ,m, spline stupeň n, uzlový vektor r = (í0, í i, • • • ,tn+m+i) Pro otevřenou (uzavřenou) B-spline křivku. Racionální B-spline křivka (NURBS-křivka): má tvar b(í)-"T^w(*r' lo'WlJ' 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» lze uvažovat jako perspektivní projekci vzhledem k počátku na rovinu Xd = 1 obyčejné B-spline křivky k d + 1-dimenzionálním de Boorovým bodům í * Věta 5.1 Vlastnosti racionálních B-spline křivek 1. Lokálnost: Změna jednoho kontrolního bodu zrněni křivku nejvýše lokálně, tj. při změně kontrolního bodu dj se změní b(í) pouze pro t G |ŕj,ŕj_|_m_|_i). 2. Vlastnost konvexního obalu: B-spline křivka b(í) Zeiz' v konvexním obalu de Boorových bodů dj. 3. 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- Výpočet křivkových bodů: Aplikací de Boorova algoritmu na projektivní tvar a následnou projekcí. Důkaz. Bezprostřední. I Rovněž u B-spline ploch s třídimenzionálními kontrolními body lze racionální formu važovat jako perspektivní projekci "obyčejného tvaru" se čtyřdimenzionálními kontrolními body: Definice. Zadáno: Uzlové vektory ß = (tt0, U\,... , tw+fc+i) Pro B-spline funkce iV™(tí) a v = (vo, v\,..., vn+i+\) pro B-spline funkce N"(u), (k + 1) • (/ + 1) bodů dij G R3, váhy Šij > 0, i = 0,..., k, j = 0,..., /, stupně man. Racionální B-spline plocha: má tvar b(í) := k ; ,(u,v) e [uo,uk+1) x [v0,vl+1). 6. PŘEHLED K B-SPLINE METODE 101 Platí: Věta 5.2 Vlastnosti racionálních B-spline ploch 1. Vlastnost konvexního obalu: B-spline plocha h(u,v) leží v konvexním obalu de Boorových bodů d^. 2. Výpočet bodů plochy: Aplikací de Boorova algoritmu na směr u- a v- v R4 a následnou projekcí. Důkaz. Analogicky jako u racionálních Bézierových segmentů a racionálních B-spline křivek. I 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™ jakožto transparentní stín simplexu v Rm+1v 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élce čá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 —► Rd, p (í) = 5^=0ajŕl, existuje jednoznačně určené symetrické multiafinní zobrazení p : Rra —► Rd tak, že p = p(í,...,í), totiž n , x -1 p(xi,... ,xn) = ^aj . j ai(xh... ,xn) kde (Ti(xi,..., xn) jsou elementární symetrické polynomy tvaru (Ji{xi,... ,xn) := ^2 xkl.....xki, i = 0,...,n. lťLr(*)> í=0 kde LT {x) jsou Lagrangeovy polynomy stupne m příslušející bodu U, i = 0,... ,m, interpoluje zadanou posloupnost bodů. Je jednoznačně určena, tzn. jediná polynomiální křivka s touto vlastností. Důkaz. p(í) je zřejmě polynomiální křivka stupně m. p(í) interpoluje zadanou posloupnost bodů, protože 1, i = 3, 0, i + 3 LT(t) = öt3 = \ Z \_,J: 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ě stupně m. Protože rozdíl má alespoň m+1 kořenů t0, ... , tm, je roven identicky 0, tj. odtud plyne jednoznačnost. I 1. INTERPOLACE S KRIVKAMI 105 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 x1 nebo Bernstei-nově bázi B™(x). Věta 1.2 Transformace Lagrangeova vyjádření do monomiálního vyjádření Buď p(x) := YľiLo Pi-^T(x) polynom v Lagrangeově reprezentaci, L™(x) jsou Lagrangeovy polynomy stupně m příslušející bodu Xi, i = 0,..., m. Pak je p(x) := / jj—q cl^x j h,ae ( a0 \ Cli \ am J í 1 x0 1 X\ x0 .Aj 1 V i xr. x. x0 „m '1 .Aj 1 \ _1 / PO \ Pi •Aj r J \Pm J Důkaz. Plyne bezprostředně z interpolační podmínky. | U křivek lze tuto transformaci aplikovat na každou souřadnici. Transformační matice v neinvertovaném tvaru se nazývá Vandermondova matice. Casteljauuv 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 (tj, p.,), tj E R, p^ G Rd, j = 0,..., m, tj < tj+\, parametrická hodnota ť E [to,tm]. Výstup: Bod křivky p(í*). BEGIN FOR i := 0 TO m DO p° := pi5 FOR j := 1 TO m DO FOR i := j TO m DO J-í , ť -t U-ť U -1 l-J J-1. I-J Jí-1 U - ť l-J P(ť) := p£; END. Časová náročnost Aitkenova algoritmu je 0{m2). Následující algoritmus podle Newtona má tu výhodu, že po předzpracovávající době 0{m2) lze spočítat bod křivky pro libovolnou hodnotu parametru v čase 0{m). 106 KAPITOLA 5. INTERPOLACE A APROXIMACE Algoritmus. (Newtonova polynomiální interpolace) Vstup: Opěrné body (tj, p.,), tj E R, p., E Rd, j = 0,..., m, tj < tj+\. Výstup: [m + 1) koeficientů p*, i = 0,... ,m, z kterých lze pro libovolnou parametrickou hodnotu ť E [to,tm] vypočíst bod křivky p(ť). Předzpracování: BEGIN FOR i := 0 TO m DO p° := pi5 FOR j := 1 TO m DO FOR i := j TO m DO ^=(pŽ_1-pÍí)/(*í-*<-'') END; Vyhodnocení: BEGIN FOR j := m - 1 TO 0 DO P^:= pgl • (í* - í;) + P£ P(0 := PŠ END. Vektory p^ 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 (xi,pi), i = 0,... ,m, Pí E R, p(x) = YľiLoPi^T odpovídající interpolační polynom. Dále buď f E Cn[xo,xn], f(xi) = Pi,i = 0,...,m, funkce s omezenou (n + ľ)-ní derivací: \fn+1(x)\ < M pro x E [x0,xn]. Pak platí M \f(x) -p{x)\ < ■ Kx-xo).....(x-xn)\. 1. INTERPOLACE S KRIVKAMI 107 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 / G [a, b] tak, že příslušná posloupnost {pn} polynomů nekonverguje stejnoměrně na [a, b] k /. Opačně lze však dosáhnout při vhodné volbě opěrných bodů stejnoměrnou konvergenci. Ke každé funkci / G C[a, b] existuje posloupnost opěrných bodů v intervalu [a, b] tak, že příslušná posloupnost {pn} interpolačních polynomů konverguje stejnoměrně na intervalu [a, b] k /. 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ů ti v opěrných bodech p^. Jednou možností je stejnoměrné rozdělení intervalu parametrů, tedy pro interval parametrů [0,1] pomocí hodnot ti = i/m, i = 0,... ,m. Nevýhodné na této volbě je, že části křivek se značně 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 pak obsahuje změny, které citem neodpovídají hladké interpolaci zadaných bodů. Vhodnější je parametrizace vzhledem k délce křivky. To lze odůvodnit tím, že ve vzorci ^/(k' * k') (k" * k") - (k' * k")2 (k'*k')f 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 *o = 0,U = —^zj---------------, i > 0. 2^=0 \\Pj+i-Pj\\ Na základě takto obdržené vhodnější interpolační křivky lze provést odhad vyššího řádu, abychom se iterativně ještě lépe přiblížili parametrizaci podle délky křivky. Další možností ovlá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 mist p0, p1;..., pm G Rd s derivacemi p'0, p[,..., p'm G Rd; parametr ti G R pro pi7 108 KAPITOLA 5. INTERPOLACE A APROXIMACE i=0, ..., m, ti < íj_|_i. Polynomiální krivka m p(t) = J>i4"(*) + PÍ£TO> í=0 kde Af{t) := (1-2- L?\U){t- U)) -LT(t)2, B?(t) := (t-U)-L?(t)2, L™(ť) jsou Lagrangeovy polynomy stupně m příslušející bodu ti, i = 0,..., m, interpoluje zadanou posloupnost bodů a derivací. Důkaz. Viz numerická matematika. I 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 A?{Xj) = 6t3, B?(Xj) = 0, A?'{Xj) = 0, B?(Xj) = ôij, 0 % ^cm + 2c,),í = 0, = 0,...,n- 1. Ara_2 2(Ara_2 + Ara_i) Ara_i 0 Ara_! 2(Ara_! + Ara) y ., n — 1. Důkaz. Z požadavku interpolace body (íi,Pj) a dvojité spojité diferencovatel-nosti přechodů v hraničních bodech ti obdržíme p Au) = Pi pAu) = Pi_i(íi) Pliti) = p'i^iu) pí'(íí) = Pi_i(í*) 1. INTERPOLACE S KRIVKAMI 111 Zejména tedy obdržíme a» = Pí(íí) = Pí- Koeficienty a^ lze tedy bezprostředně spočítat, koeficienty bj a dj lze určit jakožto funkci koeficientů Cj. Koeficienty Cj 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* = Pi-i + bi-i • A, + ct_! • A? + d,_! • A,3. Z derivuj eme-li pí; obdržíme b, = b,_! + 2ct_! • A, + 3d,_! • A?. Z derivuj eme-li p^ dvakrát, obdržíme 2cj = 2cí_i + 6dj_i • Aj, j __ Cj — Cj-i Uí-! — 3 A; ' tj. koeficienty dj závisí na koeficientech Cj. Máme tedy P^ = P^ + b^-A. + c^-Af + ^g^-A3. Výše uvedené lze psát jako U _ Pi+l~Pi ^i+i/r. , I %\ a tedy koeficienty bj závisí na koeficientech Cj. Podobně obdržíme bj-bj_i = Aj • (Cj_i + Cj). Dosadíme-li pak do této rovnice za b» a bj_i, obdržíme AiCi_i + 2(Ai + Ai+i)Ci + Ai+ici+i = 3^^ - 3Pí"P-1\ V posledním případě se jedná o systém d ■ (n + 1) lineárních rovnic o d • (n + 1) neznámých Co,... , cn. 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 Pó(*o) = PÓ, Pň-l(*n) = P'n první výše uvedený systém rovnic. V případě uzavřených spline-křivek plyne z Po(*o) = Pn(tn), Pó(*o) = Pn(tn), PÓ'(*o) = P^(ín) druhý výše uvedený systém rovnic. I 112 KAPITOLA 5. INTERPOLACE A APROXIMACE V obou případech je matice systému rovnic pro Cj 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í 0(n) na spotřebu 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 G C2[to,tn], jež splňují interpolační podmínku k(*j) = PjJ = 0,l,...,ra,k'(ío) = pó,k'(íra) = p'n, kubická spline-křivka minimalizuje hodnotu integrálu ík"(t)*k"(t)dt. ío Důkaz. Plyne bezprostředně zobecněním odpovídajícího tvrzení pro jednodimenzionální případ z numerické matematiky. I Tato minimalizační vlastnost se nazvývá "Minimum Norm Property". Při parametrizaci podle délky oblouku platí pro křivost k křivky K=v/k%k77. 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 splínovou interpolaci provést pro předem zadané hodnoty derivací: Definice. Buďte dáno 2(n+1) bodů Pj,p-G Rás hodnotami parametrů U G R, to < t\ < ■ ■ ■ < tn, i = 0,..., n. Interpolující hermiteovská splínová křivka: interpoluje body (ri,Pj,pí)> je otevřená nebo uzavřená spline-křivka 5. stupně, pro niž navíc platí otevřená hermiteovská splínová křivka: p"(ro) = 0,p"(rra) = 0, uzavřená hermiteovská splínová křivka: P(*o) = P(*n),p'(ío) = P'(ín), p"(to) = p"(tn),p'"(to) = p'"(tn). 1. INTERPOLACE S KRIVKAMI 113 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) hneárních rovnic s koeficienty jako proměnnými. Z požadavku spojitého přechodu první až čtvrté derivace ve vnitřních bodech dotyku t\,... ,tn-i 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ď Pl := a, + bi(í - U) + Ci(í - Uf + di(í - Uf + et(t - t%f + í%{t - U)5, t G [tt, íi+1], i-tý polynomiální křivkový segment interpolující hermiteovské spline-křivky p (ŕ), Aj := ti — tí-i, i = 1,... , n, Ara+1 = Ai. Pak platí: pro otevřené hermiteovské spline-křivky: 1. aj := pí; i = 0,1,... ,n. 2. bi :=p'i} i = 0,l,...,n. 3. Koeficienty c» získáme jako řešení lineárního systému rovnic c0 = cn = 0, C,; in f äj+l — d-i 3-j — Sj-l \ i /| f Pj-l 3/'A— 2 , A— 2\k Pj+l iU l A3, ~~ A3 j+4l A2 _2V^i+l + ^i JDí_A2 s Aj = íj - íj_i, z = 1,..., n - 1. ^ d, := 10aí+raí - 22b^+3bí + Ci+1r3Ci, ^ = 0, ■ ■ ■, n - 1. Ai+1 Ai+1 Ai+1 k p ._ bj+i-bj___Cj_ , diT1+5dz . _ n 1 /j f — ci+í-Ci 3dj______3ež • _ n _ i b- *»- 10a|+1 10a|+1 5Ai+1'z-u>-">n X- pro uzavřené hermiteovské spline-křivky: 1. a.i := pí; z = 0,1,... ,n, a„+i := ai. 2. bi := pí, z = 0,1,... , n, bn+x := bi. 3. Koeficienty Cj získáme jako řešení lineárního systému rovnic cn := c0)Cra+l := cl) 114 KAPITOLA 5. INTERPOLACE A APROXIMACE ^^(A^ + A^d-^ A2 -in Í3L2-3L! ai-apA , A fbp 3/A-2 | A~2\K b2 i2 y' -& + 3(Aň1 + Ar1K-^= i n i ai~an an-an_i \ , , /d„-i 3/-A-2 , a-2\l. h1 W \ A? ~~ A3 j+^A3 ~ 2^1 +^n)"n-A2 -%f + 3(A-1 + A^1)c,-g^ = in / Si+l—Si äi-3i-l | i J / Pj-l 3('A— 2 , A—2\k Pj+l \ iü\ Af+1 Af J+HA? 2^+1 +A* )^ A?+J> z = 1,..., n — 2. ^. d, := 10%P^ - 22b^+3bí + Ci+^3Ci, i = 0,...,n-l, "i+l "i+1 "i+1 ___J __ Q Dn-Dn-1 i pCn+Cn —j Tl •— uro—1 ^ A 2 ~T ^ Al c p ._ bj+i-bj___Cj_ , diT1+5dz . _ n .j /j r — ci+1-Ci____3dj______3ež • _ n _ i ö- *»- 10a|+1 10a?+1 5Ai+1'z-U'-"'n L Důkaz. Engeln-Müllges, Reutter (1990). I 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"-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 Cra-spojitá parametrizace křivky. Dále řekneme, že křivka má spojitou křivost (spojitou torzi), jestliže k (t) je spojitá funkce. Platí pak Věta 1.8 Vizuální spojitost, křivost a torze. Pro křivku v R3 je vizuální spojitost stupně n ekvivalentní s tím, že k E Cn~2 a r E Cn~3. Důkaz. Pottmann (1988). I 1. INTERPOLACE S KRIVKAMI 115 Geometrické spline-křivky vznikají složením z polynomiálních dílčích křivek tak, že výsledná křivka je podle výše definovaných pojmů spojitá. 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(í) a k(í) = k((f>(t)) v okolí bodu t0 lak, že k(í0) = k((f>(t0)), pak platí k(ťb) = k(0(ťo)), k'(ío) = '(t0)k'((t0)), k"(ío) = 0,,(ío)k,(0(ío)) + 0,2(ío)k,,(0(ío)). Požadavek vizuální spojitosti druhého řádu v bodě spojení ti mezi dvěma dílčími polynomy lze psát jako k(í-) = k(íi+), k'(U-) = ßik'(tt+), k"(íi-) = ß2k'(tt+)+ß21k"(tt+). Tyto vztahy použijeme v následujícím příkladu interpolující geometrické spline-křivky - tzv. z/-splinu. Pro v-spline-křivky požadujeme shodu prvních derivací v bodech dotyku mezi dílčími polynomy (ßi = 1) a to nám vytváří odpovídající geometrický požadavek druhého řádu. Definice. z/-spline-křivka Buď dáno n + 1 bodů p^ G Rd s hodnotami parametrů U E H, t0 < ti < ■ ■ ■ < tn spolu s hodnotami napětí z/j, i = 0,... ,n. Křivka p(í), t G [to,tn], p : [ío,ín] -^ Rd se nazývá u-spline-kňvka, jestliže platí: 1. p(í) je kubický polynom v každém dílčím intervalu [ti,ti+i], 0 < i < n. 2- Pí(íí+i) = Pí+i(íí+i), i = 0, • • •, n - 1. 3- PÍ(*i+i) = PÍ+i(*í+i), i = 0,...,n- 1, tj. p G C1l[to,tn}. 4. pV(íi+1-) = pí'+1(íi+i+) - ui+1p'i(ti+1), i = 0,...,n-l. 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é z/-spline-křivky: P,(ío) = Po,,P,(ín) = P„/, (LI) • Okrajová podmínka pro přirozené z/-spline-křivky: ľop'(ío) - P"(tn+) = 0, vnP'(tn) + p'(í„-) = 0, (1.2) 116 KAPITOLA 5. INTERPOLACE A APROXIMACE • Okrajová podmínka pro uzavřené z/-spline-křivky: P(*0) = P(*n), P'(*0) = P'(ín), P"(to + ) - p"(ín-) = (ľ0 + ľn)p'(ío) = 0. (1.3) Poznamenejme, že v 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í Vi a Vi+\ 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 z/-spline-křivek v-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" := Pi'iti+i-), b~ := p/'(ti+i-), , . a+ := p/(rm+), b+ := p/'(rm+), [LA) z výpočtu «ÍÍ4 V(a- *a~)(b * k )-(a~*b ) (a-* . 3 V(a+ *a+)((b+ -^•a+)*(b+-^-a+))- -(a+ *b+)2 (a-*a-)^ ^/((a +*a+)(bH -*b+)-(a+*b+)2) (1.5) (a-*a-)5 = «ÍÍ+1+- I Pro výpočet koeficientů z/-spline-křivek je účelné reprezentovat dílčí polynomy Pj(t) nad hermiteovskou bází. Hermiteovská báze je tvořena Hermiteovými polynomy. Definice. Hermiteovy polynomy jsou tvaru: i/o (z) := 2x3-3x2 + l, Hi(x) := -2x3 -f H0(x) := x3 -2x2 + 1, Hi(x) := x3 - x2 •ix2 (1.6) Tyto polynomy mají tu vhodnou vlastnost, že jak polynomy tak jejich derivace nabývají v krajních bodech intervalu [0,1] hodnot 0,1: Ho(0) = 1, HQ{\) íh(0) = 0, íh(l) #o(0) = 0, ßo(l) H^O) = 0, íři(l) = 0, HQ'(0) = 0, ířo(l) = 1, H^(0) = 0, ^(1) = 0, ßo'(0) = 1, ßo'(l) = 0, íř/(0) = 0, #/(!) = o, = o, = o, = 1. (1.7) 1. INTERPOLACE S KRIVKAMI 117 Herniiteovy polynomy obdržíme hermiteovskou interpolací výše uvedených bodů. Věta 1.10 Výpočet z/-spline-křivek. Buď dány body dotyku (íi,Pj), Pj G Rd a body pnutí ui; i = 0,..., n. Dále buď A, (Xi d, ti Cj_ i, = Am, = 3 (p^ii-a^i) + Pi(a?_! - a?) + Pm(a?)) . (1.8) PaA; tee j-tý dílčí polynom p j (ť) interpolující u—spline-křivky reprezentovat následovné: Pj(t) = H0(s) ■ pj + Íri (s) • Pj+1 + hjH0(s) ■ p'3 + hjH^s) ■ p'j+1, (1.9) Me s :- t-tj přičemž můžeme neznámé p'0, p[, ... ,p'n získat jakožto řešení systému lineárních rovnic: 1. Okrajové podmínky 1.1: A (p; 1 di - a0Pi p'2 d2 Pra-2 dra-2 \ Pn-1 / \ dra-l - a0Pra / / A a0 + «i + ^0 ai ai ai + a2 + -7^2 íl. Cln-3Cln-3 + ^ra-2 «ra-2 ^ra-2 \ «ra-2 (Zra-2 + «ra-1 H—^2" / pro uzavřené interpolující spline-křivky: 118 KAPITOLA 5. INTERPOLACE A APROXIMACE A c0 Cl c2 cra-2 \ Cra_i J í 0(Pl-P2) o(Pn-Pn-l) 6 Ai ó~ 3(P2-Pi) A2 3(P3-P2) . A3 ,(Pn-l-Pn-2) ' An_l o(Pn-Pn-l) An 0P1-P0 á Ai o(P2-P2) ° A2 o(Pn-2-Pn -3) An_2 (Pn-1-Pn- 2) A / 2(A! + Ara) Ai 0 A! 2(A! + A2) A2 0 A2 2(A2 + A3) A3 0 : : : 0 A„, Ar \ Ara_2 2(Ara_2 + An_i) Ara_! 0 Ara_! 2(Ara_! + Ara) y -2. b, 3. d,. ^g^ - ^cm + 2c,), i = 0,..., n - 1. Ci+i—c 3A i+í , i = 0,..., n — 1. Důkaz. Zřejmé.