CGAL users discussion list

[Qingnan Zhou <>]

Dear all,

There seems to be a bug that causes CGAL::AABBTree to produce wrong results.  The following code would illustrate the problem:  

It basically compute the center of each face and query the distance between the centroid and the mesh.  Ideally, the query should always return 0 as the distance and the source face index, otherwise the code will print out the face that causes the failure.

typedef CGAL::Cartesian<Real> K;

typedef K::Point_3 CGALPoint;

typedef K::Triangle_3 CGALTriangle;

typedef CGAL::AABB_tree<AABB_triangle_traits> AABBTree;

typedef AABBTree::Point_and_primitive_id Point_and_primitive_id;

...

    AABBTree *coarseTrianglesTree =

        new AABBTree(triangles.begin(), triangles.end());

    coarseTrianglesTree->accelerate_distance_queries();

    size_t count = 0;

    for (auto itr : triangles) {

        CGALPoint c = CGAL::ORIGIN + ((

        (itr[0] - CGAL::ORIGIN) +

        (itr[1] - CGAL::ORIGIN) +

        (itr[2] - CGAL::ORIGIN)) / 3.0);

        Point_and_primitive_id pp = coarseTrianglesTree->closest_point_and_primitive(c);

        size_t face_index = pp.second - triangles.begin();

        double distance = coarseTrianglesTree->squared_distance(c);

        if (distance > 1e-3) {

            std::cout << count << std::endl;

            std::cout << "distance  = " << distance << std::endl;

            std::cout << "face idx  = " << face_index << std::endl;

        }

        count ++;

    }

When running this test on meshes such as "suzanne.obj", the query fails on quite a few faces (the query finds the incorrect face index and gets a distance ~= 10^-3).

We are able to reproduce the error with CGAL 4.4 and CGAL 4.5 on 

Redhat Enterprise Linux server with the following setting:

gcc 4.8.2, gmp 6.0.0 (also tried 4.3.1), mpfr 3.1.2, boost 1.53

CentOS 6.3 with the following setting:

gcc 4.8.2, gmp 6.0.0a, mpfr 3.1.2, boost 1.55.0

Strangely it works on the version compiled by macports.  We have tested CGAL 4.3 and 4.4 on mac.

best,

James