Game Development Reference
In-Depth Information
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
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
Search Nedrilad ::

Custom Search