Stable Fluids - Dynamic Graphics Project

1 Stable FluidsJosStam AliaswavefrontAbstractBuildinganimationt oolsforfluid-like motionsis animportantandchallengingproblemwithmany ,unlike key frameorpro-ceduralbasedtechniques,permit ananimatortoalmosteffortlesslycreateinte resting,swirlingfluid-like , , it wasbelievedthatphysicalfluidmodelswereto oexpensive to allow thefactthatpreviousmodelsusedunstablesch emestosolve thephys-icalequationsgoverninga , forthefirsttime,weproposeanunconditional lystablemodelwhichstillproducescomplex fluid -like ,ourmethodis largertimestepsandthereforeachieve have usedourmodelinconjuctionwithadvectingsol idtexturestocreatemanyfluid-like [ComputerGraphics]:Three-DimensionalGrap hicsandRealism AnimationKeywords:animationoffluids,Navi er-Stokes,stablesolvers,im-plicitellipti cPDEsolvers,interactive modeling,gaseousphenom-ena,advectedtextu res1 IntroductionOneofthemostintriguingproble msincomputergraphicsisthesimulationofflu id-like behavior.

2 Agoodfluidsolverisofgreatimportanceinman y a highdemandtoconvincinglymimictheappearan ceandbehavioroffluidssuchassmoke, ,many texturesresultfromfluid-like pro-cesses, ,ofcourse, consensusamongscientiststhattheNavier-St okesequationsarea Aliaswavefront,1218 ThirdAve, 8thFloor, Seattle,WA beenpublishedinvariousareasonhowtocomput etheseequationsnumerically. Whichsolvertouseinpracticede-pendslargel yontheproblemat safety, performance, (shape)oftheflow is ofsecondaryimportancein ,ontheotherhand,theshapeandthebehav-ioro fthefluidareofprimaryinterest,whilephysi calaccuracy ,forcomputergraphics,shouldideallyprovid ea userwitha toolthatenablesherto achieve fluid -like effectsin , , [15, 17]orsimplegeometriessuchasleaves[23].Th ecomplexityoftheflowswasgreatlyimprovedw iththeintroductionofrandomtur-bulences[1 6,20].Theseturbulencesaremassconservinga nd,therefore, ,whichisidealformotion texturemapping [19].

3 Flowsbuiltupfroma superpositionofflowprimitivesallhave thedisadvantagethatthey vortex methodcoupledwitha Poissonsolvertocre-atetwo-dimensionalani mationsoffluids[24,8].Later, two-dimensionalsimulationoftheNavier-Sto kesequations[2].Theirmethodunlike [12].Thesimplificationsdonot,however, , FosterandMetaxasclearlyshowtheadvantages ofus-ingthefullthree-dimensionalNavier-S tokesequationsincreatingfluid-like animations[7]. Many effectswhicharehardto key framemanuallysuchasswirlingmotionandflow spastobjectsareob-tainedautomatically. Theiralgorithmis basedmainlyontheworkofHarlow andWelchin computationalfluiddynamics,whichdatesbac kto1965[11].Sincethenmany othertechniqueswhichFos-terandMetaxascou ldhave usedhave ,theirmodelhastheadvantageofbeingsimplet ocode,sinceit isbasedona finitedifferencingoftheNavier-Stokesequa tionsandanexplicittimesolver. Similarsolversandtheirsourcecodearealsoa vailablefromthebookofGriebelet al.

4 [9].Themainprob-lemwithexplicitsolversis blow-up andthereforehave Ideally, a usershouldbeabletointeractinreal-timewit ha fluidsolverwithouthavingtoworryaboutposs ible blow ups .Inthispaper, forthefirsttime,weproposea veryeasytoimplementandallowsa usertointeractinreal-timewiththree-dimen sionalfluidsona obtaina stablesolverwedepartfromFosterandMetaxas ,weusebothLagrangianandimplicitmethodsto solve ,sinceit ,it suffersfromtoomuch numericaldissipation , , computergraphicalappli-cation,ontheother hand,thisis notsobad,especiallyin aninterac-tive systemwheretheflow is keptalive ,a flow whichdoesnotdampenat employ oursolvertoupdateboththeflowandthemotion ofdensitieswithintheflow. To furtherincreasethecomplexityofouranimati onsweadvecttextureco-ordinatesalongwitht hedensity[13].Inthismannerweareabletosyn thesizehighlydetailed wispy believe thatthecombinationofphysics-basedfluidso lversandsolidtexturesisthemostpromisingm ethodofachievinghighlycomplex Sinceit reliesonsophisticatedmathematicaltechniq ues,it iswrittenina implementoursolver canskipSection2 , isdevotedtoseveralapplicationsthatdemons tratethepowerofournewsolver.

5 Finally, inSection5 keepthiswithintheconfinesofa shortpaper, wehave decidednottoincludea tutorial-type sectiononfluiddynamics,sincetherearemany a backgroundinfluiddynamicsandwhowishtoful lyunder-standthemethodinthispapershouldt hereforeconsultsucha [3].Readerswithanengineeringbentontheoth erhandcanconsultthedidacticbookbyAbbott[ 1].Also,FosterandMetaxas paperdoesa goodjobofintroducingtheconceptsfromfluid dynamicsto A fluidwhoseden-sityandtemperaturearenearl yconstantis describedbya velocityfield anda pressurefield . willdenotethespatialcoordinateby , whichfortwo-dimensionalfluidsis andthree-dimensionalfluidsisequalto . We have decidednottospecializeourresultsfora , thentheevolutionofthesequantitiesovertim eis givenbytheNavier-Stokesequations[3]: (1) "!$# &% !(') (2)where#is thekinematicviscosityofthefluid, is itsdensityand'is is a vec-torequationforthethree(two intwo-dimensions) denotesa dotproductbetweenvec-tors,whilethesymbol , * ,+ ,+ intwo-dimensionsand - ,+ ,+ ,+ have alsousedtheshorthandnotation %.

6 TheNavier-Stokesequationsareobtainedbyim posingthatthefluidconservesbothmass( )andmomentum( ).We referthereadertoany typesofboundaryconditionswhichareuse-ful in (/ 10 32).Inthiscasetherearenowalls,justa ,they ,theseboundaryconditionsleadtoaveryelega ntimplementationthatusesthefastFouriertr ansformasshownbelow. Thesecondtypeofboundaryconditionthatweco n-sideris whenthefluidliesin someboundeddomain4. Inthatcase,theboundaryconditionsaregiven bya function 65definedontheboundary workforagooddiscussionoftheseboundarycon ditionsinthecaseofa hotfluid[7]. Inany case,theboundaryconditionsshouldbesuchth atthenormalcomponentofthevelocityfieldis zeroat theboundary; brieflyoutlinethestepsthatleadtothatequa tion,sinceit followChorinandMarsden s treatmentofthesubject( , [3]).Amathematicalresult,knownastheHelmh oltz-Hodge Decomposition, statesthatany vectorfield7canuniquelybedecomposedintot heform:78 ! "9 (3)where haszerodivergence: : ; and9is a massconservingfieldanda <whichprojectsany vectorfield7ontoitsdivergencefreepart =<>7.

7 Theoperatoris by : 78 &%39@?(4)Thisis a Poissonequationforthescalarfield9withthe NeumannboundaryconditionA BADC E on 4. A solutiontothisequationisusedtocomputethe projection : <>78 F7G "9@?If weobtaina singleequationforthevelocity: < HI !$# &% !J'DKL (5)wherewehave usedthefactthat< and< M E . Thisisourfundamentalequationfromwhichwew illdevelopa stablefluidsolver. w01w2w3w4wwuqu= :Onesimulationstepofoursolveris (x,s)p(x, t)s0 tFigure2:To solve fortheadvectionpart, isthereforethevelocitythattheparticlehad a time agoattheoldlocation 6 . issolvedfromaninitialstate 6 I ) bymarchingthroughtimewitha timestep . Letusassumethatthefieldhasbeenresolvedat a time andthatwewishtocomputethefieldat alatertime ! . We resolve overthetimespan startfromthesolution7 L 6 I oftheprevioustimestepandthensequentially resolve , followedbya :7 7 ! #" $ 7% %&(' ) $ 7+*) , .- #" 7+/. ?Thesolutionat time ! is thengivenbythelastvelocityfield: 6 !

8 0 F7+/.. A simulationis now explainhow eachstepis is theadditionoftheexternalforce'.If weassumethattheforcedoesnotvaryconsidera blyduringthetimestep,then7 6 F7 !1 ' 6 I is a goodapproximationoftheeffectoftheforceon thefieldoverthetimestep . Inaninteractive systemthisis a goodapproxi-mation,sinceforcesareonlyapp liedat (orconvec-tion) .ThistermmakestheNavier-Stokesequationsn on-linear. 023 54+76 6, where ,forsmallseparationsand/orlargevelocitie s,verysmalltimestepshave ,weusea to-tallydifferentapproachwhichresultsina nunconditionallystablesolver. Nomatterhowbigthetimestepis,oursimulatio nswillnever blow up .Ourmethodis basedona techniquetosolve ofcrucialimportanceinobtainingourstables olver, ,however, canbeunderstoodintuitively. ,to obtainthevelocityat a point at thenew time .! ,webacktracethepoint throughthevelocityfield78 overa time . Thisdefinesa path 6 !9 correspondingtoa is thensettothevelocitythattheparticle,nowa t , hadatitspreviouslocationa time ago:7% 6 F7 6 I ?

9 Figure2 ,fromtheabove equationweobserve , a particletraceranda linearinterpolator(seenextSection).Thism ethodis thereforebothstableandsimpletoimplement, two highlydesirablepropertiesofany computergraph-icsfluidsolver. We employeda similarschemetomove densitiesthroughuser-definedvelocityfiel ds[19]. [13,18] orimprov-ingtherenderingofgassimulations [21, 5].Ourapplicationofthetechniqueis fundamentallydifferent,sinceweuseit toupdatethevelocityfield, equivalenttoa diffusionequation: 7% # &%7%?Thisis a standardequationforwhichmany numericalprocedureshave todiscretizethediffusionoperator %andthentodoanexplicittimestepasFosteran dMetaxasdid[7].However, thismethodis unstablewhentheviscosityis prefer, therefore,touseanimplicitmethod:H;: J# &%K7+*. 6 F7% 3 where:istheidentityoperator. Whenthediffusionoperatorisdiscretized,th isleadstoa sparselinearsystemfortheunknownfield7+*. Solvingsucha systemcanbedoneefficiently, however(seebelow).

10 Thefourthstepinvolvestheprojectionstep, : &%39 7+*7+/ F7+* "9@?Theprojectionstep,therefore,requires a similarequationusinga ,though,have poorconvergenceandusuallyrequiremany obtainedgoodresultsevenaftera , sinceweareusinga differentmethodtoresolve fortheadvectionstep,wemustusea ,themethodofcharacteristicsis moreprecisewhenthefieldis visualpointofview, theprojectionstepforcesthefieldstohave vorticeswhichre-sultinmoreswirling-like useda ,whenspatiallydiscretized, ,boththeprojectionandtheviscos-itystepsi nvolve thesolutionofa ,forexample,cansolve sparselinearsystemsinlineartime[10].Sinc eouradvectionsolveris alsolinearintime,thecomplexityofourpropo sedalgorithmis ofcomplexity & .FosterandMetaxas solverhasthesamecomplexity. Thisperfor-manceistheoreticallyoptimalsi ncefora complicatedfluid,anyalgorithmhasto consultat domainwithperiodicboundaryconditions,our algorithmtakesa : 6 I $ I ?IntheFourierdomainthegradientoperator isequivalenttothemultiplicationby , where L.