判断两个三角形是否相交 [英] Find whether two triangles intersect or not

问题描述

给定 2 组点

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

((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) 每个在 3D 空间中形成一个三角形.

如何判断这些三角形是否相交?

这个问题的一个明显解决方案是找到每个三角形形成的平面的方程.如果平面平行，则它们不相交.

否则，使用这些平面的法向量找出这些平面相交形成的直线方程.

现在，如果这条线位于两个三角形区域中，那么这两个三角形相交，否则不相交.

trianglesIntersect(Triangle T1, Triangle T2){如果(trianglesOnParallelPlanes(T1，T2)){返回假}线 L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2))如果(lineOnTriangle(T1，L1)和 lineOnTriangle(T2，L1)){返回真}返回假}

鉴于我知道如何编写上述函数，我应该考虑其他哪些 trianglesIntersect 实现?

有没有更快的算法可以解决这个问题?

解决方案

访问 ，查看线段(射线)/三角形相交的条目，并按照参考...

(重要的是要提到上面概述的简单测试不能正确处理共面三角形.对于许多应用程序来说，这并不重要:例如，当检测三角形网格之间的碰撞时，共面情况是不明确的，所以它确实不管返回哪个结果.但是如果您的应用程序是例外之一，您需要将其作为特殊情况进行检查，或者在 Ericson 中继续阅读以了解其他一些方法，例如 分离轴法，或 Tomas Möller 的 区间重叠法.)

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?

解决方案

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.)

这篇关于判断两个三角形是否相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！