Bounding Volumes - Real-Time Collision Detection - page 113

(a) (b) (c)

Figure 4.11 (a) A sphere-swept point (SSP). (b) A sphere-swept line (SSL). (c) A sphere-swept
rectangle (SSR).

for cylinders is quite expensive, making them less attractive as bounding volumes.
However, if a cylinder is fitted with spherical end caps the resulting capped cylinder
volume becomes a more attractive bounding volume. Let the cylinder be described by
the points A and B (forming its medial axis) and a radius r . The capped cylinder would
be the resulting volume from sweeping a sphere of radius r along the line segment
AB . This volume is part of a family of volumes, extensions of the basic sphere.
Recall that the test between two spheres computes the distance between the
two center points, comparing the result against the sum of the radii (squaring the
quantities to avoid an expensive square root). By replacing the sphere center points
with arbitrary inner primitives or medial structures, new bounding volumes can be
obtained. The resultant volumes are equivalent to sweeping the inner primitive with
a sphere of radius r (or, technically, forming the Minkowski sum of the sphere and the
primitive). As such, this entire family of bounding volumes is therefore collectively
referred to as sphere-swept volumes (SSVs). All points within a distance r from the
inner medial structure belong to the SSV. Three types of sphere-swept volumes are
illustrated in Figure 4.11.
Following the sphere overlap test, the intersection test for two SSVs simply
becomes calculating the (squared) distance between the two inner primitives and
comparing it against the (squared) sum of their combined radii. The cost of sphere-
swept tests is completely determined by the cost of the distance function. To make
the distance test as inexpensive as possible, the inner primitives are usually limited
to points, line segments, or rectangles. The resulting SSVs — sphere-swept points
(SSPs), sphere-swept lines (SSLs), and sphere-swept rectangles (SSRs) — are com-
monly referred to, respectively, as spheres , capsules , and lozenges . The latter looks like
an OBB with rounded corners and edges. Capsules are also referred to as capped cylin-
ders or spherocylinders . The data structures for capsules and lozenges can be defined
as follows:

x | (x - [a + (b - a)*t]) ∧ 2<=r

// Region R = ,0<=t<=1

struct Capsule {
Point a;

// Medial line segment start point

Point b; // Medial line segment endpoint