Water

Water simulation resources

Good survey of different particle based methods: http://www.cse-lab.ethz.ch/teaching/classes/mulsup.html
Siggraph 2007 course website on fluid simulation: http://www.cs.ubc.ca/~rbridson/fluidsimulation/

(Incomplete) List of movies featuring cg water

The Abyss (1989) (Great video from 1992 about it: http://www.youtube.com/watch?v=oe20_9XbUgE)
Waterworld (1995)
Titanic (1997)
The Perfect Storm (2000)
The Day After Tomorrow (2004)
...

Smoothed particle hydrodynamics

Smoothed particle hydrodynamics (SPH) is a method to simulate fluid flow using particles. Instead of dividing a volume into a grid, particles are used to represent the values of the simulation over the volume. The main idea behind this approach is that physical quantities can be smoothed over the volume; that is the quantity of a point in space can be computed with a weighted sum over the nearby particles.

In general, a quantity A is computed as follows:

$A(\bf{r}) = \sum_j{m_j \frac{A_j}{\rho_j} W(\bf{r} - \bf{r_j}, h)}$

where m_j is the mass of particle j, A_j is the field quantity at particle j, \rho_j the density at particle j, and W(r - r_j, h) is a weighting function, that depends on the distance between the particle and the point we're computing for, and the weighting kernel with a core radius of h.

If the smoothing kernel is even and normalized (integrates to 1) (Müller 2003), the interpolation is of second order accuracy.

The derivative of the quantity A is defined as:

$\nabla{A(\bf{r})} = \sum_j{m_j \frac{A_j}{\rho_j} \nabla{W(\bf{r} - \bf{r_j}, h)}}$

and the laplacian is defined in the same way.

An inherit problem of the SPH is that the derivative isn't necessarily symmetric or vanishes if the quantity A is constant. One way of seeing the derivative is as the exact derivative of an approximate function. More about this can be read in (Smoothed particle hydrodynamics, J J Monaghan)

Water using particles

In short, the movement of a fluid is governed by two equations, the mass conservation equation, and the conservation of momentum.

The mass conservation equation is:
- $\frac{\partial{\rho}}{\partial{t}} + \nabla \cdot (\rho \bf{v}) = 0$
The Navier-Stokes equation formulate the conservation of momentum and is:
$\rho(\frac{\partial{v}}{\partial{t}} + \bf{v}\cdot \nabla{\bf{v}}) = -\nabla{p} + \rho \bf{g} + \mu \nabla^2\bf{v}$
where g is an external force (gravity + other), \mu is the viscosity.

One advantage of computing these equations using particles is that the equations are simplified:

Since the number of particles is constant, the mass is constant and the mass conservation equation doesn't have to be computed.
The left hand side of the second equation can be replaced with the so called substantial derivative Dv/Dt. (Müller 2003)

The navier stokes equation can then be expressed as:

$\frac{Dv}{Dt} = \frac{-\nabla{p} + \rho \bf{g} + \mu \nabla^2\bf{v}}{\rho}$
The first term of the right-hand side is the pressure term, and using the SPH equation is defined as (for particle i):
$-\nabla{p_i} = -\sum_j{m_j \frac{p_j}{\rho_j} \nabla{W(\bf{r_i} - \bf{r_j}, h)}}$
The equation above doesn't give symmetric forces when two particles interact with each other, so another formulation of this equation has to be used. There are several different variations of this described in literature, but a simple variation proposed by Müller et al, is to replace pressure of the other particle p_j with the mean pressure of the two particles (p_i + p_j)/2
The second term is external forces (gravity and other).
The third term is the viscosity term, which is defined using SPH as:
$\mu \nabla^2 \bf{v_i} = \mu \sum_j{m_j \frac{v_j}{\rho_j} \nabla^2 W(\bf{r_i} - \bf{r_j}, h)}$
Which also has the problem that it doesn't result in symmetric forces between particles. This can be corrected by instead of using the particle velocity v_j with v_i - v_j, since "the velocity forces are only dependent on velocity differences" (Müller 2003).

The pressure force depends on the different pressures on the particles, so for each timestep, a new pressure has to be computed before the acceleration is computed. This is done with the ideal gas law: p = k*\rho , where k is a gas constant. For numerical stability an offset can be used to compute the density as p = k*(\rho - \rho_0) , where \rho_0 is the rest density (of water 1000 kg/m^3).

In short the procedure to simulate water with particles is:

for each dt:
    for each particle p:
        ComputePressure()
    for each particle p:
        ComputeForces()
        UpdateVelocityAndPosition()

References

Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In Proceedings of the 2003 ACM Siggraph/Eurographics Symposium on Computer Animation (San Diego, California, July 26 - 27, 2003). Symposium on Computer Animation. Eurographics Association, Aire-la-Ville, Switzerland, 154-159.
J J Monaghan 2005 Rep. Prog. Phys. 68 1703. Smoothed particle hydrodynamics.