Graphics Reference
In-Depth Information
g
3
2.5 m
3
), we'd find that the geometry is indeed distributed in a
nonuniform fashion. That's because a room volume overlapping the edge of a
building would contain geometry, but one on the interior or completely outside
the building would be empty.
If we instead chose grid cells to have at least the footprint of a city block, we'd
find that every cell contains about the same number of building exteriors, so the
density is nearly uniform. (Of course, some buildings might have more detail in
the model than others—let's just work with a consistent tessellation level.) So part
of the challenge in choosing the grid size is that the density, which affects our
choice, depends on the grid size itself.
The third point is that constant factors can cause orders of magnitude in per-
formance difference in ray-intersection times with a tree and a grid's own sub-
divisions (separate from the cost of intersecting the elements within them). That
is because the regular structure of the grid allows efficient memory packing and
eliminates the need to explicitly store the grid's geometry. Where a bounding vol-
ume hierarchy must explicitly encode each bounding box, the geometry of each
grid cell is implicit in the grid size and requires no memory access to obtain. The
process of tracing a ray through a grid is equivalent to the problem of conserva-
tively rasterizing a line. Line rasterization algorithms tend to simplify down to one
or two branches and a few additions per pixel (grid cell) on the line's (ray's) path.
If the ray-grid cell intersection is 50
x
faster than the ray-tree-node intersection,
we can afford to look at many empty grid cells before the inefficiency of doing so
overwhelms the performance advantage.
/
n
≈
4
×
4
×
We've covered a lot of ground in this chapter at a bunch of different levels of
detail and abstraction. Now let's step back and review the big picture. Relatively
straightforward application of basic computer science principles to spatial data
structures for representing a scene can return huge speedups for rendering and
collision detection. Of course, there are a lot of caveats about avoiding degenerate
cases and optimizing for peak performance. But you'd be crazy not to use these
kinds of structures, because no constant speedup could possibly make a program
scale to large scenes as well as even the simplest spatial tree.
Common sense, backed by examples of some specific cases, led us to the fol-
lowing big observations.
1. Different data structures work well in different places, and the choice
isn't always determined by their asymptotic behavior. Sometimes testing
in practice is the best solution.
2. Even when you've found the best data structure, you may need to do some
tuning.
3. Hardware tricks can sometimes buy you another factor of ten or more.
These items are shown in order: You should choose the right data structure
before you try to do hardware-based optimizations; you should test on sample
scenes before you do your data-structure tuning.
Spatial data structures continue to be a hot topic in computer graphics. You
should experiment by nesting (e.g.,
Grid3D< BSPTree<Triangle> >
) and com-
bine elements of different structures. It is quite common to outperform results
from the literature that use more generic structures if your particular application
