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''.

Search Nedrilad ::

Custom Search