Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Bugs in AABBTree

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Bugs in AABBTree


Chronological Thread 
  • From: Qingnan Zhou <>
  • To:
  • Cc: Julian Panetta <>
  • Subject: Re: [cgal-discuss] Bugs in AABBTree
  • Date: Wed, 12 Nov 2014 10:38:03 -0500

Hi Sebastien,

Changing the kernel to CGAL::Exact_predicates_inexact_constructions_kernel does not help in this case.  The closest point and primitive returned are still incorrect for many faces.  However, switching to gcc-4.9.2 on linux seems to make the problem go away.  Maybe it is related to how CGAL is built?

Is anyone able to reproduce this problem?  I.e. compute the distance between face center to the mesh for every face and check the distance is 0.  Try it on this mesh: "suzanne.obj"

best,
James

On Wed, Nov 12, 2014 at 2:36 AM, Sebastien Loriot (GeometryFactory) <> wrote:
This is most probably a floating point computation issue.

Also have a look here:
http://www.cgal.org/FAQ.html#inexact_NT

Sebastien.



On 11/10/2014 10:04 PM, Qingnan Zhou wrote:
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
<https://www.dropbox.com/s/j1xj8nfy68xpdqc/suzanne_tri.obj?dl=0>", 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


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss






Archive powered by MHonArc 2.6.18.

Top of Page