Game Development Reference
7.4.1 Requirements for Particle-Based Simulation
The data structures introduced to make neighboring-particle search efficient are
classified into three categories: uniform grids, hash grids, and hierarchical grids,
all illustrated in Figure 7.5. There are two major requirements for a grid used in
particle-based simulations. The first is that the construction cost is low enough to
be reconstructed at every time step. The other requirement is that it should be easy
to access the memory of the voxel to which a particle belongs, because the data
stored in the memory is frequently referred to in a simulation. There is actually
another condition—although it is not necessarily required, but is preferable—a
smaller memory footprint. In the following, we discuss these points in the three
grids: uniform grid, hash grid, and hierarchical grid.
The uniform grid allocates the memory for all the voxels in the computation
domain whether it is occupied by particles or not. This simple nature keeps the
construction and access costs low. Although the uniform grid satisfies the two
requirements, it needs a large memory to hold the data for all the voxels in the
computation domain. There can be a large number of empty voxels, storing no
particles, which is nothing but a waste of memory.
The hash grid improves on the uniform grid by not allocating all the voxels.
Instead, it maps the voxels to a fixed-sized array by using the hash function. It
looks to be a good candidate, but it suffers from hash collision, in which several
voxels are mapped to the same location because the hash grid cannot guarantee a
perfect hash. When the grid is accessed, the stored values have to be checked to
see whether they are in the same voxel or not. So the access cost is more than it
is in the uniform grid.
The hierarchical grid improves the memory efficiency a lot. Figure 7.5 (right)
shows a quad tree (correspondence to the three-dimensional case is octree), which
divides a cell with a valid entry. The top level of the tree is the bounding box of
the input data. A node with an entry will be divided into four nodes; this is done
recursively when the criteria are met. It avoids allocation of memory for empty
space by using hierarchical representation. The drawback of the hierarchy is the
access cost of a leaf node. Unlike the uniformgrid, it cannot calculate the memory
address directly from the position of the query. Instead, it has to traverse the tree
structure from the root of the tree.
We now parallelize particle-based simulations on multiple processors, which
has some additional requirements. One requirement is that all the computations
are parallelized. Especially when using a GPU, the entire algorithm should be
performed on the GPU; otherwise, data have to be transferred between the GPU
and the CPU. Another consideration is that a uniform computation burden is pre-
ferred to keep the load balance uniform. To summarize this discussion, a uniform