找出两个三角形是否相交

Question

给出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)
{
   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
}

鉴于我知道如何编写上述函数,我应该考虑使用trianglesIntersect的其他实现吗？

是否有更快的算法来解决这个问题？

Answer 1

请访问realtimerendering.com提供的几何交叉算法表,查看三角形/三角形交叉点的条目,并按照参考文献,例如Christer Ericson,Real-Time Collision Detection,第172页.(我推荐的一本书.)

基本想法很简单.如果两个三角形相交,则一个三角形的两个边与另一个相交(下图中的左边配置),或者每个三角形的一个边与另一个相交(右边配置).

因此,执行六个线段 - 三角形相交测试,看看是否找到了这些配置中的任何一个.

现在,您问,您如何进行线段/三角交叉测试？嗯,这很容易.访问此几何交叉算法表,查看线段(光线)/三角形交叉点的条目,并按照参考资料...

(重要的是要提到上面概述的简单测试不能正确处理共面三角形.对于许多应用而言,这并不重要:例如,当检测到三角形网格之间的碰撞时,共面情况是模糊的,因此无关紧要返回结果.但是如果您的应用程序是例外情况之一,则需要将其作为特殊情况进行检查,或者在Ericson中阅读其他一些方法,例如,分离轴方法或TomasMöller的间隔重叠方法.)