Vykreslování povrchů terénů s LOD, Gouraudovo a Phongovo stínování

Obsah

1. Volba úrovně detailů při vykreslování
2. Ukázka trojrozměrných scén vykreslených s využitím LOD
3. Dynamické zvyšování a snižování úrovně detailů
4. Výpočet vzdálenosti, ve které je chyba při LOD přijatelná
5. Výpočet normálových vektorů trojúhelníků
6. Gouraudovo stínování
7. Phongovo stínování
8. Výpočet normálových vektorů vrcholů trojúhelníků
9. Obsah dalšího pokračování tohoto seriálu

1. Volba úrovně detailů při vykreslování

V následujících odstavcích bude vysvětleno, jakým způsobem se při vykreslování terénu složeného z trojúhelníků (tj. pravidelné či nepravidelné trojúhelníkové sítě) zvolí správná úroveň detailu pro jednotlivé bloky z hierarchie.

V předcházejícím pokračování tohoto seriálu jsme si řekli, že princip dynamické změny úrovně detailů je založen na zobrazování vzdálenějších částí terénu s menšími detaily než mají objekty či jejich části, které se nachází blíže k pozorovateli. Klíčovým problémem zůstává určení vzdáleností, ve kterých je možné přejít na menší (méně podrobnou) úroveň detailů. Nejjednodušším způsobem je nastavení těchto vzdáleností na konstanty, podobně jako u mipmap použitých při texturování, kdy má každá textura umístěná o jednu úroveň hierarchie výše dvojnásobné rozlišení a textura na nejnižší úrovni obsahuje pouze jeden texel.

Toto na první pohled jednoduché řešení však s sebou přináší jednu poměrně závažnou komplikaci. Změna detailů z jedné úrovně do jiné ve vzdálenosti d od kamery způsobí, že se prudce změní geometrie terénu. To se při průchodu terénu bude projevovat tak, že se jednotlivé části terénu budou „vzdouvat“ či jinak nereálně měnit svůj povrch. Platí to i při přechodu z nižších detailů na vyšší. To je samozřejmě nechtěný vizuální efekt a je třeba jej pokud možno kompletně odstranit, nebo alespoň minimalizovat na přijatelnou míru. To si vysvětlíme ve třetí kapitole, v kapitole druhé jsou uvedeny ukázky trojrozměrných scén vykreslených s respektováním modifikování úrovní detailů (LOD).

2. Ukázka trojrozměrných scén vykreslených s využitím LOD

Na níže uvedené sekvenci obrázků je ukázáno, jakým způsobem se může změnit pohled na celou trojrozměrnou scénu v případě, že se změní počet generovaných trojúhelníků reprezentujících výškové pole. Scény jsou vykresleny (renderovány) pomocí programu POVRay, ve kterém je možné výškové pole zadat pomocí bitmapového obrázku (typu GIF, PNG apod.). Úpravou tohoto obrázku v grafickém editoru (většinou aplikací filtru Pixelize) se mohou sousední pixely v určitém bloku nastavit na stejnou barvu, na což POVRay reaguje vytvořením větších trojúhelníků s menší hustotou.

Bitmapové obrázky pro vstupní výškové pole byly vytvořeny v programu FractInt, jejich úprava proběhla ve známém grafickém editoru GIMP. Místo programu FractInt však bylo možné použít i některé demonstrační příklady uvedené v předchozích částech tohoto seriálu. Změna detailů je záměrně „přehnaná“, ve skutečnosti se vždy snažíme o to, aby tato modifikace vstupních dat neměla na výstupní obrázek žádný výraznější vliv.

Obrázek 1: Nemodifikované výškové pole vygenerované programem FractInt

Obrázek 2: 3D scéna vykreslená s použitím nemodifikovaného výškového pole

Obrázek 3: Výrazná změna LOD v polovině výškového pole

Obrázek 4: 3D scéna vykreslená s použitím modifikovaného výškového pole z obrázku 3

Obrázek 5: Postupná změna LOD v šesti krocích

Obrázek 6: 3D scéna vykreslená s použitím modifikovaného výškového pole z obrázku 5

Obrázek 7: Hranice šesti kroků LOD na obrázku 5

3. Dynamické zvyšování a snižování úrovně detailů

Při změně detailů (uvažujme přechod z více detailů na méně, opačný přechod se projevuje podobně) je použit větší blok, což způsobí, že některé body rastru budou při vykreslování ignorovány. Na osmém obrázku je takový přechod znázorněn. Všechny bílé body, které leží ve druhé mřížce, budou při vykreslování terénu ignorovány, tj. nebudou z nich generovány trojúhelníky.

Obrázek 8: Přechod na nižší detaily při vykreslování terénu

Ignorování těchto bodů (přesněji řečeno vrcholů trojúhelníků) při vykreslování způsobí chyby v celkové geometrii zobrazovaného terénu. To je způsobeno faktem, že po odstranění některých bodů se musí vytvořit větší bloky, které budou tvořeny trojúhelníky s větší plochou. Plocha těchto trojúhelníků aproximuje původní plochu terénu, přitom se však ignorují vynechané body původní rastrové mřížky reprezentující výšky (heightfield). Tyto body ovšem nemusely ležet v ploše trojúhelníku; u morfologicky bohatých povrchů je to dokonce velmi nepravděpodobné. V takovém případě bude mít plocha trojúhelníka odchylku od skutečné plochy terénu, což nutně povede k vizuální chybě v zobrazení – viz též devátý ilustrační obrázek, na kterém je zobrazený kolmý řez terénem.

Obrázek 9: Odchylka ve tvaru terénu vzniklá odstraněním jednoho bodu (pohled v řezu)

4. Výpočet vzdálenosti, ve které je chyba při LOD přijatelná

Díky použité perspektivní projekci se průmět této odchylky zmenšuje se vzrůstající vzdáleností vykreslovaných trojúhelníků od kamery (pozorovatele). Toho lze využít k nalezení vzdálenosti, ve které již bude velikost chyby přijatelná, tj. její rozsah bude v řádu jednotek pixelů pro dynamické scény, popř. pod úrovní velikosti pixelu pro scény statické. Nechť je ε maximální přijatelná odchylka na stínítku (tj. diskrétní mřížce obrazovky či monitoru, na který se model vykresluje) a τ je projekce této odchylky na stínítku. Pro opticky přijatelnou chybu musí platit vztah:

τ≥ε

Projekce τ na stínítku obrazovky je vyjádřena vztahem:

τ=δD^-1

kde D značí vzdálenost odchylky od kamery (pozorovatele). Výpočet vzdálenosti, ve které se odchylka δ bude jevit menší než τ, lze vyjádřit vztahem:

D≥ f_nδ/τ

kde f_n značí vzdálenost projekční roviny od kamery, přičemž horizontální i vertikální úhel pohledu je nastaven na π/2. Na výsledný průmět odchylky na stínítku nebude mít vliv pouze vzdálenost odchylky od kamery, ale i úhel, ze kterého je na odchylku pohlíženo. Je třeba si uvědomit, že vzniklé odchylky budou vznikat pouze ve směru osy Z, která představuje vertikální směr. Pozice X a Y se nikdy nemění, protože tyto pozice jsou v rámci diskrétní mřížky konstantní. Se vzrůstajícím úhlem pohledu od vodorovného směru bude průmět odchylky na obrazovce (tj. její projekce) klesat. Nejvíce zřejmá bude odchylka při pozorování ve vodorovném směru. Naopak při pozorování ve směru svislém bude výsledná odchylka nulová. Započítáme-li do projekce odchylky na stínítko i vliv úhlu pohledu α získáme následující vztah:

D≥ f_nδ sin α/τ

Pro výpočet vzdálenosti D každého bloku je třeba vypočítat průměty odchylek všech bodů, které budou ignorovány. Na základě největší odchylky je tato vzdálenost vyčíslena. Jelikož možností z jakého úhlu bude terén pozorován je nekonečně mnoho a úhel pohledu α leží v intervalu <0, π>, je zapotřebí tento interval hodnot rozdělit na několik částí a pro jednotlivé části vypočítat odpovídající vzdálenost. Při aplikaci se pak daný blok může použít pouze v případě, je-li jeho vzdálenost od kamery větší než vzdálenost, kterou má uloženu ve své datové části a které odpovídá úhel pozorování terénu α.

5. Výpočet normálových vektorů trojúhelníků

Při převodu výškového pole na síť trojúhelníků je kromě pozic jednotlivých vrcholů trojúhelníků nutné také vyjádření jejich normálových vektorů. Terén si pro tento účel můžeme představit jako funkci, kde výška v nějakém bodě je funkční hodnotou souřadnic x a y:

z=f(x,y)

V takovém případě by se normálový vektor hladké a spojité dvourozměrné funkce vyjádřil pomocí vektorového součinu parciálních derivací v každém bodě terénu:

n=(∂ f/∂ x) × (∂ f/∂ y)

Výše uvedený vztah je ovšem možné použít pouze v případě, že by byl povrch definován pomocí spojité funkce. Ve skutečnosti je terén popsán funkcí diskrétní (formou dvourozměrné tabulky reprezentované rastrovým obrázkem) a výpočet derivací je proto komplikovanější a nepřesný (na rozdíl od analytického výpočtu použitého u spojitých funkcí). Z tohoto důvodu je zapotřebí nalézt odlišný způsob výpočtu normálových vektorů surfelů.

Je zřejmé, že normála vypočtená pro daný bod, který leží na terénu, bude záviset na výškách bodů v jeho okolí. Pokud by například okolí bodu, v němž chceme znát normálový vektor, bylo tvořeno pouze dvěma body, pak by se normála vypočítala jako vektorový součin vektorů u a v:

n=u × v

kde u a v jsou normované vektory směřující z daného bodu do obou bodů tvořících jeho okolí. Okolí daného bodu však bývá obvykle tvořeno více jak dvěma body, výjimku tvoří pouze body okrajové a rohové. Bude-li se brát v úvahu pouze nejbližší okolí, tak v případě, že se nejedná o krajní či rohový bod, bude okolí obsahovat osm bodů (můžeme brát v úvahu i pouze čtyřokolí pixelu, zde se však chyba výpočtu opět zvyšuje). Výsledný normálový vektor se pak vypočte jako součet vektorových součinů:

n=∑_i=0^m (v_i × v_i+1)

kde m značí počet bodů tvořících osmiokolí (pro rohové body je m rovno třem, pro okrajové body pěti a pro body uvnitř mřížky osmi) a vektory v_i a v_i+1 jsou normované vektory směřující od daného bodu k bodům v jeho okolí, které jsou uspořádané v protisměru hodinových ručiček. Po výpočtu normálového vektoru n je zapotřebí tento vektor normalizovat, tj. provést operaci:

n'=n/|n|

Uspořádání vektorů proti směru hodinových ručiček je důležité z toho důvodu, aby výsledný vektor směřoval vzhůru k povrchu.

Výše uvedeným postupem jsme získali normálové vektory celých trojúhelníků, při jejichž použití pro vykreslování terénu sice můžeme získat zajímavé obrázky, ale vzhledem k tomu, že sousední trojúhelníky budou mít rozdílné normály a budou celé vykresleny rozdílnou barvou, bude na první pohled patrné, z čeho se terén skládá. Tento způsob vykreslování trojúhelníků na základě jejich normál se nazývá konstantní stínování (flat shading).

V počítačové grafice se však ujaly i výpočetní metody, které dokážou zobrazovat síť trojúhelníků tak, aby nebyly na první pohled patrné hranice (tj. hrany) mezi jednotlivými trojúhelníky. Těchto metod existuje celá řada, nejznámější je však Gouraudovo a Phongovo stínování (Gouraud shading a Phong shading).

6. Gouraudovo stínování

Gouraudovo stínování navrhl Henri Gouraud už v roce 1971, je tedy o celé čtyři roky starší než slavný článek Bui-Tuong Phonga. Toto stínování spočívá v interpolaci barvy v plošce (v našem případě trojúhelníku) v případě, že známe barvu jednotlivých vrcholů. Při interpolaci barev se používá bilineární interpolace, která je velmi rychlá a především tak jednoduchá, že je ji možné implementovat i v těch nejjednodušších grafických akcelerátorech (ty stejně bilineární interpolaci implementují, minimálně pro účely texturování). Díky interpolaci barev se ztrácí vizuálně nápadné (a patřičně rušivé) hrany mezi jednotlivými trojúhelníky, takže vytvářené těleso (terén) je zobrazeno jakoby hladkou plochou.

Při implementaci Gouraudova stínování brzy narazíme na jeden problém – jakým způsobem můžeme zjistit barvy vrcholů trojúhelníků? Prozatím totiž známe pouze normálové vektory celých trojúhelníků a popř. i barvu povrchu platnou pro daný trojúhelník. Samozřejmě můžeme využít osvětlovací model (např. Phongův), tím však vypočteme barvu celého trojúhelníku, nikoli obecně rozdílné barvy jeho vrcholů. Řešením je použití osvětlovacího modelu na výpočet barev ve vrcholech trojúhelníků. Proto je nutné vypočítat normálový vektor i pro vrcholy trojúhelníků, ovšem s tím, že tři vrcholy v jednom trojúhelníku mohou mít jinou normálu.

Samozřejmě se jedná o geometrický nesmysl, protože normála musí být kolmá na povrch a tím pádem je na ploše celého trojúhelníku konstantní. To je sice pravda, ale musíme si uvědomit, že trojúhelníková síť pouze hrubě aproximuje skutečný tvar objektu (terénu), proto si můžeme chybějící informace o skutečné podobě plochy doplňovat podle potřeby. Z normálových vektorů trojúhelníků, které se v daném vrcholu střetávají, vypočteme normálový vektor vrcholu a ten posléze použijeme v osvětlovacím modelu pro výpočet barvy vrcholu.

V případě Gouraudova stínování se celý trojúhelník vykreslí s využitím bilineární interpolace, která je například podporována i v grafické knihovně OpenGL – pokud každému vrcholu přiřadíme funkcí glColor??() jinou barvu, provede se bilineární interpolace zcela automaticky s využitím prostředků, které nabízí prakticky každý grafický akcelerátor. Více informací o této problematice je možné získat v seriálech Grafické karty a grafické akcelerátory a Grafická knihovna OpenGL.

7. Phongovo stínování

Phongovo stínování je do značné míry podobné stínování Gouraudovu, jde však při vizuální „rekonstrukci“ skutečného tvaru povrchu ještě o jeden krok dále. Zatímco se v Gouraudově stínování interpoluje barva vrcholů, u stínování Phongova se interpolují samotné normálové vektory, s jejichž pomocí se s využitím osvětlovacího modelu vypočte barva v každém místě plošky (trojúhelníku). Takto vykreslený povrch je vizuálně kvalitnější než povrch vykreslený s použitím stínování Gouraudova, zejména při animacích, kdy se při pohybu tělesa náhodně zobrazují odlesky.

Na druhou stranu je však Phongovo stínování časově náročnější, protože se pro každý vykreslovaný bod musí vypočítat celý osvětlovací model (obsahující většinou minimálně operaci cos a pow). Některé grafické akcelerátory proto tuto metodu stínování nepodporují, což nám však konkrétně u vykreslování trojrozměrných terénů nemusí vadit, protože terén (většinou) nemá nastaveny odlesky – právě ty nejvíce degradují vizuální kvalitu Gouraudova stínování, u matných objektů není rozdíl mezi oběma metodami výrazný.

8. Výpočet normálových vektorů vrcholů trojúhelníků

Normálové vektory vrcholů trojúhelníků se vypočtou velmi jednoduše. Postačí sečíst normálové vektory všech trojúhelníků, které se v daném vrcholu střetávají (z předchozí části tohoto seriálu víme, že sousední trojúhelníky musí mít jednu společnou hranu a dva společné vrcholy). Po součtu je zapotřebí provést normalizaci výsledku způsobem, který byl naznačen v páté kapitole, tj. vydělení jednotlivých složek normálového vektoru celkovou délkou vektoru tak, aby zůstal zaručen vztah:

|n|=1

Vzhledem k tomu, že se povrch terénu nemění (alespoň ne ve většině případů), je možné provést výpočet normálových vektorů jednotlivých vrcholů trojúhelníků v čase preprocessingu, tj. načítání celé scény do operační paměti. Výpočet normály je totiž poměrně složitá operace, která vyžaduje tři operace dělení, tři operace násobení a jeden výpočet odmocniny. Další optimalizace může spočívat ve výpočtu ambientní a difúsní barvové složky jednotlivých vrcholů (pro Gouraudovo stínování), ovšem pouze za předpokladu, že se nebude měnit poloha světelného zdroje. To je ve většině případů možné zaručit, protože pohyb provádí pouze pozorovatel (kamera). Odrazovou barvovou složku osvětlovacího modelu není možné předpočítat, protože závisí na poloze pozorovatele resp. na vzájemné pozici světelného zdroje, bodu na povrchu tělesa a pozorovatele.

9. Obsah dalšího pokračování tohoto seriálu

V příští části seriálu již problematiku stochastických fraktálů opustíme a budeme se věnovat další skupině fraktálů. Jedná se o takzvané L-systémy, které mají v počítačové grafice velmi významné místo, zejména při parametrickém vytváření modelů rostlin.

Obrázek 10: Ukázka fraktálního objektu vytvořeného pomocí L-systémů