Diamond-square algorithm, Minecraft

Metód pre vykreslenie terénu je niekoľko, avšak oveľa viac metód prináleží optimalizačným metódam terénu, než samotným algoritmom vykreslenia terénu. Určitý typ vykreslenia terénu je špecifický svojím vzhľadom.

Štandardné vykreslenie trojuholníkovej polygonálnej siete diamond-square algoritmom krajinného terénneho typu vyzerá nasledovne. Jedná sa o projekt realizovaný cudzím autorom v C# Unity. (GIT: https://github.com/mtt-git/diamond-square-terrain-unity)

Zobrazenie 3D terénu algoritmom Diamond-Square v Unity

Veľmi podobne by vyzeral terén s štvorcovými plôškami (Face), ktoré by síce tiež obsahovali trojuholník, ale vo výsledku by bola celková sieť štvorcového typu uhlopriečkou poziciovanou v rovnakom smere ako všetky ostatné uhlopriečky v teréne.

Na vykreslenie terénu sa používa tzv. height mapa, výšková mapa. Je to štandardný pojem z kartografie, ktorý definuje hodnoty s úrovňou hladiny nadmorskej výšky. Je možné si to predstaviť ako obyčajný súbor s číslami oddelenými medzerami. Každé číslo reprezentuje kolmú súradnicu vzhľadom k rovine premietania. Samo o sebe to nestačí na vykreslenie celkového terénu, ale je to metóda, ktorá umožňuje definovať tvar, reliéf terénu. Často sa používa namiesto textového súboru s diskrétnymi číslami priamo obrázok, ktorý obsahuje pixely reprezentujúce číselné zobrazenie farby v odtieňoch červenej farby, zelenej farby, modrej farby a niekedy ešte pridaný priehľadný kanál (R,G,B,A).

Heightmapa

Toto je klasický obrázok reprezentovaný ako height mapa. Môže byť aj farebná, ale kvôli jednoduchosti odčítania lineárnej úrovne sa odporúča obrázok v odtieni šedej farby. Takto predložený obrázok potom korešponduje s vykresleným terénom v 3D priestore.

3D model reprezentovaný height mapou

Úrovne je možné definovať svojvoľne, avšak konkrétne je definovaná absolútne čierna farba ako najnižšia hodnota úrovne terénu a absolútne biela farba ako najvyššia hodnota úrovne terénu.

Hra Minecraft používa rovnaký systém generovania terénu, krajiny, avšak práve táto hra používa plne algoritmus Diamond-Square.

Hra Minecraft

Ako je možné vidieť z hry Minecraft, krajina, terén, je generovaný na základe určitých "skokov", diskrétnych výškových úrovní.

Modifikáciou algoritmu Diamond-Square je možné získať rôzne podoby terénu. Často sa používa tento algoritmus v spojitosti s mnohými inými algoritmami z oblasti spracovania obrazu, napr. tzv. Delaunayová triangulácia. Všetky tieto metódy nejakým spôsobom optimalizujú polygónovú sieť, to znamená "preskupujú" jednotlivé hrany v štvorci (Face) nejakým vhodným spôsobom.

Zobrazenie 3D terénu algoritmom Diamond-Square s nižším rozlíšením terénu v C/C++ a knižnici OpenGL

Takže z takého terénu je možné nastavením algoritmu Diamond-Square vygenerovať detailnejší terén. Tento obrázok vznikol z projektu, kde určitý autor nedodal kompletné zdrojové kódy, takže som si musel vystačiť len s autorovými obrázkami. Jedná sa o projekt s použitím knižnice OpenGL.

Zobrazenie 3D terénu algoritmom Diamond-Square s vyšším rozlíšením terénu v C/C++ a knižnici OpenGL

Inou modifikáciou je možné definovať terén v pravouhlom ponímaní tak, ako je to repezentované v hre Minecraft. Tento projekt je od autora, ktorý to naprogramoval v jazyku C/C++ a grafickej knižnici SDL3. Podarilo sa mi to skompilovať a upraviť kód na niektoré typizované výstupy s úpravou základného ovládania obrazu. (GIT: https://github.com/mtt-git/diamond-square-terrain-sdl)

Zobrazenie 3D terénu algoritmom Diamond-Square s menšou mapou terénu v C/C++ a knižnici SDL

Pre celkové zobrazenie terénu by vyzeral výsledný obraz nasledovne.

Zobrazenie 3D terénu algoritmom Diamond-Square s väčšou mapou terénu v C/C++ a knižnici SDL

Tento program je naprogramovaný tak, že nepoužíva na vykreslenie atomickej štruktúry plôšky trojuholník, ale štvorec, teda je generovaný rovnakým spôsobom ako predchádzajúci projekt v inom článku na tomto webe pod názvom "Square Tile". To znamená, že jednotlivé plôšky (Face) sú vykresľované len spojením štandardnej čiary, úsečky, typu SDL funkcie SDL_RenderDrawLine() a žiadnych ďalších konštrukcií. Teda, v reálnom praktickom použití sa tento spôsob vykresľovania nepoužíva, pretože na optimálne vykresľovanie sa používajú grafické priemyselné štandardy DirectX alebo OpenGL.

Vo všeobecnosti je možné aplikovať algoritmus Diamond Square na rôzne problémy vykreslenia terénu, resp. vykreslenie terénu nejakým špecifickým spôsobom. Vykreslenie jednotlivých plôšok bude správne vykreslené v prípade nízkoúrovňového polygónového vykreslenia, tzv. LOW POLY vykreslenia ako aj v prípade vysokoúrovňového polygónového vykreslenia, tzv. HIGH POLY vykreslenia. To znamená, že v jednom prípade bude figurovať menší počet trojuholníkov v celkovej polygónovej sieti a v druhom prípade bude figurovať väčší počet trojuholníkov v celkovej polygónovej sieti. Jednotlivé "zaoblenia" terénu, teda styk medzi jednotlivými plôškami môže byť buď spojitý alebo nespojitý. V prípade spojitého styku nezáleží na zoskupení jednotlivých trojuholníkových sietí, pretože vo výsledku bude obraz "rovnomerného typu", teda bez nejakých deformít, nezrovnalostí. Medzi jednotlivými plôškami bude figurovať spojitý prechod, to znamená, že čísla vertexov, vrcholov budú reprezentované priamo "vedľa seba", napr. k číslu jedného vertexu s hodnotou 0.1, bude druhý začínať tiež presne v čísle 0.1, ďalší v napr. 0.2, 0.3 a podobne.

V prípade nespojitého styku bude situácia zaujímavejšia a svojím spôsobom variabilnejšia, čo sa týka možností zobrazenia, vykreslenia. Jednou možnosťou nespojitého zobrazenia je práve systémom algoritmu Diamond Square, kedy jednotlivé prechody medzi jednotlivými plôškami sú dimenzované na báze priameho nespojitého vykreslenia, teda napr. k číslu jedného vertexu s hodnotou 0.1, bude druhý začínať v napr. hodnote 1.1 a postupne 2.1, 3.1 a podobne.

Ak uvážime fakt, že chceme vykresľovať len na báze trojuholníkov, teda defacto spôsobom, ktorý moderná počítačová grafika umožňuje, tak je nutné riešiť určité "hraničné" problémy v zobrazení jednotlivých trojuholníkov. Určitým špecifickým spôsobom zobrazenia je zobrazenie terénu v počítačovej hre z roku 1994 s názvom Transport Tycoon od autora Chrisa Sawyera.

Hra Transport Tycoon

Ako je možné vidieť terén, jednotlivé plôšky sú generované podobne ako pri algoritme Diamond-Square, avšak nie je to priamo tento algoritmus a ani jeho upravená špecificita, pretože algoritmus Diamond-Square nerieši priamo dispozície uhlopriečkových hrán v jednotlivých plôškach. Konkrétne v hre Transport Tycoon nie sú použité 3D prvky, pretože v roku 1994 ešte neexistovali priemyselné grafické štandardy typu DirectX/OpenGL a aj keď to softwérovým spôsobom bolo možné realizovať, veľa herných spoločností to realizovali na báze 2D zobrazenia, ktoré simulovalo 3D zobrazenie. To znamená, že jednotlivé terénne prevýšenia boli koncipované ako klasické predpripravené obrázky, ktoré sa menili na základe používateľskej interakcie s terénom. Takže hra Transport Tycoon síce nebola priamo 3D, ale idea zobrazovania terénu v takto špecifickom rozpoložení je zaujímavým dispozičným prvkom v tvorbe krajinných terénných zobrazení.

Postupne v niektorých ďalších článkoch budem prezentovať jednotlivé fázy tvorby práve takto koncipovaného typu terénu.