Game Development Reference
generally causes a more gaseous behavior of the fluid. We will refrain from mak-
ing any recommendation on the value of k because of its artistic implications.
Instead, we will discuss its effects on stability and behavior in Section 6.6.
6.4.2 Grid-Cell-Based Spatial Hashing
Section 6.4.1 discussed the choice of a spatial hash as data structure for our fluid
simulation. It also discussed the choice of spatial hash and fluid-simulation pa-
rameters, with their effects on computational efficiency. Section 6.5 will change
the structure of the SPH algorithm to decrease the computational burden of find-
ing neighbors and iterating over fluid particles multiple times. Section 6.7 will
show that despite these improvements, the majority of the computational burden
still falls to the nearest-neighbor search, even more so than in the actual evaluation
of the SPH equations.
To decrease the work required for the nearest-neighbor search, we propose a
slight change in the structure of the original spatial hash, as described in [Teschner
et al. 03]. The change is meant to minimize the number of potential neighbors
visited during a spatial hash query.
In the original spatial hash, as shown in Figure 6.2, multiple grid cells map
to a single hash bucket, since we have an infinite number of grid cells but only
a limited number of hash buckets. If multiple grid cells contain fluid particles,
fluid particles from two spatially unrelated grid cells may be inserted into the
same hash bucket, causing a hash collision. The number of hash collisions can be
minimized by increasing the number of hash buckets. However, hash collisions
can rarely be avoided in practice; the fluid-simulation configuration is free to take
on any shape, including those producing collisions. As a result, during a query of
the hash at a fluid-particle position, all particles in the corresponding hash bucket
are visited, including the ones that are spatially unrelated.
The goal of our structural change is to speed up querying: we keep the hash
function enabling us to find a list of potential neighbors with O (1) time complex-
ity, while eliminating iteration over particles that do not belong to the grid cell
Figure 6.4 shows the modified hash structure, which we refer to as a grid-
cell-based spatial hash . At the topmost level we keep a hash table, but instead of
storing a bucket of fluid particles, the bucket now contains a list of grid cells—the
middle layer. Every grid cell element consists of its discretized grid cell coor-
dinates and a list of fluid particles belonging to the grid cell. The list of fluid
particles is represented by the bottom layer in Figure 6.4.
Insertion of a fluid particle into the grid-cell-based spatial hash proceeds as