Simplify object graph around HalfEdge

[hannobraun]

(This issue is part of a larger cleanup effort. See #1589.)

Arguably the most important part of the Fornjot kernel's code base are the core data structures that store the objects that make up shapes. Those objects reference each other. For example, a Cycle is made up HalfEdges and references those. Through these references, objects form a graph.

The objects and the graph they form have evolved over time, always in response to specific problems that I had to solve. The further evolution of this code is something that I think about a lot, due to the importance of the object graph to the Fornjot kernel. Everything in the kernel deals with those objects, in one way or another.

In recent weeks, I've been playing around with lots of ideas on how to simplify the object graph. Some of these ideas are vague and require further thought and experimentation. One of them has reached a stage, where it has become concrete enough to open an issue about. (And you're reading it!)

Specifically, this is a concept for how to simplify the object graph around HalfEdge. I've already started working on this, so the some of the items in this list are already checked off. I plan to keep this list updated as I'm going forward:

• Demote Vertex from its status as an object (Demote Vertex from its status as an object, embed it in HalfEdge #1521)
  What makes objects special, compared to normal structs, is that they are stored in a centralized data structure and are referenced by other objects through Handle. This gives them an identity that is independent of their value. Equal objects can still have a different identity, which is an important concept for the validation code.
  Vertex, however, doesn't need to be an object. Vertex is referenced by HalfEdge, and in practice, it is never shared between two HalfEdges. (In theory, it could be. But even then, having it be an object is not necessary. The identity checks in the validation code are done on the level of SurfaceVertex and GlobalVertex, which is enough.)
  This means that Vertex can just be a regular struct that is embedded in HalfEdge. No separate object type is necessary, which simplifies the graph.
• Move reference to Curve from Vertex to HalfEdge (Move Curve reference from Vertex to HalfEdge #1522)
  Vertex contains a 1-dimensional position, which only makes sense in relation to a Curve. For that reason, Vertex contains a reference to that Curve.
  Both vertices of a HalfEdge need to reference the same Curve, or the HalfEdge is invalid. This is checked by validation code. By moving the Curve reference to HalfEdge, we simplify things (one less reference to Curve per HalfEdge) and remove the need for that validation check.
• Remove Vertex (Continue cleanup of HalfEdge #1524, Remove Vertex #1526)
  As of the previous item in this list, Vertex only consists of a 1-dimensional point and a reference to its SurfaceVertex. Within HalfEdge, we can replace the use of Vertex with tuples containing these two things.
  There are two main reasons for removing Vertex. First, to free up the name (see below); second, because its two fields will become decoupled within HalfEdge (see next item).
• Only store a reference to a single SurfaceVertex in HalfEdge (Remove end_vertex fields of HalfEdge/PartialHalfEdge #1638)
  HalfEdge needs to store the two one-dimensional points that bound it on the edge, because both are needed for approximation. And since neighboring edges might (and often will) be on different Curves, they might not share the same coordinate system, so it's not possible to only store one boundary per HalfEdge, and get the other one from a neighbor.
  SurfaceVertex instances, on the other hand, are shared between neighboring HalfEdges, and this is actually a hard rule that is checked during validation. This means that every HalfEdge only needs to store a single SurfaceVertex (either the one where it starts or the one where it ends, not sure which one's better yet), as the other one can be retrieved from the HalfEdge's neighbor.
  This would further simplify the object graph by reducing redundancy, as well as make more validation checks unnecessary, as invalid configurations could no longer be expressed.
  There's a bit of a question mark on how to implement this. There is definitely code that has access to a HalfEdge and needs the two SurfaceVertex instances that bound it. Either that code needs to be rewritten to work with Cycles instead, if practical, or every HalfEdge needs to store a reference to its neighbor, so the second SurfaceVertex can easily be retrieved.
  I don't know which is better. The second option sounds more convenient to use, but it might re-introduce unnecessary complexity into the object graph. On the other hand, by doing this, we might be able to replace Cycle, which would be a simplification of the object graph in a different way. Not sure, we'll see!
• Demote SurfaceVertex from its status as an object (no longer necessary, thanks to the work done for Compute surface position on demand instead of storing it #1634)
  Once HalfEdge only references a single SurfaceVertex, thereby not sharing references with their neighbors any more, we no longer need to check SurfaceVertex identities in the validation code. If we don't reference the same SurfaceVertex from multiple objects, and no longer care about its identity, it doesn't need to be an object any longer. It can just become a struct that's embedded within HalfEdge.
• Remove SurfaceVertex (Remove SurfaceVertex/PartialSurfaceVertex #1641)
  Its fields, the 2-dimensional surface position, reference to Surface, and reference to GlobalVertex, can be inlined into HalfEdge. (And in fact, I have some tentative plans to move the Surface and GlobalVertex references elsewhere, which would make the existence of SurfaceVertex unnecessary, even counterproductive.)
• Rename GlobalVertex to just Vertex (Rename GlobalVertex to Vertex #1642)
  With GlobalVertex being the last remaining vertex object type, it can take over the simpler name that has been freed up during this process.

This is it! This plan, if it works out, would remove two types of objects, simplifying the object graph. This would in turn make existing of code that operates on this part of the object graph simpler, and new code easier to write.

I have already started working on this, and plan to continue until I hit a hurdle that makes it necessary to delay or stop the rest of the plan.

[hannobraun]

I've been actively working on this issue, as the list of referencing pull request above this comment shows. The list in the original issue description is up-to-date. The current focus is to only reference a single SurfaceVertex in HalfEdge, but that requires some deeper surgery than previously expected.

I've already removed a lot of references to HalfEdge::surface_vertices, but the remaining ones are a bit harder to deal with. The one I'm currently working on is in HalfEdge's Reverse implementation. There's no good way to adapt that code without it, I think, but there's a different solution: Just remove that implementation, which would mean only Cycles can be reversed, not single HalfEdges.

I think this would be fine, but unfortunately the sweep code relies on reversing single HalfEdges. But that code could use some cleanup anyway, so I'm currently rewriting the problematic parts of it.

[hannobraun]

The rewrite of (some of) the sweep code has been causing more trouble than expected. It already felt 95% done when I posted my previous comment here, but unfortunately some of the building blocks the rewritten code uses (mostly in the builder API) are too limited to support this new use case. I've been successful in addressing some of that (see the pull requests that have referenced this issue since my previous comment), but in other cases, I've hit some hard problems.

These hard problems are mostly caused by the complexity of the object graph. Which is quite ironic, since this is an attempt to simplify the object graph. But this shows how important this work is.

For now, I'll keep at it. I don't think any of the problems I've hit are impossible. It's just a lot of complicated "I need this data here to do A, but the data won't be available until later when I do B, so where do I get it now". The devil's in the details, as usual. I think it's acceptable to find some ugly hacks to paper over these problems, if necessary. If that allows me to advance the cause of object graph simplification, I can circle back later and fix these hacks, once the simplified object graph makes stuff like that easier.

If I can't find solutions, I might need to pause work on this issue and try to start another simplification attempt in a different place. I have lots of ideas, but unfortunately some are quite radical, meaning they would be larger changes and not sure to work out. This issue, on the other hand, is a series of rather incremental improvements that I can build on later, when it comes to working on the more radical solutions.

[hannobraun]

I've made a lot of progress since my last update here. The rewrite of the sweep code is finished. Since then, I've made some more specific plans to simplify the object graph (see #1589) and started picking off some of the lower-hanging fruit. This has also made the outstanding work on this issue a bit easier.

I've landed two more pull requests (see references above this comment) that made some progress here, but I'm again starting to hit hurdles. I will probably focus on #1586 for the time being, as I suspect that I can make some progress there, and that this progress will in turn help with the hurdles I'm hitting here.

[hannobraun]

Turns out I was able to return to this issue much faster than I expected. The next item on the list, referencing only a single SurfaceVertex in HalfEdge is done! List updated.