Graphics Reference
In-Depth Information
Spatial partitioning
1
3
7.5
8
12
13
16
a
b
c
d
e
f
g
Pointer structure
a
b
e
g
f
c
d
Figure 37.7: A depiction of a 1D binary tree as partitions (black lines) of values with
associated keys (red disks). The thickness of the partition line represents the tree depth of
that partition node in the tree; the root is the thickest.
A 1D binary search
tree
recursively separates the number line with splitting
points, as depicted in Figures 37.7 and 37.8. In 2D, a spatial
tree
separates 2-
space with splitting lines, as depicted in Figure 37.9. In 3D, a spatial tree separates
3-space with splitting planes.
The analogy continues to higher dimensions. For any number of dimensions,
a
binary space partition
(
BSP
) tree expresses a recursive binary (i.e., two-sided)
partition (i.e., division) of space [SBGS69, FUCH80]. This partitioning divides
space into convex subspaces, that is, convex polygons, polyhedra, or their higher-
dimensional analogs, called polytopes. The leaves of the tree correspond to these
subspaces, which we'll call polyhedra in general. The internal nodes correspond
to the partition planes. They also represent convex spaces that are unions of their
children.
BSP trees can support roughly logarithmic-time intersection queries under
appropriate conditions. These intersection queries can be framed as intersect-
ing some query geometry with either the convex polyhedra corresponding to the
leaves, or the primitives inside the leaves. In the latter case, note that the tree
is only accelerating the intersection computation on nodes. For primitives stored
within a node, it delegates the intersection operation to a list data structure. That
provides no further acceleration. But it allows the tree to have an interface that
is more useful to an application programmer. The application programmer is pri-
marily concerned with the primitives, and wants the tree's structure to provide
acceleration but have no semantic impact on the query result.
In addition to the ray, box, and ball queries, BSP trees can also enumerate their
elements in front-to-back overlap order relative to some reference point, and they
