Game Development Reference

In-Depth Information

Figure 17.8
Temporal detection between polyhedrons

necessary to use the selected interpolation to position the objects in accordance with

collision detection.

Boyse (1979) shows that when two polyhedral objects collide, it is always when an

edge (including its end points) of one of the objects collides with a surface of the other

object. Two situations are then possible: Either an end of the edge hits the surface or

the edge touches one of the borders of the surface (see figure 17.8). Purely geometrical

approaches are possible, but in most of the cases we form an analytical system whose

main objective is to find the moment of the contact. All pairs formed by a surface of one

object and a surface of the other object are considered. The surfaces are assumed to be

triangular and the path of their vertices is assumed to be uniformly straight. In this case,

it is necessary to define if a vertex of the polyhedron crosses a triangle or if two edges of

triangles cross each other. The equation of interaction between a vertex
P
and a surface

(
A, B, C
) is determined by solving equation
−−
AM

(
−
AB

∧
−
AC
)

0. If the surface is rigid,

our position can be on a reference point where this surface is fixed. Only
−−
AM
depends

on time, the equation is thus linear (Moore et al., 1988). In case of a deformable surface

(no rigidity constraint is imposed), equation
−−
AM
(
t
)

·

=

(
−
AB
(
t
)

∧
−
AC
(
t
))

0, which is a 3

degree equation, is solved (Provot, 1997). The collision of two edges is settled on a

similar principle. Edges [
AB
] and [
CD
] are in the same plane if
−
AC

·

=

(
−
AB

∧
−
CD
)

0.

This equation is a 2 degree equation for rigid edges and 3 degree for deformable

edges. The assumption of a uniformly straight path is however inconvenient; it leads

to a deformation of triangles as soon as there is a rotation in the movement. It is

necessary to use more complex paths to ensure that the triangle does not deform.

Redon (Redon et al., 2000; Redon et al., 2002a) suggests an interpolation of the path

by an intermediate screw-like motion, closer to the real movement of a rigid body.

In case of more complex geometries and/or intermediate movements, the analytical

problem can be impossible to solve. One of the solutions in this case is considering the

volume scanned by the objects between two moments. Then the intersection of these

volumes is calculated to find the first moment of the contact. In mathematical terms,

this means not testing the intersection of two 4D hyper-volumes (spatio-temporal

·

=

Search Nedrilad ::

Custom Search