Graphics Reference
In-Depth Information
A
+-
+-
+-
B
B
+
-
+
-
C
+
-
A
A
A
+
-
+
-
+
-
B
C
B
+-
+-+-
(a)
(b)
(c)
Figure 8.1
The successive division of a square into four convex subspaces and the cor-
responding BSP tree.
(a) The initial split.
(b) The first second-level split.
(c) The second
second-level split.
Originally, BSP trees were developed for addressing the hidden-surface problem
[Fuchs80]. BSP trees solve this problem by allowing a scene to be view-independently
decomposed in a preprocessing phase. The resulting tree can then be traversed at
runtime to give the correct (back-to-front or front-to-back) sorting order of objects
or individual polygons from an arbitrary viewpoint.
BSP trees have found uses in such varied applications as ray tracing, constructive
solid geometry (CSG), and robot motion and path planning, to name a few. BSP trees
are also very versatile when it comes to collision detection as they can serve
both
as a
spatial partitioning (a nonboundary representation) and as a volume representation
(a boundary representation, for a solid object). As a spatial partitioning scheme,
BSP trees are very similar to quadtrees, octrees, and
k
-d trees, but BSP trees are
more general as they can emulate these other spatial data structures. As a volume
representation, BSP trees can be used to represent and distinguish the interiors of
polygons and polyhedra from their exteriors.
Figure 8.2 illustrates the use of BSP trees for spatial partitioning and volume rep-
resentation. Figure 8.2a shows how a space can be spatially partitioned to accelerate
collision queries against the objects of the space. Thanks to the hierarchy formed
by the BSP tree, with
n
objects in the tree only on the order of
O
(log
n
) objects are
typically tested by a query, in that half of the remaining objects can be expected to be
discarded by each successive test against a partitioning plane. (However, degenerate
situations may cause all
n
objects to be tested — for example, if the query object is
very large or if the tree is poorly built.)
Figure 8.2b shows how the dividing planes can be selected to coincide with the
faces of a polygonal object, thus allowing the exterior of the shape to be partitioned
from the interior of the shape. The spatial region associated with each leaf of this tree
lies either fully inside or fully outside the original shape.
