Graphics Reference
In-Depth Information
are passed to the appropriate side of the plane in order to recursively construct the
subtrees of the node, thus ending up stored in the nodes further down the tree. Any
straddling faces are split against the dividing plane before the resulting pieces are
passed down. Leaves of a node-storing tree may be empty (as all polygons can be
stored in the nodes) or may contain a single face (plus any eventual faces coplanar
with this face). Because faces are stored in the nodes, it is not strictly necessary to
also store planes in the nodes (as they can be derived from the stored faces).
Traditionally, node-storing trees have mainly been used for software rendering of
3D environments, as keeping faces in the nodes results in fewer splits than with other
BSP variants, in turn resulting in fewer faces to render. With the advent of 3D graphics
hardware, using node-storing trees no longer makes sense in that they excessively
divide the geometry into individual polygons. Effective use of 3D rendering hard-
ware instead involves drawing long tri-strips or large patches of faces of the same
material to minimize expensive state changes and to reduce the number of vertices
transmitted to the graphics card. Such savings are not facilitated by the node-storing
BSP tree.
Node-storing trees are not really suitable for collision detection either. Faces
stored on the nodes have no spatial relationship to the position of a query object
and are thus likely not to intersect the query object. However, these faces must still
be tested against, as the query object traverses the dividing plane with which they are
associated. In particular, architectural scenes — which tend to feature many coplanar
faces — suffer from such overtesting.
Figure 8.3 illustrates the first step of building a node-storing BSP tree. The origi-
nal 12-polygon input geometry is shown in Figure 8.3a. An initial dividing plane is
selected to go through the plane of face
A
(Figure 8.3b). Because
G
also lies on this
plane, both
A
and
G
are stored in the root node. Two faces,
D
and
J
, are straddling the
divider plane and must be split, after which all faces lie entirely on one side of the
dividing plane and can be uniquely assigned to the appropriate subtree. For the next
ply of the tree, the plane through
B
is here selected as the dividing plane for the left
subtree and the plane through
H
for the right subtree. Figure 8.3c shows the BSP tree
after these splits have been performed. Construction proceeds in a similar manner
until a termination criterion has been met.
The original BSP tree as described by [Fuchs83] is a node-storing BSP tree in which
only the polygon whose supporting plane is selected as the dividing plane is stored in
the node. Any other polygons coplanar to this plane are described as going arbitrarily
to either side.
8.2.2
Leaf-storing BSP Trees
The term
leaf-storing
(or
leaf-based
)
BSP tree
refers to any BSP tree in which geometry
is stored in the leaves of the tree rather than in the internal nodes. An internal tree
node only contains the dividing plane and references to the child subtrees of the
node. With no polygons on the internal nodes, queries on leaf-storing trees do not