Game Development Reference
In-Depth Information
Figure 17.4 Spatial detection between polyhedrons
Figure 17.5 Spatial intersection between triangles
(Boyse, 1979; Moore et al., 1988). Another solution involves testing the intersection
of polygons (divided into triangles, if required) of two polyhedrons with each other
(Möller, 1997) (see figure 17.5). First it is verified whether all the points of one of the
triangles are on the same side of the supporting plane of the other triangle. If these
two trivial tests fail, then we eliminate the case in which the planes are parallel (no
intersection) or congruent (comparison of triangles in 2D). In case of secant planes,
the line of intersection of two planes is considered. Then the intersections between the
line obtained and the two triangles are found. These intersections, if they exist, are
segments which can be defined on the line by parametric coordinates of the end points.
The intersection of two triangles can then be ascertained only by comparing these
coordinates to know whether the two segments intersect each other. Another approach
involves calculating only one segment from one of the triangles and comparing it
directly with the other triangle. Several improvements were suggested later (Guigue
& Devillers, 2003). Remember that all the tests of collision between triangles are to
be performed before concluding that they do not collide. The complexness of these
algorithms is thus quadratic.
However, a mere enumeration of incident polygons is not sufficient to completely
define an overlap. An additional construction is necessary to find the surfaces that
Search Nedrilad ::




Custom Search