Graphics Reference
In-Depth Information
has not been well researched; that is a large part of how the field moves forward.
In any given year there will be several new papers on strategies for placing the
partitions in a spatial tree or clustering for BVHs. For example, in 1987, one good
idea was to build a ray-primitive intersection structure that took the ray's direction
into account [AK87]; in 2000, Havran's work on modified surface area heuristics
[Hav00] influenced the way that engineers optimized tree builds based on area;
in 2010 Pantaleone and Luebke [PL10] targeted massively parallel real-time tree
building and tuned for tree build time rather than absolute query time.
It is also common to store the same scene data in more than one structure.
For example, you may want a list of characters in the world for efficient iteration
during Artificial Intelligence simulation, a hash grid for collision detection, and a
BSP tree for rendering them. Often a single complex data structure will contain
multiple, simpler data structures. This presents a unified interface but allows it to
combine the efficiency for different methods from different single data structures.
This approach gains performance at the cost of storage space and implementation
complexity. In particular, storing the same data multiple times creates potential for
the duplicate state becoming desynchronized, and that must be weighed carefully
against the performance advantages.
There are commonly employed data structures and increasingly exotic ones.
For example, most nongraphics programs rely on a small number of classic data
structures such as arrays, hash tables, and an occasional tree. Most graphics pro-
grams rely on those plus the spatial data structures presented in this chapter (with
the list and BVH perhaps currently the most popular). There's a lot of practical
wisdom in primarily relying on such a small set of workhorses. It amortizes the
cost of polishing and optimizing those structures, and lets the programmer using
them focus on his or her application instead of learning about a new interface.
But sometimes a more exotic classic data structure is really needed. For exam-
ple, if your entire program's performance depends on having a fast priority queue
for a large data set, then it may be time to read a paper about left-leaning red-
black trees [Sed] and implementing one. But if your program depends heavily
on ray-heightfield intersection performance, then it may be worth investing in a
data structure optimized for
that
case, such as Musgrave's and Amanatides's and
Woo's grid-tracing algorithms [MKM89, AW87]. Ray-intersection data structures
are a constant topic in the global illumination literature. The ray-tracing state of
the art “STAR” reports are a good place to find surveys of current thought (e.g.,
[WMG+09]). Sphere, box and other primitive intersections often arise in the phys-
ical simulation community. The design and analysis issues presented in this chap-
ter apply equally well to the structures already discussed and to new data structures
that you will invent on your own.
We've used ray-triangle intersection as a motivating example throughout this
chapter, in part because ray casting is a common operation in most renderers, and
triangle meshes are a preferred representation for most scene geometries. But in
the future (and in some contexts even today), both of these may change. It may be,
for instance, that tracing frusta (essentially bundles of rays) becomes essential, or
that geometry is represented primarily by points, or by spline surfaces, or by some
yet-unimagined new kind of primitive. When that happens, the choices of accel-
eration structures will change as well, but the kinds of analysis we've described
in this chapter will persist: Tradeoffs involving memory coherence, patterns of
access, questions of whether our typical problem is of a size large enough that
asymptotic analysis is informative, and the costs of implementation versus use
will still guide the choices you make as you compare new structures.
