Graphics Reference
In-Depth Information
+
-
1
+-
+-
+-
+-
+-
EMPTY
EMPTY
-
-
+
3
5
+
2
EMPTY
SOLID
EMPTY
SOLID
+
+
4
-
-
Figure 8.5
A solid figure cut by a number of dividing planes and the resulting solid-leaf
BSP tree.
the partitioning planes, plus the boundary planes of the convex polyhedra. In terms of
Figure 8.5, the initial dividing plane partitions the nonconvex shape into two (convex)
triangles. The remaining dividing planes describe the boundary of these triangles.
Solid-leaf BSP trees have a number of valuable properties as far as collision detec-
tion goes. They allow trivial detection of robustness problems such as fall-throughs,
in that intersection tests directly report whether an object lies in solid or empty space.
Because the representation effectively encodes the boundary polygons of the input
geometry, there is also no need to perform specific polygon tests (as no polygons are
explicitly stored). The lack of special tests for polygons makes for very nice, uniform
code.
It is also possible to create a hybrid between a solid-leaf and a leaf-storing BSP
tree. An example of a hybrid tree is the
brush-storing
tree popularized through its use
in the
Quake II
and
Quake III
games from id Software. This tree explicitly stores the
planes that form the halfspace intersection volume that is the solid volume occu-
pied by the leaf (where
brush
is the
Quake
terminology for this collection of planes).
Additionally, the tree contains the beveling planes described in Section 8.4.3 to allow
efficient AABB queries on the tree.
The various data formats used in the
Quake
games are well documented on the
Internet. For example, the
Quake II
BSP file format is described in [McGuire00], as
well as implicitly through the
Quake II
source code itself [idSoftware01]. The collision
detection of
Quake III
is discussed in [Ostgard03].
8.3
Building the BSP Tree
Building a BSP tree involves three steps.
1. Selection of a partitioning plane.
2. Partitioning of the input geometry into two sets with respect to the plane; the
geometry in front of the plane and the geometry behind it. Geometry that straddles
