Graphics Reference
In-Depth Information
Chapter
8
BSP Tree Hierarchies
Of the many spatial partitioning methods available, the BSP tree is the most versatile.
It can perform the same tasks as the
k
-d tree, the quadtree, or the octree, but not
vice versa. In addition to spatial partitioning, the BSP tree can be used as a boundary
or solid representation of arbitrary polyhedral scenes. BSP trees are also powerful
structures for collision detection, which this chapter explores.
8.1
BSP Trees
A
binary space-partitioning tree
(or
BSP tree
for short) is a binary tree structure that
recursively partitions space into pairs of subspaces with respect to dividing planes
of arbitrary position and orientation. If the space being partitioned is
n
-dimensional,
the dividing planes are (
n
1)-dimensional hyperplanes. In practice, the working
space is usually 3D, and sometimes 2D. When the space being partitioned is 3D, the
dividing hyperplane is a plane. In two dimensions, the dividing hyperplane is a line.
The two partitions, or halfspaces, the space is divided into are commonly referred
to as the
positive
and
negative
halfspaces. The positive halfspace lies in front of the
dividing hyperplane and the negative halfspace behind it (see Section 3.6). Dividing
planes are also referred to as splitting planes or partitioning planes.
As a simple example of a BSP tree, consider the illustrations of Figure 8.1. The
square region defined by the gray outline is here the original space (note that this
space does not have to be bounded; the square could easily be a plane). A first
hyperplane,
A
, divides the original space into two regions, as illustrated in Figure
8.1a. Beneath the square is the corresponding BSP tree, with internal nodes shown
as circles and the leaves as squares. Figure 8.1b shows a second hyperplane,
B
,
dividing the negative halfspace of node
A
. Finally, a third hyperplane,
C
, is shown in
Figure 8.1c, this time dividing the positive halfspace of node
A
. Note that the spatial
regions corresponding to the leaves are always convex.
−
349
