I don't see real cases where we need XOR. @Symbian9, any samples?

XOR usefull for design parts of complex shape, for example in engine and watch constructions.

If this is the feature I am thinking where the solid result is where the 2 solds intersected. This is particularly useful in many circumstances.

The image link below shows one possible use for such an operation.
http://help.autodesk.com/cloudhelp/2016/ENU/AutoCAD-Core/images/GUID-1C31FCED-9999-4012-B6F9-518D00711466.gif

There is no question that an intersect ("AND") operation is useful. I don't see any point in "XOR" though.

@whitequark,
I think this is a lot of unpredictable work. I actually have tried do the same thing for NotSolveSpace, but some problems force me to decide stop doing this.
If @jwesthues can help, we can try again.

@Evil-Spirit OK.

FYI: I've implemented the "intersection" operation in my own fork now. I needed this function for my 3D printing, where I frequently wish to extract part of a whole object in order to make a test print of that part only.

I circumvented most of the "unpredictable work" mentioned by @Evil-Spirit by rewriting the intersection operation A * B as the result of two difference operations A - (A - B). This incurs some overhead of course, but with the benefit of less unpredictability :)

Implementation was relatively straightforward this way and mainly consisted of modifications to srf/boolean.cpp for the non-mesh solids:

void SShell::MakeFromIntersectionOf(SShell *a, SShell *b) {
   SShell c = {};
   c.MakeFromBoolean(a, b, SSurface::CombineAs::DIFFERENCE);
   MakeFromBoolean(a, &c, SSurface::CombineAs::DIFFERENCE);
   c.Clear();
}

and to mesh.cpp for the meshes:

void SMesh::MakeFromIntersectionOf(SMesh *a, SMesh *b) {
   SMesh c = {};
   c.MakeFromDifferenceOf(a, b);
   MakeFromDifferenceOf(a, &c);
   c.Clear();
}

as well as the necessary changes to the UI to present the option to the user.

Wow, this is really neat! I'll look into integrating it.

Cool. FYI, the work to do intersect without the double-Boolean should be very small, just the additional case in KeepRegion(), eight lines of code. Neither shell gets its normals flipped, and keep only the pieces from A that lie inside B (and vice versa).

@jwesthues Hello! Can you give a links to lines of code where we should do this? I have understood what are you meaning, but any additional information can help.

Six lines plus one of whitespace, I guess. It should literally just be another case inside that switch statement.

Note that even though the intersection is a commutative operation (like union), the surfaces from shell A are treated differently from the surfaces from shell B, with the test on opA. This is to handle the case where a surface from A is coincident with B--we need to keep one of those surfaces but not the other. It's arbitrary which.

Thanks. I actually tried to make the change in KeepRegion() before going the other way, but couldn't muster enough brain cells for the job. Will have another go at this. Also, I wasn't sure if anything needed to be done to KeepEdge() too.

I think no? But I often found it easier to just enumerate cases until I got the right answer than to think.

I think no? But I often found it easier to just enumerate cases until I got the right answer than to think.

Nope, can't figure it out. I enumerated all cases and they all just give either nothing or clearly wrong result. What sort of condition should it even be? This code is like black magic to me.

Also, I tried optimizing mesh intersections with...

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

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

but the resulting solid has all normals flipped (that's ok, we can flip them back) and this gives wrong result for coincident surfaces (which I never figured out how to fix). Any ideas?

The current code is pretty confusing. A surface from shell A might be:

• inside shell B
• outside shell B
• on shell B, with normals in the same direction
• on shell B, with normals in the opposite direction

The pieces (should) have been split so that each piece is strictly one of those four. It might be clearest to replace all of KeepRegion() with a lookup table, something like:

static const bool Keep[][] = {
   // inside    coinc_same    coinc_opp    outside
   { false,     false,        false,       true }, // union opA
   { false,     true,         false,       true }, //       opB
   // ...
};

You could do something similar for the BSPs for the mesh operations.

Can we get this in? @whitequark If someone put just those changes into a branch off current master will you accept a PR?

@phkahler Which changes exactly? I was never able to make it work properly, and I don't think merging the workaround with two difference operations is a good idea.

@whitequark The commits in @ghoss fork seem to have a little extra stuff - something about mirror groups. It seems a shame that someone is maintaining a useful and requested feature for so long. I don't think the implementation is bad, just not optimal. It's also hard to work out the "right" solution as outlined above when you need to integrate all the text window stuff anyway just to try things properly. I think this would be a net-positive for SolveSpace the way it is - but cleaned up with no extra fragments.

It's also hard to work out the "right" solution as outlined above when you need to integrate all the text window stuff anyway just to try things properly.

I've already worked out all the text window stuff--you can apply this patch to play with it. But given how slow and fragile all the solid operations already are, I'd probably rather not have intersection at all than have intersection that is unnecessarily twice as slow, and with twice as many opportunities for the NURBS operation to break.

So I made in "intersect" branch and put this in. Since I couldn't figure out the text window (sorry, couldn't apply the patch). I switched the call for difference to intersect in the first patch so I could test. It works using the dual difference method. Then I changed the code hoping to use KeepRegion with a single boolean. No luck. One thing of note: Making the code in INTERSECT identical to that in DIFFERENCE does not produce a difference operation. So now we know there are more changes needed to implement this in one operation.

I'm a blind as everyone else on this. It's not clear how all the pieces fit together. Like what does "opA" do? it selects one of two boolean expressions to return. Why? What does it indicate?

Anyway, I have what I just described branched off todays master if anyone wants to explore booleans again.

EDIT: Maybe I'm wrong. In order to get the shell flipped for difference, the CombineAs:: needs to be set to difference so it won't work properly if it's set to INTERSECT....

@phkahler I'll rebase the text window changes on top of master in a moment.

@phkahler See the branch wip-intersection.

As a side note, if you're ever blocked by anything related to the text window, feel free to ping me and I'll just fix it, that's one of the easier parts of SolveSpace to work on for me.

So this is in my "intersect" branch and working - freshly integrated from master. Try this out, it's really cool.

I still haven't figured out how to do it in a single boolean operation but the code is there and easy to switch. That currently works so long as none of the new edges are needed (those resulting from the intersection itself). So partly.

Thanks a lot for the test models. It seems you are concentrating at a completely different set of NURBS failures - numerical ones. All your tests fail with something like:

didn't converge
have 0.000 4.751 -23.944
want 0.000 4.633 -24.419

didn't converge
have -nan(ind) -nan(ind) -nan(ind)
want -42.080 -41.514 -55.131
distance = -nan(ind)

And they fail independent of the operation.
I had seen your pull requests on github but had not tried them. I'll merge them and try them tomorrow.

I on the other hand I was concentrating on "singularities" in the geometry. I think for intersection I have handled them all (maybe :-) .

Well, both phkaler/nurbs and phkaler/vecmath merged cleanly. The helix intersection (all booleans) does work better, bug_one.slvs does as well. Of course it is still way too easy to break all your examples...
This is deep :-)

Now that I've merged your branches I will see if I can improve Helix_test2.slvs with intersection - by now I am very used to debug intersection curves choice problems.

By the way it is always nice to see how much better the NURBS mesh is (when it works) compared to triangle...

@ruevs Did you extend the cylinder in bug1? It's fine the way I saved it, but when you cut away a little more it runs into problems:

If you fixed that it's IMHO a major improvement! Curves cause problems. Compound curves even more so.

I did not fix it :-(

Extended it, shortened it, moved it around, changed the diameter, made it larger and smaller than the "spool"... ;-)

And it is broken "most" of the time.

I looked dsuperficially for misidentified (by KeepEdge) edges and I think there are none (for intersection). I think it is all numerical.

Did the same with all four models.

I'm with Jonathan on the reversal of new curve segments. Intersection will always need them in the reverse direction for Union or Difference. Here's a drawing showing surface "A" with trimmed region "a" intersected by surface "B" with trim region "b". I have not shown the parts of A or B outside the trim regions because they aren't "real" in the sense that we don't ever care about them.

In the drawing I consider both surfaces to be facing us with b angled a bit to the left. The trim curves are supposed to be counter clockwise (CCW) for the outer curve if I recall correctly. So the arrows show the direction of the perimeter curves for a. It gets cut by surface b into two pieces. Which of those are kept depends on the boolean operation.

For Union, we'd keep the left half of a and throw away the right side because it's buried inside the other shell. For Difference we'd also keep the left side of a while the right side will be cut off because it's inside of b and needs be cut away. For Intersection, we throw away the left side and keep the right because it's inside of b.

The direction of the new edge in the middle depend which side of the surface is kept. When keeping the left side it needs to point up and for the right side down. So I agree with @jwesthues that its direction for Intersection should be opposite what it is for the other booleans. I have no idea how the direction is currently determined for new curves.

I would also argue that the existing curves should never have their direction changed. They will either be kept or discarded based on weather they are inside b or not.

While I have a diagram up, I think you can see that any curve resulting from the intersection of A and B is not relevant unless it's also inside of "a" and "b" because they're not "real" in the sense that we don't care about that part of the underlying surface. Those that are inside both a and b must be kept because they are the new edge which divides both surfaces into "keep" and "discard" regions.

I haven't thought too much about coincident surfaces, but I think all the curves on those should be pre-existing, but may be rediscovered by a surface-surface intersection algorithm.

I can imagine the data available to KeepEdge() contains all of this (or not) but it might be nice to condense it into higher level abstract flags that can have broader more understandable rules applied.

Cool re intersection--a triumph of the lookup table? You can presumably apply the same approach to difference/union, taking the existing behavior as a starting point and changing only cases that you've observed were broken.

The basis idea of the Booleans is that for each surface in each shell, we assemble a set of edges, including all the original trim curves plus any new edges arising from surface-surface intersections. This set should contain all of the edges that we'll ultimately need for the output trim curves, but may contain additional edges too. To determine which edges to keep, we want to know whether the region just inside (indir) or just outside (outdir) the edge lies within the shell. We want to know this both for the shell that the surface in question originally came from (orig) and for the other operand of the Boolean (shell -- agnst would be better).

So in raycast.cpp, we first test whether the edge lies exactly coincident with an edge of the shell, or whether it lies in a surface of the shell. In general, neither will be true, so we test by casting a ray from a point on that edge. In the general case, that ray intersects a surface of the shell somewhere inside a trim region, well away from any edges. The ray dot that surface's normal tells us whether we're inside or out. If we're unlucky, then we hit one of many possible special cases. The code doesn't try to handle these special cases. Rather, it tries to choose the ray's origin point (since that can be anywhere on the edge) and direction (since that's totally arbitrary) to avoid them.

Re the failure that turns into success by replacing a straight Bezier with a line--note that many types of surface-surface intersection are special-cased, so that we don't usually have to fall back to numerical (marching) intersection. (Though even without that, geometrically identical but parametrically different surfaces would perform differently when marching.)

If a problem is in that surface-surface intersection curve generation, then you can solve it either by improving the marching or by adding more special cases--for example, you can notice that the surfaces are particular types of conics for which a closed-form solution exists, and output that instead of a numerical approximation. Even when no exact solution exists, you can probably do an approximate special case that's more robust and faster than marching.

I just realized that using A - (A - B) is also the same as doing A - !B where !B is the (infinite) solid defined as outside of shell B. In other words, turning B inside out and subtracting it from A is equivalent to A and B. There is actually a function for turning a shell inside out that basically reverses all the trim curves. Just thought that may offer a different way to see how to deal with edges, or dealing with whatever is in the triangle mesh code.

It is done.
The smart and beautiful method prevailed after all :-)
It was correct all along. All I had to do was realize that this was the case and only the reversal of the edges resulting from surface intersections was preventing it from working correctly. This took a while to figure out (as did figuring out where and how to reverse them).
Take a look here if you are curious and like gory details.

Next up: figure out how to do the triangle mesh intersection in SMesh::MakeFromIntersectionOf.

Excellent, very glad to see this dusted off. While you're in there, you could probably improve the union and difference too, surely many special cases handled wrong now....

I am very glad as well. Too many months passed until I found time to concentrate on this,
My next targets are:

• The edge classifier failures
• "couldn't find an ear! fail" in SContour::UvTriangulateInto (Don't create redundant edges in UvGridTriangulate into. #594 (comment))

These will help with all boolean operations.
And then the "did not converge" numerical stuff... there I will need to re-learn the math first, but I think @phkahler may beat me to it :-)

Just for cross-reference :-)
https://solvespace.com/forum.pl?action=viewthread&parent=1497&tt=1474341226
https://solvespace.com/forum.pl?action=viewthread&parent=2366&tt=1531927656