Validate face orientation of `Solid`s

[hannobraun]

The orientation of a face is defined by the winding of its exterior cycle. On the front side of the face, the exterior cycle is wound counter-clockwise. It is possible to create Solids where some or all of the faces face inwards, which would lead to invalid shading when displaying the Solid, and possibly invalid meshes when exporting it to an external file format.

This should be caught in a validation check, which makes sure that all faces of every solid point outwards.

[A-Walrus]

Some questions:

• Should we be checking that all faces of a Shell have the same orientation (which can be either inwards or outwards)?
• If a Solid has a cavity, what should be the orientation of the faces of the cavity?

[hannobraun]

Should we be checking that all faces of a Shell have the same orientation (which can be either inwards or outwards)?

Yeah, that makes sense! A mixed-orientation Shell would definitely be invalid (even though that's not specified anywhere right now), and having that check in place would then make the Solid check easier

If a Solid has a cavity, what should be the orientation of the faces of the cavity?

The cavity is "outside" of the Solid. So if you're sitting inside of the cavity looking at the solid, you should see counter-clockwise faces.

[hannobraun]

I've been looking into coordinate systems and cycle winding while working on #2098, and I found out that the situation is not as simple as I presented it in the issue description above. I said that the orientation of a face is defined by the winding of its exterior cycle, and that is simply wrong. The orientation of a face is defined by the combination of the winding and the handedness of the surface coordinate system.

To summarize:

• When looking at a face from the front (i.e. looking at a shell from the outside):
  • Winding must be counter-clockwise and surface coordinate system must be right-handed, or
  • winding must be clockwise and surface coordinate system must be left-handed.
• When looking at a face from the back (i.e. looking at a shell from inside the shell):
  • Winding must be counter-clockwise and surface coordinate system must be left-handed, or
  • winding must be clockwise and surface coordinate system must be right-handed.

All of that is highly confusing, and there is way too much code that must deal with this in too many places.

I hope that it might be reasonable to just require faces to just always be winded counter-clockwise and have a right-handed coordinate system (when looking from the front), but I don't know. It would require reversing the surface when reversing a face, and if you do that, then you have coincident faces that aren't on the same surface (because I've reversed it; it's a different surface now). Which would break all kinds of assumptions that the code currently makes, or might make in the future.

So yeah, I'm confused. I'll keep thinking about it, but for now, if anyone wants to address this issue, the overview above should at least provide the correct set of rules to validate the orientation of faces.

[felix91gr]

I hope these two cents are of a currency that works in this space >.<

If I recall correctly from class, the way face orientation is often coded for computer graphics purposes is by:

• First setting in stone a handedness for the coordinate system (there is one handedness that's used basically everywhere, but I forget which one of the two it is),
• Then, encoding the face orientation through the winding order of its vertices. If the winding coincides with the handedness of the coordinate system, the face is pointing outwards. If it isn't, the face is pointing inwards.

Basically what's done is that one of the two degrees of freedom is collapsed, and the other one is used to set the orientation.

---

Aside: there are other ways to orient faces, but the ones I know of require to add normal vectors to each vertex. To my eyes though, doing so seems unnecessarily wasteful in space for CAD, as well as numerically slightly less stable, than encoding face orientation in the winding order.

[hannobraun]

I hope these two cents are of a currency that works in this space >.<

I'll take them 😄

If I recall correctly from class, the way face orientation is often coded for computer graphics purposes is by:

[...]

Yeah, that's what I would like to do. It's what I meant above, where I wrote "I hope that it might be reasonable...".

To expand/clarify that, I know that this is a common approach in general, but there are problems with it within the context of Fornjot that would need to be addressed. Specifically, the way surfaces are handled.

The short version is, Fornjot tries to make geometric relationships explicit. Two faces aren't just allowed to be coincident. If they are, they must refer to the same surface¹. This is done to handle numerical inaccuracy, and there's some not-quite-up-to-date documentation about it.

So, the problem is, if I have two coincident faces that face in different directions, they must per this rule reference the same surface. But since the coordinate system is defined by the surface, one of the faces must, necessarily, have a left-handed coordinate system.

I'm not sure what to do about that. Maybe the rule about surfaces is not exactly necessary, and we can do without it. Maybe a surface can have two coordinate systems (so each side gets a right-handed one). Or maybe coordinate systems can be decoupled from surfaces completely. Right now, it's not clear to me what the solution should be.

Aside: there are other ways to orient faces, but the ones I know of require to add normal vectors to each vertex. To my eyes though, doing so seems unnecessarily wasteful in space for CAD, as well as numerically slightly less stable, than encoding face orientation in the winding order.

Yeah, I'd like to avoid that. I'd actually like to experiment with decoupling geometric and topological data from each other (which is a topic for another day; I'll open an issue about that when I can). Using normal vectors to define orientation would run counter to that.

Footnotes

1. Actually, as of now, they need not. At least I don't think it's a documented requirement, and it's certainly not enforced. But that's more of an artifact of the current implementation. Half-edges and curves work exactly like that (i.e. coincident half-edges must refer to the same curve), and that works very well. ↩

[A-Walrus]

Can you give an example where we might have coincident faces, cause I'm having a hard time coming up with one?

[hannobraun]

@A-Walrus

Can you give an example where we might have coincident faces, cause I'm having a hard time coming up with one?

Off the top of my head:

• When using a shape to modify another shape, for example when subtracting a cylinder from some other shape to create a hole. Knowing that the top/bottom of the cylinder are supposed to be coincident with the faces of the shell we're subtracting from, can make the difference in creating a correct triangle mesh (as opposed to closing a hole with a thin face, due to numerical inaccuracy).
• There are related cases that might not end up involving coincident faces, but where knowing the surface is important. Like when creating a rabbet in a piece of wood. If we model this by drawing a sketch on the top face, then doing a subtractive sweep, then we need to know that the side of the sweep (which might or might not end up being represented by a face, depending on how that will be implemented) is supposed to be in the same surface as the side of the wooden board.
• We'll end up with solids that touch each other in assemblies. We might still want to support exporting the whole assembly to a triangle mesh (if the user want to print it as a single piece). In that case, knowing precisely which faces are coincident allows us to know which walls to remove from the mesh (or not generate in the first place).
• This last one is speculative, but I have this idea of maybe simplifying the object graph a bit further by removing the concept of interior cycles, just leaving a single exterior cycle per face. That would mean faces with holes need to connect their inside and outside into a single cycle, which means we'll end up with an edge where the face touches itself. If we then sweep such a face we might (depending on how we implement it, if it happens in the first place) with a shell that touches itself in the same way.

None of this is a reality right now (see the footnote in my previous comment), but those are some cases where I assume that whole concept will become relevant (and as I mentioned in the footnote, half-edges/curves already work that way, to great benefit).

[hannobraun]

The validation code will most likely be replaced when the experimental architecture is merged back into the mainline code. This issue may still apply then (the experimental code has no validation code to speak of, so far), but I think it would be a waste of time to fix this before then.

Labeling as "blocked" until the experimental code is merged.