This is incredibly clean given what it took to figure it out!

Excellent work! If you don't mind, I would prefer to hold off merging this until the mesh intersection is implemented properly, since there is nothing so permanent as a temporary workaround.

(Also, does the CHANGELOG include some unrelated items by accident?)

I don't mind at all. Hopefully this time it won't take me another 9 months to get to it :-D
The CHANGELOG.md was not by mistake - just some additions I thought worthy while digging in the history. But you are right, I'll make a separate pull request for it. Amended.

This is incredibly clean given what it took to figure it out!

Since Solvespace is incredibly clean and beautifull I am very glad it came out like this. As @jwesthues said back in May 2018 literally "eight lines of code". Of course the real history is different but the master branch does not deserve this :-) I mostly agree with (what I think is) @whitequark s opinion that the history in the master branch should be clean and beautiful as if geniuses with OCD wrote it :-D

However the real history (issues, pull requests, ugly dev branches) should stay because it carries the real information that would help us, or someone else, in the future to figure things out. To me this is like the statement of a theorem and its proof - only the latter really teaches you something.

clean and beautiful as if geniuses with OCD wrote it :-D

It's not so much about clean and beautiful as about the raw practicalities of combing through git blame to understand some feature and using git bisect to find where a bug comes from. A project with excellent continuous integration and test suite like rustc can afford to have a messy history, we can't.

@ruevs I took a look at Mesh booleans in mesh.cpp. I just modified SMesh::MakeFromDifference a bit a found the following:

A new empty shell is created and then surfaces are added from mesh B, followed by some from mesh A. For Union that's it, so I figured the BSP is rejecting surfaces inside the shell. For difference, the normals of B are flipped, so it keeps surfaces from A that are outside B (inside based on flipped normals).

Modifying that to set flipnormal = true for both operations give surfaces from B that are inside A, and surfaces from A that are inside B. That's intersection. There are only 2 problems. The resulting mesh is RED - inside out. And I'm not sure what to do for coincident surfaces. We need to keep them but that's not happening. Most of the logic is already there in some form.

Seems like this is going to be another "easy" thing once the "right" way is found.

Sometimes I ramble. Couldn't remember doing much special for Shells in my mirror branch, so I checked and it does make mirror images when forced to mesh. Funny thing is mirroring involves doing a scale of -1 so I figured it would also flip the normals back, but there is no such operation done. The scaling is called from inside a templated function I had to write for mirroring, so that led me to SMesh::MakeFromTransformationOf which does the scaling. Right there in the middle it checks for a negative scale and swaps two verticies.

Modifying that to set flipnormal = true for both operations give surfaces from B that are inside A, and surfaces from A that are inside B. That's intersection. There are only 2 problems. The resulting mesh is RED - inside out. And I'm not sure what to do for coincident surfaces. We need to keep them but that's not happening. Most of the logic is already there in some form.

You are right. I also figured out how to make red (inside out) mesh intersections back in September last year. But I never committed - because of the problems you listed.

void SMesh::MakeFromIntersectionOf(SMesh *a, SMesh *b) {
    SBsp3 *bspa = SBsp3::FromMesh(a);
    SBsp3 *bspb = SBsp3::FromMesh(b);

    flipNormal = true;
//    keepCoplanar = true;  // Maybe? Does not help :-(
    AddAgainstBsp(a, bspb);

    flipNormal = true;
    keepCoplanar = true;
    AddAgainstBsp(b, bspa);
}

By the way the interesting code seems to be here and here.

Is there a way to build a BSP with flipped normals? A*B = A - !B

Currently, we have:

Note that even though the union operation is commutative with respect to volumes, the two operands are treated differently. This is because we need to keep one copy of any coincident bounding surfaces, not both. It's arbitrary which copy we keep.

flipNormal turns the mesh inside out by flipping the normals (by reversing the order of the triangle vertices), as the name suggests; but it also changes the rules on what pieces to keep and discard. For intersection, those rules are what you want but the flipping is not. So I think you need to split those two behaviors into two flags, by adding something like keepInsideOtherShell. Then you'd have:

Or you could replace the three boolean flags with just one enumeration of UNION_OP_A, etc.

Thanks! I hope tomorrow I'll have some time and look.

@ruevs I applied a patch to my master based on the commit here. Then I got compiler error in boolean.cpp complaining about inFace not being declared in scope.

@jwesthues Jonathan your hint was really helpful. I implemented the triangle mesh boolean intersection. While doing it I also changed the union to keep the same coplanar faces as the NURBS one does.

@whitequark in my opinion this is done.

@phkahler

I got compiler error in boolean.cpp complaining about inFace not being declared in scope.

You did not merge properly. I removed inFace in this commit ec30567 back in November.

Despite all I have a (really nasty) test model with only flat faces that breaks all boolean operations in both NURBS and mesh mode. I will open a new issue "Nasty models that break booleans" as a convenient place for us to continue work on the boolean engine(s).

@ruevs Thanks. I really like @jwesthues' suggestion of replacing the flags with a enum. Could you do that as well in this PR? We've been replacing booleans with enums for a while and it tends to make logic a lot easier to understand.

In my opinion using an enum with six values will make the code more complex and less readable in this case. Take a look at how the flags are used.

What is more the three flags combined with the a and b operands keep the information about the type of operation in mesh.cpp. If we do enums we "pollute" bsp.c with "knowledge" about boolean operations. I think this is bad.

That's reasonable.

Strictly bsp.c is already a bit polluted, with logic like when to keep coincident surfaces with normals in the same vs. opposite directions. I guess you could go the other direction and add more flags, keepInsideOtherShell, keepOutside..., keepCoincidentSameNormals, etc.? Or make them a bit field or something? That would lend itself more to the "stupid" model of building Booleans as experimental lookup tables instead of trying to write intuitive logic (that may later mislead). No strong feelings personally though.

You are right. For example (I think?) with the available flags it is impossible to implement "XOR" since there is no way to express "keep only stuff outside of both shells".

However abstracting it out will be a bigger change with a bit more risk of breaking things. Maybe we should leave it for when/if we need it?

I'm OK with leaving that code as-is for now.

Booleans will continue to get investigated. Lots of test cases that fail, and now more people looking at it.

On the performance side I was having a look. The BSP creation for each surface in a shell can run in parallel (tried it), but I saw no obvious benefit - this will want to be included in the frame time. But I think the majority of the time is going to SShell::CopySurfacesTrimAgainst() which looks mostly thread safe at the per-surface level but not quite. I want to see about untangling "into" and see if a per-surface list or similar can be used and combined at the end. That function and its call tree nest at least 3 loops over edge lists, so it's probably a good place to look. OTOH it's not good to disrupt things before they work correctly. correct > fast.

I'm OK with leaving that code as-is for now.

[..] it's not good to disrupt things before they work correctly. correct > fast.

I agree. Normally I am not this reticent about refactoring, But this code is "old and tried" - for example no one has seriously modified boolean.cpp in the last eleven years. Jonathan made the last serious changes in August 2009. The rest are minor cleanups and "NFCs". So I am being extra careful.

By the way can someone explain why the history of boolean.cpp is not visible in git log before this 0a24cf4 ?

0a24cf40f07ef64ae28a19a82051fda925e20a68
Author: Daniel Richard G
Date:   Wed Nov 13 02:20:31 2013 -0500

    Moved most of the source into a src/ subdirectory

I can get to older commits only with blame - for example the above commit from 2009-08-21. It is the same here on GitHub. Does it have something to do with the moving?

At the same time the repository as a whole goes happily back to the first commit ever from 2008-03-25 6713923

It does – you'll likely need the --follow argument to git log:

--follow
   Continue listing the history of a file beyond renames (works only for a single file).

On my checkout, git log --follow src/srf/boolean.cpp ends at bb4b767:

commit bb4b767e99e95940086d1db21e760570966c1801
Author: Jonathan Westhues <jwesthues@cq.cx>
Date:   Thu Jan 22 19:30:30 2009 -0800

    Tear everything apart, moving away from meshes and toward shells.
    Add stubs for functions to perform Booleans, and get rid of mesh
    stuff, including the kd tree accelerated snap to vertex (which
    should not be required if the shell triangulation performs as it
    should).

    Also check that a sketch is not self-intersecting before extruding
    it or whatever. This is dead slow, needs n*log(n) implementation.

    [git-p4: depot-paths = "//depot/solvespace/": change = 1902]

Whereas git blame does it by default:

The origin of lines is automatically followed across whole-file renames (currently there is no option to turn the rename-following off). To follow lines moved from one file to another, or to follow lines that were copied and pasted from another file, etc., see the -C and -M options.

Thanks! I learned something new.

This works really well. My only suggestion would be putting the radio buttons on 2 rows:

union ...........difference
intersection...assemble

Just because that is now the widest thing in the text window.

Good idea - done. But I did

union assemble
difference intersection

looks more logical to me. But if you don't like it I can change it. @whitequark ?

Looks great, thanks everyone!

@ruevs I like your placement more too.