Graphics Reference
In-Depth Information
// If (squared) distance smaller than (squared) sum of radii, they collide
float radius = capsule1.r + capsule2.r;
return dist2 <= radius * radius;
}
The functions
SqDistPointSegment()
and
ClosestPtSegmentSegment()
used
here are found in Chapter 5 (Sections 5.1.2.1 and 5.1.9, respectively). A distance
test for SSRs (and thus, by reduction, also for SSLs and SSPs) based on halfspace
tests is given in [Larsen99] and [Larsen00].
4.5.2
Computing Sphere-swept Bounding Volumes
The machinery needed for computing SSVs has been described in previous sections.
For instance, by computing the principal axes a capsule can be fitted by using the
longest axis as the capsule length. The next longest axis determines the radius.
Alternatively, the length can also be fit using a least-square approach for fitting a
line to a set of points. For SSRs, all three axes would be used, with the shortest axis
forming the rectangle face normal. See [Eberly01], [Larsen99], and [Larsen00] for
further detail.
4.6
Halfspace Intersection Volumes
With the notable exception of spheres, most bounding volumes are convex polyhedra.
All of these polyhedral bounding volumes are representable as the intersection of a
set of halfspaces, wherein the halfspace dividing planes coincides with the sides of
the bounding volume. For instance, AABBs and OBBs are both the intersection of six
halfspaces. A tetrahedron is the intersection of four halfspaces — the smallest number
of halfspaces needed to form a closed volume. Generally, the more halfspaces used
the better the resulting intersection volume can fit an object. If the bounded object
is polyhedral, the tightest possible convex bounding volume is the convex hull of the
object. In this case, the number of faces on the hull serves as a practical upper limit
on how many halfspaces are needed to form the bounding volume. Convex hulls
are important bounding volumes, and an in-depth treatment of collision detection
algorithms for convex hulls is given in Chapter 9.
Although convex hulls form the tightest bounding volumes, they are not neces-
sarily the best choice of bounding volume. Some drawbacks of convex hulls include
their being expensive and difficult to compute, taking large amounts of memory
to represent, and potentially being costly to operate upon. By limiting the number
of halfspaces used in the intersection volume, several simpler alternative bounding
volumes can be formed. A few variants are described in the sections that follow.
