Graphics Reference
In-Depth Information
thousand visibility tests, building some kind of spatial data structure will usually
provide a net performance gain.
We now give an example of how a ray-primitive intersection query operates
within the
binary space partition tree
data structure. The issues encountered
in this example apply to most other spatial data structures, including bounding
volume hierarchies and grids.
The
binary space partition tree
(
BSP tree
) [SBGS69, FKN80] is a data structure
for arranging geometric primitives based on their locations and extents. Chapter 37
describes in detail how to build and maintain such a structure, and some alternative
data structures. The BSP tree supports finding the first intersection between a ray
and a primitive. The algorithm for doing this often has only logarithmic running
time in the number of primitives. We say “often” because there are many patho-
logical tree structures and scene distributions that can make the intersection time
linear, but these are easily avoidable for many scenes. This logarithmic scaling
makes ray casting practical for large scenes.
The BSP tree can also be used to compute the visibility function. The algo-
rithm for this is nearly identical to the first-intersection query. It simply terminates
with a return value of false when
any
intersection is detected, and returns true
otherwise.
There are a few variations on the BSP structure. For the following example, we
consider a simple one to focus on the algorithm. In our simple tree, every internal
node represents a
splitting plane
(which is not part of the scene geometry) and
every leaf node represents a geometric primitive in the scene. A plane divides
space into two half-spaces. Let the positive half-space contain all points in the
plane and on the side to which the normal points. Let the negative half-space
contain all points in the plane and on the side opposite to which the normal points.
Figure 36.8 shows one such plane (for a 2D scene, so the “plane” is a line). Both
the positive and negative half-spaces will be subdivided by additional planes when
creating a full tree, until each sphere primitive is separated from the others by at
least one plane.
Ray origin
Positive half-space
“Closer” in this case because
it contains the ray origin
Splitting plane
Query ray
Plane normal
Object
Negative half-space
Figure 36.8: The splitting plane for a single internal BSP node divides this scene composed
of five spheres into two half-spaces.
