Game Development Reference
In-Depth Information
as these primitives constitute the basis of graphic libraries, but can have the disadvan-
tage of being relatively less accurate in the case of CAD models. These primitives are,
however, quite often “organised'' in polyhedrons, which are mostly bordered. When
a bordered polyhedron is convex, it is known as polytope . The most efficient algo-
rithms are generally specific to polytopes because they can take advantage of some
smart mathematical properties of convexity. Which is why the next part differentiates
between algorithms dedicated to convex objects and those dedicated to non-convex
objects or having a structure without topological link 1 .
17.1.1 Definition of collision
A traditional approach of collision detection involves verifying if two objects are occu-
pying the same position in the space (in case of multiple objects, the collision is for each
pair of objects). We can thus say that there is a collision when the minimum distance
δ min between a given part of the objects is less than a fixed threshold ε .If δ min < 0,
we call it interpenetration .If0
ε ,itisa contact .If δ min , the objects do not
collide; they are separated . The intersection can be constructed (an operation known
in CAD) to characterise an interpenetration. However, the complete geometry of the
intersection is rarely used. In certain methods of simulation, we might require to antic-
ipate the collision of two objects to prevent them from overlapping. For this purpose,
it is enough to monitor the progress of separation between objects. The approaches
that can be taken to qualify the intersection of two objects can be classified as per the
quantity of information sent:
δ min
Separation (blank intersection): The response of this algorithm is purely Boolean;
Distance(s) separating two objects: Collision is detected by a distance calculating
algorithm;
Topology of intersection or contact: These algorithms provide a set of incident
primitives, and if required, classify the intersection or contact zones into groups;
Quantification of interpenetration: either by its shape or by defining a measure-
ment - in the mathematical sense - that can be linked to the estimation of the
interpenetration volume or, in a less evident manner, to the smallest movement
(translation and/or rotation) separating the objects;
Moment of contact: These methods, called “spatio-temporal'' (or only “temporal'')
methods, consider the movement and determine the moment and the configuration
of the contact.
The choice of approach depends essentially on the application. The last category of
methods differs from the rest as it considers an additional dimension: time ; the problem
then appears as a 4D collision detection. Here we are specifically talking of contact
detection.
17.1.2 Spatial detection between convex polyhedrons
That is, two polytopes - A and B . Let's assume that the problem to be solved is answer-
ing the question: Do the polytopes overlap? To quickly determine the answer, we can
1 We then talk about “polygon soup''.