In the previous part of this series, I’ve talked a bit about how to design the stateless rendering API, but left out a few details. This time, I’m going to cover those details as well as some questions that came up in the comments in the meantime, and even show parts of the current implementation.

Command buckets

In the first part of the series, I introduced the idea that not all layers need to store keys of the same size, e.g. a layer for rendering objects into a shadow map might only need a 16-bit key, while the G-Buffer layer requires 64-bit keys.

In Molecule parlance, the thing responsible for storing draw calls (and their associated key and data) is called a CommandBucket, which is a light-weight class template taking the key-type as a template parameter:

template <typename T>
class CommandBucket
{
  typedef T Key;
  ...
};

A renderer would create all the CommandBuckets it needs for rendering the scene, and e.g. store them as members, populating them with draw calls in its Render() method. Or you could make creation & destruction of the CommandBuckets completely data-driven and configurable.

But what does a CommandBucket need to store, and how do we store it?

• N keys that are used for sorting the N draw calls
• Data for N draw calls

Note that the amount and type of data stored for each draw call heavily depends on the type of draw call. Therefore, all data needed by a draw call is stored in a separate memory region, and the CommandBucket only stores a pointer to that region:

template <typename T>
class CommandBucket
{
  typedef T Key;
  ...

private:
  Key* m_keys;
  void** m_data;
};

Note that the keys and their data are stored in two separate arrays. The reason for that is that certain sorting algorithms don’t swap during the sort operation but rather populate a separate array with indices to the sorted entries, so they have to touch less data.

When creating a CommandBucket, it takes care of allocating the arrays of keys and data pointers, and also stores all the render targets as well as the view matrix, projection matrix and viewport to be used when submitting the commands stored in that bucket. The rationale behind this is that it is very likely that you render into a certain layer using the same camera & viewport, so it makes no sense to specify that information in each and every draw call. Furthermore, this means that each CommandBucket can only hold a certain number of draw calls, specified when creating the bucket like in the following example:

CommandBucket<uint64_t> gBufferBucket(2048, rt1, rt2, rt3, rt4, dst, viewMatrix, projMatrix);

Of course, the view and projection matrix would most likely be provided by a camera object, or some kind of camera system – but that is an entirely different topic.

Commands

Now that we have buckets for storing draw calls, how do we add commands to a bucket? And what exactly is a command?

A command is a self-contained piece of information that is understood by the render backend, and is stored in a command bucket. A command could identify any kind of draw call (non-indexed, indexed, instanced, …), or any other operation such as copying data into a constant buffer.

Each command is a simple POD that holds all the data needed by the backend in order to carry out the operation associated with a certain command. The following three structs are all examples of simple commands:

namespace commands
{
  struct Draw
  {
    uint32_t vertexCount;
    uint32_t startVertex;

    VertexLayoutHandle vertexLayoutHandle;
    VertexBufferHandle vertexBuffer;
    IndexBufferHandle indexBuffer;
  };

  struct DrawIndexed
  {
    uint32_t indexCount;
    uint32_t startIndex;
    uint32_t baseVertex;

    VertexLayoutHandle vertexLayoutHandle;
    VertexBufferHandle vertexBuffer;
    IndexBufferHandle indexBuffer;
  };

  struct CopyConstantBufferData
  {
    ConstantBufferHandle constantBuffer;
    void* data;
    uint32_t size;
  };
}

Because each command is a separate POD, putting them into a command bucket becomes simple. We can add a method that takes a key, makes space for storing the command, stores the pointer to the data in the internal array, and hands the POD instance to the user:

template <typename U>
U* CommandBucket::AddCommand(Key key)
{
  U* data = AllocateCommand<U>();

  // store key and pointer to the data
  AddKey(key);
  AddData(data);

  return data;
}

This is still really simple, but there are also a few bits we haven’t talked about yet, such as adding synchronization when accessing the arrays, and how to allocate memory for the command. We will revisit this topic later, because for now there are more important things we need to talk about first.

For now, assume that we have a command bucket which we populate in the following manner:

for (size_t i=0; i < meshComponents.size(); ++i)
{
  MeshComponent* mesh = &meshComponents[i];

  commands::DrawIndexed* dc = gBuffer.AddCommand<commands::DrawIndexed>(GenerateKey(mesh->aabb, mesh->material));
  dc->vertexLayoutHandle = mesh->vertexLayout;
  dc->vertexBuffer = mesh->vertexBuffer;
  dc->indexBuffer = mesh->indexBuffer;
  dc->indexCount = mesh->indexCount;
  dc->startIndex = 0u;
  dc->baseVertex = 0u;
}

Compared to the two alternatives presented in the last post, note that there is no need for calling another method after a draw call has been created and inserted into the bucket. After calling AddCommand(), the command completely belongs to you, and you simply fill all its members. That’s it. All store operations would write directly into one contiguous chunk of memory, without any additional copy operations – but more on that later.

The command bucket responsible for draw calls contributing to the G-Buffer now holds an indexed draw call for each mesh component. After all buckets have been populated, we can sort them by their keys:

gBufferBucket.Sort();
lightingBucket.Sort();
deferredBucket.Sort();
postProcessingBucket.Sort();
hudBucket.Sort();

For sorting the commands in the bucket, we can use whatever sorting algorithm we want. The one thing to note here is that each CommandBucket::Sort() can be run on a different thread, sorting all buckets in parallel.

After all buckets have been sorted, we can submit them to the render backend:

gBufferBucket.Submit();
lightingBucket.Submit();
deferredBucket.Submit();
postProcessingBucket.Submit();
hudBucket.Submit();

The submission process has to be done from one thread because it constantly talks to the graphics API (D3D, OGL), submitting work to the GPU. It does not matter whether it is the main thread or a dedicated rendering thread, though.

Submission process

But how do we submit the commands to the graphics API? All we have is a key and a pointer to the associated data. This is clearly not enough, so we need some kind of additional identifier for each command.

One way of implementing this would be to add an identifier (e.g. an enum value) to each command, store it alongside the key and data, and then implement the Submit() method similar to the following piece of code:

void Submit(void)
{
  SetViewMatrix();
  SetProjectionMatrix();
  SetRenderTargets();

  for (unsigned int i=0; i < commandCount; ++i)
  {
    Key key = m_keys[i];
    void* data = m_data[i];
    uint16_t id = m_ids[i];

    // decode the key, and set shaders, textures, constants, etc. if the material has changed.
    DecodeKey();

    switch (id)
    {
      case command::Draw::ID:
        // extract data for a Draw command, and call the backend
        break;

      case command::DrawIndexed::ID:
        // extract data for a DrawIndexed command, and call the backend
        break;

      ...;
    }
  }
}

This would be a possible solution, however I would not recommend it. Why?

First, we kind of do the same thing twice. We once identify the command when storing it into the bucket (e.g. by storing U::ID into our array of IDs, m_ids), and then identify it again in the huge switch statement.

Second, the hardcoded switch statement makes it hard and tedious to add new commands, and impossible to add user-defined commands if we don’t have access to the source code.

There is a better and simpler solution: function pointers.

Backend dispatch

Instead of storing the ID of a command in the bucket, we can directly store a pointer to a function that knows how to deal with a certain command, and forwards it to the render backend. This is what is known as the Backend Dispatch in Molecule.

The backend dispatch is a namespace that consists of simple forwarding functions only:

namespace backendDispatch
{
  void Draw(const void* data)
  {
    const commands::Draw* realData = union_cast<const commands::Draw*>(data);
    backend::Draw(realData->vertexCount, realData->startVertex);
  }

  void DrawIndexed(const void* data)
  {
    const commands::DrawIndexed* realData = union_cast<const commands::DrawIndexed*>(data);
    backend::DrawIndexed(realData->indexCount, realData->startIndex, realData->baseVertex);
}

  void CopyConstantBufferData(const void* data)
  {
    const commands::CopyConstantBufferData* realData = union_cast<const commands::CopyConstantBufferData*>(data);
    backend::CopyConstantBufferData(realData->constantBuffer, realData->data, realData->size);
  }
}

Each function in the backend dispatch has the same signature, hence we can use a typedef to store a pointer to any of those functions:

typedef void (*BackendDispatchFunction)(const void*);

The functions contained in the backend namespace are still the only ones that talk directly to the graphics API, e.g. by using the D3D device.

So let’s go back and revisit the CommandBucket and its AddCommand() method. In addition to the command, we now also need to store a pointer to the dispatch function. Actually, we also need to store two more things we haven’t talked about yet in addition to the above:

The first is a pointer to any other command that needs to be submitted with this command and has the same key. If we store a pointer to another command we build an intrusive linked list that allows us to handle draw calls and commands that always need to be submitted in a certain order, no matter what key was assigned to them. This came up more than once as a question in the comments, and is needed when submitting draw calls where we e.g. first need to copy data to a constant buffer, and then submit the draw call. The intrusive linked list allows us to chain any number of commands.

The second is that certain commands need auxiliary memory to store intermediate data that is needed when submitting the draw call to the API at a later point in time. The perfect example for this is updating a constant buffer with a few bytes of data, such as e.g. lighting information. These bytes are tucked away in the auxiliary memory, and copied from there into the constant buffer when the command is submitted.

Command packets

Because we no longer just store single commands in the bucket, we introduce the concept of command packets. A bucket now stores command packets, and each packet holds the following data:

• void* : a pointer to the next command packet (if any)
• BackendDispatchFunction : a pointer to the function responsible for dispatching the call to the backend
• T : the actual command
• char[] : auxiliary memory needed by the command (optional)

Whenever the user wants to add a command of type T to the bucket, we need to make space for the other things as well. For that, I simply allocate raw memory which is large enough to hold all the data using appropriate sizeof() operators, and cast the individual parts to their desired type. In order for that to work, a few static_asserts ensure that all commands are POD structs.

Finally, a helper namespace takes care of doing all the offset calculations and casting:

typedef void* CommandPacket;

namespace commandPacket
{
  static const size_t OFFSET_NEXT_COMMAND_PACKET = 0u;
  static const size_t OFFSET_BACKEND_DISPATCH_FUNCTION = OFFSET_NEXT_COMMAND_PACKET + sizeof(CommandPacket);
  static const size_t OFFSET_COMMAND = OFFSET_BACKEND_DISPATCH_FUNCTION + sizeof(BackendDispatchFunction);

  template <typename T>
  CommandPacket Create(size_t auxMemorySize)
  {
    return ::operator new(GetSize<T>(auxMemorySize));
  }

  template <typename T>
  size_t GetSize(size_t auxMemorySize)
  {
    return OFFSET_COMMAND + sizeof(T) + auxMemorySize;
  };

  CommandPacket* GetNextCommandPacket(CommandPacket packet)
  {
    return union_cast<CommandPacket*>(reinterpret_cast<char*>(packet) + OFFSET_NEXT_COMMAND_PACKET);
  }

  template <typename T>
  CommandPacket* GetNextCommandPacket(T* command)
  {
    return union_cast<CommandPacket*>(reinterpret_cast<char*>(command) - OFFSET_COMMAND + OFFSET_NEXT_COMMAND_PACKET);
  }

  BackendDispatchFunction* GetBackendDispatchFunction(CommandPacket packet)
  {
    return union_cast<BackendDispatchFunction*>(reinterpret_cast<char*>(packet) + OFFSET_BACKEND_DISPATCH_FUNCTION);
  }

  template <typename T>
  T* GetCommand(CommandPacket packet)
  {
    return union_cast<T*>(reinterpret_cast<char*>(packet) + OFFSET_COMMAND);
  }

  template <typename T>
  char* GetAuxiliaryMemory(T* command)
  {
    return reinterpret_cast<char*>(command) + sizeof(T);
  }

  void StoreNextCommandPacket(CommandPacket packet, CommandPacket nextPacket)
  {
    *commandPacket::GetNextCommandPacket(packet) = nextPacket;
  }

  template <typename T>
  void StoreNextCommandPacket(T* command, CommandPacket nextPacket)
  {
    *commandPacket::GetNextCommandPacket<T>(command) = nextPacket;
  }

  void StoreBackendDispatchFunction(CommandPacket packet, BackendDispatchFunction dispatchFunction)
  {
    *commandPacket::GetBackendDispatchFunction(packet) = dispatchFunction;
  }

  const CommandPacket LoadNextCommandPacket(const CommandPacket packet)
  {
    return *GetNextCommandPacket(packet);
  }

  const BackendDispatchFunction LoadBackendDispatchFunction(const  CommandPacket packet)
  {
    return *GetBackendDispatchFunction(packet);
  }

  const void* LoadCommand(const CommandPacket packet)
  {
    return reinterpret_cast<char*>(packet) + OFFSET_COMMAND;
  }
};

Note that Create() uses the global operator new for allocating raw memory. In a real implementation, we would use our own linear allocator that ensures that all commands are stored in memory contiguously, which is much more cache-friendly when we need to iterate through the commands in the Submit() method.

Revisiting the command bucket

With command packets in place, the actual code for adding commands to a bucket becomes the following:

template <typename U>
U* AddCommand(Key key, size_t auxMemorySize)
{
  CommandPacket packet = commandPacket::Create<U>(auxMemorySize);

  // store key and pointer to the data
  {
    // TODO: add some kind of lock or atomic operation here
    const unsigned int current = m_current++;
    m_keys[current] = key;
    m_packets[current] = packet;
  }

  commandPacket::StoreNextCommandPacket(packet, nullptr);
  commandPacket::StoreBackendDispatchFunction(packet, U::DISPATCH_FUNCTION);

  return commandPacket::GetCommand<U>(packet);
}

Once we take care of the TODO marked above, we can also start adding commands from any number of threads. As a first implementation, we can simply add a critical section to make the code work, but obviously there are better solutions, which is something I would like to write about in one of the next posts in the series.

Of course, each command now also needs to store a pointer to the backend dispatch, exemplified for the draw command:

struct Draw
{
  static const BackendDispatchFunction DISPATCH_FUNCTION;

  uint32_t vertexCount;
  uint32_t startVertex;

  VertexLayoutHandle vertexLayoutHandle;
  VertexBufferHandle vertexBuffer;
  IndexBufferHandle indexBuffer;
};
static_assert(std::is_pod<Draw>::value == true, "Draw must be a POD.");

const BackendDispatchFunction Draw::DISPATCH_FUNCTION = &backendDispatch::Draw;

Custom commands

As stated earlier, using function pointers this way allows us to support user-defined commands as well. For example, you can make up your own commands by defining a POD, implement a completely custom dispatch function for it, and add that command to any bucket, or even chain it to other commands.

Chaining commands

Now that our command packet also stores a pointer to the next command packet, we can append commands to other commands:

template <typename U, typename V>
U* AppendCommand(V* command, size_t auxMemorySize)
{
  CommandPacket packet = commandPacket::Create<U>(auxMemorySize);

  // append this command to the given one
  commandPacket::StoreNextCommandPacket<V>(command, packet);

  commandPacket::StoreNextCommandPacket(packet, nullptr);
  commandPacket::StoreBackendDispatchFunction(packet, U::DISPATCH_FUNCTION);

  return commandPacket::GetCommand<U>(packet);
}

Note that in this situation we don’t need to store a new key/value pair into our array, because each command that is appended to another one needs to have the same key anyway.

The following example shows how commands can be chained together using the new command bucket API:

for (unsigned int i=0; i < directionalLights.size(); ++i)
{
  PerDirectionalLightConstants constants =
  { directionalLights[i].diffuse, directionalLights[i].specular };

  commands::CopyConstantBufferData* copyOperation = lightingBucket.AddCommand<commands::CopyConstantBufferData>(someKey, sizeof(PerDirectionalLightConstants));

  copyOperation->data = commandPacket::GetAuxiliaryMemory(copyOperation);
  copyOperation->constantBuffer = directionalLightsCB;
  memcpy(copyOperation->data, &constants, sizeof(PerDirectionalLightConstants));
  copyOperation->size = sizeof(PerDirectionalLightConstants);

  commands::Draw* dc = lightingBucket.AppendCommand<commands::Draw>(copyOperation, 0u);
  dc->vertexCount = 3u;
  dc->startVertex = 0u;
}

Revisiting the submission process

Of course, with the command packets in place, the Submit() method also needs to be adapted. By using the backend dispatch, we can get rid of the switch statement, and the linked list of commands can be walked using a simple loop:

void Submit(void)
{
  // ... same as before
  for (unsigned int i=0; i < m_current; ++i)
  {
    // ... same as before
    CommandPacket packet = m_packets[i];
    do
    {
      SubmitPacket(packet);
      packet = commandPacket::LoadNextCommandPacket(packet);
    } while (packet != nullptr);
  }
}

void SubmitPacket(const CommandPacket packet)
{
  const BackendDispatchFunction function = commandPacket::LoadBackendDispatchFunction(packet);
  const void* command = commandPacket::LoadCommand(packet);
  function(command);
}

Recap

This post is quite long already, much longer than I anticipated. But still, let us recap which concepts this post introduced:

• Commands: a self-contained piece of information that is handed to the backend dispatch. Each command resembles one simple operation such as an indexed draw call, copying data to a constant buffer, etc. Each command is implemented as a POD struct.
• Backend dispatch: simple forwarding functions that extract data from a command, and forward them to the graphics backend. Each dispatch function deals with a different command.
• Command packets: a command packet stores a command, along with additional data such as a pointer to a dispatch function, any auxiliary memory a command might need, and an intrusive linked list for chaining commands.
• Chaining of commands: commands that need to be submitted in a certain order can be chained together.
• Command bucket: A command bucket stores command packets along with a key of any size.
• Multi-threaded rendering: Commands can be added to buckets in parallel from multiple threads. The only two points of synchronization are the memory allocation, and storing the key-value pair into the array of command packets.
• Multi-threaded sorting: Each command bucket can be sorted independently, in parallel.

Even though this is already part 3 of the series, there are still things we haven’t talked about in detail yet:

• Memory management: How do we allocate the memory for storing the keys and pointers to packets? How do we efficiently allocate memory for individual command packets in the case of multiple threads adding commands to the same bucket? How can we ensure good cache utilization throughout the whole process of storing and submitting command packets? Can we use one contiguous chunk of memory?
• Key generation: Which information does a key hold? How do we efficiently build a key?

So for now, our rendering process is stateless and layered/bucketized, but its multi-threaded rendering capabilities can still be greatly improved. Until next time!