[This sponsored feature, part of Intel's Visual Computing site and written by Dr. Michael J. Gourlay of the University of Central Florida Interactive Entertainment Academy, continues a multi-part series that explains fluid dynamics and its simulation techniques. For the first instalment, please click here.]

Fluid Simulation Techniques

As explained in the previous article, non-linear partial differential equations (PDE's), combined with initial and boundary value constraints, describe the motion of fluids. Solving those equations is difficult; unlike simpler like ballistic trajectories or harmonic oscillations, fluid motion has no "closed-form" analytical solution. This article describes numerical techniques used to compute approximate solutions to fluid motion.

The difference between reality and simulation includes at least two aspects: approximation and discretization. The equations we write down are only approximations of reality. For example, the notion of "viscosity" oversimplifies the actual interactions between molecules. Also, fluids are continuous media, meaning that they exist at an infinite number of points in a region of space. Computer simulations convert the mathematical model of fluids from a continuum into a finite number of discrete values. Those values can reside in a mesh, or they can move freely as particles.

Recall from the previous article that to calculate fluid motion, you can solve for either momentum or vorticity. You can categorize fluid simulation techniques according to which equations they solve and according to their discretization scheme. This article presents the ideas behind these techniques:

• Mesh+momentum. Examples include Jos Stam's "stable fluids" and Mick West's "practical fluid mechanics."
• Particles+momentum. Examples include smoothed particle hydrodynamics (SPH).
• Mesh+vorticity. Researchers in computational fluid dynamics (CFD) use these techniques, but they currently have less popularity in computer graphics.
• Particles+vorticity. These are called vorton simulations.

Fluid simulations run slowly (in part) because of the need to use a large number of points to represent a continuum. You can speed up simulations by employing approximations (that is, trading realism for speed). You can also parallelize the computation and make use of multicore hardware, which is becoming increasingly prevalent. This article reviews some numerical techniques often employed to simulate fluid motion and mentions some ways in which you can parallelize numerical codes to use multi-core hardware.

Discretization

When solving fluid dynamics equations numerically, you convert the original continuous problem (which has infinite degrees of freedom) into a discrete problem (which has finite degrees of freedom). The choice of discretization scheme influences other aspects of the simulation, including interpolation, approximating spatial derivatives, evolving in time, and satisfying boundary conditions. That discretization process has many forms -- too many to cover here -- so this article focuses on intuitive formulations: Discretize space, approximate spatial derivatives using that discretization, and rewrite the continuous equations by replacing spatial derivatives with those approximations.

The previous article presented Eulerian (fixed-coordinate) and Lagrangian (moving-coordinate) views of the fluid momentum and vorticity equations. Analogously, you can discretize space using grids, particles, or a hybrid of the two. Regardless of whether they use grid-based or mesh-free discretization, we give the name nodes to locations where the simulation explicitly represents values.

Grid-based Discretization

Grid-based discretizations are useful for Eulerian views -- that is, treating fluids as fields whose properties the simulation tracks at specific locations. Deciding on a specific grid to represent a field is called meshing.

The simplest is a uniform fixed grid, as Figure 1a depicts: Divide space into cells at equal intervals along the axes of the coordinate system. This allows fast lookups, because you can directly compute the memory address of a grid cell based on its location in the virtual world. Uniform grids can, however, be wasteful; in a typical flow, some regions need very high resolution, but most can use low resolution. With a uniform grid, all regions have the same resolution, so they typically over-resolve some regions and under-resolve others.

Simulations can also use an adaptive grid, which provides high spatial resolution only where needed -- for example, where vortices form and near boundaries, as Figure 1b shows. Creating such a grid can be complicated, especially when boundaries move, such as when objects move in the fluid. Also, space-based lookups are slower for adaptive grids than for uniform grids, because they entail traversing more complicated spatial partitioning data structures.

Figure 1: (a) A uniform fixed grid; (b) an adaptive grid

Recall from the previous article that certain governing equations describe fluid motion. Each equation describes the time evolution of a fluid property such as velocity and density. The recipe for a grid-based fluid simulation usually entails computing the terms of those governing equations and updating each of those properties at each grid point. Most of the effort lies in computing those terms and performing the update robustly, which this article delves into later. But in principle (if not in practice), the recipe is that simple.

If you want to know the value of a fluid property between grid points, you have to interpolate. You could use a variety of techniques to perform that interpolation, and this relates to how to compute spatial derivatives, which this article covers in more detail below.

Simulations using grid-based discretizations can suffer from unwanted numerical diffusion. You can understand this phenomenon by employing an analogy to image creation and processing. If you draw a diagonal line through a grid of pixels, you have to choose between making the line jagged or blurry: There is no way to represent a line exactly at every position along the line using a discrete grid. This problem worsens each time you move the line: After each update, it gets blurrier and noisier, as Figure 2 shows. Computer graphics applications prevent this incremental blur by storing and operating on idealized representations of lines (such as pairs of points). Computational fluid dynamics has a loosely analogous technique: store and operate on idealized fluid particles.

Figure 2: Numerical diffusion. The original line is rotated 180 degrees in increments.