There is no way to determine whether two edges are equal

[hannobraun]

When dealing with edges in the kernel (instances of struct Edge, to be precise), there is no way to tell whether two edges are actually the same. This hasn't been a problem so far, but it is getting in the way of finishing some intersection algorithms I'm currently writing for #42.

This problem consists of multiple sub-problems:

1. Edge is defined in terms of local surface coordinates, and there is no GlobalEdge that could be used to determine whether two Edges are the same in global space. This is actually quite trivial to address (I have the solution in a local branch), but by itself, this doesn't help.
2. Edges are actually half-edges, as in, they are directed. So even if we had a GlobalEdge, we'd still be dealing with the problem that two GlobalEdges could be coincident, but still defined differently. This is related to Handle surface orientation in a simpler and more robust way #695.
3. The sweep algorithm produces Edge instances that are, in principle, the same, but they are defined differently. Both in terms of their local coordinates (which can't be avoided), but also in the direction of their global ones. The shared edge of two neighboring side faces isn't actually shared; it's basically two different edges that are coincident, but point in different directions.

The last problem is the most difficult, probably. The first two just require a bit of re-shuffling within the kernel code, but the creation of side faces in the sweep algorithm has been a problem again and again, since that algorithm exists. Fortunately time has gone on, and I have new ideas on how to finally do this right. I'll report back once I had the chance to do a bit of experimentation.

[hannobraun]

I'm currently working on this, as it's blocking #42 (which is my top priority).

[hannobraun]

I've been working on this for a bit, so here's an update: Sub-problem 1. from my original comment here has been addressed (#999). As I said, this doesn't do a whole lot by itself, and I'm still working on the other sub-problems.

I'd like to address #695, which is an attractive target not only because it would progress this issue, but also because it would allow for making curves and surfaces irreversible. Curves are only reversible because surfaces need to be, and surfaces are reversible because that's how we define face orientation. If #695 could be addressed, then the Reverse operation would no longer have to be defined on Curve and Surface.

This would have a simplifying effect on reversing the direction of Edges, which in turn would make some unit tests easier to write. (One of the sweep unit tests is disabled right now, because curve/surface reversal and the resulting changes to the surface coordinate system are making things harder than they need to be.)

However, if curves can't be reversed, then there's no way to reverse edges that have no vertices, as those are defined only by the curve. Fortunately, I have a solution for that (#1020). If all edges were bound by vertices, then the order of vertices would define edge direction just fine.

But this is currently blocked by the sweep algorithm doing all kinds of dodgy stuff, so I'm working on fixing that right now. The sweep algorithm also makes up sub-problem 3. from my original comment, so cleanup that up helps in two ways, and I've started doing that (first results in #1026). I have more cleanups in a local branch, but more work is needed to get the cleaned up version over the finish line.

[hannobraun]

I'm still working on #1020 as a means to progressing this issue. I've left an update there: #1020 (comment)

[hannobraun]

The sweep algorithm has been improved significantly, and #1020 has been addressed. This leaves item 2 (from the original issue description) as the only remaining item to be addressed.

I'm currently looking into whether it makes sense fix #695 outright to advance this issue, or if there's a more minimally invasive solution that I can apply.

[hannobraun]

#695 has been addressed now, which means everything from the list in the issue description is taken care of. Addressing this issue should be relatively straight-forward now.

I plan to change GlobalEdge so it normalizes the order of its vertices on construction, making it undirected. I already have this in a local branch, but it causes about a million test failures. Not sure what's going on, but I don't expect any deep problems. I'm out of time for today though, so I'll have to sort this out next week.

[hannobraun]

Turns out most of the test failures I was seeing last week had the same source and were easy to fix, but there's also a deeper problem: Normalizing the order of vertices when constructing a GlobalEdge is not enough. We also need to normalize the GlobalCurve it references somehow, or GlobalEdge can't be used to determine edge equality (as there could still be un-equal GlobalEdge instances for the "same" edge).

Thoughts on potential solutions:

• Normalizing the curve on GlobalEdge construction is no good. That would mean the half_edge.curve().global_form() and half_edge.global_form().curve() would no longer return the same GlobalCurve, which seems like a recipe for many bugs.
• Normalizing all GlobalCurves on construction is also no good. That would mean a Curve and its global form would no longer necessarily match (meaning, the same curve coordinates wouldn't result in coincident points). This seems like another nice breeding ground for bugs.
• Normalizing all curves (Curve and GlobalCurve) on constructions might be viable. It does seem icky though. It would certainly work for some of the simpler forms of curve constructions (for example, as happens when making a HalfEdge from two points), but I can totally see that being confusing in any non-trivial circumstance. The caller would have to be aware that any curve they construct is normalized and needs to take that into account when creating any curve coordinates at the same time. Again, a ripe source of bugs, potentially.
• Taking a step back, GlobalCurve is redundant anyway, and not really needed in its current form. It is used to approximate curves, but that could be done using Curve and the Surface it references instead. As luck would have it, I already thought about that a few days ago. GlobalCurve can't be removed, as I suggested in that linked comment, because we still need it to know if two curves are the same in 3D space (or we couldn't know if two edges are the same in 3D space). But GlobalCurve doesn't need to exist as a mathematical object, which would solve the problem at hand.

I'll spend some more time thinking and weighing the options.

[hannobraun]

I've done the thinking and weighing I said I would, and the result is #1079. I consider this issue blocked on that one now.

[hannobraun]

#1079 has been addressed. This issue is no longer blocked, and I will continue working on it now.