How to sort tiled decal list?

Question

I have a tiled forward render pipeline (also called forward+). It assigns a list of lights for every 16*16 block of pixels (tiles) on the screen. Lights are accumulated additively so their order doesn't matter inside the list.

The problem comes when I add decals to the light list. Decals need to be evaluated before the lights (because they can modify surface properties), and even their order among themselves matter because their texture is alpha blended on top of each other.

Because the lights and decals are culled in parallel, and added to the list by keeping a shared pointer to the end of the list which is incremented atomically when a light is added, the order of them can not be guaranteed. This is how I add a light to the tile's light list from a thread:

// I have a [numthreads(16,16,1)] thread group
for (uint i = groupIndex; i < g_nNumLights; i += 16 * 16)
{
  Light light = GlobalLightArray[i];
  if(IsLightVisible(light))
  {
    uint index;
    InterlockedAdd(LightCount, 1, index); // LightCount is a groupshared uint (the whole threadgroup can see it)
    LightArray[index] = i; // A light is always added to the back of the per tile light array
  }
}

I thought I should try to sort the light list after the culling and the creation of the list has ended, but I have no experience with highly parallel sorting algorithms. I however came across a nice presentation: Holy smoke! Faster Particle Rendering using Direct Compute by Gareth Thomas . From the 8th slide it has a brief explanation of the bitonic sort algorithm with pseudocode and nice pictures. I get the idea, but I have no idea how to implement it or if it could be even done efficiently for my case because my light list is variable in size for each tile. Maybe it could be done in the same dispatch when the culling occurs, on this array (which hold a variable amount of light indices <= 1024):

groupshared uint LightArray[1024]

I have also seen a DirectX11 example of the algorithm of this kind of sorting, but on a different kind of dataset and across multiple dispatches and other post-processing transposing which is not clear to me at all.

Or maybe there is a completely different approach that I should take which doesn't involve sorting? Maybe when adding lights to the back of the array, the order of addition could be enforced somehow?

I have also learnt that the new Doom game also renders its decals this way.

Answer 1

OK, I haven't noticed, that in the same presentation I linked in my question, there was an other sorting algorithm for the per-tile LDS particle array, with source code. And that is nearly exactly my case, except that they are sorting their particles by distance, I only need to sort my decals by index.

It is a bitonic sorting running in a single dispatch pass, inside the light culling compute shader, after the culling phase, on the groupshared LightArray. Sadly, in the presentation, a line is not completely visible, but I have been able to fill in the missing pieces.

I am posting the sorting code:

    uint numArray = LightCount;

    // Round the number of particles up to the nearest power of two
    uint numArrayPowerOfTwo = 1;
    while( numArrayPowerOfTwo < numArray )
        numArrayPowerOfTwo <<= 1;

    GroupMemoryBarrierWithGroupSync();

    for( uint nMergeSize = 2; nMergeSize <= numArrayPowerOfTwo; nMergeSize = nMergeSize * 2 )
    {
        for( uint nMergeSubSize = nMergeSize >> 1; nMergeSubSize > 0; nMergeSubSize = nMergeSubSize >> 1 )
        {
            uint tmp_index = groupIndex; // It is the SV_GroupIndex, the flattened index of the thread within the threadgroup
            uint index_low = tmp_index & (nMergeSubSize - 1);
            uint index_high = 2 * (tmp_index - index_low);
            uint index = index_high + index_low;

            uint nSwapElem = nMergeSubSize == nMergeSize >> 1 ? index_high + (2*nMergeSubSize - 1) - index_low :  index_high + nMergeSubSize + index_low; // This is the line which is truncated in the presentation
            if( nSwapElem < numArray && index < numArray )
            {
                if( LightList[ index ] > LightList[ nSwapElem ] )
                {
                    uint uTemp = LightList[index];
                    LightList[index] = LightList[nSwapElem];
                    LightList[nSwapElem] = uTemp;
                }
            }
            GroupMemoryBarrierWithGroupSync();
        }
    }