# 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