Boolean Improvements

Theres this paper from SIGGRAPH 2019 (i think) showing something similar, a method of doing boolean operations while preserving the majority of the quad layouts: http://vcg.isti.cnr.it/Publications/2019/NHESCP19/

11 Likes

Wow that’s really cool. Thanks for the link!

1 Like

Hi Howard, is there a place where I can download the new-boolean branch? I’m making a project right now and am running into issues with boolean and would like to try the new one if it might resolve the issue.

i put a copy on GraphicAll

5 Likes

@Howard_Trickey do you have an estimate for this boolean rewrite you are working on? I am asking this because, from the looks of it, it doesn’t seams to be finished any time soon. Wouldn’t be better to merge the coplanar fix you have(assuming it’s working with the current code) into the master, and then focus on a large scale rewrite? I think the biggest issue with the current algorithm is the lack of coplanar testing. Even if this works only with the simplest use cases, it is still better than nothing.
I am saying this because two years later, there is no improvement in this area at all… not a very AGILE approach to the issue, if you ask me.

I know, and I apologize for how long this has taken – much much longer than I expected and promised at various times. I’m going to answer with a much longer answer than you probably want. The TL;DR answer to the question you asked, however is: it is not possible to apply the current coplanar fix in my branch to the code in master, because the code is completely different.

I have started basically over about 3 or 4 times during this period as I’ve run into unexpected walls. I’ve written 143 pages of notes to myself during this process (so far!). It doesn’t help that I have a full-time job and family stuff taking up my life too. And at one point, took a big break on boolean to work on mitered corners in bevel. Here is a kind of history of the project so far:

  1. A gridded approach, where all vertices snap to certain 3d (fine) grid points. This was all done with a mesh represented by matrices, quite separate from BMesh. I spent a bunch of time writing a fast triangle-triangle intersect algorithm that actually returns the intersects in the coplanar case. I hit kind of a wall when I discovered that this case is hard to get right with floating point math: if an edge A of one triangle intersects another (non-coplanar) triangle very near an edge B of that face, how do we know that a future test of edge A against another face that contains edge B will come up with the same answer (on the edge, or on one side or another)? I realized that Campbell had partially solved problems like this in the current BMesh Boolean by keeping a cache of past intersections. I decided to go more agile/incremental by changing the existing code, so abandoned this one,
  2. An approach that would change the existing BMesh code to handle: coincident vertices, overlapping edges, intersections that happen on edges or through vertices, and coplanar faces. I hit several walls here. The first was that the existing code uses a process called “edge net” to add edge segments into the interior of an existing face. It didn’t work if the added segments overlapped each other, and could not be made to work in that case. A whole new approach was needed, and I spent a long detour writing, debugging, speeding up, and making robust a “Constrained Delaunay 2D Triangulation (CDT)” routine that could handle this in all generality (it is a useful algorithm on its own, and is now in Blenlib). The second, and harder, wall was that things get very messy when trying to change BMesh on the fly when vertices and edge segments merge. I was tearing my hair out, making more and more “merge tables” to keep track of this, and the code was getting harder and harder to understand - it would have been a future maintenance nightmare. And I never got it to work in complicated cases, such as partially overlapping segments combined with three or more intersections at the same point. I think the merges got circular.
  3. I moved to an approach that used an “abstract mesh” interface to the mesh instead of BMesh (my thought was: I could use the same interface to Mesh, the structure Blender uses on disk and the one that Modifiers act on – so as to speed up Modifiers by avoiding the need to convert to and from BMesh in modifiers). Instead of trying to change the mesh on the fly, I would accumulate all the needed changes as a “change delta”, and apply them all at the end. Also, I was going to work directly on ngon faces instead of a triangulation of them, which all the previous approaches had done. I had this method pretty much working by last fall (when I optimistically said at BCon that I thought I was only about a month away from being finished). All that was left was to speed it up, handle a case that I hadn’t done yet (concave ngons), and test to make sure it was robust. I did speed it up to the point that it was about as fast as the current BMesh booean, but when I got to robustness testing, I began to hit another wall. Things were fine with simple tests, but when I tried to intersect two spheres with about 100k vertices each, problems of inconsistent intersection decisions arose again (shades of the wall I hit in approach 1 – I should have been better prepared for this, but thought I could solve it by just doing intersections with canonical ordering of vertices – I was wrong). I spent a bunch of time on the CDT code, trying to make it give the answers I wanted when points were very near other edges, including using guaranteed exact “orientation tests”. But was still hitting problems. I was at this point about a month ago, the last time I publicly updated the newboolean branch. I suppose I could have tried to put this in master in this state (after finishing the concave ngon case, still not done). But would not have been happy with myself with code that might not work with large-mesh intersections. (Though the current BMesh intersection code has cases of its own where it fails on such large mesh intersections.)
  4. All the literature about Booelans that “just work” have given up on trying to use “epsilon tweaking” tweaking approaches to robustness – that is, approaches that do calculations in floating point, with tests to see if certain geometry is within epsilon distance of other geometry, and declaring intersection when that happens). All of my previous approaches, and the current BMesh intersection algorithm use epsilon tweaking. The modern approach, which I had been avoiding like crazy because I’m afraid it would be too slow (and because I was afraid of very tiny faces coming out of the intersection), is to use exact arithmetic to calculate intersections and make orientation decisions. But I have decided to experiment with this approach. My thought is to make both a fast epsilon-tweaking version and a slow exact-arithmetic version, using a package like gmp, and either let users pick or automatically pick (e.g., use the fast one when users are moving an object involved in a boolean modifier around, and switch to the slow one when they stop moving – not that I know how to do this!). In order to avoid the nightmare of two separate pieces of code for these two very similar cases, I need to use C++ with templates (templated by the underlying arithmetic type – double or gmp) to rewrite the CDT code. And I need to redo a bunch of my approach 3 because ngons just won’t cut it in an exact-arithmetic world – except for a few specific cases, the 4 corners of a quad will not be on exactly the same plane. Also, my current approach of accumulating deltas on the abstract mesh, while good, was too serialized – to hard to use multiple threads on – and I really want to use as much parallelism as possible in order to counteract the slowness of using exact arithmetic. This has led to a rethinking of the basic building blocks of the intersection algorithm, to allow splitting the computation into independent pieces. I have been working on this approach 4 for about a month now. I have the CDT routine rewritten in templated C++ but it doesn’t quite work yet. Today’s task is to make it work. I have the outer shell of computation of the new(est) intersection written in templated C++ and will continue on that after CDT passes all the unit tests. I have been doing all this in a local branch. When the code gets to be more like a working Boolean, I will move it into my newboolean branch and start committing to that again. Probably in a week or two.

There is a lot of work to do still in approach 4. Realistically, I am probably about 3 months away. But am confident that I will finally have a robust implementation when done.

To rpopovici’s direct question, “Wouldn’t be better to merge the coplanar fix you have(assuming it’s working with the current code) into the master, and then focus on a large scale rewrite?”, the answer is that since I abandoned approach 2 (for reasons I explained above), the code I have working now is not something that can be patched into the existing BMesh Boolean code, but rather has to be a complete replacement of it. I could consider putting the current approach 3 code into master, perhaps as an experimental feature alongside the current BMesh intersection code, but am hesitant to do so because (a) I’m not really sure how well it works. Users have given me essentially no feedback on that branch. (b) Since the code I plan on eventually using is pretty different, I don’t really want to get into simultaneously working on both. That would also slow down my progress on approach 4. ( c ) Blender developers really didn’t like the idea of several simultaneous choices for Boolean that all have to be maintained – that’s why Carve went away in the first place.

41 Likes

@Howard_Trickey thanks for the detailed answer! Is the delaunay triangulation you wrote accesible via operators or just lowlevel lib?

1 Like

It is available in the Python API, but not as an operator. My thought was that when my code is in and working, the existing Face (Knife) Intersect function will use that code in the 2d case.

The Python API interface is documented here: https://docs.blender.org/api/current/mathutils.geometry.html
(see mathutils.geometry. delaunay_2d_cdt).

2 Likes

Ok, I will try to add a delaunay operator to my mesh-utils addon based on this API

1 Like

Just adding a note that my March 9 post above gave the bones of a design document for approach 3. I will eventually have to revise that.

https://wiki.blender.org/wiki/User:Howardt/Boolean

2 Likes

@Howard_Trickey I added an opeartor to my mesh-utils addon https://github.com/rpopovici/mesh-utils, but just to know: your delaunay_2d_cdt() is crashing blender when you give it an unidimensional rectangle(zero height) to process…

1 Like

Thanks, I will fix that.

2 Likes

Good luck! Sounds like a lot of work. I still have a question around curves though.

I made a small suggestion about using curves to cut a mesh in a post above. Would your latest method allow for this? Or is it not really possible? I think the only other software I can think that does this is SolidThinking. Not saying I want to see it done at the same time but is it in theory something that can be done down the road with your current solution?

Thank you for your work!

1 Like

I could possible make it so that curves would be allowed by having an invisible step where the curves are converted to a mesh. I won’t be doing that for my first release of this, but could be a future enhancement.

7 Likes

No problem! Just wanted to know if it was a possibility in the future. Thanks for the reply!

2 Likes

Your dedication to ensuring quality for your work is to be admired and respected. I’m sure whatever you come up with will be great. Keep it up! :partying_face:

7 Likes

I am making progress on my new approach, and have moved it into my newboolean branch. Still far away from anything really useful, so you won’t learn a lot by trying the branch out. But making steady progress, and maybe have two months left.

I updated the Boolean Redesign task to summarize my current decisions and progress.

35 Likes

I just love reading things I only partially understand. :slightly_smiling_face:

1 Like

Thanks for the continued efforts and updates Howard! We always appreciate it!

2 Likes

What happened with boolean modifier in 2.90?
2.83


2.90
6 Likes