Západočeská univerzita v Plzni

Fakulta aplikovaných věd

Katedra informatiky a výpočetní techniky

Bakalářská práce

Obálka tělesa reprezentovanéhotrojúhelníkovou sítí

Plzeň, 2011 David Cholt

Prohlášení

Prohlašuji, že jsem bakalářskou práci vypracoval samostatně a výhradně s pou-žitím citovaných pramenů.

V Plzni dne 28. dubna 2011 . . . . . . . . . . . . . . . . . . . . .David Cholt

Poděkování

Tímto bych chtěl poděkovat panu Ing. Josefu Kohoutovi, Ph.D. za podklady,rady a usměrnění mých myšlenek při vzniku této práce po celý akademický rok2010/2011. Dále bych chtěl poděkovat rodině a přátelům za jejich morální a fi-nanční podporu v průběhu celého mého dosavadního studia, bez níž bych nemělmožnost se k této práci dostat.

Abstract

Progressive hull of triangular meshes

Mesh deformation algorithms often use coarse hulls for a redution of the compu-tation complexity, general optimisation and problem simplification. This thesisinvestigates possibilities of coarse mesh hull creation. It gives a survey of existingapproaches and, in detail, it describes ”Progressive Hull” algorithm which canprovide outer coarse hulls while preserving shape details of the original mesh.A few optimisation techniques and quality enhancements of this algorithm areproposed. The implementation part of this thesis deals with various specifics ofthis algorithm, implementation-level optimisations, compatibility with the usedlibraries and with the integration of the produced implementation into the meshdeformation method by P. Kellnhofer. The impact on the stability of this defor-mation method and on the quality of its results is evaluated.

Obsah

Obsah

1 Úvod 1

2 Hrubé sítě a obálky těles 22.1 Globální přístup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Lokální přístup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Přístup ze strany decimace . . . . . . . . . . . . . . . . . . . . . . 6

3 Progressive Hulls 73.1 Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.2 Elementární decimace . . . . . . . . . . . . . . . . . . . . . . . . . 83.3 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.4 Formulace úlohy lineárního programování . . . . . . . . . . . . . . 10

4 Vylepšení algoritmu 124.1 Výpočet priorit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.2 Rychlost algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . 124.3 Stabilita algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . 134.4 Kvalita generovaných trojúhelníků . . . . . . . . . . . . . . . . . . 154.5 Sebeprotínání sítě . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5 Knihovny použité pro implementaci 175.1 VTK - Visualisation Toolkit . . . . . . . . . . . . . . . . . . . . . 175.2 lp solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

6 Implementace 196.1 Způsob implementace . . . . . . . . . . . . . . . . . . . . . . . . . 196.2 DempApp - demonstrační aplikace . . . . . . . . . . . . . . . . . 196.3 Implementace samotného filtru . . . . . . . . . . . . . . . . . . . 19

6.3.1 InitMesh() . . . . . . . . . . . . . . . . . . . . . . . . . . . 206.3.2 BuildMesh() . . . . . . . . . . . . . . . . . . . . . . . . . . 206.3.3 PrioritizeEdges() . . . . . . . . . . . . . . . . . . . . . . . 216.3.4 Decimate() a Substitute() . . . . . . . . . . . . . . . . . . 216.3.5 ComputeDecimationPoint() a SolveLP() . . . . . . . . . . 236.3.6 EnlargeMesh() . . . . . . . . . . . . . . . . . . . . . . . . 236.3.7 DoneMesh() a ClearMesh() . . . . . . . . . . . . . . . . . 23

6.4 Začlenění filtru do třídy MeshSurface . . . . . . . . . . . . . . . . 24

7 Testy a dosažené výsledky 257.1 Časová náročnost . . . . . . . . . . . . . . . . . . . . . . . . . . . 257.2 Vliv parametrů na rychlost decimace . . . . . . . . . . . . . . . . 277.3 Vizuální porovnání . . . . . . . . . . . . . . . . . . . . . . . . . . 287.4 Výsledky po začlenění filtru do třídy MeshSurface . . . . . . . . . 28

8 Závěr 29

Přílohy 32

i

Seznam obrázků

Seznam obrázků

2.1 Příklady obálek. Zelená obálka má více hran, ale lépe vystihujetvar původního tělesa. Červená obálka má málo hran, ale její tvarjiž původnímu tělesu odpovídá jen vzdáleně. . . . . . . . . . . . . 2

2.2 (a) Obálka pomocí průniků bublin. (b) Problém této metody. . . . 4

2.3 (a) Obálka pomocí tečen bublin. (b) Vyřešení problému 2.2a. (c)Problém této metody. . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.4 Metoda alpha shapes (a) Tvorba obálky z množiny bodů (b) a (c)Situace u problémů 2.2b a 2.3c. Červená obálka je pomocí průse-číků koulí, zelená pomocí pomocí jejich tečných ploch. . . . . . . . 5

2.5 Obálka pomocí decimace. (a) Modrá zdecimovaná síť je zvětšena nazelenou. V nekonvexní části dochází díky zvětšení k chybě, původnísíť je vně obálky. (b) Lepší přístup pomocí normál. . . . . . . . . 7

3.1 Příklad decimace. Převzato z [19] . . . . . . . . . . . . . . . . . . 7

3.2 Decimace jedné hrany. . . . . . . . . . . . . . . . . . . . . . . . . 8

3.3 Elementární decimace hrany. (a) Dvojrozměrný náčrt (b) Trojroz-měrná vizualizace . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.1 Kulička po decimaci z 480 na 250 trojúhelníků. (a) Špatné počí-tání priorit. Algoritmus střední část kuličky ignoruje. (b) Správnépočítání priorit. Celá kulička je decimována rovnoměrně. . . . . . 13

4.2 Vznik jehel. (a) Náčrt jejich vzniku (b) Ukázka v praxi (c) Zhoršeníproblému při hlubší decimaci (d) Stejná decimace po aplikovánípravidla pro eliminaci „jehelÿ . . . . . . . . . . . . . . . . . . . . 14

4.3 Výsledky pravidla pro eliminaci úzkých trojúhelníků. (a) Před za-vedením pravidla (b) Po jeho zavedení . . . . . . . . . . . . . . . 15

4.4 Možnost sebeprotnutí (a) Bez omezení (b) S omezením parametruMeshRoughness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5.1 Logo VTK. Převzato z [8] . . . . . . . . . . . . . . . . . . . . . . 17

5.2 Pipeline systému VTK. Převzato a upraveno z [1]. . . . . . . . . . 18

6.1 Orientace trojúhelníků podle pořadí jejich vrcholů. (a) Chybná ori-entace (b) Správná orientace . . . . . . . . . . . . . . . . . . . . . 21

6.2 Nahrazení hrany a rekonstrukce okolí po decimaci . . . . . . . . . 22

6.3 Začlenění mého filtru. (a) Původní způsob vytváření hrubé sítě(převzato z [10]) (b) Použití vtkProgressiveHull . . . . . . . . . . 24

7.1 Časy operací decimace vzhledem k úrovni decimace pro modely(a) Stanfordský králíček (b) Sval krejčovský - Sartorius (c) Pánev- Pelvis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

7.2 Vliv parametrů na čas decimace . . . . . . . . . . . . . . . . . . . 27

A.1 Běh programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

ii

Seznam obrázků

B.1 Výsledky algoritmu pro různé úrovně decimace. Číselný údaj udávápočet vrcholů obálky. . . . . . . . . . . . . . . . . . . . . . . . . . 33

B.2 Výsledky algoritmu pro různé úrovně parametru MeshRoughness.Číselný údaj udává nastavení tohoto parametru a počet vrcholůobálky. Cílová decimace byla pro všechny testy 80%-ní, kvůli vel-kému omezení v případě (a) však požadovaná decimace nebylamožná. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

B.3 Výsledky algoritmu pro různé úrovně parametru MeshRoughnesspro zabránění sebeprotínání. Číselný údaj udává nastavení tohotoparametru. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

B.4 Výsledky deformace pomocí filtru vtkMEDPolyDataDeformationPKpro Stehenní kost (Femur). (a) Pomocí původní hrubé sítě (b) Po-mocí mého decimačního filtru . . . . . . . . . . . . . . . . . . . . 36

B.5 Výsledky deformace pomocí filtru vtkMEDPolyDataDeformationPKpro Sval krejčovský (Sartorius). (a) Pomocí původní hrubé sítě (b)Pomocí mého decimačního filtru . . . . . . . . . . . . . . . . . . . 37

iii

Seznam obrázků

Upřesnění pojmů a zkratek

Pro porozumění následujícímu textu je zapotřebí definovat několik pojmů:

Primitivum - element triangulované sítě - vrchol, hrana či trojúhelníkDecimační vrchol - vrchol, kterým je nahrazena decimovaná hranaDecimační filtr - mnou naprogramovaný VTK modul pro vytváření hrubýchsítíDeformační filtr - programové vybavení pro deformaci triangulovaných sítí vy-vinuté Petrem Kellnhoferem jako součást jeho bakalářské práce [10]STL - Standard Template Library - soubor základních datových struktur jazykaC++VTK - Visualisation toolkit, knihovna pro operace s daty a jejich vizualizaciWrapper - Třída napsaná v požadovaném jazyce, která zpřístupňuje metodyknihovny napsané v jiném jazyceDDR2 - Double Data Rate 2 - Druhá verze dvojitého způsobu přístupu do pa-mětí (zápis a čtení na náběžné i sestupné hraně řídicího signálu)Dual Channel - Paralelní uspořádání 2 paměťových modulů pro zvýšení šířkypásma pro přístup do operační pamětix64 - 64bitová architektura operačního systému

iv

1 Úvod

1 Úvod

Při vizualizaci trojrozměrných dat je často nutné operovat s velmi objemnýmidaty. Při těchto operacích se často používají metody pro zjednodušení sítí, kdy jepožadovaná a časově náročná operace aplikována pouze na tuto jednodušší řídicísíť a její data jsou poté přenesena na původní těleso. Takovéto zjednodušenésítě lze vytvářet pomocí decimace původních dat, tedy snížením počtu primitiv(trojúhelníků, hran či vrcholů) původní sítě. Těchto metod existuje celá řada,jejich aplikace však není vždy vhodná.

Jednou z těchto aplikací je deformace tělesa podle změny zadané kostry. Za-daná kostra deformuje zjednodušenou řídící síť a data této sítě jsou poté přenesenana původní těleso. Tento postup však vyžaduje kvalitní řídicí síť splňující určitéparametry, kterých nelze běžnými algoritmy ve významném počtu případů dosáh-nout. Takovým parametrem je například požadavek obálky, kdy řídící síť musízcela obalovat řízenou jemnou síť. Běžné decimační algoritmy tuto podmínkučasto nesplňují.

Tato práce se zabývá vytvářením obálek zadaného triangulovaného tělesa,které zachovávají detaily, zejména metodou Progressive Hulls - metodou vytvá-ření obálek iteračním způsobem z původních obalovaných dat. Důraz je kladen nakvalitu obálek, zachování tvaru původního tělesa a na optimalizaci výpočtu. Tytoobálky mohou mít mnohá využití - zjednodušování detailních modelů a jejich ořezsiluetou pro vykreslování zjednodušeného modelu s vizuálními parametry jemnésítě [19], pro rychlou detekci kolizí a výpočet průsečíků tělesa a přímky (napříkladv raytracingu) [15] a samozřejmě pro použití jako řídící sítě.

Práce by měla být mimo jiné řešením problémů, na které narazil P. Kellnho-fer během své práce [10] na deformacích triangulovaných těles. Jeho práce po-strádá dobrý algoritmus pro vytváření tzv. hrubých sítí, které využívá pro řízenísvých deformací. Využívá decimačního algoritmu pro vytváření zjednodušenýchsítí, které jsou následně upraveny na obálky. Tato metoda není vždy spolehlivá,decimací totiž může dojít ke ztrátě důležitých dat (dojde například ke kolapsučásti sítě do jediného bodu) a takto vytvořená obálka poté nezaručuje, že budecelá jemná síť uvnitř sítě řídící. Při využití metody Progressive Hulls, která tentoproblém řeší, se předpokládá zlepšení výsledků jeho algoritmů.

V kapitole 2 se zabývám teorií obálek a hrubých sítí, jejich použitím, návrhyalgoritmů pro jejich získání a jejich výhodami a nevýhodami a hledám návrhalgoritmu, který bude výhody využívat a nevýhody pokud možno eliminovat.Kapitola 3 se zabývá algoritmem Progressive Hulls pro výpočet obálek se zacho-váním detailů a detaily z hlediska jeho myšlenky a postupu při decimaci sítě.Úskalími tohoto algoritmu a jejich vylepšením na základě pozorování výsledků sezabývám v kapitole 4 a dále jeho teoretickou optimalizací tak, aby bylo co nejlépesplněno zadání práce.

Ve druhé části práce se v kapitole 5 zabývám využívanými knihovnami; im-plementačními detaily, datovými strukturami a jednotlivými metodami modulu

1

2 Hrubé sítě a obálky těles

v kapitole 6 a předkládám dosažené výsledky, jak z pohledu mojí práce tak zpohledu jejího začlenění do práce P. Kellnhofera (kapitola 7). V závěru prácenaznačuji další možné úpravy algoritmu pro lepší výsledky při jeho použití provytváření hrubých řídicích sítí.

2 Hrubé sítě a obálky těles

Tato práce je především určena pro generování tzv. hrubé sítě [11], proto sepodíváme, co tento pojem znamená. Hrubé sítě jsou zjednodušené trojúhelníkovésítě použité pro výpočet časově a paměťově náročných operací a jejich výsledkyjsou poté ze použití deformačních podmínek z původní detailní sítě na tuto síťaplikovány. Tím je zachována stabilita výpočtu za významného urychlení celéhoalgoritmu. Takováto zjednodušená síť však musí mít několik vlastností:

• Musí být složena z méně trojúhelníků, než síť původní

• Musí být ve všech bodech vně sítě původní, tedy musí být obálkou původ-ního tělesa

• Měla by zachovávat původní tvar původního tělesa

• Její trojúhelníky by se neměly navzájem protínat

• Měla by být hladká a spojitá

Tyto vlastnosti jsou důležité pro zachování stability barycentrických souřadnic[12] při výpočtu deformace původní sítě. Na obrázku 2.1 jsou zobrazeny příkladyobálek (ve dvojrozměrném prostoru pro lepší představu). Takovéto zjednodušenésítě lze vytvářet několika způsoby, které lze rozdělit do skupin z pohledu vlast-nosti, ze které chceme vycházet.

Obrázek 2.1: Příklady obálek. Zelená obálka má více hran, ale lépe vystihujetvar původního tělesa. Červená obálka má málo hran, ale její tvar již původnímutělesu odpovídá jen vzdáleně.

2

2 Hrubé sítě a obálky těles

2.1 Globální přístup

Chceme-li vycházet z vlastnosti obalování původního tělesa, můžeme napříkladpoužít globální přístup. Nejjednodušší obálkou tělesa je ohraničující kvádr (an-glicky Bounding Box ). Takový kvádr lze nalézt velmi jednoduše hledáním glo-bálních maximálních a minimálních vzdáleností vrcholů původního tělesa od po-čátku souřadnic ve všech třech osách. Taková obálka však nezachovává původnítvar tělesa.

Mohli bychom použít některý z algoritmů dělení prostoru, jako napříkladOctree [20], tedy rozdělit obálku na 4 menší kvádry a eliminovat ty, ve kterýchnejsou žádná primitiva původní sítě. Rekurzivně bychom mohli získat jakousi„kostrbatouÿ obálku. Vylepšení této obálky by poté spočívalo v přizpůsobeníkoncových kvádrů obálky částem sítě, které jednotlivé kvádry obsahují (přibli-žovat vrcholy obálky z vnějšku blíže k tělesu). Takovou změnou už by pak alenebylo zaručeno, že bude ve všech částech vně původního tělesa. Tomu bychommohli zabránit hledáním průsečíků tělesa a obálky, což je však velmi výpočetněnáročné a proto se mu budeme chtít vyhnout.

Podobným přístupem by mohl být opačný přístup, tedy vytvořit ohraničujícíkvádr pro každé primitivum prostoru a tyto kvádry spojovat spojovat pomocístromové struktury. Tohoto postupu využívá algoritmus Automatic Bounding BoxTree [6], původně navržen pro aplikaci v raytracingu. I tímto přístupem však do-jdeme ke stejnému závěru jako výše. I když tedy těmito postupy lze vytvořitobálku tělesa, nezískáme hladké obálky či obálky výrazně zachovávající tvar tě-lesa.

Hladkou globálně tvořenou obálkou je konvexní obálka (Convex hull). Takovouobálku bychom si mohli představit jako vyfouknutý pouťový balónek, ve kterémje umístěno původní těleso. Nejpoužívanější algoritmy pro tvorbu těchto obálekpro trojrozměrný prostor jsou dobře, jednoduše a s ukázkami vysvětleny v [14].Tyto obálky ale v konkávních částech původní sítě nezachovávají tvar a tím sevzdálenost zjednodušené sítě od původní v různých místech tělesa mění. To takénení to, co hledáme, naše obálka by měla být od původního tělesa pokud možnovzdálena všude stejně.

Globální metody tedy nebudou to, co potřebujeme, jelikož nezachovávají tvarpůvodní sítě.

2.2 Lokální přístup

Pokud vycházíme z požadavku dosáhnutí podobnosti původní sítě a obálky, jed-ním z návrhů je lokální řešení, s využitím tzv. „bublinovéÿ metody neboli metodysjednocených koulí (Union of balls) [4]. Tato metoda je původně myšlena pro re-konstrukci povrchových sítí nad zadanou množinou bodů, což nepotřebujeme,jelikož již máme povrchovou sít zadanou, podíváme se ale, zda bychom ji nemohlivyužít.

3

2 Hrubé sítě a obálky těles

(a) (b)

Obrázek 2.2: (a) Obálka pomocí průniků bublin. (b) Problém této metody.

Do každého vrcholu původní sítě by bylo možné umístit myšlenou kouli.Abychom docílili vnější obálky, její vrcholy by byly v průnicích těchto koulí (ob-rázek 2.2a). Již zde je však problém s nalezením průniku koulí vně tělesa1, tomujsme se chtěli vyhnout už v kapitole 2.1. Počet vrcholů obálky by byl sice stejnýjako počet trojúhelníků původní sítě 2, ale obálka by byla velmi pravidelná, i kdyžjejí vzdálenost od původní sítě by také byla v různých místech rozličná. Problémtéto metody je, že selhává v situacích, kde je úhel mezi původními trojúhelníkyvelmi ostrý (obrázek 2.2b). Obrázky jsou kresleny pro dvojrozměrné případy prolepší představu.

(a) (b) (c)

Obrázek 2.3: (a) Obálka pomocí tečen bublin. (b) Vyřešení problému 2.2a. (c)Problém této metody.

Tento problém by se dal vyřešit tím, že by nové trojúhelníky byly definoványpomocí tečen - nový trojúhelník by byl umístěn na ploše, která je tečnou plochoutří sousedních koulí (obrázek 2.3a). Tento způsob řeší problém s ostrým vnějšímúhlem (2.3b), generuje sítě pravidelněji vzdálené od sítě původní, ale selhává naostrých vnitřních úhlech (2.3c). Opět také ale nastává hledání vnějších tečnýchbodů. Každé tři koule mají v ideálním případě dvojici trojic tečných bodů. Po-

1Každá trojice koulí generuje dva průniky2Každé 3 vrcholy generují jeden vnější průsečík stejně jako generují jeden trojúhelník sítě.

Pokud průsečík neexistuje, algoritmus by tvořil v obálce díry

4

2 Hrubé sítě a obálky těles

kud koule nemají vzájemné průniky, může být tečných ploch více, nebo naopaknemusí vůbec existovat. Velikost koulí by tedy musela být alespoň taková, aby ktomuto problému nedocházelo. Bublinová metoda tedy pravděpodobně spolehlivěfungovat nebude a navíc je u ní velmi obtížné regulovat potřebné zjednodušenísítě.

Další metodou hledání obálek související s metodou sjednocených koulí je me-toda alfa tvarů (alpha shapes) [5]. Tato metoda je podobná předchozí metodě,používá také koulí pro hledání triangulovaného povrchu, ale koule jsou umísťoványtak, aby na jejich povrchu byly 3 vrcholy původní sítě (2 vrcholy v dvojrozměr-ném případě). Z těchto koulí vybereme pouze ty koule, které ve svém objemunemají jiné vrcholy (vizte obrázek 2.4a). Tato metoda má oproti bublinové me-todě výhodu snadnější regulace počtu výsledných trojúhelníků pro velmi členitéokolí sítě. Na obrázku 2.4a jsou dvě velikosti umísťovaných koulí a vidíme, žeu zelené obálky dochází k zjednodušení sítě. Na konvexních částech sítě si alese zjednodušením příliš nepomůžeme. Dalším problémem je, že obálka využívápůvodní body tělesa, není tedy vždy vnější.

(a)

(b) (c)

Obrázek 2.4: Metoda alpha shapes (a) Tvorba obálky z množiny bodů (b) a (c)Situace u problémů 2.2b a 2.3c. Červená obálka je pomocí průsečíků koulí, zelenápomocí pomocí jejich tečných ploch.

Můžeme se pokusit aplikovat způsob tvorby obálky z bublinové metody pomocíprůsečíků nebo tečných ploch koulí. Na obrázcích 2.4b a 2.4c vidíme, že problémybublinové metody nenastávají. Problém použití průsečíků je však zjevný, jeden

5

2 Hrubé sítě a obálky těles

průsečík je vždy v původním vrcholu a druhý může být vně, nebo uvnitř tělesa.To bychom museli opět rozhodnout, což je časově náročné a chceme se tomuvyhnout. Přístup pomocí tečen má stejný problém s jejich nejednoznačností jakou bublinové metody. Dále má metoda tyto nevýhody:

• Opět nevelké snížení počtu vrcholů obálky, zvláště na konvexních částechsítě

• Příliš malé koule mohou způsobit, že bude síť roztržena na více komponent(jak naznačuje i článek [5]) a příliš velké koule by způsobily nedostatečnézachování detailů. U sítí s velmi různými velikostmi trojúhelníků tak tatometoda selhává3

• Výpočetní složitost. Jen nalezení všech odpovídajících koulí je dle [5] složi-tosti O(n2) + O(nlogn), v nejhorším případě θ(n2) + θ(n2logn2). Následo-valo by hledání sousedních koulí a výpočet tečen/průniků a jejich umístěnívzhledem k původnímu tělesu.

Lokální přístup je tedy lepší než globální co se týče výsledků a má výhodu vpodobnosti původní sítě a její obálky, ale redukce počtu vrcholů není příliš velkáa algoritmy jsou výpočetně složité.

2.3 Přístup ze strany decimace

Lze také přemýšlet ze třetího pohledu - ze strany snížení počtu vrcholů, tedydecimací. Existují decimační algoritmy (například decimace s využitím kvadra-tické metriky [9]), které fungují na principu nahrazování trojúhelníků nebo hranvrcholy podle určité metriky. Dostatečným zvětšením (scale) takto decimovanésítě získáme v určitých případech obálku.

Tato metoda ovšem opět selhává v mnoha případech, například situace, kdeje síť nekonvexní (obrázek 2.5a). Tento postup se však zdá být dobrý, je pouzenutné jej upravit. Jednou z možností (použitou v [10]) je použít normály vrcholůa všechny vrcholy posunout ve směru těchto normál o konstantní vzdálenost (ob-rázek 2.5b). Toto řešení má však dvě nevýhody:

• Sebeprotínání (na obrázku 2.5b je tento problém naznačen v levé části). Tolze odstranit druhou decimací sítě po posunu vrcholů (opět vizte [10]).

• Velká závislost na decimačním algoritmu. To je největším problémem tétometody. Většina decimačních algoritmů nemá možnost pracovat s parame-try decimací jednotlivých primitiv, proto mohou vznikat nepříjemné arte-fakty, které způsobují nestabilitu jakékoliv další aplikace zdecimované sítěpro další výpočty.

3Velikost koulí musí být konstantní, jinak tato metoda ztrácí smysl.

6

3 Progressive Hulls

(a) (b)

Obrázek 2.5: Obálka pomocí decimace. (a) Modrá zdecimovaná síť je zvětšenana zelenou. V nekonvexní části dochází díky zvětšení k chybě, původní síť je vněobálky. (b) Lepší přístup pomocí normál.

Lepším řešením je použití algoritmu, který bude kombinovat decimaci a lokálníposun od původní sítě najednou a provázaně. Jedním takovým je algoritmus snázvem Progressive Hulls, je naznačen v článku Silhouette clipping [19] a jehoaplikací se tato práce zabývá.

3 Progressive Hulls

3.1 Motivace

Progressive Hull je typ obálky, která je vytvářena z původní sítě s ohledem najejí tvar. Příklad aplikace této metody je na obrázku 3.1. Je vidět, že je obálkase snižujícím se počtem trojúhelníků stále větší a zachovává tvar.

(a) 69674 4 (b) 2000 4 (c) 500 4 (d) 200 4 (e) 100 4 (f) 38 4

Obrázek 3.1: Příklad decimace. Převzato z [19]

Myšlenka tohoto algoritmu popsaného v článku [19] je jednoduchá - nahra-zovat hrany původní sítě pouhými vrcholy tak, aby původní těleso leželo vždyv objemu nového tělesa, tedy pokud je povrch decimován, zůstane buď stejný,nebo se lokálně posune směrem ven. Decimace celé sítě je potom sekvencí těchtonahrazení (příklad jednoho nahrazení je zobrazen na obrázku 3.2).

7

3 Progressive Hulls

Obrázek 3.2: Decimace jedné hrany.

3.2 Elementární decimace

Zvýrazněná hrana e (na obrázku 3.2) v okolí Fi+1 (okolí hrany před decimací) jenahrazena vrcholem V v okolí Fi (po decimaci). Dle původního článku se musívrchol V nacházet v průniku poloprostorů, které jsou nad plochami definovanýmivšemi trojúhelníky f v okolí Fi+1 . Směr „nadÿ je definován, jelikož díky orien-tovanosti sítě4 lze dopočítat normály trojúhelníků a hledané poloprostory potébudou v jejich směru, nebo ve směru opačném (záleží na orientaci trojúhelníků).Průnik může být prázdný, v tom případě není decimace pro tuto hranu povolena.Díky tomuto způsobu decimace je tedy zaručeno, že objem sítě Mi bude větší,než objem sítě Mi+1 nebo stejný (v případě, že je celé okolí Fi+1 v rovině).

Poloha vrcholu V je dopočítána pomocí lineárního programování. Omezují-cími podmínkami jsou rovnice výše uvedených poloprostorů a cílovou funkcí jeminimalizace zvětšení objemu decimované sítě. Toto navýšení lze počítat jakozměnu lokálního objemu, kterou lze definovat jako rozdíl objemových příspěvků5

jednotlivých trojúhelníků f v okolích Fi a Fi+1, tedy V (Fi)− V (Fi+1).

Na obrázku 3.3a vidíme náčrt takové decimace pro dvojrozměrný případ.Máme decimovanou hranu e a hledáme vrchol V který ji může nahradit. Sousedníhrany hrany e určují vnější poloprostory a jejich průnik (zeleně) určuje prostor,kde lze hledat polohu vrcholu V . Jelikož minimalizujeme objem, bude jeho po-loha právě v bodu průniku přímek, na kterých hrany leží. Obrázek 3.3b ukazujevizualizaci takové elementární decimace v trojrozměrném prostoru. Původní okolíFi+1 je zobrazeno modře (uvnitř) a nové okolí Fi zeleně.

Jednotlivé hrany sítě vstupují do prioritní fronty podle vhodné metriky (článek[19] navrhuje použít nárůst objemu) a postupně zpracovávány - decimovány.

4Orientovaností rozumíme pořadí vrcholů jednotlivých trojúhelníků, levotočivé či pravoto-čivé. Aby síť byla orientovaná, musí všechny její trojúhelníky mít toto pořadí stejné5Každý trojúhelník sítě se podílí na celkovém objemu tělesa. Změna trojúhelníku se projeví

na jeho příspěvku k celkovému objemu

8

3 Progressive Hulls

(a) (b)

Obrázek 3.3: Elementární decimace hrany. (a) Dvojrozměrný náčrt (b) Trojroz-měrná vizualizace

3.3 Algoritmus

Při decimaci celé sítě je nutné brát v úvahu větší množství operací, které původníčlánek nutně nepopisuje. Algoritmus popsaný v článku [19] lze tedy detailnějipopsat takto:

• Příprava

1. Vyhledat vztahy6 mezi primitivy

2. Pro každý trojúhelník spočítat jeho přírůstek k objemu a jeho normálu

3. Pro každou hranu původní sítě:

I Najít okolní trojúhelníky (nalezení Fi+1)

II Pro všechny trojúhelníky f z okolí Fi+1 vyhledat poloprostoryve směrech jejich normál a jejich rovnice použít jako podmínkylineárního programování

III Sestavit cílovou funkci úlohy lineárního programování - minimali-zace změny lokálního objemu

IV Vyřešit úlohu lineárního programování. Má-li úloha řešení, zařadithranu do prioritní fronty s prioritou odpovídající možné změnělokálního objemu a přiřadit k hraně vypočtené souřadnice vrcholunahrazujícího tuto hranu

6Informace o tom, které primitivum sousedí se kterým

9

3 Progressive Hulls

• Decimace

1. Vyzvednout hranu z prioritní fronty a nahradit ji přiřazeným vrcholem

2. Odstranit ze sítě primitiva, která se v Fi nevyskytují, tedy trojúhel-níky, které s hranou sousedí a duplicity v jejich hranách7.

3. Obnovit vztahy mezi primitivy v celém okolí Fi

4. Pro všechny trojúhelníky v Fi aktualizovat normály a lokální objemy

5. Pro všechny hrany v Fi znovu přepočítat vrcholy decimace a prioritya upravit jejich pozice v prioritní frontě

6. Odstraněné hrany a hrany z okolí Fi, jejichž decimace již není možnáv důsledku jejich úprav, odstranit z prioritní fronty

7. Opakovat body 1 až 6 pro všechny položky prioritní fronty nebo propožadovaný počet decimovaných hran

3.4 Formulace úlohy lineárního programování

Jak je z algoritmu vidět, jediným opravdovým výpočtem je řešení úlohy lineár-ního programování. Lineární programování je typem optimalizace, kdy hledámeminimum (respektive maximum) zadané funkce o n proměnných vzhledem k ome-zením daným omezujícími nerovnostmi - podmínkami.

Naší cílovou funkcí úlohy lineárního programování je minimalizace nárůstuobjemu. Jelikož je ale objem před decimací konstantní, stačí pouze minimalizo-vat nový objem po decimaci. Jelikož se však mění jen okolí Fi+1 na Fi, stačíminimalizovat jen lokální objem okolí Fi (objem okolí Fi+1 je konstantní). Objemokolí lze počítat jako sumu přírůstků objemu všech trojúhelníků f . Tento přírůs-tek můžeme počítat jako orientovaný objem tetrahedronu (čtyřstěnu) vznikléhopřidáním jednoho libovolného vrcholu ke třem vrcholům tohoto trojúhelníka. Jezřejmé, že pro všechny trojúhelníky sítě použijeme stejný přidaný vrchol, pro jed-noduchost výpočtu počátek souřadnic, tedy [0, 0, 0]. Takto zadaný tetrahedron máobjem

V =~V1 · ( ~V2 × ~V3)

6

kde ~V1, ~V2 a ~V3 jsou vektory souřadnic vrcholů trojúhelníka. Dělení konstantoumůžeme vypustit, jelikož pro diferenci objemů nehraje roli. Objem okolí Fi lzetedy psát jako ∑

Fi

~X · ( ~V2 × ~V3)

7Jde o hrany trojúhelníků přilehlých k decimované hraně. Odstraněním (smrštěním) jednéhrany trojúhelníka dojde k překrytí zbylých dvou, což je nežádoucí

10

3 Progressive Hulls

kde ~X vektor hledaného vrcholu a ~V2 a ~V3 jsou vektory právě těch vrcholů troj-úhelníka, které se s decimací nemění (tyto vrcholy nenáleží decimované hraně)8.Vidíme, že suma vektorových součinů je z pohledu výpočtu objemu neměnná,vyjádříme si ji tedy jako vektor ~A

~A =∑Fi

(V2 × V3)

a cílovou funkci lze tedy psát ve tvaru

~A · ~X = a1x1 + a2x2 + a3x3

Vidíme, že tato funkce je lineární a tedy může být předmětem k řešení. Najdeme-li minimum této funkce pro zadané omezující podmínky, nalezené souřadniceminima jsou zároveň souřadnicemi vrcholu, do kterého je možné hranu uprostředokolí zdecimovat.

Zbývá tedy ještě dodefinovat omezující podmínky. Víme, že hledaný vrcholmusí být nad rovinami trojúhelníků v okolí Fi+1. Napíšeme si tedy normálovourovnici této roviny

~Vf · ~nf ,

kde ~Vf je libovolný vrchol trojúhelníka a ~nf je jeho normála9. Hledaný vrchol ~Xmusí být nad touto rovinou nebo na ní, tedy ve směru její normály [17], a tedy

~nf · ~X ≥ ~nf · ~Vf

Omezující podmínky mají na pravé straně konstantu, přepíšeme tedy tuto rovnicina

~nf · ~X − ~nf · ~Vf ≥ 0

a máme omezující podmínku pro zadaný trojúhelník hotovu. Podmínky taktosestavíme pro všechny trojúhelníky v okolí Fi+1.

Dodatečnou podmínkou algoritmu je zabránění sebeprotnutí sítě, tedy že vr-chol ~X nesmí být uvnitř tělesa. Článek [19] naznačuje, že tato podmínka nenínutná a testováním jsem došel k závěru, že opravdu není. K sebeprotnutí docházív místech, kde se k sobě blíží dvě tělesa, tento jev se však našich datech nevy-skytuje a pokud ano, lze sebeprotínání zamezit omezením parametru maximálníčlenitosti decimované sítě (vizte kapitolu 4.5).

Pro řešení této úlohy lze použít mnoho algoritmů, my se však jejich teorií a im-plementací zabývat nebudeme (použijeme knihovnu lp solve, vizte kapitolu 5.2).Pokud však čtenáře tento problém zajímá, dobrým a používaným algoritmem prořešení problémů lineárního programování je Revidovaný simplexový algoritmus [3].

8Je nutné zachovat orientaci trojúhelníka a tedy pořadí vrcholů v tomto výpočtu9Normálu trojúhelníka lze vypočítat jako vektorový součin vektorů (V2−V1) a (V3−V1) [16]

11

4 Vylepšení algoritmu

4 Vylepšení algoritmu

Cílem této práce je produkovat pokud možno kvalitní obálky v co nejlepším čase.Při testování výše zmíněného algoritmu jsem však přišel na několik nedostatků,které jsem se pokusil vylepšit.

4.1 Výpočet priorit

Článek [19] nejasně mluví o způsobu výpočtu priorit, zmiňuje pouze, že jako prio-ritu lze použít nárůst objemu, nespecifikuje však jakého. Čtenář by jistě pochopil,že jde o změnu objemu v okolí Fi+1, jelikož je to právě tato změna, která sepři výpočtu nového bodu minimalizuje.

Takto implementovaný algoritmus vždy decimuje nejprve hrany s nejmenšímlokálním nárůstem objemu. Jsou-li dvě takové hrany „u sebeÿ, dojde přirozeněk jejich okamžité decimaci a tedy ke spojení těchto malých lokálních objemů.Výsledný objem těchto spojených lokálních objemů však již může být větší, nežnárůst objemu po decimaci jiné, „vzdálenéÿ hrany. To ale algoritmus ignoruje.Nabaluje na tyto spojené objemy další a další malé objemy z okolí, jelikož jejichpriorita (lokální nárůst objemu) je nižší, než priorita (opět pouze lokální nárůstobjemu) decimace jiné „vzdálenéÿ hrany. Není totiž do priority započítán nárůstobjemu z předchozích decimací.

Výsledkem tohoto postupu je však nerovnoměrná decimace. Lokální nárůstobjemu a priorita jsou totiž dva rozdílné parametry. Priorita musí odrážet nárůstobjemu vzhledem k objemu původní sítě, nikoliv k objemu výsledku předchozíiterace. Je tedy nutné měřit rozdíl mezi objemem původní sítě a objemem decimo-vané sítě po poslední iteraci a součet tohoto rozdílu a nárůstu lokálního objemupoužít jako prioritu.

Nerovnoměrnost decimace způsobenou tímto zdánlivým detailem ukazuje ob-rázek 4.1.

4.2 Rychlost algoritmu

Autoři článku [19] se optimalizaci algoritmu příliš nevěnovali, jelikož obálky před-počítávají a následně je používají již vypočítané. My ale potřebujeme obálkypočítat v rozumném čase, jelikož je jejich výpočet součástí složitějšího výpočtudeformací. Algoritmus je časově velmi náročný díky častému řešení úlohy line-árního programování (v bodě 3IV a zejména pak v bodě 5). I původní článekvšak říká, že prioritu lze počítat jiným, vhodným způsobem. Použijeme tedy tutomožnost a oddělíme výpočet priority a výpočet decimačního bodu. Tím budemeřešit úlohu lineárního programování jen pokud je to nutné, ne jen pro výpočetpriority.

Potřebujeme tedy pouze nový algoritmus pro výpočet priority. Velmi rychlýalgoritmus popisuje článek [15]. Ten říká, že je pro výpočet priority postačující

12

4 Vylepšení algoritmu

(a) (b)

Obrázek 4.1: Kulička po decimaci z 480 na 250 trojúhelníků. (a) Špatné počítánípriorit. Algoritmus střední část kuličky ignoruje. (b) Správné počítání priorit.Celá kulička je decimována rovnoměrně.

vypočítat algebraický průměr souřadnic vrcholů v okolí Fi+1 (bez vrcholů nále-žících decimované hraně) a tento vrchol použít pro výpočet nárůstu objemu atento v absolutní hodnotě použít jako prioritu. Samozřejmě je nutné také apliko-vat odchylku od objemu původní sítě popsanou v kapitole 4.1.

Takto vypočtený bod má podobné vlastnosti jako výpočet pomocí lineárníhoprogramování. Pro malá okolí Fi+1 generuje malé objemy a tedy je jejich prioritanižší. Je-li okolí rovné, objem je také malý. Předpokládáme-li, že je počet vrcholův okolí Fi+1 pro složitost výpočtu zanedbatelný, je výpočet složitosti O(1), což jeoproti O(nx) složitosti simplexové metody řešení úlohy lineárního programovánívelmi dobré. Na druhou stranu je takto vypočtená priorita velmi nepřesná pročlenitá okolí Fi+1. Správný bod decimace může být úplně jinde, než algebraickýprůměr okolních vrcholů. To může způsobovat problémy.

4.3 Stabilita algoritmu

Nepřesný výpočet priorit a ne příliš pravidelná vstupní data mohou způsobit ne-stabilitu algoritmu, který poté vytváří nečekané artefakty, které pojmenovávám„jehlyÿ. Obrázek 4.2a naznačuje jejich vznik. Priorita decimace hrany e je vypo-čítána pro „vrcholÿ V ′ a je tedy velmi malá. Algoritmus ji tedy vybere z fronty avypočte vrchol, do kterého se hrana musí zdecimovat, aby byl zachován objem,tedy vrchol V , a decimaci provede. Vidíme však, že nárůst objemu je velký avýsledná decimace je nepěkná a pro další výpočty nevhodná. Na obrázku 4.2bvidíme, jak se tento problém projevuje v praxi.

Při hlubší decimaci10 se tento problém akumuluje a decimovaná síť se hroutí

10Při decimaci velkého počtu hran

13

4 Vylepšení algoritmu

(a) (b)

(c) (d)

Obrázek 4.2: Vznik jehel. (a) Náčrt jejich vzniku (b) Ukázka v praxi (c) Zhoršeníproblému při hlubší decimaci (d) Stejná decimace po aplikování pravidla proeliminaci „jehelÿ

(obrázek 4.2c). Dochází k sebeprotínání a síť je pro další numerické výpočtynepoužitelná.

Potřebujeme tedy zavést pravidlo, kterým takovéto decimace bude možné za-kázat. Článek [15] navrhuje použití kontroly odchylek normál trojúhelníku po-psané v článku [7]. Jde o kontrolu rozdílu normál trojúhelníků před a po deci-maci. Je-li tento rozdíl (úhel mezi normálami) mimo rozsah [0, π/2], je decimacezamítnuta. Zjistíme však, že tato metoda na eliminování jehel příliš nefunguje,jelikož (jak je vidět na obrázku 4.2a) je normála trojúhelníků před a po decimacistejná. Budeme tedy kontrolovat normály mezi trojúhelníky pouze v okolí Fi abudou-li příliš odkloněné (a tím okolí příliš špičaté), decimaci zakážeme (vícevizte kapitolu 6.3.4). Jako bonus tento postup generuje pravidelnější sítě (viztekapitolu 7.3). Ukázka aplikace tohoto pravidla je pro porovnání na obrázku 4.2d

14

4 Vylepšení algoritmu

4.4 Kvalita generovaných trojúhelníků

Nyní je již algoritmus téměř připraven, zbývá však dořešit poslední problém.Jelikož bude naše síť použita pro další výpočty, je nutné, aby trojúhelníky této sítěnebyly příliš úzké (z důvodu nestability numerických výpočtů na těchto tvarechtrojúhelníků). Zavedeme tedy ještě jedno pravidlo decimace - kontrolu nejmenšíhoúhlu všech trojúhelníků v okolí Fi. Je-li trojúhelník úzký, je jeho nejmenší úhelmalý. Povolíme tedy decimace takových hran, pro něž jsou tyto úhly pro všechnyokolní trojúhelníky nad určitou hranicí.

(a)

(b)

Obrázek 4.3: Výsledky pravidla pro eliminaci úzkých trojúhelníků. (a) Před za-vedením pravidla (b) Po jeho zavedení

Menší problém tohoto omezení však nastává, pokud již vstupní data tenkétrojúhelníky obsahují. Toto pravidlo tedy aplikujeme pouze pokud jsou trojúhel-níky v okolí Fi+1 široké, jinak decimaci provedeme vždy. Tato změna zaručí, žealgoritmus alespoň nebude zhoršovat kvalitu sítě. Z testování však plyne, že deci-mací okolních trojúhelníků dojde k pohlcení tenkých trojúhelníků v původní sítia decimovaná síť je již neobsahuje. Tento dodatek má význam jen pokud původnísít obsahuje velký počet těchto tenkých trojúhelníků.

4.5 Sebeprotínání sítě

Jak již bylo řečeno, autoři článku [19] se domnívají, ze není nutné zabraňovatsebeprotínání při deformaci sítě. Při testování algoritmu jsem došel k závěru, žepro běžná data, tedy pro hladké modely jako jsou svaly či kosti, tento problémnenastává. Může však nastat extrémní případ, kdy k sebeprotnutí dojít může.Obrázek 4.4a tuto možnost naznačuje. Stejná situace platí, pokud jde o 2 kom-ponenty modelu v jedné scéně.

15

4 Vylepšení algoritmu

(a) (b)

Obrázek 4.4: Možnost sebeprotnutí (a) Bez omezení (b) S omezením parametruMeshRoughness

Testy však ukázaly, že omezením parametru MeshRougness (v kapitole 6.3.4se dozvíme, že je použit pro kontrolu okolí na „jehlyÿ kontrolou úhlu mezi troj-úhelníky právě vznikajícího okolí Fi) dosáhneme zákazu této decimace a tím ivzniku sebeprotnutí. Obrázek 4.4b tuto možnost ukazuje, zdecimují se nejprvekrajní hrany a poté dojde k „vyplněníÿ celé „baňkyÿ, jak naznačují světlé hrany.Tyto decimace jsou povoleny, protože úhly, které jsou v procesu kontrolovány,špičaté nejsou (na obou obrázcích je minimální úhel pro povolení decimace zob-razen světle modře). Možná se zdá, že je výběr decimací zvláštní či libovolný, je sitřeba ale uvědomit, že postupným zamítnutím okolních decimací je možné právě ktěmto vhodným decimacím dojít. Pokud parametr MeshRougness omezíme více,decimace vůbec nenastane a celé okolí bude zachováno v původní podobě. Jenutné také dodat, že je kontrolován vždy ten menší úhel, ať vnitřní či vnější.Vhodnou volbou parametru MeshRougness tedy lze sebeprotínání předejít a to ipro modely o více komponentách, jak ukazuje obrázek B.3.

Možností, jak zabránit sebeprotnutí, by bylo hranám, které by sebeprotnutímohly způsobit, přidat další podmínky lineárního programování pro jejich pro-tější trojúhelníky. Je ale zřejmé, že by došlo k decimaci a vzniku malé „jehlyÿna levé straně náčrtu. Decimace druhé strany by neproběhla (jinak by došlo ksebeprotnutí), postupně by však proběhly všechny ostatní decimace a výsledekby byl velmi podobný obrázku 4.4b. Nevýhodou tohoto přístupu je, že bychommuseli hledat protější trojúhelníky. To je výpočetně velmi složité, nabízí se zjed-nodušení pomocí Octree [20] - rozdělení prostoru na menší části a poté sestavenípodmínek pro všechny trojúhelníky v té části, ve které se nachází decimovanáhrana, případně trojúhelníků v okolních částech. Tento postup však není nutný,pokud nám stačí pouze najít vhodný parametr MeshRougness. Pokud bychom

16

5 Knihovny použité pro implementaci

však potřebovali algoritmus více zobecnit, tuto kontrolu by bylo nutné zahrnout.

5 Knihovny použité pro implementaci

5.1 VTK - Visualisation Toolkit

Jedním z požadavků na tuto práci je kompatibilita s balíkem knihoven Visuali-sation Toolkit neboli VTK. Tento systém zprostředkovává mimo jiné knihovnypro zpracování a vizualizaci dat a pro práci s 3D grafikou většinou prostřednic-tvím OpenGL. Systém je vyvinut v jazyce C++, je však přizpůsoben pro použitíi v jiných jazycích (Java, Python, . . .). Velmi dobrými zdroji pro pochopení práces VTK jsou tutoriál [1] a dokumentace [8].

Obrázek 5.1: Logo VTK. Převzato z [8]

VTK používá systém bloků kaskádovitě seřazených do potrubí - pipeline. Tutopipeline zobrazuje obrázek 5.2. Zdroj dat (Data source) poskytuje data ke zpraco-vání. Může jít o generovanou aproximaci nějakého geometrického tělesa, výsledekmatematické funkce, nebo o data načtená ze souboru. Zdrojová data jsou předánaFiltrům ke zpracování (různé matematické operace) a na jejich výstupu jsou ho-tová data připravená k zobrazení. Dále je využit Mapper, který z dat vytvoří jejichvizuální podobu, která je upravena blokem Actor. Ten je schopen měnit vizuálníparametry, jako je barva, způsob stínování, drátěná reprezentace apod. Posled-ním blokem pipeliny je Renderer. Ten má za úkol vykreslení dat na obrazovku (dovlastního okna RenderWindow, nebo je použit Viewport v okně již vytvořeném).Ovládání je poskytnuto pomocí Interactoru, kterých je opět několik typů (myš,klávesnice. . .) v závislosti na požadovaném způsobu interakce s uživatelem. Celápipeline funguje na principu požadování dat od předchozího bloku, bloky jsoutedy spouštěny jen když je potřeba a tím jsou eliminovány nadbytečné výpočtya zatížení systému.

Tento balík knihoven nám nejen usnadní zobrazení výsledků naší práce, aletaké definuje abstraktní třídu vtkPolyDataToPolyDataFilter, kterou použijemepro implementaci našeho kódu. Jakákoliv třída dědící od této abstraktní třídytotiž může být zařazena do pipeliny a poskytnout změny v datech, což je přesněto, co pro implementaci decimačního filtru potřebujeme. Hlavní metodou této

17

5 Knihovny použité pro implementaci

Obrázek 5.2: Pipeline systému VTK. Převzato a upraveno z [1].

třídy je metoda Execute() která je spuštěna kdykoliv jsou potřebná data vyža-dována následujícím blokem pipeliny. Implementací této metody se budu věnovatv kapitole 6.3.

Knihovna je distribuována ve zdrojových kódech, je tedy ji nutné nejprvepřeložit pomocí nástroje CMake.

5.2 lp solve

Knihovnu lp solve [2], Mixed Integer Linear Programming solver, aktuálně veverzi 5.5.2.0, použijeme pro výpočet úlohy lineárního programování. Tato knihovnaimplementuje Revidovaný simplexový algoritmus [3] pro úlohy s reálnými číslya metodu větví a mezí (Branch-and-bound) pro výpočet celočíselných úloh. Jeschopna řešit čistě lineární, smíšené (celočíselné a binární), polospojité a speci-ální úlohy. Podporuje mnoho programovacích jazyků (C, C++, Pascal, Delphi,Java, VB, C#, VB.NET, Excel. . .), většinou pomocí wrapperů. My však vyu-žijeme nativně přeloženou knihovnu11 kterou budeme volat přes lp solve API.Knihovna slibuje vysokou stabilitu výpočtu a téměř neomezený počet proměn-ných a omezujících podmínek. Pro naše účely je tedy více než vyhovující (budememít pouze 3 proměnné a maximálně cca 20 podmínek podle počtu trojúhelníkův jednotlivých Fi+1). Distribuce obsahuje zdrojové kódy knihovny i její statickyči dynamicky použitelné binární podoby, pro OS Windows a Linux. Pro použitína jiném operačním systému si uživatel musí stáhnout zdrojové kódy knihovny azkompilovat je pod tímto systémem; knihovna je vyvinuta v jazyce ANSI C.

11Používám dynamickou knihovnu, protože statická byla v konfliktu s VTK

18

6 Implementace

6 Implementace

6.1 Způsob implementace

Implementaci jsem provedl v jazyce C++ s využitím vývojových prostředí Micro-soft Visual Studio 2008 (v rámci projektu 5) a Microsoft Visual Studio 2010(v rámci bakalářské práce) a za použití výše uvedených knihoven. Algoritmussamotný je implementován ve třídě vtkProgressiveHull která dědí od třídyvtkPolyDataToPolyDataFilter balíku VTK. Pro testování a demonstrační účelyjsem vytvořil aplikaci DemoApp. Prioritní fronta je implementována v souborupriorityQueue.h. Po odladění mého algoritmu jsem přistoupil k jeho začleněnído třídy MeshSurface, která je součástí řešení P. Kellnhofera.

6.2 DempApp - demonstrační aplikace

Demonstrační aplikace je implementována v souboru DemoApp.cxx. Implemen-tuje základní pipeline popsanou v kapitole 5.1. Jako zdroj dat je použit soubor.VTK podporuje více datových formátů, nás ale budou zajímat pouze dva - for-mát .vtk a formát .obj. Formát .vtk (popsaný v [13]) budeme využívat, protožejde o formát, ve kterém máme dostupná data. Formát .obj (popsaný v [18]) bu-deme využívat, protože do něj lze exportovat sítě vytvořené v programu Blender(pro testovací účely). Pro jejich čtení využijeme vtkPolyDataReader respektivevtkOBJReader. Obě tyto třídy předávají na výstup objekt typu vtkPolyData.

Po načtení dat je do pipeline zařazen můj filtr a následně je implemento-ván zbytek pipeline podle obrázku 5.2. Tato je dvojitá, pro současné zobrazenípůvodních dat a výstupu mého filtru.

6.3 Implementace samotného filtru

Aby vtkProgressiveHull splňoval parametry vtkPolyDataToPolyDataFilter,musí implementovat proměnné InputMesh a OutputMesh typu vtkPolyData ametodu Execute(). Odkaz na vstupní data je předán rodičovskou metodou GetInput()do proměnné InputMesh, která jsou poté zpracována metodou Execute() a pře-dána na výstup OutputMesh. Metoda Execute() volá další metody, jejichž funkceje popsána v následujícím textu.

Filtr má pouze prázdný konstruktor, pro veškeré parametry jsou přidányGetry a Setry:

• TargetReduction - poměr počtu vrcholů původní a zdecimované sítě

• MeshRoughness - drsnost povrchu zdecimované sítě (-1: hladký povrch; 1:velmi hrubý povrch [kontrola „jehelÿ je vypnuta])

19

6 Implementace

• MeshQuality - kvalita trojúhelníků v zdecimované síti (0: nekontroluje se;1: maximální dosažitelná kvalita)

• EnlargeMeshAmount - dodatečné zvětšení/zmenšení zdecimované sítě sítě(poměr)

6.3.1 InitMesh()

Použití dat přímo v reprezentaci pomocí vtkPolyDatamůže být pomalé a nepoho-dlné. Metoda InitMesh() má tedy kromě inicializace filtru za úkol také převedenívstupních dat do vnitřních datových struktur (každé primitivum je reprezento-váno instancí vnořené třídy CVertex, CTriangle nebo CEdge) a je využita struk-tura vector z knihovny Standard Template Library (STL) pro seznamy těchtoprimitiv. Převedení je provedeno postupně, nejprve jsou načteny vrcholy a potétrojúhelníky. Třída vtkPolyData reprezentuje trojrozměrná data, seznam vrcholůa tzv. buněk(Cells).

Není však pravidlem, že jedna buňka obsahuje jeden trojúhelník. Zjistímetedy jakého typu buňka je a data z ní adekvátním způsobem převezmeme. Sou-časná verze podporuje buňky s jednotlivými trojúhelníky, dvojicemi trojúhelníkův uspořádání triangle strip (použito ve VTK souborech) a dvojicemi trojúhelníkův uspořádání quad (použito v některých OBJ souborech). Jakákoliv jiná data jsouignorována.

Pro všechny trojúhelníky jsou také spočteny normály a jejich objemové pří-spěvky. Jsou také nastaveny čítače (trojúhelníků, vrcholů) a proměnné pro vý-počet úrovně decimace, celkový objem původního tělesa atd. Je také vytvořenainstance třídy lp solve.

6.3.2 BuildMesh()

Tato metoda vytváří vztahy mezi trojúhelníky a vrcholy (hledá tzv. One RingPrimitives, okolní primitiva pro každé primitivum, např. OneRingVertex - se-znam okolních vrcholů daného primitiva) a z dat jednotlivých trojúhelníků hledáhrany. Víme-li, že dva trojúhelníky sdílejí dva vrcholy, víme, že tyto vrcholy spo-juje hrana. Metoda BuildMesh() však kontroluje, zda jsou trojúhelníky správněorientovány (vizte obrázek 6.1). Jsou-li indexy obou vrcholů hrany pro oba troj-úhelníky ve stejném pořadí, znamená to, že je jeden z trojúhelníků chybně ori-entován. Takováto hrana je označena jako chybná a není později decimována.Pravděpodobně by bylo možné pořadí vrcholů těchto trojúhelníků obrátit, tojsem však neimplementoval. Mohlo by to být předmětem další práce na filtru.Po průchodu touto metodou tedy máme informace o vrcholech, trojúhelnících,hranách a sousednostech mezi těmito primitivy.

20

6 Implementace

(a) (b)

Obrázek 6.1: Orientace trojúhelníků podle pořadí jejich vrcholů. (a) Chybná ori-entace (b) Správná orientace

6.3.3 PrioritizeEdges()

Tato metoda volá metodu double ComputePriorityFast(int edgeID) pro vý-počet priority všech hran sítě a předává tyto hrany spolu s prioritou do prioritnífronty. Zdrojový kód prioritní fronty byl dodán vedoucím práce, rozhodl jsem sejej ale přepsat s použitím STL pro konzistenci a rychlost. Tato fronta je implemen-tována jako halda na poli m Data, seřazená podle priority od nejnižší k nejvyššía jednotlivé prvky jsou mapou m MapTable namapovány k jejich objektům (vnašem případě hranám) pro možnost úpravy jejich priority.

Metoda double ComputePriorityFast(int edgeID) je implementována podlekapitoly 4.2 s využitím seznamu OneRingVertex obou vrcholů zadané hrany. Vý-počet těchto priorit je pro jednotlivé hrany disjunktní, bylo by tedy možné jejurychlit paralelizací. Jelikož je však tento výpočet krátký vzhledem k výpočtudecimací, není paralelizace implementována. Vzhledem k algoritmu 3.3 je tatometoda přípravnou fází algoritmu.

6.3.4 Decimate() a Substitute()

Tato metoda vybírá hrany z prioritní fronty a volá na nich metodu Substitute-(CEdge* e) dokud není fronta prázdná nebo dokud není dosažena požadovaná de-cimace sítě (řízena parametrem TargetReduction) . Metoda Substitute(CEdge*e) je nejdůležitější a nejsložitější metodou celého filtru. Nejprve je pro hranu e vy-počten vrchol decimace metodou ComputeDecimationPoint(int edgeID). Je-lihrana připravena k decimaci a není li již označena jako smazána, je volána metodabool CheckSpikeAndTriangles().

Tato metoda kontroluje možnost vzniku „jehlyÿ tak, že provede „virtuálnídecimaciÿ12 a vytvoří pole normál všech trojúhelníků v jejím okolí. Porovná-ním těchto normál skalárním součinem (každou s každou) získáme maximální

12Nahrazení vrcholů hrany decimovaným vrcholem ve všech okolních trojúhelnících, ale pouzedočasně, v původních strukturách se nic nemění

21

6 Implementace

odklonění normál, na jehož základě decimaci hrany povolíme nebo zamítneme,podle parametru MeshRoughness. Tato metoda také kontroluje kvalitu trojúhel-níků podle kapitoly 4.4 dle parametru MeshQuality.

Pokud navrhovaná decimace hrany projde všemi podmínkami, je na řadě jejínahrazení vypočteným vrcholem. To provedeme tak, že jeden (první) vrchol hranybudeme považovat za nahrazující vrchol a okolí Fi+1 upravíme na okolí Fi. Tentoproces naznačuje obrázek 6.2.

• Vrchol Ve1 posuneme na souřadnice nahrazujícího vrcholu

• Označíme primitiva, která se v Fi nevyskytují, jako smazaná (na obrázku6.2 červeně)

• Okolní trojúhelníky, hrany a vrcholy13 vrcholu Ve1 přiřadíme vrcholu Ve1.

• Opravíme sousednosti trojúhelníků sousedících s mazanými trojúhelníky(na obrázku 6.2 modře)

• Přepočítáme normály a přírůstky objemů všech trojúhelníků v právě vy-tvořeném okolí Fi a aktualizujeme priority všech hran v tomto okolí

Obrázek 6.2: Nahrazení hrany a rekonstrukce okolí po decimaci

13Zde zabráníme duplicitním výskytům vrcholů v seznamu okolních vrcholů vrcholu Ve1 kvůlipozdějšímu správnému výpočtu vrcholu pro výpočet priority. Duplicity ostatních primitiv budouignorovány.

22

6 Implementace

6.3.5 ComputeDecimationPoint() a SolveLP()

Tato metoda vyhledá data (trojúhelníky z okolí Fi+1 pro omezující podmínky asestaví vektor ~A pro cílovou funkci (vizte kapitolu 3.4) pro metodu SolveLP(). Taprojde tyto data a vytvoří pro ně omezující podmínky a nastaví lp solve. Je nutnénejprve vymazat podmínky z předchozí iterace, přepnout solver do řádkovéhomódu (rychlejší přidávání a eliminace zcela zjevně zcestných podmínek), postupněpodmínky přidat, nastavit koeficienty cílové funkce (z vektoru ~A) a nastavit cílo-vou operaci na minimalizaci. Je velice důležité odstranit přednastavené podmínkynezápornosti proměnných, jelikož námi vypočítaný vrchol pro decimaci může býtkdekoliv v prostoru. Vypočtená data získáme metodami get objective() (vy-počtený nárůst objemu) a get variables() (souřadnice vrcholu pro decimaci).Byl-li výpočet neúspěšný, je nutné hranu označit jako nepřipravenou k decimaci,aby nedošlo k chybám v síti.

6.3.6 EnlargeMesh()

Tato metoda dodatečně zvětší síť o požadovaný počet jednotek (nastavený para-metrem EnlargeMeshAmount). Posune všechny vrcholy sítě ve směru jejich nor-mály (průměr normál okolních trojúhelníků). Pozor, tato metoda může způsobitsebeprotínání sítě.

6.3.7 DoneMesh() a ClearMesh()

Metoda DoneMesh() zrekonstruuje výstupní vtkPolyData z dat v interních struk-turách. Primitiva označená jako smazaná jsou vyřazena a identifikátory vrcholůjsou přemapovány, aby byly odstraněny „díryÿ v jejich seznamu.

Metoda ClearMesh() uvolní veškerou alokovanou paměť, včetně solveru.

23

6 Implementace

6.4 Začlenění filtru do třídy MeshSurface

MeshSurface je třída naprogramovaná Petrem Kellnoferem pro využití ve filtruvtkMEDPolyDataDeformationPK, jehož autorem je také on. Tato třída má za úkolvytvořit hrubou síť a vypočítat vztah bodů této sítě k původní trojúhelníkové sítitělesa. Nás zajímá hlavně metoda CreateCoarseMesh(vtkPolyData* source,float minimalizationFactor), která tuto hrubou síť vytváří. Původní postupa mnou použitý postup naznačuje obrázek 6.3

(a)

(b)

Obrázek 6.3: Začlenění mého filtru. (a) Původní způsob vytváření hrubé sítě(převzato z [10]) (b) Použití vtkProgressiveHull

Původní postup používá 2 průchody sítě decimátorem, první pro získání sítěo menším počtu vrcholů a druhý pro zamezení sebeprotínání po zvětšení sítě.Pro každý průchod je vypočtena poměrná decimace tak, aby výslednou síť bylazredukována podle parametru minimalizationFactor. Síť je zvětšena, aby bylozajištěno, že bude vně původního tělesa. Můj filtr tuto podmínku splňuje

24

7 Testy a dosažené výsledky

již během decimace a decimace je provedena v jednom průchodu přímo na redukciminimalizationFactor. Je ale stále nutné mým filtrem vytvořenou síť zvětšit,aby byla filtrem P.Kellnhofera akceptována. Více o tomto problému vizte kapitolu7.4.

7 Testy a dosažené výsledky

Všechny testy jsem provedl na této sestavě:

Procesor: AMD Athlon(tm) 64 X2 4200+Počet jader: 2Frekvence jader: 2,21 GHz

Paměti: Kingston KVR667D2N5K2/2GTyp: DDR2Uspořádání: 2x 1GB Dual ChannelTaktovací/pracovní frekvence: 333/667 MHzPropustnost: 5,333 GB/s

Operační systém: Windows 7 ProfessionalVerze: x64

Testy jsem provedl na aplikaci přeložené s nastavením Release.

7.1 Časová náročnost

Provedl jsem zátěžové testy na třech vstupních souborech

1. Redukovaný Stanfordský králíček - 2 503 vrcholů, 4 968 trojúhelníků, častopoužívaný model pro testování algoritmů počítačové grafiky

2. Sval krejčovský(Sartorius) - 9 001 vrcholů, 17 982 trojúhelníků, reprezentujeběžně objemná data používaná filtrem P. Kellnhofera

3. Pánev(Pelvis) - 89 997 vrcholů, 179 994 trojúhelníků, objemná data provelkou zátěž algoritmu

pro různé (cílové) úrovně decimace s nastavením MeshRoughness = 0,3 a Me-shQuality = 1,0 pro všechny testy. Naměřená data jsou v tabulce B.1a a měřenízobrazují grafy 7.1a, 7.1b a 7.1c.

Z naměřených dat a z grafů je patrné, že časová náročnost algoritmu je téměřlineární, ale je závislá na vstupních datech. Je vidět, že počet operací a tedyi časová náročnost není přímo závislá na počtu decimovaných hran, jelikož je

25

7 Testy a dosažené výsledky

0 10 20 30 40 50 60 70 80 90 1000

1000

2000

3000

4000

5000

6000

Čas decimačních operací podle úrovně decimaceStandfordský králíček

Čas přípravyČas decimaceCelkový čas běhu filtru

Úroveň decimace [%]

Čas

[ms]

(a)

0 10 20 30 40 50 60 70 80 90 1000

5000

10000

15000

20000

25000

Čas decimačních operací podle úrovně decimaceSval krejčovský - Sartorius

Čas přípravyČas decimaceCelkový čas běhu filtru

Úroveň decimace [%]

Čas

[ms]

(b)

0 10 20 30 40 50 60 70 80 90 1000

40000

80000

120000

160000

200000

Čas decimačních operací podle úrovně decimacePánev - Pelvis

Čas přípravyČas decimaceCelkový čas běhu filtru

Úroveň decimace [%]

Čas

[ms]

(c)

Obrázek 7.1: Časy operací decimace vzhledem k úrovni decimace pro modely(a) Stanfordský králíček (b) Sval krejčovský - Sartorius (c) Pánev - Pelvis

nemálo elementárních decimací v procesu zakázáno aplikací podmínek z kapitoly4 a počet těchto zákazů v průběhu decimace roste. Pokud se decimace blíží kmaximu, výpočetní náročnost stoupá nejstrměji, což je způsobeno tím, že je přivelmi hluboké decimaci počet zamítnutých decimací podstatně vyšší. Dokud je

26

7 Testy a dosažené výsledky

tedy síť hustá, podmínky nehrají příliš velkou roli, v malém počtu trojúhelníkůjsou však nevhodné decimace pravděpodobnější a tím je jich více zamítnuto.

Z grafu 7.1a je také patrné, jak algoritmus podmínky dodržuje. Není-li žádnáhrana ve frontě podle podmínek decimovatelná, decimace sítě je ukončena. Promodel Stanfordského králíčka je tedy nemožné pro parametry MeshRoughness =0,3 a MeshQuality = 1,0 dosáhnout vyšší než 95%-ní decimace. Je také vidět, žečas potřebný pro přípravné výpočty algoritmu je konstantní a vzhledem k časupotřebnému k hluboké decimaci zanedbatelný.

7.2 Vliv parametrů na rychlost decimace

Zjistili jsme, že podmínky z kapitoly 4 ovlivňují rychlost algoritmu. Provedl jsemtedy další měření na modelu Stanfordského králíčka, abych zjistil jakým způso-bem. Cílem všech těchto měření je 80%-ní decimace.

-1 -0,75 -0,5 -0,25 0 0,25 0,5 0,75 10

500100015002000250030003500400045005000

Vliv parametrů na čas decimacepro parametry MeshRoughness a MeshQuality

Čas decimace (změna členitosti)Čas decimace (změna kvality)

Hodnota parametru

Čas

dec

imac

e [m

s]

Obrázek 7.2: Vliv parametrů na čas decimace

Z grafu 7.2 je vidět, že parametr MeshRoughness ovlivňuje rychlost decimacepro záporné hodnoty velmi výrazně. To je dáno tím, že pro záporné hodnoty para-metru jsou povoleny pouze decimace, které jsou „hladkéÿ - úhel mezi trojúhelníkyv okolí je po decimaci větší než π/2. Jelikož je model Stanfordského králíčka velmioblý, decimace tuto podmínku často splňují, model ale obsahuje mnoho detailů(uši, tlapky, ocásek), kde tuto podmínku není možné splnit a decimace se zpo-maluje. Pro hodnotu MeshRoughness = -0.9 je také vidět, že nelze dosáhnout80%-ní decimace (parametr je příliž omezující, pro náhled vizte kapitolu 7.3).Parametr MeshQuality na model Stanfordského králíčka příliš velký vliv nemá,jelikož je model pravidelný a neobsahuje úzké trojúhelníky. Tento algoritmus nenípříliš efektivní, bylo by lepší kvalitu trojúhelníků vylepšit až v postprocessingu(například posunutím některých bodů).

27

7 Testy a dosažené výsledky

7.3 Vizuální porovnání

V kapitole 3.1 jsme měli možnost vidět výsledky autorů tohoto algoritmu. Před-kládám tedy vizuální porovnání mého upraveného algoritmu pro porovnání. Ob-rázek B.1 zobrazuje obálky pro různé úrovně decimace. Nastavení parametrů jeMeshRoughness = 0 a MeshQuality = 1. Ač algoritmus pro tato nastavení neníschopen vytvořit obálku o 38 trojúhelnících, je výpočet mnohem rychlejší, než vpřípadě původního algoritmu (časy původního algoritmu byly pro tento model vřádech minut).

Dále přikládám vizuální porovnání vlivu parametru MeshRoughness na kva-litu sítě na obrázku B.2. Je vidět, že při velmi nízkém nastavení (-0,9) algoritmusdecimuje pouze oblé plochy. Je ale vidět (zvláště na uších na B.2a) jak tentoparametr nutí decimovanou síť lépe obklopovat původní těleso a generovat pra-videlnější síť. Ideální nastavení tohoto parametru se tedy pohybuje od 0 do 0,5.

Tento parametr také může mít vliv na případný výskyt sebeprotínání. ObrázekB.3 ukazuje Pánev(Pelvis) pro MeshRoughness roven hodnotám 0 a -0,4. Je vidět,že dalším omezením parametru lze docílit přiblížení decimované sítě k původnísíti a zamezit tak výskytu sebeprotínání.

7.4 Výsledky po začlenění filtru do třídy MeshSurface

Dle mého názoru můj filtr v současnosti produkuje kvalitní obálky. Po začleněnífiltru do třídy MeshSurface jsem tedy očekával zlepšení výsledků celého defor-mačního filtru P. Kellnhofera. Hledal jsem vhodná nastavení, závěry však nejsoustoprocentní. Nejlepších výsledků jsem dosáhl s nastavením MeshRoughness =0,5 ; MeshQuality = 1 a zvětšení o 5 jednotek. Na obrázku B.4 je zobrazena Ste-henní kost (Femur) před a po aplikaci mého filtru. Je vidět, že je zdeformovaná a„nafoukláÿ. V průběhu hledání jsem došel k závěru, že deformační filtr vyžadujeobálky velmi vzdálené od původní sítě. To je pro můj filtr problém, jelikož produ-kuje obálky, které jsou velmi blízké původní síti. Přišel jsem se třemi možnostmiřešení:

1. Upravit deformační filtr, aby byl schopen pracovat i s velmi blízkými sítěmi

2. Po vytvoření obálky mým filtrem ji zvětšit podobně jako byly zvětšoványobálky původní14

3. Upravit vytváření obálky tak, aby byla postupně zvětšována již při deci-maci15

14Tuto možnost jsem vyzkoušel. Bohužel je ale deformační filtr velmi náchylný k chybám tam,kde v hrubé síti dochází k sebeprotínání (vizte tenké chyby na obrázku B.4a). K tomu však přizvětšení obálky často dochází.15Tento přístup by eliminoval nutnost hledat sebeprotínání během decimace.

28

Reference

Vyzkoušel jsem tedy můj filtr pro deformaci Svalu krejčovského (Sartoria), se kte-rým byl problém v původní verzi deformačního filtru, kvůli kolapsu decimace nakonci tohoto svalu při vytváření obálky. Je patrné zlepšení (můj filtr nekolabuje),ovšem výsledek stále není ideální, pravděpodobně kvůli sebeprotínání. Porovnáníje na obrázku B.5.

8 Závěr

V průběhu práce jsem si vyzkoušel práci s knihovnami VTK a programování vjazyce C++. Naučil jsem se kombinovat více myšlenek do jednoho celku za úče-lem lepšího výsledku. Projekt 5 ukázal, že algoritmus Progressive Hull je funkční.V rámci bakalářské práce jsem jej vylepšil a optimalizoval tak, aby jeho výsledky(a výsledky implementovaného decimačního filtru) byly co nejlepší. Mnohdy šloo metodu pokus-omyl, jelikož i malá změna v teorii či kódu má velký dopad nastabilitu/rychlost/výsledky algoritmu. Pro dodaná data se mi však podařilo od-stranit většinu nedostatků algoritmu a ten nyní celkem rychle produkuje kvalitníobálky, které zachovávají tvar původního tělesa (někdy až příliš).

Jednou z mála slabin algoritmu je závislost na chybách ve vstupních datech.Největším problémem je existence lokálních míst v síti s nulovým objemem (nebolilokální místa „papírovéÿ tloušťky). Tento problém nyní algoritmus přeskakuje atato lokální okolí jsou zachována v původním stavu, stejně jako u okrajů (místa,kde jsou hranice sítě, kde trojúhelníky nemají další sousedy).

V implementační části jsem vyzkoušel použití algoritmu v praxi, ukázalo sevšak, že současná verze vhodná pro požadované účely vhodná zcela není, i kdyžslibuje lepší výsledky než původně použitý postup. Výsledky, kterých jsem dosáhlvšak naznačují, že bude nutná pouze malá úprava algoritmu, několik návrhů tétoúpravy jsem již naznačil v kapitole 7.4. Je třeba zmínit, že rychlost algoritmu jeextrémně závislá na způsobu překladu (Debug/Release nastavení překladače).

Body zadání týkající se vytváření vnějších obálek těles reprezentovaných tri-angulovanými sítěmi se zachováním detailů se mi dle mého názoru podařilo splnit,výsledky po začlenění do programového vybavení P. Kellnhofera však nejsou takkvalitní, jak bylo očekáváno.

Sazba tohoto dokumentu byla vytvořena pomocí nástroje LATEX s použitím pro-gramu TEXnicCenter.

Reference

[1] Bell, J. T.: Visualization Toolkit ( VTK ) Tutorial. [Online], 2004, platné k18.4.2011.URL http://www.cs.uic.edu/~jbell/CS526/Tutorial/Tutorial.html

29

Reference

[2] Berkelaar, M.; Dirks, J.; Eikland, K.; aj.: lp solve API reference. [Online],2010.URL http://lpsolve.sourceforge.net/5.5/

[3] Chvátal, V.: Linear Programming. W. H. Freeman and Company, New York,1983, ISBN 0-71671-587-2, 478 s.

[4] Edelsbrunner, H.: The union of balls and its dual shape. Discrete Compu-tational Geometry, ročník 13, 1995: s. 415–440.

[5] Edelsbrunner, H.; Mücke, E. P.: Three-dimensional alpha shape. ACMTransactions on Graphics, ročník 13, č. 1, 1994: s. 43–72.

[6] Goldsmith, J.; Salmon, J.: Automatic Creation of Object Hierarchies for RayTracing. IEEE Comput. Graph. Appl., ročník 7, May 1987: s. 14–20, ISSN0272-1716, doi:10.1109/MCG.1987.276983.URL http://portal.acm.org/citation.cfm?id=31468.31469

[7] Guéziec, A.: Locally Toleranced Surface Simplification. IEEE Transactionson Visualization and Computer Graphics, ročník 5, Duben 1999: s. 168–189, ISSN 1077-2626, doi:10.1109/2945.773810, kapitola 5: Description ofthe Algorithm, strana 11, třetí test.URL http://portal.acm.org/citation.cfm?id=614274.614429

[8] van Heesch, D.: VTK 4.0.2 Documentation. [Online], 2001, revize 1.1080.2.1,platná k 12.10.2010.URL http://www.vtk.org/doc/release/4.0/html/

[9] Hoppe, H.: New quadric metric for simplifying meshes with appearance attri-butes. In Proceedings of the 10th IEEE Visualization 1999 Conference (VIS’99), VISUALIZATION ’99, Washington, DC, USA: IEEE Computer Soci-ety, 1999, ISBN 0-7803-5897-X, s. –.URL http://portal.acm.org/citation.cfm?id=832273.834119

[10] Kellnhofer, P.: Deformace povrchového modelu se zachováním objemu. Ba-kalářská práce, Západočeská univerzita, Plzeň, Česká Republika, 2010.

[11] Kellnhofer, P.: Deformace povrchového modelu se zachováním objemu. Baka-lářská práce, Západočeská univerzita, Plzeň, Česká Republika, 2010, kapitola5.4: Použití hrubé sítě.

[12] Kellnhofer, P.: Deformace povrchového modelu se zachováním objemu. Baka-lářská práce, Západočeská univerzita, Plzeň, Česká Republika, 2010, kapitola5.2.1: Barycentrické souřadnice pro 3D sítě.

30

Reference

[13] Kolektiv autorů: VTK File Formats for VTK Version 4.2. [Online], Březen2010, dostupné online.URL http://www.vtk.org/VTK/img/file-formats.pdf

[14] Lambert, T.: Convex Hull Algorithms. [Online], 1998, platné k 27. 4. 2011.URL http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

[15] Lindstrom, P.; Turk, G.: Fast and Memory Efficient Polygonal Simpli-fication. Visualization Conference, IEEE, ročník 0, 1998: s. 279+, doi:10.1109/VISUAL.1998.745314.URL http://dx.doi.org/10.1109/VISUAL.1998.745314

[16] Žára, J.; Beneš, B.; Sochor, J.; aj.: Moderní počítačová grafika, kapitola22.2.4. Brno: Computer Press, druhé, přepracované a rozšířené vydání, 2005,ISBN 80-251-0454-0, str. 558.

[17] Žára, J.; Beneš, B.; Sochor, J.; aj.: Moderní počítačová grafika, kapitola22.2.3. Brno: Computer Press, druhé, přepracované a rozšířené vydání, 2005,ISBN 80-251-0454-0, str. 557.

[18] Reddy, M.: Wavefront Object Files. [Online], 1994, platné k 18.4.2011.URL http://www.martinreddy.net/gfx/3d/OBJ.spec

[19] Sander, P. V.; Gu, X.; Gortler, S. J.; aj.: Silhouette clipping. In Procee-dings of the 27th annual conference on Computer graphics and interactivetechniques, SIGGRAPH ’00, New York, NY, USA: ACM Press/Addison-Wesley Publishing Co., 2000, ISBN 1-58113-208-5, s. 328–329, doi:http://dx.doi.org/10.1145/344779.344935.URL http://dx.doi.org/10.1145/344779.344935

[20] Surhone, L.; Tennoe, M.; Henssonow, S.: Octree. VDM Verlag Dr. MuellerAG & Co. Kg, 2010, ISBN 9786131288753.URL http://books.google.com/books?id=UfiicQAACAAJ

31

Přílohy

Přílohy

A Uživatelská příručka

Instalace programu není potřeba, jde o přeložené binární soubory. Veškeré knihovnyjsou v přeložené podobě přiloženy. Pokud by to však bylo vyžadováno, je nutnéstáhnout z webu http://www.vtk.org/ zdrojové soubory a přeložit je za pomociprogramu CMake. Aplikace je kompatibilní s VTK verze 4.2 a vyšší.

Program DemoApp.exe se spouští jako konzolová aplikace, vyžaduje parametrys názvem vstupního souboru, úroveň decimace, členitost sítě (-1,0 - 1,0) a kvalitasítě (0 - 1,0). Volitelně lze definovat název výstupního souboru, do kterého jevýsledek uložen ve formátu VTK (pokud je specifikován soubor *.vtk) nebo jakoobrázek do souboru PNG (pokud je specifikován soubor *.png). Při nastavenívýstupního souboru je běh programu ukončen po decimaci. Statistiky běhu jsouukládány do souboru Log.txt Běh programu je zachycen na obrázku A.1. Formátvstupních parametrů: DemoApp.exe název vstup úroveň decimace členitost sítěkvalita sítě [název výstup]

Obrázek A.1: Běh programu

Po zobrazení okna s vizualizací dat je možné modelem otáčet, přibližovat jej aposouvat myší. Ovládání je závislé na použité verzi VTK, ale je velmi intuitivní.

32

Přílohy

B Obrázky a tabulky

(a) 2503 (b) 599 (c) 300

(d) 199 (e) 149 (f) 93

Obrázek B.1: Výsledky algoritmu pro různé úrovně decimace. Číselný údaj udávápočet vrcholů obálky.

(a) MR: -0,9 n: 1568 (b) MR:0 n: 500 (c) MR:0,9 n: 500

Obrázek B.2: Výsledky algoritmu pro různé úrovně parametru MeshRoughness.Číselný údaj udává nastavení tohoto parametru a počet vrcholů obálky. Cílovádecimace byla pro všechny testy 80%-ní, kvůli velkému omezení v případě (a)však požadovaná decimace nebyla možná.

33

Přílohy

Mod

elÚ

rove

ňde

cim

ace

0,00

%20

,00%

40,0

0%60

,00%

80,0

0%85

,00%

90,0

0%95

,00%

Max

imál

níB

unny

Vrc

holů

po

deci

mac

i25

0320

0215

0110

0150

037

525

014

014

0Č

aspř

ípra

vy[m

s]15

316

015

316

515

615

415

515

615

3Č

asde

cim

ace

[ms]

4575

713

8221

8134

7935

7138

6647

9248

08C

elko

výča

s[m

s]19

891

715

3523

4636

3537

2540

2149

4849

61Č

as/P

očet

deci

mac

í-

1,51

1,38

1,45

1,74

1,68

1,72

2,03

2,03

Sart

oriu

sV

rcho

lůp

ode

cim

aci

9001

7200

5400

3600

1800

1350

900

450

336

Čas

příp

ravy

[ms]

601

613

577

589

565

621

583

623

601

Čas

deci

mac

e[m

s]10

525

0849

9280

1412

085

1346

714

667

1706

418

586

Cel

kový

čas

[ms]

706

3121

5569

8603

1265

014

088

1525

017

687

1918

7Č

as/P

očet

deci

mac

í-

1,39

1,39

1,48

1,68

1,76

1,81

2,00

2,14

Pel

vis

Vrc

holů

po

deci

mac

i89

997

7199

753

998

3599

817

999

1349

989

9944

9931

0Č

aspř

ípra

vy[m

s]59

1756

5159

9955

3655

8158

9256

8557

5456

89Č

asde

cim

ace

[ms]

988

2354

848

319

7355

010

4286

1138

0112

4232

1354

5616

6093

Cel

kový

čas

[ms]

6905

2919

954

318

7908

610

9867

1196

9312

9917

1412

1017

1782

Čas

/Poč

etde

cim

ací

-1,

311,

341,

361,

451,

491,

531,

581,

85

(a)

Čle

nito

stsí

tě-0

,9-0

,45

00,

450,

9Z

bylý

chvr

chol

ů15

6850

050

050

050

0Č

asde

cim

ace

4102

4634

3106

2869

2781

(b)

Kva

lita

sítě

00,

250,

50,

751

Zby

lých

vrch

olů

500

500

500

500

500

Čas

deci

mac

e27

3127

6328

3829

4930

78

(c)

Tab

ulka

B.1

:(a

)R

ychl

ost

algo

ritm

upr

orů

zné

úrov

něde

cim

ace;

Vliv

para

met

ruM

eshR

ough

ness

(b)

aM

eshQ

ualit

y(c

)na

čas

deci

mac

e

34

Přílohy

(a) 0

(b) -0,4

Obrázek B.3: Výsledky algoritmu pro různé úrovně parametru MeshRoughnesspro zabránění sebeprotínání. Číselný údaj udává nastavení tohoto parametru.

35

Přílohy

(a) (b)

Obrázek B.4: Výsledky deformace pomocí filtru vtkMEDPolyDataDeformationPKpro Stehenní kost (Femur). (a) Pomocí původní hrubé sítě (b) Pomocí méhodecimačního filtru

36

Přílohy

(a)

(b)

Obrázek B.5: Výsledky deformace pomocí filtru vtkMEDPolyDataDeformationPKpro Sval krejčovský (Sartorius). (a) Pomocí původní hrubé sítě (b) Pomocí méhodecimačního filtru

37