search

libigl / libigl

Simple MPL-2.0-licensed C++ geometry processing library.
http://libigl.github.io/libigl/
GNU General Public License v3.0
4.6k stars 1.14k forks source link

Performance for boolean operations #495

Open waterrhett opened 7 years ago

waterrhett commented 7 years ago

Hi,

I have a question about the optimization for the boolean operations. Specifically, is there any space-partitioning data structure used in accelerating the operations? As I am trying to apply the union operations to these following two meshes shapes_to_merge.tar.gz (.off files, one with ~16k faces and another with ~500 faces), the computation typically takes ~20 seconds. Is there any option for using such accelerations, if they exist?

Thank you!

rileyjf1 commented 7 years ago

I am also interested in this, theoretically it should be possible using AABBs but going from theory to implementation here this is beyond my abilities :/

alecjacobson commented 7 years ago

We're already using AABBs to accelerate the triangle-triangle intersections, but there's probably still lots of performance gains to be made.

rileyjf1 commented 7 years ago

Are the AABBs applied only to each triangle in the mesh or is there some sort of AABB hierarchy going on?

alecjacobson commented 7 years ago

It's using:

http://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html