i
i
i
i
i
i
i
i
17.1. Collision Detection with Rays 795
the scenario contains n moving objects and m static objects, then a naive
method would perform
nm +
n
2
= nm + n(n − 1)/2 (17.1)
object tests for each frame. The first term corresponds to testing the
number of static objects against the dynamic (moving) objects, and the
last term corresponds to testing the dynamic objects against each other.
The naive approach quickly becomes expensive as m and n rise. This
situation calls for smarter methods, which are the subject of Section 17.5.
Such a method typically uses an algorithm that first detects all potential
object-to-object collisions, which are then resolved using, for example, the
OBBTree algorithm from Section 17.4.
After discussing hierarchical collision detection, brief subsections fol-
low on several miscellaneous topics. Time-critical collision detection is a
technique for doing approximate collision detection in constant time, and is
treated in Section 17.6.1. Sometimes the shortest distance between two ob-
jects is desired, and this topic is introduced next, followed by some research
on collision detection for deformable objects. Finally, collision response is
briefly covered.
It must be pointed out that performance evaluations are extremely dif-
ficult in the case of CD, since the algorithms are sensitive to the actual
collision scenarios, and there is no algorithm that performs best in all
cases [433].
17.1 Collision Detection with Rays
In this section, we will present a fast technique that works very well under
certain circumstances. Imagine that a car drives upward on an inclined
road and that we want to use the information about the road (i.e., the
primitives of which the road is built) in order to steer the car upward. This
could, of course, be done by testing all primitives of all car wheels against all
primitives of the road, using the techniques from Section 17.3. However, for
games and some other applications, this kind of detailed collision detection
is not always needed. Instead, we can approximate a moving object with
asetofrays. In the case of the car, we can put one ray at each of the four
wheels (see Figure 17.2). This approximation works well in practice, as long
as we can assume that the four wheels are the only places of the car that
will be in contact with the environment (the road). Assume that the car is
standing on a plane at the beginning, and that we place each ray at a wheel
so that each origin lies at the place where the wheel is in contact with the
environment. The rays at the wheels are then intersection-tested against