3d空间中的三角形三角形相交 [英] Triangle Triangle Intersection in 3d-Space

问题描述

我正在处理一些3D几何.我需要找到三角形与另一个三角形的交点.

I'm working with some 3d geometry. I need to find the intersection of triangle with another triangle.

我可以使用哪种算法?

推荐答案

许多人显然依赖于实现(

Many people apparently rely on an implementation (link to source code) of the method described in 2006 in the following paper (link to PDF):

Tropp，Oren，Ayellet Tal和Ilan Shimshoni. 一个快速三角形 三角形相交测试以进行碰撞检测." 动画与虚拟世界17.5(2006):527-535.

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.

但是，该代码存在一个问题(除了采用旧的编程风格，使用非常规符号并失去基本的几何解释之外):行列式事物"不一定会使您的数学更加健壮，如果采用错误的方式

There is however a problem with that code (except for adopting an old programming style, using unconventional notations and loosing the underlying geometrical interpretation): "determinant thing" don't necessarily make your math more robust, if done the wrong way.

我建议使用Moeller的方法(链接到PDF )或查看Delliver的论文(链接到PDF)，该论文在CGAL中实现库(链接，"Triangle_3_Triangle_3_do_intersect.h").

I suggest to either use Moeller's method (link to PDF) or take a look at Delliver's paper (link to PDF), implemented in the CGAL library (link, "Triangle_3_Triangle_3_do_intersect.h").

一个例子:上面实现的交集例程告诉我们由以下几点定义的三角形(p0，p1，p2)和(q0，q1，q2)

An example: the intersection routine implemented above tells that the triangles (p0,p1,p2) and (q0,q1,q2) defined by the following points

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

不是相交.这是三角形的图片:

are not intersecting. Here is a picture of the triangles:

这是代码段(附加到原始代码):

And here is the code snippet (append to original code):

#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个+/-运算.

A final note on the number of arithmetic operations: since the method takes in input pre-computed edge vectors, 12 +/- operations should be added to Table I. of the paper.

最后但并非最不重要:请验证我自己写的内容，如果您认为我误会了一些内容，请给我反馈！

Last but not least: please verify what I am writing on your own and give me feedback if you think that I misunderstood something!

这篇关于3d空间中的三角形三角形相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！