三维空间中的三角形相交问题

Question

我正在处理一些三维几何问题。我需要找到一个三角形和另一个三角形的交集。

我可以使用哪个算法呢？

- Sakthikannan

---

请参见此处的三角形和三角形交集计算方法：http://www.realtimerendering.com/intersections.html - bobobobo

Answer 1

许多人显然依赖于一个实现方法（源代码链接），该方法在以下论文（PDF 链接）中于2006年描述：

Tropp, Oren, Ayellet Tal, and Ilan Shimshoni. "A fast triangle to triangle intersection test for collision detection." Computer Animation and Virtual Worlds 17.5 (2006): 527-535.

但是，该代码存在问题（除了采用老旧的编程风格，使用非传统的符号以及失去基础几何解释之外）：“行列式事务”并不一定会使您的数学更加健壮，如果错误地处理。

我建议使用 Moeller 的方法（PDF 链接）或查看 Delliver 的论文（PDF 链接），并在 CGAL 库（链接，“Triangle_3_Triangle_3_do_intersect.h”）中实现。

示例：上面实现的交点程序告诉我们由以下点定义的三角形（p0，p1，p2）和（q0，q1，q2）是否相交：

p0 = (-21, -72, 63)
p1 = (-78, 99, 40)
p2 = (-19, -78, -83)
q0 = (96, 77, -51)
q1 = (-95, -1, -16)
q2 = (9, 5, -21)

这两个三角形不相交。以下是三角形的图片：

接下来是代码片段（附加在原代码后面）：

#include <iostream>

inline void setPoint(double p[3], const double x, const double y, const double z)
{
    p[0] = x; p[1] = y; p[2] = z;
}

inline void computeEdges(double v0[3], double v1[3], const double p0[3], const double p1[3], const double p2[3])
{
    v0[0] = p1[0]-p0[0];
    v0[1] = p1[1]-p0[1];
    v0[2] = p1[2]-p0[2];
    v1[0] = p2[0]-p0[0];
    v1[1] = p2[1]-p0[1];
    v1[2] = p2[2]-p0[2];
}

void main()
{
    unsigned int numErrors(0), count(0);
    double p0[3], p1[3], p2[3], q0[3], q1[3], q2[3];
    double v0[3], v1[3], w0[3], w1[3];
    bool res, answer;
    int ret;

    std::cout << "Testing the correctness of tr_tri_intersect3D" << std::endl;

    {
        // Non excluding triangles in generic positions, big determinants, intersecting
        ++count;
        setPoint(p0, -21, -72, 63);
        setPoint(p1, -78, 99, 40);
        setPoint(p2, -19, -78, -83);
        setPoint(q0, 96, 77, -51);
        setPoint(q1, -95, -1, -16);
        setPoint(q2, 9, 5, -21);
        answer = true;

        computeEdges(v0, v1, p0, p1, p2);
        computeEdges(w0, w1, q0, q1, q2);
        int ret = tr_tri_intersect3D(p0, v0, v1, q0, w0, w1);
        bool res = ( ret != 0 );

        if( res != answer )
        {
            std::cout << "# wrong answer on test " << count << "!\n";
            ++numErrors;
        }
    }

}

关于算术运算的数量，最后需要注意的是：由于该方法输入了预先计算的边缘向量，因此应在论文的表格I中添加12个±运算。

最后但同样重要的是：请自行验证我所写的内容，并在您认为我误解了某些内容时给予我反馈！

- DoubleChain

---

刚刚发现了这段代码，对于想要快速找到已实现的Delliver方法解决方案的人可能很有用：https://raw.githubusercontent.com/erich666/jgt-code/master/Volume_08/Number_1/Guigue2003/tri_tri_intersect.c - Botond

Answer 2

本文介绍了一种实现方法：

http://knight.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf

请注意，根据您想要知道交点/交段还是只想告诉您是否发生了交错，有不同的技术。本文将为您提供代表交点的线段。

- MichaelM

Answer 3

Devillers等人撰写了一篇名为“更快的三角形-三角形相交测试”的论文，与MichaelM的回答中的Moeller论文相比，他们的观点是，你应该通过对选择的4个点进行行列式计算来获取组合信息（论文中描述了如何做到这一点）。这避免了计算可能存在问题的中间值，并且实际上可能并不更快...

您可以将这些行列式视为确定由4个点形成的四面体是右手还是左手，或者退化（即平面）。该值还确定了任意一个点是否在其他三个点形成的平面的一侧，以及由其中两个点形成的（有向）线段是否在另外两个点形成的线段的一侧。

简而言之，进行行列式操作可以使您的数学更加健壮，如果您注意，通常可以将最初未执行行列式操作的算法转换为执行该操作的算法。或者，您可以直接阅读这篇论文。

- comingstorm