Graphics Reference
In-Depth Information
The internal nodes in the BSP tree have at most two children, which we label
positive
and
negative.
The construction algorithm for the tree ensures that the
positive subtree contains only primitives that are in the positive half-space of the
plane (or on the plane itself) and that the negative subtree contains only those
in the negative half-space of the plane. If a primitive from the scene crosses a
splitting plane, then the construction algorithm divides it into two primitives, split
at that plane.
Listing 36.1 gives the algorithm to evaluate the visibility function in this sim-
ple BSP tree. The recursive intersects function performs the work. Point
Q
is
visible to point
P
if no intersection exists between the line segment
PQ
and the
geometry in the subtree with
node
at its root. When
node
is a leaf, it contains one
geometric primitive, so
intersects
tests whether the line-primitive intersection
is empty. Chapter 7 describes intersection algorithms that implement this test for
different types of geometric primitives, and Chapter 15 contains C++ code for
ray-triangle intersection.
Figure 36.9 visualizes the algorithm's iteration through a 2D tree for a scene
consisting of disks.
If
node
is an internal node, then it contains a splitting plane that creates two
half-spaces. We categorize the child nodes corresponding to these as being closer
and farther with respect to
P
. Figure 36.8 shows an example classification at an
internal node. With an eye toward reusing this algorithm's structure for the related
problem of finding the
first
intersection, we choose to visit the closer node first.
That is because if there is
any
intersection between segment
PQ
and the scene in
closer,
it must be closer to
P
than every intersection in
farther
[SBGS69].
If
PQ
lies entirely in one half-space, the result of the intersection test for the
current node reduces to the result of the test on that half-space. Otherwise, there
is an intersection if one is found in either half-space, so the algorithm recursively
visits both.
1
2
3
4
5
6
Figure 36.9: Tracing a ray through a scene containing disks stored in a 2D BSP tree.
Highlighted portions of space correspond to the node at which the algorithm is operating
in each step. Iteration proceeds depth-first, preferring to descend into the geometrically
closer of the two children at each node.
