Bakaláˇrská práce Detekce obrys˚u 3D objekt˚u pro VRUT

(1)

Z´ apadoˇcesk´ a univerzita v Plzni Fakulta aplikovan´ ych vˇed

Katedra informatiky a v´ ypoˇcetn´ı techniky

Bakal´ aˇ rsk´ a pr´ ace

Detekce obrys˚ u 3D objekt˚ u

pro VRUT

(2)

Prohl´ aˇ sen´ı

Prohlaˇsuji, ˇze jsem bakaláˇrskou práci vypracoval samostatnˇe a výhradnˇe s po- uˇzit´ım citovaných pramen˚u.

V Plzni dne 11. srpna 2011

Luk´aˇs Kurz

(3)

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.

(4)

Obsah

1 Uvod´ 1

2 VRUT 2

2.1 Z´akladn´ı charakteristiky . . . 2

2.2 J´adro . . . 2

2.3 Spr´ava a distribuce ud´alost´ı . . . 2

2.4 Graf sc´eny . . . 3

2.5 Hierarchie ob´alek . . . 4

2.6 Moduly . . . 5

2.7 Geometrie . . . 6

2.8 V´yvoj . . . 8

3 Detekce obrys˚u 9 3.1 Rastrov´a detekce obrys˚u . . . 9

3.2 Vektorov´a detekce obrys˚u . . . 10

3.3 Viditelnost obrysov´ych hran . . . 10

3.3.1 Roberts˚uv algoritmus . . . 11

3.3.2 Appel˚uv algoritmus . . . 11

3.3.3 Weiler-Atherton˚uv algoritmus . . . 12

4 PostScript 14 4.1 Z´akladn´ı charakteristiky . . . 14

4.2 Syntaxe . . . 15

4.3 Z´akladn´ı pˇrehled oper´ator˚u . . . 16

4.4 Definice promˇenn´ych a nov´ych pˇr´ıkaz˚u . . . 17

4.5 Souˇradn´y syst´em . . . 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)

5.4 Sestaven´ı lomen´ych ˇcar . . . 21

5.5 Viditelnost obrysov´ych hran . . . 22

5.6 Export obrys˚u . . . 25

5.7 Vznik faleˇsn´ych hran . . . 25

6 Proveden´ı 27 6.1 Uˇzivatelsk´e rozhran´ı modulu . . . 27

6.2 Popis pouˇzit´ych tˇr´ıd . . . 28

6.2.1 Tˇr´ıda DrawingScene . . . 28

6.2.2 Tˇr´ıda DrawingEdges . . . 30

6.2.3 Tˇr´ıda DrawingGeometry . . . 31

6.2.4 Tˇr´ıda PostScriptTools . . . 32

6.2.5 Tˇr´ıda VertexHashMap . . . 33

6.3 Popis exportovan´eho souboru . . . 33

7 Experimenty 35 7.1 Rychlost zobrazen´ı n´ahledu . . . 35

7.2 Kvalita v´ystupu . . . 35

8 Z´avˇer 42

(6)

1 Uvod ^´

C´ılem této práce je do jiˇz exituj´ıc´ı aplikace VRUT (viz [Václav Kyba(2010)]) vytvoˇrené ve spolupráci ˇSKODA AUTO a.s. a ˇCVUT vytvoˇrit modul, který um´ı u nahraného modelu detekovat obrysy, tyto obrysy zobrazovat (pokud moˇzno v reálném ˇcase), a umoˇznit export nalezených hran do PostScript (výsledkem bude 2D vektorový obrázek).

Nejprve ˇctenáˇre seznám´ım s aplikac´ı VRUT, aby z´ıskal pˇredstavu o jej´ı struktuˇre, moˇznosti rozˇs´ıˇren´ı jej´ıch vlastnost´ı pomoc´ı nových modul˚u a zp˚u- sobu komunikace modul˚u pomoc´ı zpráv, a pˇribl´ıˇz´ım moˇznosti programova- c´ıho jazyka PostScript (viz [Ado(1999)] a [Ado(1985)]), který je pouˇzit pro výsledný export nalezených hran.

Dále jsou zde popsány nˇekteré moˇznosti detekce obrys˚u, zp˚usob implementace nového modulu pro aplikaci VRUT a popis jeho d˚uleˇzitých ˇcást´ı, a popis výsledného souboru v jazyce PostScript.

(7)

2 VRUT

2.1 Z´ akladn´ı charakteristiky

VRUT (Virtual Reality Universal Toolkit) je aplikace pro vizualizaci a editaci 3D dat, vytváˇrená ve spolupráci ˇSKODA AUTO a.s. a ˇCVUT. Je urˇcen k zobrazen´ı grafických dat s podporou modul˚u, umoˇzˇnuj´ıc´ıch rozˇs´ıˇrit funkci hlavn´ı aplikace.

Aplikace se dá rozdˇelit na dvˇe ˇcásti – hlavn´ı aplikace neboli jádro, které je samo o sobˇe z uˇzivatelského hlediska nepouˇzitelné, a základn´ı bal´ıˇcek modul˚u, které se staraj´ı napˇr´ıklad o zobrazen´ı scény ˇci jej´ı import a export.

2.2 J´ adro

Jádro slouˇz´ı pro správu modul˚u, správu grafických dat, poskytuje pomocné prvky pro správný bˇeh aplikace a také zajiˇst’uje správu události slouˇz´ıc´ı jako komunikaˇcn´ı kanál mezi jednotlivými ˇcástmi aplikace a moduly.

Správce modulu spuˇstˇen´ı modulu a jeho propojen´ı s jádrem. Moduly jsou aktivovány jen na ˇzádost v pˇr´ıpadˇe potˇreby. Správce modul˚u obsahuje d´ılˇc´ı ˇ

cásti, z nichˇz kaˇzdá je urˇcena pro obsluhu podskupiny modul˚u stejného nebo kompatibiln´ıho typu. Nˇekteré moduly, u nichˇz je vˇetˇs´ı provázanost s jádrem, vyˇzaduj´ı zvláˇstn´ı zacházen´ı, proto typy správc˚u do znaˇcné m´ıry odpov´ıdaj´ı typ˚um podporovaných modul˚u.

2.3 Spr´ ava a distribuce ud´ alost´ı

Aplikace je rozdˇelena na objekty, pˇredevˇs´ım jednotlivé moduly, které jsou na sobˇe zpravidla nezávislé. Tyto ˇcásti vˇsak spolu potˇrebuj´ı komunikovat.

Zvolený zp˚usob komunikace je postaven nezas´ılán´ı událost´ı. Výhodou tohoto zp˚usobu je, ˇze nen´ı potˇreba znát rozhran´ı jednotlivých objekt˚u, ale staˇc´ı, aby kaˇzdý objekt umˇel pˇrijmout a zpracovat událost. Nevýhodou vˇsak je ob- t´ıˇzná synchronizace, protoˇze zas´ılán´ı událost´ı je pouze jednosmˇerná operace.

(8)

VRUT Graf sc´eny

Synchronizace se ˇreˇs´ı tak, ˇze zaslaná událost vyvolá odezvu v podobˇe jiné události, na kterou objekty poˇckaj´ı v blokuj´ıc´ım módu.

Události jsou zas´ılány centráln´ımu správci událost´ı, který se nacház´ı v já- dru, a ten je poté distribuuje pˇr´ısluˇsným objekt˚um. Kaˇzdý z objekt˚u m˚uˇze pˇrij´ımat libovolný typ událost´ı, staˇc´ı pouze, aby se u správce událost´ı zare- gistroval k odbˇeru daného typu událost´ı. Kaˇzdý novˇe vytvoˇrený modul tam m˚uˇze ihned reagovat na stávaj´ıc´ı události.

2.4 Graf sc´ eny

Graf scény je hlavn´ı úloˇziˇstˇe grafických dat. Protoˇze se jedná o ˇcást, ke které je potˇreba pˇristupovat ˇcasto a z r˚uzných m´ıst, je um´ıstˇen pˇr´ımo v jádˇre a nen´ı ho moˇzné nahradit extern´ım modulem. Jeho datové struktury jsou jednoznaˇcnˇe urˇcené a jsou spoleˇcné pro vˇsechny moduly, které s n´ım pracuj´ı.

Základn´ım prvkem grafu scény je uzel. M˚uˇze obsahovat pˇr´ımo grafická data a m˚uˇze m´ıt libovolný poˇcet potomk˚u. Kaˇzdý uzel má téˇz definovanou transformaˇcn´ı matici, která definuje um´ıstˇen´ı tohoto uzle a jeho potomk˚u jako logického celku v lokáln´ım mˇeˇr´ıtku. V globáln´ım mˇeˇr´ıtku lze z´ıskat vynásoben´ım transformaˇcn´ıch matic od koˇrene stromu po daný uzel. Tato transformaˇcn´ı matice pro globáln´ı mˇeˇr´ıtko je vˇsak automaticky pro kaˇzdý uzel pˇrepoˇc´ıtávána, protoˇze se jedná o údaj, se kterým se ˇcasto pracuje.

Kaˇzdá operace nad grafem scény vyvolá událost, která je zaslána správci událost´ı. Modul ˇci jiný zaregistrovaný pˇr´ıjemce m˚uˇze m´ıt tedy pˇrehled o tom, co se ve vybrané scénˇe odehrává. Je umoˇznˇena i opaˇcná komunikace, tedy pokud se správci událost´ı odeˇsle nˇejaká událost pro operaci nad scénou, je tato událost pˇredána a provedena skrze rozhran´ı scény.

Uzle grafu sc´eny se podle funkˇcnosti dˇel´ı na nˇekolik typ˚u. Mezi uzly nen´ı ˇ

zádná závislost na typu, je moˇzné kombinovat libovolné typy na pozici rodiˇce ˇ

ci potomka. Typu uzl˚u jsou:

Z´akladn´ı uzel – SceneNode, ASSEMBLY

Pˇredstavuje logický prvek ve scénˇe. Je výchoz´ım typem, ze kterého vycház´ı vˇsechny ostatn´ı uzly.

Koˇrenov´y uzel – SceneNode, ROOT

(9)

VRUT Hierarchie ob´alek

Jiné oznaˇcen´ı pro základn´ı uzel, který je koˇrenovým uzlem scény.

Kamera – CameraNode, CAMERA

Uzel reprezentuj´ıc´ı kameru. Pˇridává automaticky aktualizovanou pro- jekˇcn´ı matici a informace o pohledovém jehlanu vˇcetnˇe obálky v podobˇe koule.

Uzel s geometri´ı – GeometryNode, GEOMETRY

Pˇridává informace o geometrii a materiálu. Geometrie je popsána pri- mitivy, ze kterých se skládá výsledný objekt, a jejich vlastnost´ı. Kaˇzdá geometrie zahrnuje kromˇe grafických dat i obálku v podobˇe AABB v lo- káln´ım mˇeˇr´ıtku.

Uzel se svˇetlem – LightNode, LIGHT Pˇredstavuje zdroj svˇetla.

Uroveˇ´ n detail˚u – LODNode, LOD

Speciáln´ı logický celek, který umoˇzˇnuje uchovat r˚uznou kvalitu a sloˇzi- tost geometrie, spolu s informac´ı pˇri jaké vzdálenosti kamery od obálky uzlu se daná geometrie pˇrepne. Vˇzdy by mˇel být zobrazen pouze jeden potomek.

Pˇrep´ınaˇc – SwitchNode, SWITCH

Funguje jako pˇrep´ınaˇc mezi jednotlivými potomky. M˚uˇzou být téˇz ak- tivovány vˇsechny nebo ˇzádný.

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álek je implementována pˇr´ımo v jádˇre. Slouˇz´ı pˇredevˇs´ım k ze- fektivnˇen´ı operac´ı nad scénou, jako jsou oˇrezáván´ı pohledovým jehlanem, detekce koliz´ı, ˇci testy pˇri vrhán´ı paprsk˚u.

Hierarchie obálek je strom, který representuje rozdˇelen´ı scény na menˇs´ı celky. Uzly stromu jsou pouze logickým celkem ve scénˇe, list pˇredstavuje

(10)

VRUT Moduly

Obrázek 2.1: Obálky zobrazené ve scénˇe

jeden uzel grafu scény s geometrickými daty. Kaˇzdý uzel representuje ˇcást scény, která je vymezena urˇcitým tˇelesem – obálkou. Tvar obálek je kvádr, zarovnaný s osami, tzv. AABB (Axis Aligned Bounding Box). Kaˇzdá obálka potomka je plnˇe obsaˇzena v obálce rodiˇce, takˇze koˇrenový uzel pˇredstavuje AABB celé scény.

Ke kaˇzdé scénˇe je pˇriˇrazena pouze jedna hierarchie obálek a závis´ı vý- hradnˇe na prostorové hierarchii geometrie ve scénˇe, nikoliv na transformaˇcn´ı hierarchii scény. Na obrázku 2.1 jsou vidˇet zobrazené obálky modelu auta pˇr´ımo ve scénˇe.

2.6 Moduly

Moduly umoˇzˇnuj´ı aplikaci rozˇsiˇrovat o nové funkce. Moduly jsou aktivovány a spravovány pˇr´ısluˇsným správcem modul˚u. Pro jednotlivé moduly lze ak-

(11)

VRUT Geometrie

tivovat libovolné mnoˇzstv´ı instanc´ı a kaˇzdé je pˇriˇrazeno vlastn´ı vlákno, ve kterém prob´ıhá ˇcinnost modulu.

Jak jiˇz bylo popsáno, komunikaci mezi jednotlivými moduly se zajiˇst’uje pomoc´ı událost´ı, a vˇsechny moduly bez rozd´ılu mohou pouˇz´ıvat systém udá- lost´ı jako pˇr´ıjemci i odes´ılatelé. Komunikace mezi moduly tak vˇzdy prob´ıhá skrze jádro.

Moduly jsou podle ˇcinnosti, kterou vykonávaj´ı, rozdˇeleny do skupin. Typy se mohou liˇsit v úrovni povoleného pˇr´ıstupu k jádru 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ávisl´ı na jádˇre. Jediné spojen´ı s jádrem je pomoc´ı událost´ı.

Modul sc´eny – SceneModule

Má pˇr´ımý pˇr´ıstup ke správci scén, ˇzádná jiná ˇcást jádra nen´ı pˇr´ıstupná.

Modul pro import a export – IOModule

Vycház´ı z modulu scény. Na stranˇe jádra vyˇzaduje spolupráci pˇri výbˇeru správného modulu pro poˇzadovaný formát dat.

Zobrazovac´ı modul – RenderModule

Rozˇsiˇruje modul scény. Vyˇzaduje vysokou m´ıru propojenosti ze strany jádra, naopak ze strany modulu k ˇzádnému rozˇs´ıˇren´ı pˇr´ıstupu k jádru nedocház´ı.

Manipul´ator – ManipulatorModule

Zpracovává speciáln´ı události ze vstupn´ıch zaˇr´ızen´ı.

Manipul´ator kamery – CameraModule

Na rozd´ıl od manipulátoru je v´ıce specializován na ovládán´ı kamery.

2.7 Geometrie

Geometrie je souˇcást´ı scény. Odkazována m˚uˇze být pouze uzlem s geometri´ı a nen´ı nijak závislá na materiálu, takˇze jedna geometrie muˇze být pouˇzita v´ıce uzly a v kaˇzdém z nich lze poˇz´ıt jiný materiál. Na obrázku 2.2 je model krychle definovaný jednou geometri´ı ve scénˇe odkazován pˇetkrát, liˇs´ı se vˇsak v pouˇzitém materiálu.

(12)

VRUT Geometrie

Obrázek 2.2: Pro jednu geometrii je pouˇzito r˚uzných materiál˚u

Geometrie vyuˇz´ıvá dˇediˇcnost pro moˇznost definice v´ıce typ˚u geometri´ı, vˇsechny typy maj´ı svou obálku AABB a umoˇzˇnuj´ı pˇrevod geometrických dat do podoby seznamu trojúheln´ıku.

Zat´ım jediným implementovaným typem geometrie je trojúheln´ıková representace, která je definována seznamem vrchol˚u a index˚u do pole vrchol˚u, pˇr´ıpadnˇe pak normál a souˇradnic pro textury. Indexovanou trojúheln´ıkovou geometrii lze interpretovat jako TRI LIST, TRI FAN, TRI STRIP, POLY- GON, LINES, LINE STRIP, POINTS nebo QUADS. Geometrie umoˇzˇnuje libovolnou kombinaci podporované interpretace primitiv v rámci jedné geometrie.

(13)

VRUT V´yvoj

2.8 V´ yvoj

Systém VRUT se stále jeˇstˇe vyv´ıj´ı. V souˇcasné dobˇe obsahuje velké mnoˇzstv´ı modul˚u rozˇsiˇruj´ıc´ıch jeho moˇznosti. Stále vˇsak existuje funkˇcnost, která se ve stávaj´ıc´ıch modulech nenacház´ı, a proto jsou potˇreba nové moduly doimplementovat. Jedn´ım z nich je právˇe modul pro detekci kontur a jejich následný export.

(14)

3 Detekce obrys˚ u

Obrysy se v poˇc´ıtaˇcové grafice pouˇz´ıvaj´ı jako jedna z metod nefotorealistic- kého zobrazen´ı (NPR) a metody pro jejich detekce lze na nejhrubˇejˇs´ı úrovni rozdˇelit na rastrové a vektorové.

3.1 Rastrov´ a detekce obrys˚ u

Pro detekci obrys˚u byla vyvinuta celá ˇrada algoritm˚u (viz [Jiˇr´ı ˇZára(2010)]) a pro pˇredstavu cituji tˇri metody uvedené v tomto zdroji.

NPR s pomoc´ı prahov´an´ı

1. Um´ısti bodov´y zdroj svˇetla L do polohy kamery.

2. Nastav materiál vˇsech tˇeles na b´ılý, ˇcistˇe difúzn´ı.

3. Zobraz sc´enu osvˇetlenou pouze pomoc´ı zdroje L.

4. Pˇreved’ vykreslený obraz prahován´ım na ˇcernob´ılý.

NPR s pomoc´ı pˇrivrácených a odvrácených ploch 1. Rozdˇel plochy scény na pˇrivrácené a odvrácené.

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ý, a z tohoto d˚uvodu jsem je zavrhl. Imple- mentace by znamenala rasterizaci modelu, který je popsán trojúheln´ıkovou s´ıt´ı, a jeho následnou vektorizaci, aby bylo moˇzné výsledek exportovat jako vektorový obrázek.

(15)

Detekce obrys˚u Vektorov´a detekce obrys˚u

3.2 Vektorov´ a detekce obrys˚ u

Vektorový pˇr´ıstup detekce obrys˚u spoˇc´ıvá v omezen´ı mnoˇziny vˇsech hran modelu pouze na ty, které splˇnuj´ı podm´ınky obrysových hran. Nejdˇr´ıve je nutné z trojúheln´ıkové representace vytvoˇrit seznam hran, ke kterým se uloˇz´ı téˇz informace o prvc´ıch, které s n´ı soused´ı (tzv. okˇr´ıdlená hrana). Následnˇe mohou být hrany rozdˇeleny do tˇr´ı skupin:

Ostré (skuteˇcné) hrany – tvoˇr´ı hranici ploch. S touto hranou soused´ı pouze jeden trojúheln´ık, nebo dva trojúheln´ıky, které vˇsak na této hranˇe maj´ı odliˇsné normálové vektory. Tyto hrany se nemus´ı pˇri zmˇenˇe kamery pˇrepoˇc´ıtávat a jsou vˇzdy oznaˇceny jako obrysové.

Potencionáln´ı obrysové hrany – hrana, která by mohla být obrysovou hranou. Obrysová hrana vznikne mezi pˇrivráceným a odvráceným troj-

´

uheln´ı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é hrany – hrana mezi trojúheln´ıky, které leˇz´ı pˇribliˇznˇe v jedné ro- vinˇe. V této skupinˇe hran se obrysové hrany nenacház´ı.

Po tomto rozdˇelen´ı mus´ı být ve skupinˇe potencionáln´ıch obrysových hran nalezeny ty, se kterými soused´ı jeden pˇrivrácený a jeden odvrácený troj-

´

uheln´ık. Urˇcen´ı toho, zda je trojúheln´ık pˇrivrácený ˇci odvrácený vˇsak je, v pˇr´ıpadˇe, ˇze nen´ı dodrˇzeno poˇrad´ı vrchol˚u, nemoˇzné.

Pokud vˇsak pˇrevedeme vrcholy pomoc´ı zobrazovac´ı matice do 2D, m˚u- ˇ

zeme obrysovou hranu urˇcit na základˇe toho, zda tˇret´ı vrcholy (ty, které nejsou souˇcást´ı hrany) pˇrilehlých trojúheln´ık˚u leˇz´ı ˇci neleˇz´ı ve stejné poloro- vinˇe urˇcené dvˇema vrcholy hrany - pokud ve stejné polorovinˇe leˇz´ı, je tato hrana obrysová (Obrázek 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ých je vˇsak problém sloˇzitˇejˇs´ı a mus´ı se pouˇz´ıt nˇekterý z li- niových algoritm˚u viditelnosti. Jako pˇr´ıklad zde uvedu tˇri algoritmy slouˇz´ıc´ı k urˇcen´ı viditelnosti hran (viz [Jiˇr´ı ˇZára(2010)]).

(16)

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é viditelnosti ve scénˇe sloˇzené 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é hrana zakryta jen ˇ

cásteˇcnˇe, rozdˇel´ı se hrana na zakrytou a nezakrytou ˇcást a kaˇzdá nezakrytá ˇ

cást se stává novou hranou, kterou je tˇreba otestovat.

Roberts˚uv algoritmus se stal základem mnoha dalˇs´ıch metod, které se liˇs´ı napˇr´ıklad seˇrazen´ım hran, pouˇzit´ım urychlovac´ıch test˚u pˇr´ı hledán´ı zákryt˚u, apod. Vˇetˇsina úprav pˇritom zachovává hlavn´ı myˇslenku, kterou je rozdˇelen´ı potencionálnˇe viditelných hran na elementárn´ı ú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á obrysových hran, nebot’ pouze ty indikuj´ı pˇr´ıpadnou zmˇenu viditelnosti.

Velkou nevýhodou tohoto algoritmu je, ˇze zkoumán´ı zákrytu potenci-

´

alnˇe zakrytých elementárn´ıch úsek˚u s nekonvexn´ımi mnohostˇeny je pomˇernˇe zdlouhavé.

3.3.2 Appel˚ uv algoritmus

Appel˚uv algoritmus je zaloˇzen na testován´ı potencionálnˇe viditelných hran v˚uˇci hranám obrysovým a hledaj´ı se jejich zdánlivé 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

(17)

0 1 2 1

1 0 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ázek 3.2). Úseky, ve kterých je koeficient zakryt´ı roven 0, jsou viditelné.

Nejprve se mus´ı spoˇc´ıtat koeficient zakryt´ı v poˇcáteˇcn´ım vrcholu, a to urˇcen´ım poˇctu polygon˚u, které ho zakrývaj´ı. Tyto hodnoty se pak dále nesou po hranách vycházej´ıc´ıch z tohoto vrcholu a koeficient zakryt´ı se mˇen´ı, jen pokud hrana prot´ıná hranu obrysovou a vstupuje za n´ı.

₁

I

₀

I

₁

Obrázek 3.3: Zp˚usob oˇrezáván´ı ploch

Pr˚useˇc´ıky obou ploch jsou body I₀, I₁, I₃. Algoritmus pracuje se dvˇema se- znamy – vrcholy prvn´ı a druhé plochy. Pr˚useˇc´ıky se zaˇrad´ı mezi vrcholy prvn´ı a druhé 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ého 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 prv- n´ıho seznamu a postup opakujeme tak dlouho, dokud nenaraz´ıme na prvn´ı pr˚useˇc´ık. Vˇsechny proˇslé vrcholy a pr˚useˇc´ıky jsou vrcholy oˇrezané plochy.

Tento algoritmus je pˇr´ıkladem postupu, ˇreˇs´ıc´ıho viditelnost ploch. Plochy nebo jejich oˇrezané ˇcásti, které byly oznaˇceny jako viditelné, lze dále vybarvit.

(19)

4 PostScript

Jedn´ım z c´ıl˚u této práce bylo umoˇznit export nalezených hran do formátu PostScript, a proto se v této kapitole seznám´ıme s t´ımto formátem. Pouˇzité informace jsou ˇcerpány z [Ado(1999)], [Ado(1985)] a [Tiˇsnovský(2006)].

4.1 Z´ akladn´ı charakteristiky

PostScript, který byl vyvinut firmou Adobe v roce 1985, je programovac´ı jazyk, souˇz´ıc´ı k popisu stránky, která se má vykreslit na tiskárnˇe, obrazovce poˇc´ıtaˇce, ˇci jiném zobrazovac´ım zaˇr´ızen´ı.

K zobrazen´ı na monitoru je zapotˇreb´ı vhodný prohl´ıˇzeˇc, napˇr´ıklad volnˇe ˇsiˇritelný program GhostView spolu s Ghostscriptem. Tisk m˚uˇze prob´ıhat pˇr´ımo na postscriptové tiskárnˇe.

Mezi moˇznosti popisu stránky patˇr´ı operátory pro kreslen´ı pˇr´ımek, ob- louk˚u, obdéln´ık˚u a kubických kˇrivek, nastaven´ı vzhledu obrysových ˇcar a vý- plnˇe, nebo nastaven´ı oˇrezové cesty. Barvy mohou být nastaveny v´ıce zp˚u- soby – stupnˇe ˇsedi, RGB, CMYK a CIE, a téˇz je moˇzné m´ısto barvy pouˇz´ıt vzory nebo st´ınován´ı. Text je také povaˇzován za grafické tvary, takˇze s n´ım lze pracovat pomoc´ı grafických operátor˚u. Rastrová grafika je pˇr´ımo vloˇzena do popisu stránky a existuje ˇrada zp˚usob˚u, jak reprodukovat obrázky na výstupn´ım zaˇr´ızen´ı. PostScript téˇz podporuje vˇsechny kombinace lineárn´ıch transformac´ı, jako jsou posunu, zmˇeny velikosti, otoˇcen´ı, zrcadlen´ı a zkosen´ı.

Transformace se aplikuj´ı na vˇsechny prvky stránky, vˇcetnˇe textu, grafických tvar˚u a rastrové grafiky.

PostScript pouˇz´ıvá k popsán´ı grafické informace programovac´ı jazyk, je- hoˇz instrukce se zaznamenávaj´ı v postfixové notaci. To znamená, ˇze nejdˇr´ıve mus´ı být zadány operandy a potom teprve operátor. Interpretace se provád´ı pomoc´ı zasobn´ıku.

(20)

PostScript Syntaxe

4.2 Syntaxe

Poststriptov´y soubor je soubor textov´y, proto leze k jeho vytvoˇren´ı pou- ˇ

z´ıt textový editor. Jednotlivé syntaktické konstrukce jsou oddˇeleny

”b´ıl´ymi“

znaky, které jsou NUL,TAB, LF, FF, CR a SP. Je tedy jedno, zda se jednotlivé hodnoty ˇci operátory p´ıˇs´ı na nové ˇrádky, nebo se k jejich oddˇelen´ı pouˇzije jiný

”b´ıl´y“ znak, napˇr´ıklad mezera.

Dalˇs´ımi speciáln´ımi znaky jsou(,),<,>,[,],{,},/, a%, které slouˇz´ı pro oddˇelen´ı text˚u, tˇel procedur, jmen objekt˚u a komentáˇr˚u. Komentáˇre zaˇc´ınaj´ı znakem % a konˇc´ı znakem nové ˇrádky.

C´ısla lze zad´ˇ avat n´asleduj´ıc´ımi zp˚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

• C´ısla pˇri urˇˇ cit´em z´akladu, napˇr´ıklad:

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ázvy objekt˚u se zavádˇej´ı pomoc´ı znaku /, za kterým následuje zvolené jméno. Lom´ıtko nen´ı souˇcást´ı jména.

Prvky pole se zad´avaj´ı mezi znaky [ a ]. Konstrukce pole tedy m˚uˇze vypadat takto:

[ 123 /abc (xyz) ]

Tˇela procedur se zadávaj´ı pomoc´ı spustitelného pole. Jeho prvky se za- dávaj´ı mezi znaky { a}, napˇr´ıklad takto:

(21)

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á odmocnina hodnoty Operátory pro práci se zásobn´ıkem

pop – zahod´ı vrchn´ı hodnotu dup – duplikuje vrchn´ı hodnotu clear – zahod´ı cel´y z´asobn´ı

Operátory pro nastaven´ı souˇradného systému 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´ı ´useˇ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

(22)

PostScript Definice promˇenn´ych a nov´ych pˇr´ıkaz˚u

setrgbcolor – nastaven´ı barevný prostor na RGB a nastav´ı jednotlivé barevné sloˇzky

stroke – vykreslen´ı ˇcáry po aktuáln´ı cestˇe Výstupn´ı oprátory

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ých a nových pˇr´ıkaz˚u se pouˇz´ıvá pˇr´ıkaz def, který ke zvolenému jménu pˇriˇrad´ı hodnotu. Pokud je touto hodnotou seznam pˇr´ıkaz˚u, stává se takovéto jméno novým pˇr´ıkazem. Seznam pˇr´ıkaz˚u se zapisuje do sloˇzených závorek. Pro vykreslen´ı pˇr´ımky mezi zadanými 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á PostScript lineárn´ı transformace. Pro zadáván´ı souˇradnic, kterými se ˇr´ıd´ı vykreslován´ı, se pouˇz´ıvá souˇradný systém nezávislý na zobrazovac´ım zaˇr´ızen´ı. Základn´ı dél- kovou jednotkou je jeden topologický bod, jehoˇz délka se rovná 1/72 palce.

Proto se tˇesnˇe pˇred rastrován´ım provád´ı pˇrevod tˇechto souˇradnic do souˇrad- ného systému daného zobrazovac´ıho zaˇr´ızen´ı.

(23)

PostScript Souˇradn´y syst´em

Pˇri inicializaci nové stránky je nastaven poˇcátek souˇradného systému do levého doln´ıho rohu. Ne vˇzdy takovéto nastaven´ı vyhovuje, je vˇsak moˇzné nastavit transformaˇcn´ı matici a takto definovat uˇzivatelský prostor.

Nastaven´ı transformaˇcn´ı matice pro poˇcátek uˇzivatelského prostoru na stˇred stránky a délkových jednotek na milimetr vypadá napˇr´ıklad takto:

595 2 div 842 2 div translate 72 25.4 div dup scale

(24)

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ýsledkem exportu obrys˚u má byt vektorový obrázek. V pˇr´ıpadˇe poˇzit´ı nˇekteré z rastrové metody by muselo nejdˇr´ıve doj´ıt k rasterizaci – model je popsán trojúheln´ıkovou s´ıt´ı, a poté k pˇreveden´ı zpátky na vektory, které 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é a potencionálnˇe obrysové 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áci s reálnými daty se vˇsak vyskytl jeˇstˇe jeden, a to vyˇreˇsit vznik faleˇsných hran zp˚usobený v´ıcenásobným výskytem 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 po- stupném procházen´ı indexového pole zaˇrazovat hrany do seznamu na základˇe schémat na obrázku 5.1.

U interpretac´ı LINES a LINE STRIP mohou vznikat rovnou skuteˇcné hrany, POINTS se m˚uˇze ze vkládán´ı hran vynechat.

(25)

N´avrh Nalezen´ı skuteˇcn´ych hran

V0 V1

V2

V3

V4

V5

POINTS TRI_LIST

V0 V1

V2

V3

V4

V5

V0 V1

V2

V3

V4

V5

TRI_FAN

V0

V1

V2

V3

V4

TRI_STRIP V5

V0 V1

V2

V3

V4

V5

POLYGON

V0 V1

V2

V3

V4

V5

LINES

V0 V1

V2

V3

V4

V5

LINE_STRIP

V0 V1

V2

V3

QUADS

Obr´azek 5.1: Pˇrehled interpretac´ı geometrie VRUTu

5.2 Nalezen´ı skuteˇ cn´ ych hran

Nalezen´ı skuteˇcných hran je zaloˇzeno na jednoduchém principu rozdˇelen´ı seznamu vˇsech hran do dvou na základˇe toho, zda je souˇcást´ı jednoho nebo dvou trojúheln´ık˚u. Pokud je hrana souˇcást´ı jednoho trojúheln´ıku, nacház´ı se tak na okraji plochy a je to tedy skuteˇcná hrana, která se bude vykreslo- vat vˇzdy a nezávisle na parametrech kamery. Do seznamu skuteˇcných hran jsou téˇz zaˇrazeny vˇsechny hrany, které jsou souˇcást´ı v´ıce neˇz dvou trojúhel- n´ık˚u. Pokud je sd´ılena dvˇema trojúheln´ıky, pak je tˇreba provést dalˇs´ı testy, aby se rozhodla o jej´ım vykreslen´ı, a je j´ı tedy potˇreba zaˇradit do seznamu potencionálnˇe obrysových hran, jejichˇz zobrazen´ı je závislé na parametrech kamery.

5.3 Nalezen´ı obrysov´ ych hran

Po rozdˇelen´ı seznamu vˇsech hran na skuteˇcné a potencionálnˇe obrysové jsou hrany z prvnˇe jmenovaného z nich zobrazovány vˇzdy. Problém nastává v pˇr´ı- padˇe druhého seznamu, ve kterém se mus´ı hrany, které se budou zobrazovat,

(26)

N´avrh Sestaven´ı lomen´ych ˇcar

nal´ezt v z´avislosti na parametrech kamery.

Vˇsechny body se nejdˇr´ıve pomoc´ı pohledové matice pˇrevedou do souˇrad- nic, které jsou pouˇzity pˇri zobrazen´ı modelu, a poté se pro kaˇzdou hranu ze seznamu potencionálnˇe obrysových ovˇeˇruje, zda jej´ı tˇret´ı a ˇctvrtý vrchol leˇz´ı ve stejné polorovinˇe definované pˇr´ımkou urˇcenou jej´ımi prvn´ımi dvˇema vrcholy (Obrázek 3.1). Pokud ve stejné polorovinˇe leˇz´ı, je nastaven pˇr´ıznak, který urˇc´ı, ˇze pˇri vykreslen´ı bude tato hrana zobrazena.

5.4 Sestaven´ı lomen´ ych ˇ car

K sestaven´ı lomených ˇcar z jednotlivých hran jsem se rozhodl proto, aby se následnˇe lépe ˇreˇsila viditelnost hran, i z hlediska velikosti výsledného expor- tovaného souboru (nemus´ı se neustále pˇresouvat pozice pera).

Nejdˇr´ıve si ke kaˇzdému vrcholu vytvoˇr´ım seznam hran, které jsou k nˇemu navázány. Poté se postupnˇe procházej´ı vrcholy, ze kterých vede jedna nebo tˇri a v´ıce hran.

Tyto vrcholy jsou urˇceny jako poˇcátek lomené ˇcáry a dále se postupuje ve smˇeru jeˇstˇe nepouˇzité hrany (proˇslé hrany se oznaˇc´ı) tak dlouho, dokud je poˇcet hran navázaných k vrcholu roven dvˇema. Takto se postupnˇe naleznou vˇsechny acyklické lomené ˇcáry.

Pokud zbudou nˇekteré vrcholy se dvˇema navázanými neoznaˇcenými hranami, jsou urˇceny jako poˇcátek lomené ˇcáry a dále se postupuje ve smˇeru jeˇstˇe nepouˇzitý hrany tak dlouho, dokud nen´ı dosaˇzeno poˇcátku lomené ˇcáry.

T´ımto zp˚usobem jsou nalezeny vˇsechny cyklické lomené ˇcáry.

Tento mechanizmus je naznaˇcen na obrázku 5.2. Vrcholy, ze kterých vy- cház´ı jedna nebo tˇri a v´ıce hran, jsou znázornˇeny ˇcernými punt´ıky, a ty, ze kterých vycházej´ı pouze hrany dvˇe, jsou oznaˇceny punt´ıky b´ılými. Úseˇcky mezi nimi znázorˇnuj´ı nalezené obrysové hrany a ˇsipky ukazuj´ı postupné vy- tváˇren´ı lomených ˇcar. Punt´ık s kˇr´ıˇzkem znázorˇnuje zbylý vrchol, ze kterého vycház´ı pouze dvˇe hrany, který je pouˇzit jako zaˇcátek dalˇs´ı lomené ˇcáry.

(27)

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 ´uvahu Roberts˚uv, Appel˚uv nebo Weiler-Atherton˚uv algoritmus.

Roberts˚uv má tu nevýhodu, ˇze zkoumán´ı zákrytu potencionálnˇe zakry- tých úsek˚u hran s nekonvexn´ımi mnohostˇeny je zdlouhavé. Model, který jsem mˇel k dispozici, byl sloˇzen z v´ıce neˇz miliónu trojúheln´ık˚u, a proto sem se tento algoritmus rozhodl zavrhnout, aby bylo moˇzno obrysy zobrazovat v reál- ném ˇcase. Weiler-Atherton˚uv algoritmus [Kevin Weiler(1977)] ˇreˇs´ı viditelnost ploch. Tyto plochy by nejdˇr´ıve bylo nutné ze seznamu lomených ˇcar sestrojit, a aˇz potom tento algoritmus aplikovat. Rozhodl jsem se proto vyuˇz´ıt Appe- l˚uv algoritmus [Appel(1967)], pro který popis obrysových hran staˇc´ı, nebot’

ˇreˇs´ı viditelnost na z´akladˇe pr˚useˇc´ık˚u tˇechto hran.

Nejprve bylo nutné vypoˇc´ıst koeficienty zakryt´ı v roz´ıch geometrie. Pro tento výpoˇcet se pouˇzije test pr˚useˇc´ıku polopˇr´ımky zaˇc´ınaj´ıc´ı v daném rohu a procházej´ıc´ı druhým bodem testované hrany s hranou vˇsech trojúheln´ık˚u soused´ıc´ıch s daným rohem, které vˇsak rohem ani druhým bodem testované hrany neprocházej´ı. Pokud je v tomto pr˚useˇc´ıku testovaná hrana za hranou trojúheln´ıku, vycház´ı z rohu za t´ımto trojúheln´ıkem schována, a proto se jej´ı koeficient zakryt´ı zvýˇs´ı o jedna.

Pro objasnˇen´ı výpoˇctu koeficient˚u v roz´ıch nám poslouˇz´ı obrázek 5.3. Tes- tovaný roh je zde oznaˇcen p´ısmenem C, a soused´ı s n´ım ˇctyˇri trojúheln´ıky CV0V1,CV1V2,CV2V3,CV3V0. Hrana, pro kterou se provád´ı výpoˇcet koeficientu zakryt´ı, jeCV₀, a hrany vˇsech ˇctyˇr trojúheln´ık˚u, které splˇnuj´ı podm´ınku, ˇ

ze neprocházej´ı rohovým bodem C ani druhým bodem testované hrany V₀,

(28)

jsou pouze dvˇe – V₁V₂ a V₂V₃.

Pr˚useˇc´ık polopˇr´ımkyCV0 a tˇechto dvou hran je pouze jeden, na obrázku oznaˇcený krouˇzkem. Pokud se v tomto pr˚useˇc´ıku polopˇr´ımkaCV₀ nacház´ı za

´

useˇckou V₁V₂, je schována za trojúheln´ıkem CV₁V₂ a nutné zvýˇsit koeficient zakryt´ı této hrany o jedna, pokud se nacház´ı pˇred n´ı, tento koeficient se nemˇen´ı.

C

V

₀

V

₁

V

2

V

₃

Obr´azek 5.3: V´ypoˇcet koeficientu zakryt´ı v roz´ıch geometrie

Dalˇs´ım krokem by mˇelo být rozsekán´ı sestavených lomených ˇcar na ele- mentárn´ı úseky, na nichˇz se viditelnost nem˚uˇze zmˇenit. K nalezen´ı tˇechto

´

usek˚u lze s výhodou pouˇz´ıt obrysové hrany, vyjma tˇech, které sd´ılej´ı trojú- heln´ıky leˇz´ıc´ıch na obou stranách dané hrany (podmnoˇzina skuteˇcných hran).

Na obrázku 5.4 je vidˇet, jakým zp˚usobem ovlivˇnuj´ı tyto hrany (nakresleny silnˇejˇs´ı ˇcárou) viditelnost daných úsek˚u.

U lomené ˇcáry se téˇz uchovává informace o relativn´ım koeficientu zakryt´ı na jej´ım zaˇcátku a konci. V bodˇe rozdˇelen´ı se nastav´ı pro zakrytou ˇcást tento koeficient na hodnotu, která koresponduje s poˇctem pˇrilehlých trojúheln´ık˚u, pro nezakrytou ˇcást se koeficient v bodˇe rozdˇelen´ı nastav´ı na nulu.

Poté, co jsou vˇsechny ˇcáry rozdˇeleny na úseky, ve kterých 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ám, urˇc´ı se lomená ˇcára, jej´ıˇz souˇcást´ı je bod s nejmenˇs´ı hloubkou. Tato ˇcára je vˇzdy viditelná, jej´ı absolutn´ı koeficient zakryt´ı se nastav´ı na nulu, a pomoc´ı procházen´ı grafem, jehoˇz hranami jsou lomené ˇcáry, se vypoˇc´ıtaj´ı absolutn´ı koeficienty zakryt´ı vˇsech lomených ˇcar.

C´ˇara je viditeln´a, pokud jej´ı koeficient zakryt´ı je roven nule.

(29)

Obrázek 5.4: Rozdˇelen´ı hran na elementárn´ı úseky s nemˇennou viditelnost´ı

Rozdˇelen´ı lomené ˇcáry je nutné pouze v pˇr´ıpadˇe, ˇze tato vstupuje za jinou, a v m´ıstˇe rozdˇelen´ı se zákonitˇe mˇen´ı koeficient zakryt´ı. U lomené ˇcary se také ukládá informace o pˇrilehlých trojúheln´ıc´ıch, d´ıky které je moˇzné rozpoznat, která ˇcást rozdˇelené ˇcáry se nacház´ı za plochou ohraniˇcenou dˇelic´ı ˇcárou a která mimo ni. Jak s touto informac´ı pracovat objasˇnuje obrázek 5.5. Na rozdˇeleném úseku lomené ˇcáry se stejná informace o pˇrilehlých trojúheln´ıc´ıch uchovává pro obˇe nové ˇcásti.

Obrázek 5.5: U lomené ˇcary se také ukládá informace o pˇrilehlých trojúhel- n´ıc´ıch

(30)

N´avrh Export obrys˚u

5.6 Export obrys˚ u

Pro export obrys˚u do souboru ve formátu PostScript jsem se rozhodl vyuˇz´ıt sestavené lomené ˇcáry. Nejdˇr´ıve se pˇresunou souˇradnice na jej´ı zaˇcátek, a poté se k cestˇe pˇripoj´ı úseˇcka konˇc´ıc´ı v dalˇs´ım jej´ım vrcholu. Takto se k cestˇe postupnˇe pˇripoj´ı vˇsechny úseˇcky, které tvoˇr´ı lomenou ˇcáru a za posledn´ı z nich se cesta uzavˇre. Takto budou do souboru vyexportovány vˇsechny lomené ˇcáry tvoˇr´ıc´ı obrys modelu.

Exportované hrany se nebudou nikterak oˇrezávat podle velikosti zobrazo- vaného okna, ale pro toto oˇrezán´ı se pouˇzij´ı pˇr´ımo pˇr´ıkazy jazyka PostScript.

5.7 Vznik faleˇ sn´ ych hran

D˚uvodem vzniku faleˇsných hran na nˇekterých modelech je to, ˇze jeden bod je v modelu uloˇzen nˇekolikrát, a definice geometrie se d´ıky tomu na nˇej odka- zuje pomoc´ı r˚uzných index˚u. Pokud tedy seznam hran vznikal jen za pomoci index˚u, a nebral v úvahu skuteˇcnou polohu bodu a normálový vektor plochy v tomto bodˇe, výsledné obrysové hrany byly protkány velkým mnoˇzstv´ım faleˇsných hran (Obrázek 5.6).

Obrázek 5.6: Model s faleˇsnými hranami a ten samý po jejich odstranˇen´ı

K odstranˇen´ı tˇechto faleˇsných hran jsem se rozhodl pouˇz´ıt haˇsovac´ı tabulku, popsanou v práci [Ska(2009)]. Vedla mˇe k tomu jej´ı rychlost pˇri ovˇe- ˇrován´ı duplicity bod˚u, která se odv´ıj´ı od n´ızké délky klastr˚u tabulky. Je

(31)

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ý typ unsigned integer, X, Y, Z jsou sou- ˇradnice bodu,α,β,γjsou koeficienty haˇsovac´ı funkce,C je koeficient, kterým se zajist´ı, aby se vyuˇzilo plného rozsahu datového typu unsigned integer, T + 1 je velikost tabulky (T = 2^k−1), & representuje modulo, které je im- plementováno jako logický operátor, a 0.5 je konstanta, která byla zjiˇstˇena experimentálnˇe a pomáhá lepˇs´ımu rozloˇzen´ı souˇradnic v tabulce.

Velice d˚uleˇzitá, pro velký rozptyl haˇsovac´ı funkce, je volba koeficient˚u, je- jichˇz hodnoty pro dosaˇzen´ı vynikaj´ıc´ıch výsledk˚u jsouα=π,β =e,γ =√

2.

Dalˇs´ım trikem této funkce je nahrazen´ı klasického modulo logickým operáto- rem &, které výpoˇcet urychl´ı. Toto nahrazen´ı si m˚uˇzeme dovolit d´ıky tomu, ˇ

ze velikost tabulky je vˇzdy 2^k.

(32)

6 Proveden´ı

Programovac´ım jazykem pro cel´y projekt VRUT je C++, a proto byl pouˇzit i pro tento modul.

Vytvoˇrený modul se nacház´ı v adresáˇri modules/drawingscene a jeho souˇcást´ı je nˇekolik tˇr´ıd, které budou pozdˇeji podrobnˇe popsány. Je vytvoˇren jako modul scény – to znamená, ˇze má pˇr´ım´ı pˇr´ıstup ke správci scén a ˇzádná jiná ˇcást jádra nen´ı pˇr´ıstupná.

Modul se spouˇst´ı z konzole VRUTu pˇr´ıkazemrunmodule DrawingScene.

Poté lze pomoc´ı pˇr´ıkazu setparam DrawingScene.sceneID [sceneID] nastavit scénu, pro kterou bude tento modul vyuˇzit a nastaven´ım parametru setparam DrawingScene.enabled 1 pˇrepnout modul do módu zobrazován´ı obrysových hran.

Po spuˇstˇen´ı se modul zaregistruje k odbˇeru o zmˇenách transformac´ı scény, geometrie a parametr˚u kamery. Dále jsou po spuˇstˇen´ı modulu nebo po zmˇenˇe scény postupnˇe naˇcteny vˇsechny geometrie z dané scény a je z nich vyexpor- tován seznam hran a informace o sousedn´ıch plochách. Poté se hrany roztˇr´ıd´ı no ostré (skuteˇcné), které se nemus´ı pˇri zmˇenˇe kamery pˇrepoˇc´ıtat, a na poten- cionáln´ı obrysové hrany, ve kterém se to opravdu obrysové hledaj´ı pˇri kaˇzdé zmˇenˇe parametr˚u kamery.

Zvolená scéna se modifikuje tak, ˇze se p˚uvodn´ı geometrie skryje a pˇridá se nová, která se bude plnit pˇri kaˇzdé zmˇenˇe parametr˚u kamery nalezenými hranami. Tak je moˇzná zapnout klasický zp˚usob zobrazen´ı jen t´ım, ˇze se nová geometrie pro nalezené 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ém rozhran´ı modulu se nacházej´ı tˇri ovládac´ı prvky, pole pro zadán´ı jména souboru a tlaˇc´ıtko, pomoc´ı kterého se provede export do zvo- leného souboru (Obrázek 6.1).

(33)

Proveden´ı Popis pouˇzit´ych tˇr´ıd

sceneID – slouˇz´ı k výbˇeru scény, pro kterou se bude aplikovat zobrazen´ı obrysových hran.

enabled – povol´ı nebo zak´aˇze zobrazen´ı obrysov´ych hran.

showHiddenLines – povol´ı nebo zakáˇze zobrazen´ı skrytých obrysových hran.

fileName – slouˇz´ı pro zadán´ı jména souboru, do kterého bude proveden export.

export – slouˇz´ı k exportu obrysových hran vybrané scény do souboru ve formátu PostScript.

Obr´azek 6.1: Uˇzivatelsk´e rozhran´ı modulu

6.2 Popis pouˇ zit´ ych tˇ r´ıd

6.2.1 Tˇ r´ıda DrawingScene

Tato tˇr´ıda dˇed´ı zSceneModule a je vstupn´ım m´ıstem implementovaného modulu. Uchovává informace o nataven´ı modulu, obsluhuje registrované zprávy a obsahuje funkce pro modifikaci scény a nalezen´ı vˇsech geometri´ı pro jejich následné zpracován´ı. Jeho d˚uleˇzitou souˇcást´ı je téˇz obsluha GUI.

D˚uleˇzit´e funkce tˇr´ıdy:

(34)

DrawingScene – konstruktor tˇr´ıdy. Jsou zde registrovány ovládac´ı prvky uˇzi- vatelského rozhran´ı a odbˇer zpráv o zmˇenˇe transformac´ı scény, geometrie a parametr˚u kamery.

processEvent – obsluha zpráv zaslaných jádrem.

processSelectScene – tato funkce je volána pˇri zmˇenˇe scény, pro kterou se maj´ı obrysové hrany hledat. V p˚uvodn´ı scénˇe skryje geometrie s hranami a zobraz´ı p˚uvodn´ı geometrie, v novˇe vybrané scénˇe skryje p˚uvodn´ı geometrie, pokud jeˇstˇe neexistuj´ı geometrie pro hrany, jsou vytvoˇreny, a zajist´ı sestaven´ı nových seznam˚u hran.

processChangeEnable – zap´ıná nebo vyp´ıná zobrazen´ı obrysových hran.

processExport – tato funkce zabezpeˇc´ı export vybran´e sc´eny do souboru.

processShowHiddenLines – zap´ıná a vyp´ıná zobrazen´ı skrytých hran.

prepareScene – funkce slouˇz´ı k pˇripraven´ı scény pro zobrazen´ı obrysových hran. Jsou zde pˇridány nové uzly a geometrie, která bude pouˇzita pro zobrazen´ı viditelných a skrytých 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énˇe projde vˇsechny geometrie a pro kaˇzdou vytvoˇr´ı koresponduj´ıc´ı objekt tˇr´ıdy DrawingEdges, který následnˇe napln´ı hranami z dané 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á vˇsechny kamery scény a vybere kameru pro vý- poˇcet obrysových 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ýpoˇcet nových obrysových hran a jejich následné zobrazen´ı.

clear – uvoln´ı modulem alokovanou pamˇet’.

(35)

6.2.2 Tˇ r´ıda DrawingEdges

Tato tˇr´ıda uchovává informace o bodech, normálách a hranách jedné geometrie scény. Obsahuje funkce pro vloˇzen´ı jednotlivých typ˚u geometrie, pomoc´ı kterých se pˇridávaj´ı hrany do seznamu. Dalˇs´ımi funkcemi je rozdˇelen´ı hran na skuteˇcné a potencionálnˇe obrysové a výpoˇcet zdánlivého pr˚useˇc´ık˚u dvou hran.

DrawingEdges – konstruktor tˇr´ıdy. Slouˇz´ı k vytvoˇren´ı hashmap potˇrebných pro vkládán´ı hran.

insertPolygon – export vˇsech hran z geometrie typuPOLYGON.

insertQuads – export vˇsech hran z geometrie typu QUADS.

insertTriFun – export vˇsech hran z geometrie typuTRI_FAN.

insertTriList – export vˇsech hran z geometrie typuTRI_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ádaná hrana je popsána tˇremi nebo ˇctyˇrmi indexy (podle toho, zda s n´ı soused´ı jeden nebo dva trojúheln´ıky). Prvn´ı dva indexy popisuj´ı body hrany a dalˇs´ı tˇret´ı body pˇrilehlých trojúheln´ık˚u.

getVertexIndex – na vstupu této funkce je index bodu z origináln´ı geometrie. Tato funkce dohledá, zda stejný bod jiˇz nebyl pouˇzit s jiným indexem a pokud ano, vrac´ı jiˇz pouˇzity index. Tato funkce je d˚uleˇzitá k odstranˇen´ı vzniku faleˇsných hran.

(36)

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ánlivý pr˚useˇc´ık dvou hran a rozhodne, která leˇz´ı v popˇred´ı a která v pozad´ı.

6.2.3 Tˇ r´ıda DrawingGeometry

Objekty této tˇr´ıdy koresponduj´ı s uzly s geometri´ı vybrané scény. Obsahuje funkce pro nalezen´ı obrysových hran a jejich následné poskládán´ı do lomených ˇ

car, ˇreˇsen´ı viditelnosti, a vykreslen´ı hran do zvolen´e geometrie.

DrawingGeometry – konstruktor tˇr´ıdy. Inicializuje tˇr´ıdn´ı promˇenn´e.

drawLineStrings – funkce pˇrenese nalezené lomené ˇcary popisuj´ıc´ı obrysové hrany do geometri´ı slouˇz´ıc´ıch pro viditelné a neviditelné hrany, ˇc´ımˇz zajist´ı jejich vykreslen´ı.

constructLineStrings – funkce zajist´ı nalezen´ı vˇsech obrysových hran modelu v závislosti na parametrech kamery, jejich poskládán´ı do lomených ˇ

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é a potencionálnˇe obry- sové na základˇe toho, zda je k hranˇe pˇrilehlý jeden nebo dva trojúhel- n´ıky.

constructLineString – sestroj´ı lomenou ˇcáru z obrysových hran. Lomená ˇ

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’.

(37)

6.2.4 Tˇ r´ıda PostScriptTools

Tato tˇr´ıda obsahuje funkce slouˇz´ıc´ı k sestaven´ı PostScript–ového souboru ze seznamu hran, jeho zápis na disk, a také funkce pro výpoˇcet správného um´ıstˇen´ı modelu na stránku.

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ých nabývaj´ı lomené ˇcáry. Tato informace je pouˇzita pro výpoˇcet mˇeˇr´ıtka pro vloˇzen´ı pohledu na stánku.

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ásleduj´ıc´ı popis lome- ných ˇcar se bude týkat viditelných hran.

hiddenLines – zap´ıˇse do souboru informaci o tom, ˇze následuj´ıc´ı popis lo- mených ˇcar se bude týkat skrytých hran.

writeLineStrings – zap´ıˇse do souboru vˇsechny lomené ˇcáry vyhovuj´ıc´ı dané podm´ınce viditelnosti.

writeGeometryName – zap´ıˇse do souboru poznámku o názvu uzlu geometry, ze které následuj´ıc´ı popis lomených ˇcar vznikl.

exportGeometry – zajist´ı vypsán´ı poznámky o názvu uzlu geometrie a ná- sledný zápis popisu lomených ˇcar do otevˇreného 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.

(38)

Proveden´ı Popis exportovan´eho souboru

6.2.5 Tˇ r´ıda VertexHashMap

Tuto tˇr´ıdu bylo potˇreba implementovat kv˚uli vzniku faleˇsných hran na nˇe- kterých modelech. Jedná se o haˇsovac´ı tabulku slouˇz´ıc´ı k nalezen´ı shodných bod˚u geometrie.

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ý soubor s popisem obrysových hran je ve formátu PostScript.

Tento soubor m˚uˇzeme rozdˇelit na dvˇe ˇcásti – na definice pˇr´ıkaz˚u a na data s popisem exportovaných hran. Definice se nacházej´ı na zaˇcátku souboru a jejich funkce je:

/ps Velikost stránky – horizontáln´ı a vertikáln´ı rozmˇer stránky. V definici je pouˇzit pˇr´ıkaz mm, slouˇz´ıc´ı pro pˇrevod mililitr˚u na topologické body, které se pouˇz´ıvaj´ı jako délková jednotka v PostScriptu.

/sl Styl obrysových hran – zde je definováno, jaký styl ˇcáry se pouˇzije pro vykreslen´ı obrysových hran.

/hl Styl skrytých hran – je zde definováno, jaký styl ˇcáry se pouˇzije pro vykreslen´ı skrytých hran.

/m, /l, /s, /e Pˇr´ıkazy pro tvorbu cesty – tyto pˇr´ıkazy jsou pouˇzity v datové ˇcásti pro popis exportovaných hran (viz n´ıˇze).

(39)

Proveden´ı Popis exportovan´eho souboru

/mm Pˇrevodn´ı pˇr´ıkaz – pˇrevod mililitr˚u na topologické body, které se po- uˇz´ıvaj´ı jako délková 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ý formát, aby nebyly závislé na zvoleném mˇeˇr´ıtku.

/iv Nastaven´ı pohledu – nastav´ı pohled s definovan´ym mˇeˇr´ıtkem na spe- cifikovan´e souˇradnice.

/cv Oˇr´ıznut´ı pohledu – oˇr´ızne pohled urˇcený levým horn´ım a pravým spodn´ım rohem.

Za definicemi následuje sada pˇr´ıkaz˚u pro nastaven´ı stránky (zde je volán pˇr´ıkaz ps pro nastaven´ı velikosti stránky), nastaven´ı pohledu (do zásobn´ıku je vloˇzeno mˇeˇr´ıtko a x-ová a y-ová souˇradnice, která se bude krýt s bodem [0, 0] exportovaných dat, a poté je zavolán pˇr´ıkaz iv) a oˇr´ıznut´ı pohledu (do zásobn´ıku se uloˇz´ı x-ová a y-ová souˇradnice levého horn´ıho a pravého spodn´ıho rohu, poté se zavolá pˇr´ıkaz cv).

V pˇr´ıpadˇe, ˇze exportujeme i skryté hrany, bude v datové ˇcásti po sobˇe následovat popis skrytých hran a poté popis hran viditelných. Kaˇzdá z tˇechto ˇ

cást´ı je uvozena pˇr´ıkazy pro styl ˇcáry a jeho následným pˇrepoˇctem (pro skryté hrany hl rs, pro viditelné hrany sl rs).

Po tˇechto pˇr´ıkazech následuje popis hran ve formˇe lomených ˇcar. Do zá- sobn´ıku je vˇzdy uloˇzena x-ová a y-ová souˇradnice bodu následována jedn´ım z pˇr´ıkaz˚u:

/s Prvn´ı bod lomené ˇcáry – pomoc´ı pˇr´ıkaz˚u newpath a moveto zaˇcne cestu a nastav´ı poˇcáteˇcn´ı souˇradnice lomené ˇcáry.

/l Pr˚ubˇeˇzný bod lomené ˇcáry – vykonán´ım pˇr´ıkazulinetopˇripoj´ı dalˇs´ı

´

useˇcku k cestˇe.

/e Koneˇcný bod lomené ˇcáry – pˇr´ıkazemlinetopˇripoj´ı k cestˇe posledn´ı

´

useˇcku a pˇr´ıkazemstroke zajist´ı vykreslen´ı aktu´aln´ı cesty.

Na samotném konci souboru se nacház´ı pˇr´ıkazshowpage, pomoc´ı kterého se pˇripravená stránka vykresl´ı.

(40)

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ád´ım výsledky mého testován´ı, kterých bylo dosaˇzeno na pˇre- nosném poˇc´ıtaˇci s dvoujádrovým procesorem Intel^c Core^TM2 Duo, operaˇcn´ı pamˇet´ı 4GB, grafickou kartou ATI Mobility Radeon HD 3650 a 64bitovým operaˇcn´ım systémem.

Model Poˇcet hran Cas [ms]ˇ

test.fhs 90 1

FabiaRS.fhs 3 628 5

FabiaEXT 0.05.fhs 1 240 185 330 Tabulka 7.1: ˇCas potˇrebn´y k pˇrepoˇctu nov´eho pohledu

Rychlost posouván´ı a natáˇcen´ı modelu vˇsak t´ımto ˇcasem nejsou nikterak omezeny, jen u modeluFabiaEXT_0.05.fhsnedojde ke korektn´ımu zobrazen´ı obrysových hran ihned po tˇechto úkonech.

Po té, co jsem s modulem v rámci testován´ı pracoval, si mysl´ım, ˇze tato rychlost pro interaktivn´ı práci s modely postaˇcuje. Pokud by vˇsak ˇcas pˇre- poˇctu nového 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áci modulu urychlit. Nyn´ı pˇrepoˇcet hran pˇri zmˇenˇe pohledu bˇeˇz´ı pouze v jednom vláknˇe, a tak by bylo moˇzné dosáhnout vyˇsˇs´ı rychlosti rozloˇzen´ım ˇcasu na v´ıce jader procesoru pomoc´ı bˇehu výpoˇct˚u v nˇekolika paraleln´ıch vláknech.

7.2 Kvalita v´ ystupu

Na modelu krychle (Obrázek 7.1) jsou korektnˇe zobrazeny vˇsechny hrany a je zde téˇz korektnˇe vyˇreˇsena jejich viditelnost. K ˇreˇsen´ı viditelnosti hran konvexn´ıho tˇelesa dostaˇcuje pouze výpoˇcet koeficient˚u zakryt´ı v roz´ıch objektu.

Také na modelu test.fhs (Obrázek 7.2) jsou vˇsechny nalezené hrany v poˇrádku. Jejich viditelnost je správnˇe vyˇreˇsena pouze v rámci jednotlivých

(41)

Experimenty Kvalita v´ystupu

model˚u krychle, ale ne v rámci celé sestavy. Nyn´ı je implementována ˇcást Appelova algoritmu, která zaruˇc´ı korektn´ı zobrazen´ı viditelných hran pouze v rámci jednotlivých konvexn´ıch objekt˚u. Pro rozˇs´ıˇren´ı na nekonvexn´ı objekty a jejich sestavy by bylo potˇreba doimplementovat ˇcást algoritmu ˇreˇs´ıc´ı pr˚u- seˇc´ıky jednotlivých lomených ˇcar a jejich dˇelen´ı na menˇs´ı úseky, ve kterých je koeficient zakryt´ı konstantn´ı (viz sekce 5.5 na stranˇe 22).

Na obrázku 7.3 jsou vidˇet nalezené obrysové hrany modeluFabiaRS.fhs.

I zde se zdaj´ı být vˇsechny nalezené hrany opravdu tˇemi obrysovými. Chyby ve viditelnosti se zde vˇsak uˇz projevuj´ı jak na úrovni jednotlivých geometri´ı, tak v rámci celé sestavy. I zde je d˚uvodem neúplná implementace algoritmu ˇreˇs´ıc´ıho viditelnost nalezených hran.

Model FabiaEXT_0.05.fhs (Obrázek 7.4) byl nejsloˇzitˇejˇs´ım z tˇech, na kterých byl modul testován. Obrysové hrany se hledaly ve v´ıce jak miliónu vˇsech hran tohoto modelu. Problémy s viditelnost´ı se zde vyskytuj´ı obdobné jako v pˇr´ıpadˇe modelu FabiaRS.fhs. Pˇridaly se k nim vˇsak i problémy s na- lezenými obrysovými hranami, které jsou ukázány na detailu kliky pˇredn´ıch dveˇr´ı (Obrázek 7.5).

Jeden z problém˚u je viditelný na výlisku v modelu dveˇr´ı, kde se zlom opticky jev´ı jako hrana, ale ve skuteˇcnosti je zde malý pˇrechodový rádius, na kterém se v definici geometrie ˇzádná hrana nevyskytuje.

Druhým problémem jsou krátké hrany, které procházej´ı napˇr´ıˇc zaoble- nými hranami kliky. V tˇechto m´ıstech opticky ˇzádné hrany nejsou viditelné, ale v definici geometry se zde vyskytuj´ı malé odchylky normál. D´ıky tˇemto odchylkám nen´ı moˇzné sjednotit bod sousedn´ıch trojúheln´ık˚u, a algoritmus v tomto m´ıstˇe detekuje hranu.

(42)

Obr´azek 7.1: Model krychle

(43)

Obr´azek 7.2: Model test.fhs

(44)

Obr´azek 7.3: Model FabiaRS.fhs

(45)

Obr´azek 7.4: Model FabiaEXT_0.05.fhs

(46)

Obr´azek 7.5: Detail kliky pˇredn´ıch dveˇr´ı modeluFabiaEXT_0.05.fhs

(47)

8 Z´ avˇ er

C´ılem práce bylo vytvoˇrit modul do aplikace VRUT, který um´ı zobrazit a vy- exportovat obrysové hrany nahraného modelu. Pˇri práce jsem se potýkal s nevyhovuj´ıc´ı a velmi struˇcnou dokumentac´ı aplikace, a vˇetˇsinu d˚uleˇzitých informac´ı pro tvorbu nových modul˚u a práci se scénou a geometri´ı jsem musel dohledat pˇr´ımo ve zdrojových kódech jádra a jiˇz existuj´ıc´ıch modul˚u. Vzhle- dem k tˇemto fakt˚um povaˇzuji práci za úspˇeˇsnou, i kdyˇz se mi nepodaˇrilo naimplementovat vˇsechny funkce, které jsem mˇel v úmyslu.

Proto by jeˇstˇe bylo dobré u modulu doˇreˇsit korektn´ı výpoˇcet koeficient˚u zakryt´ı v Appelovˇe algoritmu pouˇzitém pro ˇreˇsen´ı viditelnosti hran, omezit pˇrepoˇcet a generován´ı obrysových hran jen na ty geometrie, které se nachá- zej´ı v pohledovém jehlanu, a umoˇznit generován´ı úplných a ˇcásteˇcných ˇrez˚u pomoc´ı oˇrezáván´ı hran pomoc´ı mnoˇziny ploch.

Reˇsen´ı, kter´ˇ e bylo pouˇzito pro odstranˇen´ı v´ıcenásobných bod˚u pˇri ˇreˇsen´ı problému faleˇsných hran, by podle mého názoru bylo dobré pouˇz´ıt i v jiných modulech. Pˇri naˇc´ıtán´ı modelu by tento jednoduchý mechanizmus sn´ıˇzil ob- sazenou pamˇet’ a pˇri ukládán´ı by zase omezil velikost souboru obsahuj´ıc´ıho popis geometrie.

C´ılem práce bylo také zobrazovat nalezené obrysy a to pokud moˇzno v reálném ˇcase. I tohoto bodu se podaˇrilo dosáhnout a detekce hran bˇeˇz´ı na standardn´ım HW v interaktivn´ı rychlosti (pˇrepoˇcet hran nejsloˇzitˇejˇs´ıho testovaného modelu trvá zhruba 1/3 sekundy).

(48)

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.

[Jiˇr´ı ˇZára(2010)] JI ˇRÍ Z ´ˇARA, BED ˇRICH BENEˇS, JI ˇRÍ SOCHOR, PETR FELKEL Modern´ı poˇc´ıtaˇcová grafika. Holandská 8, 639 00 Brno : Computer Press, a.s., 2010. ISBN 80-251-0454-0.

[Kevin Weiler(1977)] KEVIN WEILER, PETER ATHERTON Hidden sur- face removal using polygon area sorting. 1977.

[Tiˇsnovský(2006)] PAVEL TIˇSNOVSK Ý Seriál Grafické formáty. Internet Info, s.r.o, 2006. Dostupné z:

http://www.root.cz/serialy/graficke-formaty/.

[Ska(2009)] VÁCLAV SKALA, JAN HR ÁDEK, MARTIN KUCHA ˇR Hash Function for Trianglular Mesh Reconstruction. In Recent Advances in Computers, s. 233–238, Athény, 2009. WSEAS Press. ISBN 978-960- 474-099-4.

[Václav Kyba(2010)] VÁCLAV KYBA, ANTONÍN MÍˇSEK a dalˇs´ı Doku- mentace aplikace VRUT, 2010.

(49)

Seznam obr´ azk˚ u

2.1 Obálky zobrazené ve scénˇ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árn´ı úseky s nemˇennou viditelnost´ı . 24 5.5 U lomené ˇcary se také ukládá informace o pˇrilehlých trojúhel- n´ı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

(50)

SEZNAM OBR ´AZK˚U SEZNAM OBR ´AZK˚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

(51)

Seznam tabulek

7.1 Cas potˇrebn´ˇ y k pˇrepoˇctu nov´eho pohledu . . . 35

Bakaláˇrská práce Detekce obrys˚u 3D objekt˚u pro VRUT

Z´ apadoˇcesk´ a univerzita v Plzni Fakulta aplikovan´ ych vˇed

Katedra informatiky a v´ ypoˇcetn´ı techniky