Page MenuHome

Boolean Redesign
Open, NormalPublic

Tokens
"Love" token, awarded by ugosantana."Like" token, awarded by yebyte."Love" token, awarded by mazigh."Love" token, awarded by roman13."Love" token, awarded by knightknight."Love" token, awarded by maxivz."Love" token, awarded by fiendish55."Like" token, awarded by DrLex."Love" token, awarded by bnzs."Love" token, awarded by Zuorion."100" token, awarded by koloved."Love" token, awarded by CareAgain."Love" token, awarded by amonpaike."Orange Medal" token, awarded by Way."Like" token, awarded by erickblender."Like" token, awarded by YAFU."Love" token, awarded by stephen_leger."Love" token, awarded by xrg."Love" token, awarded by dark999."Love" token, awarded by wevon."Love" token, awarded by billreynish.
Authored By

Description

Problem Description

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

Proposed Design

Some design decisions to make:

  1. What algorithm(s) should be used?
  2. What kind of arithmetic to use? Possibilities are: floats, doubles, or exact arithmetic (would likely involve porting some exact arithmetic library to Blender).
  3. 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?

Algorithms

I surveyed a number of papers on how to do Booleans. Two of the most promising papers, in my opinion, are:

"Mesh Arrangements for Solid Geometry", by Zhou, Grinspun, Zorin, Jacobson. Siggraph 2016.

  • 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).

"Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments", by HachenBerger, Kettner, and Melhorn. Computational Geometry 38 (2007).

  • 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.

Arithmetic

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.

Development approach

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.

Details

Type
Design

Event Timeline

Howard Trickey (howardt) lowered the priority of this task from Needs Triage by Developer to Normal.Jul 26 2019, 4:16 PM
Howard Trickey (howardt) created this task.
Howard Trickey (howardt) created this object with edit policy "BF Blender (Project)".

Would you be open to the idea of supporting Boolean operations on other object types, like directly bezier curve objects? Would be useful for operations without having to convert to mesh first

Addon Curve Cad Tools supports boolean operations on curves. You need to test this addon well. All errors can be sent to the author or me.

https://developer.blender.org/T65825

Booleans on elements other than meshes are out of scope for this task, which is already hard enough. The math and algorithms would be rather different for curve objects. Good to hear that the Curve Cad Tools addon supports boolean operations on curves. Maybe some future design task could consider porting those into the main C code for Blender, if the authors agree.

Maybe just as another idea: what about volume-based boolean operations with OpenVDB ? But... the remesher can so far only make "soft" edges / beveled edges… it is (imho) very hard to nearly impossible to get sharp edges.
But you get different advantages like not needing to worry about self-intersections for example (although a volume of a flat object still is an issue, obviously).

https://blenderartists.org/t/pablo-dobarros-master-plan-for-sculpting-and-his-official-sculpting-branch/1150731/335
here is an example of how I utilized OpenVDB CSG operations in the voxel remesh modifier.
As I said, just my 2 cents.

Edit: Oops, read too late that booleans on non-mesh objects are out of scope… sorry.

Booleans on elements other than meshes are out of scope for this task, which is already hard enough. The math and algorithms would be rather different for curve objects. Good to hear that the Curve Cad Tools addon supports boolean operations on curves. Maybe some future design task could consider porting those into the main C code for Blender, if the authors agree.

I think you misunderstood, maybe I didn't explain it well.
I think you are both talking about edit mode boolean operations on bezier curve objects, which are indeed a extremely useful, and I've used them in your addon already.
Those are obviously quite different in nature, but I actually meant Boolean operations in Object mode, using the generated mesh from beveled or extruded Bezier curve objects.

Oh I see.

Still out of scope for this task. But would a way to achieve the desired result be to have a modifier that converts a Curve object (with bevel / extrude parameters set to something nonzero) into a Mesh. Then the Boolean modifier would only have to be careful to ask if the derived object it gets as input is a Mesh, regardless of whether the underlying object is a Curve or a Mesh? (Actually, I don't know how much of Blender might go wrong with such an Object-type change in the modifier stack. This might be trivial or already working, or it might be a major change.)

But would a way to achieve the desired result be to have a modifier that converts a Curve object (with bevel / extrude parameters set to something nonzero) into a Mesh

That would indeed be perfectly acceptable, in fact even preferable. That could even potentially solve every pending request to support X modifier on Bezier curves (like Bevel and particles, among others)
I was hoping that in "everything nodes" there would eventually be such a node that would basically act as an "abstraction layer" and allow any type of actions on meshes generated from bezier curves (or other object types), but that is obviously out of scope here.

Anyway thanks for the response.

Way awarded a token.Jul 26 2019, 8:40 PM