Proper way to construct AABB_trees

[Willie Maddox]

Hello,

Here is a summary of my problem.

My vertices, faces and edges are defined as:

vertices: an Nx3 numpy array of floats where N is the number of vertices.

faces: an Mx2 numpy array of ints where M is the number of faces.

edges: an Lx2 numpy array of ints where L is the number of edges.

Here are the routines I use to construct AABB trees in my code:

vertices_cgal = [Point_3(x, y, z) for x, y, z in vertices]

triangle_soup = [Triangle_3(vertices_cgal[f[0]], vertices_cgal[f[1]], vertices_cgal[f[2]]) for f in faces]

segment_soup = [Segment_3(vertices_cgal[e[0]], vertices_cgal[e[1]]) for e in edges]

triangle_tree = AABB_tree_Triangle_3_soup(triangle_soup)

segment_tree = AABB_tree_Segment_3_soup(segment_soup)

So using, for example, a 500x500 regularly spaced grid yields,

N = 250000

M = 498002

L = 748001

and the time (in seconds) to calculate each routine,

vertices_cgal = 2.57

triangle_soup = 7.79

segment_soup = 12.72

triangle_tree = 0.10

segment_tree = 0.14

As you can see, the bottleneck isn't in the building of the AABB trees themselves, but rather the building of the soups.

Is this the proper way to build AABB_trees?

Do the cgal bindings come with any fast algorithms for building segment soups quickly?  I haven't been able to find any.

Thanks,

Will

[Sebastien Loriot (GeometryFactory)]

I think one thing that can be done and that would be really faster
is to add a constructor to AABB_tree_Triangle_3_soup and
AABB_tree_Segment_3_soup taking ranges of double values
where a triangle is defined with 9 doubles and a segment
with 6. That way you avoid intermediate constructions.
This would need adding a new template parameter to the tree
wrapper indicating the number of double defining the primitive type.

But with the current API, I don't think there is something faster.

Sebastien.

> --
> You received this message because you are subscribed to the Google
> Groups "CGAL Bindings discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to cgal-bindings-di...@googlegroups.com
> <mailto:cgal-bindings-di...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.

[Willie Maddox]

Sebastien,

Yes, that will definitely be the fastest way.  I think I can make the changes

myself and am excited to contribute.  I've done some work with cython but

never with SWIG so it should be fun.  I see the AABB_tree.h contains the wrapper,

but it is not obvious to me which other files will need modification.  

Suggestions,

-Will

[Sebastien Loriot (GeometryFactory)]

You'll need some typemaps in the .i file to make the range of double
matching a native type.
Note that the typemap part is tricky. I've done something similar
for java in Java/typemaps.i

For example,
SWIG_CGAL_array_of_array_of_double_to_vector_of_vector_of_point_2_typemap_in
converts a c++ function taking a boost::shared_ptr<std::vector<
std::vector<EPIC_Kernel::Point_2> > > as input parameter into a
double[][] in java.

Sebastien.

[Willie Maddox]

Sebastien,

Tricky is putting it lightly unless you know python, c++, and swig rather well.

I thought I could knock this out in a few hours, but I am still trying to understand 

the flow of the code.  My python is strong, but apparently my C++ and SWIG

knowledge is insufficient.  I'll post a feature request to GitHub, maybe someone

can beat me to it.

I do have two questions. What development environment do you use for this project?

All the different flavors of code makes debugging difficult.

Thanks,

-Will

[Sebastien Loriot (GeometryFactory)]

On 11/03/2015 11:26 PM, Willie Maddox wrote:
> Sebastien,
>
> Tricky is putting it lightly unless you know python, c++, and swig
> rather well.
> I thought I could knock this out in a few hours, but I am still trying
> to understand
> the flow of the code. My python is strong, but apparently my C++ and SWIG
> knowledge is insufficient. I'll post a feature request to GitHub, maybe
> someone
> can beat me to it.
>

I know it's a pain, it took me a lot of time to learn how to do things
correctly.

> I do have two questions. What development environment do you use for
> this project?
> All the different flavors of code makes debugging difficult.
>

Old school: a terminal and an text editor

Sebastien.

> Thanks,

[Willie Maddox]

Sebastien,

You'll need some typemaps in the .i file to make the range of double
matching a native type.
Note that the typemap part is tricky. I've done something similar
for java in Java/typemaps.i

Which .i file? The CGAL_AABB_tree.i file?

I'd rather not clutter up CGAL_AABB_tree.i with a bunch of python specific %typemap()

entries unless you are ok with that. Would it be better to create

a new typemaps.i file in the Python directory?

And by native type, you mean CGAL Segment_3 and Triangle_3 primitives, yes?

For example,
SWIG_CGAL_array_of_array_of_double_to_vector_of_vector_of_point_2_typemap_in
converts a c++ function taking a  boost::shared_ptr<std::vector<
std::vector<EPIC_Kernel::Point_2> > > as input parameter into a
double[][] in java.

So, for AABB_tree_Triangle_3_soup, I'm looking to create a typemap that 

converts a c++ function taking a python list of Nx9 doubles as an input parameter

into a boost::shared_ptr<std::vector< std::vector<EPIC_Kernel::Triangle_3> > >

Thanks,

Will

[Sebastien Loriot (GeometryFactory)]

On 11/05/2015 12:47 AM, Willie Maddox wrote:
> Sebastien,
>
> You'll need some typemaps in the .i file to make the range of double
> matching a native type.
> Note that the typemap part is tricky. I've done something similar
> for java in Java/typemaps.i
>
>
> Which .i file? The CGAL_AABB_tree.i file?
> I'd rather not clutter up CGAL_AABB_tree.i with a bunch of python
> specific %typemap()
> entries unless you are ok with that. Would it be better to create
> a new typemaps.i file in the Python directory?

As soon as you wrote the typemap in the Python directory, you need to
use it inside CGAL_AABB_tree.i otherwise it cannot be taken into account.

> And by native type, you mean CGAL Segment_3 and Triangle_3 primitives, yes?
>

Yes

> For example,
> SWIG_CGAL_array_of_array_of_double_to_vector_of_vector_of_point_2_typemap_in
>
> converts a c++ function taking a boost::shared_ptr<std::vector<
> std::vector<EPIC_Kernel::Point_2> > > as input parameter into a
> double[][] in java.
>
>
> So, for AABB_tree_Triangle_3_soup, I'm looking to create a typemap that
> converts a c++ function taking a python list of Nx9 doubles as an input
> parameter
> into a boost::shared_ptr<std::vector<
> std::vector<EPIC_Kernel::Triangle_3> > >
>

Exactly.

Sebastien.

> Thanks,

[Willie Maddox]

Ok I am starting to get somewhere with this.

I've created a new typemap for converting an Nx9 list of doubles to a list of N Triangle_3 objects and placed it in SWIG_CGAL/Python/typemaps.i

As soon as you wrote the typemap in the Python directory, you need to
use it inside CGAL_AABB_tree.i otherwise it cannot be taken into account.

This part has me a bit confused.

I noticed that of all the typemaps defined in Java/typemaps.i, the only one that gets used is in the CGAL_Box_intersection_d.i.

#ifdef SWIGJAVA

%include "SWIG_CGAL/Java/typemaps.i"

SWIG_CGAL_array_of_int_to_vector_of_pair_of_int_typemap_in

#endif

Which lines in the CGAL_Box_intersection_d.i actually "use" this typemap?

Also, when you say,

This would need adding a new template parameter to the tree 

wrapper indicating the number of double defining the primitive type. 

Do mean creating something similar to the struct Primitive_iterator_helper from the AABB_tree.h file?

Thanks,

-Will

[Sebastien Loriot (GeometryFactory)]

On 11/06/2015 01:22 AM, Willie Maddox wrote:
> Ok I am starting to get somewhere with this.
>
> I've created a new typemap for converting an Nx9 list of doubles to a
> list of N Triangle_3 objects and placed it in SWIG_CGAL/Python/typemaps.i
>
> As soon as you wrote the typemap in the Python directory, you need to
> use it inside CGAL_AABB_tree.i otherwise it cannot be taken into
> account.
>
>
> This part has me a bit confused.
> I noticed that of all the typemaps defined in Java/typemaps.i, the only
> one that gets used is in the CGAL_Box_intersection_d.i.
>
> #ifdef SWIGJAVA
> %include "SWIG_CGAL/Java/typemaps.i"
> SWIG_CGAL_array_of_int_to_vector_of_pair_of_int_typemap_in
> #endif
>
>
> Which lines in the CGAL_Box_intersection_d.i actually "use" this typemap?
>

I don't think I use it in the public repo but I do for other projects.
You simply need to call the macro before %template'ing the class
containing the (member) function with the share_ptr parameter.

(%template is wrapped in SWIG_CGAL_declare_identifier_of_template_class
here)

> Also, when you say,
>
> This would need adding a new template parameter to the tree
> wrapper indicating the number of double defining the primitive type.
>
> Do mean creating something similar to the struct
> Primitive_iterator_helper from the AABB_tree.h file?
>

Oh! Actually you don't.

These two line are the instantiation of the template wrapper.

SWIG_CGAL_declare_identifier_of_template_class(AABB_tree_Segment_3_soup,AABB_tree_wrapper<CGAL_SSP_Tree,Segment_3,int
>)
SWIG_CGAL_declare_identifier_of_template_class(AABB_tree_Triangle_3_soup,AABB_tree_wrapper<CGAL_TSP_Tree,Triangle_3,int
>)

Before each of these line you need to call the approxiate macro
and you should be done (because Segment_3/Triangle_3 is a
template parameter). There might need a trick to make
other instantiations (for Polyhedron) to ignore the constructor.

Sebastien.




> Thanks,
>
> -Will

[Willie Maddox]

Sebastien,

 

You simply need to call the macro before %template'ing the class 
containing the (member) function with the share_ptr parameter. 

(%template is wrapped in SWIG_CGAL_declare_identifier_of_template_class here) 

The SWIG documentation indicates that a %template is used to modify the argument types (i.e. what goes in the <> of the template in AABB_tree.h.) So, in the AABB_tree.h we have,

template <class Tree,class Primitive_object,class Primitive_id>

But the constructor takes an argument of type Primitive_range, which is indirectly defined by,

typedef typename Primitive_iterator_helper<Primitive_object>::input Primitive_range;

So, how do we change the constructor argument type "Primitive_range" without changing the template types <CGAL_TSP_Tree,Triangle_3,int >? Or am I totally missing the point here.

Thanks again,

-Will

[Sebastien Loriot (GeometryFactory)]

Did you push your changes somewhere?

About the compilation, if the .i is not modified, simply "touch
CGAL_AABB_tree.i" and run "make".

Sebastien.

[Willie Maddox]

Not yet. Still trying to get it to work.

[Sebastien Loriot (GeometryFactory)]

On 11/09/2015 04:03 PM, Willie Maddox wrote:
> Not yet. Still trying to get it to work.
>

I can have a look if you push the current state.
You'll be able to rebase if you want a clean history.

Sebastien.

[Willie Maddox]

I pushed the changes to my fork.

Since this project now lives on github, would you rather collaborations take place there rather than on the google groups?

-Willie

[Willie Maddox]

Sebastien,

I am still having troubles with this. Were you able to look at my fork?

-Willie

[Sebastien Loriot (GeometryFactory)]

Hi,

I'm rather busy these days. Will have a look next week.

[Sebastien Loriot (GeometryFactory)]

I have something that seems to work in:
https://github.com/CGAL/cgal-swig-bindings/tree/AABB_tree-insert_from_array

with

import CGAL.CGAL_AABB_tree
t2=[[0,0,0,1,0,0,1,1,0],[0,0,1,1,0,1,1,1,1]]
tree=CGAL.CGAL_AABB_tree.AABB_tree_Triangle_3_soup()
tree.insert_from_array(t2)
tree.size()

I let you do the testing, cleaning and check how faster it is.

Sebastien.

[Willie Maddox]

I struggled trying to get this to work. Seeing your changes cleared a lot of things up for me.  Just out of curiosity is there anything preventing us from overloading the constructor versus calling the insert_from_array function? I thought about playing around with typemap typechecks, but this may not work since the input types are too similar.

I did a little organizing and cleanup and it seems to be working pretty good. I also added a new python script test_aabb2.py to the examples for testing.  I'm getting a little over 1 order of magnitude speedup, which is GREAT!

I submitted a pull request.

Thanks for all the help.

-Willie