Real-Time Rendering, Third Edition, 3rd Edition

i

i

i

i

i

i

i

i

Chapter 17

Collision Detection

“To knock a thing down, especially if it is cocked at an arrogant

angle, is a deep delight to the blood.”

—George Santayana

Collision detection (CD) is a fundamental and important ingredient in

many computer graphics applications. Areas where CD plays a vital role in-

clude virtual manufacturing, CAD/CAM, computer animation, physically

based modeling, games, flight and vehicle simulators, robotics, path and

motion planning (tolerance verification), assembly, and almost all virtual

reality simulations. Due to its huge number of uses, CD has been and still

is a subject of extensive research.

Collision detection is part of what is often referred to as collision han-

dling, which can be divided into three major parts: collision detection,

collision determination,andcollision response. The result of collision de-

tection is a boolean saying whether two or more objects collide, while col-

lision determination finds the actual intersections between objects; finally,

collision response determines what actions should be taken in response to

the collision of two objects.

In Section 17.1 we discuss simple and extremely fast collision detection

techniques. The main idea is to approximate a complex object using a set of

lines. These lines are then tested for intersection with the primitives of the

environment. This technique is often used in games. Another approxima-

tive method is described in Section 17.2,whereaBSPtreerepresentation

of the environment is used, and a cylinder may be used to describe a char-

acter. However, all objects cannot always be approximated with lines or

cylinders, and some applications may require more accurate tests.

Imagine, for example, that we want to determine whether a three-

dimensional hand collides with (grabs) a three-dimensional cup of tea,

where both objects are represented by triangles. How can this be done

efficiently? Certainly, each triangle of the hand can be tested for intersec-

tion with each triangle of the cup of tea using the triangle/triangle inter-

section tests from Section 16.11. But in the case where the two objects

793

i

i

i

i

i

i

i

i

794 17. Collision Detection

Figure 17.1. On the left, collision detection and response computed for many barrels

colliding against themselves and the environment. On the right, more chaos. (Image on

the left courtesy of Crytek, on the right courtesy of Valve Corp.)

are far from each other, an algorithm should report this quickly, which

would be impossible with such exhaustive testing. Even when the objects

are close together, exhaustive testing is not efficient. There is a need for

algorithms that handle these cases rapidly. It is easy to think of more

complex scenarios for collision detection, and one such example is shown in

Figure 17.1.

Section 17.3 deals with a general, hierarchical bounding volume collision

detection algorithm. One particular implementation based on OBBs is then

presented in Sections 17.4. The following features are characteristics that

are desirable for most CD systems.

• They achieve interactive rates with models consisting of a large num-

ber of polygons, both when the models are far from each other and

when they are in close proximity.

• They handle polygon soups, i.e., general polygon models with no re-

strictions such as convexity or the availability of adjacency informa-

tion.

• The models can undergo rigid-body motion, i.e., rotation plus trans-

lation, or even more general types of deformation.

• They provide efficient bounding volumes (BVs), in that they try to

create tight fitting volumes for a set of geometry. Small BVs improve

the performance of algorithms that determine whether there are col-

lisions between two objects. The creation of the BVs should also be

fast.

Since a scenario may contain tens or hundreds of moving objects, a

good CD system must be able to cope with such situations as well. If