Polygon Depth Sorting

you definitely don''t want to have to do all the matrix multiplication yourself. you would totally miss out on the tnl capabilities of the hardware then.

there are probably a number of solutions, but here''s what comes to mind off the top of my head:

1) forget about sorting the polys per object. this is usually needed for correct alpha blending. most objects in the scene wouldn''t need to be alpha blended (presumably), so just use the z/wbuffer for depth, and put any polys you run across into a post draw list that is then sorted (insertion sort, or whatever your fav algo is)

2) if it absolutely has to be done, then you could sort the objects by depth, then when you draw each object, sort the polys based on the current world transform. again, off the top of my head, if it *had* to be done, then build a mini-bsp tree out of each model, then render the models from back to front, then for each model, render the polys by traversing the bsp tree from back to front.

not a nice straightforward solution, but if it has to be done...

if you''re running this on purely next gen hardware, then depth peeling may be another viable solution. see nvidia''s developer page and search for ''depth peeling'' for a nice paper/implementaion on it.

fyi, if you go the bsp route, you can keep static vertex buffers and send the indices down dynamically. you won''t incur a penalty, for afaik, no video card yet supports index buffers in vram.

and i''ve assumed you''re working with triangle lists, not strips or fans.

as always, if i knew more of the problem, i could probably recommend a better solution.

luck!

dedrick@whiteknucklegames.com

It just seems like too much work for the result to me sometimes...When I do all the transforms myself All the polys of the object are then in an easy to sort form...

it just always seems to me that I''m going to need the final transforms for the objects to sort them properly... I''m not sure if having an object Bsp would circumvent this... I''m assuming you would position the camera relative to the object space and do the bsp tree walk from that to get the face order of the object? That does sound like a more feasable solution... unless it''s a complex object that has moving parts or tweening or skinning, I''m guessing the Bsp approch wouldn''t work there...

another Idea I''ve had is to gat the distance from the camera point to the object''s individual faces for sorting... at first I thought this was a good idea.. but then I realized I''d need the object to be Pretranslated again... but now after that Bsp thought.. I''m thinking it might be possible to move the Camera point into Object space and do the sorting from that camera point... Do you think this idea has too much overhead compared to the Bsp method?

Regards
-Ximmer

well, if the easiest thing to do is to have the post transformed verts, and you''re not planning on having hundreds of thousands of polys on screen, then go for it. i have to ask, though, what are you doing that requires you have each polygon sorted from back to front?

the bsp approach would do just that - you would traverse the tree from back to front from the camera''s position in modelspace. having a bsp (assuming you do poly splitting at build time), assures you of the correct solution. and yes - tweening and skinning throw a wrench into the equation.

the problem with sorting the polys based on camera distance is that the distance can vary across the poly. i suppose you could use the centroid of the triangle or something as an estimate for the depth, and this method would get you a solution that my be good enough for your application, but it''s not guarneteed to be correct all the time. think of three tris, where 0 overlaps 1 which overlaps 2 which overlaps 0.

transforming all the polys by hand is going to have tremendous overhead. using the bsp method will work unless the object undergoes tweening or skinning, but will be very fast at run time. using the method you suggest will be slower than the bsp, much faster than the manual transform method, not guarentee correct results for static meshes, but can be adapted for skinned and tweened meshes.

for skinned or tweened, just apply the skinning or tweening, then test the distance to the camera in modelspace - no need to translate into world space. though depending on the situation, there may be very little penalty to do so. in other words, doing this may not be any better than transforming everything into world space.

also, if you''re not after the totally correct solution, you could just build the bsp in model space, and forget about the tweening and skinning. depending on how it''s built, it might not look all that bad.

if your bsp building algo is sufficiently fast, then you could even build the bsp anew every n-th frame, or even prebuild it for different configurations of the mesh.

this is really jsut the tip of the iceberg, too. there are dozens of other poly sorting algos out there, some dealing with depth ranges and splitting correctly without the use of a bsp tree.

this is a dirty can of worms, though. you have to ask youself if there''s a way around this. if this is for collision, use an approximation mesh, other parametric description of hulls, obb tree or something else. if this is for rendering, use the z/wbuffer. if everything is translucent, it might be faster to let the graphics card do multiple passes and depth peeling than do all the transforms on the cpu side.

if you could shed some more light on what you''re doing, maybe i could make some better suggestions.

dedrick@whiteknucklegames.com

I''m mostly trying to expand my knowledge of 3D rendering techniques as I have seen alpha blended models be used in a high number of comercial games... Quake3 and Mario64 immediatly come to mind. I''ve just had a very difficult time trying to figure out how this is accomplished well. Having no luck in finding tutorials or much info on the subject I came here looking for some insights...

I do have a game project that me and a friend are planning that will have to do with Polygon Depth sorting (Lot''s of Explosions and particles and other such effects)... but we can almost cheat on that one because the game is played on a 2D plane with the camera almost always based from above... But since the camera is tilted there may be visible artifacts that will appear if a cheap solution is used on this...

yet another problem is that when Objects intersect each other... but I really can''t think of any good way around this problem without turning the Z-Buffer off.. which is what I may end up doing... because I understand that to sort an entire scene is no good (Have already tried it) the Many Texture State Changes Just absolutly killed any chance of having even a mildly good framerate. and it''s probbably going to be difficult to draw an Explosion with a bunch of Blended Particle Sprites as if I draw the explosion first then Sprites underneath the explosion will vanish and if I draw the Sprites first peices of the explosion will vanish causeing unwanted effects...

Again I say Thank you for your very helpfull insight and knowledge into this subject.
-Ximmer

ahhh
ok - so this isn''t an atypical use. usually, the translucent polys are the exception, not the rule.

keep track of the translucent polys seperately than the main polys. for each model, render the opaque polys normally with the zbuffer (writing/checking) enabled, then add the translucent ones into a post draw list.

after rendering all the normal polys, render the translucent ones from back to front, with zwriting disabled, but zbuffering enabled.

for the sorting, a cheap approximation of the ''right'' solution usually works pretty well - using the distance from the camera to the centroid of the triangle.

also, if i''m correct, q3 actually treats the models as mini-bsps, though i may be totally off about that one.

hope this helps - lemme know if you have any more questions

dedrick@whiteknucklegames.com

if the model is convex, you simply draw it twice: first frontfaceculling, then backface culling. that "sorts" them in hw. now, even if the model is not convex, it solves most possible artefacts. if you need more, cut it into convex pieces.. no need to write vertexbuffers then..

"take a look around" - limp bizkit
www.google.com