1 UVOD
Članek je povzet po diplomskem delu prvega avtorja
[1], ki prikaže metode za proceduralno generiranje trop-
skega otoka, primernega za uporabo v računalniški igri.
Omejimo se na generiranje in teksturiranje terena, brez
postavljanja morebitnih drugih objektov, kot so drevesa
in skale. Ker je v pri večjih terenih proceduralno generi-
ranje mnogokrat računsko intenzivna operacija, posame-
zne korake implementiramo na grafični procesni enoti
(GPE), ki je zaradi svoje visokoparalelne arhitekture
Prejet 13. februar, 2016
Odobren 15. marec, 2017
zmožna hitrega procesiranja velike količine podatkov.
Najprej generiramo začetni teren, nato pa za bolj verodo-
stojen videz simuliramo hidravlično in termično erozijo.
Ker v tropskih morjih v okolici otokov običajno rastejo
koralni grebeni, izvedemo tudi simulacijo rasti le-teh. Na
teren lepimo teksture, ustrezne njegovim značilnostim.
Enega pomembnejših prispevkov na področju proce-
duralnega generiranja je dal Ken Perlin. Predstavil je
način generiranja šuma, ki ga danes imenujemo Perlinov
šum [2]. Perlinov šum se uporablja na veliko področjih,
eno izmed njih pa je proceduralna gradnja terena. Perlin
je pozneje predstavil še šum Simplex [3], ki je za
izračun hitrejši in še dodatno izboljša videz. V delu za
gradnjo začetnega terena uporabljamo slednjega, ker je
ta še danes najboljši kompromis med hitrostjo izračuna,
pomnilno potratnostjo in kakovostjo [4], [5].
Musgrave, Kolb in Mace [6] so bili med prvimi, ki so
predstavili simuliranje erozije. Opisujejo tako termično
kot tudi hidravlično erozijo in način prikaza generira-
nega terena. Hidravlična erozija simulira pretakanje vode
po terenu, ki spodjeda material, ga prenaša v svojem
toku in ga nato odlaga. Termična erozija pa zajema
dejavnike, ki drobijo površino terena v drobir, ta pa
nato drsi po strmih pobočjih. Simuliranje hidravlične
erozije sta predstavila tudi Beneš in Forsbach [7]. Mei,
Decaudin in Hu [8] pa so prvi predstavili implementacijo
hidravlične erozije iz [7] na GPE. Jákó in Tóth [9]
sta dodatno opisala še implementacijo termične ero-
zije na GPE. Generiranje terena s pomočjo hidravlične
in termične erozije na GPE je v svojem diplomskem
delu opisal tudi Maške [10]. V tem delu uporabljamo
drugačen pristop k generiranju začetnega terena kot
PROCEDURALNO GENERIRANJE TROPSKEGA OTOKA IN KORALNEGA GREBENA 31
drugi in po simulaciji erozije simuliramo še rast koral-
nega grebena ter na teren nanesemo teksture.
Virov, ki prikazujejo simuliranje rasti koral z name-
nom vizualizacije, v računalniški grafiki nismo našli.
Po drugi strani pa smo našli vira, ki sta model rasti
koral in s tem koralnega grebena, namenjen znanstvenim
raziskavam [11], [12]. Z nekaj poenostavitvami smo ta
model priredili svojim potrebam.
2 POSTOPEK
Za predstavitev terena smo uporabili višinsko karto
(angl. heightmap). To je rastrska slika, kjer vsak piksel
pomeni višino v pripadajoči točki na terenu.
2.1 Generiranje začetnega terena
Ker je bil cilj generirati teren v obliki otoka, smo želeli,
da bo teren na sredini višinske karte višji kot ob robovih.
To smo dosegli z generiranjem višinske karte, ki definira
teren v obliki stožca z nelinearno klančino:
hA(x, y) =
{
κH
(
1−
(
r(x,y)
κR
)κP)
; če r(x, y) < κR
0; sicer,
(1)
kjer κH označuje višino stožca, κR polmer stožca in κP
potenco, ki nadzoruje obliko klančine,
r(x, y) =
√
(x− xC)2 + (y − yC)2 (2)
pa razdaljo točke (x, y) do središča osnovne ploskve
stožca (xC, yC).
Za izboljšanje verodostojnosti terena smo v nasle-
dnjem koraku generirali dodatno višinsko karto, ki
smo jo potem združili s prvo. Za generiranje te smo
uporabili šum Simplex [3], ki ga lahko implementi-
ramo v poljubnem številu dimenzij in s katerim lahko
dosežemo hribovit videz. Pri svoji rešitvi uporabljamo
C# implementacijo, ki je del prosto dostopnega paketa
MinePackage1. Za boljši videz terena smo uporabili več
oktav šuma2. Izraz oktava v glasbeni teoriji označuje
interval med višinama dveh tonov, od katerih ima eden
dvojno oziroma polovično frekvenco drugega. V primeru
funkcije šuma z višanjem frekvence šuma (skala šuma)
zmanjšujemo tudi amplitudo. Na eni višinski karti smo
uporabili več oktav šuma tako, da smo vse oktave sešteli:
hB(x, y) =
N∑
i=0
η(x2i, y2i)
1
2i
, (3)
kjer je η vrednost šuma Simplex v koordinatah (x, y) in
N število oktav.
Pri združevanju višinskih kart stožca in šuma smo se
zgledovali po orodju Worldmachine3, kjer je mogoče več
višinskih kart združiti v eno na več načinov. Najboljše
1sourceforge.net/projects/minepackage
2www.redblobgames.com/maps/terrain-from-noise
3www.world-machine.com
Slika 1: Začetni relief terena
rezultate smo dobili, ko smo višinski karti združili s
potenciranjem:
hC(x, y) = hA(x, y)
1+hB(x,y)κN , (4)
kjer je hA višina v višinski karti stožca, hB pa višina
v višinski karti šuma Simplex. Vpliv šuma določa para-
meter κN.
Ker smo želeli, da otok dobi videz vulkana, smo
dodali možnost generiranja vulkanskega kraterja. Ge-
nerirali smo ga tako, da smo vse vrednosti v združeni
višinski karti hC, ki so višje od določenega praga, čez
prag preslikali navzdol. Postopek prikazuje enačba (5),
kjer je h0 končna višinska karta začetnega terena, κC
pa višina praga in s tem višina, na kateri se ustvari
vulkanski krater. Slika 1 pa prikazuje relief, generiran
z uporabo končne višinske karte začetnega terena.
h0(x, y) =
{
2κC − hC(x, y); če hC(x, y) > κC
hC(x, y); sicer
(5)
2.2 Erozija
Kljub temu, da že začetni teren spominja na otok,
je njegov videz še neprepričljiv. Simuliranje naravnih
procesov, kot sta hidravlična in termična erozija, nam
omogoča videz izboljšati. Hidravlično erozijo smo im-
plementirali po viru [8], termično pa po [9]. Vira opisu-
jeta metodi simuliranja teh procesov na GPE.
2.2.1 Hidravlična erozija: Simuliranje hidravlične
erozije se začne s simuliranjem pretakanja vode po
površini terena. Na podlagi hitrosti vode in naklona
terena določimo količino raztopljenega sedimenta in
njegov prenos. V predelih hitrejšega vodnega toka voda
teren odnaša, v počasnejših pa ga odlaga. S tem se
teren preoblikuje in dobi želen erodiran videz. Voda med
simulacijo ves čas izhlapeva.
Za opis simulacije bomo uporabljali naslednje po-
membne količine: višina terena, količina tekoče vode,
32 KOROŠEC, LEBAR BAJEC
količina razstopljenega sedimenta, odtočni tokovi vode
in hitrost vode. Pri tem se vsaka od količin hrani za
vsako točko (celico) terena. S t dodatno označujemo
trenutni čas in s τ časovni korak ene iteracije simulacije.
Vsaka iteracija je razbita na več zaporednih korakov:
1) dodajanje vode,
2) pretakanje vode po terenu in izračun vektorjev
hitrosti ter posodobitev količine tekoče vode,
3) izračun stopljenega in odloženega sedimenta,
4) prenos sedimenta,
5) difuzija sedimenta,
6) izhlapevanje vode.
Vsak korak uporabi količine iz prejšnjega koraka in
jih posodobi. Nekatere količine se izračunajo v več
podkorakih, zato te indeksiramo še z ′, ′′ itd., da med
seboj ločimo vrednosti v različnih podkorakih. Sosednje
celice trenutne celice ozačujemo z L (leva), R (desna),
T (gornja), B (spodnja).
Za simuliranje pretakanja vode uporabljamo prirejen
model, ki povezuje sosednje celice z navideznimi cevmi,
po katerih se med njimi izmenjuje voda [13]. Ob začetku
simulacije privzemamo, da je višina vode po celotnem
terenu ničelna; d0 = 0. Dež pomeni nastanek nove vode,
kar za obravnavano celico (x, y) izračunamo kot
dt
′ = dt + rτ, (6)
kjer r označuje količino dežja, ki prispe v celico na
enoto časa. Zaradi velikosti terena namreč ni smiselno
simulirati dežja kot posamezne kaplje, temveč kot uni-
formno rast količine tekoče vode po posamezni celici
terena.
Za vsako celico hranimo njene odtočne tokove
L,R, T,B do štirih sosednjih celic, njeni pritočni to-
kovi pa so ustrezni odtočni tokovi obravnavani celici
sosednjih celic. V vsaki iteraciji simulacije se tok vode v
odtočnih tokovih pospeši zaradi razlike v hidrostatičnem
tlaku med celicami, količina tekoče vode pa se nato
izračuna s kopičenjem vseh tokov v virtualnih ceveh.
Odtočni tok v smeri proti levi celici za obravnavano
celico izračunamo po enačbi:
Lt
′ = max
{
0, Lt + τκA
κg∆h
L
t
`
}
, (7)
kjer κA pomeni površino prereza cevi, ` dolžino cevi
med dvema sosednjima celicama, κg gravitacijski po-
spešek in ∆hLt razliko višin med obravnavano in levo
sosednjo celico (x− 1, y), ki se izračuna po enačbi:
∆hLt = ht + dt
′ − hLt − d
L
t
′
. (8)
Odtočni tokovi v smeri sosed R, T, B se izračunajo
na enak način. Ker izračun odtočnih tokov upošteva
višinske razlike do vsake sosede individualno, obstaja
možnost, da bi iz obravnavane celice odteklo več vode,
kot je ta vsebuje. S tem bi količina tekoče vode v
celici po izračunu postala negativna. Težavo se rešuje
z omejitvijo moči vsakega izmed odtočnih tokov v
odvisnosti od količine tekoče vode v celici in predvidene
moči vseh odtočnih tokov [8], [10]. Pri odtočnem toku v
smeri proti levi celici se tako odtočni tok v naslednjem
koraku simulacije izračuna kot:
Lt+τ = Lt
′min
{
1,
dt
′`2
τ
∑
Ot
′
}
, (9)
kjer Ot
′ pomeni množico vseh odtočnih tokov obravna-
vane celice
{
Lt
′, Rt
′, Tt
′, Bt
′}, izračunanih z uporabo
enačbe (7),
∑
Ot
′ pa njihovo skupno vsoto.
Pretakanje vode po navideznih ceveh se odraža v
spremembi količine tekoče vode
dt
′′ = dt
′ +
∑
It+τ −
∑
Ot+τ
`2
τ, (10)
kjer sta
It+τ =
{
RLt+τ , L
R
t+τ , B
T
t+τ , T
B
t+τ
}
in
Ot+τ = {Lt+τ , Rt+τ , Tt+τ , Bt+τ}
po vrsti množici pritočnih in odtočnih tokov obravna-
vane celice v naslednjem časovnem koraku. Pri simuli-
ranju pretakanja vode moramo upoštevati robne pogoje,
ki izhajajo iz dejstva, da je teren končen. Iztekanje
vode iz terena omejimo tako, da vsaki cevi, ki nima
sosednje celice, postavimo vrednosti ustreznih odtočnih
in pritočnih tokov na 0. Na primer: za celice brez levega
soseda (0, y) postavimo tako levi odtočni tok L, kot tudi
levi pritočni tok RL na 0.
Voda med pretakanjem zaradi erozije pretvori del
terena v sediment
S = κS ‖vt‖ sinα, (11)
ki ga nato prenaša in odlaga po terenu. V enačbi (11)
κS pomeni konstanto kapacitete sedimenta, α pa lokalni
naklon terena v celici. Tega za obravnavano celico
izračunamo kot α = arccos(n̂t · k). Pri tem n̂t pomeni
normalo na teren, ki jo pridobimo kot
m = i
hRt − hLt
κM
+ j
hTt − hBt
κM
+ k, n̂t =
m
‖m‖
, (12)
kjer je κM razdalja med sosednjimi celicami terena, i, j,
k pa po vrsti enotski vektorji, ki kažejo v smereh osi x, y
in z. Hitrost vode v obravnavani celici vt = 〈vx, vy〉, ki
jo potrebujemo v enačbi (11), pa izračunamo s pomočjo
odtočnih in pritočnih tokov celice:
vx =
RLt+τ − Lt+τ +Rt+τ − LRt+τ
`(dt
′ + dt
′′)
, (13)
vy =
TBt+τ −Bt+τ + Tt+τ −BTt+τ
`(dt
′ + dt
′′)
. (14)
Na zelo položnih delih, kjer se α približuje 0, je
vrednost S zelo nizka. Na takšnih predelih proces erozije
ne bo imel občutnega učinka. To lahko omilimo tako, da
α navzdol omejimo s poljubno minimalno vrednostjo.
Na podlagi vrednosti S in raztopljenega sedimenta iz
PROCEDURALNO GENERIRANJE TROPSKEGA OTOKA IN KORALNEGA GREBENA 33
predhodne iteracije simulacije, st, se odločimo, ali se bo
del sedimenta odložil ter pretvoril nazaj v teren ali ne.
Ko velja S > st, se zgodi proces erozije in del terena
se raztopi, v nasprotnem primeru se del raztopljenega
sedimenta odloži in pretvori nazaj v teren. Novo višino
terena in količino raztopljenega sedimenta izračunamo
po enačbah:
ht+τ =
{
ht − κE(S − st); če S > st
ht + κD(S − st); sicer
(15)
st
′ =
{
st + κE(S − st); če S > st
st − κD(S − st); sicer,
(16)
kjer je κE konstanta topljenja materiala, κD pa konstanta
odlaganja materiala.
Raztopljeni sediment prenaša vodni tok, kar opisuje
advekcijska enačba δs
δt
+ (vt∇s) = 0. Enačbo rešujemo
z Eulerjevim korakom nazaj v času, kar pomeni, da
količini raztopljenega sedimenta v obravnavani celici
(x, y) priredimo vrednost, ki je odvisna od vodnega toka
v njej
st
′′(x, y) = st
′(x− vxτ, y − vyτ), (17)
kjer koordinate (x− vxτ, y− vyτ) omejimo na območje
terena. Kot je omenil že Maške [10], postopek ne deluje
zadovoljivo, saj je mogoče, da se v enem koraku količina
sedimenta iz ene celice preslika v več celic. Opazili smo
tudi, da se sediment pri nižjih hitrostih vode večkrat
prenaša v ravnih črtah. To je zato, ker se sediment v
območjih nizke hitrosti prenaša med celicami, ki so
neposredne sosede. To daje polju sedimenta grob in
nenaraven videz, zato ga mi dodatno gladimo s simu-
liranjem difuzije sedimenta.
Difuzijo simuliramo z dvodimenzionalno Laplacevo
enačbo, ki jo numerično rešujemo z Jakobi iteracijami
[14]. Izračun iteracije prikazuje enačba
st+τ =
sLt
′′
+ sRt
′′
+ sTt
′′
+ sBt
′′
nW
, (18)
kjer nW pomeni število celic izmed L, R, T in B, ki
držijo vodo (dt
′′ > 0). Robne pogoje smo poenostavili
tako, da se koordinate celic omejijo na območje terena.
Na primer: za vse celice, ki ležijo na levem robu terena
(0, y), se koordinate leve sosednje celice (x−1, y) ome-
jijo na (0, y). Celicam, ki ne vsebujejo vode, nastavimo
vrednost st′′ na 0.
V zadnjem koraku vsake iteracije simulacije hidra-
vlične erozije upoštevamo, da se količina tekoče vode
spreminja tudi zaradi izhlapevanja. V našem delu pred-
postavljamo, da je temperatura ozračja med simulacijo
konstantna, zato hitrost izhlapevanja določamo s kon-
stanto κT. Proces izhlapevanja opisuje enačba
dt+τ = dt
′′(1− κTτ). (19)
2.2.2 Termična erozija: Hidravlična erozija oblikuje
grob teren z veliko ostrimi robovi, kar je opazno pred-
vsem na pobočjih ob vodnih strugah, ki se nenehno
poglabljajo. S simuliranjem termične erozije, ki mode-
lira proces razgradnje kamnin v drobir zaradi tempera-
turnih sprememb in njegovo nadaljne razsipanje, teren
zgladimo in izboljšamo njegov videz. Podobno kot za
hidravlično lahko tudi za termično erozijo uporabljamo
model virtualnih cevi, le da v tem primeru cevi prenašajo
drobir (terena) namesto vode. Vendar se običajno [9][10]
zaradi boljšega rezultata pri termični eroziji namesto
von Neumannove okolice, ki zaobjema zgolj najbližje
štiri sosede obravnane celice, uporablja Moorova oko-
lica, ki zajema vseh osem najbližjih sosednjih celic
N ∈ {L,R,T,B,TL,TR,BL,BR}. To bi lahko sicer
storili že pri hidravlični eroziji, vendar menimo, da bi
to povzdignilo kompleksnost implementacije brez večjih
izboljšav pri rezultatu.
Količina drobirja, ki jo lahko v eni iteraciji prenesemo
v vsako od sosednjih celic, je omejena z Mt =
Ht
2
τκM
2,
kjer je Ht = ht − min
{
hit| i ∈ N
}
razlika v višini
terena v obravnavani celici in najnižjo višino terena v
njej sosednjih celicah. Če to vrednost presežemo, začne
algoritem oscilirati [9]. Nadaljnji proces smo glede na
vir [9] nekoliko poenostavili; vir upošteva tudi lokalno
trdnost terena, ki je v našem delu ne.
Drobir se pod vplivom gravitacije razsipa med niže
ležeče sosednje celice, ki z obravnavano celico tvorijo
kot naklona, večji od kota mirovanja κα. To je kritičen
kot pobočja, ki ga lahko neki zrnati material še tvori.
Če klančina preseže kot mirovanja, material zdrsne.
Kote naklona med obravnavano in posamezno sose-
dnjo celico i ∈ N izračunamo kot αit = arctan
ht−hit
κM
.
Na podlagi teh sestavimo množico, ki vsebuje vse sose-
dnje celice z naklonom, večjim od kota mirovanja κα:
Rt =
{
i ∈ N| αit > κα
}
. (20)
V vsako celico iz množice Rt na podlagi višinske
razlike z obravnavano celico prenesemo temu propor-
cionalno količino drobirja, v preostale celice ga ne
prenašamo. Na primer: količino drobirja, ki se prenese
v levo sosednjo celico, če ta spada v množico Rt,
izračunamo z enačbo:
Lt = Mt
hLt∑
i∈Rt h
i
t
. (21)
Zaradi vzporednega izvajanja simulacije drobirja ne
prestavimo v celice takoj, temveč za ta proces uporabimo
navidezne cevi. Končno višino vsake celice izračunamo
podobno kot pri hidravlični eroziji, in sicer tako, da k tre-
nutni višini prištejemo vse pritočne tokove in odštejemo
vse odtočne:
ht+τ = ht +
∑
Mint −
∑
Moutt , (22)
le da tokrat z
Moutt = {Lt, Rt, Tt, Bt,TLt,TRt,BLt,BRt}
34 KOROŠEC, LEBAR BAJEC
Slika 2: Relief terena po hidravlični in termični eroziji
označimo drobir, ki se iz obravnavane celice razsipa v
sosednje celice po ustreznih virtualnih ceveh (odtočni
tokovi drobirja), z
Mint = 〈R
L
t , L
R
t , . . . ,TL
BR
t 〉
pa pritočne tokove drobirja (odtočne tokove drobirja
usreznih sosed). Primer terena po končani simulaciji
prikazuje slika 2.
2.3 Glajenje morskega dna
Teren pod morsko gladino ima po simulaciji erozije
enak videz kot teren nad morsko gladino, saj simula-
ciji erozije ne upoštevata višine morske gladine. Med
izvajanjem simulacij smo ugotovili, da ima rezultat rasti
koralnega grebena bolj naraven videz, če pred njim teren
pod morsko gladino še dodatno zgladimo. To ponovno
počnemo z Jakobijevo iteracijo, podobno kot smo to
storili s sedimentom pri hidravlični eroziji:
ht+τ =
hLt + h
R
t + h
T
t + h
B
t
4
. (23)
Jakobijevo iteracijo računamo samo za celice, ki ležijo
pod vodno gladino in ne ležijo tik ob robu terena.
Drugim celicam vrednosti ne spreminjamo.
2.4 Rast koralnega grebena
V tropskih morjih okoli otokov, predvsem takšnih vul-
kanskega nastanka, velikokrat rastejo korale, ki skozi
čas tvorijo koralne grebene [15]. Korale rastejo v pli-
tvinah toplejših morij. Za rast potrebujejo svetlobo,
saj ožigalkarji živijo v sožitju s fotosinteznimi algami
zooksantele (angl. zooxanthellae) [15]. Sestavljene so
iz kolonij majhnih polipov, katerih apnenčasti zunanji
skeleti se nalagajo in tvorijo koralne grebene. K tvorbi
grebena pripomorejo tudi drugi organizmi, ki živijo
v koralnem ekosistemu. S simuliranjem rasti koralnih
grebenov želimo videz otoka še bolj približati resničnosti
in ga narediti zanimivejšega.
Model rasti koralnega grebena, predstavljen v na-
daljevanju, temelji na modelu Nakamure in Nakamo-
rija [12]. Avtorja sta predstavila model rasti koralnega
grebena na podlagi intenzitete svetlobe in koncentra-
cije anorganskega ogljika v vodi, za dvodimenzionalne
simulacije rasti pa v pogledu s strani. Ker za naše
potrebe potrebujemo pristop, s katerim je mogoče rast
simulirati v pogledu iz zraka, smo njun model priredili
in poenostavili.
V opisu bomo uporabljali dve pomembni količini:
višina terena (morskega dna) in koncentracija anorgan-
skega ogljika v vodi. Obe količini se hranita za vsako
točko oziroma celico terena. Vsaka iteracija simulacije
pa je razbita na dva zaporedna koraka; rast koral in
difuzijo koncentracije anorganskega ogljika.
Kalcifikacija koral je v veliki meri odvisna od stopnje
fotosinteze, ki jo lahko izračunamo na podlagi globine
vode
gt = wt − ht, (24)
kjer wt označuje globalno višino morske gladine v
trenutni iteraciji simulacije. Korale zaradi plimovanja
in drugih dejavnikov namreč običajno rastejo le do
določene globine vode κG. Stopnjo kalcifikacije koral
izračunamo z uporabo enačbe
ct =
{
O2t κBe
−gtκA ; če gt < κG
0; sicer,
(25)
kjer je Ot vrednost koncentracije anorganskega ogljika
v vodi v trenutni iteraciji simulacije, κB konstanta
hitrosti kalcifikacije in κA konstanta absorpcije vode.
V prvi iteraciji simulacije je vrednost Ot vsake celice
postavljena na O0.
Korale za rast porabijo določeno količino anorgan-
skega ogljika, zato moramo vrednost njegove koncen-
tracije v vodi zmanjšati v sorazmerju s stopnjo kalcifi-
kacije. Spremembo izračunamo po enačbi
Ot
′ = max
{
0, Ot −
ctτ
gt
κU
}
, (26)
kjer κU nadzoruje stopnjo porabe anorganskega ogljika.
S tem, da v enačbi (26) stopnjo kalcifikacije delimo
z višino vode, dosežemo, da se pri enaki stopnji rasti
koral koncentracija anorganskega ogljika v vodi zmanjša
primerno količini vode nad to točko na terenu.
Na koncentracijo anorganskega ogljika v vodi vplivata
tudi plimovanje in mešanje vode. Ker v našem primeru
simulacija teče v časovnem razponu več tisoč let, in to
na velikem terenu, lahko ta vpliv prikažemo s preprosto
difuzijo, podobno kot smo to storili s sedimentom pri hi-
dravlični eroziji. Difuzijo anorganskega ogljika modelira
enačba
∇2O =
δ2O
δx2
+
δ2O
δy2
= 0, (27)
ki jo numerično rešujemo z Jakobijevo iteracijo
Ot+τ =
OLt
′
+ORt
′
+OTt
′
+OBt
′
nU
(28)
kjer nU pomeni število najbližjih sosednjih celic v
von Neumannovi okolici, ki ležijo pod morsko gladino
PROCEDURALNO GENERIRANJE TROPSKEGA OTOKA IN KORALNEGA GREBENA 35
Slika 3: Koralni greben okoli otoka. Morska gladina je prika-
zana za boljšo predstavo.
(gt > 0). Pri robnih celicah, celicah, ki ležijo tik ob robu
terena in zato nimajo levega ali desnega, ali zgornjega,
ali spodnjega soseda, Jakobijeve iteracije ne računamo,
temveč Ot+τ priredimo vrednost O0. Jakobijeve iteracije
prav tako ne računamo pri celicah, ki so nad gladino
morja, a v nasprotju s prej v teh primerih Ot+τ prire-
dimo vrednost 0, ker celice ne izpolnjujejo pogojev za
nastanek koral.
V našem delu podatkov o višini koralnega grebena
ne hranimo ločeno, temveč ga štejemo kot teren. Rast
grebena (in s tem dvig višine terena) je neposredno od-
visna od stopnje kalcifikacije. Višino terena po iteraciji
simulacije izračunamo z enačbo
ht+τ = ht + ctτ. (29)
Rast koralnega grebena in posledično sprememba
višine terena vpliva tudi na globalno višino morske
gladine. Na spremembe v višini morske gladine seveda
vplivajo tudi drugi dejavniki. V našem delu po vzoru
Nakamure in Nakamora [12] privzemamo konstantno
rast višine morske gladine. Globalno višino morske
gladine ob koncu iteracije rasti koralnega grebena tako
izračunamo po enačbi
wt+τ = wt + κWτ, (30)
kjer je κW konstanta rasti višine morske gladine. Vpliv
simulacije rasti koralnega grebena na končni videz pro-
ceduralno generiranega otoka prikazuje slika 3.
2.5 Implementacija
Simuliranje naravnih procesov, kot sta hidravlična in
termična erozija, je običajno računsko zahtevna opera-
cija. Čas izvajanja simulacije je pomemben še posebno
takrat, ko želimo rezultate opazovati v realnem času,
zato v teh primerih posegamo po GPE. V naši imple-
mentaciji uporabljamo okolje Unity in senčilnike Com-
puteShader4. Simulacijo izvajamo nad višinsko karto,
zato podatke o njej shranjujemo v teksturi. Za hranjenje
višinske karte v osnovi potrebujemo zgolj en barvni
kanal, zato je teksura višinske karte običajno sivinska.
V naši implementaciji za posamezen barvni kanal upo-
rabljamo 32-bitno predstavitev s plavajočo vejico (float).
Vsak od predstavljenih algoritmov hrani podatke o
nekaterih količinah (npr. višina vode), ki se uporabljajo
med posameznimi koraki in iteracijami simulacije. Ti
podatki so vezani na posamezne točke v višinski karti,
zato jih hranimo na enak način kot višinsko karto, tj.
v teksturi. Za shranjevanje vsake količine tako kot za
višinsko karto potrebujemo en barvni kanal. Ker v naši
implementaciji uporabljamo teksture s štirimi kanali, ki
se v senčilniku preslika v float4, nam to omogoča v eni
teksuri shranjevati podatke o več različnih količinah.
Razvili smo tri senčilnike, pri čemer prvi izvaja hi-
dravlično erozijo, drugi termično erozijo, tretji pa skrbi
za rast koral. Vsak senčilnik simulacijo pripadajočega
procesa izvaja v več iteracijah, v posamezni iteraciji pa
določene teksture obdela večkrat. Senčilnik Compute-
Shader je sestavljen iz več funkcij, med katerimi lahko
poljubne označimo kot jedrne. Poženemo ga tako, da
poženemo eno od jedrnih funkcij. Z uporabo več jedrnih
funkcij lahko teksturo z enim senčilnikom obdelamo v
več različnih korakih. Naša koda je organizirana temu
primerno, napisana pa je v jeziku HLSL različice Di-
rectX 11.
V prvem koraku naše implementacije generiramo
višinsko karto začetnega terena in jo shranimo v obliki
teksture. Na tej točki je pripadajoča tekstura shranjena v
glavnem pomnilniku računalnika, zato jo pred začetkom
izvajanja simulacije naravnih procesov prenesemo v
pomnilnik GPE. V pogonu Unity so teksture, ki so
shranjene izključno v pomnilniku GPE, objekti tipa
RENDERTEXTURE. V senčilnikih uporabljamo le takšen
tip tekstur; tekstur ne prenašamo med glavnim pomnilni-
kom računalnika in pomnilnikom GPE, saj je to časovno
potratna operacija. Ker se vizualizacija prav tako izvaja v
senčilnikih, je prenašanje nepotrebno. Ker pa rezulatatov
posameznega koraka iteracije ne smemo pisati v isto
teksturo, ker bi zaradi vzporednega izvajanja s tem lahko
uničili rezultate preostalih niti, moramo poleg vsake
teksture hraniti še njeno kopijo. Vsaki jedrni funkciji
moramo tako pred izvajanjem nastaviti potrebne vhodne
in izhodne teksture. Jedrne funkcije berejo trenutno
stanje simulacije iz vhodnih tekstur in rezultate obde-
lave zapišejo v izhodne teksture. Posledično bi morali
po vsaki končani jedrni funkciji rezultate iz izhodnih
prekopirati nazaj v vhodne teksture. Temu kopiranju smo
se izognili z izmeničnim menjavanjem vhodnih in izho-
dnih tekstur. Izhodne teksture prejšnje jedrne funkcije
nastavimo kot vhodne teksture naslednje. Menjavanje
izvajamo samo v sklopu posamične iteracije. Kadar se
4docs.unity3d.com/Manual/ComputeShaders
36 KOROŠEC, LEBAR BAJEC
menjavanje ne izvede sodo-krat, teksture vseeno kopi-
ramo.
Iteracije simulacije izvajamo v zanki, v kateri v
določenem vrstnem redu poženemo jedrne funkcije
ustreznega senčilnika. V namen nadzora simulacije smo
implementirali preprost grafični uporabniški vmesnik. Z
njim lahko spreminjamo določene parametre in vkla-
pljamo ter izklapljamo posamezne korake simulacije.
Vrstni red zagona senčilnikov načeloma ni pomemben, a
moramo paziti, da tistega, ki je namenjen rasti koral, ne
uporabljamo hkrati s hidravlično oz. termično erozijo.
Koralnega grebena namreč ne hranimo ločeno, temveč
kot teren, erozija (tako hidravlična kot termična) pa te-
ren preoblikuje in posledično spremeni videz koralnega
grebena, kar ni zaželeno.
2.6 Vizualizacija
Višinska karta v vsakem pikslu hrani višino pripadajoče
točke na terenu. Za prikaz terena uporabljamo metodo
imenovano odmiki (angl. displacement mapping) [16].
Njena težava je, da za prenos podrobnosti višinske karte
na model potrebuje veliko oglišč. V optimalnem primeru
bi bil model predstavljen z enakim številom oglišč, kot
ima višinska karta pikslov. V praksi to pomeni modele z
izjemno visokim številom oglišč in posledično velikim
številom trikotnikov. Problem lahko rešimo z uporabo
strojne teselacije (angl. hardware tessellation) [17], ki
model v osnovi predstavi z majhnim številom oglišč in
trikotnikov, te pa nato z uporabo senčilnikov dinamično
deli na več manjših, pri čemer ustvari več oglišč in več
podrobnosti. V naši implementaciji uporabljamo strojno
teselacijo fiksne stopnje.
Osvetlitev izračunavamo z Lambertovim modelom
[18, str. 267–268]
c = (̂l · n̂)cmcl, (31)
kjer osvetljenost v neki točki izračunamo na podlagi
vpadnega kota svetlobe l̂ in normale na teren v tej
točki n̂. Parametra cm in cl po vrsti pomenita barvo
materiala v točki in barvo vira svetlobe. Za osvetljevanje
uporabljamo smerno oziroma oddaljeno luč [18, str.
264], ki nima pozicije. Luč definira samo vektor smeri,
barvo in intenziteto. V enačbi (31) je intenziteta že všteta
v barvo luči.
Naš cilj je bilo generiranje tropskega otoka, k čemur
veliko pripomorejo teksture. Osnovne štiri teksture, ki
jih uporabljamo, so: trava (zelene površine), skalovje,
pesek in morsko dno. Teksture smo dobili na spletni
strani Textures5. V senčilniku na podlagi višine in
naklona terena ter višine vode v vsaki točki terena
vzorčne teksture združujemo in ob upoštevanju osve-
tlitve izračunamo barvo v tej točki. Logika združevanja
tekstur temelji na opažanjih iz narave in osebne pred-
stave o videzu tropskega otoka. Strma pobočja so redko
poraščena, medtem ko na ravninah prevladujejo zelene
5www.textures.com
površine. Za boljši videz smo v višjih in bolj strmih
predelih teksturo trave rahlo posvetlili ter dodali rumen
odtenek. Na obalah je pogosta peščena plaža, zato smo
pod gladino vode in na ožjem pasu obale nad njo nanesli
teksturo peska, vendar le tam, kjer je obala dovolj
položna. Na koncu smo pod gladino vode dodali še
teksturo morskega dna. Za doseganje mehkih prehodov
med teksturami smo si pomagali s funkcijo SMOOTH-
STEP, ki je del jezika HLSL. Funkcija nam omogoča
definicijo poljubno širokega pasu, v katerem se dve
teksturi mešata, zunaj pasu pa je izbrana ena od njiju.
Pri nanašanju teksture skalovja smo upoštevali tudi, kje
je med hidravlično simulacijo tekla voda. V dodatni
teksturi hranimo števec prisotnosti vode v določeni točki
na terenu v zadnjem krajšem časovnem obdobju. Števec
med simulacijo hidravlične erozije povečamo, če je v
pripadajoči točki prisotna voda, in zmanjšamo, če ni.
Števec je navzdol omejen z 0 in navzgor s poljubno
vrednostjo. Prisotnost teksture skalovja je višja tam, kjer
ima števec višjo vrednost. S tem vizualno dosežemo,
da na območjih, kjer so bile vodne struge, nekaj časa
ne raste trava. Podobno v isti dodatni teksturi hranimo
tudi števec količine rasti koralnega grebena, kjer tega
povečujemo premo sorazmerno z rastjo koralnega gre-
bena. Kjer ima ta števec višjo vrednost, je večja tudi
prisotnost teksture morskega dna.
Ker je otok v naravnem okolju obkrožen z morjem,
smo dodali prikaz tudi slednjega. Morja v okolici trop-
skih otokov so običajno zelo čista, zato v plitvih predelih
pogosto vidimo dno. Intenziteta svetlobe v neki točki v
globini morja je funkcija dolžine poti svetlobnih žarkov
skozi vodno maso [11]. V naši aplikaciji na teren in
morje v pretežni meri gledamo od zelo daleč, zato pri
izračunu barve morske gladine zanemarjamo dejstvo,
da se svetlobni žarki, ko iz zraka prehajajo v vodo,
lomijo, kar vpliva na dolžino njihove poti skozi vodno
maso. Barvo morske gladine tako določamo zgolj s
spreminjanjem prosojnosti osnovne, temno modre barve
v odvisnosti globine vode v obravnavani točki
cw.a = e
−gtκA , (32)
kjer κA nadzoruje moč slabljenja svetlobe (motnost
vodne mase). Izračun opravlja ločen senčilnik, ki skrbi
zgolj za izračun barve vsake točke na površini, ki
pomeni morsko gladino.
3 REZULTATI
Uporabljamo višinske karte v velikosti 512×512 točk.
Začetni teren se, predvsem zato, ker je opravilo
prepuščeno centralni procesni enoti, v povprečju zgradi
v 2,2 s. Ker se ta korak izvede samo enkrat v celotnem
procesu, to ni moteče. Simulacije naravnih procesov brez
vizualizacije se izvajajo hitro; 1000 iteracij hidravlične
erozije se v povprečju izvede v 4 ms, 1000 iteracij
termične erozije v 1 ms in 1000 iteracij rasti koralnega
grebena v 2 ms. Vizualizacija dosega povprečno hitrost
PROCEDURALNO GENERIRANJE TROPSKEGA OTOKA IN KORALNEGA GREBENA 37
Slika 4: Atol, generiran s pomočjo vulkanskega kraterja brez simuliranja posledic erozije (levo), vulkanski otok generiran s
simulacijo hidravlične erozije, termične erozije in rasti koralnega grebena
200 fps (slik na sekundo). V celoti generiranje otoka
želenega videza z vizualizacijo traja od 10 do 20 sekund,
kar je odvisno od želene velikosti koralnega grebena.
Brez vizualizacije pa generiranje traja približno 2,3 s,
pri čemer simuliranje naravnih procesov traja 35 ms.
Vse vrednosti veljajo za računalnik s procesorjem Intel
Core i7 6700K, 16 GB delovnega pomnilnika in grafično
kartico Nvidia GeForce GTX 1070, pri čemer smo
v pogonu Unity 5 imeli nastavljen prikaz z najvišjo
stopnjo podrobnosti.
Predstavljen postopek torej uspešno generira začetni
teren, na katerem simulira hidravlično in termično ero-
zijo ter nato še rast koralnega grebena. Končni teren z
nanesenimi teksturami in izrisom morske gladine ima
prepričljiv videz tropskega otoka. S spreminjanjem pa-
rametrov lahko dobimo veliko različnih oblik otoka, kot
prikazujeta primera na sliki 4.
Z videzom tropskega otoka smo zadovoljni, hidra-
vlična in termična erozija skupaj oblikujeta razgiban
teren brez večjih vidnih napak. Dodan korak difuzije
sedimenta se dobro obnese, vendar ni fizično natančen.
Transport sedimenta in logika nalaganja sedimenta po-
trebujeta še nekaj izboljšav. Težava modela hidravlične
erozije je v tem, da je težko uravnovesiti vse konstante
v simulaciji. Simulacija hitro postane nestabilna, kar
povzroča večje napake na terenu. Maške [10] je v svojem
diplomskem delu dosegel boljši transport in nalaganje
sedimenta. Hitrosti izvajanja pa zaradi uporabe različne
strojne opreme ne moremo primerjati z njegovo.
Simulacija rasti koralnega grebena, ki je primarni
dosežek našega dela, daje prepričljive rezultate in se
izvaja hitro. Videz grebena je verodostojen, saj se
ob obali otoka ustvari razgiban in občasno prekinjen
greben. Naravni grebeni so mnogokrat prekinjeni in
različno oddaljeni od obale. Tako kot pri hidravlični
eroziji pa smo tudi pri simulaciji rasti koralnega grebena
imeli težave z uravnovešanjem konstant, saj ima že zelo
majhna sprememba velik vpliv na končni rezultat.
Dinamično nanašanje tekstur deluje hitro in daje pre-
pričljiv videz. Vzorčne teksture lahko zamenjamo in tako
na preprost način spremenimo videz otoka. Videz otoka
lahko spreminjamo tudi s spreminjanjem parametrov v
senčilniku, kot sta na primer gostota ponavljanja posa-
mezne vzorčne teksture in naklon terena, pri katerem
namesto teksture trave nanesemo teksturo skale.
Gladina morja veliko pripomore k prepričljivosti vi-
zualizacije otoka. Senčilnik morske gladine se dobro
obnese, saj nam daje tudi vizualno informacijo o globini
vode, kar je še posebno koristno v okolici koralnega
grebena. Prikaz sicer ni fizikalno natančen, saj zanemari
kot pogleda pri izrisu globine in jo vedno izrisuje, kot
da bi bil pogled od zgoraj navzdol. V praksi pa to
ne povzroča težav, saj teren večino časa opazujemo iz
zraka.
4 SKLEP
V delu smo predstavili postopek, ki na podlagi vhodnih
parametrov generira teren v obliki otoka, na katerem
v realnem času nato simulira hidravlično in termično
erozijo ter za tem še rast koralnega grebena. Na teren
dinamično nanaša teksture in izrisuje gladino morja.
Zadani cilj, da ima generiran teren prepričljiv videz
tropskega otoka z okoliškim koralnim grebenom, smo
po našem mnenju dosegli.
Končni teren je uporaben predvsem v strateških igrah,
kjer nanj večinoma gledamo iz oddaljenosti. Teren na-
mreč nima dovolj podrobnosti za igre s pogledom iz
prve osebe, kjer se igralec po terenu sprehaja in ga
raziskuje. Čas, potreben za generiranje otoka želenega
videza, je pri uporabi v računalniški igri lahko težava,
vendar bi jo z izboljšanjem implementacije generiranja
začetnega terena lahko odpravili. Generiranje začetnega
terena bi lahko pospešili tako, da bi ga namesto v jeziku
38 KOROŠEC, LEBAR BAJEC
C# implementirali v nižjenivojskem jeziku (npr. C++) ali
pa na senčilniku.
Terenu bi lahko dodatno izboljšali videz s tem, da bi
za njegovo predstavitev uporabili več plasti z različnimi
trdotami, kar bi morali nato upoštevati tudi pri simula-
cijah erozije [19]. Funkcije, ki generirajo začetni teren,
pa smo že zasnovali tako, da lahko izhod ene uporabimo
kot vhod druge. S tem imamo več možnosti pri gradnji
začetnega terena; nismo omejeni zgolj na obliko stožca.