Graphics Reference
In-Depth Information
the object is recursively divided until some preset tree depth is reached. During the
construction, each occupied octree node is circumscribed with a sphere, forming the
actual sphere tree. The octant center point is used as the
s
phere center. For a regular
cube with side
s
, the sphere radius
r
is given by
r
s
√
3
2. If the initial bounding
volume is a general A
ABB instead
of a cube, the radius for an octant with sides
x
,
y
,
and
z
becomes
r
=
x
2
z
2
2.
To eliminate redundant spheres that do not contribute to the actual collision detec-
tion it is possible to stop recursing into any octree nodes that are occluded on all
sides [O'Sullivan99]. This may cause collisions with interior parts to go undetected,
however.
The sphere tree resulting from this approach has a fairly loose fit. Hubbard sug-
gests using simulated annealing to tighten the spheres around the object, while still
maintaining conservative coverage of the object [Hubbard95]. This involves mak-
ing random changes to the spheres, accepting those producing a tighter sphere,
sometimes accepting those that are worse to fight getting stuck in local minima.
Unfortunately, as Hubbard points out, measuring the tightness of spheres around
objects is difficult. The simulated annealing step is also quite slow and can produce
very irregular distributions of spheres. The practical value of this technique is therefore
somewhat limited.
y
2
=
+
+
6.4.4
Sphere Tree from Sphere-covered Surfaces
Using the basic top-down construction method, [Quinlan94] computes sphere trees
from an input set of small spheres covering all surfaces of the original object. The
surface covering is performed in a scan conversion-like process whereby each polygon
in the input set is overlaid with a regular grid of spheres, with the sphere centers in
the plane of the polygons. Each of these spheres, forming the leaf nodes of the final
tree, is labeled with the polygon it was created to cover.
The hierarchy is built by dividing the full set of leaf spheres into two roughly
equal-size parts. Two subtrees are constructed by recursively calling the algorithm
with each of the subsets. These subtrees are then combined into a tree by adding
them as children to a new parent node. At each step, the set of spheres is divided into
two subsets by enclosing the sphere centers in an AABB. The AABB is split in half
along its longest side and spheres are assigned to the subsets based on which AABB
half their center is in.
Note that this approach assumes a surface representation based on (convex)
polygons. It will not detect collisions with the interior of an object.
6.4.5
Generate-and-Prune Sphere Covering
An interesting method that does not construct a hierarchy as such but simply com-
putes a collection of spheres, the union of which completely encloses a given object,
was suggested by Greenspan and Burtnyk [Greenspan96]. Their algorithm consists
