CGAL users discussion list

[Asher Kamiraze <>]

Hi all,

I finally managed to have a minimal test case which reproduces the problem. It is attached as a new main cpp file. As you will see, the problem arises when I build the AABB tree from triangles in a method, then try to query it in another method. If I build the AABB tree and query it in the same method, the problem does not appear, although the code is strictly the same.

Sorry for the ugly code, but please consider it as a one shot test case to reproduce the problem. Just pass on the commad line the full path to triangles.txt and queries.txt

Hope you could help.

Regards,

Asher

2013/12/11 Asher Kamiraze <>

Sorry,

I reduced the files size to not exceed the ML limit.

Regards,

Asher

2013/12/11 Asher Kamiraze <>

Philipp,

Here is a minimal sample which does NOT reproduces the problem. This is nearly a copy / paste of some parts of my original code. The only difference are:

• in my code, AABBTree tree and std::map<...,...> facetsToQuery are class members
• in my code, std::map< Face_handle, std::vector<Simple_Segment_3> > facetsToQuery; is defined as std::map< Face_handle, std::vector<Simple_Point_3> > facetsToPoints; and the segment query in the attached sample is build from Simple_Point_3

Attached archive contains triangles and queries from a real case which causes a problem in my application.

So, if you have any hint on why the attached code works and my not, I am really interested :)

Regards,

Asher

2013/12/10 Philipp Moeller <>

Asher Kamiraze <> writes:

> Thank you Philipp for your answer. I agree with your slicing idea, but it
> appears that replacing my Custom_Triangle_3 with the custom primitve as
> described in
> http://doc.cgal.org/latest/AABB_tree/AABB_tree_2AABB_custom_example_8cpp-example.htmldrops
> the same problem. Note that I use VS2010 64 + CGAL 4.2.

By "the same problem" you mean that extra data in My_triangle is not
properly preserved? That sounds very much like it shouldn't happen. I
can have a look at it this week to see what is going on.

>
> I am working on a minimal sample which reproduces the problem, but have to
> write it from scratch with IO from my applications. Once done, I will post
> it on the list with test data.
>
> You also suggest me to check how the object is constructed. Should I track
> in debug its insertion in the AABB tree to see what exactly happen?
>
> Best regards,
>
> Asher K
>
>
>
>
>>
>> 2013/12/9 Philipp Moeller <>
>>
>>> Asher Kamiraze <> writes:
>>>
>>> > Hi all,
>>> >
>>> > I am currently facing a problem with AABB Tree. I have defined my own
>>> > triangle class (because I need to store an integer for each triangle) :
>>> >
>>> > typedef CGAL::Simple_cartesian<double> Simple_Cartesian;
>>> > typedef Simple_Cartesian::Triangle_3   Simple_Triangle_3;
>>> >
>>> > class CustomTriangle_3 : public Simple_Triangle_3
>>> > {
>>> > public:
>>> >     Simple_Cartesian::Vector_3 _normal;
>>> >     Arr::Face_handle _handle; // is an int
>>> >
>>> >     CustomTriangle_3(Simple_Point_3& a, Simple_Point_3& b,
>>> Simple_Point_3&
>>> > c) : Simple_Triangle_3(a,b,c) { _handle = -1; _normal =
>>> > CGAL::unit_normal(a,b,c); }
>>> >     CustomTriangle_3() : Simple_Triangle_3() { _handle = -1; }
>>> > };
>>> >
>>> > I then build a std::list of CustomTriangle_3 and insert them in an AABB
>>> > tree:
>>> >
>>> > typedef std::list<CustomTriangle_3>::iterator                  Iterator;
>>> > typedef CGAL::AABB_triangle_primitive<Simple_Cartesian,Iterator>
>>> > TrianglePrimitive;
>>> > typedef CGAL::AABB_traits<Simple_Cartesian, TrianglePrimitive>
>>> > AABB_triangle_traits;
>>> > typedef CGAL::AABB_tree<AABB_triangle_traits>                    Tree;
>>> > typedef Tree::Object_and_primitive_id
>>> > Object_and_primitive_id;
>>> > typedef Tree::Point_and_primitive_id
>>> > Point_and_primitive_id;
>>> > typedef Tree::Primitive_id
>>> > Primitive_id;
>>> >
>>> > std::list<CustomTriangle_3> triangles;
>>> > // some code to build CustomTriangle_3
>>> > _tree.insert(triangles.begin(),triangles.end());
>>> > _tree.build();
>>> > _tree.accelerate_distance_queries();
>>> >
>>> > _tree is a class member of type Tree.
>>> >
>>> > For each created triangle, I set its _handle member to a valid value (a
>>> > positive integer).
>>> >
>>> > Later, in an other method, I query the _tree:
>>> >
>>> > if ( _tree.do_intersect(query) )
>>> > {
>>> >                 std::vector<Primitive_id> intersectedPrimitives;
>>> >                 _tree.all_intersected_primitives(query,
>>> > std::back_inserter(intersectedPrimitives));
>>> >
>>> >                 //for(std::vector<Primitive_id>::iterator
>>> > it=intersectedPrimitives.begin();it!=intersectedPrimitives.end();++it)
>>> >                 for(unsigned int
>>> gh=0;gh<intersectedPrimitives.size();++gh)
>>> >
>>> > _facetsToPoints[intersectedPrimitives[gh]->_handle].push_back(
>>> > _points[i][j] );
>>> >                     //_facetsToPoints[(*it)->_handle].push_back(
>>> > _points[i][j] );
>>> > }
>>> >
>>> > This is where the problem occurs: when I try to access
>>> > intersectedPrimitives[gh]->_handle, I get an inconsistent handle. If I
>>> run
>>> > the program in debug mode, I got an assertion:
>>> >
>>> > _expression_: list iterator not dereferencable
>>> >
>>> > At the first all_intersected_primitves query, intersectedPrimitives
>>> > contains 3 elements, all inconsistent (bad _handle and normal). I am
>>> > wondering what I am doing wrong, and hope you could help tracking the
>>> > problem.
>>>
>>> This sounds a lot like slicing is happening somewhere (e.g. an object of
>>> type A is constructed from an object of type B which inherits of A and
>>> all the extra information of B is lost). Could you check how the object
>>> is constructed and maybe attach a complete, minimal test-case to
>>> reproduce the issue?
>>>
>>
>>

--
Philipp Moeller
GeometryFactory

#include <iostream>
#include <fstream>
#include <vector>

#include "AABBTreeTestTypes.hpp"

class AABBTreeTestCase
{
public:
    AABBTreeTestCase(const std::string& triangles, const std::string& queries) :
      _trianglesFile(triangles),
      _queriesFile(queries) {}

      void buildAABBTree()
      {
          // Parse triangles
          std::ifstream ifs_triangles(_trianglesFile);
          double x0, y0, z0, x1, y1, z1, x2, y2, z2;
          int nb, handle;
          std::vector< CustomTriangle_3 > triangles;
          ifs_triangles >> nb;
          for(int i=0;i<nb;++i)
          {
              ifs_triangles >> x0 >> y0 >> z0 >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> handle;
              CustomTriangle_3 tr( Simple_Point_3(x0,y0,z0),
                  Simple_Point_3(x1,y1,z1),
                  Simple_Point_3(x2,y2,z2) );
              tr._handle = handle;
              triangles.push_back(tr);
          }
          std::cout << triangles.size() << " triangles read" << std::endl;

          // Build AABB Tree from triangles
          _tree.insert(triangles.begin(), triangles.end());
          _tree.build();
          _tree.accelerate_distance_queries();
      }

      void buildFacetsToQueryMapping()
      {
          // Parse queries
          std::ifstream ifs_queries(_queriesFile);
          double x0, y0, z0, x1, y1, z1;
          int nb;
          ifs_queries >> nb;
          for(int i=0;i<nb;++i)
          {
              ifs_queries >> x0 >> y0 >> z0 >> x1 >> y1 >> z1;
              Simple_Point_3 p1(x0,y0,z0);
              Simple_Point_3 p2(x1,y1,z1);
              Simple_Segment_3 s(p1,p2);

              // Query AABB Tree and build a mapping between queries and Face_handle
              if(_tree.do_intersect(s))
              {
                  std::vector<Primitive_id> intersectedPrimitives;
                  _tree.all_intersected_primitives(s, std::back_inserter(intersectedPrimitives));

                  std::vector<Primitive_id>::const_iterator itb = intersectedPrimitives.begin(), ite = intersectedPrimitives.end();
                  for(;itb!=ite;++itb)
                      _facetsToQuery[(*itb)->_handle].push_back(s);
              }
          }
      }


      void buildAABBTreeAndFacetsToQueryMapping()
      {
          // Parse triangles
          std::ifstream ifs_triangles(_trianglesFile);
          double x0, y0, z0, x1, y1, z1, x2, y2, z2;
          int nb, handle;
          std::vector< CustomTriangle_3 > triangles;
          ifs_triangles >> nb;
          for(int i=0;i<nb;++i)
          {
              ifs_triangles >> x0 >> y0 >> z0 >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> handle;
              CustomTriangle_3 tr( Simple_Point_3(x0,y0,z0),
                  Simple_Point_3(x1,y1,z1),
                  Simple_Point_3(x2,y2,z2) );
              tr._handle = handle;
              triangles.push_back(tr);
          }
          std::cout << triangles.size() << " triangles read" << std::endl;

          // Build AABB Tree from triangles
          _tree.insert(triangles.begin(), triangles.end());
          _tree.build();
          _tree.accelerate_distance_queries();

          // Parse queries
          std::ifstream ifs_queries(_queriesFile);
          ifs_queries >> nb;
          for(int i=0;i<nb;++i)
          {
              ifs_queries >> x0 >> y0 >> z0 >> x1 >> y1 >> z1;
              Simple_Point_3 p1(x0,y0,z0);
              Simple_Point_3 p2(x1,y1,z1);
              Simple_Segment_3 s(p1,p2);

              // Query AABB Tree and build a mapping between queries and Face_handle
              if(_tree.do_intersect(s))
              {
                  std::vector<Primitive_id> intersectedPrimitives;
                  _tree.all_intersected_primitives(s, std::back_inserter(intersectedPrimitives));

                  std::vector<Primitive_id>::const_iterator itb = intersectedPrimitives.begin(), ite = intersectedPrimitives.end();
                  for(;itb!=ite;++itb)
                      _facetsToQuery[(*itb)->_handle].push_back(s);
              }
          }
      }

    void dumpFacetsToqueryMapping()
    {
        typedef std::map< Face_handle, std::vector<Simple_Segment_3> >::const_iterator map_it;
        map_it itb = _facetsToQuery.begin(), ite = _facetsToQuery.end();
        for(;itb!=ite;++itb)
            std::cout << "Facet " << itb->first << "\t-->\t" << itb->second.size() << std::endl;
    }

private:
    std::string _trianglesFile;
    std::string _queriesFile;

    Tree _tree;
    std::map< Face_handle, std::vector<Simple_Segment_3> > _facetsToQuery;
};

int main(int argc, char** argv)
{
    std::string trianglesFile(argv[1]);
    std::string queriesFile(argv[2]);
    AABBTreeTestCase test( trianglesFile, queriesFile );
    /* Crashes with the following to method calls */
    test.buildAABBTree();
    test.buildFacetsToQueryMapping();
    /* Does not crash if all is done in the same method */
    //test.buildAABBTreeAndFacetsToQueryMapping();
    test.dumpFacetsToqueryMapping();

	return 0;
}