i
i
i
i
i
i
i
i
12.3. Spatial Data Structures 287
Figure 12.29. Although the pattern of cell hits seems irregular (left), the hits on sets of
parallel planes are very even.
Our first order of business is to find the index (i, j) of the first cell hit by
the ray e + td. Then, we need to traverse the cells in an appropriate order. The
key parts to this algorithm are finding the initial cell (i, j) and deciding whether
to increment i or j (Figure 12.30). Note that when we check for an intersection
Figure 12.30. To decide
whether we advance right
or upwards, we keep track
of the intersections with the
next vertical and horizontal
boundary of the cell.
with objects in a cell, we restrict the range of t to be within the cell (Figure 12.31).
Most implementations make the 3D array of type “pointer to surface.” To improve
the locality of the traversal, the array can be tiled as discussed in Section 12.5.
12.3.4 Axis-Aligned Binary Space Partitioning
Figure 12.31. Only hits
within the cell should be re-
ported. Otherwise the case
above would cause us to re-
port hitting object
b
rather
than object
a
.
We can also partition space in a hierarchical data structure such as a binary space
partitioning tree (BSP tree). This is similar to the BSP tree used for visibility
sorting in Section 12.4, but it’s most common to use axis-aligned, rather than
polygon-aligned, cutting planes for ray intersection.
A node in this structure contains a single cutting plane and a left and right
subtree. Each subtree contains all the objects on one side of the cutting plane.
Objects that pass through the plane are stored in in both subtrees. If we assume
the cutting plane is parallel to the yz plane at x = D, then the node class is:
class bsp-node subclass of surface
virtual bool hit(ray e + td, real t
0
, real t
1
, hit-record rec)
virtual box bounding-box()
surface-pointer left
surface-pointer right
real D