Page MenuHome

This diff is for the newboolean branch
ClosedPublic

Authored by Howard Trickey (howardt) on Aug 19 2020, 10:43 AM.

Diff Detail

Repository
rB Blender

Event Timeline

I need to write an overall documentation of the design to make this code easier to follow. I had started at https://wiki.blender.org/wiki/User:Howardt/Boolean but now that is completely out of date - it refers to an earlier version that I abandoned.

For now, you might want to skim:
“Mesh Arrangements for Solid Geometry”, by Zhou, Grinspun, Zorin, Jacobson. Siggraph 2016 - http://www.cs.columbia.edu/cg/mesh-arrangements/mesh-arrangements-for-solid-geometry-siggraph-2016-zhou-et-al.pdf
for an idea of what is going on in boolean.cc.

Testing

From examples files linked form T47030, testing this gives great results.

I've read over the logic (as well as stepping over in a debugger), and I don't have any concerns about how this works (some minor points noted inline).

  • There was one file I tested that has many overlapping shards (created by cell-fracture or similar tool) that causes "Exact" boolean to take a long time to finish (while it does complete, it runs for over 8min on release release builds), for debug builds I get an error from ASAN, see: P1589

    The test file is part of T47110 report (enable "Exact" for test file F8793432).

UI

  • Instead of an "Exact" toggle, it might be best to present this as an enum, then the tool-tips can expand on the behavior of each.
  • Threshold should be hidden when "Exact" is disabled as it's not used.

Inclusion in BLI

  • Note that this adds quite a bit of specialized code into "BLI" which internally is defining local bounding-box types for example, which are only used for booleans.

    I think this might make more sense to be moved into a more top-level module ./source/blender/boolean for example, with more generic wrappers such as mpq2,3 remaining in BLI.

    If there is a reason not to do this, other smaller changes could be made, noted next.
  • Naming BLI_boolean could be made mesh specific, suggest BLI_mesh_boolean ?
  • Naming Mesh in BLI_mesh_intersect.hh seems error prone (even though namespaces make it technically OK) (as naming matches DNA_mesh_types.h).
  • Longer term we could avoid going through DNA_mesh -> BMesh -> BLI_mesh_intersect conversion? go direct from DNA_mesh to BLI_mesh_intersect and back.

    Although geometry from the original bmesh is used in-place when no intersections are made, so it may not be worth it.

Other

  • Some of the C++ aspects of this patch I'm not covering.

    It'd be good to have a developer more with our C++ conventions check over this.
source/blender/blenlib/BLI_double2.hh
105

Using the float version of abs, also shouldn't we use std::abs in C++?

(this applies to other C++ uses of fabs in this patch too).

source/blender/blenlib/BLI_mesh_intersect.hh
192

Regarding Facep & Vertp types, normally we just write them explicitly although I can see why it's done as it saves quite a bit of repetition.
Is this intended to be a local type short-hand? Or something we might use more elsewhere?

202

This could be called MeshArena or MeshDataArena? MArena term isn't obvious what the M stands for.

source/blender/blenlib/intern/delaunay_2d.cc
1437

Blender convention is to have break in the body of the case statement.

source/blender/blenlib/intern/mesh_intersect.cc
340

Short comment to explain why it's not needed would help.

2588–2593

This could be wrapped into a utility since it's done elsewhere, to make declaring the key a one liner.

source/blender/bmesh/tools/bmesh_boolean.cc
122–133

(low priority) this capability could be part of the BMesh API, extend BM_face_exists for example.

286

BM_loop_interp_from_face could be avoided for loops which map to original vertices, since this is a heavy operation that calculates weights for all other loops in the face.

Although this only runs on intersecting faces so it's not that bad.

Also, it's possible this doesn't need to run at all: CustomData_has_interp can be assigned a variable once, then check if there is interpolation to perform before running this on all loops.

Thanks for the review Campbell. I'll address the comments soon.
Meanwhile, Jacques - Campbell asked for someone with more Blender C++ experience to look over the C++ aspects of the code. I know you and Brecht looked once before, but there have been a large number of changes since then. Could you take a look again please?

Let me respond to your overall comments here, inline:

From examples files linked form T47030, testing this gives great results.

Thanks for testing!

I've read over the logic (as well as stepping over in a debugger), and I don't have any concerns about how this works (some minor points noted inline).

There was one file I tested that has many overlapping shards (created by cell-fracture or similar tool) that causes "Exact" boolean to take a long time to finish (while it does complete, it runs for over 8min on release release builds), for debug builds I get an > error from ASAN, see: P1589

This is a case where the inputs are not "PWN" (Piecewise Winding Number - basically, if it is not PWN then it doesn't enclose volumes - there are probably open boundary edges somewhere).
I very recently added code that calculates a "general winding number" (GWN) for cases like this, instead of using much of the logic in boolean.cc that is what the paper prescribes.
A generalized winding number measures the fraction of a sphere's surface around a point that have faces of the target mesh projected upon it. When done is a signed way, and done with
a closed solid target mesh, you get 1 if a point is inside and 0 if it is outside. If the target mesh has holes in it, it gives a fractional answer that can answer fuzzily the inside vs outside question.
It is pretty expensive to calculate, and horrendously expensive if there are a lot of "patches". A patch is a connected set of faces that all are connected by manifold edges, and I have to calculate
the GWN for a point in each patch, with the target mesh being the other side of the boolean operation.
In a normal boolean use case, there are not many patches, so I figured this GWN method would be OK. But the test file you give here has something like 14k patches! Hence the really long time to execute.
I have several choices here:
(1) do nothing and hope this case doesn't come up often; in some sense, it is a bonus that boolean is doing anything at all if the inputs are not closed volumes;
(2) if there are a lot of patches, switch to another method - probably raycasting, as the current BMesh boolean does;
(3) the paper that describes using GWN has a hierarchical method to speed up the computation - I could try implementing that.
Opinions?

As for the ASAN error: thanks for the example. I will have to dig into this and see if I can find the problem. I am fearful that it may be in the GMP code itself, but hopefully not. The stack trace was
unfortunately not illuminating for me, as it seems to indicate that a gmp structure was earlier overwritten by something, and discovered only on destruction of that structure. Ugh.

The test file is part of T47110 report (enable "Exact" for test file F8793432).
T47011: BMesh boolean fails when either meshes are themselves self intersecting is still an issue, mentioning this since IIRC we had users report this more than once. On the other hand, it's a reasonable limitation.

The code has actually been written, though not much tested, to handle Boolean operations with "use_self" enabled. This should solve this problem. I was thinking of exposing this as another option in the modifier,
when in Exact mode.

UI

I was pretty unsure of what to do here, so wasn't doing much until I could get some opinions from you and maybe others on the UI module. Thanks for bringing this up.

Instead of an "Exact" toggle, it might be best to present this as an enum, then the tool-tips can expand on the behavior of each.

Do you mean something like an expanded enum choice, with buttons to choose between "Exact" and "Fast" [or what should the other choice be named? BMesh? Inexact?]
Can I assume you are on board with the general idea of having both the old and the new code selectable by the user for the 2.91 release?
Until the new code is about as fast as the old one (if that can ever happen), it seems like users would like the choice. As I said to someone who
asked about this on the thread, this is a different situation from having both Carve and BMesh boolean, since we had nobody to fix Carve.
And at least some bugs filed against the 'Fast" mode could just be closed with "known issue, use the Exact mode for cases like this".

Threshold should be hidden when "Exact" is disabled as it's not used.

Agreed. I had been intending to do this; was just being lazy. In addition, if I add more options that only work in the Exact mode (e.g., the "use_self" option mentioned above),
then likewise those should only be viewable when Exact is enabled.

There is more functionality that I'd like to add to the modifier eventually, but will hold off until we get what this patch represents agreed upon and into master.
But as a preview: I want to add the 'self' option; I'd like to add knife cut functionality into the modifier; and I'd like to add the ability to work on
multiple object operands at once into the modifier (the new code handles that case, and will be a lot faster than sequentially applying modifiers).
Someone suggested having the "Object" dropdown generalized to take the name of a Collection of objects, as one possible UI.
Another possibility would be a listbox of object names. If we wanted, we could enable this for the Fast code too, synthesizing the effect by running
the binary operand code sequentially, behind the scenes.

Inclusion in BLI
Note that this adds quite a bit of specialized code into "BLI" which internally is defining local bounding-box types for example, which are only used for booleans.
I think this might make more sense to be moved into a more top-level module ./source/blender/boolean for example, with more generic wrappers such as mpq2,3 remaining in BLI.

I would rather not do this, but would not put up a fight if you and others (Brecht, Jacques, ...?) agree that this would be better.
My reasons for preferring leaving them in BLI are:

  1. I was careful to not use anything that wasn't in BLI in the implementation, so from a "level call" perspective, it would be good to emphasize

that with the code layout structure, and prevent people from negating that aspect in the future.
There used to be an additional advantage: the unit tests could be built with only BLI, and thus would build and execute really quickly,
which was great for iterating on development. Unfortunately, that advantage went away with the new philosophy of bundling all the
unit tests into one blender_test binary.

  1. An API that does 2d and 3d intersections and booleans robustly on a more abstract specification of 2d and 3d meshes than the concrete

BMesh and (DNA) Mesh seems a generally useful tool in the BLI toolbox, that new developers should be able to discover and use.
Putting it in its own top-level directory may not signal to people that these are more generically useful APIs.

  1. Building on the previous point, I think we should expose at least the Boolean functionality, and perhaps the Mesh Intersect

functionality, in the Python API. I already did this for a previous implementation of the Constrained Delaunay Triangulation code,
and several developers have told me this was useful.

I agree that the biggest con of putting this stuff in BLI is that there are a lot of types that feel like more general functionality that
should either be separated out and more generally exposed, or hidden even more. I figured that hiding them in the blender::meshintersect
namespace was good enough, but others may disagree.

If there is a reason not to do this, other smaller changes could be made, noted next.
Naming BLI_boolean could be made mesh specific, suggest BLI_mesh_boolean ?

I'm fine with that.

Naming Mesh in BLI_mesh_intersect.hh seems error prone (even though namespaces make it technically OK) (as naming matches DNA_mesh_types.h).

Well, C++ seems pretty good at making this not error prone - the type system would catch any confusion except direct casting, which is unlikely to happen IMO.
But I do understand the point about mental confusion - especially to new developers dipping into the code - and was not very happy with my choice of Mesh
for that reason. Any good suggestions for an alternative? I was using "IMesh" in a previous attempt at newboolean, meaning "Interface Mesh" to me, but this
didn't seem like an Interface Mesh. I could use IMesh with the reimagined meaning of "Intersect Mesh". I could use "IntersectMesh" though that is a little verbose.
Opinions?

Longer term we could avoid going through DNA_mesh -> BMesh -> BLI_mesh_intersect conversion? go direct from DNA_mesh to BLI_mesh_intersect and back.
Although geometry from the original bmesh is used in-place when no intersections are made, so it may not be worth it.

This was always in the back of my mind as one of the motivations to write this independently of BMesh and DNA Mesh (among other reasons).
I don't need the full generality of topology that BMesh calculates, though I do need some limited topology information, as you probably saw in the code.
It seems doable to skip the round trip through BMesh in the modifier code, and we should consider doing so. Though at this point, the profiling I've done
does not show that as a big contributor to the expense of doing Boolean - it is dominated by the exact arithmetic.

Other
Some of the C++ aspects of this patch I'm not covering.
It'd be good to have a developer more with our C++ conventions check over this.

Jacques and Brecht looked at a much earlier version of this code and had minor comments, which I think I've addressed.
It would be good if they look again. But I realize that looking at 10k new lines of code is a big ask. Thank you to everyone who has looked!
I'll add Brecht to this too in case he wants to look again or weigh in on the above questions, especially the one about where in the file structure this code belongs.

Howard Trickey (howardt) retitled this revision from This diff is for the newboolean branch, uploading on behalf of Howard Tricky to This diff is for the newboolean branch.

In a normal boolean use case, there are not many patches, so I figured this GWN method would be OK. But the test file you give here has something like 14k patches! Hence the really long time to execute.
I have several choices here:
(1) do nothing and hope this case doesn't come up often; in some sense, it is a bonus that boolean is doing anything at all if the inputs are not closed volumes;
(2) if there are a lot of patches, switch to another method - probably raycasting, as the current BMesh boolean does;
(3) the paper that describes using GWN has a hierarchical method to speed up the computation - I could try implementing that.
Opinions?

For now 1 seems OK, although boolean with cell-fracture is not such a strange use case - the example linked was quite high poly at 125k triangles. I don't think it's a blocker.

As for the ASAN error: thanks for the example. I will have to dig into this and see if I can find the problem. I am fearful that it may be in the GMP code itself, but hopefully not. The stack trace was
unfortunately not illuminating for me, as it seems to indicate that a gmp structure was earlier overwritten by something, and discovered only on destruction of that structure. Ugh.

Let me know if you can redo, if not, I'll check on this in more detail.

The test file is part of T47110 report (enable "Exact" for test file F8793432).
T47011: BMesh boolean fails when either meshes are themselves self intersecting is still an issue, mentioning this since IIRC we had users report this more than once. On the other hand, it's a reasonable limitation.

Instead of an "Exact" toggle, it might be best to present this as an enum, then the tool-tips can expand on the behavior of each.

Do you mean something like an expanded enum choice, with buttons to choose between "Exact" and "Fast" [or what should the other choice be named? BMesh? Inexact?]

Yes, something like this, from a user perspective terms like "Exact / Fast" names are OK (could use high/low quality, not so fussed).
It just means we can explain the properties of each.

Can I assume you are on board with the general idea of having both the old and the new code selectable by the user for the 2.91 release?

Yes.

Until the new code is about as fast as the old one (if that can ever happen), it seems like users would like the choice.
As I said to someone who asked about this on the thread, this is a different situation from having both Carve and BMesh boolean, since we had nobody to fix Carve.
And at least some bugs filed against the 'Fast" mode could just be closed with "known issue, use the Exact mode for cases like this".

Right. There are issues where edges overlap with faces or other edges that can be fixed - but it wont support exactly overlapping surfaces.
If this is documented as a limitation, I think it's fine to close issues that are solved by "Exact" mode.

build_files/build_environment/cmake/versions.cmake
315

Looks accidental.

I'd prefer BLI_mesh_boolean.hh as well.

The clang-tidy issues should be fixed before the merge. Other than that I haven't found any blocking issues.
In many places you can probably remove static_cast<int>.
Added a couple more comments, but they are low priority and can also be addressed once this is in master.

source/blender/blenlib/BLI_boolean.hh
33 ↗(On Diff #27898)

This might be better:

enum class BoolOpType {
  None = -1,
  Intersect = 0,
  Union = 1,
  Difference = 2,
};

Note that you'll have to use BoolOpType::* to access the values after that change.

55 ↗(On Diff #27898)

Can pm be const? Same for boolean_trimesh and maybe pm_triangulated.
What does the p in pm stand for? poly? A more descriptive name might help.

source/blender/blenlib/BLI_double2.hh
118

Not sure if this belongs here, but we can also just leave it for now.

source/blender/blenlib/BLI_mesh_intersect.hh
137

I think it would be better to remove the copy/move constructors/operators, or to = default them explicitly. Let's not make these types more complex than they need to be.

192

I prefer using const Face * tbh. The repetition does not seem to be too bad.

202

Can derive from NonCopyable and NonMovable instead of deleting the constructors/operators.

source/blender/blenlib/intern/boolean.cc
124 ↗(On Diff #27898)

Might want to use MultiValueMap later. But that is not necessary now, because it does not actually improve performance yet.

Is there a reason why edge_tri_ uses Vector<int> * as key, while vert_edges_ uses Vector<Edge> (instead of Vector<Edge> *)?

I wonder, what does it mean when a triangle contains an edge? Typically only two triangles share an edge, right? A memory optimization could be to use Vector<int, 2> instead of Vector<int>.

238 ↗(On Diff #27898)

Why is there tri() and tris()?

378 ↗(On Diff #27898)

flag_ -> in_output_volume_?

396 ↗(On Diff #27898)

Can be a span? Same below.

631 ↗(On Diff #27898)

Can you iterate over patches directly instead of over indices?

863 ↗(On Diff #27898)

remove newline

893 ↗(On Diff #27898)

Pass Span by value and not by reference.

924 ↗(On Diff #27898)

Can be std::array<Vector<int> *, 4>. Better use std::array when the size is known at compile time.

1015 ↗(On Diff #27898)

Is this static_cast still necessary?

1311 ↗(On Diff #27898)

assert that etris != nullptr

1313 ↗(On Diff #27898)

edge_tris.last() = EXTRA_TRI_INDEX

1468 ↗(On Diff #27898)

Better define operator!= for mpq3.

1952 ↗(On Diff #27898)

Looks like I should finish my Queue implementation.

2016 ↗(On Diff #27898)

That break seems unneccesary.

2049 ↗(On Diff #27898)

out_tris -> r_tris? That's the convention used in most parts of Blender.

2206 ↗(On Diff #27898)

use std::array<*, 3>

2230 ↗(On Diff #27898)

These breaks seem unnecessary.

2331 ↗(On Diff #27898)

That epsilon seems to be quite large, is there a reason for that?

2465 ↗(On Diff #27898)

remove static_cast

2655 ↗(On Diff #27898)

unnecessary parenthesis

source/blender/blenlib/intern/math_vec.cc
279

This makes us vulnerable to the static initialization order fiasco.
Should be fine here for now, but might become a problem in the future.

Are the values computed in exactinit compile time constants? Then maybe we can just put their values in code? Not sure..

879

readability-else-after-return

887

readability-else-after-return

924

readability-function-size

944

readability-function-size

947

I'd really appreciate it, if you would not declare all variables at the top of functions. Better try to reduce the vertical scope of variables.
https://wiki.blender.org/wiki/Style_Guide/C_Cpp#Variable_Scope

1452

readability-function-size

source/blender/blenlib/intern/mesh_intersect.cc
2911

readability-named-parameter

source/blender/blenlib/tests/BLI_boolean_test.cc
18 ↗(On Diff #27898)

Should be in blender::meshintersect::tests namespace.
https://wiki.blender.org/wiki/Style_Guide/C_Cpp#Tests

111 ↗(On Diff #27898)

readability-named-parameter

Same in the lambdas below.

Howard Trickey (howardt) marked 34 inline comments as done and 2 inline comments as done.Aug 22 2020, 2:48 PM
Howard Trickey (howardt) added inline comments.
source/blender/blenlib/BLI_boolean.hh
55 ↗(On Diff #27898)

pm can't be const right now for a stupid reason - so that I could populate vertices in it for debug file dumping. I could fix that by having the vertices get populated somewhere else. But I have a feeling I'm going to have to have this be non-const in the near future so that I can do lazy populating of the plane normals, so I'm not going to change this to const right yet.
pm does stand for polymesh, a bit of a remnant from a time I had separate PolyMesh and TriMesh structures. I'll change the mesh arguments to better names.

source/blender/blenlib/intern/boolean.cc
124 ↗(On Diff #27898)

I'll check out MultiValueMap later then.

I believe I used that type for edge_tri_ because I wanted to use lookup_default(e, nullptr) on that map, and didn't need to on the other one. Maybe not the best reason.

More than two triangles can share an edge: those non-manifold edges are where all the action happens after intersecting two meshes, for instance.

238 ↗(On Diff #27898)

My mistake. Thanks. I removed tri().

1015 ↗(On Diff #27898)

Thanks. I've removed all the ones that were there when sizes were unsigned.

1313 ↗(On Diff #27898)

There seems to be no last() member in Array.

1952 ↗(On Diff #27898)

What advantages will it give over using a Vector? Just curious. I didn't find it bad to use a Vector here.

2331 ↗(On Diff #27898)

This is the sum of as many doubles as there are faces, which can be quite large. There is not a lot of downside to being too big with this number because if the point is inside a closed volume, the answer will be close to 1, and if it is not closed, it will probably still be bigger than 0.5.

source/blender/blenlib/intern/math_vec.cc
279

They are not compile time constants. They depend on the machine that the code is running on.

I believe I understand the static initialization problem, but don't think it applies here because we won't ever do any other static initialization that would call this code (which does exact answers to things like "in_circle" when the arguments are double. I could have put this initialization call in the startup code for Blender, but would also have to do it for unit tests (easier now that they are all in one binary, but who knows about the future). Forgetting to do that seems more dangerous than using this initializer.

879

As discussed in chat, this code comes from Shewchuk's publicly available code - only lightly edited to make it modern C. I'd rather not change it, both to make it easier to reimport the code again some time, and also because it would be hard to test whether or not I'd made a mistake. I'll put in comment magic to stop clang-tidy from complaining about this code.

887

ditto

924

ditto

944

ditto

947

ditto

1452

ditto

source/blender/bmesh/tools/bmesh_boolean.cc
122–133

Will do this after merge.

286

I thought of this, but I think the case where there are all original-mapped vertices is relatively rare, since most cases where that happens will just be caught by the search for an existing face, above. One exception is if some original verts were merged to others but the end result is an existing face after de-aliasing the vertices. I think that is rare. The other exception would be if a new smaller face (e.g., a triangle) is formed from existing verts in a subdivided face. This is maybe not so rare but also seems harder to handle: One has to find and reuse or copy data from Loops in some original face. Possible, but the added complexity to do that seems not worth it to me right now. I hope it is OK to leave this as is for now.

Howard Trickey (howardt) marked 13 inline comments as done and 2 inline comments as done.

This is a diff after addressing the comments of Campbell and Jacques.

source/blender/blenlib/intern/boolean.cc
1952 ↗(On Diff #27898)

Benefits of a specialized queue data structure:

  • No need for a comment that explains that a vector is used as queue.
  • No need for a separate queue_head variable.
  • Requires less memory when the number of elements in the queue is relative low all the time, but the total number of elements pushed to the queue is large.
  • Works for non-trivial data types that should be destructed when they are popped from the queue.
  • Can use queue.push and queue.pop methods which are more self-explanatory (we can also have enqueue and dequeue, but currently I prefer push and pop).

Are we good to go for merging into Master, or do you two want to see more before that?

Went over the branch and made some minor changes/cleanups, I noticed that math_vec.cc has a lot of specialized functionality in it and doesn't fit with math_vector.c, although I'm not sure what makes the most sense in this case, it could even be called, in it's current form mesh_boolean_utils.cc might make more sense, although it could be used elsewhere.

*Edit* as this file doesn't have a header and instead defines math functions for float#, double#, mpq#, we could name it in a way that suggests this. eg BLI_math_vector_generic.cc, for e.g.


Otherwise I think this is fine for master.

This revision is now accepted and ready to land.Aug 27 2020, 10:57 AM
source/blender/blenlib/intern/math_vec.cc
571

should this be significant ?

source/blender/modifiers/intern/MOD_boolean.c
79–83

We could always set eBooleanModifierSolver_Exact as we'll need to load files with exact anyway.

324–328

When exact is set but not available, suggest to show a message that it's not enabled using BKE_modifier_set_error.