Graphics Reference
In-Depth Information
in
A
and points in
B
. When the distance is zero, the objects are intersecting. Having
a distance measure between two objects is useful in that it allows for prediction of
the next time of collision. A more general problem is that of finding the
closest points
of
A
and
B
: a point in
A
and a point in
B
giving the separation distance between
the objects. Note that the closest points are not necessarily unique; there may be
an infinite number of closest points. For dynamic objects, computing the next time
of collision is known as the
estimated time of arrival
(ETA) or
time of impact
(TOI)
computation. The ETA value can be used to, for instance, control the time step in a
rigid-body simulation. Type of motion is one of the simulation parameters discussed
further in the next section.
2.4
Environment Simulation Parameters
As mentioned earlier in the chapter, several parameters of a simulation directly affect
what are appropriate choices for a collision detection system. To illustrate some of the
issues they may cause, the following sections look specifically at how the number of
objects and how the objects move relate to collision processing.
2.4.1
Number of Objects
Because any one object can potentially collide with any other object, a simulation
with
n
objects requires (
n
O
(
n
2
) pairwise tests,
worst case. Due to the quadratic time complexity, naively testing every object pair
for collision quickly becomes too expensive even for moderate values of
n
. Reducing
the cost associated with the pairwise test will only linearly affect runtime. To really
speed up the process, the number of pairs tested must be reduced. This reduction is
performed by separating the collision handling of multiple objects into two phases:
the
broad phase
and the
narrow phase
.
The broad phase identifies smaller groups of objects that
may
be colliding and
quickly excludes those that definitely
are not
. The narrow phase constitutes the pair-
wise tests within subgroups. It is responsible for determining the exact collisions, if
any. The broad and narrow phases are sometimes called n-
body processing
and
pair
processing
, respectively.
Figure 2.4 illustrates how broad-phase processing reduces the workload through a
divide-and-conquer strategy. For the 11 objects (illustrated by boxes), an all-pairs test
would require 55 individual pair tests. After broad-phase processing has produced 5
disjoint subgroups (indicated by the shaded areas), only 10 individual pair tests would
have to be performed in the narrow phase. Methods for broad-phase processing are
discussed in Chapters 6 through 8. Narrow-phase processing is covered in Chapters
4, 5, and 9.
In addition to the number of objects, the relative size of the objects also affects how
many tests have to be performed. With both small and large objects present in a scene,
−
1)
+
(
n
−
2)
+···+
1
=
n
(
n
−
1)/2
=
