More thoughts on transparent depth sorting

[Frank C <li...@si...>]

Since James has recently put a lot of work into new sorting algorithms 
I thought this may be a good time to throw a around a few more ideas on 
the topic.

I think the current method of lumping all transparent triangles into a 
single list may not be the best way to go about it. I'm no sort 
algorithm expert but I believe it would be faster sort the triangles in 
each mesh separately, then sort and draw each mesh as a whole rather 
than sort all triangles in all meshes simultaneously. Meshes with 
intersecting bounds would have to have their triangles lumped into the 
same list, but the fact that intersecting triangles aren't split means 
this scenario will rarely work no matter what sorting method is used. I 
suppose which method is faster depends on wether sorting a big list of 
triangles is faster than detecting intersections.

When sorting by mesh, there should also be some of way of flagging 
meshes to allow fast self-sorting paths:

1. A "no sort" flag can be used on objects that require absolutely no 
self-sorting; e.g. billboards, or meshes that use additive blending.

2. A "convex" flag can be used for meshes with convex hulls so they can 
be drawn quickly with the draw-backs-draw-fronts method (Quesa's 
primitives will qualify for this more often than not - all the box 
self-sorting problems instantly disappear).

3. I almost hesitate to mention this third sorting method since it's 
rather specific, but meshes with mostly-solid textures can sometimes be 
sorted acceptably in two passes. The first passes uses an alpha test 
that clips to solid (or near-solid) with z writes enabled and colour 
turned off. The second pass draws the colour with blending enabled and 
z writes off. The result may/will show depth errors at texture fringes, 
but this is often an acceptable tradeoff for complicated structures 
like branches/leaves/grasses without resorting to using 1 bit alphas. 
This technique has no doubt been described more elegantly elsewhere but 
I usually call it a "texture based depth sort".

Basically it comes down to this:

Step 1: Sort transparent meshes back-to-front, lumping intersecting 
meshes into a single group/mesh.

Step 2: Draw each mesh in the sorted list using one of the 3 methods 
listed above, or if all else fails do a per-triangle sort.

Just some ideas - feel free o shoot'em down.
Frank.