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

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

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. In which case you shouldn't be seeing this problem.

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.