i
i
i
i
i
i
i
i
3
VII
Simple and Fast Fluids
Martin Guay, Fabrice Colin, and Richard Egli
3.1 Introduction
In this chapter, we present a simple and efficient algorithm for the simulation
of fluid flow directly on the GPU using a single pixel shader. By temporarily
relaxing the incompressibility condition, we are able to solve the full Navier-
Stokes equations over the domain in a single pass.
3.1.1 Simplicity and Speed
Solving the equations in an explicit finite difference scheme is extremely simple.
We believe that anybody who can write the code for a blur post-process can
implement this algorithm and simulate fluid flow efficiently on the GPU. The code
holds is less then 40 lines and is so simple we actually had the solver running in
FxComposer (see FxComposer demo). Solving every fluid cell (texel) locally in a
single pass is not only simple, but also quite fast. In fact, the implementation of
Figure 3.1. 3D simulation with 100k particles visualization.
433
i
i
i
i
i
i
i
i
434 VII GPGPU
this algorithm on the GPU is at least 100 times faster than on the CPU.
1
In this
chapter, we show how to couple the two equations of the classical Navier-Stokes
equations into a single-phase process; a detailed explanation of the algorithm
along with example code follows.
3.2 Fluid Modeling
The greatest feature of physics-based modeling in computer graphics is the abil-
ity of a model to cope with its environment and produce realistic motion and
behavior. Attempting to animate fluids nonphysically is, in our experience, a
nontrivial task. In order to physically model the motion of fluids, the simplified
classical Navier-Stokes equations for incompressible fluids are a good description
of such mechanics, and a solver based on this model is capable of simulating a
large class of fluid-like phenomena. Fortunately a deep understanding of the par-
tial differential equations involved is not required in order to implement such a
solver.
3.2.1 Navier-Stokes Equations
The Navier-Stokes equations, widely used in numerous areas of fluid dynamics,
are derived from two very simple and intuitive principles of mechanics: the con-
servation of momentum (Equation (3.1)) and the conservation of mass (Equation
(3.2)).
ρ
∂u
∂t
+ u · ∇u
= −∇P + ρg + µ∇
2
u, (3.1)
where u is a velocity vector, g is the gravitational acceleration vector, µ the
viscosity, P the pressure and ∇
2
stands for the Laplacian operator ∂
2
/∂x
2
+
∂
2
/∂y
2
+ ∂
2
/∂z
2
.
∂ρ
∂t
+ ∇ · (ρu) = 0, (3.2)
where ∇· represents the divergence operator. These equations also have to be
supplemented with boundary conditions of Dirichlet, Neumann, or even of Robin
type. Usually, the incompressibility condition (see Equation (3.3)) is imposed on
the fluid by assuming that its density ρ remains constant over time. Using the
latter assumption, Equation (3.2) simplifies to
∇ · u = 0. (3.3)
1
The simulation runs on the CPU at 8.5 fps with 4 threads on an Intel Core 2 Quad at 2.66
GHz simulating only the velocity field over a 256 × 256 grid. Keeping the same grid size, the
simulation of both velocity and density fields runs at more than 2500 fps on a Geforce 9800
GT using 32-bit floating point render targets. Note that 16-bit floating point is sufficient to
represent velocities.
i
i
i
i
i
i
i
i
3. Simple and Fast Fluids 435
Now one of the main features of the formulation of the Navier-Stokes equations
illustrated here, is the possibility, when working with regular grid domains, to
use classical finite differences schemes.
3.2.2 Density-Invariance Algorithm
Unfortunately, a direct application of Equation (3.1) results in a nonzero diver-
gence field u (i.e. (3.3) is no longer satisfied by the vector field u). A lot of
popular methods for simulating fluids consist of two main steps. First some tem-
porary compressibility is allowed when Equation (3.1) is solved, and second, a
correction is applied to the vector field obtained, in order to fulfill the incom-
pressibility condition. This correction can be done by considering a projection
of the resulting vector w field onto its divergence-free part [Stam 99]. The latter
projection can also be performed in the spirit of the smoothed particle hydrody-
namics (SPH) method (see for instance [Colin et al. 06]). Another way to deal
with this incompressibility problem is to take advantage of the relation between
the divergence of the vector field and the local density given by Equation (3.2),
by trying to enforce a density invariance (see among others, [Premoˇze et al. 03]).
Recently, some techniques combining the two preceding approaches were stud-
ied (for an exhaustive study of all the previous techniques in the SPH context,
see [Xu et al. 09]).
We choose an approach based on density invariance. It is interesting to note
that an algorithm based on the previous approach has proven to be stable for
the SPH method [Premoˇze et al. 03]. First, observe that Equation (3.2) can be
rewritten as
∂ρ
∂t
= −∇ρ · u − ρ∇ ·u,
clearly illustrating the link between the divergence of the vector field and the
variation of the local density. After solving the above equation for density, a
corrective pressure field could simply be given as
P = K(ρ
n
− ρ
0
), (3.5)
where ρ
0
is the rest (initial) density and where the constant K is often cho-
sen according to the gas-state equation (see [Desbrun and Cani 96] or [Muller
et al. 03]).
The corrective field P (a density-invariant field) could be interpreted as an
internal pressure whose gradient corrects the original velocity field to get a null
divergence vector field. Since we are interested only in its derivative, there is no
need to retain the P variable and the corresponding correction to be applied is
simply given by
∇P = K∇ρ.
Now before jumping directly to code, we first need to discretize the formulation.
i
i
i
i
i
i
i
i
436 VII GPGPU
3.2.3 From Math to Code: Numerical Scheme
One of the main features of the formulation used in this chapter is the ability to
use, along a regular grid, simple finite differences. Since the texture is the default
data structure on a GPU, a regular grid holding four values per cell is a natural
choice for the spatial discretization of the domain. Also, since this is an Eulerian
formulation, the spatial discretization stays fixed throughout the simulation and
the neighborhood of an element, the elements (in our case, the texels) around it,
will always remain the same, greatly simplifying the solver’s code.
The simplicity of finite differences along a one-phase coupling of both momen-
tum and mass conservation equations through a density-invariant field enables the
elaboration of a very simple algorithm to solve fluid flow in a single step. Note
that other grid-based methods on the GPU exist and the interested reader can
refer to [Crane et al. 07] for a multistep but unconditionally stable simulation or
to [Li et al. 03] (also available in GPU Gems 2 ) for a lattice-based simulation.
3.3 Solver’s Algorithm
A solution to the Navier-Stokes equations is a vector-valued function u and a
scalar-valued function ρ which satisfies the momentum and mass conservation
equations. These functions are spatially discretized on a texture where quantities
u and ρ are stored at the texel’s center. In order to update a solution u and ρ
from time t
n
to time t
n+1
, we traverse the grid once and solve every texel in the
following manner:
1. Solve the mass conservation equation for density by computing the differ-
ential operators with central finite differences and integrating the solution
with the forward euler method.
2. Solve the momentum conservation equation for velocity in two conceptual
steps:
(a) Solve the transport equation using the semi-Lagrangian scheme.
(b) Solve the rest of the momentum conservation equation using the same
framework as in Step 1.
3. Impose Neumann boundary conditions.
3.3.1 Conservation of Mass
In order to compute the right-hand side of the mass conservation equation, we
need to evaluate a gradient operator ∇ for a scalar-valued function ρ and a di-
vergence operator ∇· for a vector-valued function u both, respectively, expressed
i
i
i
i
i
i
i
i
3. Simple and Fast Fluids 437
using central finite differences as follows:
∇ρ
n
i,j,k
=
ρ
n
i+1,j,k
− ρ
n
i−1,j,k
2∆x
,
ρ
n
i,j+1,k
− ρ
n
i,j−1,k
2∆y
,
ρ
n
i,j,k+1
− ρ
n
i,j,k−1
2∆z
,
∇ · u
n
i,j,k
=
u
n
i+1,j,k
− u
n
i−1,j,k
2∆x
+
v
n
i,j+1,k
− v
n
i,j−1,k
2∆y
+
w
n
i,j,k+1
− w
n
i,j,k−1
2∆z
.
And finally, an integration is performed using forward Euler over a time step
∆t:
ρ
n+1
i,j,k
= ρ
n
i,j,k
+ ∆t(−∇ρ
n
i,j,k
· u
n
i,j,k
− ρ
n
i,j,k
∇ · u
n
i,j,k
).
Indeed, there exist other finite difference schemes. For instance, one could use
upwinding for the transport term or literally semi-Lagrangian advection. Unfor-
tunately, the latter results in much numerical dissipation; an issue covered in
Section 3.3.2.
3.3.2 Conservation of Momentum
We solve the momentum conservation equation for velocity u in two conceptual
steps. The first consists of solving the transport equation
∂u
∂t
= −u · ∇u with
a semi-Lagrangian scheme, then solving the rest of the momentum conservation
equation (
∂u
∂t
= −
∇P
ρ
+ g +
µ
ρ
∇
2
u) with central finite differences and forward
Euler integration.
Semi-Lagrangian scheme. First introduced to computer graphics by Jos Stam in
the paper Stable Fluids [Stam 99], the following scheme is quite useful for solving
the generic transport equation given by
∂φ
∂t
= −u · ∇φ, (3.8)
at the current texel’s position x
i,j,k
with
φ
n+1
i,j,k
(x
i,j,k
) = φ
n
(x
i,j,k
− ∆tu
n
i,j,k
). (3.9)
The idea is to solve the transport equation from a Lagrangian viewpoint where
the spatial discretization element holding quantities (e.g., a particle) moves along
the flow of the fluid, and answer the following question: where was this element
at the previous time step if it has been transported by a field u and ends up
at the current texel’s center at the present time? Finally, we use the sampled
quantity to set it as the new value of the current texel.
Now when solving the transport equation for velocity, Equation (3.8) becomes
∂u
∂t
= −u · ∇u and is solved with
u
n+1
i,j,k
(x
i,j,k
) = u
n
(x
i,j,k
− ∆tu
n
i,j,k
).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.