Fluid Simulator
Andrew Selle
Inspiration
After watching Shrek, I became quite interested fluid dynamics applications
in graphics. I was initially inspired by two papers in particular:
Foster and Fedkiw's "Practical Animation of Liquids." And, I thought,
"It would be pretty cool if I had a program that could do that." So, I
read the paper, and naturally I didn't know enough to understand that
paper, as it built on many previous papers, so I followed the references
back until I understood sufficiently to implement a solver.
Additionally, I was recently reinspired to go back and try an implicit solver,
because of the cool results that Antoine McNamara and Adrien Treuille
produced in their smoke project at Washington.
Research History
Computational Fluid Dynamic was essentially born when Harlow and Welch
published their landmark Marker and Cell method. This method is based
on solving the Navier Stokes equations. There are two parts, solving
the velocity with explicit finite differencing and pressure with
an iterative solver. This scheme works well and is relatively easy
to code, but it suffers from instability if the velocities are too big
or the time step is too big. Foster and Metaxis introduced the
graphics community to this technique in "Realistic Animation of Liquids."
My first fluid solver used an explicit solver with successive over-relaxation,
but the instability problems were frustrating, so I abandoned it in
favor of an implicit style solver as in Stam's "Stable Fluids".
A more practical approach for graphics is an implicit solving technique.
Stam introduced the graphics community to such a technique in "Stable
Fluids." He used a semi-Lagrangian technique for velocity advection
coupled with a projection method for enforcing mass conservation.
While this approach is unconditionally stable, it suffers from mass
dissipation and excessive numerical damping, especially of the
vortices that are so interesting in fluid flows. In "Visual Simulation
of Smoke," Fedkiw, et al, combat this using a relatively new technique
from the CFD literature called Vorticy confinement where the vorticies
are detected and receive augmenting forces.
Plan
My goal is to develop a full fluid simulator based on the work of Foster and Fedkiw from SIGGRAPH 2001. I have written a 2d explicit time integration solver for non-free surface problems. Here is a picture of the vector field formed by applying constant force along the top edge. These simulations are based on the Navier-Stokes equations for fluid flow that specify both conservation of momentum and mass. They are given by the two
equations:
I have also reimplemented my simulator using an implict solver
as done in Stam's Stable Fluids paper from SIGGRAPH 1999. This approach
has a number of advantages. First, it won't be subject to blow ups
if the velocities become large. Second, it is really simple and easy
to debug, so the conversion to 3D will be much less painful.
I would next like to build some of the applications
that have been demonstrated in the past. In particular, I would like
to simulate smoke, water, and other phenomena.
Results
Smoke Simulation
I just added the forces for the smoke simulation according to
Fedkiw, et al [1]. The equation is given by:
where alpha and beta are constants to put units into physical wack,
v is the up vector, T is the temperature of the cell, roe is the
density of the cel, and T_amb is the ambient temperature. This
essentially makes dense gas fall and hot gas rise.
Video: Smoke Demo (500k)
Binary: smoke.exe (right mouse draws more smoke density)
Vorticity Confinement
Semi-lagrangian approaches suffer from excessive numerical damping. A recently invented technique
called Vorticity Confinement is designed to find where the interesting vorticies have been
artificially damped and add them back in by applying a paddle wheel like force.
We compute where the vorticies are by using the curl. In 2D the curl is
curl (u,v) = du/dy - dv/dx. Then, we use the derivative of the magnitude to define a new
vector field (d(curl(u,v))/dx, d(curl(u,v))/dy). Then, we simply cross it with curl again
to get a vector in the plane which will be our force.
Smoke Using Vorticity Confinement (100x100 grid): smoke2.avi (692K DivX)
Smoke Using Vorticity Confinement (200x200 grid): smoke3.avi (1538K DivX)
Smoke without vorticity confinement
Smoke sim with same parameters with vorticity confinement
Arbitrary Boundaries
I have implemented arbitrary boundaries using the boundary conditions
stated in Foster and Metaxis' paper. This took me a while to get right.
Boundary conditions are definitely the biggest pain in writing
a fluid solver, and I imagine the free surface boundary conditions
are the biggest pain in the ass. Although, the Enright, et al paper
from SIGGRAPH 2002 seems to have gotten around the annoying setting
of 65 boundary conditions as traditional 3D free surface modeling
requires.
Explicit Solver
I have implemented this feature in my explicit (Harlow and Welch)
style solver. I am looking into adding it to my Stam style solver
implementation, and I hope to do it before I transition the solver
to 3D.
a video of the evolution (Divx 2.5 meg)
Here's a demo binary: fluid.exe.
To use it, left click to place new boundaries. Remember to place
only boundaries that are two thick. One width boundaries are
underdetermined in a nasty way that will cause instability.
Stam Style Solver
I just got boundaries to work in the Stam style solver. below
is a video of the solver with a oval in the center of the
solving grid that the smoke will evade.
smoke-bound.avi (Divx 5 meg)
Extension to 3D
I've recently converted my solver to 3D. This was not terribly difficult, and it
took a few hours. Below is my first movie made with this new solver. The
rendering is really simple so far (I'm just doing blended cubes). But, I'm
going to modify my ray tracer to do smoke soon.
3d.avi (Divx 2.5 meg)
3d-2.avi (Divx 3 meg)
fluid3d.avi (Divx 3 meg)
Additional Resources
References
- R. Fedkiw, J. Stam, and H. W. Jensen. Visual Simulation of Smoke. In SIGGRAPH 2001 Conference Proceedings, Annual Conference Series , pages 15-22, August August 2001
- N. Foster and D. Metaxes. Modeling the Motion of a Hot, Turbulent Gas. In SIGGRAPH 97 Conference Proceedings, Annual Conference Series , pages 181-188, August 1997
- F. H. Harlow and J. E.Welch, Numerical calculations of time dependent viscous incompressible flow of fluid
with a free surface, Phys. Fluids 8, 2182 (1965).
- W. Press, S. Teukolsky, W. Vetterling, and B. Flannery. Numerical Recipes in C. Cambridge, England: Cambridge University Press, 1992.
- J. Stam. Stable Fluids. In SIGGRAPH 99 Conference Proceedings, Annual Conference Series , pages 121-128, August 1999