判断两个三角形是否相交

Question

给定两组三维空间中的点((x1,y1,z1),(x2,y2,z2),(x3,y3,z3))和((p1,q1,r1),(p2,q2,r2),(p3,q3,r3))，它们各自形成一个三角形。你该如何判断这两个三角形是否相交？

其中一个明显的解决方法是找到每个三角形所在平面的方程。如果这些平面是平行的，则它们不相交。

否则，使用这些平面的法向量来找到它们的交线的方程。

现在，如果这条直线位于这两个三角形区域内，则这两个三角形相交，否则不相交。

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
}

既然我知道如何编写上述功能，那么还有哪些triangleIntersect的实现方法值得考虑？

是否存在解决这个问题更快的算法？

- Atishay

---

请尝试在 math.stackexchange.com 上提问。SO 是用于编程问题的。 - PengOne

我很失望这个问题被关闭了。这是一个在计算机图形、光线追踪和视频游戏中经常出现的众所周知的编程问题。我自己已经多次编写过它。为什么这里不符合主题呢？ - Gareth Rees

从常见问题解答中得知：该网站适合提问"特定的编程问题"或"软件算法"，这不是一个"数学"问题，更像是计算几何问题，并且在图形、游戏、模拟等领域经常涉及。 - phkahler

您的意思是编程问题和数学问题是两个不相交的集合吗？ - Atishay

现在，如果这条线段位于两个三角形区域中，则这两个三角形相交，否则不相交。我认为这是不正确的。请参考Tomas Möller论文中的图示（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.9981&rep=rep1&type=pdf），其中有一个反例。在这种情况下，您需要进行额外的区间测试。 - Joh

Answer 1

请访问这个几何交集算法表格，由realtimerendering.com提供，查看三角形/三角形交集的条目，并跟随参考链接，例如Christer Ericson的Real-Time Collision Detection 书中第172页。（我强烈推荐这本书。）

基本思想很简单。如果两个三角形相交，则一个三角形的两条边会与另一个三角形相交（如下图左侧配置），或者每个三角形的一条边与另一个三角形的一条边相交（如下图右侧配置）。

执行六个线段-三角形交点测试，看是否找到其中任何一个配置。现在，你可能会问，如何进行线段/三角形交点测试？好吧，这很容易。请访问此几何交点算法表，查看线段（射线）/三角形交点的条目，并跟随参考...（需要注意的是，上述简单测试不能正确处理共面三角形。对于许多应用程序，这并不重要：例如，在检测三角形网格之间的碰撞时，共面情况是模糊的，因此返回哪个结果并不重要。但是，如果您的应用程序是其中之一，则需要将其视为特殊情况进行检查，或者继续阅读Ericson中的其他方法，例如分离轴方法，或Tomas Möller的区间重叠方法。）

- Gareth Rees

---

共面三角形（使用平面方程式检测相对容易，其中normal1==normal2 and d1==d2），可以通过在所有三角形顶点上使用重心坐标的ptInPoly测试轻松进行测试。 - bobobobo

顺便提一下，Moller区间重叠方法的C代码在此处。 - bobobobo

共面重叠并不像角落测试那样简单，因为仅靠这些测试无法检测到六芒星配置。如果需要检测相对朝向的三角形之间的交点，则相等性测试可能还需要考虑否定平面。 - tombola

你需要测试所有六条线吗？感觉在进行五次测试后你就已经知道答案了，因为在两种情况下都有两条线与三角形相交。在第一种情况下，这两条线都属于上部（内部！）的三角形；在第二种情况下，每个三角形的一条线穿过另一个三角形。 - Dewi Morgan

Answer 2

我实现了使用定向边界框进行动态碰撞检测中描述的算法，仅适用于非共面三角形，并基于分离轴定理。

这是我的GitHub存储库，其中包含代码（在文件collision-tests.js中）和演示/测试页面：

• kenny-evitt/three-js-triangle-triangle-collision-detection: 在three.js中实现三角形-三角形碰撞检测

该代码故意编写以匹配“动态碰撞”文档的相关部分。下面是交点测试函数（以及整个collision-tests.js文件的全部内容）。请注意，three.js三角形对象具有三个顶点的a、b和c属性。

/**
 * @function
 * @param {THREE.Triangle} t1 - Triangular face
 * @param {THREE.Triangle} t2 - Triangular face
 * @returns {boolean} Whether the two triangles intersect
 */
function doTrianglesIntersect(t1, t2) {

  /*
  Adapated from section "4.1 Separation of Triangles" of:

   - [Dynamic Collision Detection using Oriented Bounding Boxes](https://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf)
  */


  // Triangle 1:

  var A0 = t1.a;
  var A1 = t1.b;
  var A2 = t1.c;

  var E0 = A1.clone().sub(A0);
  var E1 = A2.clone().sub(A0);

  var E2 = E1.clone().sub(E0);

  var N = E0.clone().cross(E1);


  // Triangle 2:

  var B0 = t2.a;
  var B1 = t2.b;
  var B2 = t2.c;

  var F0 = B1.clone().sub(B0);
  var F1 = B2.clone().sub(B0);

  var F2 = F1.clone().sub(F0);

  var M = F0.clone().cross(F1);


  var D = B0.clone().sub(A0);


  function areProjectionsSeparated(p0, p1, p2, q0, q1, q2) {
    var min_p = Math.min(p0, p1, p2),
        max_p = Math.max(p0, p1, p2),
        min_q = Math.min(q0, q1, q2),
        max_q = Math.max(q0, q1, q2);

    return ((min_p > max_q) || (max_p < min_q));
  }


  // Only potential separating axes for non-parallel and non-coplanar triangles are tested.


  // Seperating axis: N

  {
    var p0 = 0,
        p1 = 0,
        p2 = 0,
        q0 = N.dot(D),
        q1 = q0 + N.dot(F0),
        q2 = q0 + N.dot(F1);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Separating axis: M

  {
    var p0 = 0,
        p1 = M.dot(E0),
        p2 = M.dot(E1),
        q0 = M.dot(D),
        q1 = q0,
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E0 × F0

  {
    var p0 = 0,
        p1 = 0,
        p2 = -(N.dot(F0)),
        q0 = E0.clone().cross(F0).dot(D),
        q1 = q0,
        q2 = q0 + M.dot(E0);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E0 × F1

  {
    var p0 = 0,
        p1 = 0,
        p2 = -(N.dot(F1)),
        q0 = E0.clone().cross(F1).dot(D),
        q1 = q0 - M.dot(E0),
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E0 × F2

  {
    var p0 = 0,
        p1 = 0,
        p2 = -(N.dot(F2)),
        q0 = E0.clone().cross(F2).dot(D),
        q1 = q0 - M.dot(E0),
        q2 = q1;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E1 × F0

  {
    var p0 = 0,
        p1 = N.dot(F0),
        p2 = 0,
        q0 = E1.clone().cross(F0).dot(D),
        q1 = q0,
        q2 = q0 + M.dot(E1);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E1 × F1

  {
    var p0 = 0,
        p1 = N.dot(F1),
        p2 = 0,
        q0 = E1.clone().cross(F1).dot(D),
        q1 = q0 - M.dot(E1),
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E1 × F2

  {
    var p0 = 0,
        p1 = N.dot(F2),
        p2 = 0,
        q0 = E1.clone().cross(F2).dot(D),
        q1 = q0 - M.dot(E1),
        q2 = q1;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E2 × F0

  {
    var p0 = 0,
        p1 = N.dot(F0),
        p2 = p1,
        q0 = E2.clone().cross(F0).dot(D),
        q1 = q0,
        q2 = q0 + M.dot(E2);

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E2 × F1

  {
    var p0 = 0,
        p1 = N.dot(F1),
        p2 = p1,
        q0 = E2.clone().cross(F1).dot(D),
        q1 = q0 - M.dot(E2),
        q2 = q0;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  // Seperating axis: E2 × F2

  {
    var p0 = 0,
        p1 = N.dot(F2),
        p2 = p1,
        q0 = E2.clone().cross(F2).dot(D),
        q1 = q0 - M.dot(E2),
        q2 = q1;

    if (areProjectionsSeparated(p0, p1, p2, q0, q1, q2))
      return false;
  }


  return true;
}

- Kenny Evitt