Graphics Reference
In-Depth Information
that holds for classic data structures: e.g., A hash table is neither better nor worse
than a binary search tree in general; they are appropriate for different kinds of
applications. With spatial data structures, a list of boxes may be a good fit for a
small scene. For a large scene, a binary space partition tree may be a better choice.
The art of algorithm and system design involves selecting among alternative
data structures and algorithms for a specific application. In doing so, one consid-
ers the time, space, and implementation complexity in light of the input size and
characteristics, query frequency, and implementation language and resources. The
rest of this chapter explores those issues.
Spatial data structures are typically implemented as
polymorphic types.
That is,
each data structure is parameterized on some primitive type that in this chap-
ter we'll consistently name
Value
. For example, in most programming languages
you don't just instantiate a list; instead, you make a list of something. These are
known as
templated classes
in C++ and C# and
generics
in Java. Languages
like Scheme, Python, JavaScript, and Matlab rely on runtime dynamic typing
for polymorphic types, and languages like ML use type inference to resolve
the polymorphism at compile time. The three popular graphics OOP languages
Java/C++/C# use angle-bracket notation for this polymorphism, so we adopt it too
(e.g.,
List<Triangle>
is the name of a structure representing a list of triangles).
Throughout this chapter, we assume that
Value
is the type of the geometric
primitive stored in the data structure. Common primitive choices include triangle,
sphere, mesh, and point. A value must support certain spatial queries in order to
be used in building general spatial data structures. We describe one scheme for
abstracting this in Section 37.2.2.2. Briefly, a data structure maps keys to values.
For a spatial data structure the keys are geometry and the values are the proper-
ties associated with that geometry. One frequently implements the key and value
as different interfaces for the same object through some polymorphic mechanism
of the implementation language. For example, a building object might present a
rectangular slab of geometry as a
key
for arrangement within a data structure but
also encodes as a
value
information about its surface materials, mass, occupants,
and replacement cost for simulation purposes. Note that depending on the appli-
cation, the key might assume radically different forms, such as a finely detailed
mesh, a coarse bounding volume on the visible geometry, or even a single point
at the center of mass for simulation purposes. The same value may be represented
by different keys in different data structures, but extracting a specific class of key
from a value must be a deterministic process for a specific data structure.
Beware that the use of the data-structure term “key” here is consistent with
the general computer science terminology employed throughout the chapter, but
it is uncommon in typical graphics usage. Instead, keys that are volumes are often
called
bounding geometry, bounding volumes
[RW80], or
proxies.
In this chapter, we use the variable name
key
to represent whatever form of
geometric key is employed by the data structure at that location in the implemen-
tation. The type of the key depends on the data structure and application. We also
use the name
value
, which will always have class
Value
.
In terms of an application interface, the methods implementing the intersec-
tion queries may be framed precisely to return the geometric intersections (see
