fast robust boolean operations

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

fast robust boolean operations

doug.moen
I just learned about a promising replacement for CGAL booleans in OpenSCAD.

It is the relatively new mesh_boolean module in libigl by Qingnan "James" Zhou.

Here's the paper:

Here are the claims:
* Accepts a more liberal set of meshes than CGAL and Carve.
* 6.8 times faster than CGAL (on an 8 core processor)
* (Carve is 7.72 times faster than CGAL in the same tests.)
* Uses CGAL exact arithmetic.
* Multithreaded, and can union a variable length list of shapes together in parallel.
* More robust than Carve or CGAL. The output is guaranteed to be "without self-intersections, without open boundaries, and with piecewise-constant winding number", whereas both Carve and CGAL output fails to be valid in a significant fraction of cases.
* This guarantee of output correctness applies to the exact arithmetic version of the output. However, they provide a conversion to floating point that succeeds 99.5% of the time.

My friend also claims that these operations are "CGAL compatible".

My understanding is that this could replace the multi-threaded CGAL interface that we have under development, and that it would be more robust, accepting more meshes as inputs, and succeeding more often in producing valid STL files as outputs.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: fast robust boolean operations

kintel
Administrator
> On Feb 12, 2018, at 8:53 PM, doug moen <[hidden email]> wrote:
>
> It is the relatively new mesh_boolean module in libigl by Qingnan "James" Zhou.
>
Is this the same algorithm that he implemented in libigl? https://github.com/libigl/libigl

I chatted with him on Skype a while back, one of his libigl co-authors is a prof at U of Toronto; I presented OpenSCAD to their research group a while back..

I’ve been wanting to test that out, but haven’t managed to free up enough time to clean up our interfacing with CGAL to something that makes it clean to test out various libraries..

 -Marius


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org