Consider revamping GlobalCurve

[hannobraun]

Curve is defined in surface (2D) space while GlobalCurve is defined in global (3D) space. Hence, Curve is used to convert curve (1D) coordinates to surface coordinates, while GlobalCurve is used to convert those curve coordinates to global coordinates.

This is working well enough for now, but I don't think it will be a suitable solution going forward.

Problem 1: Redundancy between Curve/GlobalCurve

GlobalCurve isn't actually needed for for generating global coordinates. Curve references the Surface it is defined on, and that Surface can be used to convert the surface coordinates that Curve generates into global coordinates, bypassing GlobalCurve.

So, as far as computing approximations goes, we don't need GlobalCurve. This isn't really much of a problem, but it's supporting evidence for what is going to be my proposal.

Interlude 1: Let's cache curve approximations

If you've been following carefully and have sufficient knowledge of the Fornjot kernel, you might note that what I've just said wouldn't actually work. It could result in slightly different 3D points being generated for Curve approximations that are supposed to be the same, thus resulting in an invalid mesh being generated. (If you actually noted that, please send more pull requests. I can use the help. 😄)

Right now, Curve approximation goes through GlobalCurve, and we're being really careful about approximations of should-be-identical GlobalCurves producing the same points (even if those GlobalCurves point in different directions). If we started going through both the Curve and the Surface to create a 3D approximation, then no amount of being really careful would prevent invalid meshes.

This "being really careful" business is probably already a warning sign that there's a deeper problem not being addressed. So let's just remove the need for being careful in the first place. When approximating a Curve, let's cache the approximation, using the GlobalCurve as a key.

(Actually, we can only cache the curve-space and global-space points generated for the approximation. We'll need to re-compute the surface points per Curve, but that's just an implementation detail and not a problem.)

This might have the side effect of saving redundant computations, leading to better performance. But right now, these re-computations don't seem to be a performance problem, so whatever.

Problem 2: CurveKind won't cut it going forward

Both Curve and GlobalCurve own a CurveKind, which defines the actual geometry of the curve. To accommodate both Curve and GlobalCurve, CurveKind is generic over its dimension. Curve owns a CurveKind<2>, GlobalCurve owns a CurveKind<3>.

There are already some subtleties with how the two referenced CurveKinds need to match each other, which adds to the redundancy problems. For example, the GlobalCurve's CurveKind<3> might be a circle, but the corresponding Curve's CurveKind<2> might be a line, if the curve is defined on a round surface.

This is going to get worse. Once we support helical sweeps, we need to represent helical curves, and a CurveKind<2>::Helix doesn't make any sense. We need to split CurveKind into separate enums for 2D and 3D.

Interlude 2: Let's split CurveKind into SurfacePath/GlobalPath

CurveKind is one of those names that I've never been happy with. But you gotta do what you gotta do to make progress. Can't just sit there for a few months, staring at the screen, trying to come up with better names for things.

Fortunately, that kind of problem tends to take care of itself over time. As it did in this case. Let's just call it a "path". That nomenclature is already used in the context of sweeps. We can have SurfacePath for 2D paths, and GlobalPath for 3D paths.

This is a change that can be done right now, with Curve owning a SurfacePath and GlobalCurve owning a GlobalPath. And I think this would serve us well going forward.

Problem 3: GlobalCurve needs to be normalized?

Sometimes we need to know whether two Curves are the same curve in 3D space. Actually, this is not completely true. What we do need to know though, is whether two HalfEdges are the same edge in 3D space (#993), but we can't have the one without the other (#993 (comment)).

In that linked comment, I've been musing about normalizing GlobalCurves, or even normalizing all Curves/GlobalCurves, but as I noted there, neither is satisfactory. Those solutions seem error-prone.

But if problems 1 and 2 were addressed, and thus Curve/GlobalCurve were no longer redundant, then normalizing GlobalCurve would no longer be necessary, because GlobalCurve would no longer contain any geometry that required normalization.

What would GlobalCurve contain though? Let's look at that next.

Proposal

Now might be as good a time as any to mention my first thoughts on this topic. My conclusion there isn't valid (we still need GlobalCurve, as per the requirements laid out in problem 3), and I wasn't fully clear on the need for 3D paths (we'd definitely need a struct to represent them, as per problem 2 and interlude 2). I'm just noting it here for the sake of completeness, and to provide some context on the thinking that lead to this issue.

So, given I'm so much smarter now, having written all this, what do I believe GlobalCurve should be, going forward?

Well, as noted previously, due to the redundancy with Curve and the Surface it references, GlobalCurve no longer needs to contain any geometry. But we do still need some way to know whether the GlobalCurves referenced by two different Curves are supposed to be the same. And all we need for that is some kind of ID value, and GlobalCurve would become a wrapper around that ID.

I see this play out like this:

• Whenever we create a Curve, instead of computing its associated GlobalCurve, we generate a unique ID and build the GlobalCurve from that.
• If we create a new Curve that is known to be the same in global space as the original Curve in 3D space (when sweeping said original Curve, for example), we make the new Curve reference the same GlobalCurve (just like we already do).
• Same goes for creating multiple Curves that are known to be the same in global space (Surface/Surface intersection testing, for example). Just create one new GlobalCurve and make them both reference it (again, no change from what we do now).

So the question is, how do we generate unique IDs for the new GlobalCurve? Two options, as far as I can see:

1. Using some hack, like a global variable.
2. Using centralized object storage (Implement lightweight, centralized object storage #1021).

While I'm not above employing a hack or two to make progress, hidden global state might be taking it a step too far. And centralized object storage is probably a good idea anyway, so maybe just do that first.

Conclusion

So in conclusion, I've laid out problems that make the current Curve/GlobalCurve/CurveKind structure unsuitable for the next batch of design challenges we'll be facing, and I've presented a proposal (along a few distinct-but-related sub-proposals) for addressing that.

These are the action items resulting from that:

• Cache curve approximations (see Interlude 1; addressed in Cache GlobalCurve approximations #1082).
• Bypass GlobalCurve in curve approximation (see Problem 1; addressed in Bypass GlobalCurve in curve approximation #1096).
• Split CurveKind into SurfacePath/GlobalPath (see Interlude 2; addressed in Replace CurveKind with SurfacePath/GlobalPath #1081).
• Implement centralized object storage for GlobalCurves (see Implement lightweight, centralized object storage #1021; addressed in Implement centralized object storage #1108).
• Bypass GlobalCurve in curve sweeping (addressed in Bypass GlobalCurve in sweep algorithm #1111)
• Change GlobalCurve into a wrapper around a unique curve ID (see Proposal).

Bonus points for giving the same "wrapper around an ID" treatment to GlobalEdge, which is redundant with HalfEdge in similar ways that GlobalCurve is redundant with Curve. As far as I can tell, this isn't causing any problems right now though, but once centralized object storage is in place, it could be a nice simplification.

Unless anyone (maybe myself?) convinces me that a clever hack is the right solution to unblock the last item, I consider this issue blocked on #1021. Labeling https://github.com/hannobraun/Fornjot/labels/status%3A%20blocked.

[hannobraun]

Since this issue blocks #993, which blocks #42, which is my main priority, I'm assigning myself and adding it to the milestone.

[hannobraun]

Updated the list of action items in the issue description. Forgot one item (bypassing GlobalCurve) and another has been addressed in #1081.

[hannobraun]

In the issue description, I said under Problem 1 that the redundancy I described is not that problematic. Turns out, it's more problematic than previously known!

There are some bugs and limitations:

• The CurveBuilder methods that build lines are buggy. They just assume that the GlobalCurve needs to be a line too, regardless of the surface.
• It's impossible to represent a circle on a curved surface. The Curve/Surface part can do that, but GlobalCurve can't.

And I'm sure there's more. These are just some that I came across while working on this. If there was any doubt that this issue addresses a real problem, it's gone now!

[hannobraun]

Curve approximation is now bypassing GlobalCurve completely, going through Surface instead. I've updated the list in the issue description accordingly.

This is about as far as I can go here, without addressing #1021 first, so that's what I'm going to do next.

[hannobraun]

Centralized object storage for GlobalCurves has been implemented in #1108. This issue is no longer blocked on #1021.

[hannobraun]

Now that this issue is unblocked and I've restarted the work here, I'm finding more code that relies on GlobalCurve referencing GlobalPath. One thing I've addressed is bypassing GlobalCurve when sweeping a Curve (see #1111). I've updated the list in the issue description accordingly.

I'm sure there are more places in the code that need to be adjusted. I'll keep this issue updated as I find and address these.

[hannobraun]

I have a local branch that makes the suggested change to GlobalCurve, changing it into a wrapper around an ID value. This leads to a large number of test failure, which isn't surprising. The problem is the distinction between object equality and object identity. Objects can be equal (the data/objects they contain/reference is equal) without being identical.

Equality vs identity

Different pieces of code can create different objects at different times, and those object can end up equal. But, having been created in different places at different times, they don't have the same identity. This didn't make a difference for a while, because there simply was no way to track identity. Now, we have a centralized store, and equal objects can still end up being stored at different memory locations within that store, hence being not identical.

This is actually happening right now with GlobalCurve. But with the change to GlobalCurve being made, there no longer is any useful notion of GlobalCurve equality. With GlobalCurve wrapping an ID, non-identical GlobalCurves will also be non-equal. Lots of code doesn't expect this, hence the test failures.

Why identity is important

This might sound like a problem, but it's actually good, and an intended side effect of the centralized storage concept. Creating non-identical but equal objects works most of the time because floating-point arithmetic, despite all its problems, is still deterministic¹. However, it's still something I would like to avoid, because it could hide buggy code.

Recomputing equal objects in multiple places could work some of the time, given specific input, but then could stop working other times, given different input. We can avoid this completely, by just never recomputing equal objects, and instead providing a Handle to the already computed identical object instead. This is tedious, but I believe it will lead to a more robust CAD kernel.

So before I can merge my local branch, I need to change all that code that computes equal but non-identical GlobalCurves.

A slight change of plans

While working on this, I realized that the original plan can be simplified. By changing GlobalCurve to wrap a unique ID, and getting that ID from its Handle, we create two redundant ways of comparing GlobalCurves (comparing the IDs of their Handles vs GlobalCurve's Eq/PartialEq implementation), as I explained above. This is potentially confusing (what's the difference between the two exactly, if any?), as well as error-prone (both ways should be the same, but someone could change one of them without updating the other).

Instead, we can simplify:

• Don't have the new version of GlobalCurve wrap an ID. It's not necessary. If we want to compare GlobalCurves for identity, we use the ID of their Handles.
• Don't implement Eq/PartialEq for GlobalCurve, hence removing the redundancy.
• Turn GlobalCurve into a unit struct without anything in it (pub struct GlobalCurve;).

This might also be confusing (why can't I compare this using ==?), but that can be alleviated using documentation.

Footnotes

1. Well, floating-point arithmetic is deterministic in the ways we care about. Identical code with identical inputs will come up with identical outputs. It wouldn't be deterministic if differing hardware was involved, for example if you have shared state between networked computers, or a piece of code that could run on either a CPU or GPU. But that's not something we're confronted with in the kernel right now. ↩

[hannobraun]

I'm still working on addressing the new problems brought up by the distinction between object identity and object equality that I talked about in my previous comment here. So far, I've identified two main sources of these problems:

• The builder API.
• The transform API.

Both construct many duplicate objects that end up being equal, which will no longer be good enough in the new world where object identity is a thing. So far, I've worked on the builder API, but I actually believe that both APIs have the same solution: Introduce the notion of partial objects, parts of which can be provided by the caller or computed ad-hoc, depending on the use case.

This required a lot of thinking and experimentation, but I think my recent pull requests on that topic (#1133, #1134, #1135) are honing in on a design that should work.

[hannobraun]

That last round of pull requests has addressed lots of issues in the builder API. I can't be sure that all of them have been solved, as my local branch still has a million failing tests, but at least the ones I knew about are done now.

I've refocused my attention on the transform API. I have rough plan of attack involving the new partial object API, and I'm currently looking into that.

I've also identified another major source of problems: The unit tests. By design, they construct objects that are equal (but having been constructed by the unit test, of course not identical) to those constructed by the code under test, and compare them for equality. With the revamped GlobalCurveno longer supporting equality comparisons, and the objects referencing GlobalCurves resorting to identity comparisons instead, this approach no longer works.

I'm not sure how to solve that yet. Ideas I have include rewriting the unit tests to follow a different style, or introducing some test-only object wrapper that can compare objects using equality where available and ignoring identity.

[hannobraun]

Turns out that addressing the (known) problems in the transform API wasn't much of a problem, now that the partial object API is in place. As of #1152, I have a local branch that implements everything that's missing to finish this issue, runs without errors, and is down to 5 failing unit tests.

Fixing those failing unit tests is the next thing I'm going to work on. I'm not sure whether my idea for an identity-ignoring test-only object wrapper will work out, but given the low number of failing unit tests, it's probably possible to just refactor all of them, so they no longer trigger any object identity issues. I'm hopeful that I can wrap up this issue before the end of the week, and return to #993!

[hannobraun]

This has been fully addressed in #1153. The road for #993 should now be clear!