In my last article on the subject, I searched for an algorithm to sort translucent triangle meshes that ran in less than quadratic time. Sadly, on large organic meshes, the proposed algorithm didn't perform very well. In particular, when triangles in one continuous patch of geometry sort differently, the individual triangles of the mesh become visible, which is visually worse than not sorting at all.

Thus, I gave up on that approach and tried some others. If the algorithm has to be quadratic, then we have some options:

Topological Sort

First, build a digraph that represents whether a triangle should be rendered before another. A triangle A should be rendered before triangle B if A is in front of B and B is facing A but A is not facing B.

Once the graph is built, cycles must be broken, ideally using a heuristic that minimizes visual errors. (If a set of triangles form a cycle, there is no ordering that has no errors.) Finally, once all cycles are broken, the graph can be topologically sorted using a depth-first traversal.

This algorithm is O(n^2) in CPU and O(n^2) in memory.

Topologically sorting works well on geometric meshes with a clear triangle ordering. But on organic meshes, there are a great number of cycles, and the heuristic cycle breaking produces visual artifacts where individual triangles become visible.

Coverage Sort

For all pairs of triangles (A, B), if A is in front of B, calculate the form factor of A onto B. Form factor between triangles is fairly hard to calculate, so I tried a simple approximation using area of covering triangle, distance between triangle centers, and incident angles. Then, using a comparison sort, order the triangles such that triangles covered the most are first in the mesh.

This algorithm is O(n^2) in CPU and O(n) in memory.

I am not sure whether my heuristic was that good, but this also produced somewhat weak results on large organic meshes.

Sort by Distance and Angle to Center

This is a cheapo algorithm that works pretty well on convex shapes. Sort all triangles by the dot product of the triangle's normal vector and the vector from the mesh's center to the triangle's center.

It's pretty easy to come up with cases where this algorithm will sort incorrectly, but for most convex meshes it does well. More importantly, errors occur across entire slabs, which looks better than errors showing individual triangles.

Jon Watte's "Coverage Peeling" Algorithm

Jon's original algorithm works by building a graph of which triangles are in front of others, just like the topological sort above. It also accumulates a per-triangle-pair coverage metric, and accumulates them into a per-triangle coverage sum.

Then it peels triangles off, one at a time, by finding the triangle with the lowest coverage value. After peeling a triangle off, it reduces coverage values by the corresponding amount.

This algorithm works well, even in the presence of triangle cycles, but it has a fairly high constant factor. However, it runs out of memory on large meshes where the topological sort doesn't.

I still plan to see if I can get an implementation to complete on a 60,000 triangle mesh in a few seconds and under a few GB of memory.

Summary

Algorithm Time Complexity Memory Constant Factors Errors
Topological Sort O(n^2) O(n^2) Low Per-triangle
Coverage Sort O(n^2) O(n) Low Per-triangle
Distance and Angle Sort O(n lg n) O(n) Low Consistent regions of the mesh
Coverage Peeling O(n^2) O(n^2) High Per-triangle, but fewer than the other algorithms