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