Gradi¨ ent domein mesh manipulatie.
Auteur: Czubin Mark
Promotor: Prof. dr. Bekaert Philippe Begeleider: Nulens Johan
2 augustus 2009 Universiteit Hasselt
Inhoudsopgave 1 Inleiding 1.1 Introductie . . . . . . . . . . . . . 1.2 Achtergrond . . . . . . . . . . . . . 1.3 Gradi¨ent domein mesh manipulatie 1.4 Verscheidenen toepassingen . . . . 1.5 Wiskundige notatie . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
1 1 1 2 3 3
2 Modellerings metaforen 2.1 Doelstellingen . . . . . . 2.2 Handles . . . . . . . . . 2.2.1 Muis controle . . 2.3 Constraints . . . . . . . 2.3.1 Shape en motion 2.4 Shape constraints . . . . 2.5 Motion constraints . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
5 5 6 7 7 8 8 8
3 Differenti¨ ele mesh representatie 3.1 Overzicht . . . . . . . . . . . . . 3.2 Toepassing op mesh manipulatie 3.2.1 Niet-lineair probleem . . . 3.3 De discrete Laplaciaan . . . . . . 3.4 Matrix representatie . . . . . . . 3.4.1 Uniform Laplace operator 3.5 Reconstructie . . . . . . . . . . . 3.5.1 Laplaciaanse constraint . 3.5.2 Positionele constraint . . 3.6 Bijkomstige problemen . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
10 10 10 11 11 13 14 15 15 16 16
4 Taxonomie van gradi¨ ent algoritmen 4.1 Classificatie . . . . . . . . . . . . . . 4.2 Lineaire methoden . . . . . . . . . . 4.3 Niet-lineaire methoden . . . . . . . . 4.4 Domein reducerend . . . . . . . . . . 4.5 Animatie of statisch . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
17 17 17 18 18 19
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
I
5 Niet-lineaire iteratieve methoden 5.1 Inleiding . . . . . . . . . . . . . . . . . 5.1.1 Niet-lineaire kleinste-kwadraten 5.2 Subspace raamwerk . . . . . . . . . . . 5.2.1 Generiek raamwerk . . . . . . . 5.2.2 Constraints . . . . . . . . . . . 5.2.3 Verdere optimalisatie . . . . . . 5.2.4 Analyse . . . . . . . . . . . . . 5.3 Subdivisie extensie . . . . . . . . . . . 5.3.1 subdivisie . . . . . . . . . . . . 5.3.2 Analyse . . . . . . . . . . . . . 5.4 Dual mesh representatie . . . . . . . . 5.4.1 Duaal representatie . . . . . . . 5.4.2 Analyse . . . . . . . . . . . . . 5.5 Vergelijking en uiteenzetting . . . . . . 5.5.1 nadelen . . . . . . . . . . . . . 5.5.2 Verdere toepassingen . . . . . .
. . . . . . . formulering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
20 20 20 21 21 22 25 26 26 26 26 26 26 26 26 26 26
6 Domein reductie methoden 27 6.1 Subspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.2 Hardware isolines Laplacian . . . . . . . . . . . . . . . . . . . . . 27 6.3 Vergelijking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 7 Post deformation werk
28
8 Kleinste-kwadraten methode 8.1 Lineair kleinste-kwadraten methode . . . 8.2 Niet-lineaire kleinste-kwadraten methode 8.3 Oplossingen van het probleem . . . . . . . 8.3.1 Gpu algo’s . . . . . . . . . . . . . 8.3.2 Pseudo-inverse matrix . . . . . . .
II
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
29 29 30 31 31 31
Hoofdstuk 1
Inleiding 1.1
Introductie
Mesh manipulatie (mesh deformation) is een techniek om interactief een mesh te manipuleren om een nieuwe model te genereren onder bepaalde voorwaarden (constraints). Een manipulatie kan gebeuren onder andere door bepaalde delen van de mesh te verplaatsen of roteren. Een voorbeeld van een randvoorwaarde is het behoud van rigiditeit oftewel de weerstand tegen buigzaamheid van een object. In deze eindwerk zal er vooral gericht worden op polygoon oppervlakken maar in algemeen wordt deformation op alles toegepast, van punten-wolken tot en met spline gebaseerde modellen. De toepassingen zijn eindeloos maar de voornaamsten zijn het animeren van meshes of statische manipulatie. Statische manipulatie is vooral het aanpassen van een mesh aan de hand van handles dat bepaalde onderdelen verplaatst of draait. Deze transformaties zullen onder bepaalde voorwaarden gedaan worden om een fysische realistische effect te bekomen. Het animeren van een mesh wordt gedaan door mesh doorheen een reeks statische manipulaties te animeren voldoen.
1.2
Achtergrond
De laatste tiental jaar werd er extensief onderzoek gepleegd naar algoritmen om de mesh te manipuleren. Er wordt kort de verschillende soorten beschreven. De studie naar mesh manipulatie algoritme begon al begin jaren 80. De eerste reeks waren de Free-form deformation(FFD) algoritmen. Hierbij werden modellen aangepast door knooppunten van een lattice of controle punten van een B-spline te verplaatsen. De grootste probleem met FFD was dat er geen rekening wordt gehouden met de fysische eigenschappen van een model. Behoudt van volume is later toegevoegd geworden. Veel commerci¨ele pakketen ondersteunen deze soort algoritmen omdat ze effici¨ent en simpel te gebruiken zijn. Skeleton gebaseerde methoden zijn momenteel de meest gebruikte soort. Ze zijn gemakkelijk te gebruiken en geven snel een plausibel resultaat weer. Ook deze zijn in bijna elke commerci¨ele software pakket ondersteunt. het nadeel is dat het soms moeilijk is om de skelet te defini¨eren met alle gewichten.
1
Een derde soort zijn de fysisch gebaseerde algoritmen. Hierbij wordt is zoveel mogelijk fysische eigenschappen nagebootst om een realistische manipulatie te krijgen. Hierbij zijn mass-spring en eindige elementen methoden zeer geliefd. Het grootte nadeel is dat ze traag zijn waardoor er niet interactief gemanipuleerd kan worden. Een belangrijke soort zijn de multiresolutie algoritmen. De grote voordeel van deze zijn dat de details van de modellen zoveel mogelijk worden behouden. Ze worden dus vooral gebruikt voor zeer grote en gedetailleerde modellen gebruikt zoals een ingescand model. Een model bij deze algoritme wordt opgebouwd uit een ruwe mesh dat in kleine stappen steeds wordt verbeterd. Van belang zijn de differenti¨ele methoden. Hieronder bevinden zich de gradi¨ent domein technieken. Er wordt namelijk intrinsieke eigenschappen van de mesh bepaald en behouden. De voornaamste voordeel is detail behoud tijdens manipulatie. Ten slotte zijn er algoritmen dat niet direct opgedeeld kunnen worden maar toch interessant om apart te vermelden. Een recent opkomend maakt gebruikt van radial basis functions(RBF) en kan sterk overweg met slecht gevormde meshes maar minder interessant voor gedetailleerde meshes. Een verassend nieuwkomer gebruikt lijnintegralen op ruimtelijk vectorveld [vFTS06, FTS07]. Het vernieuwende is dat er geen zelf-intersecties zijn en volume wordt behouden. Maar hun algoritme is meer bedoeld voor mesh creatie dan manipulatie.
1.3
Gradi¨ ent domein mesh manipulatie
Er werd voor gradi¨ent domein technieken gekozen omdat er recent veel onderzoek naar werd gepleegd maar belangrijker is dat het detail van een model wordt behouden. Omdat de laatste paar jaren de modellen steeds meer gedetailleerd werden is detail behoudenis cruciaal. ∆f = ∇ • w De term gradi¨ent domein komt vanuit het feit dat de manipulaties dat doorgevoerd worden, toegepast worden op de gradi¨ent vectorveld en niet op de mesh zelf. Dit wordt ge¨ıllustreerd in de bovenstaande formule en beschreven staat in de paper [XZ09]. Hierbij is f de onbekende scalaire functie of mesh, ∆ de Laplaciaan operator, ∇• de divergentie operator en w de guidance vectorveld of in deze context de gradi¨ent vectorveld. De scalaire functie f kan heropgebouwd worden met alleen de guidance vectorveld. Dus kunnen manipulaties uitgevoerd worden op de guidance vectorveld i.p.v. direct op de functie f . Gradi¨ent domein mesh manipulatie is een oppervlak (surface) manipulatie techniek. Dit betekent dat de verscheidene manipulaties strikt intrageren met de oppervlak. Dit is in tegenstelling tot ruimte(space) manipulatie dat de ruimte tussen in verscheidene controle punten manipuleert. De Laplaciaan speelt hierbij een centrale rol. Namelijk geeft de operatie een intrinsieke representatie van de lokale vorm van de oppervlakte weer. Deze representaties encoderen we als zogenaamde Laplaciaanse co¨ordinaten. Het behoud van details kunnen we dus representeren als het minimaliseren van het verschil in Laplaciaanse co¨ ordinaten over de verschillende manipulaties heen. Dit is een minimalisatie probleem en kan opgelost worden met behulp van de
2
kleinste-kwadraten methode. Het grote voordeel van deze representatie is dat de matrices in de stelsel namelijk sparse zijn. Het blijkt dat dit een niet-lineair probleem is. Namelijk zijn de Laplaciaanse co¨ ordinaten niet rigid(translatie en rotatie) of similarity(rigid + isotropisch schalering) invariant. Dit komt neer dat rotaties en uniforme schaleringen andere co¨ ordinaten opleveren. Voor mesh manipulatie willen we minstens dat rigid transformaties wordt toegelaten. Hierdoor staan we voor een keuze. Ofwel kan er getracht worden om het probleem te lineariseren, of om iteratief nietlineaire algoritmen toe te passen om te convergeren naar een oplossing. Het is interessant om op te merken dat lineaire algoritme vooral in het begin van de onderzoek domineerde, maar ze worden stilaan vervangen door niet-lineaire algoritmen. De reden hiervoor kan zijn dat de niet-lineaire algoritmen snel genoeg zijn, maar belangrijker dat ze veel simpeler zijn voor de gebruiker om te gebruiken. Het voordeel van een lineair probleem is dat het snel en effici¨ent kan worden opgelost met de lineaire kleinste-kwadraten methode. Maar zal in meeste gevallen een suboptimaal oplossing opleveren. Zelfs een pure translatie van controle punten zal artefacten opleveren. Ten tweede worden hierbij meestal ingewikkelde gebruikers interfaces gecre¨eerd. Hierbij is het doel om de probleem deels te laten oplossen door de gebruiker. Meestal moet de gebruiker dan zelf de rigid transformaties van de controle punten opgeven. Nier-lineaire algoritmen zullen een optimaal oplossing leveren. Verder kunnen er andere niet-lineaire constraints toegevoegd worden. En hoeft er geen complexe gebruikers interface opgericht te worden. Maar het is duidelijk dat dit veel trager is. Het grote probleem is om dit zo effici¨ent mogelijk te doen zonder al te veel afwegingen te maken. Sommige afwegingen kunnen lijden dat de algoritme niet meer convergeert. Een voorbeeld is het gebruik van Inexact Gauss-Newton iteraties met hardware acceleratie van de GPU.
1.4
Verscheidenen toepassingen
Mesh morphing, etc.
1.5
Wiskundige notatie
Er wordt in deze eindwerk een kennis van lineaire algebra aangenomen. De volgende conventie wordt gebruikt tenzij anders vermeld: • Hoofdletters voor matrices, bijv. Λ, C. • Kleine letters voor de rest, dit geld ook voor de elementen van een matrix of vector, bijv. λ, aij . λi . Standaard zal een vector gedefinieerd zijn als een kolomvector. Een rijvector zal worden weergegeven met T de transpositie operator. Verder defini¨eren we een mesh M bestaande uit een tupel (V, E). Hierbij stelt V = {v1 , . . . , vn } met vi ∈ R3 de vertices voor en E de edges. Voor elke vertex vi defini¨eren we ook de verzameling Ni dat alle directe buren van vi bevat. Oftewel alle vertices vj waarvan de edge eij bestaat.
3
Hoofdstuk 8 bevat nog een korte samenvatting van lineaire en niet-lineaire kleinste-kwadraten methoden dat veelvuldig zal gebruikt worden. Maar van belang is de sectie over ‘Inexact Gauss-Newton iteratie’ voor het oplossen van milde niet-lineaire problemen. Er wordt ook tevens veelvuldig de formule Ax = b gebruikt om aan te duiden dat het om een kleinste kwadraten formulering gaat.
4
Hoofdstuk 2
Modellerings metaforen De doelstelling van elke mesh manipulatie raamwerk is het overbrengen van de designer’s idee¨en naar een kwalitatief product. Hierbij hoort een simpel maar krachtig raamwerk te worden ontwikkeld. In deze hoofdstuk halen we de meest bekende metaforen aan.
2.1
Doelstellingen
Er zijn 3 grote doelstellingen dat bereikt moet worden in elke raamwerk. Ten eerst moet het simpel te gebruiken zijn voor de gebruiker. Ten tweede moet de controle over de manipulatie exact zijn. En ten slotte moet het raamwerk zowel realistisch als hoge kwaliteit manipulaties opleveren. Simpele operaties De eerste vereiste wordt meestal negeert maar is cruciaal. Veel raamwerken forceren de gebruiker ingewikkelde acties uit te voeren om hun gewenste resultaat te bekomen. Namelijk moet een manipulatie gemakkelijk bereikt kunnen worden met simpele operaties. Als grote voorbeeld is er de modellering techniek dat gebruik maakt van splines. Hierbij moet de gebruiker een model vormen door controle punten te verzetten of toe te voegen. Deze controle punten defini¨eren een gladde curve (C 1 of C 2 continu). Om een gewenste vorm met arbitraire topologie te bekomen wordt hierdoor een uitdagende taak. Aan de andere kant van de extrema zijn puur polygoon modellering technieken. De uitdaging hierbij is het bekomen van gladde en ronde vormen etc. Een veelgebruikte oplossing hiervoor zijn subdivision surfaces dat de twee extrema’s overspant. De gebruiker kan vrij simpel nieuwe modellen ontwikkelen. Maar ook hierbij kunnen er problemen ontstaan bij hoekpunten met een grote valence. In context van deze eindwerk gebruiken veel lineaire algoritmen een ingewikkelde gebruikers interface. De gebruiker moet namelijk zelf zorgen voor een correcte deformation. Zie sectie 2.2 voor de operaties in deze eindwerk. fi → fi hi → m(hi ) si → d(si )
5
Exacte controle Een manipulatie kan opgesplitst worden in drie grote groepen vertices. De handle regio’s specificeert de groep vertices h0 , . . . , hn dat direct gemanipuleerd worden door de gebruiker. Hierbij worden de handle regio’s aangepast door een arbitraire transformatie m(·). Veelal wordt een rigid transformatie gebruikt. Verder wordt een region of interest gespecificeerd. Dit duid aan op de regio van vertices s0 , . . . , sn dat be¨ınvloed mogen worden. De positie van deze vertices worden berekend door de deformation algoritme d(·). Alle andere vertices dat niet worden be¨ınvloed zal worden opgedeeld in een fixed regio. Zie de paper van Botsch et al. [BK05] voor meer informatie. Het doel van deze definitie is dat de drie bovenstaande afbeeldingen ten aller tijde voldaan worden. Namelijk mogen de vertices, dat niet be¨ınvloed zijn door de handles, niet verplaatst worden. Anderzijds mogen de handles niet verplaatst worden door de deformation algoritme. Aan beide van deze voorwaarden voldoen de gradi¨ent domein algoritmen niet. De handles kunnen namelijk verplaatst worden door het algoritme. Een afgrenzing van invloed opstellen is dan zeer moeilijk omdat de constraints op de grens niet meer voldaan zullen worden. Gelukkig komt dit alleen voor in extreme gevallen en kan er handmatig een parameter bepaald worden om toch deze beperking op te leggen. Zie sectie 3.5.2 voor meer info omtrent de positionele constraint. Realistisch en hoge kwaliteit deformation Om realistische manipulatie te verkrijgen moet het fysisch mogelijk lijken. Hiervoor kunnen de algoritmen vergeleken worden met de resultaten van fysische simulaties. In de paper [XZ09] wordt kort uitgelegd dat de gradi¨ent domein technieken een vereenvoudigde versie van de minimaliserende bending and stretching energie simulaties zijn. Verder moeten er afwegingen gemaakt worden voor de kwaliteit van de algoritmen. Namelijk is er een afweging tussen kwaliteit, realisme en performantie. De kwaliteit kan deels gereduceerd worden door de probleem te projecten naar een gereduceerd model. De voordeel van deze techniek is dat de realisme behouden wordt en veel grote modellen aangepakt kan worden. Verder kan hoge kwaliteit in alle omstandigheden bereikt worden maar zwaar ten koste van performantie.
2.2
Handles
Om een model te manipuleren moet de gebruiker kunnen specificeren hoe een bepaalde onderdeel aangepast wordt. Hierbij maken we onderscheid tussen twee veel gebruikte middelen. Namelijk het verplaatsen van controle punten (handles) of het aanpassen van een curve op de oppervlakte. Er kan alternatief ook gewerkt worden met een invloedsveld dat specificeert tot hoe ver een transformatie van een controle punt of curve invloed heeft op zijn naburige vertices. Het voordeel van deze twee technieken is dat bijna alle complexe operaties kunnen opgebouwd worden uit deze twee simpelere operaties. Controle punten Controle punten (point handles) zijn de gemakkelijkste manipulatie methoden. Ze geven namelijk weer naar welke positie een punt zal verplaatst worden. Er kan alternatief ook bepaald worden hoe de lokale frame geroteerd wordt. In context van deze eindwerk kunnen sommige lineaire algoritmen niet overweg met puur translaties van de controle punten. Deze
6
probleem komt vanuit het feit dat de Laplaciaanse co¨ordinaten een rotatie vereisen dat niet bepaald kan worden uit alleen puur translatie. Daardoor wordt er soms ingewikkelde gebruiker interfaces ontwikkeld om de rotatie zelf te bepalen. Niet-lineaire algoritmen hebben deze problemen niet. hi = C(ti ) h0i = C 0 (ti ) Controle curven Controle curven (handle curves) zijn een beetje meer complex maar leveren een krachtige operatie toe. Een curve wordt bepaald door 2 of meerdere curve controle punten. Hierbij maken we onderscheid tussen de controle punten dat onderdeel zijn van de oppervlak en de curve controle punten dat de vorm van de curve manipuleren. Bepaalde posities van de curve komen overeen met de controle punten van de mesh namelijk hi = C(ti ). Het toepassen van de curve is duidelijk. De gebruiker hoeft alleen de curve controle punten aan te passen en de overeenkomstige controle punten van de oppervlak worden aangepast. Dit allemaal wordt in de bovenstaande formule nog eenmaal opgesomd. Het grote probleem bij oppervlak gebaseerde algoritmen is dat de controle punten namelijk de vertices van de mesh moeten zijn. Een irreguliere mesh oppervlak zal dus grote problemen opleveren. Tenslotte is een eigenschap van de curves is dat ze ondermeer een bepaalde gladheid behouden namelijk C 1 of C 2 continu¨ıteit. Dit laat toe om gemakkelijk bepaalde onderdelen van de model te buigen etc. De WIRE techniek zoals beschreven in [ZHS+ 05, SF98] is een krachtige vorm hiervan.
2.2.1
Muis controle
We hebben keuze tussen de CPU en GPU. Deze keuze hangt af van het algoritme. Bij de cpu is de vertex tracking vrij simpel. We renderen de deformed mesh naar texture met elke vertex een co¨ordinaat. Hierna weten we welke pixel. Dit hoeft alleen gedaan worden voor een selectie van een vertex. We projecteren gewoon onze muis 2D naar 3D coordinaten vermenigvuldigd met de project matrix. De mesh zal zelf geen Object transform matrix toegepast worden, dus ook niet voor de muis. Dit is een aanpassing van de formulering in [RBM06]. Mogelijk verder uitbreiding is het hergebruiken van de texture voor rendering (gpu subdivision [SJP05]). Nakijken op artefacten.
2.3
Constraints
Constraints laten toe om bepaalde doelstellingen waaraan een mesh manipulatie moet voldoen te beschrijven. Deze doelstellingen maken in algemeen het werk van een designer gemakkelijker. Er kan ondermeer met gemak fysische realisme bereikt worden. Verder kan er ondermeer de eigenschappen van een mesh behouden worden. Het is verder van belang dat de constraints toepasbaar zijn in een manipulatie raamwerk. Dit houdt in dat er afwegingen gemaakt worden tussen een fysische accuraat model of interactieve manipulatie. In context van deze eindwerk zijn we vooral ge¨ınteresseerd in interactieve performantie. 7
Energie minimalisatie (enegry minimization) is een van de meest populaire methoden. Hierbij wordt energie beschreven als de verschil van een optimale toestand tot een huidige toestand. Het systeem probeert dan een equilibrium te bereiken door de verschillende constraint energie¨en te minimaliseren. De verschillende graden van vrijheiden zullen beperkt worden door de designer met behulp van de handles. Het voordeel van deze methode is dat er uitvoerig onderzoek naar werd gepleegd om een optimale oplossing te bereken oftewel een equilibrium te bereiken. Het belang hiervan is dat alle constraints in deze eindwerk zullen beschreven worden als energie functies. Lineair: min kAx − bk
2
x
2
Niet-lineair: min kf (x) − b(x)k x
2
Quasi-lineair: min kAx − b(x)k , x
onderschikt aan kJb k kAk De algemene constraint vorm staat aangegeven in de bovenstaande formule. Hierbij is f (x) de energie functie terwijl b(·) een optimale toestand is dat nietlineair afhankelijk kan zijn van de onbekende x. Het doel is dus het vinden van x zodat de term minimaal wordt en dus de constraints zoveel mogelijk wordt bereikt. Het lineair zijn bepaald ook tevens indien de constraints gemakkelijk kan worden ge¨ımplementeerd en effici¨ent kan worden opgelost. Hierdoor delen we de constraints op in twee groepen, lineaire en niet-lineaire constraints. Ten laatste wordt er een uitzondering gemaakt voor sommige niet-lineaire problemen dat quasi-lineair zijn. Intu¨ıtief betekent het dat het probleem gedraagt als een lineair probleem. Formeel betekent het dat de constraint geschreven kan worden in de vorm van Ax − b(x) met A een constante matrix. Verder moet de jacobiaan een magnitude kleiner zijn dan de constante matrix kJb k kAk. Zie sectie 5.2.1 voor de toepassing. Het is onmiddelijk duidelijk dat niet-lineaire constraints veel zwaardere methodes vereisen om opgelost te worden. Er kan bijvoorbeeld gebruik gemaakt worden van conjugate gradient methode. Oplossingen voor niet-lineaire problemen worden gegeven in de paper [She94] en een effici¨ent niet-lineaire kleinste kwadraten methode in sectie 8.2.
2.3.1
Shape en motion
We kunnen twee soorten onderscheiden: shape en motion.
2.4
Shape constraints
2.5
Motion constraints
Voornaamste constraints: [AOW+ 08] [XZY+ 07, SZT+ 07] • Positionele constraints ook wel bekend als Handle constraints
8
• Rigidity of ‘stijfheid’ • Behoud van volume. • Geen zelfintersecties. • Behoud van detail of van topologische continu¨ıteit. bijv.: C 1 Een duidelijk voorbeeld hiervan is de Laplaciaanse constraint • Skeleton constraint. • ...
9
Hoofdstuk 3
Differenti¨ ele mesh representatie 3.1
Overzicht
Detail behoudenis kan geformuleerd worden uit de lokale eigenschappen van een mesh oppervlak. Deze eigenschappen kunnen bepaald worden met behulp de Laplace differentiaaloperator of meer precies de Laplace-Beltrami differentiaaloperator. Het toepassen van de Laplaciaan op een mesh geeft weer een intrinsieke representatie en bevat de lokale relatie tussen een vertex en zijn buren. Hierbij beschrijft de relatie de lokale vorm van de oppervlak rond de vertex. We noemen de toepassing van de Laplaciaan op een vertex, de Laplaciaanse co¨ordinaat van de vertex. In de literatuur wordt het ook soms gerefereerd als de differenti¨ele co¨ ordinaat (differential coordinate). De detail van de mesh zal behouden worden na manipulatie indien de Laplaciaanse co¨ ordinaten tussen de nieuwe en de originele mesh minimaal verschillen. We defini¨eren hier minaal als de som van de gekwadrateerde verschillen. Er zal eerst kort worden beschreven hoe de Laplaciaan kan gebruikt worden in mesh manipulatie. In de sectie daarop volgend zullen de meest populaire versies van de discrete Laplaciaan uiteengezet worden. Hierna zullen de nodige operaties vertaald worden naar matrices operaties dat vereist zijn om de kleinstekwadraten probleemstelling op te lossen. Om ten slotte te eindigen met hoe een mesh kan gereconstrueerd worden vanuit enkel de Laplaciaan co¨ordinaten.
3.2
Toepassing op mesh manipulatie
Mesh manipulatie wordt meestal uitgedrukt in lokale rigid transformations. Dit houdt in dat de lokale vorm van een mesh wordt behouden na toepassing van een rigid transformatie. Formeel is een transformatie rigid indien de relatieve afstand tussen twee punten en onderliggende hoeken behouden wordt. Dit kan beschreven worden als een combinatie van een translatie en rotatie met uitzondering dat de rotatie geen reflectie kan veroorzaken. Indien we een rigid transformatie globaal toepassen op een lichaam dan ver-
10
anderd er niks aan de vorm. We kunnen een stap verder gaan en zeggen dat een lichaam rigid blijft indien er ook een globale isotropisch schalering transformatie plaats vindt (similarity transform). Dit wordt soms weggelaten voor lokale operaties omdat het volume veranderingen kan veroorzaken, doordat een onderdeel enkele malen groter of kleiner kan worden. Om een mesh te manipuleren zullen er enkele vertices gefixeerd worden op een bepaalde positie. Dit wordt gedaan door de gebruiker via handles. De overige vertices zullen dan zo bepaald worden dat de Laplaciaanse co¨ordinaten van de nieuwe mesh zo min mogelijk afwijken van de oude mesh. De voorwaarde hieraan is dat de Laplciaanse co¨ordinaten alleen mogen verschillen met een lokale rigid transformatie.
3.2.1
Niet-lineair probleem
Het grote probleem is dat de Laplaciaan operatie alleen translatie invariant is. In algemeen zal door de rigid transformaties andere resultaten bekomen worden. Het blijkt zelfs dat dit een niet-lineair probleem is. Namelijk om de rigid transformatie te vinden voor de Laplaciaanse co¨ordinaten zijn de vertices van de gemanipuleerde mesh vereist anderzijds om de vertices van de gemanipuleerde mesh te vinden zijn de Laplaciaanse co¨ordinaten vereist. Dit lijdt tot een kipen-eiprobleem. De oplossing hiervoor is het probleem te reduceren tot een lineaire probleem oftewel niet-lineaire iteratieve algoritmen te gebruiken. Niet-lineaire algoritmen zullen tot een globaal optimum convergeren. Namelijk zal de fout oftewel de verschil in vorm tussen de gemanipuleerde en originele mesh gedistribueerd worden over de ganse mesh. Hierbij zullen de details minaal verschillen. Lineaire algoritmen hierin tegen zullen meestal een suboptimaal resultaat leveren. Meer hierover in sectie.
3.3
De discrete Laplaciaan def
δi = L(vi ) =
X j∈
ωij (vi − vj )
(3.1)
Ni
1 |Ni | 1 cotangent: ωij = (cot αij + cot βij ) 4A tan(θij /2) + tan(θij+1 /2) mean-value: ωij = ||vi − vj || uniform: ωij =
(3.2) (3.3) (3.4)
De bovenstaande formule 3.1 is de discrete Laplaciaan gedefinieerd met ωij de gewichten tussen twee paar vertices en δi de Laplaciaanse co¨ordinaat. In de literatuur wordt soms vj − vi geschreven, dit leidt tot een teken verschil maar heeft verder geen invloed. De Laplaciaan zoals hier gedefinieerd is maar een discrete benadering en de keuze van de gewichten zijn daarom ook cruciaal. Namelijk heeft de Laplaciaan van een oppervlak rondom een vertex tangential en normal componenten. Dit wil zeggen dat er distorsies opduiken na manipulatie door de zogenaamde 11
tangential drift dat kan onstaan. Dit komt vooral voor wanneer de mesh zeer irregulier is wat in praktijk veelvuldig kan voorkomen. Er zijn nog meerdere gewichten dan de drie gegeven in de bovenstaande formule. We overlopen kort de meest belangrijke. De eerste soort gewichten zijn de uniforme gewichten zie formule 3.2. Deze neemt impliciet aan dat de edges tussen elke paar vertices even groot zijn. Ten tweede wordt er ook verwacht dat de hoeken tussen elke paar aanliggende edges even groot zijn. Dit is vrij onrealistisch en artefacten worden duidelijk wanneer er gewerkt wordt met een zeer irreguliere mesh. Het voordeel is dat deze operatie genormaliseerd is. Lu (vi ) = vi −
1 X vj |Ni |
(3.5)
j∈Ni
In de literatuur is de formule meestal vereenvoudigd zoals hierboven weergegeven. Om deze operatie op een intu¨ıtieve manier te illustreren wordt de Laplaciaan uitgevoerd op een afbeelding. Hiervoor passen we de Laplaciaan als een convolutie bewerking toe. De convolutie filter wordt geven in 3.6. De resultaten zijn te zien in figuur 3.1. Als toepassing werd de Laplaciaan toegevoegd aan het beeld om een verscherpte beeld te vormen. De belangrijkste details worden hierdoor versterkt. Verder bevat de Laplaciaan zowel positieve als negatieve waarden. De afbeelding links beneden toont alleen de positieve waarden terwijl bij de afbeelding rechts beneden de waarden gecentreerd zijn rond 0.5 met zwart en wit de negatieve respectievelijk de positieve waarden illustreren. −1 −1 −1 1 def −1 8 −1 image ⊗ h3×3 laplacian = image ⊗ 8 −1 −1 −1 0 0 0 1 1 1 1 = image ⊗ 0 1 0 − 1 0 1 (3.6) 8 0 0 0 1 1 1 De tweede soort gewichten zijn de cotangent gewichten zie formule 3.3. Hierbij zijn αij , βij de hoeken overstaanden aan de edge eij en A is de oppervlak van de omliggende driehoeken. Het is dus duidelijk dat deze vorm alleen voor driehoekige polygoon meshes kan gebruikt worden. Deze gewichten zijn afgeleid van de curvature normal dat bijna geen tangential componenten bevat. Het is dus duidelijk dat de cotangens gewichten beter overweg kunnen met een irregulier gesamplede mesh. Ten tweede kunnen deze gewichten niet overweg met grote hoeken doordat cotangens problemen heeft bij π of 180◦ . Al worden niet alle problemen opgelost toch wordt dit stilaan de meest populaire vorm. vi −
X
vj ∗ wi j = 0
(3.7)
X
(3.8)
j∈Ni
wi j = 1
j∈Ni
Ten slotte zijn de derde soort gewichten de mean-value coordinates. Hierbij worden thetaij en thetaij+1 gevormd door de hoeken tussen edges eij en 12
(a) Origineel
(b) Verscherpt
(c) Laplaciaan zonder schalering
(d) Laplaciaan
Figuur 3.1: Illustratie van de discrete Laplaciaan op Lenna. eij−1 en eij+1 . Een belangrijke eigenschap dat indien de gewichten nog eens genormaliseerd worden dat de uitkomst nul wordt. Dit is weergegeven in de formules hierboven. De toepassing van de gewichten vooral om een lokale volume behoudenis te verkrijgen.
3.4
Matrix representatie ∆ = {δ0 , . . . , δn } = {L(v0 ), . . . , L(vn )} ∆ = LV
Zoals reeds eerder besproken werd een Laplaciaanse co¨ordinaat gedefinieerd als de toepassing van de Laplaciaan op een vertex. Deze co¨ordinaten gaven we de 13
symbool δi . We kunnen een stap verder gaan en dit toepassen op de ganse mesh om alle co¨ ordinaten te berekenen. Dit wordt ge¨ıllustreerd in de bovenstaande formule. Hierbij representeert ∆ de matrix van alle co¨ordinaten aan. Indien we de mesh vertices representeren in matrix vorm kunnen we ∆ met matrix operaties berekenen. Dit vormt dan een simpel lineair stelsel. Hierbij zal in vervolg V de matrix van mesh vertices representeren. Er bestaat namelijk een matrix L genaamd de Laplace-matrix operator dat indien vermenigvuldigd wordt met de vertices van mesh de matrix ∆ oplevert. Indien de mesh connectiviteit niet veranderd is de matrix L constant. De Laplace-matrix hoeft dus meer maar ´e´enmaalig worden berekend en dit alleen tijdens inladen van een mesh. Om consistent te blijven met de literatuur zal de Laplace-matrix L gerefereerd worden als de Laplace operator. De elementen zullen gerefereerd worden als de Laplaciaan co¨ effici¨ enten (Laplacian coefficients).
L=
1 als −ωij als 0 als
i=j ∃ eij rest
De co¨effici¨enten kunnen gemakkelijk bepaald worden vanuit de gewichten. Dit wordt gedemonstreerd in de bovenstaande formule. Deze formule is afgeleid van de formule voor uniforme gewichten zoals aangeduid in [KG00]. In de volgende sectie wordt een voorbeeld uitgewerkt voor de uniforme gewichten.
3.4.1
Uniform Laplace operator Lu = I − D−1 A 1 als −1/di als Lu = 0 als
(3.9) i=j ∃ eij rest
(3.10)
In deze sectie zullen we een techniek beschrijven hoe de uniforme Laplace-matrix operator kan worden berekend. Ik wil erop duiden dat de eerste techniek via matrix vermenigvuldiging en invers operaties duidelijk ineffici¨ent is. Maar het wordt ter vervoledigheid vermeld. Er hoeven ook expliciet geen adjaceny en degree matrices aangemaakt te worden. De uniform Laplace operator kan berekend worden vanuit de adjaceny en degree matrix van mesh M. Dit is weergegeven in formule 3.9 waarbij A de ˆ de inverse degree matrix is. De degree matrix geeft adjaceny, D de degree en D weer de valence of aantal buren van een vertex, terwijl de adjaceny matrix de edges tussen elke paar vertices aangeeft. De formule kan sterk vereenvoudigd worden. Hiervoor maken we gebruik van het feit dat D een diagonaal matrix is, met alle elementen op de diagonaal −1 niet gelijk aan nul. De inverse is dus gewoon Dii = 1/di . Ten tweede zijn alle elementen van matrix A gelijk aan 1. Hierdoor versimpeld de matrix vermenigvuldiging nogmaals en kan de formule 3.9 vergeenvoudigd worden tot de formule 3.10. Deze versimpelde formule is beschreven in [KG00]. Er volgt nu een simpele uitgewerkt voorbeeld gegeven voor de graaf in figuur 3.2. Gegeven een graaf of mesh (V, E) dan zijn de twee matrices als volgt gedefinieerd: 14
6
5
4
aij =
1
2
3
Figuur 3.2: Een ongerichte graaf A
0 1 0 0 1 0
3.5
1 0 1 0 1 0
valence(vi ) als 0 als
1 0
dij =
0 1 0 1 0 0
0 0 1 0 1 1
1 1 0 1 0 0
0 0 0 1 0 0
& ,D ii
2 3 2 3 3 1
als als
i=j rest
i 6= 0j ∧ ∃ eij rest
Zoals eerder vermeld is hierbij de ‘valence’ van een vertex gedefinieerd als het aantal edges of aantal buren. Een voorbeeld van de graaf in figuur 3.2 wordt hiernaast getoond. 1 − 12 0 0 − 12 0 −1 1 − 31 0 − 31 0 3 1 1 0 − 1 − 0 0 2 2 ,L 1 1 1 0 0 − 1 − 3 3 3 1 − − 31 0 − 13 1 0 3 0 0 0 −1 0 1
Reconstructie 0 L ∆ V = ωC ωU | {z } Ax = b
Nu is de grote vraag hoe we van Laplaciaanse co¨ordinaten terug gaan naar de oorspronkelijke mesh. Zoals eerder opgemerkt in sectie 1.3 bij de uitleg of de term gradi¨ent domein, konden we de functie heropbouwen zonder extra informatie. Reconstructie van de mesh vanuit de Laplaciaanse co¨ordinaten kan gemakkelijk gedaan worden door een lineaire stelsel op te lossen met de kleinstekwadraten methode. Zie sectie 8 voor uitleg over het gebruik van de kleinstekwadraten methode. Ter verduidelijking zullen de twee volgende subsecties dieper ingaan op de twee constraints in de bovenstaande stelsel. Om dit stelsel op te lossen moet er minstens ´e´en vertex worden vastgelegd want het stelsel is onderbepaald. Dit is logisch gezien Laplaciaanse co¨ordinaten translatie invariant zijn en dus oneindig veel afbeeldingen hebben in de Euclidische ruimte. Dus als we de positionele constraint toevoegen met maar 1 vertex beperkt, kunnen we het stelsel oplossen met een unieke oplossing.
3.5.1
Laplaciaanse constraint LV = ∆0
De Laplaciaanse constraint in het stelsel zal voor alle vertices de ideale positie vinden op voorwaarde dat de nieuwe Laplaciaanse co¨ordinaten idem zal zijn aan de opgegeven reeks ∆0 . Dit wordt aangeduid in de bovenstaande formule. Opvallend is dat dit een lineair probleem is en komt door het feit dat er geen transformaties plaats vinden behalve een translatie. Belangrijker nog is dat de Laplaciaan operator matrix sparse is en dus heel effici¨ent kan worden opgelost.
15
Maar tijdens mesh manipulatie zal er maar dan 1 vertex verplaatst worden. Hierdoor wordt het probleem niet-lineair. Dit volgt uit het feit dat we willen toelaten dat er lokale rigid transformaties mogen plaatsvinden. Indien dit niet wordt toegelaten zal manipulatie vrijwel onmogelijk zijn. De constraint zal 2 herschreven worden als min(V )kLV − b(V, δ 0 )k . Hierbij zijn δ 0 de co¨ordinaten voorafgaand aan de manipulatie.
3.5.2
Positionele constraint ωCV = ωU
De positionele constraint laat toe om vertices van de mesh te fixeren op een bepaalde positie. Hierbij is C de positionele constraint matrix en U de toegewezen posities van de vertices zijn. De positionele constraint matrix kan beschouwd worden als een eenheidsmatrix waarbij enkel de rijen van de beperkte vertices gebruikt worden. Het toepassen van de constraint matrix zal elke beperkte vertex afgebeeld worden op zijn toegewezen positie in U . We introduceren ook de variabel ω, dat nodig is om te voorkomen dat het systeem de handles zelf verplaatst. De fout veroorzaakt door het verplaatsen van de handles kan soms zo groot worden dat het beter is om de handles te verplaatsen. Een aangeraden waarde is 1000. Het verplaatsen van de handles zal verder enkel U be¨ınvloeden. Terwijl het aanmaken van nieuwe handles zal C worden aangepast. Dit is ongunstig voor het aanmaken van de handles. Namelijk wordt de A matrix in de kleinste kwadraten probleem aangepast. Dit houdt in dat het ganse algoritme opnieuw moet worden uitgevoerd. Maar het verplaatsen van de handles zou hergebruik kunnen maken van reeds berekende elementen. Verder hoeven globale transformaties zelf niet uitgevoerd te worden a.d.h.v. de positionele constraint maar kunnen achteraf toegepast worden. Dit bespaart een groot deel onnodig rekenwerk. Het is verder makkelijk in te zien dat deze constraint lineair is en de positionele constraint matrix sparse is.
3.6
Bijkomstige problemen
Tangential drift. [ATLF06]
16
Hoofdstuk 4
Taxonomie van gradi¨ ent algoritmen 4.1
Classificatie
Er zijn drie grote criteria waarin onze algoritmen kunnen worden opgedeeld. Ten eerste wordt er een onderscheid gemaakt tussen statische mesh manipulatie en animatie. Verder kan alle algoritmen opgedeeld worden in lineair of nietlineair methoden. Ten slotte kan het probleem gereduceerd worden met behulp van een domein reducerende algoritme. De gebruiker zal uiteindelijk een keuze moeten maken. Een afweging tussen fysische realisme en interactieve manipulatie. Zoals beschreven in de survey van gradi¨ent algoritmen [XZ09], zal de gebruiker moeten kiezen tussen: performantie, kwaliteit en gebruiksvriendelijkheid 1 .
4.2
Lineaire methoden
Er zijn momenteel twee recente surveys over de verscheidene technieken zie [BS08a, XZ09]. Sorkine en Botsch beschrijven voornamelijk lineaire algoritmen terwijl Xu en Zhou beide classificaties en hun toepassingen beschrijven.
min v
i=0 X
kL(vi ) − Ti δi0 k
2
n
Het doel bij lineaire methoden is het vinden van de lokale transformaties Ti dat beschrijft hoe de Laplaciaanse co¨ordinaten transformeren. Hierbij moeten de transformaties ofwel een similarity of een rigidy transformatie zijn. Het vinden van deze transformaties is een niet-lineaire probleem maar kan toch gelineariseerd worden door benaderingen te maken. De bovenstaande formule beschrijft het probleem nogmaals. Hierbij is zowel de transformaties Ti als de vertices vi onbekend. Indien de transformaties bekend zijn dan is het probleem lineair en snel opgelost. 1 Gebruiksvriendelijkheid is in de zin van hoeveel de gebruiker zelf extra moet uitvoeren om een goed resultaat te bekomen
17
Tabel 4.1: Lineaire classificatie handle propagatie Geodesic propagation Harmonic propagation Material-aware propagation Explicit optimization
lineaire benadering Lineair approximation Estimation from an initial guess
De lineaire methoden kunnen ruwweg opgedeeld worden in twee categorie¨en. Ten eerste zijn er de methoden dat de transformaties bij de handles propageren naar alle andere onbekende vertices. De tweede groep probeert de lokale transformatie te benaderen door ofwel het vinden de lokale transformatie te lineariseren gebaseerd op de originele en onbekende vertices of door een initi¨ele gok. Zie bovenstaande classificatie van de verschillende methoden. De Geodesic en harmonic propagatie methoden vereisen dat de gebruiker de transformaties aangeeft. Ook bij material-aware moet de gebruiker de propagatie aanduiden en soms de rotatie aangeven van de handles. Dit kan een serieus moeilijke opgave zijn voor de gebruiker. Verder is bij bijna alle methoden is het meest voorkomend probleem translation-insensitivity. Deze probleem vloeit uit het feit dat er geen rotaties kunnen bepaald worden indien er alleen translaties van de handles plaatsvinden. Aan de andere kant kan de Lineair approximation methode niet overweg met grote rotaties. En en slotte maakt Estimation from an initial guess methode aannames over de eigenschappen van de mesh. In kort geven de lineaire methode meestal een suboptimaal oplossing. Maar de artefacten geproduceerd zijn soms niet merkbaar. Verder moet er een keuze worden gemaakt tussen gebruiksgemakkelijkheid en artefacten. Het is betwistbaar indien de methoden zonder gebruikers input meer artefacten produceren. Maar het grote voordeel is dat lineaire methoden performant en gemakkelijk te implementeren zijn.
4.3
Niet-lineaire methoden
wat ze in gemeen hebben.. niet echt onderscheiden kijk op formule: iteratie... dan b aanpassen... iteratie dan b aanpassen convergeren... eerst v dan l etc updaten huang general framework dual meer speciaal ten slotte squences problemen traag convergeren artefacten nog steeds, niet optimaal (tangential drift) vergelijk ze hier, voordelen en nadelen? nee verwijs naar volgende hoofdstuk
4.4
Domein reducerend
Domein reducerende technieken trachten een mesh te presenteren met minder vertices dan de originele mesh. De doelstelling is om dit effici¨ent en met zo weinig mogelijk vertices te doen. Verder moet de reconstructie zoveel mogelijk de originele mesh te benaderen. Het doel hiervan is om de gradi¨ent algoritmen 18
dan enkel uit te voeren op de gereduceerde model. Het grote nadeel is dat de kwaliteit van een manipulatie hierdoor wordt verlaagt. Het is dus gewenst dat dit door de gebruikers kan worden ingesteld. Een algemeen voorbeeld, dat niet gerelateerd is aan de gradi¨ent domein, wordt gegeven in [AOW+ 08]. Een mesh wordt zoveel mogelijk benaderd door controle punten. De reconstructie maakt gebruik van moving least squarers. Het grote nadeel hierbij is dat het model wordt gespecificeerd in ruimtelijk omgeving in plaats van op de oppervlak. Hierdoor kan een hand en romp ruimtelijk dicht bij elkaar liggen maar topologisch veraf. Een betere algoritme zijn de handle-aware isolines [AFTCO07]. De afstand hierbij wordt topologisch over de oppervlakte berekent. Verder is de tijdscomplexiteit niet afhankelijk van de grote van de mesh. Hierdoor schaalt het algoritme zeer sterk. Deze algoritme wordt verder besproken in hoofdstuk 5. We zullen later zien dat reductie soms tot artefacten kan leiden. Een voorbeeld is de subspace deformation algoritme van Huang et al. [HLW07]. Er wordt namelijk een convex omhullende gecre¨eerd voor de mesh. Het probleem vloeit uit het feit dat de convex omhullende een zelf intersectie kan hebben. Oplossing voor dit probleem wordt gegeven in de paper [XZY+ 07] en zorgt gewoon dat er paar extra iteraties achteraf met een andere algoritme worden toegepast.
4.5
Animatie of statisch
19
Hoofdstuk 5
Niet-lineaire iteratieve methoden 5.1
Inleiding
Niet-lineaire algoritmen leveren een optimaal resultaat onder bepaalde voorwaarden. Aan de hand van deze voorwaarden, de performantie en de toepasbaarheid in verschillende contexten, kunnen we de algoritmen onderscheiden. We zijn vooral ge¨ınstresseerd in algoritmen dat interactief een resultaat kan produceren op kleine- tot middelgrote meshes (5k tot 50k vertices). We hebben gekozen voor de drie belangrijkste en interessante methoden. • De subspace deformation framework, zie de paper van Huang et al. [HSL+ 06]. • De subdivision framework, zie de paper van Zhou et al. [ZHX+ 07]. • De dual laplacian mesh framework, zie de paper van At et al. [ATLF06]. De keuze van deze drie vloeit uit het feit dat dit alle methoden omvat dat gebruikt maakt van de Laplaciaanse co¨ordinaten. Andere algoritmen hergebruiken een deel of passen het toe in een andere context. Zelfs de subdivision raamwerk hergebruikt een groot deel van de raamwerk van de subspace raamwerk! Alle andere algoritmen kunnen dus beschouwd worden als uitbreidingen, zie [XZY+ 07, WXW+ 06, AFTCO07] voor enkele toepassingen.
5.1.1
Niet-lineaire kleinste-kwadraten formulering 2
min kAx − b(x)k x
Alle niet-lineaire algoritmen zullen het probleem behandelen als het oplossing van een kleinste-kwadraten probleem. Dit volgt meteen uit het feit dat de constraints beschreven zijn als het minimaliseren van de gekwadrateerde fout. Het voordeel van deze formulering is dat de matrices dat onze probleem beschrijven namelijk sparse zijn en dus effici¨ent kunnen worden opgelost. De bovenstaande formule illustreert het probleem nogmaals. Er wordt getracht een oplossing x te 20
Update van de vertices T
xi+1 = (A A)
−1
Update van de constraints
T
bi+1 = b(xi+1 )
A bi
Figuur 5.1: Iteratie stappen van de methoden vinden dat de fout minimaliseert, dit door iteratief naar een optimale oplossing te convergeren. Om dit probleem op te lossen kunnen we niet-lineaire kleinste kwadraten methoden toepassen. De basis werkwijze van elke niet-linear kleinste kwadraten methode is het probleem te lineariseren om dan een optimale oplossing te bereiken door iteratief x te verbeteren. Het nadeel is dat de meeste methoden traag convergeren of een initi¨ele oplossing vereisen. Nog erger is dat sommige methode niet convergeren naar een optimale oplossing! In algemeen kan een methode zoals de gaussnewton iteratie worden toegepast. Het probleem met deze methode is dat de jacobiaan in elke stap moet worden berekend. De bovenstaande figuur 5.1 geeft de procedure weer dat onze algoritmen opvolgen. Initieel stellen we gelijk x0 gelijk aan de vertices van de mesh en b0 wordt berekent uit de initi¨ele mesh. Dan wordt er alternatief de vertices en dan de constraints aangepast totdat de oplossing bereikt wordt. We hebben de eerste stap vereenvoudigd tot het oplossen van enkel een lineair kleinste-kwadraten probleem voor het vinden van de nieuwe vertices. Dit voor twee redenen. Ten eerste is dit een vereenvoudigd voorstelling dat het concept simpel illustreert. De meeste methoden vereisen immers dat de jacobiaan wordt berekent! Ten tweede laten al onze algoritmen dit deel weg, dit terwijl het algoritme nog steeds kan convergeren onder bepaalde omstandigheden. kort overzicht de verschillende van secties
5.2 5.2.1
Subspace raamwerk Generiek raamwerk
De subspace raamwerk is ontwikkeld om niet alleen de niet-lineaire laplaciaanse constraint op te lossen maar ook allerlei andere niet-lineaire constraints. Hierbij wordt er een onderscheid gemaakt tussen soft constraints en hard constraints. De onderscheid is dat hard constraints worden opgelost met Lagrangemultiplicators terwijl de soft constraints als een term mee wordt opgenomen in de deformation energie. Niet-lineaire constraints worden alleen gebruikt als soft constraint indien ze quasi-lineair zijn. Zoals eerder is een constraint quasilineair indien het geschreven kan worden als Ax − b(x) met A een constante matrix. Verder moet de jacobiaan een magnitude kleiner zijn dan de matrix A oftewel kJb k kAk.
21
s(x) ≡ Ax − b(x) min kAx − b(x)k
2
x
ondergeschikt aan h(x) = 0 We gebruiken symbool s en h om respectievelijk de soft en hard constraints aan te duiden. Dan wordt het probleem geformuleerd als het vinden van een waarde voor x dat de bovenstaande energie functie minimaliseert. Om dit op te lossen wordt gebruik gemaakt van de Gauss-Newton iteratie methode. Het nadeel van deze methode is dat dit vrij zwaar is. Maar gelukkig kunnen we in geval van de soft constraints hun jacobiaan gelijk stellen aan Jb = 0. Dit wordt verwezen als de Inexact Gauss-Newton methode. Gauss-Newton: xi+1 = xi + ∆xi ∆xi = −(JsT Js )−1 (JsT s(xi ) + JhT λxi ) λxi = −(Jh (JsT Js )−1 JhT )−1 (h(xi ) − Jh (JsT Js )−1 JsT s(xi )) Js = A − Jb (x) Js = Js (x) Inexact Gauss-Newton: kJb k kAk ⇒ Js ≈ A ∆xi = −(AT A)−1 (AT s(xi ) + JhT λxi ) λxi = −(Jh (AT A)−1 JhT )−1 (h(xi ) − Jh (AT A)−1 AT s(xi )) De formule wordt hierboven formeel weergegeven. Iteratief zal xi+1 worden verbeterd totdat er een optimaal oplossing wordt bereikt. Doordat A een constante is kan er een heel hoop berekeningen hergebruikt worden. Verder is er een kleine constante α. Dit verbeterd de convergentie en kan gevonden worden via een line search algoritme. We kunnen nu deze raamwerk gebruiken om allerlei constraints toe te passen. Het is duidelijk dat hard constraints zeer duur zijn en dus moet er moet zorgvuldig omgegaan worden met welke constraints er worden inbegrepen. In algemeen zullen we de hard constraints weglaten waardoor de formule drastische versimpeld. Namelijk is dit exact wat wordt toegepast in de raamwerk voor subdivisie oppervlakten van Zhou.
5.2.2
Constraints
We introduceren twee krachtige constraints. De niet-lineaire laplaciaan dat invariant is voor rotatie en uniforme schalering. Hiervoor zorgen we dat het gebruikt kan worden als een quasi-lineaire constraint. Ten tweede de skeleton constraint dat tevens ook quasi-lineair is. Dit laat ons toe om te zorgen dat bepaalde delen niet plooien en kan beschouwd worden als beenderen van een skelet. De toepassing is duidelijk het realistisch animeren van dieren.
22
Verder werd er door Huang et al. nog twee andere hard constraints beschreven. Namelijk de globale volume constraint en de projectie constraint. De projectie constraint maakt het werk van een designer gemakkelijker zodat manipulatie in een 2D vlak kan worden toegepast. Volume behoudenis is meer interessant maar gelukkig kunnen we dit benaderen door gebruik te maken van lokale volume constraint. Lokale volume behoudenis werd beschreven in [ZHS+ 05] en later opnieuw toegepast voor 2D beelden in [WXW+ 06]. Het nadeel is dat er een volumetrische graaf(volumetric graph) moet worden opgebouwd. We zullen zoals eerder vermeld de hard constraints niet gebruiken maar kunnen achteraf simpel worden toegevoegd. Rotatie invariant Laplaciaanse co¨ ordinaten 2
min kLV − b(V, δ 0 )k V
Het grootte probleem met Laplaciaanse co¨ordinaten is dat ze be¨ınvloed worden door rotatie en uniforme schalering. Huang et al definiert een niet-lineaire formulering dat enkel invariant is tegen rotaties. Hierdoor verliezen we de uniforme schalering component maar dit is niet zo erg. Meer specifiek proberen we de bovenstaande probleem op te lossen. Hierbij is L de Laplaciaan operator, V de vertices en δ 0 de oorspronkelijke Laplaciaanse co¨ordinaten. De niet-lineaire functie b(·) zal rotatie invariant Laplaciaanse co¨ordinaten terug geven dat geroteerd zijn naar de lokale co¨ ordinatenstelsel van de vertices. Rotatie invariante co¨ ordinaten zullen gedefinieerd worden in het normaal vectorveld van een polygoon mesh bestaande uit driehoeken. Meer precies weten we dat de Laplaciaanse co¨ ordinaat een benadering is van de curvature normal oftewel de normaal van de kromming van een oppervlak. Ten tweede is de Laplaciaanse co¨ ordinaat van en vertex gelegen in het normaal veld van de omringende driehoeken. Vertrekkend van deze eigenschappen defini¨eren we de rotatie invariant Laplaciaan: δi0 =
X
uij ((vj−1 − vi ) × (vj − vi ))
j∈Ni
=
X
uij N (vi , vj , vj−1 )
j∈Ni
matrix vorm: = N T i Ui X i = uij N (˜ vi , v˜j , v˜j−1 ) j∈Ni
Waarbij (vj−1 − vi ) × (vj − vi ) = N , de normaal van een driehoek is. Het doel is dus een reeks uij te vinden voor elke normaal zodat de som gelijk is aan de Laplaciaan. Deze uij zijn rotatie invariant en worden dus eenmalig berekent voor de oorspronkelijke mesh. We kunnen deze uij berekenen door een lineaire stelsel te lossen door bijvoorbeeld het gebruik van SVD. i δˆi = λi ki k 23
De vorige definitie is niet genoeg, de magnitude moet namelijk ook beperkt worden. De bovenstaande formule schaalt de magnitude van de co¨ordinaat naar de lengte van de oorspronkelijke co¨ordinaat. Hierbij is λi = kdelta0i k van de oorspronkelijke mesh. Nu is onze δˆi Laplaciaan translatie en rotatie invariant. Skeleton constraint De skeleton constraint laat de designer toe om virtuele onbuigbare beenderen toe te voegen aan de mesh. We voegen namelijk een constraint toe dat zorgt dat een segment ab onbuigbaar is en niet veranderd van lengte. Daarna binden we vertices van de mesh aan de segment zodat de vertices ook niet buigen. Hierdoor kan de designer met gemak onbuigbaar oppervlakten aanduiden dat het fysische realisme bij modellen verhoogt. Op een onbuigbaar segment ab zullen er n controle punten {s0 , . . . , sn } uniform verdeeld worden. De tussenruimte wordt gekozen zodat het gelijk staat aan de gemiddelde edge lengte van de vertices dat verbonden zijn. Hierbij is s0 = a en sn = b met de tussenruimte gelijk aan (sn −s0 )/n. We willen namelijk de onderstaande condities forceren. ksn − s0 k = ρ (si − si−1 ) − (sn − s0 )/n = 0 met i ∈ 1, . . . n De eerste conditie zorgt ervoor dat de lengte van de been niet veranderd waarbij ρ de originele lengte is. De tweede constraint zorgt ervoor dat elke onderdeel ongebogen is oftewel in dezelfde richting als de been zelf staat. P Aan elk controle punt hangen we enkele vertices vast, si = j kij vj . De co¨effici¨enten k zijn de mean value coordinaten. Nu zijn we klaar om de constraint in matrix vorm te schrijven. kΘV k = ρ ΓV = 0 De matrix Γ is een constante matrix met elementen Γij = (kij − ki−1,j ) − (knj − k0j )/n en vector Θ heeft elementen Θj = knj −k0j . Deze vereenvoudigde notatie is nog niet perfect omdat de magnitude wordt gebruikt. Er wordt dan geopperd om de volgende methode te gebruiken:
ΘV = ρ
ΘV kΘV k
Hierdoor wordt de constraint quasi-lineair maar zal niet zorgen voor convergentie problemen.
24
Samenvoegen van de constraints ∆ L ωC V = ωU 0 Γ ΘV ρ kΘV Θ k | {z } Ax = b(x)
(5.1)
We kunnen alle 3 constraints samenvoegen om ze tegengelijk op te lossen met de niet-lineaire kleinste-kwadraten methode. Namelijk voegen we de positionele, skeleton en Laplaciaanse constraint samen in matrix vorm en behandelen we het als een enkele probleem. Het voordeel van deze formulering is dat de matrix A sparse en constant is tijdens de berekening. Hierdoor hoeft AT A etc. maar eenmaal berekent te worden. Het nadeel is dat indien we veranderingen teweegbrengen in het aantal handles of skeletons dat A herberekent moet worden. Direct toepassen van de Inexact Gauss-Newton iteratie is niet mogelijk want het kan zijn dat het algoritme soms niet convergeert naar een oplossing door een te hoge condition nummer k(JsT Js ). De condition nummer in ons geval is sterk gerelateerd aan de mesh grootte. Er moet ofwel een extra stabiele stap ge¨ıntroduceerd worden of gebruik maken van de subspace. De subspace algoritme vertrekt vanuit een convex omhullende mesh dat een kleinere ‘condition number’ opleverd waardoor de numerieke stabiliteit hoger wordt. We komen hierop verder terug in de volgende hoofdstuk. Opmerkingen Er zijn drie grootte nadelen van de vorige definitie van de Laplaciaan. Ten eerste merken we op dat δˆi niet-lineair is en dus een niet-lineaire kleinste-kwadraten methode vereist. Hierdoor moet iteratief lineaire stelsel opgelost worden tot convergentie bereikt is. Gelukkig is de Laplaciaan constraint quasi lineair waardoor we de Inexact Gauss-Newton iteratie kunnen gebruiken. Ten tweede indien we een verandering willen behouden zal de ui j opnieuw berekend moeten worden voor de deformed mesh. Dit kan een zware berekening worden en maakt het algoritme minder interessant voor puur modelleringtoepassingen. Ten laatste kan het niet toegepast worden op een non-manifold mesh. Er moet minstens 3 normalen gebruikt worden. Een border-vertex kan gemakkelijk hieraan niet meer voldoen.
5.2.3
Verdere optimalisatie
sequences paper
25
5.2.4
5.3 5.3.1
Analyse
Subdivisie extensie subdivisie
Waarom? veel details toevoegen, kan progressief zijn (lod), niet veel ruimte overhead, en ten slotte kan leuk zijn voor DX11 samen met tesselation en displacement Voor ons? modeling wil je C1 en C2 smoothness modelen, later kan er naar game exported Watis het? vertex displacement normaal berekenen? via basis functies en op de gpu drie papers : real-time en subdivision modeling en een andere met inexact calculated normals voordeel: je krijgt normalen, je moet niet approximaten. real-time versie misschien beste sinds normals simpeler berekent kunnen worden vanuit de texture en niet opnieuw met basis functies soorten? loop catmul-clark etc hoe wij? interessant voor matrix vorm voor laplacian subdisivion surf
5.3.2
5.4
Analyse
Dual mesh representatie
eerste methode duale representatie
5.4.1
Duaal representatie
5.4.2
Analyse
5.5 5.5.1
Vergelijking en uiteenzetting nadelen
traag, herberekening u en coefficienten van laplaciaan, wat gebeurt er als je handles los laat? oplossingen in mesh animatie ... kan wel de mesh slechter maken over tijd intersecties? zie graph. uittrekkingen zie au paper
5.5.2
Verdere toepassingen
Lokale volume behouding, niet ge¨ınsprecteerd. Mogelijke oplossing via gpu behalve hard
26
Hoofdstuk 6
Domein reductie methoden 6.1
Subspace
space
6.2
Hardware isolines Laplacian
geodesic
6.3
Vergelijking
27
Hoofdstuk 7
Post deformation werk Na het bereken van de deformation kunnen verdere algoritmen gebruikt worden. Tesselation, shading, mouse selection etc. Adaptive subdivision en adaptive tesselation gebruiken om de render tijd te verhogen en artefacten te vermijden. Dit kan toegepast worden op bijna alle algoritmen. error eval, dual laplacian
28
Hoofdstuk 8
Kleinste-kwadraten methode De kleinste-kwadraten methode is een methode om de parameters van een geven aantal formules i = 0..m, fi (x0 , . . . , xn ) te bereken zodat de ideale uitkomst B = b0 , . . . , bm zo weinig mogelijk afwijkt waarbij m > n. We defini¨eren de residu fout als de afwijking van een oplossing met de ideale oplossing. Deze oplossing moet hete minimum zijn van de som van de kwadratische residu fouten. In matrix vorm levert dit de volgende formule op: Ax = b r(x) = Ax − b Hierbij is A de matrix van de formules fi , de onbekende parameters x, de ideale uitkomst B en de residu fout r(x).
8.1
Lineair kleinste-kwadraten methode min x
i=0 X
2
2
ri (x) = min kr(x)k = min kAx − bk x
n
2
x
Er wordt vereist voor een lineaire kleinste-kwadraten methode dat de ideale uitkomsten B een constante is en niet afhangt van de argumenten. Dit wil zeggen Ax = B een stelsel van lineaire vergelijkingen moet zijn. We kunnen dan een unieke oplossing bekomen als A lineair onafhankelijk is. Een mogelijk oplossing is om met de normaal vergelijkingen te werken. Hiervoor gebruiken we de eigenschap dat een matrix vermenigvuldigd met zijn transpose inverteerbaar is. Ax = b T
A Ax = AT b x = (AT A)−1 AT b
29
De oplossing hiervan is ook meteen de oplossing met de kleinste residu fout. Dit volgt uit het feit dat r geminimaliseerd wordt als de gradi¨ent nul is. Een volledige afleiding met uitleg is te vinden in Jammer genoeg komen de deformation constraint vaak voor als niet-lineaire problemen. Niet-lineair solvers zijn van natuur trager. Daarom worden sommige problemen toch opgelost als een lineaire probleem met een trucje om de nietlineaire onderdeel later te corrigeren. Maar zoals te verwachten levert dit heel veel gevallen op waarbij de oplossing ver van perfect is. Er zal dus een keuze gemaakt moeten worden tussen lineair of niet-lineair.
8.2
Niet-lineaire kleinste-kwadraten methode
Bij de niet-lineaire kleinste-kwadraten probleem is de idealen uitkomst B niet langer een constante maar afhankelijk van de argumenten. Ax = B(x) min kr(x)k
2
x
Voor het berekenen van de een optimale oplossing wordt er gebruik gemaakt van de inexact Gauss-Newton iteratie zoals beschreven in In deze eindwerk wordt een volledige afleiding gegeven vertrekkend van de normaal vergelijkingen voor de Inexact Gauss-Newton iteratie methode. Gauss-Newton: xi+1 = xi + ∆xi (JrT Jr )∆xi
= −JrT r(xi )
Jr = A − Jb Jb = Jb (x)
(8.1)
Inexact Gauss-Newton: kJb k kAk ⇒ Jr ≈ A (AT A)∆xi = −AT r(xi ) ∆xi = −(AT A)−1 AT r(xi ) ∆xi = −(AT A)−1 AT (Axi − b(xi )) ∆xi = −(AT A)−1 AT Axi + (AT A)−1 AT b(xi ) ∆xi = −(AT A)−1 (AT A)xi + (AT A)−1 AT b(xi ) ∆xi = −Ixi + (AT A)−1 AT b(xi ) ∆xi = −xi + (AT A)−1 AT b(xi ) xi+1 = xi − xi + (AT A)−1 AT b(xi ) xi+1 = (AT A)−1 AT b(xi )
(8.2)
We vertrekken van de Gauss-Newton methode gegeven in 8.1. Hierbij is xi de waarden van x bij iteratie i. We itereren xi+1 = xi + ∆xi beginnend met x0 als initi¨ele gok tot het systeem convergeert en niet meer veranderd. Voor x0 30
kan bijvoorbeeld de oorspronkelijke mesh gebruikt worden. Verder moet ∆xi voldoen aan de normaal vergelijkingen. Hierbij is J de Jacobiaan matrix. Bij elke iteratie stap moeten we de jacobiaan Jb berekenen. Dit is op zich een zware berekening. We kunnen Jb weglaten indien de iteratie stap zeer klein is of de magnitude kJb k veel kleiner is dan kAk. In praktijk zal de iteratie stap in begin groot zijn om snel te kunnen convergeren. We vervangen Jr met A en vereenvoudigen de formule tot formule 8.2. Let op dat A een m × n matrix is, b m groot is en x n groot is. De voorwaarde zodat dit opgelost kan worden is dat m > n! Ten tweede gebruiken we geen ‘line search’ algoritme omdat we deze methode op een parallelle architectuur willen gebruiken.
8.3 8.3.1
Oplossingen van het probleem Gpu algo’s
Probleem parallel? sparse matrix multiplications, SVD cuda, cublas lib.
8.3.2
Pseudo-inverse matrix
De pseudo-inverse heeft veel toepassingen maar in deze eindwerk gebruiken wij het om lineaire stelsels op te lossen. Een van de manieren waarop dit gedaan kan worden is via Singular value decomposition(SVD). Gegeven een matrix M dan is de SVD: M = U ΣV ∗ T
U M = IΣV
(8.3)
T
+
Σ UT M = V T V Σ+ U T M = I V Σ+ U ∗ = M +
(8.4)
Hierbij is een geconjugeerde getransponeerde matrix van V geschreven als V ∗ . Voor onze toepassingen is het voldoende om de re¨eel getransponeerde matrix te nemen want we gebruiken geen complexe getallen. De volledige afleiding om de pseudo-inverse van matrix M te krijgen, geschreven als M + , wordt gegeven in formule 8.4. Het was niet nodig om een volledige afleiding te geven maar toont enkele eigenschappen aan van SVD. De pseudo-inverse van Σ kan berekend worden door elke niet lege element door zijn omgekeerde. Dit kan omdat Σ een diagonaal matrix is. Verder zijn U en V unitaire matrices met de eigenschap U T U = U U T = I. Indien er effectief een inverse bestaat van matrix M dan is M −1 ≡ M + . Er wordt in deze eindwerk gebruik gemaakt van ATLAS en LAPACK bibliotheken om SVD te berekenen.
31
Bibliografie [AFTCO07] OKC Au, H Fu, CL Tai, and D Cohen-Or. Handle-aware isolines for scalable shape editing. International Conference on Computer Graphics and Interactive Techniques, 2007. [AOW+ 08] B Adams, M Ovsjanikov, M Wand, HP Seidel, and L Guibas. Meshless modeling of deformable shapes and their motion. ACM SIGGRAPH Symposium on Computer Animation, 2008. [ATLF06] OKC Au, CL Tai, L Liu, and H Fu. Dual laplacian editing for meshes. IEEE Transactions on Visualization and Computer Graphics, pages 386–395, 2006. [BFGS03] J Bolz, I Farmer, E Grinspun, and P Schr¨ooder. Sparse matrix solvers on the gpu: Conjugate gradients and multigrid. International Conference on Computer Graphics and Interactive Techniques, pages 917–924, 2003. [BK05] M Botsch and L Kobbelt. Real-time shape editing using radial basis functions. Computer graphics forum, 24(3):611–621, 2005. [BS08a] M Botsch and O Sorkine. On linear variational surface deformation methods. IEEE Transactions on Visualization and Computer Graphics, 14(1):213–230, 2008. [BS08b] T Boubekeur and C Schlick. A flexible kernel for adaptive mesh refinement on gpu. Computer Graphics Forum, 27(1):102–114, 2008. [DMSB99] M Desbrun, M Meyer, P Schroder, and AH Barr. Implicit fairing of irregular meshes using diffusion and curvature flow. 1999. [FTS07] W Von Funck, H Theisel, and HP Seidel. Explicit control of vector field based shape deformations. Proc. Pacific Graphics, pages 291– 300, 2007. [HLW07] X Huang, S Li, and G Wang. A gpu based interactive modeling approach to designing fine level features. Proceedings of Graphics Interface 2007, pages 305–311, 2007. [HSL+ 06] J Huang, X Shi, X Liu, K Zhou, LY Wei, SH Teng, H Bao, B Guo, and HY Shum. Subspace gradient domain mesh deformation. Proceedings of ACM SIGGRAPH 2006, 25(3):1126–1134, 2006.
32
[KG00] Z Karni and C Gotsman. Spectral compression of mesh geometry. Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 279–286, 2000. [KW05] J Kr¨ uger and R Westermann. Linear algebra operators for gpu implementation of numerical algorithms. International Conference on Computer Graphics and Interactive Techniques, 2005. [LSA+ 05] Y Lipman, O Sorkine, M Alexa, D Cohen-Or, D Levin, C Rossl, and HP Seidel. Laplacian framework for interactive mesh editing. International Journal of Shape Modeling, 11(1):43–61, 2005. [RBM06] T Ritschel, M Botsch, and S M¨ uller. Multiresolution gpu mesh painting. 2006. [SCOL+ 04] O Sorkine, D Cohen-Or, Y Lipman, M Alexa, C R¨ossl, and HP Seidel. Laplacian surface editing. Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 175–184, 2004. [SF98] K Singh and E Fiume. Wires: a geometric deformation technique. Proceedings of the 25th annual conference on Computer graphics and interactive techniques, pages 405–414, 1998. [She94] JR Shewchuk. An introduction to the conjugate gradient method without the agonizing pain. unpublished paper, 1994. [SJP05] LJ Shiue, I Jones, and J Peters. A realtime gpu subdivision kernel. Proceedings of ACM SIGGRAPH 2005, 24(3):1010–1015, 2005. [Sor06] O Sorkine. Differential representations for mesh processing. Computer Graphics Forum, 25(4):789–808, 2006. [SZT+ 07] X Shi, K Zhou, Y Tong, M Desbrun, H Bao, and B Guo. Mesh puppetry: cascading optimization of mesh deformation with inverse kinematics. International Conference on Computer Graphics and Interactive Techniques, 2007. [vFTS06] W von Funck, H Theisel, and HP Seidel. Vector field based shape deformations. International Conference on Computer Graphics and Interactive Techniques, pages 1118–1125, 2006. [WXW+ 06] Y Weng, W Xu, Y Wu, K Zhou, and B Guo. 2d shape deformation using nonlinear least squares optimization. The Visual Computer, 22(9):653–660, 2006. [XZ09] WW Xu and K Zhou. Gradient domain mesh deformation—a survey. Journal of Computer Science and Technology, 24(1):6–18, 2009. [XZY+ 07] W Xu, K Zhou, Y Yu, Q Tan, Q Peng, and B Guo. Gradient domain editing of deforming mesh sequences. International Conference on Computer Graphics and Interactive Techniques, 2007.
33
[ZHS+ 05] K Zhou, J Huang, J Snyder, X Liu, H Bao, B Guo, and HY Shum. Large mesh deformation using the volumetric graph laplacian. ACM transactions on graphics, Jan 2005. [ZHX+ 07] K Zhou, X Huang, W Xu, B Guo, and HY Shum. Direct manipulation of subdivision surfaces on gpus. International Conference on Computer Graphics and Interactive Techniques, 2007.
34
