Attributes and Behaviors of Primitives - Essentials of Interactive Computer Graphics - page 172

types, there are two major challenges to detecting collisions based on mathemat-
ics.

• Tedious mathematics . The mathematics of determining if two different
geometric shapes occupy the same space can be tedious, and the imple-
mentation can be complex (e.g., between a triangle and a rectangle). Often,
the mathematics can deteriorate into intersecting edges of the primitives.
In addition, to successfully participate in collision computation, every ge-
ometric shape must know how to collide with every other supported geo-
metric shape (e.g., circle against line, point, triangle, rectangle; line against
point, triangle, rectangle). In general, to support n different types of primi-
tives, we would need to implement O

n 2 collision routines! For example,

to properly support collision between our point, line, and circle primitives,
we must define 3 collision routines. If we wish to introduce a new primi-
tive type (e.g., triangle) we must implement additional three new collision
routines, i.e., triangle against circle, line, and point!

( )

• Complex invocation . At run time, based on the participating primitives in
a collision, we must determine which of the n 2 routines to invoke!

For these reasons, interactive graphics applications typically do not support true
collision between objects. Instead, simpler geometric shapes, referred to as bound-
ing volumes, are defined to bound the primitives. During a collision process,
instead of intersecting the actual primitives, application programs compute the
intersection of the corresponding bounding volumes. A collision is deemed suc-
cessful when the bounding volumes of two primitives overlap in space. For ex-
ample, if we choose to use circles as the bounding volume primitive, then we
would bound a circle around a primitive by computing a center and a radius such
that the primitive is entirely within the circle. In this case, if we wish to compute
the collision between two triangles, we would compute the collision between the
bounding circles of the two triangles.
In general, bounding volumes can be any geometric shape or shapes. For
example, circles (2D), spheres (3D), boxes, and so on. When choosing the shape
for bounding volumes, we should pay attention to the following.

• Simplicity . The bounding volume must be simple to compute. The bound-
ing volumes are typically computed during run time to approximate the
primitives. We cannot afford excessive computation when determining the
values for the bounding volume. In addition, it should be straightforward
to determine if two bounding volumes occupy the same space. After all,
mathematic simplicity is one of the main reasons for working with bound-
ing volumes.