Non-photorealistic rendering and keyframe animation of gaseous phenomena

Non-photorealistic rendering and keyframe animation of gaseous phenomena Thesis voorgedragen tot het behalen van de graad van licentiaat in de Informatica, afstudeervariant Informatica-Multimedia Kris Peeters Promotor: Prof. dr. Frank Van Reeth Begeleider: dr. Fabian Di Fiore Academiejaar 2004-2005

Samenvatting Deze thesis behandelt gasachtige fenomenen als vuur, water en rook. Meer in het bijzonder wordt enerzijds een studie gedaan naar bestaande technieken om gasachtige fenomen op een non-photorealistische manier weer te geven. Non-photorealistic renderen is het domein in de computer graphics waarin gestreefd wordt een ander effect dan fotorealisme te genereren. Zowel technieken uit de artistieke wereld, zoals het nabootsen van handgetekende beelden, als technieken uit de wetenschap, zoals het gebruik van physics-based animatie, worden hierbij besproken. Anderzijds worden methodes besproken om gasachtige fenomenen te controleren met behulp van keyframes. Dit wil zeggen dat we de simulatie be¨ınvloeden door voorwaardes op te leggen waaraan het op bepaalde tijdstippen moet voldoen.

i

Voorwoord Deze thesis wordt voorgedragen tot het behalen van de graad van licentiaat in de informatica, afstudeervariant Informatica-Multimedia. Deze thesis is het resultaat van vele uren lezen, vele uren schrijven, vele uren programmeren en vele uren debuggen. Daarbij heb ik van verschillende mensen hulp gekregen, die ik daarvoor zou willen bedanken. Allereerst wil ik mijn promotor, prof. dr. Frank Van Reeth, en mijn begeleider, dr. Fabian Di Fiore, bedanken om mij op het juiste spoor te zetten en aanmerkingen te geven over voorlopige versies van zowel de tekst als de implementatie. Verder wil ik Tom van Laerhoven en Lode Vanacken bedanken om mij te helpen met het zoeken naar fouten in de implementatie. Ook wil ik Bert De Decker bedanken, om mij inzicht te verschaffen in de Navier Stokes vergelijkingen. Ten slotte zou ik mijn ouders willen bedanken om mij de mogelijkheid te bieden deze opleiding te volgen.

ii

Inhoudsopgave Samenvatting

i

Voorwoord

ii

Inhoudsopgave 1 Inleiding 1.1 Overzicht . . . . . . . . 1.2 Non-Photorealism versus 1.3 Computer Animatie . . 1.3.1 Geschiedenis . . 1.3.2 Keyframing . . .

iii

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1 1 1 4 4 4

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

6 6 7 8 9 9 10 11 11 12

3 Non-photorealistic rendering van vuur 3.1 Procedurele methode . . . . . . . . . . 3.1.1 Positieskelet . . . . . . . . . . . 3.1.2 Vormskelet . . . . . . . . . . . 3.1.3 Connecties . . . . . . . . . . . 3.1.4 Topvlammen . . . . . . . . . . 3.1.5 Analyse van de parameters . . 3.1.6 Inkleuren . . . . . . . . . . . . 3.1.7 Wind . . . . . . . . . . . . . . 3.2 Physics based methode . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

13 13 15 15 16 16 17 17 17 17

. . . . . . . . Photorealism . . . . . . . . . . . . . . . . . . . . . . . .

2 Gaseous phenomena 2.1 Particle Systems . . . . . . . . . 2.2 Cellulaire automaten . . . . . . . 2.3 Navier-Stokes vergelijkingen . . . 2.3.1 Voeg externe krachten toe 2.3.2 Advectie . . . . . . . . . . 2.3.3 Diffusie . . . . . . . . . . 2.3.4 Projectie . . . . . . . . . 2.3.5 Het dichtheidsveld . . . . 2.3.6 Vuur . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

iii

INHOUDSOPGAVE

iv

3.2.1 Structurele vorm van een vlam . . . . . . . . . . . . . . 3.2.2 Vlam evolutie . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Splitsen van een vlam . . . . . . . . . . . . . . . . . . . 3.2.4 Profiel van een vlam . . . . . . . . . . . . . . . . . . . . 3.2.5 Toevoegen van noise . . . . . . . . . . . . . . . . . . . . 3.2.6 Rendering van de particles . . . . . . . . . . . . . . . . . 3.2.7 Procedurele controle . . . . . . . . . . . . . . . . . . . . 3.2.8 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . Vergelijking tussen de procedurele en de physics based methode

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

18 18 18 19 19 20 20 20 21

4 Non-photorealistic rendering van rook 4.1 Procedurele methode . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Skelet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Shape rendering . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Toepassingen en beperkingen . . . . . . . . . . . . . . . 4.2 Physics based methode . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Depth difference rendering . . . . . . . . . . . . . . . . . 4.2.2 2D rendering . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Self-shadowing . . . . . . . . . . . . . . . . . . . . . . . 4.2.4 Beperkingen . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.5 Uitbreidingen . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Vergelijking tussen de procedurele en de physics based methode

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

22 22 22 24 29 29 29 30 31 32 33 34

. . . . .

35 35 35 37 37 39

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

41 41 41 42 42 43 44 46 47 48 48 48 50 50

3.3

5 Non-photorealistic rendering van water 5.1 Procedurele methode . . . . . . . . . . . 5.1.1 Stromend water . . . . . . . . . . 5.1.2 Waterstralen onder druk . . . . . 5.1.3 Rimpelingen . . . . . . . . . . . 5.1.4 Andere watereffecten . . . . . . . 6 Keyframe Animation 6.1 Optimaliseren van windkrachten . 6.1.1 Inleiding . . . . . . . . . . . 6.1.2 Geparametriseerde krachten 6.1.3 Controle parameters . . . . 6.1.4 Objective functie . . . . . . 6.1.5 Afgeleiden . . . . . . . . . . 6.1.6 Uitbreiding . . . . . . . . . 6.1.7 Resultaten . . . . . . . . . 6.2 Adjoint methode . . . . . . . . . . 6.2.1 Inleiding . . . . . . . . . . . 6.2.2 Berekenen van de gradiënt . 6.2.3 Resultaten . . . . . . . . . 6.3 In-betweening techniek . . . . . . .

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

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

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

. . . . .

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

INHOUDSOPGAVE

6.4

v

6.3.1 Modelleren en animeren in gestructureerd 2D 6.3.2 Gasachtige fenomenen modelleren . . . . . . 6.3.3 Gasachtige fenomenen animeren . . . . . . . Andere methodes . . . . . . . . . . . . . . . . . . . .

7 Implementatie 7.1 Non-photorealistic rendering . . . . . 7.1.1 Depth difference rendering . . 7.1.2 2D rendering . . . . . . . . . 7.1.3 Vuur . . . . . . . . . . . . . . 7.1.4 Resultaten . . . . . . . . . . 7.1.5 Conclusie . . . . . . . . . . . 7.2 Keyframe animation . . . . . . . . . 7.2.1 Afgeleides van het dichtheids7.2.2 Minimalisatiefunctie . . . . . 7.2.3 Resultaten . . . . . . . . . . 7.2.4 Conclusie . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

50 51 51 52

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . en snelheidsveld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

53 53 54 54 54 55 55 55 59 61 61 69

8 Conclusie

71

Bibliografie

74

Hoofdstuk 1

Inleiding 1.1

Overzicht

Deze thesis bestaat uit twee delen. Enerzijds bestuderen we technieken om gasachtige fenomenen zoals water, vuur en rook op een non-photorealistische manier weer te geven. Anderzijds bestuderen we technieken om aan de hand van keyframes het animatie proces te controleren. Hierbij wordt eerst dieper ingegaan op het concept “gasachtige fenomenen”, in hoofdstuk 2. Daarna worden verschillende technieken besproken, zowel procedurele als physics-based, om gasachtige fenomenen non-photorealistisch te renderen, in hoofdstuk 3, 4 en 5. Verder worden verschillende keyframing technieken besproken in hoofdstuk 6. Ten slotte wordt de implementatie van enkele van deze technieken besproken in 7. Enkel de afbeeldingen in hoofdstuk 7 werden door de eigen implementatie gegenereerd.

1.2

Non-Photorealism versus Photorealism

In de computer graphics gebruikt men een computer om visuele beelden te generen of te bewerken. De eerste stap in dit veld werd gezet door Sutherland in de jaren 60 toen hij Sketchpad [Sut64] introduceerde, een systeem om objecten te tekenen met behulp van een grafische user interface. In de daaropvolgende jaren werd de nadruk vooral gelegd op fotorealisme, ofwel het zo goed mogelijk benaderen van de echte wereld. Belangrijke technieken die werden ontwikkeld om dit doel te bereiken, zijn onder andere texturing, bump mapping, ray tracing, subsurface scattering, photon mapping, . . . Telkens werd de vergelijking met de werkelijkheid, of een foto ervan, genomen als maatstaf voor de vorderingen. Hoewel het doel van photorealistic rendering nog niet bereikt is, werden er al zeer vergevorderde resultaten behaald, zoals in figuur 1.1 te zien. Deze figuur is gegenereerd met het photon mapping 1

HOOFDSTUK 1. INLEIDING

2

Figuur 1.1: Een afbeelding van een theepot, gegenereerd met photon mapping algoritme [Jen01]. Non-Photorealistic rendering hanteert deze maatstaf niet. Communicatie is belangrijk. Simulatie van de realiteit is hierbij niet van belang. Het gaat erom ideeën over te brengen. Technieken die reeds lang gebruikt werden door kunstenaars, worden op het domein van de computer graphics toegepast Een voorbeeld hiervan is een bepaalde schilderstijl na te bootsen [HJO+ 01]. Men gebruikt als input een schilderij en een foto. De output is de foto in de stijl van het schilderij. Zie figuur 1.2, waar gebruik gemaakt wordt van een schilderij van Van Gogh om een willekeurige foto in dezelfde stijl als het schilderij van Van Gogh te schilderen. Een andere toepassing van NPR is het maken van technische illustraties. Een fotorealistisch beeld is ongeschikt voor bepaalde doelen. Het bouwplan van een huis bijvoorbeeld, moet voor de aannemer duidelijk weergeven hoe het huis precies moet gebouwd worden. Het is geen vereiste om het huis zo realistisch mogelijk weer te geven op het bouwplan. In de medische wereld is het soms interessant om een lichaamsdeel niet fotorealistisch weer te geven. Met NPR is het mogelijk meer overzicht te creeëren door belangrijke elementen te accentuëren en onbelangrijke elementen meer naar de achtergrond te verplaatsen of zelfs helemaal niet weer te geven. In figuur 1.3 is het menselijke oor schematisch weergegeven. Alle delen van het oor zijn hierbij weergegeven, maar de andere elementen, zoals de schedel, zijn weggelaten.


3

Figuur 1.2: Het schilderij van Van Gogh rechts en de foto links worden gecombineerd tot een schilderij van de foto in dezelfde stijl als het schilderij van Van Gogh.

Figuur 1.3: Schematische voorstelling van het menselijk oor


1.3

4

Computer Animatie

Computer animatie is het creeëren van animaties, ofwel bewegende beelden, met behulp van een computer. Letterlijk betekent “to animate”, “to give life to”. Iets animeren is iets bewegen wat zichzelf niet kan bewegen, zij het een pop in de poppenkast, een tekening van Mickey Mouse of een met de computer gemodelleerd 3D karakter.

1.3.1

Geschiedenis

Traditionele animatie Reeds in de 19e eeuw werd onderzoek gedaan naar de mogelijkheid om een lijst van stilstaande beelden te interpreteren als een bewegend beeld1 . Dit leidde tot enkele simpele toepassingen als de thaumatroop, een platte schijf met aan beide kanten een beeld en aan beide zijkanten een koord. Door het koord te verdraaien kon de schijf snel omgedraaid worden en lijkt het alsof de twee beelden in elkaar over gaan. Jaren later, met de komst van de camera, werden deze animaties frame per frame met de hand getekend. Waarbij de hoofdanimator de belangrijkste frames, oftewel de keyframes tekende, en zijn medewerkers daarna de tussenliggende frames moesten invullen. Deze frames werden dan in snel tempo afgespeeld voor een videocamera.

Computer animatie In de jaren 60 ontstond de mogelijkheid om grafische modellen te tekenen op displays. In het begin werden statische beelden getekend op het scherm en opgenomen door een camera voor het scherm te plaatsen. In de jaren die daarop volgde, werden steeds nieuwe methodes ontwikkeld om computerbeelden te bewegen, onder andere door Ed Catmull en Barry Wessler. Later werden talen ontworpen om animaties te definiëren. Nog later, in de jaren 80 en 90 werd computer animatie gebruikt in grote commerciële projecten, bijvoorbeeld in films als Starship Troopers en Titanic. Voor een volledig historisch overzicht, zie [Par01].

1.3.2

Keyframing

In deze thesis richten we ons op het keyframing aspect van de computer animatie. Net als in de traditionele animatie, worden keyframes in de computer animatie gebruikt als refrentiepunten in het animatieproces. Letterlijk vertaald is een keyframe een “sleutel-frame”. Keyframes worden vooraf gedefiniëerd door de animator. De tussenliggende frames worden achteraf door 1

http://www.precinemahistory.net/introduction.htm


5

de computer berekend, om een overgang te maken tussen twee keyframes. Dit noemt men interpoleren.

Hoofdstuk 2

Gaseous phenomena Met gaseous phenomena ofwel gasachtige fenomenen, bedoelen we vuur, rook en wolken. Gassen hebben geen vaste geometrie. Gassen en vloeistoffen hebben allebei de eigenschap vloeibaar te zijn: Ze kunnen “vloeien” en vervormd worden. Gassen en vloeistoffen worden vaak op dezelfde manier beschreven in de fysica. Daarom besteden we in deze thesis ook kort aandacht aan vloeistoffen. Het verschil tussen beide is dat gassen geen vast volume hebben. Vloeistoffen wel. Daarom worden gassen meestal behandeld als compressible, dit wil zeggen dat de dichtheid spatiaal kan variëren. Vloeistoffen worden meestal behandeld als incompressible, dit wil zeggen dat de dichtheid overal hetzelfde is. Er zijn verschillende methodes beschikbaar om deze gasachtige fenomenen te simuleren. Hier bespreken we particle systems, cellulaire automaten en een numerieke methode, gebaseerd op de Navier-Stokes vergelijkingen.

2.1

Particle Systems

In [Ree83] wordt een particle system ge¨ıntroduceerd om fuzzy objecten zoals gasachtige fenomenen te simuleren. Een particle system is een collectie van particles, ofwel deeltjes. Aan elke particle zijn bepaalde attributen verbonden, zoals positie, snelheid, versnelling, kleur en leeftijd. De attributen veranderen in de tijd, volgens bepaalde regels. Zo verandert de positie van een particle als gevolg van zijn snelheid en de snelheid kan dan weer afhankelijk zijn van zijn versnelling. De kleur van een particle kan bijvoorbeeld afhankelijk zijn van zijn leeftijd, of van zijn positie. Particles kunnen gecreëerd worden in een bron en kunnen sterven als ze bijvoorbeeld een bepaalde positie of leeftijd bereiken. In figuur 2.1 is een vuurzee gesimuleerd met een particle system. Een uitbreiding op het klassieke particle system wordt globular dynamics genoemd, zie [MP89]. Elke particle heeft nu ook bepaalde afmetingen. En particles kunnen botsen met elkaar. Ver6

HOOFDSTUK 2. GASEOUS PHENOMENA

7

Figuur 2.1: Een vuurzee die zich uitstrekt over een planeet der kunnen er verschillende krachten tussen de particles werken zoals aantrekkingskracht of afstoting. In figuur 2.2 is een voorbeeld van globular dynamis weergegegeven. In [MCG03] wordt een particle system uitgebreid zodat het voldoet aan de Navier-Stokes vergelijkingen, die we bespreken in sectie 2.3.

2.2

Cellulaire automaten

Een cellulaire automaat bestaat uit een grid van cellen. Het grid kan een willekeurige dimensie hebben en de cellen kunnen een willekeurige vorm hebben. Elke cel is in een bepaalde toestand en de verzameling van mogelijke toestanden is eindig. De toestand van een cel verandert in de tijd onder invloed van de toestanden van zijn buren. Deze verandering wordt beschreven door bepaalde regels. Er zijn dus vier elementen belangrijk bij het definiëren van een cellulaire automaat: 1. De vorm van het grid en de cellen; 2. De mogelijke toestanden die de cellen kunnen aannemen; 3. Welke cellen beschouwd worden als buren van een cel; 4. Welke regels er van toepassing zijn om de state van cellen te veranderen. Deze cellulaire automaten hebben verschillende toepassingen, waaronder cryptografie, het simuleren van traffic flow, bosbranden en virtueel leven en ook op het gebied van gaseous


8

Figuur 2.2: Het simuleren van stromend water met globalur dynamics

Figuur 2.3: Het simuleren van wolken met een cellulaire automaat phenomena, zie [WKM98], [WLMK04] en [DKY+ 00]. De cellen worden dan gebruikt om dichtheden in op te slaan die het gas voorstellen. In figuur 2.3 ziet u een resultaat van de methode beschreven in de laatste paper.

2.3

Navier-Stokes vergelijkingen

In de fysica worden vloeibare stoffen gemodelleerd door de Navier-Stokes vergelijkingen. Deze vergelijkingen gebruiken een drukgrid p een snelheidsveld v om een vloeibare stof te modelleren. Deze zijn als volgt, zie [Sta99]: ∇·v = 0 ∂v 1 = −(v · ∇)v − ∇p + ν∇2 v + f ∂t ρ

(2.1) (2.2)


9

met ρ de dichtheid en ν de viscositeit, of kleverigheid” van de vloeibare stof. f Is een externe ” kracht. ∇ is de gradiënt operator: ∇ = (∂/∂x, ∂/∂y, ∂/∂z), in een driedimensionale ruimte. Deze twee vergelijkingen kan men combineren tot één vergelijking, waarbij het drukgrid p weg valt: ∂v = P −(v · ∇)v + ν∇2 v + f (2.3) ∂t Dit noemt men de Helmoholtz-Hodge decompositie. Voor de preciese afleiding, zie [Sta99]. P stelt hierbij de projectie operator voor. Deze zorgt dat het snelheidsgrid v divergentievrij blijft. Dit wil zeggen dat de massa behouden blijft. −(v · ∇)v staat voor de advectie, ν∇2 v voor de diffusie en f voor het toevoegen van krachten. Dus om de verandering van het snelheidsgrid in de tijd (= ∂v/∂t) te berekenen, moeten we deze 4 stappen achtereenvolgens toepassen op v. De volgorde is als volgt: Voeg externe krachten toe ⇒ advectie ⇒ diffusie ⇒ projectie. Om vloeistoffen en gassen te modelleren op een computer, wordt vergelijking 2.3 opgelost in discrete tijdstappen ∆t. Ook wordt een grid opgedeeld in een discreet aantal cellen. De waarde van een cel stelt dan de dichtheid in het centrum van de cel voor.

2.3.1

Voeg externe krachten toe

Een externe kracht wordt toegevoegd door deze kracht als een grid voor te stellen en dit grid op te tellen bij het snelheidsgrid v. Het krachtgrid wordt eerst nog vermenigvuldigd met de grootte van de tijdstap ∆t. Krachten die gedurende een lange tijd worden uitgeoefend op v hebben zo een grotere impact. We stellen v(x) voor als de waarde van v op positie x met x een spatiale variabele die in 2D kan voorgesteld worden als x = (x, y) en in 3D als x = (x, y, z) en we stellen f (x, t) voor als de kracht op positie x op tijd t. Dan kunnen we het toevoegen van externe krachten schrijven als: vnew (x) = v(x) + ∆tf (x, t)

(2.4)

Dit is een benadering van de realiteit want we gaan er van uit dat de kracht niet verandert over de tijdstap.

2.3.2

Advectie

Als de vloeistof of gas in een bepaald punt in beweging wordt gebracht door een externe kracht, wordt deze beweging gepropageerd naar andere punten. Dit noemt men advectie. Om de advectie te berekenen, moeten we dus de verandering van het snelheidsgrid in de tijd berekenen als gevolg van deze advectie: ∂vnew = − (u · ∇) v ∂t

(2.5)

Om deze vergelijking op te lossen, kan men finite differincing gebruiken, zie [FM96]. Deze methode is echter instabiel bij grote tijdstappen. Een stabiele methode bestaat ook, en deze


10

wordt de “method of characteristics” genoemd. Om de waarde van het snelheidsveld op een bepaald punt v(x) op een bepaald tijdstip t te weten, backtracen we x over een tijd −∆t. Dit wil zeggen, we berekenen waar dit vloeistofdeeltje zich bevond op tijdstip t − ∆t. We noemen deze positie v(x0 ). Dan gebruiken we deze waarde als de waarde van v(x): v(x) = v(x0 ).

Interpolatie Aangezien we het snelheidsgrid opdelen in een discreet aantal cellen, treedt er een probleem op bij deze methode. De positie x stelt het centrum van de cel voor. Als we x echter backtracen en zo x0 vinden, is het meestal zo dat x0 niet precies in het centrum van een cel ligt. Dit lossen we op door interpolatie. De waarde van x0 is dan de gecombineerde waarde van zijn naburige cellen.

Particle tracing Om te backtracen in het snelheidsgrid, moeten we een manier hebben om bij te houden hoe een deeltje, of particle zich verplaatst in het grid. Dit gebeurt met particle tracing. Als een deeltje p zich op op tijd t op positie x = (x, y, z) bevindt, dan vermenigvuldigt men dit deeltje met v(x) en met ∆t om te weten waar p zich bevindt op tijdstip t + ∆t. Bij backtracen gaat men omgekeerd te werk. Men weet de positie van p op een tijdstip t + ∆t, en dus vermenigvuldigen we x met v(x) en −∆t om de positie van p op het tijdstip t te bepalen.

2.3.3

Diffusie

Een vloeistof of gas heeft een bepaalde viscositeit, dit is de mate waarin een vloeistof of gas weerstand biedt tegen vervormingen. Deze vervormingen, worden ook wel diffusie genoemd, de verspreiding van een vloeistof of gas in de ruimte. Om diffusie te modelleren, moeten we volgende vergelijking oplossen: ∂v = ν∇2 v (2.6) ∂t Dit kan herschreven worden als: (I − v∂t∇2 )vnew (x) = v(x)

(2.7)

Dit is een lineair stelsel dat na discretisatie kan opgelost worden naar de onbekende vnew (x).


2.3.4

11

Projectie

Deze stap zorgt ervoor dat er geen divergentie optreedt in het snelheidsveld. Hiervoor moeten we volgende vergelijkingen oplossen: ∇2 q = ∇ · v

(2.8)

vnew = v − ∇q

(2.9)

De eerste vergelijking wordt opgelost om ∇q te berekenen, en deze oplossing wordt gebruikt om vnew in de tweede vergelijking te berekenen.

2.3.5

Het dichtheidsveld

De Navier-Stokes vergelijkingen kunnen toegepast worden om een snelheidsveld voor te stellen die invloed uitoefent op het gas of de vloeistof. Zoals eerder gezegd is een vloeistof incompressible, de dichtheid is overal gelijk. Een gas is dit echter niet. En dus hebben we ook een formule nodig om de dichtheid van een gas op elke positie in de ruimte te bepalen. Deze is als volgt: ∂ρ = −(v · ∇)ρ + κ∇2 ρ + S (2.10) ∂t Deze vergelijking lijkt sterk op vergelijking 2.3 en de oplossing ervan is dan ook analoog. De eerste term, −(v ·∇)ρ is de advectie stap, en stelt dat de dichtheid voortbeweegt onder invloed van het snelheidsgrid. Dit is logisch. Als we een kracht uitoefenen op rook, bijvoorbeeld een windkracht, zal de rook deze kracht volgen. De tweede term, κ∇2 ρ is de diffusie stap voor het dichtheidsgrid. Deze zegt dat rook zich verspreidt in de omgeving. κ is de diffusie variabele, die aangeeft in welke mate rook onderhevig is aan diffusie. De derde term, S, is het toevoegen van rookbronnen. Een dichtheidsveld wordt groter als er bronnen worden toegevoegd. Dit is analoog aan het toevoegen van krachten op het snelheidsveld. Merk op dat we in deze formule geen projectie stap toepassen. Dit is omdat het dichtheidsveld niet divergentievrij hoeft te zijn. Rook kan oplossen in de omgeving. Als men toch wil dat het dichtheidsveld een gewenste massa m behoudt, kan men simpelweg alle cellen vermenigvuldigen met een constante: m ρnew (x) = ρ(x) P ρ met

P

(2.11)

ρ de som van de cellen van het dichtheidsveld.

In figuur 2.4 is rook weergegeven dat gesimuleerd werd met de Navier-Stokes vergelijkingen. Deze afbeelding is afkomstig van [Sta99].


12

Figuur 2.4: Het simuleren van rook met de Navier-Stokes vergelijkingen

2.3.6

Vuur

De Navier-Stokes vergelijkingen kunnen gebruikt worden om het snelheidsgrid van een brandend vuur te modelleren. Het vuur zelf reageert echter anders op dit snelheidsgrid dan rook. In [NFJ02] wordt een methode beschreven om vuur fysisch accuraat te modelleren.

Hoofdstuk 3

Non-photorealistic rendering van vuur 3.1

Procedurele methode

Vuurhaarden worden be¨ınvloed door de lucht rondom het vuur. Het heetste deel van het vuur bevindt zich in het centrum, en de lucht hierboven stijgt. Door de stijging van deze hete lucht, wordt het vervangen door koude lucht die van de zijkanten wordt aangevoerd. Dit proces herhaalt zich: deze koude lucht wordt weer verwarmd door het vuur en gaat weer stijgen. Dit zorgt ervoor dat het vuur een conische vorm krijgt, met inhammen naar binnen en naar boven toe, door de stootjes van koude lucht langs de zijkanten, zoals weergegeven in figuur 3.1. Hier stellen we een model op, beschreven in [Yu99] met als doel om dit effect na te bootsen. Dit model heeft een hiërarchische structuur, zoals weergegeven in figuur 3.2. Met FN het aantal vlammen van de vuurbasis. Deze vlammen worden gecontroleerd door positieskeletten en vormskeletten. Alle parameters geassocieerd met de skeletten worden opgeslagen in een matrix om het model van de vuurbasis voor te stellen. Topvlammen, dit zijn vlammen zonder conectie met de basis, worden gecontroleerd door een ander, soortgelijk model. In deze sectie bespreken we hoe men een vuurbasis en topvlammen kan construeren. We bestuderen de verschillende parameters en we onderzoeken hoe we windeffecten kunnen toevoegen. In de handgetekende animatie van vuur (figuur 3.1) zien we dat de vuurbasis bestaat uit verschillende vlammen op verschillende posities, elk met een verschillende vorm, geconnecteerd met elkaar. We bestuderen nu deze drie kenmerken (positie, vorm, en connectie).

13

HOOFDSTUK 3. NON-PHOTOREALISTIC RENDERING VAN VUUR

Figuur 3.1: Een handgetekende animatie van vuur

Figuur 3.2: Het vuurmodel

14


15

Figuur 3.3: Het vormskelet van een vlam

Figuur 3.4: Verschillende vlamvormen. Vorm 1,2 en 3 zijn vlammen van de vuurbasis. 4 en 5 zijn topvlammen.

3.1.1

Positieskelet

De vlammen zijn verspreid over de basis, daarom bestaat het positieskelet uit een lijst van vectoren van het centrum van de basis naar de positie van de vlammen. Deze posities zijn afgeleid uit figuur 3.1(a).

3.1.2

Vormskelet

Als we de vorm van de vlammen in figuur 3.1 bekijken, zien we dat een driehoek kan gebruikt worden als vorm van het skelet, zoals in figuur 3.3. Als we eenmaal de vormskeletten hebben, is het gemakkelijk om de vlamvormen eruit af te leiden. We zien in figuur 3.1 dat verschillende vlammen verschillende vormen kunnen hebben, deze vormen zijn opgesomd in figuur 3.4. Deze vlammen worden op de vormskeletten geplaatst.


16

Figuur 3.5: Een vlamvorm

Figuur 3.6: Verschillende connectie types

3.1.3

Connecties

Elke vlam heeft nu zijn eigen vorm. Het enige wat ons nog rest is de connecties tussen de vlammen. In figuur 3.1 zien we dat ook hier weer verschillende mogelijkheden zijn, opgesomd in figuur 3.6. Wat opvalt, is dat, hoewel elk van deze vormen duidelijk verschillend zijn, ze toch allemaal het effect simuleren van de koude laterale wind, die stijgt als ze in de vlammen komt. Het inbouwen van deze curves in het model gebeurt analoog aan het inbouwen van de vlamvormen. De curve wordt geplaatst op de zijdes van de driehoeken.

3.1.4

Topvlammen

Om topvlammen te genereren, delen we de vuurbasis op in een linker, rechter en middendeel. Voor elk deel zoeken we de laagste vlam en we plaatsen de topvlam op dezelfde verticale positie en we plaatsen de topvlam net hoger dan de hoogste vlam van dat deel. Deze topvlam stijgt op uit de vuurbasis en wordt kleiner naarmate het hoger klimt.


3.1.5

17

Analyse van de parameters

De parameters in de matrix stellen de volledige animatie voor. Het is mogelijk de parameters aan te passen tot we een animatie krijgen die vergelijkbaar is met de handgetekende versie. Een groot aantal van deze parameters kunnen we stochastisch laten variëren om de willekeurige bewegingen van vuur te modelleren. We kunnen bijvoorbeeld het vormskelet van de vlammen met kleine stapjes laten variëren in de tijd. We kunnen de vlamvormen en de connectietypes wijzigen in de tijd. Het kan interessant zijn om sommige parameters constant te houden, zoals bijvoorbeeld de vlamvormen van de buitenste vlammen. Om de conische vorm van het vuurmodel te behouden, is het best om de hoogtes van de buitenste vlammen altijd kleiner te houden dan de hoogtes van de binnenste vlammen.

3.1.6

Inkleuren

Het heetste gedeelte van het vuur is in het centrum, en er circuleert koude lucht langs de zijdes van het vuur. Om dit te simuleren, kunnen we een kleur gradiënt gebruiken, met geel in de kern tot rood om de koudere delen van de vlammen voor te stellen.

3.1.7

Wind

Wind kan gesimuleerd worden door slechts één parameter aan het model toe te voegen. Als vuur onder invloed is van wind die langs de zijkant blaast, worden de vlammen naar de andere kant bewogen, maar blijft de basis vast. De vlammen worden gebogen door de wind. Als we deze buiging kunnen genereren, kunnen we het effect van wind simuleren. Dit doen we door een parameter ∆θ die de hoek voorstelt, vergeleken met vlammen niet onder invloed van wind. Het is voldoende om enkel de referentiepunten van de vormskeletten te transformeren onder invloed van ∆θ. Figuur 3.7 laat het effect van wind zien op de gegenereerde vlammen. Omdat de buiging wordt gecontroleerd door ∆θ, kunnen we deze waarde ook interpoleren om het wind effect realistischer te maken. We kunnen deze waarde bijvoorbeeld laten moduleren met een sinusfunctie, zodat het effect van een zacht heen- en weerslingerend vuurtje ontstaat. Dit model is echter gebaseerd op handgetekende figuren, en niet op de fysische kenmerken van vuur. Grote waardes van ∆θ geven onrealistische resultaten.

3.2

Physics based methode

In [LF02] wordt een methode beschreven om vuur te modelleren en te animeren. Hun systeem bestaat uit verschillende stages, die gecontroleerd kunnen worden door de animator of die gebaseerd zijn op physics. In deze sectie behandelen we deze stages en onderzoeken we


18

Figuur 3.7: Vlammen, gegenereerd door deze procedurele methode, met invloed van wind hoe dit model kan toegepast worden om vuur non-photorealistisch weer te geven. De verschillende stages zijn als volgt:

3.2.1

Structurele vorm van een vlam

Er wordt een B-spline curve1 gebruikt om de structurele vorm van een vlam te modelleren. Deze curve interpoleert een aantal controlepunten. De vlam zelf kan splitsen of mergen met een andere vlam. De controlepunten worden getraced doorheen het wind field. Het eerste en laatste controlepunt blijven vast om visuele artefacten te voorkomen.

3.2.2

Vlam evolutie

Tijdens de animatie bewegen de controlepunten in het wind field. Deze beweging is afhankelijk van 4 componenten: advectie, diffusie, intiële beweging en Archimedeskracht. advectie is de beweging van een particle als gevolg van de windkrachten. De windkrachten kunnen fysisch gebaseerd zijn, of gedefiniëerd door de animator. De initiële beweging wordt gebruikt om de beweging van de vlammenbron te modelleren, zoals bijvoorbeeld een bewegende fakkel. De archimedeskracht is een opwaartse kracht dat het stijgen van hete lucht beschrijft.

3.2.3

Splitsen van een vlam

De structurele curve kan breken zodat er verschillende vlammen ontstaan met een beperkte levensduur. Dit wordt gemodelleerd als een statistisch proces. Een vlam bestaat typisch uit drie verschillende regio’s, zoals weergegeven in figuur 3.8. De vlam ontwikkelt zich tot het Hi 1

http://mathworld.wolfram.com/B-Spline.html : de B-spline curve is een generalisatie van een bezier-curve.


19

Figuur 3.8: De drie regio’s van een vlam bereikt. Daar bestaat een kans dat de vlam zal splitsen of flikkeren.Als er zich een splitsing voordoet, wordt een deel van de curve gescheiden van de top van de vlam. Elk afgescheiden deel blijft een korte tijd zichtbaar, afhankelijk van zijn grootte. Om een meer dynamisch effect te verkrijgen kan ook hier een statistische variabele worden toegevoegd die, samen met de grootte, de levensduur van de afgescheiden vlam bepaalt.

3.2.4

Profiel van een vlam

Er wordt een cylindrisch profiel gebruikt om de oxidisatie regio voor te stellen. Dit is het zichtbare gedeelte van de vlam. De vlam wordt voorgesteld als een rotationeel symmetrisch oppervlak; gebaseerd op een simpel tweedimensionaal profiel. Zie figuur 3.9 voor voorbeelden van dergelijke profielen. Dit profiel wordt ge-pointsampled om later noise toe te voegen.

3.2.5

Toevoegen van noise

Het profiel van een vlam wordt lokaal getransformeerd en verplaatst om het chaotische, realistische effect van echte vlammen te benaderen. Dit gebeurt door de particles, ontstaan door de pointsampling, te transformeren en te verplaatsen. Een tweede noise functie wordt


20

Figuur 3.9: Vlamprofielen voor een kaarsvlam, een fakkelvlam en kampvuurvlammen toegepast om de turbulentie van lucht te simuleren.

3.2.6

Rendering van de particles

In plaats van de kleur van de vlam te berekenen uit een fysisch model, kunnen we de kleur ook verkrijgen door een foto te mappen op het profiel voor de vlamvorm, zoals in figuur 3.9. Elk beeld kan gebruikt worden, deze techniek is dus geschikt om de vlam non-photorealistisch weer te geven door een non-photorealistisch beeld te gebruiken. Het is ook mogelijk om dezelfde manier te gebruiken als die in de procedurele methode: het gebruik van een kleur gradiënt. Het gloeien van de vlammen kan ook weergegeven worden. Dit doet men door voor elk particle de hoeveelheid straling te berekenen die de camera bereikt. Deze factor wordt dan gebruikt om de intensiteit van de particle af te stellen.

3.2.7

Procedurele controle

De beschreven methode geeft de animator directe controle over de vorm en de kleur van de vlammen. Ook de schaal, het flikkeren en de scheiding van vlammen kan gecontroleerd worden. De globale beweging van de vlammen wordt gestuurd door het wind field. er zijn nog controle mogelijkheden, waaronder interactie met een object, het controleren van de spreiding van de vlammen en het genereren van rook.

3.2.8

Conclusie

Deze methode wordt physics based genoemd omdat de vlammenbeweging fysisch gemodelleerd wordt. Het model modelleert niet de fysische reacties die plaats vinden als een brandstof ontstoken wordt. Het model maakt gebruik van statistische methodes, bijvoorbeeld bij het splitsen van de vlammen, en van procedurele technieken, zoals het kiezen van de vlamvorm, om een realistische animatie te benaderen. Zoals in figuur 3.10 weergegeven, is het moge-


21

Figuur 3.10: Een scene van de film Shrek lijk om met deze techniek goede resultaten te behalen op een hoge resolutie. Deze methode implementeert een vlamprofiel, zoals uitelegd in sectie 3.2.4, en dus kunnen contouren duidelijk onderscheiden worden, en is het mogelijk het vuur op een non-photorealistische wijze te genereren. Voor een volledige physics based methode, zie [NFJ02].

3.3

Vergelijking tussen de procedurele en de physics based methode

De procedurele methode, beschreven in sectie 3.1 en de physics based methode, beschreven in sectie 3.2 hebben veel technieken gemeenschappelijk. Beide maken gebruik van een structurele vorm, in de procedurele methode vormskelet genoemd, en een vlamprofiel, in de procedurele methode vlamvorm genoemd. Statistische technieken worden door beide methodes gebruikt om de chaos van een vlam na te bootsen. Verder wordt splitsing van vlammen bij beide methodes gecontroleerd door de animator. Beide methodes baseren zich sterk op (een getekende versie van) een echte vlam, zoals bijvoorbeeld bij het tekenen van de vlamprofielen. Het grote verschil tussenbeide is dat de procedurele methode wind simuleert door de vorm van de vlammen aan te passen en door het model te buigen in een windrichting. De physics based methode leest de windkrachten af uit een wind field en past deze toe op de structurele vorm van de vlammen, waardoor deze vervormd worden.

Hoofdstuk 4

Non-photorealistic rendering van rook 4.1

Procedurele methode

Een manier die animators gebruiken om rook voor te stellen is weergegeven in figuur 4.1 . Rook wordt weergegeven als lange slierten of als kleine wolkjes, puffs genaamd. Het model dat we hiervoor gebruiken, is weergegeven in figuur 4.2. Eerst wordt een skelet gemoddeleerd, de globale vorm. En daarna wordt de vorm van de rook zelf getekend over het skelet (shape rendering). Deze methode is beschreven in [Yu99].

4.1.1

Skelet

Zoals figuur 4.1 aangeeft, kan de globale vorm van rook voorgesteld worden door een sinu¨ısidale vorm waarvan de amplitude en frequentie groter wordt, naarmate de rook stijgt. Daarom kunnen we volgende formule toepassen om het skelet na te bootsen: SmkSKLTu,t = SmkAM (u) · sin(α(t) + ω(u))

(4.1)

met SmkSKLTu,t een punt op het skelet, u een spatiale variabele en t de tijd. SmkAM (u) is de amplitude en ω(u) de frequentie, beide zijn lineaire functies van u. α(t) is de fase, een lineaire functie van t. In figuur 4.3 en 4.4 ziet u twee voorbeelden van dergelijke skeletfuncties. Voor figuur 4.3 zijn de bijbehorende functies: SmkAM (u) = u;

(4.2)

2

α(t) = t ;

(4.3)

ω(u) = u;

(4.4)

22

HOOFDSTUK 4. NON-PHOTOREALISTIC RENDERING VAN ROOK

Figuur 4.1: handdrawn

Figuur 4.2: Het model om rook weer te geven

23


24

Figuur 4.3: Een voorbeeld van de skeletfunctie SmSKLT(u,t) Voor 4.4 zijn de bijbehorende functies: SmkAM (u) = u2 ;

(4.5) 3

4.1.2

α(t) = 0, 2 · t ;

(4.6)

ω(u) = 3 · u;

(4.7)

Shape rendering

In figuur 4.1 wordt rook links weergegeven door slierten en rechts door een aantal puffs. De slierten worden dunner en splitsen in kleinere slierten naarmate ze stijgen. Rechts worden er onderaan veel puffs getekend, en minder naarmate men stijgt. De grootte van elke puff variëert om dispertie, oftewel het uiteenvallen van de rook, te modelleren.

Rook slierten Bij het tekenen van rook slierten moet rekening gehouden worden met volgende delen:


25

Figuur 4.4: Een andere skeletfunctie SmSKLT(u,t) 1. Detectie van breekpunten; 2. Keuze van de grootte van de opening tussen breekpunten; 3. Keuze van de twee eindpunten van een opening; 4. De vorm van een gesplitst stuk van de sliert; 5. Inkleuren. Als we naar figuur 4.1 kijken, zien we dat breekpunten pas voorkomen op een bepaalde hoogte. Daarom wordt er een drempelwaarde SmkRH ingesteld. Zie ook figuur 4.5, links. Enkel de rook boven die drempelwaarde wordt opgesplitst. Slierten splitsen in het midden, bij snijding van de Y-as. Alle snijpunten van het skelet en de Y-as boven SmkRH worden in een array geplaatst, BreakPi (i = 1, ..BrkN ) met BrkN het aantal breekpunten. Figuur 4.1 laat ook zien dat de opening tussen twee slierten groter wordt naarmate de rook stijgt. Daarom definiëren we een array van openingsgroottes GapSi (i = 1, ..BrkN ) (van het Engelse woord gapsize) als een functie van de amplitude van het skelet en het hoogteverschil tussen het huidige breekpunt BreakPi en de total hoogte SmkH : GapSi = Cw · SmkAM (u) · (BreakP i − SmkH), (i = 1, ..BrkN ) met Cw een factor die de animator kan instellen om GapSi te tunen.

(4.8)


26

Figuur 4.5: Het skelet

Figuur 4.6: De breedte van het eerste stuk van de sliert, afhankelijk van t Nu we weten waar de breekpunten zijn en hoe groot de openingen zijn, kunnen we het beginen eindpunt van elke sliert bepalen. Zie figuur 4.5, rechts. We maken hiervoor 2 arrays, i Lef tBKPi (i = 1, ..BrkN ) en RightBKPi (i = 1, ..BrkN ). met als u-coördinaat − GapS voor 2 GapSi Lef tBKPi en 2 voor RightBKPi . De t-coördinaat voor Lef tBKPi is de t-coördinaat van het dichtstbijzijde punt met dezelfde u op het skelet. Nu het skelet is ingedeeld in stukken, kunnen we de slierten zelf tekenen. Zoals we zien in 4.1 is de breedte van het eerste stuk groot onderaan, en daalt de breedte naarmate de rook stijgt. Om dit te simuleren, maken we de breedte SmkW van het eerste stuk afhankelijk van t zoals weergegeven in figuur 4.6 Uit 4.1 blijkt dat de breedte van de andere slierten afhankelijk is van u om het effect van dispertie te moddeleren. Om dit te bereiken, gebruiken we een sinu¨ısidale vorm zoals weergegeven in figuur 4.7.


27

Figuur 4.7: De breedte van de overige in functie van u

Figuur 4.8: puff De laatste stap van het renderingsproces is het inkleuren. Het heetste gedeelte van de rook bevindt zich onderaan daarom laten we de kleur overlopen van de achtergrondkleur onderaan tot een zelfgekozen kleur, bijvoorbeeld wit, boven. Een andere methode is om de rook één kleur te geven, en transparantie toepassen, afhankelijk van de hoogte. Hoe verder naar onder, hoe meer transparantie. De contouren van de slierten krijgen een vaste kleur. Het resultaat is weergegeven in figuur 4.9.

Rook puffs De puffs in figuur 4.1, rechts, kunnen gemodelleerd worden door een antal bogen op verschillende posities en met verschillende groottes, getekend rond een cirkel, zoals weergegeven in figuur 4.8. Het aantal puffs en hun groottes worden bepaald door een simpel stochastisch model, met een sinus of een gaussiaanse functie als probability density function. Voor meer info over de probability density functions, zie [Yu99].


Figuur 4.9: Sigaretten rook gerenderd met rookslierten

Figuur 4.10: Schoorsteenrook gerenderd met rookpuffs

28


4.1.3

29

Toepassingen en beperkingen

De rookslierten kunnen toegepast worden om rook van sigaret of damp van een kop koffie voor te stellen, zie figuur 4.9. De puffs zijn meer geschikt om rook uit een schoorsteen of van een stoomboot te modelleren, zie figuur 4.10. Deze techniek is echter niet geschikt voor sommige types van rook, zoals de rook die vrijkomt bij een grote explosie, of hele dikke rook.

4.2

Physics based methode

4.2.1

Depth difference rendering

Een manier om rook cartoonachtig weer te geven, is gebruik maken van depth differencing, beschreven in [SMC04]. De rook wordt voorgesteld door particles. Om de rook te simuleren gebruiken we een fysisch gebaseerd model, zoals beschreven in 2.3. We hebben echter enkel de output van de simulator nodig, dus elke andere simulator waarin een particle system kan gebruikt worden, kan in principe gebruikt worden. Om een particle system te genereren, introducren we gewichtloze marker particles aan de bron. Deze particles volgen het snelheidsveld. Positie, snelheid en dichtheid worden dan berekend uit de simulatie. Dit is gemakkelijk te implementeren want het model dat wij gebruiken heeft al particle tracing als één van zijn basisfeatures. Als de dichtheid lager is dan een bepaalde drempelwaarde, wordt de particle verwijderd en wordt een nieuwe particle gecreëerd op een willekeurige plaats waar de dichtheid wel hoog genoeg is. Het systeem werkt in twee stappen. In een eerste stap worden de particles gerenderd door middel van een rendering primitieve, bijvoorbeeld een schijf, en ingekleurd. In een tweede stap wordt de dieptebuffer onderzocht. Als het verschil van de dieptebuffer van een pixel met één van zijn aangrenzende pixels groter is dan een bepaalde drempelwaarde, wordt zijn kleur veranderd in de silhouetkleur. Meer specifiek wordt een pixel i,j in de silhouetkleur gezet (bijvoorbeeld zwart) als één van volgende formules geldt:

zi+1,j − zi,j ∆x zi,j − zi−1,j ∆x zi,j+1 − zi,j ∆y zi,j − zi,j−1 ∆y

>γ

(4.9)

>γ

(4.10)

>γ

(4.11)

>γ

(4.12)


30

Figuur 4.11: depth differencing

Figuur 4.12: Het gebruik van depth differincing voor het renderen van rook met γ de drempelwaarde ingesteld door de animator. In figuur 4.11 is dit algoritme ge¨ıllustreerd. We hebben drie particles. In een eerste stap worden de particles weergegeven als schijven en ingekleurd. In een tweede stap wordt de dieptebuffer pixel per pixel doorzocht. Stel nu dat de afstand tussen particle 1 en 2 groter is dan γ maar de afstand tussen particle 2 en 3, en de afstand tussen particle 1 en 3 niet. De afstand tussen de particles en de achtergrond is uiteraard groter dan γ. Dan worden de pixels aan de buitenkant van de particles in de silhouetkleur gezet, en ook de pixels die grenzen aan particle 1 en 2. In figuur 4.12 wordt een resultaat weergegeven van deze techniek.

Achtergrond Deze techniek is gebaseerd op [DS00]. Hierin worden de bladeren van een boom ook voorgesteld door particles die gerenderd worden aan de hand van een rendering primitieve. Door depth differincing worden de contouren getekend. Zie figuur 4.13.

4.2.2

2D rendering

Deze techniek, besproken in [FCR04], werkt ook in 2 stappen en is voor een deel analoog aan de vorige techniek. Ook hier wordt de rook gesimuleerd aan de hand van een fysisch model en gebruikt men de output van de simulatie als input voor dit algoritme. Men gebruikt marker particles die getraced worden doorheen het velocity field. Men gaat nu echter omgekeerd


31

Figuur 4.13: De bladeren worden weergegeven door depth difference rendering.

Figuur 4.14: 2d rendering tewerk als in de vorige sectie. Men tekent eerst de outlines van de rendering primitieve en daarna plakt men de binnenkant erover. Zie figuur 4.14. Om de animator meer controle te geven over het resultaat is het ook mogelijk om de particles in groepen in te delen, op basis van hun afstand tot het viewpoint. De animator kan zelf kiezen hoe grof de indeling moet gebeuren. In figuur 4.15 staan 4 voorbeelden. Linksboven worden alle particles in één groep ingedeeld. Rechtsboven worden de particles gesplitst in 2 groepen. De particles die het meest ver weg zijn worden gegroepeerd, en de particles die het dichtst bij zijn worden gegroepeerd. Idem voor de particles linkssonder, maar hier worden 3 groepen gebruikt. De particles rechtsonder worden in het maximaal aantal groepen verdeeld. Elke groep bestaat uit precies 1 particle.

4.2.3

Self-shadowing

In [MFH04] wordt een methode beschreven om rook non-photorealistisch weer te geven. Hierbij wordt de rook in 2 kleuren ingekleurd, en kan de schaduw van de rook op de rook zelf weergegeven worden. Deze techniek is gebaseerd op depth differencing. Het gebruikt rookpuffs als rendering primitieve en het berekent een normaalmap en dieptemap om een rookpuff in 2 kleuren te genereren. Een normaalmap kent aan elk punt op de puff een kleur toe op basis van de richting van zijn normaal. De dieptemap doet hetzelfde, maar dan op basis van


32

Figuur 4.15: Indeling in groepen

Figuur 4.16: Het generen van een tweekleurige rookpuff (rechts) door het gebruik van een normaal map en diepte map de diepte van het punt. Men gebruikt vier verschillende puffs om het geheel dynamischer te maken. Zie figuur 4.16. In figuur 4.17 wordt een resultaat van deze techniek weergegeven.

4.2.4

Beperkingen

Als primitieven naar voor of achter bewegen en zo de drempelwaarde oversteken, ontstaan er plotse verschuivingen in de silhouettes. Dit komt ook voor als het camerastandpunt verandert.


33

Figuur 4.17: Een rookwolk gerenderd met de methode van self-shadowing

4.2.5

Uitbreidingen

Variabele grootte Als we de depth differincing of 2d rendering techniek toepassen, gaat er onder andere dichtheidsinformatie verloren. Een particle wordt verwijderd als de dichtheid op die positie onder een bepaalde drempelwaarde valt. Hoe hoog de dichtheid precies is, wordt echter niet weergegeven. Een oplossing hiervoor is de particles op een variabele grootte renderen, afhankelijk van de dichtheid op die positie. Hoe hoger de dichtheid, hoe groter de particle.

Variabele kleur Een andere manier om het verlies van dichtheidsinformatie op te vangen, is de kleur van de particle afhankelijk te maken van de dichtheid. De rook kan bijvoorbeeld zwart gerenderd worden bij de hoogste dichtheid en wit op plaatsen van lage dichtheid. Deze techniek kan ook gebruikt worden als de simulatie temperatuurinformatie bevat. In gebieden met een hoge temperatuur kunnen particles rood gerenderd worden. Hoe meer de temperatuur daalt, hoe meer het rood overgaat in zwart.

Variabele vorm Om het geheel een meer dynamische look te geven, kan men ervoor kiezen de vorm van de particle aan te passen afhankelijk van zijn snelheid. Met vorm bedoelt men oriëntatie en stretch. De oriëntatie van een particle is dan afhankelijk van de richting van de snelheid, en de stretch van een particle is afhankelijk van de grootte van de snelheid. Een vaste vorm


34

Figuur 4.18: Het effect van de richting (angle) en de grootte (magnitude) van de snelheid op de vorm van een particle resulteert in oninteressante renderings. De vorm aanpassen aan zijn snelheid maken de rook visueel duidelijker. Zie figuur 4.18.

4.3

Vergelijking tussen de procedurele en de physics based methode

De procedurele methode is veel beperkter dan de physics based methode. Het is enkel mogelijk om lange slierten stijgende rook te modelleren. De physics based methode kan in principe gebruikt worden voor elk type rook, van een dikke rookwolk tot de rook van een smeulende sigaret.

Hoofdstuk 5

Non-photorealistic rendering van water 5.1

Procedurele methode

In deze sectie bespreken we een procedurele methode, beschreven in [Yu99], om verschillende watereffecten op een non-photorealistische manier weer te geven.

5.1.1

Stromend water

Figuur 5.1 laat een methode zien om stromend water gestyleerd weer te geven. In deze sectie bespreken we een model die deze tekening nabootst. Deze methode kan gebruikt worden om stromend water, zoals bijvoorbeeld een rivier weer te geven. Om één frame te tekenen, beginnen we met twee grenslijnen, die de bedding van de rivier aangeven. Tussen deze grenslijnen tekenen we een aantal verbindingslijnen, horizontale golven

Figuur 5.1: Handgetekend stromend water 35

HOOFDSTUK 5. NON-PHOTOREALISTIC RENDERING VAN WATER

36

Figuur 5.2: Het tekenen van stromend water: (a) Teken de grenslijnen (b) Teken de horizontale golven (c) Teken de vertikale golven

Figuur 5.3: Stromend water, ingekleurd met de gradiënt methode genaamd. Op deze golven tekenen we een aantal kleine lijnen, vertikale golven genaamd. Daarna tekenen we toppen bovenop de horizontale golven en schuim rondom deze toppen. In een volgend frame worden weer dezelfde grenslijnen getekend. De horizontale golven worden verplaatst om de stroming van het water te simuleren. De vertikale golven, toppen en het schuim worden weer op deze horizontale golven getekend, zoals weergegeven in figuur 5.2. Zowel de horizontale en vertikale golven, en de toppen en schuim op deze golven bevatten random parameters. Dit dient om het water meer levendig te maken. Het inkleuren kan gebeuren door een eenduidige kleur, zoals licht blauw voor het watergedeelte te gbruiken, donker blauw voor de horizontale en vertikale golven en wit voor de toppen schuim. Een andere manier is om een gradiënt kleur te gebruiken van licht naar donkerblauw om het gebied tussen twee aanliggende horizontale golven in te kleuren. Dan hoeven de vertikale golven niet getekend te worden. In figuur 5.3 wordt deze gradiënt methode geillustreerd.


37

Figuur 5.4: De globale vorm van een waterstraal

Figuur 5.5: Toevoegen van golven aan de waterstraal

5.1.2

Waterstralen onder druk

Een waterstraal onder druk, zoals de waterstraal die uit een tuinslang komt, kan op grotendeels dezelfde manier gemodelleerd worden als voorgaande methode. Het gebruikt grenslijnen, golven en druppels. Een skelet bevat de globale vorm van een waterstraal. Deze is meestal parabolisch, zie figuur 5.4. De grenslijnen moeten zo getekend worden dat de waterstraal smal is aan de basis, en breed uitloopt. De golven verbinden de grenslijnen en veranderen van positie om de stroming van het water te modelleren. Een golf kan getekend worden als een sinus curve die de twee grenslijnen verbindt. Zie figuur 5.5. Om het snelheidseffect te benadrukken kunnen aan de basis van de straal enkele rechte lijnen getekend worden. Individuele druppels worden binnen en buiten de straal getekend. Hun aantal neemt toe, naarmate ze dichter bij het einde van de straal komen. Het resultaat is weergegeven in figuur 5.6.

5.1.3

Rimpelingen

Als een object in het water ligt, worden rondom het object vaak rimpelingen getekend, zoals in figuur 5.7. Deze rimpelingen vertrekken aan het object, en verplaatsen zich naar buiten toe. Hoe verder van het object weg, hoe meer de rimpelingen splitsen. Het modelleren van deze rimpelingen bestaat uit 3 stappen: Stel een rimpelingen skelet op: Het skelet is de structurele vorm die gebruikt wordt om in een volgende fase de rimpelingen op te tekenen. De vorm van het skelet wordt bepaald door de ligging van het object in het water. Als het object een cylinder is, zullen de rimpelingen een ronde vorm aan nemen. Figuur 5.8 stelt het skelet voor. Het skelet beweegt in de tijd van binnen naar buiten.


Figuur 5.6: Een waterstraal gegenereerd door dit model

Figuur 5.7: Rimpelingen rondom een object

Figuur 5.8: De structurele vorm waarop de rimpelingen worden getekend

38


39

Figuur 5.9: Het resultaat van de hier beschreven methode

Figuur 5.10: Schemerend zonlicht teken de rimpelingen: De rimpelingen worden op het skelet getekend. Zoals in figuur 5.7 te zien, kunnen de randen voorgesteld worden als een aantal sinuscurves met viariabele amplitude en frequentie aan weerszijden van het skelet. De rimpelingen aan de buitenkant worden dunner getekend dan die aan de binnenkant. opsplitsen van de rimpelingen: De buitenste rimpels worden opgesplitst. Hoe verder de rimpelingen van het object, hoe smaller ze worden, en hoe groter de afstand tussen twee rimpelingen. In figuur 5.9 wordt het resultaat van deze methode weergegeven.

5.1.4

Andere watereffecten

In [Yu99] worden nog andere watereffecten besproken, zoals schemerend zonlicht, zie figuur 5.10, bewegende oppervlaktes zoals zeeën en meren, zie figuur 5.11 en reflecties, zie figuur 5.12 .


Figuur 5.11: Bewegende oppervlaktes

Figuur 5.12: Reflecties

40

Hoofdstuk 6

Keyframe Animation In dit hoofdstuk beschrijven we verschillende technieken om gasachtige fenomenen te controleren door gebruik te maken van keyframes. Een keyframe is een vooraf getekend frame, zie sectie 1.3.2. Het doel van een keyframe controle methode is dit keyframe op een bepaald moment zo goed mogelijk te benaderen. Een simulatie kan bestaan uit meerdere keyframes op verschillende tijdstippen.

6.1 6.1.1

Optimaliseren van windkrachten Inleiding

Een manier om rook te animeren met behulp van keyframes, is de methode beschreven in [TMPS03]. Deze methode is gebaseerd op de Stable Fluids methode [Sta99]. Zie sectie 2.3 voor meer uitleg over dit algoritme. Hier herhalen we dat een simulatie Q bestaat uit een array van toestanden: h

Q(q0 ) = q1T , . . . , qnT

iT

(6.1)

q0 is de begintoestand en q1 , q2 , . . . , qn worden met een Step-functie berekend uit de vorige toestand: qt = S(qt−1 ) (6.2) Elke toestand q bestaat uit een dichtheidsgrid ρ en een snelheidsgrid v. Op het snelheidsgrid werken krachten, die ervoor zorgen dat de rook beweegt. De krachten worden geoptimaliseerd zodat de simulatie op een bepaald tijdstip zo goed mogelijk overeenkomt met een keyframe, gedefiniëerd voor dat tijdstip.

41

HOOFDSTUK 6. KEYFRAME ANIMATION

42

Figuur 6.1: Links: windkrachten, rechts: vortexktrachten

6.1.2

Geparametriseerde krachten

Om controle uit te oefenen op de simulatie, kan de animator met de hand alle krachten definieren om zo, na veel iteraties, ervoor te zorgen dat de rook de gewenste vorm aan neemt. De invloed van krachten op rook is echter moeilijk voorspelbaar. Een kleine verandering in de krachten kan zorgen voor een grote verandering in de vorm van de rook. Het automatiseren van het definiëren van deze krachten zou heel wat werk besparen, en dat is precies wat deze methode doet. De animator specifiëert een aantal keyframes die de simulatie zo goed mogelijk moet benaderen. Een dichtheidskeyframe bestaat uit een dichtheidsgrid ρ∗t dat op tijd t zo goed mogelijk moet benaderd worden door het dichtheidsgrid van de simulatie, ρt . Een snelheidskeyframe bestaat uit een snelheidsgrid vt∗ dat op tijd t zo goed mogelijk moet benaderd worden door het snelheidsgrid van de simulatie, vt . Op deze manier kan de animator uitdrukken welke vorm de rook op een bepaald tijstip moet hebben en hoe de windkrachten zich op een bepaald tijdstip gedragen. Om de simulatie te controleren, definiëren we een aantal geparametriseerde krachten. Deze parameters kunnen bijvoorbeeld de positie, de richting en de grootte van de kracht bevatten. Deze parameters worden opgeslagen in een controlevector u. Elke gegeven waarde van u definieert een gegeven set van krachten op het snelheidsveld en definiëert dus een unieke simulatie Q(q0 , u). Deze methode gebruikt een optimalisatie techniek om Q(q0 , u) op te lossen naar u zodanig dat de gegeven set van keyframes het best benaderd worden.

6.1.3

Controle parameters

Er worden twee soorten krachten gebruikt om de simulatie te controleren: windkrachten en vortexkrachten, zie figuur 6.1. Een windkracht fω is een vector toegpast op het grid, en geschaleerd door een Gaussiaanse fall-off functie. In 2D, als w de windrichting is en c het


43

centrum, dan geldt: (fω )i,j = Gi,j w

(6.3)

2

met Gi,j = e−a|∆c| en ∆c = [i, j]T − c en a de breedte van de wind. Als controleparameters kunnen we nu de richting van de wind, w nemen, of het centrum c. Dat wil zeggen dat we de componenten van w of c toevoegen aan de controlevector u. Een vortexkracht fv wordt ook met een Gaussiaanse falloff functie gedefiniëerd: (fv )i,j = rGi,j R∆c "

(6.4)

#

0 −1 met R = , de matrix die zorgt voor een rotatie van π/2 en r de hoeveelheid rota1 0 tionele kracht. Hier kunnen we als controleparameters de spin r en het centrum c gebruiken.

6.1.4

Objective functie

Om Q(q0 , u) op te lossen naar u, hebben we een functie nodig die evalueert hoe goed de simulatie met een bepaalde waarde voor u de keyframes benadert. Deze functie noemen we ϕ, de objective functie. Ook willen we dat het systeem zo weinig mogelijk krachten gebruikt om deze keyframes te bereiken. De objective functie ϕ bestaat dus uit twee delen: • ϕk (Q(q0 , u)), het keyframe-matching gedeelte, waarin het verschil gemeten wordt tussen de gedefiniëerde keyframes en de simulatietoestanden. • ϕs (u), het smoothness gedeelte, dat de hoeveelheid kracht berekent die aan het systeem wordt toegevoegd. ϕ is dan de lineaire combinatie van deze twee termen: ϕ = ϕk + ϕs . Het doel is deze objective functie te minimaliseren voor u. Er zijn verschillende numerieke methodes beschikbaar om een functieminimalisatie uit te voeren. Hier gebruikt men een methode beschreven in [ZBLN97]. Deze methode heeft zowel ϕ als dϕ/du nodig. We onderzoeken nu wat ϕk en ϕs precies inhouden. ϕs meet hoeveel kracht er wordt toegevoegd aan de simulatie, dus: ϕs = ks

n X

|ft |2

(6.5)

t=0

met ks een schaleringsconstante, n het aantal tijdstappen en |x|2 = x · x de som van de gekwadrateerde waardes van elke gridcel. De afgeleide van ϕs (u) naar een willekeurige controleparameter uk is dan: n X dϕs dft = 2ks ft · (6.6) duk du k t=0


44

ϕk meet het verschil tussen het keyframe en de overeenkomstige toestand van de simulatie. Stel dat een dichtheidsgrid ρt op tijd t een overeenkomstig keyframe ρ∗t moet benaderen. De meest voor de hand liggende metriek is dan |ρt − ρ∗t |2 . Dit is echter niet voldoende voor deze methode. Als de rook in het keyframe en in de simulatietoestanden niet overlappen, blijft |ρt − ρ∗t |2 constant. Een oplossing hiervoor is om eerst zowel het keyframe als de simulatietoestand te blurren. Blurren is het verspreiden van de rook naar de aanliggende gridcellen. Een blurfactor wordt bijgehouden om aan te geven over hoeveel gridcellen de rook verspreid wordt. ϕk wordt dan: ϕk = kd

|B(ρt − ρ∗t )|2 + kv

X t∈Kd

X

|B(vt − vt∗ )|2

(6.7)

t∈Kv

met Kd en Kv de lijst van dichtheids- en snelheidskeyframes en kd en kv schaleringsconstantes. De afgeleide van ϕk naar een willekeurige controleparameter uk is dan: X dϕk dρt = 2kd B(ρt − ρ∗t ) · B duk duk t∈K

+ 2kv

d

X

B(vt − vt∗ ) · B

t∈Kv

dvt duk

(6.8)

In deze formule hebben we dρt /duk en dvt /duk gebruikt. Dus hebben we naast het dichtheidsgrid en het snelheidsgrid, ook de gradiënt, dit is de afgeleide hiervan naar elke controleparameter, nodig. Het dichtheidsgrid en het snelheidsgrid kunnen we rechtstreeks uit de simulatie halen. Hun afgeleides moeten we echter zelf berekenen.

6.1.5

Afgeleiden

Het berekenen van de afgeleiden Een simulatietoestand bestaat uit een dichtheidsgrid en een snelheidsgrid: q = (ρ, v)

(6.9)

We breiden de toestand q uit met zijn afgeleiden naar elke controleparameter, en noemen deze nieuwe toestand qˆ: dqt dqt dqt qˆt = (qt , , ,..., ) (6.10) du1 du2 dun Net als bij de simulatie, waarin qt berekend wordt door een Step-functie uit qt−1 , wordt qˆt ook berekend door een Step functie uit qˆt−1 : ˆ qt−1 ) qt−1 = S(ˆ qˆ0 = (q0 , 0, 0, . . . , 0) (6.11)


45

S bestaat uit een aantal operaties, zie sectie 2.3. Hier wordt de simulatie vereenvoudigd, en beschouwen we S als: S = M ◦ Aρ ◦ P ◦ D ◦ Av ◦ F (6.12) Met F het toevoegen van krachten op het snelheidsveld, Av de advectie van het snelheidsveld, D de diffusie van het snelehidsveld, P de projectie van het snelheidsveld, Aρ de advectie van het dichtheidsveld en M het behoud van massa van het dichtheidsveld. Voor elke operatie in S, moet zijn afgeleide naar u berekend worden. Dit gebeurt in parallel met de berekening van de operatie zelf.

Projectie en diffusie Projectie en diffusie zijn lineaire operatoren dus geldt: dP (v) = P duk

dv duk

dv dD (v) = D duk duk

(6.13) (6.14)

Advectie Advectie van een dichtheidsveld σ door een snelheidsveld v wordt gedaan door eerst door v te backtracen en dan σ te updaten met het backtraced punt. Dit kunnen we noteren als: A(v, σ, p0 ) = I(σ, ps ) pi = pi−1 − ∆tI(v, pi−1 ) (6.15) Met I(σ, p) de waarde van σ in het punt p, bekomen door interpolatie. In 2D is p = [px , py ]T en geldt voor I: I(σ, p) = (1 − α)(1 − β)σl,m + α(1 − β)σl+1,m + (1 − α)βσl,m+1 + αβσl+1,m+1 met l = bpx c m = bpy c α = px − l β = py − m

(6.16)


46

De afgeleide naar uk van deze stap wordt dan: dA (v, σ, p0 ) = duk dpi = duk

dI (σ, ps ) duk dpi−1 dI − ∆t (v, pi−1 ) duk duk (6.17)

dI/duk wordt dan: dI =I duk

dσ ,p + duk

∂I dpx ∂I dpy + ∂α duk ∂β duk

(6.18)

Behoud van massa De massa van de rook wordt behouden door volgende stap toe te passen: m 0 ρ = ρP ρ

(6.19)

met m de gewenste massa van de rook. De afgeleide naar uk hiervan is: 0 dρ dρ m m X dρ P −ρ P 2 = duk duk ρ ( ρ) duk

(6.20)

Krachten De krachten toegevoegd door de controlevector u werden besproken in sectie 6.1.3. Hier bespreken we hun afgeleiden naar uk . Bij windkrachten werd ofwel de richting w toegevoegd aan u, ofwel het centrum c. Als de richting w werd gebruikt, moeten we dus afleiden naar w en als c werd gebruikt, moeten we afleiden naar c, dus, voor windkrachten geldt:

dfω dw

= Gi,j

(6.21)

= 2aGi,j w(∆c)T

(6.22)

i,j

en

6.1.6

dfω dc

i,j

Uitbreiding

De hierboven beschreven methode is geschikt voor korte simulatie met een beperkt aantal krachten, maar is minder geschikt voor grote simulaties. Hoe meer krachten er gebruikt


47

Figuur 6.2: Rook splitst op in drie richtingen

Figuur 6.3: Het woord SMOKE wordt geschreven in rook worden, hoe langer het duurt om de objective functie te evalueren. Daarenboven moet voor elke kracht een afgeleide berekend worden. Grote simulaties met veel keyframes hebben ook een grotere kans om vast te lopen in lokale minima. Om deze problemen op te lossen, kan het probleem opgesplitst worden in verschillende kleine problemen, die elk lokaal opgelost moeten worden. Deze oplossingen gecombineerd, geven een ruw idee voor de globale oplossing.

6.1.7

Resultaten

In figuur 6.2 en figuur 6.3 worden enkele resultaten getoond van deze methode in [TMPS03]. Het eerste resultaat duurde 2 uur op een 2ghz pentium4. Het tweede resultaat duurde 2 tot 5 uur per letter.


6.2 6.2.1

48

Adjoint methode Inleiding

Deze methode, beschreven in [MTPS04], is voor het grootste gedeelte analoog aan de vorige methode. Het verschil tussenbeide is de manier waarop de gradiënt van de objective functie wordt berekend. Aan de basis van deze techniek ligt een verandering van variabelen om de gradiënt sneller te berekenen. Stel dat we een matrix A en vectoren g en c gegeven hebben en we willen het vectorproduct g T b berekenen zodat Ab = c, met b een onbekende vector. Een manier om dit op te lossen, is eerst b te berekenen uit Ab = c, en daarna g T b berekenen. Een andere manier is om een nieuwe vector s te introduceren en sT c te berekenen zodat AT s = g. Dan geldt dat sT c = g T b want: sT c = sT Ab = (AT s)T b = g T b

(6.23)

Stel nu dat de onbekende vector b en de bekende vector c matrixen B en C zijn, dan geldt nog steeds g T B = sT C. Om B te berekenen uit de linkerhelft, moeten we de vergelijking AB = C oplossen. Om s uit het rechter gedeelte te berekenen, moeten we de vergelijking AT s = g oplossen. Dit is een groot verschil. In plaats van een matrix te vinden, moeten we nu slechts één vector vinden. Dus als we een probleem tegenkomen waarin we g T B moeten berekenen en we kunnen het probleem zo formuleren dat sT C kan berekend worden, is dit zeker de moeite waard. Dit noemnt men de adjoint methode.

6.2.2

Berekenen van de gradi¨ ent

Zoals we in de vorige sectie hebben gezien, kan elke toestand berekend worden uit zijn vorige toestand met een Step functie. Deze Step functie bestaat zelf uit een aantal functies, zoals diffusie, advectie en projectie. In het algemene geval kan men dus van één toestand naar de andere overgaan, door een functie fi : qi+1 = fi (qi , u)

(6.24)

met elke fi een differentiëerbare functie, geparametriseerd door een controlevector u. We kunnen deze toestanden als één grote vector schrijven. Deze vector stelt dan de gehele simulatie voor: h iT Q = q1T , . . . , qnT (6.25) De functies fi kunnen we analoog schrijven als: h

F (Q, u) = f0 (q0 , u)T , . . . , fn−1 (qn−1 , u)T

iT

(6.26)

Dus wordt vergelijking 6.24: Q = F (Q, u)

(6.27)


49

De afgeleide hiervan naar u, die we later nog gaan nodig hebben is dan, volgens de kettingregel: dQ dF ∂F dQ ∂F du ∂F dQ ∂F = = + = + du du ∂Q du ∂u du ∂Q du ∂u

(6.28)

Stel nu dat we een objective functie ϕ(Q, u) hebben, die berekent hoe goed de simulatie Q een set van keyframe benadert als de controlevector u op Q wort toegepast. Dan is de afgeleide naar u hiervan, ook volgens de kettingregel: dϕ ∂ϕ dQ ∂ϕ = + du ∂Q du ∂u

(6.29)

In plaats van dQ/du rechtstreeks te berekenen, zoals we in de vorige sectie hebben gedaan, gebruiken we nu de adjoint methode om deze stap te ontwijken. Vergelijking 6.28 kunnen we herschrijven als: ∂F dQ ∂F I− (6.30) = ∂Q du ∂u en kunnen we zien als een voorwaarde op dQ/du. In het eerste deel van vergelijking 6.29 moeten we dus ∂ϕ dQ (6.31) ∂Q du berekenen zodat

I−

∂F ∂Q

dQ ∂F = du ∂u

(6.32)

Deze situatie is dezelfde als de situatie in sectie 6.2.1, waar we g T B moesten berekenen, zodat AB = C. Door dezelfde verandering van variabelen, kan men dit dus schrijven als, bereken : RT zodat

∂F I− ∂Q

∂F ∂u

T

R=

(6.33) ∂ϕ T ∂Q

(6.34)

Merk op dat ∂fi /∂qj = 0 als i 6= j. Net zoals Q een array van toestanden voorstelt, zo stelt ∂ϕ T R = r1 , . . . , rn een array van adjoint toestanden voor, met rn = ( ∂q ) en n

ri =

∂fi ∂qi

T

ri+1 +

∂ϕ ∂qi

T

(6.35)

Dus we moeten elke adjoint toestand uit zijn volgende toestand berekenen. De implementatie van dit algoritme is beschreven in [MTPS04].


50

Figuur 6.4: Een resultaat van de adjoint methode, met een keyframe in het midden (3e beeld)

6.2.3

Resultaten

In figuur 6.4 wordt een resultaaat getoond van deze methode in [MTPS04]. Dit resultaat duurde 2uur om te berekenen.

6.3

In-betweening techniek

In [FCR04] wordt een methode beschreven om een willekeurig gasachtig fenomeen op een nonphotorealistische manier te controleren. Deze methode maakt gebruik van zowel 2D als 3D technieken om de animator volledige controle te geven in 2D, en toch de 3D coherentie van een simulatie te behouden. Er wordt een onderscheid gemaakt tussen de 2D modelleringsfase en de 3D animatiefase. We bekijken eerst een algemene methode om te modelleren en animeren in 2D. Daarna passen we dit toe op gasachtige fenomenen.

6.3.1

Modelleren en animeren in gestructureerd 2D

In [FSER01] wordt een methode uitgelegd om, vertrekkende van 2D informatie, een 3D model op te stellen. Er zijn twee types transformaties mogelijk: Transformaties in een vlak parallel aan het tekenvlak (het XY vlak) en transformaties buiten het tekenvlak, zoals rotaties rondom de X- en Y- as. Dit laatste type zorgt voor problemen omdat informatie nodig is, die niet meteen beschikbaar is in de 2D tekening. Deze methode gebruikt 4 niveaus om dit probleem op te lossen. Op niveau 0 worden objecten gemodelleerd als primitieven, bijvoorbeeld curves, in 2D. Op niveau 1 worden keyframes gebruikt om 2.5D objecten te creëeren. Zie figuur 6.5. Deze keyframes zijn frames die door de animator gecreëerd worden en die de rotaties om de X- en Y-as beschrijven. Door interpolatie kan dan een nieuw beeld gerenderd worden dat in het bereik van deze keyframes ligt. Dit noemt men in-betweening. Niveau 2 implementeert 3D informatie door het gebruik van 3D skeletten om 3D objecten te benaderen. Niveau 3, ten slotte, biedt te mogelijkheid om highlevel tools te implementeren bovenop niveau 0, 1 of 2.


51

Figuur 6.5: Links de keyframes die door de animator gecreëerd worden. Rechts voorbeelden van frames die getekend kunnen worden uit deze keyframes

Figuur 6.6: Voorbeelden van tijdsafhankelijke animatiepaden en acceleratiecurves

6.3.2

Gasachtige fenomenen modelleren

Het gasachtig fenomeen wordt voorgesteld als een particle system. In deze methode wordt geen gebruik gemaakt van fysische wetten om deze particles te bewegen, maar tijd- en camerapositie-afhankelijke versies van het animatiepad en getekende acceleratiecurves voor de versnelling van de particles.De animator definiëert een animatiepad door een of meerdere strepen te tekenen. Tijd- en camerapositie-afhankelijke versies van het animatiepad kunnen getekend worden om meer overtuigende animaties te verkrijgen. Deze paden kunnen beschouwd worden als “keyframe” en ook zo gebruikt worden in de animatiefase. Elk 2D animatiepad wordt “opgeblazen” naar een 3D pad [DAC+ 03]. Acceleratiecurves definiëren hoe de particles versneld worden op hun weg langs het animatiepad, zie figuur 6.6. Om de rook, het vuur of het water zelf te tekenen, gebruiken we een rendering primitieve, zie ook sectie 4.2.1. Deze rendering primitieve kan variëren om een dynamischer effect te verkrijgen.

6.3.3

Gasachtige fenomenen animeren

We hebben nu de animatiepaden en de acceleratiecurves om een gasachtig fenomeen te modelleren. Het animatieproces verloopt als volgt: 1. Blaas het 2D animatiepad op naar een 3D traject.


52

Figuur 6.7: Een barbecue in cartoon-stijl 2. Voor elk frame, parse de positie, orientatie en andere informatie die gegeven is door de animator, met behulp van keyframes. 3. Deze informatie wordt gebruikt om een in-betweening 3D traject te maken en een inbetweening 2D acceleratiecurve. 4. 3D particles worden op dit traject geplaatst. Aan elke particle wordt een rendering primitieve toegekend. 5. Update de positie, oriëntatie, leeftijd, diepte en eventueel andere attributen van deze rendering primitieve aan de hand van het traject en de acceleratiecurve. 6. Met behulp van de diepte-informatie in de vorige stap, worden de rendering primitieven gesorteerd en van achter naar voor uitgetekend. 7. Deze rendering primitieven kunnen variëren, dus wordt voor elke rendering primitieve een 2D particle gecreëerd door het in-betweening proces, dat uiteindelijk getekend wordt op het scherm. In figuur 6.7 staat een voorbeeldanimatie.

6.4

Andere methodes

In [FL04] wordt een methode beschreven om rook te controleren door de Navier Stokes vergelijkingen aan te passen zodat de rook op een natuurlijke wijze evolueert naar een vooraf gedefiniëerde vorm. In [SY05] wordt de rook gecontroleerd door guiding objects te gebruiken. De rook transformeert van zijn initiële toestand naar de vorm van het guiding object. Door constraints op te leggen voor het snelheidsveld aan het oppervlak van de guiding objects, behoudt de rook een natuurlijke vorm.

Hoofdstuk 7

Implementatie Net als de literatuurstudie, bestaat ook de implementatie uit twee delen: Non-photorealistic rendering, waarin drie technieken ge¨ımplementeerd worden om rook en vuur non-photorealistisch weer te geven, en keyframe animation, waarin een keyframing methode ge¨ımplementeerd wordt. De implementatie is in C++ geprogrammeerd en er is gebruik gemaakt van Qt1 voor de user interface en openGL2 voor het renderen van de simulaties. De implementatie maakt gebruik van een open source framework3 , gebaseerd op de Navier-Stokes vergelijkingen, voor het simuleren van de rook en de weergave van de dichtheids- en snelheidsvelden.

7.1

Non-photorealistic rendering

We bespreken hier de implementatie van de drie technieken die ge¨ıntroduceerd werden in sectie 4.2.1, 4.2.2 en 6.3. Alle drie de methodes maken gebruik van een particle system. Er is dus allereerst een particle system ge¨ımplementeerd met volgende features: • Particles kunnen getraced worden doorheen het snelheidsveld; • Particles kunnen op random-posities worden toegevoegd waar de dichtheid hoog genoeg is; • Particles kunnen verwijderd worden; • Er kan een drempelwaarde ingesteld worden voor de dichtheid. De particles worden 1

http://www.trolltech.com/ http://www.opengl.org/ 3 http://www.copro.org/ 2

53

HOOFDSTUK 7. IMPLEMENTATIE

54

enkel getraced op posities met een dichtheid boven de drempelwaarde. Als een particle op een positie komt waar de dichtheid kleiner is dan de drempelwaarde, sterft de particle; • Particles kunnen vervormd worden door hun snelheid; • Particles kunnen voorgesteld worden met textures; • Er kan een drempelwaarde voor de diepte worden ingesteld. • Particles kunnen een bepaalde vaste grootte hebben of de grootte kan afhangen van de dichtheid op de positie van de particle. De mate waarin een particle afhangt van de dichtheid kan aangepast worden. Daarenboven kan men met een schaleringsfactor alle particles verkleinen of vergroten; • Particles kunnen een variabele kleur hebben, afhankelijk van de dichtheid op de positie van de particle.

7.1.1

Depth difference rendering

Zoals in sectie 4.2.1 beschreven, wordt dit algoritme in 2 stappen uitgevoerd: In een eerste stap worden de particles uitgetekend. In een tweede stap wordt de dieptebuffer onderzocht, en daar waar het verschil tussen twee pixels groter is dan een bepaalde drempelwaarde, worden de pixels zwart gekleurd. De grootte van deze drempelwaarde voor de diepte kan ingesteld worden. Het uitlezen van de dieptebuffer gebeurt in openGL door de glReadPixels() functie. Daarna wordt met glDrawPixels() op de juiste posities zwarte pixels getekend.

7.1.2

2D rendering

Zoals in sectie 4.2.2 wordt uitgelegd, wordt ook dit algoritme in 2 stappen uitgevoerd: Eerst wordt de buitenkant getekend, daarna wordt de binnenkant over de buitenkant getekend. Dit gebeurt door de particles niet in 3D uit te tekenen, maar te projecteren op het scherm. De gluProject() functie wordt gebruikt om aan de hand van de positie van de particles, hun schermpositie te bepalen. Particles kunnen ingedeeld worden in groepen en het aantal groepen kan aangepast worden door de gebruiker door de dieptewaarde te veranderen.

7.1.3

Vuur

Hierbij gaan we hetzelfde tewerk als bij het renderen van rook, maar we gebruiken andere textures, om het effect van vuur te bereiken. Deze keuze van textures is afhankelijk van welk non-photorealistisch effect men wil bereiken, zie [FCR04]. We gebruiken twee drempelwaardes voor de dichtheid. Zo wordt het vuur ingedeeld in drie zones. Aan elke zone kunnen we een andere texture, een andere kleur en een andere transparantie toekennen. De animator kan de drempelwaardes instellen en zo de zones indelen.


55

Figuur 7.1: Verandering van de dieptewaarde bij depth difference rendering

7.1.4

Resultaten

In figuur 7.1 wordt het instellen van de dieptewaarde bij depth difference rendering weergegeven. In figuur 7.1 wordt het instellen van de dieptewaarde bij 2d rendering weergegeven. In figuur 7.3 wordt het instellen van de grootte van de particles weergegeven. In figuur 7.4 wordt de mate waarin de particles afhangen van de dichtheid aangepast. In figuur 7.5 worden de particles vervormd onder invloed van hun snelheid. In figuur 7.7 tenslotte zijn drie voorbeelden weergegeven van het non-photorealistisch renderen van vuur. We gebruiken hierbij de textures van figuur 7.8. In de linkse figuur is een kleurovergang van wit naar geel in de binnenste zone en een kleurovergang van geel naar rood in de middelste en buitenste zone, afhankelijk van de dichtheid. De transparantie is overal afhankelijk van de dichtheid. In de middelste figuur is er voor alle zones een kleurovergang van geel naar rood. De linkse texture wordt gebruikt voor de binnenste en middelste zone. Voor de buitenste zone wordt de rechtste texture gebruikt. In de rechtse figuur wordt enkel de linkse texture gebruikt.

7.1.5

Conclusie

Bovenstaande resultaten tonen een implementatie van beide methodes. De resultaten zijn zeer vergelijkbaar met de resultaten van de papers zelf.

7.2

Keyframe animation

In deze sectie wordt de implementatie van de keyframing methode, beschreven in sectie 6.1. Om deze methode te implementeren, werd het framework uitgebreid met volgende onderdelen:


Figuur 7.2: Verandering van de dieptewaarde bij 2D rendering

Figuur 7.3: Het veranderen van de grootte van de particles

56


57

Figuur 7.4: De mate waarin de grootte afhangt van de dichtheid veranderen

Figuur 7.5: Het veranderen van de vorm van een particle afhankelijk van zijn snelheid en het veranderen van de kleur van een particle afhankelijk van de dichteid op zijn positie


Figuur 7.6: Het toepassen van 2 verschillende textures op de rook

Figuur 7.7: Non-photorealistische weergave van vuur

Figuur 7.8: De twee textures die we gebruiken om vuur te renderen

58


59

Een controlevector u waarin de krachten worden opgeslagen die de simulatie controleren Keyframes die de waarde definiëren van het dichtheidsgrid of snelheidsgrid op een bepaald tijdstip t. Objective functie, en zijn afgeleides, die berekent hoe goed de huidige simulatie voldoet aan de keyframes Afgeleides van het dichtheids- en snelheidsveld die nodig zijn om de afgeleide van de objective functie te berekenen. Een minimalisatiefunctie die een minimum berekent voor de objective functie. Het implementeren van de controlevector en de keyframes is voor de hand liggend. Er wordt gebruikt gemaakt van stl::vector klasses om een lijst van krachten en een lijst van keyframes op te slaan. Voor de krachten en keyframes zelf worden klasses gemaakt. Voor de objective functie werd het framework uitgebreid met blur-functie en een functie om twee grids met elkaar te vermenigvuldigen.

7.2.1

Afgeleides van het dichtheids- en snelheidsveld

De afgeleides van het dichtheids- en snelheidsveld werden als volgt ge¨ımplementeerd:

Projectie en diffusie Aangezien de afgeleide van de projectiestap gelijk is aan de projectiestap van de afgeleide (zie sectie 6.1), hoeft voor deze stap geen extra code geschreven te worden. Idem voor de diffusie stap.

Advectie We herhalen hier de advectiestap: A(v, σ, p0 ) = I(σ, ps ) pi = pi−1 − ∂tI(v, pi−1 ) (7.1) en haar afgeleide: dA (v, σ, p0 ) = duk dpi = duk

dI (σ, ps ) duk dpi−1 dI − ∆t (v, pi−1 ) duk duk


60

In 3D geeft dit voor de interpolatiefunctie I: (1 − α)(1 − β)(1 − γ)σl,m,n + α(1 − β)(1 − γ)σl+1,m,n +

I(σ, p) =

(1 − α)β(1 − γ)σl,m+1,n + αβ(1 − γ)σl+1,m+1,n + (1 − α)(1 − β)γσl,m,n+1 + α(1 − β)γσl+1,m,n+1 + (1 − α)βγσl,m+1,n+1 + αβγσl+1,m+1,n+1

(7.2)

De afgeleide van I naar uk wordt dan: dI =I duk

dσ ,p + duk

∂I dpx ∂I dpy ∂I dpz + + ∂α duk ∂β duk ∂γ duk

(7.3)

met ∂I/∂α (de afgeleides naar β en γ zijn analoog): ∂I = ∂α

−(1 − β)(1 − γ)σl,m,n + (1 − β)(1 − γ)σl+1,m,n −β(1 − γ)σl,m+1,n + β(1 − γ)σl+1,m+1,n −(1 − β)γσl,m,n+1 + (1 − β)γσl+1,m,n+1 −βγσl,m+1,n+1 + βγσl+1,m+1,n+1

(7.4)

Als we nu nog dp/duk berekenen, hebben we alle componenten om dI/duk te berekenen, en dus ook dA/duk . dp/duk halen we uit formule 7.2. We hebben dps /duk nodig. Als we een éénfasige backtrace doen, is s = 1. Hierbij geldt dat dp0 /duk = 0 want het backtracen begint in p0 dus geldt: dps duk

dp1 duk dp0 dI = − ∆t (v, p0 ) duk duk dv = −∆t I , p0 + duk dv = −∆tI , p0 duk =

∂I dpx0 ∂I dpy0 ∂I dpz0 + + ∂α duk ∂β duk ∂γ duk

!!

Behoud van massa De afgeleide van deze stap is als volgt: 0 dρ dρ m m X dρ P −ρ P 2 = duk duk ρ ( ρ) duk

(7.5)

Het vereist een functie om de som van alle gridcellen van een densitygrid te berekenen. Als we dit hebben, kunnen we de formule invullen.


61

Krachten Voor deze implementatie hebben we windkrachten ge¨ımplementeerd die afgeleid kunnen worden naar hun richting: dfω = Gi,j (7.6) dw i,j Een richting w stellen we in 3D voor als een vector (x, y, z). Aangezien elke component van deze vector een element is van de controlevector, moeten we deze stap afleiden naar elke component: dfω = (Gi,j,k , 0, 0); dx i,j,k dfω = (0, Gi,j,k , 0); dy i,j,k dfω = (0, 0, Gi,j,k ); dz i,j,k

(7.7)

Met deze formules kan men een afgeleide krachtveld berekenen, en dit veld toevoegen aan het snelheidsveld.

7.2.2

Minimalisatiefunctie

Als minimalisatiefunctie wordt een implementatie4 gebruikt van de optimalisatiemethode, beschreven in [ZBLN97]. Deze implementatie is geschreven in Fortran en werd met behulp van f2c5 omgezet naar C code.

7.2.3

Resultaten

Het implementeren leverde enige problemen op. De minimalisatiefunctie heeft regelmatig problemen om een minimum te vinden. Dit kan verschillende oorzaken hebben: • De functie is inherent te complex om vlot een minimum te vinden. • De objective functie wordt niet correct berekend. • De afgeleides van de objective functie worden niet correct berekend. Aangezien er reeds goede resultaten werden bereikt met deze techniek in [TMPS03], is de eerste mogelijkheid uitgesloten. De objective functie zelf lijkt ook correct berekend te worden. 4 5

http://www.ece.northwestern.edu/ ciyou/code/Lbfgsb.2.4.tar.gz http://www.netlib.org/f2c/


62

Als het verschil tussen een keyframe en het bijbehorende frame van de simulatie visueel klein is, is de objective functie ook klein. Als er een groot verschil is, is de objective functie ook groot. Dan blijft er nog één mogelijkheid over: de afgeleides van de objective functie worden niet correct berekend. Om deze te berekenen, wordt gebruik gemaakt van de afgeleides van elke simulatiestap. Het is mogelijk dat in één van deze afgeleide simulatiestappen een fout zit. We bespreken hier enkele voorbeelden van minimalisaties die een acceptabel resultaat geven, dit wil zeggen, dat de simulatie op een bepaald tijdstip een keyframe visueel goed benadert, en van minimalisaties die de mist in gaan. De testen werden uitgevoerd op een AMD64 Athlon 3500+ met 2gb RAM geheugen en een WindowsXP besturingssysteem.

Simpel voorbeeld We beginnen met een simpel voorbeeld: We gebruiken een 10x10x10 grid en we voegen in het midden van het grid, beneden rook toe. Als keyframe nemen we een pilaar van rook. Dus, de rook wordt toegevoegd op positie (5, 1, 5), zie figuur 7.9, en we willen dat op tijdstip t = 15de rook verspreid wordt over (5, 1, 5), (5, 2, 5), (5, 3, 5), (5, 4, 5), zie figuur 7.10. We beginnen met een blurfactor van 3. Zoals in sectie 6.1 beschreven, verminderen we de blurfactor telkens een oplossing wordt gevonden. Deze oplossing wordt dan gebruikt als initële gok voor de nieuwe minimalisatie. We plaatsen een kracht op tijdstip t = 0 op positie (5, 1, 5). De positie van een kracht wordt voorgesteld door een groene bol. Zijn richting door een lijn aan de bol te bevestigen. We verwachten intu¨ıtief een resultaat in de richting van (0, 1, 0), een simpele kracht recht omhoog. We geven echter een “domme” initiële gok van (0, 0, 0). In minder dan 3 minuten, wordt een acceptabel minimum gevonden: (1.525764, 352.406179, 1.525702), een resultaat dat we verwacht hadden. Het resultaat wordt visueel weergegeven in figuur 7.11. We kunnen het bereik van de oplossing beperken in de minimalisatiefunctie. Zo kunnen we ervoor zorgen dat de simulatie geen ongeldige waardes oplevert als er bijvoorbeeld een kracht van (0, 106 , 0) wordt toegevoegd. Als we het bereik beperken treedt er een eigenaardigheid op. Stel dat we het bereik beperken tot [−2·103 , 2·103 ]. Hoewel de beperking geen invloed heeft op onze oplossing, heeft dit toch invloed op het resultaat. De minimalisatie duurde nu 3min54sec en er werd een ander minimum gevonden: (−122.431314, 678.329757, −122.431120), zie figuur 7.12. Hoewel deze oplossing misschien nog aanvaardbaar zou zijn, is ze toch beduidend minder goed dan de vorige. Aangezien de unconstrained en de constrained methode een ander algoritme gebruiken, kan dit wijzen op fouten in de berekening van de objective functie of van zijn afgeleides.


Figuur 7.9: De begintoestand

Figuur 7.10: Het keyframe

63


64

Figuur 7.11: Een goede oplossing voor de minimalisatiefunctie

Figuur 7.12: De minimalisatiefunctie geeft een andere oplossing als het bereik beperkt wordt.


65

Figuur 7.13: Het keyframe Meerdere krachten In deze test plaatsen we op positie (5, 5, 5) een hoeveelheid rook, die op tijdstip t = 20 een keyframe moet benaderen zoals in figuur 7.13 afgebeeld. Deze keer voegen we vier krachten toe, telkens op positie (5, 5, 5), op tijdstip t = 0, t = 5, t = 10 en t = 15. De extra moeilijkheid die hier bij komt kijken is dat de rook zowel naar boven als naar beneden moet gestuwd worden. De minimalisatiefunctie had 8min10sec nodig en gaf de oplossing 187.234974, zie ook figuur 7.14, met als coördinaten voor de richtingen: tijdstip 0 5 10 15

x-richting -64.545252 -22.727240 159.355220 -69.081805

y-richting -233.460585 -709.378616 -176.459957 1393.464773

z-richting -64.527102 -22.718354 159.377483 -69.068710

Wat hierbij opvalt is dat de twee krachten op tijdstip 0 en 10 niet echt bijdragen tot de oplossing, die, hoewel zeker niet optimaal, toch nog acceptabel is. We merken dat de totale krachten vrij groot zijn, en we vervijfvoudigen de invloed van de krachtgrootte op de objective functie door de schaleringsconstante van de smoothness term te vervijfvoudigen. Het minimaliseren duurde 15min15sec en geeft 151.590137 als minimum met als coördinaten voor de richtingen:


66

Figuur 7.14: Een acceptabele oplossing voor de minimalisatiefunctie

tijdstip 0 5 10 15

x-richting -13.319067 -15.013572 6.720342 94.950999

y-richting -586.367435 36.017635 307.330508 857.539032

z-richting -12.574894 -13.619883 9.058424 95.026785

Er werd een lager minimum gevonden, hoewel de smoothness term vervijfvoudigd is. Visueel is het resulaat ook beter, zie figuur 7.15. Daarom verdubbelen we nogmaals de smoothness term. Hierbij wordt echter geen goed minimum meer gevonden omdat het toevoegen van krachten te hard wordt afgestraft, zie figuur 7.16. Dit duurde slechts 8min15sec. Het gevonden minimum is 391.057465 met als coördinaten voor de richtingen: tijdstip 0 5 10 15

x-richting -36.954969 -12.589990 9.532178 39.261218

y-richting -47.656852 -74.853330 -70.653494 -4.355632

z-richting -36.978038 -12.609198 9.518523 39.253151


67

Figuur 7.15: Het resultaat behaald door de schaleringsconstante van de smoothness term te vervijfvoudigen

Figuur 7.16: Het resultaat behaald door de schaleringsconstante van de smoothness term te vertienvoudigen


68

Figuur 7.17: Het keyframe Meerdere keyframes In deze test plaatsen we op positie (5, 5, 5) een hoeveelheid rook, die op tijdstip t = 11 een keyframe moet benaderen zoals in figuur 7.13 afgebeeld en op tijdstip t = 20 zoals in figuur 7.17. We voegen weer vier krachten toe, telkens op positie (5, 5, 5), op tijdstip t = 0, t = 5, t = 10 en t = 15. Deze keer moet de rook in 4 richtingen gestuwd worden. We vervijfvoudigen weer de smoothness term omdat het in de vorige test ook betere resultaten gaf. Na 7min41sec werd een minimum gevonden van 533.230241 met als coördinaten voor de richtingen: tijdstip 0 5 10 15

x-richting -9.284837 33.459164 -65.641274 -171.395878

y-richting -77.775165 -3.752282 133.477103 24.756800

z-richting -7.243552 11.066524 -17.322971 -75.089787

Dit is geen voldoende resultaat dus werd de schaleringsconstante voor de smoothness term weer gedeeld door 5. Ook dit gaf geen voldoende resultaat, een minimum van 371.056549. Dit is weliswaar minder dan het vorige minimum maar aangezien de smoothness term minder


69

Figuur 7.18: Het resultaat op tijdstip t=20. Dit komt duidelijk niet overeen met het keyframe zwaar weegt, zal de objective functie ook lager zijn. Het resultaat was visueel niet merkelijk beter, zie figuur 7.19. De coördinaten voor de richtingen zijn: tijdstip 0 5 10 15

x-richting -3.194490 -31.681307 230.888643 -369.692641

y-richting -6.368553 -30.333063 244.557106 342.317264

z-richting 10.767343 -38.499846 -70.280735 326.728162

Ook het vermeerderen van het aantal krachten, of het verminderen van het aantal keyframes leverde geen betere resultaten op.

7.2.4

Conclusie

Bepaalde, simpele simulaties kunnen gecontroleerd worden. Resultaten als in [TMPS03] werden echter niet behaald. De oorzaak hiervan is niet geheel duidelijk. Het minimaliseren vergt veel fijnafstemming van variabelen, zoals de schaleringsconstanten en de krachten (positie, tijdstip, aantal). Als het constrained algoritme wordt gebruikt, krijgen we nog ander resultaten. Daarenboven waren dit bijzonder simpele testcases waarin de optimale oplossing beter


70

Figuur 7.19: Het resultaat op tijdstip t=20. Dit komt weer niet overeen met het keyframe door een mensenhand kan worden ingevuld. Het lijkt erop dat het evalueren van de objective functie correct gebeurt. Als het verschil tussen een keyframe en het bijbehorende frame van de simulatie visueel klein is, is de objective functie ook klein. Als er een groot verschil is, is de objective functie ook groot. Daarom ligt de oorzaak waarschijnlijk bij het evalueren van de afgeleides van de objective functie. Hoewel deze berekeningen verschillende keren zijn nagekeken, door verschillende personen, op zowel redeneringsfouten, als onopvallende bugs, is het niet gelukt een fout te vinden.

Hoofdstuk 8

Conclusie In deze thesis werden gasachtige fenomenen bestudeerd. Er werden verschillende methodes, zoals particle systemen, cellulaire automaten en een numerieke methode, besproken om deze gasachtige fenomenen te simuleren op een computer. Vervolgens werd besproken hoe men gasachtige fenomenen non-photorealistisch kan weergeven. Hierbij kwamen zowel physics-based methodes als procedurele methodes, gebaseerd op traditionele tekeningen, aan bod. Beide type methodes hebben duidelijke overeenkomsten maar de physics based methode blijkt krachtiger te zijn omdat het meer algemene types van gasachtige fenomenen aan kan. De procedurele methodes blijven meestal beperkt tot speciale gevallen. Vervolgens werden technieken besproken om gasachtige fenomenen te controleren aan de hand van keyframes. Er werd hierbij zowel gekeken naar een indirecte als een directe methode. De indirecte methode controleert het gasachtig fenomeen door de onderliggende krachten, die de vorm van het gasachtig fenomeen bepalen, te optimaliseren. De directe methode laat de animator toe rechtstreeks de vorm en de animatie van het gasachtig fenomeen te bepalen. Er werden technieken ge¨ımplementeerd om rook en vuur non photorealistisch weer te geven en een techniek om rook te controleren aan de hand van keyframes. Hierbij werden goede resultaten behaald in het non photorealistisch renderen. Het keyframing gedeelte zorgde echter voor problemen. Hoewel enkele simpele animaties kunnen gecontroleerd worden, faalt de implementatie in het controleren van de andere animaties. Om een animatie te controleren moet een bepaalde functie geminimaliseerd worden. De oorzaak van het falen moet waarschijnlijk gezocht worden in de berekening van de gradiënt van deze functie. Als uitbreiding op deze thesis kan men in de eerste plaats de implementatie van het keyframing gedeelte grondig doorlichten en onderzoeken welke fout precies gemaakt wordt. Verder kan men, naast rook, ook de keyframe animatie van water implementeren. Op het gebied van non photorealistisch renderen kan men de Self-shadowing methode en de procedurele methodes om water weer te geven, implementeren. Ook kan men een complete tool creeëren waardoor de animator zelf textures kan ontwerpen en waardoor alle parameters van de animatie ingesteld kunnen worden door de animator. 71

Bibliografie [DAC+ 03]

James Davis, Maneesh Agrawala, Erika Chuang, Zoran Popovic, and David Salesin. A sketching interface for articulated figure animation. In SCA ’03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, pages 320–328, Aire-la-Ville, Switzerland, Switzerland, 2003. Eurographics Association.

[DKY+ 00] Yoshinori Dobashi, Kazufumi Kaneda, Hideo Yamashita, Tsuyoshi Okita, and Tomoyuki Nishita. A simple, efficient method for realistic animation of clouds. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 19–28, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co. [DS00]

Oliver Deussen and Thomas Strothotte. Computer-generated pen-and-ink illustration of trees. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 13–18, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.

[FCR04]

Fabian Di Fiore, Johan Claes, and Frank Van Reeth. A framework for user control on stylized animation of gaseous phenomena. In the Computer Animation and Social Agents Conference (CASA2004). Computer Graphics Society (CGS), 2004.

[FHR03]

Fabian Di Fiore, William Van Haevre, and Frank Van Reeth. Rendering artistic and believable trees for cartoon animation. In Proceedings of Computer Graphics International (CGI2003), pages 144–151, July 2003.

[FL04]

Raanan Fattal and Dani Lischinski. Target-driven smoke animation. ACM Trans. Graph., 23(3):441–448, 2004.

[FM96]

Nick Foster and Dimitri Metaxas. Realistic animation of liquids. Graph. Models Image Process., 58(5):471–483, 1996.

[FSER01]

Fabian Di Fiore, Philip Schaeken, Koen Elens, and Frank Van Reeth. Automatic in-betweening in computer assited animation by exploiting 2.5d modelling techniques. In Proceedings of Computer Animation (CA2001), pages 192–200, November 2001. 72

BIBLIOGRAFIE

73

[HJO+ 01]

Aaron Hertzmann, Charles E. Jacobs, Nuria Oliver, Brian Curless, and David H. Salesin. Image analogies. In SIGGRAPH ’01: Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 327–340, New York, NY, USA, 2001. ACM Press.

[Jen01]

Henrik Wann Jensen. Realistic image synthesis using photon mapping. A. K. Peters, Ltd., Natick, MA, USA, 2001.

[LF02]

Arnauld Lamorlette and Nick Foster. Structural modeling of flames for a production environment. In SIGGRAPH ’02: Proceedings of the 29th annual conference on Computer graphics and interactive techniques, pages 729–735, New York, NY, USA, 2002. ACM Press.

[MCG03]

Matthias M¨ uller, David Charypar, and Markus Gross. Particle-based fluid simulation for interactive applications. In SCA ’03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, pages 154–159, Aire-la-Ville, Switzerland, Switzerland, 2003. Eurographics Association.

[MFH04]

Morgan McGuire, Andi Fein, and Colin Hartnett. Real-time cartoon rendering of smoke. In Proceedings of the 31st annual conference on Computer graphics and interactive techniques, 2004.

[MP89]

Gavin Miller and Andrew Pearce. Globular dynamics: a connected particle system for animating viscous fluids. Computer Graphics Forum, 13(3):305–309, 1989.

[MTPS04] Antoine McNamara, Adrien Treuille, Zoran Popovic, and Jos Stam. Fluid control using the adjoint method. ACM Trans. Graph., 23(3):449–456, 2004. [NFJ02]

Duc Quang Nguyen, Ronald Fedkiw, and Henrik Wann Jensen. Physically based modeling and animation of fire. ACM Trans. Graph., 21(3):721–728, 2002.

[Par01]

Rick Parent. Computer animation: algorithms and techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001.

[Ree83]

W. T. Reeves. Particle systems, a technique for modeling a class of fuzzy objects. ACM Trans. Graph., 2(2):91–108, 1983.

[SMC04]

Andrew Selle, Alex Mohr, and Stephen Chenney. Cartoon rendering of smoke animations. In NPAR ’04: Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, pages 57–60, New York, NY, USA, 2004. ACM Press.

[Sta99]

Jos Stam. Stable fluids. In SIGGRAPH ’99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques, pages 121–128, New York, NY, USA, 1999. ACM Press/Addison-Wesley Publishing Co.

BIBLIOGRAFIE

74

[Sut64]

Ivan E. Sutherland. Sketch pad a man-machine graphical communication system. In DAC ’64: Proceedings of the SHARE design automation workshop, pages 6.329–6.346, New York, NY, USA, 1964. ACM Press.

[SY05]

Lin Shi and Yizhou Yu. Controllable smoke animation with guiding objects. ACM Trans. Graph., 24(1):140–164, 2005.

[TMPS03] Adrien Treuille, Antoine McNamara, Zoran Popovic, and Jos Stam. Keyframe control of smoke simulations. ACM Trans. Graph., 22(3):716–723, 2003. [WKM98]

R. Wcislo, J. Kitowski, and J. Mo’sci’nski. Cellular automaton as a fast tool for animation of liquid in multi-object scenes, 1998.

[WLMK04] Xiaoming Wei, Wei Li, Klaus Mueller, and Arie Kaufman. The lattice-boltzmann method for gaseous phenomena. IEEE Transactions on Visualization and Computer Graphics, 10(2):164–176, 2004. [Yu99]

Jinhui Yu. Stylised ProceduralAnimation. PhD thesis, University of Glasgow, Scotland, 1999.

[ZBLN97]

Ciyou Zhu, Richard H. Byrd, Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization. ACM Trans. Math. Softw., 23(4):550–560, 1997.

Non-photorealistic rendering and keyframe animation of gaseous phenomena

Recommend Documents