Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky

Za´padocˇeska´ univerzita v Plzni Fakulta aplikovany´ch veˇd Katedra informatiky a vy´pocˇetnı´ techniky

´ PRA ´ CE DIPLOMOVA

Plzenˇ, 2006

Prˇemysl Zı´tka

Za´padocˇeska´ univerzita v Plzni Fakulta aplikovany´ch veˇd Katedra informatiky a vy´pocˇetnı´ techniky

Diplomova´ pra´ce

Hierarchicke´ povrchove´ modely

Plzenˇ, 2006

Prˇemysl Zı´tka

Anotace Hierarchicke´ a adaptivnı´ prˇ´ıstupy k rˇadeˇ proble´mu˚ jsou v poslednı´ dobeˇ v pocˇ´ıtacˇove´ grafice cˇasto diskutovany´mi te´maty. Zejme´na se objevujı´ v souvislosti s reprezentacı´ prostoru nebo v souvislosti s pojmem Level of Detail (LOD) prˇi zobrazova´nı´ dat s velky´m mnozˇstvı´m detailu˚. Tato pra´ce zkouma´ mozˇnosti vyuzˇitı´ hierarchie a adaptivity v problematice hleda´nı´ cest. Zaby´va´ se prˇ´ıpravou a testova´nı´m 3D adaptivnı´ mrˇ´ızˇky pro algoritmus vyhleda´va´nı´ cesty v potencia´lneˇ nezna´me´m a dynamicke´m prostrˇedı´. Cı´lem je poskytnout navenek grafovou strukturu bodu˚, ktera´ umozˇnı´ snadne´ pla´nova´nı´ cesty. Vnitrˇnı´ funkcˇnost grafove´ struktury vsˇak zajisˇt’uje dynamicka´ adaptivnı´ mrˇ´ızˇka, prˇina´sˇejı´cı´ vy´znamnou u´sporu vy´pocˇetnı´ch prostrˇedku˚.

Abstract Hierarchical and adaptive approaches to a variety of problems are at present often discussed topics in computer graphics. They appear mainly in relation to space representation and in detailed model visualization, known as Level of Detail (LOD). This work focuses on possibilities of use of hierarchy and adaptivity in the area of path finding. The work concerns with creating 3-dimensional adaptive grid used in pathfinding in possibly unknown and dynamic space. The goal is to provide output graph structure of points, easy to use for path-finding algorithms. Under the graph structure, however, a dynamic adaptive grid provides more cost-effective approach to computer’s resources.

Prohla´sˇenı´

Prohlasˇuji, zˇe jsem diplomovou pra´ci vypracoval samostatneˇ a vy´hradneˇ s pouzˇitı´m uvedeny´ch citovany´ch pramenu˚.

V Plzni dne 21. srpna 2006

Prˇemysl Zı´tka

Podeˇkova´nı´ Ra´d bych podeˇkoval zejme´na Bc. Petru Brozˇovi, se ktery´m jsme na projektu spolupracovali. Jeho vy´borna´ bakala´rˇska´ pra´ce mi umozˇnila mnou zpracovany´ syste´m nejen rea´lneˇ pouzˇ´ıt, ale i otestovat a demonstrovat. Stejneˇ bych velice ra´d podeˇkoval i vedoucı´ diplomove´ pra´ce panı´ Doc. Dr. Ing. Ivaneˇ Kolingerove´ za odbornou pomoc a uzˇitecˇne´ rady a podneˇtne´ prˇipomı´nky prˇi zpracova´nı´ me´ diplomove´ pra´ce. Nemensˇ´ı dı´k na´lezˇ´ı take´ vsˇem teˇm, kterˇ´ı se mnou beˇhem mnoha meˇsı´cu˚, ve ktery´ch jsem diplomovou pra´ci vytva´rˇel, meˇli te´meˇrˇ bezmeznou trpeˇlivost, me´ rodineˇ i prˇa´telu˚m za jejich podporu a pochopenı´ v pru˚beˇhu cele´ho me´ho studia.

Obsah Anotace

2

Abstract

2

Podeˇkova´nı´

4

Obsah

4

1

´ vod U

2

Adaptivita a hierarchie 2.1 Adaptivita . . . . . . . . . . . . . . . . . . . . . . 2.2 Hierarchie . . . . . . . . . . . . . . . . . . . . . .

10 10 14

3

Pouzˇı´vana´ deˇlenı´ prostoru 3.1 Mrˇ´ızˇky . . . . . . . . . 3.2 BSP Tree . . . . . . . . 3.3 Voronoiovy diagramy 3.4 kD Tree . . . . . . . . . 3.5 Quadtree a Octtree . .

17 17 18 18 19 20

4

8

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

Stanovenı´ u´kolu˚ pra´ce 4.1 Adaptivnı´ datova´ struktura pro pla´nova´nı´ v dynamicke´m prostrˇedı´ . . . . . . . . . . . 4.1.1 Pu˚vodnı´ u´loha pla´nova´nı´ cest . . . . 4.1.2 Pozˇadovana´ rozsˇ´ırˇenı´ . . . . . . . . 4.1.3 Vy´sledne´ rozdeˇlenı´ a rˇesˇenı´ u´lohy . 5

. . . . .

. . . . .

. . . . .

22 cest . . . . . . . . . . . .

22 22 23 24

´ loha modifikace povrchu . . . . . . . . . . . . . U

25

5

Adaptivnı´ mrˇı´zˇka 5.1 Role adaptivnı´ mrˇ´ızˇky prˇi hleda´nı´ cesty . . . . . 5.2 Vrcholy a jejich sousednost . . . . . . . . . . . . .

26 26 27

6

Objektoveˇ orientovana´ analy´za 6.1 Na´vrh rozhranı´ . . . . . . . 6.1.1 Interface IEngram . . 6.1.2 Interface IGraph . . 6.2 Na´vrh trˇ´ıd . . . . . . . . . . 6.2.1 Trˇ´ıda Mesh . . . . . 6.2.2 Trˇ´ıda Cluster . . . . 6.2.3 Trˇ´ıda Engram . . . .

31 31 32 32 33 33 34 35

4.2

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

7

Implementace 36 7.1 Pouzˇite´ programovacı´ prostrˇedky . . . . . . . . . 37 7.2 Pozˇadavky na prˇeklad a spousˇteˇnı´ dodane´ aplikace 38

8

Testova´nı´ 8.1 Podmı´nky pru˚beˇhu testu˚ . . . . . . . . . . . . . . 8.2 Testovacı´ sce´ny . . . . . . . . . . . . . . . . . . . 8.3 Provedene´ testy a jejich vy´sledky . . . . . . . . . 8.3.1 Rychlost operacı´ split a merge v za´vislosti na povolene´ hloubce u´rovneˇ . . . . . . . 8.3.2 Cˇasovy´ vy´voj mnozˇstvı´ buneˇk sı´teˇ . . . . 8.3.3 Rychlost adaptace sı´teˇ . . . . . . . . . . . 8.3.4 Spotrˇeba pameˇti . . . . . . . . . . . . . . 8.3.5 Za´vislost na pocˇtu prˇeka´zˇek . . . . . . . . 8.3.6 Porovna´nı´ adaptivnı´ a pravidelne´ mrˇ´ızˇky 8.3.7 Pocˇet buneˇk sı´teˇ v za´vislosti na rozlozˇenı´ prˇeka´zˇek a hrozeb . . . . . . . . . . . . .

9

Modifikace povrchu 9.1 Potrˇebna´ rozsˇ´ırˇenı´ a u´pravy . . . . . . . . . . . .

6

39 39 40 41 41 43 44 45 45 47 49 51 51

9.2

Testova´nı´ . . . . . . . . . . . . . . . . . . . . . . .

52

10 Za´veˇr

54

Literatura

57

Prˇı´loha A: Class diagramy

57

Prˇı´loha B: Path planning in combined 3D grid and graph environment 60 Prˇı´loha C: Path planning in dynamic environment using an adaptive mesh 61

7

Kapitola 1 ´ vod U Pocˇ´ıtacˇova´ grafika a vizualizace dat je v dnesˇnı´ dobeˇ vy´znamny´m oborem informatiky a s rostoucı´m vy´konem a dostupnostı´ pocˇ´ıtacˇu˚ v ru˚zny´ch oborech roste i potrˇeba zobrazovat mnoho rozlicˇny´ch modelu˚ a vizualizovat sta´le veˇtsˇ´ı mnozˇstvı´ informacı´. Pocˇ´ıtacˇova´ grafika se tak sta´va´ nepostradatelny´m prostrˇednı´kem mezi cˇloveˇkem a jeho pocˇ´ıtacˇovy´mi daty. Vy´voj modernı´ch metod pro pocˇ´ıtacˇovou grafiku proto nezaosta´va´. Ke v poslednı´ dobeˇ cˇasto zminˇovany´m a take´ aplikovany´m postupu˚m patrˇ´ı mimo jine´ adaptivnı´ algoritmy ve vsˇech svy´ch podoba´ch. Cı´lem te´to diplomove´ pra´ce je prozkoumat neˇktere´ beˇzˇne´ adaptivnı´ postupy a algoritmy, jejich mozˇnosti a jejich aplikace. Pu˚vodnı´ te´ma se meˇlo ty´kat hierarchie pro povrchove´ modely, ovsˇem na zˇa´dost vedoucı´ jsem se zaby´val objemovou hierarchiı´ pro beˇzˇ´ıcı´ projekt pla´nova´nı´ cest, ktery´ navazuje na pra´ci Dr. Gavrilove´ z University of Calgary v Kanadeˇ. Dalsˇ´ım u´kolem te´to pra´ce bylo oveˇrˇenı´ mozˇnosti uzˇitı´ za prˇedchozı´m u´cˇelem vytvorˇene´ struktury pro jiny´ projekt, konkre´tneˇ interaktivnı´ modifikaci povrchu na´strojem VR, v na´vaznosti na pra´ci Dr. Benesˇe z Purdue University ve Spojeny´ch Sta´tech. Kapitola 2 te´to pra´ce se veˇnuje nejprve objasneˇnı´ pojmu˚ adaptivita a hierarchie a da´le pak zpu˚sobu˚m jejich vyuzˇitı´ v ra´mci oboru pocˇ´ıtacˇove´ grafiky. Na´sledujı´cı´ kapitola 3 pak zminˇuje neˇktere´ beˇzˇneˇ pouzˇ´ıvane´ adaptivnı´ 8

metody. Po teoreticke´m u´vodu na´sleduje v kapitole 4 prˇedstavenı´ u´lohy hleda´nı´ ´ cˇelem pra´ce cest v potencia´lneˇ nezna´me´m a dynamicke´m 3D prostrˇedı´. U je proka´zat, zda je vyuzˇitı´ adaptivnı´ho deˇlenı´ trˇ´ırozmeˇrne´ho prostoru pro takovou u´lohu vhodne´ a zda mu˚zˇe prˇine´st vy´znamne´ urychlenı´ cˇi u´sporu prostrˇedku˚. Na´sledneˇ je popsa´na u´loha modifikace povrchu, ktera´ ma´ oveˇrˇit pouzˇitelnost navrzˇene´ho syste´mu i v jiny´ch souvislostech, nezˇ pro ktere´ byl pu˚vodneˇ vytvorˇen. Kapitola 5 popisuje dı´lcˇ´ı proble´my, jejich mozˇna´ rˇesˇenı´ a vy´sledna´ rˇesˇenı´. V kapitole 6 na´sleduje dekompozice a popis na´vrhu jednotlivy´ch rozhranı´ a trˇ´ıd a kapitola 7 uva´dı´ detaily o implementaci, pouzˇity´ch prostrˇedcı´ch a pozˇadavcı´ch pro prˇeklad a spusˇteˇnı´ aplikace. Kapitola 8 obsahuje informace o navrzˇeny´ch a provedeny´ch testech, o podmı´nka´ch testova´nı´ a o meˇrˇenı´ jednotlivy´ch aspektu˚ ovlivnˇujı´cı´ch vy´kon vy´sledne´ aplikace. Kapitola 9 se zaby´va´ zmeˇnami a rozsˇ´ırˇenı´mi provedeny´mi pro u´lohu modifikace povrchu a testy na te´to u´loze provedeny´mi. Za´veˇrecˇne´ zhodnocenı´ v kapitole 10 pak shrnuje klady i za´pory zvolene´ho rˇesˇenı´ a prˇedkla´da´ mozˇne´ u´pravy a dodatecˇna´ rozsˇ´ırˇenı´ pro budoucı´ vy´voj.

9

Kapitola 2 Adaptivita a hierarchie 2.1

Adaptivita

Adaptivita je prˇ´ıstup prˇina´sˇejı´cı´ rozumny´ kompromis mezi potrˇebou pocˇ´ıtacˇove´ reprezentace zachytit pozˇadovane´ mnozˇstvı´ detailu˚ (typicky´ pozˇadavek fotorealisticˇnosti sce´ny a modelu˚ v nı´ zobrazeny´ch) na jedne´ straneˇ a rychlostı´ a pameˇt’ovy´mi na´roky na straneˇ druhe´. S rostoucı´mi na´roky na detailnost totizˇ take´ naru˚stajı´ na´roky na pameˇt’ovy´ prostor i vy´pocˇetnı´ sı´lu. Nemusı´ se prˇitom nutneˇ jednat jenom o vy´pocˇetnı´ sı´lu potrˇebnou k zobrazova´nı´ vy´sledne´ sce´ny. Je trˇeba si uveˇdomit, zˇe se vsˇemi objekty se mu˚zˇe podle typu u´lohy prova´deˇt mnohem vı´ce operacı´, at’ uzˇ graficke´ transformace nebo trˇeba vy´pocˇty ru˚zny´ch fyzika´lnı´ch velicˇin cˇi aplikace vlivu˚ pu˚sobenı´ modelovane´ho prostrˇedı´. Rostoucı´ pozˇadavky na realisticˇnost si vsˇak pouzˇ´ıva´nı´ dat s velky´m mnozˇstvı´m detailu˚ vynucujı´. V naproste´ veˇtsˇineˇ prˇ´ıpadu˚ reprezentujeme takova´ data troju´helnı´kovy´mi sı´teˇmi. Sı´teˇ zı´ska´va´me prˇeva´zˇneˇ tesalacı´ matematicky definovany´ch ploch modelu nebo triangulacı´ bodu˚ zı´skany´ch skenova´nı´m fyzicky´ch objektu˚. V obou prˇ´ıpadech vznikajı´ velmi detailnı´ sı´teˇ a jejich ukla´da´nı´ na disk, vykreslova´nı´ cˇi prˇenos po komunikacˇnı´ lince jsou natolik na´rocˇne´, zˇe je cele´ problematice veˇnova´na vy´znamna´ pozornost. 10

[1] uva´dı´ neˇkolik za´kladnı´ch prˇ´ıstupu˚ a smeˇru˚ vy´voje k rˇesˇenı´ teˇchto proble´mu˚: Mesh simplification (zjednodusˇenı´, decimace sı´teˇ): Sı´teˇ zı´skane´ vy´sˇe popsany´mi zpu˚soby nejsou v prˇeva´zˇne´ veˇtsˇineˇ prˇ´ıpadu˚ nijak optimalizova´ny pro efektivnı´ vykreslova´nı´ a mohou by´t aproximova´ny pro lidske´ oko neodlisˇitelnou sı´tı´ obsahujı´cı´ podstatneˇ mensˇ´ı pocˇet troju´helnı´ku˚. Level-of-detail (LOD) approximation (u´rovneˇ detailu˚ aproximujı´cı´ pu˚vodnı´ model): Beˇzˇny´m postupem by´va´ definova´nı´ neˇkolik verzı´ modelu s ru˚znou u´rovnı´ detailu˚ (s ru˚zny´m pocˇtem troju´helnı´ku˚ tvorˇ´ıcı´ch sı´t’ modelu). Detailnı´ slozˇita´ sı´t’ je pouzˇita, pokud se objekt nacha´zı´ v blı´zkosti pozorovatele, jednodusˇsˇ´ı sı´teˇ pak s rostoucı´ vzda´lenostı´. Jelikozˇ prˇepı´na´nı´ mezi jednotlivy´mi u´rovneˇmi detailu˚ mu˚zˇe ve´st k pozorovatelne´mu problika´va´nı´, rozumny´m prˇ´ıstupem je konstruovat plynule´ prˇechody, geomorfy, mezi sı´teˇmi ru˚zny´ch rozlisˇenı´. Progressive transmission (postupny´ prˇenos): Prˇi prˇenosu troju´helnı´kove´ sı´teˇ komunikacˇnı´ linkou ocˇeka´va´me, zˇe budeme mı´t velmi brzy po zacˇa´tku prˇenosu k dispozici alesponˇ ma´lo detailnı´ model a spolecˇneˇ s prˇicha´zejı´cı´m tokem dat bude na´sledneˇ docha´zet k postupne´mu zkvalitnˇova´nı´ zobrazene´ sı´teˇ. Mozˇny´ prˇ´ıstup je naprˇ´ıklad posı´lat postupneˇ jednotlive´ u´rovneˇ detailu˚ – od nejhorsˇ´ı azˇ po nejkvalitneˇjsˇ´ı. Mesh compression (komprese sı´teˇ): Komprese je jiny´m prˇ´ıstupem k rˇesˇenı´ proble´mu minimalizace prostoru potrˇebne´ho pro ulozˇenı´ troju´helnı´kove´ sı´teˇ. Na rozdı´l od decimace se nezameˇrˇuje na zmensˇenı´ pocˇtu troju´helnı´ku˚, ale na optimalizaci zpu˚sobu jejich ukla´da´nı´. Selective refinement (selektivnı´ zjemnˇova´nı´): Kazˇda´ z troju´helnı´kovy´ch sı´tı´ jednotlivy´ch LOD reprezentacı´ prˇedstavuje model v urcˇite´ jednotne´ u´rovni detailu˚. Cˇasto je vy´hodne´ adaptovat u´rovenˇ zjemneˇnı´ odlisˇneˇ v jednotlivy´ch oblastech te´hozˇ modelu podle toho, kde jsou a nejsou detaily trˇeba.

11

Obra´zek 2.1: Skalnı´ u´tvar Uluru. Adaptivitu lze obecneˇ cha´pat jako prˇizpu˚sobova´nı´ dat vy´konu pocˇ´ıtacˇe. V oblasti pocˇ´ıtacˇove´ grafiky ma´ toto prˇizpu˚sobova´nı´ svu˚j geometricky´ vy´znam. V takove´m pojetı´ pak vyuzˇ´ıva´me toho, zˇe cˇasto nenı´ trˇeba vzorkovat prostor cˇi model na vsˇech mı´stech stejneˇ, cozˇ lze vy´hodneˇ vyuzˇ´ıt zejme´na ve trˇech mı´rneˇ odlisˇny´ch situacı´ch, ktere´ se pokusı´m vysveˇtlit jednoduchy´m prˇ´ıkladem: V Austra´lii nalezneme pomeˇrneˇ zna´my´ a jedinecˇny´ skalnı´ u´tvar jme´nem Uluru. Jedna´ se o horu, ktera´ znenada´nı´ vystupuje ze zemeˇ uprostrˇed rozlehle´ pousˇtnı´ roviny (Obra´zek 2.1). Prˇi u´loze zmapovat okolnı´ pousˇt’ rychle dojdeme k za´veˇru, zˇe zdaleka nenı´ vhodne´ kvu˚li jedne´ ska´le vzorkovat vy´sˇkova´ meˇrˇenı´ rˇekneˇme naprˇ´ıklad s krokem jednoho metru po cele´ rozsa´hle´ plosˇe pousˇteˇ, tvorˇ´ıcı´ jednu velkou rovinu. To je trˇeba v prˇ´ıpadeˇ jedine´ vy´jimky a tou je pra´veˇ na´sˇ skalnı´ u´tvar. Pouzˇijeme tedy adaptivnı´ rˇesˇenı´ – vy´sˇkova´ meˇrˇenı´ vlastnı´ pousˇteˇ mu˚zˇeme vzorkovat naprˇ´ıklad po deseti kilometrech, bezprostrˇednı´ okolı´ skalnı´ho u´tvaru pak naprˇ´ıklad po deseti metrech a vlastnı´ ska´lu po pu˚l metru. Adaptivitu tedy aplikujeme tak, zˇe na rozdı´l od pravidelne´ mrˇ´ızˇky mapy prova´dı´me podrobne´ meˇrˇenı´ pouze v oblastech, kde detaily fakticky existujı´. Do druhe´ situace se snadno dostaneme jako autorˇi aplikace, ktera´ bude umozˇnˇovat zmapovany´m tere´nem procha´zet. Jizˇ vı´me, jaky´m zpu˚sobem mohla by´t mapa navzorkova´na a ulozˇena. Prˇi vizualizaci skalnı´ho u´tvaru v nasˇ´ı aplikaci jisteˇ uvı´12

ta´me mozˇnost si jej podrobneˇ prohle´dnout. Ale ma´ se v pameˇti prˇi zobrazova´nı´ v plny´ch detailech udrzˇovat i od pozorovatele odvra´cena´ strana u´tvaru, nebo u´tvar cely´ v okamzˇiku, kdy je od neˇj pozorovatel odvra´cen nebo vy´razneˇ vzda´len? Samozrˇejmeˇ je vy´hodneˇjsˇ´ı vyuzˇ´ıt adaptivitu i zde a pouzˇ´ıvat plne´ detaily ne ve vsˇech mı´stech, ale kde nejen fakticky existujı´, ale tam, kde jsou i prakticky potrˇeba Trˇetı´ situace je pak zpu˚sob, jaky´m v nasˇ´ı aplikaci zobrazı´me okolı´ skalnı´ho u´tvaru. Beˇhem vizualizace s vy´hodou adaptivitu pu˚vodnı´ho meˇrˇenı´ vyuzˇijeme a zobrazujeme pousˇt’jen neˇkolika ma´lo troju´helnı´ky, jako rovinu. Prˇesto mu˚zˇe vzniknout potrˇeba v okolı´ pozorovatele umeˇle troju´helnı´ky rozdeˇlit a umozˇnit naprˇ´ıklad drobne´ zvlneˇnı´ pousˇteˇ nebo otisky stop pozorovatele pro lepsˇ´ı vizua´lnı´ dojem z aplikace. Adaptivitu tedy nasazujeme v mı´stech, kde detaily fakticky neexistujı´ a sami je umeˇle dotva´rˇ´ıme. Adaptivita umozˇnˇuje veˇnovat dostatek prostrˇedku˚ na oblasti, kde jsou detaily pozˇadova´ny, naopak prostrˇedky usˇetrˇit v oblastech, na ktere´ takovy´ pozˇadavek v dany´ okamzˇik nema´me a prˇ´ıpadneˇ vyuzˇ´ıt volne´ vy´pocˇetnı´ sı´ly k dotvorˇenı´ detailu˚ v mı´stech, kde v datech ani rea´lneˇ nejsou. Pozˇadavek na detailnost mu˚zˇe by´t da´n naprˇ´ıklad smeˇrem, ktery´m se ve virtua´lnı´m sveˇteˇ dı´va´ kamera, a vzda´lenostı´, do ktere´ majı´ detaily smysl. Udrzˇovat v pameˇti modely v takovy´ch detailech, zˇe je zobrazovacı´ zarˇ´ızenı´ za dany´ch podmı´nek ani nedoka´zˇe vykreslit, totizˇ cˇasto smysl mı´t nemusı´. Stejneˇ tak nemusı´ mı´t smysl ani s takto zbytecˇneˇ detailnı´mi objekty prova´deˇt vsˇechny dalsˇ´ı prˇ´ıpadne´ operace. Daleko vy´hodneˇjsˇ´ı je upravit detailnost podle aktua´lnı´ch podmı´nek a pozˇadavku˚ a teprve s vy´sledkem pak da´le pracovat. Krite´ria pro rozhodova´nı´ o potrˇebeˇ detailu˚ mohou by´t na za´kladeˇ zada´nı´ u´lohy cˇi typu proble´mu pomeˇrneˇ rozlicˇna´. Velmi cˇasto se jedna´ o krite´ria souvisejı´cı´ se zobrazova´nı´m, zejme´na jde o smeˇr pohledu a vzda´lenost objektu od pozorovatele, ovsˇem pohled na cely´ proble´m mu˚zˇe by´t i komplexneˇjsˇ´ı. Do detailu˚ se problematice adaptivity v za´vislosti na vizua´lnı´ch krite´riı´ch veˇnuje [2]. 13

Adaptivnı´ algoritmy se vyuzˇ´ıvajı´ zejme´na ve dvou oblastech pocˇ´ıtacˇove´ grafiky, a to v oblasti povrchovy´ch modelu˚ a pro adaptivnı´ deˇlenı´ prostoru. Stejneˇ tak se pouzˇ´ıvajı´ dva rozdı´lne´ prˇ´ıstupy. Jednı´m je v okamzˇiku potrˇeby pominout detaily v cˇa´stech cˇi oblastech, kde nejsou trˇeba. Adaptova´nı´m pak rozumı´me jeho jake´si „zhrubova´nı´ “ a pomı´jenı´ detailu˚. Druhy´ postup je v podstateˇ opacˇny´. Oblast za´jmu je deˇlena na mensˇ´ı bunˇky sı´teˇ. Adaptova´nı´m tedy naopak „zjemnˇujeme“ a snazˇ´ıme se detaily v oblasti za´jmu zprˇ´ıstupnit.

2.2

Hierarchie

Zatı´mco pojem adaptivita v pocˇ´ıtacˇove´ grafice vyjadrˇuje vy´sˇe popsanou schopnost algoritmu prˇizpu˚sobit se datu˚m, pojem hierarchie popisuje zpu˚sob prˇ´ıstupu k te´to schopnosti adaptivity. Pokud si prˇedstavı´me naprˇ´ıklad zobrazova´nı´ modelu, pak prˇi adaptivnı´m prˇ´ıstupu je mozˇno model zobrazit jak v u´plne´m detailnı´m provedenı´ (za odpovı´dajı´cı´ spotrˇeby vy´pocˇetnı´ch prostrˇedku˚), tak i v jeho nejhrubsˇ´ıch rysech (naopak vy´znamna´ u´spora pameˇti i vy´konu). Lze ovsˇem zobrazit i mnoho ru˚zny´ch mezikroku˚ mezi teˇmito dveˇma hranicˇnı´mi stavy. Kazˇdy´ z takove´ rˇady stavu˚ pak nazveme jinou u´rovnı´ detailu˚ - zaveden je anglicky´ pojem Level of Detail (LOD). Tyto u´rovneˇ lze snadno (naprˇ´ıklad podle pocˇtu zobrazeny´ch troju´helnı´ku˚) serˇadit od nejdetailneˇjsˇ´ıho po nejme´neˇ detailnı´, cˇ´ımzˇ definujeme jejich hierarchii. Kazˇda´ u´rovenˇ prˇina´sˇ´ı oproti svojı´ prˇedchu˚dkyni vı´ce detailu˚ a objekt se beˇhem pru˚chodu u´rovneˇmi sta´va´ postupneˇ komplexneˇjsˇ´ım. V rozhodovacı´m algoritmu se pak podle dane´ho krite´ria zvolı´, kterou u´rovenˇ pouzˇ´ıt, prˇ´ıpadneˇ se zvolı´ vhodna´ kombinace neˇkolika u´rovnı´. Tedy naprˇ´ıklad zˇe pozˇadavky na nejblizˇsˇ´ı modely ve sce´neˇ budou zpracova´va´ny v plny´ch detailech, objekty da´le od kamery jen v polovicˇnı´ch a objekty daleko od kamery jen v hruby´ch rysech. Nebo lze kombinovat neˇkolik ru˚zny´ch u´rovnı´ na jedine´m modelu. V nejmensˇ´ı vzda´lenosti od kamery budou pouzˇity plne´ detaily, v oblastech od kamery vzda´leneˇjsˇ´ıch detaily polovicˇnı´ a v mı´stech kamerˇe skryty´ch (naprˇ´ıklad odvra´cena´ strana

14

objektu) pak jen v hruby´ch rysech. Neˇktere´ metody, naprˇ´ıklad pouzˇita´ a pozdeˇji v kapitole 3.5 popsana´ metoda deˇlenı´ prostoru pomocı´ octtree, kde jednotlive´ u´rovneˇ detailu˚ vlastneˇ odpovı´dajı´ jednotlivy´m u´rovnı´m stromove´ struktury, vedou na hierarchii prˇ´ımo. Obecneˇ existujı´ dva prˇ´ıstupy, jak s adaptivitou a hierarchiı´ pracovat. Nazveˇme je pro nasˇe potrˇeby offline a online prˇ´ıstup. U offline prˇ´ıstupu se jednotlive´ u´rovneˇ detailu˚ prˇipravı´ v ra´mci prˇedzpracova´nı´ prˇedem, aplikaci takove´ho postupu uva´dı´ naprˇ´ıklad [3]. Algoritmy na decimaci, ktere´ se o snı´zˇenı´ pocˇtu troju´helnı´ku˚, a tedy i snı´zˇenı´ u´rovneˇ detailu˚ starajı´, mohou by´t komplikovane´ a cˇasoveˇ na´rocˇne´, zejme´na pokud je kladen du˚raz na maxima´lnı´ vizua´lnı´ kvalitu a veˇrnost i me´neˇ detailnı´ch modelu˚. V naproste´ veˇtsˇineˇ prˇ´ıpadu˚ je proto vy´hodne´ prove´st decimaci prˇedem a za chodu jizˇ jen pouzˇ´ıvat prˇipravene´ modely s ru˚zny´mi u´rovneˇmi detailu˚. V jednom „objektu“ pak nalezneme naprˇ. hned neˇkolik jeho modelu˚, se ktery´mi pak na´sledneˇ algoritmy pracujı´. [1] nabı´zı´ alternativnı´ rˇesˇenı´, kdy je ulozˇena nejhrubsˇ´ı sı´t’ a se´rie inkrementa´lnı´ch operacı´ postupneˇ tuto sı´t’zkvalitnˇujı´cı´ch. Zrˇejme´ vy´hody jsou zejme´na prˇi prˇenosu modelu pomalou linkou, kdy v u´vodu se prˇevede a je okamzˇiteˇ k dispozici alesponˇ hruby´ model a ten je na´sledneˇ prˇicha´zejı´cı´m proudem inkrementa´lnı´ch zmeˇn zkvalitnˇova´n. Za´rovenˇ je snadne´ definovat tzv. geomorfy (geomorph), cozˇ jsou plynule´ prˇechody mezi jednotlivy´mi definovany´mi u´rovneˇmi detailu˚. Geomorfem se stane definovana´ sekvence inkrementa´lnı´ch vylepsˇenı´ sı´teˇ, ktera´ vede od jedne´ u´rovneˇ detailu˚ ke druhe´. Vyuzˇitı´m geomorfu˚ se podstatneˇ zvy´sˇ´ı vizua´lnı´ kvalita LOD rˇesˇenı´, nebot’se zabra´nı´ skokovy´m zmeˇna´m a problika´va´nı´ modelu, na ktere´ je lidske´ oko vy´razneˇ citlive´. Jako online prˇ´ıstup popisuji variantu, kdy se adaptivita aplikuje azˇ za vlastnı´ho beˇhu programu. Z mnoha du˚vodu˚ mu˚zˇe by´t nezˇa´doucı´ nebo prˇ´ımo nemozˇne´ si potrˇebne´ u´rovneˇ prˇipravit v prˇedzpracova´nı´. V takove´m prˇ´ıpadeˇ je pak trˇeba volit rozumny´ kompromis mezi kvalitou vy´sledku 15

a rychlostı´ cele´ adaptace zohlednˇujı´cı´ pozˇadavky konkre´tnı´ u´lohy. Obecneˇ samozrˇejmeˇ platı´, zˇe adaptivita by za cenu komplikovaneˇjsˇ´ı implementace meˇla prˇine´st bud’to na´ru˚st kvality detailu˚ prˇi zachova´nı´ doby operacı´, nebo cˇasovou u´sporu prˇi zachova´nı´ kvality detailu˚. Prˇ´ıpadneˇ rozumny´ kompromis mezi kvalitou a rychlostı´. Prˇ´ıpad, kdy pouzˇitı´ adaptivnı´ch algoritmu˚ povede ke zpomalenı´ prˇi zhorsˇenı´ kvality detailu˚, nebo i jejı´ho zachova´nı´, na´s tak jasneˇ informuje o proble´mu. Bud’to byl adaptivnı´ algoritmus sˇpatneˇ zvolen cˇi naimplementova´n, nebo se pro danou u´lohu adaptivnı´ prˇ´ıstup nemusı´ vu˚bec hodit. To je vzˇdy trˇeba zva´zˇit.

16

Kapitola 3 Pouzˇı´vana´ deˇlenı´ prostoru 3.1

Mrˇı´zˇky

Deˇlenı´ prostoru pravidelnou mrˇ´ızˇkou je zrˇejmeˇ nejjednodusˇsˇ´ı z mozˇny´ch zpu˚sobu˚. Karte´zska´ mrˇ´ızˇka (krok mrˇ´ızˇky je ve vsˇech smeˇrech stejny´, bunˇky tvorˇ´ı krychle) s sebou prˇina´sˇ´ı vy´znamne´ vy´hody – poloha vrcholu mrˇ´ızˇky je da´na prˇ´ımo jeho indexy a stejneˇ tak i sousedy ve vsˇech smeˇrech lze urcˇit inkrementacı´ cˇi dekrementacı´ patrˇicˇne´ho indexu. Da´le mu˚zˇe by´t mrˇ´ızˇka pravidelna´ (v kazˇde´m smeˇru je velikost kroku definova´na zvla´sˇt’, bunˇky tvorˇ´ı obecneˇ kva´dry), pravou´hla´ (promeˇnliva´ velikost kroku v jednotlivy´ch osa´ch), cˇi strukturovana´ (bunˇky majı´ tvar zdeformovany´ch kva´dru˚). Vsˇechny tyto varianty pracujı´ s topologicky usporˇa´dany´mi vrcholy. Dalsˇ´ı mozˇnostı´ je mrˇ´ızˇka nestrukturovana´, ktera´ pracuje s neusporˇa´dany´mi vrcholy a topologii je tak nutno udrzˇovat ve zvla´sˇtnı´m poli. Mrˇ´ızˇky blokoveˇ strukturovane´ nebo hybridnı´ jsou pak kombinacı´ ostatnı´ch v jednom objemu dat. Detailneˇjsˇ´ı popis a prˇ´ıklady jednotlivy´ch mrˇ´ızˇek lze nale´zt naprˇ´ıklad v [4].

17

3.2

BSP Tree

BSP (Binary Space Partitioning) strom reprezentuje rekurzivnı´ hierarchicke´ deˇlenı´ n-rozmeˇrne´ho prostoru. Uzel stromu obsahuje informaci o deˇlı´cı´ nadrovineˇ, jeden syn odpovı´da´ za´porne´mu a druhy´ kladne´mu poloprostoru. Zpu˚sob deˇlenı´ prostoru a vy´stavby odpovı´dajı´cı´ho stromu naznacˇuje obra´zek 3.1. Vlevo vidı´me jednoduchou 2D sce´nu, uprostrˇed jedno z mozˇny´ch deˇlenı´ a vpravo jemu odpovı´dajı´cı´ strom.

Obra´zek 3.1: Prˇ´ıklad deˇlenı´ sce´ny pomocı´ BSP a jemu odpovı´dajı´cı´ stromova´ struktura. Hierarchicke´ deˇlenı´ prostoru pomocı´ BSP stromu˚ se vyuzˇ´ıva´ naprˇ´ıklad prˇi vykreslova´nı´ trojrozmeˇrne´ sce´ny (urcˇenı´ viditelnosti, odstraneˇnı´ skryty´ch ploch), prˇi detekcı´ch kolizı´ nebo pro urychlova´nı´ raytracingu. Detailnı´ informace o BSP stromech lze nale´zt naprˇ´ıklad na [7].

3.3

Voronoiovy diagramy

Voronoiovy diagramy prˇedstavujı´ deˇlenı´ prostoru podle v neˇm definovane´ mnozˇiny vrcholu˚. Kolem kazˇde´ho vrcholu je definova´na bunˇka prostoru tak, zˇe obsahuje vsˇechny body, pro neˇzˇ je dany´ vrchol nejblizˇsˇ´ım z cele´ mnozˇiny. Prˇ´ıklady dvourozmeˇrny´ch Voronoiovy´ch diagramu˚ uva´dı´ obra´zek 3.2 Voronoiovy diagramy se pouzˇ´ıvajı´ naprˇ´ıklad prˇi triangulacı´ch (prˇ´ımkovy´m dua´lem Voronoiova diagramu je Delaunayova triangulace maxima18

Obra´zek 3.2: Prˇ´ıklady Voronoiovy´ch diagramu˚ ve 2D. lizujı´cı´ nejmensˇ´ı u´hel ve vznikajı´cı´ch polygonech), urcˇova´nı´ nejblizˇsˇ´ıch bodu˚ a sousedu˚ cˇi pla´nova´nı´ cest. Vı´ce lze nale´zt naprˇ´ıklad na [8].

3.4

kD Tree

Jedna´ se o vı´cerozmeˇrny´ bina´rnı´ strom pro organizaci k-rozmeˇrne´ho prostoru podle mnozˇiny vrcholu˚. Deˇlenı´ prova´dı´me nadrovinou kolmou k jedne´ z os, vedenou „prostrˇednı´m“ vrcholem mnozˇiny. Vrchol, ktery´m deˇlı´cı´ nadrovinou povedeme, vybereme naprˇ´ıklad jako media´n z bodu˚ usporˇa´dany´ch podle dane´ osy. Vznikle´ podprostory opeˇt deˇlı´me nadrovinami kolmy´mi k dalsˇ´ı z os a s postupujı´cı´m deˇlenı´m osy pravidelneˇ strˇ´ıda´me. Postup je naznacˇen na obra´zku 3.3.

Obra´zek 3.3: Postup vytva´rˇenı´ struktury kD Tree.. Vı´ce o kD stromech lze nale´zt na [9]. 19

3.5

Quadtree a Octtree

Jelikozˇ na´sledna´ pra´ce vycha´zı´ pra´veˇ ze struktury octtree, veˇnujme jejı´mu popisu veˇtsˇ´ı pozornost. Quadtree a octtree jsou hierarchicke´ stromove´ struktury beˇzˇneˇ pouzˇ´ıvane´ pro adaptivnı´ deˇlenı´ prostoru. V obou prˇ´ıpadech se jedna´ o vyuzˇitı´ stejne´ho principu, pouze quadtree je deˇlenı´ 2D prostoru a octtree pak 3D prostoru. Princip deˇlenı´ prostoru v obou prˇ´ıpadech je patrny´ na obra´zku 3.4. Vlastnı´ adaptivita je zajisˇteˇna pomocı´ dvou protichu˚dny´ch operacı´ – split (rozdeˇlenı´) a merge (sloucˇenı´). Jejich vysveˇtlenı´ uvedeme na prˇ´ıkladeˇ quadtree.

Obra´zek 3.4: Struktury quadtree a octtree. Vymezenou cˇa´st roviny ohranicˇ´ıme do cˇtverce a prohla´sı´me za za´kladnı´ bunˇku quadtree u´rovneˇ 0. Rozdeˇlenı´ te´to bunˇky na kvadranty (operace split ) provedeme tak, zˇe rozdeˇlı´me cˇtverec vodorovny´m a svisly´m rˇezem na stejneˇ velke´ cˇtvrtiny. Zı´ska´me tak 4 (odtud quad) dcerˇine´ bunˇky u´rovneˇ 1, cˇtverce o polovicˇnı´ de´lce strany nezˇ meˇla bunˇka rodicˇovska´. Libovolnou ze vznikly´ch buneˇk mu˚zˇeme da´le stejny´m postupem rozdeˇlit na dalsˇ´ı 4 bunˇky u´rovneˇ 2 a pokracˇovat lze rekurzivneˇ tak dlouho, dokud je trˇeba. Naznacˇeny´m postupem pak mu˚zˇeme zı´skat adaptivnı´ rozdeˇlenı´ prostoru podle toho, ve ktere´ oblasti a do jake´ hloubky jsme prˇi deˇlenı´ buneˇk postupovali, cozˇ zvolı´me podle potrˇeb konkre´tnı´ u´lohy. 20

Pokud nenı´ zı´skane´ deˇlenı´ nada´le trˇeba, je mozˇno postupovat obdobny´m zpu˚sobem, pouze pozpa´tku. Vzˇdy 4 bunˇky nizˇsˇ´ı u´rovneˇ se spojı´ v jednu bunˇku u´rovneˇ vysˇsˇ´ı (operace merge ) a tı´mto spojenı´m zaniknou prˇebytecˇne´ vrcholy i bunˇky nizˇsˇ´ı u´rovneˇ samotne´. Jejich mı´sto zaujı´ma´ bunˇka sloucˇena´. Pro jasnou prˇedstavu jsou obeˇ operace split a merge zachyceny na obra´zku 3.5.

Obra´zek 3.5: Operace split a merge nad strukturou quadtree. V prˇ´ıpadeˇ octtree probı´ha´ vsˇe naprosto stejneˇ, jenom bunˇka nenı´ cˇtverec, ale krychle, nove´ vrcholy prˇi deˇlenı´ vznikajı´ ve strˇedech hran, steˇn a vlastnı´m strˇedu krychle a rozdeˇlenı´m rodicˇovske´ bunˇky zı´ska´me rovnou 8 buneˇk dcerˇiny´ch. Odtud tedy ono oct v na´zvu. Jak uva´dı´ [4], s vy´hodou se popsane´ adaptivnı´ struktury vyuzˇ´ıvajı´ nejen jako prima´rnı´ reprezentace objektu˚, ale cˇasto i jak pomocna´ datova´ struktura doplnˇujı´cı´ jiny´ popis objektu˚, zejme´na pro potrˇeby urychlenı´ mnoha algoritmu˚. Takovy´ bude i na´sˇ prˇ´ıpad pla´nova´nı´ cest.

21

Kapitola 4 Stanovenı´ u´kolu˚ pra´ce 4.1

Adaptivnı´ datova´ struktura pro pla´nova´nı´ cest v dynamicke´m prostrˇedı´

4.1.1

Pu˚vodnı´ u´loha pla´nova´nı´ cest

Pu˚vodnı´ kanadska´ pra´ce [6] se zaby´va´, proble´mem autonomnı´ch agentu˚ hledajı´cı´ch cestu v potencia´lneˇ nezna´me´m dynamicke´m 2D prostrˇedı´. V prostoru se pohybujı´ hrozby jakozˇto zdroje nebezpecˇ´ı a agenti pla´nujı´ svoje trasy tak, aby obesˇli prˇeka´zˇky a za´rovenˇ se vsˇem hrozba´m vyhnuli, nebo alesponˇ souhrn nebezpecˇ´ı na svojı´ trase minimalizovali. Vlastnı´ chova´nı´ agentu˚ a algoritmy hleda´nı´ cesty nejsou te´matem te´to diplomove´ pra´ce, tyto proble´my rˇesˇ´ı bakala´rˇska´ pra´ce [5]. Du˚lezˇita´ je ovsˇem reprezentace prˇeka´zˇek a samotne´ho prostoru pro celou u´lohu hleda´nı´ cest vymezene´ho. Zatı´mco prˇeka´zˇky jsou urcˇeny pravidelnou mrˇ´ızˇkou (konkre´tneˇ jsou definova´ny bitmapou), samotny´ prostor je reprezentova´n mrˇ´ızˇkou adaptivnı´, vybudovanou nad strukturou quadtree. Autor pro ni pouzˇ´ıva´ pojem ASM (Adaptive Spatial Memory). ASM slouzˇ´ı jako centra´la, do ktere´ agenti zası´lajı´ zı´skane´ informace o pu˚vodneˇ nezna´me´m prostoru a za´rovenˇ pak na´sledneˇ na za´kladeˇ sloucˇenı´ 22

teˇchto jednotlivy´ch u´daju˚ zı´ska´vajı´ navigacˇnı´ body pro pla´nova´nı´ svojı´ trasy. Mrˇ´ızˇka je v za´kladnı´m tvaru sice pomeˇrneˇ hruba´, ovsˇem adaptuje se podle mapy prˇeka´zˇek, kterou agenti postupneˇ skla´dajı´ dohromady. V pru˚beˇhu vlastnı´ho hleda´nı´ cest se pak adaptivnı´ mrˇ´ızˇka prˇizpu˚sobuje vsˇem zmeˇna´m dynamicke´ho prostrˇedı´, zejme´na pohybu, vznika´nı´ a zanika´nı´ prˇ´ıpadny´ch prˇeka´zˇek nebo hrozeb. Vlastnı´ hleda´nı´ cest je na adaptivnı´ mrˇ´ızˇce za´visle´, nebot’ agenti pla´nujı´ cesty mezi jednotlivy´mi uzly mrˇ´ızˇky. Dı´ky adaptaci jizˇ majı´ v okolı´ prˇeka´zˇek a hrozeb prˇipraveno detailneˇjsˇ´ı rozdeˇlenı´ procha´zene´ho prostoru (dostatek vrcholu˚ grafu v dane´ zajı´mave´ oblasti) a mohou napla´novat cestu odpovı´dajı´cı´m zpu˚sobem, aby se nebezpecˇny´m nebo nepru˚chodny´m oblastem vyhnuli. Implementace a demonstrace teˇchto principu˚ byla prˇipravena v jazyce C++ a o zobrazova´nı´ se stara´ knihovna OpenGL.

4.1.2

Pozˇadovana´ rozsˇ´ırˇenı´

Nasˇ´ım u´kolem bylo uka´zat, zda je mozˇne´ u´lohu prosty´m zpu˚sobem rozsˇ´ırˇit do 3D, a pokud ne, pokusit se identifikovat problematicka´ mı´sta a navrhnout vlastnı´ u´pravy tak, aby vy´sledne´ rˇesˇenı´ funkcˇnı´ a pouzˇitelne´ by´t mohlo. Jako za´sadnı´ se z tohoto hlediska uka´zaly by´t pra´veˇ zmeˇny v datovy´ch struktura´ch. Zatı´mco v origina´le pouzˇ´ıvane´ 2D struktury plneˇ u´loze dostacˇujı´ a za´rovenˇ neprˇedstavujı´ za´sadnı´ vy´pocˇetnı´ nebo pameˇt’ove´ proble´my, jejich 3D varianty jsou na tom o pozna´nı´ hu˚rˇe. S na´ru˚stem o jednu dimenzi se vesˇkera´ pameˇt’ova´ slozˇitost navysˇuje na trˇetı´ mocninu a je trˇeba pocˇ´ıtat s obdobny´m na´ru˚stem pocˇtu operacı´ a tedy i trva´nı´ cele´ho vy´pocˇtu. Mozˇny´m rˇesˇenı´m je vy´znamneˇ omezit rozmeˇry cˇi rozlisˇenı´ map, nebo mapy reprezentovat a zpracova´vat u´plneˇ jiny´m zpu˚sobem. Obdobneˇ u adaptivnı´ mrˇ´ızˇky naru˚sta´ prˇi prˇechodu od quadtree k octtree stejny´m zpu˚sobem slozˇitost pameˇt’ova´ a vy´znamneˇ i slozˇitost vy´pocˇetnı´. 23

Mrˇ´ızˇka totizˇ musı´ kvu˚li nad nı´ pracujı´cı´m vyhleda´vacı´m algoritmu˚m poskytovat informace o sousednosti vrcholu˚. S rozsˇ´ırˇenı´m o jeden rozmeˇr pocˇet sousedu˚ vrcholu˚ vy´razneˇ naru˚sta´ a prˇiby´va´ i jednotlivy´ch mozˇnostı´ jejich pozic a prˇ´ıpadu˚ jejich prˇ´ıtomnosti. Udrzˇova´nı´ teˇchto informacı´ v konzistentnı´m stavu je pak podstatneˇ komplikovaneˇjsˇ´ı

4.1.3

Vy´sledne´ rozdeˇlenı´ a rˇesˇenı´ u´lohy

Vzhledem k velke´mu rozsahu jsme se s vedoucı´ pra´ce rozhodli u´lohu rozdeˇlit mezi dva rˇesˇitele, jak jizˇ bylo vy´sˇe naznacˇeno. Bakala´rˇska´ pra´ce [5] se zaby´vala proble´my map prˇeka´zˇek a hrozeb, vlastnı´m hleda´nı´m cesty a prˇ´ıpravou demonstracˇnı´ aplikace. Mapy zu˚staly v podstateˇ 3D bitmapami, ktere´ jsou zejme´na z pameˇt’ovy´ch a vy´pocˇetnı´ch du˚vodu˚ pouzˇ´ıva´ny pouze v maly´ch rozmeˇrech. Hleda´nı´ cest probı´ha´, jak jizˇ bylo rˇecˇeno, nad vrcholy adaptivnı´ mrˇ´ızˇky. Diplomova´ pra´ce, kterou drzˇ´ıte v rukou, pak, vzhledem ke sve´mu te´matu hierarchicky´ch modelu˚, zahrnuje analy´zu, na´vrh a pra´ci na implementaci hierarchicke´ho modelu prostoru u´lohy. Ten je reprezentova´n jizˇ zminˇovanou hybridnı´ adaptivnı´ mrˇ´ızˇkou zalozˇenou cˇa´stecˇneˇ na stromove´ strukturˇe octtree (viz kapitola 3.5). Hybridnı´ proto, zˇe jde z jedne´ strany o adaptivnı´ mrˇ´ızˇku a ze strany druhe´ o grafovou strukturu poskytujı´cı´ v kazˇde´m okamzˇiku prˇ´ıme´ sousedy jednotlivy´ch vrcholu˚. Spolecˇnou pracı´ pak byl u´vodnı´ na´vrh aplikace, komunikacˇnı´ho rozhranı´ mezi obeˇma cˇa´stmi a take´ po implementaci na´sledujı´cı´ ladeˇnı´, testova´nı´, meˇrˇenı´ vy´sledku˚ a dodatecˇne´ u´pravy implementace. Struktura cele´ aplikace a konkre´tnı´ funkcˇnost vyhleda´va´nı´ cest nenı´ prˇedmeˇtem te´to diplomove´ pra´ce a proto v prˇ´ıloha´ch B a C uva´dı´m na neˇkolik konferencı´ nabı´dnute´ cˇla´nky, ktere´ celou aplikaci popisujı´. V dalsˇ´ım textu te´to diplomove´ pra´ce se nada´le budeme veˇnovat zejme´na pouzˇ´ıvane´ adaptivnı´ datove´ strukturˇe a rozhranı´, prˇes ktere´ je prˇ´ıstupna´.

24

Obecneˇ panoval prˇedpoklad, zˇe nasˇe pra´ce ve vy´sledku povede ke zjisˇteˇnı´ za´sadnı´ch, at’ jizˇ pameˇt’ovy´ch nebo vy´pocˇetnı´ch, komplikacı´ takove´ povahy, zˇe se uka´zˇe nemozˇne´ cˇi neprakticke´ proste´ rozsˇ´ırˇenı´ prove´st. Zejme´na jsme ocˇeka´vali nezvladatelny´ na´ru˚st pameˇt’ovy´ch i vy´pocˇetnı´ch na´roku˚ rozsˇ´ırˇeny´ch datovy´ch struktur. Stejneˇ tak i zvolene´ programove´ prostrˇedı´ .NET s sebou prˇina´sˇelo riziko zpomalenı´. Prˇesto bylo nasˇ´ım u´kolem konkre´tnı´ proble´my a mı´sta jasneˇ identifikovat a navrhnout mozˇnosti rˇesˇenı´ cˇi zmı´rneˇnı´ komplikacı´, nebo jejich obejitı´ pouzˇitı´m jine´ho prˇ´ıstupu k rˇesˇenı´ dane´ho proble´mu.

4.2

´ loha modifikace povrchu U

My´m samostatny´m u´kolem bylo pokusit se adaptivnı´ strukturu prˇipravenou pro vy´sˇe uvedenou u´lohu vyuzˇ´ıt pro jiny´ u´cˇel a uka´zat tak jejı´ univerza´lnost. Zvoleny´m proble´mem byl pokus otiskovat do materia´lu reprezentovane´ho adaptivnı´ mrˇ´ızˇkou jiny´ objekt. Vy´sledkem by meˇla by´t na spra´vny´ch mı´stech adaptovana´ struktura s vyznacˇeny´m povrchem otiskovane´ho objektu. Kromeˇ oveˇrˇenı´ mozˇnosti jine´ aplikace jsem se zameˇrˇil zejme´na na dalsˇ´ı zkouma´nı´ rychlosti, jakou je struktura schopna´ se adaptovat.

25

Kapitola 5 Adaptivnı´ mrˇı´zˇka 5.1

Role adaptivnı´ mrˇı´zˇky prˇi hleda´nı´ cesty

Adaptivnı´ mrˇ´ızˇka hraje v u´loze roli prostrˇednı´ka mezi bitovy´mi mapami reprezentujı´cı´mi prˇeka´zˇky a hrozby a vlastnı´m algoritmem pro hleda´nı´ cest v prostrˇedı´ definovane´m teˇmito mapami. Zajisˇt’uje prˇevod bitmapovy´ch informacı´ na grafovou datovou strukturu, se kterou umeˇjı´ vyhleda´vacı´ algoritmy da´le pracovat. Vrcholy mrˇ´ızˇky jsou dostupne´ jako uzly grafu a informace o sousednosti je pouzˇita ke spojova´nı´ teˇchto uzlu˚ cestami. Reprezentovany´ prostor je dynamicky´, a tak se s postupem cˇasu meˇnı´ bitove´ mapy. Mrˇ´ızˇka na tyto zmeˇny neusta´le reaguje a adaptuje se podle aktua´lnı´ situace. Jelikozˇ by zmeˇna meˇla probı´hat co nejblı´zˇe rea´lne´mu cˇasu, kladl jsem prˇi na´vrhu a implementaci adaptivnı´ mrˇ´ızˇky du˚raz zejme´na na jejı´ rychlost, pameˇt’ova´ slozˇitost pak byla druhy´m, prˇesto velmi vy´znamny´m argumentem. Vy´sledne´ rˇesˇenı´ je, myslı´m si, nakonec rozumny´m kompromisem mezi teˇmito dveˇma hlavnı´mi neaplikacˇnı´mi pozˇadavky.

26

Obra´zek 5.1: Vlastnı´ a nevlastnı´ vrcholy bunˇky.

5.2

Vrcholy a jejich sousednost

Zatı´mco u pravidelneˇ strukturovany´ch mrˇ´ızˇek je znalost sousednosti vrcholu˚ samozrˇejma´ (sousedy lze snadno zı´skat kombinacı´ inkrementacı´ a dekrementacı´ jednotlivy´ch indexu˚ urcˇujı´cı´ch dotazovany´ vrchol mrˇ´ızˇky), pouzˇitı´m jine´ nezˇ pravidelne´ struktury tuto vy´hodu ztra´cı´me. Znalost sousednosti vrcholu˚ je i prˇesto za´kladnı´m aplikacˇnı´m pozˇadavkem kladeny´m na adaptivnı´ mrˇ´ızˇku. Bylo tedy nutne´ pouzˇ´ıvanou strukturu octtree rozsˇ´ırˇit a upravit tak, aby tento pozˇadavek splnˇovala. Struktura octtree zajisˇt’uje hierarchicke´ deˇlenı´ prostoru na mensˇ´ı bunˇky. Jednotlivy´mi vrcholy takto vznikajı´cı´ch buneˇk se ale nijak nezaby´va´. V prvnı´m kroku tedy bylo nutne´ prˇidat k octtree vrcholy a operace s nimi. Oproti 2D rˇesˇenı´ quadtree ma´ bunˇka octtree mı´sto 4 vlastnı´ch vrcholu˚ 8. Kromeˇ vlastnı´ch vrcholu˚ definuji bunˇce jesˇteˇ vrcholy, ktere´ nazy´va´m nevlastnı´mi. V za´kladnı´m tvaru se jedna´ o neobsazene´ pozice, prˇipravene´ pro noveˇ vznikle´ vrcholy prˇ´ımy´ch potomku˚ bunˇky. Na obra´zku 5.1 jsou vlastnı´ vrcholy vyznacˇeny´ cˇerneˇ a vrcholy nevlastnı´ sˇedeˇ. Jak je patrne´, spolu s nevlastnı´mi vrcholy jich kazˇda´ bunˇka obsahuje celkem 27. Operace split a merge jsou proto doplneˇny o vytva´rˇenı´ a rusˇenı´ vrcholu˚ a jejich spra´vne´ obsazova´nı´ do odpovı´dajı´cı´ch pozic. Sousedı´cı´ bunˇky nebo bunˇky do sebe zanorˇene´ (rodicˇ a jeho potomci) se navza´jem doty´kajı´ a proto majı´ neˇkolik totozˇny´ch vrcholu˚. Sousedı´cı´ bunˇky mohou sdı´let spolecˇnou steˇnu (4 vlastnı´ a 5 nevlastnı´ch vrcholu˚), hranu (2 27

Obra´zek 5.2: Mozˇnosti sdı´lenı´ vrcholu˚ mezi sousedı´cı´mi bunˇkami. vlastnı´ a 1 nevlastnı´ vrchol), nebo 1 rohovy´ vrchol, jak ukazuje obra´zek 5.2. Vzhledem k prˇedpokla´dane´mu velke´mu mnozˇstvı´ buneˇk v sı´ti a na´roku˚m na pameˇt’nenı´ zˇa´doucı´, aby se v celkove´ strukturˇe takove´ vrcholy udrzˇovaly duplicitneˇ. Prˇed jejich vytva´rˇenı´m proto probı´ha´ kontrola oveˇrˇujı´cı´, zda jizˇ na dane´ pozici struktury existuje pouzˇitelny´ vrchol a naopak prˇi rusˇenı´ se kontroluje, zda dany´ vrchol nepouzˇ´ıvajı´ i jine´ nezˇ rusˇene´ bunˇky. Takova´ kontrola, prova´deˇna´ sice efektivneˇ, ale prova´deˇna´ prˇi vytva´rˇenı´ a rusˇenı´ kazˇde´ bunˇky, ma´ za na´sledek zpomalenı´ adaptace sı´teˇ. Druhy´m krokem rozsˇ´ırˇenı´ struktury octtree je prˇida´nı´ mozˇnosti snadne´ho a hlavneˇ rychle´ho urcˇova´nı´ sousedu˚. Po vzoru 2D rˇesˇenı´ sousedı´ v ra´mci jedne´ bunˇky vlastnı´ vrcholy kazˇdy´ s kazˇdy´m, cozˇ znamena´ 28 vza´jemny´ch vazeb. Nevlastnı´ vrcholy jsou prˇipravene´ pozice pro dcerˇine´ bunˇky na nizˇsˇ´ı u´rovni a do sousednosti v ra´mci bunˇky tak nezasahujı´. Kromeˇ okrajovy´ch prˇ´ıpadu˚ je kazˇdy´ vrchol mrˇ´ızˇky obklopen osmi bunˇkami a v kazˇde´ z nich ma´ svoje sousedy, ktery´ch mu˚zˇe by´t dohromady azˇ 26. Bunˇky obklopujı´cı´ vrchol ovsˇem nemusejı´ by´t na stejne´ u´rovni stromu. Sousednost v ra´mci bunˇky a prˇ´ıklad vsˇech sousedu˚ v okolı´ bodu ukazuje obra´zek 5.3. Zmı´neˇne´ okrajove´ prˇ´ıpady, jedna´ se o vrcholy na steˇneˇ cˇi hraneˇ mrˇ´ızˇky nebo o rohovy´ bod, jsou zna´zorneˇny´ na obra´zku 5.4. Z uvedeny´ch uka´zek je patrne´ je patrne´, zˇe sousednost vrcholu˚ uvnitrˇ adaptovane´ mrˇ´ızˇky je pomeˇrneˇ komplikovana´ za´lezˇitost. Vyhleda´va´nı´ sousedu˚ bez dodatecˇne´ informace ulozˇene´ ve strukturˇe by tak bylo prˇ´ılisˇ slozˇite´ a tedy i cˇasoveˇ na´rocˇne´. Vzhledem k tomu, zˇe zjisˇt’ova´nı´ sousedu˚ velke´ho mnozˇstvı´ vrcholu˚ prova´dı´ aplikace prˇi urcˇova´nı´ cesty v grafu po kazˇde´ adaptaci sı´teˇ, je pozˇadavek na rychlost za´sadnı´. Ukla´dat do kazˇ28

Obra´zek 5.3: Vza´jemne´ vazby uvnitrˇ bunˇky a prˇ´ıklad sousedu˚ v ru˚zny´ch u´rovnı´ch okolo jednoho bodu.

Obra´zek 5.4: Okrajove´ prˇ´ıpady pocˇtu a pozic sousedu˚ vrcholu.; de´ho vrcholu 26 odkazu˚ na sousedy by sice umozˇnilo jejich okamzˇite´ urcˇenı´, ovsˇem pameˇt’ove´ na´roky struktury by tı´m pova´zˇliveˇ narostly. Stejneˇ tak i modifikace odkazu˚ na sousedy u vsˇech vrcholu˚ beˇhem operacı´ split a merge by adaptaci sı´teˇ vy´znamneˇ zpomalovala. Zvolene´ rˇesˇenı´ prˇedstavuje kompromis mezi obeˇma protichu˚dny´mi pozˇadavky. Vrchol neobsahuje odkazy na svy´ch 26 sousedu˚, ale na 8 buneˇk, ktere´ jej obklopujı´. Jedna´ se o bunˇky nejvysˇsˇ´ı u´rovneˇ, ktera´ vrchol pouzˇ´ıva´. Bod na te´to u´rovni vznikl a dokud existuje, existujı´ i obklopujı´cı´ bunˇky. Dı´ky tomu se odkazy beˇhem adaptace sı´teˇ nemusı´ upravovat a zu˚sta´vajı´ platne´ po celou dobu existence vrcholu. Pro kazˇdou z obklopujı´cı´ch buneˇk je zkoumany´ bod vrcholem vlastnı´m a lezˇ´ı tedy v jednom z rohu˚ bunˇky. Bezprostrˇednı´ sousede´ se pak naleznou jizˇ pomeˇrneˇ snadno. Stacˇ´ı urcˇit nejhloubeˇji zanorˇenou podbunˇku v dane´m rohu a jejı´ vlastnı´ vrcholy jsou hledany´mi sousedy. Popsany´m zpu˚sobem je dosazˇeno vı´ce nezˇ dvoutrˇetinove´ u´spory pameˇti potrˇebne´ k uchova´nı´ sousednosti a za´rovenˇ je vlastnı´ adaptace sı´teˇ zbavena 29

jake´hokoliv zpomalenı´ z hlediska prˇepocˇ´ıta´va´nı´ odkazu˚. Ani zaznamena´nı´ obklopujı´cı´ch buneˇk beˇhem vytva´rˇenı´ vrcholu nenı´ cˇasoveˇ na´rocˇne´ a je prˇijatelnou cenou za zisk v podobeˇ pameˇt’ove´ u´spory a rychle´ho hleda´nı´ sousedu˚.

30

Kapitola 6 Objektoveˇ orientovana´ analy´za Jizˇ ze zada´nı´ jsme meˇli prˇedstavu o rozdeˇlenı´ u´kolu˚, tedy zˇe na´vrh a implementace adaptivnı´ch struktur a s nimi pracujı´cı´ch algoritmu˚ budou soucˇa´stı´ te´to diplomove´ pra´ce a prˇ´ıprava vyhleda´va´nı´ cest soucˇa´stı´ pra´ce bakala´rˇske´. Celou analy´zu jsme tomu podrˇ´ıdili a navrhli tak dva samostatne´ celky, komunikujı´cı´ co nejjednodusˇsˇ´ım rozhranı´m.

6.1

Na´vrh rozhranı´

Rozhranı´ mezi nasˇimi soucˇa´stmi tvorˇ´ı dva jednoduche´ interfacy. Prakticky jsou zestrucˇneˇny na za´kladnı´ pozˇadavek, zˇe vyhleda´vacı´ cˇa´st pozˇaduje ke svojı´ pra´ci graf navigacˇnı´ch uzlu˚ a datova´ struktura, trˇebazˇe z principu negrafova´, jej musı´ poskytnout. Interfacy jsou navrzˇeny tak, zˇe soucˇa´sti na obou jejich strana´ch lze snadno nahradit jiny´mi, z hlediska dane´ho interfacu ekvivalentnı´mi implementacemi, ktere´ mohou vnitrˇneˇ pracovat na zcela jine´m principu. Adaptivnı´ strukturu je tak mozˇno do budoucna v prˇ´ıpadeˇ potrˇeby snadno nahradit strukturou jinou a stejneˇ tak vyhleda´va´nı´ cest lze teoreticky nahradit jiny´m algoritmem, ktery´ adaptivnı´ strukturu vyuzˇije jiny´m zpu˚sobem pro svoje u´cˇely.

31

6.1.1

Interface IEngram

Interface IEngram popisuje pozˇadavky kladene´ na jednotlive´ uzly grafu, se ktery´m vyhleda´vacı´ algoritmus pracuje. Proto jej musı´ implementovat jaky´koliv objekt, ktery´ by meˇl v libovolne´ implementaci struktury takovy´ uzel reprezentovat. Jsou definova´ny dveˇ za´kladnı´ metody: • Kazˇdy´ uzel musı´ poskytovat vyhleda´vacı´mu algoritmu svoje sourˇadnice v prostoru u´lohy, podle ktery´ch se na´sledneˇ urcˇuje, v jake´ oblasti se bod nacha´zı´, jak velke´ v okolı´ hrozı´ nebezpecˇ´ı a podobneˇ. • Zı´ska´nı´ seznamu sousednı´ch uzlu˚. Kazˇdy´ uzel musı´ by´t schopen poskytnout aktua´lneˇ platny´ seznam vrcholu˚, se ktery´mi bezprostrˇedneˇ sousedı´. Dı´ky tomu mu˚zˇe algoritmus hleda´nı´ cesty snadno pla´novat u´seky, ktere´ dohromady vy´slednou trasu slozˇ´ı.

6.1.2

Interface IGraph

Interface IGraph popisuje, jaky´m zpu˚sobem bude algoritmus hleda´nı´ cest komunikovat se samotnou datovou strukturou a jake´ u´daje po nı´ bude pozˇadovat. Tento interface tedy musı´ implementovat kazˇda´ struktura, nad kterou v nasˇem syste´mu bude vyhleda´va´nı´ cest probı´hat. Jsou definova´ny dveˇ za´kladnı´ metody: • Zı´ska´nı´ seznamu vsˇech uzlu˚. Jedna´ se o za´kladnı´ grafovy´ pozˇadavek. Algoritmus hleda´nı´ cesty potrˇebuje zna´t seznam navigacˇnı´ch bodu˚. Mezi ktery´mi bude trasu vytycˇovat. Struktura splnˇujı´cı´ interface IGraph mu tento seznam musı´ poskytovat s tı´m, zˇe prvky seznamu musejı´ navı´c implementovat jizˇ popsany´ interface IEngram. Touto kombinacı´ je pro vyhleda´vacı´ algoritmus zajisˇteˇna nutna´ znalost grafovy´ch informacı´. • Zı´ska´nı´ uzlu nejblizˇsˇ´ıho zvolene´mu mı´stu v prostoru. Jelikozˇ vyhleda´vacı´ algoritmus nema´ zˇa´dnou znalost o adaptivnı´ strukturˇe, nebyl 32

by schopen v nı´ sa´m dohleda´vat body jinak nezˇ procha´zenı´m jejich seznamu a naprˇ´ıklad porovna´va´nı´m sourˇadnic s hledany´mi. Takovy´ postup by samozrˇejmeˇ nebyl efektivnı´. Naproti tomu jaka´koliv struktura za interfacem ukryta´ mu˚zˇe snadno vyuzˇ´ıt znalosti o svojı´ stavbeˇ a bod nejblizˇsˇ´ı pozˇadovane´mu mı´stu snadno a efektivneˇ dodat. Vraceny´ vrchol opeˇt musı´ implementovat interface IEngram. Po definici rozhranı´ a rozdeˇlenı´ si u´kolu˚ jsme na´sledneˇ mohli kazˇdy´ pokracˇovat v samostatne´ pra´ci na svojı´ cˇa´sti u´lohy. Kromeˇ ostatnı´ch vy´hod na´m navrzˇene´ rozhranı´ take´ vy´znamneˇ usnadnilo pocˇa´tecˇnı´ fa´ze vy´voje. Umozˇnilo na´m beˇhem te´to pra´ce pouzˇ´ıvat mı´sto jesˇteˇ zdaleka ne hotove´ kolegovy soucˇa´sti docˇasnou jednoduchou na´hradu, ktera´, trˇebazˇe zdaleka neplnila pozˇadovane´ u´koly pozˇadovany´m zpu˚sobem, pomohla prˇi testova´nı´ a ladeˇnı´ v u´vodu implementace vznikajı´cı´ho ko´du.

6.2

Na´vrh trˇı´d

V analy´ze datovy´ch struktur jsem navrhl trˇi za´kladnı´ trˇ´ıdy. Trˇ´ıdu specifikujı´cı´ vlastnı´ adaptivnı´ mrˇ´ızˇku, trˇ´ıdu reprezentujı´cı´ bunˇku te´to mrˇ´ızˇky a trˇ´ıdu zastupujı´cı´ vrchol bunˇky. Na´vrh zahrnuje vsˇechny potrˇebne´ vlastnosti a data popsana´ v kapitole 5 a metody s nimi pracujı´cı´. Mrˇ´ızˇka je navrzˇena dostatecˇneˇ obecneˇ, aby ji bylo mozˇno pouzˇ´ıt i pro jine´ aplikace bez nutnosti vy´razny´ch zmeˇn.

6.2.1

Trˇı´da Mesh

Trˇ´ıda Mesh popisuje samotnou adaptivnı´ mrˇ´ızˇku, implementuje tedy v kapitole 6.1.2 popsany´ interface IGraph. Obaluje modifikovanou strukturu octtree, resp. jejich veˇtsˇ´ı mnozˇstvı´. V obecne´m na´vrhu jsme se totizˇ neomezili na pouze krychlovy´ prostor, ale mrˇ´ızˇka mu˚zˇe mı´t tvar kva´dru slozˇene´ho z vı´ce krychlı´. Kazˇda´ z takovy´ch krychlı´ se mu˚zˇe sama o sobeˇ 33

adaptovat jako octtree s tı´m, zˇe jsou vsˇechny navza´jem propojeny a prˇile´hajı´cı´ steˇny krychlı´ navza´jem sdı´lejı´ vrcholy ve vsˇech u´rovnı´ch adaptace. Trˇ´ıda obsahuje metody pro procha´zenı´ vnitrˇnı´ch struktur pro zı´ska´va´nı´ seznamu˚ existujı´cı´ch elementu˚ (buneˇk cˇi vrcholu˚) a take´ pro jejich udrzˇova´nı´ a aktualizaci. Noveˇ vznikajı´cı´ elementy se tak do teˇchto seznamu˚ registrujı´ a zanikajı´cı´ elementy se naopak ze seznamu˚ odstranˇujı´.

6.2.2

Trˇı´da Cluster

Trˇ´ıda Cluster reprezentuje bunˇku adaptivnı´ mrˇ´ızˇky. Pro udrzˇova´nı´ stromove´ struktury ma´ referenci na sve´ho rodicˇe a na vsˇechny svoje potomky. Za´rovenˇ si udrzˇuje informaci o hloubce u´rovneˇ, na ktere´ je bunˇka zkonstruova´na. Trˇ´ıda obsahuje odkazy na svoje vlastnı´ vrcholy i pozice prˇipravene´ pro vrcholy nevlastnı´. Za´rovenˇ definuje metody pro vy´pocˇet sourˇadnic teˇchto nevlastnı´ch bodu˚. Ty se budou nacha´zet vzˇdy v polovineˇ hran a u´hloprˇ´ıcˇek, vy´pocˇet proto nenı´ slozˇity´. Cluster definuje dveˇ za´kladnı´ metody split a merge, ktere´ implementujı´ stejnojmenne´ operace popsane´ v kapitole 3.5. V souvislosti se zavedenı´m vrcholu˚ bunˇek a jejich sousednosti rˇesˇ´ı metody split a merge i dodatecˇne´ proble´my popsane´ v kapitole 5.2. V ra´mci deˇlenı´ bunˇky jsou vola´ny metody pro spra´vne´ nastavenı´ vlastnostı´ noveˇ vznikly´ch vrcholu˚ a buneˇk. Zejme´na se jedna´ o udrzˇova´nı´ spra´vne´ hierarchie stromu, nastavova´nı´ rodicˇu˚ a potomku˚ a nastavenı´ cˇlenstvı´ vrcholu˚ v jednotlivy´ch bunˇka´ch. Pro zajisˇteˇnı´ funkcˇnosti trˇ´ıdy Mesh (vy´pis vsˇech vrcholu˚ sı´teˇ) jı´ da´va´ Cluster k dispozici metodu pro vy´pis vsˇech vrcholu˚ ve sve´m prostoru, tedy vsˇech vrcholu˚ svy´ch i vrcholu˚ potomku˚.

34

6.2.3

Trˇı´da Engram

Trˇ´ıda Engram reprezentuje vrchol bunˇky mrˇ´ızˇky. Nese si informaci o svojı´ prˇesne´ pozici v prostoru a kompletnı´ vy´cˇet vsˇech buneˇk, pro ktere´ byl vrchol vytvorˇen (azˇ 8 obklopujı´cı´ch buneˇk). Dı´ky tomu je jasneˇ definovana´ struktura, jakou vrcholy v prostoru tvorˇ´ı. Kazˇdy´ engram si za´rovenˇ s tı´m nese i informaci o u´rovni zanorˇenı´, na ktere´ byl vytvorˇen. Pak mu˚zˇe poskytovat rychlou metodu vracejı´cı´ aktua´lneˇ platne´ sousedy, postupem popsany´m v kapitole 5.2.

35

Kapitola 7 Implementace Zdrojove´ ko´dy implementace vsˇech popsany´ch trˇ´ıd jsou dostupne´ na prˇilozˇene´m datove´m nosicˇi, doplneˇny dokumentacˇnı´mi komenta´rˇi jak je u jazyka C# zvykem. Ko´d a dokumentace se tak navza´jem doplnˇujı´ a poskytujı´ velmi zevrubny´ a za´rovenˇ prˇehledny´ popis samotne´ implementace. Konkre´tnı´ umı´steˇnı´ vsˇech souboru˚ naleznete popsane´ v souboru readme.txt v korˇenove´m adresa´rˇi nosicˇe. Implementace se drzˇ´ı analy´zy uvedene´ v kapitole 6. Odpovı´dajı´cı´ classdiagramy jednotlivy´ch trˇ´ıd, jak je poskytuje visual studio, jsou k dispozici v prˇ´ıloze A a poskytujı´ rychlou prˇedstavu o prˇesne´ podobeˇ trˇ´ıd a interfacu˚. Jelikozˇ adaptivnı´ struktura je sama o sobeˇ pouhy´m na´strojem pro dalsˇ´ı pouzˇitı´, je na prˇilozˇene´m datove´m nosicˇi doda´na i uka´zkova´ aplikace. Jedna´ se pra´veˇ o syste´m vyhleda´vajı´cı´ nad adaptivnı´ strukturou cestu, jak byl popsa´n v kapitole 4.1. Aplikace pracuje na´sledujı´cı´m zpu˚sobem. Je definova´na mapa prˇeka´zˇek zaznamena´vajı´cı´ nepohyblive´ objekty (jako prˇeka´zˇky byly pro jednoduchost zvoleny koule ru˚zny´ch polomeˇru˚) a mapa hrozeb zachycujı´cı´ vzˇdy aktua´lnı´ pozici a velikost pohyblivy´ch nebezpecˇny´ch objektu˚. Vlivy prˇeka´zˇek a hrozeb jsou v mapa´ch zaznamena´ny cˇ´ıselny´mi va´hami. Je vytvorˇena adaptivnı´ mrˇ´ızˇka v za´kladnı´m tvaru (zatı´m nijak adaptovana´ jedna velka´ 36

bunˇka), ktera´ pokry´va´ prostor reprezentovany´ mapami. Adaptace mrˇ´ızˇky probı´ha´ tak, zˇe pro kazˇdou bunˇku mrˇ´ızˇky (v u´vodu tedy pro jedinou) je va´hovou funkcı´ kombinujı´cı´ hodnoty z obou map urcˇena celkova´ va´ha bloku prostoru reprezentovane´ho bunˇkou. Pokud je hodnota va´hy moc vysoka´, znamena´ to, zˇe v dane´m bloku jsou prˇeka´zˇky nebo hrozby a bunˇka je proto rozdeˇlena operacı´ split. Tato operace se nad cely´m prostorem opakuje azˇ dokud nejsou va´hy vsˇech bloku˚ nizˇsˇ´ı nezˇ meznı´ hodnota, nebo dokud nenı´ dosazˇeno maxima´lnı´ povolene´ u´rovneˇ deˇlenı´. Obdobny´m zpu˚sobem se vyhodnocuje a prova´dı´ i operace merge nad bunˇkami, jejichzˇ celkova´ va´ha je nizˇsˇ´ı nezˇ ke sloucˇenı´ stanovena´ meznı´ hodnota. Algoritmus vyhleda´vajı´cı´ cestu pak k adaptovane´ mrˇ´ızˇce prˇistupuje jako ke grafu, nad jehozˇ uzly a cestami mezi nimi urcˇuje optima´lnı´ trasu. Spolu s pohybem hrozeb se sı´t’ iterativneˇ adaptuje a v kazˇde´m kroku se znovu hleda´ vy´sledna´ cesta odpovı´dajı´cı´ pozmeˇneˇny´m podmı´nka´m. Aplikace nebyla vytvorˇena v ra´mci te´to diplomove´ pra´ce (pouze ji vyuzˇ´ıva´ ke svojı´ cˇinnosti) a jejı´ detailneˇjsˇ´ı popis a uka´zky jsou proto dostupne´ v cˇla´ncı´ch uvedeny´ch jako prˇ´ılohy B a C tohoto textu.

7.1

Pouzˇite´ programovacı´ prostrˇedky

Pro implementaci jsme zvolili objektoveˇ orientovane´ prostrˇedı´ Microsoft .NET Framework a jazyk C#, vizua´lnı´ stra´nku obstara´va´ DirectX. Z du˚vodu zmeˇny platformy jsme se rozhodli pro kompletnı´ vlastnı´ na´vrh a implementaci aplikace, bez vyuzˇitı´ cˇi inspirace v pu˚vodnı´m C++ ko´du. Nasˇ´ım vy´chozı´m bodem byl tedy teoreticky´ popis principu˚ aplikace s mozˇnostı´ konzultace u autoru˚ metody. Na prostrˇedı´ .NET padla nasˇe volba zejme´na z na´sledujı´cı´ch du˚vodu˚. Na rozdı´l od pu˚vodneˇ pouzˇite´ho C++ je C# cˇisteˇ objektoveˇ orientovany´ jazyk a usnadnil na´m tak pomeˇrneˇ cˇisty´ a jasny´ na´vrh a take´ zvy´sˇil vy´slednou 37

cˇitelnost a srozumitelnost vznikle´ho ko´du. Objektoveˇ orientovany´ prˇ´ıstup na´m take´ umozˇnil snadnou definici rozhranı´ mezi jednotlivy´mi cˇa´stmi u´lohy a tı´m i snadnou spolupra´ci.

7.2

Pozˇadavky na prˇeklad a spousˇteˇnı´ dodane´ aplikace

Pro prˇeklad aplikace je trˇeba mı´t nainstalova´n operacˇnı´ syste´m Microsoft Windows, Microsoft .NET Framework 2.0 SDK a DirectX 9.0 SDK October 2005. Vzhledem k jejich vy´voji nelze zarucˇit stoprocentneˇ spra´vnou funkcˇnost s noveˇjsˇ´ımi verzemi. Doporucˇeno je i Microsoft Visual Studio 2005, ve ktere´m je cely´ projekt zpracova´n, prˇeklad by ovsˇem meˇl by´t teoreticky mozˇny´ i bez jeho instalace. Pro vlastnı´ spusˇteˇnı´ by pak meˇl stacˇit opeˇt operacˇnı´ syste´m Microsoft Windows, Microsoft .NET Framework 2.0 Runtime a DirectX 9.0. Kromeˇ operacˇnı´ho syste´mu a Visual Studia se jedna´ o produkty volneˇ dostupne´ z webu spolecˇnosti Microsoft (www.microsoft.com) a za´rovenˇ jsou prˇipraveny na datove´m nosicˇi prˇilozˇene´m k te´to pra´ci. Jejich konkre´tnı´ umı´steˇnı´ naleznete popsane´ v souboru readme.txt v korˇenove´m adresa´rˇi nosicˇe.

38

Kapitola 8 Testova´nı´ Vzhledem k cı´lu˚m u´lohy a pouzˇite´ aplikaci se veˇtsˇina testova´nı´ veˇnovala vy´sledne´ implementace hleda´nı´ cest. Prˇesto se neˇktera´ meˇrˇenı´ zameˇrˇila na specificke´ vlastnosti mrˇ´ızˇky samotne´ a i vy´sledky testu˚ ostatnı´ch jsou na jejı´ pra´ci vy´znamneˇ za´visle´.

8.1

Podmı´nky pru˚beˇhu testu˚

Chova´nı´ testovacı´ aplikace bylo meˇrˇeno na PC s procesorem Athlon XP 2000+ a 512 MB DDR RAM, operacˇnı´m syste´mem Windows XP SP2 a bez jiny´ch zbytecˇneˇ spusˇteˇny´ch programu˚ cˇi sluzˇeb. Vy´znamnou cˇa´st meˇrˇenı´ jsem neprova´deˇl sa´m, ale probı´hala jako spolupra´ce prˇi prˇ´ıpraveˇ cˇla´nku uvedene´ho v prˇ´ıloze B tohoto textu. Cˇla´nek je psany´ v anglicke´m jazyce, proto vzˇdy uvedu cˇesky´ popis podmı´nek testova´nı´ i testu samotne´ho. Pouzˇiji vsˇak neˇktere´ z pu˚vodnı´ch grafu˚ s anglicky´mi popisky. V aplikaci jsme vygenerovali zvolene´ mnozˇstvı´ pevneˇ definovany´ch prˇeka´zˇek ru˚zne´ velikosti, vizualizovany´ch kulovy´mi objekty v prostoru, a pohyblive´ hrozby reprezentovane´ malou cˇervenou krychlicˇkou. Za beˇhu pro39

gramu se hrozby na´hodneˇ pohybujı´ z mı´sta na mı´sto a adaptivnı´ mrˇ´ızˇka na jejich pohyb reaguje u´pravou svojı´ struktury. Mapa prˇeka´zˇek je prˇedpocˇ´ıta´na a vyplneˇna odpovı´dajı´cı´mi hodnotami jesˇteˇ prˇed zapocˇetı´m hlavnı´ smycˇky programu, jejı´ prˇ´ıprava tedy nijak neovlivnˇuje samotny´ pru˚beˇh meˇrˇenı´ beˇhu programu. Optima´lnı´ cesta se prˇepocˇ´ıta´va´ po kazˇde´ adaptaci sı´teˇ. Meˇrˇenı´ je vzˇdy zameˇrˇeno na vlastnı´ operace a nezahrnuje cˇas potrˇebny´ k vizualizaci jejich vy´sledku˚.

8.2

Testovacı´ sce´ny

Pro prozkouma´nı´ chova´nı´ algoritmu˚ nad odlisˇny´mi druhy a rozsahy dat jsme definovali neˇkolik ru˚znorody´ch typu˚ sce´n. Pokud nenı´ u konkre´tnı´ch meˇrˇenı´ uvedeno jinak, prova´deˇly se vsˇechny testy nad na´sledujı´cı´mi cˇtyrˇmi sce´nami. Sce´na 1 je slozˇena z 8 na´hodneˇ rozmı´steˇny´ch kulovy´ch prˇeka´zˇek na´hodneˇ zvolene´ velikosti, ktere´ zaujı´majı´ prˇiblizˇneˇ 3% objemu prostoru u´lohy. Mapy prˇeka´zˇek a hrozeb majı´ rozlisˇenı´ 32 x 32 x 32 hodnot a maxima´lnı´ povolena´ u´rovenˇ deˇlenı´ adaptivnı´ mrˇ´ızˇky je 4 (nejmensˇ´ı bunˇka ma´ tedy hranu o de´lce 1/24 celkove´ho rozmeˇru). Sce´na 2 je definova´na stejneˇ jako sce´na 1, ovsˇem povoluje o stupenˇ hlubsˇ´ı u´rovenˇ deˇlenı´, tedy do u´rovneˇ 5. Sce´na 3 se skla´da´ z 16 prˇeka´zˇek, ktere´ zaujı´majı´ prˇiblizˇneˇ 6% prostoru u´lohy. Rozlisˇenı´ map prˇeka´zˇek a hrozeb bylo 64 x 64 x 64 hodnot a maxima´lnı´ u´rovenˇ deˇlenı´ adaptivnı´ mrˇ´ızˇky je 4. Sce´na 4 je definova´na stejneˇ jako sce´na 3, ovsˇem povoluje o stupenˇ hlubsˇ´ı u´rovenˇ deˇlenı´, tedy do opeˇt u´rovneˇ 5. Prˇ´ıklad sce´ny s 16 prˇeka´zˇkami a dveˇma pohyblivy´mi hrozbami je uveden na obra´zku 8.1. Vlevo vidı´me samotnou sce´nu spolecˇneˇ s cestou nalezenou 40

Obra´zek 8.1: Prˇ´ıklad sce´ny zpracova´vane´ aplikacı´. mezi dveˇma proteˇjsˇ´ımi rohy reprezentovane´ho prostoru. Uprostrˇed jsou na sce´neˇ zobrazeny hodnoty vah mapy prˇeka´zˇek. Cˇ´ım sveˇtlejsˇ´ı barva, tı´m veˇtsˇ´ı cˇa´st dane´ho bloku zaujı´majı´ prˇeka´zˇky a naopak. Vpravo pak je pak v te´zˇe sce´neˇ zobrazena samotna´ adaptivnı´ mrˇ´ızˇka.

8.3 8.3.1

Provedene´ testy a jejich vy´sledky Rychlost operacı´ split a merge v za´vislosti na povolene´ hloubce u´rovneˇ

Meˇrˇenı´ bylo zameˇrˇeno na vlastnı´ adaptivnı´ mrˇ´ızˇku a zpracova´nı´ prˇeka´zˇek, hrozeb i samotny´ algoritmus hleda´nı´ cesty byly odpojeny. Meˇrˇenı´ tedy neprobı´halo nad vy´sˇe definovany´mi testovacı´mi sce´nami. Meˇrˇeny byly pouze cˇiste´ rychlosti operacı´ split a merge. Pro meˇrˇenı´ byl pouzˇit jeden za´kladnı´ cluster (u´rovneˇ 0), ktery´ na´sledneˇ umeˇly´m za´sahem kompletneˇ rozdeˇlen na potomky azˇ do pozˇadovane´ u´rovneˇ a na´sledneˇ byly tyto noveˇ vytvorˇene´ clustery opeˇtovneˇ sloucˇeny do pu˚vodnı´ho jedine´ho. Prˇi kazˇde´m splitu do nizˇsˇ´ı u´rovneˇ je bunˇka sı´teˇ rozdeˇlena na 2d∗n buneˇk dcerˇiny´ch, kde n je u´rovenˇ zanorˇenı´ a d je dimenze, tedy v nasˇem prˇ´ıpadeˇ 41

level 0 1 2 3 4 5 6

pocet clusteru pocet engramu 1 8 9 27 73 179 585 1395 4681 11123 37449 88947 299593 711539

Tabulka 8.1: Exponencia´lnı´ na´ru˚st pocˇtu elementu˚ sı´teˇ s rostoucı´ u´rovnı´ deˇlenı´.

3. Tento exponencia´lnı´ na´ru˚st mnozˇstvı´ elementu˚ sı´teˇ (buneˇk a vrcholu˚) prˇi plne´m deˇlenı´ jedne´ bunˇky zachycuje tabulka 8.3.1. Vzhledem k tomu, zˇe zejme´na pro nizˇsˇ´ı u´rovneˇ zanorˇenı´ (relativneˇ nı´zky´ pocˇet vznikajı´cı´ch a zanikajı´cı´ch elementu˚) jsou operace velmi rychle´ (teoreticky zlomky milisekund), bylo meˇrˇenı´ prova´deˇno opakovaneˇ a vy´sledny´ cˇas pak vydeˇlen pocˇtem opakova´nı´. S rostoucı´ dobou potrˇebnou k provedenı´ dany´ch operacı´ jsem pak pocˇet opakova´nı´ snizˇoval: pro u´rovenˇ 1 10 000x, pro u´rovenˇ 2 5 000x, pro u´rovenˇ 3 1 000x, pro u´rovenˇ 4 500x, pro u´rovenˇ 5 100x a pro u´rovenˇ 6 50x. Vy´sledky zı´skane´ prˇi meˇrˇenı´ rychlostı´ operacı´ split a merge na jednotlivy´ch u´rovnı´ch maxima´lnı´ho povolene´ho deˇlenı´ ukazuje obra´zek 8.2. Z teˇchto vy´sledku˚ je dobrˇe patrne´, zˇe operace merge je rˇa´doveˇ rychlejsˇ´ı nezˇ split. Prˇi porovna´nı´ s pocˇty zpracova´vany´ch elementu˚ je take´ zrˇejme´, zˇe prodlouzˇenı´ doby trva´nı´ operacı´ zhruba odpovı´da´ na´ru˚stu objektu˚, ktere´ se musejı´ zpracova´vat. Zatı´mco na´ru˚st rychlosti operace merge se tempa ru˚stu elementu˚ drzˇ´ı pomeˇrneˇ prˇesneˇ (naprˇ. vzru˚st z prˇedposlednı´ na poslednı´ hodnotu prˇiblizˇneˇ 8x stejneˇ jako u pocˇtu elementu˚), u splitu je na´ru˚st o neˇco veˇtsˇ´ı (ve zminˇovane´m prˇ´ıpadeˇ prˇiblizˇneˇ 11x). Na vineˇ je pravdeˇpodobneˇ nutna´ kontrola, kdy prˇi vytva´rˇenı´ nove´ho clusteru je trˇeba nejprve odhalit v okolı´ jizˇ existujı´cı´ vrcholy, ktere´ lze pro cluster pouzˇ´ıt. 42

Obra´zek 8.2: Rychlost operacı´ split a merge v za´vislosti na povolene´ u´rovni deˇlenı´.

Obra´zek 8.3: Vy´voj pocˇtu buneˇk v cˇase. Svoji roli mu˚zˇe hra´t i to, zˇe zatı´mco prˇi operaci split vzˇdy vznikajı´ nove´ objekty (bunˇky a vrcholy), v pru˚beˇhu operace merge ne nutneˇ tyto objekty zanikajı´. Jsou pouze prˇipraveny ke zrusˇenı´, ktere´ ale rˇ´ıdı´ garbage collector prostrˇedı´ .NET.

8.3.2

Cˇasovy´ vy´voj mnozˇstvı´ buneˇk sı´teˇ

Sledovali jsme vy´voj pocˇtu buneˇk sı´teˇ v za´vislosti na cˇasove´m pru˚beˇhu adaptace jednotlivy´ch testovacı´ch sce´n. Tento vy´voj zachycuje obra´zek 8.3, kde vlevo vidı´me situaci na sce´na´ch 1 a 2 a vpravo na sce´na´ch 3 a 4. V pocˇa´tku pru˚beˇhu pozorujeme rychly´ na´ru˚st pocˇtu buneˇk z pocˇa´tecˇnı´

43

Obra´zek 8.4: Vy´voj rychlosti adaptace sı´teˇ v cˇase. nulove´ hodnoty, jak se sı´t’ adaptuje okolo prˇeka´zˇek v prostoru. Na´sledny´ pru˚beˇh pak vykazuje nepravidelne´ kolı´sa´nı´. To je zpu˚sobeno na´hodny´m pohybem hrozeb. Dokud se hrozba pohybuje v blı´zke´m okolı´ neˇktere´ z prˇeka´zˇek, jsou do nejnizˇsˇ´ı u´rovneˇ rozdeˇleny bunˇky v jejich spolecˇne´m okolı´. Jakmile se ovsˇem hrozba vzda´lı´ do pu˚vodneˇ pra´zdne´ho prostoru, zvedne hodnotu vah v dane´ oblasti a tı´m zpu˚sobı´ dalsˇ´ı deˇlenı´ a na´ru˚st pocˇtu buneˇk. Oblast, odkud se vzda´lila, ovsˇem zu˚sta´va´ kvu˚li prˇ´ıtomne´ prˇeka´zˇce i nada´le rozdeˇlena´.Toto chova´nı´ pozorujeme na vsˇech testovacı´ch sce´na´ch. Ve sce´na´ch 2 a 4 je toto kolı´sa´nı´ vı´ce patrne´, pocˇty buneˇk se beˇhem kolı´sa´nı´ lisˇ´ı daleko vy´razneˇji nezˇ v prˇ´ıpadeˇ sce´n 1 a 3. To je ale zpu˚sobeno tı´m, zˇe na´ru˚st pocˇtu buneˇk je s rostoucı´ u´rovnı´ exponencia´lnı´, jak jsme jizˇ videˇli v kapitole 8.3.1. Kazˇda´ dalsˇ´ı u´rovenˇ tak znamena´ mnohem vysˇsˇ´ı na´ru˚st pocˇtu elementu˚ sı´teˇ.

8.3.3

Rychlost adaptace sı´teˇ

Zajı´mavy´m aspektem je rychlost adaptace sı´teˇ v jednotlivy´ch iteracı´ch beˇhu programu. Abychom se zbavili na´hodny´ch vy´kyvu˚, nepouzˇili jsme prˇ´ımo nameˇrˇene´ hodnoty, ale jejich klouzavy´ pru˚meˇr se zvolenou periodou 8. Takto zpracovane´ hodnoty jsou zachyceny v grafech na obra´zku 8.4. Porovna´nı´m pru˚beˇhu˚ je dobrˇe patrne´, zˇe rychlost adaptace sı´teˇ vy´razneˇ za´visı´ zejme´na na maxima´lnı´ povolene´ u´rovni deˇlenı´ sı´teˇ. Na grafech mu˚44

Obra´zek 8.5: Vy´voj spotrˇeby pameˇti v cˇase. zˇeme opeˇt pozorovat kolı´sa´nı´ meˇrˇene´ doby, ktere´ stejneˇ jako v minule´m prˇ´ıpadeˇ souvisı´ s na´hodny´m pohybem hrozeb. Pokud si hrozba svy´m pohybem vynutı´ deˇlenı´ vı´ce buneˇk, je adaptace pomalejsˇ´ı.

8.3.4

Spotrˇeba pameˇti

Na obra´zku 8.5 je zna´zorneˇno mnozˇstvı´ pameˇti v MB, kterou aplikace v pru˚beˇhu iteracı´ alokuje. Nameˇrˇene´ hodnoty nemusı´ by´t u´plneˇ vypovı´dajı´cı´, nebot’jsou ovlivneˇny garbage collectorem prostrˇedı´ .NET. Prˇesto lze rˇ´ıci, zˇe podstatna´ cˇa´st pameˇti je alokova´na pro mapy prˇeka´zˇek a hrozeb, ktere´ naprˇ´ıklad pro rozmeˇr 32 udrzˇujı´ kazˇda´ 32 * 32 * 32 hodnot typu float. Toto mnozˇstvı´ zabrane´ pameˇti je ale po celou dobu beˇhu aplikace konstantnı´ a schodovite´ zmeˇny v grafech jsou tedy zpu˚sobeny samotnou adaptacı´ sı´teˇ, byt’poklesy nemusejı´ kvu˚li cˇinnosti garbage collectoru prostrˇedı´ .NET nasta´vat bezprostrˇedneˇ prˇi operacı´ch merge.

8.3.5

Za´vislost na pocˇtu prˇeka´zˇek

Dalsˇ´ım cı´lem nasˇeho testova´nı´ bylo oveˇrˇit, zda je chod aplikace za´visly´ na pocˇtu prˇeka´zˇek definovany´ch v prostoru u´lohy. K tomuto testu jsme prˇipravili cˇtyrˇi sce´ny, ktere´ se tentokra´t lisˇily pouze pocˇtem prˇeka´zˇek (256,

45

Obra´zek 8.6: Vy´voj pocˇtu buneˇk sı´teˇ pro ru˚zne´ pocˇty prˇeka´zˇek.

Obra´zek 8.7: Doby trva´nı´ adaptace sı´teˇ pro ru˚zne´ pocˇty prˇeka´zˇek. 512, 1024 a 2048). Rozlisˇenı´ map je ve vsˇech prˇ´ıpadech 64 x 64 x 64 a maxima´lnı´ povolena´ u´rovenˇ deˇlenı´ 4. Na obra´zku 8.6 vidı´me cˇasovy´ vy´voj pocˇtu˚ buneˇk pro vsˇechny definovane´ sce´ny a je patrne´, zˇe tyto pocˇty zrˇejmeˇ na mnozˇstvı´ prˇeka´zˇek prˇ´ımo za´visle´ nejsou. Rozdı´ly mezi jednotlivy´mi pru˚beˇhy jsou zpu˚sobeny zejme´na na´hodny´m rozmı´steˇnı´m prˇeka´zˇek. Stejna´ situace nasta´va´ i na obra´zku 8.7, kde je zachycen vy´voj dob trva´nı´ adaptace sı´teˇ a obra´zek 8.8,ukazujı´cı´ vy´voj dob hleda´nı´ cesty. Z du˚vodu odstraneˇnı´ na´hodny´ch vy´kyvu˚, jsme v obou prˇ´ıpadech opeˇt mı´sto nameˇ46

Obra´zek 8.8: Doby trva´nı´ hleda´nı´ cesty pro ru˚zne´ pocˇty prˇeka´zˇek. rˇeny´ch hodnot pouzˇili jejich klouzavy´ pru˚meˇr. Ukazuje se tedy, zˇe vy´sˇe uvedene´ operace nejsou na mnozˇstvı´ prˇeka´zˇek prˇ´ımo za´visle´. Jedinou operacı´ za´vislou na pocˇtu prˇeka´zˇek tedy zu˚sta´va´ preprocessing, ktery´ po spusˇteˇnı´ aplikace vsˇechny prˇeka´zˇky procha´zı´ a vyplnˇuje jejich mapu odpovı´dajı´cı´mi hodnotami vah. Po tomto u´vodu jizˇ ale mnozˇstvı´ prˇeka´zˇek za´sadnı´ roli nehraje.

8.3.6

Porovna´nı´ adaptivnı´ a pravidelne´ mrˇı´zˇky

Vzhledem k tomu, jak je aplikace implementova´na, bylo mozˇne´ v nı´ pro testova´nı´ nahradit adaptivnı´ mrˇ´ızˇku mrˇ´ızˇkou pravidelnou. Dı´ky tomu lze snadno tyto dva prˇ´ıstupy porovnat. Porovna´nı´ bylo provedeno nad dveˇma sce´nami z prˇedchozı´ kapitoly s rozlisˇenı´m map 64 x 64 x 64 a stejneˇ definovany´mi sce´nami nad pravidelnou mrˇ´ızˇkou o odpovı´dajı´cı´ch rozmeˇrech 64 x 64 x 64 buneˇk. Na obra´zku 8.9 vidı´me, zˇe zatı´mco u pravidelne´ mrˇ´ızˇky se cˇasy potrˇebne´ k nalezenı´ cesty pohybujı´ po celou dobu beˇhu programu v oblasti kolem 47

Obra´zek 8.9: Doby hleda´nı´ cesty nad pravidelnou a adaptivnı´ mrˇa´zˇkou. 400ms, cˇasy potrˇebne´ u adaptivnı´ mrˇ´ızˇky kolı´sajı´, jak se dalo prˇedpokla´dat. Podstatne´ ovsˇem je, zˇe tyto cˇasy zdaleka nedosahujı´ stejneˇ vysoke´ hodnoty. U sce´ny 4 je pru˚meˇrna´ hodnota prˇiblizˇneˇ 200ms a u sce´ny 2 dokonce jen asi 45ms. Vy´hoda pouzˇitı´ adaptivnı´ datove´ struktury je tedy jasneˇ patrna´. Podstatne´ je i to, zˇe obeˇ implementace da´vajı´ kvalitativneˇ si odpovı´dajı´cı´ vy´sledky. Optimalita nalezene´ cesty byla meˇrˇena pomocı´ va´hy nebezpecˇ´ı na nalezene´ trase. Hodnota te´to va´hy byla meˇrˇena ve vsˇech uzlech, z nichzˇ se cesta skla´dala, a z teˇchto hodnot bylo vybra´no maximum. Maxima byla zaznamena´na beˇhem chodu aplikace a na´sledneˇ prolozˇena polynomia´lnı´ regresı´ trˇetı´ho rˇa´du. Cˇ´ım nizˇsˇ´ı maxima zı´ska´va´me, tı´m lepsˇ´ı je kvalita dosazˇene´ho vy´sledku. Obra´zek 8.10 porovna´va´ pru˚beˇhy maxim pro jednotlive´ sce´ny a je patrne´, zˇe si dosazˇene´ vy´sledky prˇiblizˇneˇ odpovı´dajı´. Rozdı´ly jsou stejneˇ jako drˇ´ıve zpu˚sobeny na´hodny´m rozmı´steˇnı´m prˇeka´zˇek.

48

Obra´zek 8.10: Vzda´lenost cesty od prˇeka´zˇek.

8.3.7

Pocˇet buneˇk sı´teˇ v za´vislosti na rozlozˇenı´ prˇeka´zˇek a hrozeb

Beˇhem prˇedchozı´ch testu˚ se jasneˇ projevila za´vislost stavu adaptivnı´ mrˇ´ızˇky na rozmı´steˇnı´ prˇeka´zˇek a hrozeb v reprezentovane´m prostoru. Pokud je jejich rozmı´steˇnı´ takove´, zˇe zu˚sta´vajı´ v prostoru dostatecˇneˇ velke´ volne´ oblasti, je mrˇ´ızˇka v teˇchto oblastech nerozdeˇlena´ a obsahuje tak mensˇ´ı pocˇet buneˇk. Oblasti obsazene´ jsou naopak rozdeˇleny do nejvysˇsˇ´ı mozˇne´ u´rovneˇ. Hranice mezi obsazeny´mi a neobsazeny´mi oblastmi jsou pak adaptova´ny cˇa´stecˇneˇ, podle klesajı´cı´ho vlivu prˇeka´zˇek a hrozeb. Pokud je ovsˇem prˇeka´zˇek dostatecˇne´ mnozˇstvı´ nebo jsou rozmı´steˇny vı´ceme´neˇ rovnomeˇrneˇ po cele´m objemu prostoru, je mrˇ´ızˇka adaptova´na do nejvysˇsˇ´ı povolene´ u´rovneˇ prakticky cela´. Protozˇe ma´ kazˇda´ prˇeka´zˇka i hrozba definovany´ urcˇity´ rozsah vlivu na va´hy v mapa´ch i mimo svu˚j vlastnı´ objem, cˇasto jsou rozdeˇleny i bunˇky v prostora´ch mezi teˇmito objekty, kde se i prˇes jejich neprˇ´ıtomnou vlivy blı´zky´ch objektu˚ nascˇ´ıtajı´ prˇes stanovenou mez. Modifikace vy´pocˇtu va´hove´ funkce a samotne´ho zpracova´nı´ prˇeka´zˇek 49

a hrozeb mu˚zˇe tak chova´nı´ cele´ aplikace velmi vy´razneˇ ovlivnit. Jejich vhodnou zmeˇnou by bylo zrˇejmeˇ mozˇne´ rozdeˇlova´nı´ volne´ho prostoru mezi objekty a v jejich bezprostrˇednı´ blı´zkosti vy´razneˇji omezit.

50

Kapitola 9 Modifikace povrchu 9.1

Potrˇebna´ rozsˇı´rˇenı´ a u´pravy

Pro u´lohu modifikace povrchu jsem pouzˇil zcela nepozmeˇneˇnou adaptivnı´ strukturu ve formeˇ, v jake´ byla vyvinuta pro pu˚vodnı´ zada´nı´ a popsa´na v kapitole 6.2. Zmeˇny si vsˇak pochopitelneˇ vyzˇa´dala uka´zkova´ aplikace. V te´ vyuzˇ´ıva´m pu˚vodnı´ metody volajı´cı´ adaptaci sı´teˇ, syste´m pra´ce s hrozbami a vizualizacˇnı´ cˇa´st. Ko´d starajı´cı´ se o vyhleda´va´nı´ cesty, pohyb agentu˚ a zpracova´nı´ prˇeka´zˇek nebyl pouzˇit. Syste´m pohybu hrozeb jsem rozsˇ´ırˇil o specifickou hrozbu prˇedstavujı´cı´ „razı´tko“ modifikujı´cı´ povrch a upravil jeho vizualizaci. Razı´tko je pro jednoduchost reprezentova´no koulı´, ktera´ se prˇi sve´m pohybu otiskuje do povrchu kva´dru tvorˇene´ho jednou za´kladnı´ bunˇkou adaptivnı´ mrˇ´ızˇky. Koule do kva´dru opakovaneˇ vnika´ a zase jej opousˇtı´, cˇ´ımzˇ vyvola´va´ adaptaci mrˇ´ızˇky obeˇma smeˇry. Pozˇadavkem u´lohy bylo vytvorˇit pokud mozˇno veˇrny´ otisk prˇedmeˇtu v rea´lne´m cˇase. Jelikozˇ je adaptivnı´ mrˇ´ızˇka tvorˇena´ krychlovy´mi bunˇkami, znamena´ veˇrny´ otisk male´ rozmeˇru teˇchto krychlicˇek v otiskove´ oblasti a tedy vysokou u´rovenˇ deˇlenı´ sı´teˇ. Jizˇ prˇedchozı´ testy ovsˇem odhalily, zˇe nejvy´znamneˇjsˇ´ım parametrem ovlivnˇujı´cı´m rychlost adaptace, je pra´veˇ 51

Obra´zek 9.1: Uka´zka otiskova´nı´ razı´tka do materia´lu. maxima´lnı´ povolena´ u´rovenˇ deˇlenı´ z du˚vodu exponencia´lnı´ho na´ru˚stu pocˇtu elementu˚ sı´teˇ, jak je uvedeno v kapitole 8.3.1.

9.2

Testova´nı´

Pro meˇrˇenı´ jsem prˇipravil sce´nu cˇ´ıtajı´cı´ pra´zdnou bunˇku adaptivnı´ mrˇ´ızˇky a kulove´ razı´tko, ktere´ se do bunˇky do poloviny zanorˇ´ı a tı´m zpu˚sobı´ jejı´ adaptaci. Uka´zka sce´ny je uvedena na obra´zku 9.1. Meˇrˇene´ varianty se lisˇili jen maxima´lnı´ povolenou hloubkou deˇlenı´, otestoval jsem rozsah od 3 do 7. Nameˇrˇene´ hodnoty jsem opeˇt pro vyhlazenı´ na´hodny´ch vy´kyvu˚ prolozˇil jejich klouzavy´m pru˚meˇrem a vy´sledek je videˇt na obra´zku 9.2. V cˇasove´m pru˚beˇhu vidı´me pravidelne´ strˇ´ıda´nı´ na´ru˚stu˚ a poklesu˚ meˇrˇeny´ch cˇasu˚, ktere´ souvisı´ se zanorˇova´nı´m koule do materia´lu a jeho opeˇtovny´m opousˇteˇnı´m.Pokud je koule mimo materia´l, nenı´ mrˇ´ızˇka rozdeˇlena a cˇasy potrˇebne´ k zpracova´nı´ jednoho kroku Je patrne´, zˇe doba potrˇebna´ k adaptaci spolu s u´rovnı´ deˇlenı´ vy´razneˇ naru˚sta´. Jak se dalo ocˇeka´vat jizˇ z drˇ´ıveˇjsˇ´ıch meˇrˇenı´, nejsou vy´sledky prˇ´ılisˇ uspokojive´. Jizˇ na u´rovni deˇlenı´ 5 trva´ kazˇda´ adaptace prˇiblizˇneˇ 180ms. Syste´m je tedy schopen prove´st asi 5 – 6 vy´pocˇtu˚ beˇhem jedne´ vterˇiny, cozˇ uzˇ jisteˇ nemu˚zˇe pu˚sobit plynuly´m dojmem. Doba tedy prˇesta´va´ by´t u´nosna´ pro jake´koliv otiskova´nı´ v rea´lne´m cˇase. Nameˇrˇene´ cˇasy navı´c postihujı´

52

Obra´zek 9.2: Rychlost adaptace v za´vislosti na u´rovni detailu˚ pouze vlastnı´ vy´pocˇet a nijak nezohlednˇujı´ dobu potrˇebnou k vizualizaci. Prˇi rea´lne´m pouzˇitı´ by tedy potrˇebne´ cˇasy jesˇteˇ vzrostly. Je trˇeba si uveˇdomit, zˇe omezena´ hloubka deˇlenı´ vy´znamneˇ ovlivnˇuje kvalitu vy´sledne´ho otisku. Obecneˇ rozdeˇlenı´ do n-te´ u´rovneˇ prˇinese schopnost rozlisˇovat detaily otisku jen do rozmeˇru 1/2n de´lky hrany pu˚vodnı´ bunˇky. Prˇi pouzˇitı´ jesˇteˇ u´nosne´ hloubky deˇlenı´ 4 tedy dostaneme pomeˇrneˇ hruby´ otisk slozˇeny´ z krychlicˇek o hraneˇ 1/16 de´lky hrany za´kladnı´ bunˇky, cozˇ zdaleka nemusı´ by´t vizua´lneˇ uspokojivy´ vy´sledek

53

Kapitola 10 Za´veˇr V ra´mci diplomove´ pra´ce jsem prozkoumal neˇkolik ru˚zny´ch variant mozˇny´ch adaptivnı´ch deˇlenı´ prostoru a navrhl a implementoval 3D adaptivnı´ mrˇ´ızˇku zalozˇenou na silneˇ modifikovane´ strukturˇe octtree. V pru˚beˇhu na´vrhu se postupneˇ podarˇilo vyrˇesˇit vsˇechny za´sadnı´ proble´my zpu˚sobene´ prˇechodem z 2D do 3D prostoru. Vy´sledna´ implementace pak prˇekonala pu˚vodneˇ skepticka´ ocˇeka´va´nı´ a v aplikaci pro hleda´nı´ cest je vy´sledna´ mrˇ´ızˇka pameˇt’oveˇ i rychlostneˇ uspokojiva´. I porovna´nı´ s obycˇejnou pravidelnou mrˇ´ızˇkou jasneˇ demonstruje vy´hody pouzˇite´ho rˇesˇenı´. S vyuzˇitı´m navrzˇene´ datove´ struktury pak Bc. Petr Brozˇ u´speˇsˇneˇ vytvorˇil kompletnı´ syste´m hleda´nı´ cest v nezna´me´m dynamicke´m 3D prostrˇedı´ a cˇla´nky zaby´vajı´cı´ se tı´mto navrzˇeny´m syste´mem byly nabı´dnuty na neˇkolik mezina´rodnı´ch konferencı´. Druha´ cˇa´st pra´ce, aplikace navrzˇene´ adaptivnı´ mrˇ´ızˇky v ra´mci odlisˇne´ u´lohy, jizˇ tak u´speˇsˇna´ nebyla. Jasneˇ se uka´zal za´sadnı´ rozdı´l mezi pouzˇitı´m adaptivnı´ mrˇ´ızˇky jako pomocne´ datove´ struktury (prˇ´ıpad hleda´nı´ cest) a jako modelu pro vizualizaci, jak tomu bylo v prˇ´ıpadeˇ druhe´ u´lohy. Zatı´mco v prvnı´m prˇ´ıpadeˇ jsou na mrˇ´ızˇku kladeny na´roky pouze aplikacı´ a uspokojivy´ch vy´sledku˚ je mozˇno dosa´hnout i prˇi nizˇsˇ´ıch u´rovnı´ch deˇlenı´, v prˇ´ıpadeˇ druhe´m je prakticky vzˇdy pozˇadova´na vysoka´ u´rovenˇ detailu˚ minimalizujı´cı´ „hranatost“ vizualizovany´ch modelu˚. Meˇrˇenı´ jasneˇ uka´54

zala, zˇe pro dosazˇenı´ takovy´ch detailu˚ implementovana´ mrˇ´ızˇka vhodna´ nenı´. Ota´zka do budoucna mu˚zˇe znı´t, jak by testy dopadli prˇi pouzˇitı´ jednodusˇsˇ´ı struktury, ktera´ nebude poskytovat grafove´ rozhranı´, jezˇ nebylo pro u´lohu trˇeba. Prˇesto ale pokusy proka´zaly, zˇe adaptivnı´ mrˇ´ızˇka je prˇipravena natolik obecneˇ, zˇe ji lze aplikovat bez jaky´chkoliv u´prav i v naprosto jine´m vhodne´m typu u´lohy, nezˇ pro jaky´ byla navrzˇena. V budoucı´ pra´ci by mohlo by´t zajı´mave´ rozsˇ´ırˇit mrˇ´ızˇku o prioritnı´ fronty, jednu pro bunˇky urcˇene´ k rozdeˇlenı´ a jednu pro bunˇky urcˇene´ ke slucˇova´nı´. Bylo by zajı´mave´ prozkoumat, zda nelze vhodny´m rˇazenı´m takovy´ch front dosa´hnout urychlenı´ procesu adaptace a u´spor syste´movy´ch prostrˇedku˚. Podneˇtny´m smeˇrem by mohlo by´t take´ zkouma´nı´ ru˚zny´ch krite´riı´ pro rˇazenı´ v teˇchto fronta´ch. V aplikaci pro hleda´nı´ cest by bylo take´ vhodne´ prozkoumat detailneˇji va´hovou funkci rozhodujı´cı´ o rozdeˇlenı´ a slucˇova´nı´ buneˇk, ktera´ ma´ za´sadnı´ vliv na chova´nı´ cele´ aplikace. Prozkoumat prˇesny´ vliv jednotlivy´ch zapocˇ´ıta´vany´ch parametru˚ a urcˇit neˇkolik mozˇny´ch va´hovy´ch funkcı´ pro ru˚zna´ chova´nı´ sı´teˇ, naprˇ´ıklad pro prˇesneˇjsˇ´ı odlisˇenı´ obsazene´ho a volne´ho prostoru se snahou omezit deˇlenı´ oblastı´ sousedı´cı´ch s prˇeka´zˇkami. Takova´ zmeˇna by ve vy´sledku mohla znamenat mensˇ´ı pocˇet buneˇk v sı´ti a proto dalsˇ´ı urychlenı´ jejı´ adaptace. Zajı´mavy´m pokusem by mohlo by´t i adaptivnı´ urcˇova´nı´ maxima´lnı´ povolene´ hloubky deˇlenı´ v za´vislosti na vypocˇ´ıtany´ch vaha´ch v ru˚zny´ch oblastech reprezentovane´ho prostoru. Jako pozitivnı´ zmeˇnu bych videˇl i jiny´ zpu˚sob reprezentace prˇeka´zˇek. V momenta´lnı´ implementaci je prostor prˇeka´zˇky rozdeˇlen na maxima´lnı´ povolenou u´rovenˇ v cele´m objemu prˇeka´zˇky. Prˇitom jejı´ vnitrˇek nenı´ zajı´mavy´ a vznikle´ bunˇky jen zpomalujı´ rychlost cele´ho syste´mu. Vola´nı´ adaptace sı´teˇ pouze okolo povrchu prˇeka´zˇek by mohlo mı´t rovneˇzˇ pozitivnı´ dopad na rychlost. Diplomova´ pra´ce uspokojiveˇ splnila stanovene´ cı´le a za´rovenˇ klade mozˇnost dalsˇ´ıch u´prav a vy´voje cele´ho syste´mu do budoucna.

55

Pouzˇite´ zkratky a pojmy ASM – Adaptive Spatial Memory (adaptivnı´ prostorova´ pameˇt’) BSP Tree – Binary Space Partitioning (stromove´ bina´rnı´ deˇlenı´ prostoru) CLUSTER – bunˇka adaptivnı´ sı´teˇ ENGRAM – vrchol adaptivnı´ sı´teˇ GEOMORPH – plynuly´ prˇechod mezi dveˇma u´rovneˇmi detailu˚ modelu (v pra´ci je pouzˇ´ıva´na pocˇesˇteˇna´ varianta GEOMORF) kD Tree – k-rozmeˇrny´ strom LOD – Level of Detail (u´rovenˇ detailu˚) MERGE – operace sloucˇenı´ potomku˚ do rodicˇovske´ bunˇky OCTTREE – stromova´ struktura adaptivnı´ho deˇlenı´ 3D prostoru QUADTREE – stromova´ struktura adaptivnı´ho deˇlenı´ 2D prostoru SPLIT – operace deˇlenı´ bunˇky na potomky

56

Literatura [1] Hoppe, Hugues. Progressive Meshes. Computer Graphics, SIGGRAPH’96 Proceedings, Microsoft Research, 1996. [2] Hoppe, Hugues. View-Dependent Refinement of Progressive Meshes. Computer Graphics, SIGGRAPH’97 Proceedings, Microsoft Research, 1997. [3] Hoppe, Hugues; DeRose, Tony; Duchamp, Tom; McDonald, John; Stuetzle, Werner. Mesh Optimalization. Computer Graphics, SIGGRAPH’93 Proceedings, 1993. ˇ a´ra, Jirˇ´ı; Benesˇ, Bedrˇich; Felkel, Petr. Modernı´ pocˇ´ıtacˇova´ grafika. Com[4] Z puter Press, 1998. [5] Brozˇ, Petr. Path Planning in Combined 3D Grid and Graph Environment. Proceedings of the 10th Central European Seminar on Computer Graphics, 2006. [6] Apu, Russel Ahmed; Gavrilova, Marina. Adaptive Spatial Memory Representation for Real-Time Motion Planning. Proceedings of the 8th International Conference on Computer Graphics and Artificial Intelligence, 2005. [7] http://en.wikipedia.org/wiki/BSP tree. [8] http://en.wikipedia.org/wiki/Voronoi diagram. [9] http://en.wikipedia.org/wiki/Kd tree.

57

Prˇı´loha A Class diagramy

Obra´zek 10.1: Class diagramy trˇ´ıd a interfacu˚ adaptivnı´ datove´ stuktury.

59

Prˇı´loha B Path planning in combined 3D grid and graph environment

Prˇı´loha C Path planning in dynamic environment using an adaptive mesh