Implement union operation

[hannobraun]

It should be possible to create the union of two shapes, using constructive solid geometry (CSG). This is currently not supported, except for the simplest case, disjoint bodies, which is supported in the form of fj::Group.

Implementing this requires more solid infrastructure in the host application for storing and querying shapes. Also see #43 and #44.

[hannobraun]

Blocked on #97.

[hannobraun]

Now that fj::Union has been renamed to fj::Group, which explicitly is only intended for disjoint bodies, this can no longer be classified as a bug. I've updated the issue accordingly.

[hannobraun]

This is no longer blocked on #97!

[hannobraun]

I'm back to working on this issue directly. I'm not aware of any blockers, but of course some new ones may show up, as I'm getting into this.

[hannobraun]

My attention is currently diverted to #568. While not strictly a blocker, addressing that issue will make the implementation of the union operation easier, as help as circumvent #567, which would otherwise affect the implementation.

[hannobraun]

All known hurdles are out of the way now. I'm back to working on this issue directly.

[hannobraun]

I've made some progress this week, but I've hit another blocker: The shell/point intersection algorithm requires edges to be compared with one another, and this isn't currently possible (which was a bit of a surprise). See #993 for full context.

This is now blocked on #993.

[hannobraun]

#993 has been addressed. This issue is no longer blocked!

[hannobraun]

I've made some good progress on the Shell/Point intersection test since yesterday, but have hit on another hurdle. #1162 is explaining the problem.

Labeling this issue as blocked again, until #1162 is addressed.

[hannobraun]

#1162 has been addressed (for the most part). This is no longer blocked.

I'll be dealing with other priorities before I can pick this back up (namely #1589). Un-assigning myself from this issue.

[hannobraun]

This issue has been sidelined for a long time now, but with both #1162 and #1589 addressed, I'm finally ready to get back to it!

That this work has been sitting for so long is unfortunate, but it's also given me some perspective. I now believe that the approach I was following previously was not optimal, and ultimately rooted in a naive view of the problem. Basically, I approach this with the thought of "let's just implement the algorithm", then realizing that a lot of intersection tests had to exist for the algorithm to even know what to do, then going off and implementing those.

However, even when all the intersection tests are in place and the "knowing what to do" problem is solved, the other (maybe even bigger) problem still exists: actually doing the thing. Basically, once the algorithm knows where to remove/split/add vertices/edges/faces, it needs to then do those things.

Initially, I didn't realize how hard of a problem that was. But over the last few months that became painfully clear, mostly when I needed to construct geometry to write test cases, and that always turned into a huge pain. Since then, I've done a lot to ease the problem, namely the cleanup work in #1589 (and a lot of what came before). Those cleanups will directly benefit the work required for this issue.

However, there remain two problems:

1. We're not quite there yet. The cleanups laid the groundwork, but to effectively manipulate geometry, we need better APIs. I feel like we're finally in a good place to actually build those now.
2. Even if the "doing the thing" part of the algorithm were a non-issue, the approach of building the intersection tests first was the wrong one. All those intersection tests that have already been completed are basically dead code, not serving any use, and they have been a (not critical, but still significant) maintenance burden all this time. That won't change until the very last line of code of the union algorithm has been written.

Since I don't want to write more code that will be useless until the very end, I think it would be better to start with the geometry construction/manipulation APIs first. This has the following advantages:

• It is immediately applicable to other code in the kernel. For example the sweep code does geometry construction/manipulation, and it could really use some better APIs. I've rewritten that thing so often already... it always seems to get a tiny bit better, but so far it hasn't reached a point where I'd feel confident about being able to write similar code easily.
• It is also immediately applicable to any code that uses the kernel as a library to create geometry.
• The new APIs could be exposed to model code (although the details of that would require quite some figuring out), which would provide a low-level modeling API to end users, which could fill in until other, more productive APIs are ready.

So given all that, I've decided to build up this geometry construction/manipulation API until it has become powerful enough to support the union operation. When it has, it's time to revisit the intersection testing side of it.

[A-Walrus]

Another thing to think about is whether we can even represent the model created from our union. Say we create a union of two identical cylinders in a "cross" shape:

(Screenshot from blender)
In order to represent this shape we would have (4 times at 90 degress)

• Circular face on a flat plane (simple enough)
• some face on a cylindrical plane
  The 2d shape that would define the "cut" that we are doing to our cylinder is two sine waves, see image from UV unwrapping the shape in blender:
  

From my understanding we cannot represent this yet, as we only have circles and lines.

[hannobraun]

You are right about that, @A-Walrus. It's a fact that the way we represent geometry is pretty limited, and won't serve us much longer. As far as this issue is concerned, this problem is out of scope though. Please note that the milestone this issue is assigned to only plans for straight edges and flat faces. There's also this older blog post which provides some more context.

I've been thinking about this in the back of my mind for a while, but I don't know what the solution is. A possible feature-based milestone after "straight edges, flat faces" could be "square things with round holes", which would essentially mean the stable subset of Fornjot (see #431) would be restricted to combining a straight/flat part with a round part, side-stepping the problem you mentioned to some degree.

After that, I don't know what the best path is. Maybe there are some more tricks we can pull (i.e. enable more useful features with specific, targeted changes), or maybe we're going to need a better geometry representation (I don't currently know what that would look like) or maybe we would need to go for full NURBS at that point.

[hannobraun]

I've decided to add boolean operations to the feature wishlist and close this issue. There are just too many moving parts (some of which I've implemented, many of which are still missing) to make this actionable. I wrote about why that is a while ago.

This doesn't mean that I don't think this is a desirable feature, but I want issues to be actionable work items, and this one definitely isn't.