I am working on finalizing my 3D engine, and I have one last thing to straighten out: z-depth sorting.
Currently my engine draws meshes with filled in polygons using the drawing API. The z-depth of the mesh’s faces is supposed to determine the order in which they are drawn on the screen (so that faces closer to the viewer are drawn last). Up until now, I have determined the drawing order in the following fashion (in pseudo-code):
:PSEUDO-CODE:
loop through each face to be drawn:
loop through each vertex of the face:
keep a running sum of z-depths of each vertex for this face.
end vertex loop.
push the z-depth sum for this face into an array of sums.
end face loop.
sort elements of the array of sums.
draw the faces in the order determined by the now sorted array of sums.
:/PSEUDO-CODE:
In most cases, this method works fine. However, in cases where a mesh contains a long stretched out faces, along with shorter faces, the method falters. I will give an example of a mesh consisting of only two faces, faceA, and faceB (faceA should overlap faceB) (z increases towards the viewer):
faceA vertices: 1:(x1, y1, 0) 2:(x2, y2, 100) 3:(x3, y3, 100)
faceB vertices: 1:(x4, y4, 80) 2:(x5, y5, 80) 3:(x6, y6, 80)
sum of z-depths of faceA’s vertices: 0+100+100 = 200
sum of z-depths of faceB’s vertices: 80+80+80 = 240
So faceB is drawn atop faceA, but in real life faceA should overlap faceB.
This is not a major problem since it only occurs rarely, and not at all if I watch my faces when I’m modelling so that none are too stretched out. But it is a flaw in my engine; one which I would be happier without. Any thoughts (or links) for a better z-depth sorting procedure?
On a related topic, I would like to include a module in my engine that will apply perspective to predrawn images that I want to represent in 3-space (like text, for example). The only hurdle I have to pass to implement this is z-depth sorting. Of course it’s much easier to determine true z-depth in this situation, but I would like to know if anybody knows how the built-in sort() method of the Array object compares to more traditional sorting methods (like the quicksort, for example). I would like to optimize my engine so that it doesn’t crawl at run-time so I’d like to use the fastest sorter I can find. Any ideas?
-Al
