Graphics Reference
In-Depth Information
A
B
D
A
C
C
D
B
(a)
(b)
Figure 8.2
The recursive division of space in half can be used as (a) a spatial partitioning over
a number of objects. It can also be used as (b) a volume or boundary representation of an
object.
When, as in the latter example, the dividing planes are selected to coincide with the
faces of the input geometry, they are commonly called
autopartitioning
(and sometimes
polygon aligned
). Dividing planes coplanar to the
xy
,
xz
,or
yz
plane are called
axis
aligned
. BSP trees using only axis-aligned dividing planes are commonly referred to
as
k
-d trees (as described in Chapter 7). Dividing planes that have no restrictions put
on them (nor on the partitionings they form) are here called
arbitrary
or
general
.
Constructing a BSP tree from scratch or recomputing parts of a tree is sufficiently
expensive that they are rarely built or modified at runtime. For this reason, BSP trees
are primarily used to hold static background geometry. Collision detection among
moving objects is usually handled through some other method.
8.2
Types of BSP Trees
BSP trees can be categorized in many ways, such as how the dividing planes are
oriented, if geometry is stored in the nodes or the leaves (if at all), and whether they
are used for spatial partitioning or as a volume representation. In particular, three
types of BSP trees are commonly identified, here called
node-storing
,
leaf-storing
, and
solid-leaf
(or just
solid
) BSP trees. These types are described in more detail in the
following sections.
8.2.1
Node-storing BSP Trees
A node-storing (or node-based) BSP tree is autopartitioning, thus selecting support-
ing planes of faces from the geometry as the dividing planes used during construction.
As the name suggests, the face whose supporting plane was selected as the dividing
plane and all other faces coplanar with it are stored in the node. Remaining faces
