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