CGAL users discussion list

[Julian Panetta <>]

Dear Sebastien and Laurent,

The main point of the example was to show that querying the AABB for a triangle by its centroid is finding the incorrect triangle. The distance printout shows that the error made is many orders of magnitude greater than machine precision (the example mesh bounding box is 26.6x19.2x16.1). You can see a full printout of the large errors here:

http://julianpanetta.com/bad.txt

Notice that even when the AABB tree gets the correct face, sometimes the distance is not close to zero:

11208

distance  = 0.0363889

face idx  = 11208

(the first number means the centroid of 11208 was queried, and face idx = 11208 means the AABB returned face 11208).

It's difficult to believe this is a simple floating point error; the example mesh doesn't have small or degenerate triangles, and the errors are visually obvious:

http://julianpanetta.com/incorrect_result.png

(a query and the incorrectly retrieved triangle are outlined).

Furthermore, the results are compiler dependent: when gcc 4.8.2 is used to compile CGAL and the example, both kernels Cartesian<double> and Exact_predicates_inexact_constructions_kernel, give the incorrect AABB results. When gcc 4.9.2 is used to compile CGAL and the example, both kernels give the correct AABB results. It also works to compile CGAL with gcc 4.8.2 but the example with gcc 4.9.2.

-Julian

On Wed, Nov 12, 2014 at 11:03 AM, Laurent Rineau (CGAL/GeometryFactory) <> wrote:

Le Wednesday 12 November 2014 10:38:03 Qingnan Zhou a écrit :
> 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
> <https://www.dropbox.com/s/j1xj8nfy68xpdqc/suzanne_tri.obj?dl=0>"

The computation of a distance is a construction. With the kernel
CGAL::Exact_predicates_inexact_constructions_kernel, then the constructions
are not exact, and thus the computation of a distance is not exact either.
That is expected.

Please explain what sort of problem you want to solve, that is impacted by
this "bug", and we might be able to propose other solutions.

--
Laurent Rineau, PhD
R&D Engineer at GeometryFactory           http://www.geometryfactory.com/
Release Manager of the CGAL Project       http://www.cgal.org/