# How do OpenGL ES 2 engines typically handle automatic geometry sorting and batching?

I'm trying to write a basic OpenGL ES 2 engine that can automatically sort and batch a fairly flexible set of input draw descriptions.

When I say 'draw description' I mean the actual uniforms, state, the shader, etc required to issue a single draw command for some geometry described by a vertex/index buffer.

When I say 'sort' I mean order a list of draw descriptions so that unnecessary state changes are minimized (ie. sort by surface, then shader, then texture, etc)

When I say 'batch' I'm specifically referring to merging draw calls by merging multiple vertex/index buffers that share the same draw description.

What I've tried

It seems like if you can sort a list of draw descriptions, you can batch as well because you can group draw descriptions that compare identical. So I thought I'd create something like:

std::map<DrawDesc,std::vector<Geometry>,DrawDescComparator>


std::map sorts the DrawDescs and I can stash geometry for identical draw descriptions in std::vector for batching.

However, I'm having trouble creating a draw description object that encapsulates all the required information, and specifically allows it to be compared.

Some things are easy to describe and compare, like a shader which can be assigned a unique id. Other things get complicated; to check if blend state is the same between two draw descriptions I'd have to look at (blend_enabled, equation_rgb, src_rgb, dst_rgb, equation_alpha, src_alpha, dst_alpha, and blend_color) in the worst case:

bool CompareBlendState(DrawDesc a, DrawDesc b)
{
if (!a.blend)
return true;

if (!b.blend)
return false;

if (a.equation_rgb != b.equation_rgb)
// just use the underlying gl_enums for a consistent comparison
return a.equation_rgb < b.equation_rgb;

if (a.src_rgb != b.src_rgb)
return a.src_rgb < b.src_rgb;

//...

if(a.etc != b.etc)
return a.etc < b.etc;

return false;
}


This is probably probably pretty inefficient. One possible way of making this nicer is storing blend state information in a std::bitset and just comparing the corresponding integer(s)

In general though, I feel like I may be barking up the wrong tree. There's way more state to compare (depth, cull modes, etc) and I don't want to create a difficult-to-maintain mess of code.

I'd like to know how other engines or libraries (unity, ue4, etc) typically handle this problem and if there's a common approach I've missed.

What you're doing may not be the most efficient, but it is still quite efficient, simple, flexible and commonly done. A more efficient, but code-wise more complex and less flexible solution would be to use different draw buckets' into which you put your drawables depending on the required state, e.g. you separate opaque from transparent meshes.

With your approach I suggest packing the draw description' into an integer. There is also no need for a tuple type (DrawDesc + geometry vector), just pack the geometry id right into that integer as well (what mesh needs to be drawn could be considered part of the DrawDesc, right?).

You should put the most expensive state changes into the higher bits and the least expensive ones into the lower bits. Then you can simply sort your data container using this number (simple "greater than" check, no branches, no structs). So you will get a scheme roughly like this:

typedef uint16_t DrawDesc; // may be 32 or 64 bits too)
std::vector<DrawDesc> drawables;

// put whatever info you need into this number, try to save bits.
// here: 5 shader bits (32 shaders), 9 mesh bits (512 meshes)
DrawDesc myDrawable = ((shaderID & 0x1f) << 9) | (meshID & 0x1ff);
drawables.push_back(myDrawable);

// Sort before drawing
std::sort(drawables.begin(), drawables.end());


You can now just iterate through the data container and count the consecutive elements that can be batched (and maybe cache the result somewhere).

Sadly std::map is one of the worst data containers the STL has to offer (memory allocations can occur, not as cache friendly as it could be, etc). But with this solution you can avoid a map anyway.

• Thanks for the answer. Storing shader, textures, blending, depth, cull, all into a single int seems limiting even if I used a uint64. Part of the larger problem I'm having with comparing state is dealing with the complexity of state that isn't just an id. I'll consider using a better container, but turning DrawDesc into an integer just moves the complexity of looking up the underlying data (shaders, etc) somewhere else.
– Pris
Feb 13 '15 at 14:40
• That's true, but you just do the lookup once per draw batch. Many uniforms become unnecessary when using uniform buffers (for normal matrix etc), further reducing the amount of information you need to store. Many of the more detailed attributes may be stored in a material which you look up with a material id. Here is a good article about this implementation realtimecollisiondetection.net/blog/?p=86 Feb 13 '15 at 16:45
• Also I wouldn't fret those lookups. Your material id, mesh id etc. will probably refer to another std::vector, so you have O(1) lookups and the ids will be sorted, so you can make proper use of prefetching (cache-friendly) Feb 13 '15 at 17:01