Za´padoˇceska´ univerzita v Plzni Fakulta aplikovany´ch vˇed Katedra informatiky a vy´poˇcetn´ı techniky
Bakal´ aˇ rsk´ a pr´ ace Detekce obrys˚ u 3D objekt˚ u pro VRUT
Plzeˇ n 2011
Luk´aˇs Kurz
Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakal´aˇrskou pr´aci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 11. srpna 2011 Luk´aˇs Kurz
Abstract The goal of the work is to create a module for detection of the 3D objects contours in the VRUT application. Used vectors approach for contours detection is based on limiting the group of the model edges only to those which meet the conditions of contour edges. The module was implemented in the C++ language and tested on the three models. The module found the right edges and these edges meet the requirement of the contour edges. The only problem is that the visibility of the contour edges is not properly solved. This could be, however, solved by the full implementation of the Appel’s algorithm which is also described in this work.
Obsah ´ 1 Uvod 2 VRUT 2.1 Z´akladn´ı charakteristiky . . 2.2 J´adro . . . . . . . . . . . . . 2.3 Spr´ava a distribuce ud´alost´ı 2.4 Graf sc´eny . . . . . . . . . . 2.5 Hierarchie ob´alek . . . . . . 2.6 Moduly . . . . . . . . . . . 2.7 Geometrie . . . . . . . . . . 2.8 V´ yvoj . . . . . . . . . . . .
1
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
3 Detekce obrys˚ u 3.1 Rastrov´a detekce obrys˚ u . . . . . . . 3.2 Vektorov´a detekce obrys˚ u . . . . . . 3.3 Viditelnost obrysov´ ych hran . . . . . 3.3.1 Roberts˚ uv algoritmus . . . . . 3.3.2 Appel˚ uv algoritmus . . . . . . 3.3.3 Weiler-Atherton˚ uv algoritmus 4 PostScript 4.1 Z´akladn´ı charakteristiky . . . 4.2 Syntaxe . . . . . . . . . . . . 4.3 Z´akladn´ı pˇrehled oper´ator˚ u. . 4.4 Definice promˇenn´ ych a nov´ ych 4.5 Souˇradn´ y syst´em . . . . . . .
. . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . pˇr´ıkaz˚ u . . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
. . . . . .
. . . . .
. . . . . . . .
2 2 2 2 3 4 5 6 8
. . . . . .
9 9 10 10 11 11 12
. . . . .
14 14 15 16 17 17
5 N´ avrh 19 5.1 Nalezen´ı vˇsech hran . . . . . . . . . . . . . . . . . . . . . . . . 19 5.2 Nalezen´ı skuteˇcn´ ych hran . . . . . . . . . . . . . . . . . . . . . 20 5.3 Nalezen´ı obrysov´ ych hran . . . . . . . . . . . . . . . . . . . . 20
5.4 5.5 5.6 5.7
Sestaven´ı lomen´ ych ˇcar . . . Viditelnost obrysov´ ych hran Export obrys˚ u. . . . . . . . Vznik faleˇsn´ ych hran . . . .
. . . .
. . . .
6 Proveden´ı 6.1 Uˇzivatelsk´e rozhran´ı modulu . . 6.2 Popis pouˇzit´ ych tˇr´ıd . . . . . . 6.2.1 Tˇr´ıda DrawingScene . . 6.2.2 Tˇr´ıda DrawingEdges . . 6.2.3 Tˇr´ıda DrawingGeometry 6.2.4 Tˇr´ıda PostScriptTools 6.2.5 Tˇr´ıda VertexHashMap . 6.3 Popis exportovan´eho souboru .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
21 22 25 25
. . . . . . . .
27 27 28 28 30 31 32 33 33
7 Experimenty 35 7.1 Rychlost zobrazen´ı n´ahledu . . . . . . . . . . . . . . . . . . . 35 7.2 Kvalita v´ ystupu . . . . . . . . . . . . . . . . . . . . . . . . . . 35 8 Z´ avˇ er
42
´ 1 Uvod C´ılem t´eto pr´ace je do jiˇz exituj´ıc´ı aplikace VRUT (viz [V´aclav Kyba(2010)]) ˇ ˇ vytvoˇren´e ve spolupr´aci SKODA AUTO a.s. a CVUT vytvoˇrit modul, kter´ y um´ı u nahran´eho modelu detekovat obrysy, tyto obrysy zobrazovat (pokud moˇzno v re´aln´em ˇcase), a umoˇznit export nalezen´ ych hran do PostScript (v´ ysledkem bude 2D vektorov´ y obr´azek). Nejprve ˇcten´aˇre sezn´am´ım s aplikac´ı VRUT, aby z´ıskal pˇredstavu o jej´ı struktuˇre, moˇznosti rozˇs´ıˇren´ı jej´ıch vlastnost´ı pomoc´ı nov´ ych modul˚ u a zp˚ usobu komunikace modul˚ u pomoc´ı zpr´av, a pˇribl´ıˇz´ım moˇznosti programovac´ıho jazyka PostScript (viz [Ado(1999)] a [Ado(1985)]), kter´ y je pouˇzit pro v´ ysledn´ y export nalezen´ ych hran. D´ale jsou zde pops´any nˇekter´e moˇznosti detekce obrys˚ u, zp˚ usob implementace nov´eho modulu pro aplikaci VRUT a popis jeho d˚ uleˇzit´ ych ˇca´st´ı, a popis v´ ysledn´eho souboru v jazyce PostScript.
1
2 VRUT 2.1
Z´ akladn´ı charakteristiky
VRUT (Virtual Reality Universal Toolkit) je aplikace pro vizualizaci a editaci ˇ ˇ 3D dat, vytv´aˇren´a ve spolupr´aci SKODA AUTO a.s. a CVUT. Je urˇcen k zobrazen´ı grafick´ ych dat s podporou modul˚ u, umoˇzn ˇuj´ıc´ıch rozˇs´ıˇrit funkci hlavn´ı aplikace. Aplikace se d´a rozdˇelit na dvˇe ˇc´asti – hlavn´ı aplikace neboli j´adro, kter´e je samo o sobˇe z uˇzivatelsk´eho hlediska nepouˇziteln´e, a z´akladn´ı bal´ıˇcek modul˚ u, kter´e se staraj´ı napˇr´ıklad o zobrazen´ı sc´eny ˇci jej´ı import a export.
2.2
J´ adro
J´adro slouˇz´ı pro spr´avu modul˚ u, spr´avu grafick´ ych dat, poskytuje pomocn´e prvky pro spr´avn´ y bˇeh aplikace a tak´e zajiˇst’uje spr´avu ud´alosti slouˇz´ıc´ı jako komunikaˇcn´ı kan´al mezi jednotliv´ ymi ˇca´stmi aplikace a moduly. Spr´avce modulu spuˇstˇen´ı modulu a jeho propojen´ı s j´adrem. Moduly jsou aktivov´any jen na ˇza´dost v pˇr´ıpadˇe potˇreby. Spr´avce modul˚ u obsahuje d´ılˇc´ı ˇc´asti, z nichˇz kaˇzd´a je urˇcena pro obsluhu podskupiny modul˚ u stejn´eho nebo kompatibiln´ıho typu. Nˇekter´e moduly, u nichˇz je vˇetˇs´ı prov´azanost s j´adrem, vyˇzaduj´ı zvl´aˇstn´ı zach´azen´ı, proto typy spr´avc˚ u do znaˇcn´e m´ıry odpov´ıdaj´ı typ˚ um podporovan´ ych modul˚ u.
2.3
Spr´ ava a distribuce ud´ alost´ı
Aplikace je rozdˇelena na objekty, pˇredevˇs´ım jednotliv´e moduly, kter´e jsou na sobˇe zpravidla nez´avisl´e. Tyto ˇca´sti vˇsak spolu potˇrebuj´ı komunikovat. Zvolen´ y zp˚ usob komunikace je postaven nezas´ıl´an´ı ud´alost´ı. V´ yhodou tohoto zp˚ usobu je, ˇze nen´ı potˇreba zn´at rozhran´ı jednotliv´ ych objekt˚ u, ale staˇc´ı, aby kaˇzd´ y objekt umˇel pˇrijmout a zpracovat ud´alost. Nev´ yhodou vˇsak je obt´ıˇzn´a synchronizace, protoˇze zas´ıl´an´ı ud´alost´ı je pouze jednosmˇern´a operace. 2
VRUT
Graf sc´eny
Synchronizace se ˇreˇs´ı tak, ˇze zaslan´a ud´alost vyvol´a odezvu v podobˇe jin´e ud´alosti, na kterou objekty poˇckaj´ı v blokuj´ıc´ım m´odu. Ud´alosti jsou zas´ıl´any centr´aln´ımu spr´avci ud´alost´ı, kter´ y se nach´az´ı v j´adru, a ten je pot´e distribuuje pˇr´ısluˇsn´ ym objekt˚ um. Kaˇzd´ y z objekt˚ u m˚ uˇze pˇrij´ımat libovoln´ y typ ud´alost´ı, staˇc´ı pouze, aby se u spr´avce ud´alost´ı zaregistroval k odbˇeru dan´eho typu ud´alost´ı. Kaˇzd´ y novˇe vytvoˇren´ y modul tam m˚ uˇze ihned reagovat na st´avaj´ıc´ı ud´alosti.
2.4
Graf sc´ eny
Graf sc´eny je hlavn´ı u ´loˇziˇstˇe grafick´ ych dat. Protoˇze se jedn´a o ˇca´st, ke kter´e je potˇreba pˇristupovat ˇcasto a z r˚ uzn´ ych m´ıst, je um´ıstˇen pˇr´ımo v j´adˇre a nen´ı ho moˇzn´e nahradit extern´ım modulem. Jeho datov´e struktury jsou jednoznaˇcnˇe urˇcen´e a jsou spoleˇcn´e pro vˇsechny moduly, kter´e s n´ım pracuj´ı. Z´akladn´ım prvkem grafu sc´eny je uzel. M˚ uˇze obsahovat pˇr´ımo grafick´a data a m˚ uˇze m´ıt libovoln´ y poˇcet potomk˚ u. Kaˇzd´ y uzel m´a t´eˇz definovanou transformaˇcn´ı matici, kter´a definuje um´ıstˇen´ı tohoto uzle a jeho potomk˚ u jako logick´eho celku v lok´aln´ım mˇeˇr´ıtku. V glob´aln´ım mˇeˇr´ıtku lze z´ıskat vyn´asoben´ım transformaˇcn´ıch matic od koˇrene stromu po dan´ y uzel. Tato transformaˇcn´ı matice pro glob´aln´ı mˇeˇr´ıtko je vˇsak automaticky pro kaˇzd´ y uzel pˇrepoˇc´ıt´av´ana, protoˇze se jedn´a o u ´daj, se kter´ ym se ˇcasto pracuje. Kaˇzd´a operace nad grafem sc´eny vyvol´a ud´alost, kter´a je zasl´ana spr´avci ud´alost´ı. Modul ˇci jin´ y zaregistrovan´ y pˇr´ıjemce m˚ uˇze m´ıt tedy pˇrehled o tom, co se ve vybran´e sc´enˇe odehr´av´a. Je umoˇznˇena i opaˇcn´a komunikace, tedy pokud se spr´avci ud´alost´ı odeˇsle nˇejak´a ud´alost pro operaci nad sc´enou, je tato ud´alost pˇred´ana a provedena skrze rozhran´ı sc´eny. Uzle grafu sc´eny se podle funkˇcnosti dˇel´ı na nˇekolik typ˚ u. Mezi uzly nen´ı ˇz´adn´a z´avislost na typu, je moˇzn´e kombinovat libovoln´e typy na pozici rodiˇce ˇci potomka. Typu uzl˚ u jsou: Z´ akladn´ı uzel – SceneNode, ASSEMBLY Pˇredstavuje logick´ y prvek ve sc´enˇe. Je v´ ychoz´ım typem, ze kter´eho vych´az´ı vˇsechny ostatn´ı uzly. Koˇ renov´ y uzel – SceneNode, ROOT 3
VRUT
Hierarchie ob´alek
Jin´e oznaˇcen´ı pro z´akladn´ı uzel, kter´ y je koˇrenov´ ym uzlem sc´eny. Kamera – CameraNode, CAMERA Uzel reprezentuj´ıc´ı kameru. Pˇrid´av´a automaticky aktualizovanou projekˇcn´ı matici a informace o pohledov´em jehlanu vˇcetnˇe ob´alky v podobˇe koule. Uzel s geometri´ı – GeometryNode, GEOMETRY Pˇrid´av´a informace o geometrii a materi´alu. Geometrie je pops´ana primitivy, ze kter´ ych se skl´ad´a v´ ysledn´ y objekt, a jejich vlastnost´ı. Kaˇzd´a geometrie zahrnuje kromˇe grafick´ ych dat i ob´alku v podobˇe AABB v lok´aln´ım mˇeˇr´ıtku. Uzel se svˇ etlem – LightNode, LIGHT Pˇredstavuje zdroj svˇetla. ´ Uroveˇ n detail˚ u – LODNode, LOD Speci´aln´ı logick´ y celek, kter´ y umoˇzn ˇuje uchovat r˚ uznou kvalitu a sloˇzitost geometrie, spolu s informac´ı pˇri jak´e vzd´alenosti kamery od ob´alky uzlu se dan´a geometrie pˇrepne. Vˇzdy by mˇel b´ yt zobrazen pouze jeden potomek. Pˇ rep´ınaˇ c – SwitchNode, SWITCH Funguje jako pˇrep´ınaˇc mezi jednotliv´ ymi potomky. M˚ uˇzou b´ yt t´eˇz aktivov´any vˇsechny nebo ˇz´adn´ y. Pozad´ı – BackgroundNode, BACKGROUND Definuje pozad´ı pˇri zobrazen´ı. M˚ uˇze se jednat o kulovou plochu pozad´ı nebo o jeden obr´azek zobrazen´ y jako pozad´ı. Zdroj zvuku – SoundNode, SOUND SOURCE Uzel pˇredstavuj´ıc´ı zdroj svˇetla.
2.5
Hierarchie ob´ alek
Hierarchie ob´alek je implementov´ana pˇr´ımo v j´adˇre. Slouˇz´ı pˇredevˇs´ım k zefektivnˇen´ı operac´ı nad sc´enou, jako jsou oˇrez´av´an´ı pohledov´ ym jehlanem, detekce koliz´ı, ˇci testy pˇri vrh´an´ı paprsk˚ u. Hierarchie ob´alek je strom, kter´ y representuje rozdˇelen´ı sc´eny na menˇs´ı celky. Uzly stromu jsou pouze logick´ ym celkem ve sc´enˇe, list pˇredstavuje 4
VRUT
Moduly
Obr´azek 2.1: Ob´alky zobrazen´e ve sc´enˇe
jeden uzel grafu sc´eny s geometrick´ ymi daty. Kaˇzd´ y uzel representuje ˇca´st sc´eny, kter´a je vymezena urˇcit´ ym tˇelesem – ob´alkou. Tvar ob´alek je kv´adr, zarovnan´ y s osami, tzv. AABB (Axis Aligned Bounding Box). Kaˇzd´a ob´alka potomka je plnˇe obsaˇzena v ob´alce rodiˇce, takˇze koˇrenov´ y uzel pˇredstavuje AABB cel´e sc´eny. Ke kaˇzd´e sc´enˇe je pˇriˇrazena pouze jedna hierarchie ob´alek a z´avis´ı v´ yhradnˇe na prostorov´e hierarchii geometrie ve sc´enˇe, nikoliv na transformaˇcn´ı hierarchii sc´eny. Na obr´azku 2.1 jsou vidˇet zobrazen´e ob´alky modelu auta pˇr´ımo ve sc´enˇe.
2.6
Moduly
Moduly umoˇzn ˇuj´ı aplikaci rozˇsiˇrovat o nov´e funkce. Moduly jsou aktivov´any a spravov´any pˇr´ısluˇsn´ ym spr´avcem modul˚ u. Pro jednotliv´e moduly lze ak5
VRUT
Geometrie
tivovat libovoln´e mnoˇzstv´ı instanc´ı a kaˇzd´e je pˇriˇrazeno vlastn´ı vl´akno, ve kter´em prob´ıh´a ˇcinnost modulu. Jak jiˇz bylo pops´ano, komunikaci mezi jednotliv´ ymi moduly se zajiˇst’uje pomoc´ı ud´alost´ı, a vˇsechny moduly bez rozd´ılu mohou pouˇz´ıvat syst´em ud´alost´ı jako pˇr´ıjemci i odes´ılatel´e. Komunikace mezi moduly tak vˇzdy prob´ıh´a skrze j´adro. Moduly jsou podle ˇcinnosti, kterou vykon´avaj´ı, rozdˇeleny do skupin. Typy se mohou liˇsit v u ´rovni povolen´eho pˇr´ıstupu k j´adru a pˇredevˇs´ım v m´ıˇre a zp˚ usobu integrace do chodu hlav´ı aplikace. Typy modul˚ u jsou: Obecn´ y – Module Modul nez´avisl´ı na j´adˇre. Jedin´e spojen´ı s j´adrem je pomoc´ı ud´alost´ı. Modul sc´ eny – SceneModule M´a pˇr´ım´ y pˇr´ıstup ke spr´avci sc´en, ˇz´adn´a jin´a ˇca´st j´adra nen´ı pˇr´ıstupn´a. Modul pro import a export – IOModule Vych´az´ı z modulu sc´eny. Na stranˇe j´adra vyˇzaduje spolupr´aci pˇri v´ ybˇeru spr´avn´eho modulu pro poˇzadovan´ y form´at dat. Zobrazovac´ı modul – RenderModule Rozˇsiˇruje modul sc´eny. Vyˇzaduje vysokou m´ıru propojenosti ze strany j´adra, naopak ze strany modulu k ˇza´dn´emu rozˇs´ıˇren´ı pˇr´ıstupu k j´adru nedoch´az´ı. Manipul´ ator – ManipulatorModule Zpracov´av´a speci´aln´ı ud´alosti ze vstupn´ıch zaˇr´ızen´ı. Manipul´ ator kamery – CameraModule Na rozd´ıl od manipul´atoru je v´ıce specializov´an na ovl´ad´an´ı kamery.
2.7
Geometrie
Geometrie je souˇc´ast´ı sc´eny. Odkazov´ana m˚ uˇze b´ yt pouze uzlem s geometri´ı a nen´ı nijak z´avisl´a na materi´alu, takˇze jedna geometrie muˇze b´ yt pouˇzita v´ıce uzly a v kaˇzd´em z nich lze poˇz´ıt jin´ y materi´al. Na obr´azku 2.2 je model krychle definovan´ y jednou geometri´ı ve sc´enˇe odkazov´an pˇetkr´at, liˇs´ı se vˇsak v pouˇzit´em materi´alu. 6
VRUT
Geometrie
Obr´azek 2.2: Pro jednu geometrii je pouˇzito r˚ uzn´ ych materi´al˚ u
Geometrie vyuˇz´ıv´a dˇediˇcnost pro moˇznost definice v´ıce typ˚ u geometri´ı, vˇsechny typy maj´ı svou ob´alku AABB a umoˇzn ˇuj´ı pˇrevod geometrick´ ych dat do podoby seznamu troj´ uheln´ıku. Zat´ım jedin´ ym implementovan´ ym typem geometrie je troj´ uheln´ıkov´a representace, kter´a je definov´ana seznamem vrchol˚ u a index˚ u do pole vrchol˚ u, pˇr´ıpadnˇe pak norm´al a souˇradnic pro textury. Indexovanou troj´ uheln´ıkovou geometrii lze interpretovat jako TRI LIST, TRI FAN, TRI STRIP, POLYGON, LINES, LINE STRIP, POINTS nebo QUADS. Geometrie umoˇzn ˇuje libovolnou kombinaci podporovan´e interpretace primitiv v r´amci jedn´e geometrie.
7
VRUT
2.8
V´yvoj
V´ yvoj
Syst´em VRUT se st´ale jeˇstˇe vyv´ıj´ı. V souˇcasn´e dobˇe obsahuje velk´e mnoˇzstv´ı modul˚ u rozˇsiˇruj´ıc´ıch jeho moˇznosti. St´ale vˇsak existuje funkˇcnost, kter´a se ve st´avaj´ıc´ıch modulech nenach´az´ı, a proto jsou potˇreba nov´e moduly doimplementovat. Jedn´ım z nich je pr´avˇe modul pro detekci kontur a jejich n´asledn´ y export.
8
3 Detekce obrys˚ u Obrysy se v poˇc´ıtaˇcov´e grafice pouˇz´ıvaj´ı jako jedna z metod nefotorealistick´eho zobrazen´ı (NPR) a metody pro jejich detekce lze na nejhrubˇejˇs´ı u ´rovni rozdˇelit na rastrov´e a vektorov´e.
3.1
Rastrov´ a detekce obrys˚ u
ˇ ara(2010)]) Pro detekci obrys˚ u byla vyvinuta cel´a ˇrada algoritm˚ u (viz [Jiˇr´ı Z´ a pro pˇredstavu cituji tˇri metody uveden´e v tomto zdroji. NPR s pomoc´ı prahov´ an´ı 1. Um´ısti bodov´ y zdroj svˇetla L do polohy kamery. 2. Nastav materi´al vˇsech tˇeles na b´ıl´ y, ˇcistˇe dif´ uzn´ı. 3. Zobraz sc´enu osvˇetlenou pouze pomoc´ı zdroje L. 4. Pˇreved’ vykreslen´ y obraz prahov´an´ım na ˇcernob´ıl´ y. NPR s pomoc´ı pˇ rivr´ acen´ ych a odvr´ acen´ ych ploch 1. Rozdˇel plochy sc´eny na pˇrivr´acen´e a odvr´acen´e. 2. Vykresli pˇrivr´acen´e plochy b´ıle. 3. Posuˇ n model bl´ıˇze k rovinˇe. 4. Vykresli odvr´acen´e plochy ˇcernˇe (pomoc´ı pamˇeti hloubky). NPR s vyhled´ av´ an´ım zmˇ eny hloubky 1. Vyhodnot’ sc´enu pouze pomoc´ı pamˇeti hloubky. 2. Naˇcti mapu hloubek. 3. Pomoc´ı technik hled´an´ı hran nalezni na mapˇe m´ısta s v´ yraznou zmˇenou hloubky a vykresli je. Pˇr´ıstup tˇechto metod je rastrov´ y, a z tohoto d˚ uvodu jsem je zavrhl. Implementace by znamenala rasterizaci modelu, kter´ y je pops´an troj´ uheln´ıkovou s´ıt´ı, a jeho n´aslednou vektorizaci, aby bylo moˇzn´e v´ ysledek exportovat jako vektorov´ y obr´azek. 9
Detekce obrys˚ u
3.2
Vektorov´a detekce obrys˚ u
Vektorov´ a detekce obrys˚ u
Vektorov´ y pˇr´ıstup detekce obrys˚ u spoˇc´ıv´a v omezen´ı mnoˇziny vˇsech hran modelu pouze na ty, kter´e splˇ nuj´ı podm´ınky obrysov´ ych hran. Nejdˇr´ıve je nutn´e z troj´ uheln´ıkov´e representace vytvoˇrit seznam hran, ke kter´ ym se uloˇz´ı t´eˇz informace o prvc´ıch, kter´e s n´ı soused´ı (tzv. okˇr´ıdlen´a hrana). N´aslednˇe mohou b´ yt hrany rozdˇeleny do tˇr´ı skupin: Ostr´ e (skuteˇ cn´ e) hrany – tvoˇr´ı hranici ploch. S touto hranou soused´ı pouze jeden troj´ uheln´ık, nebo dva troj´ uheln´ıky, kter´e vˇsak na t´eto hranˇe maj´ı odliˇsn´e norm´alov´e vektory. Tyto hrany se nemus´ı pˇri zmˇenˇe kamery pˇrepoˇc´ıt´avat a jsou vˇzdy oznaˇceny jako obrysov´e. Potencion´ aln´ı obrysov´ e hrany – hrana, kter´a by mohla b´ yt obrysovou hranou. Obrysov´a hrana vznikne mezi pˇrivr´acen´ ym a odvr´acen´ ym troju ´heln´ıkem. U t´eto skupiny hran se mus´ı pˇri kaˇzd´e zmˇenˇe kamery ovˇeˇrit, zda je ˇci nen´ı hranou obrysovou. Pomocn´ e hrany – hrana mezi troj´ uheln´ıky, kter´e leˇz´ı pˇribliˇznˇe v jedn´e rovinˇe. V t´eto skupinˇe hran se obrysov´e hrany nenach´az´ı. Po tomto rozdˇelen´ı mus´ı b´ yt ve skupinˇe potencion´aln´ıch obrysov´ ych hran nalezeny ty, se kter´ ymi soused´ı jeden pˇrivr´acen´ y a jeden odvr´acen´ y troju ´heln´ık. Urˇcen´ı toho, zda je troj´ uheln´ık pˇrivr´acen´ y ˇci odvr´acen´ y vˇsak je, v pˇr´ıpadˇe, ˇze nen´ı dodrˇzeno poˇrad´ı vrchol˚ u, nemoˇzn´e. Pokud vˇsak pˇrevedeme vrcholy pomoc´ı zobrazovac´ı matice do 2D, m˚ uˇzeme obrysovou hranu urˇcit na z´akladˇe toho, zda tˇret´ı vrcholy (ty, kter´e nejsou souˇc´ast´ı hrany) pˇrilehl´ ych troj´ uheln´ık˚ u leˇz´ı ˇci neleˇz´ı ve stejn´e polorovinˇe urˇcen´e dvˇema vrcholy hrany - pokud ve stejn´e polorovinˇe leˇz´ı, je tato hrana obrysov´a (Obr´azek 3.1).
3.3
Viditelnost obrysov´ ych hran
U rastrov´ ych metod je viditelnost obrysov´ ych hran ˇreˇsena pomoc´ı Z-bufferu. U tˇech vektorov´ ych je vˇsak probl´em sloˇzitˇejˇs´ı a mus´ı se pouˇz´ıt nˇekter´ y z liniov´ ych algoritm˚ u viditelnosti. Jako pˇr´ıklad zde uvedu tˇri algoritmy slouˇz´ıc´ı ˇ ara(2010)]). k urˇcen´ı viditelnosti hran (viz [Jiˇr´ı Z´ 10
Detekce obrys˚ u
Viditelnost obrysov´ych hran
Obr´azek 3.1: Urˇcen´ı, zda se jedn´a o obrysovou hranu
3.3.1
Roberts˚ uv algoritmus
Roberts˚ uv algoritmus je urˇcen pro ˇreˇsen´ı hranov´e viditelnosti ve sc´enˇe sloˇzen´e z konvexn´ıch ploch a tˇeles. Postupnˇe pro vˇsechny hrany testuje, zda jsou zakryty jinou plochou nebo tˇelesem. Pokud je testovan´e hrana zakryta jen ˇc´asteˇcnˇe, rozdˇel´ı se hrana na zakrytou a nezakrytou ˇca´st a kaˇzd´a nezakryt´a ˇc´ast se st´av´a novou hranou, kterou je tˇreba otestovat. Roberts˚ uv algoritmus se stal z´akladem mnoha dalˇs´ıch metod, kter´e se liˇs´ı napˇr´ıklad seˇrazen´ım hran, pouˇzit´ım urychlovac´ıch test˚ u pˇr´ı hled´an´ı z´akryt˚ u, apod. Vˇetˇsina u ´prav pˇritom zachov´av´a hlavn´ı myˇslenku, kterou je rozdˇelen´ı potencion´alnˇe viditeln´ ych hran na element´arn´ı u ´seky, na nichˇz se jiˇz viditelnost nem˚ uˇze mˇenit. K nalezen´ı tˇechto s nemˇennou viditelnost´ı se pouˇz´ıv´a obrysov´ ych hran, nebot’ pouze ty indikuj´ı pˇr´ıpadnou zmˇenu viditelnosti. Velkou nev´ yhodou tohoto algoritmu je, ˇze zkoum´an´ı z´akrytu potencia´lnˇe zakryt´ ych element´arn´ıch u ´sek˚ u s nekonvexn´ımi mnohostˇeny je pomˇernˇe zdlouhav´e.
3.3.2
Appel˚ uv algoritmus
Appel˚ uv algoritmus je zaloˇzen na testov´an´ı potencion´alnˇe viditeln´ ych hran v˚ uˇci hran´am obrysov´ ym a hledaj´ı se jejich zd´anliv´e pr˚ useˇc´ıky (v pr˚ umˇetu). Pokud testovan´a hrana v tomto pr˚ useˇc´ıku leˇz´ı za obrysovou hranou, mˇen´ı se 11
Detekce obrys˚ u
Viditelnost obrysov´ych hran
0
1
2
1
0
1
0
Obr´azek 3.2: Zmˇena koeficient zakryt´ı v pr˚ useˇc´ıc´ıch hran
v tomto m´ıstˇe koeficient zakryt´ı – pokud za n´ı vstupuje, koeficient se zvyˇsuje, ´ pokud vystupuje, tak se sniˇzuje (Obr´azek 3.2). Useky, ve kter´ ych je koeficient zakryt´ı roven 0, jsou viditeln´e. Nejprve se mus´ı spoˇc´ıtat koeficient zakryt´ı v poˇca´teˇcn´ım vrcholu, a to urˇcen´ım poˇctu polygon˚ u, kter´e ho zakr´ yvaj´ı. Tyto hodnoty se pak d´ale nesou po hran´ach vych´azej´ıc´ıch z tohoto vrcholu a koeficient zakryt´ı se mˇen´ı, jen pokud hrana prot´ın´a hranu obrysovou a vstupuje za n´ı. Pomˇernˇe jednoduch´ y postup tohoto algoritmu je komplikov´an nutnost´ı oˇsetˇrov´an´ı mnoha moˇzn´ ych singul´arn´ıch pˇr´ıpad˚ um kdy napˇr. pr˚ umˇet vrcholu obrysov´e hrany leˇz´ı v pr˚ umˇetu testovan´e hrany a naopak.
3.3.3
Weiler-Atherton˚ uv algoritmus
Weiler-Atherton˚ uv algoritmus je zaloˇzen na rychl´em oˇrez´av´an´ı nekonvexn´ıch ploch vybranou bl´ızkou plochou. Nejdˇr´ıve jsou vˇsechny plochy seˇrazeny podle jejich minim´aln´ı vzd´alenosti od pozorovatele a n´aslednˇe je vybr´ana prvn´ıho, podle kter´e jsou rozstˇr´ıh´any vˇsechny zb´ yvaj´ıc´ı plochy. Ty jsou roztˇr´ıdˇeny do dvou dalˇs´ıch seznam˚ u v z´avislosti na tom, zda dan´a ˇc´ast leˇz´ı uvnitˇr nebo vnˇe nadˇrazen´e plochy. Tento postup se d´ale opakuje i pro dalˇs´ı plochy v seznamu. Zp˚ usob oˇrez´av´an´ı je naznaˇcen na obr´azku 3.3. Z´akladem je nalezen´ı vˇsech pr˚ useˇc´ık˚ u mezi dvˇema mnoˇzinami u ´seˇcek v rovinˇe. Prvn´ı je tvoˇrena u ´seˇckami mezi vrcholy A0 – A1 – A2 – A0 , druh´a mezi vrcholy B0 – B1 – B2 – B3 – B0 . 12
Detekce obrys˚ u
Viditelnost obrysov´ych hran
A2
B2
I1
I0
A0
B1
A1
B3
B0
A0
I0
A1
I1
A2
B0
B1
I1
B2
I0
B3
Obr´azek 3.3: Zp˚ usob oˇrez´av´an´ı ploch
Pr˚ useˇc´ıky obou ploch jsou body I0 , I1 , I3 . Algoritmus pracuje se dvˇema seznamy – vrcholy prvn´ı a druh´e plochy. Pr˚ useˇc´ıky se zaˇrad´ı mezi vrcholy prvn´ı a druh´e plochy. V prvn´ıho seznamu najdeme vstupn´ı pr˚ useˇc´ık a postupujeme pˇres vrcholy vpˇred, dokud nenaraz´ıme na dalˇs´ı z pr˚ useˇc´ık˚ u. V tomto m´ıstˇe pˇrejdeme do druh´eho seznamu na odpov´ıdaj´ıc´ı m´ısto, a zase postupujeme pˇres vrcholy vpˇred aˇz k dalˇs´ımu pr˚ useˇc´ıku. Zde se zase pˇresuneme do prvn´ıho seznamu a postup opakujeme tak dlouho, dokud nenaraz´ıme na prvn´ı pr˚ useˇc´ık. Vˇsechny proˇsl´e vrcholy a pr˚ useˇc´ıky jsou vrcholy oˇrezan´e plochy. Tento algoritmus je pˇr´ıkladem postupu, ˇreˇs´ıc´ıho viditelnost ploch. Plochy nebo jejich oˇrezan´e ˇc´asti, kter´e byly oznaˇceny jako viditeln´e, lze d´ale vybarvit.
13
4 PostScript Jedn´ım z c´ıl˚ u t´eto pr´ace bylo umoˇznit export nalezen´ ych hran do form´atu PostScript, a proto se v t´eto kapitole sezn´am´ıme s t´ımto form´atem. Pouˇzit´e informace jsou ˇcerp´any z [Ado(1999)], [Ado(1985)] a [Tiˇsnovsk´ y(2006)].
4.1
Z´ akladn´ı charakteristiky
PostScript, kter´ y byl vyvinut firmou Adobe v roce 1985, je programovac´ı jazyk, souˇz´ıc´ı k popisu str´anky, kter´a se m´a vykreslit na tisk´arnˇe, obrazovce poˇc´ıtaˇce, ˇci jin´em zobrazovac´ım zaˇr´ızen´ı. K zobrazen´ı na monitoru je zapotˇreb´ı vhodn´ y prohl´ıˇzeˇc, napˇr´ıklad volnˇe ˇsiˇriteln´ y program GhostView spolu s Ghostscriptem. Tisk m˚ uˇze prob´ıhat pˇr´ımo na postscriptov´e tisk´arnˇe. Mezi moˇznosti popisu str´anky patˇr´ı oper´atory pro kreslen´ı pˇr´ımek, oblouk˚ u, obd´eln´ık˚ u a kubick´ ych kˇrivek, nastaven´ı vzhledu obrysov´ ych ˇcar a v´ yplnˇe, nebo nastaven´ı oˇrezov´e cesty. Barvy mohou b´ yt nastaveny v´ıce zp˚ usoby – stupnˇe ˇsedi, RGB, CMYK a CIE, a t´eˇz je moˇzn´e m´ısto barvy pouˇz´ıt vzory nebo st´ınov´an´ı. Text je tak´e povaˇzov´an za grafick´e tvary, takˇze s n´ım lze pracovat pomoc´ı grafick´ ych oper´ator˚ u. Rastrov´a grafika je pˇr´ımo vloˇzena do popisu str´anky a existuje ˇrada zp˚ usob˚ u, jak reprodukovat obr´azky na v´ ystupn´ım zaˇr´ızen´ı. PostScript t´eˇz podporuje vˇsechny kombinace line´arn´ıch transformac´ı, jako jsou posunu, zmˇeny velikosti, otoˇcen´ı, zrcadlen´ı a zkosen´ı. Transformace se aplikuj´ı na vˇsechny prvky str´anky, vˇcetnˇe textu, grafick´ ych tvar˚ u a rastrov´e grafiky. PostScript pouˇz´ıv´a k pops´an´ı grafick´e informace programovac´ı jazyk, jehoˇz instrukce se zaznamen´avaj´ı v postfixov´e notaci. To znamen´a, ˇze nejdˇr´ıve mus´ı b´ yt zad´any operandy a potom teprve oper´ator. Interpretace se prov´ad´ı pomoc´ı zasobn´ıku.
14
PostScript
4.2
Syntaxe
Syntaxe
Poststriptov´ y soubor je soubor textov´ y, proto leze k jeho vytvoˇren´ı pouˇz´ıt textov´ y editor. Jednotliv´e syntaktick´e konstrukce jsou oddˇeleny b´ıl´ ymi“ ” znaky, kter´e jsou NUL, TAB, LF, FF, CR a SP. Je tedy jedno, zda se jednotliv´e hodnoty ˇci oper´atory p´ıˇs´ı na nov´e ˇr´adky, nebo se k jejich oddˇelen´ı pouˇzije jin´ y b´ıl´ y“ znak, napˇr´ıklad mezera. ” Dalˇs´ımi speci´aln´ımi znaky jsou (, ), <, >, [, ], {, }, /, a %, kter´e slouˇz´ı pro oddˇelen´ı text˚ u, tˇel procedur, jmen objekt˚ u a koment´aˇr˚ u. Koment´aˇre zaˇc´ınaj´ı znakem % a konˇc´ı znakem nov´e ˇra´dky. ˇ ısla lze zad´avat n´asleduj´ıc´ımi zp˚ C´ usoby: • Cel´a ˇc´ısla, napˇr´ıklad: 123 -98 43445 0 +17 • Re´aln´a ˇc´ısla, napˇr´ıklad: -.002 34.5 -3.62 123.6e10 1.0E-5 1E6 -1. 0.0 ˇ ısla pˇri urˇcit´em z´akladu, napˇr´ıklad: • C´ 8#1777 16#FFFE 2#1000 Textov´e ˇretˇezce se zad´avaj´ı takto: • Doslovn´ y text je uzavˇren v ( a ) • Hexadecim´aln´ı data jsou uzavˇrena v < a > • ASCII base-85 data jsou uzavˇrena v <∼ a ∼> N´azvy objekt˚ u se zav´adˇej´ı pomoc´ı znaku /, za kter´ ym n´asleduje zvolen´e jm´eno. Lom´ıtko nen´ı souˇca´st´ı jm´ena. Prvky pole se zad´avaj´ı mezi znaky [ a ]. Konstrukce pole tedy m˚ uˇze vypadat takto: [ 123 /abc (xyz) ] Tˇela procedur se zad´avaj´ı pomoc´ı spustiteln´eho pole. Jeho prvky se zad´avaj´ı mezi znaky { a }, napˇr´ıklad takto: 15
PostScript
Z´akladn´ı pˇrehled oper´ator˚ u
{add 2 div}
4.3
Z´ akladn´ı pˇ rehled oper´ ator˚ u
Matematick´ e oper´ atory add – souˇcet hodnot div – pod´ıl hodnot mod – zbytek po dˇelen´ı hodnot mul – vyn´asoben´ı hodnot sub – rozd´ıl hodnot sqrt – druh´a odmocnina hodnoty Oper´ atory pro pr´ aci se z´ asobn´ıkem pop – zahod´ı vrchn´ı hodnotu dup – duplikuje vrchn´ı hodnotu clear – zahod´ı cel´ y z´asobn´ı Oper´ atory pro nastaven´ı souˇ radn´ eho syst´ emu trnaslate – posun scale – mˇeˇr´ıtko rotate – natoˇcen´ı Oper´ atory pro kreslen´ı cesty newpath – Inicializace nov´e cesty moveto, rmoveto – pˇresunut´ı aktu´aln´ıch souˇradnic lineto, rlineto – pˇripojen´ı u ´seˇcky arc, arcn, arct, arcto – pˇripojen´ı oblouku cuketo, rcurveto – pˇripojen´ı Bezi´erovy kubiky closepath – uzavˇre cestu Grafick´ e oper´ atory setlinewidth – nastaven´ı ˇs´ıˇrku ˇc´ary 16
PostScript
Definice promˇenn´ych a nov´ych pˇr´ıkaz˚ u
setrgbcolor – nastaven´ı barevn´ y prostor na RGB a nastav´ı jednotliv´e barevn´e sloˇzky stroke – vykreslen´ı ˇca´ry po aktu´aln´ı cestˇe V´ ystupn´ı opr´ atory showpage – vykresl´ı a smaˇze aktu´aln´ı str´anku
4.4
Definice promˇ enn´ ych a nov´ ych pˇ r´ıkaz˚ u
Pro definici promˇenn´ ych a nov´ ych pˇr´ıkaz˚ u se pouˇz´ıv´a pˇr´ıkaz def, kter´ y ke zvolen´emu jm´enu pˇriˇrad´ı hodnotu. Pokud je touto hodnotou seznam pˇr´ıkaz˚ u, st´av´a se takov´eto jm´eno nov´ ym pˇr´ıkazem. Seznam pˇr´ıkaz˚ u se zapisuje do sloˇzen´ ych z´avorek. Pro vykreslen´ı pˇr´ımky mezi zadan´ ymi body lze napˇr´ıklad definovat pˇr´ıkaz: /linefromto {moveto lineto} def Tento pˇr´ıkaz lze pak pouˇz´ıt n´asleduj´ıc´ım zp˚ usobem: x1 y1 x2 y2 linefromto
4.5
Souˇ radn´ y syst´ em
Pro natoˇcen´ı, zkosen´ı, posun, zmˇenu velikosti ˇci zrcadlen´ı pouˇz´ıv´a PostScript line´arn´ı transformace. Pro zad´av´an´ı souˇradnic, kter´ ymi se ˇr´ıd´ı vykreslov´an´ı, se pouˇz´ıv´a souˇradn´ y syst´em nez´avisl´ y na zobrazovac´ım zaˇr´ızen´ı. Z´akladn´ı d´elkovou jednotkou je jeden topologick´ y bod, jehoˇz d´elka se rovn´a 1/72 palce. Proto se tˇesnˇe pˇred rastrov´an´ım prov´ad´ı pˇrevod tˇechto souˇradnic do souˇradn´eho syst´emu dan´eho zobrazovac´ıho zaˇr´ızen´ı.
17
PostScript
Souˇradn´y syst´em
Pˇri inicializaci nov´e str´anky je nastaven poˇca´tek souˇradn´eho syst´emu do lev´eho doln´ıho rohu. Ne vˇzdy takov´eto nastaven´ı vyhovuje, je vˇsak moˇzn´e nastavit transformaˇcn´ı matici a takto definovat uˇzivatelsk´ y prostor. Nastaven´ı transformaˇcn´ı matice pro poˇca´tek uˇzivatelsk´eho prostoru na stˇred str´anky a d´elkov´ ych jednotek na milimetr vypad´a napˇr´ıklad takto: 595 2 div 842 2 div translate 72 25.4 div dup scale
18
5 N´avrh Pˇri n´avrhu ˇreˇsen´ı jsem se nejdˇr´ıve ocitl pˇred ot´azkou, zda pouˇz´ıt rastrovou nebo vektorovou detekci obrys˚ u. Rozhodl jsem se pro vektorovou, a to proto, ˇze v´ ysledkem exportu obrys˚ u m´a byt vektorov´ y obr´azek. V pˇr´ıpadˇe poˇzit´ı nˇekter´e z rastrov´e metody by muselo nejdˇr´ıve doj´ıt k rasterizaci – model je pops´an troj´ uheln´ıkovou s´ıt´ı, a pot´e k pˇreveden´ı zp´atky na vektory, kter´e by se pouˇzily pro export. Bylo tedy nutn´e vyˇreˇsit 6 z´akladn´ıch bod˚ u, a to: • Nalezen´ı vˇsech hran modelu • Rozdˇelen´ı seznamu na skuteˇcn´e a potencion´alnˇe obrysov´e hrany • Nalezen´ı skuteˇcnˇe obrysov´ ych hran • Sestaven´ı lomen´ ych ˇcar z obrysov´ ych hran • Viditelnost obrysov´ ych hran • Export obrys˚ u do souboru Pˇri pr´aci s re´aln´ ymi daty se vˇsak vyskytl jeˇstˇe jeden, a to vyˇreˇsit vznik faleˇsn´ ych hran zp˚ usoben´ y v´ıcen´asobn´ ym v´ yskytem jednoho bodu v popisu geometrie.
5.1
Nalezen´ı vˇ sech hran
Indexovou geometrii VRUTu lze interpretovat jako TRI LIST, TRI FAN, TRI STRIP, POLYGON, LINES, LINE STRIP, POINTS, QUADS. Proto jsem se rozhodl kaˇzdou z tˇechto interpretac´ı zpracovat samostatnˇe a pˇri postupn´em proch´azen´ı indexov´eho pole zaˇrazovat hrany do seznamu na z´akladˇe sch´emat na obr´azku 5.1. U interpretac´ı LINES a LINE STRIP mohou vznikat rovnou skuteˇcn´e hrany, POINTS se m˚ uˇze ze vkl´ad´an´ı hran vynechat.
19
N´avrh V4
Nalezen´ı skuteˇcn´ych hran V4
V3
V2
V5
V0
V3
V0
TRI_LIST
TRI_FAN
V4
V4
V3
V5
V2
V0
V1
LINES
V4
V1
V1
POLYGON V3
V5
V3
V2
V2
V0
V1
POINTS
LINE_STRIP
V2
V0
V4
TRI_STRIP
V2
V0
V2
V3
V5
V3
V5
V0
V1
V4
V5
V2
V5
V1
V3
V1
V0
V1 QUADS
Obr´azek 5.1: Pˇrehled interpretac´ı geometrie VRUTu
5.2
Nalezen´ı skuteˇ cn´ ych hran
Nalezen´ı skuteˇcn´ ych hran je zaloˇzeno na jednoduch´em principu rozdˇelen´ı seznamu vˇsech hran do dvou na z´akladˇe toho, zda je souˇca´st´ı jednoho nebo dvou troj´ uheln´ık˚ u. Pokud je hrana souˇca´st´ı jednoho troj´ uheln´ıku, nach´az´ı se tak na okraji plochy a je to tedy skuteˇcn´a hrana, kter´a se bude vykreslovat vˇzdy a nez´avisle na parametrech kamery. Do seznamu skuteˇcn´ ych hran jsou t´eˇz zaˇrazeny vˇsechny hrany, kter´e jsou souˇc´ast´ı v´ıce neˇz dvou troj´ uheln´ık˚ u. Pokud je sd´ılena dvˇema troj´ uheln´ıky, pak je tˇreba prov´est dalˇs´ı testy, aby se rozhodla o jej´ım vykreslen´ı, a je j´ı tedy potˇreba zaˇradit do seznamu potencion´alnˇe obrysov´ ych hran, jejichˇz zobrazen´ı je z´avisl´e na parametrech kamery.
5.3
Nalezen´ı obrysov´ ych hran
Po rozdˇelen´ı seznamu vˇsech hran na skuteˇcn´e a potencion´alnˇe obrysov´e jsou hrany z prvnˇe jmenovan´eho z nich zobrazov´any vˇzdy. Probl´em nast´av´a v pˇr´ıpadˇe druh´eho seznamu, ve kter´em se mus´ı hrany, kter´e se budou zobrazovat, 20
N´avrh
Sestaven´ı lomen´ych ˇcar
nal´ezt v z´avislosti na parametrech kamery. Vˇsechny body se nejdˇr´ıve pomoc´ı pohledov´e matice pˇrevedou do souˇradnic, kter´e jsou pouˇzity pˇri zobrazen´ı modelu, a pot´e se pro kaˇzdou hranu ze seznamu potencion´alnˇe obrysov´ ych ovˇeˇruje, zda jej´ı tˇret´ı a ˇctvrt´ y vrchol leˇz´ı ve stejn´e polorovinˇe definovan´e pˇr´ımkou urˇcenou jej´ımi prvn´ımi dvˇema vrcholy (Obr´azek 3.1). Pokud ve stejn´e polorovinˇe leˇz´ı, je nastaven pˇr´ıznak, kter´ y urˇc´ı, ˇze pˇri vykreslen´ı bude tato hrana zobrazena.
5.4
Sestaven´ı lomen´ ych ˇ car
K sestaven´ı lomen´ ych ˇcar z jednotliv´ ych hran jsem se rozhodl proto, aby se n´aslednˇe l´epe ˇreˇsila viditelnost hran, i z hlediska velikosti v´ ysledn´eho exportovan´eho souboru (nemus´ı se neust´ale pˇresouvat pozice pera). Nejdˇr´ıve si ke kaˇzd´emu vrcholu vytvoˇr´ım seznam hran, kter´e jsou k nˇemu nav´az´any. Pot´e se postupnˇe proch´azej´ı vrcholy, ze kter´ ych vede jedna nebo tˇri a v´ıce hran. Tyto vrcholy jsou urˇceny jako poˇca´tek lomen´e ˇca´ry a d´ale se postupuje ve smˇeru jeˇstˇe nepouˇzit´e hrany (proˇsl´e hrany se oznaˇc´ı) tak dlouho, dokud je poˇcet hran nav´azan´ ych k vrcholu roven dvˇema. Takto se postupnˇe naleznou vˇsechny acyklick´e lomen´e ˇc´ary. Pokud zbudou nˇekter´e vrcholy se dvˇema nav´azan´ ymi neoznaˇcen´ ymi hranami, jsou urˇceny jako poˇc´atek lomen´e ˇca´ry a d´ale se postupuje ve smˇeru jeˇstˇe nepouˇzit´ y hrany tak dlouho, dokud nen´ı dosaˇzeno poˇc´atku lomen´e ˇca´ry. T´ımto zp˚ usobem jsou nalezeny vˇsechny cyklick´e lomen´e ˇca´ry. Tento mechanizmus je naznaˇcen na obr´azku 5.2. Vrcholy, ze kter´ ych vych´az´ı jedna nebo tˇri a v´ıce hran, jsou zn´azornˇeny ˇcern´ ymi punt´ıky, a ty, ze ´ cky kter´ ych vych´azej´ı pouze hrany dvˇe, jsou oznaˇceny punt´ıky b´ıl´ ymi. Useˇ mezi nimi zn´azorˇ nuj´ı nalezen´e obrysov´e hrany a ˇsipky ukazuj´ı postupn´e vytv´aˇren´ı lomen´ ych ˇcar. Punt´ık s kˇr´ıˇzkem zn´azorˇ nuje zbyl´ y vrchol, ze kter´eho vych´az´ı pouze dvˇe hrany, kter´ y je pouˇzit jako zaˇca´tek dalˇs´ı lomen´e ˇc´ary.
21
N´avrh
Viditelnost obrysov´ych hran
Obr´azek 5.2: Sestaven´ı lomen´ ych ˇcar
5.5
Viditelnost obrysov´ ych hran
Protoˇze jsem se rozhodl pro vektorovou detekci obrys˚ u, pro ˇreˇsen´ı viditelnost´ı hran pˇripadal v u ´vahu Roberts˚ uv, Appel˚ uv nebo Weiler-Atherton˚ uv algoritmus. Roberts˚ uv m´a tu nev´ yhodu, ˇze zkoum´an´ı z´akrytu potencion´alnˇe zakryt´ ych u ´sek˚ u hran s nekonvexn´ımi mnohostˇeny je zdlouhav´e. Model, kter´ y jsem mˇel k dispozici, byl sloˇzen z v´ıce neˇz mili´onu troj´ uheln´ık˚ u, a proto sem se tento algoritmus rozhodl zavrhnout, aby bylo moˇzno obrysy zobrazovat v re´aln´em ˇcase. Weiler-Atherton˚ uv algoritmus [Kevin Weiler(1977)] ˇreˇs´ı viditelnost ploch. Tyto plochy by nejdˇr´ıve bylo nutn´e ze seznamu lomen´ ych ˇcar sestrojit, a aˇz potom tento algoritmus aplikovat. Rozhodl jsem se proto vyuˇz´ıt Appel˚ uv algoritmus [Appel(1967)], pro kter´ y popis obrysov´ ych hran staˇc´ı, nebot’ ˇreˇs´ı viditelnost na z´akladˇe pr˚ useˇc´ık˚ u tˇechto hran. Nejprve bylo nutn´e vypoˇc´ıst koeficienty zakryt´ı v roz´ıch geometrie. Pro tento v´ ypoˇcet se pouˇzije test pr˚ useˇc´ıku polopˇr´ımky zaˇc´ınaj´ıc´ı v dan´em rohu a proch´azej´ıc´ı druh´ ym bodem testovan´e hrany s hranou vˇsech troj´ uheln´ık˚ u soused´ıc´ıch s dan´ ym rohem, kter´e vˇsak rohem ani druh´ ym bodem testovan´e hrany neproch´azej´ı. Pokud je v tomto pr˚ useˇc´ıku testovan´a hrana za hranou troj´ uheln´ıku, vych´az´ı z rohu za t´ımto troj´ uheln´ıkem schov´ana, a proto se jej´ı koeficient zakryt´ı zv´ yˇs´ı o jedna. Pro objasnˇen´ı v´ ypoˇctu koeficient˚ u v roz´ıch n´am poslouˇz´ı obr´azek 5.3. Testovan´ y roh je zde oznaˇcen p´ısmenem C, a soused´ı s n´ım ˇctyˇri troj´ uheln´ıky CV0 V1 , CV1 V2 , CV2 V3 , CV3 V0 . Hrana, pro kterou se prov´ad´ı v´ ypoˇcet koeficientu zakryt´ı, je CV0 , a hrany vˇsech ˇctyˇr troj´ uheln´ık˚ u, kter´e splˇ nuj´ı podm´ınku, ˇze neproch´azej´ı rohov´ ym bodem C ani druh´ ym bodem testovan´e hrany V0 ,
22
N´avrh
Viditelnost obrysov´ych hran
jsou pouze dvˇe – V1 V2 a V2 V3 . Pr˚ useˇc´ık polopˇr´ımky CV0 a tˇechto dvou hran je pouze jeden, na obr´azku oznaˇcen´ y krouˇzkem. Pokud se v tomto pr˚ useˇc´ıku polopˇr´ımka CV0 nach´az´ı za u ´seˇckou V1 V2 , je schov´ana za troj´ uheln´ıkem CV1 V2 a nutn´e zv´ yˇsit koeficient zakryt´ı t´eto hrany o jedna, pokud se nach´az´ı pˇred n´ı, tento koeficient se nemˇen´ı.
V3
V2 C V0 V1 Obr´azek 5.3: V´ ypoˇcet koeficientu zakryt´ı v roz´ıch geometrie
Dalˇs´ım krokem by mˇelo b´ yt rozsek´an´ı sestaven´ ych lomen´ ych ˇcar na element´arn´ı u ´seky, na nichˇz se viditelnost nem˚ uˇze zmˇenit. K nalezen´ı tˇechto u ´sek˚ u lze s v´ yhodou pouˇz´ıt obrysov´e hrany, vyjma tˇech, kter´e sd´ılej´ı troj´ uheln´ıky leˇz´ıc´ıch na obou stran´ach dan´e hrany (podmnoˇzina skuteˇcn´ ych hran). Na obr´azku 5.4 je vidˇet, jak´ ym zp˚ usobem ovlivˇ nuj´ı tyto hrany (nakresleny silnˇejˇs´ı ˇca´rou) viditelnost dan´ ych u ´sek˚ u. U lomen´e ˇca´ry se t´eˇz uchov´av´a informace o relativn´ım koeficientu zakryt´ı na jej´ım zaˇca´tku a konci. V bodˇe rozdˇelen´ı se nastav´ı pro zakrytou ˇca´st tento koeficient na hodnotu, kter´a koresponduje s poˇctem pˇrilehl´ ych troj´ uheln´ık˚ u, pro nezakrytou ˇca´st se koeficient v bodˇe rozdˇelen´ı nastav´ı na nulu. Pot´e, co jsou vˇsechny ˇca´ry rozdˇeleny na u ´seky, ve kter´ ych se jiˇz viditelnost zmˇenit nem˚ uˇze, a jsou nastaveny jejich relativn´ı koeficienty zakryt´ı v˚ uˇci ostatn´ım navazuj´ıc´ım ˇcar´am, urˇc´ı se lomen´a ˇca´ra, jej´ıˇz souˇc´ast´ı je bod s nejmenˇs´ı hloubkou. Tato ˇc´ara je vˇzdy viditeln´a, jej´ı absolutn´ı koeficient zakryt´ı se nastav´ı na nulu, a pomoc´ı proch´azen´ı grafem, jehoˇz hranami jsou lomen´e ˇca´ry, se vypoˇc´ıtaj´ı absolutn´ı koeficienty zakryt´ı vˇsech lomen´ ych ˇcar. ˇ ara je viditeln´a, pokud jej´ı koeficient zakryt´ı je roven nule. C´ 23
N´avrh
Viditelnost obrysov´ych hran
Obr´azek 5.4: Rozdˇelen´ı hran na element´arn´ı u ´seky s nemˇennou viditelnost´ı
Rozdˇelen´ı lomen´e ˇca´ry je nutn´e pouze v pˇr´ıpadˇe, ˇze tato vstupuje za jinou, a v m´ıstˇe rozdˇelen´ı se z´akonitˇe mˇen´ı koeficient zakryt´ı. U lomen´e ˇcary se tak´e ukl´ad´a informace o pˇrilehl´ ych troj´ uheln´ıc´ıch, d´ıky kter´e je moˇzn´e rozpoznat, kter´a ˇca´st rozdˇelen´e ˇca´ry se nach´az´ı za plochou ohraniˇcenou dˇelic´ı ˇca´rou a kter´a mimo ni. Jak s touto informac´ı pracovat objasˇ nuje obr´azek 5.5. Na rozdˇelen´em u ´seku lomen´e ˇca´ry se stejn´a informace o pˇrilehl´ ych troj´ uheln´ıc´ıch uchov´av´a pro obˇe nov´e ˇc´asti.
Obr´azek 5.5: U lomen´e ˇcary se tak´e ukl´ad´a informace o pˇrilehl´ ych troj´ uheln´ıc´ıch
24
N´avrh
5.6
Export obrys˚ u
Export obrys˚ u
Pro export obrys˚ u do souboru ve form´atu PostScript jsem se rozhodl vyuˇz´ıt sestaven´e lomen´e ˇca´ry. Nejdˇr´ıve se pˇresunou souˇradnice na jej´ı zaˇca´tek, a pot´e se k cestˇe pˇripoj´ı u ´seˇcka konˇc´ıc´ı v dalˇs´ım jej´ım vrcholu. Takto se k cestˇe postupnˇe pˇripoj´ı vˇsechny u ´seˇcky, kter´e tvoˇr´ı lomenou ˇca´ru a za posledn´ı z nich se cesta uzavˇre. Takto budou do souboru vyexportov´any vˇsechny lomen´e ˇca´ry tvoˇr´ıc´ı obrys modelu. Exportovan´e hrany se nebudou nikterak oˇrez´avat podle velikosti zobrazovan´eho okna, ale pro toto oˇrez´an´ı se pouˇzij´ı pˇr´ımo pˇr´ıkazy jazyka PostScript.
5.7
Vznik faleˇ sn´ ych hran
D˚ uvodem vzniku faleˇsn´ ych hran na nˇekter´ ych modelech je to, ˇze jeden bod je v modelu uloˇzen nˇekolikr´at, a definice geometrie se d´ıky tomu na nˇej odkazuje pomoc´ı r˚ uzn´ ych index˚ u. Pokud tedy seznam hran vznikal jen za pomoci index˚ u, a nebral v u ´vahu skuteˇcnou polohu bodu a norm´alov´ y vektor plochy v tomto bodˇe, v´ ysledn´e obrysov´e hrany byly protk´any velk´ ym mnoˇzstv´ım faleˇsn´ ych hran (Obr´azek 5.6).
Obr´azek 5.6: Model s faleˇsn´ ymi hranami a ten sam´ y po jejich odstranˇen´ı
K odstranˇen´ı tˇechto faleˇsn´ ych hran jsem se rozhodl pouˇz´ıt haˇsovac´ı tabulku, popsanou v pr´aci [Ska(2009)]. Vedla mˇe k tomu jej´ı rychlost pˇri ovˇeˇrov´an´ı duplicity bod˚ u, kter´a se odv´ıj´ı od n´ızk´e d´elky klastr˚ u tabulky. Je
25
N´avrh
Vznik faleˇsn´ych hran
zaloˇzena na haˇsovac´ı funkci Index = (int)((αX + βY + γZ)C + 0.5)&T kde (int) je konverze na datov´ y typ unsigned integer, X, Y , Z jsou souˇradnice bodu, α, β, γ jsou koeficienty haˇsovac´ı funkce, C je koeficient, kter´ ym se zajist´ı, aby se vyuˇzilo pln´eho rozsahu datov´eho typu unsigned integer, T + 1 je velikost tabulky (T = 2k − 1), & representuje modulo, kter´e je implementov´ano jako logick´ y oper´ator, a 0.5 je konstanta, kter´a byla zjiˇstˇena experiment´alnˇe a pom´ah´a lepˇs´ımu rozloˇzen´ı souˇradnic v tabulce. Velice d˚ uleˇzit´a, pro velk´ y rozptyl haˇsovac´ı funkce, je volba koeficient˚ u,√jejichˇz hodnoty pro dosaˇzen´ı vynikaj´ıc´ıch v´ ysledk˚ u jsou α = π, β = e, γ = 2. Dalˇs´ım trikem t´eto funkce je nahrazen´ı klasick´eho modulo logick´ ym oper´atorem &, kter´e v´ ypoˇcet urychl´ı. Toto nahrazen´ı si m˚ uˇzeme dovolit d´ıky tomu, k ˇze velikost tabulky je vˇzdy 2 .
26
6 Proveden´ı Programovac´ım jazykem pro cel´ y projekt VRUT je C++, a proto byl pouˇzit i pro tento modul. Vytvoˇren´ y modul se nach´az´ı v adres´aˇri modules/drawingscene a jeho souˇc´ast´ı je nˇekolik tˇr´ıd, kter´e budou pozdˇeji podrobnˇe pops´any. Je vytvoˇren jako modul sc´eny – to znamen´a, ˇze m´a pˇr´ım´ı pˇr´ıstup ke spr´avci sc´en a ˇz´adn´a jin´a ˇca´st j´adra nen´ı pˇr´ıstupn´a. Modul se spouˇst´ı z konzole VRUTu pˇr´ıkazem runmodule DrawingScene. Pot´e lze pomoc´ı pˇr´ıkazu setparam DrawingScene.sceneID [sceneID] nastavit sc´enu, pro kterou bude tento modul vyuˇzit a nastaven´ım parametru setparam DrawingScene.enabled 1 pˇrepnout modul do m´odu zobrazov´an´ı obrysov´ ych hran. Po spuˇstˇen´ı se modul zaregistruje k odbˇeru o zmˇen´ach transformac´ı sc´eny, geometrie a parametr˚ u kamery. D´ale jsou po spuˇstˇen´ı modulu nebo po zmˇenˇe sc´eny postupnˇe naˇcteny vˇsechny geometrie z dan´e sc´eny a je z nich vyexportov´an seznam hran a informace o sousedn´ıch ploch´ach. Pot´e se hrany roztˇr´ıd´ı no ostr´e (skuteˇcn´e), kter´e se nemus´ı pˇri zmˇenˇe kamery pˇrepoˇc´ıtat, a na potencion´aln´ı obrysov´e hrany, ve kter´em se to opravdu obrysov´e hledaj´ı pˇri kaˇzd´e zmˇenˇe parametr˚ u kamery. Zvolen´a sc´ena se modifikuje tak, ˇze se p˚ uvodn´ı geometrie skryje a pˇrid´a se nov´a, kter´a se bude plnit pˇri kaˇzd´e zmˇenˇe parametr˚ u kamery nalezen´ ymi hranami. Tak je moˇzn´a zapnout klasick´ y zp˚ usob zobrazen´ı jen t´ım, ˇze se nov´a geometrie pro nalezen´e hrany skryje a p˚ uvodn´ı se naopak zviditeln´ı. Pˇri ukonˇcen´ı modulu se uvoln´ı vˇsechna alokovan´a pamˇet’ vytvoˇren´ ych objekt˚ u a modul se zavˇre.
6.1
Uˇ zivatelsk´ e rozhran´ı modulu
Na uˇzivatelsk´em rozhran´ı modulu se nach´azej´ı tˇri ovl´adac´ı prvky, pole pro zad´an´ı jm´ena souboru a tlaˇc´ıtko, pomoc´ı kter´eho se provede export do zvolen´eho souboru (Obr´azek 6.1).
27
Proveden´ı
Popis pouˇzit´ych tˇr´ıd
sceneID – slouˇz´ı k v´ ybˇeru sc´eny, pro kterou se bude aplikovat zobrazen´ı obrysov´ ych hran. enabled – povol´ı nebo zak´aˇze zobrazen´ı obrysov´ ych hran. showHiddenLines – povol´ı nebo zak´aˇze zobrazen´ı skryt´ ych obrysov´ ych hran. fileName – slouˇz´ı pro zad´an´ı jm´ena souboru, do kter´eho bude proveden export. export – slouˇz´ı k exportu obrysov´ ych hran vybran´e sc´eny do souboru ve form´atu PostScript.
Obr´azek 6.1: Uˇzivatelsk´e rozhran´ı modulu
6.2 6.2.1
Popis pouˇ zit´ ych tˇ r´ıd Tˇ r´ıda DrawingScene
Tato tˇr´ıda dˇed´ı z SceneModule a je vstupn´ım m´ıstem implementovan´eho modulu. Uchov´av´a informace o nataven´ı modulu, obsluhuje registrovan´e zpr´avy a obsahuje funkce pro modifikaci sc´eny a nalezen´ı vˇsech geometri´ı pro jejich n´asledn´e zpracov´an´ı. Jeho d˚ uleˇzitou souˇca´st´ı je t´eˇz obsluha GUI. D˚ uleˇzit´e funkce tˇr´ıdy: 28
Proveden´ı
Popis pouˇzit´ych tˇr´ıd
DrawingScene – konstruktor tˇr´ıdy. Jsou zde registrov´any ovl´adac´ı prvky uˇzivatelsk´eho rozhran´ı a odbˇer zpr´av o zmˇenˇe transformac´ı sc´eny, geometrie a parametr˚ u kamery. processEvent – obsluha zpr´av zaslan´ ych j´adrem. processSelectScene – tato funkce je vol´ana pˇri zmˇenˇe sc´eny, pro kterou se maj´ı obrysov´e hrany hledat. V p˚ uvodn´ı sc´enˇe skryje geometrie s hranami a zobraz´ı p˚ uvodn´ı geometrie, v novˇe vybran´e sc´enˇe skryje p˚ uvodn´ı geometrie, pokud jeˇstˇe neexistuj´ı geometrie pro hrany, jsou vytvoˇreny, a zajist´ı sestaven´ı nov´ ych seznam˚ u hran. processChangeEnable – zap´ın´a nebo vyp´ın´a zobrazen´ı obrysov´ ych hran. processExport – tato funkce zabezpeˇc´ı export vybran´e sc´eny do souboru. processShowHiddenLines – zap´ın´a a vyp´ın´a zobrazen´ı skryt´ ych hran. prepareScene – funkce slouˇz´ı k pˇripraven´ı sc´eny pro zobrazen´ı obrysov´ ych hran. Jsou zde pˇrid´any nov´e uzly a geometrie, kter´a bude pouˇzita pro zobrazen´ı viditeln´ ych a skryt´ ych hran. setDrawingScene – pˇrepne vybranou sc´enu do reˇzimu zobrazen´ı hran a zajist´ı pˇrepoˇcet hran a jejich zobrazen´ı. returnOrigScene – pˇrepne vybranou sc´enu do reˇzimu standardn´ıho zobrazen´ı. extractEdges – postupnˇe ve sc´enˇe projde vˇsechny geometrie a pro kaˇzdou vytvoˇr´ı koresponduj´ıc´ı objekt tˇr´ıdy DrawingEdges, kter´ y n´aslednˇe napln´ı hranami z dan´e geometrie. extractGeometries – postupnˇe projde vˇsechny uzly s geometriemi a pro kaˇzdou vytvoˇr´ı koresponduj´ıc´ı objekt tˇr´ıdy DrawingGeometry. extractCameras – vyhled´a vˇsechny kamery sc´eny a vybere kameru pro v´ ypoˇcet obrysov´ ych hran. clearGeometry – odstran´ı z geometrie vˇsechny body, indexy a definice. fillGeometry – funkce slouˇz´ı k naplnˇen´ı geometri´ı pro viditeln´e a neviditeln´e hrany. redraw – pˇri zmˇenˇe parametr˚ u kamery zajist´ı tato funkce v´ ypoˇcet nov´ ych obrysov´ ych hran a jejich n´asledn´e zobrazen´ı. clear – uvoln´ı modulem alokovanou pamˇet’. 29
Proveden´ı
6.2.2
Popis pouˇzit´ych tˇr´ıd
Tˇ r´ıda DrawingEdges
Tato tˇr´ıda uchov´av´a informace o bodech, norm´al´ach a hran´ach jedn´e geometrie sc´eny. Obsahuje funkce pro vloˇzen´ı jednotliv´ ych typ˚ u geometrie, pomoc´ı kter´ ych se pˇrid´avaj´ı hrany do seznamu. Dalˇs´ımi funkcemi je rozdˇelen´ı hran na skuteˇcn´e a potencion´alnˇe obrysov´e a v´ ypoˇcet zd´anliv´eho pr˚ useˇc´ık˚ u dvou hran. D˚ uleˇzit´e funkce tˇr´ıdy: DrawingEdges – konstruktor tˇr´ıdy. Slouˇz´ı k vytvoˇren´ı hashmap potˇrebn´ ych pro vkl´ad´an´ı hran. insertPolygon – export vˇsech hran z geometrie typu POLYGON. insertQuads – export vˇsech hran z geometrie typu QUADS. insertTriFun – export vˇsech hran z geometrie typu TRI_FAN. insertTriList – export vˇsech hran z geometrie typu TRI_LIST. insertTriStrip – export vˇsech hran z geometrie typu TRI_STRIP. insertLineStrip – export vˇsech hran z geometrie typu LINE_STRIP. insertLines – export vˇsech hran z geometrie typu LINES. getEdges – funkce vrac´ı ukazatel na seznam hran. getVertexMap – funkce vrac´ı pole obsahuj´ıc´ı seznam vˇsech vrchol˚ u geometrie a seznam vrchol˚ u, kter´e jsou s nimi spojeny hranou. cornerEdgeDepth – urˇc´ı viditelnost hrany vych´azej´ıc´ı z dan´eho vrcholu. addEdge – slouˇz´ı k vloˇzen´ı hrany do seznamu. Vkl´adan´a hrana je pops´ana tˇremi nebo ˇctyˇrmi indexy (podle toho, zda s n´ı soused´ı jeden nebo dva troj´ uheln´ıky). Prvn´ı dva indexy popisuj´ı body hrany a dalˇs´ı tˇret´ı body pˇrilehl´ ych troj´ uheln´ık˚ u. getVertexIndex – na vstupu t´eto funkce je index bodu z origin´aln´ı geometrie. Tato funkce dohled´a, zda stejn´ y bod jiˇz nebyl pouˇzit s jin´ ym indexem a pokud ano, vrac´ı jiˇz pouˇzity index. Tato funkce je d˚ uleˇzit´a k odstranˇen´ı vzniku faleˇsn´ ych hran.
30
Proveden´ı
Popis pouˇzit´ych tˇr´ıd
insertForTest – vloˇzen´ı hrany do seznamu, podle kter´eho bude ovˇeˇrena viditelnost hrany vych´azej´ıc´ıho z vrcholu. intersect – vypoˇcte zd´anliv´ y pr˚ useˇc´ık dvou hran a rozhodne, kter´a leˇz´ı v popˇred´ı a kter´a v pozad´ı.
6.2.3
Tˇ r´ıda DrawingGeometry
Objekty t´eto tˇr´ıdy koresponduj´ı s uzly s geometri´ı vybran´e sc´eny. Obsahuje funkce pro nalezen´ı obrysov´ ych hran a jejich n´asledn´e poskl´ad´an´ı do lomen´ ych ˇcar, ˇreˇsen´ı viditelnosti, a vykreslen´ı hran do zvolen´e geometrie. D˚ uleˇzit´e funkce tˇr´ıdy: DrawingGeometry – konstruktor tˇr´ıdy. Inicializuje tˇr´ıdn´ı promˇenn´e. drawLineStrings – funkce pˇrenese nalezen´e lomen´e ˇcary popisuj´ıc´ı obrysov´e hrany do geometri´ı slouˇz´ıc´ıch pro viditeln´e a neviditeln´e hrany, ˇc´ımˇz zajist´ı jejich vykreslen´ı. constructLineStrings – funkce zajist´ı nalezen´ı vˇsech obrysov´ ych hran modelu v z´avislosti na parametrech kamery, jejich poskl´ad´an´ı do lomen´ ych ˇcar a urˇcen´ı jejich viditelnosti. getGeometryName – vrac´ı jm´eno uzlu geometrie, pro kterou dan´ y objekt vznikl. getVertices – vrac´ı seznam vˇsech bod˚ u pouˇzit´ ych v popisu obrysov´ ych hran. getLineString – funkce vrac´ı ukazatel na seznam lomen´ ych ˇcar. prepareEdges – rozdˇelen´ı seznamu hran na skuteˇcn´e a potencion´alnˇe obrysov´e na z´akladˇe toho, zda je k hranˇe pˇrilehl´ y jeden nebo dva troj´ uheln´ıky. constructLineString – sestroj´ı lomenou ˇca´ru z obrysov´ ych hran. Lomen´a ˇc´ara je spojnice mezi body, ze kter´ ych vede jedna nebo tˇri a v´ıce hran. getSecondVertexFromEdge – funkce vrac´ı druh´ y bod hrany. clearLineString – maˇze seznam lomen´ ych ˇcar a uvoln´ı jimi alokovanou pamˇet’. 31
Proveden´ı
6.2.4
Popis pouˇzit´ych tˇr´ıd
Tˇ r´ıda PostScriptTools
Tato tˇr´ıda obsahuje funkce slouˇz´ıc´ı k sestaven´ı PostScript–ov´eho souboru ze seznamu hran, jeho z´apis na disk, a tak´e funkce pro v´ ypoˇcet spr´avn´eho um´ıstˇen´ı modelu na str´anku. D˚ uleˇzit´e funkce tˇr´ıdy: PostScriptTools – konstruktor tˇr´ıdy. Prob´ıh´a zde inicializace parametr˚ u str´anky. fileOpen – otevˇre soubor, do kter´eho bude prob´ıhat z´apis. fileClose – zavˇre otevˇren´ y soubor. setBound – funkce slouˇz´ı pro nastaven´ı mezn´ıch hodnot, kter´ ych nab´ yvaj´ı lomen´e ˇc´ary. Tato informace je pouˇzita pro v´ ypoˇcet mˇeˇr´ıtka pro vloˇzen´ı pohledu na st´anku. begin – zap´ıˇse do souboru definice pˇr´ıkaz˚ u a nastaven´ı str´anky. end – zap´ıˇse do souboru pˇr´ıkaz pro zobrazen´ı str´anky. solidLines – zap´ıˇse do souboru informaci o tom, ˇze n´asleduj´ıc´ı popis lomen´ ych ˇcar se bude t´ ykat viditeln´ ych hran. hiddenLines – zap´ıˇse do souboru informaci o tom, ˇze n´asleduj´ıc´ı popis lomen´ ych ˇcar se bude t´ ykat skryt´ ych hran. writeLineStrings – zap´ıˇse do souboru vˇsechny lomen´e ˇc´ary vyhovuj´ıc´ı dan´e podm´ınce viditelnosti. writeGeometryName – zap´ıˇse do souboru pozn´amku o n´azvu uzlu geometry, ze kter´e n´asleduj´ıc´ı popis lomen´ ych ˇcar vznikl. exportGeometry – zajist´ı vyps´an´ı pozn´amky o n´azvu uzlu geometrie a n´asledn´ y z´apis popisu lomen´ ych ˇcar do otevˇren´eho souboru. write – zap´ıˇse pˇr´ısluˇsnou informaci do souboru. calcScale – v´ ypoˇcet mˇeˇr´ıtka podle mezn´ıch hodnot lomen´ ych ˇcar pro vloˇzen´ı pohledu na st´anku.
32
Proveden´ı
6.2.5
Popis exportovan´eho souboru
Tˇ r´ıda VertexHashMap
Tuto tˇr´ıdu bylo potˇreba implementovat kv˚ uli vzniku faleˇsn´ ych hran na nˇekter´ ych modelech. Jedn´a se o haˇsovac´ı tabulku slouˇz´ıc´ı k nalezen´ı shodn´ ych bod˚ u geometrie. D˚ uleˇzit´e funkce tˇr´ıdy: VertexHashMap – konstruktor tˇr´ıdy. Jako vstupn´ı parametr m´a poˇcet bod˚ u, pro kter´e je haˇsovac´ı tabulka urˇcena. insert – funkce pro vloˇzen´ı dan´eho bodu. find – slouˇz´ı pro zjiˇstˇen´ı, zda jiˇz dan´ y bod existuje, a pokud ano, poskytne jeho index. clear – smaz´an´ı vˇsech prvk˚ u haˇsovac´ı tabulky a uvolnˇen´ı alokovan´e pamˇeti. hash – haˇsovac´ı funkce.
6.3
Popis exportovan´ eho souboru
Exportovan´ y soubor s popisem obrysov´ ych hran je ve form´atu PostScript. Tento soubor m˚ uˇzeme rozdˇelit na dvˇe ˇca´sti – na definice pˇr´ıkaz˚ u a na data s popisem exportovan´ ych hran. Definice se nach´azej´ı na zaˇca´tku souboru a jejich funkce je: /ps Velikost str´ anky – horizont´aln´ı a vertik´aln´ı rozmˇer str´anky. V definici je pouˇzit pˇr´ıkaz mm, slouˇz´ıc´ı pro pˇrevod mililitr˚ u na topologick´e body, kter´e se pouˇz´ıvaj´ı jako d´elkov´a jednotka v PostScriptu. /sl Styl obrysov´ ych hran – zde je definov´ano, jak´ y styl ˇca´ry se pouˇzije pro vykreslen´ı obrysov´ ych hran. /hl Styl skryt´ ych hran – je zde definov´ano, jak´ y styl ˇc´ary se pouˇzije pro vykreslen´ı skryt´ ych hran. /m, /l, /s, /e Pˇ r´ıkazy pro tvorbu cesty – tyto pˇr´ıkazy jsou pouˇzity v datov´e ˇca´sti pro popis exportovan´ ych hran (viz n´ıˇze).
33
Proveden´ı
Popis exportovan´eho souboru
/mm Pˇ revodn´ı pˇ r´ıkaz – pˇrevod mililitr˚ u na topologick´e body, kter´e se pouˇz´ıvaj´ı jako d´elkov´a jednotka v PostScriptu. /rs Pˇ repoˇ cet styl˚ uˇ car – pˇr´ıkaz slouˇz´ıc´ı po pˇrepoˇcet styl˚ u ˇcar na jednotn´ y form´at, aby nebyly z´avisl´e na zvolen´em mˇeˇr´ıtku. /iv Nastaven´ı pohledu – nastav´ı pohled s definovan´ ym mˇeˇr´ıtkem na specifikovan´e souˇradnice. /cv Oˇ r´ıznut´ı pohledu – oˇr´ızne pohled urˇcen´ y lev´ ym horn´ım a prav´ ym spodn´ım rohem. Za definicemi n´asleduje sada pˇr´ıkaz˚ u pro nastaven´ı str´anky (zde je vol´an pˇr´ıkaz ps pro nastaven´ı velikosti str´anky), nastaven´ı pohledu (do z´asobn´ıku je vloˇzeno mˇeˇr´ıtko a x-ov´a a y-ov´a souˇradnice, kter´a se bude kr´ yt s bodem [0, 0] exportovan´ ych dat, a pot´e je zavol´an pˇr´ıkaz iv) a oˇr´ıznut´ı pohledu (do z´asobn´ıku se uloˇz´ı x-ov´a a y-ov´a souˇradnice lev´eho horn´ıho a prav´eho spodn´ıho rohu, pot´e se zavol´a pˇr´ıkaz cv). V pˇr´ıpadˇe, ˇze exportujeme i skryt´e hrany, bude v datov´e ˇc´asti po sobˇe n´asledovat popis skryt´ ych hran a pot´e popis hran viditeln´ ych. Kaˇzd´a z tˇechto ˇc´ast´ı je uvozena pˇr´ıkazy pro styl ˇca´ry a jeho n´asledn´ ym pˇrepoˇctem (pro skryt´e hrany hl rs, pro viditeln´e hrany sl rs). Po tˇechto pˇr´ıkazech n´asleduje popis hran ve formˇe lomen´ ych ˇcar. Do z´asobn´ıku je vˇzdy uloˇzena x-ov´a a y-ov´a souˇradnice bodu n´asledov´ana jedn´ım z pˇr´ıkaz˚ u: /s Prvn´ı bod lomen´ eˇ c´ ary – pomoc´ı pˇr´ıkaz˚ u newpath a moveto zaˇcne cestu a nastav´ı poˇca´teˇcn´ı souˇradnice lomen´e ˇca´ry. /l Pr˚ ubˇ eˇ zn´ y bod lomen´ eˇ c´ ary – vykon´an´ım pˇr´ıkazu lineto pˇripoj´ı dalˇs´ı u ´seˇcku k cestˇe. /e Koneˇ cn´ y bod lomen´ eˇ c´ ary – pˇr´ıkazem lineto pˇripoj´ı k cestˇe posledn´ı u ´seˇcku a pˇr´ıkazem stroke zajist´ı vykreslen´ı aktu´aln´ı cesty. Na samotn´em konci souboru se nach´az´ı pˇr´ıkaz showpage, pomoc´ı kter´eho se pˇripraven´a str´anka vykresl´ı.
34
7 Experimenty 7.1
Rychlost zobrazen´ı n´ ahledu
ˇ Cas, kter´ y zabere pˇrepoˇcet nov´eho pohledu, je z´avisl´ı na poˇctu hran modelu. V tabulce 7.1 uv´ad´ım v´ ysledky m´eho testov´an´ı, kter´ ych bylo dosaˇzeno na pˇrec nosn´em poˇc´ıtaˇci s dvouj´adrov´ ym procesorem Intel CoreTM 2 Duo, operaˇcn´ı pamˇet´ı 4GB, grafickou kartou ATI Mobility Radeon HD 3650 a 64bitov´ ym operaˇcn´ım syst´emem. ˇ [ms] Model Poˇ cet hran Cas test.fhs 90 1 FabiaRS.fhs 3 628 5 FabiaEXT 0.05.fhs 1 240 185 330 ˇ potˇrebn´ Tabulka 7.1: Cas y k pˇrepoˇctu nov´eho pohledu Rychlost posouv´an´ı a nat´aˇcen´ı modelu vˇsak t´ımto ˇcasem nejsou nikterak omezeny, jen u modelu FabiaEXT_0.05.fhs nedojde ke korektn´ımu zobrazen´ı obrysov´ ych hran ihned po tˇechto u ´konech. Po t´e, co jsem s modulem v r´amci testov´an´ı pracoval, si mysl´ım, ˇze tato rychlost pro interaktivn´ı pr´aci s modely postaˇcuje. Pokud by vˇsak ˇcas pˇrepoˇctu nov´eho pohledu pˇrestal dostaˇcovat, popˇr´ıpadˇe by se pracovalo s jeˇstˇe sloˇzitˇejˇs´ımi modely, existuj´ı metody, jak pr´aci modulu urychlit. Nyn´ı pˇrepoˇcet hran pˇri zmˇenˇe pohledu bˇeˇz´ı pouze v jednom vl´aknˇe, a tak by bylo moˇzn´e dos´ahnout vyˇsˇs´ı rychlosti rozloˇzen´ım ˇcasu na v´ıce jader procesoru pomoc´ı bˇehu v´ ypoˇct˚ u v nˇekolika paraleln´ıch vl´aknech.
7.2
Kvalita v´ ystupu
Na modelu krychle (Obr´azek 7.1) jsou korektnˇe zobrazeny vˇsechny hrany a je zde t´eˇz korektnˇe vyˇreˇsena jejich viditelnost. K ˇreˇsen´ı viditelnosti hran konvexn´ıho tˇelesa dostaˇcuje pouze v´ ypoˇcet koeficient˚ u zakryt´ı v roz´ıch objektu. Tak´e na modelu test.fhs (Obr´azek 7.2) jsou vˇsechny nalezen´e hrany v poˇr´adku. Jejich viditelnost je spr´avnˇe vyˇreˇsena pouze v r´amci jednotliv´ ych 35
Experimenty
Kvalita v´ystupu
model˚ u krychle, ale ne v r´amci cel´e sestavy. Nyn´ı je implementov´ana ˇca´st Appelova algoritmu, kter´a zaruˇc´ı korektn´ı zobrazen´ı viditeln´ ych hran pouze v r´amci jednotliv´ ych konvexn´ıch objekt˚ u. Pro rozˇs´ıˇren´ı na nekonvexn´ı objekty a jejich sestavy by bylo potˇreba doimplementovat ˇca´st algoritmu ˇreˇs´ıc´ı pr˚ useˇc´ıky jednotliv´ ych lomen´ ych ˇcar a jejich dˇelen´ı na menˇs´ı u ´seky, ve kter´ ych je koeficient zakryt´ı konstantn´ı (viz sekce 5.5 na stranˇe 22). Na obr´azku 7.3 jsou vidˇet nalezen´e obrysov´e hrany modelu FabiaRS.fhs. I zde se zdaj´ı b´ yt vˇsechny nalezen´e hrany opravdu tˇemi obrysov´ ymi. Chyby ve viditelnosti se zde vˇsak uˇz projevuj´ı jak na u ´rovni jednotliv´ ych geometri´ı, tak v r´amci cel´e sestavy. I zde je d˚ uvodem ne´ upln´a implementace algoritmu ˇreˇs´ıc´ıho viditelnost nalezen´ ych hran. Model FabiaEXT_0.05.fhs (Obr´azek 7.4) byl nejsloˇzitˇejˇs´ım z tˇech, na kter´ ych byl modul testov´an. Obrysov´e hrany se hledaly ve v´ıce jak mili´onu vˇsech hran tohoto modelu. Probl´emy s viditelnost´ı se zde vyskytuj´ı obdobn´e jako v pˇr´ıpadˇe modelu FabiaRS.fhs. Pˇridaly se k nim vˇsak i probl´emy s nalezen´ ymi obrysov´ ymi hranami, kter´e jsou uk´az´any na detailu kliky pˇredn´ıch dveˇr´ı (Obr´azek 7.5). Jeden z probl´em˚ u je viditeln´ y na v´ ylisku v modelu dveˇr´ı, kde se zlom opticky jev´ı jako hrana, ale ve skuteˇcnosti je zde mal´ y pˇrechodov´ y r´adius, na kter´em se v definici geometrie ˇza´dn´a hrana nevyskytuje. Druh´ ym probl´emem jsou kr´atk´e hrany, kter´e proch´azej´ı napˇr´ıˇc zaoblen´ ymi hranami kliky. V tˇechto m´ıstech opticky ˇz´adn´e hrany nejsou viditeln´e, ale v definici geometry se zde vyskytuj´ı mal´e odchylky norm´al. D´ıky tˇemto odchylk´am nen´ı moˇzn´e sjednotit bod sousedn´ıch troj´ uheln´ık˚ u, a algoritmus v tomto m´ıstˇe detekuje hranu.
36
Experimenty
Kvalita v´ystupu
Obr´azek 7.1: Model krychle
37
Experimenty
Kvalita v´ystupu
Obr´azek 7.2: Model test.fhs
38
Experimenty
Kvalita v´ystupu
Obr´azek 7.3: Model FabiaRS.fhs
39
Experimenty
Kvalita v´ystupu
Obr´azek 7.4: Model FabiaEXT_0.05.fhs
40
Experimenty
Kvalita v´ystupu
Obr´azek 7.5: Detail kliky pˇredn´ıch dveˇr´ı modelu FabiaEXT_0.05.fhs
41
8 Z´avˇer C´ılem pr´ace bylo vytvoˇrit modul do aplikace VRUT, kter´ y um´ı zobrazit a vyexportovat obrysov´e hrany nahran´eho modelu. Pˇri pr´ace jsem se pot´ ykal s nevyhovuj´ıc´ı a velmi struˇcnou dokumentac´ı aplikace, a vˇetˇsinu d˚ uleˇzit´ ych informac´ı pro tvorbu nov´ ych modul˚ u a pr´aci se sc´enou a geometri´ı jsem musel dohledat pˇr´ımo ve zdrojov´ ych k´odech j´adra a jiˇz existuj´ıc´ıch modul˚ u. Vzhledem k tˇemto fakt˚ um povaˇzuji pr´aci za u ´spˇeˇsnou, i kdyˇz se mi nepodaˇrilo naimplementovat vˇsechny funkce, kter´e jsem mˇel v u ´myslu. Proto by jeˇstˇe bylo dobr´e u modulu doˇreˇsit korektn´ı v´ ypoˇcet koeficient˚ u zakryt´ı v Appelovˇe algoritmu pouˇzit´em pro ˇreˇsen´ı viditelnosti hran, omezit pˇrepoˇcet a generov´an´ı obrysov´ ych hran jen na ty geometrie, kter´e se nach´azej´ı v pohledov´em jehlanu, a umoˇznit generov´an´ı u ´pln´ ych a ˇc´asteˇcn´ ych ˇrez˚ u pomoc´ı oˇrez´av´an´ı hran pomoc´ı mnoˇziny ploch. ˇ sen´ı, kter´e bylo pouˇzito pro odstranˇen´ı v´ıcen´asobn´ Reˇ ych bod˚ u pˇri ˇreˇsen´ı probl´emu faleˇsn´ ych hran, by podle m´eho n´azoru bylo dobr´e pouˇz´ıt i v jin´ ych modulech. Pˇri naˇc´ıt´an´ı modelu by tento jednoduch´ y mechanizmus sn´ıˇzil obsazenou pamˇet’ a pˇri ukl´ad´an´ı by zase omezil velikost souboru obsahuj´ıc´ıho popis geometrie. C´ılem pr´ace bylo tak´e zobrazovat nalezen´e obrysy a to pokud moˇzno v re´aln´em ˇcase. I tohoto bodu se podaˇrilo dos´ahnout a detekce hran bˇeˇz´ı na standardn´ım HW v interaktivn´ı rychlosti (pˇrepoˇcet hran nejsloˇzitˇejˇs´ıho testovan´eho modelu trv´a zhruba 1/3 sekundy).
42
Literatura [Ado(1985)] Postscript language tutorial and cookbook. Adobe Systems Incorporated, 1985. Dostupn´e z: www-cdf.fnal.gov/offline/PostScript/BLUEBOOK.PDF. [Ado(1999)] PostScript language reference manual. Adobe Systems Incorporated, 3 edition, 1999. Dostupn´e z: http://www.adobe.com/products/postscript/pdfs/PLRM.pdf. [Appel(1967)] ARTHUR APPEL The notion of quantitative invisibility and the machine rendering of solid. New York : AMC Inc., 1967. ˇ ara(2010)] JIR ˇ ´I Z ˇ ARA, ´ ˇ ˇ JIR ˇ ´I SOCHOR, [Jiˇr´ı Z´ BEDRICH BENES, PETR FELKEL Modern´ı poˇc´ıtaˇcov´a grafika. Holandsk´a 8, 639 00 Brno : Computer Press, a.s., 2010. ISBN 80-251-0454-0. [Kevin Weiler(1977)] KEVIN WEILER, PETER ATHERTON Hidden surface removal using polygon area sorting. 1977. ˇ ´ [Tiˇsnovsk´ y(2006)] PAVEL TISNOVSK Y Seri´al Grafick´e form´aty. Internet Info, s.r.o, 2006. Dostupn´e z: http://www.root.cz/serialy/graficke-formaty/. ´ ´ ˇ Hash [Ska(2009)] VACLAV SKALA, JAN HRADEK, MARTIN KUCHAR Function for Trianglular Mesh Reconstruction. In Recent Advances in Computers, s. 233–238, Ath´eny, 2009. WSEAS Press. ISBN 978-960474-099-4. ´ ˇ [V´aclav Kyba(2010)] VACLAV KYBA, ANTON´IN M´ISEK a dalˇs´ı Dokumentace aplikace VRUT, 2010.
43
Seznam obr´ azk˚ u
2.1
Ob´alky zobrazen´e ve sc´enˇe . . . . . . . . . . . . . . . . . . . .
5
2.2
Pro jednu geometrii je pouˇzito r˚ uzn´ ych materi´al˚ u . . . . . . .
7
3.1
Urˇcen´ı, zda se jedn´a o obrysovou hranu . . . . . . . . . . . . . 11
3.2
Zmˇena koeficient zakryt´ı v pr˚ useˇc´ıc´ıch hran . . . . . . . . . . . 12
3.3
Zp˚ usob oˇrez´av´an´ı ploch . . . . . . . . . . . . . . . . . . . . . . 13
5.1
Pˇrehled interpretac´ı geometrie VRUTu . . . . . . . . . . . . . 20
5.2
Sestaven´ı lomen´ ych ˇcar . . . . . . . . . . . . . . . . . . . . . . 22
5.3
V´ ypoˇcet koeficientu zakryt´ı v roz´ıch geometrie . . . . . . . . . 23
5.4
Rozdˇelen´ı hran na element´arn´ı u ´seky s nemˇennou viditelnost´ı . 24
5.5
U lomen´e ˇcary se tak´e ukl´ad´a informace o pˇrilehl´ ych troj´ uheln´ıc´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.6
Model s faleˇsn´ ymi hranami a ten sam´ y po jejich odstranˇen´ı . . 25
6.1
Uˇzivatelsk´e rozhran´ı modulu . . . . . . . . . . . . . . . . . . . 28
7.1
Model krychle . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7.2
Model test.fhs . . . . . . . . . . . . . . . . . . . . . . . . . 38
44
´ ˚ SEZNAM OBRAZK U
´ ˚ SEZNAM OBRAZK U
7.3
Model FabiaRS.fhs . . . . . . . . . . . . . . . . . . . . . . . 39
7.4
Model FabiaEXT_0.05.fhs . . . . . . . . . . . . . . . . . . . 40
7.5
Detail kliky pˇredn´ıch dveˇr´ı modelu FabiaEXT_0.05.fhs . . . . 41
45
Seznam tabulek
7.1
ˇ potˇrebn´ Cas y k pˇrepoˇctu nov´eho pohledu . . . . . . . . . . . . 35
46
