the way to sort faces front-to-back

[MickeyMouse]

hi!

my problem is i want to make some really fast rendering. i disable depth buffer but then have to sort faces back-to-front to get correct effect...
..and i assume there're no 2 intersecting faces, so it's 100% possible to display them in correct order..
for most cases an algorithm sorting all faces by it's distance (distance from the center of it's bounding box or whatever) from the viewer origin is good, but there're some situations when it doesn't work like below
(there're 2 diagonal faces seen from the top and the viewer, dots are only tabs)

........../
.........//
........//
......./
....../
...../

..........*

in this case bigger face will be considered closer, although it should be drawn first, thus we'd be wrong doing simple sorting...

anyway for 2 faces it's easy to determine which should be drawn first by simply checking whether all A face vertices are in front of plane of face B...but using this kind of comparing function would be wrong, cause
A<B B<C doesn't mean A<C (< means should be drawn first)
thx for help

[This message has been edited by MickeyMouse (edited 03-22-2002).]

[This message has been edited by MickeyMouse (edited 03-22-2002).]

[This message has been edited by MickeyMouse (edited 03-22-2002).]

[Bob]

Depending on the layout of your scene, you might want to use a BSP tree, or something similar.

There is no general algorithm to sort arbitrary triangles in the correct order, that can handle all possible cases, even if you forget about triangels that intersects. Three mutually overlapping triangles (A overlaps parts of B, B parts of C, and C parts of A) is impossible to sort properly.

[Mazy]

Really fast? isn't the depthtest faster than sorting polyons in most cases, depending on the scene complexity and number of polygons ofcause, but i think a fast occlusion culling and then use the delpthbuffer will be faster than a polysort in the CPU.. ( not completely sure though..)

[MickeyMouse]

thx Bob
i forgot about situations like the one you described
now i see it's impossible to do it right unless i cut some faces, thus bsp should be good for this, but anyway this could be difficult to build bsp where every leaf has exactly 1 face...
asked about this cause i'm trying to implement mirrors in mirrors in....until certain level (for instance 7) - sometimes this never ends - so this could be faster not to write to depth buffer (hope so) but only sort small number of visible faces and draw them in good order

[harsman]

Before you go and devise a sorting algorithm to do this, please see how fast it is to just use the depthbuffer. Sorting roughly front to back and using depth testing usually leads to a speed increase on modern hw. I don't think the depth buffer is what's slowing you down. Profile, then optimize.

[MickeyMouse]

sure i'll try both, but having for example 5 big (1 fifth of screen) triangles, what should i write to depth buffer for? - it's so easy(not very easy as i see) to sort them and draw back-to-front....
i tested on my card voodoo2 that there really is significant difference between switched on/off depth buffer...however probably on not archaic cards(whatever != voodoo2 i fight with all the time) this may result in unnoticable difference.

[Bob]

You said in your second post, that you are trying to do something. Does that mean it does not yet work? If so, then skip optimization until it DOES work.

With an older card like the Voodoo, and with only 5 triangles, sorting them is probably better. But with newer cards, and with a huge scene, your sorting isn't going to work in practice anymore.

[Lev]

Here's an interesting thread on depth-test performance:
http://www.opengl.org/discussion_boards/ubb/Forum3/HTML/005776.html

-Lev