Game Development Reference

In-Depth Information

[
x
i
]
1
using a symplectic Euler integration scheme:

[
v
i
]
1
=[
v
i
]
0
+[
a
i
]
0

t,

[
x
i
]
1
=[
x
i
]
0
+[
v
i
]
1

t,

t
0
. We chose a symplectic Euler scheme over normal Euler

integration because it has better energy-conservation properties [Ruth 83].

When [
x
i
]
1
is known, the algorithm repeats itself for the next time step.

t
=
t
1
−

where

6.4 The Choice of Data Structure

6.4.1 Spatial Hashing

The SPH equations that have to be evaluated per fluid particle are defined by

Equations (6.2), (6.6) and (6.7) in Section 6.2. Each of these equations is a sum-

mation over attributes of every fluid particle in the simulation. Obviously, a full

quadratic evaluation is wasteful to perform in practice, as a certain fluid particle

only influences other particles within a radius
h
of its position. Overall, evaluat-

ing the SPH equations in Steps 1 and 2 of Figure 6.1 is more expensive than the

velocity and position integration in Step 3, which only has a complexity linear in

the amount of fluid particles.

The process of finding a particle's neighboring particles can be accelerated

by using a data structure. Most SPH simulations employ a spatial hash, as de-

scribed by [Teschner et al. 03], which can also be used in the case of parallel

execution [Green 08]. The structure of a spatial hash is shown in Figure 6.2.

A spatial hash consists of a hash table, with each entry called a hash bucket.

Hash buckets are—in the case of an SPH simulation—lists of fluid particles. Fluid

particles are mapped to hash buckets based on their position
x
i
using a hash func-

tion
H
(
x
), indexing into the hash table.

A property of the hash function is that it discretizes three-dimensional space

into grid cells and maps each grid cell to the limited number of hash buckets

available in a uniformly random fashion. So regardless of the spatial configuration

of grid cells that participate in the fluid simulation—the ones that contain fluid

particles—they are uniformly distributed over the available hash buckets.

Constructing a spatial hash is of time complexity
O
(
n
), while a single query

is of time complexity
O
(
q
), with
q
being the number of fluid particles mapping to

a single hash bucket within the spatial hash. Construction of the hash structure is

performed in the
construction phase
, which takes place immediately after the fluid

particle locations are known, before Step 1 in Figure 6.1. Querying is performed

during Step 2—the density and force calculations—which is referred to as the