You don't need to do multiple sorts in order to sort by multiple criteria. For each criteria, you just need to be able to map it to an integer with N bits. So lets say you were sorting by shader and by texture. If you come up with a system that assigns a unique 16-bit ID for each shader and and a similar system for assigning a 16-bit ID for each texture, you could combine those two into a single 32-bit integer. When combining you just want the higher-precedence criteria to go into the higher bits, and the lower-precedence criteria into the lower bits. So in your case if you want to sort first by shader then sort by texture, you would do sortID = (shaderID << 16) | textureID. Then you just sort one using your combined sort ID.

Expanding on what MJP said (I just typed “MJ” and hit Tab hoping it would auto-complete the name).

• Do I need to check if a state is set before changing it?
  • It may not be necessary for things to work, but it is a major improvement on performance. It is heavily recommended, especially for shaders, textures, vertex buffers, index buffers, and render targets.
• 
  

  I use Quicksort3

  • Use an insertion sort and take advantage of per-frame temporal coherence.
  • Sort indices of items, not actual items themselves. Copying items back and forth is transfer overhead.
  • You should always restrict yourself to stable sorts for this type of sorting. Flickering artifacts on translucent objects can otherwise occur.
• 
  

  for sorting you have to perform a huge amount of sorts to make sure everything turns out ok

  • For completeness I am just going to reiterate that you don’t have to sort by all forms of criteria. The main ones are shaders, textures, and depth.
• 
  

  for automatic state monitoring you get tons of branching each time you render an object

  • Branching is faster than calling functions. Especially if those functions always go to ring 0 or cause pipeline flushes/stalls.
• 
  

  Maybe I should make some combination of the two?

  • They are meant to be used together. Sorting has no meaning if you are still calling Direct3D functions on each redundant state change, and preventing redundant state changes has no meaning if you are drawing in random order. Both are necessary.

Most of this is covered here: 3D Performance Tips


L. Spiro

do you mean an integer?

Yes.

Though my sortables always use more than that (try to at least fit it within a 64-bit integer though) plus the depth component, which is why I sort indices rather than the sortables themselves.

Why not just a direct pointer to the draw item?

Because what is used to sort is only a subset of what a mesh (or mesh part) actually is; sending a pointer to a mesh/sub-mesh off to a render queue means the render knows far more than it needs to know to do its job. All it needs is a small structure or key to use for sorting. Fill it out and send it one. Don’t create unnecessary dependencies.

Does the way they are depth sorted correspond to how the GPU draws them?

They are drawn in the order specified by your instance buffer. Except when drawing translucent objects, instancing is preferred over anything else as it implicitly means no shader swapping, texture swapping, vertex-buffer swapping, index-buffer swapping, etc. Any gains by drawing front-to-back on opaque objects is completely trumped by this, so ignore depth.

L. Spiro