All posts by Kim Restad

Using bitmasks for draw call sorting

As we wanted our graphics engine to be completely separate from the rest of the code, we needed a way to be able to assure order independent draw calls. To do this, we queue every draw call made to the graphics and store it for later. The actual drawing then happens at one time during the frame as opposed to at the time when the draw call is made.

We decided to use a bitmask sorting system as a tool for batching our draw calls. Our method is inspired by the blog post by Christer Ericson (http://realtimecollisiondetection.net/blog/?p=86).

The idea is to pack every piece of information needed for a draw call into a single key.

In our case we use a 64-bit key to describe object type, mesh, material, depth etc. Other information, such as position, scale, and rotation, will be sent as a pointer along with the key to use with the actual rendering. We are using this key/value-interface for all draw calls to our graphics, including lights.

The values are stored in order of the most significant bit. If we want to sort mesh before material, we put the mesh bits in more significant bits than the material. By compiling the key this way, a simple sorting algorithm can then be used to sort all keys.

For example, imagine we want to sort our draw calls by mesh, and for each mesh we want to draw all instances with the same material together to minimize state changes. Sorting the bitmask keys before rendering will give us the result we want.

So why did we decide to use this method of sending draw calls?

Using this method allows us to have a relatively “dumb” renderer, i.e., a renderer with minimal logic and branching, making it faster as well as making it easier to maintain. It also works well with a data-oriented system.

As we started to implement bitmask sorting, we were surprised to see that it was such an easy system to extend. For example, as we implemented instancing, all that had to be done was pretty much skipping a few of the draw calls in the sorted list. This even applied for lighting, which was easily implemented using the same interface.