CS计算机代考程序代写 algorithm PowerPoint Presentation
PowerPoint Presentation
Stable Fluids
A paper by Jos Stam
Contributions
Real-Time unconditionally stable solver for Navier-Stokes fluid dynamics equations
Implicit methods allow for large timesteps
Excessive damping – damps out swirling vortices
Easy to implement
Controllable (?)
Some Math(s)
Nabla Operator:
Laplacian Operator:
Gradient:
More Math(s)
Vector Gradient:
Divergence:
Directional Derivative:
Navier-Stokes Fluid Dynamics
Velocity field u, Pressure field p
Viscosity v, density d (constants)
External force f
Navier-Stokes Equation:
Mass Conservation Condition:
Navier-Stokes Equation
Derived from momentum conservation condition
4 Components:
Advection/Convection
Diffusion (damping)
Pressure
External force (gravity, etc)
Mass Conservation Condition
Velocity field u has zero divergence
Net mass change of any sub-region is 0
Flow in == flow out
Incompressible fluid
Comes from continuum assumption
Enforcing Zero Divergence
Pressure and Velocity fields related
Say we have velocity field w with non-zero divergence
Can decompose into
Helmholtz-Hodge Decomposition
u has zero divergence
Define operator P that takes w to u:
Apply P to Navier-Stokes Equation:
(Used facts that and )
Operator P
Need to find
Implicit definition:
Poisson equation for scalar field p
Neumann boundary condition
Sparse linear system when discretized
Solving the System
Need to calculate:
Start with initial state
Calculate new velocity fields
New state:
Step 1 – Add Force
Assume change in force is small during timestep
Just do a basic forward-Euler step
Note: f is actually an acceleration?
Step 2 – Advection
Method of Characteristics
p is called the characteristic
Partial streamline of velocity field u
Can show u does not vary along streamline
Determine p by tracing backwards
Unconditionally stable
Maximum value of w2 is never greater
than maximum value of w1
Step 3 – Diffusion
Standard diffusion equation
Use implicit method:
Sparse linear system
Step 4 – Projection
Enforces mass-conservation condition
Poisson Problem:
Discretize q using central differences
Sparse linear system
Maybe banded diagonal…
Relaxation methods too inaccurate
Method of characteristics more precise for divergence-free field
Complexity Analysis
Have to solve 2 sparse linear systems
Theoretically O(N) with multigrid methods
Advection solver is also O(N)
However, have to take lots of steps in particle tracer, or vortices are damped out very quickly
So solver is theoretically O(N)
I think the constant is going to be pretty high…
Periodic Boundaries
Allows transformation into Fourier domain
In Fourier domain, nabla operator is equivalent to ik
New Algorithm:
Compute force and advection
Transform to Fourier domain
Compute diffusion and projection steps
Trivial because nabla is just a multiply
Transform back to time domain
Diffusing Substances
Diffuse scalar quantity a (smoke, dust, texture coordinate)
Advected by velocity field while diffusing
ka is diffusion constant, da is dissipation rate, Sa is source term
Similar to Navier-Stokes
Can use same methods to solve equations, Except dissipation term
The End
