Boolean Redesign #67744

Closed
opened 2019-07-26 16:16:20 +02:00 by Howard Trickey · 71 comments
Member

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. 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
Author
Member

Added subscribers: @howardt, @ideasman42

Added subscribers: @howardt, @ideasman42

Added subscriber: @DuarteRamos

Added subscriber: @DuarteRamos

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

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

Added subscriber: @cwolf3d

Added subscriber: @cwolf3d

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
Author
Member

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.

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

Added subscriber: @scorpion81

Added subscriber: @scorpion81
Member

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.

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.
Author
Member

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

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.

Added subscriber: @capnm

Added subscriber: @capnm

Added subscriber: @nokipaike

Added subscriber: @nokipaike

Added subscriber: @CareAgain

Added subscriber: @CareAgain

Added subscriber: @ahmad.junaed

Added subscriber: @ahmad.junaed

Added subscriber: @NahuelBelich

Added subscriber: @NahuelBelich

Added subscriber: @item412

Added subscriber: @item412

Added subscriber: @ThatAsherGuy

Added subscriber: @ThatAsherGuy

Added subscriber: @testure

Added subscriber: @testure

Added subscriber: @justastatue

Added subscriber: @justastatue

Added subscriber: @maxivazquez

Added subscriber: @maxivazquez
Member

Added subscriber: @lichtwerk

Added subscriber: @lichtwerk

Added subscriber: @Jaydead

Added subscriber: @Jaydead

Added subscriber: @Zuorion-4

Added subscriber: @Zuorion-4

Added subscriber: @Fux

Added subscriber: @Fux

Added subscriber: @ugosantana

Added subscriber: @ugosantana

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

Added subscriber: @MrBlissfly

Added subscriber: @MrBlissfly

Added subscriber: @relwof

Added subscriber: @relwof

Added subscriber: @MiroHorvath

Added subscriber: @MiroHorvath

Added subscriber: @yebyte

Added subscriber: @yebyte

Added subscriber: @z01ks

Added subscriber: @z01ks

Added subscriber: @MACHIN3

Added subscriber: @MACHIN3

Added subscriber: @arc4g-1

Added subscriber: @arc4g-1

Added subscriber: @AmosManneschmidt

Added subscriber: @AmosManneschmidt

Added subscriber: @SpectreFirst

Added subscriber: @SpectreFirst

Added subscriber: @MaciejMorgas

Added subscriber: @MaciejMorgas

Added subscriber: @thomasmouilleron

Added subscriber: @thomasmouilleron

Added subscriber: @korjaa

Added subscriber: @korjaa

Added subscriber: @kouzanagi

Added subscriber: @kouzanagi

Added subscriber: @Draxley

Added subscriber: @Draxley

Added subscriber: @Schiette

Added subscriber: @Schiette

Added subscriber: @Russ1642

Added subscriber: @Russ1642

Added subscriber: @snieb-1

Added subscriber: @snieb-1

Added subscriber: @shanberg

Added subscriber: @shanberg

Added subscriber: @costa

Added subscriber: @costa

Added subscriber: @toruki

Added subscriber: @toruki

Added subscriber: @ckohl_art

Added subscriber: @ckohl_art

Added subscriber: @AlexeyPerminov

Added subscriber: @AlexeyPerminov

Added subscriber: @higgsas

Added subscriber: @higgsas

Added subscriber: @Pipeliner

Added subscriber: @Pipeliner

Added subscriber: @PetterLundh

Added subscriber: @PetterLundh

Added subscriber: @MeshVoid

Added subscriber: @MeshVoid

Added subscriber: @xan2622

Added subscriber: @xan2622

Added subscriber: @yunta

Added subscriber: @yunta

Added subscriber: @DimaM

Added subscriber: @DimaM

Added subscriber: @marioamb

Added subscriber: @marioamb

Added subscriber: @thinsoldier

Added subscriber: @thinsoldier
Contributor

Added subscriber: @KenzieMac130

Added subscriber: @KenzieMac130

Added subscriber: @christian-clavet

Added subscriber: @christian-clavet

This comment was removed by @christian-clavet

*This comment was removed by @christian-clavet*

Added subscriber: @Memento

Added subscriber: @Memento

Removed subscriber: @christian-clavet

Removed subscriber: @christian-clavet

Added subscriber: @SirPigeonz

Added subscriber: @SirPigeonz

Added subscriber: @Beryesa

Added subscriber: @Beryesa
Author
Member

Changed status from 'Confirmed' to: 'Resolved'

Changed status from 'Confirmed' to: 'Resolved'
Author
Member

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

Added subscriber: @1D_Inc

Added subscriber: @1D_Inc

Thank you!

Thank you!

Added subscriber: @Olliver

Added subscriber: @Olliver

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
Sign in to join this conversation.
No Label
Interest
Alembic
Interest
Animation & Rigging
Interest
Asset Browser
Interest
Asset Browser Project Overview
Interest
Audio
Interest
Automated Testing
Interest
Blender Asset Bundle
Interest
BlendFile
Interest
Collada
Interest
Compatibility
Interest
Compositing
Interest
Core
Interest
Cycles
Interest
Dependency Graph
Interest
Development Management
Interest
EEVEE
Interest
EEVEE & Viewport
Interest
Freestyle
Interest
Geometry Nodes
Interest
Grease Pencil
Interest
ID Management
Interest
Images & Movies
Interest
Import Export
Interest
Line Art
Interest
Masking
Interest
Metal
Interest
Modeling
Interest
Modifiers
Interest
Motion Tracking
Interest
Nodes & Physics
Interest
OpenGL
Interest
Overlay
Interest
Overrides
Interest
Performance
Interest
Physics
Interest
Pipeline, Assets & IO
Interest
Platforms, Builds & Tests
Interest
Python API
Interest
Render & Cycles
Interest
Render Pipeline
Interest
Sculpt, Paint & Texture
Interest
Text Editor
Interest
Translations
Interest
Triaging
Interest
Undo
Interest
USD
Interest
User Interface
Interest
UV Editing
Interest
VFX & Video
Interest
Video Sequencer
Interest
Virtual Reality
Interest
Vulkan
Interest
Wayland
Interest
Workbench
Interest: X11
Legacy
Blender 2.8 Project
Legacy
Milestone 1: Basic, Local Asset Browser
Legacy
OpenGL Error
Meta
Good First Issue
Meta
Papercut
Meta
Retrospective
Meta
Security
Module
Animation & Rigging
Module
Core
Module
Development Management
Module
EEVEE & Viewport
Module
Grease Pencil
Module
Modeling
Module
Nodes & Physics
Module
Pipeline, Assets & IO
Module
Platforms, Builds & Tests
Module
Python API
Module
Render & Cycles
Module
Sculpt, Paint & Texture
Module
Triaging
Module
User Interface
Module
VFX & Video
Platform
FreeBSD
Platform
Linux
Platform
macOS
Platform
Windows
Priority
High
Priority
Low
Priority
Normal
Priority
Unbreak Now!
Status
Archived
Status
Confirmed
Status
Duplicate
Status
Needs Info from Developers
Status
Needs Information from User
Status
Needs Triage
Status
Resolved
Type
Bug
Type
Design
Type
Known Issue
Type
Patch
Type
Report
Type
To Do
No Milestone
No project
No Assignees
57 Participants
Notifications
Due Date
The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: blender/blender#67744
No description provided.