Rendering issues - some help?

[namida]

I'm wondering if anyone more experienced with 3D graphics (or perhaps just geometry / maths in general is enough) can help with ideas on how to improve the rendering.

The main problem here is around determining the order to draw block faces and other 3D-space elements in. Due to how L3D levels can have multiple block faces in the same position, a Z buffer is not an option - this leads to an awful level of Z-fighting, and can also lead to lemmings' graphics disappearing inside blocks when they're close to a block face (especially deflectors). Instead, we need to determine what order to draw the block faces in. (Optionally, we can also work out which ones don't need to be drawn at all, due to being outside the viewing area. However, not doing this only results in a performance penalty, not glitches, so this is not critical.)

The current build, orders these elements purely by the distance from the camera to a "key point". The key point is usually, but not always, the middle of the element's position in 3D space. In the case of a tie, it's broken by a defined priority order based on the element type (so for example, if a block face and a lemming have exactly the same key point - or different points that are the same distance from the camera - the block face will be drawn first, then the lemming).

Source code in a side branch (wip/rendering-fix-20220828) implements a different algorithm, which looks at every vertex of each element, and finds the one that when transformed into screen coordinates is furthest from the camera (including the depth) then uses this as the "key point". The other difference is that instead of determining position based on the entire key point at once, it determines it based only on the depth at first, using the other two axes as a tiebreaker only (if it's still a tie after this, it uses the same priority order as the existing algorithm to break the tie). This algorithm seems to have slightly fewer glitches, but those it does have tend to be more noticable.

I'm wondering if anyone has any better ideas here? I've taken several shots at it throughout Loap's development, and these two algorithms (the former of which has been the one used in virtually all released builds; the latter is a recent development and hasn't been included in any build yet) are the only ones that even come close to getting it right - most other things I've tried have felt like they should work, but  produce awful results when I actually implement and try them out. To be clear - what I really need is thoughts on the algorithm itself; once I have the right idea, I shouldn't have any difficulty coding it.

Also, just to avoid miscommunications - note that in Loap, the X axis is left to right, the Y axis is front to back, and the Z axis is bottom to top. (ie: the coordinates (1, 2, 3) would be 1 space to the right, 2 spaces "into" the screen, and 3 spaces upwards from the origin).

EDIT: Also, with regards to freedom of movement of the camera - the camera in Loap can move in any 3D direction, has a full 360 degree freedom of movement for the yaw, a -45 degrees to +45 degrees range of movement for the pitch, and no ability at all to roll.

[Simon]

This problem sounds like it must have a standard solution; the problem seems ubiquitous in 3D rendering. But I have no experience with 3D rendering. Therefore, I'll treat it as a puzzle. Let's see if I solve it sometime under the shower.

I make the following assumptions:

• Elements are always triangles or rectangles. In particular, every element is a subset of some 2D plane.
  
• Lemmings are not special either, they're rectangles with lots of transparency in the texture.
  
• Inner points of different elements never intersect. Boundaries of elements can intersect anything, even inner points, of different elements. E.g., a lemming can stand on anywhere on a floor rectangle. Wrong, see namida's attachment in next post.
  
• Given 2 elements, the desired output is always to paint one of them first entirely, then the other entirely. We never have to paint part of an element, then part of the other, then some more of the first. (Maybe it's even possible to prove this assumption, using that everything is a triangle/rectangle. For now, I'll just use it as an axiom.)
  
• The camera is a point in 3D space (that tells us where the camera is), plus a unit direction in 3D space that describes where it looks.
  

Indeed, the problem then reduces to defining a linear order (a.k.a. total order) on the set of elements so that the drawing "looks" good, and I can't yet point the finger on how to express that.

I conjecture that you don't need the midpoint or far point of the element. The midpoint gives me an idea though: Maybe something good comes from considering the angle relative to the camera, or, equivalently, do something with normal vectors (perpendicular to the element, and resting on the element; these always exist because the elements are 2D).

-- Simon

[namida]

Given 2 elements, the desired output is always to paint one of them first entirely, then the other entirely. We never have to paint part of an element, then part of the other, then some more of the first. (Maybe it's even possible to prove this assumption, using that everything is a triangle/rectangle. For now, I'll just use it as an axiom.)

Not always possible. Consider in particular a deflector block and a lemming, as attached. I have a gut feeling that the solution for elements such as lemmings (ie: those that are displayed as "billboards") is to only consider their center point on the X/Y axes (but still account for the entirity of their height) rather than the boundaries of their graphics, or at least something related to this idea.

[Simon]

Very good corner case, thanks.

It's a counterexample to how rectangles can intersect in arbitrary ways. But is it a counterexample to how one of the two gets painted first entirely, then the second? If we paint all elements in the deflector block first, and then the lemming on top, is that desired? Or do you want to hide the hand (that the lemming sticks inside the deflector)?

-- Simon

[namida]

But is it a counterexample to how one of the two gets painted first entirely, then the second? If we paint all elements in the deflector block first, and then the lemming on top, is that desired? Or do you want to hide the hand (that the lemming sticks inside the deflector)?

No - we would always want one or the other drawn in its entirity first. In general, I'm quite happy to accept corner case glithches occuring in situations that otherwise can only be resolved by partial drawing of one / both elements; this should be fairly rare anyway.

Note that in Loap:
- Seperate faces of a block can be drawn at different times; each face is its own element when it comes to rendering.
- A block is 1 unit wide x 1 unit deep x 0.25 units high (where a unit is the size of what would visually appear as a single block, or in other words, the size of a "block" by L3D's definition). Sprites on the other hand can be arbitrarily-sized, but in practice none are larger than 1 unit wide x 1 unit high (some are smaller).

Also worth noting - a lemming will almost always be at a half-block position on either the X or Y axis. The only time where a lemming can be at a position that is not the middle of the block in at least one (non-vertical) axis, is during the movement caused by a spring or rope slide. Or to put this a different way - at all times except when springing / rope sliding, it is guaranteed that at least one (and possibly both) of the lemming's X or Y coordinate, will be (n + 0.5), where n is any integer.

[Simon]

Okay, then I'll treat all elements as non-intersecting, in this sense: Given elements A and B, all points of the intersection of A with B are in the boundary of A or in the boundary of B or in both. Equivalently, the inner points of A are disjoint from the inner points of B.

Anything that violates this rule, we'll accept whatever glitchy behavior comes from it, and solve that later. One idea to solve it later is to compute the line of intersection of { the plane that contains A } with { the plane that contains B }, then cut both A and B along this line into two elements each, then apply the ordering algo (that we're still looking for) to the 4 parts instead of applying it to A and B directly.

Right, a block produces several elements that possibly get drawn at wildly different times.

-- Simon

[Simon]

Old version of next post (click to show/hide)

Let A and B be two 2D elements without intersecting inner points. We want to find out which to draw first entirely, then which to draw second.

Let EA be the infinite 2D plane that contains A.
Let EB be the infinite 2D plane that contains B.

Case 1: EA and EB are parallel.

Compute which of EA or EB is farther away from the camera C. (= Find the shortest vector VA between C and EA. The vector VA will be a normal vector of EA. The plane EA is farther if |VA| > |VB|.) Draw the element belonging to the farther plane first.

If their distances from the camera are the same, then EA = EB because they're already parallel. By assumption, A ∩ B are at most boundary points that we can ignore. Paint either A or B first, it doesn't matter. If you like, order A and B by distance of their midpoints from C.

Case 2: EA and EB are not parallel.

Then X = EA ∩ EB is a line.

The line X divides EA into two half-planes.

Let EAN ("EA near") be the half-plane of EA that contains the point of EA that's closest to the camera.
Let EAF ("EA far") be the other half-plane of EA.
Let EBN and EBF be likewise for EB.

It's possible that X contains the point of EA closest to the camera. In this corner case ignore EAN, EAF and work only with EBN, EBF.
(I'll continue later, no time now)

It's impossible for X to contain both the point of EA closest to C and also the point of EB closest to C. Proof: Assume otherwise. Consider the point of X itself that's closest to C. That point must then coincide with the point of EA closest to C (because we assume that to be in X) and with the point of EB closest to C (also by assumption). Take the vector VX that connects that closest point to C. Then VX is a normal vector to both EA and EB. Thus EA and EB are parallel. (They're the same plane even.) Contradiction because we're in case 2 of nonparallel planes. End of proof.

(More later what you should do with EAN, EAF, no time now.)

-- Simon

[Simon]

Here is the continuation from earlier this morning, but sadly, it omits an important case near the end. I'll post it nonetheless, maybe the ideas help you or others.

Input

Point C = our camera's location.
Triangle A = a textured element to draw.
Triangle B = another textured element to draw.

A and B share no inner points. (= All points in A ∩ B, if any, are in the boundary of A or in the boundary of B or in both boundaries.)

Clarifications (click to show/hide)

We're working in ℝ³, so triangles, planes, points, ... are subsets or elements of ℝ³.

A triangle is the convex hull of three pairwise-different points. Thus, triangles contain their corners and their edges, which together constitute the boundary of the triangle. An inner point of a triangle is a point of the triangle that is not in that triangle's boundary.

Distance means the Euclidean distance.
The distance between two points X and Y is
d(X, Y) = sqrt((x1-y1)² + (x2-y2)² + (x3-y3)²).

The distance between two subsets S1 and S2 of ℝ³ is
d(S1, S2) = inf(d(X, Y) : X ∈ S1, Y ∈ S2).

A distance vector from S1 to S2 of ℝ³ is a vector V with |V| = d(S1, S2) such that there is a point X ∈ S1 with X + V ∈ S2.

For arbitrary subsets S1 and S2 of ℝ³, distance vectors don't necessarily exist and are not necessarily unique. But all of our subsets of ℝ³ will be sufficiently nice (they're points, lines, triangles, planes, half-planes) so that the distance vector will always exist and will always be unique.

Task: Determine which of the two triangles, A or B, to paint first.

Plane EA = the infinite 2D plane that contains A.
Plane EB = the infinite 2D plane that contains B.
Vector VA = the distance vector from C to EA.
Vector VA = the distance vector from C to EB.

Case: VA = 0 or VB = 0 (zero visible area)

If VA = 0, then the camera C is contained in EA, and the camera would only see at a 1D degeneration of A with zero 2D area. Don't paint A altogether. Likewise, if VB = 0, don't paint B. (With software, maybe we should treat small nonzero |VA| < 0.001 as this edge case, too? I worry about artifacts from floating-point math in other cases otherwise. Experiment.)

For the remaining cases, we may assume that C is contained in neither EA or EB, therefore |VA| > 0 and |VB| > 0.

Case: VA/|VA| = VB/|VB| (Parallel Planes)

Equivalently: VA and VB are linearly dependent; one is a multiple of the other. In this case, we have parallel planes EA and EB. Paint the farther plane's triangle first: If |VA| > |VB|, paint A first. If |VA| < |VB|, paint B first. If |VA| = |VB| for the parallel planes EA and EB, you can paint either A first or B first, it doesn't matter.

Reason (click to show/hide)

Given parallel planes EA and EB, the edge case |VA| = |VB| can only happen in two ways.

Either we have VA = VB and thus EA = EB, then A and B won't overlap during rendering because we assume the points in A ∩ B are negligible boundary points.

Or we have VA = −VB, then the camera sandwiched exactly halfway between the parallel EA and EB. Here, the camera wouldn't render any overlap of the entire planes EA and EB whatsoever, thus we won't see any overlap between the particular subsets A of EA and B of EB.

Case: Nonparallel Planes



Line X = EA ∩ EB.
Vector VX = the distance vector from C to X.

This line X will halve the planes EA and EB into two half-planes each, making four half-planes in total. The main idea will be that, for at least one plane out of EA or EB, we can clearly label one of its two resulting half-planes as "the closer half-plane" and "the farther half-plane".

Theorem: Either |VX| > |VA| or |VX| > |VB| or both.

Proof (click to show/hide)

We have |VX| ≥ |VA| because X is a subset of EA. (|VX| < |VA| is not possible.)

If |VX| = |VA|, then the point of EA closest to C must lie in X, and this point is then also the point of X closest to C, again because X is a subset of EA. This closest point is C + VX = C + VA. Thus, if |VX| = |VA|, then VX = VA. Likewise, |VX| ≥ |VB|, and if |VX| = |VB|, then VX = VB.

It remains to show that |VX| = |VA| and |VX| = |VB| can't both be true.

Assume both are true. Then VX = VA = VB. The two planes EA and EB then have identical normal vectors because a distance vector to a plane is necessarily normal to the plane. Thus, EA and EB are parallel, even identical. But we're in the case of nonparallel planes, a contradiction. End of proof.

Without loss of generality, let |VX| > |VA|. (Otherwise, swap A and B.) Then the point in EA closest to C, i.e., C + VA, lies outside X. We can now let X divide EA into two half-planes, with exactly one of them containing C + VA.

Clarification (click to show/hide)

Since we don't care about boundary points of A or B, we don't care if X is part of either half-plane. The argument will be the same either way.

For sake of a sound definition, let's include X in both half-planes. Then the two half-planes aren't disjoint, their intersection will be X. Formally:

A half-plane H of a plane E is a subset of E so that there exists a bijection f: ℝ² -> E with H = f({(x, y) : y ≥ 0}) and that is affine (preserves straight lines, preserves parallel lines, is a translation plus a linear map).

Half-plane EAN ("EA near") = the half-plane of EA that contains C + VA.
Half-plane EAF ("EA far") = the half-plane of EA that does not contain C + VA.

If A is contained entirely in EAF, paint A first.
If A is contained entirely in EAN, paint B first.

Reason (click to show/hide)

Look again at the image from earlier:



X is the red line. The two planes EA and EB divide ℝ³ into four disjoint open 3D subspaces -- the air around the blue planes.

We know |VA| > 0 and |VB| > 0 from rejecting earlier cases, therefore the camera point C lies in one of the four open subspaces. What does the camera see from here? It sees a blue region that's part of one plane, then X, and then a different blue region that's part of the second plane. This holds no matter in which of the four subspaces C lies.

Now assume that EB is opaque. What part of EA does C see? It will see EAN -- all of it, even -- and it will not see EAF because the opaque EB blocks that completely.

Thus, if our triangle A is contained in EAN, paint B first, then paint A over B to show all of A. If A is contained in EAF, paint A first.

If A is neither fully contained in EAF nor in EAN, some inner points of A must intersect X.

Now it gets ugly, and I'll stop being exact. The idea is: If inner points of A intersect X, then inner points of B can still intersect X, but elsewhere in X at best. We have a nasty case analysis where we have to see if B appears above, below, left, or right of A. And by now, I doubt whether the approach so far (with EAN and EAF) is so fruitful afterall. If we can't kill this ugly case with my approach, we should probably find a new theory where this ugly case vanishes as just another standard case. I speculate that we can make progress by looking at the 3 corners of the triangle A and comparing them with the 3 corners of the triangle B.

-- Simon

[geoo]

The main problem here is around determining the order to draw block faces and other 3D-space elements in. Due to how L3D levels can have multiple block faces in the same position, a Z buffer is not an option - this leads to an awful level of Z-fighting, and can also lead to lemmings' graphics disappearing inside blocks when they're close to a block face (especially deflectors). Instead, we need to determine what order to draw the block faces in. (Optionally, we can also work out which ones don't need to be drawn at all, due to being outside the viewing area. However, not doing this only results in a performance penalty, not glitches, so this is not critical.)

I want to have a look at this problem, but I think I need some clarification to understand the issues with using a Z buffer (which then also affect face sorting):

• How is block faces in the same position an issue? I can see that happening when there are two adjacent blocks, but then their touching faces are obscured by other faces of these blocks and therefore not visible, so this seems to be a non-issue (also, in that case you see the front of one of them and the back of the other, so if you're doing back-face culling, you'd only draw one of them anyway. Note: If you compute the normal vector of a face so that it points out of the front side rather than back, you can determine whether you see the front or back face of the triangle by computing the scalar product of the normal vector with the vector where the camera is pointing, and skip drawing the back faces. Are you doing back-face culling, and if not, maybe it improves your results already?).
  
• I assume, as Simon is suggesting, lemmings are simply a quadrangle with a texture (that has some transparency)? If you have Z-fighting between a lemming and a terrain surface, couldn't you just always prioritize the lemming whenever the difference between the distances is very small (i.e. possibly caused by a rounding error)?
• Are there other instances of Z-fighting to consider?
• If you do have instances of Z-fighting because of faces being in the same location, then it seems to me that moving from Z-buffer to face ordering just moves the issue from pixel-level to face-level, i.e. on one frame you might see texture A, and in the next texture B.

Anyway, if you do want to do face sorting properly, it seems to me if you're doing pairwise comparisons for intersection like Simon is suggesting, you can then piece it together into a linear order by building a graph (the nodes are the faces, the edges are when a face is partially obscured by another face), and then doing a topological sort. (Note that in practice you might encounter cycles in this graph, e.g. if you have 3 triangles where each one obscures but also is obscured by another one.)

As for the comparisons (of say a convex polygon P and Q), I think the following should work assuming no cycles and intersecting faces:

• Compute the projections of P and Q into the viewing plane. Then check if these 2D polygons intersect. (I had this for pairs of triangles as a programming exercise once, it's a pain. It's not hard, but just a lot of cases. You could probably find this for pairs of triangles somewhere on the internet, and reduce the quadrangles to triangles. Or just check the bounding rectangles and hope for the best...) If they don't intersect, you're done: Don't add an edge to the graph, you can draw them in either order.
• If they do intersect in 2D: take an arbitrary intersection point (in the interior), compute the original points in P and Q that they are projections of, check which one is closer to the camera, and add an edge accordingly.

If you do have intersecting polygons, then either of them could end up on top with this strategy. (And of course, you will still have issues with cycles as well.)

I was looking up how people resolve this, and found Newell's algorithm, outlined in the last comment here: https://stackoverflow.com/questions/58367851/how-to-sort-these-lines-with-painters-algorithm

Basically, it does the sorting in a smarter way to resolve cycles along the way, and replaces my second point with the following (technically it adds more checks, but these are just for optimization):

• Are all points of P on the same side of the Q-plane, or are all points of Q on the same side of the P-plane? If either is true, you can determine which one is closer to the camera: e.g. if the points of P are on the same side of the Q-plane, and the camera is on the same side as well, then P is closer to the camera than Q, and you have to draw it later. (Otherwise it's the other way around.)
• If neither of the above holds, split the polygons.

Interestingly, even after all the conditional checks in Newell's algorithm where it decides to split the polygons, we still cannot conclude that P and Q intersect in 3D (I found a counterexample, see attached GeoGebra file).
Hopefully this should be rare, so instead of implementing splitting, maybe you can hope it doesn't happen

[namida]

A Z-buffer, when set "overwrite on less or equal" rather than purely "overwrite on less only", would work in theory (except for the corner case where when a lemming walks up against a wall, in particular, a lemming walking into a deflector block, part of the sprite would disappear into the wall).

In practice though, rounding errors end up causing issues. An example of where this might occur is, let's say we have two adjacent blocks, A and B. A is directly in front of B (from the camera's perspective), and they are touching. A's back face has a texture that includes transparent pixels, and is double-sided. (Note that alpha blending is not relevant; texture pixels in Loap are either fully opaque or fully transparent). Z-fighting will then occur between A's back face and B's front-face. It can also occur with the SIGN.xxx (and maybe WALL.xxx) graphics, if those are placed up against a block face.

Yes, back-faces are culled (unless they are double-sided). Additionally, so are "inside" faces in most cases (ie: if there are two blocks touching each other, such that the connecting faces are completely hidden by each other, those faces will be culled even if they're a front face). There are some cases where the algorithm to detect inside faces doesn't produce completely correct results (in particular, around the top face of the lower half of 22.5 degree slopes); in these cases, it simply errs on the side of caution and does not cull the face.

[namida]

Thinking of another possible approach (somewhat based on Simon's idea using planes) - let's suppose I can come up with a list of prerequisites (eg. face A must be rendered before face B, face B and C must both be rendered before face D) - what is generally the most efficient way to translate these requirements into an ordered list? Keeping in mind that two faces may be neutral with regards to each other, but a third face might need to be drawn inbetween them (eg: A and B have no order preference to each other, but A must be drawn before C while B must be drawn after C).

[Simon]

As a mathematician (not as an engineer), the instinct is to complete your relation into a partial order: Compute the transitive closure by repeatedly adding the forced pairs (if A < C and C < B, then add A < B to your relation) until you can't add any more. Then websearch for an algorithm about partial orders; the task is to find a linear order a.k.a. total order that contains your partial order.

But problem: I don't know if we're wasting too much algorithmic time by first computing the transitive closure. Maybe there is a better way to work directly with the nontransitive relation that you have, a way that will still come up with a suitable total order. It's probably enough to assume that the transitive closure (that always exists) would, if we were to compute it, be cycle-free (and thus be a partial order).

When websearching for algorithms, include "partial order" as a search term nonetheless, or "extend partial order into total order", maybe you find useful things that still work.

Ad hoc, I found:
Partial-Order Planning
Linear Extension of a partial order. This looks like pure math, but refers to algorithms in reference #5.

The next keyword to websearch from there is: Topological sort, or directly on wikipedia. (Starts to sounds like geoo or another computer scientist could have pointed us there much quicker. )

-- Simon

[geoo]

Thinking of another possible approach (somewhat based on Simon's idea using planes) - let's suppose I can come up with a list of prerequisites (eg. face A must be rendered before face B, face B and C must both be rendered before face D) - what is generally the most efficient way to translate these requirements into an ordered list? Keeping in mind that two faces may be neutral with regards to each other, but a third face might need to be drawn inbetween them (eg: A and B have no order preference to each other, but A must be drawn before C while B must be drawn after C).

The next keyword to websearch from there is: Topological sort, or directly on wikipedia. (Starts to sounds like geoo or another computer scientist could have pointed us there much quicker. )

Yep, that's exactly what I suggested a couple of posts ago x_x

Anyway, if you do want to do face sorting properly, it seems to me if you're doing pairwise comparisons for intersection like Simon is suggesting, you can then piece it together into a linear order by building a graph (the nodes are the faces, the edges are when a face is partially obscured by another face), and then doing a topological sort. (Note that in practice you might encounter cycles in this graph, e.g. if you have 3 triangles where each one obscures but also is obscured by another one.)

But back to Z-buffering and the Z-fighting issues that you had when using that approach: Why don't you make the blocks a tiny bit smaller (not enough to be visible, but enough to avoid z-fighting due to rounding errors) than a full grid unit?

[namida]

Yep, that's exactly what I suggested a couple of posts ago x_x

Yeah, I was asking more in terms of the specific algorithm rather than the general concept, sorry, should have been clearer. I recall looking this up before but not finding anything, but when I look again now, I found several suggested algorithms very easily. Not sure how I didn't find them before.

But back to Z-buffering and the Z-fighting issues that you had when using that approach: Why don't you make the blocks a tiny bit smaller (not enough to be visible, but enough to avoid z-fighting due to rounding errors) than a full grid unit?

I already considered this; no sufficiently-tiny "bit" exists. It becomes visible before the Z-fighting stops. A possible solution I saw to this was to render in multiple passes with a smaller Z range each, but I had already decided to abandon Z-buffering before trying this.

There are other advantages to a non-Z-buffer approach. In particular, the way a lemming is rendered when approaching the angled wall of a deflector block - while 3D rendering is still relatively new to me, I'm not aware of any way to reproduce this behavior while using Z-buffering (although I will concede that it's more of a "nice to get right" than a "critical" in the first place).

In terms of determining the prerequisites, I was thinking along the lines of the plane-based idea suggested earlier, but - I'm wondering, assuming that I'm not considering polygon-splitting, is there any advantage to calculating the intersections of the planes etc, as opposed to simply (where A and B are two elements, which may be two faces of the same block, faces of two different blocks, a face and a sprite, or two sprites - but NOT land, sea or sky graphics, or UI elements, as these are rendered seperately altogether):

Code: [Select]

1. Calculate the plane of face A.  In practice, at least for blocks, this would be calculated once at the start of the level and cached.
2. Check which side of A's plane the camera is on.
3. If all vertices of face B are on the same side of A's plane as the camera, set the result (but do not return it yet) to "A first". If they are on the opposite side, set the result to "B first". If they are mixed, set the result to "neutral".
4. Calculate the plane of face B.
5. Check which side of B's plane the camera is on.
6. If all vertices of face A are on the same side of B's plane as the camera, move the result one step closer to "B first" (ie: "A first" becomes "neutral", and "neutral" becomes "B first", while "B first" just remains as-is).
7. If the result is "neutral", defer to priority (ie: block faces are lowest priority [i]to be visible when graphics overlap[/i] and so are drawn first, overlays (WALL.xxx / SIGN.xxx graphics) are higher, objects even higher, lemmings are higher again, etc) to determine which one should be drawn first.

Special case: When checking the vertices, if the element is a sprite, only check two positions - the top and bottom at the center of it.
I've been thinking this over for a while and the only obvious downside I can see is that it will mark a lot of pairs of faces as having one that must come first, even when it actually doesn't matter. However, this would only result in a performance penalty, rather than a failure - it might be acceptable, would have to test (and possibly optimize) before I could say for sure.

[namida]

I've attempted this, and it seems to come up with a lot of cyclic dependencies - not yet sure why (could well just be a bug in my implementation). It works fine when dummying out all cases except for faces that are parallel (including that it produces the correct result), but yeah, not so well once non-parallel faces are compared.

It's also quite slow, but then, I haven't made much effort at optimizing it yet.