This design task is about making the Boolean modifier and intersect tool handle special cases and be more robust, so that users can depend on it and not complain about things Carve could do that the BMesh boolean cannot.
A number of bug reports about Boolean have been captured in T47030. They can be mostly grouped into these kinds of problems:
- Not handling cases where there is coinciding or nearly coinciding geometry (typically edges and faces that intersect other edges and faces at more than one point, or vertices that intersect the middle of a face or edge). By design the current BMesh Boolean code does not handle these cases, putting it on the user to move the geometry around some so that the desired effect can be gotten without these special cases. But this annoys users, who regard it as a bug, and also sometimes misses the point of what they are trying to do (e.g., bring in a bunch of "roads" in a plane and intersect them).
- Not dealing with precision problems (e.g., near-zero area faces). I suspect but am not positive that when the intersection objects have very small faces, say the result of sculpting on a high-res mesh, that the precision problems start to become abundant.
- (For Boolean only) Not dealing with non-hermetically sealed intersection objects. Again this is by design in the current code, but some users miss the behavior of Carve, which would sometimes do useful things in such cases. Also, by requiring hermetically sealed objects, we miss the opportunity to use Boolean for cleaning up objects that have self-intersection.
- Performance issues, usually when there are a very large number of intersections in a single face. E.g., T52471
Some design decisions to make:
- What algorithm(s) should be used?
- What kind of arithmetic to use? Possibilities are: floats, doubles, or exact arithmetic (would likely involve porting some exact arithmetic library to Blender).
- Should this be done by evolving / modifying current BMesh code, or starting from scratch? If the latter, do we try to follow the lead of the current code in trying to do the work as much as possible in BMesh structures themselves, and reusing BMesh elements wherever possible, or do the calculations in some different structure and then rebuild all affected BMesh geometry?
I surveyed a number of papers on how to do Booleans. Two of the most promising papers, in my opinion, are:
- Handles coplanar, self-intersections, non-manifold edges (but not ‘flaps’ nor open volumes; uses exact arithmetic; requires closed volumes, but mentions generalized winding number concept (which could fix the requirement about no-open-volumes but looks a bit messy to incorporate).
- Handles everything in closure of boolean ops on half-spaces - so, non-manifold edges, topological singularities, etc. Uses exact arithmetic. Basic idea is to represent 3d topology by “Sphere Maps” which show which volumes are in/out around vertices. They have a representation called “Selective Nef Complex” (SNC) which is a lot like BMesh but with sphere maps at the vertices instead of just vertices. There’s an algorithm that creates SNC’s from just sphere maps. And another algorithm that does boolean operations by first doing all intersections, then getting sphere maps at each intersection point according to boolean operation and in/out labels, and finally synthesizing resulting SNC. This is what CGAL implements now.
The Zhou et al. paper pays more attention to things like coplanar faces, and looks easier to implement, so I have a preference for that approach.
An important subproblem that comes up as soon as we want to handle arbitrary intersections of faces, edges, and vertices in a single plane, is how to do that. The current Blender code uses the BM_face_split_edgenet function to do the work of remaking faces when there are edges intersecting it. So one approach is to generalize the triangle-triangle intersection code in Blenlib to handle all the results of coplanar intersections, and use that to figure out what edges to feed BM_face_split_edgenet. The latter would need to be slightly generalized to handle isolated vertices in a face too; treating them as zero-length edges will work (I tried this). One issue with this approach is that it only deals with intersections with one given face: if the things being intersected with the face intersect with each other, then the code doesn't work, and needs considerable development in order to make it work.
Another approach to the planar intersection problem is to use Constrained Delaunay Triangulation, with an algorithm that will discover all the intersections, coincident vertices, and overlapping edges, as a by-product of doing that triangulation. Afterwards, most of the triangulation edges can be removed, leaving only enough that valid BMesh faces can be formed out of what remains. A promising paper for doing CDT, paying close attention to overlaps etc., and keeping track of how the output relates to the input, is "Fully Dynamic Constrained Delaunay Triangulations”, by Kallmann, Bieri, and Thalmann. I have this implemented now and plan to soon propose putting it in Blenlib, as I believe it can be useful for other things, including Python API users.
Update (June 15, 2020)
Though I had the whole thing mostly working in May 2020, I hit a kind of brick wall when intersecting very dense meshes. My approach to using doubles with epsilons was just proving too hard to make work in such cases. More details of my journey are in this devtalk thread.
The new approach I am taking is to make a fairly faithful implementation of the Mesh Arrangements Zhou et al paper cited above. For the CDT, I switched to using the Guibas-Stolfi algorithm described in "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams", by Guibas and Stolfi, though still using the plane subdivision data structure from the Kallmann et al. paper. For triangle-triangle intersection, I am using the algorithm of "Faster Triangle-Triangle Intersection Tests", by Devillers and Guigue. This is all mostly implemented now in the newboolean branch.
We had some discussion of arithmetic in general, and somewhat about Boolean in particular, in this devtalk thread. A general consensus was that using double arithmetic internally to Boolean would likely be helpful. But what about exact arithmetic? Many of the papers on Boolean and other intersection problems have reached the conclusion: just use exact arithmetic and many problems go away; it is a lot slower, but can be sped up some by tricks that use floating point in many cases an only resorting to the more expensive techniques sometimes. I see three main problems with this approach: (1) the code to implement exact arithmetic is complex; there are libraries that we could import into Blender (maybe -- have to check licensing) but do we need to do that? (2) I'm pretty sure our users don't actually want the result of doing exact arithmetic: in many cases where faces are almost coplanar, they would not appreciate have two separate planes joined by extremely long and skinny triangles. (3) Do we really want the performance hit? For all of these reasons, I think we should use doubles (with careful epsilon tests) instead of exact arithmetic.
Update (June 15, 2020)
Going along with the algorithm changes update, above, I have decided to bite the bullet and use exact arithmetic. I have decided to use the rational type from GMP multiprecision library, which is a reasonably small additional library dependency for Blender, and has a suitable license. In order to solve the other downsides I mention above: maybe add post-processing to remove very small triangles; and use floating point filtering to try to limit the cases where full rational arithmetic is needed for doing orientation tests. The basic support for this is now in the newboolean branch, though not yet with floating point filters. There is a new rational type vector called mpq2 and mpq3 in the C++ blenlib.
I have tried for a number of months to use the "evolve the current code" approach. It is kind of working and I'll continue to do that for a while. But the code needed to deal with merged vertices and edges has gotten increasingly complex and hard to do correctly, so I hit a kind of wall. I think switching from trying to use BM_face_split_edgenet to the CDT approach may unblock me, so I will continue down this path for now. But there are attractions to the approach of building the geometry up separately from existing BMesh, and then putting it back into BMesh at the end. That's the approach I took for Bevel, and I do not regret that decision. So if the code starts to look too hairy, I might try to switch to that approach.
Update (June 15, 2020)
For the reboot started in May, I decided to use C++ for the implementation. There is a template-ized version of the CDT routine (capable of doing either double arithmetic, with exact-arithmetic predicates; or an mpq2 version using exact rational arithmetic. For now I am only doing an mpq3 version of the Mesh Intersection and Boolean functions, since the attempt to do it with doubles and epsilon tweaking mostly failed, so there doesn't seem to be much point in template-izing these algorithms with double, at least for now.
Most of the heavy algorithm lifting operates on a separate, simple, mesh representation that uses mpq3 coordinates and integer vertex indices for triangles and faces. The reasons for not doing this in BMesh were (1) We need separate coordinate representation for the mpq3 values (though I could have solved this problem by having and maintaining a parallel map of BMVert -> exact coords); and (2) I thought the algorithm may have to go through some states where the mesh is not representable in BMesh; (3) it was not clear that maintaining the topological relations in all generality, as BMesh does, was going to be necessary; (4) it is easier to debug algorithms with integers instead of pointers everywhere, and also hash tables based on integers can lead to algorithms with consistent results across runs and architectures, while hash tables based on pointers usually do not have those properties; and (5) there is no C++ interface for BMesh (yet, anyway).
Status as of June 15, 2020: The newboolean branch does basic booleans using the new approach in the Boolean tool (with an Exact option, so the user can choose between the current BMesh boolean and the new one). However, I have yet to code the part that removes the triangulation edges after doing the boolean, and yet to code the part that preserves the BMVert, BMEdge, BMLoop, and BMFace attributes and data. And no performance tuning has been done yet, so it is still very slow. I expect that getting the whole thing done to the state where users will want to use it will take another two to three months.
Status as of July 14, 2020: Now the code to remove triangulation edges after doing the boolean is done. Also, coplanar intersections work. I also did a fairly big refactor to reduce copying of vertex and face data, and to prepare for using floating-point filtering of exact arithmetic predicates (to improve performance). Also did the very first step of performance improvement: using bounding boxes and BVH trees to greatly reduce the number of triangle-triangle intersections tried. The performance is still very far from what I want it to be (currently about 100 times slower than the BMesh boolean on test that intersects two 8k face spheres; and 10 times slower on two 250 face spheres). But I still have a lot of things to do that I know will improve performance.
In terms of functionality, still to do: using original mesh attributes on created new ones (though plumbing is there to make this easy now); hooking up the boolean modifier to this code; doing proper post-operator selection; handling the proper final cutting in the Boolean Knife intersect mode; some handling of non-manifold inputs.
Status as of Aug 4, 2020: It is mostly all implemented now: the modifier is hooked up, the Boolean Knife mode works, the original edge and face attributes are preserved. The performance is much better (within a factor of 5 of the BMesh code); there is still more headroom for performance improvement, so will likely to get even closer to the old BMesh performance in the near future. It still needs work to do something reasonable if the inputs are non-manifold. Now the GMP libraries are in SVN (thanks to the platform maintainers!), so buildbot can build the branch, as well as anyone else who can compile blender,
Status as of Aug 17, 2020: The implementation is complete. There is a known performance problem, which will be fixed soon, and other opportunities for performance improvement still. Most bugs found by initial testers have been fix, though one is still outstanding. This code seems in reasonable shape (to me) to include in 2.91. But still need a review and agreement from the rest of the Modeling Module before this is certain.
Update (Aug 28, 2020)
The newboolean branch has now been merged into master, and should be in the 2.91 release, barring any big problems discovered during testing.