You can find more information about the key/hash approach here: Order your graphics draw calls around!.

It seems like it is only practical to sort objects based on a couple properties. For example, say I am given a list of visible objects L.

I can choose how to sort or divide them. Say I divide them into three sub lists:

Sublist S1 = Opaque
Sublist S2 = AlphaTested
Sublist S3 = Transparent

I can then sort the first two in front-to back order, and the last in back-to-front order.

However, when I go to draw S1, there are additional properties that could be sorted (shader programs--e.g., skinned or not, normal mapped or not--textures).

Is this just a fact of life, and you just choose to sort based on the property that gives the best bang for your buck, or am I missing something?

It is only a fact based on how detailed you want to get. Now, sorting S1 front to back is pretty much a waste of time since it is opaque and you probably have a z-buffer (why wouldn't you anymore?), there is no sorting required. You "may" simply sort on shader/texture for this stage and if shader costs are high, do a z-prepass so shaders are only computed for visible pixels.

Alpha tested and translucent items get considerably more entertaining. I don't know that folks go to the levels I'm about to detail anymore but given that I did this in software rasterization at one point, sorting was MUCH more important. You can get back "some" of your shader/texture sorting abilities by doing an overlap sort in 3 dimensions. It's something like a culling exercise done in world and screen space.

Basically what you are doing is similar to the broad phase in collision detection. You want to sort the triangles into "islands" where only a subset of triangles/objects are overlapping and require any form of advanced work. Basically take the bounds of all the submeshes (in my system this means "per material" and in this case means with sorting enabled, implied translucent or alpha tested) and build groups of objects which overlap each other. This tells you which submeshes have triangles which can actually interpenetrate and need to be sorted and or even subdivided if you want absolute perfection. (Down side, a huge explosion particle system makes this VERY expensive, when don't huge things have problems though. )

Now sort the bounds projected to screen space on the x. You setup lists of objects which overlap on the x plane. Repeat for the y plane in screen space. What you have at this point is an interaction graph, well the start of one, which tells you which pieces can be rendered safely with or without merged material soups. Any object which is not in any of the overlap groups simply renders with it's own polys sorted against each other since it can have no interaction with anything else. Anything in the x/y groups but not in the world overlap groups can sort their tri's into a single draw call much like the prior but they have to be object level depth sorted (i.e. you don't need to merge the tri's of the various objects) with other objects and rendered back to front, but this needs to include the islands of world space overlapping objects as part of the order.

Basically after doing all the object bounds sorting, you end up with:
1. Objects which can be drawn completely independently and you can resort those for shader/texture etc freely.
2. Objects which overlap only in terms of painters algorithm which means you just sort front to back and do whatever is required in #1 to each object. I.e. sort the individual triangles for non-convex shapes or render back face/front face to avoid sorting etc.
3. The nightmare of poly soup is the remaining set of objects which physically overlap in world space. This is the bit you mention and no, can't think of a way to reduce draw calls if you want perfect sorting. Depth peeling and related items may be the only proper solution for these or cpu side tri-splitting etc.

Without diagrams this is difficult to describe and I'm sure my brief overview was probably confusing. To get a better explanation google up broad phase collision detection specifically involving sort and sweep variations. That covers how to maintain a quick "island" system. The overlaps in 2D space should all be pretty obvious, basically if the object doesn't overlap in both x and y, then it is independent and has no need of being sorted against other things.

[quote name='Quat' timestamp='1311196461' post='4838139']
It seems like it is only practical to sort objects based on a couple properties. For example, say I am given a list of visible objects L.

I can choose how to sort or divide them. Say I divide them into three sub lists:

Sublist S1 = Opaque
Sublist S2 = AlphaTested
Sublist S3 = Transparent

I can then sort the first two in front-to back order, and the last in back-to-front order.

However, when I go to draw S1, there are additional properties that could be sorted (shader programs--e.g., skinned or not, normal mapped or not--textures).

Is this just a fact of life, and you just choose to sort based on the property that gives the best bang for your buck, or am I missing something?

Basically after doing all the object bounds sorting, you end up with:
1. Objects which can be drawn completely independently and you can resort those for shader/texture etc freely.
2. Objects which overlap only in terms of painters algorithm which means you just sort front to back and do whatever is required in #1 to each object. I.e. sort the individual triangles for non-convex shapes or render back face/front face to avoid sorting etc.
3. The nightmare of poly soup is the remaining set of objects which physically overlap in world space. This is the bit you mention and no, can't think of a way to reduce draw calls if you want perfect sorting. Depth peeling and related items may be the only proper solution for these or cpu side tri-splitting etc.
[/quote]

I should mention that this is easily optimized and only sounds complicated when you don't really understand it. Start with the 2D case first and then add the 3D islands, it's not nearly as difficult as it sounds. (And rather CPU friendly with good GPU performance results.)

[quote name='AllEightUp' timestamp='1311208451' post='4838201']
Now, sorting S1 front to back is pretty much a waste of time since it is opaque and you probably have a z-buffer (why wouldn't you anymore?), there is no sorting required.

Front-to-back sorting of opaques is designed to take advantage of the hierarchical z-buffer, which can perform a coarse Z-test prior to executing the pixel shader. If you've got expensive pixel shaders, then this might help reudce your shading costs.

However, a common alternative is the z-pre-pass, where you render all your opaques first, only writing to the depth buffer (which is cheap), and then render them all again, this time actually using the real pixel shaders. This gives you the benefits of the hierarchical z-buffer, without having to use a front-to-back ordering.

Also, in a deferred pipeline, your objects themselves don't typically have expensive pixel shaders (the lights do), so front-to-back sorting probably won't help you that much.

So, with opaques, sorting by depth is designed to reduce GPU-side pixel shader costs, whereas sorting by state (e.g. by material) is designed to reduce CPU-side submission costs.
As with any optimisation, the best choice can only be made after measuring the characteristics of your particular situation.
[/quote]

I tend to ignore the hierarchical z buffers lately as the z-prepass trumps it in both performance and added abilities. The cpu cost and reordering of the batches just doesn't seem to give any benefit on recent cards in my testing. I do leave it as an option but just never turn it on anymore. This may be a side effect of my pipeline so your milage may vary.

[quote name='AllEightUp' timestamp='1311208451' post='4838201']Now, sorting S1 front to back is pretty much a waste of time since it is opaque and you probably have a z-buffer (why wouldn't you anymore?), there is no sorting required.

If you draw back to front then the z-buffer is useless. Everything will pass the z test if the geometry you are drawing is always in front of everything else. So sorting front to back is what actually allows you to take advantage of the z buffer.

Am I right?
[/quote]


Erm, my other left..... Yup, front to back ordering, not the other way around, would be the proper direction for opaque objects to get hierarchical z. Dislexia ftw.