Vizualizace vnitřní struktury 3D modelů pomocí ořezávání v reálném čase

České vysoké učení technické v Praze Fakulta elektrotechnická

Diplomová práce

Vizualizace vnitřní struktury 3D modelů pomocí ořezávání v reálném čase Bc. Milan Timko

Vedoucí práce: Ing. Ladislav Čmolík Studijní program: Elektronika a informatika strukturovaný magisterský Obor: Výpočetní technika 20. května 2009

Poděkování Chtěl bych zde poděkovat především vedoucímu práce Ing. Ladislavu Čmolíkovi za pravidelné konzultace a cenné rady k návrhu aplikace. Dále bych rád poděkoval své rodině za podporu v průběhu studií.

Prohlášení Prohlašuji, že jsem svou diplomovou práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonu (autorský zákon). Ve Velešíně dne 20.5.2009

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

Abstract The main goal of this work is to analyze basic approaches to the problem of visualization inner structure of complex 3D models and automatic generation of illustrations in realtime. Based on this analysis, design and implement own application, which will realize one of these approaches.

Abstrakt Cílem této práce je analyzovat základní přístupy k problému vizualizace vnitřní struktury složitých 3D modelů a automatického generování ilustrací v reálném čase. Na základě této analýzy bude navržena a implementována vlastní aplikace, která jeden z těchto přístupů realizuje.

Obsah 1 Úvod..................................................................................................................................13 2 Vymezení cílů a požadavků práce.....................................................................................15 3 Používané metody vizualizace vnitřní struktury...............................................................17 3.1 Využití průhlednosti...................................................................................................17 3.2 Exploze modelu.........................................................................................................19 3.3 Využití řezů................................................................................................................21 3.3.1 Řezy odvozené podle tvaru důležitého objektu.................................................22 3.3.2 Řezy odvozené podle tvaru vnějšího objektu....................................................24 4 Analýza a návrh implementace..........................................................................................30 4.1 Shrnutí hlavních rysů zvolené metody......................................................................31 4.2 Analýza rozhraní systému..........................................................................................32 4.2.1 Proces tvorby ilustrace.......................................................................................33 4.2.2 Prohlížení ilustrace.............................................................................................33 4.3 Analýza a návrh implementace ilustračních konvencí...............................................34 4.3.1 Geometrická reprezentace objektu.....................................................................34 4.3.2 Úhly pohledu......................................................................................................44 4.3.3 Vnořené řezy......................................................................................................46 4.4 Vytvoření kostry modelu............................................................................................47 4.5 Geodetické vzdálenosti..............................................................................................49 4.6 Ořezávací shadery......................................................................................................50 4.6.1 Ořezávání rovinami............................................................................................50 4.6.2 Víceprůchodový algoritmus...............................................................................52 4.6.3 Geodetický výřez...............................................................................................53 5 Implementace....................................................................................................................54 5.1 Hlavní třídy aplikace.................................................................................................54 5.2 Rozdělení programu do Java balíčků.........................................................................56 5.3 Rozhraní GLSL shaderů............................................................................................59 5.4 Přehled knihoven třetích stran...................................................................................61 6 Testování aplikace.............................................................................................................62 6.1 Minimální požadavky na systém...............................................................................62 6.2 Rychlost aplikace.......................................................................................................63 7 Srovnání aplikace s existujícími řešeními.........................................................................65 8 Závěr..................................................................................................................................66 9 Seznam literatury...............................................................................................................67 Příloha A – Snímky obrazovky aplikace.............................................................................69 Příloha B - Uživatelská příručka.........................................................................................71 Vytvoření ilustrace...............................................................................................................71 Interaktivní prohlížení.........................................................................................................73 Příloha C – Obsah přiloženého DVD..................................................................................75

Seznam obrázků

Jméno Obrázek 1 Obrázek 2 Obrázek 3 Obrázek 4 Obrázek 5 Obrázek 6 Obrázek 7 Obrázek 8 Obrázek 9 Obrázek 10 Obrázek 11 Obrázek 12 Obrázek 13 Obrázek 14 Obrázek 15 Obrázek 16 Obrázek 17 Obrázek 18 Obrázek 19 Obrázek 20 Obrázek 21 Obrázek 22 Obrázek 23 Obrázek 24 Obrázek 25

Popis Vnitřní struktura komplexních modelů. Příklad ručně vytvořených ilustrací vnitřní struktury modelů. Renderování řízené důležitostí. Příklad ilustrace pomocí metody „Exploded Views“. Příklad použití řezů k zobrazení vnitřní struktury 3D modelu. Příklad použití zvlněných okrajů řezu. Příklad použití obdélníkového výřezu v ručně kreslené ilustraci. Použití příčného a klínového výřezu v ručně kreslené ilustraci. Řez respektující tvar povrchu objektu v ručně kreslené ilustraci Příklad zobrazení vnořených řezů. Diagram znázorňující strukturu systému. Přiřazování geometrické reprezentace částem modelu. Obdélníkový výřez. Výpočet parametrů výřezu pro obdélníkovou reprezentaci. Klínový výřez . Příklad výpočtu úhlů klínu. Příčný výřez. Geodetický výřez. Struktura dat geometrické reprezentace složitého povrchu. Výpočet rozsahu geodetického výřezu . Příklad sestavení vrstev viditelnosti a grafu viditelnosti. Fáze algoritmu pro nalezení kostry modelu. Ukázka dělení hran. Příklad detekce vnitřních stěn. Zjednodušený diagram tříd .

Stránka 13 14 18 20 22 23 25 26 27 28 32 33 35 36 37 38 39 41 42 43 45 47 49 51 55

Kapitola 1. Úvod

13

1 Úvod Ilustrace vnitřní struktury je téma počítačové grafiky, které se zvláště v posledních letech těší zvýšenému zájmu v mnoha odvětvích lidské činnosti. Komplexní geometrické modely složené z mnoha vnořených částí vznikají v medicíně, strojírenství nebo v průmyslové výrobě. Někdy bývají vytvořené ručně (například model chystaného výrobku), jindy zase automaticky pomocí skenovacích přístrojů (CT, rentgen). Složitost takových modelů často dosahuje stupně, kdy již pro nezasvěceného pozorovatele není možné pochopit vnitřní vazby jen podle několika pohledů z vnějšku (viz. obrázek 1), či pomocí schémat.

Obrázek 1: Vnitřní strukturu a vzájemné vazby jednotlivých částí komplexních modelů nelze pochopit jen na základě pohledu z vnějšku.

Ještě v nedávné minulosti existovalo pouze jediné řešení – využití služeb profesionálních ilustrátorů, kteří jsou schopni pomocí uměleckých metod ručně vytvořit přehlednou ilustraci a popsaný problém částečně odstranit (viz. obrázek 2). Tento přístup má však jednu zásadní nevýhodu – cenu. Jeden takový obrázek totiž zabere zkušenému tvůrci přinejmenším několik hodin nepřetržité práce. Jakákoliv pozdější požadavek na úpravu ilustrace navíc může znamenat nutnost začít úplně od začátku.

14

Kapitola 1. Úvod

Obrázek 2: Příklad ručně vytvořených ilustrací vnitřní struktury modelů. [SV05].

S nástupem moderních počítačů s grafickými akcelerátory se proto logicky začaly hledat možnosti, jak ruční tvorbu ilustrací nahradit a pokud možno také zjednodušit. Dnes již existuje mnoho různých metod, jak tohoto dosáhnout. Navzájem se liší ve dvou základních bodech. Prvním je způsob, jakým odstraňují vnější geometrii a tím zviditelňují důležité vnitřní části (například přidáním průhlednosti nebo vytvořením řezů). Za druhé je to stupeň automatizace celého procesu tvorby. Plně automatické systémy jsou schopny generovat výsledek během několika minut, avšak tvůrce do značné míry ztrácí kontrolu nad dílčími parametry ilustrace. Plně manuální systémy na druhou stranu umožní definovat i ty nejmenší detaily, konečná doba práce ale bývá mnohonásobně delší.

Shrnutí hlavních výhod počítačové grafiky pro vizualizaci vnitřní struktury komplexních modelů proti ručnímu kreslení ilustrací: •

rychlejší vytvoření (a tedy i nižší cena)

•

rychlá modifikovatelnost (změna úhlu pohledu, úprava modelu, atd...)

•

interaktivní prohlížení (zviditelnění určité části, volné otáčení modelu)

•

možnost vytvářet animace (vhodné například pro prezentace)

Kapitola 2. Vymezení cílů a požadavků práce

15

2 Vymezení cílů a požadavků práce V této práci bude popsáno několik nejpoužívanějších přístupů, jak dosáhnout cílů, popsaných v úvodu a dosáhnout tak počítačem generované ilustrace, které se svým vzhledem přibližují těm ručně nakresleným. Všechny tyto metody navíc využívají moderní grafický hardware a tedy umožňují i interaktivní prohlížení v reálném čase.

Cílem je zmapovat základní metody určené k vizualizaci vnitřní struktury komplexních modelů a tvorby přehledných ilustrací pro účely prezentací či různých manuálů a katalogů. Dále pak zvolit jednu metodu a na jejím základě implementovat aplikaci, která umožní: 1. načtení externího 3D modelu 2. možnost zviditelnit uživatelem vybrané vnitřní části 3D modelu v reálném čase 3. interaktivní prohlížení výsledné ilustrace v reálném čase 4. umožnit uživateli změnit různé parametry ilustrace

ad. 1) Načtením externích modelů se rozumí možnost uživatele kdykoliv do aplikace importovat libovolný vlastní 3D model se kterým si přeje pracovat. ad. 2) Uživatel bude mít možnost vybrat jednu nebo více vnitřních částí modelu a aplikace musí pomocí implementované metody vizualizace vnitřní struktury zajistit, aby se tyto části v reálném čase zviditelnily. Výběr bude probíhat buď přímo kliknutím myši na vykreslenou část v hlavním okně aplikace, nebo výběrem podle jména v seznamu všech částí. ad. 3) Interaktivní prohlížení je důležité především kvůli usnadnění celkové orientaci uživatele. Aplikace umožní volné otáčení, posouvání a přibližování/oddalování modelu. ad. 4) Uživatel bude mít možnost manuálně změnit parametry odstraňování překrývající geometrie. Tím bude moci vylepšit vzhled výsledné ilustrace ke své spokojenosti.

16

Kapitola 2. Vymezení cílů a požadavků práce

Kapitola 3. Používané metody vizualizace vnitřní struktury

17

3 Používané metody vizualizace vnitřní struktury Existuje několik základních způsobů, jak dosáhnout vizualizace vnitřní struktury komplexních 3D modelů. Podle použité metody k odstranění geometrie, která překrývá důležitou vnitřní část, se nejčastěji dělí na tři skupiny: •

využití průhlednosti (Ghost Views)

•

exploze modelu (Exploded Views)

•

využití řezů (Cut-away Views)

Každá z těchto metod má své výhody a nevýhody a každá je vhodná pro trochu jiný typ modelů. V následujících kapitolách budou všechny blíže popsány na konkrétních příkladech implementace.

3.1 Využití průhlednosti Základ této metody je jednoduchý. Každé ploše modelu se k základním atributům (barva, atd.) přiřadí další položka – průhlednost (desetinné číslo od 0 do 1). Ta udává, jestli je plocha zcela viditelná, neviditelná, nebo částečně průhledná.

Velice jednoduchý systém pro zobrazení vnitřní struktury by tedy mohl fungovat tak, že tvůrce ilustrace nastaví každé části 3D modelu manuálně hodnotu průhlednosti a systém podle toho jednoduše vykreslí výsledný obrázek (překrývající části se zneviditelní). Tento způsob má však několik nevýhod. Za prvé by se při každé změně úhlu pohledu musely zadat jiné hodnoty (změní se pořadí překrývajících se částí). Za druhé by zneviditelnění celé části modelu kvůli jedné malé vnitřní součástce vedlo ke zmatení pozorovatele.

18


Je tedy nezbytné navrhnout takové řešení, které průhlednost určí automaticky pro každý vykreslovaný bod modelu zvlášť na základě ilustrátorem specifikovaných priorit. Jedno z nejznámějších se jmenuje Renderování řízené důležitostí, anglicky Importance-driven Rendrering,

kreré je popsáno v článku [IDVR04]. Základní myšlenka tkví v tom, že

namísto průhlednosti se jednotlivým částem modelu přiřazuje tzv. důležitost. Potřebná hodnota průhlednosti se pak vypočítává průběžně podle úhlu ke kameře a vzájemného překrytí. Méně důležitým částem bude přiřazena větší průhlednost a naopak.

Renderování řízené důležitostí automaticky odstraňuje nežádoucí překrytí a tím maximalizuje obsah informací ve výsledném obrázku. Důležitost určuje, který objekt je nejzajímavější a bude mít nejvyšší prioritu. Každému objektu je přiřazeno kladné číslo, značené jako důležitost, jehož hodnota bude mít vliv na určení viditelnosti při renderování. Pokud tedy méně významný objekt překrývá zajímavější, bude zobrazen s nižší viditelností (větší průhledností). Výhoda metody spočívá v tom, že méně důležité objekty jsou méně viditelné jen v případě, že se za nimi nalézá další objekt.

Obrázek 3: Renderování řízené důležitostí. Tvůrce ilustrace přiřadí každé části modelu důležitost, na základě které je poté vypočítána průhlednost pro každý vykreslovaný pixel zvlášť. [IDVR04].


19

Metody založené na průhlednosti se používají například pro zobrazení lékařských dat či v automobilovém průmyslu. Hodí se především pro modely obsahující rozsáhlé vnitřní části (například kostru na obrázku 3), případně pro ilustraci objektů, jejichž základní tvar a pozice jednotlivých částí jsou obecně známé (například automobily). Hlavní nevýhoda je totiž ve špatném zachovávání percepce hloubky (lze částečně vyřešit možností interaktivního prohlížení).

Další nevýhodou je fakt, že pro vykreslení výsledné scény nestačí použít pouze běžné metody, které nabízí grafické karty využívající z-buffer. U nich se totiž musí zajistit správné pořadí vykreslovaných poloprůhledných objektů nejvzdálenějších k nejbližším, vzniká tedy potřeba implementace složitého vykreslovacího systému, který umí zobrazit průhledné objekty bez ohledu na pořadí v jakém se vykreslují.

3.2 Exploze modelu Způsob, jakým tato metoda zobrazí vnitřní strukturu, je založen na explozi modelu na jednotlivé části, které se poté rozmístí ve výsledné ilustraci tak, aby nedošlo k žádnému nežádoucímu překrývání (viz. obrázek 4). Aby došlo k zachycení vnitřních vazeb, musí mít toto rozmístění jistá pravidla. V ručně kreslených ilustracích bývá často zvolena taková pozice částí, která naznačuje potřebný směr jejich montáže to celku. Proces animace exploze modelu by tedy měl být jakýsi opak skládání ilustrovaného výrobku.

Opět by bylo možné navrhnout plně manuální systém, kdy tvůrce ilustrace ručně nastaví, které části se mají jak rozdělit, jakým směrem se přesunout atd.. V praxi mnohem užitečnější způsob je však navržen v článku [EXPVIEW08], kde se autoři snaží podrobně definovat konvence používané v ručně kreslených ilustracích a poté proces počítačem generovaných ilustrací automatizovat.

20


Obrázek 4: Příklad ilustrace pomocí metody „Exploded Views“. [EXPVIEW08].

Na základě těchto konvencí je vytvořena skupina pravidel, ke kterým se při automatickém generování ilustrací přihlíží. Pravidla definují způsob, jakým se provede výpočet nových pozic částí či jakým způsobem a kdy se provede rozdělení jedné části na dvě.

Pravidla definovaná v [EXPVIEW08] pro rozbití modelu na menší části: •

Blokující omezení – části jsou posunuty od sebe v neblokovaných směrech. Výsledné uspořádání částí umožní pozorovateli pochopit lokální vazby a relativní pozice částic.

•

Viditelnost -

části jsou posunuty tak daleko od sebe,

aby se navzájem

nepřekrývaly. •

Kompaktnost – vzdálenost o kterou se části posunou ze svých původních pozic musí být co možná nejmenší.


•

21

Kanonický směr posunu – směr posunu částí by měl respektovat kanonický tvar 3D modelu a tedy by měl vést podél některé z jeho hlavních os (tím se nejlépe odhadne směr montáže do celku).

•

Hierarchie částí – složitější modely se rozdělí do několika menších skupin, které se zobrazí zvlášť.

•

Kontejnerové části – část, která v sobě obsahuje několik jiných částí se uprostřed rozdělí řezací rovinou. Takto vzniknou dvě nové části, jejíž nová pozice se určí na základě předchozích pravidel.

Systém poté vytvoří tzv. „Exlosion Graph“, což je orientovaný acyklický graf, jehož struktura definuje relativní pořadí, ve kterém mohou být části přesunuty bez porušení definovaných pravidel. S jeho pomocí pak lze interaktivně vytvářet požadované ilustrace z různých úhlů pohledu.

Nevýhodou tohoto typu ilustrace je především omezení na technické výrobky. Ačkoliv autoři článku zkoušeli svůj systém použít i na anatomické modely lidského těla, sami přiznávají, že pro ně tato metoda není příliš vhodná.

3.3 Využití řezů Tento způsob zobrazení vnitřních prostor modelu je založen na vytvoření řezu, jenž odstraní geometrii překrývající části 3D modelu. Výstup může být na první pohled velice podobný s metodou využití průhlednosti, avšak princip je zcela odlišný. Implementace bývá většinou založena na ořezávacích rovinách, kdy se při vykreslování jednoduše zahazují všechny fragmenty, které leží před danou rovinou (viz. obrázek 5). Umístění rovin probíhá pro každou část modelu zvlášť a opět může být provedeno buď manuálně tvůrcem ilustrace, či automaticky systémem podle nějakých daných pravidel.

22


Obrázek 5: Příklad použití řezů k zobrazení vnitřní struktury 3D modelu. Při zobrazení touto metodou je patrná i struktura nedůležitých částí. [CUTAWAY07].

Výhoda řezů, oproti předchozím metodám, je především možnost jejich použití jak pro technické, tak pro anatomické 3D modely. Jejich vhodným umístněním lze dosáhnout jak požadovaného zobrazení vnitřní struktury, tak zachování přehlednosti vnitřních vazeb jednotlivých částí u složitějších objektů. Na rozdíl od metod založených na průhlednosti je totiž zřejmá i struktura a tvar nedůležitých částí.

3.3.1 Řezy odvozené podle tvaru důležitého objektu Velmi často citovanou prací, zabývající se řezy, je článek „Interactive Cutaway Illustrations“ autora J. Diepstratena a kol. [CUTAWAY03]. Ačkoliv je zaměřen spíše na implementaci ořezávání pomocí grafického HW, podrobně analyzuje konvence používané v ručně kreslených ilustracích. Tato metoda, stejně jako naprostá většina ostatních, vypočítává pozice řezů (a tedy tvar odstraněné geometrie) na základě tvaru části, která má být viditelná.


23

Konvence pro použití řezů podle [CUTAWAY03]: •

Rozlišení mezi vnitřními a vnějšími částmi – musí být zřejmé, na které části má být potenciálně aplikován řez, protože překrývají jinou (vnitřní) část.

•

Tvar řezu – řez bývá reprezentován průsečíkem několika poloprostorů.

•

Pozice řezu – řez je umístěn na nebo podél hlavní osy vnitřního objektu. Při použití dvou ořezávacích rovin leží obě na hlavní ose objektu a úhel mezi nimi je parametr definovaný uživatelem.

•

Okraje řezu – volitelně by se okraj řezu neměl zobrazovat jen ploše (podle poloprostoru, který jej reprezentuje), ale s nějakým plastickým efektem jako zubaté či zvlněné okraje (viz. obrázek č.6). Tím lze dosáhnout většího stupně abstrakce (větší názornosti) ilustrace.

•

Vyplnění vnitřních prostor – 3D modely bývají reprezentovány pomocí tzv. hraniční reprezentace. Objekt je definován pouze svým vnitřním a vnějším okrajem, při použití ořezávací roviny tak může dojít k odstraní předního okraje a tím k odkrytí okraje zadního (viz. obrázek č.6). Je tedy nutné do modelu přidat další geometrii, která odebraný okraj nahradí.

Obrázek 6: Příklad použití zvlněných okrajů řezu. Na obrázku je také zřetelně vidět problém s odkrytou zadní stěnou, kdy se model v hraniční reprezentaci jeví jako dutý. [CUTAWAY03].

24


V článku je popsáno několik přístupů, s jejichž pomocí lze na grafické kartě implementovat různou podmnožinu výše uvedených pravidel. Rovněž je zde diskutována varianta použití systému pro konstruktivní geometrii (CSG), který by umožnil jednoduchou implementaci všech pravidel. Tato možnost je ale zavržena z obavy o dosažení dostatečné rychlosti vykreslování pro aplikaci běžící v reálném čase.

Nevýhodou této metody je především fakt, že odstranění vnější geometrie na základě tvaru vnitřní části nemusí být pro pozorovatele vždy přehledné. Řešení, které bere v úvahu i tvary vnějších částí je popsáno v článku „Interactive Cutaway Illustrations of Complex 3D Models“ [CUTAWAY07], který vyšel o 4 roky později (v roce 2007). Zajímavé je především to, že je v něm použití CSG systému pro implementaci řezů již pokládáno za samozřejmost.

3.3.2 Řezy odvozené podle tvaru vnějšího objektu Tato kapitola se zabývá popisem hlavních rysů systému pro automatické generování řezů a interaktivního prohlížení ilustrací, popsaného v článku [CUTAWAY07]. Přístup prezentovaný v tomto článku je založen především na těchto dvou hlavních myšlenkách: pozice řezů by měly respektovat tvar objektu, který řežou a systém by měl podporovat interaktivního prohlížení ilustrací.

V navrženém systému tvůrce ilustrace vybaví jednotlivé části 3D modelu dodatečnými informacemi o jejich tvaru, na jejichž základě se pak automaticky generují odpovídající řezy. Tato anotace modelu proběhne pouze jednou při vytváření ilustrace. Poté je k dispozici nástroj pro interaktivní prohlížení, kdy uživatel kliknutím myši vybere požadované části 3D modelu a systém sám vybere odpovídající úhel pohledu a vybrané části pomocí řezů zviditelní. Stejně jako v předchozích citovaných pracích, se i autoři tohoto článku nejprve zabývali analýzou vzhledu ručně vytvořených ilustrací, aby poté mohli navrhnout pravidla pro jejich automatické vytváření. Tímto způsobem byly definovány čtyři základní konvence, které by systém měl respektovat.


25

Konvence, které musí systém pro automatické generování řezů implementovat podle článku [CUTAWAY07]: •

Geometrie řezů respektuje tvar ořezávaného objektu

•

Automatický výběr nejlepšího úhlu pohledu

•

Vhodný vzhled vnořených řezů

Geometrické konvence řezů

Nejlepší způsob, jakým lze provést řez objektem, je ve většině případů dán jeho geometrickým tvarem. Analýzou vzhledu ručně kreslených ilustrací byly definovány tři základní kategorie geometrických tvarů, z nichž každý vyžaduje jiný přístup pro výpočet automatického ořezávání:

•

Obdélníkový tvar – ilustrátoři pro objekty, které se svým tvarem podobají obdélníku, často volí obdélníkový výřez, jehož orientace os je shodná s orientací hlavních os ořezávaného objektu.

Obrázek 7:Příklad použití obdélníkového výřezu v ručně kreslené ilustraci. [CUTAWAY07].

26


•

Trubicový tvar – jde se o objekty, jejichž okraje se nacházejí v rovnoměrné vzdálenosti kolem středové osy. Typickým příkladem je objekt tvaru válce, je ale potřeba brát v úvahu i případy, kdy středová osa není přímá (například potrubí či cévy v anatomickém modelu). Ilustrátoři pro tento typ modelů obvykle používají dva způsoby pro odstranění překrývající části, příčný a klínový řez. Příčný řez je založen na umístnění dvou ořezávacích rovin kolmo na hlavní osu objektu v určité vzdálenosti od sebe. Mezi nimi pak dojde k odebrání veškeré geometrie. Klínový řez má roviny položené na hlavní ose v úhlu zvoleném tak, aby byly vidět požadované vnitřní části.

Obrázek 8: Příklad použití příčného a klínového výřezu v ručně kreslené ilustraci [CUTAWAY07].

•

Modely povrchu – jak v technických, tak v anatomických 3D modelech se často vyskytují tvarem velice složité části, které reprezentují vnější povrch (například karosérie auta nebo lidská kůže) a „obalují“ velkou většinu ostatní geometrie. Pro takové případy bývá v ručně kreslených ilustracích použita metoda geodetického výřezu, kdy se provede odstranění překrývající geometrie s respektem k lokálnímu tvaru objektu. Tvar výřezu může být odvozen například z obrysů nakresleného modelu, nebo například podle geodetických křivek na jeho povrchu.


27

Obrázek 9: Příklad řezu respektujícího tvar povrchu objektu v ručně kreslené ilustraci [CUTAWAY07].

Výběr úhlu pohledu

Úhel pohledu v ručně tvořených ilustracích bývá velmi pečlivě vybírán, aby bylo možné co nejlépe rozlišit vnitřní strukturu a vazby mezi jednotlivými vnitřními částmi modelu. V případě, že je potřeba zvýraznit jednu konkrétní vnitřní část, bývá většinou vybrán takový směr pohledu, aby množství překrývající struktury bylo co možná nejmenší. Tím se minimalizuje počet potřebných řezů a výsledkem bývá vyšší přehlednost ilustrace. Někdy také bývá výhodné zvolit úhel pohledu podle tvaru 3D modelu, například pohled zepředu či z boku.

Systém tedy musí vzít v úvahu i tento aspekt ilustrace a umožnit tvůrci ilustrace definovat vhodné směry pohledu na model ručně. Z takto stanovených úhlů pohledu poté při interaktivním prohlížení automaticky vybírá ten nejvhodnější (tedy ten, u kterého je hloubka vybrané části nejmenší).

28


Vzhled vnořených řezů

V případech, kdy je vnitřní část překryta větším množstvím dalších objektů, je potřeba upravit rozměr jednotlivých automaticky vytvořených řezů tak, aby se jejich velikost směrem od zobrazované vnitřní části k pozorovateli kaskádovitě zvětšovala. Bez této vlastnosti by z ilustrace nebylo patrné, která geometrie musela být odstraněna a pozorovatel by jen velmi obtížně rozeznal vnitřní strukturu.

Obrázek 10: Příklad zobrazení vnořených řezů [CUTAWAY07].


29

30

Kapitola 4. Analýza a návrh implementace

4 Analýza a návrh implementace Po podrobném prostudování používaných metod vizualizace vnitřní struktury komplexních 3D modelů, byl k implementaci vybrán systém [CUTAWAY07], popsaný v kapitole 3.3.2. Ačkoliv se autoři článku odkazují na již implementovanou aplikaci, její stažení není v současné době možné a lze se domnívat, že nebude volně dostupná ani v budoucnu.

Mezi hlavní výhody navrhovaného řešení patří rychlé automatické generování řezů, které vychází z dat dodatečně zadaných uživatelem. Tato dodatečná anotace modelu je však velice intuitivní a rychlá, první ilustrace 3D modelu tak lze získat v relativně krátkém čase. Další nespornou výhodou je i plně interaktivní uživatelské rozhraní, umožňující prohlížení modelu a vytváření ilustrací vybraných částí v reálném čase.

Mezi nevýhody patří především složitá implementace a také skutečnost, že metoda nefunguje zdaleka na každém obecném 3D modelu. Při jeho tvorbě se tedy musí brát v úvahu některé zásady, které jsou popsány níže. Dalším problémem je nutnost použít systém pro konstruktivní geometrii (CSG), který umí pracovat v reálném čase. Tím by se významně zvýšili hardwarové nároky a proto bude v této práci navrženo vlastní řešení pro zobrazování řezů, které rovněž funguje v reálném čase a dosahuje stejného vizuálního výsledku jako CSG systém.

Požadované parametry 3D modelu: •

model se musí skládat z několika různých vzájemně oddělených částí

•

každá část musí být „vyrobitelná“ (manifold). Nesmí se například vyskytovat stěny nulové tloušťky.

•

každá část by se měla podobat jednomu ze základních geometrických tvarů, které jsou popsány v kapitole 3.3.2.


31

4.1 Shrnutí hlavních rysů zvolené metody Systém navržený v [CUTAWAY07] je určen k zobrazení vnitřní struktury komplexních 3D modelů pomocí řezů, které odstraňují překrývající geometrii vnějších částí. Řezy jsou vytvářeny automaticky na základě dat poskytnutých tvůrcem ilustrace. Následně je možné pomocí interaktivního rozhraní vybírat jednotlivé části 3D modelu, které mají být viditelné.

Vstupní data, která poskytuje tvůrce ilustrace: •

3D model

•

úhly pohledu

•

přiřazení geometrické reprezentace jednotlivým částem 3D modelu

Tvůrce ilustrace definuje úhly pohledu na model proto, aby bylo možné vytvořit tzv. graf viditelnosti. Ten ukládá informace o vzájemném překrývání částí modelu a je nezbytný pro výpočet řezů (pozice a velikost řezu je závislá na směru pohledu pozorovatele).

Přiřazování geometrické reprezentace tvoří základní pilíř popisované metody, neboť způsob vytvoření řezu na jednotlivých částech 3D modelu je závislý na jejich tvaru (viz. kapitola 3.3.2). Tvůrce ilustrace tedy musí projít každou část modelu a podle jejího tvaru k ní přiřadí některou z geometrických reprezentací (například kvádr nebo válec).

Interaktivní rozhraní poté umožní výběr jedné nebo více částí, které se poté pomocí řezů zviditelní. Úhel pohledu je vybrán tak, aby byl obsah informace v ilustraci co možná největší. Rozhraní umožňuje i prohlížení výsledné ilustrace pomocí pohybu kamery (funkce rotace, zoom, posun), ovšem tyto změny již nemají vliv na pozici řezů.

32


4.2 Analýza rozhraní systému Dosud uvažovaný model pro rozhraní předpokládal pouze jednu uživatelskou roli: tvůrce ilustrace. Šlo o osobu, jenž vytváří ilustraci určitého 3D modelu pomocí počítačového systému. Vzhledem k interaktivnímu uživatelskému rozhraní v navrhovaném systému je však vhodné tuto roli rozdělit na dvě, z nichž každá se vyskytuje na opačném konci procesu tvorby ilustrace (viz. obrázek 13).

První role se opět jmenuje tvůrce ilustrace, ovšem tentokrát má na starosti pouze vybavení 3D modelu dodatečnými informacemi, potřebnými k automatickému generování řezů. Interaktivní prohlížení výstupu je nyní práce pro uživatele systému, jemuž je poskytována hotová 2D ilustrace. Interaktivním prohlížením se rozumí především možnost zvolil konkrétní část 3D modelu, kterou považuje za důležitou a která mu pak bude zobrazena pomocí automaticky generovaných řezů. Úhel pohledu bude zvolen automaticky nejlepší z množiny pohledů definovaných tvůrcem ilustrace. Přesto má ale uživatel možnost manipulace s kamerou a může tedy směr pohledu měnit, tato změna ale už nebude mít vliv na vytvořené řezy.

Obrázek 11: Diagram znázorňující strukturu systému pro automatické generování řezů.


33

4.2.1 Proces tvorby ilustrace Proces tvorby ilustrace začíná v okamžiku, kdy má tvůrce ilustrace k dispozici hotový 3D model splňující podmínky definované v úvodu této kapitoly. Ten je poté předán systému, konkrétně části renderer, která má na starosti vykreslování scény. Práce tvůrce ilustrace pokračuje výběrem vhodných úhlů pohledu, pro které bude vypočítán graf viditelnosti. Také je potřeba projít jednotlivé části modelu a přiřadit jim vhodnou geometrickou reprezentaci. Obě tyto činnosti jsou prováděny prostřednictvím rozhraní pro vybavení modelu, které poté takto získané dodatečné informace o scéně poskytne dalšímu bloku systému – generátoru řezů.

Obrázek 12: Přiřazování geometrické reprezentace jednotlivým částem modelu. Obrázek pochází z prezentačního videa k článku [CUTAWAY07].

4.2.2 Prohlížení ilustrace Uživatel systému již nepřichází do styku s rozhraním pro vybavení modelu a namísto toho pracuje s generátorem řezů. Jemu posílá informaci o vybraných částech 3D modelu, které si přeje zobrazit. Generátor řezů na jejich základě automaticky vybere nejvhodnější úhel pohledu a provede výpočet potřebných řezů. Data o řezech poté předá rendereru, který je použije k vykreslení výsledné ilustrace. Uživatel systému má rovněž možnost přistupovat i k rendereru a měnit parametry kamery přímo. Řezy jsou ale již vypočítány a změna směru pohledu na ně tedy nemůže mít žádný vliv.

34


4.3 Analýza a návrh implementace ilustračních konvencí Tato kapitola se věnuje analýze a návrhu implementace jednotlivých konvencí pro generování ilustrací. Bude zde vysvětleno, jakým způsobem se provádějí řezy objekty v závislosti na geometrickém tvaru, který jim byl přiřazen, jakým způsobem se sestavuje a využívá graf viditelnosti a v neposlední řadě též metoda pro výběr nejlepšího úhlu pohledu na scénu.

4.3.1 Geometrická reprezentace objektu Vzhled řezů je závislý na tvaru objektu, na kterém má být zobrazen. Na základě rozboru ručně kreslených ilustrací byly popsány čtyři základní způsoby provedení řezu: obdélníkový, klínový, příčný a geodetický výřez.

Který z těchto výřezů je vhodnější pro kterou část 3D modelu určuje tvůrce ilustrace přiřazením vhodné geometrické reprezentace jednotlivým částem 3D modelu, na jejímž základě je pak prováděn výpočet řezů. Důvodem k zavedení geometrické reprezentace je, že díky ní již generátor řezů ke své činnosti nepotřebuje přístup k 3D modelu (pozice a tvar řezů je vypočítán jen za základě této reprezentace).

Jednotlivým částem 3D modelu lze přiřadit jednu z následujících geometrických reprezentací: •

obdélník – pro vytvoření řezu bude použit obdélníkový výřez

•

válec – pro vytvoření řezu bude použit klínový výřez

•

kostra – bude použit příčný výřez

•

složitý povrch – bude použit geodetický výřez


35

Geometrická reprezentace „obdélník“

Tato reprezentace vlastně nahrazuje objekt jeho orientovaným obalovým boxem. Orientace může být vypočítána buď automaticky systémem pomocí tzv. PCA analýzy souřadnic jeho vrcholů nebo zadána ručně prostřednictvím rozhraní pro vybavení modelu tvůrcem ilustrace. Orientace, pozice a velikost obalového boxu tvoří tzv. konstanty geometrické reprezentace (jedná se o hodnoty, které se při výpočtu řezů již nemění).

Pro objekty tohoto tvaru byl jako nejvhodnější způsob provedení řezu zvolen obdélníkový výřez, jehož orientace je shodná s orientací geometrické reprezentace. Pro zobrazení výřezu stačí určit intervaly na základních osách, udávající odkud a kam má výřez sahat. Rozsah intervalů je dán od 0 do 1, kde 0 značí počátek a 1 konec objektu na dané ose (ve 3D jsou tedy potřeba 3 intervaly). Tyto intervaly dohromady tvoří tzv. parametry výřezu, což je označení používané i u všech dalších geometrických reprezentací k definici všech proměnných, podle kterých je počítán výřez a které se při každém novém výpočtu řezů mění (v závislosti na požadované části 3D modelu, která má být zobrazena).

Obrázek 15: Obdélníkový výřez je orientován stejně jako geometrická reprezentace objektu [CUTAWAY07].

36


Výpočet parametrů výřezu je prováděn pokaždé, když uživatel systému změní svůj výběr částí 3D modelu, které mají být viditelné. Graf viditelnosti zajistí, že každé geometrické reprezentaci je předán orientovaný obalový box všech částí modelu, které se nalézají (pro daný úhel pohledu) za ní. Souřadnice těchto obalových boxů se poté spolu s pozicí kamery převedou do souřadného systému geometrické reprezentace, kde se z nich vytvoří nový osově orientovaný obalový box, jehož rozměry odpovídají hledaným parametrům ořezávání (viz. obrázek 16).

Obrázek 16: Ukázka výpočtu parametrů výřezu pro obdélníkovou geometrickou reprezentaci (pro zjednodušení ve 2D). Čárkovaně je naznačen osově orientovaný obalový box vnitřní části a kamery, který ve skutečnosti tvoří požadovaný obdélníkový výřez.

K implementaci obdélníkového výřezu je použita metoda ořezávacích rovin. Pro každou stěnu výřezu se v generátoru řezů, na základě parametrů geometrické reprezentace, vypočítá jedna obecná rovnice roviny. Rovnice se poté předají do rendereru, kde se provede vykreslení příslušné části 3D modelu. Pomocí shaderu jsou z ní ale zahozeny všechny fragmenty nalézající se před těmito ořezávacími rovinami (fragment je odstraněn jen když se nalézá před všemi ořezávacími rovinami současně). Bližší popis funkce shaderů pro odstraňování překrývající geometrie se nalézá v příslušné kapitole této práce.


37

Geometrická reprezentace „válec“

Konstanty této geometrické reprezentace tvoří, stejně jako u obdélníku, pozice a orientace. Místo velikosti na jednotlivých hlavních osách jsou ale u válce použity hodnoty výšky a poloměru. Výpočet konstant

lze provést opět automaticky pomocí PCA analýzy, v

takovém případě ale musí být stanoven nějaký způsob, jak určit hlavní osu válce (výstupem PCA analýzy je pouze orientační matice, kterou tvoří tři rovnocenné bázové vektory). Jednou z možností je například sestrojení všech tří možných obalových válců a poté výběr toho s nejmenším objemem. Rozhraní pro vybavení modelu rovněž poskytuje nástroj pro ruční zadání hlavní osy (pro případy, kdy automatický výpočet selže).

Obrázek 17: Klínový výřez na objektu reprezentovaném válcem [CUTAWAY07].

Pro tuto geometrickou reprezentaci byl pro vizualizaci vnitřní struktury zvolen klínový výřez. Parametry výřezu tvoří interval na hlavní ose válce, který udává pozici bočních stěn (ty jsou kolmé na hlavní osu) a dva úhly udávající orientaci horní a dolní stěny (ty na hlavní ose válce leží). Parametry úhlů mohou nabývat hodnot od nuly do 2π, interval na hlavní ose je opět omezen na hodnoty od nuly do jedné. Implementace výřezu je, stejně jako v předchozím případě, založena na ořezávacích rovinách. Tentokrát je jich ale potřeba méně – pouze čtyři.

38


Výpočet parametrů výřezu je u válce poněkud obtížnější, než tomu bylo u obdélníku. Je to dáno složitým způsobem výpočtu úhlů rozevření klínu, které musí být tak velké aby byl vnitřní objekt vidět celý. Parametry bočních stěn jsou pak určeny stejným způsobem jako u obdélníku. Rovněž je potřeba rozlišit situaci, kdy leží vnitřní objekt uvnitř válce a kdy až za ním. Ve druhém případě je situace vyřešena jednoduše tím, že se horní a dolní stěna klínu vynechá a použijí se pouze stěny boční, čímž vznikne dojem obdélníkové výseče (stejně se postupuje i když je objekt částečně uvnitř válce a částečně venku).

V případě, že je vnitřní objekt skutečně celý uvnitř válce, je potřeba přistoupit k výpočtu úhlů horní a dolní stěny. Situace je naštěstí usnadněna faktem, že se jedná o dvourozměrný problém, třetí rozměr klínu totiž tvoří parametr na hlavní ose válce a ten je již vypočítán. Prvním krokem je opět převedení souřadnic orientovaného obalového boxu vnitřního objektu a pozice kamery do souřadnic válce. Z nich se poté odstraní rozměr odpovídající ose válce, čímž je proces transformace do 2D dokončen. Nyní je nezbytné provést výpočty průsečíků mezi kružnicí reprezentující okraj válce a vektory od kamery k jednotlivým bodům vnitřního obalového boxu. K průsečíkům se nakonec vypočítají úhly od kladné osy X a seřadí se od nejmenšího k největšímu. Nejmenší a největší úhel tvoří hledané parametry klínu (viz. obrázek 18).

Obrázek 18: Příklad výpočtu úhlů klínu. Napřed se naleznou průsečíky mezi přímkami od kamery k vrcholům obalového boxu vnitřního objektu a okrajem válce (vlevo), poté se k průsečíkům vypočítají úhly (od kladné osy X). Nejmenší a největší úhel tvoří minimální možný rozsah klínu, při kterém je ještě vidět celý vnitřní objekt.


39

Geometrická reprezentace „kostra“

Geometrickou reprezentaci kostrou je vhodné zvolit u objektů, jejichž tvar připomíná dlouhou, zakroucenou trubici (například různé pružiny, potrubí, cévy atd...). Výřez se provádí na určitém intervalu délky této kostry a jeho okraje jsou na ní kolmé. Konstanty reprezentace objektu kostrou jsou tedy pozice a tloušťka jednotlivých segmentů kostry a její celková délka.

Výpočet kostry lze provést mnoha způsoby, některé používané metody bývají založeny na kolapsu geometrie, jiné na konstrukci Reebova grafu. V této práci byla ale zvolena metoda založená na tvaru povrchu, neboť implementované funkce budou užitečné i pro výpočet geodetického výřezu. Zvolená metoda je popsána v článku [SKEL97] a bude vysvětlena v některé z dalších kapitol.

Obrázek 19: Příčný výřez je definován parametrem od 0 do 1. Jeho stěny jsou vždy kolmé na kostru modelu v daném místě [CUTAWAY07].

Parametry výřezu jsou pro tuto geometrickou reprezentaci nejjednodušší. Tvoří je pouze jediný interval, udávající odkud a kam až sahá příčný výřez. Jako i v minulých případech, je jeho rozsah od nuly do jedné, kde nula reprezentuje počátek kostry modelu a jedna její konec. Výpočet intervalu je proveden na bázi jednotlivých segmentů, kdy se pro každý z nich určí, jestli leží na cestě mezi kamerou a vnitřním objektem. Poté se najde první a poslední takto „překážející“ segment a všechna geometrie mezi nimi se odstraní.

40


Implementace příčného výřezu opět využívá ořezávacích rovin, ty ale tentokrát musejí být definovány pro jednotlivé segmenty kostry samostatně. Problematika zobrazení výřezu lze rozdělit na dva dílčí podproblémy: •

zobrazení jen některých segmentů kostry (některé segmenty jsou vidět, jiné ne)

•

částečné zobrazení jednoho segmentu (stěna výřezu se při animaci plynule pohybuje, může se tedy nalézat i uprostřed segmentu)

Zobrazení jen určitých segmentů kostry je řešeno pomocí šesti ořezávacích rovin, které obklopují celý segment. Jedná se tedy o orientovaný obalový box, definovaný pro každý segment zvlášť. V ořezávacím shaderu je ale potřeba invertovat podmínku vyhodnocující zahazování fragmentů, neboť v tomto případě je potřeba fragmenty před rovinami ponechat a naopak zahodit vše ostatní. Je rovněž nezbytné zajistit, aby na sebe boční stěny obalů navazovaly (například pravá stěna prvního segmentu musí mít stejnou orientaci jako levá stěna druhého segmentu).

Částečné zobrazení jednoho segmentu je řešeno pomocí pohybu jedné z krajních ořezávacích rovin jeho obalového boxu (to jsou ty, které protínají kostru modelu). Při tomto přesunutí ale musí proběhnout interpolace její orientace, aby byl pohyb výřezu spojitý. Díky těmto interpolacím je stěna výřezu zdánlivě kolmá na skutečný tvar objektu, nikoliv na osu konkrétního segmentu.

Nevýhodou popsaného přístupu je především nutnost opakovaného vykreslování ořezávané části 3D modelu, která je kostrou reprezentována. Pro každý viditelný segment je totiž nutné ji vykreslit znova, jen s použitím jiných ořezávacích rovin. Dalším problémem je rovněž situace, kdy obě stěny výřezu při animaci procházejí stejným segmentem. V případě posunutí obou krajních ořezávacích rovin totiž zůstane zobrazen prostředek segmentu, tedy ta část, která by naopak měla být odstraněna. Tento problém je v implementované aplikaci vyřešen odstraněním celého segmentu (opět invertovat podmínku pro zahazování fragmentů v shaderu nelze, neboť zbylé ořezávací roviny by pak neplnily svojí funkci).


41

Geometrická reprezentace „složitý povrch“

Všechny předchozí popisované geometrické reprezentace měli jednu základní společnou vlastnost. Při přiřazení části 3D modelu tvůrcem ilustrace

se provedl výpočet jejich

konstant a při výběru požadovaných viditelných částí uživatelem systému se vypočítali parametry výřezu. U geometrické reprezentace složitých povrchů to již tak docela neplatí, neboť při výpočtu konstant je potřeba vzít v úvahu i definované úhly pohledu a předpočítat si parametry výřezu pro všechny vnitřní objekty. V okamžiku, kdy si uživatel vybere nějakou vnitřní část 3D modelu se reprezentaci povrchu předá jen její jméno a parametr výřezu se vezme z předem vytvořené tabulky.

Důvodem k předpočítání je závislost parametru výřezu na skutečném tvaru modelu, bez něj by tedy došlo k eliminaci hlavní výhody používání geometrických reprezentací. Dalším důvodem je i fakt, že výpočet tohoto parametru je časově velice náročný (čas výpočtu roste lineárně s počtem vrcholů 3D modelu) a uživatelská část aplikace by pak nemusela být schopna práce v reálném čase.

U této geometrické reprezentace je pro zobrazení vnitřních částí 3D modelu použit tzv. geodetický výřez. Využívá se metoda odstranění překrývající geometrie na základě geodetické vzdálenosti na povrchu objektu. Parametrem výřezu je jediná hodnota, která udává jak daleko od jeho středu se budou zahazovat fragmenty.

Obrázek 20: Geodetický výřez na složitém povrchu. [CUTAWAY07].

42


K implementaci geodetického výřezu bude potřeba navrhnout nový shader, neboť použití ořezávacích rovin již není možné (výřez může mít libovolný nekonvexní tvar). Základem jeho funkce bude předávání vypočtené vzdálenosti od středu výřezu každému vrcholu 3D modelu. Shader poté tuto hodnotu interpoluje pro každý fragment a porovná s požadovanou velikostí výřezu. Pokud je vzdálenost menší než velikost výřezu, bude fragment zahozen. Více o implementaci tohoto shaderu je napsáno v příslušné kapitole.

Konstanty výřezu musí být vypočteny pro každý úhel pohledu zvlášť a jsou tvořeny tabulkou přiřazující hodnoty geodetických vzdáleností od středu výřezu k identifikátorům jednotlivých vrcholů 3D modelu. Dále je nutné uchovat informaci o všech vnitřních částech modelu a pro každou předpočítat potřebnou velikost výřezu, která je nezbytná k jejímu úplnému zobrazení.

Konstanty geodetického výřezu Viewpoint 1

předpočítaná data

Viewpoint 2


Viewpoint n


Předpočítaná data Vertex 1 vzdálenost Vertex n

vzdálenost

Mesh 1

velikost výřezu

Mesh n

velikost výřezu

Obrázek 21: Vlevo se nalézá ilustrace znázorňující strukturu dat geometrické reprezentace složitého povrchu. Vpravo je zobrazena struktura předpočítaných dat pro každý pohledový úhel (viewpoint).

Postup pro výpočet konstant pro jeden úhel pohledu je tedy následující: •

Určení středu výřezu.

•

Výpočet geodetických vzdáleností od středu výřezu k jednotlivým vrcholům 3D modelu.

•

Výpočet minimální potřebné velikosti výřezu pro zobrazení jednotlivých vnitřních částí.


43

Střed výřezu je určen na základě pozic a obalových boxů jednotlivých vnitřních částí tak, aby byl přibližně uprostřed. Rozhraní pro vybavení modelu však tvůrci ilustrace umožňuje zadat vlastní souřadnice středu pomocí kliknutí myši na požadované místo na povrchu. Poté co je střed určen je potřeba vypočítat geodetické vzdálenosti. Tato problematika je ale popsána v jiné kapitole a proto zde bude popis tohoto kroku přeskočen.

V okamžiku, kdy je určen střed výřezu a vzdálenost od něj k jednotlivým vrcholům modelu, lze přistoupit k výpočtu minimální nezbytné velikosti výřezu pro zobrazení vnitřních částí. To se provádí pomocí hledání průsečíků mezi trojúhelníky tvořícími povrch modelu a mezi přímkami od kamery k okrajům obalového boxu vnitřní části. Pro každý nalezený průsečík se určí jeho geodetická vzdálenost od středu výřezu (pomocí interpolace vzdáleností vrcholů trojúhelníku) a vybere se ten nejvzdálenější. Jeho vzdálenost je pak i minimální potřebná velikost výřezu, která zajistí zobrazení celé vnitřní části.

Obrázek 22: Výpočet rozsahu geodetického výřezu pro vnitřní část modelu (červená). Tlustá černá čára reprezentuje vnější povrch, tenká čárkovaná čára střed výřezu.

Nevýhodou popisovaného přístupu je především výrazně vyšší paměťová náročnost, neboť je potřeba pro každý pohledový úhel uchovávat velké množství dat o vzdálenostech vrcholů. Implementovaná aplikace tento nedostatek částečně obchází tím, že si pamatuje jen vzdálenosti těch vrcholů, které se nalézají v rozsahu největšího možného výřezu.

44


4.3.2 Úhly pohledu Pro dosažení kvalitní automaticky generované ilustrace je v popisovaném systému nezbytné, aby tvůrce ilustrace stanovil několik vhodných úhlů pohledu na scénu. Z nich pak bude při interaktivním prohlížení uživatelem systému automaticky vybrán ten, který poskytuje nejlepší výhled na zkoumanou část 3D modelu. Důvodem existence úhlů pohledu je, že při generování řezů je potřeba znát přesné pořadí, v jakém se jednotlivé části 3D modelu překrývají. Toto pořadí je uloženo v tzv. grafu viditelnosti, který se vytváří pouze právě pro tyto zadané pohledové úhly (vytvoření grafu je časově náročné a není ho tedy možné provádět pro libovolný směr pohledu při prohlížení ilustrace).

Graf viditelnosti

Graf viditelnosti je orientovaný acyklický graf, jehož uzly reprezentují jednotlivé části 3D modelu a hrany udávají jejich vzájemné překrývání. Následující postup pro jeho vytvoření je převzat z článku [CUTAWAY07].

Před sestavením grafu se nejprve provádí rozdělení částí modelu do viditelných vrstev. Každá část bude přiřazena do určité vrstvy na základě toho, kolik jiných částí je potřeba odebrat pro její úplné zobrazení. Algoritmus, který toto provádí, je založen na víceprůchodovém renderování. Na začátku inicializuje množinu S, do které vloží všechny části 3D modelu. Poté se opakují tyto tři kroky, dokud není každá z částí přiřazena k nějaké vrstvě: 1. Vykreslení všech částí z množiny S 2. Vytvoření nové vrstvy, která bude obsahovat všechny viditelné části z S 3. Odstranění všech viditelných částí z S a opakování od bodu 1.

Viditelnost jednotlivých části se provádí výpočtem poměru počtu zobrazených pixelů po vykreslení množiny S a počtu zobrazených pixelů při vykreslení části samotné. V případě, že žádná část není úplně viditelná, dojde k odebrání té, která má tento poměr největší.


45

Sestavení grafu pak probíhá tak, že pro každou část v 3D modelu systém postupně prochází vyšší vrstvy viditelnosti a hledá objekty, které tuto část přímo překrývají. Pokud toto překrytí přesáhne jistou mez (navrhovaná hranice je 20%), vytvoří se mezi částmi hrana v grafu viditelnosti.

Obrázek 23: Příklad sestavení vrstev viditelnosti (uprostřed) a grafu viditelnosti (vpravo) z 3D modelu vlevo. [CUTAWAY07].

Algoritmus pro sestavení grafu viditelnosti na základě vrstev viditelnosti, tak jak je navržen v článku [CUTAWAY07] by ale byl velice pomalý. Pro každou část modelu by se totiž muselo provést tolik vykreslování, kolik částí se nalézá ve vyšších vrstvách viditelnosti. Proto byl pro sestavení grafu použit jiný přístup, jenž je výrazně rychlejší.

Základem je vykreslení všech částí v jedné vrstvě do společné textury (pro každou vrstvu tedy vznikne jedna textura) a sestavení tabulky překrytí. Tato tabulka udává, kolik pixelů si vzájemně části 3D modelu překrývají. Nejprve se vezme textura první a druhé vrstvy a pro každou dvojici korespondujících pixelů se provádí následující dva kroky: 1. Vyhodnocení, zda pixel objektu z první vrstvy překrývá pixel nějakého objektu z druhé vrstvy (pokud ano, uloží se tato informace v tabulce překrytí) 2. Sloučení textur vrstev. Pokud je pixel druhé textury prázdný (nenachází se zde žádný objekt), bude do něj zkopírována informace z první textury.

46


Poté se provede vyhodnocení tabulky překrytí a sestavení grafu viditelnosti mezi objekty první a druhé vrstvy. Nakonec se celý popsaný postup opakuje znova, tentokrát pro texturu vzniklou sloučením první a druhé vrstvy a texturu třetí vrstvy. Po zopakování pro všechny ostatní vrstvy vznikne hledaný graf viditelnosti.

Automatický výběr nejlepšího úhlu pohledu

Určení, který směr pohledu je nejlepší pro vybranou množinu částí 3D modelu, je řešeno definováním proměnné energie pohledového úhlu. Tato energie je vypočítána na základě průměrné hloubky vnitřních částí v grafu viditelnosti a na jejich součtu pixelů, který zaberou ve výsledné ilustraci. Čím je energie větší, tím složitější je provést zobrazení vnitřní struktury. V článku [CUTAWAY07] byl definován následující vzorec:

E v =2ov 

Amax−a v Amax

kde Ev je energie pohledového úhlu, ov je průměrná hloubka částí v grafu viditelnosti, av je počet pixelů, které na obrazovce zabírají vybrané části a Amax je normalizační konstanta, udávající celkový počet pixelů obrazovky.

4.3.3 Vnořené řezy Efekt kaskádovitého zvětšování vnořených řezů, jak je popsán v kapitole 3.3.2, lze implementovat velmi jednoduchým způsobem. Stačí zavést novou proměnnou offset, která se předá jednotlivým geometrickým reprezentacím společně s odkazem na obalový box vnitřní části při výpočtu řezu. Podle její hodnoty se pak vypočtená velikost výřezu zvětší. Určení hodnoty offsetu probíhá na základě rozdílu hloubky vnitřní a ořezávané části 3D modelu v grafu viditelnosti (čím větší rozdíl v hloubce, tím větší je hodnota offsetu).


47

4.4 Vytvoření kostry modelu Nalezení kostry 3D modelu je potřeba implementovat kvůli geometrické reprezentaci „kostra“, která je na tomto založena. Po prozkoumání několika používaných metod byl nakonec k implementaci vybrán článek [SKEL97], který problém řeší pomocí analýzy geometrie povrchu. Vstupem popsaného algoritmu je pouze množina vrcholů 3D modelu a požadovaný počet částí (kostí), ze kterých se má kostra skládat.

Po přihlédnutí k charakteru celého implementovaného systému však bylo potřeba provést některé menší změny. Především je nutné zakázat větvení kostry, neboť geometrická reprezentace s touto možností nepočítá. Dále bylo provedeno jedno vylepšení, kdy výpočet kostry bere v úvahu i hrany 3D modelu. Tímto došlo k výraznému zvýšení úspěšnosti algoritmu na objektech s nerovnoměrně rozmístěnými vrcholy.

Činnost algoritmu pro vytvoření kostry tvořené k částmi lze rozdělit do následujících čtyř fází: 1. Vytvoření grafu sousedů z vrcholů 3D modelu 2. Určení počátečního vrcholu a vytvoření geodetického grafu 3. Rozdělení vrcholů do k úrovní podle vzdálenosti od počátku 4. Výpočet spojů (kloubů) kostry

Obrázek 24: Jednotlivé fáze algoritmu pro nalezení kostry modelu z množiny jeho vrcholů. [SKEL97] .

48


V první fázi algoritmus vytvoří graf sousedů na vrcholech 3D modelu. Pro každý vrchol najde jeho n nejbližších sousedů a přidá k nim hranu v grafu. Počet nejbližších sousedů n zadává uživatel. Čím je hodnota menší tím větší je riziko, že graf nebude spojitý. Naopak velké hodnoty n celý výpočet výrazně zpomalí. Implementovaná aplikace snižuje riziko nespojitosti grafu tím, že do grafu sousedů přidá i hrany trojúhelníků z 3D modelu. Pro výpočet geodetického grafu je nezbytné nejprve určit jeho počáteční uzel. K tomuto účelu byla použita jednoduchá heuristika, která náhodně vybere jeden z uzlů grafu sousedů a k němu najde nejvzdálenější protějšek. Výpočet grafu je pak již jednoduchý, stačí ohodnotit hrany v grafu sousedů podle jejich skutečné délky a od nalezeného nejvzdálenějšího uzlu zahájit prohledávání Dijkstrovým algoritmem. Dijkstrův algoritmus určí pro každý uzel grafu jeho vzdálenost od počátku. Podle této vzdálenosti se nyní provede rozdělení uzlů do k skupin, kde geometrický střed každé skupiny odpovídá jednomu spoji (kloubu) kostry.

Nejnáročnější částí celého výpočtu je sestavení grafu sousedů, jehož asymptotická složitost dosahuje hodnoty O(n2). Kvůli urychlení této fáze algoritmu byla implementována metoda prostorového dělení do 3D mřížky.

Tím je výpočet kostry podle [SKEL97] dokončen, avšak kvůli specifickým potřebám implementovaného systému je potřeba provést ještě dva další dodatečné kroky. Prvním z nich je určení tloušťky každé části (segmentu) kostry, aby mohla geometrická reprezentace správně vypočítat pozici okrajových ořezávacích rovin. To je provedeno pomocí tohoto postupu, který se opakuje pro každý segment kostry: 1. sloučení obou skupin uzlů tvořící okrajové klouby segmentu 2. nalezení a odebrání těch uzlů, které patří do jiného segmentu 3. nalezení nejvzdálenějšího uzlu od spojnice obou kloubů segmentu

Vzdálenost tohoto uzlu pak tvoří hledanou tloušťku segmentu. Druhým dodatečným krokem je prodloužení prvního a posledního segmentu tak, aby obsáhly všechny uzly v okrajových skupinách (kostra totiž začíná a končí uprostřed těchto skupin uzlů).


49

4.5 Geodetické vzdálenosti Geodetickou vzdáleností je myšlena nejkratší možná cesta mezi dvěma vrcholy 3D modelu po jeho povrchu. V případě geodetického výřezu je ale potřebné nalézt geodetickou vzdálenost mezi středem a všemi ostatními vrcholy. Tento výpočet lze provést exaktně pomocí tzv. Fast Marching algoritmu. Ten je ale relativně pomalý a příliš náročný na implementaci, proto byla zvolena heuristická metoda, založená na dělení hran.

Nejprve se sestaví neorientovaný graf, jehož uzly a hrany jsou odvozeny z 3D modelu (podobně jako v předchozí kapitole). V grafu se poté najde nejdelší vyskytující se hrana a její délka se vydělí konstantou dělení (čím je konstanta větší, tím je aproximace přesnější). Takto získaná hodnota se poté porovnává s délkou ostatních hran v grafu. Je-li hrana delší, bude rovnoměrně rozdělena na tolik částí, aby délka ani jedné z nich této hodnoty nedosáhla. Při rozdělování vznikají nové uzly, které je nutné hranami vhodně napojovat do již existující struktury.

Na závěr je na takto upraveném grafu proveden Dijkstrův algoritmus. Ačkoliv počítá pouze topologické vzdálenosti, díky popsanému rozdělení hran je chyba oproti reálným geodetickým vzdálenostem pouze konstantní.

Obrázek 25: Ukázka dělení hran. Levý obrázek ukazuje původní trojúhelník. Na druhém obrázku došlo k rozdělení první hrany na tři části. Na třetím k rozdělení druhé hrany na dvě části (je totiž kratší). Vpravo je ukázán konečný stav (pro konstantu dělení rovnou dvěma).

50


4.6 Ořezávací shadery Poté, co generátor řezů předá vypočtené informace o jednotlivých řezech rendereru, je potřeba vhodným způsobem zajistit vykreslení ořezaných částí 3D modelu. V této kapitole budou popsány dva programy pro grafickou kartu - shadery, z nichž jeden je založen na využití ořezávacích rovin (používá se pro obdélníkový, klínový a příčný výřez) a druhý na vzdálenostech vrcholů (používá se pro geodetický výřez).

4.6.1 Ořezávání rovinami Cíl navrhovaného shaderu je na první pohled jednoduchý – na základě zadaných obecných rovnic ořezávacích rovin odstranit požadované fragmenty. Takové ořezávání je již na úrovni grafického hardwaru implementováno (například pomocí funkce glClipPlane v OpenGL), nabízí se tedy otázka, proč vymýšlet vlastní řešení. Důvodem je především potřeba realizovat konvence řezů popsané v kapitole 3.3.1, v případě implementované aplikace se jedná především o vyplňování vnitřních stěn. Použití vlastních shaderů ale otevírá cestu i pro další efekty, jako například zobrazení nepravidelných okrajů řezů.

Pro každý vykreslovaný fragment je tedy nutné provést tyto operace (a v tomto pořadí): 1. otestování, zda fragment nemá být zahozen 2. pokud ne, otestování zda netvoří vnitřní stěnu 3. pokud ano, vyplnění vnitřní stěny

První krok je nejjednodušší. Jediné co je potřeba vypočítat je skalární součin mezi pozicí fragmentu a zadanými obecnými rovnicemi rovin. Výsledek těchto operací udává vzdálenost fragmentu od rovin. Pokud je ve všech případech kladný, fragment se bude zahazovat (tato podmínka ale musí být pro příčný výřez invertována, viz. příslušná kapitola). Důležité je také zajistit, aby jak zadané rovnice, tak pozice fragmentu byly transformovány do stejné souřadné soustavy.


51

Vyhledávání vnitřních stěn je rovněž poměrně snadné. Je založeno na výpočtu úhlu mezi normálou fragmentu a vektorem od fragmentu ke kameře. Pokud je tento úhel větší než 90 stupňů, jde o vnitřní stěnu. Zobrazovaný 3D model ale musí mít korektně definované normálové vektory, jinak metoda nebude pracovat správně.

Obrázek 26: Příklad detekce vnitřních stěn. Vlevo je naznačena pozice řezu. Uprostřed je již provedeno ořezání a probíhá vykreslení fragmentu. Pokud je úhel mezi jeho normálou a vektorem ke kameře větší než 90 stupňů, jde o vnitřní stěnu a je potřeba provést vyplnění (vpravo).

V tomto okamžiku již došlo k ořezání a byl detekován odvrácený fragment. Zbývá tedy nakreslit stěnu ležící na ořezávací rovině, která vyplní vnitřek objektů. Toho se dosáhne změnou vzhledu dotyčného fragmentu tak, že mu bude nastaven nový normálový vektor (shodný s normálou ořezávací roviny). Vzhledem k tomu, že použitá stínovací metoda nebere v úvahu vzdálenost od kamery a světelný zdroj má s kamerou shodnou pozici, dosáhne se tím efektu, že fragment leží na ořezávací rovině (pozici fragmentu v z-bufferu netřeba řešit, neboť mezi vnitřní a vyplňující stěnou se stejně nemůže nalézat žádný jiný objekt).

Tento postup by byl velice snadno implementovatelný v případě jedné ořezávací roviny. V našem případě je ale potřeba počítat s jejich proměnlivým počtem. Tím se vynořuje nový problém, spočívající v určení konkrétní roviny, která ořezala fragmenty před momentálně zpracovávaným fragmentem. Vyřešení tohoto problému je nezbytné pro korektní zobrazování řezů v zobrazované scéně.

52


V případě, že chceme zachovat jednoprůchodový algoritmus, se jako nejlepší řešení jeví provést výpočet průsečíků mezi paprskem od kamery a všemi použitými rovinami. Rovina, která protne paprsek svou přivrácenou stranou nejdříve, je zároveň rovinou, která tvoří řez. Pro výpočet průsečíku mezi přímkou (paprskem) a rovinou se používá následující vzorec:

t=

P⋅C N⋅D

kde P jsou parametry obecné rovnice roviny, C je pozice kamery, N je normálový vektor roviny a D je směr paprsku. Parametr t udává vzdálenost průsečíku od kamery. V případě, že je jmenovatel zlomku roven nule, paprsek se s rovinou neprotíná (je paralelní). Pokud je nule roven i čitatel, paprsek na rovině leží.

4.6.2 Víceprůchodový algoritmus V průběhu implementace aplikace bylo zjištěno, že výše popsaný přístup k vyplňování řezu je svou rychlostí až příliš závislý na velikosti vyplňovaných částí (ve smyslu počtu pixelů na obrazovce). Například při zobrazování animací docházelo k velkému kolísání FPS, které na uživatele působilo rušivě. Byl proto navržen dvouprůchodový algoritmus, jenž je sice pro malý počet řezů mírně pomalejší, avšak jeho rychlost vykreslování u složitější scény je stabilnější.

První průchod provede vykreslení vystínovaných ořezávacích rovin (roviny se zobrazí jako polygony stejné barvy, jako má objekt) do 2D textury o stejném rozlišení, jako má obrazovka. Ve druhém průchodu jsou prováděny stejné operace, jako v jednoprůchodovém algoritmu, avšak v okamžiku detekce vnitřní stěny se místo výpočtu nového vzhledu fragmentu jednoduše převezme jeho konečná barva z textury (souřadnice v textuře odpovídají souřadnicím fragmentu na obrazovce).


53

4.6.3 Geodetický výřez Shader pro zobrazení geodetického výřezu již není založen na ořezávacích rovinách, ale na zadané geodetické vzdálenosti od středu výřezu. Při vykreslování geometrie modelu se jednoduše jednotlivým vrcholům kromě běžných parametrů (barva, normála) předají i předem vypočítané hodnoty vzdáleností od středu výřezu. Tyto hodnoty jsou pak na grafické kartě interpolovány pro jednotlivé fragmenty.

Při výpočtu ořezávání fragmentu tedy shaderu stačí pouze porovnat tyto vzdálenosti s požadovanou velikostí výřezu a v případě, že fragment leží blíže, se zahodí. Detekce vnitřních stěn pak probíhá stejným způsobem jako v případě ořezávacích rovin. Bohužel vystínování řezů již v tomto případě není možné (nelze určit normálu řezu). Řez je tedy pouze vyplněn stejnou barvou, jako má objekt. Při testování se ale ukázalo, že tato absence stínování nemá na výslednou ilustraci příliš velký vliv, neboť složité povrchy, pro které se geodetický výřez používá, bývají většinou velice tenké.

54

Kapitola 5. Implementace

5 Implementace K implementaci aplikace byl vybrán programovací jazyk JAVA a vývojové prostředí NetBeans. Tato volba zajišťuje především výbornou přenositelnost na různé operační systémy (testováno na GNU Linux a MS Windows). Pro přístup k OpenGL byla použita knihovna JOGL, jejíž hlavní předností je velká podobnost funkcí s knihovnami jazyka C. Výsledný program je založen na frameworku, jehož autorem je vedoucí této práce a který výrazně usnadňuje použití některých vlastností OpenGL v Javě.

5.1 Hlavní třídy aplikace Pří vývoji aplikace bylo implementováno velké množství tříd, ty základní zde budou popsány. Prvním objektem, který je po spuštění kódu vytvořen (samozřejmě mimo Main), je instance třídy ui. Tato třída má za úkol vytvoření uživatelského rozhraní a jeho navázání na jádro programu, tvořené třídou OpenGLListener. OpenGLListener obsahuje další klíčové třídy, a to Scene (ukládá veškeré potřebné informace o zobrazovaném 3D modelu), Viewer (zajišťuje pohyb kamery), Animator (vytváří hlavní vykreslovací smyčku) a ViewpointManager (správce pohledových úhlů). Komunikace mezi jádrem a uživatelským rozhraním je zajištěna pomocí vestavěné funkcionality JAVY, konkrétně tříd pro posílání a příjem zpráv (PropertyChangeSupport, PropertyChangeListener a PropertyChangeEvent).

Třída Scene obsahuje seznam jednotlivých částí 3D modelu, které jsou reprezentovány třídou Mesh. Třída Mesh je potomkem třídy Bbox (orientovaný obalový box) a ukládá informace o geometrii (třída MeshGeometry) a geometrické reprezentaci části (třída GeometricRepresentation). Geometrická reprezentace je abstraktní třída, jejímiž potomky jsou třídy Cube, WedgeTube, Skeleton a FreeformWindow, v závislosti na zvoleném typu výřezu.


55

MainMenu

Viewer

ToolBar Animator OpenGLListener

UI

StatusBar

Text Renderer

ObjectList

Viewpoint Manager

EditPanel BBox Occlusion Graph

MeshGeometry

Scene

Mesh

Viewpoint

Bounding Sphere

Geometric Representation

Cube

WedgeTube

Skeleton

FreeForm Window

Obrázek 27: Zjednodušený diagram tříd nejdůležitějších částí implementované aplikace.

56


5.2 Rozdělení programu do Java balíčků Pro větší přehlednost kódu byly třídy rozděleny do jednotlivých JAVA balíčků. Následující přehled popisuje účel a obsah každého z nich.

cutawayGen – základní balíček. Obsahuje třídu Main a elementární třídy aplikace. •

Main.java – třída Main. Pouze spouští program.

•

OpenGLListener.java – jádro aplikace, zajišťuje vykreslování pomocí OpenGL.

•

GeometricRepresentation.java – abstraktní třída geometrických reprezentací.

•

Cube.java – implementuje geometrickou reprezentaci obdélník.

•

WedgeTube.java - implementuje geometrickou reprezentaci válec.

FreeformWindow – balíček obsahuje třídy nezbytné k použití geodetického výřezu. •

FreeformWindow.java - implementuje geometrickou reprezentaci složitý povrch.

•

GeodesicGraph.java – vytváří geodetický graf a implementuje hledání geodetické vzdálenosti.

Skeleton - obsahuje třídy nezbytné k použití příčného výřezu. •

Skeleton.java - implementuje geometrickou reprezentaci kostra.

•

Voxel.java a Grid.java – rozdělují vrcholy 3D modelu do voxelů (kvůli rychlejšímu sestavení grafu sousedů).

•

NeighborGraph.java – vytváří graf sousedů.

•

GeodesicGraph.java – vytváří geodetický graf z grafu sousedů.

•

Branch.java a Level.java – vytvoření větví kostry z geodetického grafu.

•

Segment.java – reprezentuje jednotlivé výsledné segmenty kostry.


57

UI - balíček obsahuje jednotlivé třídy tvořící uživatelské rozhraní. •

ui.java – třída, která zajišťuje vytvoření uživatelského rozhraní.

•

SceneList.java – vytváří postranní seznam částí 3D modelu.

•

ToolBar.java – vytváří panel nástrojů pod hlavní nabídkou.

•

StatusBar.java – vytváří informační panel vespod okna.

•

EditPanel.java – vytváří místo na pravé straně okna pro nástroje na editaci geometrických reprezentací.

•

BasicPanel.java – pravý panel, který umí přiřazovat jednotlivé geometrické reprezentace vybraným částem 3D modelu.

•

CubeEditPanel.java – panel pro úpravu geometrické reprezentace obdélník.

•

WedgeEditPanel.java – panel pro úpravu geometrické reprezentace válec.

•

SkeletonEditPanel.java – panel pro úpravu geometrické reprezentace kostra.

•

WindowEditPanel.java –panel pro úpravu geometrické reprezentace složitý povrch.

•

FileMenu.java – třída implementuje nabídku File v liště hlavního menu.

•

SceneMenu.java – třída implementuje nabídku Scene v liště hlavního menu.

•

ObjectMenu.java – třída implementuje nabídku Object v liště hlavního menu.

•

ViewpointMenu.java – třída implementuje nabídku Viewpoint v liště menu.

•

DisplayMenu.java – třída implementuje nabídku Display v liště hlavního menu.

•

HelpMenu.java – třída implementuje nabídku Help v liště hlavního menu.

Graph – obsahuje pomocné třídy pro práci s grafy. •

Edge.java – hrana grafu.

•

Node.java – uzel grafu.

•

Graph.java – algoritmy pro práci s grafem (Dijksta, prohledávání do šířky, atd...).

58


Mesh.loaders – balíček zajišťuje načtení 3D modelu ze souboru. •

MtlLoader.java – načtení materiálů OBJ modelu.

•

ObjLoader – načtení geometrie OBJ modelu.

Mesh – třídy pro uložení informací o jednotlivých částech 3D modelu. •

Mesh.java – třída, která sdružuje informace o části 3D modelu.

•

Scene.java – informace o celém 3D modelu.

•

Bbox.java – vytváří orientovaný obalový box kolem geometrie 3D modelu.

•

MeshGeometry.java – geometrické informace.

•

Face.java – ukládá informace o jednotlivých polygonech

•

Vertex.java – informace o vrcholech 3D modelu

•

Vec4.java – třída reprezentující čtyřrozměrný vektor.

•

Appearance.java – vzhled polygonů.

•

PCA.java – třída pro výpočet PCA analýzy (k určení orientace obalových boxů).

Viewpoints – balíček zajišťuje vytváření a správu pohledových úhlů. •

ViewpointManager.java – účelem této třídy je spravovat jednotlivé pohledové úhly.

•

Viewpoint.java – informace o konkrétním pohledovém úhlu.

•

OcclusionGraph.java – graf viditelnosti pro pohledový úhel.

•

OcclusionGraphNode – uzel grafu vidtelnosti (odpovídá jedné části 3D modelu).

Gleem – balíček zajišťuje některé základní funkce OpenGL v Javě. •

BSphere.java – obalující koule kolem scény

•

ExamineViewer.java – třída zajišťující činnost kamery.


59

OpenGL – třídy pro práci s OpenGL. •

FrameBuffer.java – vytváření framebuffer objektů (pro kreslení do textury).

•

GLSLProgram.java – vytváření GLSL shaderů.

•

Texture2D.java – vytváření textur.

Shaders – balíček obsahující zdrojové kódy GLSL shaderů. •

White.frag a White.vert – shadery sloužící k vytvoření grafu viditelnosti.

•

clipping_plane.frag a clipping_plane.vert – implementace ořezávacích rovin.

•

windowCut.frag a windowCut.vert – implementace geodetického výřezu.

5.3 Rozhraní GLSL shaderů Každý ořezávací shader potřebuje ke své činnosti nějaká vstupní data. V případě použití OpenGL a jazyka GLSL se rozlišují dva typy předávaných hodnot: uniform a attribut. Rozdíl mezi nimi je především v tom, že proměnné prvního typu mohou svou hodnotu změnit pouze mezi jednotlivými vykreslovacími cykly (tedy před funkcí glBegin), zatímco proměnné druhého typu slouží k přiřazování parametrů jednotlivým vrcholům a mohou tedy být změněny kdykoliv.

Shader pro ořezávání pomocí rovin vyžaduje pouze proměnné typu uniform, které je potřeba nastavit před vykreslením 3D modelu: •

plane0, plane1 ... plane5 – obecné rovnice jednotlivých ořezávacích rovin.

•

num_planes – celkový počet ořezávacích rovin.

60


•

plane_texture – 2D textura obsahující vykreslené a vystínované ořezávací roviny.

•

screen_size – informace o rozlišení obrazovky.

•

inside – invertuje podmínku pro vyhodnocení zahození fragmentu (pro příčný výřez).

Shader implementující geodetický výřez využívá i jedné proměnné typu attribut, kterou je potřeba nastavit pro každý vrchol zvlášť: •

distance_from_center – udává vzdálenost vrcholu od středu výřezu.

Rovněž potřebuje také jednu proměnných typu uniform: •

window_size – velikost požadovaného výřezu.

Nakonec následuje přehled proměnných typu uniform, které jsou společné oba dva popsané shadery: •

camera_position – pozice kamery.

•

shader – zapíná či vypíná NPR zobrazování.

•

clipping – zapíná či vypíná ořezávání.

•

alpha – identifikátor části 3D modelu (každá část má přiřazen svůj identifikátor, který se při vykreslování ukládá do alfa kanálu).

•

selected – udává, zda je daná část modelu vybrána uživatelem (pokud ano, tak se zvýrazní).


61

5.4 Přehled knihoven třetích stran Při vývoji aplikace byly použity některé knihovny a balíčky třetích stran, jejichž přehled následuje: •

Knihovna JOGL – knihovna umožňující použití OpenGL v Javě. Její vývoj má na starosti Game Technology Group, Sun Microsystems.

•

Knihovna JAMA – matematická knihovna implementující různé maticové operace. Vyvinuta byla organizacemi MathWorks a NIST a nyní je volně šiřitelná.

•

Knihovna GlueGen – slouží k volání funkcí knihoven napsaných v jazyce C. Je nezbytná pro činnost knihovny JOGL, pro kterou byla původně vytvořena.

•

Balíček OpenGL – balíček obsahuje kód pro práci s OpenGL, jehož autorem je Ladislav Čmolík.

•

Balíček Gleem – balíček implementuje užitečné OpenGL manipulátory a je šířen pod licencí GNU GPL.

•

Balíček Mesh a Mesh.loaders – balíčky obsahují kód pro práci s 3D modely. Autorem je Ladislav Čmolík, avšak obsažené třídy byly v průběhu implementace výrazně pozměněny.

62

Kapitola 6. Testování aplikace

6 Testování aplikace Výsledná aplikace byla již v průběhu implementace důkladně testována jak na výskyt chyb, tak na rychlost provádění klíčových výpočtů. To se pozitivně podepsalo na stavu finální verze, jenž splnila všechny požadavky definované ve druhé kapitole.

6.1 Minimální požadavky na systém Požadavky, které aplikace klade na systém, lze rozdělit na hardwarové a softwarové. Následující hardwarové požadavky jsou spíše doporučené, neboť aplikaci lze teoreticky spustit i na slabším systému, avšak uživatelský komfort bude v takovém případě výrazně snížen dlouhou dobou reakce. Splnění softwarových požadavků je však nezbytné.

Minimální hardwarové požadavky: •

CPU 1.4 Ghz

•

512 MB RAM

•

Grafická karta podporující OpenGL 2.0

•

Monitor s rozlišením alespoň 800x600 bodů

Minimální softwarové požadavky: •

Operační systém GNU Linux nebo MS Windows XP/Vista

•

Nainstalovaný ovladač grafické karty podporující OpenGL

•

Nainstalovaná Java 6.0 JDK


63

6.2 Rychlost aplikace Testování rychlosti aplikace bylo provedeno na této počítačové sestavě: •

AMD Athlon(tm) 64 3000+ 1800 Mhz

•

1024 MB RAM

•

Nvidia GeForce 7600, ovladač NVIDIA GLX 180.44

•

Ubuntu 9.04 i386, verze jádra 2.6.28

Velikost okna aplikace byla po celou dobu měření nastavena na 512x512 pixelů. Rychlost byla měřena v těchto kategoriích (výsledné hodnoty jsou založeny na opakovaném měření a průměrování výsledků):

•

načítání OBJ modelu (včetně výpočtu orientovaných obalových boxů) ◦ model skládající se z 1620 polygonů – 0.392 sekund ◦ model skládající se z 73300 polygonů – 5.122 sekund

•

rychlost vykreslování (bez řezů) ◦ model skládající se z 1620 polygonů – 676 FPS ◦ model skládající se z 73300 polygonů – 133 FPS

•

rychlost vykreslování (použití 6 ořezávacích rovin) ◦ model skládající se z 1620 polygonů – 202 FPS ◦ model skládající se z 73300 polygonů – 73 FPS

•

uložení pohledového úhlu (vytváří se graf viditelnosti) ◦ model skládající se z 1620 polygonů – 1.831 sekundy ◦ model skládající se z 73300 polygonů – 48.101 sekundy

64


•

výpočet kostry modelu pro příčný výřez (model tvořený 608 polygony) ◦ kostru tvoří 10 segmentů – 0.059 sekund ◦ kostru tvoří 50 segmentů – 0.121 sekund

•

výpočet geodetického výřezu (model tvořený 3968 polygony) ◦ je definován 1 pohledový úhel – 2.309 sekund ◦ je definováno 5 pohledových úhlů - 7.420 sekund

Na základě testování rychlosti se dá říci, že největší problém představuje vytváření nových pohledových úhlů. V budoucnosti by se tedy pozornost měla zaměřit na optimalizování výpočtu grafů viditelnosti (například by mohlo být použito nižší rozlišení pro textury vrstev, či by mohla být prozkoumána možnost urychlení jejich vytváření pomocí využití occlusion queries).

Kapitola 7. Srovnání aplikace s existujícími řešeními

65

7 Srovnání aplikace s existujícími řešeními Existuje mnoho aplikací, které implementují různé metody pro automatickou vizualizaci vnitřní struktury komplexních 3D modelů. Většina z nich ale k popsanému problému přistupuje zcela opačně – odstraňuje překrývající geometrii na základě tvaru vybraných důležitých částí (například VolumeShop). Jediná nalezená metoda, která při odstraňování geometrie respektuje tvar ořezávané části, je ta zde analyzovaná.

Objektivní srovnání aplikace je tedy možné pouze s aplikací vytvořenou autory článku [CUTAWAY07], která ovšem není veřejně přístupná. Na základě zveřejněného videa a popisu aplikace ve zmíněném článku však lze říci, že ve většině případů je funkcionalita srovnatelná. V implementované aplikaci chybí pouze některé nástroje pro interaktivní vytváření řezů a zobrazování jmen jednotlivých vykreslovaných částí (labeling). Výhodou ale je možnost volného šíření, lepší uživatelské rozhraní a rychlejší vykreslování (pouze teoreticky na základě použitých metod ořezávání, neboť skutečné hodnoty o rychlosti vykreslování bohužel nejsou k dispozici).

66

Kapitola 8. Závěr

8 Závěr Cílem práce bylo popsat základní metody pro vizualizaci vnitřní struktury složitých 3D modelů a na jejich základě implementovat vlastní systém pro automatické generování ilustrací, umožňující interaktivní prohlížení v reálném čase. Po zhodnocení práce lze prohlásit, že byly splněny všechny tyto vytyčené požadavky. Výsledkem je plně funkční aplikace, která může snadno najít uplatnění v praxi.

Kapitola 9. Seznam literatury

67

9 Seznam literatury AUTOI90: D. Dooley and M. F. Cohen, Automatic illustration of 3d geometric models: surfaces, 1990 CMOLIK07: Ladislav Čmolík, Semantic Approach to Exploration of 3D Models, 2007 CUTAWAY03: J. Diepstraten, D. Weiskopf, T. Ertl, Interactive Cutaway Illustrations, 2003 CUTAWAY07: Wilmot Li, Lincoln Ritter, Maneesh Agrawala, Brian Curless, David Salesin, Interactive Cutaway Illustrations of Complex 3D Models, 2007 EXPVIEW08: Wilmot Li, Maneesh Agrawala, Brian Curless, David Salesin, Automated Generation of Interactive 3D Exploded View Diagrams, 2008 GLEEM: , gleem: OpenGL Extremely Easy-to-use Manipulators, 2009, http://www.gnu.org/software/gleem/ IDVR04: I. Viola, A. Kanitsar, M.E. Groller, Importance-driven Volume Rendering, 2004 JAMA: , JAMA : A Java Matrix Package, 2009, http://math.nist.gov/javanumerics/jama/ JAVADOC: , Dokumentace jazyka JAVA, 2009, http://java.sun.com LINUXSOFT09: Petr Hatina, Programování v jazyku Java, 2009, www.linuxsoft.cz OPENGL07: Richard S. Wright, Benjamin Lipchak, Nicolas Haemel, OpenGL SuperBible: Comprehensive Tutorial and Reference, 2007 SKEL97: Anne Verroust, Francis Lazarus, Extracting Skeletal Curves from 3D Scattered Data, 1997 SV05: Ivan Viola, Meister E. Gröller, Smart Visibility in Visualization, 2005 TRANSP02: J. Diepstraten, D. Weiskopf, and T. Ertl., Transparency in interactive technical illustrations., 2002 ZPG97: B. Hudec, Základy počítačové grafiky, 1997

68

Kapitola .

Kapitola . Příloha A – Snímky obrazovky aplikace

Příloha A – Snímky obrazovky aplikace

69

70

Kapitola .

Kapitola . Příloha B - Uživatelská příručka

71

Příloha B - Uživatelská příručka Aplikace implementuje rozhraní jak pro tvůrce ilustrace, tak pro uživatele systému. V první části této příručky bude popsán postup pro vybavení scény všemi potřebnými informacemi k automatickému generování ilustrací. Druhá část se zabývá možnostmi interaktivního prohlížení výstupu.

Prázdné okno před načtením modelu. Panel nalevo slouží k zobrazení seznamu jednotlivých částí 3D modelu. Nahoře je hlavní menu a panel nástrojů. Dole se nalézá informační pruh s aktuální hodnotou FPS a zvoleným režimem aplikace (viz. Dále).

Vytvoření ilustrace Po spuštění programu je potřeba nejprve načíst 3D model. To lze provést buď pomocí příslušné ikony v liště nástrojů, případně také přes nabídku Scene/Import OBJ v hlavním menu. Dalším krokem by měla být definice pohledových úhlů. Nejprve je potřeba stanovit vhodnou pozici kamery pomocí manipulace s myší a poté tento úhel pohledu uložit nabídkou Viewpoint/Save Viewpoint (či alternativně klávesovou zkratkou Ctrl+V).

72

Kapitola . Vytvoření ilustrace

Manipulace s pozicí kamery pomocí myši: •

levé tlačítko + pohyb – rotace kamery kolem 3D modelu

•

pravé tlačítko + pohyb – přesun kamery v osách X a Y

•

levé a pravé tlačítko + pohyb – přibližování a vzdalování kamery od 3D modelu

Po uložení několika vhodných pohledových úhlů přichází na řadu přiřazování geometrických reprezentací jednotlivým částem 3D modelu. K tomu slouží zvláštní režim aplikace tzv. Edit Mode, který se aktivuje nabídkou Object/Edit Mode. V tomto režimu se zobrazuje vždy pouze jedna část 3D modelu a v pravé části obrazovky se objeví nový panel s nástroji pro modifikaci geometrických reprezentací. Tvůrce ilustrace nyní může v levém seznamu vybrat požadovaný objekt a pomocí pravého panelu přiřadit vhodnou geometrickou reprezentaci. Po přiřazení dojde ke změně obsahu panelu na nástroje určené k modifikaci konkrétní zvolené reprezentace.

Přepnutí aplikace do režimu „Edit Módu“.

Kapitola . Vytvoření ilustrace

73

Definované pořadí činností tvůrce ilustrace je nicméně pouze doporučené, aplikace umožňuje definici nových pohledových úhlů či změnu přiřazené geometrické reprezentace v jakémkoliv okamžiku.

Posledním krokem vybavování modelu je uložení projektu pomocí nabídky File/Save. Tím se všechny nastavené a vypočtené hodnoty uloží do zvoleného souboru a práce tvůrce ilustrace může být ukončena.

Interaktivní prohlížení Uživatel systému má nyní možnost načíst projekt vytvořený tvůrcem ilustrace pomocí nabídky File/Open. Poté již stačí jen vybírat požadované části modelu v levém seznamu, popřípadě přímým výběrem ve vykreslované ilustraci. V případě výběru více částí současně, stačí pouze přidržet klávesu CTRL. Vybrané části se automaticky zviditelní umístěním řezů a výběrem vhodného úhlu pohledu.

Uživatel má rovněž možnost automatický výběr pohledových úhlů zakázat volbou v nabídce Display. Na stejném místě je rovněž možné volit mezi fotorealistickým a NPR vykreslováním.

Klávesová zkratka

Přiřazená akce

Ctrl + N

Vytvoření nového projektu.

Ctrl + O

Načtení projektu.

Ctrl + S

Uložení projektu

Ctrl + E

Změna režimu aplikace (Edit Mode)

H

Skrytí vybraných částí modelu

S

Zobrazení vybraných částí modelu

A

Zobrazená všech částí modelu

Ctrl + V

Uložení pohledového úhlu

74

Kapitola .

Kapitola . Příloha C – Obsah přiloženého DVD

75

Příloha C – Obsah přiloženého DVD Soubor readme.txt run.sh run.bat Text/ Program/

Popis Informace o aplikaci (včetně minimálních požadavků na systém). Skript pro spuštění aplikace pod GNU Linux. Skript pro spuštění aplikace pod MS Windows. Adresář obsahující soubory s textem této práce. Adresář s implementovanou aplikací a zdrojovými kódy.

Vizualizace vnitřní struktury 3D modelů pomocí ořezávání v reálném čase

Recommend Documents