CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

I compiled the program attached on your input converted to off using
meshlab using
g++-4.8 (Debian 4.8.3-2) 4.8.3
g++-4.7 (Debian 4.7.3-14) 4.7.3
g++-4.6 (Debian 4.6.4-7) 4.6.4
g++-4.4 (Debian 4.4.7-8) 4.4.7
with CGAL-4.5 and all was fine.

Could you give it a try and let us know?

Thanks,

Sebastien.

On 11/12/2014 06:04 PM, Julian Panetta wrote:
> 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)
> <
>  
> <mailto:>>
>  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/

#include <iostream>

#include <CGAL/Simple_cartesian.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <CGAL/AABB_face_graph_triangle_primitive.h>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/bind.hpp>

#include <CGAL/IO/Polyhedron_iostream.h>
#include <boost/foreach.hpp>
#include <fstream>

typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point;
typedef CGAL::Polyhedron_3<K> Polyhedron;
typedef CGAL::AABB_face_graph_triangle_primitive<Polyhedron> Primitive;
typedef CGAL::AABB_traits<K, Primitive> Traits;
typedef CGAL::AABB_tree<Traits> Tree;
typedef boost::graph_traits<Polyhedron>::face_descriptor face_descriptor;

int main(int, char** argv)
{
  Polyhedron P;
  std::ifstream input(argv[1]);
  
  input >> P;
  
  Tree tree(faces(P).first, faces(P).second, P);
  
  int count = 0;
  BOOST_FOREACH(face_descriptor f, faces(P))
  {
    Point c = CGAL::ORIGIN + (
        (f->halfedge()->vertex()->point() - CGAL::ORIGIN) +
        (f->halfedge()->next()->vertex()->point() - CGAL::ORIGIN) +
        (f->halfedge()->opposite()->vertex()->point() - CGAL::ORIGIN)) / 3.0;
    
    
    Tree::Point_and_primitive_id pp = tree.closest_point_and_primitive(c);
    double distance = CGAL::squared_distance(c,pp.first);

      if (distance > 1e-3) {
        std::cout << count << std::endl;
        std::cout << "distance  = " << distance << std::endl;
      }
        count ++;

    if (pp.second!=f){
      std::cout << "face  " << count << std::endl;
    }
  }
}