How do I Z-sort triangles for a 3D engine?

Question

I'm building a small 3D engine for a game I'm working on. I've got my basics sorted: textured triangles with backface culling. However depth sorting is proving to be a difficult problem.

I'm calculating the face Z by averaging out the 3 points that make up the triangular face. The longer faces sometimes overlap the smaller faces since they have a larger Z value and therefore rise up in the depth sorted display list.

How do I fix this? I'm sure there are known depth sorting techniques if I can only get some practical help in programming them. I've build the render pipeline myself so I have access to all the required data - triangles, points, textures, UV coordinates, etc.

Cathedral rendered in a 3D program

Cathedral rendered in my 3D engine

Answer 1

You need to subdivide your triangles so that they are all roughly the same size - regardless of whether you do the sorting yourself or employ a z-buffer. Unless, of course, the z-buffer algorithm also splits the long thin triangles up for you.

The problem is that if you've got some small compact triangles and some long thin ones (for example) the algorithm will miss classify the long thin ones more often than not. If you use the mid point of the triangle there will be view points where it will be regarded as "in front" of a more compact one when in fact if really is behind. Take this top down view where + represents the mid point.

            o

-+-            1
-----+------   2
         -+-   3

*

Looking from * to o the large triangle (2) could be interpreted as being in front of the small triangle (3) and hence be drawn on top of it.

If (2) was split into 3 or 4 smaller triangles then the z-buffering would work more of the time.

Answer 2

You choices are either to:

1. Subdivide your meshes so that you can sort each polygon reliably (but there are still horrible edge cases that you may or may not see).

2. Use a Z-Buffer, which is supported by all graphics hardware and is essentially free.

Answer 3

The corner case that complicates any triangle sorting algorithm is represented by the following diagram:

Each of the triangles is in front of one triangle and behind the other. I had to do some very simple tricks in inkscape just to create this diagram.

It is not hard to arrange polygons in 3D such that you have a cycle in the "in front of" graph. To solve this problem your algorithm would need the ability to subdivide the triangles to break the cycle.

This is one of the reasons Z buffers are so popular (that and they are easily accelerated in hardware).