Boolean Redesign #67744

New Issue

Howard Trickey · 2019-07-26T16:16:20+02:00

Howard Trickey commented

2019-07-26 16:16:20 +02:00

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 #47030. 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., #52471

Proposed Design

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?

Algorithms

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

[[http://www.cs.columbia.edu/cg/mesh-arrangements/mesh-arrangements-for-solid-geometry-siggraph-2016-zhou-et-al.pdf |
"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).

[[https://www.sciencedirect.com/science/article/pii/S092577210700018 |
"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 [http:*citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.6477&rep=rep1&type=pdf | "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 [https:*hal.inria.fr/inria-00072100/document|"Faster Triangle-Triangle Intersection Tests", by Devillers and Guigue. This is all mostly implemented now in the newboolean branch.

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.

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.

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.

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.

# 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 #47030. 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., #52471 # 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: [[http://www.cs.columbia.edu/cg/mesh-arrangements/mesh-arrangements-for-solid-geometry-siggraph-2016-zhou-et-al.pdf | "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). [[https://www.sciencedirect.com/science/article/pii/S092577210700018 | "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 [[http:*citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.6477&rep=rep1&type=pdf | "Fully Dynamic Constrained Delaunay Triangulations”, by Kallmann, Bieri, and Thalmann](https:*en.wikipedia.org/wiki/Constrained_Delaunay_triangulation). 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](https://devtalk.blender.org/t/boolean-improvements/6200/72). 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 [[https:*hal.inria.fr/inria-00072100/document|"Faster Triangle-Triangle Intersection Tests", by Devillers and Guigue](https:*dl.acm.org/doi/10.1145/282918.282923). This is all mostly implemented now in the *newboolean* branch. ## Arithmetic We had some discussion of arithmetic in general, and somewhat about Boolean in particular, in [this devtalk thread](https://devtalk.blender.org/t/arithmetic-types-in-blender/150/6). 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](https:*gmplib.org/), 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. ## 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. **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.

Howard Trickey self-assigned this 2019-07-26 16:16:20 +02:00

Howard Trickey commented

2019-07-26 16:16:20 +02:00

Added subscribers: @howardt, @ideasman42

Duarte Farrajota Ramos commented

2019-07-26 17:10:07 +02:00

Added subscriber: @DuarteRamos

Duarte Farrajota Ramos commented

2019-07-26 17:16:29 +02:00

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

Vladimir Spivak commented

2019-07-26 17:29:07 +02:00

Added subscriber: @cwolf3d

Vladimir Spivak commented

2019-07-26 17:29:07 +02:00

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

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

Howard Trickey commented

2019-07-26 17:37:57 +02:00

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.

Martin Felke commented

2019-07-26 17:38:23 +02:00

Added subscriber: @scorpion81

Martin Felke commented

2019-07-26 17:38:23 +02:00

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.

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.

Duarte Farrajota Ramos commented

2019-07-26 18:14:22 +02:00

In #67744#736230, @howardt wrote:
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.

> In #67744#736230, @howardt wrote: > 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.

Howard Trickey commented

2019-07-26 18:47:36 +02:00

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

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

Duarte Farrajota Ramos commented

2019-07-26 18:56:22 +02:00

In #67744#736320, @howardt wrote:
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.

> In #67744#736320, @howardt wrote: > 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.

Martin Capitanio commented

2019-07-26 19:06:58 +02:00

Added subscriber: @capnm

noki paike commented

2019-07-26 21:08:49 +02:00

Added subscriber: @nokipaike

Michael New commented

2019-07-31 01:32:08 +02:00

Added subscriber: @CareAgain

Ahmad Junaed commented

2019-08-09 05:23:29 +02:00

Added subscriber: @ahmad.junaed

Nahuel Belich commented

2019-08-09 21:46:10 +02:00

Added subscriber: @NahuelBelich

item412 commented

2019-08-11 05:02:30 +02:00

Added subscriber: @item412

Asher commented

2019-08-16 01:59:39 +02:00

Added subscriber: @ThatAsherGuy

eldee smith commented

2019-08-21 20:42:04 +02:00

Added subscriber: @testure

M commented

2019-08-22 18:13:21 +02:00

Added subscriber: @justastatue

Maximiliano Vazquez commented

2019-08-25 21:01:56 +02:00

Added subscriber: @maxivazquez

Philipp Oeser commented

2019-08-28 15:36:14 +02:00

Added subscriber: @lichtwerk

Janne Aliu commented

2019-09-01 13:27:20 +02:00

Added subscriber: @Jaydead

PawelP commented

2019-09-05 23:41:30 +02:00

Added subscriber: @Zuorion-4

Tobias Fuchsberger commented

2019-09-11 12:23:47 +02:00

Added subscriber: @Fux

Ugo Santana commented

2019-11-08 13:44:05 +01:00

Added subscriber: @ugosantana

Ugo Santana commented

2019-11-08 13:44:05 +01:00

@howardt I read in another post that If things go well in the next few weeks, this could go for 2.82... I'm hoping you are getting those good weeks...

Couple of suggestion for the redesign: I think it would be great to add an option to automatically turn off for render and turn on wireframe visibility for the object of the operation, seeing only the result object. It could have another option to automatically parent, to move both together. With these options selected the apply button should delete the object and keep only the modified one...

@howardt I read in another post that If things go well in the next few weeks, this could go for 2.82... I'm hoping you are getting those good weeks... Couple of suggestion for the redesign: I think it would be great to add an option to automatically turn off for render and turn on wireframe visibility for the object of the operation, seeing only the result object. It could have another option to automatically parent, to move both together. With these options selected the apply button should delete the object and keep only the modified one...

Richard Smith commented

2019-11-09 17:59:30 +01:00

Added subscriber: @MrBlissfly

James Fowler commented

2019-11-12 19:26:07 +01:00

Added subscriber: @relwof

Miro Horváth commented

2019-11-15 23:50:22 +01:00

Added subscriber: @MiroHorvath

Yiwei Ye commented

2019-11-17 05:19:46 +01:00

Added subscriber: @yebyte

Peeter Maimik commented

2019-12-21 16:23:15 +01:00

Added subscriber: @z01ks

MACHIN3 commented

2020-01-12 00:06:40 +01:00

Added subscriber: @MACHIN3

AR commented

2020-01-12 11:06:45 +01:00

Added subscriber: @arc4g-1

Amos Manneschmidt commented

2020-02-17 16:42:06 +01:00

Added subscriber: @AmosManneschmidt

Alex commented

2020-02-29 16:39:19 +01:00

Added subscriber: @SpectreFirst

Maciej Morgaś commented

2020-03-04 10:38:40 +01:00

Added subscriber: @MaciejMorgas

Thomas commented

2020-03-14 16:05:33 +01:00

Added subscriber: @thomasmouilleron

Jaakko Korhonen commented

2020-03-31 10:44:14 +02:00

Added subscriber: @korjaa

kouza commented

2020-04-02 14:56:10 +02:00

Added subscriber: @kouzanagi

Martin Tégláš commented

2020-04-03 02:22:40 +02:00

Added subscriber: @Draxley

Pieter Schiettecatte commented

2020-04-18 17:00:52 +02:00

Added subscriber: @Schiette

Russell commented

2020-04-19 01:01:05 +02:00

Added subscriber: @Russ1642

snieb commented

2020-04-19 14:03:42 +02:00

Added subscriber: @snieb-1

shanberg commented

2020-04-21 14:35:46 +02:00

Added subscriber: @shanberg

fwfeet commented

2020-04-21 19:23:52 +02:00

Added subscriber: @costa

Roger Ivan Pineda M commented

2020-04-28 10:51:49 +02:00

Added subscriber: @toruki

Chris Kohl commented

2020-05-01 21:49:20 +02:00

Added subscriber: @ckohl_art

Alexey commented

2020-05-31 18:32:30 +02:00

Added subscriber: @AlexeyPerminov

higgsas commented

2020-06-15 17:31:53 +02:00

Added subscriber: @higgsas

Pipeliner commented

2020-06-15 17:35:02 +02:00

Added subscriber: @Pipeliner

Petter Lundh commented

2020-06-22 09:53:38 +02:00

Added subscriber: @PetterLundh

Chingiz Jumagulov commented

2020-06-22 22:19:49 +02:00

Added subscriber: @MeshVoid

xan2622 commented

2020-06-24 17:17:29 +02:00

Added subscriber: @xan2622

Maciej Blomberg commented

2020-06-27 11:07:53 +02:00

Added subscriber: @yunta

Dmitry commented

2020-08-07 12:39:02 +02:00

Added subscriber: @DimaM

Mario Ambrogetti commented

2020-08-07 18:06:44 +02:00

Added subscriber: @marioamb

thin soldier commented

2020-08-12 01:16:43 +02:00

Added subscriber: @thinsoldier

Kenzie commented

2020-08-16 07:47:46 +02:00

Added subscriber: @KenzieMac130

Christian Clavet commented

2020-08-19 19:25:15 +02:00

Added subscriber: @christian-clavet

Christian Clavet commented

2020-08-19 19:25:15 +02:00

This comment was removed by @christian-clavet

*This comment was removed by @christian-clavet*

Anton Raves commented

2020-08-20 09:58:21 +02:00

Added subscriber: @Memento

Christian Clavet commented

2020-08-20 16:40:55 +02:00

Removed subscriber: @christian-clavet

Przemyslaw Golab (SirPigeonz) commented

2020-08-27 16:08:55 +02:00

Added subscriber: @SirPigeonz

Berk Elyesa Yıldırım commented

2020-09-02 16:02:18 +02:00

Added subscriber: @Beryesa

Howard Trickey commented

2020-09-05 12:40:12 +02:00

Changed status from 'Confirmed' to: 'Resolved'

Howard Trickey closed this issue

2020-09-05 12:40:12 +02:00

Howard Trickey commented

2020-09-05 12:40:12 +02:00

Closing this task now, as the design is done and implemented and now merged to master with commit 9e09b5c418

Closing this task now, as the design is done and implemented and now merged to master with commit 9e09b5c418

Paul Kotelevets commented

2020-09-05 13:40:27 +02:00

Added subscriber: @1D_Inc

Paul Kotelevets commented

2020-09-05 13:40:27 +02:00

Thank you!

Mr Chocolate Bar commented

2020-09-28 19:18:27 +02:00

Added subscriber: @Olliver

Mr Chocolate Bar commented

2020-09-28 19:18:27 +02:00

Hi, amazing work on this! I've started using it in the current 2.91 Alpha (and actually do all my modelling in the alpha version now because of how much Im loving it) :)

Now, Im here because when using a lot of cutters, eventually the boolean gets very slow (Even when using the "fast" mode for the modifier) with lots of cutters in the stack where it eventually gets to a point where it simply gets unbearing/impossible to do any modelling with it active in the modifier stack, so Im genuinely asking for more optimization on this when used with a large collection.

Here I have an example just to demo:
https://u.teknik.io/ZvCFP.mp4 (Shorter)
https://u.teknik.io/xV2va.mp4 (Slightly longer)
Theres a single mesh with a boolean modifier with only 6 cutters, which after the boolean modifier (as well as a bevel modifier) results in 1.09 million polygons/triangles and 550K vertices.

So, Im thinking it would be nice if the modifier could update the geometry of the mesh only based on the last modified cutter in the "cutter" collection instead of recalculating the geometry based on every cutter in the collection like it appears to do at the time being.

Other than this issue however, amazing work, this update speeds up any non-destructive modelling workflow by a lot and will for sure be much appreciated by all hard surface artists out there.

Hi, amazing work on this! I've started using it in the current 2.91 Alpha (and actually do all my modelling in the alpha version now because of how much Im loving it) :) Now, Im here because when using a lot of cutters, eventually the boolean gets very slow (Even when using the "fast" mode for the modifier) with lots of cutters in the stack where it eventually gets to a point where it simply gets unbearing/impossible to do any modelling with it active in the modifier stack, so Im genuinely asking for more optimization on this when used with a large collection. Here I have an example just to demo: https://u.teknik.io/ZvCFP.mp4 (Shorter) https://u.teknik.io/xV2va.mp4 (Slightly longer) Theres a single mesh with a boolean modifier with only 6 cutters, which after the boolean modifier (as well as a bevel modifier) results in 1.09 million polygons/triangles and 550K vertices. So, Im thinking it would be nice if the modifier could update the geometry of the mesh only based on the last modified cutter in the "cutter" collection instead of recalculating the geometry based on every cutter in the collection like it appears to do at the time being. Other than this issue however, amazing work, this update speeds up any non-destructive modelling workflow by a lot and will for sure be much appreciated by all hard surface artists out there.

Thomas Dinges added this to the 2.91 milestone 2023-02-08 16:21:50 +01:00

Germano Cavalcante referenced this issue

2024-10-18 23:38:21 +02:00

Modifiers: Boolean Fast Mode Refactor #106631

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Boolean Redesign #67744

Problem Description

Proposed Design

Algorithms

Arithmetic

Development approach

Update (Aug 28, 2020)