3D 三角形 (CGAL) 之间错误的不精确交点

Question

我在使用 CGAL::Exact_predicates_inexact_constructions_kernel 内核时尝试在 3D space 中相交两个三角形时遇到了一个非常奇怪的错误。本质上，我有两个不应相交的三角形。函数 CGAL::do_intersect return 在测试它们时总是 false，但是函数 CGAL::intersection 建立一个交集，这取决于三角形顶点的顺序。

当我使用CGAL::Exact_predicates_exact_constructions_kernel内核时，该错误消失，但在实际情况下我无法使用它。

下面是带有错误的最小代码。三角形 B 和 C 相等（取决于顶点的排列），并且应该 return 与三角形 A 有相同的交集。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Intersections.h>

#include <iostream>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;

typedef Kernel::Point_3     Point_3;
typedef Kernel::Triangle_3  Triangle_3;


int main(int argc, char *argv[])
{
    std::vector<Point_3> APoints(3);
    std::vector<Point_3> BPoints(3);

    APoints[0] = Point_3(2, 2, 0.9423616295572568);
    APoints[1] = Point_3(0.9685134704003172, 2, 0.9678422992674797);
    APoints[2] = Point_3(2, 1.124710354419025, 1.068692504586136);

    BPoints[0] = Point_3(2.5, 2.5, 1.442361629557257);
    BPoints[1] = Point_3(1.588259113885977, 2.5, 0.5);
    BPoints[2] = Point_3(2.5, 1.624710354419025, 1.568692504586136);

    Triangle_3 TriangleA(APoints[0],APoints[1],APoints[2]);
    Triangle_3 TriangleB(BPoints[0],BPoints[1],BPoints[2]);
    Triangle_3 TriangleC(BPoints[2],BPoints[1],BPoints[0]);

    std::cout.precision(16);
    std::cout   << "   - Tried to intersect: " << std::endl;
    std::cout   << "   - Triangle (A) " << " : "
                << "(" << TriangleA.vertex(0) << ") "
                << "(" << TriangleA.vertex(1) << ") "
                << "(" << TriangleA.vertex(2) << ") " << std::endl;
    std::cout   << "   - Triangle (B) " << " : "
                << "(" << TriangleB.vertex(0) << ") "
                << "(" << TriangleB.vertex(1) << ") "
                << "(" << TriangleB.vertex(2) << ") " << std::endl;
    std::cout   << "   - Triangle (C) " << " : "
                << "(" << TriangleC.vertex(0) << ") "
                << "(" << TriangleC.vertex(1) << ") "
                << "(" << TriangleC.vertex(2) << ") " << std::endl;

    if( TriangleB.vertex(0)==TriangleC.vertex(2) && 
        TriangleB.vertex(1)==TriangleC.vertex(1) && 
        TriangleB.vertex(2)==TriangleC.vertex(0))
    {
        std::cout << "   - Triangles (B) and (C) have the same vertices " << std::endl;
    }

    bool bIntersectAB = CGAL::do_intersect(TriangleA,TriangleB);
    bool bIntersectAC = CGAL::do_intersect(TriangleA,TriangleC);

    bool bIntersectInexactAB = CGAL::intersection(TriangleA,TriangleB);
    bool bIntersectInexactAC = CGAL::intersection(TriangleA,TriangleC);

    if(bIntersectAB)
    {
        std::cout << " --> A and B are intersecting (exact) ..." << std::endl;
    }

    if(bIntersectAC)
    {
        std::cout << " --> A and C are intersecting (exact) ..." << std::endl;
    }

    if(bIntersectInexactAB)
    {
        std::cout << " --> A and B are intersecting (inexact) ..." << std::endl;
    }

    if(bIntersectInexactAC)
    {
        std::cout << " --> A and C are intersecting (inexact) ..." << std::endl;
    }

    return 0;
}

这是输出...

   - Tried to intersect: 
   - Triangle (A)  : (2 2 0.9423616295572568) (0.9685134704003172 2 0.9678422992674797) (2 1.124710354419025 1.068692504586136) 
   - Triangle (B)  : (2.5 2.5 1.442361629557257) (1.588259113885977 2.5 0.5) (2.5 1.624710354419025 1.568692504586136) 
   - Triangle (C)  : (2.5 1.624710354419025 1.568692504586136) (1.588259113885977 2.5 0.5) (2.5 2.5 1.442361629557257) 
   - Triangles (B) and (C) have the same vertices 
 --> A and C are intersecting (inexact) ...

... 和一个带有两个三角形（A：顶点 1、2、3；B：顶点 11、12、13）和 "intersection"（线段 21 - 22）的图形，使用该程序的类似版本。

有什么问题吗？我在 OS X 10.10.5 (Yosemite) 上使用 CGAL 4.6.1。提前致谢！

Answer 1

我也把这个问题发到了CGAL的邮件列表，开发人员回答说这个行为不是bug，虽然这是不幸的。 intersection 是一个通用函数，对所有 CGAL 内核都以相同的方式实现，并且它使用的一个步骤并不总是被不精确的内核正确处理 - 因此出现交集错误。根据 CGAL GitHub 页面上的 this 线程，

In order to keep using a kernel with inexact constructions, I usually advice to first call the do_intersect predicate and then call the intersection function using EPECK on primitives converted on the fly using CGAL::Cartesian_converter. You'll have to convert the output using another CGAL::Cartesian_converter. The call to do_intersect is not mandatory, it usually depends on your setting.

3D 三角形 (CGAL) 之间错误的不精确交点

Wrong inexact intersection between 3D triangles (CGAL)

c++

cgal