Graphics Reference
In-Depth Information
Chapter 37
Spatial data structures,
such as the oct tree (Figure 37.1), are the multidimen-
sional generalization of classic ordered data structures, such as the binary search
tree. Because spatial data structures generally trade increased storage space for
decreased query time, these are also known as
spatial acceleration data struc-
tures.
Spatial data structures are useful for finding intersections between different
pieces of geometry. For example, they are used to identify the first triangle in a
mesh that is intersected by a ray of light.
The development and analysis of spatial data structures is an area in which the
field of computer graphics has contributed greatly to computer science in general.
The practice of associating values with locations in spaces of various dimensions
is of use in many fields. For example, many machine learning, finite element anal-
ysis, and statistics algorithms rely on the data structures originally developed for
rendering and animation.
The ray-casting renderer in Chapter 15 represented surfaces in the scene using
an unordered list of triangles. This chapter describes how to abstract that list
with an interface. Once the implementation is abstracted, we can then change that
implementation without constantly rewriting the ray caster. Why would we change
it? Introductory computer science courses present data structures that improve the
space and time cost of common operations. In this chapter we apply the same ideas
to 3D graphics scenes. Of course, when comparing 3D points or whole shapes
instead of scalars, we have to adjust our notions of “greater than” and “less than,”
and even “equals.”
The original ray caster could render tens of triangles in a reasonable amount of
time—maybe a few minutes, depending on the image resolution and your proces-
sor speed. A relatively small amount of elegant programming will speed this up
by an amazing amount. Even a naive bounding volume hierarchy should enable
your renderer to process millions of triangles in a few minutes. We hope you'll
share the joy that we experienced when we first implemented this speedup. It is
a great instance of algorithmic understanding leading directly to an impressive
Figure 37.1: A gargoyle model
embedded in an oct tree. The
cube volume surrounding the
model is recursively subdivided
into smaller cubes, forming a tree
data structure that allows effi-
cient spatial intersection queries
compared to iterating exhaus-
tively over the triangles in the
mesh. The boundaries of the
cube cells are visualized as thin
lines in this image. (Courtesy of
Preshu Ajmera.)
1065
