i
i
i
i
i
i
i
i
12.3. Spatial Data Structures 279
We will use ray tracing as the primary motivation while discussing these struc-
tures, though they can all also be used for view culling or collision detection. In
Chapter 4, all objects were looped over while checking for intersections. For N
objects, this is an O(N) linear search and is thus slow for large scenes. Like most
search problems, the ray-object intersection can be computed in sub-linear time
using “divide and conquer” techniques, provided we can create an ordered data
structure as a preprocess. There are many techniques to do this.
This section discusses three of these techniques in detail: bounding volume hi-
erarchies (Rubin & Whitted, 1980; Whitted, 1980; Goldsmith & Salmon, 1987),
uniform spatial subdivision (Cleary et al., 1983; Fujimoto et al., 1986; Ama-
natides & Woo, 1987), and binary space partitioning (Glassner, 1984; Jansen,
1986; Havran, 2000). An example of the first two strategies is shown in Fig-
ure 12.22.
12.3.1 Bounding Boxes
A key operation in most intersection-acceleration schemes is computing the in-
tersection of a ray with a bounding box (Figure 12.23). This differs from conven-
tional intersection tests in that we do not need to know where the ray hits the box;
we only need to know whether it hits the box.
To build an algorithm for ray-box intersection, we begin by considering a 2D
ray whose direction vector has positive x and y components. We can generalize
this to arbitrary 3D rays later. The 2D bounding box is defined by two horizontal
and two vertical lines:
Figure 12.23. The ray is
only tested for intersection
with the surfaces if it hits the
bounding box.
x = x
min
,
x = x
max
,
y = y
min
,
y = y
max
.
The points bounded by these lines can be described in interval notation:
(x, y) ∈ [x
min
,x
max
] × [y
min
,y
max
].
As shown in Figure 12.24, the intersection test can be phrased in terms of these
intervals. First, we compute the ray parameter where the ray hits the line x =
x
min
:
t
xmin
=
x
min
− x
e
x
d
.