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
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
i
i
i
i
i
i
i
i
796 17. Collision Detection
Figure 17.2. Instead of computing the collision between the entire car and the environ-
ment (the road), we place a ray at each wheel. These rays are then tested for intersection
against the environment.
the environment. If the distance from a ray origin to the environment is
zero, then that wheel is exactly on the ground. If the distance is greater
than zero, then that wheel has no contact with the environment, and a
negative distance means that the wheel has penetrated the environment.
The application can use these distances for computing a collision response—
a negative distance would move the car (at that wheel) upward, while a
positive distance would move the car downward (unless the car is flying
though the air for a short while). Note that this type of techniques could
be harder to adapt to more complicated scenarios. For example, if the car
crashes and is set in rotating motion, many more rays in different directions
are needed.
To speed up the intersection testing, we can use the same technique
we most often use to speed things up in computer graphics—a hierar-
chical representation. The environment can be represented by an axis-
aligned BSP tree (which is essentially the same as a k-d tree). BSP
trees are presented in Section 14.1.2, where they were used for view frus-
tum culling algorithms. BSP trees can also be used to speed up inter-
section testing. Depending on what primitives are used in the environ-
ment, different ray-object intersection test methods are needed (see Chap-
ter 16). A BSP tree is not the only representation that can be used
to find intersections quickly—e.g., a bounding volume hierarchy is also
usable.
Unlike standard ray tracing, where we need the closest object in front of
the ray, what is actually desired is the intersection point furthest back along
the ray, which can have a negative distance. To avoid having to treat the
ray as searching in two directions, the test ray’s origin is essentially moved
back until it is outside the bounding box surrounding the environment, and
is then tested against the environment. In practice, this just means that,
instead of a ray starting at a distance 0, it starts at a negative distance
that lets it begin outside the box. To handle a more general setting, such
as driving a car through a tunnel and detecting collision against the roof,
one would have to search in both directions though.
i
i
i
i
i
i
i
i
17.2. Dynamic CD using BSP Trees 797
Figure 17.3. To the left is some geometry (blue) seen from above. Its BSP tree is shown
in the middle. To test this tree against a circle with origin at p, the BSP tree is grown
outwards with the circle’s radius, and then the point p can instead be tested against
the grown BSP tree. This is shown to the right. Notice that the corners should really
be rounded, so this is an approximation that the algorithm introduces.
17.2 Dynamic CD using BSP Trees
Here, the collision detection algorithm by Melax [854, 855] will be pre-
sented. It determines collisions between the geometry described by a BSP
tree (see Section 14.1.2), and a collider that can be either a sphere, a cylin-
der, or the convex hull of an object. It also allows for dynamic collision
detection. For example, if a sphere moves from a position p
0
at frame n to
p
1
at frame n + 1, the algorithm can detect if a collision occurs anywhere
along the straight line path from p
0
to p
1
. The presented algorithm has
been used in commercial games, where a character’s geometry was approx-
imated by a cylinder.
The standard BSP tree can be tested against a line segment very effi-
ciently. A line segment can represent a point (particle) that moves from
p
0
to p
1
. There may be several intersections, but the first one (if any)
represents the collision between the point and the geometry represented in
the BSP tree. Note that, in this case, the BSP tree is surface aligned, not
axis-aligned. That is, each plane in the tree is coincident with a wall, floor,
or ceiling in the scene. This is easily extended to handle a sphere, with
radius r,thatmovesfromp
0
to p
1
instead of a point. Instead of testing
the line segment against the planes in the BSP tree nodes, each plane is
moved a distance r along the plane normal direction (see Section 16.18 for
similar ways of recasting intersection tests). This sort of plane adjustment
is illustrated in Figure 17.3. This is done for every collision query on the fly,
so that one BSP tree can be used for spheres of any size. Assuming a plane
is π : n·x+ d = 0, the adjusted plane is π
: n ·x+d±r =0,wherethesign
of r depends on which side of the plane you continue testing/traversing in
search of a collision. Assuming that the character is supposed to be in the
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.