Graphics Reference
In-Depth Information
depth at which an object will be inserted can be computed from the size of the object,
allowing for
O
(1) insertions.
This power does not come for free, however. The larger nodes overlap more neigh-
boring nodes, and more nodes have to be examined to determine whether any two
objects must be tested against each other. Still, in most cases the reduction in pairwise
tests makes loose octrees attractive for collision detection purposes.
Loose octrees are similar in structure to hierarchical grids. The key difference is
that octrees are rooted. This means that time is spent traversing the (largely) empty
top of the tree to get at the lower-level nodes where the objects are, due to objects
generally being much smaller than the world. In comparison, the hgrid is a shallower,
rootless structure providing faster access to the nodes where the objects are stored.
In addition, hgrid levels can be dynamically deactivated so that no empty levels
are processed and processing stops when no objects exist on the remaining levels.
A linearized or array-based octree allows similar optimizations. The corresponding
optimization for a pointer-based octree is to maintain a subtree object-occupancy
count for each node. The cost of updating these occupancy counts is proportional to
the height of the tree, whereas the hgrid level occupancy counters are updated in
O
(1)
time. Thanks to the automatic infinite tiling performed by the hash mapping, a hashed
hgrid does not need to know the world size. The octree cannot easily accommodate
an unbounded world without growing in height. Overall, hgrids seem to perform
somewhat better than loose octrees for collision detection applications.
7.3.7
k
-d Trees
A generalization of octrees and quadtrees can be found in the
k
-dimensional tree,
or
k-d tree
[Bentley75], [Friedman77]. Here,
k
represents the number of dimensions
subdivided, which does not have to match the dimensionality of the space used.
Instead of simultaneously dividing space in two (quadtree) or three (octree) dimen-
sions, the
k
-d tree divides space along one dimension at a time. Traditionally,
k
-d trees
are split along
x
, then
y
, then
z
, then
x
again, and so on, in a cyclic fashion. However,
often the splitting axis is freely selected among the
k
dimensions. Because the split
is allowed to be arbitrarily positioned along the axis, this results in both axis and
splitting value being stored in the
k
-d tree nodes. An efficient way of storing the two
bits needed to represent the splitting axis is presented in Section 13.4.1. One level
of an octree can be seen as a three-level
k
-d tree split along
x
, then
y
, then
z
(all
splits selected to divide the space in half). Figure 7.14 shows a 2D spatial
k
-d tree
decomposition and the corresponding
k
-d tree layout.
Splitting along one axis at a time often accommodates simpler code for operating
on the tree, in that only the intersection with a single plane must be considered.
Furthermore, because this plane is axis aligned, tests against the plane are numerically
robust.
For collision detection,
k
-d trees can be used wherever quadtrees or octrees are
used. Other typical uses for
k
-d trees include
point location
(given a point, locate the
