Game Development Reference
InDepth Information
dimension of the computation domain. A sliced grid allocates memory for the
twodimensional 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 (twodimensional 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 xdirection) (right).