I'm using OpenGL ES 2.0 right now on an Android game, but I think the ideas here apply to D3D stuff as well. What are the typical best practices when rendering scenes (particularly with sorting objects)? And how are these ideas best implemented (i.e. who sorts them (and when/how often) and stores them, and how are they sorted)?

To give you an idea of what I'm talking about, consider rendering a scene that uses multiple vertex and fragment shaders. Is it best to:

• Sort each object in the scene by the texture used first (so that those using the same texture are rendered sequentially so the texture can be reused)
  
• Then sort each object in the scene by the shader program (so that you don't have to call [font=courier new,courier,monospace]glUseProgram()[/font] (or the D3D equivalent) on every object in the scene)
  

Or is it better to do it the other way around (sort by shader program, then by texture)? Or are neither of these the best way to sort objects, and is there a better way to do it? I don't want to overcomplicate this and do too much work on the CPU, as it has other things it needs to do other than sorting objects in a scene.

When sorting these things, would the sorting be done in some [font=courier new,courier,monospace]scene[/font] object that stores references to all the renderable objects in the scene, sorts them, and draws them?

And finally, how can these ideas best be translated into a 2D game (I'm also curious about these answers for a 3D game though too)? In 2D games, the depth buffer is usually disabled, which makes the sorting/drawing order significant. There are so many transparent parts to textures and alpha blending going on that the order in which things are drawn need to be carefully controlled. Would you do the sorting above first, and then sort by layer number to ensure the correct drawing order? And if two sprites have the same layer number, you just have to make no guarantees about which will be drawn on top of the other (though you'd use a stable sorting algorithm, so that they don't alternate every frame which one is on top of the other)?

Sorry for the eleventy billion questions, but a huge thanks in advance for any responses!

Sort opaque objects by shader, then by texture, then if you want by depth (front to back). Transparent objects need to be sorted by depth first (back to front) in order for things to look correct, then by shader, then by texture.

Most of this information has come from http://lspiroengine.com/?p=96

I was actually hoping L. Spiro would reply, so thank you for that link, as it covers a lot of the stuff I was trying to get at!

Web383++

When sorting these things, would the sorting be done in some scene object that stores references to all the renderable objects in the scene, sorts them, and draws them?

For different materials/shaders use bucket sort.

In 2D games, the depth buffer is usually disabled, which makes the sorting/drawing order significant.

Why disable it ? When you have an order, you have some kind of indicator. Just assign this indicator to an according z-value, render the 2d sprites as simple quads (orthogonal projection) and utilise the z-buffer to do the sorting. But this will only work if you don't use transparency (i.e. alpha blended sprite edges).

There are so many transparent parts to textures and alpha blending going on that the order in which things are drawn need to be carefully controlled.

You can try to render each layer on a separate render target (is this supported by andriod hardware ?) and blend the whole layer on-top of each other (use stencil to minimise overdraw). I.e. a background layer (one shader, only opaque objects), a moving object layer, a fog layer (lot of alpha blended, unsorted sprites).

A few extended notes on what I said in my blog post.

#1: For PowerVR or other tile-based deferred rendering hardware, you do not, and I repeat do not want to sort front-to-back except where necessary for a proper effect (which is usually for alpha objects which instead requires back-to-front).
For these devices, you will notice a drop in speed if you add distance testing; it is nothing but overhead.

#2: Your sorting routine can slow you down rather than help you if not done correctly.
If you using something like the C-style std::qsort() which works with function pointers you will likely lose performance.
Here are the rankings based on my own tests. The % is the percent of speed without performing any sort at all, meaning anything below 100% is slower than having no sort.
* Top-Down Merge Sort C-Style: ~87%
* Quick Sort C-Style: ~95%
* Quick Sort Template: ~111%
* Insertion Sort Template: ~120%

I haven’t tested a bucket sort so I can’t compare it to a raw insertion sort. As long as you can easily take advantage of temporal coherence it could end up being a bit faster.
And I want to additionally say explicitly that temporal coherence is one of the most important factors here—insertion sort is slower than quick sort without it.
Also I want to reiterate that I sorted the indices of the “render queue items” instead of moving the actual items all over. This reduces copy bandwidth heavily.
Also you must use a stable sort. With quick sort, things flicker when they are on top of each other etc., meaning it is really only for benchmarks/comparisons and not practical for actual use anyway.

#3: For PowerVR and similar hardware, avoid dependent texture reads. There are many ways to accidentally cause reads to become dependent:
* If the texture coordinates are not used as-is (as they were sent from the vertex shader) in the fragment shader (including adding any offsets to them even if it is just for the read).
* Using anything but the x and y of the texture-coordinate vector causes dependent texture reads, so you can’t avoid it by packing one texture read into xy and another into zw.
* Check the hardware documents for your device for the rest of the list.
For 2D, the most likely place where this would happen is if you have any post-processing taking place. One way to handle it there is by determining all of the texture-coordinates in the vertex shader and you will be bound by the number of texture units available to use (unless you are willing to take the dependent-texture-read hit a little bit).

#4: If you have a lot of sprites you should not be using a bunch of small vertex buffers. Keep 2 buffers and fill one each frame (with only objects that are on the screen), swapping between them each frame to avoid hardware stalls.


L. Spiro

Sorry it's taken so long to reply... work has been hectic.

#1: For PowerVR or other tile-based deferred rendering hardware, you do not, and I repeat do not want to sort front-to-back except where necessary for a proper effect (which is usually for alpha objects which instead requires back-to-front).
For these devices, you will notice a drop in speed if you add distance testing; it is nothing but overhead.

Good to know. My current game is 2D (but this is useful for future stuff), so I'll disable distance testing all together. I only need to sort draw calls to make sure the right "layers" are drawn in order.

#2: Your sorting routine can slow you down rather than help you if not done correctly.

Yes, I figured; thanks for the stats though!

#3: For PowerVR and similar hardware, avoid dependent texture reads. There are many ways to accidentally cause reads to become dependent:
* If the texture coordinates are not used as-is (as they were sent from the vertex shader) in the fragment shader (including adding any offsets to them even if it is just for the read).
* Using anything by the x and y of the texture-coordinate vector causes dependent texture reads, so you can’t avoid it by packing one texture read into xy and another into zw.
* Check the hardware documents for your device for the rest of the list.
For 2D, the most likely place where this would happen is if you have any post-processing taking place. One way to handle it there is by determining all of the texture-coordinates in the vertex shader and you will be bound by the number of texture units available to use (unless you are willing to take the dependent-texture-read hit a little bit).

Interesting. Good to know. I shouldn't be modifying texture coords in my current game, but this is good for future stuff.

#4: If you have a lot of sprites you should not be using a bunch of small vertex buffers. Keep 2 buffers and fill one each frame (with only objects that are on the screen), swapping between them each frame to avoid hardware stalls.

Now that's an interesting idea. I suppose it only works if you enable depth testing or break the buffer filling/draw calls up by layer.

For different materials/shaders use bucket sort.

Thanks for that! I've used radix sorting but haven't ever used bucket sorting, so I'll check it out.

[quote name='Cornstalks' timestamp='1338912188' post='4946488']
In 2D games, the depth buffer is usually disabled, which makes the sorting/drawing order significant.

Why disable it ? When you have an order, you have some kind of indicator. Just assign this indicator to an according z-value, render the 2d sprites as simple quads (orthogonal projection) and utilise the z-buffer to do the sorting. But this will only work if you don't use transparency (i.e. alpha blended sprite edges).
[/quote]
That's an idea I had a while ago, and proposed it over at the SFML forums, but most sprites these days make use of alpha blending (for antialiasing the edges). If only I was working on an 8-bit retro game...

You can try to render each layer on a separate render target (is this supported by andriod hardware ?)

I have no idea... I'll find out, but even if I can't, it's an interesting idea for desktop games, so I'll have to remember that.

All that L. Spiro said about PowerVR is correct.


About sorting, you may keep your radix sorter, depending how it's implemented (8bits/11bits radices, w/ or w/o histogram, stable (+mem) or unstable (in-place)) it can be quite fast and depending on your dataset size you can even multithread it.
(8 bits radices, histogram and stable did it for me. Check "A Cache-Aware Hybrid Sorter" from GPU Gems 2 AFAIR for a good implementation.)