Transcript PPTX

Fluid Animation
Christopher Batty
November 17, 2011
What distinguishes fluids?
What distinguishes fluids?
•
•
•
•
No “preferred” shape
Always flows when force is applied
Deforms to fit its container
Internal forces depend on velocities, not
displacements
Watch fluid simulation clips
Basic Theory
Eulerian vs. Lagrangian
Lagrangian: Point of reference moves with the
material.
Eulerian: Point of reference is stationary.
e.g. Weather balloon (Lagrangian) vs. weather
station on the ground (Eulerian)
Eulerian vs. Lagrangian
Consider an evolving temperature field.
• Lagrangian: Set of moving particles, each
with a temperature value.
Eulerian vs. Lagrangian
Consider an evolving temperature field.
• Eulerian: A fixed grid of temperature values,
that temperature flows through.
Relating Eulerian and Lagrangian
Consider the temperature 𝑇(𝑥, 𝑡) at a point
following a given path, 𝑥(𝑡).
𝑥(𝑡1 )
𝑥(𝑡𝑛𝑜𝑤 )
𝑥(𝑡0 )
Two ways temperature changes:
1. Heating/cooling occurs at the current point.
2. Following the path, the point moves to a
cooler/warmer location.
Time derivatives
Mathematically:
𝐷
𝜕𝑇 𝜕𝑇 𝜕𝑥
𝑇 𝑥 𝑡 ,𝑡 =
+
𝐷𝑡
𝜕𝑡 𝜕𝑥 𝜕𝑡
Chain rule!
𝜕𝑇
𝜕𝑥
=
+ 𝛻𝑇 ∙
𝜕𝑡
𝜕𝑡
Definition
of 𝛻
𝜕𝑇
=
+ 𝒖 ∙ 𝛻𝑇
𝜕𝑡
Choose
=𝑢
𝜕𝑥
𝜕𝑡
Material Derivative
This is called the material derivative, and denoted
𝐷
.
𝐷𝑡
Change at a point moving
with the velocity field.
Change due
to movement.
𝐷𝑇 𝜕𝑇
=
+ 𝒖𝛻𝑇
𝐷𝑡
𝜕𝑡
Change at the current
(fixed) point.
Advection
To track a quantity T simply moving (passively)
through a velocity field:
𝐷𝑇
=0
𝐷𝑡
or equivalently
𝜕𝑇
+ 𝒖𝛻𝑇 = 0
𝜕𝑡
This is the advection equation.
Think of colored dye or massless particles drifting
around in fluid.
Watch dye in fluid clip
Equations of Motion
• For general materials, we have Newton’s
second law: F = ma.
• Specialized for fluids:
“Navier-Stokes Equations”
Navier-Stokes
Density × Acceleration = Sum of Forces
𝐷𝒖
𝜌
=
𝐷𝑡
𝑭𝑖
𝑖
Expanding the material derivative…
𝜕𝒖
𝜌
= −𝜌 𝒖 ∙ 𝛻𝒖 +
𝜕𝑡
𝑭𝑖
𝑖
What are the forces on a fluid?
Primarily for now:
• Pressure
• Viscosity
• Simple “external” forces
– (e.g. gravity, buoyancy, user forces)
Also:
• Surface tension
• Coriolis
• Possibilities for more exotic fluid types:
– Elasticity (e.g. silly putty)
– Shear thickening / thinning (e.g. “oobleck”, ketchup)
– Electromagnetic forces
• Sky’s the limit...
Watch oobleck clip
In full…
𝜕𝒖
𝜌
= −𝜌 𝒖 ∙ 𝛻𝒖 +
𝜕𝑡
Change in
velocity at a
fixed point
Advection
𝑭𝑖
𝑖
Forces
(pressure,
viscosity
gravity,…)
Operator splitting
Break the equation into steps:
1.
2.
3.
4.
𝜕𝒖
Advection: 𝜌 = −𝜌 𝒖 ∙ 𝛻𝒖
𝜕𝑡
𝜕𝒖
Pressure: 𝜌 = 𝑭𝑝𝑟𝑒𝑠𝑠𝑢𝑟𝑒
𝜕𝑡
𝜕𝒖
Viscosity: 𝜌 = 𝑭𝑣𝑖𝑠𝑐𝑜𝑠𝑖𝑡𝑦
𝜕𝑡
𝜕𝒖
External: 𝜌 = 𝑭𝑜𝑡ℎ𝑒𝑟
𝜕𝑡
1. Advection
Advection
Previously, we considered advection of a passive
scalar quantity, 𝑇, by velocity 𝒖.
𝜕𝑇
= −𝒖 ∙ 𝛻𝑇
𝜕𝑡
In Navier-Stokes we saw:
𝜕𝒖
= −𝒖 ∙ 𝛻𝒖
𝜕𝑡
Velocity 𝒖 is advected by itself!
Advection
i.e., The scalar components 𝑢, 𝑣 of the vector
𝒖 are each advected in the same way.
We can reuse the same numerical method.
2. Pressure
Pressure
What does pressure do?
– Enforces incompressibility.
Typical fluids (mostly) do not compress.
• Exceptions: high velocity, high pressure, …
Incompressibility
Compressible
velocity field
Incompressible
velocity field
Incompressibility
Intuitively, net flow into/out of a given region is zero (no
sinks/sources).
Integrate the flow across the boundary of a closed
region:
𝒏
𝒖∙𝒏=0
𝜕Ω
Incompressibility
𝒖∙𝒏=0
𝜕Ω
By divergence theorem:
𝛁∙𝒖=0
But this is true for any region, so 𝛁 ∙ 𝒖 = 𝟎
everywhere.
Pressure
How does pressure enter in?
– Pressure is the force required to ensure that 𝛻
∙ 𝒖 = 0.
– Pressure force has the following form:
𝑭𝑝 = −𝛻𝑝
Helmholtz-Hodge Decomposition
Input Velocity field
Curl-Free
(irrotational)
Divergence-Free
(incompressible)
+
=
𝑢
=
𝛻𝑝
+
𝛻×𝜑
𝑢𝑜𝑙𝑑
=
𝐹𝑝𝑟𝑒𝑠𝑠𝑢𝑟𝑒
+
𝑢𝑛𝑒𝑤
Aside: Pressure as Lagrange Multiplier
Interpret as an optimization:
Find the closest 𝒖𝑛𝑒𝑤 to 𝒖𝑜𝑙𝑑 where 𝛻 ∙ 𝒖𝑛𝑒𝑤 = 0
min 𝒖𝑛𝑒𝑤 − 𝒖𝑜𝑙𝑑
𝒖𝑛𝑒𝑤
s. t. 𝛻 ∙ 𝒖𝑛𝑒𝑤 = 0
A Lagrange multiplier to enforce the constraint
is exactly pressure.
3. Viscosity
Viscosity
What characterizes a viscous liquid?
• “Thick”, damped behaviour
• Higher resistance to flow
Watch viscous honey clip
Viscosity
Loss of energy due to internal friction between
molecules moving at different velocities.
Interactions between molecules in different layers
causes shear stress that…
• acts to oppose relative motion.
• causes an exchange of momentum
Viscosity
Loss of energy due to internal friction between
molecules moving at different velocities.
Interactions between molecules in different layers
causes shear stress that…
• acts to oppose relative motion.
• causes an exchange of momentum
Viscosity
Loss of energy due to internal friction between
molecules moving at different velocities.
Interactions between molecules in different layers
causes shear stress that…
• acts to oppose relative motion.
• causes an exchange of momentum
Viscosity
Loss of energy due to internal friction between
molecules moving at different velocities.
Interactions between molecules in different layers
causes shear stress that…
• acts to oppose relative motion.
• causes an exchange of momentum
Viscosity
Imagine fluid particles with general velocities.
Each particle interacts with nearby neighbours,
exchanging momentum.
Viscosity
Amount of momentum exchanged is proportional to:
• Velocity gradient, 𝛻𝒖.
• Viscosity coefficient, 𝜇
For any closed region, net in/out flow of momentum:
𝜇𝛻𝒖 ∙ 𝒏 =
𝜇𝛁 ∙ 𝛁𝒖
𝜕Ω
So the viscosity force is: 𝑭𝑣𝑖𝑠𝑐𝑜𝑠𝑖𝑡𝑦 = 𝜇𝛁 ∙ 𝛁𝒖
Viscosity
The end result is a smoothing of the velocity.
This is exactly the action of the Laplacian
operator, 𝛁 ∙ 𝛁.
For scalar quantities, the same operator is
used to model diffusion.
4. External Forces
External Forces
Any other forces you may want.
• Simplest is gravity:
– 𝐹𝑔 = 𝜌𝒈 for 𝒈 = (0, −9.81)
• Buoyancy models are similar,
– e.g., 𝐹𝑏 = 𝛽(𝑇𝑐𝑢𝑟𝑟𝑒𝑛𝑡 − 𝑇𝑟𝑒𝑓 )𝒈
Numerical Methods
1. Advection
Advection of a Scalar
• First, we’ll consider advecting a scalar
quantity, 𝜑.
– temperature, color, smoke density, …
• The grid stores 𝜑 and 𝒖.
Eulerian
Approximate derivatives with finite differences.
𝜕𝜑
+ 𝒖 ∙ 𝛻𝜑 = 0
𝜕𝑡
FTCS = Forward Time, Centered Space:
𝜑𝑖 𝑛+1 − 𝜑𝑖 𝑛
𝜑𝑖+1 𝑛 − 𝜑𝑖−1 𝑛
+𝑢
=0
∆𝑡
2∆𝑥
Unconditionally
Unstable!
Lax:
Conditionally
𝜑𝑖 𝑛+1 − (𝜑𝑖+1 𝑛 + 𝜑𝑖−1 𝑛 )/2
𝜑𝑖+1 𝑛 − 𝜑𝑖−1 𝑛
+𝑢
=0
Stable!
∆𝑡
2∆𝑥
Many possible methods, stability can be a challenge.
Lagrangian
• Advect data forward from grid points by integrating
position according to grid velocity.
?
• Problem: New data position doesn’t necessarily land
on a grid point.
Semi-Lagrangian
• Look backwards in time from grid points, to
see where data is coming from.
• Interpolate data at previous time.
Semi-Lagrangian - Details
1. Determine velocity 𝒖𝑖,𝑗 at grid point,.
2. Integrate position for a timestep of −∆𝑡.
 e.g. 𝑥𝑏𝑎𝑐𝑘 = 𝑥𝑖,𝑗 − ∆𝑡𝒖𝑖,𝑗
3. Interpolate 𝜑 at 𝑥𝑏𝑎𝑐𝑘 , call it 𝜑𝑏𝑎𝑐𝑘 .
4. Assign 𝜑𝑖,𝑗 = 𝜑𝑏𝑎𝑐𝑘 for the next time.
Unconditionally stable!
Advection of Velocity
• This is great for scalars. What about velocity advection?
• Same method:
𝜕𝒖
= −𝒖 ∙ 𝛻𝒖
𝜕𝑡
– Trace back with current velocity
– Interpolate velocity (component) at that point
– Assign it to the grid point at the new time.
• Caution: Do not overwrite the velocity field you’re using to
trace back!
2. Pressure
Recall… Helmholtz-Hodge
Decomposition
Input Velocity field
Curl-Free
(irrotational)
Divergence-Free
(incompressible)
+
=
𝑢
=
𝛻𝑝
+
𝛻×𝜑
𝑢𝑜𝑙𝑑
=
𝐹𝑝𝑟𝑒𝑠𝑠𝑢𝑟𝑒
+
𝑢𝑛𝑒𝑤
Pressure Projection - Derivation
(1)
𝜕𝒖
𝜌
𝜕𝑡
= −𝛻𝑝
Discretize (1) in time…
and (2) 𝛻 ∙ 𝒖 = 0
∆𝑡
𝒖𝑛𝑒𝑤 = 𝒖𝑜𝑙𝑑 − 𝛻𝑝
𝜌
Then plug into (2)…
∆𝑡
𝛻 ∙ 𝒖𝑜𝑙𝑑 − 𝛻𝑝 = 0
𝜌
Pressure Projection
Implementation:
1) Solve a linear system for p:
∆𝑡
𝛻 ∙ 𝛻𝑝 = 𝛻 ∙ 𝒖𝑜𝑙𝑑
𝜌
2) Update grid velocity with:
𝒖𝑛𝑒𝑤
∆𝑡
= 𝒖𝑜𝑙𝑑 − 𝛻𝑝
𝜌
Implementation
∆𝑡
𝛻 ∙ 𝛻𝑝 = 𝛻 ∙ 𝒖𝑜𝑙𝑑
𝜌
Discretize with finite differences:
𝑢𝑖+1
𝑝𝑖+1
𝑢𝑖
𝑝𝑖
𝑝𝑖−1
e.g., in 1D:
𝑝𝑖+1 − 𝑝𝑖 𝑝𝑖 − 𝑝𝑖−1
𝑜𝑙𝑑
−
∆𝑡
𝑢𝑖+1 − 𝑢𝑖
∆𝑥
∆𝑥
=
𝜌
∆𝑥
∆𝑥
𝑜𝑙𝑑
Solid Boundary Conditions
Free Slip:
𝒖𝑛𝑒𝑤 ∙ 𝒏 = 0
𝒏
𝒖
52
Staggered vs. Non-staggered
• Two choices for grids:
– Velocity and pressure co-located
𝑝𝑖+1
𝑝𝑖−1
𝑝𝑖
𝑢𝑖
𝑢𝑖+1
𝑢𝑖−1
– Velocity and pressure staggered
𝑝𝑖+1
𝑢𝑖+1
𝑝𝑖
𝑢𝑖
𝑝𝑖−1
Why prefer staggered?
• Finite differences line up nicely.
– 𝑢 and 𝛻𝑝 match, 𝑝 and 𝛻 ∙ 𝑢 match
𝑢𝑖+1
𝑝𝑖+1
𝑢𝑖
𝑝𝑖
• …which improves stability!
𝑝𝑖−1
3. Viscosity
Viscosity
𝜕𝒖
PDE: 𝜌
𝜕𝑡
= 𝜇𝛻 ∙ 𝛻𝒖
Use finite differences.
Discretized in time:
𝒖𝒏𝒆𝒘 = 𝒖𝑜𝑙𝑑 + ∆𝑡𝜇
𝛻 ∙ 𝛻𝒖∗
𝜌
Viscosity – Time Integration
𝒖𝒏𝒆𝒘 = 𝒖𝑜𝑙𝑑 + ∆𝑡𝜇
𝜌 𝛻 ∙ 𝛻𝒖∗
Explicit integration, let 𝒖∗ be 𝒖𝑜𝑙𝑑 :
– Just estimate ∆𝑡𝜇
𝛻 ∙ 𝛻𝒖𝑜𝑙𝑑
𝜌
– Add to current 𝒖.
– Very unstable.
Implicit integration, let 𝒖∗ be 𝒖𝑛𝑒𝑤 :
– Stable for high viscosities.
– Need to solve a system of equations.
Viscosity – Implicit Integration
Solve for 𝒖𝒏𝒆𝒘 :
𝒖𝒏𝒆𝒘 − ∆𝑡𝜇
𝛻 ∙ 𝛻𝒖𝑛𝑒𝑤 = 𝒖𝑜𝑙𝑑
𝜌
Apply separately for each velocity component.
e.g. in 1D:
𝑢𝑖+1
𝑢𝑖 𝑢
−
𝑢𝑖−1
𝑢𝑖+1 − 𝑢𝑖 𝑢𝑖
𝑖−1
−
∆𝑡𝜇
∆𝑥
∆𝑥
𝑢𝑖 −
= 𝑢𝑖
𝜌
∆𝑥
𝑜𝑙𝑑
Solid Boundary Conditions
No-Slip:
𝒖𝑛𝑒𝑤 = 0
Watch no-slip clip
59
4. External Forces
Gravity
Discretized form is:
𝒖𝒏𝒆𝒘 = 𝒖𝑜𝑙𝑑 + ∆𝑡𝒈
Just add a downward acceleration to each
velocity, scaled by timestep.
Gravity
• Note: in a closed fluid-filled container, gravity
(alone) won’t do anything!
– Incompressibility cancels it out.
– (Assuming constant density)
Start
After gravity step
After pressure step
Simple Buoyancy
Look up 𝑇𝑐𝑢𝑟𝑟𝑒𝑛𝑡 at grid point, increment
velocity based on difference from a
reference velocity.
𝒖𝒏𝒆𝒘 = 𝒖𝑜𝑙𝑑 + ∆𝑡𝛽 𝑇𝑐𝑢𝑟𝑟𝑒𝑛𝑡 − 𝑇𝑟𝑒𝑓 𝒈
𝛽 dictates the strength of the buoyancy
force.
See paper for a more elaborate model:
“Visual simulation of smoke”, 2001.
User Forces
Add whatever additional forces we want, such
as:
• near the mouse when the user clicks
• Paddle forces in Plasma Pong
Watch clip
Ordering of Steps
Order turns out to be important.
Why?
1) Incompressibility is not guaranteed at
intermediate steps
2) Advecting with a compressible field causes
volume/material loss or gain!
Ordering of Steps
Consider advection in this field:
Best ordering
1) Advection
2) Viscosity
3) Add Forces
4) Make incompressible (Pressure)
Useful References
• Robert Bridson’s SIGGRAPH 2007 Fluid
Course notes:
http://www.cs.ubc.ca/~rbridson/fluidsimulation/
• “Stable Fluids” [Stam 1999]
• “Real-Time Stable Fluid Dynamics for
Games” [Stam, 2003]
Liquids
Liquids
What’s missing so far?
We need:
• A surface representation
• Boundary conditions at the surface
The Big Picture
Velocity Solver
Advect Velocities
Add Viscosity
Add Gravity
Project Velocities
to be
Incompressible
What about liquids?
Velocity Solver
Advect Velocities
Add Viscosity
Add Gravity
Project Velocities
to be
Incompressible
Surface Tracker
Surface Tracker
Given: liquid surface geometry, velocity field,
timestep
Compute: new surface geometry by advection.
𝒖𝑛
𝑇𝑛
𝑇𝑛+1
Surface Tracker
Ideally:
• Efficient
• Accurate
• Handles merging/splitting (topology changes)
• Conserves volume
• Retains small features
• Smooth surface for rendering
• Provides convenient geometric operations
• Easy to implement…
Very hard (impossible?) to do all of these at once.
Surface Tracking Options
1.
2.
3.
4.
5.
Particles
Level sets
Volume-of-fluid (VOF)
Triangle meshes
Hybrids (many of these)
Particles
[Zhu & Bridson 2005]
Particles
Perform passive Lagrangian advection on each
particle.
For rendering, need to reconstruct a surface.
Level sets
[Losasso et al.
2004]
Level sets
Each grid point stores signed distance to the
surface (inside <= 0, outside > 0).
Surface is interpolated zero isocontour.
>0
<= 0
Volume of fluid
[Mullen et al 2007]
Volume-Of-Fluid
Each cell stores fraction f ϵ 0,1 indicating
how empty/full it is.
Surface is transition region, f ≈ 0.5.
1
1
1
1
1
0.
8
0
0
0
1
0.4
0
0
1
1
0.4
0
0
1
1
0.8
0
0
0
1
1
0.5
0
0
0
Meshes
[Brochu et al 2010]
Meshes
Store a triangle mesh.
Advect its vertices, and correct for collisions.