Game Development Reference

In-Depth Information

H(x)

Figure 6.2.
The structure of a spatial hash as described by [Teschner et al. 03]. A fluid

particle—the black dot at the top—is mapped to a table of hash buckets of fixed size—the

grid in the middle—by a hash function
H
(
x
)
. Every hash bucket references a list of fluid

particles, which is represented by the bottom layer. Note that this figure shows only the

concept of the structure; it is not representative of the memory layout for an optimized

implementation.

query phase
. This section will focus on the choices that can be made during the

design of a spatial hash and their effect on computational efficiency, both in the

construction phase and in the query phase.

Hash construction can be performed from scratch each frame or incrementally.

In both cases, an efficient implementation keeps particles belonging to the same

hash bucket in a contiguous block of memory, to avoid cache misses during a

query of the spatial hash. Construction from scratch is possible by placing all

fluid particles in a contiguous block of memory and (radix) sorting them based

on their hash index. Each particle stores its hash index along with its state, so

constructing the hash table only requires an iteration through the list of particles

to find the start of each hash bucket. For parallel implementations, a radix sort

is suitable as well, and constructing the hash table follows from the sorted list

of particles as a compaction step, where each first hash bucket element writes a

reference to itself into the corresponding hash bucket of the hash table. Radix

sort and compaction for parallel architectures like a GPU is explained in detail

by [Harris et al. 07].

To construct the spatial hash incrementally, inserted fluid particles are not

removed from the spatial hash at every frame. Instead, particles are relocated

whenever they move to another hash bucket. This method performs well if par-

ticles do not move around too much between consecutive frames. Ideally, hash

buckets are represented by contiguous blocks of memory; each hash bucket is