More Boolean Solvers #120182

New Issue

Open

opened 2024-04-02 18:50:27 +02:00 by Howard Trickey · 23 comments

Howard Trickey commented 2024-04-02 18:50:27 +02:00

Member

Copy Link

Why More Boolean Solvers?

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

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

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

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

Which Solvers to Add?

Native Float Solver

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

Pros

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

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

Cons

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

Manifold Float Solver

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

Pros

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

Cons

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

Ember Solver

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

Pros

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

Cons

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

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

👍 5 ❤️ 13 🎉 3 🚀 4

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

Howard Trickey added the

Interest

Modeling

Interest

Geometry Nodes

Type

Design

labels 2024-04-02 18:50:28 +02:00

Howard Trickey self-assigned this 2024-04-02 18:50:28 +02:00

Sean Kim commented 2024-04-03 02:49:40 +02:00

Member

Copy Link

I did some very rough timings on the existing float solver to attempt to identify areas of potential optimization inside the existing BM_mesh_intersect function. For a mesh with 491,522 vertices and 524,288 faces, doing a Trim Lasso operation on the mesh in a developer build took 16.3s inside the BM_mesh_intersect function.

The areas of largest runtime are as follows:

Performing the Tri-Tri Intersections

    for (i = 0; i < tree_overlap_tot; i++) {
      bm_isect_tri_tri(&s,
                       overlap[i].indexA,
                       overlap[i].indexB,
                       looptris[overlap[i].indexA],
                       looptris[overlap[i].indexB],
                       isect_tri_tri_no_shared);
    }

(tree_overlap_tot = 3570558) taking 5.2s (31.9% of runtime)

Iteratively Removing Faces

      for (i = 0; i < tot; i++) {
        if (ftable[i]->mat_nr == -1) {
          BM_face_kill_loose(bm, ftable[i]);
        }
      }

(Removing 139446 / 525801 faces) taking 10.1s (61.9% of runtime)

Of the two areas, parallelizing the former seems less intrusive but still requires minor adjustments to some internal structs to support splitting this work across a number of threads.

I did some very rough timings on the existing float solver to attempt to identify areas of potential optimization inside the existing `BM_mesh_intersect` function. For a mesh with **491,522** vertices and **524,288** faces, doing a *Trim Lasso* operation on the mesh in a developer build took **16.3s** inside the `BM_mesh_intersect` function. The areas of largest runtime are as follows: ### Performing the Tri-Tri Intersections ``` for (i = 0; i < tree_overlap_tot; i++) { bm_isect_tri_tri(&s, overlap[i].indexA, overlap[i].indexB, looptris[overlap[i].indexA], looptris[overlap[i].indexB], isect_tri_tri_no_shared); } ``` (tree_overlap_tot = 3570558) taking 5.2s (31.9% of runtime) ### Iteratively Removing Faces ``` for (i = 0; i < tot; i++) { if (ftable[i]->mat_nr == -1) { BM_face_kill_loose(bm, ftable[i]); } } ``` (Removing 139446 / 525801 faces) taking 10.1s (61.9% of runtime) Of the two areas, parallelizing the former seems less intrusive but still requires minor adjustments to some internal `struct`s to support splitting this work across a number of threads.

❤️ 2

Bastien Montagne commented 2024-04-15 14:12:21 +02:00

Owner

Copy Link

@ideasman42 @JacquesLucke hey, any thoughts here?

@ideasman42 @JacquesLucke hey, any thoughts here?

Bastien Montagne commented 2024-04-15 14:17:04 +02:00

Owner

Copy Link

FYI some context from @LazyDodo re adding manifold lib to our dependencies:

[... Adding the] manifold (Apache 2) lib, this will bring in the following additional deps

• GLM (MIT)
• thrust (Apache2/BSD, concern: same platform support as cuda, we could be on or own for mac support there)
• Clipper2 (Boost Software License)
• QuickHull ("100% Public Domain.", yeah... I'm not sure how this jives with our GPL, someone at compliance needs to sign off on this, is that you these days @ThomasDinges ?)

Given the large number of deps it has, I don't think it living in /extern is the way to go
[...]

FYI [some context](https://blender.chat/channel/core-module?msg=K6Bzw9G5PR5inRoMT) from @LazyDodo re adding `manifold` lib to our dependencies: > [... Adding the] [manifold](https://github.com/elalish/manifold) (Apache 2) lib, this will bring in the following additional deps > > - [GLM](https://github.com/g-truc/glm/) (MIT) > - [thrust](https://github.com/NVIDIA/thrust) (Apache2/BSD, concern: same platform support as cuda, we could be on or own for mac support there) > - [Clipper2](https://github.com/AngusJohnson/Clipper2) (Boost Software License) > - [QuickHull](https://github.com/akuukka/quickhull) ("100% Public Domain.", yeah... I'm not sure how this jives with our GPL, someone at compliance needs to sign off on this, is that you these days @ThomasDinges ?) > > Given the large number of deps it has, I don't think it living in /extern is the way to go [...]

Hans Goudey commented 2024-04-15 20:16:54 +02:00

Member

Copy Link

I think it makes sense to pursue using the manifold library. Ideally the performance will be very good and we will be satisfied there. And ideally it could replace the existing exact solver. Adding library and its dependencies makes sense then. If it doesn't work out, they can always be removed again anyway.

For boolean performance in general, I think it would make sense to make the topology cleanup and de-triangulation optional. For many procedural workflows this shouldn't be necessary, and I could foresee it taking a significant portion of the overall runtime.

I think it makes sense to pursue using the manifold library. Ideally the performance will be very good and we will be satisfied there. And ideally it could replace the existing exact solver. Adding library and its dependencies makes sense then. If it doesn't work out, they can always be removed again anyway. For boolean performance in general, I think it would make sense to make the topology cleanup and de-triangulation optional. For many procedural workflows this shouldn't be necessary, and I could foresee it taking a significant portion of the overall runtime.

Jacques Lucke commented 2024-04-15 20:28:50 +02:00

Member

Copy Link

I think it would be good to talk a bit more about the different use-cases of mesh boolean solvers. Then we can check which solvers work well for certain types of work. This approach also makes it easier to tell users which solvers they should use.

Currently, I can think of these main use-cases, but I might be missing some stuff:

1. Fixing models: The user starts out with a fairly broken model that might not be a closed volume and wants to make it ready for e.g. 3D printing. An boolean algorithm for this case should be quite forgiving when the input mesh is bad. However, it's also fine if the algorithm isn't super fast, because it generally only has to be done once for a mesh.
2. Mesh modelling where the output topology matters. This kind of algorithm could potentially make more assumptions about the input meshes, but it sometimes has to trade-off performance for a better output topology that users can continue to work on.
3. Mesh modelling where the output topology does not matter. I think in many procedural setups, the exact output topology does not matter too much and users don't really expect a clean topology. Here one can also make more assumptions about the input meshes. This should be suitable for high performance CSG modelling. As such it should probably also be able to deal with coplanar faces.

Am I missing something important? Which solver would you use for each of these tasks?

I think it would be good to talk a bit more about the different use-cases of mesh boolean solvers. Then we can check which solvers work well for certain types of work. This approach also makes it easier to tell users which solvers they should use. Currently, I can think of these main use-cases, but I might be missing some stuff: 1. Fixing models: The user starts out with a fairly broken model that might not be a closed volume and wants to make it ready for e.g. 3D printing. An boolean algorithm for this case should be quite forgiving when the input mesh is bad. However, it's also fine if the algorithm isn't super fast, because it generally only has to be done once for a mesh. 2. Mesh modelling where the output topology matters. This kind of algorithm could potentially make more assumptions about the input meshes, but it sometimes has to trade-off performance for a better output topology that users can continue to work on. 3. Mesh modelling where the output topology does not matter. I think in many procedural setups, the exact output topology does not matter too much and users don't really expect a clean topology. Here one can also make more assumptions about the input meshes. This should be suitable for high performance [CSG modelling](https://en.wikipedia.org/wiki/Constructive_solid_geometry). As such it should probably also be able to deal with coplanar faces. Am I missing something important? Which solver would you use for each of these tasks?

Howard Trickey commented 2024-04-16 00:33:37 +02:00

Author

Member

Copy Link

I don't think any of our current or proposed Boolean solvers are good for your use case 1 (fixing broken models). But there is an aspect to the question: if you have a broken model, which solver is more likely to give what people think a boolean operation should do on those models. This usually means falling back on ray tracing to discover insideness-outsideness, but there is a bit of an art to doing that. I would say it is a tossup right now whether the current float solver or the current exact solver is better here.

For use case 2, either the current exact solver or the manifold solver would be best IMO. The float solver sometimes works for this case but is unreliable -- sometimes the output will be utterly wrong. But I will note that within case 2 there are still many users who are very unsatisfied with the speed of the current exact solver.

Case 3 seems to be mostly about sculpting, but I case could also apply to cases where the resulting geometry is just rendered as is, using some kind of texturing that doesn't care about topololgy.

There is also the question of: is attribute propagation from input to output important? LIke untriangulating, that also slows things down and may not be needed by some users.

Should I start a user feedback thread on devtalk to ask about their requirements/desiderata for boolean solvers?

I don't think any of our current or proposed Boolean solvers are good for your use case 1 (fixing broken models). But there is an aspect to the question: if you have a broken model, which solver is more likely to give what people _think_ a boolean operation should do on those models. This usually means falling back on ray tracing to discover insideness-outsideness, but there is a bit of an art to doing that. I would say it is a tossup right now whether the current float solver or the current exact solver is better here. For use case 2, either the current exact solver or the manifold solver would be best IMO. The float solver sometimes works for this case but is unreliable -- sometimes the output will be utterly wrong. But I will note that within case 2 there are still many users who are very unsatisfied with the speed of the current exact solver. Case 3 seems to be mostly about sculpting, but I case could also apply to cases where the resulting geometry is just rendered as is, using some kind of texturing that doesn't care about topololgy. There is also the question of: is attribute propagation from input to output important? LIke untriangulating, that also slows things down and may not be needed by some users. Should I start a user feedback thread on devtalk to ask about their requirements/desiderata for boolean solvers?

Jacques Lucke commented 2024-04-16 10:13:25 +02:00

Member

Copy Link

Thanks.

There is also the question of: is attribute propagation from input to output important?

It definitely is in general, i.e. the code should support it. Currently, one can generally assume that nodes in geometry nodes propagate all attributes and I think the same will be true for boolean operations. However, we also give users tools to avoid propagating attributes: named attributes can be removed before the boolean node and anonymous attributes are detected whether they need to be propagated automatically.

I think a general "don't propagate attributes" checkbox in the boolean node is way to inflexible. What could help is to provide additional information in the timing overlay. We could explicitly show how long the attribute propagation takes so that it is more obvious to the user that it might make sense to optimize this part.

Should I start a user feedback thread on devtalk to ask about their requirements/desiderata for boolean solvers?

Might be useful to get a better understanding of what trade-offs we can make to get better performance. I'd assume that generally performance gets worse in the following cases:

• The output should have good topology.
• Bad input meshes should be handled gracefully.
• Robust handling of coplanar faces.

It would also be useful to know if people often only use one boolean operation or whether they usually use multiple chained operations. For the latter case we should figure out a way to keep the mesh data in a boolean solver friendly data-structure for longer instead of converting back and forth for each operation.

---

Overall, I think the Manifold library seems to be a good fit for procedural workflows, probably better than the other solvers we have already. Are there functional benefits of using Ember over Manifold? Does Manifold handle coplanar faces as well as Ember? How does Ember decide what's inside when the input is not a closed volume?

Thanks. > There is also the question of: is attribute propagation from input to output important? It definitely is in general, i.e. the code should support it. Currently, one can generally assume that nodes in geometry nodes propagate all attributes and I think the same will be true for boolean operations. However, we also give users tools to avoid propagating attributes: named attributes can be removed before the boolean node and anonymous attributes are detected whether they need to be propagated automatically. I think a general "don't propagate attributes" checkbox in the boolean node is way to inflexible. What could help is to provide additional information in the timing overlay. We could explicitly show how long the attribute propagation takes so that it is more obvious to the user that it might make sense to optimize this part. > Should I start a user feedback thread on devtalk to ask about their requirements/desiderata for boolean solvers? Might be useful to get a better understanding of what trade-offs we can make to get better performance. I'd assume that generally performance gets worse in the following cases: * The output should have good topology. * Bad input meshes should be handled gracefully. * Robust handling of coplanar faces. It would also be useful to know if people often only use one boolean operation or whether they usually use multiple chained operations. For the latter case we should figure out a way to keep the mesh data in a boolean solver friendly data-structure for longer instead of converting back and forth for each operation. ------ Overall, I think the Manifold library seems to be a good fit for procedural workflows, probably better than the other solvers we have already. Are there functional benefits of using Ember over Manifold? Does Manifold handle coplanar faces as well as Ember? How does Ember decide what's inside when the input is not a closed volume?

Nika Kutsniashvili commented 2024-04-16 11:43:46 +02:00

Contributor

Copy Link

Just wanted to mention that in my professional work I deal with insane amount of boolean operations. I prepare stop-motion puppet replacement parts for 3D printing and sometimes do multiple boolean operators on 50-100+ objects in a day. I also use booleans for sculpting. I would be happy to test in my workflow whatever library needs to be tested

Just wanted to mention that in my professional work I deal with insane amount of boolean operations. I prepare stop-motion puppet replacement parts for 3D printing and sometimes do multiple boolean operators on 50-100+ objects in a day. I also use booleans for sculpting. I would be happy to test in my workflow whatever library needs to be tested

Howard Trickey commented 2024-04-16 19:02:00 +02:00

Author

Member

Copy Link

I'll answer Jacques' questions later, but Nika: would you like to explain your particular requirements on boolean here? Do you care about the output topology (do you care if they are all triangles?). Do you care about reliability in cases where one edge of one part exactly intersects an edge or vertex of another part? Do you care about handling coplanar intersections properly? How large are your models typically? Do your booleans typically have only two operands or many operands? Do you chain many booleans together? How fast, ideally, do you need boolean to run?

I'll answer Jacques' questions later, but Nika: would you like to explain your particular requirements on boolean here? Do you care about the output topology (do you care if they are all triangles?). Do you care about reliability in cases where one edge of one part exactly intersects an edge or vertex of another part? Do you care about handling coplanar intersections properly? How large are your models typically? Do your booleans typically have only two operands or many operands? Do you chain many booleans together? How fast, ideally, do you need boolean to run?

Nika Kutsniashvili commented 2024-04-16 19:14:20 +02:00

Contributor

Copy Link

Do you care about the output topology (do you care if they are all triangles?)

I don't think so. Nowadays 3D printers can print almost any topology. Sometimes we do get some weirdness, but it's all fixable. Sometimes I even run Decimate on models but they still print fine. What is hard requirement for us is that silhouette of the object isn't changed and object is watertight. Judging by the name only Manifold might help here.

Do you care about reliability in cases where one edge of one part exactly intersects an edge or vertex of another part? Do you care about handling coplanar intersections properly?

I'm not sure I fully understand that, but because my models are typically 300,000+ polygons, and there are lot of intersections (also because they're tiny), so in many cases where I run booleans there are lot of vertices and edges that are intersecting or very close to each other. Sometimes I use "Merge by Distance" to reduce the number, and it can take out even 30,000k vertices that are close to each other. It's important for me that boolean can handle that and doesn't need merge beforehand. For example, I had mustache and head as separate objects, and before printing I was using union boolean to combine them, and in at least 2/3 of cases I had to run "Merge by Distance" on head object because otherwise boolean would screw up.

How large are your models typically?

Our models are 30-50 mm, but sometimes we don't follow real-life scale in Blender, because it's harder to work on smaller sizes and we scale them up to meters, and then rescale them in 3D printing software.

Do your booleans typically have only two operands or many operands? Do you chain many booleans together?

I use Bool Tools automatic option, which adds boolean and immediatelly applies it. So even though I use multiple booleans on single objects, they're never chained in a sense that I never have all modifiers at the same time.

So that answers your last question as well, speed is the most important requirement for me besides it just preserving mesh well. I've had workdays where I had to spend 4+ hours just doing booleans, and when each operation takes 10+ seconds on 500,000 poly mesh it's quite daunting.

> Do you care about the output topology (do you care if they are all triangles?) I don't think so. Nowadays 3D printers can print almost any topology. Sometimes we do get some weirdness, but it's all fixable. Sometimes I even run Decimate on models but they still print fine. What is hard requirement for us is that silhouette of the object isn't changed and object is watertight. Judging by the name only Manifold might help here. > Do you care about reliability in cases where one edge of one part exactly intersects an edge or vertex of another part? Do you care about handling coplanar intersections properly? I'm not sure I fully understand that, but because my models are typically 300,000+ polygons, and there are lot of intersections (also because they're tiny), so in many cases where I run booleans there are lot of vertices and edges that are intersecting or very close to each other. Sometimes I use "Merge by Distance" to reduce the number, and it can take out even 30,000k vertices that are close to each other. It's important for me that boolean can handle that and doesn't need merge beforehand. For example, I had mustache and head as separate objects, and before printing I was using union boolean to combine them, and in at least 2/3 of cases I had to run "Merge by Distance" on head object because otherwise boolean would screw up. > How large are your models typically? Our models are 30-50 mm, but sometimes we don't follow real-life scale in Blender, because it's harder to work on smaller sizes and we scale them up to meters, and then rescale them in 3D printing software. > Do your booleans typically have only two operands or many operands? Do you chain many booleans together? I use Bool Tools automatic option, which adds boolean and immediatelly applies it. So even though I use multiple booleans on single objects, they're never chained in a sense that I never have all modifiers at the same time. So that answers your last question as well, speed is the most important requirement for me besides it just preserving mesh well. I've had workdays where I had to spend 4+ hours just doing booleans, and when each operation takes 10+ seconds on 500,000 poly mesh it's quite daunting.

Howard Trickey commented 2024-04-16 19:21:36 +02:00

Author

Member

Copy Link

Niki,

Thanks for your response.

By "how large", I meant "how many polygons", but you answered that already.

Can I assume you are currently using the "Float" solver in the modifier? (I don't know if Bool Tool always uses Float, or if there is an option). With models that large, the 'Exact' solver must be too slow by far. But that would be why you have to fiddle with merging so often in order to not have boolean "screw up".

While I understand that you use Bool Tool and thus do one boolean at a time, if there were a way to do multiple booleans at a time, about how many total operands would there be in your typical use?

Niki, Thanks for your response. By "how large", I meant "how many polygons", but you answered that already. Can I assume you are currently using the "Float" solver in the modifier? (I don't know if Bool Tool always uses Float, or if there is an option). With models that large, the 'Exact' solver must be too slow by far. But that would be why you have to fiddle with merging so often in order to not have boolean "screw up". While I understand that you use Bool Tool and thus do one boolean at a time, if there were a way to do multiple booleans at a time, about how many total operands would there be in your typical use?

Nika Kutsniashvili commented 2024-04-16 19:26:33 +02:00

Contributor

Copy Link

Mostly I use Exact, because even though it's slower, it's most important that it looks the best. Objects we print are gonna be shot in close-ups and shown on large screens, so they have to look best. Sometimes there are cases where Float also can do the job, but problem is if I spend time checking Float, seeing if it works, and if it doesn't then undoing and redoing with Exact, I spend more time than if I do all Exacts.

That reminds me that undo speed is biggest performance hit in my workflow. Because every time Exact solver fails and I have to adjust my mesh and redo Blender freezes on undo and triples waiting time.

While I understand that you use Bool Tool and thus do one boolean at a time, if there were a way to do multiple booleans at a time, about how many total operands would there be in your typical use?

Either 3 or 4 operands on each object.

Mostly I use Exact, because even though it's slower, it's most important that it looks the best. Objects we print are gonna be shot in close-ups and shown on large screens, so they have to look best. Sometimes there are cases where Float also can do the job, but problem is if I spend time checking Float, seeing if it works, and if it doesn't then undoing and redoing with Exact, I spend more time than if I do all Exacts. That reminds me that undo speed is biggest performance hit in my workflow. Because every time Exact solver fails and I have to adjust my mesh and redo Blender freezes on undo and triples waiting time. > While I understand that you use Bool Tool and thus do one boolean at a time, if there were a way to do multiple booleans at a time, about how many total operands would there be in your typical use? Either 3 or 4 operands on each object.

Sean Kim commented 2024-04-16 19:28:47 +02:00

Member

Copy Link

From the sculpting side of things, this comment and others in the issue may be helpful in gathering some requirements / desired features, though it also concerns more specific Trim functionality that isn't necessarily relevant to the boolean solver itself.

From the sculpting side of things, [this comment](https://projects.blender.org/blender/blender/issues/84229#issuecomment-896500) and others in the issue may be helpful in gathering some requirements / desired features, though it also concerns more specific Trim functionality that isn't necessarily relevant to the boolean solver itself.

Howard Trickey commented 2024-04-16 21:00:21 +02:00

Author

Member

Copy Link

Answering Jacques' earlier questions:

Overall, I think the Manifold library seems to be a good fit for procedural workflows, probably better than the other solvers we have already. Are there functional benefits of using Ember over Manifold? Does Manifold handle coplanar faces as well as Ember? How does Ember decide what's inside when the input is not a closed volume?

Ember is an exact solver that handles special cases such as coplanar faces, edges exactly intersecting edges at something other than their endpoints, etc., as one would expect. Manifold is a "robust float solver", where the "robust" means that it will not create topological nonsense. But it does that by taking cases like coplanar faces and edges exactly intersecting edges and perturbing them in the decision process so that the special cases don't happen. This means that it can create zero area faces and the like. There is a cleanup process that does merges and other operations to try to get rid of such things. We need to experiment to see how successful that is in practice. But note that there are several caveats to saying that Ember is exact: first, it is only exact in the space where all vertex positions are converted to 26-bit integers (after scaling the floats to take full advantage of that range, of course). Second, sometimes "exact" doesn't correspond to what users actually want -- for instance, if you rotate a cube by what feels like 90 degrees, maybe the rotation matrix makes the vertex positions slightly away from their exact values if the rotation were perfect; then if you expected a face in that to be coplanar with another mesh's face, you might be disappointed that it creates an almost-zero-area face instead.

Ember, as described in the paper creates a strange output topology compared to Manifold. Ember's faces have t-junctions all over the place. If I continue working on Ember, I will try to fix that problem, which I think Blender users who care about output toplogy would not find very acceptable.

Ember might be faster than Manifold huge models, because it pays more attention to short-circuiting around large parts of models that are unaffected by intersection. But this is just a hypothesis at this point, not proven.

Manifold determines inside-vs-outside via local computations with the entities involved in the intersections, followed by some kind of sort. (Basically, the local computations determine which elements are "shadowed by", and hence "inside" in some sense, which other elements.) It is hard to see how to adapt this to the cases where our current Float and Exact solvers can deal with non-manifold meshes.

One possibility open to us: I take Manifold's code as a starting point, remove its dependencies on clipper, thrust, and glm, and then adapt it to Blender's specific use case, adding optimizations like the short-circuiting of Ember. The big downside of this would be losing (or at least making much harder) any future improvements to Manifold by its author.

Answering Jacques' earlier questions: > Overall, I think the Manifold library seems to be a good fit for procedural workflows, probably better than the other solvers we have already. Are there functional benefits of using Ember over Manifold? Does Manifold handle coplanar faces as well as Ember? How does Ember decide what's inside when the input is not a closed volume? Ember is an exact solver that handles special cases such as coplanar faces, edges exactly intersecting edges at something other than their endpoints, etc., as one would expect. Manifold is a "robust float solver", where the "robust" means that it will not create topological nonsense. But it does that by taking cases like coplanar faces and edges exactly intersecting edges and perturbing them in the decision process so that the special cases don't happen. This means that it can create zero area faces and the like. There is a cleanup process that does merges and other operations to try to get rid of such things. We need to experiment to see how successful that is in practice. But note that there are several caveats to saying that Ember is exact: first, it is only exact in the space where all vertex positions are converted to 26-bit integers (after scaling the floats to take full advantage of that range, of course). Second, sometimes "exact" doesn't correspond to what users actually want -- for instance, if you rotate a cube by what feels like 90 degrees, maybe the rotation matrix makes the vertex positions slightly away from their exact values if the rotation were perfect; then if you expected a face in that to be coplanar with another mesh's face, you might be disappointed that it creates an almost-zero-area face instead. Ember, as described in the paper creates a strange output topology compared to Manifold. Ember's faces have t-junctions all over the place. If I continue working on Ember, I will try to fix that problem, which I think Blender users who care about output toplogy would not find very acceptable. Ember might be faster than Manifold huge models, because it pays more attention to short-circuiting around large parts of models that are unaffected by intersection. But this is just a hypothesis at this point, not proven. Manifold determines inside-vs-outside via local computations with the entities involved in the intersections, followed by some kind of sort. (Basically, the local computations determine which elements are "shadowed by", and hence "inside" in some sense, which other elements.) It is hard to see how to adapt this to the cases where our current Float and Exact solvers can deal with non-manifold meshes. One possibility open to us: I take Manifold's code as a starting point, remove its dependencies on clipper, thrust, and glm, and then adapt it to Blender's specific use case, adding optimizations like the short-circuiting of Ember. The big downside of this would be losing (or at least making much harder) any future improvements to Manifold by its author.

Jacques Lucke commented 2024-04-17 18:38:07 +02:00

Member

Copy Link

I'm not sure how much effort it would be, but I'd really like to see a prototype with Manifold where one can chain multiple mesh boolean nodes and everything is evaluated as efficiently as possible, i.e. no unnecessary data structure conversions and attribute propagations (I'm fine with using a hacky approach to implement this). If that feels fast enough, it may be good to work towards properly implementing it. Otherwise, we might have to hope that Ember can feel fast enough in this situation. I can't really put numbers on what "fast enough" means yet unfortunately.. Right now it just too often feels slow when one would expect things to be real-time still.

I'm not sure how much effort it would be, but I'd really like to see a prototype with Manifold where one can chain multiple mesh boolean nodes and everything is evaluated as efficiently as possible, i.e. no unnecessary data structure conversions and attribute propagations (I'm fine with using a hacky approach to implement this). If that feels fast enough, it may be good to work towards properly implementing it. Otherwise, we might have to hope that Ember can feel fast enough in this situation. I can't really put numbers on what "fast enough" means yet unfortunately.. Right now it just too often feels slow when one would expect things to be real-time still.

Howard Trickey commented 2024-04-17 19:59:42 +02:00

Author

Member

Copy Link

I can see what I can do. Interestingly, Manifold internally keeps a tree of boolean operations, unevaluated, until one asks for the mesh output.

I did a very rough timing test yesterday (unsatisfactory mixture of Debug and Release code) that leads me to believe that Manifold will likely be about the same, or maybe somewhat faster, than our current Float solver. Which is much better than current Exact, but still not where I'd like it to be (Sean was ready to investigate improving the Float solver for sculpting as it was still sometimes too slow there).

To do the prototype you talk about, I can see several approaches:

1. Make a cache property of Mesh runtime that holds the internal manifold, or something like it, and not evaluate the manifold until some Geometry input really wants to suck up the realized mesh. The boolean node could then use such an cached value input instead of freshly converting input Mesh into manifold.

2. Try to examine the geo node tree and make connected components of boolean operations, and then make a boolean expression tree from that and evaluate it all at once.

Thoughts? Other ideas?

I can see what I can do. Interestingly, Manifold internally keeps a tree of boolean operations, unevaluated, until one asks for the mesh output. I did a very rough timing test yesterday (unsatisfactory mixture of Debug and Release code) that leads me to believe that Manifold will likely be about the same, or maybe somewhat faster, than our current Float solver. Which is much better than current Exact, but still not where I'd like it to be (Sean was ready to investigate improving the Float solver for sculpting as it was still sometimes too slow there). To do the prototype you talk about, I can see several approaches: 1. Make a cache property of Mesh runtime that holds the internal manifold, or something like it, and not evaluate the manifold until some Geometry input really wants to suck up the realized mesh. The boolean node could then use such an cached value input instead of freshly converting input Mesh into manifold. 2. Try to examine the geo node tree and make connected components of boolean operations, and then make a boolean expression tree from that and evaluate it all at once. Thoughts? Other ideas?

Howard Trickey commented 2024-04-18 03:19:41 +02:00

Author

Member

Copy Link

Here are some timings for a Release build on my Macbook Pro M3 Max (12 performance cores, 4 efficiency cores):

For a sphere-sphere difference where sphere1 has 200k faces (400k triangles) and sphere2 has 500k face (1 M triangles):

exact: 1281 ms
float: 422 ms
manifold: 327 ms. (triangle output for now; the other two have quad output except in the actual intersection areas)

Here are some timings for a Release build on my Macbook Pro M3 Max (12 performance cores, 4 efficiency cores): For a sphere-sphere difference where sphere1 has 200k faces (400k triangles) and sphere2 has 500k face (1 M triangles): exact: 1281 ms float: 422 ms manifold: 327 ms. (triangle output for now; the other two have quad output except in the actual intersection areas)

👍 2

Bastien Montagne commented 2024-04-18 09:41:33 +02:00

Owner

Copy Link

Regarding how to integrate manifold for prototyping work (and making builds on the buildbot for people to try it out once ready enough), an idea would be to put it and its dependencies into the extern/ of the wip branch for the time being. Then if we decide it's worth it and when it's ready for main, we can properly add the libraries to our pre-compiled repository instead.

Regarding how to integrate manifold for prototyping work (and making builds on the buildbot for people to try it out once ready enough), an idea would be to put it and its dependencies into the `extern/` of the wip branch for the time being. Then if we decide it's worth it and when it's ready for main, we can properly add the libraries to our pre-compiled repository instead.

Howard Trickey commented 2024-04-18 12:46:17 +02:00

Author

Member

Copy Link

I kind of like that idea, Bastien, and think I will try it out. For one thing, it makes it easier for me to experiment with some things without having to involve the platform maintainers (though I thank LazyDodo for his help so far, which has made it possible for me to get this far).

I may even be able to figure out how to remove some, if not all, of the dependencies beyond manifold itself (I think, but have to verify), that clipper and hull are only needed for features that we don't need for 3D Boolean.

I kind of like that idea, Bastien, and think I will try it out. For one thing, it makes it easier for me to experiment with some things without having to involve the platform maintainers (though I thank LazyDodo for his help so far, which has made it possible for me to get this far). I may even be able to figure out how to remove some, if not all, of the dependencies beyond manifold itself (I think, but have to verify), that clipper and hull are only needed for features that we don't need for 3D Boolean.

Emmett-Lalish commented 2024-05-07 17:55:40 +02:00

Contributor

Copy Link

Ember might be faster than Manifold huge models, because it pays more attention to short-circuiting around large parts of models that are unaffected by intersection. But this is just a hypothesis at this point, not proven.

Manifold determines inside-vs-outside via local computations with the entities involved in the intersections, followed by some kind of sort. (Basically, the local computations determine which elements are "shadowed by", and hence "inside" in some sense, which other elements.) It is hard to see how to adapt this to the cases where our current Float and Exact solvers can deal with non-manifold meshes.

One possibility open to us: I take Manifold's code as a starting point, remove its dependencies on clipper, thrust, and glm, and then adapt it to Blender's specific use case, adding optimizations like the short-circuiting of Ember. The big downside of this would be losing (or at least making much harder) any future improvements to Manifold by its author.

Hi all, maintainer of Manifold here - sorry I didn't notice this thread earlier. I don't think you'll gain much by short-circuiting more than Manifold already does. Already almost all of the work is focused on intersection regions. We used to have a short circuit to avoid computing the winding numbers of the non-intersecting verts, but it turned out the parallel computation of winding numbers was so efficient that it was faster than the short circuiting approach.

As for handling non-manifold meshes, all I can say is that may sound nice, but you'll always get some very surprising results. The reason is that fundamentally a Boolean operation is not well-defined for non-closed meshes, so the result will always be heuristic. You can certainly create intersections between any meshes, but deciding which part(s) to keep gets hard, particularly when a mesh only cuts part-way through another.

As to dependencies - clipper and hull should be easy to remove as they are siloed in related files. I tried to keep the library partitioned this way, but we haven't had any users consuming it like that yet, so would be happy to help make that process easier. I don't think you want to remove GLM - it's tiny, header-only, totally open and underpins everything in the library. As for Thrust - it's also header-only and it works just fine on Mac - that's what I develop on and our CI runs on Linux, Mac, and Windows. We don't use any of it's CUDA backend anymore, so really it's just a wrapper for TBB. We're actively looking to replace it with something else, maybe PSTL, but we're waiting for adequate compiler support first.

> Ember might be faster than Manifold huge models, because it pays more attention to short-circuiting around large parts of models that are unaffected by intersection. But this is just a hypothesis at this point, not proven. > > Manifold determines inside-vs-outside via local computations with the entities involved in the intersections, followed by some kind of sort. (Basically, the local computations determine which elements are "shadowed by", and hence "inside" in some sense, which other elements.) It is hard to see how to adapt this to the cases where our current Float and Exact solvers can deal with non-manifold meshes. > > One possibility open to us: I take Manifold's code as a starting point, remove its dependencies on clipper, thrust, and glm, and then adapt it to Blender's specific use case, adding optimizations like the short-circuiting of Ember. The big downside of this would be losing (or at least making much harder) any future improvements to Manifold by its author. Hi all, maintainer of Manifold here - sorry I didn't notice this thread earlier. I don't think you'll gain much by short-circuiting more than Manifold already does. Already almost all of the work is focused on intersection regions. We used to have a short circuit to avoid computing the winding numbers of the non-intersecting verts, but it turned out the parallel computation of winding numbers was so efficient that it was faster than the short circuiting approach. As for handling non-manifold meshes, all I can say is that may sound nice, but you'll always get some very surprising results. The reason is that fundamentally a Boolean operation is not well-defined for non-closed meshes, so the result will always be heuristic. You can certainly create intersections between any meshes, but deciding which part(s) to keep gets hard, particularly when a mesh only cuts part-way through another. As to dependencies - clipper and hull should be easy to remove as they are siloed in related files. I tried to keep the library partitioned this way, but we haven't had any users consuming it like that yet, so would be happy to help make that process easier. I don't think you want to remove GLM - it's tiny, header-only, totally open and underpins everything in the library. As for Thrust - it's also header-only and it works just fine on Mac - that's what I develop on and our CI runs on Linux, Mac, and Windows. We don't use any of it's CUDA backend anymore, so really it's just a wrapper for TBB. We're actively looking to replace it with something else, maybe PSTL, but we're waiting for adequate compiler support first.

Howard Trickey commented 2024-05-07 19:16:45 +02:00

Author

Member

Copy Link

Thanks for the information on your attempts to short circuit. Interesting, and I guess I won't worry about that so much now.

I understand and agree with what you say, but Blender users have gotten used to things usually working when thy use some kinds of non-manifold meshes. And is a little hard to argue with an artist who will look at some non-manifold mesh and say "come on, it is clear to everyone what the result is here". To give three examples

1. Two cubes side-by-side sharing a face (just one!) where they touch. This is non-manifold but to many "it seems clear" that the face that is inside the two cubes is inside, so a self-union should remove that inner face
2. Suzanne, the blender example monkey, subtracting a cube (say) intersecting the back of her head (and coming nowhere near the eyes). Suzanne has holes where the eyes are, and separate spheres for the eyes, so is non-manifold. Yet to a user it is "clear" what part of the back of the head is removed with a part of a cube joining the removed parts.
3. A cube minus a large dihedral shape (a plane bent along some line in it). People expect that the dihedral cuts a roof-shape cut out of the cube.

So I need some fallback or alternative for users to use when things such as these occur. Users will understand that it is caveat emptor whether or not the result is surprising, but know that they usually won't be surprised.

I do have an experimental branch right now where I put manifold's source into blender's "external" folder, copied the distributed source for gsm and thrust into the third_party folder, and commented out about a half a dozen places in the code that depended on clipper2 and hull, so this does get rid of those dependencies. It is a hack at the moment, with hand-done CMake; it would be nice to get this more configurable upstream (the losses in functionality are: convex hull; polygon stuff, and most primitive shapes -- none of these are needed for the Blender Boolean application.

Thanks for the information on your attempts to short circuit. Interesting, and I guess I won't worry about that so much now. I understand and agree with what you say, but Blender users have gotten used to things _usually_ working when thy use some kinds of non-manifold meshes. And is a little hard to argue with an artist who will look at some non-manifold mesh and say "come on, it is clear to everyone what the result is here". To give three examples 1) Two cubes side-by-side sharing a face (just one!) where they touch. This is non-manifold but to many "it seems clear" that the face that is inside the two cubes is inside, so a self-union should remove that inner face 2) Suzanne, the blender example monkey, subtracting a cube (say) intersecting the back of her head (and coming nowhere near the eyes). Suzanne has holes where the eyes are, and separate spheres for the eyes, so is non-manifold. Yet to a user it is "clear" what part of the back of the head is removed with a part of a cube joining the removed parts. 3) A cube minus a large dihedral shape (a plane bent along some line in it). People expect that the dihedral cuts a roof-shape cut out of the cube. So I need some fallback or alternative for users to use when things such as these occur. Users will understand that it is caveat emptor whether or not the result is surprising, but know that they usually won't be surprised. I do have an experimental branch right now where I put manifold's source into blender's "external" folder, copied the distributed source for gsm and thrust into the third_party folder, and commented out about a half a dozen places in the code that depended on clipper2 and hull, so this does get rid of those dependencies. It is a hack at the moment, with hand-done CMake; it would be nice to get this more configurable upstream (the losses in functionality are: convex hull; polygon stuff, and most primitive shapes -- none of these are needed for the Blender Boolean application.

Rob-Blair commented 2024-05-08 05:43:18 +02:00

Copy Link

A robust "Make Manifold" would have value even outside of boolean. Maybe something like this
robust inside outside segmentation could be utilized to manifold the mesh prior to Manifold Boolean?

Some thoughts on EMBER:

• The classify functions only needs to determine +, - or 0. Carry a max calculated epsilon through the operations (probably with a class) and run a quick estimate (32 bit?) for an initial classify. Only estimates that are within the calculated epsilon distance from zero need to be rerun with exact numbers (256 bit) for the possible 0 result.
• Can the dicing of the meshsoup by the AABBs be avoided (fig 26-f on the EMBER paper shows extra seemingly unnecessary geometry)? Instead put copies of the overlapping polygons in each subproblem for WNTV and intersection concerns. Only new geometry and associated meshes get revised from the original mesh

Thank you Blender and Howard for this incredible effort that I get to see happen

A robust "Make Manifold" would have value even outside of boolean. Maybe something like this [robust inside outside segmentation](https://igl.ethz.ch/projects/winding-number/robust-inside-outside-segmentation-using-generalized-winding-numbers-siggraph-2013-jacobson-et-al.pdf) could be utilized to manifold the mesh prior to Manifold Boolean? Some thoughts on EMBER: - The classify functions only needs to determine +, - or 0. Carry a max calculated epsilon through the operations (probably with a class) and run a quick estimate (32 bit?) for an initial classify. Only estimates that are within the calculated epsilon distance from zero need to be rerun with exact numbers (256 bit) for the possible 0 result. - Can the dicing of the meshsoup by the AABBs be avoided (fig 26-f on the EMBER paper shows extra seemingly unnecessary geometry)? Instead put copies of the overlapping polygons in each subproblem for WNTV and intersection concerns. Only new geometry and associated meshes get revised from the original mesh Thank you Blender and Howard for this incredible effort that I get to see happen

Emmett-Lalish commented 2024-05-08 18:11:21 +02:00

Contributor

Copy Link

1. Two cubes side-by-side sharing a face (just one!) where they touch. This is non-manifold but to many "it seems clear" that the face that is inside the two cubes is inside, so a self-union should remove that inner face

Manifold will properly handle unioning two cubes with coplanar faces, but if the mesh has an extra face inside already, that will be a problem. Also, Manifold has no concept of a "self-union" (remove self-intersections). I am working on that, but it's novel research, so no promises.

2. Suzanne, the blender example monkey, subtracting a cube (say) intersecting the back of her head (and coming nowhere near the eyes). Suzanne has holes where the eyes are, and separate spheres for the eyes, so is non-manifold. Yet to a user it is "clear" what part of the back of the head is removed with a part of a cube joining the removed parts.

Fair, but Manifold doesn't deal in heuristics. I would recommend an alternative: fill all mesh holes with simple, arbitrary fans of triangles to create a Manifold, and mark these faces with a special OriginalID. Perform the Boolean op, then remove the triangles with that ID. Now the heuristic is on your side of the code (hole filling) and in cases when it doesn't work well, likely those would also be unclear cases for even a heuristic Boolean anyway. This should be robust, as Manifold is robust to self-intersected geometry.

3. A cube minus a large dihedral shape (a plane bent along some line in it). People expect that the dihedral cuts a roof-shape cut out of the cube.

This can be handled by extruding the shape beyond the bounding box of the object it is operating on. This is how Manifold does TrimByPlane() - the plane is automatically turned into a sufficiently large cube.

A robust "Make Manifold" would have value even outside of boolean. Maybe something like this
robust inside outside segmentation could be utilized to manifold the mesh prior to Manifold Boolean?

Yes, this has a lot of value - Netfabb made a whole business out of this a decade ago. I remember their founder said to me "well, if the mesh is too terrible, I can always just give you back a cube - that'll be manifold at least". The hard part is protecting the desirable parts of the mesh, since it's entirely heuristic.

> 1) Two cubes side-by-side sharing a face (just one!) where they touch. This is non-manifold but to many "it seems clear" that the face that is inside the two cubes is inside, so a self-union should remove that inner face Manifold will properly handle unioning two cubes with coplanar faces, but if the mesh has an extra face inside already, that will be a problem. Also, Manifold has no concept of a "self-union" (remove self-intersections). I am working on that, but it's novel research, so no promises. > 2) Suzanne, the blender example monkey, subtracting a cube (say) intersecting the back of her head (and coming nowhere near the eyes). Suzanne has holes where the eyes are, and separate spheres for the eyes, so is non-manifold. Yet to a user it is "clear" what part of the back of the head is removed with a part of a cube joining the removed parts. Fair, but Manifold doesn't deal in heuristics. I would recommend an alternative: fill all mesh holes with simple, arbitrary fans of triangles to create a Manifold, and mark these faces with a special OriginalID. Perform the Boolean op, then remove the triangles with that ID. Now the heuristic is on your side of the code (hole filling) and in cases when it doesn't work well, likely those would also be unclear cases for even a heuristic Boolean anyway. This should be robust, as Manifold is robust to self-intersected geometry. > 3) A cube minus a large dihedral shape (a plane bent along some line in it). People expect that the dihedral cuts a roof-shape cut out of the cube. This can be handled by extruding the shape beyond the bounding box of the object it is operating on. This is how Manifold does TrimByPlane() - the plane is automatically turned into a sufficiently large cube. >A robust "Make Manifold" would have value even outside of boolean. Maybe something like this robust inside outside segmentation could be utilized to manifold the mesh prior to Manifold Boolean? Yes, this has a lot of value - Netfabb made a whole business out of this a decade ago. I remember their founder said to me "well, if the mesh is too terrible, I can always just give you back a cube - that'll be manifold at least". The hard part is protecting the desirable parts of the mesh, since it's entirely heuristic.

Sign in to join this conversation.

No Branch/Tag Specified

Branches Tags

main

universal-scene-description

brush-assets-project

blender-v3.3-release

blender-v3.6-release

partial-write-refactor

blender-v4.1-release

blender-v3.6-temp_wmoss_animrig_public

temp-sculpt-dyntopo

gpencil-next

anim/animation-id-113594

blender-v4.0-release

blender-projects-basics

bridge-curves

sculpt-blender

asset-browser-frontend-split

asset-shelf

tmp-usd-python-mtl

tmp-usd-3.6

blender-v3.5-release

blender-v2.93-release

realtime-clock

sculpt-dev

bevelv2

xr-dev

v4.1.1

v3.6.11

v3.3.18

v4.1.0

v3.3.17

v3.6.10

v3.6.9

v3.3.16

v3.6.8

v3.6.7

v3.3.14

v4.0.2

v4.0.1

v4.0.0

v3.6.5

v3.3.12

v3.6.4

v3.6.3

v3.3.11

v3.6.2

v3.3.10

v3.6.1

v3.3.9

v3.6.0

v3.3.8

v3.3.7

v2.93.18

v3.5.1

v3.3.6

v2.93.17

v3.5.0

v2.93.16

v3.3.5

v3.3.4

v2.93.15

v2.93.14

v3.3.3

v2.93.13

v2.93.12

v3.4.1

v3.3.2

v3.4.0

v3.3.1

v2.93.11

v3.3.0

v3.2.2

v2.93.10

v3.2.1

v3.2.0

v2.83.20

v2.93.9

v3.1.2

v3.1.1

v3.1.0

v2.83.19

v2.93.8

v3.0.1

v2.93.7

v3.0.0

v2.93.6

v2.93.5

v2.83.18

v2.93.4

v2.93.3

v2.83.17

v2.93.2

v2.93.1

v2.83.16

v2.93.0

v2.83.15

v2.83.14

v2.83.13

v2.92.0

v2.83.12

v2.91.2

v2.83.10

v2.91.0

v2.83.9

v2.83.8

v2.83.7

v2.90.1

v2.83.6.1

v2.83.6

v2.90.0

v2.83.5

v2.83.4

v2.83.3

v2.83.2

v2.83.1

v2.83

v2.82a

v2.82

v2.81a

v2.81

v2.80

v2.80-rc3

v2.80-rc2

v2.80-rc1

v2.79b

v2.79a

v2.79

v2.79-rc2

v2.79-rc1

v2.78c

v2.78b

v2.78a

v2.78

v2.78-rc2

v2.78-rc1

v2.77a

v2.77

v2.77-rc2

v2.77-rc1

v2.76b

v2.76a

v2.76

v2.76-rc3

v2.76-rc2

v2.76-rc1

v2.75a

v2.75

v2.75-rc2

v2.75-rc1

v2.74

v2.74-rc4

v2.74-rc3

v2.74-rc2

v2.74-rc1

v2.73a

v2.73

v2.73-rc1

v2.72b

2.72b

v2.72a

v2.72

v2.72-rc1

v2.71

v2.71-rc2

v2.71-rc1

v2.70a

v2.70

v2.70-rc2

v2.70-rc

v2.69

v2.68a

v2.68

v2.67b

v2.67a

v2.67

v2.66a

v2.66

v2.65a

v2.65

v2.64a

v2.64

v2.63a

v2.63

v2.61

v2.60a

v2.60

v2.59

v2.58a

v2.58

v2.57b

v2.57a

v2.57

v2.56a

v2.56

v2.55

v2.54

v2.53

v2.52

v2.51

v2.50

v2.49b

v2.49a

v2.49

v2.48a

v2.48

v2.47

v2.46

v2.45

v2.44

v2.43

v2.42a

v2.42

v2.41

v2.40

v2.37a

v2.37

v2.36

v2.35a

v2.35

v2.34

v2.33a

v2.33

v2.32

v2.31a

v2.31

v2.30

v2.28c

v2.28a

v2.28

v2.27

v2.26

v2.25

Labels

Clear labels   

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

This issue affects/is about backward or forward 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

Issues relating to Wayland windowing support.

  

Interest

Workbench

  

Interest: X11

Issues relating to Xorg/X11 support.

  

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

Issues relating to security: https://wiki.blender.org/wiki/Process/Vulnerability_Reports

  

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

Milestone

Clear milestone

No items

No Milestone

4.2 LTS

Projects

Clear projects

No project

Assignees

Clear assignees

No Assignees

Howard Trickey

8 Participants

Notifications

Subscribe

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#120182

No description provided.