Game Development Reference
Figure 7.5. Uniform grid (left), hash grid (middle), and hierarchical grid (right). The uni-
form grid allocates memory for an entire domain. The hash grid maps a voxel to a memory
array using the hash function. The hierarchical grid only subdivides voxels containing
grid is memory inefficient and a hash grid is not suited for implementation on the
GPU because of the hash collision. Construction of a grid and accessing a voxel
is computationally expensive in a hierarchical grid.
The sliced grid, developed by [Harada et al. 07], is another option. This is
a grid whose construction cost is low, has easy access to a voxel, and requires a
small footprint. So we chose the sliced grid for the acceleration structure for our
neighboring-particle search. In the following, a short introduction of the sliced
grid is presented, followed by an implementation on the GPU using CUDA.
7.4.2 Sliced Grid
When a uniform grid is used, a bounding box is defined to enclose the computa-
tional domain, and memory for the voxels inside of the bounding box is allocated
whether a voxel is occupied or not by a particle, as shown in Figure 7.6 (left). We
can see that a large amount of memory is wasted because it allocates memory for
unused voxels. However, the sliced grid allocates memory, as shown in Figure
7.6 (right). The procedure to build a grid starts by scanning the space for the grid
cells filled with particles. Of course, it is possible to identify voxels containing
particles by scanning the whole space, but there is a cost for that. The sliced grid
increases the memory efficiency by adding a little computation.
First of all, orthogonal basis vectors ( e x , e y , e z ) and a uniform grid along the
bases in the computational domain are prepared. Note that the grid is not allocated
in the memory at this time. The first step is the scanning of the number of voxels
required to store the data.
An axis is chosen from the bases, and the grid in the domain is divided into
slices perpendicular to the axis. Each slice has a one-voxel thickness in the di-
rection of the axis. Thus, the slices have one dimension less than the spatial