Handle surface orientation in a simpler and more robust way

[hannobraun]

I've run into a problem while working on #691, and that problem is VerticesOfEdge::reverse. Simply put, I don't see a good way to translate this method to the new approach suggested in #691.

This could be seen as a problem with the new approach, but I don't think it is. That method is one component of the infrastructure for managing the direction of edges, which in turn is tied up with the way surface orientation is defined. That whole infrastructure is highly suspect. I'm pretty sure it won't hold up to future challenges, and I'm not even sure it's not subtly broken right now.

The purpose of this issue is to find a better solution. I'm not sure what a better solution would be, but I have ideas. I suspect that this is one of those cases where the act of properly explaining all the alternatives will make it clear which ones are viable. Let's hope I'll have my solution by the end of it.

How does it work currently?

Before I go into potential solutions, let's recap how surface orientation works in the first place, and why we care about the direction of edges (which is the most problematic part).

The answer is, we don't really care about edge direction. Not directly. What we do care about, is the orientation of triangles (defined by their winding) in the mesh that is generated from a model. If those triangles are not oriented correctly, that will cause two problems: First, incorrect shading in the graphics; second, invalid 3MF/STL files.

To get triangle orientation correct, we need to know the orientation of the surface they triangulate. Surface orientation is currently defined implicitly, through the coordinate system of the surface. If you're looking at the surface and see a right-handed coordinate system, you're looking at it from the outside.

Since the only type of surface supported right now, is one swept from a curve, the surface coordinate system is defined by the direction of the curve it was swept from (as well as the direction of the sweep, but the user will notice if we just change that). And since an edge needs to make sure its vertices are consistent with its curve, curve direction is inherently tied to edge direction.

So either, we replace the current edge direction infrastructure with something better, or we avoid it entirely, by tracking surface orientation in a different way.

Solution 1: Replace Edge with HalfEdge

Instead of the Edge object, have the HalfEdge object instead. In principle, an edge is undirected, and each edge is represented by two directed half-edges. Those half-edges reference each other, so instead of having to reverse the direction of an edge, you just reference its sibling half-edge instead.

The problem is the half-edges referencing each other, as that can not be accommodated by the current Shape infrastructure (nor any of the improvements I'm thinking about). I think having the half-edges stored in Shape will not pose a problem, but creating them will, as you need one to create the other, and the other way around of course.

While that doesn't seem hard to overcome, I don't see a good way to do so. All solutions I can think of will require the first half-edge to be created with a placeholder reference, which you then need to replace after creating the second half-edge. But I don't want to rely on the mutability of Shape even more (I'd like to go in the other direction instead, making Shape append-only).

The best idea I can come up with, is to somehow reserve space for both HalfEdge objects before creating them, then create the Handles that reference the reserved space, then create the HalfEdges using those Handles, then put the finished HalfEdges into the reserved space, completing the transaction. That would require supporting infrastructure in Shape, possibly in the form of an unsafe API.

Solution 2: Augment Edge with HalfEdge

Like solution 1, but instead of replacing Edge with HalfEdge, there'd still be an Edge that now references the two HalfEdge objects. You'd still need to be able to produce an HalfEdge instance's sibling, so HalfEdge would need a reference to its parent Edge. Now we're running into the same problem, just with extra steps.

In addition, if there's going to be some solution to create the reference loop as described above, it might be more complicated to involve multiple types of objects in that.

Solution 3: Add flags to indicate edge direction and surface orientation

Keep Edge directed, like it is now, but instead of reversing Edge itself as needed, have a bool flag in Cycle to indicate whether the direction of these edges should be considered reversed, for the purpose of this cycle. Set that flag where necessary (right now, that would be necessary for the interior cycles of an fj::Difference2d) and carry that flag forward into either Curve or Face, where it can be used during triangulation to make sure the required triangle winding is observed.

While that might work right now, it won't hold up for long. Let's consider a pyramid with three top faces that meet at the pyramid's top point. I've drawn those three faces here, projected into a 2D plane for clarity.

If we assume that each face's surface is defined by the direction of the bottom edge (those are the outside edges in my drawing), then the neighboring faces (or to be precise, their cycles) need to have different values of the reverse flag to make it work. Obviously can't work with three faces. I've marked the conflicting edge in yellow.

Solution 4: Keep a direction flag with each edge reference

Like in solution 3, Edges are still directed, but Cycle keeps a reverse flag with each edge reference.

So instead of this (simplified; not the actual code):

pub struct Cycle {
    pub edges: Vec<Handle<Edge>>,
}

We'd have something like this (again, simplified):

pub struct Cycle {
    pub edges: Vec<EdgeInCycle>,
}

pub struct EdgeInCycle {
    pub edge: Handle<Edge>,
    pub reverse: bool,
}

This way, the problem with solution 3 will be avoided.

I think this could work. When doing something like sweeping a face, each side face that is swept from an edge can directly copy the curve and the flag. The flag is then used during triangulation to ensure correct triangle winding.

Solution 5: Define surface orientation using a normal

All the solutions so far have focused on managing the edge direction in a better way. But what if we define surface orientation not by the surface coordinate system, but instead keep track of a surface normal that is independent of the coordinate system, and thus independent of edge direction?

Unfortunately, that doesn't break the surface orientation's dependency on the edge. For example, if we create the side face of a sweep, where do we get the normal from? We must get it from the edge we're sweeping, but while that may we well-defined through the edge's curve (e.g. a circle's normal always points outward), we still might need to invert the normal, if the edge is part of an interior cycle of the face we're sweeping.

Keeping track of whether the normal needs to be inverted is no different than keeping track of edge direction. Now add to that, that we can't just take the normal from the curve, but also need to take the direction of the sweep into account, and we're just doing the same thing in a more complicated way.

---

So, what's it going to be? I think of the solutions presented here solution 4 is viable. Solution 1 is too, if we can figure out the creation of the reference loop.

The way I see it, solution 4 has the advantage of most likely being implementable right now, without requiring any yet-to-be-determined new infrastructure that is potentially unsafe. Solution 1 has the advantage of a simple elegance. No maintaining interrelated flags on multiple types and checking them during triangulation, just using the sibling HalfEdge where that is needed.

Not sure what I want to do yet, but at least I have 2 potential solutions with clear trade-offs now.

[hannobraun]

In the Matrix channel, Nick Hemsley recommended this crate: https://github.com/asny/tri-mesh/tree/master

Looks potentially useful. Definitely worth a closer look, before going ahead with this issue.

[hannobraun]

Since I opened this issue, a lot of cleanup has happened, most importantly #697. With the new, simpler structure, implementing VerticesOfEdge::reverse should still be feasible, even with the approach proposed by #691, which means the original motivation for addressing this issue now is probably no longer there.

I think having an approach based on half-edges would still be nicer than what we have now, but it's probably no longer beneficial to try and address this now. I'll go back to working on #691 instead, and leave this issue for a later time.

[hannobraun]

I've started working on this, as a means to advancing #993. I've gone with solution 1, and already have a mostly-working version. Still fiddling with some details to make it work correct, which might actually make up most of the work 😄