Game Development Reference

In-Depth Information

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

being queried.

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

follows: