Hlavní navigace

Trojrozměrné modely terénu

Pavel Tišnovský 3. 10. 2006

V dnešním článku o fraktálech si ukážeme, jakým způsobem se prakticky vytváří a zobrazují modely krajiny pomocí obrázků plasmy, a to jak plasmy generované metodou náhodného přesouvání prostředního bodu, tak i plasmy vytvořené spektrální syntézou. Začneme výkladem tradičních metod a skončíme u postupů založených na vykreslování polygonů.

Obsah

1. Použití obrázků plasmy pro tvorbu 3D terénů
2. Základní informace o výškových polích
3. Výšková pole jako speciální případ objemové reprezentace
4. Vykreslování výškových polí pomocí řezů
5. Předpočítání řezů
6. Obarvení terénu – dvourozměrné textury
7. Obarvení terénu – prostorové textury
8. Literatura a odkazy na Internetu
9. Obsah dalšího pokračování tohoto seriálu

1. Použití obrázků plasmy pro tvorbu 3D terénů

The drawing of landscapes by computers was one of the first artistic uses envisaged for fractals. Mandelbrot has made some studies and several authors have written programs and have obtained spectacular results. Fractal landscapes have been used, for example, in Star Trek II. One of the most known creator is Ken Musgrave who worked first with Mandelbrot. This topic is generally named „fractal terrains“. The use of fractals is obvious in this field because, if you travel or zoom in such a landscape it will show more and more details owing to its fractal structure.
Fractal FAQ

V několika minulých částech tohoto seriálu jsme si ukázali, jakým způsobem je možné vytvářet obrázky plasmy pomocí různých metod. Jednalo se zejména o metodu náhodného přesouvání prostředního bodu (Midpoint Displacement Method) a metodu spektrální syntézy (Spectral Synthesis). V dnešní části si ukážeme, jakým způsobem je možné takto získané obrázky plasmy použít pro vytvoření a následné vykreslení trojrozměrného modelu terénu. Jak již naznačilo motto první kapitoly, fraktální metody v minulosti byly a dodnes jsou prakticky jedinou úspěšně používanou metodu pro vytváření modelů krajin.

Nejprve si řekneme, jaký význam mají pro počítačovou grafiku výšková pole (height fields), včetně jejich vztahu k rastrově orientovanému vyjádření objemů těles pomocí voxelů. Obrázky plasmy je možné považovat za výšková pole uložená ve formě bitmap. Dále si ukážeme některé tradiční způsoby vykreslování výškových polí (známé například z mnoha dem i několika velmi úspěšných počítačových her) a následně si řekneme, jak je možné výšková pole převést na plošné polygony a ty následně otexturovat a vykreslit pomocí dnes běžných grafických akcelerátorů.

fractals49_1

Obrázek 1: Model 3D terénu vzniklý použitím obrázku plasmy jako výškového pole, druhý obrázek plasmy tvoří oblohu (autor Honza Bulín)

2. Základní informace o výškových polích

All successful synthetic terrain models for computer graphics are fractal: That is, they feature complexity resulting from the repetition of form over a variety of scales.
Ken Musgrave

Výšková pole (heightfield, height-field) představují ve své podstatě velmi specifický druh pravidelných trojúhelníkových sítí (TRN – triangular regular network). Tato pole jsou většinou použita pro úspornou reprezentaci části zemského povrchu nebo povrchu jiné (fiktivní) planety, u kterého neuvažujeme zaoblení, tj. danou planetu považujeme za „placku“, což však přináší pouze zanedbatelné chyby, která se u dnes používaných rozlišení pohybuje v řádu sotva jednoho či dvou pixelů.

fractals49_2

Obrázek 2: Obrázek plasmy chápaný jako výškové pole s barevně zvýrazněnými výškami ve stylu map (vytvořeno v programu FractInt)

Výšková pole přináší oproti obecné trojúhelníkové síti jedno zásadní, ale relativně snadno splnitelné omezení – jednotlivé trojúhelníky se nesmí po projekci do roviny x-y překrývat (při reprezentaci zemského nebo mimozemského povrchu jsou osy x a y orientovány vodorovně, kdežto osa z svisle vzhůru). Toto omezení však na druhou stranu přináší možnost reprezentace povrchu pomocí výšek uložených v pravidelné rastrové mřížce (bitmapě, pixmapě), což je výhodné především z hlediska značně snížených paměťových nároků, ale, jak si ukážeme v dalším textu, i z hlediska rychlosti vykreslování. I přes dnešní výraznou dominanci polygonových modelů trojrozměrných těles se výšková pole pro svoje dobré vlastnosti stále používají.

fractals49_3

Obrázek 3: Výškové pole z obrázku 2 promítnuté do 3D prostoru – drátový model (vytvořeno v programu FractInt)

Převod výškových dat do rastrové mřížky je proveden diskretizací souřadnic ve směru všech tří souřadných os (v každé ose je možné provést diskretizaci s jiným krokem) a uložením výšek, tj. z-ových souřadnic do rastrové mřížky, kterou lze považovat za bitmapu, ve které hodnota každého pixelu neodpovídá barvě, ale výšce z předem zadaného rozsahu (použitím barev a textur se budeme zabývat v následujících kapitolách). Výšková pole bývají na externích datových médiích uložena většinou v některém bitmapovém formátu, například BMP, PNG či TGA, čímž je umožněn jejich snadný přenos do jiných systémů a aplikací, zejména do GIS systémů a renderovacích programů typu POVRay. V případě, že se výšková mapa generuje přímo z obrázku plasmy, je samozřejmě možné diskretizaci (v tomto případě spíše pouhé převzorkování) vynechat, a to za předpokladu, že rozlišení plasmy bude odpovídat požadovanému rozlišení výškové mapy, tj. počtu uložených výšek v obou směrech.

fractals49_4

Obrázek 4: Výškové pole z obrázku 2 zobrazené metodou zpětného sledování paprsku (vytvořeno v programu POVRay)

Na obrázcích 4 až 7 je zobrazeno výškové pole vzniklé z plasmy (obrázek 2). Obrázky jsou vykresleny metodou zpětného sledování paprsku (raytracing) ve známém programu POVRay, kterým se na stránkách Roota také budeme zabývat. Na pátém obrázku je do modelu krajiny přidána i mořská hladina, což je ve skutečnosti rovina, která zakrývá nejnižší místa krajiny. Jak dramaticky se celý obraz krajiny změní pouhou změnou hladiny, dokládá šestý obrázek. Na sedmém obrázku je pro změnu na krajinu nanesena textura připomínající barvy použité v některých tematických mapách.

fractals49_5

Obrázek 5: Úprava předchozí scény přidáním roviny reprezentující mořskou hladinu (vytvořeno v programu POVRay)

3. Výšková pole jako speciální případ objemové reprezentace

Výškové mapy můžeme z jiného pohledu považovat za speciální případ reprezentace trojrozměrné scény pomocí objemových elementů, neboli voxelů. Voxely se začínají stále více používat ve specializovaných aplikacích, zejména medicíně; jejich dalšímu rozšíření brání především praktická neexistence vhodných grafických akcelerátorů (kromě Volume Pro). Jejich největší nevýhodou jsou však velké nároky na paměť, protože celý trojrozměrný model musí být rozdělen na elementární krychle (voxely), podobně jako při rastrování obrázku při převodu do bitmapové (rastrové) reprezentace pomocí pixelů.

fractals49_6

Obrázek 6: Změna hladiny oproti obrázku číslo 5 (vytvořeno v programu POVRay)

Výšková mapa jakožto speciální případ voxelového modelu, je z programátorského pohledu datová struktura reprezentující výšku sloupce voxelů, tj. počet „plných“ voxelů ležících nad sebou. Vzhledem k tomuto zjednodušení se nemohou ve výškové mapě vyskytovat některé krajinné útvary, které vyžadují přerušení sloupce voxelů. Jedná se zejména o různé skalní převisy a jeskyně. Pokud se s tímto omezením smíříme (což v 99% případů můžeme udělat), představuje výšková mapa ideální datovou strukturu pro popis povrchu, která v sobě spojuje značnou jednoduchost voxelového vyjádření a paměťovou nenáročnost vyjádření pomocí polygonů či nepravidelné trojúhelníkové sítě (TIN – Triangular Irregular Network).

fractals49_7

Obrázek 7: Nanesení textury připomínající tematické mapy (vytvořeno v programu POVRay)

4. Vykreslování výškových polí pomocí řezů

Patrně nejstarší technikou použitou pro vykreslování výškových polí, je zobrazování řezů (slices) – viz osmý a devátý obrázek. Řezy jsou ve výškovém poli vedeny tak, aby po promítnutí na obrazovku vytvořily horizonty kolmé na obrazovku. 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. Pro určení viditelnosti jednotlivých řezů a jejich částí se používala metoda plovoucího horizontu, při které se vykreslování provádělo od pozorovatele směrem do vzdálenějších prostor scény a pro každý sloupec pixelů na obrazovce se pamatovala minimální a zejména maximální vykreslená výška.

fractals49_8

Obrázek 8: Zobrazení výškového pole pomocí řezů

Povšimněte si, že se jedná o přesný opak klasického a dodnes často používaného malířova algoritmu (painter's al­gorithm), při kterém se naopak provádí překreslování směrem od nejvzdálenějších objektů k objektům nejbližším pozorovateli. Speciální vlastnosti výškových polí (zejména jejich spojitost a fakt, že se v poli nemohou nacházet body ležící nad sebou) nám však umožňují provést výše popsanou optimalizaci, která zcela zásadním způsobem zjednodušuje a současně i urychluje vykreslování.

fractals49_9

Obrázek 9: Kombinace řezů výškového pole s jeho zobrazením dalšími technikami

Urychlení vykreslování výškových polí pomocí řezů je natolik zřetelné, že se metoda řezů (i když značně modifikovaná) objevila ve známé hře Rescue On Fractalus, která byla firmou LucasFilm vytvořena v roce 1985 pro některé typy osmibitových počítačů, jakými jsou Atari 5200, Atari 800XL a Commodore C64. Je až neuvěřitelné, že se na osmibitových mikroprocesorech taktovaných pod 2MHz dala vykreslovat grafika systémem, jehož funkční obdoba se objevila až o mnoho let později na mnohem silnějších strojích (80286 16MHz). Použitý engine umožňoval, aby se nad trojrozměrným povrchem planety vznášela loď ovladatelná se šesti stupni volnosti, mnohé pozdější enginy buď nepovolovaly náklon a/nebo otáčení (demo Mars).

fractals49_a

Obrázek 10: Hra Rescue On Fractalus na počítači Atari 800XL

fractals49_b

Obrázek 11: Použitý engine umožňoval pohyb se šesti stupni volnosti (viz umělý horizont a kompas)

5. Předpočítání řezů

Metoda, při které je použito předpočítání řezů, může značným způsobem urychlit vykreslování, zejména na platformách s relativně pomalým CPU a přitom rychlým přístupem do paměti. Na druhou stranu se jedná o metodu, která je značně náročná na paměť, a to i při pouhém předpočítání řezů v jednom směru. Ve skutečnosti není praktické udržovat v pomocných tabulkách všechny variace řezů pro všechna možná natočení ve všech místech mapy (přinejmenším neznám žádnou aplikaci, která by toto předpočítání prováděla).

Z tohoto důvodu se v některých programech používají různá zjednodušení, například je povolen pohyb pouze v kolmých směrech (S-J) a (Z-V), čímž je možné počet položek uložených v pomocných tabulkách výrazným způsobem snížit. Tuto techniku používá například slavné demo Mars, ve kterém se uživatel může pohybovat pouze dopředu, dozadu, doprava a doleva bez možnosti natáčení a náklonu. Počet řezů je v tomto demu relativně malý, ale vzhledem k chytře vyřešené změně výšky kamery v závislosti na povrchu se toto zjednodušení výrazněji neprojevuje.

fractals49_c

Obrázek 12: Screenshot ze známého dema Mars

6. Obarvení terénu – dvourozměrné textury

Při obarvování vykreslovaného trojrozměrného povrchu se velmi často používají dvourozměrné textury, zejména v případě, že je vykreslování prováděno pomocí grafického akcelerátoru. Tyto textury mohou být dvojího typu. Buď se jedná o textury, které pokrývají celý povrch, tj. jejich rozlišení odpovídá rozlišení výškového pole (ve skutečnosti jde o obdobu leteckých snímků), nebo se jedná o textury o menším rozlišení, které se dají na povrch aplikovat opakovaně. Může se jednat například o tématické textury s motivy trávy, štěrku, písku, vody apod.

Pomocí těchto textur je možné dosáhnout znatelného snížení paměťové náročnosti a mnohdy i zvýšení kvality zobrazení, protože textura může po svém namapování na zobrazovaný povrch obsahovat více pixelů ležících v jednom původním voxelu, tj. v obrázku může být zobrazeno více detailů. Jediným problémem, který je nutné řešit, je vzájemné navazování textur, aby nebyl patrný přechod od jedné textury k textuře druhé. Tento problém se řeší různými způsoby, nejčastěji lineární interpolací barev pixelů (resp. texelů) ležících na okrajích obou textur.

fractals49_d

Obrázek 13: Dvourozměrná textura pokrývající větší část povrchu

7. Obarvení terénu – prostorové textury

Prostorové textury představují významné rozšíření původních dvourozměrných textur. Tyto textury jsou vlastně tvořeny voxely, z nichž každému voxelu je přiřazena určitá barva odpovídající barvě v daném místě prostoru. Tyto textury si také můžeme představit jako hranol vytvořený z nějakého materiálu, ze kterého se obráběním vytváří určitý předmět (představme si například dřevěný hranol s výraznými letokruhy). Barva povrchu tohoto předmětu v nějakém místě bude záviset na barvě voxelu z původního hranolu.

Pro potřebu vykreslování trojrozměrných modelů terénu je vhodné použít prostorovou texturu tvořenou několika vrstvami, kde každá vrstva představuje normální dvourozměrnou texturu, která je pro jednoduchost čtvercová. Výsledná prostorová textura má rozměry U×U×H, kde U je rozměr dvourozměrné textury a H je počet těchto textur nad sebou, tj. počet vrstev. Příklad prostorové textury s rozlišením 64×64×32 voxelů je zobrazen na dalším obrázku. Vidíme, že každá vrstva obsahuje jednu tematickou texturu nebo postupný přechod mezi dvěma tematickými texturami. Přímé mapování této textury (která se ve vodorovném směru opakuje) nám tedy umožňuje jednoduše vykreslit reálně vypadající povrch bez nutnosti výpočtů interpolace barev pixelů, jak tomu bylo u dvourozměrných textur.

fractals49_e

Obrázek 14: Ukázka trojrozměrné textury

8. Literatura a odkazy na Internetu

  1. Calahan R.F. a Joseph J.H: „Fractal statistics of cloud fields“,
    Mon. Wea.Rev. 117, 261–272, 1989
  2. Calahan R.F. a kol.: „The albedo of fractal stratocumulus clouds“,
    Sci. 51, 2434–2455, 1994
  3. Mandelbrot Benoit: „Fractal Landscapes without creases and with rivers“,
    The Science of Fractal Images, ed. Heinz-Otto Peitgen, Dietmar Saupe; Springer-Verlag (1988) pp 243–260
  4. Wikipedia: „Fractal Landscape“,
    http://en.wiki­pedia.org/wiki/Frac­tal_landscape
  5. Bourke Paul: "Fractal Landscapes (for midpoint displacement),
    http://local.was­p.uwa.edu.au/~pbou­rke/modelling/frachi­ll/
  6. Bourke Paul: „Frequency Synthesis of Landscapes (and clouds)“,
    http://local.was­p.uwa.edu.au/~pbou­rke/modelling/freq­land/
  7. Martz Paul: „Generating Random Fractal Terrain“,
    http://www.ga­meprogrammer.com/frac­tal.html
  8. Musgrave Ken: Building Fractal Planets,
    http://www.wi­zardnet.com/mus­grave/article­.html
  9. Jorgensen Eric: Generating Terrain,
    http://www.ge­ocities.com/A­rea51/6902/te­rrain.html
  10. Cahalan Robert F.: Fractal Clouds Reference by ,
    http://climate­.gsfc.nasa.gov/~ca­halan/Fractal­Clouds/Fractal­Clouds.html
  11. Terragen – photorealistic scenery rendering software,
    http://www.pla­netside.co.uk/te­rragen/
  12. MDTerrain – a Terrain Generator (psaný v C++ a OpenGL),
    http://www.em­bege.com/frac­tals/mdterrain/
  13. The Center for the Computation and Visualization of Geometric Structures (obrázky fraktálních oblaků),
    http://www.ge­om.umn.edu/grap­hics/pix/Gene­ral_Interest/Frac­tals/
  14. Gforge and Landscapes (John Beale),
    http://www.bes­t.com/~beale/
  15. Ter Screenshots (program pro Linux),
    http://www.pen­guintown.net/Grap­hics/ter/
  16. Plasma effect (Wikipedia),
    http://en.wiki­pedia.org/wiki/Plas­ma_effect
  17. Rescue on Fractalus (Wikipedia),
    http://en.wiki­pedia.org/wiki/Res­cue_On_Fracta­lus
  18. Žára J., Beneš B., Felkel P.: „Moderní počítačová grafika“,
    Computer Press, Praha, 1998, ISBN 80–7226–049–9
  19. Žára J., Limpouch A., Beneš B., Werner T.: „Počítačová grafika – principy a algoritmy“,
    Grada, 1992
  20. Sharman, J: „How to render landscapes“
  21. Bulín Jan: „Vykreslování výškových map“,
    Ročníkový projekt, VUT Brno, FEI, 1998

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

V následujícím pokračování tohoto seriálu si ukážeme vykreslovací metodu pro výšková pole založenou na sloupcově orientovaném vrhání paprsku (raycastingu). Také si řekneme, jak se výšková pole vykreslují na běžných grafických akcelerátorech, včetně popisu různě složitých a účinných urychlovacích me­tod.

Našli jste v článku chybu?

12. 10. 2006 20:34

Dee (neregistrovaný)
Uz jsem nenasel zdrojak, ale staci disassemblovat
http://pouet.net/prod.php?which=1843
Asi jsem do tech 60 nepocital nastaveni modu a esc. Vzniklo to tak ze kamos napsal na 200 modrou vlnici se placku a chtel ji releasnout; mne to nedalo a do mista kde pocita barvu pixelu jsem bez jakychkoliv uprav cut&pastnul svuj kod na animovanou julii. Vim ze to pak melo jeste slabe nad 256. Zajimay je ze po onom brutalnim cut&paste julie se na placce rozvlnil mandelbrot :) (stacilo nekde prohodit re…

9. 10. 2006 9:13

To me docela zajima. Vzhledem k tomu, ze jen nahozeni grafickeho rezimu, na konci cekani na stisk klavesy, zhozeni grafickeho rezimu a navrat do DOSu (retn, ne int) zabere 15 bytu, tak je to stlaceni na 45 bytu dost dobre (dalsich sest bytu pro nastaveni ukazatele do obrazove pameti, i kdyz mozna vynulovani DI neni potrebne).
Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

Lupa.cz: Slevové šílenství je tu. Kde nakoupit na Black Friday?

Slevové šílenství je tu. Kde nakoupit na Black Friday?

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

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

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

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

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

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

Lupa.cz: Babiš: E-shopů se EET možná nebude týkat

Babiš: E-shopů se EET možná nebude týkat

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Lupa.cz: Není sleva jako sleva. Jak obchodům nenaletět?

Není sleva jako sleva. Jak obchodům nenaletět?