# 1. Křivky

Jedním z klíčových problémů počítačové vědy je vstup dat. Cesty, jimiž se data do počítačů mohou dostat, jsou v zásadě dvě. První cestou je generování dat přímo počítačem. Druhým způsobem je fyzické vkládání dat za pomocí nějakého vstupního zařízení. Druhý způsob je zřejmě velice náročný, je tedy přirozenou snahou tuto činnost zefektivnit.

Problém vstupu dat je obzvláště markantní v počítačové grafice. Pro většinu operací s objekty v počítači je nutné jejich exaktní vymezení. Objekty v počítačové grafice jsou obyčejně množiny bodů, které jsou omezeny plochami, případně v rovině křivkami (pokud se nejedná o fraktály, u nichž je problematické vymezení pojmů jako dimenze, délka atp.). Je tedy přirozeným požadavkem zjednodušit vstup právě křivek a ploch. Křivky a plochy jsou nejlépe reprezentovány funkcemi a funkce je problematické zadávat. Bylo by absurdní chtít po uživateli, aby zadal funkci ve tvaru y = f (x1, x2, . . . , xn) a měl představu o jejím tvaru. Hledají se tedy metody, které umožní uživateli co nejjednodušeji zadat nějakou křivku, či plochu, a to pokud možno tak aby byl dopředu odhadnutelný její tvar. Uživatel má obyčejně za úkol zadat jen několik řídicích bodů a matematický aparát (od kterého je odstíněn) se o vytvoření křivky postará sám.

V roce 1959 používal P. de Casteljau u firmy Citröen matematický model křivek a ploch, jenž mu je umožňoval jednoduše zadávat. Podobně roku 1961 P. Béziere používal program UNISURF u firmy Renault. V té době byla ještě stále tato disciplína integrální součástí počítačové grafiky. V sedmdesátých letech se stále zřetelněji vyčleňovala, až si vysloužila vlastní název: CAGD jako součást A. R. Forrestem zavedené disciplíny zvané výpočetní geometrie. Metody CAGD se postupem času zdokonalovaly a v současné době je k dispozici velmi silný nástroj, který je stále aktivně rozvíjen. Podstatou tohoto rozvoje je poměrně kvalitní matematický aparát (částečně převzatý z deskriptivní geometrie) a v neposlední řadě zřetelný komerční efekt..

Výraznou změnu do CAGD vneslo používání racionálních Bézierových křivek (a ploch) a zvláště jejich speciální případ, racionální Bézierovy křivky s neuniformní parametrizací, tzv. NURBS. Tyto metody umožňují generovat klasické geometrické prvky (jako jsou koule, válce, kuželosečky atp.) za pomoci metod aproximace. Popis těchto metod je možno nalézt například v [Peig84].

Pozn.: V tomto odstavci budeme pro zjednodušení používat výhradně křivky dvourozměrné. Většina metod je do trojrozměrného prostoru rozšiřitelná tak, že se jednoduše přidá souřadnice z. a opíší se rovnice, jež jsou pro souřadnice x a y. Nebude-li tento postup platit, bude vše výslovně uvedeno.

## 1.1. Vyjádření křivek

Křivky jsou obyčejně v počítači reprezentovány jako soustava parametrů nějaké rovnice, která je posléze generativně zobrazována. Toto vyjádření může být v podstatě trojího druhu: Explicitní Implicitní Parametrické

Obr.1.1 Křivka vyjádřená explicitně

Explicitně vyjádřená křivka je zadána jako funkce ve tvaru:

( 1.1 )

Derivace v obecném bodě x se spočítá podle vztahu

.

( 1.2 )

Křivka je orientována ve směru rostoucího x (Obr. 1.1).

Implicitní zadání křivky má tvar:

F(x, y)

= 0

( 1.3 )

Toto zadání není příliš vhodné pro potřeby počítačové grafiky, neboť neumožňuje postupný výpočet křivky. Svůj význam má například při výpočtu průsečíků s implicitně zadanou křivkou (v trojrozměrném prostoru).

Obr. 1.2 Křivka vyjádřená parametricky

V počítačové grafice se nejčastěji pro vyjádření křivek používá tvar parametrický:

x

= x(t)
y = y(t)

( 1.4 )

Parametrické vyjádření se jednoduše zapisuje vektorově:

P

(t) = [x(t), y(t)]

( 1.5 )

kde P(t) je polohový vektor (Obr. 1.2).

Derivace křivky vyjádřené parametricky má tvar

( 1.6 )

Derivuje se tedy po jednotlivých složkách.

Parametr t se pohybuje v intervalu < 0,1 >. Pro t = 0 a t = 1 jsou zápisem ( 1.5 ) vyjádřeny krajní body (Obr. 1.2). Výhodou parametrického zápisu je závislost na jediném parametru. Nevýhodou je, že v některých případech nezaručuje parametrické zadání rovnoměrné rozložení bodů na křivce.

## 1.2. Modelování křivek

Základním prvkem teorie křivek v počítačové grafice jsou křivky polynomiální (Pn(t) = a0 + alt + ... + antn). Z nich se skládají křivky po částech polynomiální, to jsou křivky jejichž segmenty jsou polynomiálními křivkami. Nejčastěji používané jsou křivky třetího stupně - kubiky, které poskytují dostatečně širokou škálu tvarů. Jejich výpočet bývá nenáročný, jsou snadno manipulovatelné a je možné u nich zaručit spojitost C2, požadovanou někdy při modelování v CAD systémech. Křivky vyššího stupně mohou způsobovat nežádoucí vlnění a oscilace a jsou náročnější na výpočet.

Modelování probíhá obyčejně tak, že je definováno několik řídicích bodů (řídicí polygon) a matematický aparát z jejich polohy určí průběh křivky. Některé metody umožňují zadávání křivek též pomocí tečných vektorů, je možno klást podmínky na hladkost navázání aj.

Existují dva základní druhy interpretace řídicích bodů a to interpolace a aproximace. Při interpolaci (Obr. 1.3) generovaná křivka probíhá danými body, zatímco při aproximaci je řídicími body tvar křivky určen, ta jimi však procházet nemusí.

Obr. 1.3 Aproximační (vlevo) a interpolační křivka

## 1.3. Interpolační křivky

Na intervalu I je dána uspořádaná n-tice tzv. opěrných bodů:

a

l = (x1, y1), a2 = (x2, y2), ... , an = (xn, yn).

( 1.7 )

Interpolační funkce je funkce f, jež splňuje požadavek

yi = f (xi), i = 1, ... , n.

( 1.8 )

Interpolační křivka k dané množině bodů je tedy taková křivka, která jimi prochází.

### 1.3.1 Interpolace polynomem

V praxi je nejčastější interpolační technikou interpolace polynomem, a to bud' jediným polynomem n -1 řádu pro n bodů, nebo po částech.

### 1.3.2 Interpolace jediným polynomem

Interpolace polynomem n -1 řádu znamená najít řešení rovnic

( 1.9 )

Vstupem této rovnice jsou body, jimiž má křivka procházet a jejím řešením jsou parametry matice aij. Do výrazu se postupně dosazují body, jimiž má křivka procházet, a tím se obdrží soustava rovnic.

Nevýhodou polynomiální interpolace je, že polynomy vyššího řádu mohou vnutit křivce nepřirozené vlnění. V počítačové praxi bývá polynomiální interpolace používána pro křivky stupně maximálně pět.

### 1.3.3. Interpolace po částech

Daleko častější interpolační technikou je interpolace křivky po jejích částech.

Uvažujme n-tici bodů. Aproximací polynomem třetího řádu potom rozumíme aproximaci jejích každých čtyř bodů polynomem třetího stupně. Problémem, který je potřeba řešit, je potom navazování křivky v bodech, kde jedna část přechází v druhou. Existuje několik metod, které řeší navazování v těchto bodech automaticky. Akimova interpolace, interpolace Hermitovskými polynomy (jejíž zvláštním případem jsou Fergusonovy kubiky, které se používají i pro aproximace a konečně spline křivky k-tého řádu, které zaručují spojitost k-1 řádu. Rozbor těchto metod je možno nalézt v [Drs84], [Drs85] nebo [Drdl92].

Interpolační metody nejsou pro výše uvedené nevýhody příliš často v počítačové grafice využívány. Tyto metody nacházejí uplatnění v numerické matematice a v matematické statistice, kde se na základě interpolací usuzuje na potenciální chování nějakých jevů v budoucnu (potom se hovoří o extrapolaci). Tyto metody z těchto oborů také původně vzešly.

## 1.4. Aproximační křivky

Aproximací bodů rozumíme vytvoření takové křivky, která je těmito body vhodně řízena. Není kladen požadavek na procházení opěrnými body (ani prvním a posledním bodem). Způsob řízení odpovídá vytváření této křivky. Existuje v zásadě dvojí přístup k aproximacím.

Přístup první je znám z numerické matematiky a jeho cílem je smysluplná interpretace vstupních dat. Uveďme metodu nejmenších čtverců, její smyslem je nalézt křivku, jež je hladká, a čtverec vzdálenosti řídicích bodů od ní je minimální. Neměnným základem těchto postupů jsou zadané body. Generovaná křivka má jen informativní charakter.

Druhý přístup je používán v počítačové grafice. Smyslem není interpretace bodů, ale generování křivky. Křivka může být řízena body, potom hovoříme o tzv. řídicím polygonu nebo body a vektory. Metoda, která křivku vytváří, zaručuje její vlastnosti. Požadované vlastnosti jsou její hladkost, spojitost, počet inflexí aj. Tyto metody byly navrženy tak, aby vyhovovaly technické praxi, a zaručují tedy například nízké tření navržených objektů aj.

V počítačové grafice se nejčastěji používá aproximace po částech (podobně jako interpolace), a to obyčejně kubikami (tedy křivkami, které jsou generovány polynomy třetího řádu). Důvody pro to jsou dva. Kubiky jsou dostatečně "pružnými" křivkami, aby se jimi dalo vyjádřit téměř vše, co je v praxi potřeba. Dalším důležitým faktorem je, že stupeň polynomu tři umožňuje velmi rychlý výpočet výsledné křivky, což je výhodné pro její interaktivní tvorbu.

Parametricky lze danou kubiku Q(t) vyjádřit ve tvaru:

x

(t) = axt3 + bxt2 + cxt + dx
y(t) = ayt3 + byt2 + cyt + dy
z(t) = azt3 + bzt2 + czt + dz

( 1.10 )

můžeme zapsat zkráceně v maticovém tvaru:

( 1.11 )

Derivaci q'(t) získáme derivací vektoru T

( 1.12 )

Konstantní matici C můžeme rozepsat do součinu

C = MG

( 1.13 )

kde matice M je typu 4x4 a nazývá se bázová matice. Čtyřprvkový vektor se nazývá geometrický vektor. Geometrický vektor reprezentuje vliv vnějších parametrů. Obsahuje řídicí body nebo řídicí body a tečné vektory atp. Bázová matice, která je dána použitou metodou,pak určuje výpočet křivky podle vztahu:

( 1.14 )

Mezi často požadované vlastnosti křivek patří:

1. Invariance k afinním transformacím a projekcím, která zaručuje, že například rotace řídicího polygonu a následné generování křivky má stejný výsledek, jako rotace každého bodu z vygenerované křivky.

2. Vlastnost konvexní obálky (angl. convex hull property)

(a) silná podmínka - celá křivka leží v konvexní obálce všech svých řídicích bodů,

(b) slabá podmínka - část křivky leží v konvexní obálce některých řídicích bodů (typicky segment, v obálce svého generujícího polygonu).

3. Lokalita změn - změnou polohy (u racionálních křivek i váhy) řídicího bodu se mění jen část křivky, nikoli křivka celá.

4. Křivka může procházet krajními body svého řídicího polygonu.

## 1.5. Spojitost

Při navazování oblouků je významným faktorem spojitost křivek. Říkáme, že výsledná křivka je spojitá, pokud je spojitá ve všech svých bodech, a tedy zejména v navazovacích bodech. Křivka je hladká, pokud jsou ve všech jejích bodech spojité i její první derivace. Pro vyšší derivace říkáme, že křivka má spojitost druhého, třetího a obecně n-tého řádu.

Říkáme, že křivka Q(t) je třídy Cn, má-li ve všech bodech spojité derivace do řádu n. Označení Cn se nazývá parametrická spojitost (Obr. 1.4).

Obr. 1.4 Spojitost C0, C1 a C2

Dva segmenty jsou spojitě navázány (neboli mají spojení třídy C0), pokud je koncový bod prvního segmentu počátečním bodem segmentu druhého. Dva segmenty mají spojení C1, pokud je tečný vektor v koncovém bodě segmentu Q1 roven tečnému vektoru Q2 v jeho počátečním bodě. Analogicky rovnost vektoru první a druhé derivace je požadována pro C2 (Obr. 1.4) atd. Zkráceně zapisujeme:

( 1.15 )

Čím vyšší spojitost je požadována, tím delší "dobu" (ve smyslu parametru t) se oba segmenty k sobě přimykají. Zjevně. Ze spojitosti C0 plyne, že bod se pohybuje po spojité dráze, ale v uzlu může měnit skokem směr pohybu, rychlost i zrychlení. Směr pohybu a velikost rychlosti se nemůže měnit skokem při spojitosti C1 a zrychlení zůstává nezměněné při spojitosti C2.

Podmínka parametrické spojitosti je velice silná, jak ukazuje i následující příklad.

Obr. 1.5 Dvě úsečky spojité G1 a nespojité C1

Představme si křivku spojenou ze dvou úseček (Obr. 1.5) zadaných

Q1

(t) = [2t. 2t]; t Î <0, 1>

Q2

(t) = [t+2. t+2]; t Î <0, 1>

( 1.16 )

a spojených v bodě [2, 2].

Tečné vektory v tomto bodě mají hodnoty a . Podmínka identity tečen není tedy splněna, křivka není C1 spojitá, pohybující se objekt by v uzlu skokem změnil rychlost, i když směr pohybu by zůstal zachován. Právě tyto případy byly motivující pro zavedení geometrické spojitosti označované Gn. Nejčastěji se však používá geometrická spojitost G1.

Řekneme, že dva segmenty křivky Q(t) jsou G0 spojité, pokud je koncový bod Q1 počátečním bodem Q2. Dva segmenty jsou G1 spojité, pokud tečné vektory segmentu Q1 a segmentu Q2 jsou lineárně závislé, t.j. pokud pro ně platí:

k>0

( 1.17 )

Tato spojitost zaručuje totožnost tečen (nikoli tečných vektorů). Pohybující se bod v uzlu nemůže změnit skokem směr, ale může skokem změnit rychlost.

Obr. 1.6 Geometrická a parametrická spojitost. Lupa ukazuje tečné vektory

Opticky zaručuje G1 spojitost "skoro stejnou" hladkost jako C1, z hlediska použití bývá daleko snažší zaručit spojitost G1 nežli C1.

Spojitost G2 je definována jako shoda prvních křivostí 1k v uzlu obou segmentů , kde 1k(t) je tzv. první křivost, která se vypočítá podle vztahu :

( 1.18 )

Spojitost C1 implikuje G1 (obráceně však nikoliv).

Obsah |  | Lagrangeova interpolační křivka