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
·
=