Find whether two triangles intersect or not

问题:

Given 2 set of points

((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and

((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space.

How will you find out whether these triangles intersect or not?

One obvious solution to this problem is to find the equation of the plane formed by each triangle. If the planes are parallel, then they don't intersect.

Else, find out the equation of line formed by the intersection of these planes using the normal vectors of these planes.

Now, if this line lies in both of the triangular regions, then these two triangles intersect, otherwise not.

trianglesIntersect(Triangle T1, Triangle T2)
{
   if(trianglesOnParallelPlanes(T1, T2))
   {
      return false
   }
   Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2))
   if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1))
   {
      return true
   }
   return false
}

Given that I know how to write the above functions, what other implementations of trianglesIntersect should I consider?

Are there faster algorithms that solve this problem?

回答1:

Visit this table of geometric intersection algorithms courtesy of realtimerendering.com, look at the entry for triangle/triangle intersections, and follow the references, for example to Christer Ericson, Real-Time Collision Detection, page 172. (A book which I recommend highly.)

The basic idea is straightforward. If two triangles intersect, then either two edges of one triangle intersect the other (left configuration in the diagram below), or one edge of each triangle intersects the other (right configuration).

So perform six line segment–triangle intersection tests and see if either of these configurations is found.

Now, you ask, how do you do a line segment/triangle intersection test? Well, it's easy. Visit this table of geometric intersection algorithms, look at the entry for line segment (ray)/triangle intersections, and follow the references...

(It's important to mention that the simple test outlined above doesn't handle coplanar triangles correctly. For many applications this does not matter: for example, when detecting a collision between meshes of triangles, the coplanar cases are ambiguous so it does not matter which result is returned. But if your application is one of the exceptions, you'll need to check for that as a special case, or read on in Ericson for some other methods, for example, the separating-axis method, or Tomas Möller's interval overlap method.)