OpenGL evaluátory I

Pavel Tišnovský

Úvodník

Dnešním dnem začíná na Rootu nový seriál, ve kterém se budeme věnovat další pokročilé technice používané při vytváření aplikací s grafickou knihovnou OpenGL. Jedná se o implementaci takzvaných evaluátorů, pomocí nichž je možné jednoduše vypočítat souřadnice bodů, které se nachází na parametrické křivce nebo ploše. Evaluátory je možné použít také pro poloautomatické generování normálových vektorů (normál) k povrchu tělesa, barev pro jednotlivé vrcholy, souřadnice do textury apod.

Obsah

Reprezentace těles v počítačové grafice

Tento díl je úvodní, proto si v něm uvedeme základní informace o reprezentaci těles v počítačové grafice a významu parametrických křivek a ploch pro reprezentaci těles.

Mnoho objektů zpracovávaných a zobrazovaných v počítačové grafice má charakter tělesa, tedy útvaru, který zaujímá určitý objem v prostoru. V tomto smyslu můžeme na tělesa používaná v počítačové grafice nahlížet také jako na množinu bodů v trojrozměrném prostoru, které splňují určitá kritéria. Pokud například nadefinujeme relaci sousednosti bodů v trojrozměrném prostoru, lze za trojrozměrné těleso považovat sjednocení dvou navzájem disjunktních množin - množiny vnitřních bodů a množiny bodů hraničních. Různými způsoby reprezentace tělesa se snažíme efektivně popsat buď množinu hraničních bodů (hraniční reprezentace) nebo množinu vnitřních bodů (objemová reprezentace).

Mezi tři základní způsoby reprezentace prostorových těles patří:

1. Hraniční reprezentace - těleso je popsáno svým povrchem, který může mít kromě geometrických vlastností zadané například i optické vlastnosti povrchu (barvu, průhlednost, odrazivost, index lomu, texturu apod.).
2. Objemová reprezentace - těleso je popsáno svým objemem, tj. výčtem těch částí prostoru, které tvoří hmotu (vnitřek) tělesa. Podobně jako u hraniční reprezentace, i u této reprezentace je možné kromě vlastní informace o obsazeném prostoru zadávat i další data, které se vztahují k vnitřní oblasti tělesa, například průhlednost nebo barvu jednotlivých obsazených částí prostoru.
3. Procedurální reprezentace - těleso není přímo zadáno geometrickými daty, jako v předchozích dvou reprezentacích, ale algoritmem, který umožňuje vyjádřit povrch tělesa, objem tělesa, nebo i další informace o tělese. Mezi dva nejpoužívanější způsoby procedurální reprezentace patří využití fraktálů a částicových systémů.

V současné době patří v počítačové grafice mezi nejpoužívanější reprezentaci těles reprezentace hraniční (Boundary representation, zkráceně též B-rep). Mezi hlavní důvody vedoucí k používání hraniční reprezentace patří poměrně jednoduché datové struktury využívané pro popis geometrie tělesa, přímočaré a rychlé zobrazení s využitím 3D knihoven (OpenGL, Direct3D apod.) a podpora grafických akcelerátorů.

Použitím metod reprezentace těles ve scéně pomocí popisu jejich hranice musíme vyřešit netriviální otázku, jakým způsobem se bude povrch těles (ten chápeme jako hranici mezi tělesem a volným prostorem či jiným tělesem) popisovat a jak se budou definovat optické vlastnosti těles. Mezi obvyklé způsoby popisu těles patří rozložení celého povrchu na rovinné plošky (polygony), parametrické plochy či na použití přímkových ploch. Při popisu grafické knihovny OpenGL (viz http://www.root.cz/clanek/1713) jsme se zaměřili především na popis povrchu pomocí rovinných plošek, zde se zaměříme na použití parametrických ploch.

Obrázek 1: Procedurální model terénu vytvořený pomocí metody přesouvání prostředního bodu

Obrázek 2: Model vytvořený pomocí NURBS ploch

Obrázek 3: Jednoduchý částicový systém

Parametrické křivky a plochy

Při popisu hranice tělesa pomocí parametrické hraniční reprezentace je povrch tělesa rozdělen na elementární části nazývané pláty či záplaty (patch). Výsledná plocha tělesa se získá navázáním těchto plátů na sebe. Každý z plátů je přitom vyjádřen takzvanou bodovou rovnicí. V počítačové grafice se nejčastěji používají bodové rovnice, které jako své bázové funkce obsahují polynomy nízkého stupně, protože tyto jsou snadno diferencovatelné a lze provádět rychlé výpočty hodnot těchto funkcí pomocí Hornerova schématu, ve kterém jsou použity pouze jednoduché a rychlé operace sčítání a násobení.

Bodovou funkci parametrické křivky P_3D(t) s parametrem t lze zapsat jako:
P_3D(t)=[x(t), y(t), z(t)]

V ploše se zápis zjednoduší, protože není nutné vyjadřovat z-ovou souřadnici:
P_2D(t)=[x(t), y(t)]

Podobně lze zapsat i bodovou funkci parametrické plochy Q(u, v) s parametry u a v:
Q_3D(u, v)=[x(u,v), y(u,v), z(u,v)]

Kde x(u,v), y(u,v) a z(u,v) jsou funkce dvou parametrů u a v. Tyto parametry mohou nabývat hodnot z rozsahu 0 až 1. Jinými slovy znamená zápis bodové funkce fakt, že bodu o souřadnicích [x, y, z] v trojrozměrném prostoru odpovídá bod o souřadnicích [u, v] v prostoru parametrickém.

Na parametrickou plochu se můžeme dívat jako na množinu bodů vzniklou tažením křivky po určité trajektorii. Tato křivka při svém pohybu může měnit svůj tvar. Z bodové rovnice lze jednoduše vyjádřit rovnice tečných vektorů ve směrech parametrů u a v k ploše Q(u, v) a z těchto dvou vektorů vypočítat normálu k povrchu:
n=(q_u x q_v) / |q_u x q_v|

Kde x znamená operaci vektorového součinu.

Napojování parametrických křivek a ploch

Pro účely počítačové grafiky i dalších (například fyzikálních či estetických) požadavků je důležité zaručit spojitost napojení dvojice plátů. Rozlišujeme dva druhy spojitosti - parametrickou spojitost Cⁿ a geometrickou spojitost Gⁿ.

Dva pláty parametrické plochy mají napojení C⁰, mají-li společnou hranu, která je křivkou třídy alespoň C⁰. Dva pláty mají spojité napojení C¹, pokud mají společnou jednu stranu a mají-li shodné parciální derivace ve všech bodech společné strany prvního i druhého plátu.

Dva pláty mají spojité napojení G¹, mají-li společnou hranu, která je křivkou spojitosti alespoň G¹ (pro zaručení geometrické spojitosti G¹ je zapotřebí zachovat alespoň spojitou změnu tečen, nikoli tečných vektorů, jak je tomu u spojitosti G¹) a jsou-li parciální derivace podél této strany ve směru napojení lineárně závislé s koeficientem k>0, který se spojitě mění podél této společné strany.

Pro většinu aplikací je pro hladké napojení plátů nutné dodržet alespoň spojitost G¹, pouze pro některé specializovanější aplikace se musí dodržet přísnější podmínky spojitosti C¹.

Modelování parametrických křivek a ploch

Parametrické plochy se při interaktivním modelování zadávají pomocí řídicích bodů a bázových funkcí. Bázové funkce jsou většinou přímo dané použitým typem křivek a ploch, uživatel tedy může měnit pouze polohu řídicích bodů (u NURBS křivek se mění ještě uzlový vektor a váhy řídicích bodů).

V počítačové grafice se ponejvíce používají aproximační křivky a plochy. Interpolační plochy se pro modelování v trojrozměrném prostoru většinou nepoužívají, neboť mají pro většinu úloh počítačové grafiky nevhodné vlastnosti - nežádoucí oscilace, nelokálnost změn při posunu řídicích bodů atd. I v plošné grafice mají interpolační křivky omezené použití, například tvorbu cest animovaných objektů.

Aproximace a interpolace s použitím parametrických křivek a ploch

Při aproximaci určuje poloha řídicích bodů určitým způsobem tvar výsledné plochy, i když tato plocha obecně těmito body nemusí procházet. Pro napojování ploch je důležité, aby byly specifikovány tečné podmínky na všech jejich stranách. Jako bázové funkce se nejčastěji používají polynomy, které však nutně nemusí mít ve směrech růstu parametrů u a v stejný stupeň.

V interaktivní počítačové grafice se nejčastěji používají polynomy třetího stupně, protože u polynomů nižších stupňů nelze vždy zaručit podmínky napojení (C²). Kubický polynom zaručuje spojitost C¹ a C² (a samozřejmě také G¹ a G²) a poskytuje tak uspokojivé modelovací možnosti. Použití polynomů vyššího stupně vede ke zvýšení časové náročnosti výpočtů, možnému vzniku numerických chyb, případně i k nežádoucím oscilacím.

Mezi často požadované vlastnosti parametrických křivek a ploch patří:

1. Invariance k lineárním transformacím popř. i perspektivní projekci. Tato vlastnost zaručuje, že lineární transformace popř. projekce aplikované na řídicí body parametrické plochy má stejný výsledek, jako aplikace této transformace na každý bod vygenerované plochy. Je zřejmé, že při splnění podmínky invariance je z výkonnostního hlediska výhodnější aplikovat transformace pouze na řídicí body parametrické plochy. Většina používaných aproximačních ploch podmínku invariance splňuje vzhledem k lineárním transformacím, u racionálních ploch (mezi něž patří i NURBS plochy) je současně splněna i invariance vzhledem k perspektivní projekci. Dále probírané (neracionální) Bézierovy plochy a křivky však nejsou invariantní vzhledem k perspektivní projekci.
2. Vlastnost konvexní obálky zaručuje, že všechny body vygenerované parametrické křivky či plochy leží v konvexní obálce všech svých řídicích bodů. Může se použít i slabší podmínka, kde pouze část plochy leží v konvexní obálce některých řídicích bodů. Pokud zaručíme tuto vlastnost, zjednoduší se velké množství algoritmů prováděných s modely těles, například test na průnik dvou těles, vytváření obalových těles nebo test průsečíku paprsku s tělesem. Bézierovy křivky i plochy leží uvnitř konvexní obálky. Totéž platí pro racionální Bézierovy plochy a křivky, ovšem za předpokladu, že jsou váhy všech řídicích bodů kladné.
3. Lokalita změn zaručuje, že se změnou polohy jednoho řídicího bodu se změní tvar jen části plochy přiléhající k tomuto řídicímu bodu, nikoli plocha celá. Tato vlastnost je důležitá především při interaktivním modelování těles pomocí parametrických ploch, protože lze dopředu odhadnout vliv editačních operací na tvar výsledné plochy.
4. Plocha může procházet krajními body svého řídicího polygonu. Tuto vlastnost, která je zaručena například u Bézierových ploch, lze využít pro snadné napojování jednotlivých plátů s dodržením požadované třídy spojitosti C⁰, C¹, G¹ nebo G². Této vlastnosti lze dosáhnout i u B-spline ploch použitím takzvaných násobných řídicích bodů, tj. bodů majících stejné souřadnice v prostoru.

V současnosti se v počítačové grafice používá několik navzájem odlišných typů parametrických křivek a ploch, které se liší jak svými geometrickými vlastnostmi, tak i implementační, výpočetní a paměťovou náročností. Vzhledem k zaměření článku si popíšeme pouze Bézierovy křivky a plochy, které patří k nejjednodušším typům parametrických křivek a ploch (jak z uživatelského, tak i programátorského hlediska).

V navazujícím seriálu, který bude věnován knihovně GLU, budou popsány i plochy NURBS (Non-Uniform Rational B-Splines), které jsou použity v mnoha aplikacích typu CAD a CAM, protože je pomocí nich možné přesně modelovat kvadriky (koule, válec, kužel) a offsetové plochy. Ukázka základních těles vymodelovaných pomocí NURBS je zobrazena na čtvrtém obrázku.

Obrázek 4: Základní tělesa vytvořená z NURBS

Obsah dalších pokračování

V druhém pokračování tohoto seriálu si popíšeme charakteristiky Bézierových křivek, které tvoří základní prvek v OpenGL evaluátorech.

Zkomprimovaná verze článku i s přílohami

Zkomprimovaná verze tohoto článku je umístěna zde.