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'm still actively working on this. I made some slow progress over the last few weeks, implementing building blocks that the union algorithm is going to need. Over the last few days I've been stumbling a bit, as it became increasingly unclear what the next step is, and a few things I've tried didn't work out.

So I sat down, did some hard thinking (not easy in this heat :smile:), and came up with a plan for what's missing to take the next step with implementing the union algorithm.

So here's what I'm likely going to be working on for the next weeks/months(/years? :scream:):

• [x] Implement Face/Point containment test (#941)
  • Required for ray/face intersection.
  • There's code in triangulation that can be reused.
• [x] Implement ray/face intersection test (https://github.com/hannobraun/Fornjot/pull/978)
  • Look into using robust-predicates, specifically orient3d.
  • Reuse the ray type from the triangulation/polygon code.
  • Return where the ray hits the face: vertex, edge, or face itself.
• [x] Extract Shell from Solid (https://github.com/hannobraun/Fornjot/pull/983) To make sense of the ray/face intersection result, I'm going to need APIs for determining the neighbors of a face, or the faces connected by an edge. I think Shell would be the right place for this kind of thing.
• [ ] Implement Shell/Point intersection
  • Implement using ray/face intersection.
• [ ] Implement Shell/Face intersection
  • Implement by checking the face against each face of the shell.
  • Detect whether the face is fully contained within the shell.
  • If a face doesn't intersect, it is inside the shell, if any of its vertices is inside the shell.
• [ ] Implement Shell/Shell intersection
  • Implement using Shell/Face intersection, by checking each shells faces against the other shell.
  • Indicate whether one shell is fully contained within the other.
  • Return intersection edges.
  • Indicate whether intersection edges lie in a face, split the face, or split edges of the face.
• [ ] Implement Solid/Solid intersection
  • Implement using Shell/Shell intersection.

This list is subject to change, as I figure more things out, but I think it'll at least serve as a good guide going forward.

[hannobraun]

I've been making some progress this week. I implemented face/point intersection (the first item on the list) and am now extending it, to provide the information required for ray/face intersection (the second item on the list).

[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 https://github.com/hannobraun/Fornjot/issues/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.