CGAL users discussion list

[Thiago Milanetto Schlittler <>]

Hello!

   I'm having a really weird bug when trying to intersect two triangles inside a 3D space while using the `CGAL::Exact_predicates_inexact_constructions_kernel` kernel. Essentially, I have two triangles that should not intersect. The function `CGAL::do_intersect` returns always `false` when testing them, but the function `CGAL::intersection` builds an intersection, depending on the order of the vertices of the triangles. 

   The bug disappears when I use the `CGAL::Exact_predicates_exact_constructions_kernel` kernel, but I can't afford to use it in the real case scenario.

   Below is a minimal code with the bug. Triangles B and C are equal (up to a permutation of the vertices), and should return the same intersection with Triangle 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;

    }

Here's the output ...

       - 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) …

Does anyone have any idea about what could be happening? I’m using CGAL 4.6.1, on OS X 10.10.5 (Yosemite).

Thanks in advance,

Thiago Milanetto Schlittler