}w !"#$%&'()+,-./012345
MASARYKOVA UNIVERZITA V BRNEˇ FAKULTA INFORMATIKY
Vizualizace vybrany´ch geometricky´ch algoritmu˚ pro potrˇeby vy´uky DIPLOMOVA´ PRA´CE
Bc. Ondrˇej Skutka
Brno, podzim 2005
Prohla´sˇenı´ Prohlasˇuji, zˇe tato diplomova´ pra´ce je my´m pu˚vodnı´m autorsky´m dı´lem, ktere´ jsem vypracoval samostatneˇ. Vsˇechny zdroje, prameny a literaturu, ktere´ jsem prˇi vypracova´nı´ pouzˇ´ıval nebo z nich cˇerpal, v pra´ci rˇa´dneˇ cituji s uvedenı´m u´plne´ho odkazu na prˇ´ıslusˇny´ zdroj.
Vedoucı´ pra´ce: Ing. Petr Ada´mek ii
Podeˇkova´nı´ Zde bude uvedeno „podeˇkova´nı´“ ...
iii
Shrnutı´ Abstrakt
iv
Klı´cˇova´ slova Computational geometry, software visualization, pocˇ´ıtacˇova´ grafika, geometricke´ algoritmy, vy´uka, vizualizace
v
Obsah ´ vod . . . . . . . . . . . . . . . . . . . . . . . . U Geometricke´ algoritmy . . . . . . . . . . . . . ´ vod . . . . . . . . . . . . . . . . . . . . . 2.1 U 2.2 Vy´pocˇet konvexnı´ho obalu . . . . . . . . . . 3 Vizualizace geometricky´ch algoritmu˚ . . . . . 3.1 Vizualizace algoritmu˚ . . . . . . . . . . . . . 3.2 Proble´my 3-D vizualizace . . . . . . . . . . . 3.3 Pouzˇ´ıvane´ prˇ´ıstupy k zobrazova´nı´ algoritmu˚ 3.4 Vizualizace vy´pocˇtu konvexnı´ho obalu . . . . 4 Implementace . . . . . . . . . . . . . . . . . . . 4.1 Cı´le projektu . . . . . . . . . . . . . . . . . . 4.2 Charakteristika soucˇasne´ho stavu . . . . . . . 4.3 Na´vrh rˇesˇenı´ . . . . . . . . . . . . . . . . . 4.4 proble´my prˇi rˇesˇenı´ . . . . . . . . . . . . . . 4.5 Implementace vy´pocˇtu konvexnı´ho obalu . . . 5 Zhodnocenı´ dosazˇeny´ch vlastnı´ch vy´sledku˚ . 5.1 Dosazˇene´ schopnosti syste´mu . . . . . . . . . 5.2 Negativa syste´mu . . . . . . . . . . . . . . . 5.3 Budoucnost . . . . . . . . . . . . . . . . . . 6 Za´veˇr . . . . . . . . . . . . . . . . . . . . . . . . 7 Trademarks . . . . . . . . . . . . . . . . . . . . A FAQ . . . . . . . . . . . . . . . . . . . . . . . . . 1 2
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
2 3 3 4 6 6 8 10 15 17 17 17 19 21 22 23 23 23 24 25 26 29
1
Kapitola 1
´ vod U vizualizace geometricky´ch algoritmu
2
Kapitola 2
Geometricke´ algoritmy ´ vod 2.1 U Tato pra´ce pojedna´va´ o vizualizaci geometricky´ch algoritmu˚. Prˇedem te´to pra´ce bychom si tedy meˇli vyjasnit alesponˇ tento za´kladnı´ pojem, nebot’ nenı´ dostatecˇneˇ jasny´ ani jednotneˇ definovany´ a je tedy namı´steˇ jej trochu zprˇesnit. Tato kapitola pojedna´va´ o tom, co budeme pro u´cˇely te´to pra´ce povazˇovat za geometricky´ algoritmus, na´sledujı´cı´ kapitola rozebı´ra´ mozˇnosti, zpu˚soby a prˇ´ınosy jeho vizualizace. Nebude zde vysveˇtlova´no, co je to algoritmus. Prˇesnou definici si laskavy´ cˇtena´rˇ jisteˇ dohleda´1 a pro nasˇe u´cˇely stacˇ´ı intuitivnı´ cha´pa´nı´ tohoto slova. Co je to geometricky´ algoritmus lze sice take´ cha´pat intuitivneˇ, ale prˇesto zde uvedeme obecnou definici tohoto pojmu: Definice 1. Algoritmus, ktery´ rˇesˇ´ı proble´my zadane´ pomocı´ geometricky´ch prostrˇedku˚ se nazy´va´ geometricky´.[Wikipedia, 2004] Takova´to definice je velmi sˇiroka´, nevhodna´ pro nasˇe u´cˇely. Takto definovane´ geometricke´ algoritmy totizˇ zahrnujı´ naprˇ´ıklad postupy pro na´vrh a verifikaci tisˇteˇny´ch spoju˚, cozˇ nenı´ oblast, kterou si tato pra´ce klade za cı´l postihnout. Je tedy nutne´ zu´zˇit tuto definici tak, aby co nejle´pe vystihovala za´meˇr te´to pra´ce. Upravme tedy definici geometricke´ho algoritmu na´sledujı´cı´m zpu˚sobem: Definice 2. Algoritmus, jehozˇ vy´pocˇet probı´ha´ v ra´mci geometricky´ch prostrˇedku˚ se nazy´va´ geometricky´. Pu˚vodnı´ definice vymezovala algoritmy, jejichzˇ zada´nı´ lze vizualizovat, ale jizˇ nerozlisˇovala, zda lze zobrazovat i pru˚beˇh vy´pocˇtu takove´ho algoritmu. Naoko drobnou zmeˇnou definice jsme vsˇak zı´skali algoritmy, prˇi jejichzˇ vy´pocˇtu se meˇnı´ neˇjake´ geometricky interpretovatelne´ promeˇnne´, 1. naprˇ´ıklad na http://en.wikipedia.org/wiki/Algorithm
3
2. GEOMETRICKE´ ALGORITMY ktere´ jizˇ mu˚zˇeme vizualizovat. A pra´veˇ o tyto algoritmy na´m jde. O zpu˚sobu sledova´nı´ takovy´chto algoritmu˚ bude pojedna´no v kapitole 3.
2.2 Vy´pocˇet konvexnı´ho obalu Pro na´zornost uved’me prˇ´ıklad geometricke´ho algoritmu, ktery´ splnˇuje nasˇi definici. Za´meˇrneˇ je zde uveden ne prˇ´ılisˇ jednoduchy´ algoritmus, a to z toho du˚vodu, aby mohla by´t pozdeˇji podrobneˇ rozebra´na jeho vizualizace. Algoritmus pro vy´pocˇet konvexnı´ho obalu bodu˚ ve trˇech dimenzı´ch metodou rozdeˇl a panuj [Preparata and Hong, 1977] je zobecneˇnı´m podobne´ho 2D algoritmu. Rekurzivneˇ rozdeˇlujeme mnozˇinu bodu˚ na dveˇ disjunktnı´, stejneˇ velke´ mnozˇiny (levou a pravou), spocˇ´ıta´me jejich konvexnı´ obal a vy´sledne´ dva disjunktnı´ konvexnı´ mnohosteˇny „sesˇijeme“. Rekurzi ukoncˇ´ıme v okamzˇiku, kdy zby´vajı´ cˇtyrˇi body, jejichzˇ konvexnı´ obal umı´me trivia´lneˇ vytvorˇit. Klı´cˇovy´ okamzˇik je ono „sesˇ´ıva´nı´ “: Algoritmus 1 Vytva´rˇenı´ konvexnı´ho mnohosteˇnu spojenı´m dvou disjunktnı´ch konvexnı´ch mnohosteˇnu˚ [Joskowicz, 2005] 1: Oznacˇme si A (respektive B) mnoz ˇ inu bodu˚ tvorˇ´ıcı´ch svu˚j respektivnı´ mnohosteˇn 2: Nalezneme nejspodneˇjsˇ´ı hranu spojujı´cı´ body z A a B. 3: Kolem nove´ u ´ secˇky naklonı´me plochu Π k nejblizˇsˇ´ımu bodu p. 4: repeat 5: Vytvorˇ´ıme novy´ polygon (abp) a opakujeme nakla´neˇnı´ kolem nove´ hrany, tvorˇene´ bodem p a jeho proteˇjsˇkem (bud’ a nebo b). 6: until Balenı´ je dokoncˇeno. 7: Smaz ˇ eme skryte´ polygony sledova´nı´m polygonu okolo A a B, jejichzˇ hrany lezˇ´ı na hranici sˇvu. Toto je samozrˇejmeˇ pouze letmy´ na´stin algoritmu2 . Naprˇ´ıklad se pro jednoduchost prˇedpokla´da´, zˇe pu˚vodnı´ mnozˇina ma´ pra´veˇ (n + 1)2 prvku˚. Dalsˇ´ı zamlcˇeny´ proble´m je ota´cˇenı´ roviny. Dı´ky konvexnosti obou mnohosteˇnu˚ by stacˇilo zkusit natocˇit rovinu ke kazˇde´mu bodu spojene´ho hranou s bodem a nebo b a porovnat jejı´ norma´lu s norma´lou prˇedchozı´ roviny. To by ovsˇem vedlo k neu´meˇrne´ slozˇitosti O(n2 ). Musı´me tedy sledovat vı´teˇze mnozˇin A a B a testovat pouze je, dı´ky cˇemuzˇ kazˇdy´ bod otestujeme nejvy´sˇe dvakra´t a tedy tı´mto zpu˚sobem doka´zˇeme tyto mnozˇiny sesˇ´ıt v cˇase O(n), celkova´ slozˇitost algoritmu bude O(nlog(n)). Tento algoritmus je sice teore2. Podrobny´, 15 stran dlouhy´ popis lze najı´t naprˇ´ıklad v [Edelsbrunner, 1987].
4
2. GEOMETRICKE´ ALGORITMY ticky du˚lezˇity´, ale jeho implementace je celkem slozˇita´ a v praxi se nepouzˇ´ıva´ tak cˇasto, jako jine´, byt’asymptoticky pomalejsˇ´ı algoritmy.[O’Rourke, 1994]
5
Kapitola 3
Vizualizace geometricky´ch algoritmu˚ 3.1 Vizualizace algoritmu˚ Nynı´ se dosta´va´me k za´sadnı´mu te´matu, a tı´m je vizualizace algoritmu˚. Jak je definovana´ vizualizace algoritmu? Jake´ jsou mozˇnosti zobrazova´nı´ algoritmu˚ a co prˇina´sˇejı´? Jake´ metody zobrazova´nı´ algoritmu˚ se pouzˇ´ıvajı´? V Oxfordske´m slovnı´ku je vizualizace definova´na takto: Definice 3. Schopnost nebo proces vytva´rˇenı´ menta´lnı´ho obrazu nebo prˇedstavy neˇcˇeho, co nenı´ zrovna videˇt.1 Z te´to definice jasneˇ vyply´va´, zˇe vizualizace se neomezuje pouze na zobrazovacı´ techniky. Vizualizace mu˚zˇeme stejneˇ tak dobrˇe vytva´rˇet naprˇ´ıklad pomocı´ zvukovy´ch prostrˇedku˚ (vypra´veˇnı´). Dalsˇ´ı pojem – „softwarova´ vizualizace“ dobrˇe definovali Price, Baecker a Small [Price et al., 1993]: Definice 4. Definujme softwarovou vizualizaci jako pouzˇitı´ dovednostı´ typografie, graficke´ho designu, animace a kinematografie s modernı´ technologiı´ interakce cˇloveˇka s pocˇ´ıtacˇem za u´cˇelem usnadneˇnı´ pochopenı´ i efektivnı´ho pouzˇitı´ pocˇ´ıtacˇove´ho softwaru.2 Podle Price, Baecker a Small [Price et al., 1993] je vizualizace algoritmu˚ soucˇa´stı´ softwarove´ vizualizace. Samotnou vizualizaci algoritmu˚ popisujı´ takto: Definice 5. Vizualizacı´ (cˇi animacı´) algoritmu˚ rozumı´me vizualizaci vysokou´rovnˇove´ho popisu cˇa´sti softwaru, na rozdı´l od vizualizace ko´du nebo 1. The power or process of forming a mental picture or vision of something not actually present to the sight. 2. We define SV as the use of the crafts of typography, graphic design, animation, and cinematography with modern human-computer interaction technology to facilitate both the human understanding and effective use of computer software.
6
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ dat (ktere´ jsou druhem programove´ vizualizace3 ), kde je vizualizova´n skutecˇny´ implementovany´ ko´d.4 Stasko a Kerren v [Kerren and Stasko, 2002, strana 1] velmi dobrˇe popsali animaci algoritmu˚: Animace algoritmu vizualizuje chova´nı´ algoritmu vytva´rˇenı´m abstrakce dat i operacı´ algoritmu. Na pocˇa´tku prˇevede soucˇasny´ stav algoritmu do obra´zku, ktery´ je pak animova´n na za´kladeˇ operacı´ mezi dveˇma na´sledujı´cı´mi stavy v beˇhu algoritmu. Animova´nı´ algoritmu umozˇnˇuje lepsˇ´ı pochopenı´ toho, jak algoritmus pracuje uvnitrˇ, a nadto jesˇteˇ ozrˇejmuje jeho nedostatky a vy´hody a tı´m umozˇnˇuje jeho dalsˇ´ı vylepsˇenı´. Vizualizace, neˇkdy te´zˇ animace algoritmu˚ je tedy zna´zorneˇnı´ postupu algoritmu. Jeho u´cˇelem by´va´ snadne´ pochopenı´ podstaty dane´ho algoritmu ´ cˇelem neˇktery´ch v souladu s prˇ´ıslovı´m, zˇe obra´zek vyda´ za tisı´c slov. U vizualizacı´ algoritmu˚ vsˇak mu˚zˇe by´t naprˇ´ıklad porovna´nı´ prˇ´ıstupu jednotlivy´ch algoritmu˚ ke stejne´mu proble´mu, nale´za´nı´ chyb v algoritmech nebo dokonce pouhe´ vysveˇtlenı´ proble´mu. Takovy´mi vizualizacemi se vsˇak nebudeme zaby´vat a nada´le se budeme veˇnovat pouze zobrazova´nı´ algoritmu˚ za u´cˇelem jejich pochopenı´. Ota´zkou zu˚sta´va´ jakou hraje animace algoritmu˚ roli v jejich ucˇenı´. Na prvnı´ pohled se jisteˇ zda´, zˇe algoritmus, ktery´ vidı´me prˇed sebou beˇzˇet doka´zˇeme le´pe pochopit, nezˇ algoritmus, ktery´ si musı´me sami (cˇasto slozˇiteˇ) prˇedstavovat na za´kladeˇ popisu cˇi pseudoko´du. Ukazuje se vsˇak, zˇe ucˇenı´ algoritmu˚ pomocı´ jejich animacı´ nema´ tak vy´razny´ efekt, jaky´ bychom od neˇj ocˇeka´vali [Lawrence et al., 1994]. Naproti tomu aktivnı´ vytva´rˇenı´ animacı´ algoritmu˚ studenty je pro neˇ sice zdlouhave´, ale extre´mneˇ u´cˇinne´ [Stasko, 1997]. Pokud nechceme studenty prˇ´ılisˇ zateˇzˇovat, pak je nutna´ pecˇliva´ pra´ce prˇedna´sˇejı´cı´ho, ktery´ doka´zˇe prˇimeˇt studenty, aby si vytvorˇili pojı´tko mezi animacı´ algoritmu, textem a jeho pseudoko´dem [Kehoe and Stasko, 1996].
3. Programova´ vizualizace – pouzˇitı´ ru˚zny´ch technik k lepsˇ´ımu pochopenı´ pocˇ´ıtacˇove´ho programu.[Price et al., 1993] 4. Algorithm visualization (or animation) is understood to be the visualization of a high-level description of a piece of software which is in contrast to code or data visualization (which are collectively a kind of program visualization) where actual implemented code is visualized.
7
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚
3.2 Proble´my 3-D vizualizace Zameˇrˇme se nynı´ na proble´my prˇi zobrazova´nı´ 3-D algoritmu˚. Trˇi hlavnı´ proble´my jsou uvedeny v [Goldman et al., 1996]: Omezene´ vnı´ma´nı´ pohybu -- je teˇzˇke´ zjistit pohyb objektu v ose u´hlu pohledu (smeˇrem od pozorovatele nebo k pozorovateli). Trˇ´ırozmeˇrne´ objekty, ktere´ tı´m meˇnı´ svou velikost si lidska´ mysl jesˇteˇ doka´zˇe uveˇdomit, ale pro u´secˇky nebo proste´ body je jejich pru˚meˇtem na obrazovku tato informace ztracena. Prˇesahova´nı´ 3-D objektu˚ -- prˇi 2-D zobrazenı´ dvourozmeˇrny´ch objektu˚ cˇasto mu˚zˇeme rozmı´stit jednotlive´ objekty tak, aby se neprˇekry´valy. 3-D objekty lze podobneˇ snadno umı´stit v 3-D prostoru, ale prˇi jejich promı´ta´nı´ na 2-D obrazovku se nelze vyhnout jejich prˇekrytı´, a tedy snı´zˇenı´ prˇehlednosti sce´ny. Neadekva´tnost meˇrˇı´tka zobrazenı´ -- prˇi sˇpatne´m meˇrˇ´ıtku zobrazenı´ sce´ny (prˇ´ılisˇ male´m i prˇ´ılisˇ velke´m), mohou du˚lezˇite´ informace zu˚stat bez povsˇimnutı´. K teˇmto bodu˚m bychom mohli jesˇteˇ prˇipojit: Zobrazova´nı´ nekonecˇny´ch u´tvaru˚ -- pokud bychom chteˇli zobrazit plochu beˇzˇny´m zpu˚sobem, vyplnˇovala by na´m (azˇ na pa´r vy´jimek) cele´ zorne´ pole, cˇ´ımzˇ by zajiste´ znehodnotila nejen vsˇechny sve´ atributy, ale pravdeˇpodobneˇ by na´m i zakryla jine´ objekty. Jake´ jsou mozˇne´ prˇ´ıstupy k rˇesˇenı´ teˇchto proble´mu˚? •
Vzhledem k tomu, zˇe mnohe´ vznikajı´ projekcı´ 3-D prostoru na 2-D obrazovku, tedy ztra´tou jednoho rozmeˇru, je mozˇny´m rˇesˇenı´m zamezit pra´veˇ te´to ztra´teˇ. Tı´mto proble´mem se zaby´va´ stereoskopie. Nebudeme uvazˇovat metody, ktere´ jsou prˇ´ılisˇ drahe´, nebo jinak na´rocˇne´ na realizaci (a tudı´zˇ nevhodne´ pro vy´uku). Mozˇny´m levny´m rˇesˇenı´m zu˚sta´vajı´ metody zalozˇene´ na anaglyfech (nutne´ pouzˇ´ıt cˇervenomodre´ nebo cˇervenozelene´ bry´le) a na krˇ´ızˇenı´ smeˇru˚ pohledu˚ ocˇ´ı (sˇilha´nı´).
•
Dalsˇ´ı mozˇnostı´ je rozhy´bat pozici a smeˇr pohledu na sce´nu (kameru), nebot’ lidsky´ mozek si jizˇ chybeˇjı´cı´ rozmeˇr doka´zˇe doplnit. Problematicky´ ovsˇem je zpu˚sob, jaky´m by se kamera meˇla hy´bat. Tradicˇnı´ rotace kolem osy y s pohledem na pocˇa´tek sourˇadne´ho syste´mu na´m sice poskytne jasnou informaci o rozmı´steˇnı´ objektu˚ ve sce´neˇ, ale za´rovenˇ prˇispı´va´ ke zveˇtsˇenı´ mı´ry prˇesahova´nı´ objektu˚ a tı´m na´m rusˇ´ı 8
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ pohled na to podstatne´, co se v dane´ sce´neˇ deˇje. Uzˇivatel by jisteˇ uvı´tal, kdyby si o pozici a smeˇru pohledu na sce´nu mohl rozhodovat sa´m a tak by automaticky´ pohyb kamery nemeˇl jeho rozhodova´nı´ znemozˇnˇovat. Kamera by se tedy nemeˇla prˇ´ılisˇ vychylovat z uzˇivatelem dane´ pozice, ale za´rovenˇ by se meˇla hy´bat natolik, aby mu poskytla informace o rozmı´steˇnı´ objektu˚ ve sce´neˇ, naprˇ´ıklad nepatrny´m, kole´bavy´m pohybem. •
Prˇesahova´nı´ 3-D objektu˚ lze rˇesˇit pomocı´ jejich pru˚hlednosti. Toto je nezbytne´ naprˇ´ıklad pro roviny, ktere´ by mohly zakry´t celou sce´nu, ale pokud bychom se podı´vali naprˇ´ıklad na pru˚hledny´ mnohosteˇn, pak mu˚zˇeme teˇzˇko odhadnout, ktere´ steˇny a hrany vlastneˇ jsou na prˇivra´cene´ straneˇ mnohosteˇnu a ktere´ by naopak bez pru˚hlednosti videˇt nebyly. Nezobrazova´nı´ odvra´ceny´ch steˇn by bylo neprˇirozene´ a ˇ esˇenı´ tedy musı´ nutneˇ vedlo by ke zbytecˇne´ ztra´teˇ informacı´ o sce´neˇ. R pouzˇ´ıt neˇkterou z vy´sˇe uvedeny´ch technik stereometrie.
•
Proble´m zobrazova´nı´ prˇ´ımek a rovin lze rozdeˇlit na proble´m vnı´ma´nı´ jejich polohy uzˇivatelem a proble´m prˇekrytı´ jiny´ch objektu˚ (ty´ka´ se pouze rovin). Proble´m vnı´ma´nı´ polohy nekonecˇny´ch objektu˚ nelze rˇesˇit technikami stereometrie, nebot’ ty jsou zalozˇeny na ru˚zny´ch u´hlech pohledu na jeden objekt, ktere´ si cˇloveˇk spojı´ do trˇetı´ho rozmeˇru. Prˇ´ımka ani rovina vsˇak neobsahujı´ zˇa´dne´ body, na ktere´ by oko mohlo zaostrˇit a porovnat jejich polohu. Je tedy nutne´ oku trochu pomoci prˇida´nı´m vizua´lnı´ch prvku˚, ktere´ by si mohlo asociovat. Nejobecneˇjsˇ´ı prˇ´ıstup je pouzˇitı´ vhodne´ho nasvı´cenı´ sce´ny (se vzda´lenostı´ klesa´ jas bodu˚). To ale umozˇnı´ asociovat stejne´ body na prˇ´ımce cˇi rovineˇ pouze pomocı´ porovna´nı´ jejich jasu a tedy velmi neprˇesneˇ, nebot’se okolnı´ body lisˇ´ı jen minima´lnı´ zmeˇnou nasvı´cenı´. Dalsˇ´ı mozˇnostı´ je zdrsneˇnı´ povrchu takove´ho objektu (textura na rovineˇ). Jine´ rˇesˇenı´ se nabı´zı´ vhodnou reprezentacı´ nekonecˇny´ch objektu˚ jejich konecˇny´mi reprezentacemi (polygon mı´sto roviny), kde pozorovatel mu˚zˇe prˇesneˇ urcˇit koncove´ body, nebo lze vyuzˇ´ıt neˇjaky´ch restartovacı´ch znacˇek naprˇ´ıklad v podobeˇ stupnice na prˇ´ımce. Proble´m zakrytı´ jiny´ch objektu˚ rovinou lze rˇesˇit pomocı´ jizˇ zmı´neˇne´ pru˚hlednosti.
•
Pokud uzˇivatel nesleduje tu cˇa´st sce´ny, ve ktere´ se odehra´va´ podstatny´ proces algoritmu, syste´m by mu meˇl umozˇnit opakovanı´ tohoto procesu. 9
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ Je bohuzˇel zrˇejme´, zˇe zˇa´dne´ jednoduche´ (levne´) a bez vy´hrad u´cˇinne´ rˇesˇenı´ vsˇech teˇchto proble´mu˚ neexistuje. Neˇktera´ navrhovana´ rˇesˇenı´ urcˇity´ch proble´mu˚ majı´ totizˇ negativnı´ dopad na jine´ proble´my. Naprˇ´ıklad pokud aplikace dovolı´ uzˇivateli, aby si mohl volit za´beˇr sce´ny, tak sice omezı´me proble´m prˇekry´va´nı´ objektu˚, ale za´rovenˇ mu mohou uniknout du˚lezˇite´ dynamicke´ deˇje ve sce´neˇ. Take´ s postupem algoritmu se meˇnı´ sce´na a deˇj se mu˚zˇe prˇesouvat na jine´ mı´sto. Uzˇivatel je tak nucen cˇasto opravovat za´beˇr sce´ny, cozˇ je jednak u´navne´, a take´ mu mohou uniknout deˇje odehra´vajı´cı´ se mimo za´beˇr. Pro vyrˇesˇenı´ proble´mu˚ zobrazova´nı´ 3-D algoritmu˚ je tedy nutne´ citliveˇ zvolit jednotlive´ prˇ´ıstupy. Nechat uzˇivateli prˇ´ılisˇ velke´ mozˇnosti v nastavenı´ take´ nemusı´ by´t nejlepsˇ´ım rˇesˇenı´m, nebot’uzˇivatel se algoritmus teprve ucˇ´ı, nevı´ co od neˇj mu˚zˇe cˇekat a nemusı´ se tudı´zˇ soustrˇedit na jeho podstatne´ cˇa´sti.
3.3 Pouzˇı´vane´ prˇı´stupy k zobrazova´nı´ algoritmu˚ Jake´ se v praxi pouzˇ´ıvajı´ animace k zobrazova´nı´ algoritmu˚? Lze je rozdeˇlit podle neˇkolika krite´riı´. Efektivita Schopnost programu naucˇit uzˇivatele konkre´tnı´ algoritmus je velmi osˇidna´ vlastnost. Serio´zneˇ se tomuto te´matu veˇnovali naprˇ´ıklad Hundhausen, Douglas a Stasko v [Hundhausen et al., 2002] a pro pro potrˇeby jejich vy´zkumu pouzˇili tyto techniky: Nepodlozˇene´ -- hodnotı´ programy na za´kladeˇ naprˇ´ıklad vizua´lnı´ch prvku˚ nebo schopnosti zaujmout uzˇivatele. Tato hodnocenı´ se ovsˇem nemusı´ nutneˇ odra´zˇet ve vy´sledne´ efektiviteˇ programu. Programove´ -- efektivitu programu meˇrˇ´ı podle softwarovy´ch metrik aplikovany´ch na zdrojovy´ ko´d konkre´tnı´ho algoritmu. Cox a Roman v [Cox and Roman, 1994] naprˇ´ıklad pouzˇ´ıvajı´ pocˇet rˇa´dku˚ potrˇebny´ch k naprogramova´nı´ dane´ho algoritmu. Cˇ´ım kratsˇ´ı ko´d, tı´m samozrˇejmeˇ le´pe. Analyticke´ -- snazˇ´ı se analyzovat program bez pouzˇitı´ empiricky´ch metod. Naprˇ´ıklad [Nielsen, 1992] se zaby´va´ heuristickou analy´zou proble´mu˚ pouzˇitelnosti. 10
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ Empiricke´ -- zkouma´ vliv programu na pochopenı´ prezentovane´ho algoritmu. Cı´lovy´ uzˇivatel Programy pro animaci algoritmu˚ mu˚zˇeme deˇlit podle cı´love´ skupiny uzˇivatelu˚, pro kterou jsou navrzˇeny. Nebudeme se tu zaby´vat programy slouzˇ´ıcı´mi k jiny´m nezˇ vy´ukovy´m u´cˇelu˚m (naprˇ´ıklad k verifikaci algoritmu˚ – viz. [Hundhausen et al., 2002]). Prˇedna´sˇejı´cı´ -- program je urcˇen pro prˇedna´sˇejı´cı´ho, ktery´ dany´ algoritmus vysveˇtluje a animace mu pouze poma´ha´ v jeho prezentaci. Takovy´ program nemusı´ zvla´dat komentova´nı´ algoritmu˚, meˇl by ale neˇjaky´m zpu˚sobem umozˇnit prˇedna´sˇejı´cı´mu zvy´raznˇova´nı´ jednotlivy´ch objektu˚ (naprˇ´ıklad zmeˇnou jejich barvy). Pasivnı´ student -- program je urcˇen pro studenty, kterˇ´ı majı´ k dispozici i jine´ materia´ly o algoritmu a dany´ program pouze poma´ha´ dokreslovat jejich prˇedstavu o fungova´nı´ dane´ho algoritmu. Aktivnı´ student -- program je urcˇen pro aktivnı´ studenty, kterˇ´ı se dany´ algoritmus ucˇ´ı tı´m, zˇe si ho sami naprogramujı´. Takove´to programy tedy neimplementujı´ dany´ algoritmus, ale vytva´rˇ´ı vhodne´ prostrˇedı´ (framework) pro usnadneˇnı´ jeho implementace a vhodny´m zpu˚sobem ho zobrazujı´. Samouk -- program je urcˇen ke kompletnı´ prezentaci algoritmu studentovi, ktery´ nema´ zˇa´dne´ jine´ informace o cˇinnosti algoritmu. Takovy´ program musı´ implementovat krokova´nı´ algoritmu˚ a syste´m komenta´rˇu˚ jednotlivy´ch kroku˚. Interaktivnost Interaktivnostı´ rozumı´me to, zda program reaguje na uzˇivatelovy podneˇty. Mu˚zˇeme je rozdeˇlit podle mı´ry interakce. Neinteraktivnı´ -- program nebo pouhe´ video nemu˚zˇeme nijak ovlivnit, cozˇ ma´ sve´ nevy´hody, ale i jasne´ vy´hody. Mezi nevy´hody patrˇ´ı nemozˇnost spustit algoritmus na libovolne´m vstupu a tudı´zˇ ucˇenı´ typu „Co by algoritmus udeˇlal, kdyby. . . “ Tento prˇ´ıstup ma´ ovsˇem obrovske´ vy´11
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ hody v tom, zˇe anima´tor5 vı´ prˇedem jak bude algoritmus postupovat a zameˇrˇit uzˇivatelovu pozornost vhodny´m smeˇrem. Dalsˇ´ı velkou vy´hodou je snadna´ implementace zvukove´ho doprovodu, tedy kvalifikovany´m vy´kladem algoritmu. Uzˇivatel ma´ take´ mozˇnost si opakovat jemu nejasne´ sekvence prˇetocˇenı´m za´znamu. Lehce interaktivnı´ -- program umozˇnˇuje uzˇivateli naprˇ´ıklad zada´va´nı´ pocˇa´tecˇnı´ch podmı´nek algoritmu anebo zmeˇny zobrazenı´ sce´ny za beˇhu algoritmu. Plneˇ interaktivnı´ -- program umozˇnˇuje zada´nı´ libovolny´ch pocˇa´tecˇnı´ch podmı´nek algoritmu, stejneˇ tak jako libovolne´ zobrazenı´ sce´ny, vcˇetneˇ mozˇnosti meˇnit pru˚hlednost objektu˚, pohyb kamery, zobrazova´nı´ dı´lcˇ´ıch vy´sledku˚ algoritmu a podobneˇ. Tento prˇ´ıstup samozrˇejmeˇ vyzˇaduje zvy´sˇene´ u´silı´ od uzˇivatele a jak jizˇ bylo uvedeno vy´sˇe, uzˇivatel nemusı´ veˇdeˇt, co je pro neˇj nejlepsˇ´ı. Tento prˇ´ıstup ale mu˚zˇe mı´t sve´ opodstatneˇnı´. Pokud je program vyuzˇ´ıva´n neˇky´m, kdo tento algoritmus prezentuje (prˇedna´sˇejı´cı´), ktery´ vı´ kde se ve sce´neˇ odehra´vajı´ podstatne´ deˇje, mu˚zˇe by´t vysoka´ mı´ra interaktivity prˇ´ınosem. Univerza´lnost Programy mu˚zˇeme deˇlit take´ podle pocˇtu algoritmu˚, ktere´ jsou schopny zobrazit. Jednou´cˇelove´ -- program je urcˇeny´ pro jediny´ algoritmus. Obrovskou vy´hodou je, zˇe prˇ´ıstup k tomuto konkre´tnı´mu algoritmu se promı´tne jizˇ v na´vrhu tohoto programu. Takovy´ program pak ma´ velkou vy´hodu v plneˇnı´ sve´ho posla´nı´, tedy aby uzˇivatel plneˇ pochopil prezentovany´ algoritmus. Specializovane´ -- program je urcˇeny´ pro vı´ce algoritmu˚, majı´cı´ch ovsˇem podobny´ za´klad. Naprˇ´ıklad je tedy urcˇen pro zobrazova´nı´ Voronoiu˚v diagramu˚, triangulace a konvexnı´ho obalu v rovineˇ (naprˇ´ıklad program VoroGlide), tedy algoritmu˚m se stejny´m vstupem a pracujı´cı´m se stejny´mi objekty. Pokud takovy´ program ma´ jesˇteˇ navı´c jednoduche´ rozhranı´ pro prˇida´va´nı´ novy´ch algoritmu˚ pomocı´ za´suvny´ch modulu˚ (plug-inu˚), pak ho lze velmi u´speˇsˇneˇ pouzˇ´ıvat jako platformu, ve 5. Budeme rozlisˇovat na´sledujı´cı´ trˇi role: Programa´tor vyvı´jı´ animacˇnı´ syste´m, anima´tor vytva´rˇ´ı v tomto syste´mu animace jednotlivy´ch algoritmu˚ a uzˇivatel sleduje vy´slednou prezentaci.
12
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ ktere´ sami studenti programujı´ ucˇene´ algoritmy, jak to navrhuje John T. Stasko [Stasko, 1997]. Univerza´lnı´ -- program umozˇnˇuje beˇh libovolny´ch algoritmu˚, cˇasto 2-D i 3-D. Nevy´hody jsou zrˇejme´ – programova´nı´ jednotlivy´ch algoritmu˚ vyzˇaduje netrivia´lnı´ u´silı´, nebot’ takovy´ program nutneˇ musı´ pouzˇ´ıvat nı´zkou´rovnˇove´ prˇ´ıkazy pro kreslenı´ graficky´ch primitiv. Tyto programy nejsou urcˇene´ pouze pro ucˇenı´ algoritmu˚, ale take´ pro jejich verifikaci a podobneˇ.
Krokova´nı´ Neˇktere´ animace algoritmu˚ beˇzˇ´ı bez za´sahu˚ uzˇivatele, jine´ umozˇnˇujı´ beˇh algoritmu po urcˇity´ch krocı´ch. Mu˚zˇeme je tedy deˇlit podle u´rovneˇ krokova´nı´ a zobrazovany´ch informacı´. Bez krokova´nı´ -- nevy´hodou tohoto prˇ´ıstupu je nemozˇnost zopakovat uzˇivateli nejasne´ mı´sto a take´ nemozˇnost prˇedna´sˇejı´cı´ho poda´vat vy´klad jednotlivy´ch kroku˚. Vy´hodou pak je snadnost implementace jednotlivy´ch algoritmu˚ i pru˚vodnı´ho zvukove´ho za´znamu. Vysokou´rovnˇove´ krokova´nı´ -- program je krokova´n po logicky´ch celcı´ch. Takove´to chova´nı´ programu je sice slozˇiteˇjsˇ´ı na implementaci, ale poskytuje velke´ mozˇnosti prˇi poskytova´nı´ informacı´ uzˇivateli o pra´veˇ probı´hajı´cı´ch deˇjı´ch v algoritmu. Tyto mohou by´t jak textove´, tak zvukove´. Dalsˇ´ım vy´znamny´m prvkem k pochopenı´ algoritmu je umozˇneˇnı´ prˇehra´nı´ alesponˇ poslednı´ho kroku. Nı´zkou´rovnˇove´ krokova´nı´ -- program je krokova´n podle rˇa´dku˚ zdrojove´ho ko´du dane´ho algoritmu. Uzˇitecˇnost takove´hoto krokova´nı´ za´lezˇ´ı na univerza´lnosti programu. Univerza´lnı´ programy neposkytujı´ vysˇsˇ´ı u´rovenˇ funkcı´ pro pra´ci s objekty algoritmu a tak se krokova´nı´ sta´va´ pro uzˇivatele prˇ´ılisˇ detailnı´ a komplikovane´. Pokud je ovsˇem oblast programu vymezena u´zˇeji, algoritmus mu˚zˇe vyuzˇ´ıvat prˇ´ıkazu˚ vysˇsˇ´ı u´rovneˇ (naprˇ´ıklad prˇ´ıkaz pro zı´ska´nı´ spodnı´ spolecˇne´ tangenty dvou mnozˇin bodu˚), pak takove´to krokova´nı´ mu˚zˇe by´t prˇ´ınosne´. Komenta´rˇe k jednotlivy´m kroku˚m se ovsˇem omezujı´ pouze na komenta´rˇe zdrojove´ho ko´du, cozˇ nedovoluje internacionalizaci programu. 13
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ Abstrakce Dalsˇ´ım parametrem animacı´ algoritmu˚ je u´rovenˇ abstrakce prˇi zobrazova´nı´ programovy´ch dat do graficke´ prezentace. V [Cox and Roman, 1992] rozdeˇlujı´ vizualizacˇnı´ syste´my podle u´rovneˇ abstrakce na peˇt typu˚ (serˇazeno vzestupneˇ podle u´rovneˇ abstrakce): Prˇı´ma´ reprezentace -- neobsahuje zˇa´dnou abstrakci a data jsou pouze jednodusˇe transformova´na do vizua´lnı´ podoby. Struktura´lnı´ reprezentace -- schova´va´ nadbytecˇna´ data a zapouzdrˇuje objekty do veˇtsˇ´ıch struktur. Synteticka´ reprezentace -- zobrazuje informace, ktere´ nejsou prˇ´ımo obsazˇeny v algoritmu, ale jsou z neˇj odvoditelne´. Analyticka´ reprezentace -- snazˇ´ı se zachytit abstraktneˇjsˇ´ı informace, nezˇ jen prˇ´ımo odvoditelne´. Jako prˇ´ıklad Cox a Roman uva´deˇjı´ vizualizaci invariantu algoritmu. Vysveˇtlujı´cı´ reprezentace -- pomocı´ deˇju˚ a objektu˚, ktere´ nejsou v algoritmu obsazˇeny se snazˇ´ı o lepsˇ´ı pochopenı´ algoritmu uzˇivatelem. Naprˇ´ıklad nakla´neˇnı´m rovin, nebo plynuly´m prˇesunova´nı´m bodu˚ se snazˇ´ı upoutat jeho pozornost. Cox a Roman za´rovenˇ poukazujı´ na velkou du˚lezˇitost vhodne´ abstrakce vizualizace. Shrnutı´ Neˇktere´ algoritmy majı´ zajı´mave´ teoreticke´ pozadı´, ktere´ take´ lze vizualizovat. Naprˇ´ıklad se jedna´ o zobrazenı´ a postup tzv. prˇ´ılivove´ vlny ve Fortunoveˇ algoritmu pro vytva´rˇenı´ Voronoiu˚v diagramu˚. Ta se prˇi prakticke´m vy´pocˇtu nepocˇ´ıta´ a slouzˇ´ı jenom k zobrazenı´ principu fungova´nı´ algoritmu. Programy tedy mu˚zˇeme deˇlit podle zobrazova´nı´ teˇchto teoreticky´ch kroku˚. V implementacˇnı´ rovineˇ mu˚zˇeme deˇlit programy na ty, ktere´ pocˇ´ıtajı´ algoritmy za beˇhu (on-line) a ty, ktere´ si algoritmus prˇedpocˇ´ıtajı´, uchovajı´ si vy´sledky a ty na´sledneˇ zobrazujı´ (post mortem). Programy prvnı´ skupiny jsou jednodusˇsˇ´ı na implementaci, ale vyzˇadujı´ veˇtsˇ´ı vy´pocˇetnı´ vy´kon a implementace vracenı´ kroku˚ je te´meˇrˇ nemozˇna´. Post mortem algoritmy oproti tomu majı´ veˇtsˇ´ı na´roky na sekunda´rnı´ pameˇt’, zvla´sˇteˇ u slozˇity´ch sce´n a dlouhy´ch algoritmu˚. 14
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ Programy bychom mohli jesˇteˇ da´le klasifikovat naprˇ´ıklad podle dostupnosti zdrojovy´ch ko´du˚ (cozˇ mu˚zˇe jisteˇ zodpoveˇdeˇt ota´zky studentu˚ ty´kajı´cı´ se detailnı´ implementace). Da´le bychom se mohli pta´t, zda jsou programy pouzˇitelne´ v alternativnı´ch operacˇnı´ch syste´mech, jake´ majı´ syste´move´ na´roky, zda jsou prˇipraveny pro prˇeklad do jiny´ch jazyku˚ nebo zda doka´zˇou beˇzˇet v internetove´m prohlı´zˇecˇi. Neme´neˇ zajı´mava´ je ota´zka licence dane´ho produktu a jeho ceny. O parametrech konkre´tnı´ch implementacı´ bude pojedna´no v cˇa´sti 4.2 o soucˇasne´m stavu rˇesˇene´ problematiky.
3.4 Vizualizace vy´pocˇtu konvexnı´ho obalu Nynı´ jizˇ zna´me mozˇne´ vlastnosti vizualizacı´ algoritmu˚ a tak si mu˚zˇeme nastı´nit, jak by mohla vypadat vizualizace vy´sˇe uvedene´ho algoritmu pro vy´pocˇet konvexnı´ho obalu metodou rozdeˇl a panuj (v cˇa´sti 2.2). Abstrakce Pro u´plne´ pochopenı´ tohoto algoritmu je nutne´ pomoci uzˇivateli odhle´dnout od urcˇity´ch jednoduchy´ch operacı´ algoritmu a zameˇrˇit jeho pozornost na jine´ procesy, ktere´ nejsou intuitivneˇ zrˇejme´. Algoritmus rozdeˇluje body na dveˇ cˇa´sti (naprˇ´ıklad levou a pravou), na nich rekurzivneˇ vola´ sebe sama a vy´sledne´ cˇa´sti sesˇije (algoritmus 1). Animace ovsˇem musı´ od urcˇity´ch cˇa´stı´ vhodny´m zpu˚sobem abstrahovat. Je naprˇ´ıklad nemyslitelne´, aby uzˇivateli zobrazovala zpu˚sob, jaky´m si algoritmus rozdeˇluje body na levou a pravou polovinu. Mu˚zˇeme take´ prˇedpokla´dat, zˇe uzˇivatel vı´, na jake´m principu pracujı´ rekurzivnı´ algoritmy rozdeˇl a panuj6 , takzˇe mu to nenı´ potrˇeba detailneˇ vysveˇtlovat. Naopak podstatny´m detailem tohoto algoritmu je zpu˚sob, jaky´m jsou sesˇ´ıva´ny dva konvexnı´ obaly. Tady se uplatnı´ nata´cˇenı´ rovin, ktere´ upouta´ pozornost uzˇivatele. Animace te´to cˇa´sti algoritmu vsˇak mu˚zˇe jı´t do jesˇteˇ veˇtsˇ´ıch podrobnostı´ a vhodny´m zpu˚sobem (naprˇ´ıklad barevny´m znacˇenı´m) prˇiblı´zˇit pravidlo, jaky´m jsou vybı´ra´ni kandida´ti na prˇ´ısˇtı´ vrchol sˇvu. Krokova´nı´ Prˇedpokla´da´me, zˇe princip „Rozdeˇl a panuj“ je uzˇivateli dobrˇe zna´m7 , takzˇe prvnı´m krokem vizualizace se prˇeneseme azˇ do stavu, ve ktere´m jizˇ ma´me 6. Algoritmus se nazy´va´ “Divide-and-conquer convex hull”, ale jeho daleko nejdu˚lezˇiteˇjsˇ´ı cˇa´stı´ je sesˇ´ıva´nı´, proto by´va´ cˇasto nazy´va´n “Merge hull” 7. U takto slozˇite´ho algoritmu si to mu˚zˇeme dovolit.
15
3. VIZUALIZACE GEOMETRICKY´CH ALGORITMU˚ spocˇ´ıta´ny konvexnı´ obaly leve´ a prave´ mnozˇiny bodu˚. Po prvnı´m kroku tedy uzˇivatele mu˚zˇeme prˇ´ımo postavit prˇed proble´m sesˇ´ıva´nı´ a tak vyzdvihnout jeho vy´znam. V na´sledujı´cı´ch krocı´ch se budeme veˇnovat pouze proble´mu sesˇ´ıva´nı´. Dalsˇ´ım (jizˇ detailneˇjsˇ´ım) logicky´m krokem algoritmu je nalezenı´ spodnı´ho mostu (tangenty) leve´ho a prave´ho konvexnı´ho obalu. To nenı´ sice trivia´lnı´ za´lezˇitost, ale tato znalost nenı´ bezpodmı´necˇneˇ nutna´ pro pochopenı´ principu fungova´nı´ tohoto algoritmu. Navı´c mu˚zˇeme prˇedpokla´dat, zˇe uzˇivatel se s tı´mto proble´mem setkal ve dvourozmeˇrne´ varianteˇ tohoto algoritmu, ve ktere´ pra´veˇ hleda´nı´ spodnı´ tangenty bylo to podstatne´ ja´dro algoritmu. V na´sledujı´cı´ch krocı´ch opakovaneˇ prˇida´va´me nove´ kandida´ty, vybı´ra´me vı´teˇze ke ktere´mu nakla´pı´me rovinu a mazˇeme stare´ kandida´ty. Tento postup se opakuje sta´le dokola a uzˇivatel nemusı´ videˇt vsˇechny iterace se stejny´m detailem krokova´nı´. Naprˇ´ıklad mohou by´t prvni trˇi kroky iterace podrobne´, kazˇdy´m dalsˇ´ım krokem pak uzˇ vybereme rovnou vı´teˇze a vytvorˇ´ıme novy´ polygon. V poslednı´m kroku odebereme vnitrˇnı´ polygony, ktere´ jsme obalili sˇvem.
16
Kapitola 4
Implementace 4.1 Cı´le projektu Soucˇa´stı´ te´to pra´ce je i na´vrh a implementace programu pro podporu vy´uky geometricky´ch algoritmu˚. Vytycˇme si tedy cı´le, ktery´ch bychom chteˇli dosa´hnout. Postupujme po jednotlivy´ch bodech cˇa´sti 3.3 o prˇ´ıstupech k zobrazova´nı´ algoritmu˚. Prima´rnı´m urcˇenı´m tohoto programu meˇla by´t podpora prˇedna´sˇejı´cı´ho prˇi vysveˇtlova´nı´ algoritmu˚. Uzˇivatelem budeme tedy rozumeˇt prˇedna´sˇejı´cı´ho. Cı´lem tohoto projektu by v zˇa´dne´m prˇ´ıpadeˇ nemeˇla by´t snaha o nahrazenı´ prˇedna´sˇejı´cı´ho. Syste´m by meˇl podporovat zvy´raznˇova´nı´ jednotlivy´ch objektu˚, naopak nenı´ nutna´ podpora podrobne´ho komentova´nı´ kroku˚. Jednoduche´ (orientacˇnı´) komenta´rˇe kroku˚ jsou vsˇak potrˇebne´. Protozˇe se prˇedpokla´da´ podrobneˇjsˇ´ı sezna´menı´ uzˇivatele (prˇedna´sˇejı´cı´ho) s prostrˇedı´m programu, je mozˇne´ pouzˇitı´ strˇedneˇ azˇ velmi interaktivnı´ho prostrˇedı´. Vzhledem k tomu, zˇe 2-D algoritmy se velmi dobrˇe prezentujı´ na tabuli a studenti nemajı´ proble´my v interpretaci sce´ny, bude hlavnı´m u´kolem zobrazenı´ 3-D algoritmu˚. Navı´c je na Internetu spousta programu˚, ktere´ vizualizujı´ 2-D algoritmy. Rozhodneˇ se vsˇak vyhneme snaze o maxima´lnı´ univerza´lnost programu a radeˇji se zameˇrˇ´ıme na vytvorˇenı´ vhodny´ch vysokou´rovnˇovy´ch prˇ´ıkazu˚ v ra´mci 3-D zobrazenı´ za u´cˇelem jednoduchosti psanı´ novy´ch za´suvny´ch modulu˚ (novy´ch algoritmu˚) pro tento program. Nezbytnou vlastnostı´ programu musı´ by´t podpora krokova´nı´, nejle´pe vcˇetneˇ zpeˇtny´ch kroku˚. Dalsˇ´ımi vlastnostmi programu mu˚zˇe by´t zobrazova´nı´ abstraktnı´ch operacı´ prova´deˇny´ch algoritmem (naprˇ´ıklad nakla´neˇnı´ rovin) nebo podpora internacionalizace.
4.2 Charakteristika soucˇasne´ho stavu Podı´vejme se na nynı´ na vlastnosti konkre´tnı´ch programu˚, ktere´ se zaby´vajı´ vizualizacı´ 3-D algoritmu˚. Rozdeˇlme si je podle jejich univerza´lnosti, jak bylo popsa´no vy´sˇe. 17
4. IMPLEMENTACE Na Internetu se nacha´zı´ velmi mnoho programu˚, spadajı´cı´ch do kategorie jednou´cˇelovy´ch, prˇedevsˇ´ım dı´ky semestra´lnı´m u´kolu˚m studentu˚ vysoky´ch sˇkol. Bohuzˇel jen velmi ma´lo jich implementuje 3-D algoritmy. Jeden z nich1 je tento: Algoritmy konvexnı´ch obalu˚ -- neˇkolik algoritmu˚ pro vy´pocˇet konvexnı´ho obalu (rozdeˇl a panuj, gift-wrapping, inkrementa´lnı´ a QuickHull). Program je napsany´ v Javeˇ jako aplet, takzˇe je spustitelny´ v prohlı´zˇecˇi. Bohuzˇel neimplementuje krokova´nı´, ani nedovoluje pozastavit pru˚beˇh algoritmu. Pocˇetneˇjsˇ´ı skupinu tvorˇ´ı programy, poskytujı´cı´ univerza´lnı´ prostrˇedı´ pro tvorbu animacı´ 3-D algoritmu˚: Zeus -- tento program byl vyvı´jeny´ v jazyce Modula-3 v prvnı´ polovineˇ 90. let a byl pu˚vodneˇ navrzˇeny´ pro animace 2-D algoritmu˚ [Brown, 1992], teprve pozdeˇji byla prˇida´na podpora pro zobrazova´nı´ ve trˇech dimenzı´ch [Brown and Najork, 1993], prima´rneˇ vsˇak pro zobrazova´nı´ dodatecˇny´ch informacı´ 2-D algoritmu˚. Bohuzˇel se mi nepodarˇilo najı´t zdrojove´ ko´dy a prˇedkompilovane´ bina´rnı´ verze programu jsou dostupne´ pouze pro exoticke´ syste´my2 . Obliq-3D -- univerza´lnı´ syste´m pro tvorbu 3-D animacı´, ktery´ lze propojit se syste´mem Zeus k animova´nı´ algoritmu˚. Bohuzˇel ma´ shodne´ syste´move´ na´roky, cozˇ jeho pouzˇitelnost znacˇneˇ snizˇuje. Polka-3D -- pu˚vodneˇ syste´m pro vizualizaci 2-D algoritmu˚ byl rozsˇ´ırˇen o dalsˇ´ı rozmeˇr [Stasko and Wehrli, 1993]. Tento vizualizacˇnı´ syste´m je znacˇneˇ univerza´lnı´, prˇesto poskytuje vysokou´rovnˇove´ funkce pro pra´ci s 3-D objekty, takzˇe je vhodny´ i pro anima´tory, kterˇ´ı nemajı´ sˇiroke´ znalosti 3-D grafiky. Vyvı´jeny´ byl vsˇak z jine´ho du˚vodu. John Stasko chteˇl zkoumat dopady pouzˇitı´ dalsˇ´ıho rozmeˇru na ucˇenı´ algoritmu. Dalsˇ´ı rozmeˇr mu˚zˇe podle neˇj slouzˇit ke trˇem u´cˇelu˚m3 : 1. Jedina´ funkcˇnı´, jednou´cˇelova´, interaktivnı´ vizualizace 3-D algoritmu˚, kterou jsem doka´zal najı´t, i s vyuzˇitı´m zdroju˚ The Complete Collection of Algorithm Animations cˇi Algorithmique re´fe´rences Internet animations ge´ome´trie. 2. DECstation 3100 nebo DECstation 5000 se syste´mem Ultrix 4.3, DEC 3000 AXP se syste´mem OSF/1 2.0, Sun SPARC se syste´mem SunOS 4.1.3 3. Srov. s [Brown and Najork, 1993], ktery´ definuje take´ trˇi u´cˇely 3-D zobrazenı´, kupodivu vsˇak nepocˇ´ıta´ se zobrazova´nı´m 3-D objektu˚: Dodatecˇne´ informace o 2d objektech, sjednocenı´ neˇkolika pohledu˚ a zachycova´nı´ historie beˇhu algoritmu
18
4. IMPLEMENTACE Rozsˇı´rˇenı´ 2-D pohledu˚ -- do te´to kategorie Stasko rˇadı´ pohledy, ktery´m by stacˇil 2-D prostor a ktere´ dalsˇ´ı rozmeˇr vyuzˇ´ıvajı´ pouze k esteticky´m u´cˇelu˚m. Prˇizpu˚sobenı´ 2-D pohledu˚ -- trˇetı´ rozmeˇr je zde vyuzˇ´ıva´n k zobrazenı´ dodatecˇny´ch informacı´ (vcˇetneˇ historie beˇhu algoritmu). Vlastnı´ 3-D aplikace -- v te´to kategorii uzˇ jsou jednak nativnı´ 3-D algoritmy a take´ 2-D algoritmy, ktere´ vsˇak vyuzˇ´ıvajı´ 3-D vizualizace dat, naprˇ´ıklad algoritmy neplana´rnı´ch grafu˚ (ktere´ jsou v ja´dru 2-D, ale pro vizualizaci je vhodne´ vyuzˇ´ıt trˇetı´ rozmeˇr). Tento kvalitnı´ program byl vsˇak pouzˇit prˇedevsˇ´ım jako zdroj statisticky´ch dat pro dalsˇ´ı Staskovy pra´ce ty´kajı´cı´ se efektu animacı´ na vy´uku studentu˚ [Kehoe and Stasko, 1996]. Byl vyvı´jen na platformeˇ SGI za pouzˇitı´ 3-D graficke´ knihovny IrisGL4 , bohuzˇel se vsˇak jeho vy´voj zastavil a v soucˇasne´ dobeˇ je na Linuxu neprˇelozˇitelny´5 . Pro Microsoft Windows byla Polka portova´na v roce 1997, ovsˇem bez sve´ho 3-D rozsˇ´ırˇenı´. Geomview -- za´stupce velmi univerza´lnı´ch syste´mu˚, ve ktery´ch sice lze tvorˇit animace algoritmu˚, ale nenı´ to jejich posla´nı´ a tudı´zˇ vyzˇadujı´ po uzˇivateli podrobneˇjsˇ´ı znalosti pra´ce s graficky´mi objekty i s dany´m syste´mem. Gawain -- syste´m animace algoritmu˚, ktery´ je napsany´ cˇa´stecˇneˇ v Javeˇ a vyuzˇ´ıva´ knihovny psane´ v jazyce C. Jeho orˇezana´ verze je schopna beˇzˇet v okneˇ prohlı´zˇecˇe a prˇestozˇe hlavnı´ teˇzˇisˇteˇ tohoto programu tkvı´ v zobrazova´nı´ 2-D algoritmu˚, je schopen i jednoduche´ho zobrazova´nı´ 3-D algoritmu˚.
4.3 Na´vrh rˇesˇenı´ V te´to kapitole navrhneme vlastnosti implementace programu v souladu s cı´li projektu (kapitola 4.1). •
Program by meˇl poskytovat vhodnou u´rovenˇ abstrakce, ktera´ skryje prˇed uzˇivatelem nepodstatne´ informace a naopak mu pomu˚zˇe zameˇrˇit se na du˚lezˇite´ deˇje algoritmu. Spra´vneˇ zvolena´ u´rovenˇ abstrakce hraje klı´cˇovou u´lohu v procesu vstrˇeba´nı´ algoritmu studentem
4. prˇedchu˚dce OpenGL 5. gcc verze 3.4.4
19
4. IMPLEMENTACE [Cox and Roman, 1992]. Z toho tedy vyply´va´, zˇe krokova´nı´ programu nemu˚zˇe by´t prova´deˇno po rˇa´dcı´ch algoritmu, ale po logicky´ch celcı´ch. Program musı´ take´ zobrazovat vhodny´ komenta´rˇ k jednotlivy´m kroku˚m. •
Jako princip zobrazova´nı´ vy´pocˇtu algoritmu si zvolme zobrazova´nı´ post mortem, ktere´ na´m dovolı´ vı´cena´sobne´ vracenı´ kroku˚ algoritmu.
•
Vzhledem k tomu, zˇe program bude zameˇrˇen na zpracova´nı´ 3-D sce´n, bude jisteˇ prˇ´ınosna´ podpora hardwarove´ akcelerace. Tı´mto rozhodnutı´m se vsˇak zbavujeme mozˇnosti beˇhu programu na velke´m mnozˇstvı´ platforem. Zvolili jsme aplikacˇnı´ rozhranı´ Java3D API od spolecˇnosti Sun Microsystems, dı´ky jeho vyzra´losti a rozsˇ´ırˇenosti.
•
Program by meˇl vhodneˇ zobrazovat nekonecˇne´ objekty (roviny). Rovinu tedy zobrazujme jako dveˇ mnozˇiny rovnobeˇzˇny´ch prˇ´ımek:
•
Program by meˇl by´t jednodusˇe prˇ´ıstupny´, nejle´pe bez nutnosti instalace, idea´lneˇ tedy v okneˇ prohlı´zˇecˇe. Zvolı´me tedy programovacı´ jazyk Java, ktery´ je k tomuto za´meˇru vhodny´ a na´stroj pro spra´vu projektu˚ Maven.
•
Program by meˇl umozˇnˇovat snadnou tvorbu novy´ch animacı´ algoritmu˚. Z tohoto du˚vodu by meˇl syste´m obsahovat vysokou´rovnˇove´ prˇ´ıkazy pro pra´ci s 3-D objekty, aby se minimalizoval vy´sledny´ ko´d 20
4. IMPLEMENTACE animace. Zvolenı´m za´suvny´ch modulu˚ (s pevneˇ definovany´m rozhranı´m) v jazyce Java za´rovenˇ ponecha´va´me anima´torovi mozˇnost vyuzˇ´ıt vsˇech dostupny´ch prostrˇedku˚ jazyka6 . •
Do programu bude implementova´n automaticky´ i manua´lnı´ pohyb kamery, jak bylo odu˚vodneˇno v kapitole 3.2.
•
Rozhranı´ programu musı´ by´t prˇehledne´ a u´cˇelne´.
•
Syste´m by meˇl umozˇnˇovat jednoduchy´ prˇeklad do cizı´ch jazyku˚. Vesˇkere´ znakove´ rˇeteˇzce tedy budou externalizova´ny.
4.4 proble´my prˇi rˇesˇenı´ Prˇi rˇesˇenı´ se vyskytly neˇktere´ proble´my, ktere´ v dobeˇ psanı´ te´to pra´ce zu˚sta´vajı´ sta´le nedorˇesˇene´ uspokojivy´m zpu˚sobem. •
Hardwarova´ podpora 3-D akcelerace vyzˇaduje nativnı´ knihovny. Se za´vislostmi na nativnı´ch knihovna´ch si ovsˇem Maven nedoka´zˇe poradit, takzˇe uzˇivatel musı´ manua´lneˇ nainstalovat balı´k Java3D API. Toto je vsˇak proble´m, ktery´ se ty´ka´ pouze prˇekladu pomocı´ na´stroje Maven. Pro spousˇteˇnı´ aplikace v okneˇ prohlı´zˇecˇe je pouzˇit na´stroj Java Web Start, ktery´ zvla´da´ za´vislosti nativnı´ch knihoven, takzˇe spousˇteˇnı´ aplikace je opravdu jednoduche´.
•
Proble´m rea´lny´ch cˇ´ısel. Prˇi ukla´da´nı´ rea´lny´ch cˇ´ısel (typu float, cˇi double) docha´zı´ k jejich zaokrouhlova´nı´. Odchylka od spra´vne´ hodnoty mu˚zˇe da´le naru˚stat naprˇ´ıklad na´sobenı´m maticı´ a podobneˇ a mu˚zˇe zpu˚sobovat nespra´vne´ chova´nı´ syste´mu. Naprˇ´ıklad pokud vezmeme mnozˇinu bodu˚ lezˇ´ıcı´ch na spolecˇne´ rovineˇ a vyna´sobı´me je transformacˇnı´ maticı´, vy´sledne´ body (jejichzˇ sourˇadnice byly zaokrouhleny) jizˇ pravdeˇpodobneˇ nebudou lezˇet na zˇa´dne´ spolecˇne´ rovineˇ. Prˇ´ıstupy k rˇesˇenı´ tohoto proble´mu jsou dva. Bud’ se vyhneme pouzˇ´ıva´nı´ numericky´ch typu˚ float a double a namı´sto nich pouzˇijeme knihovnu, ktera´ doka´zˇe pracovat s rea´lny´mi cˇ´ısly s libovolnou prˇesnostı´, nebo povazˇujeme dva body, jejichzˇ vzda´lenost je mensˇ´ı, nezˇ zvolene´ ε, za totozˇne´. V projektu byla zvolena druha´ mozˇnost, nebot’
6. na rozdı´l od pouzˇitı´ skriptu˚ pro definici animace
21
4. IMPLEMENTACE jeho prioritou byla jednoduchost vytva´rˇenı´ za´suvny´ch modulu˚ algoritmu˚. V prˇ´ıpadeˇ zvolenı´ druhe´ mozˇnosti bychom totizˇ po anima´torovi vyzˇadovali znalosti one´ knihovny implementujı´cı´ prˇesna´ rea´lna´ cˇ´ısla. Nevy´hodou zvolene´ho rˇesˇenı´ je nemozˇnost urcˇit ε takove´, zˇe se pra´veˇ nastı´neˇny´ proble´m nevyskytne, takzˇe se mu˚zˇe sta´t (ve vy´jimecˇny´ch prˇ´ıpadech), zˇe k tomu dojde.
4.5 Implementace vy´pocˇtu konvexnı´ho obalu Nynı´ se podı´vejme na to, jak mu˚zˇe vypadat implementace „nasˇeho“ algoritmu pro animacˇnı´ u´cˇely v porovna´nı´ s implementacı´ pro rea´lne´ nasazenı´. V prvnı´ rˇadeˇ nenı´ nutne´, aby implementace meˇla prˇ´ıslusˇnou cˇasovou ani pameˇt’ovou slozˇitost. Vzhledem k velikosti vstupnı´ch dat (rˇa´doveˇ pouhe´ desı´tky bodu˚) je na´ru˚st doby vy´pocˇtu zanedbatelny´, zvla´sˇteˇ prˇi zobrazova´nı´ post mortem. S tı´m souvisı´ take´ datove´ struktury, ktere´ jsou v algoritmu pouzˇity. Prˇestozˇe v rea´lne´ implementaci hraje jejich na´vrh du˚lezˇitou roli, v animaci algoritmu je zcela nepodstatny´. Dalsˇ´ı vlastnost, kterou si mu˚zˇeme prˇi animaci algoritmu˚ dovolit osˇidit je jeho robustnost. Robustnı´ algoritmus si musı´ umeˇt poradit se vsˇemi mozˇny´mi vstupy, tedy naprˇ´ıklad s prˇ´ıpady, kdy neˇkolik vstupnı´ch bodu˚ ma´ shodne´ sourˇadnice, lezˇ´ı na stejne´ prˇ´ımce nebo rovineˇ. V teˇchto prˇ´ıpadech neˇktere´ implementace algoritmu˚ mohou selhat, ale vzhledem k tomu, zˇe si sami urcˇujeme vstup, mu˚zˇeme vytva´rˇet algoritmy me´neˇ robustnı´. Naopak by vsˇak implementace pro studijnı´ u´cˇely meˇla by´t prˇehledna´, strucˇna´ a dobrˇe okomentovana´, nebot’mu˚zˇeme, ocˇeka´vat zˇe neˇkterˇ´ı studenti se s nı´ budou chtı´t sezna´mit.
22
Kapitola 5
Zhodnocenı´ dosazˇeny´ch vlastnı´ch vy´sledku˚ 5.1 Dosazˇene´ schopnosti syste´mu Jaky´ch vlastnostı´ jsme prˇi implementaci syste´mu pro vykreslova´nı´ 3-D algoritmu˚ dosa´hli? •
Syste´m obsahuje pestrou sˇka´lu vysokou´rovnˇovy´ch funkcı´ pro pra´ci s 3-D objekty. Dı´ky tomu je psanı´ novy´ch za´suvny´ch modulu˚ jednoduche´.
•
Syste´m poskytuje mozˇnosti automaticke´ho i manua´lnı´ho pohybu kamery a vhodneˇ zobrazuje nekonecˇne´ objekty, cˇ´ımzˇ poma´ha´ prˇekonat ztra´tu informacı´ o hloubce zpu˚sobenou projekcı´.
•
Syste´m je prˇipraven pro internacionalizaci, vsˇechny znakove´ rˇeteˇzce jsou externalizova´ny.
•
Aplikace je prˇ´ıstupna´ pomocı´ webove´ho prohlı´zˇecˇe s podporou Javy bez nutnosti jake´koliv manua´lnı´ instalace.
•
Je vyuzˇ´ıva´na hardwarova´ podpora 3-D zobrazova´nı´1 .
•
Aplikace je bohateˇ komentova´na2 .
5.2 Negativa syste´mu Jake´ jsou negativnı´ vlastnosti vytvorˇene´ho programu? •
Beˇh programu je omezen pouze na platformy podporovane´ nativnı´mi knihovnami balı´ku Java 3D.
1. Java 3D Web Start podporuje pouze syste´my Microsoft Windows 32-bit, Linux 32-bit a Solaris/Sparc. 2. Podle vy´stupu scriptu slocc zabı´rajı´ komenta´rˇe 36 % rˇa´dku˚ zdrojovy´ch ko´du˚.
23
5. ZHODNOCENI´ DOSAZˇENY´CH VLASTNI´CH VY´SLEDKU˚ •
Jak bylo uvedeno v cˇa´sti 4.4, geometricky´ syste´m nenı´ bezvy´hradneˇ robustnı´.
•
Cˇasova´ slozˇitost neˇktery´ch internı´ch algoritmu˚ nenı´ optima´lnı´.
5.3 Budoucnost Vytvorˇeny´ syste´m vizualizacı´ algoritmu˚ nenı´ fina´lnı´ verzı´ a v budoucnosti by se meˇl nada´le vyvı´jet. •
Velmi prˇ´ınosne´ by bylo provedenı´ statisticke´ho pru˚zkumu ucˇinnosti syste´mu na ucˇenı´ algoritmu˚ v porovna´nı´ s jiny´mi syste´my.
•
Je vhodne´ jej doplnit o rˇadu dalsˇ´ıch 3-D algoritmu˚, ktere´ by pokryly vı´ce proble´mu˚ specificky´ch pro trˇi dimenze.
•
Program je mozˇne´ doplnit o podporu multimediı´, tedy naprˇ´ıklad pru˚vodnı´ slovo, cˇi video.
•
Vytvorˇenı´ na´vodu pro studenty jak postupovat prˇi vytva´rˇenı´ za´suvny´ch modulu˚ by usnadnilo jejich pra´ci prˇi ucˇenı´ pomocı´ aktivnı´ho vytva´rˇenı´ algoritmu˚.
24
Kapitola 6
Za´veˇr
25
Kapitola 7
Trademarks Microsoft Windows Sun Java Java3D API
26
Literatura [Brown, 1992] Brown, M. H. (1992). Zeus: A system for algorithm animation and multi-view editing. Technical Report 75. [Brown and Najork, 1993] Brown, M. H. and Najork, M. (1993). Algorithm animation using 3d interactive graphics. In ACM Symposium on User Interface Software and Technology, pages 93–100. [Cox and Roman, 1992] Cox, K. and Roman, G. (1992). Abstraction in algorithm animation. [Cox and Roman, 1994] Cox, K. and Roman, G. (1994). An evaluation of the pavane visualization system. [Edelsbrunner, 1987] Edelsbrunner, H. (1987). Algorithms in combinatorial geometry. Springer-Verlag New York, Inc., New York, NY, USA. [Goldman et al., 1996] Goldman, D. A., Eckert, R. R., and Cohen, M. S. (1996). Three-dimensional computation visualization for computer graphics rendering algorithms. In SIGCSE ’96: Proceedings of the twenty-seventh SIGCSE technical symposium on Computer science education, pages 358–362, New York, NY, USA. ACM Press. [Hundhausen et al., 2002] Hundhausen, C. D., Douglas, S. A., and Stasko, J. T. (2002). A meta-study of algorithm visualization effectiveness. Journal of Visual Languages and Computing, 13:259–290. [Joskowicz, 2005] Joskowicz, L. (2005). Computational geometry. [Kehoe and Stasko, 1996] Kehoe, C. M. and Stasko, J. T. (1996). Using animations to learn about algorithms: An ethnographic case study. Technical Report 96-20, College of Computing, Georgia Institute of Technology, Atlanta, GA. [Kerren and Stasko, 2002] Kerren, A. and Stasko, J. T. (2002). Algorithm animation - introduction. In Revised Lectures on Software Visualization, International Seminar, pages 1–15, London, UK. Springer-Verlag. 27
7. TRADEMARKS [Lawrence et al., 1994] Lawrence, A., Badre, A., and Stasko, J. (1994). Empirically evaluating the use of animations to teach algorithms. Technical Report 94-07, Graphics, Visualization, and Usability Center, Georgia Institute of Technology, Atlanta, GA. [Nielsen, 1992] Nielsen, J. (1992). Finding usability problems through heuristic evaluation. In CHI ’92: Proceedings of the SIGCHI conference on Human factors in computing systems, pages 373–380, New York, NY, USA. ACM Press. [O’Rourke, 1994] O’Rourke, J. (1994). Computational geometry in C. Cambridge University Press, New York, NY, USA. [Preparata and Hong, 1977] Preparata, F. P. and Hong, S. J. (1977). Convex hulls of finite sets of points in two and three dimensions. Commun. ACM, 20(2):87–93. [Price et al., 1993] Price, B. A., Baecker, R., and Small, I. S. (1993). A principled taxonomy of software visualization. J. Vis. Lang. Comput., 4(3):211– 266. [Stasko, 1997] Stasko, J. T. (1997). Using student-built algorithm animations as learning aids. SIGCSEB: SIGCSE Bulletin (ACM Special Interest Group on Computer Science Education), 29. [Stasko and Wehrli, 1993] Stasko, J. T. and Wehrli, J. F. (1993). Three-dimensional computation visualization. In Proc. of the 1993 IEEE Symposium on Visual Languages, pages 100–107, Bergen, Norway. [Wikipedia, 2004] Wikipedia (2004). Wikipedia.
28
Prˇı´loha A
FAQ
29
