Graphics Reference
In-Depth Information
that a quality production system is likely to use two completely different representa-
tions for performance reasons. The BSP tree used during tree construction should be
designed for easy manipulation using regular pointers to address child nodes, and
it should have full-size uncompressed fields. In contrast, the BSP tree used at run-
time should be designed to use little memory (using compressed nodes and pointers)
and have its nodes output in a cache-efficient format (as discussed in Chapters 6
and 13).
8.3.1
Selecting Dividing Planes
The order in which dividing planes are selected during tree construction greatly affects
the size and shape of the resulting tree, and therefore the effectiveness of the tree
for querying. It also affects the tree's memory requirements. Due to the sheer num-
ber of possible plane orderings, computing an optimal BSP tree is an intractable
problem. Fortunately, in practice good or even near-optimal solutions can be obtained
by trying a number of candidate dividing planes at each level of the tree, proceeding
with the one that scores best according to an evaluation function (as described in
Section 8.3.2).
Because there are infinitely many arbitrary dividing planes, one approach of con-
straining the problem is limiting the set of possible dividing planes to a finite number
by relying on autopartitioning. That is, the strategy is to restrict the search to the
supporting planes of the faces in the input geometry.
Autopartitioning is simple to implement. It is also a natural choice for a node-
storing tree. However, autopartitioning (alone) is not always ideal. In some cases —
such as for a leaf-storing tree — relying on autopartitioning alone may lead to more
splitting than is desired. To illustrate the point, Figure 8.6a shows a geometrical
configuration in which all possible autopartitioned dividing planes end up splitting
several faces. Figure 8.6b shows how, by using general dividing planes, the groups of
polygons can be separated from each other, resulting in no splits at all. (However, it
is important to note that if the three groups are moved closer to one another it will
be impossible to find even a general dividing plane to separate the groups.)
For another drawback of using just autopartitioning, consider the problem of
building a BSP tree from a polygon sphere. Because the sphere is a convex shape,
all sphere faces will lie on just one side of a plane through any one of its faces.
The resulting tree will in some sense therefore be maximally unbalanced, with a
depth equal to the number of faces in the sphere (Figure 8.7a). Determining point
containment — a typical worst-case query — is now an
O
(
n
) operation. In contrast, if
selected planes are instead allowed to cut across the sphere, roughly half the faces can
be discarded for each plane tested, making the same worst-case query an
O
(log
n
)
operation (Figure 8.7b).
If the BSP tree is computed as a boundary representation of the sphere, the sup-
porting planes of the sphere faces at some point must be selected as dividing planes.
One option is to perform general splits, dividing the geometry in half until only a
