Elektrotehniški vestnik 84(1-2): 30-38, 2017 Izvirni znanstveni članek Proceduralno generiranje tropskega otoka in koralnega grebena Oskar KoroSec, Iztok Lebar Bajec Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, VeČina pot 113, 1000 Ljubljana, Slovenija E-pošta: oskar.korosec@gmail.čom, ilb@fri.uni-lj.si Povzetek. V računalniški grafiki pogosto nastane potreba po prikazu večjih območij terena. Ročno oblikovanje le-tega je običajno časovno potratno. S proceduralnim generiranjem pa lahko ob minimalnih ročnih posegih ali celo brez njih ustvarimo večja območja terena z verodostojnim videzom v razmeroma kratkem času. V članku predstavljamo pročes preočeduralnega generiranja tropskega otoka. Začne se z generiranjem začetnega terena, sledi mu preoblikovanje s simuliranjem pročesov hidravlične in termične erozije katerima sledi še simulačija rasti koralnega grebena, ki se pogosto nahaja v neposredni okoliči tropskega otoka. Na teren dinamično nanašamo teksture glede na njegove lokalne značilnosti in med simulačijo omogočamo vizualizačijo sprememb terena v realnem času. Končni rezultat je verodostojen model tropskega otoka z okoliškim koralnim grebenom in ustreznimi teksturami. Ključne besede: pročeduralno generiranje, generiranje terena, termalna in hidravlična erozija, koralni greben, simulačija, GPE Procedural generation of a tropic island and coral reef In computer graphics there is a frequent need for displaying large vistas of a naturally looking terrain. Designing such terrain by hand is typically time consuming. With procedural generation, on the other hand, larger areas of a naturally looking terrain can be generated with or with no minimal intervention in a relatively short time. In this work we present a process of procedural generation of a tropical island with an associated corral reef. We start by generating a heightmap for the base terrain. The heightmap is then transformed by simulating processes of hydraulic and thermal erosion to achieve a more natural look of the terrain. As coral reefs often grow around tropical islands, we also simulate their growth as part of the last step. Real-time visualization is enabled during simulation, so that one can observe evolution of the terrain. Here we dynamically apply textures to the terrain based on its local characteristics. The result is a naturally looking model of a textured tropical island and corral reef. Keywords: procedural generation, terrain generation, thermal and hydraulic erosion, coral reef, simulation, GPU 1 Uvod članek je povzet po diplomskem delu prvega avtorja [1], ki prikaZe metode za proceduralno generiranje tropskega 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 vecjih terenih proceduralno generiranje mnogokrat racunsko intenzivna operacija, posamezne korake implementiramo na graficni procesni enoti (GPE), ki je zaradi svoje visokoparalelne arhitekture Prejet 13. februar, 2016 Odobren 15. marec, 2017 zmozšna hitrega procesiranja velike kolicšine podatkov. Najprej generiramo zacetni teren, nato pa za bolj verodostojen videz simuliramo hidravlicno in termicno erozijo. Ker v tropskih morjih v okolici otokov obicšajno rastejo koralni grebeni, izvedemo tudi simulacijo rasti le-teh. Na teren lepimo teksture, ustrezne njegovim znacšilnostim. Enega pomembnejših prispevkov na podrocju proceduralnega generiranja je dal Ken Perlin. Predstavil je nacin generiranja šuma, ki ga danes imenujemo Perlinov sšum [2]. Perlinov sšum se uporablja na veliko podrocšjih, eno izmed njih pa je proceduralna gradnja terena. Perlin je pozneje predstavil še šum Simplex [3], ki je za izracun hitrejši in še dodatno izboljša videz. V delu za gradnjo zacetnega terena uporabljamo slednjega, ker je ta še danes najboljši kompromis med hitrostjo izracuna, pomnilno potratnostjo in kakovostjo [4], [5]. Musgrave, Kolb in Mace [6] so bili med prvimi, ki so predstavili simuliranje erozije. Opisujejo tako termicno kot tudi hidravlicšno erozijo in nacšin prikaza generira-nega terena. Hidravlicna erozija simulira pretakanje vode po terenu, ki spodjeda material, ga prenaša v svojem toku in ga nato odlaga. Termicšna erozija pa zajema dejavnike, ki drobijo površino terena v drobir, ta pa nato drsi po strmih pobocjih. Simuliranje hidravlicne erozije sta predstavila tudi Beneš in Forsbach [7]. Mei, Decaudin in Hu [8] pa so prvi predstavili implementacijo hidravlicne erozije iz [7] na GPE. Jako in Toth [9] sta dodatno opisala še implementacijo termicne erozije na GPE. Generiranje terena s pomocjo hidravlicne in termicne erozije na GPE je v svojem diplomskem delu opisal tudi Maške [10]. V tem delu uporabljamo drugacen pristop k generiranju zacetnega terena kot PROCEDURALNO GENERIRANJE TROPSKEGA OTOKA IN KORALNEGA GREBENA 31 drugi in po simulaciji erozije simuliramo se rast koralnega grebena ter na teren nanesemo teksture. Virov, ki prikazujejo simuliranje rasti koral z namenom 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 visš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 zeleli, 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 stozca z nelinearno klancino: hA (x,y) = = 1 kh (i - KP) ; ce r(x,y) < kr 0; sicer, (i) kjer kh označuje višino stožca, kr polmer stožca in kp potenco, ki nadzoruje obliko klancine, r(x,y) = - xc)2 + (y - yc)2 (2) pa razdaljo tocke (x, y) do središča osnovne ploskve stožca (xc ,yc). Za izboljšanje verodostojnosti terena smo v naslednjem 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 implementiramo 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 oznacuje interval med visšinama dveh tonov, od katerih ima eden dvojno oziroma polovicno frekvenco drugega. V primeru funkcije šuma z višanjem frekvence šuma (skala šuma) zmanjšujemo tudi amplitudo. Na eni višinski karti smo uporabili vec oktav šuma tako, da smo vse oktave sešteli: N 1 he (*,y) = X; n (x2i ,y2i)-, (3) i=0 kjer je n vrednost šuma Simplex v koordinatah (x, y) in N število oktav. Pri zdruzevanju višinskih kart stozca in šuma smo se zgledovali po orodju Worldmachine3, kjer je mogoce vec višinskih kart zdruziti v eno na vec nacinov. Najboljše 1 sourceforge.net/projects/minepackage 2 www.redblobgames.com/maps/terrain-from-noise 3 www.world-machine.com Slika 1: Zacetni relief terena rezultate smo dobili, ko smo višinski karti zdruzili s potenciranjem: hc (x,y ) = hA (x,y )1+hB , (4) kjer je hA višina v višinski karti stozca, hB pa višina v višinski karti šuma Simplex. Vpliv šuma doloca parameter . Ker smo zeleli, da otok dobi videz vulkana, smo dodali moznost generiranja vulkanskega kraterja. Generirali smo ga tako, da smo vse vrednosti v zdruzeni višinski karti hc, ki so višje od dolocenega praga, cez prag preslikali navzdol. Postopek prikazuje enacba (5), kjer je h0 koncna višinska karta zacetnega terena, kc pa višina praga in s tem višina, na kateri se ustvari vulkanski krater. Slika 1 pa prikazuje relief, generiran z uporabo koncne višinske karte zacetnega terena. ho (x,y) = 2kc - hc(x,y); hc (x,y); ce hc (x,y) > kc sicer (5) 2.2 Erozija Kljub temu, da že zacetni 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 implementirali po viru [8], termično pa po [9]. Vira opisujeta metodi simuliranja teh pročesov 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 zelen erodiran videz. Voda med simulačijo ves čas izhlapeva. Za opis simulačije bomo uporabljali naslednje pomembne 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. Š t dodatno označujemo trenutni čas in s t časovni korak ene iteračije simulačije. Vsaka iteračija 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. Šosednje čeliče trenutne čeliče ozačujemo z L (leva), R (desna), T (gornja), B (spodnja). Za simuliranje pretakanja vode uporabljamo prirejen model, ki povezuje sosednje čeliče z navideznimi čevmi, po katerih se med njimi izmenjuje voda [13]. Ob začetku simulačije privzemamo, da je visšina vode po čelotnem terenu ničelna; d0 =0. Dez pomeni nastanek nove vode, kar za obravnavano čeličo (x, y) izračunamo kot dt = dt + tt, (6) Lt' = max < 0, Lt + tka g AfeL j (7) kjer pomeni površino prereza cevi, l dolžino cevi med dvema sosednjima celicama, Kg gravitacijski pospešek in Ah^ razliko višin med obravnavano in levo sosednjo celico (x - 1,y), ki se izračuna po enačbi: AhL = ht + dt' - hL - dL . (8) odvisnosti od kolicšine tekocše vode v celici in predvidene moci vseh odtocnih tokov [8], [10]. Pri odtocnem toku v smeri proti levi celici se tako odtocšni tok v naslednjem koraku simulacije izracšuna kot: Lt+r = Lt' min < 1 dt'e2 (9) r£ Ot kjer O/ pomeni množico vseh odtocnih tokov obravnavane celice {Lt', Rt',Tt', Bt'}, izracunanih z uporabo enacbe (7), J2 Ot' pa njihovo skupno vsoto. Pretakanje vode po navideznih ceveh se odraza v spremembi kolicšine tekocše vode j '' j ' . It+r - J2 Ot+T dt = dt +--j2-t, (10) kjer sta •■t+T /i?L rR rt tb \ lRt+r, Lt+T , Bt+T , Tt+T } in O t+T {Lt+T , Rt+T , Tt+T , Bt+T } kjer r oznacuje kolicino dezja, ki prispe v celico na enoto casa. Zaradi velikosti terena namrec ni smiselno simulirati dezja kot posamezne kaplje, temvec kot uniformno rast kolicine tekoce vode po posamezni celici terena. Za vsako celico hranimo njene odtocšne tokove L, R, T, B do štirih sosednjih celic, njeni pritocni tokovi pa so ustrezni odtocšni tokovi obravnavani celici sosednjih celic. V vsaki iteraciji simulacije se tok vode v odtocšnih tokovih pospesši zaradi razlike v hidrostaticšnem tlaku med celicami, kolicina tekoce vode pa se nato izracuna s kopicenjem vseh tokov v virtualnih ceveh. Odtocni tok v smeri proti levi celici za obravnavano celico izracunamo po enacbi: po vrsti mnozšici pritocšnih in odtocšnih tokov obravnavane celice v naslednjem cšasovnem koraku. Pri simuliranju pretakanja vode moramo upoštevati robne pogoje, ki izhajajo iz dejstva, da je teren koncen. Iztekanje vode iz terena omejimo tako, da vsaki cevi, ki nima sosednje celice, postavimo vrednosti ustreznih odtocšnih in pritocnih tokov na 0. Na primer: za celice brez levega soseda (0, y) postavimo tako levi odtocni tok L, kot tudi levi pritocni tok RL na 0. Voda med pretakanjem zaradi erozije pretvori del terena v sediment S = ks ||vt|| sin a, (11) ki ga nato prenaša in odlaga po terenu. V enačbi (11) ks pomeni konstanto kapačitete sedimenta, a pa lokalni naklon terena v čeliči. Tega za obravnavano čeličo izračunamo kot a = arccos(ñt • k). Pri tem ñt pomeni normalo na teren, ki jo pridobimo kot .hR - hL . m = -+ j km hT - hB , —-- + k, km ñ t m r, (12) kjer je razdalja med sosednjimi celicami terena, i, j, k pa po vrsti enotski vektorji, ki kanejo v smereh osi x, y in z. Hitrost vode v obravnavani celici vt = (vx, vy), ki jo potrebujemo v enacbi (11), pa izracunamo s pomocjo odtocšnih in pritocšnih tokov celice: RL+T - Lt+T + Rt+T - LR+t t+T i(dt' + dt'') Odtocni tokovi v smeri sosed R, T, B se izracunajo na enak nacin. Ker izracun odtocnih tokov upošteva visšinske razlike do vsake sosede individualno, obstaja mozšnost, da bi iz obravnavane celice odteklo vecš vode, kot je ta vsebuje. S tem bi kolicina tekoce vode v celici po izracunu postala negativna. Tezavo se rešuje z omejitvijo moci vsakega izmed odtocnih tokov v Tt+T - Bt+T + Tt+T - B T t+T (13) (14) ' i(dt' + dt'') Na zelo poloznih delih, kjer se a priblizuje 0, je vrednost S zelo nizka. Na taksšnih predelih pročes erozije ne bo imel občšutnega učšinka. To lahko omilimo tako, da a navzdol omejimo s poljubno minimalno vrednostjo. Na podlagi vrednosti S in raztopljenega sedimenta iz m Vx = 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 odlozi in pretvori nazaj v teren. Novo višino terena in količino raztopljenega sedimenta izračunamo po enačbah: ht+T — st ht - ke(S - st); če S > st ht + kd(S - st); sičer J st + ke(S - st); če S > st 1 st - kd(S - st); sičer, (15) (16) kjer je ke konstanta topljenja materiala, kd pa konstanta odlaganja materiala. Raztopljeni sediment prenasša vodni tok, kar opisuje advekčijska enačba |f + (vtVs) — 0. Enačbo rešujemo z Eulerjevim korakom nazaj v času, kar pomeni, da količšini raztopljenega sedimenta v obravnavani čeliči (x, y) priredimo vrednost, kije odvisna od vodnega toka v njej st"(x, y) — st'(x - vxt, y - vyr), (17) kjer koordinate (x - vxt, y - vyT) omejimo na območje terena. Kot je omenil ze Maške [10], postopek ne deluje zadovoljivo, saj je mogoče, da se v enem koraku količina sedimenta iz ene čeliče preslika v večš čelič. Opazili smo tudi, da se sediment pri nizšjih hitrostih vode večškrat prenaša v ravnih črtah. To je zato, ker se sediment v območšjih nizke hitrosti prenasša med čeličami, ki so neposredne sosede. To daje polju sedimenta grob in nenaraven videz, zato ga mi dodatno gladimo s simuliranjem difuzije sedimenta. Difuzijo simuliramo z dvodimenzionalno Laplačevo enačbo, ki jo numerično rešujemo z Jakobi iteračijami [14]. Izračun iteračije prikazuje enačba st+T — + sR + stT + sB nw (18) 2.2.2 Termična erozija: Hidravlična erozija oblikuje grob teren z veliko ostrimi robovi, kar je opazno predvsem na pobočjih ob vodnih strugah, ki se nenehno poglabljajo. S simuliranjem termične erozije, ki modelira pročes razgradnje kamnin v drobir zaradi temperaturnih 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 čevi, le da v tem primeru čevi prenasšajo drobir (terena) namesto vode. Vendar se običajno [9][10] zaradi boljsšega rezultata pri termičšni eroziji namesto von Neumannove okoliče, ki zaobjema zgolj najblizje štiri sosede obravnane čeliče, uporablja Moorova oko-liča, ki zajema vseh osem najblizjih sosednjih čelič N G {L, R, T, B, TL, TR, BL, BR}. To bi lahko sičer storili ze pri hidravlični eroziji, vendar menimo, da bi to povzdignilo kompleksnost implementačije brez večšjih izboljsšav pri rezultatu. Količina drobirja, ki jo lahko v eni iteračiji prenesemo v vsako od sosednjih čelič, je omejena z Mt = H tkm2, kjer je Ht = ht — min {i G N} razlika v višini terena v obravnavani čeliči in najnizšjo visšino terena v njej sosednjih čeličah. Ce to vrednost presezemo, začne algoritem osčilirati [9]. Nadaljnji pročes smo glede na vir [9] nekoliko poenostavili; vir upošteva tudi lokalno trdnost terena, ki je v nasšem delu ne. Drobir se pod vplivom gravitačije razsipa med nize lezšečše sosednje čeliče, ki z obravnavano čeličo tvorijo kot naklona, večji od kota mirovanja Ka. To je kritičen kot pobočja, ki ga lahko neki zrnati material še tvori. Ce klančina preseze kot mirovanja, material zdrsne. Kote naklona med obravnavano in posamezno sosednjo čeličo i g N izračunamo kot at = arctan ht-ht. t km Na podlagi teh sestavimo mnozšičo, ki vsebuje vse sosednje čeliče z naklonom, večjim od kota mirovanja Ka: Rt — {i € N| at > k, (20) kjer nW pomeni število čelič izmed L, R, T in B, ki drzijo vodo (dt" > 0). Robne pogoje smo poenostavili tako, da se koordinate čelič omejijo na območšje terena. Na primer: za vse čeliče, ki lezijo na levem robu terena (0, y), se koordinate leve sosednje čeliče (x — 1, y) omejijo na (0, y). Celičam, ki ne vsebujejo vode, nastavimo vrednost st" na 0. V zadnjem koraku vsake iteračije simulačije hidra-vličšne erozije uposštevamo, da se količšina tekočše vode spreminja tudi zaradi izhlapevanja. V nasšem delu predpostavljamo, da je temperatura ozračšja med simulačijo konstantna, zato hitrost izhlapevanja določšamo s konstanto kt. Pročes izhlapevanja opisuje enačba V vsako čeličo iz mnoziče Rt na podlagi višinske razlike z obravnavano čeličo prenesemo temu propor-čionalno količšino drobirja, v preostale čeliče ga ne prenašamo. Na primer: količino drobirja, ki se prenese v levo sosednjo čeličo, če ta spada v mnozičo Rt, izračunamo z enačbo: Lt Mt hL ^¿eRt ht (21) Zaradi vzporednega izvajanja simulačije drobirja ne prestavimo v čeliče takoj, temvečš za ta pročes uporabimo navidezne čevi. Končno višino vsake čeliče izračunamo podobno kot pri hidravlični eroziji, in sičer tako, da k trenutni visšini prisštejemo vse pritočšne tokove in odsštejemo vse odtočšne: ht+T — ht + ^ Mtn - ^ M' out t, (22) le da tokrat z dt+T — dt"(1 - ktt). (19) M0ut — {Lt, Rt, Tt, Bt, TLt, TRt, BLt, BRt} L s 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 Mtn = 0). Pri robnih celicah, celicah, ki leZijo tik ob robu terena in zato nimajo levega ali desnega, ali zgornjega, ali spodnjega soseda, Jakobijeve iteracije ne racunamo, temvec Ot+T priredimo vrednost O0. Jakobijeve iteracije prav tako ne racunamo pri celicah, ki so nad gladino morja, a v nasprotju s prej v teh primerih Ot+T priredimo vrednost 0, ker celice ne izpolnjujejo pogojev za nastanek koral. V našem delu podatkov o višini koralnega grebena ne hranimo loceno, temvec ga štejemo kot teren. Rast grebena (in s tem dvig višine terena) je neposredno odvisna od stopnje kalcifikacije. Višino terena po iteraciji simulacije izracunamo z enacbo ht+T = ht + ct t. (29) Rast koralnega grebena in posledicno 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 izracšunamo po enacšbi Wt+T = wt + kw t, (30) kjer je kw konstanta rasti višine morske gladine. Vpliv simulacije rasti koralnega grebena na koncni videz proceduralno generiranega otoka prikazuje slika 3. 2.5 Implementacija Simuliranje naravnih procesov, kot sta hidravlicna in termicna erozija, je obicajno racunsko zahtevna operacija. Cas izvajanja simulacije je pomemben še posebno takrat, ko zelimo rezultate opazovati v realnem casu, zato v teh primerih posegamo po GPE. V naši implementaciji uporabljamo okolje Unity in sencilnike 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 obicajno sivinska. V naši implementaciji za posamezen barvni kanal uporabljamo 32-bitno predstavitev s plavajoco vejico (float). Vsak od predstavljenih algoritmov hrani podatke o nekaterih kolicinah (npr. višina vode), ki se uporabljajo med posameznimi koraki in iteracijami simulacije. Ti podatki so vezani na posamezne tocke v višinski karti, zato jih hranimo na enak nacin kot višinsko karto, tj. v teksturi. Za shranjevanje vsake kolicine tako kot za višinsko karto potrebujemo en barvni kanal. Ker v naši implementaciji uporabljamo teksture s štirimi kanali, ki se v sencilniku preslika v float4, nam to omogoca v eni teksuri shranjevati podatke o vec razlicnih kolicinah. Razvili smo tri sencilnike, pri cemer prvi izvaja hi-dravlicno erozijo, drugi termicno erozijo, tretji pa skrbi za rast koral. Vsak sencilnik simulacijo pripadajocega procesa izvaja v vec iteracijah, v posamezni iteraciji pa dolocene teksture obdela veckrat. Sencilnik Compute-Shader je sestavljen iz vec funkcij, med katerimi lahko poljubne oznacimo kot jedrne. Pozenemo ga tako, da pozenemo eno od jedrnih funkcij. Z uporabo vec jedrnih funkcij lahko teksturo z enim sencšilnikom obdelamo v vec razlicnih korakih. Naša koda je organizirana temu primerno, napisana pa je v jeziku HLSL razlicice DirectX 11. V prvem koraku naše implementacije generiramo višinsko karto zacetnega terena in jo shranimo v obliki teksture. Na tej tocki je pripadajoca tekstura shranjena v glavnem pomnilniku racunalnika, zato jo pred zacetkom izvajanja simulacije naravnih procesov prenesemo v pomnilnik GPE. V pogonu Unity so teksture, ki so shranjene izkljucno v pomnilniku GPE, objekti tipa RenderTexture. V sencilnikih uporabljamo le takšen tip tekstur; tekstur ne prenašamo med glavnim pomnilnikom racunalnika in pomnilnikom GPE, saj je to casovno potratna operacija. Ker se vizualizacija prav tako izvaja v sencilnikih, je prenašanje nepotrebno. Ker pa rezulatatov posameznega koraka iteracije ne smemo pisati v isto teksturo, ker bi zaradi vzporednega izvajanja s tem lahko unicili 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 obdelave zapišejo v izhodne teksture. Posledicno bi morali po vsaki koncani jedrni funkciji rezultate iz izhodnih prekopirati nazaj v vhodne teksture. Temu kopiranju smo se izognili z izmenicnim menjavanjem vhodnih in izhodnih tekstur. Izhodne teksture prejšnje jedrne funkcije nastavimo kot vhodne teksture naslednje. Menjavanje izvajamo samo v sklopu posamicne iteracije. Kadar se 4 docs.unity3d.com/Manual/ComputeShaders 36 KOROŠEC, LEBAR BAJEC menjavanje ne izvede sodo-krat, teksture vseeno kopiramo. Iteracije simulacije izvajamo v zanki, v kateri v določenem vrstnem redu poZenemo jedrne funkcije ustreznega senčilnika. V namen nadzora simulacije smo implementirali preprost graficni uporabniški vmesnik. Z njim lahko spreminjamo dolocene parametre in vkla-pljamo ter izklapljamo posamezne korake simulacije. Vrstni red zagona sencilnikov naceloma ni pomemben, a moramo paziti, da tistega, ki je namenjen rasti koral, ne uporabljamo hkrati s hidravlicšno oz. termicšno erozijo. Koralnega grebena namrecš ne hranimo locšeno, temvecš kot teren, erozija (tako hidravlicna kot termicna) pa teren preoblikuje in posledicno spremeni videz koralnega grebena, kar ni zazšeleno. 2.6 Vizualizacija Višinska karta v vsakem pikslu hrani višino pripadajoce tocke na terenu. Za prikaz terena uporabljamo metodo imenovano odmiki (angl. displacement mapping) [16]. Njena tezava je, da za prenos podrobnosti višinske karte na model potrebuje veliko oglišc. V optimalnem primeru bi bil model predstavljen z enakim sštevilom oglisšcš, kot ima višinska karta pikslov. V praksi to pomeni modele z izjemno visokim številom oglišc in posledicno velikim številom trikotnikov. Problem lahko rešimo z uporabo strojne teselacije (angl. hardware tessellation) [17], ki model v osnovi predstavi z majhnim številom oglišc in trikotnikov, te pa nato z uporabo sencšilnikov dinamicšno deli na vec manjših, pri cemer ustvari vec oglišc in vec podrobnosti. V naši implementaciji uporabljamo strojno teselacijo fiksne stopnje. Osvetlitev izracunavamo z Lambertovim modelom [18, str. 267-268] c = (l • n)cmci, (31) kjer osvetljenost v neki tocki izracunamo na podlagi vpadnega kota svetlobe l in normale na teren v tej tocki n. Parametra cm in cl po vrsti pomenita barvo materiala v tocki in barvo vira svetlobe. Za osvetljevanje uporabljamo smerno oziroma oddaljeno luc [18, str. 264], ki nima pozicije. Luc definira samo vektor smeri, barvo in intenziteto. V enacbi (31) je intenziteta ze všteta v barvo lucši. Naš cilj je bilo generiranje tropskega otoka, k cemur veliko pripomorejo teksture. Osnovne sštiri teksture, ki jih uporabljamo, so: trava (zelene površine), skalovje, pesek in morsko dno. Teksture smo dobili na spletni strani Textures5. V sencilniku na podlagi višine in naklona terena ter visšine vode v vsaki tocški terena vzorcne teksture zdruzujemo in ob upoštevanju osvetlitve izracunamo barvo v tej tocki. Logika zdruzevanja tekstur temelji na opažanjih iz narave in osebne predstave o videzu tropskega otoka. Strma pobocja so redko porašcena, medtem ko na ravninah prevladujejo zelene 5 www.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 plaZa, zato smo pod gladino vode in na oZjem pasu obale nad njo nanesli teksturo peska, vendar le tam, kjer je obala dovolj poloZna. 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 nanasšanju teksture skalovja smo uposštevali tudi, kje je med hidravlicno simulacijo tekla voda. V dodatni teksturi hranimo števec prisotnosti vode v doloceni tocki na terenu v zadnjem krajšem casovnem obdobju. Stevec med simulacijo hidravlicne erozije povecamo, ce je v pripadajoci tocki prisotna voda, in zmanjšamo, ce ni. Stevec 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 dosezemo, da na obmocšjih, kjer so bile vodne struge, nekaj cšasa ne raste trava. Podobno v isti dodatni teksturi hranimo tudi sštevec kolicšine rasti koralnega grebena, kjer tega povecujemo premo sorazmerno z rastjo koralnega grebena. Kjer ima ta števec višjo vrednost, je vecja tudi prisotnost teksture morskega dna. Ker je otok v naravnem okolju obkrozšen z morjem, smo dodali prikaz tudi slednjega. Morja v okolici tropskih otokov so obicšajno zelo cšista, zato v plitvih predelih pogosto vidimo dno. Intenziteta svetlobe v neki tocki v globini morja je funkcija dolzine poti svetlobnih zarkov skozi vodno maso [11]. V naši aplikaciji na teren in morje v pretezni meri gledamo od zelo dalec, zato pri izracšunu barve morske gladine zanemarjamo dejstvo, da se svetlobni zarki, ko iz zraka prehajajo v vodo, lomijo, kar vpliva na dolzšino njihove poti skozi vodno maso. Barvo morske gladine tako dolocamo zgolj s spreminjanjem prosojnosti osnovne, temno modre barve v odvisnosti globine vode v obravnavani tocški cw.a = e-g KA, (32) kjer ka nadzoruje moc slabljenja svetlobe (motnost vodne mase). Izracšun opravlja locšen sencšilnik, ki skrbi zgolj za izracšun barve vsake tocške na povrsšini, ki pomeni morsko gladino. 3 Rezultati Uporabljamo višinske karte v velikosti 512x512 tock. Zacšetni teren se, predvsem zato, ker je opravilo prepušceno centralni procesni enoti, v povprečju zgradi v 2,2 s. Ker se ta korak izvede samo enkrat v celotnem procesu, to ni motecše. Simulacije naravnih procesov brez vizualizacije se izvajajo hitro; 1000 iteracij hidravlicne erozije se v povprečju izvede v 4 ms, 1000 iteracij termicne erozije v 1 ms in 1000 iteracij rasti koralnega grebena v 2 ms. Vizualizacija dosega povprecno 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 zelene velikosti koralnega grebena. Brez vizualizacije pa generiranje traja priblizno 2,3 s, pri cemer simuliranje naravnih procesov traja 35 ms. Vse vrednosti veljajo za racunalnik s procesorjem Intel Core i7 6700K, 16 GB delovnega pomnilnika in graficno kartico Nvidia GeForce GTX 1070, pri cemer smo v pogonu Unity 5 imeli nastavljen prikaz z najvišjo stopnjo podrobnosti. Predstavljen postopek torej uspešno generira zacetni teren, na katerem simulira hidravlicno in termicno erozijo ter nato še rast koralnega grebena. Koncni teren z nanesenimi teksturami in izrisom morske gladine ima prepricljiv videz tropskega otoka. S spreminjanjem parametrov lahko dobimo veliko razlicšnih oblik otoka, kot prikazujeta primera na sliki 4. Z videzom tropskega otoka smo zadovoljni, hidra-vlicna in termicna erozija skupaj oblikujeta razgiban teren brez vecjih vidnih napak. Dodan korak difuzije sedimenta se dobro obnese, vendar ni fizicno natancen. Transport sedimenta in logika nalaganja sedimenta potrebujeta še nekaj izboljšav. Tezava modela hidravlicne erozije je v tem, da je tezško uravnovesiti vse konstante v simulaciji. Simulacija hitro postane nestabilna, kar povzroca vecje napake na terenu. Maške [10] je v svojem diplomskem delu dosegel boljši transport in nalaganje sedimenta. Hitrosti izvajanja pa zaradi uporabe razlicne strojne opreme ne moremo primerjati z njegovo. Simulacija rasti koralnega grebena, ki je primarni dosezek našega dela, daje prepricljive rezultate in se izvaja hitro. Videz grebena je verodostojen, saj se ob obali otoka ustvari razgiban in obcasno prekinjen greben. Naravni grebeni so mnogokrat prekinjeni in razlicno oddaljeni od obale. Tako kot pri hidravlicni eroziji pa smo tudi pri simulaciji rasti koralnega grebena imeli tezave z uravnovešanjem konstant, saj ima ze zelo majhna sprememba velik vpliv na koncni rezultat. Dinamično nanašanje tekstur deluje hitro in daje preprič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 posamezne vzorčne teksture in naklon terena, pri katerem namesto teksture trave nanesemo teksturo skale. Gladina morja veliko pripomore k prepričljivosti vi-zualizačije otoka. Senčilnik morske gladine se dobro obnese, saj nam daje tudi vizualno informačijo o globini vode, kar je še posebno koristno v okoliči koralnega grebena. Prikaz sičer 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 tezav, 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 čilj, 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 namreč nima dovolj podrobnosti za igre s pogledom iz prve osebe, kjer se igraleč po terenu sprehaja in ga raziskuje. Cas, potreben za generiranje otoka zelenega videza, je pri uporabi v računalniški igri lahko tezava, vendar bi jo z izboljšanjem implementačije generiranja začetnega terena lahko odpravili. Generiranje začetnega terena bi lahko pospesš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 simulacijah erozije [19]. Funkcije, ki generirajo začetni teren, pa smo ze zasnovali tako, da lahko izhod ene uporabimo kot vhod druge. S tem imamo več moznosti pri gradnji začetnega terena; nismo omejeni zgolj na obliko stozca. [19] O. St'ava, B. Benes, M. Brisbin, and J. Krivanek, "Interactive terrain modeling using hydraulic erosion," in Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Eurographics Association, 2008, pp. 201-210. Oskar Korošec je diplomiral (2016) na Fakulteti za računalništvo in informatiko v Ljubljani. Zaposlen je v podjetju v zasebnem sektorju, kjer se ukvarja z razvojem mobilnih aplikačij in iger. Literatura [1] O. Korošec, Proceduralno generiranje tropskega otoka. Fakulteta za računalništvo in informatiko, Univerza v Ljubljani, 2016, diplomsko delo. [2] K. Perlin, "An image synthesizer," ACM SIGGRAPH Computer Graphics, vol. 19, no. 3, pp. 287-296, Jul. 1985. [3] -, "Noise hardware," in Real-Time Shading Languages - SIGGRAPH Course Notes, M. Olano, Ed., 2002. [4] W. L. Raffe, F. Zambetta, and X. Li, "A survey of procedural terrain generation techniques using evolutionary algorithms," in 2012 CEC, IEEE Congress on Evolutionary Computation. IEEE, 2012, pp. 1-8. [5] T. J. Rose and A. G. Bakaoukas, "Algorithms and approaches for procedural terrain generation-a brief review of current techniques," in VS-GAMES 2016, 8th International Conference on Games and Virtual Worlds for Serious Applications. IEEE, 2016, pp. 1-2. [6] F. K. Musgrave, C. E. Kolb, and R. S. Mace, "The synthesis and rendering of eroded fractal terrains," SIGGRAPH Comput. Graph., vol. 23, no. 3, pp. 41-50, Jul. 1989. [7] B. Beneš and R. Forsbach, "Visual simulation of hydraulic erosion," Journal of WSCG, vol. 10, no. 1-2, pp. 79-86, 2002. [8] X. Mei, P. Decaudin, and B.-G. Hu, "Fast hydraulic erosion simulation and visualization on GPU," in Proceedings of the 15th Pacific Conference on Computer Graphics and Applications. IEEE, 2007, pp. 47-56. [9] B. Jako and B. Toth, "Fast hydraulic and thermal erosion on GPU," in Eurographics 2011 - Short Papers, N. Avis and S. Lefebvre, Eds. The Eurographics Association, 2011, pp. 57-60. [10] L. Maške, Simulacija in vizualizacija erozije terena z uporabo GPE. Fakulteta za racšunalnisštvo in informatiko, Univerza v Ljubljani, 2013, diplomsko delo. [11] T. Nakamura and T. Nakamori, "A geochemical model for coral reef formation," Coral Reefs, vol. 26, no. 4, pp. 741-755, 2007. [12] -, "A simulation model for coral reef formation: Reef topographies and growth patterns responding to relative sea-level histories," in Sea Level Rise, Coastal Engineering, Shorelines and Tides. Nova Science Publishers, 2011, pp. 251-262. [13] J. F. O'Brien and J. K. Hodgins, "Dynamic simulation of splashing fluids," in Proceedings of Computer Animation '95. IEEE, 1995, pp. 198-205. [14] J. M. Cecilia, J. M. Garcia, and M. Ujaldon, "CUDA 2D stencil computations for the Jacobi method," in International Workshop on Applied Parallel Computing. Springer, 2010, pp. 173-183. [15] M. Dermastia, T. Kiauta, and T. Turk, Oxfordova ilustrirana enclikopedija žive narave, 2nd ed., M. J. Coe, Ed. Ljubljana: DZS, 1995. [16] L. Szirmay-Kalos and T. Umenhoffer, "Displacement mapping on the GPU - state of the art," Computer Graphics Forum, vol. 27, no. 6, pp. 1567-1592, 2008. [17] M. NieBner, B. Keinert, M. Fisher, M. Stamminger, C. Loop, and H. Schafer, "Real-time rendering techniques with hardware tessellation," Computer Graphics Forum, vol. 35, no. 1, pp. 113137, 2016. [18] E. Angel and D. Shreiner, Interactive Computer Graphics: A Top-Down Approach with Shader-Based OpenGL, 6th ed. USA: Addison-Wesley Publishing Company, 2011. Iztok Lebar Bajec je diplomiral (2000), magistriral (2002) in doktoriral (2005) na Fakulteti za računalništvo in informatiko. Na isti fakulteti je trenutno izredni profesor. Raziskovalno se ukvarja z modeliranjem in simulačijo skupinskega vedenja ter večvrednostno logiko v kvantnih čeličnih avtomatih.