Stam, J. (1999). Stable Fluids. Proceedings Of the 26th Annual Conference on Computer Graphics and Interactive Techniques. doi:10.1145/311535.311548

Summary

This paper introduces the first stable fluid simulation algorithm for computer graphics. This is a hard problem, because there is not analytic solution to Navier-Stokes. Previous methods had used explicit approximations such as Eulerian methods; however, these types of methods can become unstable and “blow up” for large timesteps. Using small enough timesteps is not a feasible option in computer graphics, in which the simulation needs to run in real time, thus prohibiting small timesteps.

This algorithm is specific to contained fluids (i.e., gases) and approximates the following form of Navier-Stokes:

where $\nabla\cdot{}\mathbf{u}=0$. Here, $\mathbf{u}$ is the velocity field, $\nabla$ is a vector of spatial partial derivatives, $\nu$ is the kinematic viscosity of the fluid, $\mathbf{f}$ is an external force, and $\mathbf{P}$ is a projection operator which projects any vector field onto its divergence free part. Divergence free essentially means that at any point in the vector field, the flow towards that point is the same as the flow away from it.

They compute the approximate solution to this equation in four steps. First, $\mathbf{w}_0$ is the solution from the previous time step:

Then, the first step is to add force:

The second step is advection:

where $\mathbf{p}(\mathbf{x},-\Delta t)$ says that the new velocity at $\mathbf{x}$ is the velocity at a location backwards in time by $-\Delta t$ (i.e., something like the velocity at the location given by $\dot{\mathbf{x}}\ \Delta t)$.

The third step is diffusion, in which the effects of viscosity are applied and solved as a linear system:

The fourth and final step is projection, in which the system is projected back onto its divergence free part.