三角形-三角形相交测试

Question

我想知道在3D环境中是否有一些教程或指南来理解和实现三角形与三角形的相交测试（我不需要知道交点的精确位置，只需要知道是否发生了相交）。

我原本打算按照一个理论pdf来实现它，但我在第5步卡住了：

1. 计算三角形2的平面方程。 2. 如果三角形1的所有点都在同一侧，则拒绝为微不足道。 3. 计算三角形1的平面方程。 4. 如果三角形2的所有点都在同一侧，则拒绝为微不足道。 5. 计算交点线并投影到最大轴上。 6. 计算每个三角形的间隔。 7. 相交间隔。

对于这个指南中的第5点，我真的不知道在问什么（5、6和7）。XD

由于我对数学没有很高的认识（好吧，我只是通过大学的几门考试学过一点（我是一个初级程序员XD），所以请尽可能简单地与我交流。:D（我尝试在谷歌上搜索，但大多数链接都指向一些充满公式的4-5页内容，我真的不关心也不理解。）

感谢您的帮助。

- feal87

---

这是一个3D还是2D的问题？ - Jon Seigel

一般来说，程序员需要了解数学呢 :-P - Cory Charlton

说真的，如果你不理解它，就不要去实现它。如果你选择实现它，然后它在以后出了问题（或者根本从一开始就没有工作），你就无法确定为什么出了问题，甚至不能确定它是否已经出了问题。我并不是说不要去实现它，而是说不要跳过理解它所需的时间投资。 - Cory Charlton

嗯...它是3D的。 抱歉，我只懂简单的数学。XD - feal87

我正在努力理解它，但是我在网上找到的所有理论信息都只是向我泼洒了大量的公式等等... :( - feal87

Answer 1

您说：

我想知道是否有一些教程或指南来了解并在3D环境中实现三角形-三角形相交测试。

然后你说：

大多数链接都指向一些我不太想了解的公式填满的4-5页内容

我注意到这两个说法完全相互矛盾。那么是哪一个？你想理解三角形 - 三角形相交如何工作，还是你只是想要一个有效的实现，但你不理解它？

并不是所有这些网页都充满了不必要的数学。理解相交算法需要必要的数学知识。从头开始学习所有内容。

一旦你知道这些单词的含义，步骤5、6和7就很容易理解了。相交线是由两个平面相交形成的线。每个三角形都位于一个平面上。有三种情况：

• 两个平面平行且不相交。三角形明显不相交。
• 两个平面相同。三角形可能相遇，也可能不相遇。
• 两个不同的平面在一条线上相交。如果三角形相交，则它们显然必须在该线上相交。

假设我们处于第三种情况。计算包含在第一个三角形中的相交线段。计算包含在第二个三角形中的相交线段。问题现在是“这些线段重叠吗？”

您可以通过将线段投影到方便的轴上，然后查看该轴上的线段是否重叠来解决这个问题。基本上，它的工作原理是这样的：想象一下，您正在对线段照射光，使它们在轴上产生阴影。如果轴上的阴影相交，则线段必须相交。如果轴上的阴影之间存在间隙，则线段之间肯定存在间隙，因此三角形不相交。

如果你想了解这是如何工作的，那么你必须理解所有这些内容 - 所有代数方程式，它们用于计算平面相交和投影到轴上的方式。这些基础知识是必要的，也是更复杂的变换、投影等构建的基石，因此如果您想更深入地了解，请彻底理解这些基础知识。

- Eric Lippert

---

很好的解释。如果这些PDF能够以这种方式解释，我就不会为了理解而感到困难了。:D 问题解决了。 - feal87

@feal87：这里的重要教训是学会从呈现的公式中提取洞见。也就是说，既然已经向你解释了公式背后的洞见，那么你能否通过公式并看到这些洞见？你能否利用这种经验在未来自己提取洞见？ - jason

Answer 2

我的答案很简单...在任意坐标系中，这个问题很难，所以将其转换为使问题变得容易的东西。XNA中的Matrix类具有CreateLookAt函数，可用于创建所有顶点上有用的转换。

以下示例未经过优化，仅用于理解解决方案。所有异常及其相应的if语句都可以删除，同时还可以删除一些向量变换。

    public static bool CheckColision(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//rotates each edge of the first triangle to the Z axis and checks the second triangle against it then repeats with the second one against the first, and lastly checks to see if all points of the second triangle are on the same side as the first
        if(! CheckColisionLookAt(t1a, t1b, t1c, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1b, t1c, t1a, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1c, t1a, t1b, t2a, t2b, t2c))
            return false;

        if (!CheckColisionLookAt(t2a, t2b, t2c, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2b, t2c, t2a, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2c, t2a, t2b, t1a, t1b, t1c))
            return false;

        return CheckColisionAllOnOneSide(t1a, t1b, t1c, t2a, t2b, t2c);
    }

    public static bool CheckColisionAllOnOneSide(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//simply performs a transformation to check if all points on one triangle are on the same side of the other triangle
        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.X < 0 && t2b.X < 0 && t2c.X < 0)
            return false;
        if (0 < t2a.X && 0 < t2b.X && 0 < t2c.X)
            return false;
        return true;
    }

    public static bool CheckColisionLookAt(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//performs a transformation and checks if all points of the one triangle are under the other triangle after the transformation

        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t1a = Vector3.Transform(t1a, m);//  (0,     0,      0)
        if ( ZERRO < Math.Abs(t1a.X)|| ZERRO < Math.Abs(t1a.Y) || ZERRO < Math.Abs(t1a.Z))
            throw new Exception();
        t1b = Vector3.Transform(t1b, m);//  (0,     0,      maxZ)
        if (ZERRO < Math.Abs(t1a.X) || ZERRO < Math.Abs(t1a.Y))
            throw new Exception();
        t1c = Vector3.Transform(t1c, m);//  (0,     maxY,   someZ)
        if (ZERRO < Math.Abs(t1a.X))
            throw new Exception();
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.Y < 0 && t2b.Y < 0 && t2c.Y < 0)
            return false;
        return true;
    }

- Kyle Fillingim

Answer 3

这是一个包含许多交叉引用的网站：

实时渲染物体/物体交叉页面

以下是他们列出的Tri/Tri内容：

Möller jgt 2(2);
Held jgt 2(4);
GTweb;
Möller;
GPG p.393;
GTCG p.539;
TGS;
RTCD p.155,172;
Shen jgt 8(1);
Guigue jgt 8(1);
SoftSurfer;
《实时渲染》第二版 p.590;
《实时渲染》第三版 p.757

- Frank Krueger

---

我正在查看此链接中的代码...希望我能理解它们。XD - feal87

Answer 4

我假设您已经有了三角形顶点的x，y坐标。 例如：
对于三角形A：
1. 边A1：xa1，ya1 2. 边A2：xa2，ya2 3. 边A3：xa3，ya3 对于三角形B：
1. 边B1：xb1，yb1 2. 边B2：xb2，yb2 3. 边B3：xb3，yb3

如果它们的任何线段相交，则三角形相交。这意味着如果A1与B1或B2或B3相交，或者如果A2与B1或B2或B3相交，或者如果A3与B1或B2或B3相交。

因此，您需要算法来检测两条线是否相交。这是我找到的最简单的示例：http://www.mathopenref.com/coordintersection.html

- papadi

---

抱歉，我在问题中没有表达得很清楚。我是在谈论三维环境中的三角形。 - feal87

这不是一个正确的算法。如果一个三角形完全在另一个三角形内部，会怎样呢？这时它们的任何边都不会相交，但是这两个三角形却相交了。 - Eric Lippert

在 Papadi 描述的检查之后，您可以计算两个三角形的面积。 取较小者的任意一点，通过将该点与较大三角形中的每个点连接而创建3个新三角形。 然后计算3个新三角形的面积。 如果它正好等于最大三角形的面积，则较小的三角形位于较大三角形内部。 这不是最有效的方法，但如果您希望尽可能地简化数学，这样做还是不错的。 - Gravitate

Answer 5

你发布的方法看起来像是使用了类似于这个算法来检测凸多边形是否相交，基于分离轴定理。这并不难理解。

如果可以在两个多边形之间画一条被称为分离轴的线，则它们不相交。每个多边形的每条边都是候选的分离轴。将多边形投影到垂直于该轴的向量上，并测试1D范围是否重叠。如果没有1D重叠，则当前边是一个分离轴，两个多边形不相交。如果有1D重叠，则结果不确定，直到所有候选边都被测试过后，才得出两个多边形相交的结论。请注意，两个多边形允许共享一条边。

- Scottie T