Transcription
Lecture 26:Advanced Topics:Fluid SimulationComputer GraphicsCMU 15-462/15-662, Fall 2015
Previously: Partial Differential EquationsAnimation via differential equationsImplicit description of motionSolve in space and timeConsidered three model equations:- Laplace (elliptic)- heat (parabolic)- wave (hyperbolic)Already saw some cool/interesting behavior (e.g., ripples)Real physical phenomena involve harder (nonlinear) PDEsTODAY: fluids (smoke, water, fire, .)- Basis of many recent (beautiful!) visual effectsCMU 15-462/662, Fall 2015
Fluids in Computer Graphics - SmokeZhang, Bridson, Greif, “Restoring the Missing Vortices in Advection-Projection Fluid Solvers”CMU 15-462/662, Fall 2015
Fluids in Computer Graphics - WaterAndo, Thürey, Wojtan, “Highly Adaptive Liquid Simulations on Tetrahedral Meshes”CMU 15-462/662, Fall 2015
Fluids in Computer Graphics - FireHong, Shinar, Fedkiw, “Wrinkled Flames and Cellular Patterns”CMU 15-462/662, Fall 2015
Fluids in Computer Graphics - PaintCurtis, Anderson, Seims, Fleischer, Salesin, “Computer-Generated Watercolor”CMU 15-462/662, Fall 2015
Fluids in Computer Graphics - CrowdsTreuille, Cooper, Popovic, “Continuum Crowds”CMU 15-462/662, Fall 2015
Visual Vector Calculus—Div, Grad, & CurlWe’re going to use these a lot todayKeep these three pictures in mind!GRADIENTDIVERGENCE(“steepest direction”)(how much “spreading out?”)— scalar function— vector fieldCURL(how much “spinning?”)CMU 15-462/662, Fall 2015
The Fluid Equation?How do we describe the motion of a fluid?IMPORTANT: There are many different ways- Navier-Stokes equation- vorticity equation- Euler-Arnold equation- molecular dynamics- .For mainly historical reasons, Navier-Stokes (velocity-based)approach largely dominates computer graphicsMoving forward, does not mean it’s the right way for computationAs with everything: pick the right tool for the job!CMU 15-462/662, Fall 2015
Incompressible Navier–StokesNavier-Stokes “most traditional” descriptionIllustrates many* important phenomenaExpressed in terms of fluid velocity u(t,x)At each point, how fast is fluid moving?Nonlinear PDE, 1st-order in time, 2nd-order in space:change invelocity overtimeadvection(“particles moveforward”)pressure(“particles shouldnot collide”)viscosity / diffusion(one of our linearmodel equations!)external forces(e.g., gravity)incompressibility (assume fluiddoesn’t gain/lose volume)*but not all!CMU 15-462/662, Fall 2015
Where does this equation come from?For the moment, let’s ignore viscosity,incompressibility, and external forces.CMU 15-462/662, Fall 2015
Review: Chain RuleConsider a composite function f(g(x))Once upon a time, you may have memorized the formula“chain rule”CMU 15-462/662, Fall 2015
Q: Where does this “rule” come from?CMU 15-462/662, Fall 2015
A: It comes from your highschool calculus teacher.CMU 15-462/662, Fall 2015
Rules are something you’re told byan authority to blindly obey.What we’d rather understand is theundeniably self-evident “chain fact.”So how do we see it?CMU 15-462/662, Fall 2015
Visual Calculus: The Chain FactFirst, stop thinking about a function in terms of its graph;instead, think about it as a map from one space to another: ( ) same function,different picture!CMU 15-462/662, Fall 2015
Visual Calculus: The Chain FactThe derivative is no longer the slope; it is now the amount bywhich the function locally gets squashed/stretched:“squash factor”CMU 15-462/662, Fall 2015
Visual Calculus: The Chain FactSo, the chain rule just says: “to get the total amount ofsquashing, just multiply the squash factors.”“repeated squashing rule”CMU 15-462/662, Fall 2015
The more you do graphics, the moreyou discover that you need to take“derivatives of weird functions.”Keeping this “stretching” picture inmind can be enormously helpful.CMU 15-462/662, Fall 2015
Review: The Total DerivativeNow suppose we have a function f that depends on someparameter t both directly and indirectly:How does f change as we vary t? Another “rule”.(Food for thought: what does it mean intuitively/geometrically?)CMU 15-462/662, Fall 2015
The Material DerivativeFor fluids, the derivative we really need to understand is theso-called material derivative or Lagrangian derivativeAs a running example, think about the temperature φ in aswimming pool, at a point x, at a time t:timepositiontemperatureNotice that the point x is itself moving over time.CMU 15-462/662, Fall 2015
The Material Derivative - TimeSuppose our point x is not moving. The observed change intemperature is then just“how much is the pool heating up/cooling down at the current point x?”CMU 15-462/662, Fall 2015
The Material Derivative - SpaceSuppose we swim from one end to the other, without changingthe temperature in the pool. Then the observed change intemperature is“how much does the temperaturechange if we swim in a given direction?”Spatial derivative alone is calledthe “directional derivative” (moregenerally: covariant derivative orconnection.) Can be written asCMU 15-462/662, Fall 2015
The Material DerivativeSo what’s the overall change in temperature?Well, we could apply the “total derivative rule”:“pool is changing temperature”“swimmer is moving to hotter /cooler part of the pool”And. hey! That’s exactly what we got by thinking about thechange in time and space independently.CMU 15-462/662, Fall 2015
The Material DerivativeIn a fluid, the direction of motion is the fluid velocity u:The material derivative is the change in a quantity due tofluid motion, i.e., due to the phenomenon of “advection”:“material derivative”CMU 15-462/662, Fall 2015
Example of AdvectionColor gets “pushed along” by /fluid.htmCMU 15-462/662, Fall 2015
Computing AdvectionNumerically, how do we advect a given quantity φ (color,temperature, .) in a given vector field u?Many options—recall discussion of Eulerian vs. LagrangianEULERIANEulerian(upwinding)- Lagrangian (PIC/FLIP)- semi-Lagrangian (“stable fluids”)LAGRANGIANEach has pros & cons.track velocity (or flux)at fixed grid locationstrack position & velocityof moving particlesCMU 15-462/662, Fall 2015
Upwinding (1D)1D advectionUse Eulerian discretization (grid)Consider 1D advection equationApproximate time derivative w/ finite difference:Same deal w/ space derivative. but which direction?Pick based on sign of velocity (“upwind” direction):Similar story in 2D, 3D (though many different options.)CMU 15-462/662, Fall 2015
Upwinding—Pros & ConsSimilar tradeoffs to many Eulerian methodsPROS:- easy to compute (local stencil)- can generalize to very accurate schemes- helps capture strongly directional behavior like shockwavesCONS:- numerical diffusion (“blurring”) due to grid resolution- time step limited by grid size (“CFL condition”)Hence, computation gets (even) moreexpensive as resolution/velocity increases;not ideal for real-time (games, etc.)time stepdimensionvelocitygrid spacingCMU 15-462/662, Fall 2015
Numerical DiffusionUnwanted “blurring” issue in all numerical advection schemes (sampling error!)Crane, Llamas, Tariq, “Real Time Simulation and Rendering of 3D Fluids”CMU 15-462/662, Fall 2015
Lagrangian AdvectionInstead of grid, use particles to track velocityStill use background grid for other aspects of simulationE.g., PIC (“particle-in-cell”) or FLIP (“fluid-implicit-particle”)Far less numerical diffusion, but. (drawbacks?)Need many particles; sampling is hard; incoherent memory accessCMU 15-462/662, Fall 2015
Particle Advection—Example(produced using “Naiad,” now “Bïfrost”)CMU 15-462/662, Fall 2015
Semi-Lagrangian AdvectionTechnique from atmospheric science (weather prediction!)Popular in graphics because unconditionally stableVelocities on grid; to advect, trace backwards and “copy”:Since new velocity is interpolated from old ones, can neverincrease. However, can still be inaccurate, damped.CMU 15-462/662, Fall 2015
Numerical Energy DissipationAnother common problem: loss of energy/momentumMullen, Crane, Pavlov, Tong, Desbrun, “Energy-Preserving Integrators for Fluid Animation”CMU 15-462/662, Fall 2015
Advection—SummaryBasic idea: push quantity forward by velocityMany different ways to compute:- Eulerian (grid)- Lagrangian (particles)- semi-Lagrangian (trace characteristics)Common challenges faces by all schemes:- stability (“does it blow up for large time steps?”)- numerical diffusion (“does it get blurred out?”)- numerical dissipation (“does it lose energy?”)- convergence/consistency (“do we get the correct answer?”)CMU 15-462/662, Fall 2015
Ok, we’ve now seen the first coupleterms in Navier-Stokes (advection).Let’s keep going.CMU 15-462/662, Fall 2015
IncompressibilityMany common fluids—like water!—are incompressible, i.e.,no change in density (for all practical purposes.)Suppose the fluid has constant mass density ρ. Since masscannot be created nor destroyed, we haveno changein masstotal masstotal change in massis the same as fluxthrough the boundaryCMU 15-462/662, Fall 2015
IncompressibilityFrom here, apply divergence theoremSince this quantity is zero for every possible region Ω,it must in fact be zero pointwise:Since density is constant, we get ourincompressibility constraint“no divergence,” i.e., no sources or sinks allowed!(otherwise, fluid will COMPRESS!)CMU 15-462/662, Fall 2015
How do constraints enter intoour equations of motion?CMU 15-462/662, Fall 2015
Simple Example: Bead on a HoopConsider a bead constrained to slide around on a hoop:positionvelocityconstraint functionFor simplicity, let’s assume no external forces (gravity, etc.)How do we get the equations of motion?CMU 15-462/662, Fall 2015
Constrained Lagrangian MechanicsReturn to Lagrangian picture, with a rgypotentialenergyconstraintfunctionAs before, equations of motion are given by Euler-Lagrange:Don’t have to reason about force diagrams, etc.—just have towrite down energy, constraints, and then “plug and chug”.CMU 15-462/662, Fall 2015
Equations of Motion for a Bead on a HoopLet’s try it for our bead on a hoop:“pushes”bead backonto tforceEQUATIONS OF MOTIONCMU 15-462/662, Fall 2015
Fluid PressureSo what’s the force due to incompressibility in our fluid?Constraint was a divergence-free constraint on velocity:Skipping the rest of the Lagrangian, the constraint term isL2 innerproductStokes’ theoremLagrange multiplieris now a function!Derivative with respect to velocity u? (Any guesses?)constraint forceCMU 15-462/662, Fall 2015
Fluid Pressure.Ok, what the heck does this force mean?For fluids, typically use “p” rather than “λ” to denoteLagrange multiplier:Physically, corresponds to pressure, i.e., the force per unit arearequired to keep the fluid from compressing.Intuitively, prevents “particles from bumping into each-other”Geometrically, pressure is force pushing the velocity back ontothe space of divergence-free vector fields (just like our bead.)“pushes” velocity towardssomething divergence-free!CMU 15-462/662, Fall 2015
Constraint EnforcementRemember that equations of motion are implicit: they don’tdirectly tell us the trajectory; they just say which equationsany physical trajectory must satisfy.How do we integrate equations of motion w/ constraints?Many different techniques! One basic divisionREDUCED COORDINATES- use as few degrees of freedom as possible- e.g., angle of bead instead of (x,y)- not always possible/easy“FULL” COORDINATES*- use coords that are easy/intuitive to work with- somehow need to keep them on constraint curve.*Point of philosophy: there is no canonical “full set of coordinates.” Can always add more, cook up other descriptions, etc.CMU 15-462/662, Fall 2015
Constraint ProjectionPrototypical approach to constraints:1. Pretend there are no constraints; take a small step2. Project back onto constraint set3. RepeatE.g., bead on hoop:1. Move forward2. Normalize position3. RepeatDo we get the right dynamics?Yes—but only as time step goes to zero!For large time steps, we lose energy/momentum(just saw this for fluids!)CMU 15-462/662, Fall 2015
Constraint Projection for Fluids(Not the only method, butis the basis of many currenttechniques in graphics.)ADTCVEPROJECTIONIn fluids, analog of “moving forward” is advectionAfterwards, velocity may no longer be divergence-freeIDEA: Project onto nearest divergence-free field“Chorin’s projection method”Same loop as before:1. Advect2. Project3. RepeatNOICMU 15-462/662, Fall 2015
Helmholtz-Hodge DecompositionSo, how do we find the closest divergence-free field?FACT: every vector field can be expressed as the sum of adivergence-free part, a curl-free part, and a harmonic part:divergence-freecurl-freeharmonic:zero curl andzero divergenceCMU 15-462/662, Fall 2015
Removing DivergenceA divergence-free field should not have any divergence!So, seek and destroy: find divergence, then subtract it.Taking divergence of Helmholtz-Hodge decomposition yieldsPoisson equation!Overall, simple strategy for enforcing incompressibility:1. Solve (linear) Laplace equation2. Subtract pressure gradient to get div-free fieldCMU 15-462/662, Fall 2015
We now have the most important terms:The rest is easy.CMU 15-462/662, Fall 2015
Reminder: Heat / Diffusion Equation“How does an initial distribution of heat spread out over time?”CLAIM: Models damping / viscosity in many physical systemsCMU 15-462/662, Fall 2015
Fluid ViscosityFor fluids, diffusion models “slowingdown” of velocity due to internal“friction” (intermolecular forces)kinematicviscosityvelocityour old frenemythe LaplacianViscosity much higher for e.g., honey;much lower for wine.Different regimes of viscosity lead tovery different simulation techniques.CMU 15-462/662, Fall 2015
Honey SimulationBergou, Audoly, Vouga, Wardetzky, Grinspun, “Discrete Viscous Threads”CMU 15-462/662, Fall 2015
Wine SimulationAzencot, Vantzos, Wardetzky, Rumpf, Ben-Chen, “Functional Thin Films on Surfaces”CMU 15-462/662, Fall 2015
And that’s pretty much it.The rest is just “anything else” (like gravity).CMU 15-462/662, Fall 2015
Notice that we used two of our modelequations: the Poisson and heat equations.(We weren’t kidding when we said thesethings show up everywhere in simulation!)CMU 15-462/662, Fall 2015
An ocean of knowledge. be a sponge!So much more to say about fluids:Other forms of fluid equations- vorticity increasingly popular in graphics- leads, e.g., to nice 1D vortex filamentsFree surface tracking- e.g., simulation of liquids- track surface with grid OR particles OR meshVarious fluid phenomena- fire, smoke, viscoelastic, .Pure particle-based methods (SPH, MD)Go out there and make a splash!CMU 15-462/662, Fall 2015
Next up: Virtual RealityCMU 15-462/662, Fall 2015
-Basis of many recent (beautiful!) visual effects CMU 15-462/662, Fall 2015 Previously: Partial Differential Equations. . Constraint was a divergence-free constraint on velocity: Skipping the rest of the Lagrangian, the constraint term is L2 inner product Lagrange multiplier
