More Boolean Solvers #120182

New Issue

Howard Trickey · 2024-04-02T18:50:27+02:00

Howard Trickey commented

2024-04-02 18:50:27 +02:00

Why More Boolean Solvers?

The Mesh Boolean node in Blender 4.1 and earlier uses only the Exact Boolean geometry solver, unlike the modifier which allowed a choice between the native float boolean solver and the Exact Boolean solver that was put into Blenlib, using the "Mesh Arrangements" paper for the algorithm.

Users have long asked for the float solver to be included as an option in the Mesh Boolean node. And in general, complained about the speed of the Exact Boolean solver. For example, this bug: Extremely Long time delay using geometry nodes with simple mesh boolean node 37706ms #98020.

Some recent papers and open source projects have offered hope of even better and even faster solvers. Having a super-fast solver (even faster than the current float solver) is desirable especially for these use cases:

sculpting
high-detail hard-ops modeling
interactive tools that would like to use boolean ("extrude manifold", "bevel-after-boolean")

Which Solvers to Add?

Native Float Solver

The obvious first one to add is the current native float solver.

Pros

Already works, though needed some adaptation to work in geometry node context
Decently fast on medium size models
Users of the modifier are familiar with how to use it to avoid problems
Doesn't put any limitations on the topology of the inputs
Doesn't touch the parts of the mesh that aren't part of intersection (so less chance for messing up attributes on those parts of the meshes)

And in fact, the main branch of the 4.2 alpha already has the native float solver added. #119294.

Cons

Doesn't work with coplanar faces or intersections that hit exactly on vertices or edges of the other meshes involved
The raycast method for determining insideness/outsideness isn't reliable, especially on high-density meshes
Not a lot of attention paid to parallelizing it (I think BVH tree building, for fast intersection testing, is parallelized)
Needs a round trip through BMesh, which gathers more topology information than is strictly necessary and in any case isn't well optimized for modern computer memory

Manifold Float Solver

We recently became aware of the manifold open source boolean solver. This is a float solver too, but it uses a technique of symbolic perturbation to make it guaranteed to product a manifold output when given a manifold input. Here "manifold" means that the input edges are all used in exactly two faces and the those faces are joined with consistently facing normals. The upshot of this is that it has some restrictions but is much more robust than our current float solver, and is probably faster to boot.

Pros

Robust, so less likely to fail in strange ways compared to the native float solver
Highly parallelized so will take full advantage of modern machines with many cores
The library has means for tracking which original elements the output elements come from, making attribute propagation reasonably straightforward
The developer is active and engages with us in a very timely fashion

Cons

The manifold requirement on inputs means that users cannot use this with just any Blender Mesh. Though if one starts with Mesh primitives and is a bit careful, it is not hard to maintain the manifold property. And some non-manifold meshes can easily be faked into being manifold for the purpose of doing the boolean. For example, the library has routines for booleaning with a plane that are handled this way.
The library requires triangulated input, unlike the native float solver. So this adds a slow-down step, and also adds the need to "untriangulate" the result, which also will slow things down. The current exact solver does this too, however, and has code that can be copied to do the untriangulation.
Several new dependencies are needed in Blender, mostly header-only libraries, but Clipper2 is an actual library
Using an external library instead of writing the code ourselves has several downsides: (1) we have to rely on upstream to fix bugs (unless we want to get into a patch-it-ourselves game); (2) we can't really adapt the code to our specific use case, which may mean, for instance, extra copying of data into nearly-identical forms, which wastes time and memory. (3) less intimate familiarity with how the library works may mean that bugs are harder to diagnose and fix.

Ember Solver

Another task, Exact Boolean V2 #114476, describes a new native exact solver that I have been working on. It is based on using fixed-length multiprecision integer arithmetic. The authors of the paper that it is based on claim that their implementation is faster than float solvers they have measured against (not including Manifold, which post-dates the paper). It had been my intention to use this to replace the old Exact Solver, and maybe avoid the need for any float solver, but at this point I am a lot less clear that that can happen. It has taken a lot longer than i expected to get it working (and it is still quite a way from really working), so when the Manifold library came to my attention, I switched priorities to get that solver in first.

Pros

Gives exact results, so extremely robust.
Has a promising approach of subdividing the input by successive space-partitioning planes, into "subproblems". This has three great speed advantages: (1) naturally parallelizable; (2) one can extensively use "short cut" evaluation to find cases where large parts of the input meshes don't need any processing; (3) one can have a local reference point in each subproblem, with calculated insideness/outsideness for each boolean argument -- this makes applying the boolean operation to a subproblem into a local problem that does't have to examine the whole input meshes.
We would know the code very well and can optimize it specifically in the Blender context

Cons

Preliminary tests of speed have not been all that encouraging. Probably lots of optimization at the base arithmetic level are still needed
it turns out to a lot more complicated than anticipated to take the results of the paper's algorithm -- a disconnected set of faces -- and turn them into a connected Mesh. At least, to do it efficiently.
The paper's algorithm produces T-junctions all over the place, which Blender users would not like. There might be ways to redo the intersection faces in a nicer way, but that's more algorithm development, and goes against the paper's desire to keep within a certain precision budget (which in turn determines how big the fixed-integer-length arithmetic has to be).
The paper's algorithm produces long skinny faces (almost zero-area) sometimes, which would likely have to be removed by more post-processing (a slow-down step). This is also true of the Manifold algorithm, but that library handles the postprocessing itself.
There are restrictions on the input topology, similar to those of the current (Mesh Arrangements) Exact Solver.

### Why More Boolean Solvers? The Mesh Boolean node in Blender 4.1 and earlier uses only the Exact Boolean geometry solver, unlike the modifier which allowed a choice between the native float boolean solver and the Exact Boolean solver that was put into Blenlib, using the "Mesh Arrangements" paper for the algorithm. Users have long asked for the float solver to be included as an option in the Mesh Boolean node. And in general, complained about the speed of the Exact Boolean solver. For example, this bug: [Extremely Long time delay using geometry nodes with simple mesh boolean node 37706ms #98020](https://projects.blender.org/blender/blender/issues/98020). Some recent papers and open source projects have offered hope of even better and even faster solvers. Having a super-fast solver (even faster than the current float solver) is desirable especially for these use cases: - sculpting - high-detail hard-ops modeling - interactive tools that would like to use boolean ("extrude manifold", "bevel-after-boolean") ### Which Solvers to Add? #### Native Float Solver The obvious first one to add is the **current native float solver.** _Pros_ - Already works, though needed some adaptation to work in geometry node context - Decently fast on medium size models - Users of the modifier are familiar with how to use it to avoid problems - Doesn't put any limitations on the topology of the inputs - Doesn't touch the parts of the mesh that aren't part of intersection (so less chance for messing up attributes on those parts of the meshes) And in fact, the main branch of the 4.2 alpha already has the native float solver added. [#119294](https://projects.blender.org/blender/blender/pulls/119294). _Cons_ - Doesn't work with coplanar faces or intersections that hit exactly on vertices or edges of the other meshes involved - The raycast method for determining insideness/outsideness isn't reliable, especially on high-density meshes - Not a lot of attention paid to parallelizing it (I think BVH tree building, for fast intersection testing, is parallelized) - Needs a round trip through BMesh, which gathers more topology information than is strictly necessary and in any case isn't well optimized for modern computer memory #### Manifold Float Solver We recently became aware of the [manifold](https://github.com/elalish/manifold) open source boolean solver. This is a float solver too, but it uses a technique of symbolic perturbation to make it guaranteed to product a manifold output when given a manifold input. Here "manifold" means that the input edges are all used in exactly two faces and the those faces are joined with consistently facing normals. The upshot of this is that it has some restrictions but is much more robust than our current float solver, and is probably faster to boot. _Pros_ - Robust, so less likely to fail in strange ways compared to the native float solver - Highly parallelized so will take full advantage of modern machines with many cores - The library has means for tracking which original elements the output elements come from, making attribute propagation reasonably straightforward - The developer is active and engages with us in a very timely fashion _Cons_ - The manifold requirement on inputs means that users cannot use this with just any Blender Mesh. Though if one starts with Mesh primitives and is a bit careful, it is not hard to maintain the manifold property. And some non-manifold meshes can easily be faked into being manifold for the purpose of doing the boolean. For example, the library has routines for booleaning with a plane that are handled this way. - The library requires triangulated input, unlike the native float solver. So this adds a slow-down step, and also adds the need to "untriangulate" the result, which also will slow things down. The current exact solver does this too, however, and has code that can be copied to do the untriangulation. - Several new dependencies are needed in Blender, mostly header-only libraries, but Clipper2 is an actual library - Using an external library instead of writing the code ourselves has several downsides: (1) we have to rely on upstream to fix bugs (unless we want to get into a patch-it-ourselves game); (2) we can't really adapt the code to our specific use case, which may mean, for instance, extra copying of data into nearly-identical forms, which wastes time and memory. (3) less intimate familiarity with how the library works may mean that bugs are harder to diagnose and fix. #### Ember Solver #### Another task, [Exact Boolean V2 #114476](https://projects.blender.org/blender/blender/issues/114476), describes a new native exact solver that I have been working on. It is based on using fixed-length multiprecision integer arithmetic. The authors of the paper that it is based on claim that their implementation is faster than float solvers they have measured against (not including Manifold, which post-dates the paper). It had been my intention to use this to replace the old Exact Solver, and maybe avoid the need for any float solver, but at this point I am a lot less clear that that can happen. It has taken a lot longer than i expected to get it working (and it is still quite a way from really working), so when the Manifold library came to my attention, I switched priorities to get that solver in first. _Pros_ - Gives exact results, so extremely robust. - Has a promising approach of subdividing the input by successive space-partitioning planes, into "subproblems". This has three great speed advantages: (1) naturally parallelizable; (2) one can extensively use "short cut" evaluation to find cases where large parts of the input meshes don't need any processing; (3) one can have a local reference point in each subproblem, with calculated insideness/outsideness for each boolean argument -- this makes applying the boolean operation to a subproblem into a local problem that does't have to examine the whole input meshes. - We would know the code very well and can optimize it specifically in the Blender context _Cons_ - Preliminary tests of speed have not been all that encouraging. Probably lots of optimization at the base arithmetic level are still needed - it turns out to a lot more complicated than anticipated to take the results of the paper's algorithm -- a disconnected set of faces -- and turn them into a connected Mesh. At least, to do it efficiently. - The paper's algorithm produces T-junctions all over the place, which Blender users would not like. There might be ways to redo the intersection faces in a nicer way, but that's more algorithm development, and goes against the paper's desire to keep within a certain precision budget (which in turn determines how big the fixed-integer-length arithmetic has to be). - The paper's algorithm produces long skinny faces (almost zero-area) sometimes, which would likely have to be removed by more post-processing (a slow-down step). This is also true of the Manifold algorithm, but that library handles the postprocessing itself. - There are restrictions on the input topology, similar to those of the current (Mesh Arrangements) Exact Solver.

👍 5 ❤️ 13 🎉 3 🚀 4

Howard Trickey added this to the 4.2 LTS milestone 2024-04-02 18:50:27 +02:00

Howard Trickey added the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

More Boolean Solvers #120182

Why More Boolean Solvers?

Which Solvers to Add?

Native Float Solver

Manifold Float Solver

Ember Solver

Performing the Tri-Tri Intersections

Iteratively Removing Faces