Rekonstrukce terénu z vrstevnicových dat

eské vysoké uení technické v Praze Fakulta elektrotechnická

Bakaláská práce

Rekonstrukce terénu z vrstevnicových dat Radek Bien

Vedoucí práce:Ing. Jaroslav Kivánek, Ph.D.

Studijní program:Elektrotechnika a informatika, strukturovaný, bakaláský Obor:Informatika a výpoetní technika kvten 2008

-I-

-II-

Pod
kování Chtl bych podkovat panu Ing. Jaroslavu Kivánkovi, Ph.D., vedoucímu práce, za odborné vedení, cenné rady a poskytnutí asu pi konzultacích.

-III-

-IV-

Prohlášení Prohlašuji, že jsem svou bakaláskou práci vypracoval samostatn a použil jsem pouze podklady uvedené v piloženém seznamu. Nemám závažný dvod proti užití tohoto školního díla ve smyslu §60 Zákona . 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zmn nkterých zákon (autorskýzákon). V Praze dne 5.6.2008

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

-V-

-VI-

Abstract: This work deals with three-dimensional terrain model generation from vector contour data. It compares various methods for terrain reconstruction anddescribes implementation ofthe algorithm that generates 3D model. The work also contains results ofthe terrain reconstruction from topographic maps usedin GPS navigation andresults ofterrain reconstruction for the purpose ofarcheology.

Abstrakt: Tato práce se zabývá tvorbou prostorového modelu krajiny z vektorových vrstevnicových dat. Práce porovnává rzné metody rekonstrukce terénu a popisuje implementaci algoritmu generující 3D model pro další použití. Práce také obsahuje výsledky rekonstrukce terénu z topografických map užívaných v GPS navigaci a výsledky rekonstrukce terénu pro úely archeologie

-VII-

-VIII-

Obsah Seznam obrázk
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .XIII Seznam tabulek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .XIII 1

Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.1 M otivace ................................................................................................................ 1 1.2 Vrstevnice .............................................................................................................. 1 1.3 Omezení vrstevnic ................................................................................................. 2 1.4 2.5D model terénu. ................................................................................................ 2 1.5 Zámr práce ........................................................................................................... 3

2

M etody tvorby virtuálního terénu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 2.1 Datové struktury .................................................................................................... 5 2.2 Hrubýmodel terénu ............................................................................................... 5 2.3 Terén generovanýna základ vstupních dat.......................................................... 5 2.3.1 Aproximaní algoritmus 1 ............................................................................. 6 2.3.2 Aproximaní algoritmus 2 ............................................................................. 6 2.3.3 M inimum curvature a Krigování ................................................................... 6 2.3.4 Užití metody nejmenších tverc .................................................................. 7 2.3.5 Contour Interpolation andSurface Reconstruction ofSmooth Terrain......... 7 2.3.6 Shape Reconstruction from Contours usingIsotopic Deformation............... 8 2.3.7 Terrain Reconstruction from Contours by Skeleton Construction ................ 9 2.3.8 C1 continuous Terrain Reconstruction from Sparse Contours..................... 11

3

Teoretický rozbor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 3.1 Výbr algoritmu................................................................................................... 13 3.2 Úpravy algoritmu................................................................................................. 13 3.3 Popis algoritmu.................................................................................................... 14 3.3.1 Vstupní data ................................................................................................. 14 3.3.2 Úprava vrstevnic.......................................................................................... 15 3.3.3 Triangulace .................................................................................................. 15 3.3.4 Hledání nových bod vrstevnic ................................................................... 16 3.3.5 Hledání nejbližších bod vrstevnic.............................................................. 16 3.3.6 Výpoet svah ............................................................................................. 17 3.3.7 Výpoet výšek ............................................................................................. 18 3.3.8 Vyhlazení chyb............................................................................................ 19 3.3.9 Výpoet normál ........................................................................................... 19 3.4 Vstupy.................................................................................................................. 20 3.4.1 Specifikace vstupu ....................................................................................... 20 3.4.2 Vstup ze souboru s kartézskými souadnicemi............................................ 20 3.4.3 Vstup ze souboru Polish formátu GPS map ................................................ 20 3.5 Výstupy................................................................................................................ 21 3.5.1 Specifikace výstupu ..................................................................................... 21 3.5.2 Výstup pomocí VRM L................................................................................ 21

4

Realizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 4.1 Analýza ................................................................................................................ 23

-IX-

4.1.1 Návrhová tída Point2D a PointS.................................................................23 4.1.2 Návrhová tída Contour................................................................................24 4.1.3 Návrhová tída M ap .....................................................................................24 4.1.4 Návrhové tídy Point3D a Vector3D a Triangle ..........................................24 4.1.5 Návrhová tída M odel ..................................................................................24 4.1.6 Postup algoritmu ..........................................................................................25 4.2 Použité knihovny a funkce ...................................................................................26 4.2.1 STL –Standardtemplate library ..................................................................26 4.2.2 OpenGL........................................................................................................26 4.2.3 GLUT ...........................................................................................................26 4.2.4 CGAL...........................................................................................................27 4.2.5 CDT objekt...................................................................................................27 4.2.6 Funkce refine_Delaunay_mesh_2() .............................................................27 4.3 Implementace vizualizaního prostedí................................................................27 4.4 Implementace tíd.................................................................................................28 4.4.1 Tída Point2D a PointS................................................................................28 4.4.2 Tída Contour ...............................................................................................29 4.4.3 Tídy Point3D, Vector3D a Triangle ...........................................................30 4.4.4 Tída M odel..................................................................................................30 4.4.5 Tída M ap.....................................................................................................31 4.5 Implementace krok algoritmu ............................................................................32 4.5.1 Natení vrstevnic..........................................................................................32 4.5.2 Úprava Vrstevnic .........................................................................................33 4.5.3 Triangulace...................................................................................................33 4.5.4 Hledání nových bod vrstevnic....................................................................33 4.5.5 Hledání nejbližších bod vrstevnic ..............................................................34 4.5.6 Výpoet svah a výšek.................................................................................34 4.5.7 Vyhlazení chyb.............................................................................................34 4.5.8 Výpoet normál ............................................................................................35 4.5.9 Tvorba modelu .............................................................................................35 5

Testování. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.1 Testované M apy ...................................................................................................37 5.1.1 M ount St. Helens..........................................................................................37 5.1.2 Svržno ..........................................................................................................37 5.1.3 Hostnice......................................................................................................37 5.1.4 HrubýJeseník...............................................................................................37 5.1.5 Dlouhé Strán...............................................................................................37 5.1.6 Orlické Hory.................................................................................................37 5.1.7 Pec podSnžkou ..........................................................................................37 5.2 Parametry testování ..............................................................................................38 5.3 Výsledky ..............................................................................................................38 5.4 Ukázky rekonstrukcí. ...........................................................................................40 5.4.1 M ount St. Helens..........................................................................................40 5.4.2 Hosttice.......................................................................................................41 5.4.3 Svržno ..........................................................................................................41 5.4.4 HrubýJeseník...............................................................................................42 5.4.5 Dlouhé Strán...............................................................................................43 5.4.6 Orlické Hory.................................................................................................43

-X-

5.4.7

Pec PodSnžkou.......................................................................................... 43

6

Závr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47 6.1 Zhodnocení .......................................................................................................... 47 6.2 Další práce ........................................................................................................... 47

7

Použitáliteratura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49

A –Seznam zkratek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51 B –Uživatelskápíruka. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53 C –Obsah CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55

-XI-

-XII-

Seznam obrázk Obr. 1. Obr. 2. Obr. 3. Obr. 4. Obr. 5. Obr. 6. Obr. 7. Obr. 8. Obr. 9. Obr. 10. Obr. 11. Obr. 12. Obr. 13. Obr. 14. Obr. 15. Obr. 16. Obr. 17. Obr. 18. Obr. 19. Obr. 20. Obr. 21. Obr. 22. Obr. 23. Obr. 24. Obr. 25.

Píkladtopografické mapy..................................................................................... 1 vrstevnice a popis terénu pomocí vrstevnic........................................................... 2 Píklad2.5D povrchu (a) a obecného 3D povrchu (b). ......................................... 3 výpoet výšky ze dvou prmrných výšek............................................................ 6 M etoda nejmenších tverc ................................................................................... 7 Ukázka ovlivnní terénu smrnicí svahu............................................................... 8 Eliminace trojúhelník........................................................................................... 9 Tvorba skeletonu ................................................................................................. 10 Výpoet výšky bod skeletonu............................................................................ 10 Rozdlení rekonstruovaného terénu na oblasti. ................................................... 11 Výpoet svahu na vrstevnici c1. .......................................................................... 12 UCF prohledávání................................................................................................ 17 Extrapolace bodu z okolních vrstevnic................................................................ 19 Návrhové tídy ..................................................................................................... 23 Postup algoritmu.................................................................................................. 25 M etody reduceM ap() a thickM ap(). .................................................................... 29 M ount St.Helens .................................................................................................. 40 Hostetice .............................................................................................................. 41 Svržno .................................................................................................................. 42 Rekonstrukce sedla mezi dvma vrcholy ............................................................ 42 chyby na povrchu terénu...................................................................................... 43 HrubýJeseník (celkovýpohled) .......................................................................... 43 Dlouhé Strán ...................................................................................................... 44 Orlické Hory. ....................................................................................................... 44 Pec podSnžkou.................................................................................................. 45

Seznam tabulek Tab. 1. Tab. 2. Tab. 3. Tab. 4. Tab. 5. Tab. 6.

Implementace krok algoritmu............................................................................ 14 Postup algoritmu z hlediska analýzy ................................................................... 25 Postup algoritmu z hlediska implementace ......................................................... 32 Vstupní data. ........................................................................................................ 39 Doba výpotu pi triangulaci metodou generateM esh(). ..................................... 39 Doba výpotu pi triangulaci metodou genSparseM esh(). .................................. 39

-XIII-

-XIV-

1 Úvod Úvodní kapitola je seznámení se základními poj my. Jsou zde popsány topologické vrstevnice jako prostedek pro zobrazení terénu. Vrstevnice mají také nkterá omezení, které jsou zmínna dále a jež vedou na tvorbu specifických 2.5D model. V závru jsou shrnuty cíle práce. 1.1 Motivace M odelování virtuálních terén v poítaové grafice má dlouhou historii. A už se jedná o náhodné terény, nebo o generování model z reálných dat, jsou dležité v mnoha oblastech. Nejpodstatnjší z nich v souasné dob jsou pravdpodobn letecké simulátory a poítaové hry. Další dležitou oblastí, kde se uplatují modely reálných terén jsou Geografické informaní systémy- takzvané GIS. Geografické informaní systémy jsou poítaové informaní systémy pro získávání, ukládání, analýzu a vizualizaci dat. V souasné dob se stávají velice populární zejména 3D vizualizace mst –takzvané virtuální procházky mstem. Tvrcm takovýchto aplikací mže algoritmus, generující povrch automaticky usnadnit práci. Podobn prospšnýmže být algoritmus napíkladarcheologm pi vizualizaci pravkých a starovkých sídliš. 1.2 Vrstevnice Nejrozšíenjším zpsobem popisu ástí zemského povrchu jsou v souasné dob mapy. M ohou popisovat katastrální, sociální i geologické lenní. Nejpoužívanjší mapy jsou však mapy topografické. Topografie je nauka o tvarech a zákonitostech zobrazení terénu. Topografické mapy popisují jak pírodní prvky (hory, údolí, eky, lesy...), tak i díla vytvoená lidskou rukou (msta, vesnice, cesty, umlé kanály...) (viz Obr. 1). První topografické mapy vznikaly již v druhé polovin 18. století ve Francii.

Obr. 1. Píkladtopografické mapy. (zdroj:http://geoportal.cenia.cz )

-1-

K popisu terénu jsou používány tzv. vrstevnice (Obr. 2). Vrstevnice je definována jako kivka, spojující na map body se stejnou nadmoskou výškou. Jedná se tedy o izoáru. V globálním pohledu, v rámci celé zemkoule, jsou kivky uzavené. V rámci map, zobrazujících pouze malé územní celky toto vtšinou neplatí a kivky jsou otevené. Popis tvaru terénu mže být dále obohacen o doplující prostedky, jako jsou napíklad spádnice, kóty, šrafy, údolnice a hbetnice. Tyto prostedky se však, s výjimkou kót, píliš nepoužívají.

Obr. 2.

Vrstevnice a popis terénu pomocí vrstevnic. (zdroj:www.wikipedia.cz)

Lidskýmozek je schopnýz pouhých vrstevnic vytvoit hrubýmodel terénu. Pro lepší pedstavu musí však být pro zobrazení použita výpoetní technika. 1.3 Om ezení vrstevnic Samotné topografické vrstevnice nedokážou popsat terén zcela dokonale. Jak jižbylo eeno, vrstevnice jsou kivky, jimž je piazena výška. Tyto kivky se také nesmjí vzájemn protínat. (Na nkterých mapách soubh nkolika vrstevnic v jednu oznauje útes. Vtšinou je však pro útesy a skály použita speciální znaka.) Toto omezení zaruuje, že každému bodu mapy mže být výška piazena jednoznan. Povrch terénu tak mžeme považovat za skalární funkci dvou promnných: (1.1) h = f ( x, y ) Z uvedeného je zejmé, že pomocí vrstevnic není možné modelovat nkteré krajinné prvky, jako napíkladpevisy, útesy, jeskyn i sloupcové skály.

1.4 2.5D m odelterénu. Pro trojrozmrné modely terén, jejichžpovrch vyhovuje rovnici 1.1, se v poítaové grafice, používá oznaení 2.5D model ([1]). Obecné metody modelování 3D povrchu z vrstevnic (lépe eeno z ez) se používají zejména pi zobrazování medicínských dat. Algoritmem tvoícím 3D povrchy je nap. „Marching Cubes“ zmiovaný v [1]. Jeho principem je vytvoení pravoúhlé prostorové mížky nad získanými daty, jejížbody tvoí vrcholy krychle. Hledaný povrch se zkoumá vždy pouze v jediné krychli, lineární

-2-

interpolací hodnot ve vrcholech. M etoda má také své nevýhody, nebo tvoí velmi hustou sí trojúhelník. Další metody tvorby 3D terénu jsou nap. v [15]a [16]. M y se nadále budeme zabývat pouze 2.5D modely, které na terén vtšinou postaují. Tí dimenzionální (2.5D) model terénu z mapy vzniká tak, že každému bodu, urenému dvma souadnicemi, je piazena výška. Body každé mapy mžeme rozdlit do dvou skupin:ležící na vrstevnicích a mimo vrstevnice. Výška bod vrstevnic je známa. U ostatních, je nutné tento údajvypoítat nebo odhadnout. M etod, jak odhadnout i vypoítat neznámou hodnotu výšky je mnoho. Nkteré z metod generování virtuálních krajin jsou popsány ve 2. kapitole. 1.5 Zám
rpráce Cílem práce je nalézt a naimplementovat algoritmus, který z dat popisujících vrstevnice ve výezu mapy reálného terénu, vytvoí digitální model. Algoritmus musí pracovat efektivn a vytváet spojité povrchy bez zásadních poruch hladkosti. Výstupní model musí být nejen zobrazitelný, ale také dále použitelnýjako datová struktura. Dalším požadavkem je možnost uložit model v nkterém standardním grafickém formátu. Jako základní algoritmus byla zvolena metoda popsaná v lánku [6], která byla rozšíena o možnost použití neuzavených vrstevnic. Toho bylo docíleno nahrazením nkterých ástí inteligentními prohledávacími algoritmy. Byla doplnna ást algoritmu pro hledání nových bod vrstevnic a vytvoena byla také metoda pro rekonstrukci terénu z dat, která porušují pravidla pro vstupní data algoritmu uvedeného v [6].

(a) Obr. 3.

(b) Píklad2.5D povrchu (a) a obecného 3D povrchu (b). (zdroj:[15])

-3-

-4-

2 Metody tvorby virtuálního terénu Tato kapitola je pehledem používaných metod tvorby virtuálních terén. Nejprve jsou diskutovány datové struktury užívané pro reprezentaci povrchu krajiny v pamti poítae. Další odstavec se zabývá získáváním hrubého modelu. Následuje pehled algoritm užívaných pro generování povrch krajin z vrstevnicových dat. 2.1 Datové struktury Základní datovou strukturou pro tvorbu 2.5D povrchu je výšková mapa. Výšková mapa je sí tverc i obdélník (regular grid), asto reprezentovaná dvourozmrným polem (maticí), v nmžj sou uloženy hodnoty výšek píslušných bod. Tato struktura však mže být pamov neúsporná, proto se pi zobrazení asto pevádí na trojúhelníky. Další, velmi astou reprezentací povrchu, jsou trojúhelníkové sít. Trojúhelníkové sít mohou mít pravidelnou topologii, které se pamovou nároností ovšem pílišneliší od sít tvercové. Proto se astji používají nepravidelné trojúhelníkové sít (TIN).Tyto jsou rychle a snadno zobrazitelné a pi vhodné volb sít mohou být pamov úspornjší. Nepravidelná sí trojúhelník (TIN) bude nadále preferovaná pi hledání vhodného algoritmu. 2.2 Hrubý m odelterénu Tvorbu virtuální krajiny mžeme rozdlit do dvou základních fází:tvorba hrubého modelu a jeho úprava. Hrubý model je popis krajiny, poskytující základní pedstavu o tvarových vlastnostech modelovaného povrchu. Hrubý model mže být generován zcela náhodn. K tomu se nejastji používají Metoda náhodného p
esouváníst
edního bodu a Metoda náhodných poruch. Ob metody vycházejí ze studia Brownova pohybu a fraktální geometrie (viz [1]). Takto získanýhrubý model je poté asto upravován tzv. Erozními algoritmy. Náhodné modely terénu ovšem nepopisují reálné terény (pouze reáln vypadající). Proto mají daleko vtší význam modely, které vycházejí z reálných vstupních dat. Vstupními daty mohou být vrstevnice, spádnice i náhodn odebrané vzorky bod. Samotná vstupní data získaná vzorkováním reálné krajiny mžeme považovat za hrubý model. Fází úpravy hrubého modelu získaného na základ vstupních dat se zabývá následující kapitola, v nížse zamíme pouze na terén generovanýz vrstevnic. Fáze úpravy spoívá v mapování dat do píslušné datové struktury a dopotu výšek dalších bod povrchu krajiny. 2.3 Terén generovaný na základ
vstupních dat Krajina mže být generována aproximaními metodami, kdy vrstevnice urují pouze pibližný tvar a ve výsledném modelu nemusí ležet pímo na povrchu, ale vtšinou leží v tsné blízkosti. Lepší variantou jsou metody užívající interpolace. Tyto metody zachovávají body vrstevnic na povrchu generovaného terénu. Lze je asto považovat za

-5-

interpolan- extrapolaní; K výpotu bodu ležícího mezi dvma vrstevnicemi rzných výšek je užita interpolace vhodnou funkcí, s hraniními podmínkami urenými výškami sousedních vrstevnic. Výšky bod umístných uvnit uzavené vrstevnice (vrcholy, hebeny, údolí, prohlubn) jsou pak vypoítávány extrapolací z okolních bod. 2. 3. 1 Aproximaníalgoritmus 1 M ichal
ernohorský ve své práci [11] použil algoritmus, který vrstevnice aproximuje. Pro reprezentaci terénu používá pravidelné obdélníkové sít (regulargrid) o rozmrech 256 × 256 bod. Algoritmus naítá body lomené áry (anglicky polyline) urujících vrstevnice a mapuje je do rozmr obdélníkové sít. Pírstkovým algoritmem jsou v rastru sít doplnny ostatní body ležící na píslušných úsekách polyline. Po natení všech vrstevnic, je všem bodm sít, které ji dosudnemají stanovenou, piazena výška nejbližšího souseda. Vzniká tak terasovitý terén, který je dále upravován prmrováním každého bodu s body sousedními. Hladkost terénu je urena prmrovacím koeficientem. Algoritmus pracuje velmi rychle. Prmrováním dochází ke zkreslení, zejména v místech úzkých údolí, i heben. Pesto poskytuje uživateli pomrn dobrý obraz o lenitosti daného terénu. 2. 3. 2 Aproximaníalgoritmus 2 Obdobný algoritmus k uvedenému ve 2.3.1 nabízí také lánek [10]. Každým bodem tvercové sít prochází tyi polopímky (urené hranami incidujících tverc). Na tchto polopímkách se hledají nejbližší body, v kterých protínají vrstevnice. Takto mohou být nalezeny až 4 body. Z dvojic protilehlých jsou vypoítány dva vážené prmry. Vtší z tchto hodnot výšky je použit pro stanovení výšky hledaného místa (viz Obr. 4). Získaný terén je opt upravován prmrováním. Hy − By ( Ah − Bh) + Bh Ay − By Hx − Cx h2 = ( Dh − Ch) + Ch Dx − Cx Hh = max(h1, h 2)

h1 =

Obr. 4.

výpoet výšky ze dvou prmrných výšek (zdroj[10])

2. 3. 3 M inimum curvature a Krigování V omezené míe je možné pro modelování terénu použít také metody zmínné ve lánku [7].
lánek se zabývá zejména zobrazováním geofyzických dat, konkrétn pak anomáliemi gravitaního pole. Obsažené metody rekonstrukce povrchu z namených dat mohou mít ovšem širší využití.

-6-

M etoda M inimum curvature je vlastn zpsob vyrovnávání modelované plochy. Plocha je namenými body proložena tak, aby obsahovala co nejmén záhyb. Algoritmus pracuje iteran a má interpolaní charakter. Krigování(krigging) lze oznait za metodu píspvkovou. Výška hledaného bodu je získána jako váženýsouet hodnot nejbližších známých bod. Váhy musí být zvoleny, aby minimalizovaly chybu krigování. Dané váhy lze urit za pomocí tzv. semivariogram ([7]). 2. 3. 4 Užitímetody nejmenších tverc
Pro hledání výšky bod mže být také využita metoda nejmenších tverc (viz [17]). M etoda umožuje nalézt funkci, která aproximuj e zadanou množinu bod tak, že souet druhých mocnin vzdáleností bod odtéto funkce je minimální. V našem pípad je aproximuj ící funkcí rovina. M nožinu bod tvoí pedem stanovený poet nejbližších bod, jejichž výška je známa (tedy bod vrstevnic). Touto množinou je poté proložena rovina, od nížje souet tverc vzdáleností ke všem bodm množiny nejmenší. Hledaný bod je poté na tuto rovinu promítnut a tím je získána jeho výška. Poet nejbližších bod musí být vhodn zvolen, aby nedocházelo k znehodnocení lokální aproximaní funkce. Algoritmus aplikovaný na povrch definovaný vrstevnicemi vrací dobré výsledky, pokud jsou vrstevnice dostaten oblé. V místech, kde vrstevnice formují svažuj ící se brázdu vznikají patrné schody. Ty jsou zpsobeny pílišným zastoupením bod stejné výšky v množin. 4 3 2 1 0 0

2

4

6

8

Obr. 5. M etoda nejmenších tverc - proložení bod p0, p1 a p2 lineární funkcí p.

Daleko zajímavjší, než obecné metody generování povrch jsou algoritmy specializované pímo na rekonstrukci krajin. K nim patí také následující tyi metody: 2. 3. 5 Contour Interpolation and Surface Reconstruction ofSmooth Terrain
lánek [8]se zabývá rekonstrukcí terénu z vrstevnic. Algoritmus v nm uvedený zaruuje C1 spojitost povrchu. K dosažení hladkosti terénu je užit výpoet parciální diferenciální rovnice druhého ádu. Je zde oddlena interpolace (výpoet výšky bod mezi dvma vrstevnicemi) odextrapolace (výpoet vrchol, prohlubní, heben). Extrapolaci se lánek nevnuje vbec.

-7-

V lánku je poukázáno na analogii mezi 2D elektrickým polem a krajinou, kde izoáry elektrického potenciálu odpovídají vrstevnicím a stejn jako izoáry jsou kolmé na indukní siloáry, jsou vrstevnice kolmé na svážnice. Pro vrstevnice tak platí stejná omezení jako pro izoáry potenciálu:Nesmjí se vzájemn protínat a výška bodu mezi dvma vrstevnicemi roste pravideln pouze v omezeném intervalu. To jsou podmínky pro generování 2.5D terénu. Na vstupu pijímá algoritmus data popisující vrstevnice - jejich pozici, výšku a také smrnici svahu. Smrnice svahu nemusí být zadána. Poté je ovšem dosazena implicitní hodnota. Výstupem algoritmu je sada trojúhelníkových segment. Každý segment reprezentuje prostor mezi dvma vrstevnicemi. Po natení vstupních dat dochází k triangulaci a následnému zjemnní trojúhelník na požadovanou velikost. Pokud nebyly stanoveny smrnice svahu na vrstevnicích, jsou vypoítány prmrováním ze vzdáleností a výšek nejbližších bod jiných vrstevnic. Nyní nastupuje iteraní ást, v nížjsou nalezeny všechny spádnice –kivky spojující každýbod vrstevnice s nejbližším bodem protjší vrstevnice. Na základ tchto ideálních spádnic a jejich prniku do každého trojúhelníku (v horizontálním smru) je pepoítávána výška a lokální modifikaní parametr, kterýuruje možnou velikost zmny v dané iteraci. Iteraní ást se zastavuje v okamžik, kdy se vypoítaný povrch ve všech místech piblíží k ideálnímu na vzdálenost menší, nežje urená chybová tolerance. Autoi tohoto algoritmu sice zaruují C1 spojitost. Použitýiteraní princip mže být ovšem asov neefektivní. V lánku také není komentován problém extrapolace vrchol a údolí.

Obr. 6.

Ukázka ovlivnní terénu smrnicí svahu

2. 3. 6 Shape Reconstruction from Contours usingIsotopic Deformation
lánek [13]se nezabývá kompletní rekonstrukcí terénu. Vnuje se pouze zpsobu urení výšky bod ležících mezi dvma vrstevnicemi. K tomuto je zde použit djnazvaný izotopická deformace. M etoda využívá omezené Delaunayovy triangulace (constrained Delaunay triangulation), ale jako výstupní formát je použita tvercová míž. Algoritmus na vstupu dostane popis vrstevnic. Pro práci tohoto algoritmu je nutné, aby vrstevnice byly uzavené kivky vhnízdné uvnit sebe. Souástí vstupu je také urení korespondence alespo nkterých zásadních bod na jedné vrstevnici s body druhé vrstevnice. Tyto vztahy poté ídí izotopickou deformaci. V kontextu tohoto lánku je izotopickou deformací myšlena skutenost, že pechod mezi vnjší a vnitní vrstevnicí je ve všech smrech rovnomrný. M žeme si pedstavit, že

-8-

vnjší vrstevnice se postupn smrskává a tím se pibližuje k vnitní. Tímto zpsobem lze tedy vytvoit mnoho nových vrstevnic ležících mezi dvma pvodními. Izotopická deformace je zde simulována za pomocí omezené Delaunayovy triangulace. Zásadní zlomové body jsou triangulovány. Následuje eliminace trojúhelník, probíhající podle následujících pravidel (viz Obr. 7): 1. Hrana PiPi+1 trojúhelníku leží na vnjší vrstevnici. Zbylý bod Qj leží na vnitní vrstevnici. Bod K ležící na hran PiPi+1 je promítnut na bod Qj. Ostatní body z úseky PiK (respektive KPi+1) jsou promítnuty na úseky PiQj (respektive QjPi+1). 2. BodPi+2 je promítnut na bodL. Body z úseky Pi+1Pi+2 (respektive Pi+2Pi+3) j sou promítnuty na úseku Pi+1L (respektive LPi+3). V souladu s obma pravidly musí být pepoítána také výška daných bod. Ta je urena lineární interpolací. Postupným promítáním bod smrem k vnitní vrstevnici mže v nkterých místech vznikat pílišná hustota tchto bod. V posledním kroku jsou proto nkteré odstranny.

Obr. 7. Eliminace trojúhelník - náznak eliminace podle pravidel 1 a 2 (zdroj:[13])

Dále je komentován problém vtvení terénu - kdy uprosted jedné vrstevnice se nachází více nežjedna vnitní vrstevnice a je tedy nutné formovat sedlo mezi více vrcholy. V tomto pípad je pro každý vrchol spuštn algoritmus zvláš a výsledky jsou nakonec spojeny prmrem.
lánek pináší zajímavou myšlenku izotopické deformace vrstevnic. Nevhodn ovšem používá pro výpoet výšky lineární interpolaci. Pi rekonstrukci kompletního terénu toto bude znamenat zlomy na povrchu v míst vrstevnic. Znan omezující je také nutnost použití pouze uzavených a vhnízdných vrstevnic. 2. 3. 7 Terrain Reconstruction from Contours by Skeleton Construction
lánek [9]se zabývá rekonstrukcí terénu za pomocí konstrukce Skeletonu, nebo-li jádra. Algoritmus je postaven na metodách tvorby Voronoiova diagramu a k nmu duální Delaunayovy triangulace. V úvodní ásti se lánek zabývá možnostmi extrakce kivek ze zadaných bod za pomocí konstrukce Voronoiova diagramu. V druhé ásti se vnuje pevážn tvorb skeletonu. Skeleton vzniká také za pomocí konstrukce Voronoiova diagramu, který je sestrojen nad množinou bod definujících

-9-

polyline vrstevnic. Každá Voronoiova hrana, která neprotíná žádnou z hran pvodních kivek (vrstevnic) se stává hranou vznikajícího skeletonu. Skeleton se mže znan vtvit, proto jsou nkteré vtve zrušeny.

a)

b) c) Obr. 8. Tvorba skeletonu a) tvorba skeletonu z Voronoiových hran.; b) ukázka skeletonu na j avorovém listu; c) aplikace skeletonu na vrstevnice (zdroj:[9])

Body skeletonu netvoí jedinou kivku jako vrstevnice a díky vtvení mohou mít rznou výšku. Výška je vypoítávána za pomoci polomr kružnic. Body skeletonu (Voronoiovy body) jsou vlastn stedy kružnic, jejichž polomr je uren vzdáleností k nejbližšímu bodu na vrstevnici. Protože je Voronoiv diagram jižvytvoen, není nároné tyto hodnoty získávat. Pro každou kružnici se zkoumá, jestli na jejím obvodu leží body ze dvou vrstevnic. Pokud ano, je výška tohoto bodu nastavena na prmrnou hodnotu výšek obou vrstevnic (Protože je vzdálenost k obma vrstevnicím stejná, jde o lineární interpolaci.). Pokud na kružnici leží body pouze z jedné vrstevnice, znamená to, že sted kružnice leží na njaké vtvi. Postupuje se tedy po vtvi a hledá se sted kružnice, která protíná ob vrstevnice. Na základ pomru prmr tchto dvou kružnic je vypoítána výška píslušného bodu podle vzorce: ( Ri / Rr) ⋅ ( Zc − Zb) , Zi = Zc − (2.4) 2 kde Zc je výška vyšší vrstevnice, Zb výška nižší vrstevnice, Ri - polomr kružnice v hledaném bodu a Rrje polomr kružnice protínající dv vrstevnice (viz Obr. 9).

Obr. 9.

Výpoet výšky bod skeletonu

Po urení všech výšek zbývá vytvoit triangulaci daných bod. Triangulovány jsou body pvodní (generující Voronoiv diagram) i Voronoiovy.

-10-


lánek popisuje zajímavou aplikaci Voronoiova diagramu na konstrukci virtuální krajiny. Krom bod skeletonu nejsou však již použity v modelu žádné jiné body, což mže být nepíjemné, pokudbudou vrstevnice daleko odsebe. Nevýhodou je také lineární interpolace, která na vrstevnicích mže zaruit pouze spojitost C0. 2. 3. 8 C1 continuous Terrain Reconstruction from Sparse Contours
lánek [6]uvádí efektivní metodu rekonstrukce terénu pomocí lineární i hermitovské interpolace vrstevnic. Algoritmus zaruuje C1 spojitost terénu ve všech bodech (v pípad hermitovské interpolace) s výjimkou údolí vrchol a heben (místa kde je výška extrapolována). Algoritmus využívá pro tvorbu modelu trojúhelníkové sít vzniklé pomocí omezené Delaunyovy triangulace (Constrained Delaunay Triangulation). Základní ideou uvádné metody je redukce dvourozmrného (dvoupromnného) problému rekonstrukce terénu na jednopromnnou interpolaní kivku. Podstata tohoto spoívá ve skutenosti, že nejkratší cestou jak vystoupit z jedné výšky do druhé (i sestoupit) je sledovat svážnici, která je kolmá na vrstevnice. Pi hledání nejbližšího bodu na vrstevnici je úseka spojující naši polohu s nalezeným bodem na píslušnou vrstevnici také kolmá. V malém okolí naší pozice tedy tato úseka aproximuje svážnici. Na vstupu algoritmus oekává n vrstevnic, které se nesmjí protínat a jsou vždy uzavené. Vrstevnice tak rozdlí horizontální rovinu na n+1 oblastí blast 0 obklopuje všechny vrstevnice. Tato oblast se nerekonstruuje. Pro ostatní i platí, že jsou z vnjšku ohranieny práv jednou vrstevnicí. Podle potu k vnitních hraniních vrstevnic lze odhadnout, jak se bude daná oblast rekonstruovat:pi k = 0 bude oblast rekonstruována jako vrchol nebo prohlube; pi k = 1; bude oblast rekonstruována jako svah; pi k > 1; oblast bude obsahovat nejmén k-1 sedel. Rozdlení do oblastí je naznaené na Obr. 10.

Obr. 10. Rozdlení rekonstruovaného terénu na oblasti. c1, c2, c3, c4, c5 :vrstevnice; 0 –vnjší oblast; 1 oblast s 2 vnitními vrstevnicemi –rekonstrukce sedla; 2, 4 oblasti s jednou vnitní vrstevnicí –rekonstrukce svahu; 3, 5 –oblast bez vnitních vrstevnic –rekonstrukce lokálního extrému (zdroj:[6])

Po uspoádání vrstevnic a oblastí pichází na adu triangulace. Ta mže být provedena pro každou oblast zvláš (poté je ihnedzejmé, do jaké oblasti kterýbodpatí), nebo mže být provedena jedna globální triangulace (pak je body nutné rozdlit do správných oblastí). Nyní je teba pro každý bod nalézt nejbližší body na vnjší a vnitní

-11-

hranici dané oblasti. Po této ásti je jižmožné rekonstruovat terén lineární interpolací. Pro použití hermitovské interpolace je poteba ješt znát smrnici svahu (tj. první derivaci interpolující plochy) na vrstevnici. Každá vrstevnice mže být hranice dvou oblastí a každá z tchto oblastí pispívá svým lineárním svahem. Jsou tak definovány horní a dolní svah. Horní svah pro danýbodje možno nalézt hledáním nejbližšího bodu ležícího na vrstevnici s vtší výškou. Naopak dolní svah je možno najít hledáním nejbližšího bodu z vrstevnice s menší výškou. Hledaná smrnice je pak váženým prmrem horního a dolního svahu (viz Obr. 11). Pokud „horní“(resp. „dolní“) oblast chybí, je použita pímo hodnota získaná z „dolní“ (resp. „horní“) oblasti. To platí také v pípad, že ob sousedící vrstevnice jsou vyšší (resp. nižší). Nyní je možno interpolací zjistit výšku každého bodu použitím tzv. monotónníinterpolace, která zaruuje spojitost C1 a nezpsobuje oscilace. Oblasti, jež nemají vnitní hraniní vrstevnice (vrcholy, údolí) jsou extrapolovány z hodnoty vnjší vrstevnice a známého svahu v obklopující oblasti.
lánek pináší popis velmi elegantního a rychlého algoritmu, kterýnevyžaduje žádný píliš složitý matematický aparát. Nepíjemnou skuteností je požadavek na uzavenost vrstevnic, což znan snižuje procento mapových výez, na nž mže být algoritmus použit. Tento lánek se stal výchozím pro implementovaný algoritmus popsaný v kapitole 3.3.

Obr. 11. Výpoet svahu na vrstevnici c1. Výpoet svahu s1 na vrstevnici c1 za pomocí dolního svahu s01 a horního svahu s12.

-12-

3 Teoretický rozbor V teoretickém rozboru jsou popsány kritéria pro výbr algoritmu ureného k implementaci. Dále jsou popsány úpravy a rozšíení pidané do implementace. Následuje popis krok algoritmu. V závru kapitoly jsou specifikovány formáty vstupních a výstupních dat. 3.1 Výb
ralgoritm u Pro výbr algoritmu ureného k implementaci byla stanovena následující kritéria. Algoritmus : 1. M usí vytváet spojitýhladkýpovrch, jehožsouástí jsou vstupní vrstevnice, 2. musí pracovat efektivn, 3. bude využívat pro výstup nepravidelnou trojúhelníkovou sí (TIN), 4. bude aplikovatelnýna standardní topologické vrstevnice z mapových výez. Pravidlo 3. nepímo také vyplývá z prvního, kde je stanoven požadavek, aby vstupní body byly souástí také výstupu, což v obecném pípad u tvercové sít není možné zaruit. Pravidlo 1. také íká, že není možné použít aproximaní metody. Tmto požadavkm nevyhovují algoritmy uvedené v kapitolách 2.3.1, 2.3.2 a 2.3.3. Algoritmus obsažený v 2.3.4 byl testován. Nepíjemná byla ovšem velmi patrná schodovitost terénu v místech ostejších záhyb vrstevnic. M etoda popsaná v kapitole 2.3.5 mže být pomrn neefektivní, nebo pracuje iteran. M etoda 2.3.7 je velice zajímavá, ovšem vrací terén se spojitostí C0. Postupy 2.3.6 a 2.3.8 vyžadují na vstupu pouze uzavené vrstevnice. Nejsou tedy aplikovatelné na mapové výezy, které vtšinou obsahují také neuzavené kivky. Akoliv žádnýz algoritm zmínných v kapitole 2.3, zcela neodpovídá požadavkm, byla, jako základ algoritmu, zvolena metoda 2.3.8. Tato metoda pracuje velmi elegantn a efektivn. K výpotu výšky používá jednoduchou aritmetiku, kterou lze snadno naimplementovat. Zaruuje také hladkost terénu na vtšin povrchu. Pvodní algoritmus bude lehce upraven, aby dokázal na vstupu pijímat neuzavené vrstevnice. Veškeré úpravy jsou shrnuty v 3.2. 3.2 Úpravy algoritm u Pvodní algoritmus popsaný v lánku [6], je urený pouze pro uzavené vrstevnice. To je znan omezující, nebo vtšina mapových výezu se sestává také z vrstevnic otevených. Implementovaný algoritmus byl tedy rozšíen v použitelnosti na otevené vrstevnice. Rozšíením o neuzavené vrstevnice musejí být zrušeny oblasti i, které byly jednoznan ohranieny vrstevnicemi (viz kapitola 2.3.8). Bodnáležící dané oblasti i ml tedy jednoznan ureny vrstevnice, z kterých se pro nj hledají nejbližší sousedé. Zrušením oblastí je porušena tato jednoznanost. V implementovaném algoritmu jsou tedy

-13-

nejbližší body sousedních vrstevnic hledány pomocí inteligentních prohledávacích algoritm, využívajících grafových vlastností trojúhelníkové sít (TIN).
lánek [6]také nediskutoval možnost vzniku nových bod vrstevnic pi tvorb husté trojúhelníkové sít. Nášalgoritmus byl obohacen o hledání nových vrstevnicových bod, ímžbyla snížena nepesnost rekonstrukce povrchu v bezprostedním okolí vrstevnic. Zpsobvýpotu výšky zstal totožnýs pvodním algoritmem –za pomoci známých výšek blízkých vrstevnic a smrnice svahu na nich. Zmnn byl ovšem zpsob výbru správného vzorce pro extrapolaci. Pvodní algoritmus ml pouze dva extrapolaní problémy:výpoet výšek údolí a vrchol, které byly vždy ohraniené jednou uzavenou vrstevnicí. V pvodním algoritmu tak stailo pouze prozkoumat výšky hraniních vrstevnic vedlejších oblastí a vzorec byl jednoznan uren. Použitím otevených vrstevnic se výbr ponkudkomplikuje, nebo na map mohou nastat situace, že dv vedle sebe ležící vrstevnice mají totožnou výšku. Správný vzorec je tak hledán zkoumáním vzájemné konfigurace dvou až tí nejbližších vrstevnic v okolí. Krom vrchol a údolí je poteba také extrapolovat okraje map (Pvodní algoritmus rekonstruoval pouze oblasti, které mli vnjší hraniní vrstevnici. Viz nap. Obr. 10. 0 nemá vnjší vrstevnici –nerekonstruuje se.). K algoritmu byl také pidán výpoet normál k rekonstruované ploše - pro snazší aplikaci osvtlovacího modelu. Protože mohou vznikat chyby ve výpotu, a generovat tak poruchy povrchu, byla doplnna také funknost detekce a korekce tchto chyb. 3.3 Popis algoritm u Popis implementovaného algoritmu je zamen na diskrétní model konstruovaného pomocí nepravidelné trojúhelníkové sít (TIN). Uspoádán je do nkolika chronologicky seazených krok (viz Tab. 1), jejichžpoadí musí být zachováno. poadí 1 2 3 4 5 6 7 8 9


innost Natení vstupních dat Úprava vrstevnic Triangulace Hledání nových bod vrstevnic Hledání nejbližších bod vrstevnic Výpoet svah Výpoet výšek Vyhlazení chyb Výpoet normál Tab. 1.

Implementace krok algoritmu

3. 3. 1 Vstupnídata Vstupními daty algoritmu jsou vrstevnice. Na rozdíl od pvodního algoritmu ([6]), kde byly vrstevnice uzavené (tedy polygony), jsou nyní pijímány jako otevené. Vstupní

-14-

data jsou tedy lomené áry (anglicky polylines). Jednotlivé body lomených ar jsou specifikovány pomocí kartézských souadnic. V pípad jiného souadnicového systému (nap. W GS-84) je teba souadnice vhodn pevést do souadnic kartézských. Vrstevnice se vzájemn neprotínají. 3. 3. 2 Úprava vrstevnic Je-li to požadováno, jsou vrstevnice upravovány. Úprava algoritmu [6]spoívala v pevzorkování všech vrstevnic na body se konstantní vzdáleností od sebe. Implementovaný algoritmus zachovává vstupní body a umožuje pidat podle poteby další, nebo v pípad pílišhustého vzorkování nkteré odebrat. 3. 3. 3 Triangulace Výsledný model má být reprezentovaný nepravidelnou trojúhelníkovou sítí, která vzniká triangulací vstupních bod a pidáním nových bod. Sít je vhodné konstruovat jako Omezenou Delaunayovu triangulaci (CDT –Constrained Delaunay Triangulation). Omezená Delaunayova triangulace, je speciální pípadDelaunayovy triangulace. Pro Delaunayovu triangulaci platí, že kružnice opsaná jakémukoliv trojúhelníku ze sít neobsahuje žádnýjinýbod(Delaunayova podmínka). Omezené Delaunayov triangulaci se krom množiny bod zadávají také povinné (tzv. Delaunayovy) hrany, které se musí ve výsledné triangulaci prosadit. V okolí tchto hran mže být porušena Delaunayova podmínka. Do triangulace se tak dostávají nejen body definující vrstevnice, ale také hrany lomených ar. Povinné hrany vrstevnic se tak projeví ve výsledné síti. Hrany na vrstevnici mají stanovenou výšku, cožzvyšuje pesnost rekonstrukce v okolí vrstevnic. V implementovaném algoritmu i v [6]je použit algoritmus J. R. Shewchuka, popsaný v [20]. Tento algoritmus si klade podmínku, že na vstupu je tzv. PSLG (planar stright line graph) - grafplanárních rovných hran. Z této podmínky vyplývá, že žádná hrana vrstevnic se nesmí protínat s jinou hranou, cožstandardní vrstevnice splují. V pípad nedodržení této podmínky algoritmus koní neúspšn. Algoritmus dostává dv tvarová kritéria. Prvním tvarovým kritériem je nepovinné délkové kritérium. Jestliže je délkové kritérium zadané, je vytváena taková triangulace, v níž není žádná hrana delší než tato hodnota. Druhým kritériem je B hodnota, což je pomr polomru opsané kružnice trojúhelníku a nejkratší hrany tohoto trojúhelníku. Tato vlastnost uruje možné maximální a minimální velikosti úhl v trojúhelníku. Toto je velké omezení algoritmu, nebo je-li nkterý z úhl menší, nežminimální úhel, není zarueno úspšné ukonení algoritmu. M ezní minimální úhel byl spoítán na pibližn 20.7°. Jsou tedy stanoveny další podmínky na vrstevnice a okrajmapy: • Žádná hrana lomené áry definující vrstevnice nesmjí protínat jinou hranu. • V žádném bod lomené áry definující vrstevnice a okraje mapy nesmí být úhel menší než20.7°. Pokud jsou tyto podmínky splnny, algoritmus vytvoí trojúhelníkovou sí, jejíž žádnýúhel není menší nežstanovená mez a žádná hrana není vtší nežstanovená délka. Je-

-15-

li povinná hrana delší, dojde k jejímu plení, tj. vzniku nového bodu na hran. Body ležící na hranách náleží tedy vrstevnicím. Protože triangulace probíhá pouze v horizontální rovin (pozice bodu je urena pouze souadnicemi x, y). Nové body vrstevnic je tedy nutné najít a do píslušných vrstevnic je zaadit (stanovit jim píslušnou výšku). 3. 3. 4 Hledánínových bod
vrstevnic Pestože lánek [6] používá stejný algoritmus tvorby TIN sít se stejnými vlastnostmi, není v nm problém hledání nových bod diskutován. Nové body vrstevnic je ovšem nutné nalézt, z dvod snížení nepesnosti rekonstrukce. Protože množství nov vzniklých bod mže být velké, bylo by znan neefektivní testovat každý bod, zda neleží na pvodních hranách. Trojúhelníkovou sí mžeme považovat za planární graf. Je tedy možné využít vhodného grafového prohledávacího algoritmu. Takovým algoritmem je nap. A*(A star). A* algoritmus je informovaným prohledáváním stavového prostoru (resp. grafu). Principem A* je znalost startovní i cílové pozice prohledávání. Prohledávány jsou pouze uzly, které nejlépe vyhovují heuristické funkci. Touto heuristickou funkcí je zde absolutní vzdálenost mezi pvodními body. Algoritmus je aplikován na všechny dvojice za sebou jdoucích bod vstupních vrstevnic. V prvním kroku jsou nalezeni všichni sousedé startovacího uzlu (expanze uzlu) a zaazeny do prioritní fronty podle soutu vzdáleností od startovacího do nalezeného a od nalezeného do cílového uzlu. Z prioritní fronty je následn vybrán uzel s nejmenší hodnotou a ten je expandován stejn jako poátení, do doby, nežje nalezen cílový uzel. Všechny uzly, které byly expandovány a nejsou dosud souástí vrstevnice jsou do vrstevnice pidány. Protože pi triangulaci algoritmem podle [20] dochází pouze k rozdlování hran novými body, je vždy vzdálenost z poáteního do cílového uzlu i pes tyto body stejná. Volba heuristické funkce tedy zajistila nejlepší informovanost algoritmu a nové body jsou nacházeny zcela neomyln. 3. 3. 5 Hledánínejbl ižších bod
vrstevnic Pvodní algoritmus rozdluje rekonstruovaný povrch do oblastí  (viz kapitola 2.3.8). Po triangulaci je nutné urit do které oblasti nov vzniklé body spadají. To je možné provést bu triangulací pouze píslušné oblasti  a pak je jasné, že všechny vzniklé body patí do dané oblasti, nebo po jedné globální triangulaci zkoumat pro každý bod, do jaké oblasti patí. Píslušností v oblasti j sou pro každý bod stanoveny nejbližší hraniní vrstevnice. Tato znalost je dležitá pro výpoet svah na vrstevnicích a tudíž také pro výpoet výšek ostatních bod. V naší verzi algoritmu ovšem oblasti nevznikají. I pesto je ovšem nutné znát nejbližší vrstevnice. Pro jejich hledání se opt nabízí jako v pedchozím kroku použití grafového prohledávacího algoritmu. A* v tomto pípad nemá smysl, nebo neznáme cílový uzel. Je poteba procházet nejbližší okolí každého bodu a prohledávání zastavit až s nalezením bodu náležícímu vrstevnici. Tomuto zpsobu nejlépe odpovídá algoritmus UCS (Uniform Cost Search).

-16-

UCS algoritmus je využíván v umlé inteligenci pro vylepšení neinformovaného prohledávání do šíky (BFS). Oproti prohledávání do šíky je ovšem seznam open uzl seazen podle ceny daného uzlu. V tomto pípad je cenou vzdálenost odpoáteního uzlu. Použitím UCS algoritmu je zarueno nalezení nejbližšího bodu splujícího kritérium pro zastavení. Úloha hledání je ovšem ponkud ztížena požadavkem nalezení dvou bod. Nalezení prvního je pomrn jednoduché. Druhý ovšem musí být hledán opatrn. Významné situace jsou znázornny na Obr. 12. Jsou hledány nejbližší body na vrstevnicích pro bod p1. Bod p2 je nalezen jako první. Nyní hledáme další bod na jiné vrstevnici. Nalezeným je bod p3. V pvodním algoritmu však tento bod leží v úpln j iné oblasti nežbod p1. Prohledávací algoritmus se tedy nesmí pohybovat dále za vrstevnici s bodem p2, cožvede k nalezení správného bodu p4. Obdobnou situací je hledání pro bodp5. Prvním nalezeným bodem je p6. Ten má odp5 vtší vzdálenost, nežp5 odokraje mapy. Lze tedy usoudit, že bodp5 se nachází na okraji mapy a nemá smysl hledat druhýbod.Nalezené body jsou piazeny bodu aktuálnímu. Stejným zpsobem se hledají sousední vrstevnice i pro body ležící na vrstevnicích, jak je tomu naznaeno na Obr. 12, kde pro bod b jsou nalezeny body dvou nejbližších vrstevnic a a c. Hledání nejbližších bod vrstevnic pro body ležící na vrstevnicích (bod b na Obr. 12) v pvodním algoritmu v podstat odpovídá rozdlení mapy do oblastí. Hledání nejbližších bod vrstevnic pro ostatní body pak odpovídá urování píslušnosti každého bodu do dané oblasti.

Obr. 12. UCF prohledávání

3. 3. 6 Výpoet svah
Smrnici svahu je nutné vypoítat pouze pro body na vrstevnicích. Svah je nutnýpro výpoet výšky ostatních bod. V pedchozím kroku byly pro každýbodvrstevnice ureny dva body jiných dvou nejbližších vrstevnic. Z nich je možno vypoítat smrnice horního a dolního svahu a následn váženým prmrem vlastní svah. Podle [6]lze ovšem výpoet provést najednou použitím vzorce : h 2 − h1

(3.1) , d 2 + d1 kde h2 a h1 jsou výšky bod z okolních vrstevnic a d2 a d1 jsou vzdálenosti k tmto bodm. Pokud druhý bod není nalezen (první je vždy!), je k výpotu použit pouze první bodpodle: s=

-17-

h − h1

(3.2) , d Kde h je výška aktuálního bodu vrstevnice, h1 je výška nalezeného bodu a d je vzdálenost mezi tmito body. s=

3. 3. 7 Výpoet výšek Znalost svah z pedchozího kroku je využita pro výpoet výšky bod ležících mimo vrstevnice. Výpoet výšky mžeme rozdlit na interpolaní a extrapolaní problém. Zná-li bod oba body ze dvou sousedních vrstevnic, pak lze použít interpolaci. Jestliže je znám pouze jeden bod vrstevnice, pak se nacházíme uprosted uzavené vrstevnice, nebo poblíž okraje mapy. Tyto místa je teba extrapolovat. Rozhodnutí, zda rekonstruovat svah nebo údolí je závislé na blízkém okolí vrstevnice. Pro výpoet interpolované výšky v bod p mjme dva body nalezené v kroku 3.3.5: p1 a p2. Tyto body mají odp vzdálenost d1 a d2, výšku h1 a h2 a smrnice svah s1 a s2. Lze použít následující postup: d + d2 ; i = 1,2 t i = si ⋅ 1 (3.3) h2 − h1

u1 = d1 + t1 ⋅ d 2 , u 2 = d 2 + t 2 ⋅ d1 h=

h2 d1u1 + h1d 2 u 2 d1u1 + d 2 u 2

(3.4) (3.5)

Vzorce ukazují aplikaci tzv. monotonní interpolace. Tento zpsob zaruuje C1 spojitost povrchu a nezpsobuje oscilace. V pípad extrapolované výšky je nutné rozhodnout se, zda bude rekonstruováno údolí, nebo vrchol. V pvodním algoritmu toto bylo jednoduše provedené prozkoumáním sousední oblasti. (Extrapolovaná oblast byla obklopena vrstevnicí, ježbyla vnitní hranicí jiné oblasti. Pokud svah v sousední oblasti smrem ke zkoumané oblasti rostl, byl extrapolován vrchol. Pokud svah klesal, bylo rekonstruováno údolí.). Zrušením oblastí se mechanismus výbru ponkudzkomplikoval. Nicmén vzorce zstaly stejné. Pokudje rekonstruován vrchol je použit vzorec: (3.6) h = h1 + s1 d1 , v pípad údolí:

h = h1 − s1 d1 ,

(3.7)

e svah v tomto bod a d1 je vzdálenost od kde h1 je výška nejbližšího bodu z vrstevnice, s1 j aktuálního bodu. Výbr správného ze vzorc pro extrapolaci je proveden s využitím znalosti nejbližších bod vrstevnic. Extrapolace je znázornna na Obr. 13:

-18-

Obr. 13. Extrapolace bodu z okolních vrstevnic.

Pro bod x je uren nejbližší bod na vrstevnici c1 jehožvýška je h1. Pro bod c1 byl v korku popsaném v kapitole 3.3.5 nalezen nejbližší bod j iné vrstevnice c2 s výškou h2. Nyní je zkoumána výška obou nalezených vrstevnic. Jestliže je h1 > h2 (Obr. 13 vlevo), je použit vzorec (3.6). Jestliže je h1 < h2 (Obr. 13 uprosted), je použit vzorec (3.7). Správnost výpotu je ovená pokudpro vzdálenosti a, b a c platí (viz:Obr. 13 vpravo): (3.8) a+b ≥ c ∧ a < c, Doposud odpovídá hledání výšek pvodnímu algoritmu. Zrušením oblastí a zavedením neuzavených vrstevnic mže ovšem nastat zcela nová situace, kdy h1 = h2. V tomto pípad je poteba provit také tetí vrstevnici. Pro bodc2 jsou nalezeny dv nejbližší vrstevnice, z nichž jedna je c1 a druha c3. Podle vzájemné konfigurace nalezených tí vrstevnic je pak uren správný vzorec. Situace kdy vedle sebe jsou ti vrstevnice se stejnou výškou u standardních topologických vrstevnic nenastává, není tedy nutné prozkoumávat vtší oblast. Pokudje porušena podmínka (3.8) je výška nastavena na hodnotu nebližší vrstevnice c1, aby pípadná chyba v terénu nebyla tak velká. Stejn je výška nastavena, pokudmá bod na vrstevnici c2 urenu pouze jednu nejbližší vrstevnici a tou je opt c1. 3. 3. 8 Vyhlazeníchyb Použitím neuzavených vrstevnic mohou nastat v terénu situace, které nelze dost dobe zachytit a mohou tak vzniknout chyby. Algoritmus byl tedy doplnn o možnost detekce a korekce alespo jednobodových poruch. Pokud se v terénu vyskytne jednobodová porucha taková, že bod svoji výškou pesahuje všechny své sousedy, nebo naopak všichni sousedé jejsvou výškou pesahují, jedná se patrn o chybu výpotu. Tuto chybu lze eliminovat nastavením výšky bodu na hodnotu získanou váženým prmrem výšek pímých soused v triangulaci. Váhou je zde vzdálenost sousedního bodu. Vyhlazovány jsou pouze body ležící mimo vrstevnice. 3. 3. 9 Výpoet normál Po pedchozím kroku je již model možné zobrazit. Jsou však jasn patrné hrany trojúhelník tvoících sí. To lze eliminovat použitím vhodného osvtlovacího modelu. Pro aplikaci osvtlovacího modelu je však nutné znát normálové vektory k rekonstruovanému povrchu. Normály jsou poítány v každém bodu povrchu (tj. v každém bod TIN). Opt je využito grafových vlastností TIN. Prozkoumávány jsou všechny trojúhelníky incidující s bodem, v nmž hledáme normálu. Každý trojúhelník je vlastn rovinou urenou temi body. Tyto ti body urují dva vektory, z nichžvektorovým souinem je získána hodnota

-19-

normály v daném trojúhelníku. Normálový vektor n rekonstruovaného povrchu v daném bod je pak dán váženým prmrem normál ni všech trojúhelník incidujících s tímto bodem. Váha w je dána úhlem i kterýzastupuje píslušnýtrojúhelník i v daném bod: αi

n =
wi ⋅ ni , kde wi = (3.9)


α

i

Výslednývektor je nutné znormalizovat na jednotkovou délku. Nyní je rekonstruovanýmodel jižmožné zobrazit bez viditelných hran trojúhelník. 3.4 Vstupy Algoritmus pracuje s kartézským systémem souadnic. Vstup je specifikován v podkapitole 3.4.1. Data jsou vtšinou naítána ze souboru. Stanoveny jsou požadavky na dva druhy vstupních soubor:Vstupy zadané kartézskými souadnicemi a Polish Formát GPS topologických map ([21]). 3. 4. 1 Specifikace vstupu Vstupem algoritmu jsou vrstevnice reprezentované lomenými árami (polylines). Ty jsou ureny sekvencí trojrozmrných bod. Každý bod specifikuje svoji topologickou pozici a výšku v kartézských souadnicích se stejnou jednotkou na všech osách. (Výška je zadávána proporcionáln vzhledem k ostatním rozmrm.) 3. 4. 2 Vstup ze souboru s kartézskými souadnicemi Vstup je rozdlen do nkolika textových soubor. Jeden soubor je indexový (u testovacích dat je použita koncovka *.txt). Tento soubor obsahuje relativní cesty k ostatním souborm, v nichž jsou uloženy data vrstevnic (u testovacích dat mají tyto soubory koncovku *.xyz). Každý soubor specifikuje práv jednu vrstevnici. Data v nich jsou uložena jako trojice reálných ísel, reprezentujících postupn souadnice x, y a z. Jednotlivá ísla j sou od sebe oddleny tzv. bílými znaky (mezera, tabulátor, enter). K oddlení desetinných míst v ísle se používá teka. Vstupní body jsou naítány po trojicích. Pokudnaítání nkteré trojice ísel selže, (chybné znaky –nap. písmena, konec souboru, apod.), naítání vrstevnice je ukoneno a pokrauje se další vrstevnicí z indexového souboru. 3. 4. 3 Vstup ze souboru Polish formátu GPS map Polish formát je textový formát souboru, který byl vyvinut jako vstupní formát pro program cGPSmapper([21]). Program umožuje pepis vektorových GPS map do formát specifických pro jednotlivé GPS pijímae (nap IM G formát pro pijímae Garmin). Pro polish formát byl vytvoen celý pseudojazyk, který, je podobn jako nap. html, znakovací. Každá specifická sekvence dat je uvozena otvírací znakou a ukonena zavírací znakou, mezi nimiž se nacházejí jednotlivé atributy. Pro námi požadované vrstevnice jsou to znaky [RGN40]a [END-RGN40](tzv. region). Bezprostedn za otvírací znakou následuje atribut Type. Tomu je piazena hexadecimální hodnota. Hodnoty 0x20, 0x21, nebo 0x22, byly vyhrazeny pro popis vrstevnic. Až po uzavírací znaku budou tedy popisovány vrstevnice. Na dalším ádku

-20-

následuje Label. Ten udává hodnotu výšky daných vrstevnic. Podle specifikace je výška zadávána ve stopách. Za znakou Labelnásledují ádky oznaené jako DataX. Polish formát umožuje pracovat s aždesíti vrstvami. Každá vrstva uruje velikost detailu mapy. Písmeno X za slovem Data je nahrazeno íslem píslušné vrstvy. Pro naítání dat používáme vrstvu 0 - tedy ádky oznaené Data0. Tato vrstva nabízí nejvtší úrove detailu. Každý ádek oznaený jako DataX obsahuje data práv jedné vrstevnice. Na stejném ádku za touto znakou jsou tedy uloženy dvojice hodnot oznaujících polohu bodu. Poloha bod je zadána ve stupních (severní šíky a východní délky). Po natení dat ze souboru musí být tyto hodnoty pevedeny do kartézských souadnic, které vyžaduje algoritmus. Více informací a úplná specifikace Polish formátu je dostupná na [18]. 3.5 Výstupy 3. 5. 1 Specifikace výstupu Jsou požadovány ti druhy výstupu: Grafický výstup na obrazovku; výstup do souboru a datová struktura. Datová struktura reprezentující výstup je tída obsahující seznam bod a trojúhelník, tvoených body. Pro každýbodje také specifikován normálovývektor. Tída má pístupové metody umožující tení i modifikaci atribut. Souástí této datové struktury jsou také metody umožující výstup na obrazovku pomocí OpenGL a výstup do souboru formátu VRM L. Veškerývýstup je tak obsloužen jedinou tídou. Výstup pomocí OpenGL i do souboru je istýpepis topologie a geometrie povrchu. Algoritmus s texturami nepracuje. Aplikace textur je ponechána na uživateli. 3. 5. 2 Výstup pomocíVRM L Pro datový výstup do souboru je uren soubor typu VRM L. VRM L nabízí nkolik datových struktur, z nichž nejvhodnjší pro reprezentaci trojúhelníkové sít je IndexedFaceSet. Struktura umožuje uložit body, normály i trojúhelníky. Body a normály jsou ukládány do pole reálných ísel. Každá trojice za sebou jdoucích ísel uruje souadnice jednoho bodu (resp. vektoru). Trojúhelníky jsou ukládané v poli ve form tí index do pole bod, ukonených íslem -1. (více o VRM L a IndexedFaceSet v [5]).

-21-

-22-

4 Realizace Kapitola je rozdlena na ti ásti. V první ásti je proveden návrh objektového ešení algoritmu. Druhá ást uvádí knihovny a funkce použité pro implementaci. Tetí ást se vnuje vlastní realizaci v programovacím jazyku C++. Na úvod je strun popsána implementace vizualizaního prostedí, následuje popis implementace tída jejich metod. 4.1 Analýza Vlastní implementace algoritmu je postavena na principech objektového programování. Veškeré datové struktury jsou realizovány pomocí objekt a kolekcí objekt. Lze tak snadnji modifikovat zdrojovýkódalgoritmu. Jednotlivé kroky algoritmu jsou realizovány voláním metodhlavního objektu tídy Map, kterýv sob zahrnuje ostatní tídy. Následuje popis návrhových tíd, jejichžschéma je nakreslené na Obr. 14. PointS

Point2D attributes

extends

- x:double - y :double operations + distance2D(Point2D) :double

*

attributes - height :double - slope :double - normal :double [3] -cIdent :int - index:int operations + computeSlope() :void + computeHeight() :void

Contour

1..*

1

attributes - cIdent :int operations + reducePoints() :void + thickPoints() :void

0..* 1..*

1..2

Vector3D

Point3D

attributes - x:double - y :double - z :double - index:int

attributes - x:double - y :double - z :double - index:int

1

M ap attribute 1s - minX :double - maxX :double - minY :double - maxY :double - minHeight :double - maxHeight :double operations + loadContours() :void + generateM odel() :Model + clipPoints() :void + computeSlopes() :void + computeHeights() :void + computeNormals() :void + findNewContourPoints() :void + generateM esh():void + thickM ap() :void + reduceM ap() :void

1..* 1..*

3

1

M odel attributes - maxZ :double - minZ :double operations + genDisplayList() :Gluint + saveVRM L(Stringfname) :void

1

1..* 1..*

Triangl e

1

Obr. 14. Návrhové tídy

4. 1. 1 Návrhovátída Point2D a PointS Tída Point2D reprezentuje bod v map – tedy v horizontální rovin. V nkterých ástech algoritm se provádí hledání nejbližších bod s uritou vlastností (nap. nejbližší bodna vrstevnici). Pro zjištní vzdáleností bod slouží metoda distance2D(). Tída PointS je rozšíením tídy Point2D. Pro body ležící na vrstevnicích je teba poítat smrnici svahu (atribut slope), k emužslouží metoda coumputeSlope(). Pro ostatní body musí být vypoítána výška (height) metodou computeHeight().

-23-

K tmto výpotm je nutné znát dva nejbližší body z vrstevnic. Informaci o tom, zda bod leží na vrstevnici udržuje atribut cIdent. Atribut index je pomocný, používaný pi tvorb tídy Model. 4. 1. 2 Návrhovátída Contour Contour reprezentuje vrstevnici jako sekvenní kontejner obsahující tídy PointS. U vrstevnic je pidána možnost upravit hustotu jejich bod.
lenská metoda reducePoints() redukuje poet bod, vrstevnice. Vypouštny jsou body, které vyhovují zadanému úhlovému a délkovému kritériu. M etoda thickPoints() vrstevnici naopak zahustí, pokudjsou následující body odsebe dále nežstanovené kritérium. 4. 1. 3 Návrhovátída M ap Map je tída, nadnížjsou provádny hlavní kroky algoritmu. Uchovává informace o rozmrech mapy (atributy minX, maxX, minY, maxY) a rozsahu výšek vrstevnic (minHeight, maxHeight). Tída také obsahuje kolekce vrstevnic a bod ležících mimo vrstevnice. Nkteré metody reprezentují kroky algoritmu:M etoda loadContours() naítá vrstevnice v daném formátu. M etoda generateMesh() vytvoí dostaten hustou TIN. Hledání nejbližších bod na okolních vrstevnicích zajišuje funkce clipPoints(). Funkce computeSlopes() nad všemi body vrstevnic volá píslušnou metodu pro výpoet svahu. Obdobn computeHeights() volá nad každým bodem, který dosud nemá stanovenou výšku, metodu pro její výpoet. M etoda computeNormals() vypoítá normálové vektory rekonstruované plochy v píslušných bodech za pomocí okolních bod a trojúhelník. Funkce generateModel() vytvoí objekt tídy Model a naplní jejpotebnými daty – všemi body, normálami a trojúhelníky tvoící sí. 4. 1. 4 Návrhové tídy Point3D a Vector3D a Triangle Tída Point3D a Vector3D reprezentují bod a vektor v trojrozmrném prostoru. M ají lenské promnné reprezentující kartézské souadnice (x, y, z) a identifikátor (index). Tídy jsou použity jako souást tídy M odel, kde Point3D reprezentuje pirozen bod trojúhelníkové sít a Vector3D normálu v tchto bodech. Spolený identifikátor index uruje píslušnost normály danému bodu. Akoliv jsou tyto dv návrhové tídy sémanticky odlišné, mohou být implementovány jedinou datovou strukturou, nebo mají stejné atributy. Tída Triangle reprezentuje trojúhelník, který tvoí souást nepravidelné trojúhelníkové sít (TIN) v objektu Tídy model. Trojúhelník je uren temi body, které jsou reprezentovány tídou Point3D. 4. 1. 5 Návrhovátída M odel Tída Model je výstupní datovou strukturou. Obsahuje kolekci trojúhelník Triangle, reprezentujících rekonstruovanýpovrch, kolekci objekt typu Point3D, jež jsou vrcholy daných trojúhelník a kolekci vektor Vector3D reprezentujících normálové vektory plochy v píslušných bodech. Tída obsahuje metody pro pístup

-24-

k daným atributm. Obsaženy jsou také metody pro vizuální reprezentaci modelu. M etoda genDisplayList() vytváí displayList pro renderování pomocí OpenGL (atributy minZ a maxZ jsou zde použity pro obarvení výškové mapy). M etoda saveVRML() ukládá danýpovrch ve formátu VRM L –IndexedFaceSet do souboru. (viz 3.5).

tení vstupu

upravit

neupravovat vrstevnice

úprava vstupu

triangulace

hledání nových bod vrstevnic

hledání nej bližších bod vrstevnic

výpoet svah

výpoet výšek

vyhlazení chyb

výpoet normál

tvorba modelu

Obr. 15. Postup algoritmu

4. 1. 6 Postup algoritmu Jak bylo zmínno na zaátku kapitoly, kroky algoritmu jsou reprezentovány voláním metod hlavního objektu. Hlavním výpoetní tídou je Map. Na zaátku celého algoritmu musí tedy být nejprve vytvoena instance této tídy. Ta následn volá píslušné metody algoritmu. Dané poadí volání metod nesmí být mnno, nebo jednotlivé kroky jsou na pedchozích závislé a pi jejich volání se pedpokládá, že pedchozí krok byl proveden. Schéma postupu algoritmu je znázornno na Obr. 15. a v Tab. 2. poadí 1 2 3 4 5 6 7 8 9 10


innost Natení vrstevnic Úprava vrstevnic Triangulace Hledání nových bod vrstevnic Hledání nejbližších bod vrstevnic Výpoet svah Výpoet výšek Vyhlazení chyb Výpoet normál Tvorba modelu Tab. 2.

Jméno funkce loadContours() thickMap()/reduceMap() generateMesh() findNewContourPoints() clipPoints() countSlopes() countHeights() pickPoints() countNormal() generateModel()

Postup algoritmu z hlediska analýzy

-25-

Po vytvoení hlavního objektu je teba zavolat metodu loadContours() pro natení vstupních dat. Vrstevnice mohou být podle poteby upraveny metodami thickMap() nebo reduceMap(). Následn jsou vstupní data triangulována metodou generateMesh(). Po triangulaci je teba nalézt nové body vrstevnic a vrstevnicím je správn piadit. Dále je volána metoda clipPoints(), která hledá nejbližší body vrstevnic (viz 3.3.5). Poté je volána sekvence funkcí computeSlopes(), computeHeights() pickPoints() a computeNormal(), které vypoítají smrnice svahu na bodech vrstevnic, s jejichž pomocí poté ostatní body poítají svoji výšku. Je spuštna detekce a korekce jednobodových poruch a vypoítány normálové vektory k rekonstruované ploše. V tuto chvíli je model prakticky hotov a mže být zobrazen. Pro oddlení výstupu odvýpoetní ásti je však metodou generateModel() vytvoena instance tídy model a vypoítanýpovrch je peveden do její reprezentace. 4.2 Použité knihovny a funkce Algoritmus je implementován v jazyku C++. Použité knihovny musejí tedy být také napsané v C++, nebo musejí být z C++ volatelné. Použité jsou knihovny:STL, OpenGL, GLUT a CGAL. 4. 2. 1 STL –Standard template library Standard Template Library, neboli standardní knihovna šablon je multiplatformní C++ knihovnou obsahující kontejnery, iterátory a základní algoritmy a datové struktury. Pevážná vtšina komponent jsou šablony, a tím pádem snadno parametrizovatelné. Knihovna STL je ásten souástí standardu jazyka C++ . Pi implementaci algoritmu byly využity zejména kontejnery a iterátory. Více informací o STL v [3]. Knihovnu je dostupná na stránkách www.sgi.com. 4. 2. 2 OpenGL Pro vykreslení grafické reprezentace modelu je použita knihovna OpenGL. Knihovna OpenGL je standardizované multiplatformní rozhraní pro tvorbu poítaové grafiky. OpenGL mže být implementováno jak softwareov, tak hardwareov a využívat tedy veškerých možností hardware. Obsahuje více než 120 funkcí pro práci s rastrovou i vektorovou grafikou v 3D prostoru. Z nich nejdležitjší jsou vykreslování grafických primitiv, transformace souadnic, osvtlení scény a aplikace textur. Více informací o OpenGL v [4]. 4. 2. 3 GLUT Protože standardOpenGL pro práci s grafikou pímo nepodporuje práci s okny, musí být pro vizualizaci použita knihovna, která umožní zobrazení OpenGL. Takovou knihovnou je napíklad GLUT – GL Utility Toolkit. Okenní systém nemá podporu pro komponenty jako nap. tlaítka, posuvníky apod. Nabízí pouze jednoduchou práci s okny, klávesnicí a myší. S pomocí knihovny je vytvoeno jednoduché prostedí s názvem Saddle(sedlo) pro zobrazení modelu a výškové mapy.

-26-

4. 2. 4 CGAL Knihovna CGAL – Computational Geometry Algorithms Library, je C++ knihovna distribuovatelná pod dvojí licencí (viz [19]). Pro open-source programy je ovšem zcela zdarma. Je vytvoena objektov a nabízí velké množství datových struktur a algoritm výpoetní geometrie, jako jsou nap.:Triangulace, Voronoiovy diagramy, generování sítí, operace nadpolygony, konvexní obálky a spousta dalších. CGAL knihovna je založená na knihovnách projektu BOOST (www.boost.org). Umožuje práci ve 2D i 3D, ve specifických úlohách dokonce v n-rozmrném prostoru (nap. nD konvexní obálka). Knihovna CGAL je velmi mocným nástrojem výpoetní geometrie. Z mnoha jejich datových struktur a algoritm byla použita datová struktura (resp. objekt) CDT (Constrained Delaunay Triangulation) a funkce refine_Delaunay_mesh_2(). Popsány jsou v následujících kapitolách 4. 2. 5 CDT objekt CDT je datová struktura knihovny CGAL, urená zejména pro použití ve funkcích generujících trojúhelníkovou sí. Odtud také název CDT – Constrained Delaunay Triangulation. Obsahuje body (Point), hrany a trojúhelníky (Face). Struktura je navržená tak, že na ni lze aplikovat grafové prohledávací algoritmy. Každýtrojúhelník zná všechny svoje body a hrany a naopak každýbod ví, kterým trojúhelníkm a hranám patí. Pomocí iterátor lze procházet všechny body, nebo trojúhelníky CDT struktury. Existují také cirkulátory, kterými lze k uritému bodu procházet všechny incidující trojúhelníky, hrany, i body. Díky použití šablon (templates) lze body i trojúhelníky doplnit o další informace. 4. 2. 6 Funkce refine_Delaunay_mesh_2() Implementace algoritmu, který vytváí sí trojúhelník je netriviální problém. Pro tvorbu sít z vrstevnic je proto použita funkce refine_Delaunay_mesh_2() z knihovny CGAL. Tato funkce je implementací J. R. Shewchukova algoritmu popsaného v [20]. Tato metoda generování trojúhelníkové sít byla použita také v pvodním algoritmu popsaném v [6]. Funkce pebírá dva parametry. Prvním z nich je objekt CDT popsanývýše. Druhým je objekt tídy Criteria (souást CGAL), který uruje tvarová kritéria výsledné sít: délkové kritérium a B kritérium (viz kapitola 3.3.3). 4.3 Im plem entace vizualizaního prostedí Vizualizaní prostedí Saddle je naimplementováno pomocí OpenGL a nadstavby GLUT. Knihovna je nejprve inicializována. Poté je vytvoeno okno, jemužjsou piazeny parametry (velikost a pozice okna, double buffering). GLUT pracuje s tzv. callback obslužnými funkcemi, které je ped použitím nutné zaregistrovat. Poté program vstupuje do obslužné smyky, kde oekává událost vyvolanou nap. klávesnicí, myší, nebo zmnou velikosti okna. Píslušná callback funkce je zavolána a dojde k obsluze události. Saddle používá okno s dvojitým bufferováním obrazu a barevným modelem RGBA. Jsou registrovány callback funkce pro zmnu velikosti okna (reshape), pro zobrazení (display) a pro obsluhu myši (mouse, motion) a klávesnice (special, keybord). Každá

-27-

z callback funkcí umožuje použití ve dvou módech:2D a 3D. Na základ píznaku módu jsou volány specifické obslužné funkce (nap. Mouse2D() nebo Mouse3D()). Pomocí tchto funkcí jsou mnny transformaní matice souadnic. Ve 2D módu je možné zobrazovaný objekt posouvat a mnit mítko. Ve 3D módu je možné model posouvat, mnit mítko a natáet ve dvou osách. Po obsluze událostí myši nebo klávesnice (mouse, motion, special, keyboard) je volána funkce display() pro pekreslení okna. Ta volá píslušnou funkci módu (Display2D(), Display3D()), v níž jsou transformaní matice aplikovány na zobrazovaný model. M odel je vykreslen do zadního bufferu a buffery jsou prohozeny, Je tak zajištn plynulý chod obrazu pi posouvání a otáení modelu. (ovládání viz.Uživatelská píruka) 4.4 Im plem entace tíd M ezi základní pravidla objektov orientovaného programování patí zapouzdení (encapsulation). Zapouzdení je použito pro všechny tídy algoritmu. Všechny lenské promnné dané tídy (s výjimkou statických) jsou definovány jako soukromé. Píslušné hodnoty jsou nastavovány, je-li to žádoucí, pomocí lenských pístupových metod nazývaných gettery a settery. Každá modifikovatelná promnná tak má metody getA(), která vrací hodnotu promnné A a setA(val), která ji nastavuje na hodnotu val. 4. 4. 1 Tída Point2D a PointS Tídy Point2D a PointS jsou implementací stejnojmenných návrhových tíd. Petížená metoda distanceFromPoint2D() tídy Point2D dostává jako parametr bu ukazatel na objekt Point2D, nebo souadnice x, y. Pomocí vzorce odvozeného z Pythagorovy vty vrací vzdálenost obou bod. Pro specifické úlohy, byla vytvoena také metoda squareDistance(), která vrací druhou mocninu vzdálenosti. Pi výpotu pesné vzdálenosti je nutné poítat odmocninu, což je pomrn nároná a pomalá operace.Vynecháním výpotu odmocniny tak dochází k potenciálnímu urychlení algoritmu, zejména v místech, kde není nutné znát absolutní vzdálenosti, ale staí pouze jejich pomr. Tída PointS je rozšíením tídy Point2D. Obsahuje dv lenské promnné typu ukazatel na PointS: pNearestPointAtCplus a pNearestPointAtCminus. Ukazatel pNearestPointAtCplus uruje nejbližší bod nejbližší vrstevnice a pNearestPointAtCminus udává nejbližší body druhé sousední vrstevnice (viz kapitola 3.3.5). Pomocí tchto ukazatel jsou získávány údaje potebné pro výpoet výšky (v pípad bod ležících mimo vrstevnice) nebo svahu (v pípad bod ležících na vrstevnicích). Funkce computeSlope() a computeHeight() využívají pro výpoet postupy popsanév kapitole 3.3.6 a 3.3.7. Pibyla metoda normalize(), která pepoítává normálovývektor na jednotkovou délku.

-28-

4.4.2 Tída Contour Tída Contour v podstat pekrývá STL sekvenní seznam list, který umožuje ukládat ukazatele na typ PointS. Každý ukládaný PointS by tak ml být vytvoen pomocí operátoru new. Tída navíc obsahuje iterátor, který umožuje snazší procházení seznamu bod. Pohyb iterátoru zajišují metody forward() a backward(), které iterátorem pohybují o jednu pozici v daném smru. Je také možné iterátory pesunout na zaátek nebo konec seznamu bod pomocí metod begin() a end().
lenská promnná Identificator je identifikátor vrstevnice (bod PointS obsahuje také identifikátor vrstevnice, je-li toto íslo shodné s identifikátorem vrstevnice, patí bod dané vrstevnici. Je-li íslo -1 nebo -5 leží bod mimo vrstevnici). Hodnota identifikátoru vrstevnice je udržována pomocí statické promnné. Pokud je vytvoena nová instance tídy Contour, je tato promnná inkrementována a její hodnota je použita jako identifikátor. Pro manipulaci se seznamem jsou ureny metody popFront(), která vyjme první prvek ze seznamu a vrátí na nj ukazatel, a addPoint(), která pidá zadaný ukazatel na bod do seznamu a zárove bodu nastaví identifikátor vrstevnice na svoji hodnotu. Pomocí výše zmínného iterátoru lze k položkám seznamu pistupovat prostednictvím funkce getPoint(). Tato funkce vrací ukazatel na bod, na njž práv ukazuje iterátor. Funkce getPoint() mže dostat nepovinný parametr ITERATOR_FORWARD nebo ITERATOR_BACKWARD, který po navrácení ukazatele na bod z funkce iterátor inkrementuje nebo dekrementuje. Samozejmostí je zjištní potu bod tvoících vrstevnici metodou size(). Tída obsahuje dv metody na kompletní úpravu obsahu: metody reducePoints(), která odstrauje pebytené body, a thickPoints(), která nové body pidává, pokud v daném míst chybí. Metoda reducePoints() dostává jako parametr vzdálenostní kritérium k. Jsou ovovány všechny trojice za sebou jdoucích bod a, b, c. Jestliže |ac| < k a zárove |ab| + |bc| < |ac|*1.01, je bod b vypuštn. Tato metoda zajišuje, že budou odstranny body, které tvoí pouze velmi tupé úhly (viz abc Obr. 16 vlevo` v rovnostranném trojúhelníku vzorec odpovídá úhlu pibližn 165°), nebo které tvoí poruchu hladkosti, jak naznaují body cde. Metoda thickPoints() provuje vždy dvojice bod. Jestliže jejich vzdálenost je vtší než dané kritérium, je hrana spojující tyto dva body rozdlena novým bodem (viz Obr. 16 vpravo)

Obr. 16. Metody reduceMap() a thickMap().

-29-

4.4.3 TídyPoint3D,Vector3D a Triangle Návrhové tídy Vector3D a Point3D mají stejné lenské promnné, a tedy také stejné pístupové metody. Akoliv jsou sémanticky rozdílné, je možné je implementovat pouze jednou tídou. Byla tedy vytvoena tída Point3D a alias Vector3D pomocí typedef Point3D Vector3D;

Krom pístupových metod obsahuje tída Point3D metodu dumpCoords(), jejíž parametem je výstupní stream. Do tohoto streamu jsou vypsány souadnice oddlené árkou. Této metody je využíváno zejména pi zápisu do VRML souboru. Píslušný stream je z funkce také navrácen. Tída Triangle obsahuje ti ukazatele na typ Point3D. Podobn jako tída Point3D obsahuje Triangle metodu dumpIndexes(), která také dostává jako parametr výstupní proud (anglicky stream). Do tohoto proudu jsou zapsány indexy bod daného trojúhelníku oddlené árkou. Stream je opt navrácen z funkce. Metoda je využita pi zápisu do VRML souboru.
lenské promnné index u tídy Point3D (a Vector3D) jsou vlastn jedinené identifikátory každého bodu a odpovídají pozici v kontejneru v nadazené tíd Model. Instance tídy Vector3D jsou normály rekonstruované plochy v bod, který má stejný indexjako daný vektor. 4.4.4 Tída M odel Model je realizací stejnojmenné návrhové tídy. Kolekce trojúhelník, bod a normál jsou implementovány STL kontejnery vector, které umožují rychlé pidávání prvk nakonec seznamu a rychlý náhodný pístup k prvkm pomocí indexu (a operátoru []). Tmto vlastnostem jsou pizpsobeny lenské metody addPoint(), addNormal() a addTriangle(), které pidají píslušný element na konec kontejneru a vrátí jeho index, a metody getPoint(), getVector() a getTrinagle(), které pebírají jako argument index a vracejí požadovaný element. Objekty normál píslušející k bodm jsou pidávány ve stejném poadí jako objekty bod. Mají tak stejné indexy do kontejner, ehož je využito pi generování OpenGL a VRML model funkcemi genDisplayList() a saveVRML(). Metoda saveVRML() otvírá soubor s daným jménem. Zapisuje píslušné hlaviky formátu. Poté jsou procházeny postupn kontejnery bod, normál a trojúhelník a na každém elementu je volána funkce dumpCoords() (resp. dumpIndexes()) s daným výstupním streamem. Metoda genDisplayList() vytváí OpenGL displaylist (viz[4]), pomocí nhož lze kompletní model vykreslit jediným voláním funkce a není tedy nutné procházet všechny hodnoty modelu pi každém pekreslení obrazovky. Procházením všech trojúhelník jsou získány souadnice vrchol a jejich indexy, pomocí nichž se pistupuje do kontejneru normál. Hodnoty jsou pak zapsány do displaylistu. Barva každého bodu je odvozená od jeho výšky. Model je tak pokryt barevnou výškovou mapou, v níž zelená

-30-

barva znaí nízké polohy, tmav ervená vysoké polohy a ostatní výšky jsou plynulým pechodem mezi tmito barvami. 4.4.5 Tída M ap Tída Map je realizací stejnojmenné návrhové tídy. Kolekce vrstevnic je implementována STL kontejnerem set, uchovávajícím ukazatele na píslušné vrstevnice vytvoené operátorem new. Pro snazší pístup k prvkm je stejn jako u tídy Contour pidán iterátor procházející kontejner a k nmu pístupové metody beginContourIterator() a endContourIterator(). Obdobou metody getPoint() u Contour tídy je zde metoda getContour(). Metoda contourCount() pak vrací poet vrstevnic. Množina bod ležících mimo vrstevnice není nutná, nebo tato informace je udržována v lenské struktue CDT (Constrained Delaunay Trinagulation), z knihovny CGAL a umožuje vytváet trojúhelníkovou sí. Novým atributem je také STL kontejner list contourVertex, který obsahuje všechny body vrstevnic (PointS) obalené objektem vertex_handle. Tída vertex_handle je souástí CDT a umožuje aplikaci grafových algoritm. Tohoto seznamu je užito v úloze popsané v kapitole 4.5.6. Tída má také ti privátní metody. První z nich je metoda quantil(), která pomáhá urit velikost trojúhelníkové sít výpotem kvantilu. Uvnit funkce je vytvoeno dynamické pole, do kterého jsou postupn zadávány vzdálenosti dvou následujících bod všech vrstevnic. Pole je poté seazeno za pomocí funkce sort(), kterou nabízí knihovna STL. Zadaný parametr je procento (desetinné íslo z rozsahu 0 – 100), jehož hodnota je poté pepoítána na absolutní podle velikosti daného pole. Získaná hodnota je pak indexem do seazeného pole a hodnota z nj je vrácena z funkce. Takto získané íslo je používáno jako délkový parametr triangulace (voláno quantil(99)) a pi volání metody reduceMap() (voláno quantil(75)). Další privátní metoda prearange() zajišuje pepis vrstevnic do struktury CDT. Jsou procházeny všechny body všech vrstevnic a jsou zapisovány do CDT zárove jsou zadávány omezující hrany (hrany které se v triangulaci musí prosadit) jako spojnice dvou za sebou jdoucích bod na vrstevnici. Metoda také napluje pomocný seznam contourVertex, nebo zde jsou vertex_handle vytváeny. Privátní metoda updateMeshInfo() se volá po provedení triangulace. Tato metoda zadává správné hodnoty index a identifikátor vrstevnic u bod, které byly nov vytvoeny. Pro potebu vyznait vrstevnice vznikla metoda displayContours(), která všechny vrstevnice vykresluje jako polyline a ukládá do displaylistu, jehož íslo je z funkce navráceno. Displaylist generuje i metoda displayFrame(), která vykreslí hranice mapy. Ostatní metody tídy reprezentující kroky algoritmu jsou popsány v následující kapitole

-31-

4.5

Implementace krok algoritmu

Jednotlivé kroky algoritmu odpovídají tabulce. Vznikly pouze dv varianty funkce pro natení vstupních dat a dv varianty tvorby trojúhelníkové sít. Pidán byl krok tvorby modelu poadí
innost 1 Natení vrstevnic 2 Úprava vrstevnic 3 Triangulace 4 5 6 7 8 9 10

Hledání nových bod vrstevnic Hledání nejbližších bod vrstevnic Výpoet svah Výpoet výšek Vyhlazení chyb Výpoet normál Tvorba modelu Tab. 3.

Jméno funkce loadContours() loadFromPolish() thickMap()/reduceMap() generateMesh() genSparseMesh() findNewContourPoints() clipPoints() countSlopes() countHeights() pickPoints() countNormal() generateModel

Postup algoritmu z hlediska implementace

4.5.1 Natení vrstevnic Podle požadavk má být vstup zadán bu kartézskými souadnicemi, nebo polish formátem GPS dat. Každému zpsobu tak odpovídá jedna z uvedených funkcí. Metoda loadContours() dostává jako parametr název index souboru. Její chování odpovídá popisu v odstavci 3.4.2. Každá petená trojice ísel vytváí objekt PointS, který je umístn do píslušné vrstevnice Contour. Metoda loadFormPolish() je pizpsobená k tení dat z GPS polish formátu. V tle metody je volán „parser“, obsahující základní gramatiku pro naítání topologických vrstevnic. Naítaná data ukazují polohu ve stupních (severní šíka a východní délka) a výšku ve stopách. Proto jsou nejprve nahrávány do zvláštních kontejner, které jsou souástí parseru. Polish formát asto nezapisuje jednu vrstevnici jako celek, ale rozkouskuje ji do nkolika menších. Natené vrstevnice jsou tedy procházeny a kontrolovány, zda na sebe nenavazují pes krajní body. Pokud se nkde krajní body rovnají, jsou pomocí tohoto bodu spojeny. Zabraní se tak duplicitám, které by mohly být nepíjemné pi tvorb sít. Následn jsou vrstevnice pepisovány do kartézských souadnic. Pi pepisu je nutné dát pozor zejména na hodnotu východní (resp. západní) délky. Její absolutní hodnota (nap. v metrech) se mní v závislosti na šíce (severní/jižní). Rozdíl úhlu 1° délky na rovníku (0° severní šíky) odpovídá pibližn dvojnásobku vzdálenosti pi stejném úhlu v
eské republice (pibližn 50°severní šíky). Vzhledem k absolutním rozmrm mapy je teba také pizpsobit výšky vrstevnic.

-32-

4.5.2 Úprava Vrstevnic Tyto metody mohou mít velký vliv na výslednou hustotu sít. Metoda reduceMap() volá metodu quantil(75), od níž dostává délkové kritérium. Tento parametr je podstoupen všem vrstevnicím a jejich metodám reducePoints(). Obdobn metoda thickMap() volá pro každou vrstevnici metodu thickContours(). Zde funkce quantil() nemá píliš smysl. Jako parametr je proto použita hodnota 1/128 šíky mapy. 4.5.3 Triangulace Triangulace je velmi kritická ást algoritmu. Pokud zadané vrstevnice neodpovídají všem požadavkm, dochází k nestandardnímu ukonení v této fázi. Nabídnuty jsou dv metody tvorby triangulaní sít: generateMesh() a genSparseMesh(). Metody se liší v parametrech funkce refine_Delaunay_mesh_2(cdt,Criteria()). Metoda generateMesh() nejprve volá privátní metodu prearange(), která zajistí naplnní potebné struktury CDT body a hranami. Následuje volání funkce refine_Delaunay_mesh_2(cdt,Criteria()). Úhlové a délkové kritérium je reprezentované objektem Criteria. Délkové kritérium je získané z metody quantil(99). Je tak zajištno vytváení sít, která nebude mít žádnou hranu delší než získaná hodnota. Protože jsou vkládány povinné hrany, je nutné, aby se žádné dv neprotínaly. Nkterá vstupní data tuto podmínku nemusí splovat. Proto byla zavedena metoda genSparseMesh(), která volá funkci refine_Delaunay_mesh_2() pouze s úhlovým kritériem. Volání této funkce pedchází naplnní CDT, ovšem pouze body. Povinné hrany jsou vynechány. V míst kde nejsou vrstevnice tak mže být sí tvoena i pomrn velkými trojúhelníky. V místech bod vrstevnic není vytvoena povinná hrana a mže tak dojít k chybám v kroku 4.5.5. Kvalita sít je tak celkov nižší, umožuje ale tvorbu terénu z dat která porušují podmínky kladené na vrstevnice. Pokud generování sít skoní úspšn, je v tle generateMesh() (resp. genSparseMesh()) volána metoda, která zajistí doplnní potebných informací bodm, vznikajícím v prbhu triangulace (updateMeshInfo()). 4.5.4 Hledání novýchbod
vrstevnic Protože triangulaní algoritmus mže v pípad poteby rozdlit omezené hrany novým bodem, je zde možnost, že budou rozdleny práv hrany vrstevnic. Tyto body musejí být nalezeny a registrovány jako body píslušných vrstevnic. Pokud by tak uinno nebylo, docházelo by k poruchám hladkosti na vrstevnicích. Pro hledání tchto bod byl zvolen algoritmus umlé inteligence A*(A-star–viz 3.3.4). Prioritní fronta algoritmu je implementována pomocí prority_queue z STL knihovny. Jejími prvky jsou objekty nové tídy QueNode, která obsahuje ukazatel na daný bod a hodnotu priority. Prioritou je v tomto pípad souet tverc vzdáleností. Použity jsou kvadráty vzdáleností, nebo není teba znát pesné vzdálenosti, ale pouze jejich pomr, zda jsou vtší nebo menší. Pi výpotu ze souadnic tak odpadá pomalá operace odmocniny (je použita metoda squareDistance()).

-33-

Oproti standardnímu azení priority_queue, je teba adit od nejmenšího po nejvtší. STL prioritní fronta užívá pro zaazování operátoru „<“Pro tídu QueNode byl petížen s opaným chováním – je-li prvek napravo menší než prvek nalevo, je výrok vyhodnocen jako pravdivý. 4.5.5 Hledání nejbl ižších bod
vrstevnic Funkce clipPoints() hledá pro všechny body nejbližší body sousedních vrstevnic. Pro každý bod funkce spouští dvojnásobný UCF algoritmus (viz 3.3.5). Tento algoritmus stejn jako A* vyžaduje prioritní frontu. Použita je opt STL priority_queue s elementy QueNode. V prioritní front (open seznam) jsou seazeny body podle kvadrát vzdálenosti, expandován je opt nejbližší. Kvadráty vzdáleností jsou opt poítány pomocí squaredDistance() Algoritmus probíhá, dokud nenalezne nejbližší bod, který má jiný identifikátor vrstevnice (pokud bod leží mimo vrstevnici má identifikátor -1. Pokud leží na vrstevnici, je identifikátor kladné íslo), je tento uzel vyjmut z fronty (není expandován!) a pro startovací bod nastaven jako pNearestPointAtCplus. Následn je testováno, zda nalezený bod je od startovacího ve vtší vzdálenosti, než okraj mapy. Pokud ano, znamená to, že se startovací bod nachází pi okraji mapy, bude muset být extrapolován a proto mu není nastavena hodnota pNearestPointAtCminus. Pokud je vzdálenost v poádku algoritmus jsou všechny pomocné seznamy (open prioritní fronta, closed seznam) pedány další ásti, která s tmito frontami opt provádí UCF. Nyní ovšem nesmí být identifikátor vrstevnice roven ani startovací hodnot, ani -1 (bod mimo vrstevnice), ani hodnot bodu pNearestPointAtCplus. První nalezený bod na vrstevnici, který vyhovuje dané podmínce je pro daný bod uložen do pNearestPointAtCminus. Pokud ovšem dojde k vyprázdnní prioritní fronty, aniž by byl bod jiné vrstevnice nalezen, nachází se startovací bod uvnit uzavené vrstevnice, Bude jej nutné tedy extrapolovat. A pNearestPointAtCminus opt není nastavena. Nakonec jsou pomocné seznamy vymazány a algoritmus je spuštn pro nový startovací bod. 4.5.6 Výpoet svah
a výšek Implementan tyto metody odpovídají metodám popsaným v analýze. Metoda countSlopes() prochází všechny body vrstevnic, jejichž seznam je udržován v pomocném seznamu list tídy Map (viz 4.4.5) a pro každý bod PointS, jež je souástí objektu vertex_handle, volá píslušnou metodu countSlope(). Metod countSlopes() musí pedcházet metoda clipPoints(), která naplní body potebnými daty. Následuje volání metody countHeights(), tato metoda prochází všechny body struktury CDT a pro každý, který má identifikátor vrstevnice -1 (neleží na vrstevnici) volá metodu countHeights(). 4.5.7 Vyhlazení chyb

-34-

Vyhlazení chyb provádí metoda pickPoints(), která pomocí cirkulátoru prochází všechny incidující body. Jestliže mají všichni pímí sousedé uzlu výšku vtší (resp. menší) než daný bod, je výška daného bodu nastavena na vážený prmr výšek okolních bod. Váha každého souseda je dána tvercem jeho vzdálenosti (poítána metodou squaredDistance()). Poté je již volána metoda countNormals(). 4.5.8 Výpoet normál Pro každý bod jsou prohledáváni jeho nejbližší sousedé, opt pomocí cirkulátor. Protože cirkulátory prochází sousedy postupn v protismru hodinových ruiek, tvoí dva za sebou následující body spolen s daným bodem trojúhelník, pro njž mže být normálový vektor snadno vypoítán vektorovým násobkem. Takto jsou zjištny všechny normály, z nichž je vytvoen prmrný vektor. Danému bodu jsou poté tyto hodnoty vektoru nastaveny a je volána metoda normalize(), která upraví vektor na jednotkový. 4.5.9 Tvorba modelu Pro tvorbu modelu se pedpokládá, že výpoet terénu je již hotový. V tle funkce generateModel3D() je pomocí operátoru new vytvoen nový objekt typu Model. Poté jsou procházeny všechny body struktury CDT. Z jejich souadnic jsou vytvoeny body Point3D a z normálových vektor objekty Vector3D. Tyto jsou uloženy do píslušných kontejner objektu Model. Ukládající metody vracejí indexy do kontejner. Hodnoty tchto index musí být shodné a danému bodu ve struktue CDT je tento index nastaven také. Po pepsání všech bod a normál jsou procházeny všechny trojúhelníky (faces). Každý trojúhelník obsahuje ukazatel na ti body. Každý bod byl v pedchozím kroku nov indexován, a hodnota indexu tak odpovídá pístupovému indexu v kontejnerech objektu Model. Z píslušného kontejneru jsou tedy získány ukazatele na dané body typu Point3D a jsou piazeny vytvoenému Trojúhelníku. Trojúhelník je uložen do kontejneru tídy Model. Ukazatel na vytvoený model je navrácen z funkce. Po skonení metody generateModel3D() mže být objekt tídy Map smazán. V pamti tak zstane pouze objekt Model, který není tak pamov nároný.

-35-

-36-

5 Testování Algoritmus byl testován v programu nazvaném Saddle(sedlo), které bylo pro tento úel vytvoené. Testováno bylo nkolik map popsaných v kapitole 5.1. V následující kapitole jsou rekonstruované terény srovnávány z hlediska nkolika parametr (poet vrstevnic, vstupních bod, poet bod po triangulaci atd.) Jsou diskutovány chyby a pipojeny ukázky rekonstruovaných povrch. 5.1 Testované Mapy K dispozici byly ti modely zadané kartézskými souadnicemi (Svržno, Hosttice, Mount St. Helens) a tyi mapy GPS polish formátu (Hrubý Jeseník, Dlouhé strán v Jeseníkách, Orlické Hory a Pec pod Snžkou). 5.1.1 M ount St. Helens Hora Sv. Heleny je stratovulkán nacházející se v USA, ve stát W ashington. Mapa vrstevnic zachycuje kráter ped erupcí v kvtnu roku 1980, kdy byl z velké ásti znien. Výbuch spoky je nejlépe zdokumentovanou erupcí vulkánu. Hora byla rekonstruována také v [6], byla proto vybrána pro porovnání s výsledkem pvodního algoritmu. 5.1.2 Svržno Svržno je obec poblíž msta Hostou v okrese Domažlice. Nedaleko se nachází
erný vrch s archeologickým nalezištm eneoletického výšinného sídlišt. Mapa Svržno zachycuje topologickou situaci okolí nalezišt. 5.1.3 Hostnice Hostnice jsou stejn jako Svržno výšinným eneoletickým sídlištm. Leží pibližn 3 km jihovýchodn od Svržna. Jedná se o tvercové sídlišt s kruhovými palisádami v nkolika adách. 5.1.4 HrubýJeseník Hrubý Jeseník je pohoí v severní ásti Moravy a Slezska s nejvyšší horou Pradd (1491 m. n. m.) Mapa zachycuje celé pohoí hrubého Jeseníku a ást pechodu do Nízkého Jeseníku na jihu a do Rychlebských hor na severu. 5.1.5 DlouhéStrán Dlouhé strán jsou peerpávací vodní elektrárna, jejíž horní nádrž byla vybudována srovnáním vrcholu stejnojmenné hory v Hrubém Jeseníku. Mapa zachycuje bezprostední okolí horní nádrže i údolní pehrady 5.1.6 OrlickéHory Pohoí lemující severní hranici s Polskem ve Východních
echách. Mapa popisuje okolí nejvyššího vrcholu –Velké Deštné (1115) a Skuhrova nad Blou. 5.1.7 Pecpod Snžkou Mapa popisuje ást Krkonoš jižn od nejvyšší hory Snžky (1602) v okolí letoviska Pec pod Snžkou. Nejvyšší hora na map není Snžka, ale Studniní Hora (1554).

-37-

5.2 Parametry testování Hlavním cílem algoritmu je vytvoit hladký povrch. Hladkost povrchu lze mit pomocí parametrické spojitosti (nap. C0, C1, C2,… ). Pro výpoet spojitosti musí být ovšem znám matematický popis funkce reprezentující povrch, což je pro povrch terénu velice obtížné. Možností je také zkoumat hladkost pouze lokáln –na malé ásti plochy. I tato varianta ovšem vyžaduje robustní matematický aparát. Zhodnocení hladkosti terénu je tedy ponecháno subjektivnímu dojmu. Dalším dležitým parametrem je pesnost rekonstruovaného povrchu. Tu mžeme posoudit pomocí odchylky výšky rekonstruovaného terénu v míst, kde jsou vrstevnice zadány (tedy je známa vstupní výška). V ideálním pípad leží vrstevnice pesn na povrchu rekonstruovaného terénu. Požadavkem na algoritmus bylo také docílit urité efektivity. Efektivita mže být mena asov, jako doba výpotu. Ta mže být ovšem na rzných PC sestavách rzná. K mení byla použita PC sestava: • procesor AMD Athlon 64, 2800+, • fyzická pam RAM 1.5GB DDR 400 • operaní systém W indows XP SP2 profesional (32bit) 5.3 Výsledky Použitím interpolaních a extrapolaních metod výpotu výšek v algoritmu je zarueno, že body, jejichž výška je známa ze vstupních dat, hodnotu své výšky nezmní. Všechny body vstupních dat tedy leží na povrchu rekonstruované krajiny. Vstupní data jsou zadávána jako lomené áry (polylines), jejichž body vznikly vzorkováním reálné vrstevnice. Pvodní tvar kivky se od lomené áry tedy liší a tím je také zpsobena chyba pesnosti (rozdíl ideální a vypoítané výšky). Tuto chybu lze zmenšit hustším vzorkováním vrstevnic, což se ovšem projeví na hustší síti a prodloužení doby výpotu. Pedpokládejme, že lomené áry na vstupu popisují reálné vrstevnice zcela pesn. Použitím metody generateMesh(), která v triangulaci prosazuje body i hrany vrstevnic, lze zaruit nulovou odchylku vypoítané výšky od ideální. Lomené áry vrstevnic se tak projeví na povrchu. U Metody genSparseMesh(), toto ovšem nelze zajistit.. Odchylku mohou zpsobit body, vznikající pi generování TIN v blízkosti pvodních hran. Jejich výška není stanovena výškou hrany, ale vypoítána z okolních vrstevnic. Nulovou odchylku lze zaruit pouze u bod tvoících vstupy. Doba výpotu se odvíjí od velikosti vstupních dat. V následující tabulce (Tab. 4) je zaznamenán poet vrstevnic a jejich bod (sloupec Mapa), v okamžiku ped aplikací triangulace (tedy po natení a úprav). Testovány byly ob varianty generování trojúhelníkové sít (viz 4.5.3). Sloupec ModelQ obsahuje poet bod a trojúhelník po triangulaci metodou generateMesh(), Sloupec Model S pak výsledky metody genSparseMesh(). Sloupec „typ“je oznaení typu vstupu: P = polish format;I= index (kartézské souadnice)

-38-

Tabulky Tab. 5 a Tab. 6 zaznamenávají pak dobu výpotu ástí algoritmu. Zpracovánívrstevnic zahrnuje natení vrstevnic a potebné úpravy (redukce, zahuštní) Triangulace je vlastní provedení metody generující trojúhelníkovou sí. Nejbližšíbodyje doba zpracování metody provádjící UCS prohledávání. Rekonstrukce povrchu zahrnuje metody výpotu hladkého povrchu (svahy na vrstevnicích, výšky bod, korekce chyb a výpoet normál). Generování modelu pak popisuje asovou náronost pevodu vypoítaných dat do objektu tídy Model. Všechny hodnoty jsou uvedené v sekundách. Mapa

typ

Mount St. Helens Svržno Hostnice Hrubý Jeseník Dlouhé Strán Orlické Hory Pec pod Snžkou Tab. 4.

I I I P P P P

Mapa vrstevnic 21 46 30 818 139 126 212

Model Q

Model S

bod

bod

trojúhelník

2130 6033 5716 88644 25559 20204 31850

9453 18547 12314 24116 13589 26759 nelze rekonstruovat 67228 133242 68231 135221 69758 138245

bod

trojúhelník

2701 12087 9065 101853 30166 27520 36389

5289 23687 17978 202191 59517 54256 71809

Vstupní data. P –polish formát vstupních dat;I–indexformát vstupních dat;Q –model rekonstruovaný metodou generateMesh(). S –model generovaný metodou genSparseMesh()

Mapa Q St. Helens Svržno Hosttice Hrubý Jeseník Dlouhé Strán Orlické Hory Pec pod Snžkou Tab. 5.

0.047 0.172 0.125 0.078 0.094 0.125

Nejbližší Rekonstrukce Generování body Celkem povrchu modelu vrstevnic

0.234 0.406 0.375 2.609 2.453 2.031

3.985 0.641 7.422 4.282 7.797 4.594

0.39 0.39 0.375 2.781 3.219 2.063

0 0.016 0.015 0.125 0.125 0.093

4.656 1.625 8.312 9.875 13.688 8.906

Doba výpotu pi triangulaci metodou generateMesh().
asy uvedeny v sekundách.

Mapa S St. Helens Svržno Hosttice Hrubý Jeseník Dlouhé Strán Orlické Hory Pec pod Snžkou Tab. 6.

Zpracování Triangulace vrstevnic

Zpracování Triangulace vrstevnic 0.047 0.172 0.125 0.891 0.063 0.078 0.125

Nejbližší Rekonstrukce Generování body Celkem povrchu modelu vrstevnic

0.031 0.328 0.203 3.922 0.984 0.625 0.797

0.125 0.609 0.39 1.437 0.75 1.0 0.75

0.031 0.406 0.188 1.281 0.406 0.515 0.359

Doba výpotu pi triangulaci metodou genSparseMesh().
asy uvedeny v sekundách.

-39-

0 0.016 0.016 0.157 0.047 0.032 0.047

0.234 1.531 0.922 7.688 2.25 2.25 2.078

Z uvedených dat je patrné, že tvorba kvalitní sít vyžaduje i nkolikanásobn delší as než varianta s jednoduchou sítí. Celkový as algoritmu ovšem nezávisí pouze na velikosti vstupních dat, ale také na rozložení vstupních bod a vrstevnic. Nevhodné rozložení mže mít za následek obtížnou konstrukci trojúhelníkové sít. Velké mezery mezi vrstevnicemi a požadavek na píliš hustou sí mže zpsobit dlouhé prohledávání UCS algoritmem. Tato situace nastává nap. U mapy Q –Hostnice. Mapu Hrubého Jeseníku se nepodailo rekonstruovat pomocí metody generateMesh(), nebo tato data porušují podmínky kladené na vrstevnice (prnik dvou hran). 5.4

Ukázky rekonstrukcí.

V nkterých místech rekonstruovaných povrch jsou patrné chyby. Chyby mohou vznikat v místech, kde je málo vstupních dat (vrstevnic). Tyto chyby vznikají zejména na okrajích mapy a mohou se projevit nap. jako schody na povrchu. Další chyby mohou být zpsobeny použitím metody genSparseMesh(), kdy hrany vrstevnic nemusí být souástí trojúhelníkové a v míst vrstevnic tak mohou vznikat vyvýšeniny, nebo prohlubn. Dalším problémem mže být vznik píliš velkých trojúhelník, na nichž se špatn odráží svtlo. 5.4.1 M ount St. Helens Mount St. Helens je zejména ukázkou rekonstrukce kráteru. Pomocí tohoto modelu je možné srovnat implementaci algoritmu s implementací reprezentovanou v [6].

Obr. 17. Mount St.Helens Nahoe: vrstevnice a fotografie hory;vlevo dole: model z [6], vpravo dole: rekonstruovaný VRML model

-40-

Kráter i svah byly rekonstruovány pomrn vrn. Porucha povrchu v levém dolním rohu je zpsobena extrapolací ze svah, kdy dv skupiny bod se ídí rznými hodnotami svahu s velkým rozdílem. 5.4.2 Hosttice Na této map se velice zeteln projevují chyby zpsobené malým množstvím dat u okraj mapy. Nedostatek vstupních dat je patrný na Obr. 18, v pravém horním rohu. Velká blízkost vrstevnic v pravé ásti zpsobila znané klesání svahu a tím pádem výška extrapolovaných míst smrem k okraji mapy pesáhla uritý povolený interval (1.5 násobek maximálního rozdílu výšek vrstevnic) a byla oezána na hraniní hodnotu tohoto intervalu.

Obr. 18. Hostetice Nahoe: Nákres terénu a palisád okolo sídlišt;vlevo: vstupní vrstevnice (ervený obdélník znaí hranice mapového výezu);vpravo: rekonstruovaný terén s výškovou mapou (nedostatek dat se projevuje v pravém horním rohu (svtle zelená barva), kde byla hodnota výšky omezena intervalem.)

5.4.3 Svržno Vrstevnice tohoto modelu jsou velice lenité – zaznamenávají drobné záhyby. Protože vrstevnice musí ležet na povrchu rekonstruovaného terénu, projevují se tyto záhyby také na rekonstruovaném povrchu, jak ukazuje Obr. 19. Pi zkoumání okraj modelu je v nkterých místech patrná schodovitost, jak naznauje Obr. 20, který je zárove ukázkou hladké rekonstrukce sedla mezi dvma vrcholy.

-41-

Obr. 19. Svržno Vlevo: vstupní data;vpavo: lenitost vrstevnic a její projevy v rekonstruovaném terénu.

Obr. 20. Rekonstrukce sedla mezi dvma vrcholy (na okraji mapy schodovitost terénu)

5.4.4 HrubýJeseník Hrany velmi hustých vrstevnic se v nkterých místech kíží. Je tedy nutné nepoužívat omezené hrany, což ovšem zpsobuje poruchy v místech, kudy vrstevnice prochází. Vznikají nové body, které nejsou vrstevnici piazeny a jejich výška je poítána z nesprávných hodnot. Vznikají tak ve svazích jednobodové hrbolky i prohlubn, které ovšem nejsou upravitelné metodou pickPoints(). Vznik takové poruchy je naznaen na Obr. 21 vpravo.
erven jsou naznaené hrany, které bod použije pro nalezení nejbližších bod vrstevnic. Hrany jsou stejn dlouhé, což znamená, že vrstevnice na bod

-42-

psobí pibližn stejnou vahou (jako by ležela uprosted mezi nimi). Z obrázku je ovšem patrné, že ve skutenosti leží blíže k vrstevnici vpravo.

Obr. 21. Hrubý Jeseník - chyby na povrchu terénu. Vlevo: kížení vrstevnic –chyba vstupu;uprosted: porucha zpsobená nepoužitím omezených hran;vpravo: trojúhelníková sí v míst chyby obrázku uprosted.

Obr. 22. Hrubý Jeseník (celkový pohled) teka oznauje vrchol Praddu

5.4.5 DlouhéStrán Na povrchu tohoto terénu se do znané míry projevil zpsob zadání vrstevnic. Vrstevnic je mnoho, ovšem jsou tvoeny málo body. Vznikají tak dlouhé rovné úseky a hrany, které se projevují i na svazích. (viz Obr. 23.) 5.4.6 OrlickéHory Z hlediska rekonstrukce jsou velmi zdailá dobe patrná údolí ek Zdobnice a Blé v podhí jižn od Velké Deštné. (viz Obr. 24.) 5.4.7 PecPod Snžkou Mapa zachycuje lenitý terén v okolí Pece pod Snžkou, Obího Dolu a
erné Hory a je ukázkou velmi povedené rekonstrukce. (viz Obr. 25.)

-43-

Obr. 23. Dlouhé Strán

Obr. 24. Orlické Hory. V pravé ásti patrné údolí eky Zdobné, v levé pak pítok eky Blé.

-44-

Obr. 25. Pec pod Snžkou

-45-

-46-

6 Záv
r 6.1 Zhodnocení Cílem práce bylo nalezení a implementace algoritmu ešícího problém rekonstrukce terénu z vrstevnic. Zdailá metoda byla nalezena ve lánku [6]. Tato metoda se stala základem pro implementovaný algoritmus, jenž byl rozšíen v použitelnosti na vrstevnice, které netvoí uzavené kivky. Souástí ešení se stala také možnost uložit model jako VRML dokument. Výsledný povrch je závislý na kvalit vstupních dat. Byly vytvoeny dva zpsoby volání triangulaní funkce. První zpsob vyžaduje, aby se hrany polylines reprezentujících vrstevnice vzájemn neprotínaly. Tato omezení dovolují vytvoit kvalitní hustou sí, jejímž výsledkem je hladký terén s minimálním potem chyb. Druhá varianta umožuje rekonstrukci z vrstevnic, které se vzájemn protínají. Výsledný terén ovšem zaznamenává poruchy v místech pvodních hran vrstevnic, kde vznikají prohlubn nebo hrbolky zpsobené nesprávným nalezením soused okolních vrstevnic. Nejproblémovjšími místy rekonstrukce jsou okraje map. Vrstevnice, které koní na okraji map zde zpsobují schodovitost terénu (viz Obr. 19). Naopak, pokud pi okraji vrstevnice chybí, dochází k extrapolaci z nejbližší vrstevnice a hodnoty svahu na ni. Mže tak vzniknout extrémn prudký okraj, který musí být omezen uritým intervalem, jako nap. u Hosttic (viz Obr. 18). Ipes tyto chyby vytváí algoritmus pomrn vrné modely reálných terén. 6.2 Dalšípráce Algoritmus je možno vylepšit v mnoha ohledech. Nejvýznamnjším vylepšením by mohla být úprava vrstevnic. Algoritmus by mohl kontrolovat a opravovat intersekce hran polylines (vrstevnic), ímž by mohla být použita pouze první varianta triangulaního algoritmu komentovaná níže. Zmnna by mohla být také metoda zahušující vrstevnice. Souasná metoda používá plení stávajících hran lomené áry (polyline). Vylepšením by mohlo být kladení nových bod na kubickou kivku interpolující pvodní body. Tento zpsob by ovšem byl výpoetn, a tedy i asov náronjší. Zásadním vylepšením by mohla být implementace vlastního triangulaního algoritmu, který by byl specializován na použité datové struktury vrstevnic a bod. Výsledkem by byla nezávislost celého algoritmu na pomrn mohutné knihovn CGAL. Dalším vylepšením mže být nap. aplikace textur na vytvoený model i možnost jeho uložení ve více formátech.

-47-

-48-

7 Použitá literatura [1]

J. Žára, B. Beneš, J. Sochor, P. Felkel. Modernípoítaovágrafika. Computer Press Brno, 2004.

[2]

J. Liberty. Naute se C++ za 21 dní.Computer Press Praha, 2002.

[3]

Nicolai M Josuttis. C++ Standardníknihovna a STL. Computer Press, a.s. Brno, 2005.

[4]

D. Shreiner, M. W oo, J. Neider, T. Davis. OpenGL prvodce programátora. Computer Press, a.s. Brno, 2006.

[5]

J. Žára. VRML 97Laskavýprvodce virtuálnímisvty. Computer Press, Brno, 1999

[6]

K. Horman, S. Spinello, P. Schröder. C1-continuousTerrainReconstructionfrom Sparse Contours. Vision Modellingand Visualisation (conference), München, 2003.

[7]

M. Ruth. Applicationof2D methodsforscattered data approximationto geophysicaldata sets. Conf. SampTa’95 Riga/Litva,1995.

[8]

J. Chai, T. Miyoshi, E. Nakamae. ContourInterpolationand Surface ReconstructionofSmoothTerrainModels. IEEE Visualization’98 (conference), Durham (N. Carolina) 1998.

[9]

D. Thibault, C.M. Gold. TerrainReconstructionfrom ContoursbySkeleton Construction. GeoInformatica (journal), Netherlands (december) 2000.

[10] T. Dvoák, A. Herout. Výpoetvýškovémapyzvrstevnic vnaskenovanémap. FIT VUT Brno, 2005. [11] M.
ernohorský. Zobrazování3D modeluvýškopisnýchvektorovýchmappro naviganísystém GPS.
VUT FEL (bakaláská práce), 2007. [12] J. Vank. Zobrazováníterénu. Univerzita Hradec Králové (diplomová práce), 2003 [13] K. Fujimura, E. Kuo. Shape Reconstructionfrom ContoursusingIsotopic Deformation. Graphical Models and Image Processing(journal), May1999. [14] L. D. Cohen, E. Bardinet, N. Ayache. Surface ReconstructionusingActive Contour Models. SPIE’93 Conference on Geometric Methods in Computer Vision, San Diego/Kalifornia, 1993. [15] O. Nilsson, D.Breen, K. Museth. Surface ReconstructionVia Contour Metamorphosis:AnEulerianApproachWithLagrangianParticle Tracking,IEEE Visualisation, Minneapolis 2005 [16] J. Marker, I. Braude, K. Museth, D. Breen. Contour-Based Surface Reconstruction usingImplicitCurve Fitti ng,and Distance Field Filteringand Interpolation. The Eurographics Association, Proc. Int. W orkshop on Volume Graphics, Boston 2006. [17] D. Eberly. LeastSquaresFittingofData. (www.geometrictools.com) 2001. [18] Geopaintingweb. http://www.geopainting.com/2008

-49-

[19] CGAL online manual.www.cgal.org/Manual/.Release 3.3.1. 25 August 2007. [20] J.R. Shewchuk. DelaunayRefinementAlgorithmsforTriangularMesh Generation.paper 2001, University of California, Barkley [21] Specifikace Polish Formátu GPS map http://www.cgpsmapper.com , July 2005

-50-

A – Seznam zkratek (Seznam zkratek použitých v textu práce) • GIS • TIN • OpenGL • • • • • • • • • • • •

•

GeographicInformation System –Geografický informaní systém. Triangulated irregular network –Nepravidelná trojúhelníková sí. Open Graphics Li brary – Grafická knihovna – standardizované multiplatformní rozhraní. VRM L VirtualRealityM odelingLanguage–Jazyk pro modelování virtuální reality. HTM L HyperText M arkup Language–hypertextový znakovací jazyk. BFS Breadth First Search –Algoritmus prohledávání do šíky. UCS Uniform Cost Search – Metoda prohledávání stejných cen (verze algoritmu prohledávání do šíky). STL Standard Template Library – C++ knihovna šablon standardních kontejner a algoritm. GLUT OpenGL UtilityToolkit –Okenní systém pro zobrazování OpenGL. CGAL Computational Geometry Algorithms Library – C++ knihovna algoritm a datových struktur výpoetní geometrie. BOOST Boost C++ libraries –Open Source knihovny rozšiující funkcionalitu C++ a STL. PSLG Planar Stright Line Graph – Graf planárních úseek. (žádné dv úseky se neprotínají). CDT Constrained Delaunay Triangulation – Omezená Delaunayova Triangulace (speciální pípad Delaunayovy triangulace). GPS GlobalPositioningSystem –Naviganí systém. 0 1 2 C ,C ,C Písmeno C znamená continuity – tedy spojitost funkce.
íslo v horním indexu znaí stupe spojitosti. Stupe 0 znamená spojitost v každém bod funkce. Stupe 1 znaí spojitost první derivace dané funkce (v každém bod lze jednoznan urit smrnici teny – zleva i zprava), spojitost 2 znaí spojitost druhé derivace funkce. W GS-84 –W orld GeodeticSystém –souadnicový systém z roku 1984 využívaný v GPS navigaci. Poloha bodu na povrchu zemkoule je urena dvma úhly (zempisnou šíkou a délkou).

-51-

-52-

B – Uživatelská píruka Uživatelská píruka vizualizaního prostedí Saddle Saddleje jednoduché prostedí pro vizuální prezentaci implementovaného algoritmu. Prostedí umožuje jednoduchou manipulaci s vytvoeným modelem, zobrazení vrstevnic a trojúhelníkové sít a to jak ve 2D prostoru, tak v kompletním 3D.

Vstupy Naítaná data jsou dvojího druhu: Polish formát GPS map (viz 3.4.3) má vtšinou koncovku .mp. U kartézského vstupu (index) není koncovka souboru pesn specifikována, užívána je ovšem .txt. Po spuštní programu je uživatel vyzván k zadání vstupních parametr: název vstupního souboru, název výstupního souboru, druh vstupního souboru a druh triangulaní funkce. Parametry je také možné zadávat pomocí píkazové ádky pi spouštní programu. Píkazová ádka má tvar: saddle.exe input output p|i s|q saddle.exe –jméno spouštného souboru input – název souboru se vstupními daty (koncovka mže být libovolná – ukázková data užívají koncovky .txt a .mp) • output – název výstupního souboru VRML (koncovka .wrl je standardní koncovkou formátu VRML) • p| i –volba druhu vstupního souboru.
p -soubor input bude oteven jako Polish Format GPS map.
i-oekává se vstup indexformátu (viz 3.4). • s| q –volba použité triangulaní funkce.
s –tvorba ídké trojúhelníkové sít (vrstevnice tvoeny body).
q – tvorba kvalitní síe trojúhelník (vrstevnice tvoeny body a hranami (viz 4.5.3). Pi spouštní musí být zadány všechny tyi hodnoty.

• •

Ovládání Po zadání vstupních parametr probíhá vlastní algoritmus a mení asu spuštní. Po úspšné rekonstrukci povrchu jsou data pevedena do objektu tídy Model. Ten je následn uložen do souboru VRML. Do konzole jsou vypsány hodnoty mení asu a je spuštno okno a v nm je vykreslena 2D výšková mapa a vrstevnice. K dispozici jsou dva módy – pro prohlížení ve 2D a 3D. Mód 2D umožuje pohled z nadhledu – tedy vykreslení výškové mapy (pop. vrstevnic). 3D mód umožuje natáení modelu o 360° kolem vertikální osy modelu. Vertikální osu modelu je také možné naklánt o úhel až 90° ve smru k pozorovateli. Program se ovládá prostednictvím klávesnice a myši.

-53-

Klávesnice: • s –zobrazí model jako neprhledný povrch • w –zobrazí model jako trojúhelníkovou sí • šipky – posouvají modelem doleva, doprava, nahoru, nebo dolu vzhledem k pozorovateli. (Ovládání pomocí šipek je k dispozici pouze ve 3D módu) M yš: • levétlaítko – ve spojení s pohybem myši – ve 2D módu posouvá celou mapu ve smru pohybu myši. Ve 3D módu levé tlaítko + pohyb doleva (resp. doprava) znamenají otáení modelu kolem vertikální osy modelu v daném smru. Pohyb myši nahoru (resp. dolu) ve spojení s levým tlaítkem myši pak ve 3D módu naklání vertikální osu modelu. • Prostední tlaítko (scroll)– ve spojení s pohybem myši nahoru (resp. dolu) zobrazovaný model piblíží (resp. oddálí). • Pravétlaítko –pravé tlaítko vyvolá menu s dalšími volbami ovládání.

Menu pravého tlaítka: Menu obsahuje 5 položek, které mní svj popisek v závislosti na módu zobrazení: • Contours ON /Contours OFF –zapne (resp. vypne) zobrazení vrstevnic. • M odelOn /M odelOFF – zapne (resp. vypne) zobrazení povrchu modelu, popípad trojúhelníkové sít • show 3D model/show 2D map – pokud je práv aktivní 2D mód, položka show 3D model pepne do 3D módu. Pokud je aktivní 3D mód, položka show 2D map pepne do 2D módu. • reset – položka reset vrací sted modelu do stedu obrazovky a nastavuje zoom na implicitní hodnotu. Ve 2D módu je tak mapa vrácena zcela do pvodní polohy. Ve 3D módu je model vrácen na sted, ovšem natoení je zachováno. Reset také zachovává nastavení zapnutá pomocí „Contours On / OFF“, „Model On/OFF“ položek a pomocí klávesnic w resp. s. • exit –položka ukoní proces programu Saddle

-54-

C – Obsah CD Piložené CD obsahuje 6 následujících složek: • input_data - testovací vstupní data pro algoritmus (mapy: svrzno.txt, hostetice.txt, helen.txt, Hruby_Jesenik.mp, Dlouhe_Strane.mp, Orlicke_Hory.mp, Pec_pod_Snezkou.mp • libraries - instalace podprných knihoven BOOST, CGAL a GLUT • models - VRML modely generované bhem testování algoritmu. (každý model má v názvu souboru píznak _s nebo _q – podle použité funkce pro generování TIN. • run_wi n32 - Zkompilovaná verze programu spustitelná ve 32 bitovém operaním systému W indows XP. • src - Soubory obsahující zdrojový kód algoritmu a programu Saddle • text - Elektronická podoba textu bakaláské práce

-55-