# 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:

More Math(s)

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:

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:

Calculate new velocity fields

New state:

Assume change in force is small during timestep
Just do a basic forward-Euler step

Note: f is actually an acceleration?

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

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:

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