Z-Depth Sorting

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):

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.

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?


Did you check the link to Brandon Williams’ site in the best of Kirupa forum? I remember reading something about that there.

*Originally posted by ilyaslamasse *
Brandon Williams’ site

yes, its a must if you havent already - he knowns his schtuff (though I dont know which site in best of is referenced but no doubt it will be of help :))

Thanks guys. I can’t find any references to Brandon Williams in the BOK forum (except where pom refers to them in the “rotating a vector” thread). Can anybody pass me the link?


in http://www.kirupaforum.com/showthread.php?s=&threadid=10836

Trigonometry: http://home.velocitus.net/leroyclim...metry/index.htm
3D stuff: http://www.macromedia.com/desdev/mx...s/flash_3d.html
Math and physics (advanced): http://www20.brinkster.com/ahab/tutorials/mathindex.htm
Experimental: http://www.bit-101.com
Trigoometry (angles): http://www.actionscript.org/tutoria…_II/index.shtml

Check your links, Sen. They’re truncated so they lead to 404’s (except Bit-101). :slight_smile:

But thanks! I’ve actually been to a few of these already. Great resources!


the bolded one was the only important one, and I made sure that one was fully there in the post

the thread id of the thread where all the links were is visible too, something you can just throw in the url to make the change