Gilbert Bernstein is currently a Ph.D. student at Stanford and had published some remarkable papers on computational geometry. I was first drawn to his work by his 2009 paper on Fast, Exact, Linear Booleans as my interest in 3D printing led me to create some tooling of my own. The various libraries I found online for performing Constructive Solid Geometry (CSG) operations were certainly good but overall, very slow. CGAL is one library I had worked with and I found that the time required for operations on even moderately complex meshes was quite long. CGAL’s numeric precision and stability is impeccable, the 3D CSG operations in CGAL are based on 3D Nef Polyhedra but I found myself waiting quite a while for results.
I exchanged a couple emails with Gilbert and he pointed me to a new library he had published, Cork. One challenge with the models he used in his Fast, Exact paper is that the internal representation of 3D meshes was not all that compatible with other toolsets. Though the boolean operations were fast, using those algorithms imposed a conversion overhead and eliminates the ability to take other algorithms developed on standard 3D mesh representations and use them directly on the internal data structures. Cork is fast but uses a ‘standard’ internal representation of 3D triangulated meshes, a win-win proposition.
I’ve always been one to tinker with code, so I forked Gilbert’s code to play with it. I spent a fair amount of time working with the code and I don’t believe I found any defects but I did find a few ways to tune it and bump up the performance. I also took a swag at parallelizing sections of the code to further reduce wall clock time required for operation, though with limited success. I believe the main problem I ran into is related to cache invalidation within the x86 CPU. I managed to split several of the most computationally intensive sections into multiple thread of execution – but the performance almost always dropped as a result. I am not completely finished working on threading the library, I may write a post later on what I believe I have seen and how to approach parallelizing algorithms like Cork on current generation CPUs.
Building the Library
My fork of Cork can be found here: https://github.com/stephanfr/Cork. At present, it only builds on MS Windows with MS Visual Studio, I use VS 2013 Community Edition. There are dependencies on the Boost C++ libraries, the MPIR library, and Intel’s Threading Building Blocks library. There are multiple build targets, both for Win32 and x64 as well as for Float, Double and SSE arithmetic based builds. In general, the Win32 Float-SSE builds will be the quickest but will occasionally fail due to numeric over or underflow. The Double x64 builds are 10 to 20% slower but seem solid as a rock numerically. An ‘Environment.props’ file exists at the top level of the project and contains a set of macros pointing to dependencies.
The library builds as a DLL. The external interface is straightforward, the only header to include is ‘cork.h’, it will include a few other files. In a later post I will discuss using the library in a bit more detail but a good example of how to use it may be found in the ‘RegressionTest.cpp’ file in the ‘RegressionTest’ project. At present, the library can only read ‘OFF’ file formats.
There is no reason why the library should not build on Linux platforms, the dependencies are all cross platform and the code itself is pretty vanilla C++. There may be some issues compiling the SSE code in gcc, but the non-SSE builds should be syntactically fine.
Sample Meshes
I have a collection of sample OFF file meshes in the Github repository: https://github.com/stephanfr/SolidModelRepository. The regression test program loads a directory and performs all four boolean operations between each pair of meshes in the directory – writing the result mesh to a separate directory.
These sample meshes range from small and simple to large and very complex. For the 32bit builds, the library is limited to one million points and some of the samples when meshed together will exceed that limit. Also, for Float precision builds, there will be numeric over or underflows whereas for x64 Double precision builds, all operations across all meshes should complete successfully.
When Errors (Inevitably) Occur
I have tried to catch error conditions and return those in result objects with some descriptive text, the library should not crash. The code is very sensitive to non-manifold meshes. The algorithms assume both meshes are two manifold. Given the way the optimizations work, a mesh may be self intersecting but if the self intersection is in a part of the model that does not intersect with the second model, the operation may run to completion perfectly. A different mesh my intersect spatially with the self intersection and trigger an error.
Meshes randomly chosen from the internet are (in my experience) typically not two manifold. I spent a fair amount of time cleaning up the meshes in the sample repository. If you have a couple meshes and they do not what to union – use a separate program like MeshLab to look over the meshes and double check that they are both in fact 2 manifold.
Conclusion
If you are interested in CSG and need a fast boolean library, give Cork a shot. If you run into crashes or errors, let me know – the code looks stable for my datasets but they are far from exhaustive.
Stephan Friedl 