Game Development Reference

In-Depth Information

Figure 17.3
Problem of detection in case of a division into convex parts

objects into convex parts, but in that case, the results obtained can have some lacunas.

For example, in figure 17.3, we obtain several overlap measurements, depending on

the decomposition we select. In an application that is looking for a global character-

isation of the collision (for example by a translation separating the two objects), the

object division proves to be inadequate. Finding a separator plane requires determin-

ing parameters
a
,
b
,
c
and
d
of the equation of the plane so that
ax

+

by

+

cz

+

d >
0

for all the vertices of one polyhedron and
ax

d <
0 for the vertices of the

other polyhedron. This problem is generally settled by linear programming. Using the

simulated annealing method can also be effective (Zachmann, 2001).

If the distance between polyhedrons is to be found, the methods consist of con-

verging on the surfaces closest to the two polyhedrons. For this purpose, each object is

approximated by a hierarchy of bounding volumes (Quinlan, 1994; Johnson&Cohen,

1998; Ehmann & Lin, 2001).

The root volume includes the entire object. The volumes of intermediate nodes

include parts of the object; the parts become smaller as we move down the hierarchy.

At the level of leaves, the volume includes only one surface of the object. Methods for

constructing such a hierarchy are studied in section 17.2.3.1. Let
d
be an estimation

of the minimum distance (measured between any two polygons of the object or up to

infinity). Going through the two hierarchies makes it possible to delete all the pairs of

polygons not involved in the calculation of the minimum distance at the same time,

by ignoring the volume pairs separated by a distance more than
d
. When two volumes

are at a distance less than
d
and they are the leaves of the tree, then we calculate the

distance between the corresponding surfaces. If this distance is less than
d
, we modify

d
and continue the algorithm until the distance between the last two pairs of primitives

that modified
d
is found. When the distance between objects is nil, a different algorithm

should be used to characterise the intersection. Intersection of two polyhedrons is not

empty if and only if one of the following two conditions is verified:

+

by

+

cz

+

•

One vertex of one polyhedron belongs to the other;

•

One edge of one of them cuts one surface of the other.

These conditions are often, but not necessarily, checked simultaneously. In figure 17.4,

the intersections of polyhedrons are characterised by a vertex of a polyhedron located

in the other and/or an edge of this polyhedron passing through a surface of the other

Search Nedrilad ::

Custom Search