## Hybrid Schemes

Eulerian approaches can suffer from instability because of the
advection term (as explained below). One way to avoid the instability is to
ask, for each grid point at each time step, from where did the flow arrive? This
"backtracking" is called a semi-Lagrangian
technique, because it treats advection similarly to particle-based methods.

Conversely, discrete vortex methods require either expensive or
complicated algorithms (described above) to compute velocity. Instead of using
the Biot-Savart law, you can transfer vorticity from particles to a grid and
solve a vector Poisson equation to recover the velocity field. (Poisson solvers
are readily available.) These so-called particle-in-cell (PIC) or vortex-in-cell
(VIC) techniques also simplify computing spatial derivatives (discussed below).
Meanwhile, the basis of the simulation remains in vortons, which do not
diffuse, so VIC methods give you the relative simplicity of a grid-based method
and the lack of diffusion of a particle method.

# Numerical Methods

Numerical methods used in fluid simulation include interpolating
values between nodes, approximating spatial derivatives, solving differential
equations to evolve flow through time, and satisfying boundary conditions.

## Interpolation

You need to be able to determine values at locations other than nodes
where the simulation explicitly represents them. You do so using interpolants,
also called basis
functions, which pass through nodes.

You can choose among a variety of interpolating functions,
from local to global. Piecewise line segments provide linear interpolation
between adjacent gridpoints (Figure 6a). Instead of using only the immediately
adjacent points, you can also use a broader neighborhood of gridpoints and a
higher-order interpolant such as a piecewise cubic spline (Figure 6b). Taking
that line of thought to its logical conclusion, you can use a much higher-order
function to create a spline that spans the entire domain (Figure 6c).

**Figure 6: Interpolation
on a grid. (a) Linear. (b) Cubic. (c) Global.
**

Particle simulations can track nearest-neighbors (as a portion of
Figure 3b shows) and use interpolation techniques specialized for irregular
data. Spatial partitions such as octrees and kd-trees organize particles that
reside in the same physical neighborhood to also reside in the same data
neighborhood. You can then search the resulting tree for the nearest neighbors
of a given location.

Alternatively, you could use a hybrid PIC approach; use particles
to represent fluid properties, transfer values from particles to a grid, and
use grid-based techniques to interpolate those properties in the regions
between particles.

## Spatial Derivatives

The equations governing fluid motion include terms
involving spatial derivatives, so you need to compute those. The techniques to
approximate spatial derivatives relate directly to the interpolation
techniques.

Finite difference (FD) methods use differences of
quantities from adjacent locations divided by their separation (as shown in
Figure 7). Because they use only local information, FD methods readily handle
arbitrary, changing boundaries (for example, moving bodies in the fluid) but
have low accuracy compared to other techniques. FD is simple, flexible, and
effective and so is a good choice for video games, where accuracy is not
paramount.

**Figure 7: Finite
differences. (a) Forward, (b) backward, and (c) centered.
**

Spectral methods use interpolating functions spanning multiple
values in the domain, and you can compute derivatives of those functions
analytically. Spectral methods offer higher accuracy but because they use
global (or less local) information, the domain shape and boundary conditions
impose constraints that determine which functions work well to represent the
flow field.

Spectral methods come in two varieties: collocation and Galerkin. Collocation
techniques use values arranged in a spatial domain, as depicted above. Galerkin
methods use an abstract domain, analogous to the frequency domain for audio
signals. Hybrid collocation-Galerkin methods also exist.

These techniques to approximate spatial derivatives equip you
with the ability to compute each term in the governing equations.

By replacing derivatives in the continuous equations with
approximation, you convert the continuous equations with a discretized form. When
using FDs, this means the continuous PDE's change into a system of linear
algebraic equations. For example, replacing the gradient with a centered difference, the continuous equation

becomes the spatially discrete equation

After plugging approximated spatial derivative values into
the original fluid dynamics equations we must also discretize those equations
in time to create an algorithm to update the simulation for each new step in
time.