Game Development Reference
In-Depth Information
dimension of the computation domain. A sliced grid allocates memory for the
two-dimensional bounding boxes for each slice. By not excluding empty voxels
completely, it keeps the computation cost low. When e x is chosen as the axis,
the slice is spread over the space of the bases e y and e z . The following expla-
nation assumes that the coordinate in the grid space of a point x =( x, y, z ) is
b =( b x ,b y ,b x )=( x
e z ). After dividing the computational space
into slices, the bounding box (two-dimensional in this case) for each slice is cal-
culated by scanning the grid coordinates of all the particles. The maximum and
minimum of y and z of slice i are
·
e x , x
·
e y , x
·
B i, max =max j∈P i {
b j }
B i, min =min j∈P i {
b j }
,
,
B i, max =max j∈P i {
b j }
B i, min =min j∈P i {
b j }
,
,
b j = i
where P i =
.
With these values, the number of voxels in the y -and z -directions are com-
puted as
{
j
|
}
= B i, max −B i, min
d
n i
+1 ,
= B i, max −B i, min
d
n i
+1 ,
where d is the side length of the voxels. This bounding box with n i = n i n i
voxels in a slice is allocated in memory. This is much more efficient than using
the uniform grid, although it still has some empty voxels. The index of a voxel at
( x, y, z ) at slice i can be calculated by
v i ( x, y, z )= ( y
B i, min ) /d + ( z
B i, min ) /d n i .
(7.3)
Placing the memory for slices in a contiguous memory requires the offsets or the
indices of the first voxels of the slices. Let the index of the first voxel of slice i be
Figure 7.6. Uniform grid (left) and sliced grid(sliced in the x-direction) (right).