Graphics Reference
In-Depth Information
Spatial partitioning
1
3
7.5
8
12
13
16
g
a
b
c
d
e
f
Pointer structure
a
b
f
g
c
d
e
Figure 37.8: An alternative choice of tree structure for the same data shown in Fig-
ure 37.7. This tree is shallower and contains multiple primitives per node, indicated by
adjacent boxes. Such a structure might be preferred if the overhead of processing a node
is high.
can produce a convex polyhedron bounding the empty space around a point. Many
video games use the latter operation to locate the convex space that contains the
viewer for efficient access to precomputed visible-surface information.
The ordered enumerations are possible because the partitions impose an order-
ing of the convex spaces along a ray. This allows partially ordered enumeration of
primitives encountered along a ray. It is not a total ordering because some nodes
may contain more than one primitive in an unordered list. The ordering of nodes
allows early termination when ray casting, which is why they have been frequently
employed for accelerating ray casting as described in Section 36.2.1. It also allows
hierarchical culling of occluded nodes within a camera frustum and early termi-
nation in that case, as explained in Section 36.7.
The logical (i.e., pointer) structure of the tree in memory is simply that of a
binary tree (see Listing 37.12), regardless of the number of spatial dimensions.
Trees are typically built over primitives, such as polygons. This leaves a design
choice of how to handle primitives that span a partition. In one form, primitives
that span a partition plane are cut by the plane, and the leaves store lists of the cut
primitives that lie entirely within their convex spaces. To preserve the precision
of the input, the cutting operation may be performed while building the tree and
the original primitives stored at the leaves. Under that scheme, the same primitive
may appear in multiple leaves.
An alternative is to store primitives that span a partition plane in the node for
that plane. This can destroy the asymptotic efficiency of the tree if many primitives
span a plane near the root of the tree. However, for some scenes this problem can
be avoided by choosing the partitions to avoid splitting primitives.
