Yes, it is a known issue that when the input meshes are not in the expected form for Exact boolean, the output may not be right. Suzanne is non-manifold, as you know.
The “expected form” for meshes is a bit technical but I might as well put it here for posterity: the requirement is that the input meshes be “PWN” which means “piecewise-constant winding number”. The generalized winding number of a point p is (a factor times) the the sum over all triangles in the mesh of the signed solid angle that the triangle makes for point p. You can think of the solid angle as: if you project the triangle onto a sphere surrounding the point, what portion of the sphere is covered by that projection? The generalized winding number is piecewise-constant if in regions of 3-space it stays constant as you move smoothly among all the points in space, except where it crosses triangles. If the faces aren’t all triangles, then any triangulation of the faces can be used to do this calculation.
This is admittedly hard to understand, but you can think of it as approximately:
All edges of faces either are shared with edges of other faces, or butt up against other faces, leaving no gaps.
You can form groups of faces that together completely enclose a 3d volume in a water-tight way: that is, there is an “outside” that is the part of space on the side of faces that the normals point to, and an “inside” that is on the side they don’t point to. There is no path through 3-space that goes from the inside to the outside without penetrating a face or an edge between faces.
An example of a mesh that satisfies this is one where all the edges are manifold (are shared by exactly two faces) and have normals pointing in consistent directions. The mesh primitives that you can Add in Blender mostly are like this (but not Suzanne). However, PWN is more general than this. It allows, for example, two cubes that join on one common edge - that edge is not manifold, but the two cubes still enclose well-defined 3d volumes.
My code checks for PWN inputs, and if they are, then it uses an efficient and exact method to determine what is in the Boolean output and what is not. But if the inputs are not PWN, it tries a different method. Currently, that method is to actually calculate the generalized winding number as defined above for a representative point that we are trying to decide is inside or outside some input mesh. That number will be a fraction, but comparing it to zero gives a decent guess as to whether a point would be regarded by a human as inside or outside a volume-with-gaps. While this works sometimes (e.g., when one mesh is just a plane), unfortunately it hasn’t been working as well as I hoped in all cases. And in addition, it is quite slow to compute. So I’m going to try experimenting with other ways to handle the non-PWN case. But probably not before the 2.91 release.
Hi Howard,
Really liking the new Exact Bools in 2.9.1.
I have a file which is of a manifold tire and a manifold tire tread. I’m trying to subtract the tire tread from the tire with no luck. If you have a moment, can you take a look and let me know if there’s anything that can be done, or it is a too complicated operation. Thanks for any insights you might have
@Howard_Trickey
One possible optimization I found:
Changing the type of the itt_map (in mesh_intersect.cc) to std::unordered_map (and changing the calls accordingly) more than halves the peak memory use in some cases (at least on Windows). It might be worth looking into replacing this hashmap with a better implementation, at least for the booleans.
And a tiny optimization for the struct ITT_value: reordering the members to be in the order kind, t_source, p1, p2 saves 8 bytes per instance on my machine. (208 before, 200 after)
And sort of a request:
I often work with “high-poly” sculpts (around 1M triangles), and in the end I combine then into one piece.
However, the collection booleans always seem to use the Self flag. This causes it to use way more memory and often taking longer, than if I boolean the pieces pairwise without using the Self flag. Often, it even runs out of memory (I have 16 GB of RAM).
I wish the collection booleans could also work without the Self flag, since I don’t see a reason why that should be required.
Thanks for looking at these things. I admit that I have been paying attention to speed optimizations a lot and memory optimizations not at all. I will have to spend time looking at memory usage too.
I am currently looking at some major surgery to the code to improve the speed. It may be that by the time I’m done, the itt_map may be implemented differently anyway (for better parallelism), but I don’t know yet. It is interesting about the size difference. I’ve been trying to use the Blender-defined C++ containers designed by Jacques, and maybe I should have him look at whether the size difference is due to some space / speed tradeoff, or something that he could just change to get better memory usage.
Thanks for pointing out the ITT_kind field order issue. I will fix that.
The reason I always assumed ‘Self’ for the Collection case: because having self turned off makes the code more complicated, and because it seems users sometimes report bugs that are due to them not having Self enabled when they should – for correctness and simpler interface for users it would be nicer if there were no Self flag and it was always assumed. Having the flag and the possibility of turning it off is just an optimization that can allow the code to test fewer intersections. I have special cased the two-operand no-self case, but did not bother special casing the n-operand no-self case. I admit not putting much thought into how to special-case it – it might be easy, so I will look. I think I was thinking that it might be more common for the n operands to mutually intersect pairwise, and that I needed Self on to handle those cases properly, but thinking about it now, that is probably not true. The main reason that having Self on so increases the memory and time is that the bounding-box overlap test to see if two faces intersect will of course find for a face in one operand that all the other adjacent faces in the same operand are potentially intersecting. I can try (and have tried) to exclude those cases from the later tests for intersection, but it is not trivial: think about the case where an adjacent face doubles back over and is coplanar with a given face (of course, I could dictate that with Self off, the user asserts that such cases don’t happen).
What I am currently working on: I am trying to have the modifier skip the step of convert the Mesh data into a BMesh before doing Boolean, and then converting the resulting BMesh back to Mesh. This should save both memory and time. The bare bones of doing this skipping BMesh are easy, and already mostly done. The hard part is making sure all the custom data comes out right - especially shape keys, UVs, custom split normals, and vertex groups.
Update: I committed a change to master to reorder the ITT_value fields.
No idea if this is the right place to mention this, but is the new Exact boolean supposed to give a more or less correct result. Because this is not the first time I’ve noticed where the exact algorithm gives a worse result that the legacy fast one.
I am running into a similar problem as MrTheRich here and I also have an actual usecase for this. Though I am not too sure whether this is a new boolean question or if everything nodes is going to solve this with a version of procedural ‘bisect’.
My concrete problem is this: I am trying to replicate a similar setup to Luan Vetoreti’s learning videos (“Fundamentals of modular Kits”) for modular game assets. He bascially creates a plane template to start off, which he instances and cuts, rotates and merges into modular wall pieces t that the original plane can easily be edited and iterated on. He uses 3DS Max and a version of procedural bisect modifier to cut the pieces.
So trying to replicate this setup in Blender seems only possible with boolean operations so far:
As a game art set solidifying isn’t really an option as it would either increase the polycount without real benefit and manual editing isn’t an option as it would be a destructive process. Plus - remaining on the grid is paramount for snapping. Solidify is a rather fast way to stray from precise bounding box values.
Especially once the geometry nodes become more mature over the next iterations this could be a super powerful addition for modular game asset creation. Though it would probably really need to work on thin meshes as especially modular pieces need to:
a) remain procedural/non-destructive as long as possible as changes might need to propagate over many pieces
b) need to be aware of polycount as they may be used many times in a scene.
This wouldn’t only go for shortening walls but also for cutting panels, windows, holes etc. in geometry.
Did you try the Blender currently in the nightly builds of master? I changed the algorithm that Exact Boolean uses a couple of weeks ago in cases where both objects are not volume-enclosing. I am hoping it will give the desired results more often, especially if you are doing a difference with a cutter that is a closed volume.
I mean - this isn’t a thing that entirely keeps me from working or anything.
I just realized it when I edited the prototype and suddenly had some artifacts in there that weren’t there before.
Thank you 
Wow. Seems to work smoothly. You rock! Thank you.
