RACU N A L NI STVO
Proceduralno generiranje terena s prelomnim algoritmom
Marko Jovčeski Uvod
Gotovo ste se kdaj ob igranju katere od strateških iger vprašali, na kakšen nacin se vsakic ustvari nova igralna površina. Kako bi se vi lotili generiranja pokrajine?
Z razvojem računalniške grafike se je porodila potreba po hitrem generiranju vsebin, kar bi poenostavilo dolgotrajnost in zahtevnost ročnega modeliranja. V ta namen se je razvilo proceduralno generiranje vsebin, ki algoritmično ustvarja podatke. Pomemben del tega področja predstavlja proceduralno modeliranje, ki vkljucuje algoritme za nakljucno generiranje trirazsežnostnih modelov. Sem spada proceduralno generiranje terena, ki z uporabo algoritmov modelira pokrajine za uporabo v racunalniški grafiki in animaciji, filmski industriji in tudi na drugih podrocjih, kot so geologija, geografija in inženir -stvo [1-4].
Eden od možnih pristopov h generiranju terena je uporaba funkcije dveh spremenljivk, katere graf je ploskev v trirazsežnem prostoru. Vendar se tak pristop navadno ne uporablja, saj so takšne funkcije težko izracunljive, niso dovolj nakljucne in njihovi grafi niso podobni pokrajinam v naravi.
V nadaljevanju bomo predstavili enega od možnih pristopov k nakljucnemu modeliranju terena z upo-
rabo fraktalnega algoritma. Nastala fraktalna površina bo predstavljala želeni nakljucni teren. Zaradi fraktalnih lastnosti narave se izkaže uporaba takšnega algoritma kot zelo ucinkovita, saj je takšno stopnjo nakljucnosti in kompleksnosti modela z uporabo klasicnih metod težko doseci. Na sliki 1 vidimo primer terena, generiranega s fraktalnim algoritmom.
Prelomni algoritem
S pojmom prelom opisujemo ploskovno razpoko ali razmeroma ozko razpokano cono v Zemljini skorji, povezano s preteklimi in morebitnimi prihodnjimi tektonskimi premiki [5]. Fraktal lahko definiramo kot geometrijski vzorec, ki ga dobimo s ponavljanjem nekega iterativnega procesa na preprostejšem mnogotniku ali poliedru.
Prelomni fraktal na grobo simulira posledice moc-nih potresov vzdolž nakljucnih prelomnih premic. Pod izrazom prelomna premica razumemo vsako takšno premico, ki gre skozi teren in ga deli na dva dela. Fraktal bomo ustvarili na prazni višinski sliki. Višinska slika je sivinska rasterska slika, ki se uporablja za shranjevanje vrednosti, obicajno so to nadmorske višine. Bela barva predstavlja najvišjo višino,
SLIKA 1.
Primer generiranja fraktalnega terena v vec korakih, od leve proti desni
26
PRESEK 43 (2015/2016) 5
RACUNALNIS TVO
crna pa najnižjo. Na prazni višinski sliki se bo izvršilo zaporedje »potresov« na sledeči nacin: na sliki se izbere naključna premica in vsako vozlišče nad to premico se premakne gor, vozlišča pod njo pa navzdol. Ta iterativni postopek se ponavlja, dokler ne dobimo zadovoljivega terena.
Psevdokoda
Algorithm 1 Prelomni fraktal Require: Poligonska ravnina n Ensure: Poligonska mreža n 1:
2
3
4
5
6
7
8 9
10 11 12
13
14
15
16
17
18
19
20 21 22 23
iter <= 0
while iter < stIteracij do k <= naključno število
> Zgenerira smerni koeficient k n <= naključno število
> Zgenerira odsek na osi y for all vozlišce vi g n do fvt ^ Xi • k + n
>	Izracuna tocko na premici if yi > fvi then
>	Ce je vozlišce nad premico dvigni zi ^ zi + Ah
>	Spremeni višino vozlišca vi
else
spusti zi ^ zi - Ah
>	Spremeni višino vozlišca vi
end if end for
zmanjšaj Ah ^ Ah- konst.
>	Zmanjša spremembo višine
iter ^ iter + 1
> Poveca števec izvedenih iteracij
end while
SLIKA 2.
Primer vozlišča vi, ki leži nad generirano premico f.
dvorazsežnem ali trirazsežnem prostoru. Vozlišce vi je 3-terica oblike (xi,yi,zi), kjer so xi,yi in zt elementi iz množice realnih števil R.
Poligonska ravnina se nahaja v tridimenzionalnem prostoru, vendar je premice dovolj generirati v dvodimenzionalnem prostoru. Zato je koordinata z v algoritmu uporabljena le takrat, ko se spremeni višina vozlišca V.
Algoritem izpolnjuje teren iterativno z izbiro dveh naključnih parametrov. Za vsako iteracijo se določita smerni koeficient k in odsek na y osi n.
y = k • x + n
(1)
Delovanje algoritma
Poligonska ravnina je poseben primer poligonske mreže, ki zadošca Evklidovi definiciji ravnine. Poligonska mreža je v racunalniški grafiki definirana kot 3-terica (V,E,F), kjer V predstavlja množico vozlišc (tock v prostoru), E c (V x V) množico robov (segmentov premice) in s F c E* oznacujemo množico lic (konveksnih poligonov). Vozlišče v racunalniški grafiki predstavlja podatkovno strukturo, ki opisuje dolocene atribute. Obicajno je to pozicija tocke v
Enacba 1 predstavlja eksplicitno enacbo premice v ravnini z = 0, ki jo enolicno dolocata parametra k in n. Za vsako vozlišce vt poligonske ravnine n je moc izracunati, ali Vi leži nad ali pod generirano premico. Algoritem preveri, ali bo vozlišce dvignil ali spustil tako, da koordinato xt vstavi v formulo 1. Par (xi,fVi) predstavlja tocko, ki leži na premici f. Iz slike 2 je ocitno, da zadošca pogledati odnos med koordinato yi od vozlišca vi in izracunan fVi. V primeru, da je yi > fVi, se to vozlišce dvigne. Na tak nacin se preverijo vsa vozlišca, ki ležijo na poligon-ski ravnini, in priredi nova višina.
Po vsaki iteraciji se zmanjša sprememba višine Ah zato, da teren ne bo imel v vseh tockah enakih višinskih razlik. Atribut consth je konstanta in do-loca razliko, za katero se zmanjšuje višina. Vecja vrednost consth pomeni hitrejše padanje Ah in s

PRESEK 43 (2015/2016) 5
27
RACU N A L NI STVO
SLIKA 3.
Primer štirih višinskih slik dimenzij 256 x 256 pikslov in barvne globine 8 po 4, 8, 32 in 1 28 iteracijah algoritma
tem tudi položnejši teren. Manjši consth pomeni, da bo sprememba višine Ah manjša, zato se bo teren bolj strmo vzpenjal ali spuščal. Z drugimi besedami to pomeni, da consth vpliva na razgibanost terena. Atribut stIteracij neposredno vpliva na izgled terena, saj predstavlja število ponovitev algoritma. Za upodobitev realističnega terena je potrebnih veliko prelomov, kot je razvidno na sliki 5.
Sicer na takšen način ne moremo generirati navpičnih prelomov, saj v ekspličitni obliki naklon za navpično premico ni definiran, vendar izvzetje le-teh ne vpliva občutno na končni teren.
Primeri generiranih terenov
Na sliki 3 so prikazani primeri generiranih višinskih slik pri različnem številu iteracij prelomnega algoritma. Zgenerirana višinska slika je odvisna od števila zgeneriranih naključnih prelomov, dimenzije te-ksture ter barvne globine teksture.
Na skrajno levi višinski sliki, prikazani na sliki 3, jasno ločimo, kje so potekale prelomne premiče. Na sliki je le nekaj zelo podobnih sivih odtenkov, ki zavzemajo veliko površine. Iz tega lahko sklepamo, da bi teren iz takšne slike bil skoraj povsem raven, z malimi višinskimi razlikami. Druga slika je podobna prejšnji in pridemo tudi do enakih zaključkov. To ni presenetljivo, saj je razlika v iteračijah algoritma med slikama zelo majhna. Na tretjem primeru opazimo v zgornjem desnem kotu zabrisane meje, kjer so potekale prelomne premiče. Ker je tisto obmo-
čje svetlo obarvano, vemo, da bi v upodobitvi takšne višinske slike tam stal hrib, kot lahko vidimo na tretjem terenu na sliki 5.
Na skrajno desnem primeru zaznamo ogromno različnih odtenkov. Povemo lahko le, da ta višinska slika opisuje dve gori ter dolino med njima. Za razliko od prvih dveh višinskih slik, si je brez upodobitve v trirazsežnem prostoru takšen primer težko predstavljati.
Ker je višinska slika odvisna tudi od barvne globine generirane teksture, velja, da lahko teksture z večjo barvno globino tvorijo bolj razgibane terene.
SLIKA 4.
Primerjava sivinske lestvice med slikama z 8-bitno barvno globino (zgoraj) in 16-bitno barvno globino (spodaj)
28
PRESEK 43 (2015/2016) 5
RAČ UNALNIŠ TVO
SLIKA 5.
Primer generiranih terenov po 4, 8, 32 in 1 28 iteracijah algoritma na poligonski ravnini velikosti 10 x 10 enot z 1 0201 vozlišču v programu Autodesk Maya
Slika 4 ponazarja razliko dveh sivinskih lestvic.
Upodobitev višinskih slik iz slike 3 na ravnini v prostoru vidimo na sliki 5. Po dovolj veliko iteracijah algoritma lahko zmodeliramo realistični fraktalni teren, ki je dovolj dober za uporabo v računalniški grafiki ali na kakšnem drugem področju.
Zaključek
Vidimo, da fraktalni teren izkazuje značilnosti, ki bi jih pričakovali v pokrajinah iz narave. Sicer predstavljeni algoritem ne generira jam in votlin, za to se v praksi uporabijo posebni algoritmi, vendar pa smo z implementačijo prelomnega algoritma dobili realistične gore in doline. Ce bi podoben teren želeli zmodelirati ročno, bi nam to vzelo prečej časa.
Algoritem z vsako iteračijo obišče vsa vozlišča v poligonski mreži, zato je njegova časovna zahtevnost O(n2), kjer je n število vozlišč poligonske mreže. To med drugim pomeni, da algoritem ni primeren za uporabo v grafiki v realnem času, saj je prepočasen. Tovrstni algoritem se zato uporablja v pred-pročesiranju, kjer si vnaprej zgeneriramo poljubno število višinskih slik, ki jih potem uporabljamo kot teksture za upodobitev terena.
Postavi se nam vprašanje, ali je mogoče prelomni algoritem na kak način posplošiti. Izkaže se, da je z nekaj spremembami prelomni fraktal moč pretvoriti v algoritem, ki generira naključne planete. V tem primeru ne ločujemo ravnine s premičo, ampak generi-ramo naključne ravnine, ki delijo sfero. Potrebno je samo določiti lego vozlišč glede na ravnino. Ce se vozlišče nahaja nad prelomno ravnino, ga premaknemo v smeri njegovega normalnega vektorja, v primeru da se nahaja pod njo, pa v negativno smer tega vektorja.
Literatura
[1]	D. S. Ebert, F. K. Musgrave, D. Peachey, K. Perlin in S. Worley, Texturing and Modeling, Third Edition: A Procedural Approach, Morgan Kaufmann, 2002.
[2]	M. DeLoura, Game Programming Gems 2, Charles River Media, 2001.
[3]	I. Parberry, Tobler's First Law of Geography, Self Similarity, and Perlin Noise: A Large Scale Analysis of Gradient Distribution in Southern Utah with Application to Procedural Terrain Generation, Technical Report LARC-2014-04, 2014.
[4]	e-on software, inc. Vue Helps Industrial Light & Magic Create Environments for »Pirates Of The Caribbean: Dead Man's Chest« VFX, ogled 12. 1. 2016. Dostopno na naslovu: http://www.e-onsoftware.com/ news/?page=pressreleases\&date=August\ %201,\%202006.
[5]	J. Lapajne. Uprava Republike Slovenije za zaščito in reševanje. Nekateri tektonski, seizmotek-tonski in seizmološki termini - 1. Del, ogled 12. 1. 2016. Dostopno na naslovu: http://www. sos112.si/slo/tdocs/ujma/2008/316.pdf.
_XXX
www.dmfa.si www.presek.si
PRESEK 43 (2015/2016) 5
29