Hlavní navigace

OpenGL evaluátory

Pavel Tišnovský

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ázejí 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řadnic do textury apod.

Obsah

Reprezentace těles v počítačové grafice
Parametrické křivky a plochy
Napojování parametrických křivek a ploch
Modelování parametrických křivek a ploch
Aproximace a interpolace s použitím parametrických křivek a ploch
Obsah dalších pokračování
Zkomprimovaná verze článku i s přílohami

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 o 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í zadány 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). Hlavními důvody vedoucími 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 přímkové plochy. Při popisu grafické knihovny OpenGL (viz /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 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 2: Model vytvořený pomocí NURBS ploch

Obrázek 3: Jednoduchý částicový systém
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 P3D(t) s parametrem t lze zapsat jako:
P3D(t)=[x(t), y(t), z(t)]

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

Podobně lze zapsat i bodovou funkci parametrické plochy Q(u, v) s parametry u a v:
Q3D(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 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=(qu x qv) / |qu x qv|

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 Cn a geometrickou spojitost Gn.

Dva pláty parametrické plochy mají napojení C0, mají-li společnou hranu, která je křivkou třídy alespoň C0. Dva pláty mají spojité napojení C1, 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í G1, mají-li společnou hranu, která je křivkou spojitosti alespoň G1 (pro zaručení geometrické spojitosti G1 je zapotřebí zachovat alespoň spojitou změnu tečen, nikoli tečných vektorů, jak je tomu u spojitostiG1) 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 G1, pouze pro některé specializovanější aplikace se musí dodržet přísnější podmínky spojitosti C1.

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

Parametrické plochy se při interaktivním modelování zadávají pomocí řídících bodů a bázových funkcí. Bázové funkce jsou většinou přímo dány použitým typem křivek a ploch, uživatel tedy může měnit pouze polohu řídících bodů (u NURBS křivek se mění ještě uzlový vektor a váhy řídící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 řídící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 řídící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í (C2). Kubický polynom zaručuje spojitost C1 a C2 (a samozřejmě takéG1 a G2) 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 řídící 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 řídící 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 řídících bodů. Může se použít i slabší podmínka, kde pouze část plochy leží v konvexní obálce některých řídící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 řídících bodů kladné.
  3. Lokalita změn zaručuje, že se změnou polohy jednoho řídícího bodu se změní tvar jen části plochy přiléhající k tomuto řídící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 řídící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 C0, C1,G1 nebo G2. Této vlastnosti lze dosáhnout i u B-spline ploch použitím takzvaných násobných řídící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 z programátor­ské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
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.

Našli jste v článku chybu?

14. 5. 2004 15:15

Pavel Tišnovský (neregistrovaný)

No, napriklad u racionalnich Bezierovych krivek nebo NURBS lze transformace vcetne projekce aplikovat pouze na ridici body a body na krivce/plose vypocitat uz bez dalsiho provadeni transformaci na kazdy bod (coz je casove vice narocne).

U Bezierovych krivek (neracionalnich) aplikace projekce na ridici body nestaci - vysledek by nebyl korektni.



14. 5. 2004 8:42

asd (neregistrovaný)

nechapu jen tu neinvariantnost bezierovych ploch a krivek vzhledem k perspektivni projekci :-(

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

Podnikatel.cz: Změny v cestovních náhradách 2017

Změny v cestovních náhradách 2017

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?