Hlavní navigace

Pokročilé metody zobrazování 3D modelů krajiny

Pavel Tišnovský

V jubilejním padesátém pokračování seriálu si vysvětlíme dvě metody pro vykreslování výškových polí. Jedná se o metodu založenou na sloupcově orientovaném vrhání paprsku a převod výškových polí na pravidelnou i nepravidelnou polygonální síť. Také si nastíníme problém urychlení vykreslování výškových polí.

Obsah

1. Vykreslování 3D terénů pomocí sloupcově orientovaného raycastingu
2. Naklánění a rotace
3. Naklánění posouváním sloupců obrazovky
4. Dvoufázové naklánění
5. Vykreslování 3D terénů pomocí polygonů
6. Řešení viditelnosti a urychlení vykreslování
7. Použití hierarchických bloků
8. Obsah dalšího pokračování tohoto seriálu

1. Vykreslování 3D terénů pomocí sloupcově orientovaného raycastingu

V předchozím pokračování tohoto seriálu jsme si teoreticky řekli, jakým způsobem je možné vykreslit trojrozměrný terén reprezentovaný výškovým polem (heightfield) metodou řezů (horizontů). Řezy jsou ve výškovém poli vedeny tak, aby po promítnutí na obrazovku vytvořily horizonty kolmé na obrazovku; to znamená, že rovina řezu je kolmá na osu procházející pozorovatelem a orientovanou podle nastaveného pohledu. Samotnou adresaci jednotlivých výšek, tj. hodnot pixelů ve výškovém poli, je možné provést celočíselným Bresenhamovým algoritmem, původně určeným pro rasterizaci úsečky.

fractals50_1

Obrázek 1: Princip vykreslování terénu pomocí horizontů (řezů)

Princip vedení řezů ve výškovém poli je naznačen na prvním obrázku, vykreslené horizonty po přepočtu do promítací roviny můžete vidět na obrázku druhém. Všimněte si, že řezy nejsou umístěny v ekvidistantní vzdálenosti, ale tak, aby odpovídaly nastavenému zornému úhlu, který určuje perspektivu. V některých demech jsou vzdálenosti řezů předpočítány do tabulky, protože jejich výpočet vyžadoval dělení, které bylo na starších CPU (M68000, i80286, i80376) relativně pomalou operací. Dnes je použití tabulek v tomto případě spíše kontraproduktivní, neboť operace s pamětí jsou v důsledku zdlouhavější než dělení.

fractals50_2

Obrázek 2: Vykreslené horizonty (řezy) po přepočtu do promítací roviny

Alternativní metodou k metodě řezů je metoda sloupcově orientovaného raycastingu. Princip metody je poměrně jednoduchý: každým sloupcem obrazovky je veden paprsek směrem od pozorovatele do scény. Paprsek je samozřejmě při průletu výškovým polem „diskretizován“ pomocí Bresenhamova algoritmu či DDA algoritmu. Při každém posunu paprsku o jeden voxel (výšku uloženou ve výškovém poli) je vypočtena výška sloupce voxelů v tomto místě. Tato výška je posléze transformována na obrazovku. Průchod „diskretizovaného“ paprsku 3D terénem (výškovým polem) je zobrazený na třetím obrázku.

fractals50_3

Obrázek 3: Princip vykreslování terénu pomocí raycastingu

Podobně jako u předchozího algoritmu, i zde je zjištěno, zda je nejvyšší voxel tohoto sloupce viditelný. Používá se metoda plovoucího horizontu, která zde může být do značné míry zjednodušena na test, zda je nejvyšší voxel po transformaci umístěný nad všemi voxely vykreslenými v předcházejících krocích. Pokud je voxel nižší než již nakreslený sloupec, žádné vykreslení se neprovede, pokud je naopak umístěn výše, je sloupec pixelů mezi již nakreslenou částí terénu a novou pozicí vyplněn buď konstantní barvou nebo přechodem mezi dvěma barvami – to znamená, že ztrácíme informaci o terénu, který se nachází mezi dvěma vypočtenými vzorky. Pokud nastane situace, že vykreslovaný sloupec překročí výšku obrazovky, může být vykreslování tohoto sloupce ukončeno, protože v dalších krocích se stejně žádné pixely nemohou vykreslit. Výsledek použití této metody je zobrazen na čtvrtém obrázku (jedná se o technologické demo wgten).

fractals50_4

Obrázek 4: Terén vykreslený pomocí raycastingu

2. Naklánění a rotace

V mnoha demech i několika hrách byla použita buď metoda řezů nebo metoda sloupcově orientovaného raycastingu ve své základní podobě, kdy byl umožněn pohyb pozorovatele pouze se dvěma stupni volnosti – buď se jednalo o pohyb dopředu/dozadu/do­leva/doprava (demo Mars), nebo bylo možné pozorovatelem natáčet doprava a doleva. Metody naklánění nám umožní alespoň částečné zvětšení manévrovacích schopností (naklánění na bok) tak, jak to ukazuje hra Commanche nebo minule zmiňovaná Rescue On Fractalus. V následujících dvou kapitolách bude popsán pouze úvod do celé problematiky, více informací se můžete dozvědět například v diplomové práci Honzy Bulína (VUT Brno, FEI).

3. Naklánění posouváním sloupců obrazovky

Nejjednodušším a při programové implementaci i nejrychlejším způsobem, jakým je možné v uživateli navodit dojem natočení (náklonu) kolem osy pohledu, je výpočet celé scény bez natočení s tím, že se při finálním vykreslení na obrazovku sloupce v jedné polovině obrazovky zvýší (posunou směrem nahoru) a v druhé polovině obrazovky naopak sníží (posunou dolů). Míra posunu je samozřejmě závislá na vzdálenosti sloupce od osy pohledu. Předností této metody je značná rychlost, nevýhodou pak nemožnost otočení okolo celé osy (+-180°), náklon je možné reálně provádět maximálně o 15–20°.

fractals50_5

Obrázek 5: Horizont před a po provedení náklonu

Náklon nemůže být větší z toho důvodu, že je korektně proveden pouze pro vrcholy sloupců voxelů a nikoli pro všechny voxely, které se ve sloupci nachází. Pro malé úhly nejsou vizuální chyby velké, ale se vzrůstajícím úhlem se obrázek stane nerealistický. Ačkoli se tato metoda zdá primitivní a není matematicky čistá (rotace všech bodů je nahrazena jejich translací), je použita i v nejznámější aplikaci vizualizace krajiny pomocí voxelů – simulátoru vrtulníku Comanche firmy Novalogic.

4. Dvoufázové naklánění

Při použití dvoufázového naklánění je nejprve vypočtena scéna bez náklonu (stejně jako v předchozím příkladu) a následně je tato scéna použita jako textura, která je v druhém kroku výpočtu přenesena na obrazovku se správným natočením. Textura, která je v prvním kroku vytvořena, však musí mít větší počet sloupců než je počet sloupců obrazovky. Počet sloupců potřebný k natočení se vypočte podle vzorce:

PS=U×cos α

kde U je délka úhlopříčky stínítka (v pixelech) a α je úhel, který svírá úhlopříčka s nakloněnou krajinou. Maximální počet sloupců je tedy roven počtu pixelů úhlopříčky obrazovky s respektováním čtyř-sousednosti.

Nebylo by však možné provést pouze jednu fázi výpočtu, tj. vykreslování spolu s nakláněním? Ukazuje se, že to není ze dvou důvodů proveditelné:

Vzhledem k tomu, že výše popsané algoritmy pro vykreslování výškových polí (metoda řezů i metoda raycastingu) jsou orientovány sloupcově – obrazovka se vykresluje po svislých čarách – není možné provádět náklon při prvním průchodu mapou výšek, protože mapa výšek je tvořena sloupci voxelů, a z tohoto důvodu musí být tento sloupec vždy vykreslen do obrazovky svisle. Při vykreslování šikmé čáry by nebyly vykresleny všechny body rastru obrazovky a vznikala by hluchá místa.

fractals50_6

Obrázek 6: Problém vzniklý při jednofázovém náklonu

Při snaze vykreslovat obrazovku po sloupcích a zároveň provádět naklánění narazíme na další zásadní problém. Není možné zjistit, jaký nejvyšší voxel (z kterého sloupce voxelů) má být vykreslen pro daný sloupec obrazovky. Na šestém obrázku je demonstrován případ, kdy je vykreslován sloupec obrazovky S. Jeho poloha odpovídá sloupci voxelů SV1, jehož nejvyšší voxel V1 je však zcela mimo sloupec S a není proto započítán. Naopak by měl být započítán voxel V2 ležící na vrcholu SV2, jehož polohu však neznáme a nelze ji jednoduše vypočítat, protože povrch krajiny je vlnitý a cesta 2D mapou přes sloupce voxelů, jejichž nejvyšší voxely by měly být zobrazeny v sloupci S, není přímková (jde o obecnou křivku).

5. Vykreslování 3D terénů pomocí polygonů

V současnosti se trojrozměrné modely terény reprezentované pomocí výškových polí nejčastěji vykreslují pomocí polygonů. Výškové pole je převedeno buď na pravidelnou trojúhelníkovou síť (TRN – Triangular Regular Network) či na nepravidelnou trojúhelníkovou síť (TIN – Triangular Irregular Network). Oba typy trojúhelníkových sítí mají svůj význam, který bude vysvětlen v následujících odstavcích.

Pravidelné trojúhelníkové sítě jsou sestavené z trojúhelníků vytvořených takovým způsobem, že se při promítnutí této sítě do roviny x-y zobrazí mozaika složená ze shodných trojúhelníků (samotné trojúhelníky mají samozřejmě obecně různý tvar, musíme však brát v potaz pouze projekci do roviny). Převod na pravidelnou trojúhelníkovou síť je jednoduchý a přímočarý, protože se mezi každou čtveřici výšek vloží dvojice trojúhelníků. Výhoda tohoto typu trojúhelníkových sítí spočívá v triviálním převodu, jednoduchém výpočtu normálových vektorů u jednotlivých vrcholů (touto problematikou se budeme zabývat příště) a možnosti použití výškového pole jako primárního nositele informace o trojrozměrném modelu terénu.

fractals50_7

Obrázek 7: 3D povrch reprezentovaný pravidelnou trojúhelníkovou­ sítí

Nepravidelné trojúhelníkové sítě (TIN) jsou taktéž sestavené pomocí trojúhelníků, avšak tyto trojúhelníky mohou mít libovolný tvar a plochu. Jediné podmínky, které musí tato síť splňovat jsou dvě:

  1. Trojúhelníky se nesmí při promítnutí do roviny x-y překrývat.
  2. Sousední trojúhelníky musí mít shodnou jednu hranu a dva vrcholy.

První podmínka nám umožní použít některé speciální optimalizační metody, podmínka druhá pak zajistí bezešvost celého povrchu a také možnost paměťově méně náročného způsobu uložení – každý vrchol je i se svou normálou uložen v operační paměti jedenkrát, trojúhelníky obsahují pouze odkazy na vrcholy. Na osmém obrázku je zobrazena TIN síť vytvořená tak, že se v místě velkých změn povrchu použije větší množství trojúhelníků a na rovinách trojúhelníky o větší ploše a menší četnosti. Takové „adaptivní“ rozdělení povrchu na různě velké trojúhelníky představuje největší přednost tohoto způsobu popisu výškových polí, mezi nevýhody patří komplikované vytváření TIN.

fractals50_8

Obrázek 8: 3D povrch reprezentovaný nepravidelnou trojúhelníkovou­ sítí

6. Řešení viditelnosti a urychlení vykreslování

Vzhledem k tomu, že vykreslování trojrozměrného terénu je velmi často používaná činnost a samotný terén má specifické vlastnosti (spojitost apod.), bylo vyvinuto velké množství metod, které vedly k urychlení jeho vykreslování, tj. k redukci počtu trojúhelníků, které musí být poslány do grafického akcelerátoru. Musíme si uvědomit, že vzhledem ke specifickým vlastnostem terénu není možné s úspěchem použít obecné metody typu portálů (Descent, Quake) či BSP, proto je vývoj specializovaných metod ve své podstatě nutností. Dnes si popíšeme použití hierarchických bloků (aplikace LOD – Level Of Detail) a celou problematiku dokončíme v dalším pokračování tohoto seriálu.

7. Použití hierarchických bloků

Jedno z možných řešení problému rychlého vykreslování terénů představuje použití takzvaných hierarchických bloků, které se v některých ohledech podobají mipmapám použitým při texturování na grafických akcelerátorech. Aby byl tento systém reálně použitelný, je nutné po převodu výškového pole na polygony zkonstruovat hierarchické bloky pro jednotlivé úrovně detailů LOD a polygony uložit do těchto hierarchických bloků. V následujících odstavcích bude popsán způsob rozdělení původní rastrové mřížky na hierarchické bloky.

Na začátku převodu je zapotřebí provést rozhodnutí, kolik stupňů detailů se bude využívat, tj. kolik úrovní hierarchických bloků bude zkonstruováno. Je-li těchto úrovní málo, je pravděpodobné, že se bude muset stále zobrazovat velký počet detailů, protože nebude k dispozici blok nižší úrovně, který by se v dané situaci dal použít. Představme si například situaci, že máme ve vytvořeném terénu velkou rovinu, která by se dala zobrazit pomocí jednoho velikého bloku složeného z malého množství polygonů s poměrně velkou plochou. Pokud tento velký blok už není součástí vybudované úrovně detailů, bude se muset nahradit větším počtem menších bloků, čímž však naroste počet vykreslovaných plošek, které mají mnohdy zbytečně malou plochu (plochu polygonu je vždy nutné vztahovat k rozlišení obrazovky a nastavení kamery/pozoro­vatele).

Na druhou stranu není optimální ani příliš velký počet úrovní. V takovém případě jsme sice schopni velké plochy bez detailů nahradit jedním blokem s malým počtem polygonů, ale ve většině zobrazovaných výškových map nenastane situace, že by se tak malé detaily daly použít. Při velkém počtu úrovní detailů je tu pak ještě problém s větší paměťovou náročností a současně také s výpočetní složitostí (v určitém momentě dokonce převáží výpočetní náročnost dobu vykreslování scény, která není uložena hierarchicky). Při hledání odpovídající úrovně detailu pro danou část terénu se zpracování vždy začíná od nejnižších detailů a postupně se přechází k detailům vyšším do té chvíle, kdy se nalezne úroveň dostačující.

Bude-li tedy těchto úrovní vytvořeno příliš mnoho, bude se při vykreslování provádět test nejprve pro veliké bloky, které třeba nikdy ani nebudou použity. Proto je tento test z hlediska vykreslování celé scény redundantní a bloky s tak malými detaily pouze představují zátěž a žádný výkonnostní zisk. Zjistili jsme, že pro běžná výšková pole je optimální použít maximálně 4–6 úrovní detailů. Velikost hierarchických bloků pro šest nejvyšších úrovní detailů je uvedena v následující tabulce:

Úroveň detailů Velikost bloku
1 1×1
2 2×2
3 4×4
4 8×8
5 16×16
6 32×32

Aby bylo možno použít výše zmíněnou hierarchii bloků pro tvorbu více úrovní detailů, je třeba klást i jeden specifický požadavek na rozměr výškové mapy. Ten nemůže být libovolný, ale je třeba, aby měl rozměr:

R=2N+1

a současně musí platit, že hodnota 2N je větší než velikost největšího bloku:

2N>=2LODmax

Při praktické aplikaci hierarchie bloků v operační paměti počítače je zapotřebí mít na zřeteli, že jednotlivé bloky spolu budou muset při vykreslování navzájem jistým způsobem „komunikovat“. A to nejen sousední bloky se stejnou úrovní detailu, ale i bloky, které mají úrovně detailu odlišné. Je proto důležité dobře navrhnout způsob uložení hierarchie bloků v operační paměti počítače.

Jelikož jsou všechny bloky reprezentovány ekvivalentní datovou strukturou, je možné jejich uložení do jednoho staticky či dynamicky vytvořeného pole. V tomto poli budou bloky seřazeny po sloupcích tak, že na začátku budou bloky představující úroveň detailů 1. Bloky s úrovní detailů 0 není třeba vytvářet, protože v hierarchii jsou na nejnižší úrovni a jejich vykreslení není limitováno žádnou vzdáleností; naopak jsou vykresleny pouze v nejhorším případě. Je-li třeba použít bloky s úrovní detailů 0, postarají se o jejich vykreslení nejbližší bloky s úrovní 1.

V operační paměti musí být uloženy také indexy do pole, na kterých jsou uloženy první bloky každé úrovně, počet jednotlivých bloků a informace o počtu bloků každé úrovně, které leží na jednom řádku v rastru. Pokud uvažujeme, že jsou data výškového pole uložena v úrovních 0–5 a rozměr výškové mapy je 513×513 bodů (viz dva předchozí vzorce), bude uložení bloků v operační paměti vypadat tak, jak je naznačeno v další tabulce:

Úroveň detailů (LOD) Počet bloků Index prvního bloku Počet bloků na řádku
0 není zastoupen
1 65536 0 256
2 16384 65536 128
3 4096 16384 64
4 1024 4096 32
5 256 1024 16

Při určování toho, s jakými detaily se mají bloky vykreslit, je nezbytné, aby tyto mohly mezi sebou vzájemně komunikovat. O jaký typ komunikace se jedná, bude zmíněno později. V této části je ukázáno, jak lze indexovat sousední bloky při použití paměťové reprezentace, jež byla zmíněna v předešlých odstavcích.

Každý blok potřebuje znát své nejbližší sousedy: levého, pravého, horního, dolního. Levý soused leží v poli bloků na indexu mindex-1. Pravý soused obdobně na indexu mindex+1. Dolní soused pak bude ležet na mIndex+pocet_blo­ku_na_radku, podobně horní soused na indexu rovném mIndex-pocet_bloku_na_rad­ku. Všechny indexy sousedních bloků jsou přehledně vypsány v tabulce:

Soused Index
levý mindex-1
pravý mindex+1
horní mIndex-pocet_bloku_na_rad­ku
dolní mIndex+pocet_blo­ku_na_radku

Dále musí každý blok znát indexy svých podbloků, tedy těch bloků, které tvoří o jednu úroveň přesnější detaily a číslo jejich úrovně je rovno mLOD-1. Je zřejmé, že každý blok v hierarchické struktuře (nejedná-li se o blok nulté úrovně) má čtyři podbloky. Počáteční index bloků (všechny údaje budiž chápány z pohledu bloku na úrovni mLOD) tvořících úroveň mLOD-1 je roven mBlockStartIn­dex[m_LOD-1].

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

V následující části tohoto seriálu navážeme na problematiku LOD a ukážeme si, jakým způsobem je možné volit různé úrovně detailů při vykreslování. Také se zmíníme o výpočtu normálových vektorů jednotlivých trojúhelníků, resp. normálových vektorů vrcholů trojúhelníků (což je sice geometrický nesmysl, ale z hlediska počítačové grafiky často používaný pojem).

Našli jste v článku chybu?

13. 10. 2006 13:09

Alim (neregistrovaný)
Používám vlastní algoritmus generující nejprve spojnice a to takovým způsobem, že když se 2 spojnice protínají nechá vždy tu kratší, takže ve výsledku vznikne TIN, která má nejkratší možné hrany trojúhelníků. Je možné zadat i některé spojnice jako pevné, které budou zachovány a všechny ostatní co je protnou budou zrušeny bez ohledu na délku.

Na reálných datech jsem to právě testoval. Data pro celou ČR nemám, ale zase záleží na tom kolik tam těch bodů bude (jak daleko od sebe budou) já zatim pou…

10. 10. 2006 17:23

Můžu se zeptat, jaký používáte algoritmus pro triangulaci? Nějaký vlastní nebo něco známého (inkrementální, radial sweep apod.)? Přepdokládám, že půjde o postup vytvářející nejdříve neoptimální TIN a posléze provádějící optimalizaci. Zkuste to pustit na reálných datech, třeba síť ČR , pod hodinu byste se měl vejít.
Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

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

Taky věříte na pravidlo 5 sekund?

DigiZone.cz: TV Philips a Android verze 6.0

TV Philips a Android verze 6.0

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

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

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

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

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

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: Potvrzeno: Pobyt v lese je skvělý na imunitu

Potvrzeno: Pobyt v lese je skvělý na imunitu

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

Jak vymáhat výživné zadarmo?

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

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

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

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

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

mBank cenzuruje, zrušila mFórum

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

Na ucho teplý, nebo studený obklad?

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

Jmenuje se Janina a žije bez cukru

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č?

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

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