Graphics Reference
In-Depth Information
E
A
A
B
B
C
A
C
C
D
D
B
E
(a)
(b)
Figure 8.19
(a) The unbeveled tree for a triangle. (b) Beveling planes inserted between the
solid leaf and its parent node.
Specifically, each supporting plane through the AABB faces is added at the polytope
vertices most extreme in the direction of that plane normal (except in the case in
which this plane is already present in the BSP tree). The planes corresponding to
the edge-edge cross products are placed so as to pass through the edges of the leaf
polytope.
Because the orientation of an AABB is fixed, if only AABB queries are performed
on the solid BSP tree the additional beveling planes required can be precomputed
and stored in the tree. They would be added between each solid leaf and the leaf's
parent node, as illustrated in Figure 8.19.
When performing arbitrary polytope queries against the BSP tree, including OBB
or sphere queries, the beveling planes cannot be precomputed but must instead be
computed at runtime. This also holds when the BSP tree itself is not fixed but is
allowed to rotate. To facilitate the computation of the required beveling planes using
the separating-axis test, the solid BSP tree must be enhanced to contain an explicit
boundary description of the solid leaf volumes of the tree.
Note that when performing a point or ray query against the expanded tree
all
dividing planes must be offset as the hierarchy is traversed, not just the planes cor-
responding to a boundary of the solid represented by the BSP tree. Otherwise, the
query would not correctly end up in all of the leaves the original query volume would
be overlapping.
8.5
Summary
In this chapter the BSP tree was presented as the most versatile spatial partitioning
method, capable of performing the same tasks as quadtrees, octrees, and
k
-d trees,
albeit at the cost of requiring more memory for storing full plane equations at each
node of the tree. Additionally, it was shown how BSP trees can also be used as a
boundary or solid representation of polyhedral objects.
