Graphics Reference
In-Depth Information
and practical result—where a small amount of algorithmic cleverness brings the
miraculous suddenly to hand.
To support the generalization of 1D to
k
-dimensional data structures and build
intuition for the performance of the spatial data structures, we first describe classic
1D ordered data structures and how they are characterized.
Because triangle meshes are a common surface representation and rays are
central to light transport, data structures for accelerating ray-triangle intersection
receive particular attention in this chapter and in the literature.
We select our examples from the 2D and 3D spatial data structures most com-
monly encountered in computer graphics. However, the structures described in
this chapter apply to arbitrary dimensions and have both graphics and nongraph-
ics applications.
Read the first half of this chapter if you are new to spatial data structures;
you may want to skip it if you are familiar with the concept and are looking
for details. That first half of this chapter motivates their use, explains practical
details of implementing in various programming languages, and reviews evalua-
tion methodology for data structures.
The second half of this chapter assumes that you are familiar with the concepts
behind spatial data structures. It explores four of the most commonly used struc-
tures: lists, trees, grids, and hash grids. For each, a few variations are presented;
for example, the BSP,
k
d, oct, BVH, and sphere tree variants of “trees.” The expo-
sition emphasizes the tradeoffs between structures and how to tune a specific data
structure once you have chosen to apply it.
Our experience is that it is relatively easy to understand the algorithms behind
the spatial data structures, but converting that understanding to an interface and
implementation that work smoothly in practice (e.g., ones that are efficient, con-
venient, maintainable, and general) may take years of experience.
Many graphics algorithms rely on queries that can be described by geometric inter-
sections. For example, consider an animated scene containing a ball that is moving
with constant velocity toward a pyramid of three boxes resting on the ground, as
depicted in Figure 37.2. As the ball moves along its straight-line path, the ball
traces a 3D volume called a
capsule,
which is a cylinder with radius equal to
that of the ball and capped by two hemispheres bounding all of the trailing and
leading sides of the sphere. For each discrete physical simulation time step, there
is a capsule bounding all of the ball's locations during the time. The boxes are
static, so the volume that they occupy remains constant. A collision between the
moving sphere and the boxes will occur during some time step. To determine if
the collision is in the current step, we can compute the geometric intersection of
the capsule and the boxes. If it is empty, then at no time did the ball intersect the
boxes, so there was no collision. If the intersection is nonempty, then there was
a collision and the dynamics system can respond appropriately by knocking over
the boxes and altering the ball's path.
Intersection computation is also essential for rendering. Some common inter-
section queries in graphics that arise from rendering are
•The
first
intersection of a light ray with a scene for ray casting or photon
tracing
• The intersection of the camera's view frustum with the scene to determine
which objects are potentially visible
