Fakulta elektrotechnická. Martin Fousek. Studijní program: Informatika a výpočetní technika

ˇ e vysoké uˇcen´ı technické v Praze Cesk´ Fakulta elektrotechnická

ˇ VUT FEL katedra pocˇı´tacˇu˚ C

Diplomová práce

Simulace vzniku a v´ yvoje p´ıseˇ cn´ ych dun Martin Fousek

Vedouc´ı práce: Ing. Jaroslav Sloup

Studijn´ı program: Informatika a v´ ypoˇcetn´ı technika leden 2006

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem svou diplomovou práci vypracoval samostatnˇe a pouˇzil jsem pouze podklady uvedené v pˇriloˇzeném seznamu. Nemám závaˇzn´ y d˚ uvod proti uˇzit´ı tohoto ˇskoln´ıho d´ıla ve smyslu §60 Zákona ˇc. 121/2000 Sb., o právu autorském, o právech souvisej´ıc´ıch s právem autorsk´ ym a o zmˇenˇe nˇekter´ ych zákon˚ u (autorsk´ y zákon).

V Praze dne 27.1. 2006

.............................................................

ii

Abstract This diploma thesis is focused on a simulation of wind activity in sandy areas. Main goal is creation and evolution of dunes, large scale patterns created by wind. Used method is not based on exact physical processes, due to the enormous complexity of such approach. Like in similar works, quite simple equations, that are the results of field observations, were used instead.

Abstrakt Tato diplomová práce se zab´ yvá simulac´ı vlivu vˇetru na ˇcistˇe p´ıseˇcn´ y povrch s kamenit´ ym podloˇz´ım, pˇredevˇs´ım vznikem dun a v´ yvojem jejich tvaru. Metoda k tomu pouˇzitá nen´ı postavena na pˇresném fyzikáln´ım popisu proudˇen´ı vˇetru p´ıseˇcnou krajinou, jehoˇz vyjádˇren´ı by bylo krajnˇe komplikované a v´ ypoˇcetnˇe velmi nároˇcné. Stejnˇe jako v ostatn´ıch publikovan´ ych prac´ıch na podobné téma se i v této pouˇz´ıvá pomˇernˇe jednoduch´ ych vztah˚ u a rovnic, odvozen´ ych z pozorovan´ı základn´ıch dˇej˚ u v p´ıseˇcn´ ych krajinách.

iii

Obsah ´ 1 Uvod

2

´ 2 Uvod do problematiky 2.1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Pohyb p´ısku zp˚ usoben´ y vˇetrem . . . . . . . . . . . . . . . 2.3 Ukládán´ı p´ısku . . . . . . . . . . . . . . . . . . . . . . . . ´ adán´ı p´ısku v malém mˇeˇr´ıtku aneb wind-ripples 2.3.1 Ukl´ 2.3.2 Ukládán´ı p´ısku ve velkém mˇeˇr´ıtku aneb duny . . . 2.4 Typy dun . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Prostˇred´ı umoˇzn ˇuj´ıc´ı vznik uveden´ ych typ˚ u dun . . . . . . 2.6 C´ıle této diplomové práce . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

3 3 4 4 5 5 7 7 8

3 Popis metod pouˇ zit´ ych v prac´ıch na podobn´ e t´ ema 3.1 Simulace p´ıseˇcn´ ych oblast´ı . . . . . . . . . . . . . . . . 3.2 Simulace wind-ripples pomoc´ı bump-mapping . . . . . 3.3 Simulace wind-ripples jejich pˇr´ım´ ym zobrazen´ım . . . 3.4 Integrodiferenciáln´ı model wind-ripples . . . . . . . . 3.5 Simulace vzniku a v´ yvoje dun bunˇeˇcn´ ym automatem . 3.6 Simulace vzniku a v´ yvoje dun na diskrétn´ı mˇr´ıˇzce . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

10 10 10 11 12 14 14

4 Teoretick´ y rozbor modelu 4.1 Základn´ı vlastnosti modelu . . . 4.2 Inicializace . . . . . . . . . . . . 4.3 Vˇetrná eroze . . . . . . . . . . . 4.4 Uloˇzen´ı . . . . . . . . . . . . . . 4.5 Pˇresun p´ısku vlivem gravitace . . 4.6 V´ıtr vanouc´ı libovoln´ ym smˇerem 4.6.1 Vˇetrné pole . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

16 16 17 17 17 20 20 20

5 Implementace 5.1 Model . . . . . . . . . . . . . . 5.1.1 Vytvoˇren´ı vˇetrného pole 5.1.2 Vˇetrná eroze a ukládán´ı 5.1.3 Eroze vlivem gravitace .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

22 23 23 24 25

iv

. . . .

5.2

5.3

5.4

5.1.4 Aktualizace vˇetrného st´ınu . . . . . . . . . . 5.1.5 Aktualizace hodnoty href . . . . . . . . . . . Visualizace . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 V´ ypoˇcet normálov´ ych vektor˚ u vrcholu . . . . 5.2.2 Dynamické st´ıny . . . . . . . . . . . . . . . . LOD . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 V´ yhody a nev´ yhody pouˇzitého pˇr´ıstupu . . . 5.3.2 Struˇcn´ y popis neoptimalizovaného algoritmu 5.3.3 Zaveden´ı prahové vzdálenosti . . . . . . . . . 5.3.4 Obalován´ı prahov´ ych vzdálenost´ı . . . . . . . 5.3.5 Generován´ı obecného triangle strip . . . . . . Vstup / v´ ystup . . . . . . . . . . . . . . . . . . . . . 5.4.1 Komprese dat . . . . . . . . . . . . . . . . . . 5.4.2 V´ıce dat v jednom souboru . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

26 27 28 28 29 31 33 34 34 36 36 39 39 40

6 Ovl´ ad´ an´ı programu 42 6.1 Pˇriloˇzen´ y kód . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2 Uˇzivatelské prostˇred´ı a pohyb kamery . . . . . . . . . . . . . 42 6.3 Poˇzadavky na hardware . . . . . . . . . . . . . . . . . . . . . 43 7 Popis proveden´ ych experiment˚ u 7.1 Závislost na dostupném mnoˇzstv´ı p´ısku 7.2 Závislost na nastaven´ı parametru L0 . . 7.3 LOD . . . . . . . . . . . . . . . . . . . . 7.4 Umˇelé objekty ve scénˇe . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

44 45 45 45 45

8 Z´ avˇ er

53

9 N´ avrhy dalˇ s´ıho rozvoje t´ ematu

54

A Pˇ r´ılohy A.1 Podrobn´ y popis uˇzivatelského prostˇred´ı A.1.1 Run . . . . . . . . . . . . . . . . A.1.2 Camera positions . . . . . . . . . A.1.3 Visualization . . . . . . . . . . . A.1.4 Wind . . . . . . . . . . . . . . . A.1.5 Terrain . . . . . . . . . . . . . . A.1.6 Average height . . . . . . . . . . A.1.7 Input / Output . . . . . . . . . .

58 58 58 58 59 60 60 61 61

1

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

Kapitola 1

´ Uvod V pouˇstn´ıch oblastech celého svˇeta lze nalézt p´ıseˇcné duny rozmanit´ ych tvar˚ u a vˇsech moˇzn´ ych velikost´ı. Tyto u ´tvary, pˇrestoˇze dosahuj´ı v´ yˇsky aˇz des´ıtek metr˚ u, jsou sloˇzeny z p´ıseˇcn´ ych zrnek, tedy ˇcásteˇcek vˇetˇsinou menˇs´ıch neˇz jeden milimetr. Je proto zaj´ımavé zab´ yvat se studiem faktor˚ u, které nˇeco takového umoˇzn ˇuj´ı a na základˇe tohoto studia pak navrhovat metody simulace, které s menˇs´ı ˇci vˇetˇs´ı pˇresnost´ı dosahuj´ı v´ ysledk˚ u podobn´ ych pˇr´ırodˇe. Pˇresto prac´ı na podobné téma bylo publikováno jen nˇekolik. Tato diplomová práce se k nim pˇridává a soustˇred´ı se pˇredevˇs´ım na visualizaci a drobná rozˇs´ıˇren´ı jiˇz navrˇzeného modelu, kter´ y vˇsak nikdy nebyl pouˇzit v oblasti poˇc´ıtaˇcové grafiky. V tomto textu bude postupnˇe vysvˇetleno, jaké fyzikáln´ı procesy se pod´ılej´ı na tvorbˇe dun a také na tvorbˇe jevu o hodnˇe menˇs´ıho mˇeˇr´ıtka naz´ yvaného vˇetrné vlnky (wind ripples). Jaké metody byly pouˇzity v jiˇz publikovan´ ych prac´ıch a bude popsán model spoleˇcnˇe s implementac´ı pouˇzit´ y v této diplomové práci. V posledn´ıho dvou kapitolách pak je shrnuto, jak´ ych v´ ysledk˚ u tato práce dosáhla a jak´ ych ne a tedy jak´ ym smˇerem by se mˇel ub´ırat dalˇs´ı v´ yvoj.

2

Kapitola 2

´ Uvod do problematiky V této kapitole je popsána terminologie pouˇz´ıvaná v celém textu. Dále jsou uvedeny dva základn´ı pozorované jevy, které se daj´ı pˇri tématu vliv vˇetru na p´ıseˇcn´ y povrch simulovat. Nakonec je vysvˇetleno, ˇc´ım se tato diplomová práce zab´ yvala a ˇc´ım ne, a zd˚ uvodnˇeno proˇc tomu tak je.

2.1

Terminologie

Ke zpˇrehlednˇen´ı popisovaného tématu by mˇel pˇrispˇet soupis dále pouˇz´ıvan´ ych term´ın˚ u. Vybrané a dále popisované informace z prac´ı ostatn´ıch autor˚ u jsou také popisovány pomoc´ı této terminologie v rámci snahy o sjednocen´ı. • T´ımto textem je dále oznaˇcován text této diplomová práce. • Dvourozmˇernou mˇr´ıˇzkou, pokud nen´ı uvedeno jinak, se rozum´ı datová struktura, do které se pˇristupuje pomoc´ı dvou index˚ u x a y. Jej´ı grafická reprezentace je pravidelná, ˇctvercová mˇr´ıˇzka. • Buˇ nkou se rozum´ı jedna libovolná pozice v mˇr´ıˇzce. • h(x, y) je hodnota uloˇzená v buˇ nce urˇcené (x, y). Grafická reprezentace je v´ yˇska buˇ nky v mˇr´ıˇzce. ~ oznaˇcen´ı pro vektor pˇresunu. Je urˇcen rozd´ılem pozic dvou bunˇek • L ~ = (x, y)−(x0 , y 0 ). Jeho velikost L je poˇcet bunˇek mezi (x, y) a (x0 , y 0 ) L vˇcetnˇe (x, y). • q znaˇc´ı mnoˇzstv´ı pˇreneseného p´ısku. Jedná se vˇzdy o ˇc´ıslo, o které je sn´ıˇzena hodnota buˇ nky jedné a nav´ yˇsena hodnota buˇ nky jiné. Zde se také sluˇs´ı upozornit, ˇze anglické term´ıny, u nichˇz nebyl znám odborn´ y ˇcesk´ y pˇreklad, z˚ ustaly v p˚ uvodn´ım znˇen´ı obˇcas s titulky.

3

2.2

Pohyb p´ısku zp˚ usoben´ y vˇ etrem

Hlavn´ım ˇcinitelem, kter´ y v p´ıseˇcn´ ych oblastech zp˚ usobuje pˇresun materiálu, je v´ıtr. Pro lepˇs´ı pochopen´ı toho, jak zde nakonec vznikaj´ı tvary dosahuj´ıc´ı v´ yˇsky des´ıtek metr˚ u je tˇreba se uch´ ylit k pozorován´ı vlivu vˇetru na ˇcásteˇcky rozmˇeru okolo 1mm a ménˇe, tedy p´ıseˇcn´ ych zrnek. Existuj´ı dva pozorované zp˚ usoby pohybu jednotliv´ ych zrnek p´ısku. V´ yraznˇejˇs´ı vliv na pˇresun materiálu má prvn´ı z nich naz´ yvan´ y saltation. T´ımto zp˚ usobem se pohybuje zhruba 75% pˇresunovaného materiálu. Tento proces je odstartován t´ım, ˇze rychlost vˇetru pˇresáhne práh naz´ yvan´ y fluid treshold. P˚ usoben´ım tlaku vˇetru této rychlosti jsou z p´ıseˇcného povrchu vyráˇzena jednotlivá zrnka p´ısku. Takto vyraˇzené zrnko je vˇsak ve vˇetˇsinˇe pˇr´ıpad˚ u pˇr´ıliˇs tˇeˇzké na to, aby bylo trvale unáˇseno vˇetrem, a proto opisuje balistickou kˇrivku a dopadá zpˇet na povrch. Po dopadu se m˚ uˇze odrazit nebo b´ yt pohlceno povrchem. Kaˇzdopádnˇe tento dopad vyráˇz´ı z povrchu dalˇs´ı zrnka, která jsou urychlena vˇetrem, dopadaj´ı na povrch, vyráˇz´ı z povrchu dalˇs´ı zrnka a proces se kaskádovitˇe ˇs´ıˇr´ı. Jakmile je takov´ yto proces odstartován, rychlost vˇetru uˇz nemus´ı b´ yt tak velká aby tlak vˇetru vyráˇzel zrnka z povrchu. Rychlost vˇetru dostaˇcuj´ıc´ı k zachován´ı procesu je pak taková, která vyráˇzen´ ym zrnk˚ um dodá alespoˇ n tu samou energii, kterou cel´ y systém ztrác´ı pˇri dopadu zrnek zpˇet na povrch. Tato udrˇzovac´ı rychlost se oznaˇcuje jako impact treshold. V´ yˇska letu zrnka se udává v jednotkách aˇz des´ıtkách cm. Pozorován´ım a mˇeˇren´ım bylo zjiˇstˇeno, ˇze se stoupaj´ıc´ı rychlost´ı vˇetru mnoˇzstv´ı pˇrenáˇseného p´ısku stoupá exponenciálnˇe. Tˇeˇzká zrnka p´ısku 1 se u ´ˇcastn´ı procesu saltation jen pˇri siln´ ych vˇetrn´ ych smrˇst´ıch. Vˇetˇsinu ˇcasu jsou vˇsak souˇcást´ı druhého procesu oznaˇcovaného creep 2 . Pˇri nˇem nejsou tˇeˇzká zrnka vyráˇzena vˇetrem ani dopadaj´ıc´ımi lehk´ ymi zrnky pˇr´ımo do vzduchu, ale pod vlivem náraz˚ u dopadaj´ıc´ıch zrnek se pouze pomalu kutál´ı po povrchu. Tento zp˚ usob se pod´ıl´ı zbyl´ ymi 25% na mnoˇzstv´ı pˇresunovaného p´ısku.

2.3

Ukl´ ad´ an´ı p´ısku

Má-li docházet k akumulaci p´ısku, je potˇreba, aby se rychlost vˇetru unáˇsej´ıc´ıho p´ısek na urˇcitém m´ıstˇe sniˇzovala. D˚ usledkem toho se sn´ıˇz´ı i objem pˇrenáˇseného materiálu a dojde k ukládán´ı. Takovéto zpomalován´ı vˇetru nastává mimo jiné za pˇrekáˇzkou nebo v terénn´ıch depres´ıch. Ke zpomalen´ı vˇetru vˇsak m˚ uˇze doj´ıt i bez pˇr´ımého vlivu terénu, d´ıky jevu oznaˇcovanému saltation drag. Tento jev je v´ ysledkem tˇren´ı mezi ˇcásticemi vzduchu a p´ıseˇcn´ ymi zrnky a je nejsilnˇejˇs´ı pˇri povrchu, kde je koncentrace zrnek ve vzduchu nejvyˇsˇs´ı. Zaj´ımav´ ym d˚ usledkem velmi siln´ ych vˇetr˚ u pak je zdánlivˇe paradoxn´ı 1 2

S pr˚ umˇerem vˇetˇs´ım neˇz 1 mm. Obˇcas se také pro ten sam´ y jev objevuje oznaˇcen´ı reptation.

4

zv´ yˇsená intenzita ukládán´ı. Se stoupaj´ıc´ı rychlost´ı vˇetru stoupá koncentrace zrnek, zvyˇsuje se tˇren´ı, rychlost vˇetru klesá, docház´ı k ukládán´ı a kolobˇeh se opakuje.

2.3.1

´ ad´ Ukl´ an´ı p´ısku v mal´ em mˇ eˇ r´ıtku aneb wind-ripples

Jak anglick´ y název napov´ıdá, jedná se o vlnky tvarované vˇetrem v p´ıseˇcném povrchu. Jsou charakteristick´ ym jevem nejen v rozlehl´ ych p´ıseˇcn´ ych oblastech, ale napˇr´ıklad i na pláˇz´ıch. Jejich v´ yˇska se pohybuje v ˇrádu cm a rychlost jejich vzniku nebo kompletn´ı zmˇeny jejich vzoru se pohybuje v ˇrádech minut aˇz des´ıtek minut. D˚ uvodem jejich vzniku je jakákoliv byt’ i nepatrná nerovnost povrchu. Protoˇze zrnka vykonávaj´ıc´ı saltation dopadaj´ı na povrch pod témˇeˇr stejn´ ym pomˇernˇe mal´ ym u ´hlem ˇcin´ıc´ım pr˚ umˇernˇe 10◦ , tak tato nerovnost zabraˇ nuje dopadu zrnek typu saltation do m´ıst za pˇrekáˇzkou. Na obrázku 2.1 je tato oblast mezi A a B. Sn´ıˇzenou koncentrac´ı dopadaj´ıc´ıch zrnek do této oblasti je zde pak utlumen i pˇresun p´ısku. Naproti tomu do oblasti mezi body B a C uˇz zrnka dopadaj´ı a smˇerem od B do C zde docház´ı pˇresunu materiálu. T´ım se prohlubeˇ n zvˇetˇsuje a vzniká prvn´ı vlnka. V oblasti za bodem C, ve které je t´ım, ˇze nen´ı naklonˇena, intenzita dopad˚ u trochu niˇzˇs´ı, vzniká dalˇs´ı nerovnost a vˇse se opakuje.

ˇ Obrázek 2.1: Sipky vyznaˇcuj´ı dopadaj´ıc´ı zrnka. Oblast mezi A a B je odst´ınˇena Se vzr˚ ustaj´ıc´ım vˇetrem vzr˚ ustá vzdálenost mezi jednotliv´ ym vlnkami, ´ ernˇe této vzdálenosti pak protoˇze u ´hel dopadu zrnek saltation klesá. Umˇ vzr˚ ustá v´ yˇska vlnek. Tento proces zvyˇsován´ı je vˇsak omezen, pˇri urˇcité rychlosti vˇetru se zaˇcnou pohybovat i tˇeˇzká zrnka a vypln´ı mezery a nerovnosti formuj´ıc´ı wind-ripples.

2.3.2

Ukl´ ad´ an´ı p´ısku ve velk´ em mˇ eˇ r´ıtku aneb duny

Pˇri odpov´ıdaj´ıc´ıch vˇetrn´ ych podm´ınkách a dostateˇcném pohybu a pˇresouván´ı materiálu se mohou ukládán´ım p´ısku zaˇc´ıt formovat mnohem vˇetˇs´ı objekty neˇz wind-ripples. 5

Hlavn´ım jevem tvoˇr´ıc´ım duny je uˇz zmiˇ novan´ y efekt saltation drag. V´ıtr pravidelnˇe vanouc´ı p´ıseˇcnou krajinou je postupnˇe zpomalen nar˚ ustaj´ıc´ı koncentrac´ı zrnek ve vzduchu a na urˇcitém m´ıstˇe docház´ı k ukládán´ı materiálu a vzniká zárodek budouc´ı duny. 2.2a,b. Tento zárodek nar˚ ustá a pˇridává se dalˇs´ı jev, kter´ ym je zrychlován´ı vˇetru vanouc´ıho terénem vzh˚ uru. V´ıtr je zpomalován jevem saltation drag, protoˇze ale vane vzh˚ uru po dunˇe, jeho rychlost tolik neklesá a nab´ırá stále v´ıce zrnek p´ısku. Teprve po pˇrekonán´ı vrcholku v´ıtr zˇretelnˇe zpomaluje a na závˇetrné stranˇe docház´ı k ukládán´ı 2.2c. Duna dále nar˚ ustá, pˇriˇcemˇz po dosaˇzen´ı urˇcité v´ yˇsky pˇrestává v´ıtr kop´ırovat závˇetrnou stranu a vane pˇres vrcholek duny paralelnˇe s povrchem. T´ım vzniká dalˇs´ı jev sand trap. Témˇeˇr vˇsechna zrnka p´ısku hnaná vˇetrem smˇerem k vrcholku jsou po jeho pˇrekonán´ı zachycena na závˇetrné stranˇe 2.2d. Sklon závˇetrné strany se zvˇetˇsuje a po pˇrekroˇcen´ı klidového u ´hlu 3 doch´ az´ı k sesypán´ı ˇcásti p´ısku po závˇetrné stranˇe avalanching. Sklon z´ avˇetrné strany se t´ım zmenˇs´ı, ale jelikoˇz neustále docház´ı k zachycován´ı nov´ ych a nov´ ych zrnek, sklon postupem ˇcasu opˇet nar˚ ustá. Opakován´ı tohoto kolobˇehu sesypávaj´ıc´ıho se p´ısku a opˇetovného zvyˇsován´ı sklonu závˇetrné strany zp˚ usobuje pomal´ y pˇresun duny ve smˇeru vˇetru.

Obrázek 2.2: Vznik duny, sd je m´ısto nejvyˇsˇs´ı intenzity ukládán´ı. Délka ˇsipky ukazuje rychlost vˇetru. (a,b) vznikaj´ıc´ı zárodek duny. (c) v´ıtr vanouc´ı vzh˚ uru nab´ırá dalˇs´ı zrnka. (d) sand trap. 3

Pro such´ y p´ısek pˇribliˇznˇe 33◦ .

6

2.4

Typy dun

Pˇres velkou r˚ uznorodost tvar˚ u dun se naˇsli spoleˇcné rysy jejich tvar˚ u v r˚ uzn´ ych p´ıseˇcn´ ych oblastech. Základn´ı rozdˇelen´ı dun vycház´ı z orientace jejich hˇrbetu v˚ uˇci hlavn´ımu smˇeru pˇresunu p´ısku. Toto rozdˇelen´ı dává tyto typy dun transverse dunes, linear dunes a star dunes. Hlavn´ı smˇer pˇresunu p´ısku a hˇrbet transverse dune jsou na sebe kolmé, se hˇrbetem linear dune jsou paraleln´ı a v pˇr´ıpadˇe star dune se p´ısek pohybuje ke stˇredu duny. V tˇechto kategori´ıch pak nastává dalˇs´ı dˇelen´ı. • Transverse dunes – Dome dune Osamocená duna bez v´ yraznˇeji vytvoˇrené návˇetrné a závˇetrné strany. Obr. 2.3a. – Barchan dune Duna se srpkovit´ ym p˚ udorysem, konce srpku jsou orientovány po smˇeru vˇetru. Tento typ dun cestuje po vˇetru aniˇz by v´ yraznˇeji mˇenil sv˚ uj tvar. Obr. 2.3b. – Transverse dune Jedná se o p´ıseˇcn´ y hˇreben kolm´ y na smˇer vˇetru a cestuj´ıc´ı po smˇeru vˇetru. Obr. 2.3c. – Reversing dunes Podobná pˇredchoz´ımu typu, vzniká v oblastech kde se smˇer vˇetru mˇen´ı o 180◦ . Obr. 2.3d. • Linear dunes – Seif dune Sinusového tvaru s ostr´ ym hˇrbetem. ˇ asteˇcnˇe porostlá vegetac´ı, vˇetˇs´ıch rozmˇer˚ – Sand ridge C´ u neˇz pˇredchoz´ı typ. • Star dunes – Star dune Jehlanovit´ y nebo kopulovit´ y tvar s vyb´ıhaj´ıc´ımi rameny. Obr. 2.3e. – Network dune V oblastech kde se pˇrevládaj´ıc´ı v´ıtr pravidelnˇe mˇen´ı pr˚ ubˇehem ˇcasu. Jedná se o soubory Transverse dunes, které se navzájem pˇrekr´ yvaj´ı. Obr. 2.3f.

2.5

Prostˇ red´ı umoˇ zn ˇ uj´ıc´ı vznik uveden´ ych typ˚ u dun

V ˇcistˇe p´ıseˇcn´ ych oblastech, bez v´ yskytu vegetace a pˇrekáˇzek, je hlavn´ım ˇcinitelem udávaj´ıc´ım typ dun zde panuj´ıc´ı vˇetrn´ y reˇzim. Podle zmˇen vˇetru bˇehem roku jej lze rozdˇelit na unimodal, bimodal a complex. V prvn´ım pˇr´ıpadˇe vane v´ıtr po cel´ y rok z jednoho smˇeru s mal´ ymi odchylkami. V druhém pˇr´ıpadˇe se stˇr´ıdaj´ı dva sezónn´ı vˇetry s odliˇsn´ ym smˇerem. Complex reˇzim znamená, ˇze v´ıtr bˇehem roku vane z v´ıce neˇz dvou smˇer˚ u nebo 7

vane takov´ ym zp˚ usobem, ˇze se smˇer vˇetru nedá jednoznaˇcnˇe urˇcit. Dalˇs´ım faktorem ovlivˇ nuj´ıc´ım tvorbu dun v dané oblasti je mnoˇzstv´ı p´ısku, které se na tvorbˇe dun pod´ıl´ı. Na obrázku 2.4 je zobrazen diagram ukazuj´ıc´ı typy dun v závislosti na vˇetrném reˇzimu a dostupném mnoˇzstv´ı p´ısku.

2.6

C´ıle t´ eto diplomov´ e pr´ ace

Simulovatelné jevy jsou tedy tvorba wind-ripples a simulace vzniku a v´ yvoje dun. Tato diplomová práce se soustˇredila na téma dun. D˚ uvodem tohoto rozhodnut´ı bylo, ˇze zat´ımco na téma wind-ripples uˇz byly publikovány na internetu volnˇe dostupné práce v oboru poˇc´ıtaˇcová grafika, tématem visu-

Obrázek 2.3: Typy dun. Pˇrevzato z [2]

8

Obrázek 2.4: Typy dun v závislosti na vˇetrném reˇzimu a dostupnosti p´ısku v dané oblasti. Pˇrevzato z [2]

alizace vzniku a v´ yvoje dun pomoc´ı vztah˚ u popsan´ ych v této kapitole se zˇrejmˇe jeˇstˇe nikdo nezab´ yval. I samotn´ ym autor˚ um jiˇz hotov´ ych prac´ı ˇslo pˇredevˇs´ım o zkoumán´ı vlastnost´ı jimi navrˇzen´ ych model˚ u a ne o visualizaci. Dalˇs´ım d˚ uvodem této volby je, ˇze téma dun je ˇsirˇs´ı neˇz téma wind-ripples, coˇz by mˇelo vyplynout z informac´ı uveden´ ych v této kapitole.

9

Kapitola 3

Popis metod pouˇ zit´ ych v prac´ıch na podobn´ e t´ ema V této kapitole jsou popsány základn´ı principy a metody pouˇz´ıvané pro simulaci v´ yvoje p´ıseˇcn´ ych oblast´ı, jak v malém tak velkém mˇeˇr´ıtku, a jsou zde zároveˇ n s t´ımto popisem uvedeny práce, které danou metodu pouˇz´ıvaj´ı.

3.1

Simulace p´ıseˇ cn´ ych oblast´ı

At’ se jedná o simulaci vzniku a v´ yvoje dun nebo o simulaci wind ripples, lze u vˇetˇsiny prac´ı naj´ıt spoleˇcné rysy. Jsou to jednak datová struktura, kterou je dvou popˇr´ıpadˇe jednorozmˇerná mˇr´ıˇzka, a pak také základn´ı simulaˇcn´ı schéma uvedené v tabulce 3.1.

3.2

Simulace wind-ripples pomoc´ı bump-mapping

Tento postup byl pouˇzit ve velmi ˇcasto citované práci [3], která se soustˇred´ı pˇredevˇs´ım na visualizace jevu. Jsou pouˇzity dvˇe dvourozmˇerné mˇr´ıˇzky, jedna reprezentuje samotn´ y pouˇstn´ı terén, kter´ y bude zobrazen a druhá je pomocná a pouˇz´ıvá se pro generován´ı vlnek a následné generován´ı bumb-map textury. Hodnoty pomocné mˇr´ıˇzky jsou na zaˇcátku simulace inicializovány n´ ahodn´ ymi ˇc´ısly. Poté prob´ıhá simulace. Jej´ım prvn´ım krokem je generován´ı vlnek na mˇr´ıˇzce, které prob´ıhá shodnˇe s tabulkou 3.1. Po v´ ybˇeru erodované buˇ nky je vyjádˇrena velikost pˇresunu jako L = L0 + bh(x, y) ~ L0 v´ıtr fouká vˇzdy v kladném smˇeru osy x, proto staˇc´ı poˇc´ıtat s velikost´ı L. je kontroln´ı parametr odpov´ıdaj´ıc´ı s´ıle vˇetru, b je konstanta. Po pˇresunut´ı urˇcitého mnoˇzstv´ı materiálu, reprezentované sn´ıˇzen´ım hodnoty erodované buˇ nky a zv´ yˇsen´ım hodnoty c´ılové buˇ nky, je pro obˇe buˇ nky a jejich nejbliˇzˇs´ı 10

1. Nastav poˇcáteˇcn´ı hodnoty bunˇek mˇr´ıˇzky. 2. V mˇr´ıˇzce urˇci buˇ nku s ze které bude odebráno mnoˇzstv´ı p´ısku q. 3. Podle v´ yˇsky a popˇr´ıpadˇe polohy s a aktuáln´ıho stavu systému vypoˇcti hodnotu q. Odeber materiál, tedy h0 (s) = h(s) − q. 4. Zkontroluj stabilitu s a bl´ızkého okol´ı a proved’ pˇr´ıpadné opravné kroky. ~ 5. Vypoˇcti vektor pˇresunu L. ~ a proved’ uloˇzen´ı, tedy h0 (d) = h(d) + q. 6. Urˇci m´ısto uloˇzen´ı d = s + L 7. Zkontroluj stabilitu d a bl´ızkého okol´ı a proved’ pˇr´ıpadné opravné kroky. 8. Uprav stavové promˇenné podle nové situace a pokraˇcuj bodem 2. Tabulka 3.1: Základn´ı schéma pr˚ ubˇehu simulac´ı jak wind-ripples tak vzniku a v´ yvoje dun. Body 4 a 7 jsou vˇetˇsinou pouˇz´ıvány ke kontrole pˇrekroˇcen´ı klidového u ´hlu svahu a odpov´ıdaj´ıc´ım pˇresun˚ um materiálu. okol´ı aplikována difusn´ı funkce. Tato funkce pˇredstavuje sesypáván´ı materiálu vlivem gravitace. Cyklus eroze ukládan´ı prob´ıhá aˇz do zformován´ı vlnek na pomocné mˇr´ıˇzce a poté nastoup´ı druh´ y krok algoritmu. Pro kaˇzdou buˇ nku pomocné mˇr´ıˇzky je urˇcen jej´ı normálov´ y vektor. Normálové vektory jsou pak pouˇzity pro generován´ı bump-mapping textur, které jsou kombinovány s texturou p´ıseˇcného povrchu. Tato kombinace textur je pak nanáˇsena na v´ ysledn´ y povrch reprezentovan´ y hlavn´ı mˇr´ıˇzkou a tak je efektu wind-ripples doc´ıleno aniˇz by se zv´ yˇsil poˇcet polygon˚ u hlavn´ıho modelu.

3.3

Simulace wind-ripples jejich pˇ r´ım´ ym zobrazen´ım

Pˇr´ıkladem práce vyuˇz´ıvaj´ıc´ı tento postup je [5]. I tato se chová podle schématu tabulky 3.1 a pouˇz´ıvá dvourozmˇernou mˇr´ıˇzku. Autoˇri definuj´ı chován´ı navrˇzeného modelu pomoc´ı dvou jev˚ u. Prvn´ım z nich je saltation a odpov´ıdá v tabulce 3.1 bod˚ um 2,3 a 5,6 a druh´ y jev je creep odpov´ıdaj´ıc´ı bod˚ um 4 a 7. Zde pozor, autoˇri jev creep popisuj´ı tak, ˇze neodpov´ıdá popisu v podkapitole 2.2, n´ ybrˇz se jedná o sesypáván´ı materiálu. Po zvolen´ı buˇ nky s ve které probˇehne eroze, je vypoˇc´ıtán vektor pˇresunu t´ımto vzorcem. Lx = (l0x + wx h(s))(1 − tanh ∂h(s) ∂x ) ∂h(s) Ly = (l0y + wy h(s))(1 − tanh ∂y ) 11

A mnoˇzstv´ı pˇreneseného materiálu je urˇceno takto. q = q0 (1 + tanh(∇h(s))) Operátory gradient a parciáln´ı derivace slouˇz´ı k vyjádˇren´ı nejvˇetˇs´ıho rozd´ılu v´ yˇsek v mˇr´ıˇzce mezi buˇ nkou s a nˇekterou z bunˇek sousedn´ıch. Oba tyto operátory zaruˇcuj´ı, ˇze se chován´ı modelu pˇrizp˚ usobuje hodnotám aktuáln´ı buˇ nky s a jej´ımu nejbliˇzˇs´ımu okol´ı. Vektor w ~ reprezentuje v´ıtr, vektor l~0 je uˇzivatelem definovan´ y pr˚ umˇern´ y “skok”, parametr q0 urˇcuje pr˚ umˇerné pˇrenesené mnoˇzstv´ı p´ısku. Vˇsechny tyto hodnoty se pod´ılej´ı na charakteru vytvoˇren´ ych wind-ripples. Po kaˇzdém odebrán´ı nebo uloˇzen´ı materiálu se pro buˇ nky s a d a buˇ nky v jejich okol´ı urˇcuje váˇzen´ y pr˚ umˇer v´ yˇsek a tyto hodnoty jsou pak zpˇetnˇe dosazeny. T´ım se realizuje proces autory naz´ yvan´ y creep. V této pr´ aci je také uvedena metoda pro simulaci pˇrekáˇzky, která nepodléhá vlivu vˇetru. Tak vzniká jev, pˇri kterém se na návˇetrné stranˇe pˇred pˇrekáˇzkou pomalu hromad´ı p´ısek a naopak za pˇrekáˇzkou, v jej´ım vˇetrném st´ınu, vzniká m´ırná prohloubenina. Velmi struˇcn´ y popis této metody je takov´ yto. Po kaˇzdém urˇcen´ı c´ılové buˇ nky d se provád´ı kontrola, zda se tato buˇ nka nenacház´ı uvnitˇr pˇrekáˇzky. Pokud je tomu tak, m´ısto uloˇzen´ı d je posunuto pˇred pˇrekáˇzku smˇerem proti vˇetru. Poté probˇehne test, zda sklon naakumulovaného p´ısku pˇred pˇrekáˇzkou nepˇrekraˇcuje klidov´ y u ´hel a probˇehne pˇr´ıpadné sesypán´ı. Pro simulaci vˇetrného st´ınu se podle ˇs´ıˇrky pˇrekáˇzky vypoˇcte oblast parabolického tvaru. V této oblasti je intenzita vˇetru sn´ıˇzena, nejmenˇs´ı hodnoty nab´ yvá ihned u pˇrekáˇzky a smˇerem ke kraji oblasti intenzita vˇetru lineárnˇe nar˚ ustá. Smˇer vˇetru v závˇetˇr´ı je nezmˇenˇen, mˇen´ı se pouze intenzita.

3.4

Integrodiferenci´ aln´ı model wind-ripples

Práce [6] nepouˇz´ıvá schéma tabulky 3.1 a m´ısto dvourozmˇerné mˇr´ıˇzky je pouˇzita jednorozmˇerná. Práce vycház´ı z fyzikáln´ıho popisu obou proces˚ u viz. 2.2, kteˇr´ı se pod´ılej´ı na tvorbˇe wind-ripples. Základn´ı rovnic´ı, ze které je cel´ y model odvozen, je (1 − λp )ρp

∂ζ(x, t) ∂Q(x, t) =− ∂t ∂x

(3.1)

kde ζ(x, t) je v´ yˇska terénu na pozici x v ˇcase t, ρp je hustota p´ısku, λp reprezentuje poréznost povrchu (hodnota této veliˇciny je obyˇcejnˇe volena 0.35). Q(x, t) je mnoˇzstv´ı materiálu, které se pˇresouvá pozic´ı x v ˇcase t a je souˇctem mnoˇzstv´ı materiálu pˇreneseného procesem saltation a procesem creep Q(x, t) = Qs (x, t) + Qc (x, t). Vzorec tedy vyjadˇruje, ˇze zmˇena v´ yˇsky terénu je u ´mˇerná zmˇenˇe mnoˇzstv´ı pohybuj´ıc´ıho se materiálu. Pokud tedy ∂ζ(x, t)/∂t < 0 coˇz vyjadˇruje, ˇze na daném m´ıstˇe prob´ıhá eroze pak v 12

tomto m´ıstˇe mus´ı nar˚ ustat objem pˇrenáˇseného materiálu ∂Q(x, t)/∂x > 0. V opaˇcném pˇr´ıpadˇe, kdyˇz na daném m´ıstˇe nastává ukládán´ı, vyjádˇrené ∂ζ(x, t)/∂t > 0 mus´ı objem pˇrenáˇseného materiálu klesat ∂Q(x, t)/∂x < 0. Pokud nenastává ˇzádná zmˇena v´ yˇsky daného m´ısta, pak objem pˇrenáˇseného materiálu z˚ ustává konstantn´ı ∂Q(x, t)/∂x = 0. Pˇredpokladem, ˇze proud zrnek pˇresouvaj´ıc´ı se procesem saltation je v tak malé oblasti jakou se model zab´ yvá konstatn´ı dostáváme ∂Qs (x, t)/∂x = 0 a tento proces uˇz tedy nen´ı tˇreba v rovnici 3.1 vyjadˇrovat. Je ale tˇreba m´ıt na pamˇeti, ˇze toto zjednoduˇsen´ı je moˇzné jen pˇri studiu mal´ ych oblast´ı, pokud zkoumaná oblast pokr´ yvá celou dunu pak je t´ımto zjednoduˇsen´ım model jednoznaˇcnˇe znehodnocen. Nyn´ı je nutné vyjádˇrit vztah pro mnoˇzstv´ı zrnek pohybuj´ıc´ıch se jevem creep. Pokud pr˚ umˇerná délka pohybu tˇechto zrnek bˇehem jednoho vymrˇstˇen´ı bude oznaˇcena a ¯, pak veˇsker´ y pˇresun materiálu m´ıstem x je souˇcet zrnek, které byly vymrˇstˇeny z povrchu v oblasti urˇcené x − a ¯ a x. Je tˇreba také zapoˇc´ıtat rozdˇelen´ı délky kutálen´ı jednoho zrnka do v´ ysledného vzorce. Z ∞ Z x Q0r (x) = mp np dαp(α) Nim (x0 )dx0 (3.2) −∞

x−a

Kde mp je hmota jednotlivého zrnka, np je pr˚ umˇern´ y poˇcet zrnek typu creep vyraˇzen´ ych dopadem jednoho zrnka typu saltation, tato hodnota je brána jako konstantn´ı, Nim (x0 ) je poˇcet zrnek dopadaj´ıc´ıch na m´ısto x0 a p(α) je pravdˇepodobnostn´ı rozdˇelen´ı délky kutálen´ı jednoho zrnka typu creep. Protoˇze bylo zavedeno zjednoduˇsen´ı, ˇze mnoˇzstv´ı zrnek v procesu saltation je bˇehem simulace konstantn´ı a ˇze dopadaj´ı na povrch pod témˇeˇr stejn´ ym u ´hlem φ, pak jediná vˇec, která ovlivˇ nuje koncentraci jejich dopadu ´ na terén, je zmˇena sklonu povrchu. Uhel sklonu povrchu je oznaˇcen θ. T´ım dostáváme vzorec pro koncentraci dopad˚ u 1 + ζx cot φ tan θ 0 0 Nim (x) = Nim (x) 1 + cos θ = Nim (x) p (3.3) tan φ 1 + ζx2 0 (x) je koncentrace dopadu zrnek na rovn´ kde Nim em povrchu. Pozorován´ım a experimenty bylo zjiˇstˇeno, ˇze na návˇetrné stranˇe je poˇcet zrnek procesu creep sn´ıˇzen a naopak na závˇetrné stranˇe zv´ yˇsen. Z toho vypl´ yvá koneˇcn´ y vztah pro mnoˇzstv´ı materiálu pˇrenesené procesem creep

Qc (x) = (1 − µζx )Q0c (x)

(3.4)

kde parametr µ zahrnuje tento experimenty zjiˇstˇen´ y jev. Hodnotu µ je tˇreba urˇcit empiricky. Dosazen´ım hodnoty 3.4 do 3.1 dostáváme rovnici Z ∞ Z x Z ∞ n o 0 0 ζt = Q0 µζxx dαp(α) F (x )dx +(1−µζx ) dαp(α)[F (x−a)−F (x)] −∞

−∞

x−a

(3.5) 13

p 0 cot φ/(ρ (1 − λ )) a F (x) = (tan φ + ζ )/ 1 + ζ 2 . Je kde Q0 = mp np Nim p p x x nutné zd˚ uraznit, ˇze rovnice 3.5 naprosto selˇze pokud závˇetrná strana vlnek pˇrekroˇc´ı u ´hel φ, pod kter´ ym dopadaj´ı zrnka procesu saltation. V takovém 0 z´ pˇr´ıpadˇe nab´ yvá pomˇer Nim /Nim aporné hodnoty. Proto je tˇreba pˇridat podm´ınku, ˇze F (x) = 0 pokud sklon závˇetrné strany vlnek pˇresáhne u ´hel φ. Tato práce se zab´ yvá pouze vlastnostmi navrˇzeného modelu a v´ ysledky z´ıskává numerick´ ym ˇreˇsen´ım rovnice 3.5.

3.5

Simulace vzniku a v´ yvoje dun bunˇ eˇ cn´ ym automatem

V práci [7], která se zab´ yv´ a vyuˇzit´ım bunˇeˇcn´ ych automat˚ u (cellular automata) pro u ´ˇcely simulace r˚ uzn´ ych typ˚ u eroz´ı prob´ıhaj´ıc´ıch v krajinˇe, je navrˇzen také postup, jak t´ımto automatem simulovat vznik a v´ yvoj dun. Protoˇze se jedná o bunˇeˇcn´ y automat, tedy o dvourozmˇernou mˇr´ıˇzku, kde spolu mohou komunikovat pouze nejbliˇzˇs´ı sousedn´ı buˇ nky, tak tato práce také ˇcásteˇcnˇe vyboˇcuje ze schématu popsaného tabulkou 3.1, protoˇze délka pˇrenosu je zde vˇzdy maximálnˇe 1. Ve dvourozmˇerné mˇr´ıˇzce, která je základem algoritmu, vane v´ıtr pouze jedn´ım smˇerem a to paralelnˇe s osou y. V´ıtr m˚ uˇze nab´ yvat hodnot v intervalu h0, 1i. V´ yvoj proudˇen´ı vˇetru pak ve struˇcnosti pracuje takto. 1. V prvn´ı ˇradˇe bunˇek mˇr´ıˇzky s indexy (0, 0) aˇz (xs , 0) je v´ıtr nastaven na hodnotu 1.0. 2. Pro kaˇzdou buˇ nku v následuj´ıc´ı ˇradˇe je hodnota vˇetru vypoˇc´ıtána jako pr˚ umˇer hodnot tˇrech bunˇek v pˇredchoz´ı ˇradˇe. 3. Hodnota vˇetru je pak d´ ale sn´ıˇzena u ´mˇernˇe rozd´ılu v´ yˇsek mezi aktuáln´ı buˇ nkou a sousedn´ı buˇ nkou po smˇeru vˇetru. Takto generované hodnoty vˇetru pak slouˇz´ı pro porovnáván´ı s urˇcitou prahovou hodnotou definovanou pro kaˇzdou buˇ nku. Pokud je prahová hodnota dosaˇzena, pak je ˇcást materi´ alu pˇrenesena do jedné z nejbliˇzˇs´ıch sousedn´ıch tˇr´ı bunˇek v následuj´ıc´ı ˇradˇe a to vˇzdy do té, buˇ nky která má nejniˇzˇs´ı v´ yˇsku.

3.6

Simulace vzniku a v´ yvoje dun na diskr´ etn´ı mˇ r´ıˇ zce

Tento pˇr´ıstup je pouˇzit u dvou prac´ı od toho samého kolektivu autor˚ u [1] a [2]. Informace v nich obsaˇzené jsou základem této diplomové práce, proto se jejich podrobnˇejˇs´ı vysvˇetlen´ı nalézá v následuj´ıc´ı kapitole. Základem je dvourozmˇerná pˇr´ıpadnˇe jednorozmˇerná mˇr´ıˇzka a simulaˇcn´ı schéma, které je aˇz na jednu v´ yjimku totoˇzné s 3.1. V´ yjimkou je, ˇze se 14

neurˇcuje mnoˇzstv´ı pˇrenáˇseného p´ısku, protoˇze to je vˇzdycky konstantn´ı. T´ım se dá znatelnˇe urychlit v´ ypoˇcet napˇr´ıklad test˚ u zda sklon povrchu nepˇresahuje klidov´ yu ´hel. Erodovaná buˇ nka se vyb´ırá náhodnˇe. Pˇresouvan´ y materiál nemus´ı b´ yt vˇzdy uloˇzen hned do prvn´ı c´ılové buˇ nky, záleˇz´ı na v´ ysledku testu pravdˇepodobnosti, ale c´ılové buˇ nky se mohou za sebou ˇretˇezit. T´ım se simuluje skákán´ı p´ıseˇcn´ ych zrnek po povrchu. V modelu je zaveden vˇetrn´ y st´ın postupnˇe se rozˇsiˇruj´ıc´ı za dunou, t´ım jak tato roste. D´ıky nˇemu je moˇzné efektivnˇe simulovat jev p´ıseˇcné pasti, ve které je vˇetˇsina pˇresouvan´ ych mnoˇzstv´ı p´ısku zachycena. V prac´ıch je popsáno, jak se vyv´ıjel pˇr´ıstup autor˚ u k v´ ypoˇctu velikosti pˇresunu L aˇz do nynˇejˇs´ı podoby. Nyn´ı jeho velikost závis´ı jak na v´ yˇsce m´ısta odkud je materiál pˇresouván tak na aktuáln´ım tvaru terénu. V modelu je pouˇzit v´ıtr, kter´ y vˇzdy vane ve smˇeru kladné osy x, proto je také navrˇzena rotace mˇr´ıˇzky. Tato umoˇzn ˇuje simulaci vˇetru vanouc´ıho v´ıce smˇery. Práce [4] vycház´ı ze stejn´ ych pˇredpoklad˚ u, tedy vˇetrn´ y st´ın za dunou, konstantn´ı mnoˇzstv´ı pˇresouvaného p´ısku a test pravdˇepobnosti pˇred samotn´ ym ukládán´ım materiálu. Hlavn´ı rozd´ıl oproti [1] a [2] je dán t´ım, ˇze velikost a ~ je zadána pˇredem a je tedy bˇehem jedné simulace smˇer vektoru pˇresunu L konstantn´ı, s v´ yjimkou zp˚ usobenou t´ım, ˇze jedna sloˇzka vektoru m˚ uˇze mˇenit ~ = (1, 3) pak dalˇs´ı moˇzná hodnota tohoto vektoru znaménko. Napˇr. pokud L ~ = (−1, 3). Tak se dociluje vˇetru dvou smˇer˚ je L u. C´ılem vˇsech tˇrech prac´ı nen´ı visualizace ale studium vlastnost´ı modelu.

15

Kapitola 4

Teoretick´ y rozbor modelu Dále popsan´ y simulaˇcn´ı model vycház´ı z prac´ı [1] a [2]. V tˇechto prac´ıch odvozené rovnice a pouˇzité vztahy vycházej´ı ze skuteˇcn´ ych pozorován´ı v pouˇstn´ıch oblastech, z experiment˚ u ve vˇetrném tunelu a ze studia p´ıseˇcn´ ych zrnek na mikroskopické u ´rovni. Proto autory navrˇzená metoda obsahuje základn´ı skuteˇcnosti jako je vˇetrn´ y st´ın, kter´ y v závˇetrné stranˇe za dunou tvoˇr´ı past na vˇetrem hnaná p´ıseˇcná zrnka, velmi jednoduchou ale u ´ˇcinnou kontrolu sklonu svahu, ale i zrychlován´ı vˇetru smˇerem po dunˇe vzh˚ uru a urˇcen´ı aktuáln´ıho stavu terénu pomoc´ı odchylek od pr˚ umˇerné hodnoty. Podle dostupn´ ych publikac´ı nebyly metody uvedené v tˇechto prac´ıch nikdy pouˇzity pro visualizaci v oboru poˇc´ıtaˇcové grafiky, i z tohoto d˚ uvodu je snaha o visualizaci tohoto modelu lákavá.

4.1

Z´ akladn´ı vlastnosti modelu

Základn´ı schéma pouˇzitého modelu také vycház´ı z tabulky 3.1. Základn´ı strukturou je dvourozmˇerná mˇr´ıˇzka cel´ ych ˇc´ısel vˇetˇs´ıch nebo rovn´ ych nule. Jednotlivé buˇ nky mˇr´ıˇzky jsou indexovány (x, y). Pˇri geometrické reprezentaci je vzdálenost dvou nejbliˇzˇs´ıch bunˇek a. Hodnota buˇ nky na pozici (x, y) bude znaˇcena h(x, y) a reprezentuje poˇcet sand slabs na daném m´ıstˇe. Sand slab je v rámci modelu nejmenˇs´ı, dále nedˇelitelné mnoˇzstv´ı p´ısku, se kter´ ym model pracuje. V´ yˇska sand slab je rovna a/3. Z toho plyne, ˇze skuteˇcnou v´ yˇsku η buˇ nky (x, y) urˇc´ıme η(x, y) = h(x, y)(a/3). Pokud h(x, y) = 0 pak je buˇ nka na této pozici oznaˇcena jako skalnaté podloˇz´ı, coˇz je m´ısto kde nen´ı moˇzná dalˇs´ı eroze. V modelu je také simulován wind shadow (vˇetrn´ y st´ın), coˇz je oblast leˇz´ıc´ı po smˇeru vˇetru za dunou, která je pˇred vˇetrem chránˇena tˇelem duny. Je urˇcena jako plocha zabraná z duny pod u ´hlem 15◦ smˇerem dol˚ u a prob´ıhá zde pouze gravitaˇcn´ı eroze.

16

4.2

Inicializace

Jak bylo uvedeno v podkapitole 2.3.2, duny maj´ı schopnost vzniknout z p˚ uvodnˇe u ´plnˇe rovného p´ıseˇcného povrchu. Z tohoto d˚ uvodu jsou hodnoty vˇsech bunˇek mˇr´ıˇzky nastaveny na stejnou hodnotu. T´ım je také umoˇznˇena regulace celkového mnoˇzstv´ı p´ısku v modelu.

4.3

Vˇ etrn´ a eroze

Vˇetrná eroze nem˚ uˇze probˇehnout na pozici, kde h(x, y) = 0 (skalnaté podloˇz´ı) a na pozici, která je ve vˇetrném st´ınu. Na náhodnˇe zvolené pozici x, y je tedy proveden test, zda se pozice nenacház´ı ve vˇetrném st´ınu a zda se nejedná o kamenné podloˇz´ı. Pokud ani jedna z tˇechto podm´ınek nen´ı splnˇena, provedeme erozi, ta je provedena odebrán´ım jednoho sand slab z vybrané buˇ nky, tedy h0 (x, y) = h(x, y) − 1. V opaˇcném pˇr´ıpadˇe je mˇr´ıˇzka ponechána beze zmˇen a probˇehne nová náhodná volba pozice.

4.4

Uloˇ zen´ı

Berme nyn´ı v u ´vahu pouze v´ıtr vanouc´ı v kladném smˇeru osy x, d´ıky tomu si ~ pouze jeho velikost´ı L. Pokud m˚ uˇzeme dovolit oznaˇcovat vektor pˇresunu L doˇslo k erozi v buˇ nce na pozici (x, y) pak na pozici (x + L(x, y), y) bude sand slab s pravdˇepodobnost´ı P uloˇzen. Pokud uloˇzen´ı nenastalo, pokus´ıme se o uloˇzen´ı na pozici (x + L(x, y) + L(x + L(x, y), y), y) atd. Tento postup vycház´ı z pozorován´ı, ˇze bˇehem procesu saltation zrnka p´ısku po povrchu “skáˇc´ı” (bouncing) a bˇehem dopadu mezi skoky mohou b´ yt s pravdˇepodobnost´ı P zachycena povrchem. Bylo také zjiˇstˇeno, ˇze pravdˇepodobnost zachycen´ı zrnka na skalnatém povrchem je menˇs´ı. Z toho vycház´ı toto nastaven´ı pravdˇepodobnost´ı zachycen´ı na Ps = 0.6 na p´ıseˇcném povrchu, Pns = 0.4 na skalnatém podloˇz´ı a Pns = Ps = 1.0 pro oblasti ve vˇetrném st´ınu. Vzdálenost pˇrenosu z dané pozice L(x, y) je urˇcena rovnic´ı 4.4. K vysvˇetlen´ı této rovnice se docela dobˇre hod´ı popis historie jej´ıho v´ yvoje. Model, kter´ y vyuˇz´ıvá jej´ı prvn´ı verze L(x, y) = L0 (4.1) produkuje duny se symetrick´ ym profilem, jejich závˇetrné i návˇetrné strany maj´ı sklon odpov´ıdaj´ıc´ı kritickému u ´hlu 33◦ . Pro vytváˇren´ı návˇetrn´ ych stran ◦ s typick´ ym sklonem okolo 10 nen´ı proto tato rovnice dostateˇcná. Následuj´ıc´ı verze rovnice vycház´ı z poznatku, ˇze rychlost vˇetru smˇerem vzh˚ uru po dunˇe lineárnˇe vzr˚ ustá, do rovnice 4.1 byl tedy pˇridán lineárn´ı ˇclen. L(x, y) = L0 + C1 (h(x, y) − havg ) (4.2) Konstanta C1 vˇetˇsinou pˇredstavuje hodnotu 0.4 a reprezentuje lineárn´ı nár˚ ust rychlosti vˇetru. Havg je pr˚ umˇern´ y poˇcet sand slab v jedné buˇ nce mˇr´ıˇzky. 17

Pouˇzit´ım této rovnice vznikaj´ı duny, které jsou niˇzˇs´ı, cestuj´ı rychleji a sklon jejich návˇetrné hrany se pohybuje okolo 10◦ . Zároveˇ n s touto rovnic´ı bylo zavedeno, aby v oblastech ve vˇetrném st´ınu neprob´ıhala eroze. Pokud simulace vybavená rovnic´ı 4.2 pobˇeˇz´ı dostateˇcnˇe dlouho, dosáhne se vyrovnaného stavu (equilibrium), pˇri kterém je na celé ploˇse jen jedna osamocená duna obklopená rovinou. D˚ uvodem toho je, ˇze objem p´ısku pˇricházej´ıc´ıho do oblasti pokryté dunou je vˇetˇs´ı neˇz odchoz´ıho a velikost tohoto rozd´ılu nar˚ ustá s velikost´ı duny. To je zp˚ usobeno oblast´ı ve vˇetrném st´ınu, která má pravdˇepodobnost zachycen´ı Ps = Pns = 1, jej´ı plocha jak se duna zvˇetˇsuje samozˇrejmˇe nar˚ ustá a rychlost, kterou sand slab potˇrebuje aby oblast pˇreletˇel, je vyˇsˇs´ı neˇz rychlost, kterou m˚ uˇze z´ıskat pomoc´ı rovnice 4.2. Proto je po urˇcité dobˇe simulace kaˇzd´ y sand slab zachycen za dunou. Lineárn´ı ˇclen rovnice 4.2 tedy pouze reguluje sklon návˇetrné strany, ale uˇz nen´ı schopen dostateˇcnˇe regulovat v´ yˇsku duny. Tato rovnice je tedy také nedostateˇcná. Z dalˇs´ıch praktick´ ych pozorován´ı vyplynulo, ˇze délka skoku zrnka bˇehem saltation nen´ı pˇr´ımo lineárnˇe u ´mˇerná smykové rychlosti vˇetru (u∗ ), obrázek 4.1. Proto byl do rovnice 4.2 pˇridán dalˇs´ı ˇclen reprezentuj´ıc´ı nelineárn´ı nár˚ ust

Obrázek 4.1: Závislost délky skoku zrnka na smykové rychlosti [1] smykové rychlosti. L0 + C1 (h(x, y) − havg ) + C2 (h(x, y) − havg )2 (h(x, y) ≥ havg ) L(x, y) = L0 + C1 (h(x, y) − havg ) (h(x, y) < havg ) (4.3) C2 je koeficient nelineárn´ıho nár˚ ustu smykové rychlosti a jeho hodnota se nastavuje na 0.002 Touto zmˇenou vznikaj´ı duny, které jsou niˇzˇs´ı, a celkov´ y poˇcet dun se zvˇetˇsil. Ani po dlouhé dobˇe simulace nevzniká jedna osamocená duna, nelineárn´ı ˇclen je tedy schopen dodat nˇekter´ ym sand slab dostateˇcnou rychlost k pˇrekonán´ı oblasti ve vˇetrném st´ınu za dunou. Posledn´ı u ´pravou je nahrazen´ı havg . Tuto zmˇenu zd˚ uvodn´ıme t´ım, ˇze havg dostateˇcnˇe nevypov´ıdá o aktuáln´ım stavu tvaru povrchu, protoˇze jeho hodnota z˚ ustává po celou dobu simulace konstantn´ı. Obrázek 4.2. V praxi se 18

toto nejv´ıce projevuje pˇri simulaci eroze povrchu, jehoˇz ˇcást byla na poˇcátku simulace umˇele vytvarována (napˇr. jehlan obklopen´ y rovinou). V takovém pˇr´ıpadˇe pouˇzit´ım rovnice 4.3 nevznikaj´ı duny ale jen terén pln´ y drobn´ ych vlnek.

Obrázek 4.2: Profil dvou mˇr´ıˇzek s vyobrazen´ ymi poˇcty sand slab, obˇe maj´ı stejnou hodnotu havg ale jejich tvar se v´ yraznˇe liˇs´ı.

Havg nahrad´ıme href , neboli referenˇcn´ım poˇctem sand slab a dostáváme v´ yslednou rovnici, která byla pouˇzita v této práci. L0 + C1 (h(x, y) − href ) + C2 (h(x, y) − href )2 (h(x, y) ≥ href ) L0 + C1 (h(x, y) − href ) (h(x, y) < href ) (4.4) Referenˇcn´ı poˇcet (href ) je dán rovnic´ı 4.5. Prav´ y ˇclen rovnice nám dává pr˚ umˇernou odchylku od hodnoty havg , o tuto hodnotou zmenˇsené, havg nám d´ avá v´ ysledn´ y referenˇcn´ı poˇcet sand slab. Parametry xm a ym udávaj´ı velikosti mˇr´ıˇzky.

L(x, y) =

href = havg −

1

xm −1,y Xm −1

2xm ym

x,y=0

|h(x, y) − havg |

(4.5)

V´ ysledná délka pˇrenosu L je zaveden´ım této zmˇeny ovlivnˇena takto, oznaˇcme si L0 (xc , yc ) resp. L00 (xc , yc ) v´ ysledky rovnice 4.3 resp. 4.4 pro stejnou mˇr´ıˇzku na té samé libovolnˇe zvolené pozici (xc , yc ). Pro naprostou rovinu nám rovnice 4.5 dává v´ ysledek href = havg . V ostatn´ıch pˇr´ıpadech je hodnota href < havg . Z toho plyne vztah L00 (xc , yc ) ≥ L0 (xc , yc ). V´ ysledn´ y model je nyn´ı schopen reagovat na zmˇeny tvaru povrchu. Protoˇze m´ırnˇe vzrostla velikost pˇresunu L, duny cestuj´ı rychleji a jsou menˇs´ı a vytvoˇren´ı oblasti dun z poˇcáteˇcn´ıho rovného povrchu je pomalejˇs´ı. Model je nyn´ı také schopen vˇernˇeji erodovat umˇele vytvarovanou ˇcást povrchu a na okoln´ı rovné ploˇse vznikaj´ı duny.

19

4.5

Pˇ resun p´ısku vlivem gravitace

Pro such´ y p´ısek se udává kritick´ yu ´hel svahu, pˇri kterém se zaˇcne materiál pˇresypávat jako 33◦ . Vzhledem k navrˇzen´ ym rozmˇer˚ um sand slab 1 , je tento u ´hel dosaˇzen, pokud je rozd´ıl dvou sousedn´ıch bunˇek mˇr´ıˇzky vˇetˇs´ı neˇz 2. Po vˇetrné erozi m˚ uˇze nastat situace, kdy právˇe erodovaná buˇ nka (x, y) m´ a hodnotu o 3 menˇs´ı neˇz nˇekteré ze sousedn´ıch bunˇek. V tom pˇr´ıpadˇe je jeden sand slab ze sousedn´ıch bunˇek pˇresunut do buˇ nky (x, y) a na buˇ nku z n´ıˇz byl sand slab odebrán je aplikován ten sam´ y proces. Teprve poté prob´ıhá uloˇzen´ı sand slab erodovaného vˇetrem. Buˇ nka na jej´ıˇz pozici probˇehlo uloˇzen´ı je testována, zda rozd´ıl jej´ı v´ yˇsky v˚ uˇc´ı v´ yˇsce okoln´ıch bunˇek nen´ı 3. V tom pˇr´ıpadˇe je jeden sand slab pˇresunut do náhodnˇe vybrané nejniˇzˇs´ı buˇ nky a na této buˇ nce pak prob´ıhá u ´plnˇe identick´ y test. Tento typ gravitaˇcn´ı eroze se uplatˇ nuje nejv´ıce v závˇetˇr´ı dun a oblastech ve vˇetrném st´ınu. Obrázek 4.3.

Obrázek 4.3: Kaskádovit´ y proces sesypán´ı (avalanche) vˇetrem pˇrineseného sand slab.

4.6

V´ıtr vanouc´ı libovoln´ ym smˇ erem

Protoˇze v´ıtr vanouc´ı pouze v kladném smˇeru osy x je nedostaˇcuj´ıc´ı pro u ´ˇcely simulace, je v práci [2] navrˇzena rotace mˇr´ıˇzky tak aby smˇer osy x odpov´ıdal novému smˇeru vˇetru. Viz. obrázek 4.4. Tento zp˚ usob zavád´ı chybu pˇri diskretizaci z reáln´ ych ˇc´ısel vznikl´ ych rotac´ı na celá ˇc´ısla index˚ u do mˇr´ıˇzky, coˇz nen´ı tak v´ yznamné jako hlavn´ı nev´ yhoda tohoto postupu, která se projevuje pˇri u ´hlech rotace r˚ uzn´ ych od násobku 90◦ . Tehdy se nezachovává celkov´ y poˇcet sand slab v systému, t´ım se zároveˇ n mˇen´ı i havg a href , coˇz ovlivn´ı cel´ y v´ ypoˇcet. Proto byl v této práci pouˇzit jin´ y pˇr´ıstup.

4.6.1

Vˇ etrn´ e pole

K hlavn´ı mˇr´ıˇzce obsahuj´ıc´ı buˇ nky s poˇcty sand slab se pˇridává pomocná mˇr´ıˇzka, která mimo jiné obsahuje informaci, ze které sousedn´ı buˇ nky vane v´ıtr do aktuáln´ı a do které buˇ nky vane v´ıtr z aktuáln´ı buˇ nky. Tvorba 1

V´ yˇska je a/3 tedy 1/3 vzd´ alenosti nejbliˇzˇs´ıch sousedn´ıch bunˇek mˇr´ıˇzky.

20

Obrázek 4.4: Rotace mˇr´ıˇzky umoˇzn ˇuje simulovat v´ıtr (Winter a Summer ) vanouc´ı z libovolného smˇeru. Pˇrevzato z [2]. vˇetrného pole nevyˇzaduje operace v plovouc´ı ˇrádové ˇcárce a je tˇreba proj´ıt celé pole maximálnˇe 3krát, takˇze zmˇena smˇeru vˇetru pˇri pouˇzit´ı vˇetrného pole, nen´ı ani moc v´ ypoˇcetnˇe nároˇcná.

21

Kapitola 5

Implementace Základn´ı datovou strukturou je dvourozmˇerná mˇr´ıˇzka, dále oznaˇcovaná jako hlavn´ı mˇr´ıˇzka, reprezentovaná jednorozmˇern´ ym polem, dále oznaˇcovan´ ym jako hlavn´ı pole. Tato hlavn´ı mˇr´ıˇzka urˇcuje hodnotou sv´ ych bunˇek poˇcet sand slab na jednotliv´ ych pozic´ıch. Jej´ı grafická reprezentace je mˇr´ıˇzka pravideln´ ych ˇsesti´ uheln´ık˚ u v konfiguraci ukázané obrázkem 5.1. Po zaveden´ı následuj´ıc´ıho znaˇcen´ı • xs - poˇcet bunˇek ve smˇeru osy x • ys - poˇcet bunˇek ve smˇeru osy y • xi - souˇradnice aktuáln´ı buˇ nky ve smˇeru osy x • yi - souˇradnice aktuáln´ı buˇ nky ve smˇeru osy y • size - celkov´ y poˇcet bunˇek v poli • h(xi , yi ) - hodnota buˇ nky na pozici xi , yi lze vyjádˇrit mapovac´ı funkci z index˚ u mˇr´ıˇzky do indexu pole takto i = yi xs + xi . Hraniˇcn´ı podm´ınky jsou definovány tak aby hraniˇcn´ı buˇ nky sousedili s hraniˇcn´ımi buˇ nkami na opaˇcném konci mˇr´ıˇzky, tato vlastnost je nezbytná pro správné fungován´ı modelu, obrázek 5.2. Kromˇe hlavn´ı mˇr´ıˇzky je zavedena pomocná mˇr´ıˇzka, dále oznaˇcovaná jako mˇr´ıˇzka pˇr´ıznak˚ u, stejn´ ych rozmˇer˚ u a tedy i s identick´ ym indexován´ım. Ta obsahuje pomocné pˇr´ıznaky o vˇsech buˇ nkách hlavn´ı mˇr´ıˇzky. Typy pˇr´ıznak˚ u jsou vypsané v následuj´ıc´ım seznamu. • Pro hraniˇcn´ı buˇ nky obsahuje pˇr´ıznaky, na které hranici mˇr´ıˇzky se buˇ nka nacház´ı. • Pˇr´ıznak zda je buˇ nka ve vˇetrném st´ınu. • Pˇr´ıznaky urˇcuj´ıc´ı vˇetrné pole. 22

Program se skládá ze 4 logick´ ych ˇcást´ı. Tyto ˇcásti sd´ılej´ı pomoc´ı ukazatel˚ u hlavn´ı mˇr´ıˇzku a mˇr´ıˇzku pˇr´ıznak˚ u, jinak jsou oddˇelené a mohou spolu komunikovat jen pomoc´ı k tomu urˇcen´ ych funkc´ı. V následuj´ıc´ıch podkapitolách budou popsány d˚ uleˇzité vlastnosti tˇechto ˇcásti programu.

Obrázek 5.1: Pouˇz´ıtá indexace na mˇr´ıˇzce ˇsesti´ uheln´ık˚ u

5.1

Model

Zde prob´ıhá vlastn´ı simulace, ostatn´ı ˇcásti programu do simulace niˇc´ım nezasahuj´ı a pro svou práci jen vyuˇz´ıvaj´ı data vytvoˇrená modelem, která jsou uloˇzena v hlavn´ı mˇr´ıˇzce.

5.1.1

Vytvoˇ ren´ı vˇ etrn´ eho pole

Inicializace vˇetrného pole je prvn´ı vˇec, kterou model mus´ı provést po své vlastn´ı inicializaci. Bez informace, kudy vane v´ıtr mˇr´ıˇzkou, simulace nem˚ uˇze prob´ıhat. Na mˇr´ıˇzce pravideln´ ych ˇsesti´ uheln´ık˚ u je moˇzné pˇresouvat se z jedné buˇ nky do buˇ nky sousedn´ı pouze pod u ´hlem, kter´ y je násobek 60◦ . Proto algoritmus generuj´ıc´ı vˇetrné pole mus´ı pracovat s chybou vzniklou touto

23

Obrázek 5.2: Hraniˇcn´ı podm´ınky pro mˇr´ıˇzku 4x4

diskretizac´ı v pˇredchoz´ıch kroc´ıch pro urˇcen´ı smˇeru vˇetru v následuj´ıc´ım kroku. Na obrázku 5.3 je pˇr´ıklad práce algoritmu, a tabulka 5.1 ukazuje samotn´ y algoritmus.

Obrázek 5.3: Pˇr´ıklad algoritmu pro generován´ı vˇetrného pole pro v´ıtr vanouc´ı pod u ´hlem 23◦ . (a) chyby vzniklé diskretizac´ı (b) v´ ystup algoritmu, ˇc´ıslo na ˇsipkou ukazuje chybu zp˚ usobenou pˇresunem dan´ ym smˇerem, ˇc´ıslo na zaˇcátku ˇsipky je aktuáln´ı hodnota chyby

5.1.2

Vˇ etrn´ a eroze a ukl´ ad´ an´ı

N´ ahodnˇe je zvolena pozice buˇ nky s = (xi , yi ), která nemá nastaven pˇr´ıznak vˇetrného st´ınu ani nereprezentuje skalnaté podloˇz´ı, tedy h(xi , yi ) > 0. Hodnota h(xi , yi ) je dosazena do rovnice 4.4, t´ım z´ıskáme vzdálenost pˇresunu L. Ten udává poˇcet bunˇek, o které se mus´ıme posunout smˇerem po vˇetru z buˇ nky s do c´ılové buˇ nky d = (xj , yj ). Teprve poté se provede eroze buˇ nky s dekrementac´ı jej´ı hodnoty h0 (xi , yi ) = h(xi , yi ) − 1. Pokud c´ılová buˇ nka 24

error = 0; axis = (max_angle + min_angle)/2; error_max = wind_angle- max_angle; error_min = wind_angle - min_angle; for every i do: [i].wind = 0; while ( [i].wind==0 ) do: if (error > axis) [i].wind = flag_max; error = error + error_max; i = [i].neigbour_max; else [i].wind = flag_mix; error = error + error_min; i = [i].neigbour_min;

Tabulka 5.1: Algoritmus generuj´ıc´ı vˇetrné pole. i je index do hlavn´ıho pole, yu ´hel vˇetru, max angle a min angle jsou maximáln´ı a wind angle je zadan´ minimáln´ı hodnota u ´hl˚ u, kter´ ymi se diskretizuje hodnota wind angle a error je chyba vzniklá pˇredchoz´ımi kroky. leˇz´ı ve vˇetrném st´ınu, pak je provedeno uloˇzen´ı h0 (xj , yj ) = h(xj , yj ) + 1. Pokud leˇz´ı mimo vˇetrn´ y st´ın tak jsou urˇceny pravdˇepodobnosti uloˇzen´ı1 a porovnány s vygenerovan´ ym náhodn´ ym ˇc´ıslem z intervalu h0.0, 1.0i. Na p´ıseˇcném povrchu pak nastáv´ a uloˇzen´ı pokud náhodné ˇc´ıslo leˇzelo v intervalu h0.0, 0.6i a pro skalnat´ y povrch pokud bylo v intervalu h0.0, 0.4i. V pˇr´ıpadˇe, ˇze uloˇzen´ı nenastalo, je buˇ nka d ponechána beze zmˇeny a vyjádˇr´ı se nová vzdálenost L, dosazen´ım hodnoty h(xj , yj ) do rovnice 4.4, toto reprezentuje skok sand slab po povrchu. Pˇr´ıpadnˇe dalˇs´ı pˇresuny se opakuj´ı tak dlouho, dokud nedojde k uloˇzen´ı.

5.1.3

Eroze vlivem gravitace

Pro erodovanou buˇ nku a pro buˇ nku, do které probˇehlo uloˇzen´ı, se provád´ı test, zda nebyl poruˇsen klidov´ y u ´hel svahu, tedy zda se poˇcet sand slab mezi aktuáln´ı a jednou pˇr´ıpadnˇe v´ıce sousedn´ımi buˇ nkami neliˇs´ı v´ıce jak o 2. Pokud je klidov´ yu ´hel poruˇsen, vybere se náhodnˇe jedna sousedn´ı buˇ nka, která tuto podm´ınku nesplˇ nuje a mezi n´ı a aktuáln´ı buˇ nkou nastane pˇresun jednoho sand slab. Tato sousedn´ı buˇ nka se poté stane aktuáln´ı a proces se zopakuje. Takto se pokraˇcuje, dokud nen´ı zjiˇstˇeno, ˇze aktuáln´ı a sousedn´ı buˇ nky neporuˇsuj´ı klidov´ yu ´hel. Pˇr´ıklad je na obrázku 5.4 1

Ps = 0.6 pro h(xj , yj ) > 0 a Pns = 0.4 pro h(xj , yj ) = 0

25

Obrázek 5.4: Pˇr´ıklad eroze vlivem gravitace. Uvedeny jsou hodnoty jednotliv´ ych bunˇek a smˇer pˇresunu sand slab.

5.1.4

Aktualizace vˇ etrn´ eho st´ınu

Nejdˇr´ıve je tˇreba zd˚ uraznit, ˇze vˇetrn´ y st´ın je brán jako oblast zabraná pod ◦ u ´hlem 15 z vyˇsˇs´ıho vrcholu, coˇz odpov´ıdá rozd´ılu v´ yˇsek dvou sousedn´ıch bunˇek o 1, obrázek 5.5. Toho vyuˇz´ıvá dále popsan´ y algoritmus.

ˇ Obrázek 5.5: Pˇr´ıklady vˇetrného st´ınu. Cernˇ e oznaˇcené buˇ nky jsou ve vˇetrném st´ınu vrˇzeném nˇekterou z bunˇek nacházej´ıc´ıch se proti vˇetru.

Vˇetrn´ y st´ın se aktualizuje po kaˇzdé zmˇenˇe v hlavn´ı mˇr´ıˇzce (tzn. po kaˇzdém odeˇcten´ı nebo pˇriˇcten´ı jednoho sand slab). Jedinˇe tak se dá udrˇzovat informace o vˇetrném st´ınu v konzistentn´ım stavu aniˇz by bylo nutno procházet celou hlavn´ı mˇr´ıˇzku. Aktualizace provede kontrolu a pˇr´ıpadnou zmˇenu pˇr´ıznaku vˇetrného st´ınu, kdyˇz se buˇ nka jej´ıˇz hodnota byla sn´ıˇzena dostala do st´ınu nebo pokud byla jej´ı hodnota zv´ yˇsena a dostala se ze st´ınu. Dále se kontroluje, jak se zmˇenil vˇetrn´ y st´ın touto buˇ nkou vrˇzen´ y. Tabulka 5.2 ukazuje popsan´ y algoritmus. Kde i a j jsou indexy do hlavn´ıho pole, wshadow distance je poˇcet bunˇek, kter´ y byl schován ve vˇetrném st´ınu za aktuáln´ı buˇ nkou pˇred t´ım, neˇz byla jej´ı hodnota zmˇenˇena a shadow height udává, o kolik sand slab by musela b´ yt právˇe testovaná buˇ nka 2 vyˇsˇs´ı, aby nebyla ve vˇetrném st´ınu. Pokud je tato 2

T´ım je myˇslena buˇ nka, na kterou v algoritmu pr´ avˇe ukazuje index i, nikoliv tedy

26

j = [i].updwind_index; while ( [j].wind_shadow_flag == true ) do: j = [j].upwind_index; shadow_height = [j].height - [i].height - distance(i,j) - 1; if (shadow_height > 0) [i].wind_shadow_flag = true; else [i].wind_shadow_flag = false; shadow_height = 0; wshadow_distance = number of cells covered by windshadow casted from i; wshadow_distance = wshadow_distance + 1; while (wshadow_distance > 0) do: wshadow_distance = wshadow_distance - 1; shadow_height = shadow_height + [i].height; shadow_height = shadow_height - [[i].downwind_index].height; if (shadow_height > 0) [[i].downwind_index].wind_shadow_flag = true; else [[i].downwind_index].wind_shadow_flag = false; shadow_height = shadow_height - 1; if (shadow_height < 0) shadowHeight = 0; i = [i].downwind_index; Tabulka 5.2: Algoritmus pro aktualizaci vˇetrného st´ınu promˇenná rovna nule nebo má zápornou hodnotu, pak je právˇe testovaná buˇ nka mimo vˇetrn´ y st´ın.

5.1.5

Aktualizace hodnoty href

Stˇejnˇe jako v pˇr´ıpadˇe aktualizace vˇetrného st´ınu viz. 5.1.4 se hodnota href d´ a aktualizovat velmi jednoduch´ ym zp˚ usobem, pokud se tak dˇeje po kaˇzdé zmˇenˇe v hlavn´ı mˇr´ıˇzce. Pr˚ umˇern´ y poˇcet sand slab havg je po celou dobu simulace konstantn´ı, jako d˚ ukaz staˇc´ı, ˇze sand slab je konstantn´ı a velikost mˇr´ıˇzky také. Mˇejme promˇennou Sum s takovouto hodnotou Sum =

xs −1,y Xs −1

|h(xi , yi ) − havg |

x,y=0

buˇ nka jej´ıˇz hodnota byla zmˇenˇena.

27

Po kaˇzdé zmˇenˇe, která o 1 sniˇzuje hodnotu aktuáln´ı buˇ nky plat´ı Sum − 1 h(xi , yi ) > havg Sum = Sum + 1 h(xi , yi ) ≤ havg Po kaˇzdé zmˇenˇe, která o 1 zvyˇsuje hodnotu aktuáln´ı buˇ nky, plat´ı Sum − 1 h(xi , yi ) < havg Sum = Sum + 1 h(xi , yi ) ≥ havg Hodnota h(xi , yi ) mus´ı b´ yt brána pˇred samotnou inkrementac´ı resp. dekrementac´ı. Po tomto u ´konu staˇc´ı dosadit novou hodnotu Sum do rovnice 4.5. Takto se z´ıská nová hodnota href aniˇz by bylo tˇreba procházet celé pole.

5.2

Visualizace

Pro trojrozmˇerné zobrazován´ı je na mˇr´ıˇzce zavedena lokáln´ı kartézská soustava souˇradnic, orientovaná CCW. Kaˇzdé buˇ nce hlavn´ı mˇr´ıˇzky na pozici (xi , yi ) a s hodnotou h(xi , yi ) pak odpov´ıdá trojrozmˇern´ y bod (x, y, z). Pˇrevod mezi souˇradnicemi buˇ nky a bodu je proveden následuj´ıc´ım zp˚ usobem. 2xi t yi = 2k • x= t(2xi − 1) yi = 2k + 1 • y = ah(xi , yi ) • z = −1.5syi Z toho vypl´ yvá, ˇze bod (0.0, y, 0.0) odpov´ıdá stˇredu buˇ nky na pozici (0, 0). Parametry a, s, t jsou rozmˇery geometrické reprezentace sand slab, obrázek 5.7. Visualizace mˇr´ıˇzky ˇsesti´ uheln´ık˚ u byla realizována tak, ˇze jsou rohy renderovac´ıch troj´ uheln´ık˚ u um´ıstˇeny ve stˇredech ˇsesti´ uheln´ık˚ u, viz. obrázek 5.6. T´ım vznikaj´ı na stranách mˇr´ıˇzky zubaté okraje, které jsou zahlazeny pomocnou ˇradou rovnoramenn´ ych troj´ uheln´ık˚ u, ty jsou na obrázku také vyznaˇceny.

5.2.1

V´ ypoˇ cet norm´ alov´ ych vektor˚ u vrcholu

Normálov´ y vektor vrcholu vertex, kter´ y je základem osvˇetlovac´ıho modelu, byl vypoˇc´ıtán jako pr˚ umˇer normál 6 troj´ uheln´ık˚ u, které vrchol obklopuj´ı. Po u ´pravách, které zahrnuj´ı v´ ypoˇcet normál a jejich zpr˚ umˇerován´ı, dostáváme vztah 5.1, kter´ y vrcholu odpov´ıdaj´ıc´ımu buˇ nce na pozici (xi , yi ) pˇriˇrad´ı v´ ysledn´ y vektor ~n = (nx , ny , nz ), kter´ y je tˇreba dále znormalizovat.

28

Obrázek 5.6: Zobrazován´ı mˇr´ıˇzky ˇsesti´ uheln´ık˚ u

nx = 3as(dhw − dhe ) + (3as/2)(dhsw − dhse − dhne + dhnw ) ny = 18st nz = 3at(dhsw + dhse − dhne − dhnw )

(5.1)

Parametry √ rovnice a, t, s jsou vysvˇetleny obrázkem 5.7 a jsou na sobˇe závislé t = s 3/2 a a = 2t/3. Zbylé parametry jsou vysvˇetleny následuj´ıc´ım seznamem. • dhw = h(xi − 1, yi ) − h(xi , yi ) • dhsw = h(xi − 1, yi − 1) − h(xi , yi ) • dhse = h(xi + 1, yi − 1) − h(xi , yi ) • dhe = h(xi + 1, yi ) − h(xi , yi ) • dhne = h(xi + 1, yi + 1) − h(xi , yi ) • dhnw = h(xi − 1, yi + 1) − h(xi , yi )

5.2.2

Dynamick´ e st´ıny

Osvˇetlovac´ı model vypoˇc´ıtan´ y pomoc´ı normál vrchol˚ u nen´ı sám o sobˇe dostateˇcn´ y, protoˇze neumoˇzn ˇuje efekt vrˇzeného st´ınu duny na dunu. Byl tedy pˇridán algoritmus 5.3, kter´ y podle dvou u ´hl˚ u urˇcuj´ıc´ıch smˇer ke svˇetelnému zdroji v nekoneˇcnu vrhá st´ınové paprsky z jednotliv´ ych vrchol˚ u. Data takto z´ıskána ale nemaj´ı dostateˇcnou vypov´ıdac´ı hodnotu o struktuˇre terénu, protoˇze informace st´ın, polost´ın, ˇzádn´ y st´ın je pˇr´ıliˇs hrubá. V´ ysledn´ y osvˇetlovac´ı algoritmus proto kombinuje oba pˇr´ıstupy. Pokud je vrchol mimo st´ın, je jeho normálov´ y vektor ponechán beze zmˇeny, pokud je vrchol ve st´ınu, jeho normála je ˇcásteˇcnˇe odklonˇena od p˚ uvodn´ıho smˇeru tak, aby byla zároveˇ n v´ıce odklonˇena od vektoru ukazuj´ıc´ıho ke zdroji svˇetla. Tak je zaruˇceno, ˇze i oblasti ve st´ınu si stále zachovávaj´ı své obrysy. 29

Obrázek 5.7: Rozmˇery kvádru s podstavou pravidelného ˇsesti´ uheln´ıku, jedná se o geometrickou reprezentaci sand slab. for every i do: [i].shadow = 0.0; for every i do: shadow_ray = cast_shadow_ray([i].height); i = [shadow_ray].next_index; while(shadow_ray is not intersecting with the ground) do: [i].shadow = 1.0; i = [shadow_ray].next_index; for every i do: [i].shadow = sum(weight1*[i].shadow + weight2*[[i].all_neigbours].shadow); [i].shadow = [i].shadow / (neighbours_count + 1); Tabulka 5.3: Algoritmus v´ ypoˇctu dynamického st´ınu Odkl´ anˇ en´ı norm´ alov´ eho vektoru Pˇri v´ ypoˇctu osvˇetlovac´ıho modelu záleˇz´ı pouze na u ´hlu mezi normálov´ ym vektorem a vektorem ukazuj´ıc´ım ke zdroji svˇetla. Stávaj´ıc´ı hodnota tohoto u ´hlu se dá z´ıskat snadno pomoc´ı skalárn´ıho souˇcinu normálového vektoru ~n = (nx , ny , nz ) a vektoru smˇeˇruj´ıc´ımu ke svˇetelnému zdroji v nekoneˇcnu ~l = (lx , ly , lz ). cos ϕ = ~l · ~n Hodnota u ´hlu ϕ je pak zvˇetˇsena u ´mˇernˇe hodnotˇe z´ıskané algoritmem 5.3 pro danou buˇ nku (xi , yi ). Smˇer nového normálového vektoru ~n0 lze urˇcit mnoha zp˚ usoby, protoˇze jde jen o to, aby sv´ıral s ~l u ´hel ϕ0 , a takov´ ych vektor˚ u

30

je nekoneˇcnˇe mnoho. V této praci se vycházelo z tˇechto pˇredpoklad˚ u. n0x = tlx

n0z = tlz

Kde t je parametr. T´ım urˇc´ıme, ˇze projekce nového vektoru do roviny (x, 0.0, z) bude leˇzet na stejné pˇr´ımce jako projekce vektoru ~l q 2 02 2 02 02 (n02 (5.2) x + ny + nz ) = 1 =⇒ (tlx ) + ny + (tlz ) = 1 Tato rovnice vycház´ı z jednotkové velikosti obou vektor˚ u. t(lx )2 + n0y ly + t(lz )2 = cos ϕ0 =⇒ t =

cos ϕ0 − n0y ly (lx )2 + (lz )2

(5.3)

Dosazen´ım hodnoty t z rovnice 5.4 do rovnice 5.2 dostáváme kvadratickou rovnici a jej´ım ˇreˇsen´ım jsou dvˇe moˇzné hodnoty n0y . q cos ϕ0 ly ± ly2 + cos2 ϕ0 + 1 u0y = (5.4) ly2 + 1 Dosazen´ım jedné této hodnoty do rovnice 5.4 z´ıskáme hodnotu parametru ysledn´ y t, jeho dosazen´ım pak dostáváme hodnoty n0x a n0z a z´ıskáváme v´ odklonˇen´ y vektor ~n0 = (n0x , n0y , n0z ).

5.3

LOD

Protoˇze je popis této ˇcásti programu pomˇernˇe obsáhl´ y, je mu vˇenována samostatná kapitola, i kdyˇz by bylo logické zaˇradit jej do kapitoly visualizace. Základem je zjednoduˇsen´ y algoritmus pocházej´ıc´ıch z práce [8]. Nejdˇr´ıve si nadefinujeme dále pouˇz´ıvané term´ıny. Rozliˇsen´ım, pokud nebude uvedeno jinak, bude v této kapitole oznaˇcován poˇcet troj´ uheln´ık˚ u v urˇcité oblasti. Zvýˇsit rozliˇsen´ı tedy znamen´ a, nahradit p˚ uvodn´ı jeden velk´ y troj´ uheln´ık v´ıce menˇs´ımi troj´ uheln´ıky, naproti tomu sn´ıˇzit rozliˇsen´ı logicky znamená nahradit v´ıce mal´ ych troj´ uheln´ık˚ u jedn´ım velk´ ym. Abychom mohli oba tyto procesy popsat pokud moˇzno co nejjednoduˇsˇs´ım algoritmem, pouˇzijeme modifikaci techniky obvykle pouˇz´ıvané v oblasti renderován´ı v´ yˇskov´ ych map. Touto technikou je p˚ ulen´ı nejdelˇs´ı strany troj´ uheln´ıka (the longest edge bisection). Modifikace spoˇc´ıvá ve zmˇenˇe názvu na p˚ ulen´ı strany troj´ uheln´ıka a s t´ım i d˚ usledky, které toto pˇrináˇs´ı, obrázek 5.8. D˚ uvod této modifikace je podrobnˇeji vysvˇetlen v 5.3.1, ale jednoduché vysvˇetlen´ı zn´ı, rovnostrann´ y troj´ uheln´ık nemá nejdelˇs´ı stranu. Bisekˇcn´ım bodem budeme rozumˇet bod na stranˇe troj´ uheln´ıku, ve kterém se strana p˚ ul´ı. δ segment je rozd´ıl vzdálenosti mezi spoleˇcn´ ym bodem troj´ uheln´ıkového páru a bisekˇcn´ım bodem troj´ uheln´ıku, kter´ y vznikl spojen´ım tohoto páru. D´ıra (crack ) v mˇr´ıˇzce je jev, kter´ y vzniká 31

na rozhran´ı dvou oblast´ı z nichˇz jedná má vyˇsˇs´ı rozliˇsen´ı neˇz druhá, obrázek 5.13. Pokud je vertex aktivn´ı, pak bude vykreslen. Metoda p˚ ulen´ı strany troj´ uheln´ıku má jako vstupn´ı parametr základn´ı troj´ uheln´ık, kter´ y se dále dˇel´ı. Je tedy tˇreba hlavn´ı mˇr´ıˇzku, která je ˇctvercová nebo obdéln´ıková, rozdˇelit na tyto základn´ı dále uˇz nezjednoduˇsitelné troj´ uheln´ıky spojené vrcholem viz obrázek 5.10 a ty jsou dále zpracovávány.

Obrázek 5.8: Metoda p˚ ulen´ı strany rovnostranného troj´ uheln´ıku

Obrázek 5.9: Geometrická reprezentace delta segmentu. δB = 4, δD = 2.5, δF = 1.5, δH = 0. Pˇrevzato z [8].

32

Obrázek 5.10: (a) Spojen´ı 4 základn´ıch troj´ uheln´ık˚ u pˇres spoleˇcn´ y vrchol. (b) Pˇr´ıklad metody p˚ ulen´ı stran na takovémto u ´tvaru.

5.3.1

V´ yhody a nev´ yhody pouˇ zit´ eho pˇ r´ıstupu

Algoritmus umoˇzn ˇuje, d´ıky metodˇe p˚ ulen´ı strany, lokálnˇe zv´ yˇsit rozliˇsen´ı aniˇz by t´ım bylo v´ yznamnˇe ovlivnˇeno okol´ı, obrázek 5.10b. Po vˇsech optimalizac´ıch uveden´ ych dále je natolik v´ ypoˇcetnˇe nenároˇcn´ y, ˇze se zobrazován´ı skuteˇcnˇe zrychl´ı. Umoˇzn ˇuje vygenerován´ı jednoho triangle strip pro celou mˇr´ıˇzku. Umoˇzn ˇuje elegantnˇe zamezit vzniku dˇer v mˇr´ıˇzce, zv´ yˇsen´ım rozliˇsen´ı na styku dvou oblast´ı s r˚ uzn´ ym stupnˇem rozliˇsen´ı. Nev´ yhody jsou naznaˇceny na obrázku 5.11. Poˇzitá metoda pro generován´ı LOD je nejefektivnˇejˇs´ı na mˇr´ıˇzce (2n +1)x(2n +1), protoˇze ale model vyˇzaduje rozmˇer mˇr´ıˇzky sud´ y 3 ,vzniká jedna ˇrada troj´ uheln´ık˚ u mimo oblast zpracovanou LOD. Dalˇs´ı nev´ yhoda je také zˇrejmá z 5.11c, d´ıky obdéln´ıkovému tvaru bude vˇzdy na jedné stranˇe ˇcást bod˚ u pˇresahovat oblast zpracovávanou LOD. Oba tyto problémy se daj´ı pomˇernˇe snadno vyˇreˇsit napojen´ım pomocného pruhu troj´ uheln´ık˚ u na aktivn´ı body na hranici oblasti zpracované LOD. Posledn´ı problém je zp˚ usoben t´ım, ˇze rozdˇelen´ım rovnostranného troj´ uheln´ıku na dva troj´ uheln´ıky p˚ ulen´ım jeho strany jiˇz nebudou takto vzniklé troj´ uheln´ıky rovnostranné, proto ani pˇri nejvyˇsˇs´ım rozliˇsen´ı nedostáváme ten sam´ y obrázek jako pˇri vypnutém LOD. Tento problém se odstranit nepodaˇrilo. 3

Kv˚ uli napojen´ı protilehl´ ych hranic mˇr´ıˇzky.

33

Obrázek 5.11: Mˇr´ıˇzka 5x6. (a) Zobrazena rovnostran´ ymi troj´ uheln´ıky. (b) Nejvyˇsˇs´ım rozliˇsen´ım zde navrˇzeného LOD. (c) Pˇrekryv obou.

5.3.2

Struˇ cn´ y popis neoptimalizovan´ eho algoritmu

Jedin´ ym vstupn´ım parametrem algoritmu je povolená chyba τp urˇcená v pixelech. Jej´ı hodnota udáv´ a, jaké maximáln´ı velikosti m˚ uˇze nab´ yvat projekce δ segmentu na obrazovku. Prvn´ım zjednoduˇsen´ım je, ˇze δ segment pˇred projekc´ı um´ıst´ıme tak, aby se jedn´ım koncov´ ym bodem nacházel na ose z. Algoritmus testuje troj´ uheln´ıkové páry, které je moˇzné vytvoˇrit na dané mˇr´ıˇzce metodou p˚ ulen´ı strany, a pracuje smˇerem odshora dol˚ u, tedy od nejvˇetˇs´ıho základn´ıho troj´ uheln´ıku k tˇem nejmenˇs´ım. Pokud projekce δ segmentu aktuáln´ıho troj´ uheln´ıkového páru nepˇrekraˇcuje hodnotu τp , pak je pro tento troj´ uheln´ıkov´ y pár sn´ıˇzeno rozliˇsen´ı a algoritmus touto vˇetv´ı hloubˇeji nepokraˇcuje. V opaˇcném pˇr´ıpadˇe je troj´ uheln´ıkov´ y pár ponechán neslouˇcen´ y a oba jeho troj´ uheln´ıky jsou opˇet dˇeleny na troj´ uheln´ıkové páry, pro které prob´ıhá ten sam´ y test s projekc´ı δ segmentu. Algoritmus v této fázi má hlavn´ı nev´ yhodu v tom, ˇze generuje d´ıry v zobrazovaném povrchu, protoˇze netestuje, zda spolu nesoused´ı oblasti s r˚ uzn´ ym rozliˇsen´ım.

5.3.3

Zaveden´ı prahov´ e vzd´ alenosti

Je zˇrejmé, ˇze se v pˇr´ıpadˇe projekce δ segmentu jedná o nároˇcnou operaci,která vyˇzaduje jednak urˇcen´ı vzdálenosti mezi kamerou a aktuáln´ım bodem a poté jeˇstˇe prob´ıhá samotná projekce. Protoˇze jsme schopni urˇcit, jak daleko mus´ı b´ yt pˇri dan´ ych hodnotách τp a δ segmentu kamera od bisekˇcn´ıho bodu, aby se projekce δ segmentu rovnala τp , m˚ uˇzeme operaci samotné projekce vynechat. Pˇri pˇredzpracován´ı nyn´ı m´ısto δ segment˚ u urˇc´ıme pˇr´ımo prahovou vzdálenost d, pˇri které se oba parametry rovnaj´ı. Obr´ azek 5.12. Nejdˇr´ıve urˇc´ıme dp , tedy vzdálenost kamery od projekˇcn´ı plochy v pixelech, kde pres je rozliˇsen´ı na ose y v pixelech. pres dp = tan(f ov/2)

34

A z podobnosti troj´ uheln´ık˚ u dostáváme vzorec pro prahovou vzdálenost. d=

dp δ τp

Obrázek 5.12: Prahová vzd´ alenost d, τp povolená chyba v pixelech, dp vzdálenost kamery od projekˇcn´ı plochy p, δAB hodnota δ segmentu pro body A a B, f ov/2 je poloviˇcn´ı hodnota u ´hlu field of view. Geometrická reprezentace prahové vzdálenosti je koule se stˇredem v bisekˇcn´ım bodˇe. Jakmile se kamera nacház´ı uvnitˇr této koule, chyba pˇrekroˇcila zadanou mez a troj´ uheln´ık je tˇreba rozdˇelit na troj´ uheln´ıkov´ y pár. Kamera nacházej´ıc´ı se vnˇe této koule znamená, ˇze zadaná mez nen´ı pˇrekroˇcena a troj´ uheln´ık nen´ı tˇreba dˇelit. Pro to, aby byl bisekˇcn´ı bod oznaˇcen jako aktivn´ı 4 , je tˇreba, aby byla následuj´ıc´ı podm´ınka splnˇena. q (xp − xc )2 + (yp − yc )2 + (zp − zc )2 < d (xc , yc , zc ) je pozice kamery, (xp , yp , zp ) je pozice bisekˇcn´ıho bodu a d je prahová vzdálenost. Vzorec jeˇstˇe zjednoduˇs´ıme odstranˇen´ım odmocniny a dostáváme rovnici, která byla pouˇzita v algoritmu. (xp − xc )2 + (yp − yc )2 + (zp − zc )2 < d2 4

T´ım je aktu´ aln´ı troj´ uheln´ık rozdˇelen na troj´ uheln´ıkov´ y p´ ar

35

(5.5)

Pro sn´ıˇzen´ı v´ ypoˇcetn´ı nároˇcnosti algoritmu jsou zavedeny dva axis aligned bounding box. Prvn´ı tato krychle má stranu velikosti prahové vzdálenosti d, coˇz znamená, ˇze koule s polomˇerem d je do n´ı vepsána. Pokud plat´ı tato podm´ınka |(xp − xc )| > d/2

nebo |yp − yc | > d/2

nebo |zp − zc )| > d/2

pak se kamera nacház´ı mimo prahovou vzdálenost, troj´ uheln´ık nen´ı tˇreba dále dˇelit a rovnici √ 5.5 uˇz nemus´ıme poˇc´ıtat. Druhá krychle má stranu velikosti a = 2d/ 3 a koule j´ı je opsána. Proto jakmile je splnˇena tato podm´ınka |(xp − xc )| ≤ a/2

and

|yp − yc | ≤ a/2

and

|zp − zc )| ≤ a/2

kamera se nacház´ı uvnitˇr koule, rovnici 5.5 opˇet nemus´ıme poˇc´ıtat a troj´ uheln´ık je tˇreba rozdˇelit. Rovnice 5.5 se tedy poˇc´ıtá jen pokud se kamera nalézá v prostoru mezi obˇema axis aligned bounding box.

5.3.4

Obalov´ an´ı prahov´ ych vzd´ alenost´ı

Doposud byl algoritmus jen optimalizován, ale stále generuje oblasti o r˚ uzn´ ych rozliˇsen´ıch, a t´ım vznikaj´ı d´ıry v zobrazovaném terénu, obrázek 5.13a. Vertex nacházej´ıc´ı se na tomto rozhran´ı naz´ yváme T-junction a je zdrojem dˇer. Zabránit vzniku T-junctions a t´ım i dˇer lze pomoc´ı dodrˇzován´ı jednoduchého pravidla. Pokud je vertex aktivn´ı, mus´ı b´ yt vˇsichni jeho pˇredch˚ udci aktivn´ı, obrázek 5.13b. Protoˇze cestovat vzh˚ uru grafem za u ´ˇcelem aktivace vˇsech pˇredch˚ udc˚ u pokaˇzdé, kdyˇz je nalezen aktivn´ı vertex, by bylo velmi nároˇcné a neefektivn´ı, pozmˇen´ıme trochu náˇs pˇr´ıstup. Urˇc´ıme prahové vzdálenosti pomoc´ı δ segmentu jen u list˚ u grafu. Jakmile uzel nen´ı listem, pak jeho prahovou vzdálenost urˇc´ıme tak, aby obalovala prahové vzdálenosti vˇsech jeho potomk˚ u. T´ım je zaruˇceno, ˇze pokud je vzdálenost kamery od bodu menˇs´ı neˇz jeho prahová vzdálenost, pak je zároveˇ n vzdálenost kamery od vˇsech pˇredk˚ u bodu menˇs´ı neˇz jejich prahové vzdálenosti a tyto jsou tedy také aktivn´ı.

5.3.5

Generov´ an´ı obecn´ eho triangle strip

Triangle strip je z hlediska zadáván´ı bod˚ u mnohem hospodárnˇejˇs´ı, neˇz zadáván´ı bod˚ u pro jednotlivé troj´ uheln´ıky. Toto se samozˇrejmˇe projevuje i na v´ ykonu zobrazován´ı. Na pravidelné mˇr´ıˇzce se triangle strip utvoˇr´ı snadno, je zde pˇredem známá velikost, tvar troj´ uheln´ıku a jeho pozice v˚ uˇci ostatn´ım a tyto vlastnosti se pr˚ ubˇehem ˇcasu nemˇen´ı. I v pˇr´ıpadˇe, kdy se v´ yˇsky na 2D mˇr´ıˇzce dynamicky mˇen´ı, ˇc´ımˇz se zároveˇ n v ˇcase mˇen´ı jedna ze souˇradnic bod˚ u troj´ uheln´ık˚ u, je stále nemˇenná ortogonáln´ı projekce troj´ uheln´ık˚ u do plochy (x, 0, z), coˇz je stále postaˇcuj´ıc´ı informace. Pˇri pouˇzit´ı LOD je pˇredem 36

známo jen to, ˇze ortogonáln´ı projekce vˇsech troj´ uheln´ık˚ u které mohou vzniknout, bude z urˇcité omezené mnoˇziny (napˇr. obrázek5.13b), ale nen´ı pˇredem jasné, kter´ y s kter´ ym nakonec budou sousedé. V [8] je navrˇzen algoritmus, kter´ y pomoc´ı vkládán´ı zdegenerovan´ ych troj´ uheln´ık˚ u vytvoˇr´ı obecn´ y triangle strip pro celou oblast zpracovanou LOD. V algoritmu 5.4 se vyskytuj´ı tyto promˇenné: V je pole bod˚ u tvoˇr´ıc´ıch v´ ysledn´ y triangle strip, v n a v (n-1) jsou posledn´ı a pˇredposledn´ı bod pole V, n je v´ yˇska binárn´ıho stromu vzniklého dˇelen´ım troj´ uheln´ık˚ u, i x jsou indexy do mˇr´ıˇzky kde x odpov´ıdá bod˚ um vyznaˇcen´ ym na obrázku 5.14, parity je hodnota 0 nebo 1 podle u ´rovnˇe, na které se nalézáme v binárn´ım stromu, a c l a c r. bisekˇcn´ı body levého a pravého troj´ uheln´ıka. Levý a pravý je pouhé oznaˇcen´ı. Mˇejme mateˇrsk´ y troj´ uheln´ık s vrcholy A, B, v a bisekˇcn´ım bodem c. v je vrchol proti c a A, B, v jsou uspoˇrádány v CCW orientaci. Levý troj´ uheln´ık je ten, jehoˇz body v CCW orientaci jsou A, c, v, pravý troj´ uheln´ık je ten, jehoˇz body v CCW orientaci v, c, B, obrázek 5.15.

ˇ sen´ı pomoc´ı aktivován´ı vˇsech Obrázek 5.13: (a) Pˇr´ıklad T-junctions. (b) Reˇ rodiˇcovsk´ ych bod˚ u.

37

tris-append(V, v, p) 1 if (v != v_(n-1) ) and (v != v_n) 2 if (p != V.parity) 3 V.parity = p 4 else 5 V = (V,v_(n-1) ) 6 V = (V, v) submesh-refine(V, i, j, l) 1 if (l > 0) and i.active 2 submesh-refine(V, j, c_l(i,j), l-1) 3 tstrip-append(V, i, l mod 2) 4 submesh-refine(V, j, c_r(i,j), l-1) mesh-refine(V, n) 1 V.parity = 0 2 V = (i_sw, i_sw) 3 submesh-refine(V, i_c, 4 tstrip-append(V, i_se, 5 submesh-refine(V, i_c, 6 tstrip-append(V, i_ne, 7 submesh-refine(V, i_c, 8 tstrip-append(V, i_nw, 9 submesh-refine(V, i_c, 10 V = (V, i_sw)

i_s, 1) i_e, 1) i_n, 1) i_w,

n) n) n) n)

Tabulka 5.4: Algoritmus generuj´ıc´ı obecn´ y triangle strip. Pˇrevzato z [8]

Obrázek 5.14: Pr˚ uchod mˇr´ıˇzkou generuj´ıc´ı obecn´ y triangle strip. Pˇrevzato z [9]

38

5.4

Vstup / v´ ystup

Protoˇze model umoˇzn ˇuje volbu parametr˚ u 5 je vhodné m´ıt nástroj, kter´ y umoˇzn´ı porovnávat v´ ysledky r˚ uzn´ ych nastaven´ı. Proto byl do programu pˇridán kód umoˇzn ˇuj´ıc´ı uloˇzen´ı hlavn´ıho pole na HDD a jeho opˇetovného nahrán´ı. Zde budou popsány jen jeho v´ yznamnˇejˇs´ı vlastnosti.

5.4.1

Komprese dat

Aby v´ ysledné soubory nezab´ıraly zbyteˇcnˇe mnoho m´ısta, byla zavedena jednoduchá ale velmi u ´ˇcinná komprese 6 , která vyuˇz´ıvá vlastnost´ı modelu. Gravitaˇcn´ı eroze zajiˇst’uje, ˇze rozd´ıl v´ yˇsek sousedn´ıch bunˇek nepˇrekroˇc´ı 2. Tato vlastnost je vyuˇzita a do souboru se ukládá jen 2B hodnota buˇ nky nalézaj´ıc´ı se v hlavn´ım poli na pozice 0, zbytek je uloˇzen jako rozd´ıl oproti buˇ nce pˇredchoz´ı. Zde je tˇreba upozornit, ˇze v naˇsem pˇr´ıpadˇe pˇredchoz´ı buˇ nka neznamená buˇ nku s indexem i − 1, obrázek 5.16. Rozd´ıl v´ yˇsek sousedn´ıch bunˇek m˚ uˇze tedy nab´ yvat pˇeti hodnot −2, −1, 0, 1, 2, které m˚ uˇzeme zakódovat napˇr´ıklad takto. Hodnota rozd´ılu -2 -1 0 1 2 5 6

bitov´ y k´ od 00 01 10 110 111

S´ıla a u ´hel vˇetru, poˇcet vˇetr˚ u atd. Po kompresi mˇr´ıˇzka 257x257 zabere pˇribliˇznˇe 19KB, 1025x1025 pˇribliˇznˇe 280KB

Obrázek 5.15: Pˇr´ıklad levých a pravých troj´ uheln´ık˚ u

39

T´ımto kódován´ım je jeden Byte komprimován pr˚ umˇernˇe 2.4 bity. Optimalizace, která by prohledávala, které znaky se v poli v´ yˇsek vyskytuj´ı v´ıce a tˇem pˇridˇelila 2bitové hodnoty, nebyla implementována z d˚ uvodu rychlosti a zv´ yˇsen´ı sloˇzitosti tohoto velmi jednoduchého algoritmu.

Obrázek 5.16: (a) Buˇ nky na pozic´ıch i a i + 1 nemus´ı b´ yt vˇzdy sousedn´ı. (b) Tento zp˚ usob cestován´ı mˇr´ıˇzkou sousedstv´ı bunˇek neporuˇsuje.

5.4.2

V´ıce dat v jednom souboru

Protoˇze program umoˇzn ˇuje uloˇzen´ı po kaˇzdém x poˇctu iterac´ı, takˇze lze pohodlnˇe bˇehem jedné simulace poˇr´ıdit stovky uloˇzen´ ych pol´ı, byl zaveden systém aktivn´ıho souboru. Program pracuje s jedn´ım aktuáln´ım souborem, do kterého nebo z kterého ukládá/nahrává vˇsechna data, dokud mu nen´ı ˇreˇceno, aby aktivn´ı soubor zmˇenil. T´ımto se zvyˇsuje pˇrehlednost a jednoduchost manipulace s uloˇzen´ ymi daty. Pˇr´ıklad aktivn´ıho souboru, do kterého jsou právˇe uloˇzena data ze 4 hlavn´ıch mˇr´ıˇzek, je na obrázku 5.17. Jedna uloˇzená poloˇzka obsahuje tyto informace. • Deskriptor dat – Kolika iterac´ı probˇehlo na uloˇzené mˇr´ıˇzce. – Velikost mˇr´ıˇzky. – Velikost komprimovaného pole v´ yˇsek. ´ – Uhel vˇetru. – Poloha a smˇer pohledu kamery. • Komprimované hlavn´ı pole.

40

Obrázek 5.17: Struktura aktivn´ıho souboru, kter´ y právˇe obsahuje data 4 hlavn´ıch mˇr´ıˇzek. D znaˇc´ı deskriptor dat a data oznaˇcuje komprimované hodnoty hlavn´ı mˇr´ıˇzky.

41

Kapitola 6

Ovl´ ad´ an´ı programu 6.1

Pˇ riloˇ zen´ y k´ od

Program je naprogramován v C++ s pomoc´ı knihoven OpenGL a GLUT a nen´ı nijak vázán na konkrétn´ı operaˇcn´ı systém. Kód je pˇriloˇzen ve dvou verz´ıch. Jako projekt Microsoft Visual Studio 6.0 s nutn´ ymi zmˇenami kódu pro tento ANSI C++ nekompatibiln´ı pˇrekladaˇc a jako kódy a makefile soubor pro platformu Linux s pˇrekladaˇcem gcc.

6.2

Uˇ zivatelsk´ e prostˇ red´ı a pohyb kamery

Uˇzivatelské prostˇred´ı je vytvoˇreno pomoc´ı menu. Jeho hierarchie je popsána n´ asleduj´ıc´ım seznamem. • Run – spouˇst´ı simulaci. • Camera positions – mˇen´ı pozici kamery, smˇer pohledu je vˇzdy smˇerem do stˇredu mˇr´ıˇzky. • Visualization – zmˇena nastaven´ı parametr˚ u zobrazován´ı. • Wind – nastaven´ı smˇeru s´ıly vˇetru a poˇcet vˇetr˚ u. • Terrain – umoˇzn ˇuje zmˇenit rozmˇery hlavn´ı mˇr´ıˇzky a vytvarovat umˇel´ y tvar na p´ıseˇcném povrchu. • Average height – nastaven´ı pr˚ umˇerné hodnoty jednotliv´ ych bunˇek. Slouˇz´ı ke zmˇenˇe v´ yˇsky. • Input / Output – ukládán´ı a nahráván´ı aktuáln´ıho stavu hlavn´ı mˇr´ıˇzky a ukládán´ı aktuáln´ıho okna do BMP souboru. Kromˇe menu Camera positions lze pozici kamery mˇenit i klávesnic´ı a to takto. 42

• Up arrow – pohyb kamery vpˇred • Down arrow – pohyb kamery vzad • Left arrow – rotace pohledu doleva • Righ arrow – rotace pohledu doprava • klávesa ’a’ – rotace pohledu nahoru • klávesa ’z’ – rotace pohledu dol˚ u

6.3

Poˇ zadavky na hardware

Nen´ı implementováno ˇzádné pouˇz´ıván´ı hardwarové akcelerace, proto program nemá ˇzádné speciáln´ı poˇzadavky na vlastnosti grafické karty. Pro plynul´ y pr˚ ubˇeh simulace na mˇr´ıˇzce 257 x 257 je nutn´ y procesor s taktovac´ı frekvenc´ı minimálnˇe 1GHz. Program má tyto pamˇet’ové nároky. • 18MB pro mˇr´ıˇzku 257 x 257. • 40MB pro mˇr´ıˇzku 513 x 513. • 110MB pro mˇr´ıˇzku 1025 x 1025.

43

Kapitola 7

Popis proveden´ ych experiment˚ u Chován´ı modelu lze ovlivnit následuj´ıc´ımi kontroln´ımi parametry a nastaven´ımi. • Intenzita vˇetru urˇcená hodnotou L0 . ´ • Uhel pod kter´ ym v´ıtr vane. • Nastaven´ım poˇctu stˇr´ıdaj´ıc´ıch se vˇetr˚ u. • Nastaven´ım poˇctu cykl˚ u, po kter´ ych se v´ıtr zmˇen´ı. • Mnoˇzstv´ım p´ısku v modelu, dáno souˇctem hodnot vˇsech bunˇek hlavn´ı mˇr´ıˇzky. • Rozmˇery hlavn´ı mˇr´ıˇzky. ˇ ast mˇr´ıˇzky lze pˇred zaˇcátkem simulace vymodelovat umˇele, pr˚ • C´ ubˇeh simulace je t´ım samozˇrejmˇe ovlivnˇen. Jeden cyklus je oznaˇcen´ı pro jeden bˇeh programu, pˇri kterém se provede jedna eroze a jedno uloˇzen´ı vlivem vˇetru a management1 s t´ım spojen´ y. Term´ın velký cyklus oznaˇcuje 50000 cykl˚ u a jedná se o hodnotu zavedenou na základˇe pozorován´ı. Po probˇehnut´ı jednoho velkého cyklu, se terén na mˇr´ıˇzce 257 x 257 zˇretelnˇe zmˇen´ı. Pˇri popisu skupin obrázk˚ u se zaˇc´ıná horn´ım lev´ ym obrázkem a konˇc´ı se spodn´ım prav´ ym. 1

Testy na pˇrekroˇcen´ı klidového u ´hlu, aktualizace hodnoty href a aktualizace vˇetrného st´ınu.

44

7.1

Z´ avislost na dostupn´ em mnoˇ zstv´ı p´ısku

Zde jsou ukázány zmˇeny chován´ı modelu v závislosti na celkovém mnoˇzstv´ı p´ısku, které bylo na poˇcátku simulace nastaveno pomoc´ı stejné hodnoty ve vˇsech buˇ nkách hlavn´ı mˇr´ıˇzky. Obrázky 1-4 v souboru obrázk˚ u 7.1. Nastaven´ı je toto, mˇr´ıˇzka 513x513, u ´hel vˇetru 0◦ a poˇcáteˇcn´ı hodnota vˇsech bunˇek byla 1. Protoˇze dostupného p´ısku je málo, modelu trvá dlouhou dobu neˇz vzniknou prvn´ı duny, jedná se o Barchan dunes. Obrázky 5-8 v souboru obrázk˚ u 7.1. Nastaven´ı je toto, mˇr´ıˇzka 513x513, u ´hel vˇetru 0◦ , vˇsechny obrázky byly sn´ımány po 1500 velk´ ych cyklech. Mˇen´ı se dostupné mnoˇzstv´ı p´ısku, je vidˇet, ˇze s jeho pˇrib´ yvaj´ıc´ım mnoˇzstv´ım se duny typu Barchan postupnˇe mˇen´ı na pole dun.

7.2

Z´ avislost na nastaven´ı parametru L0

Tento parametr reprezentuje s´ılu vˇetru. D˚ usledkem zvyˇsován´ı s´ıly vˇetru je n´ ar˚ ust dun v´ yˇsky a jejich profil pˇrestává b´ yt asymetrick´ y a stává se opˇet symetrick´ ym, soubor obrázk˚ u 7.1. D˚ uvod je zˇrejm´ y pˇri pohledu na rovnici 4.4, zvyˇsován´ım parametru L0 se sniˇzuje vliv zbytku této rovnice na v´ yslednou vzdálenost pˇrenosu L a model se zaˇc´ıná chovat podobnˇe jako pˇri pouˇzit´ı rovnice 4.1. Mˇr´ıˇzka velikosti 513 x 513, u ´hel vˇetru je 0◦

7.3

LOD

Soubory obrázk˚ u 7.3 a 7.4 ukazuj´ı práci algoritmus pro sniˇzován´ı u ´rovnˇe detailu v závislosti na vzdálenosti od pozorovatele a v závislosti na zadané povolené chybˇe. Hlavn´ı mˇr´ıˇzka má rozmˇery 513 x 513.

7.4

Umˇ el´ e objekty ve sc´ enˇ e

Soubor obrázk˚ u 7.5 ukazuje v´ yvoj simulace, kdyˇz byl do scény vloˇzen jehlan. Mˇr´ıˇzka velikost 513 x 513, nadefinovány 4 vˇetry vanouc´ı postupnˇe pod u ´hly 0◦ , 180◦ , 90◦ a 270◦ a stˇr´ıdaj´ıc´ı se po 20 velk´ ych cyklech. Jak je vidˇet z posledn´ıho obrázku i po 14 000 velk´ ych cyklech je jehlan stále patrn´ y. To je d´ ano ˇcast´ ym stˇr´ıdán´ım vˇetr˚ u. Soubor obrázk˚ u 7.6 ukazuje v´ yvoj simulace, kdyˇz byla na poˇcátku simulace vytvoˇrena uprostˇred mˇr´ıˇzky parabolická prohlubeˇ n. Mˇr´ıˇzka velikost 513 x 513, definován je pouze jeden v´ıtr intenzity L0 = 5 a vanouc´ı pod u ´hlem 0◦ . Oproti pˇredchoz´ı simulaci 7.5 je umˇel´ y tvar témˇeˇr zahlazen po 10000 velk´ ych cyklech i kdyˇz jeho vliv na terén je stále patrn´ y.

45

Obrázek 7.1: Obr. 1-4. Poˇcáteˇcn´ı hodnota vˇsech bunˇek hlavn´ı mˇr´ıˇzky byla pˇred zaˇcátkem simulace rovna 1. Obrázky sn´ımány po 500, 1500, 2000 a 2500 velk´ ych cyklech. Obr. 5-8. Poˇcáteˇcn´ı hodnoty vˇsech bunˇek hlavn´ı mˇr´ıˇzky byly pˇred zaˇcátkem simulace rovny 3, 5, 7, 10. Vˇsechny obrázky sn´ımány po 1500 velk´ ych cyklech. 46

Obrázek 7.2: Vliv parametru L0 na pr˚ ubˇeh simulace. Kamera ja um´ıstˇena st´ ale ve stejné pozici. Obr. 1-2, L0 = 5, 1000 a 2000 velk´ ych cykl˚ u. Obr. 3-4, L0 = 10, 1000 a 2000 velk´ ych cykl˚ u. Obr. 5-6, L0 = 20, 1000 a 2000 velk´ ych cykl˚ u.

47

Obrázek 7.3: Pˇr´ıklad funkce LOD na umˇelém tvaru. V´ ypoˇcet st´ın˚ u je vypnut. Vlevo je zobrazen wireframe, vpravo obyˇcejné zobrazen´ı té samé scény. Parametr LOD je 1, 2, 4, 8. 48

Obrázek 7.4: Pˇr´ıklad funkce LOD na povrchu tvoˇreném dunami. Vlevo je zobrazen wireframe, vpravo normáln´ı zobrazen´ı té samé scény. Hodnoty parametru LOD jsou opˇet tyto 1, 2, 4, 8. 49

Obrázek 7.5: Do hlavn´ı mˇr´ıˇzky je um´ıstnˇen jehlan. Jsou nadefinovány 4 vˇetry, stejné intenzity L0 = 5 vanouc´ı pod u ´hly 0◦ , 180◦ , 90◦ a 270◦ . Zmˇena vˇetru nastává po 20 velk´ ych cyklech. Obrázky sn´ımány po 500, 2500, 5000, 7500, 11000, 12000, 13000 a 14000 velk´ ych cyklech. 50

Obrázek 7.6: Uprostˇred hlavn´ı mˇr´ıˇzky byla na zaˇcátku simulace vytvoˇrena parabolická prohlubeˇ n. V´ıtr intenzity L0 = 5, vanouc´ı pod u ´hlem 0◦ . Obrázky sn´ımány po 100, 500, 1000, 2500, 4200, 5000, 7000 a 10000 velk´ ych cyklech. 51

Obrázek 7.7: Obr. 1-2. Barchan dune se st´ınem a beze st´ınu. Obr 3-8. Ta samá scéna zobrazená postupnˇe pomoc´ı ˇsesti´ uheln´ık˚ u. Troj´ uheln´ık˚ u. Scéna je bez textur. Textury pˇridány. Pˇridán st´ın. Vyhlazován´ı pr˚ umˇerován´ım z 6 okol´ı. Vyhlazován´ı pr˚ umˇerován´ım z 18 okol´ı. 52

Kapitola 8

Z´ avˇ er Model simuluje v reálném ˇcase jev, kter´ y je v pˇr´ırodˇe realizován obrovsk´ ym mnoˇzstv´ım miniaturn´ıch p´ıseˇcn´ ych zrnek. Ta se pod vlivem komplexn´ıho proudˇen´ı vˇetru a dalˇs´ıch fyzikáln´ıch proces˚ u malého mˇeˇr´ıtka, pˇresunuj´ı bˇehem stovek let natolik organizovan´ ym zp˚ usobem, ˇze jsou schopna zformovat duny. Proto popis tohoto dˇeje nem˚ uˇze b´ yt pˇresnou kopi´ı proces˚ u odehrávaj´ıc´ıch se v pˇr´ırodˇe, ale je tˇreba popis znaˇcnˇe zjednoduˇsit, aniˇz by se vytratily charakteristické vlastnosti celého systému jako takového. Pˇresnˇe takov´ y pˇr´ıstup byl pouˇzit i v této diplomové práci. Zda byl hlavn´ı c´ıl, tedy simulace vzniku a v´ yvoje dun, dodrˇzen, záleˇz´ı na u ´hlu pohledu. Pokud budeme p´ıseˇcné duny chápat jako u ´tvary vznikaj´ıc´ı vlivem vˇetru v p´ıseˇcn´ ych oblastech se zˇretelnˇe rozliˇsenou návˇetrnou a závˇetrnou stranu, pak dodrˇzen byl. Podle mnoˇzstv´ı p´ısku zadaného pˇri inicializaci modelu, je tento schopen generovat jak osamocené duny Barchan, tak pole dun, kde jedna duna pˇrecház´ı plynule v druhou. Zaveden´ım dvou vˇetr˚ u jejichˇz smˇery jsou na sebe kolmé, vznikaj´ı symetrické lineárn´ı duny, cestuj´ıc´ı ve smˇeru v´ yslednice vektor˚ u obou vˇetr˚ u. Definován´ım ˇctyˇr vˇetr˚ u lze dosáhnout network dunes, tehdy je hlavn´ı mˇr´ıˇzka rozdˇelena do ˇcásteˇcnˇe se pˇrekr´ yvaj´ıc´ıch oblast´ı a v kaˇzdé z nich jsou duny vytvarovány trochu odliˇsn´ ym zp˚ usobem. Vzniku typické star dune se doc´ılit nepodaˇrilo, ale u ´tvary, u kter´ ych se sb´ıhaj´ı tˇri ramena v jeden centráln´ı uzel, bˇehem simulace také vznikaj´ı. V této diplomové práci byla dále implementována netriviáln´ı u ´loha, kterou je sniˇzovován´ı u ´rovnˇe detailu v závislosti na pozici pozorovatele. Na algoritmy tohoto typu obecnˇe jsou kladeny pomˇernˇe vysoké poˇzadavky, protoˇze mus´ı pracovat efektivnˇe ale zároveˇ n mus´ı b´ yt natolik jednoduché aby nebyly velkou v´ ypoˇcetn´ı zátˇeˇz´ı. Tento u ´kol se podaˇrilo splnit jen ˇcásteˇcnˇe, implementovan´ y algoritmus totiˇz znaˇcnˇe urychl´ y zobrazován´ı jen za cenu viditelného sn´ıˇzen´ı detailu.

53

Kapitola 9

N´ avrhy dalˇ s´ıho rozvoje t´ ematu Protoˇze je tato diplomová práce z oboru visualizace pomoc´ı poˇc´ıtaˇcové grafiky, dalˇs´ı kroky by se mˇely ub´ırat pˇridán´ım algoritm˚ u vykresluj´ıc´ıch wind-ripples neboli vˇetrné vlnky. T´ım zobrazovaná scéna z´ıská charakteristick´ y rys p´ıseˇcn´ ych oblast´ı. Jednou z moˇzn´ ych cest m˚ uˇze b´ yt i vyuˇzit´ı jiˇz naprogramovaného modelu a pomoc´ı vhodného nastaven´ı parametr˚ u vygenerovan´ı u ´tvar˚ u podobn´ ych vlnkám. Normálové vektory této druhé hlavn´ı mˇr´ıˇzky pak pouˇzijeme pro bump-mapping, stejnˇe jako je tomu v práci [3]. Dále je tˇreba provést podrobnˇejˇs´ı zkoumán´ı vlastnost´ı mˇr´ıˇzek tvoˇren´ ych pravideln´ ymi ˇsesti´ uheln´ıky. Hlavn´ım u ´ˇcelem tohoto studia by mˇelo dosaˇzen´ı optimáln´ıho zp˚ usobu indexace. Algoritmus je nyn´ı totiˇz ˇcásteˇcnˇe zpomalován t´ım, ˇze pˇri pˇresunu z jedné buˇ nky mˇr´ıˇzky do buˇ nky sousedn´ı je tˇreba znát hodnotu yi aktuáln´ı buˇ nky. Bohuˇzel, tuto hodnotu lze z indexu i do hlavn´ıho pole z´ıskat jen pomˇernˇe nároˇcnou operac´ı dˇelen´ı, kdy yi = i/xs . Jedn´ım z moˇzn´ ych ˇreˇsen´ı je pouˇzit´ı hlavn´ı mˇr´ıˇzky velikosti xs = 2k , pak lze operaci dˇelen´ı realizovat posunem bit˚ u v indexu i. Problém tohoto ˇreˇsen´ı se ale skr´ yvá v kombinaci s aktuálnˇe implementovan´ ym algoritmem LOD, pro kter´ y je rozmˇer mˇr´ıˇzky 2k naprosto nev´ yhodn´ y. Téˇz je moˇzno rozˇs´ıˇrit vlastnosti vˇetrného pole tak, aby ˇsla plynule mˇenit intenzita vˇetru a aby v´ıtr vanouc´ı pod u ´hlem r˚ uzn´ ym od násobku 60◦ nebyl zat´ıˇzen diskretizaˇcn´ı chybou. Rozˇs´ıˇren´ım vlastnost´ı vˇetrného pole by pak ˇslo kupˇr´ıkladu realizovat neerodovatelné pˇrekáˇzky ve scénˇe. Na druhou stranu je tˇreba m´ıt na pamˇeti, ˇze ˇc´ım sloˇzitˇejˇs´ı je definice vˇetrného pole, t´ım vzr˚ ustá sloˇzitost nejen v´ ypoˇctu vektoru pˇresunu ale také se t´ım komplikuje aktualizace hranic oblast´ı ve vˇetrném st´ınu. V´ ypoˇcet dynamick´ ych st´ın˚ u vrˇzen´ ych dunou na ostatn´ı duny je nyn´ı realizován velmi jednoduchou metodou. Ta je sice schopna pracovat v reálném ˇcase, ale je postavena ˇcistˇe na normálov´ ych vektorech jednotliv´ ych vrchol˚ u a st´ın takto tvoˇren´ y má pak zubaté okraje. Proto by bylo pro zlepˇsen´ı

54

visuáln´ıho dojmu vhodné, implementovat algoritmus zajiˇst’uj´ıc´ı pˇred hlavn´ım vykreslen´ım scény v´ ypoˇcty st´ın˚ u jinou, preciznˇejˇs´ı metodou.

55

Literatura [1] Momiji H., Carretero-González R., Bishop S.R. and Warren A. (2000) “Simulation of the effect of wind speedup in the formation of transverse dune fields”, Earth Surface Processes and Landforms 25, pp. 905–918. [2] Steven R. Bishop, Hiroshi Momiji, Ricardo Carretero-González and Andrew Warren. (2002) “Modelling Desert Dune Fields Based on Discrete Dynamics”, Discrete Dynamics in Nature and Society, Vol. 7 (1), pp. 7–17. [3] Koichi Onoue, Tomoyuki Nishita. (2000) “A Method for Modeling and Rendering Dunes with Wind-ripples”, In Proceedings of Pacific Graphics’00, pp. 427–428. [4] Hatano, Y., and Hatano D., (2001). “Dune Morphology and Sand Transport”. Forma, Vol. 16 (No. 1), pp. 65-75. [5] Benes, B., Roa, T. (2004) “Simulating Desert Scenery”, Proceedings of WSCG 2004, pp. 17-22. [6] Yizhaq, H., Balmforth N.J and Provenzale A., “An integro-differential model for the dynamics of aeolian sand ripples”. Proceedings of Sedimentation and Sediment-Transport At the crossroads of physics and engineering (2002). Monte Verita , Switzerland ( September 2002). [7] Adam Koh. (2002) “Dramatic Landscapes, Cellular Automata Modeling of Landscape Phenomena”, Bachelor thesis, School of Computer Science and Software Engineering Monash University. [8] Peter Lindstrom and Valerio Pascucci, “Visualization of large terrains made easy,” in IEEE Visualization 2001, Kenneth I. Joy, Amitabh Varshney, and Thomas Ertl, Eds., San Diego, California, Oct. 2001, pp. 363–370, IEEE. [9] Peter Lindstrom and Valerio Pascucci, “Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization” IEEE Transactions on Visualization and Computer Graphics, Volume 8, Issue 3, July-Sept. 2002 pp. 239-254. 56

[10] Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust, Gregory A. Turner, “Real-Time, Continuous Level of Detail Rendering of Height Fields” Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pp. 109-118, August 1996.

57

Dodatek A

Pˇ r´ılohy A.1

Podrobn´ y popis uˇ zivatelsk´ eho prostˇ red´ı

Zde jsou podrobnˇe vysvˇetleny a popsány jednotlivé poloˇzky hlavn´ıho menu, tedy nástroje urˇceného k ovládán´ı programu.

A.1.1

Run

• Run Blind Fluently 50000x on/off – Spust´ı simulaci aniˇz by prob´ıhalo zobrazován´ı modelu. Kaˇzd´ ych 50000 cykl˚ u pˇredá ˇr´ızen´ı GLUT za u ´ˇcelem oˇsetˇren´ı událost´ı. Smysluplné pouˇzit´ı této poloˇzky nastává v pˇr´ıpadˇe, kdyˇz maj´ı b´ yt ukládány v´ ysledky simulace v hlavn´ı mˇr´ıˇzce do aktivn´ıho souboru aniˇz by byl procesor zatˇeˇzován zobrazován´ım scény. • Run 1x on/off – Po kaˇzdém jednom cyklu je scéna znovu zobrazena. • Run Blind x – Tyto poloˇzky spust´ı bˇeh simulace aniˇz by byly jej´ı v´ ysledky pr˚ ubˇeˇznˇe zobrazovány a po x poˇctu cykl˚ u je simulace zastavena. • Run Fluently x on/off – Tyto poloˇzky spust´ı bˇeh simulace. Po kaˇzdém x poˇctu cykl˚ u se provede zobrazen´ı a simulace pokraˇcuje.

A.1.2

Camera positions

• Camera Left Bottom corner – Um´ıst´ı kameru do levého spodn´ıho rohu mˇr´ıˇzky. • Camera Center Bottom – Um´ıst´ı kameru do stˇredu spodn´ı hrany mˇr´ıˇzky. • Camera Right Bottom corner – Um´ıst´ı kameru do pravého spodn´ıho rohu mˇr´ıˇzky. • Camera Center Right – Um´ıst´ı kameru do stˇredu pravé hrany mˇr´ıˇzky. 58

• Camera Right Top corner – Um´ıst´ı kameru do horn´ıho pravého rohu mˇr´ıˇzky. • Camera Center Top – Um´ıst´ı kameru do stˇredu horn´ı hrany mˇr´ıˇzky. • Camera Left Top corner – Um´ıst´ı kameru do horn´ıho levého rohu mˇr´ıˇzky. • Camera Left Center – Um´ıst´ı kameru do stˇredu levé hrany mˇr´ıˇzky. • Higher position – Po aktivaci této poloˇzky a zvolen´ı nˇekteré z pˇredcházej´ıc´ıch je kamera um´ıstˇena v´ yˇse ale jinak do té samé polohy.

A.1.3

Visualization

• Hexes – Zobraz´ı scénu pomoc´ı kvádr˚ u s ˇsesti´ uheln´ıkovou podstavou. • Triangles – Zobraz´ı scénu pomoc´ı troj´ uheln´ık˚ u. • Wireframe / Solid – Zobraz´ı scénu drátˇen´ ym modelem / plochami. • Light on / off – Pˇrep´ınan´ı svˇetla ve scénˇe. • Light model Flat / Smooth – Pˇrep´ınan´ı typu st´ınován´ı. • LOD on / off – Pˇrep´ınaˇc pro LOD. • Textures of / off – Pˇrep´ınaˇc pro Texturován´ı. • Wind shadow on /off – Pˇrep´ınaˇc pro zobrazován´ı vˇetrného st´ınu. • Wind in on / off – Zobrazován´ı vˇetrného pole, singalizuje kter´ ym smˇerem z bunˇek vane v´ıtr. • Wind out on / off – Zobrazován´ı vˇetrného pole, singalizuje kter´ ym smˇerem do bunˇek vane v´ıtr. • Rotate around origin – Vypne / zapne pomalou rotaci kamery okolo stˇredu hlavn´ı mˇr´ıˇzky. • Land volume on/off – Pˇrep´ınaˇc pro zobrazován´ı kvádrového objemu okolo vlastn´ı mˇr´ıˇzky. • Land ironing 1 – Pˇrep´ınaˇc pro pr˚ umˇerován´ı hodnot hlavn´ı mˇr´ıˇzky pˇred zobrazen´ım, terén pak p˚ usob´ı plynuleji. Pr˚ umˇer je brán z ˇsestiokol´ı buˇ nky. • Land ironing 2 – Pˇrep´ınaˇc pro pr˚ umˇerován´ı hodnot hlavn´ı mˇr´ıˇzky pˇred zobrazen´ım, terén pak p˚ usob´ı plynuleji. Pr˚ umˇer je brán z osmnácti okol´ım buˇ nky. 59

• Shadows – Pˇrep´ınaˇc pro dynamické st´ıny. • LOD error – T´ımto podmenu se nastavuje maximáln´ı povolená chyba pro LOD.

A.1.4

Wind

• • Set wind direction to x – Nastav´ı u ´hel vˇetru na hodnotu x. • Set wind direction to + 15 degrees – Mˇen´ı u ´hel vˇetru o + 15◦ . • Set wind direction to - 15 degrees – Mˇen´ı u ´hel vˇetru o - 15◦ . • Set wind force to x – Nastav´ı parametr, L0 na hodnotu x. • Setting wind 1 – Zmˇeny u ´hlu a parametru L0 se projev´ı na vˇetru ˇc´ıslo 1. • Setting wind 2 – Zmˇeny u ´hlu a parametru L0 se projev´ı na vˇetru ˇc´ıslo 2. • Setting wind 3 – Zmˇeny u ´hlu a parametru L0 se projev´ı na vˇetru ˇc´ıslo 3. • Setting wind 4 – Zmˇeny u ´hlu a parametru L0 se projev´ı na vˇetru ˇc´ıslo 4. • Unidirectional wind regime – V modelu je pouˇzit pouze prvn´ı v´ıtr. • Bidirectional wind regime – V modelu stˇr´ıdá 1. a 2. v´ıtr. • Tridirectional wind regime – V modelu se stˇr´ıdaj´ı vˇetry ˇc´ıslo 1, 2 a 3. • Quaddirectional wind regime – V modelu se stˇr´ıdaj´ı vˇsechny vˇetry. • Wind change after x – Zmˇena aktuáln´ıho vˇetru se provád´ı kaˇzd´ ych x cykl˚ u.

A.1.5

Terrain

• Small size – Umˇele vloˇzen´ y tvar bude malé velikosti. • Medium size – Umˇele vloˇzen´ y tvar bude stˇredn´ı velikosti. • Large size – Umˇele vloˇzen´ y tvar zabere témˇeˇr pˇres celou mˇr´ıˇzku. • Hill – Vloˇz´ı do stˇredu hlavn´ı mˇr´ıˇzky parabolick´ y kopec. • Bowl – Uprostˇred hlavn´ı mˇr´ıˇzky vyhloub´ı parabolickou jámu. 60

• Sinus – Cel´ y terén je zvlnˇen pomoc´ı funkce sin. • Sinus Sinus – Cel´ y terén je zvlnˇen pomoc´ı funkce sin a m´ısto kde funkce dosahuje amplitudy je opˇet funkc´ı sin • Pyramid – Vloˇz´ı do stˇredu hlavn´ı mˇr´ıˇzky jehlan se sklonem stran 15◦ . • Pyramid steep – Vloˇz´ı do stˇredu hlavn´ı mˇr´ıˇzky jehlan se sklonem stran 33◦ . • a x a Flat – Vytvoˇr´ı novou hlavn´ı mˇr´ıˇzku, velikosti a x a.

A.1.6

Average height

• Inc height x – Pˇriˇcte k hodnotˇe kaˇzdé buˇ nky hlavn´ı mˇr´ıˇzky hodnotu x. • Dec height x – Sn´ıˇz´ı hodnotu kaˇzdé buˇ nky hlavn´ı mˇr´ıˇzky o x. ˇ ıslo x ukazuje pr˚ • Hieght value x – C´ umˇern´ y poˇcet sand slab v jedné buˇ nce mˇr´ıˇzky. Nejvˇetˇs´ı smysl má tento ukazatel pˇri inicializaci modelu, kdy je povrch dokonale ploch´ y a kdy tedy ukazuje pˇr´ımo mocnost p´ıseˇcné vrstvy.

A.1.7

Input / Output

• Save – Uloˇz´ı hlavn´ı mˇr´ıˇzku do aktivn´ıho souboru. • New active file, activate it – Vytvoˇr´ı nov´ y aktivn´ı soubor. • Animate active file – Postupnˇe zobraz´ı vˇsechny hlavn´ı mˇr´ıˇzky uloˇzené v aktivn´ım souboru. • Stop/Cont animation – Zastav´ y / nechá dále bˇeˇzet animaci hlavn´ıch mˇr´ıˇzek uloˇzen´ ych v aktivn´ım souboru. • Do not save – Vypne automatické ukládán´ı. • Save after x iterations – Automaticky uloˇz´ı kaˇzd´ ych x cykl˚ u hlavn´ı mˇr´ıˇzku. • Rotate camera after saving – Po kaˇzdém uloˇzen´ı otoˇc´ı kamerou kolem stˇredu hlavn´ı mˇr´ıˇzky. • Camera follow data – Pˇrep´ınaˇc, pokud je aktivn´ı, tak se po nahrán´ı hlavn´ı mˇr´ıˇzky kamera pˇresune do té samé pozice kde byla bˇehem ukládán´ı. • Save to BMP – Uloˇz´ı Color buffer do BMP souboru, soubory jsou ˇc´ıslovány od 1. 61

• Save every frame to BMP – Uloˇz´ı Color buffer do BMP souboru po kaˇzdém pˇrekreslen´ı obrazovky. BMP soubory jsou ˇc´ıslovány od 1.

62

Fakulta elektrotechnická. Martin Fousek. Studijní program: Informatika a výpočetní technika

Recommend Documents