Game Development Reference
[ x i ] 1 using a symplectic Euler integration scheme:
[ v i ] 1 =[ v i ] 0 +[ a i ] 0
[ x i ] 1 =[ x i ] 0 +[ v i ] 1
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 −
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