There's a bunch of setup needed here, so I'll go into a bit of detail with some code segments. First, we'll set up a buffer for our atomic counter:

GLuint counterBuffer;  
glGenBuffers(1, &counterBuffer);
glBindBufferBase(GL_ATOMIC_COUNTER_BUFFER, 0, counterBuffer);
glBufferData(GL_ATOMIC_COUNTER_BUFFER, sizeof(GLuint), NULL, 
             GL_DYNAMIC_DRAW);

Next, we create a buffer for our linked list storage:

GLuint llBuf;
glGenBuffers(1, &llBuf);
glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 0, llBuf);
glBufferData(GL_SHADER_STORAGE_BUFFER, maxNodes * nodeSize, NULL, 
             GL_DYNAMIC_DRAW);

We also need to create a texture to hold the list head pointers. We'll use 32-bit unsigned integers, and bind it to image unit 0:

glGenTextures(1, &headPtrTex);
glBindTexture(GL_TEXTURE_2D, headPtrTex);
glTexStorage2D(GL_TEXTURE_2D, 1, GL_R32UI, width, height); 
glBindImageTexture(0, headPtrTex, 0, GL_FALSE, 0, GL_READ_WRITE, 
                   GL_R32UI);

After we render each frame, we need to clear the texture by setting all texels to a value of 0xffffffff. To help with that, we'll create a buffer of the same size as the texture, with each value set to our "clear value":

vector<GLuint> headPtrClear(width * height, 0xffffffff); 
GLuint clearBuf;
glGenBuffers(1, &clearBuf);
glBindBuffer(GL_PIXEL_UNPACK_BUFFER, clearBuf);
glBufferData(GL_PIXEL_UNPACK_BUFFER, 
             headPtrClear.size()*sizeof(GLuint), 
             &headPtrClear[0], GL_STATIC_COPY);

That's all the buffers we'll need. Note the fact that we've bound the head pointer texture to image unit 0, the atomic counter buffer to index 0 of the GL_ATOMIC_COUNTER_BUFFER binding point (glBindBufferBase), and the linked list storage buffer to index 0 of the GL_SHADER_STORAGE_BUFFER binding point. We'll refer back to that later.

Use a pass-through vertex shader that sends the position and normal along in eye coordinates.

With all of the buffers set up, we need two render passes. Before the first pass, we want to clear our buffers to default values (that is, empty lists), and to reset our atomic counter buffer to zero.

glBindBuffer(GL_PIXEL_UNPACK_BUFFER, clearBuf);
glBindTexture(GL_TEXTURE_2D, headPtrTex);
glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, width, height, 
                GL_RED_INTEGER, GL_UNSIGNED_INT, NULL);
GLuint zero = 0;
glBindBufferBase(GL_ATOMIC_COUNTER_BUFFER, 0, counterBuffer);
glBufferSubData(GL_ATOMIC_COUNTER_BUFFER, sizeof(GLuint), &zero);

In the first pass, we'll render the full scene geometry. Generally, we should render all the opaque geometry first, and store the results in a texture. However, we'll skip that step for this example to keep things simple and focused. Instead, we'll render only transparent geometry. When rendering the transparent geometry, we need to make sure to put the depth buffer in read-only mode (use glDepthMask). In the fragment shader, we add each fragment to the appropriate linked list.

layout (early_fragment_tests) in;

#define MAX_FRAGMENTS 75 

in vec3 Position;
in vec3 Normal;

struct NodeType {
  vec4 color;
  float depth;
  uint next;
};

layout(binding=0, r32ui) uniform uimage2D headPointers;
layout(binding=0, offset=0) uniform atomic_uint 
                                         nextNodeCounter;
layout(binding=0, std430) buffer linkedLists {
  NodeType nodes[];
};
uniform uint MaxNodes;

subroutine void RenderPassType();
subroutine uniform RenderPassType RenderPass;

…

subroutine(RenderPassType)
void pass1()
{
  // Get the index of the next empty slot in the buffer
  uint nodeIdx = atomicCounterIncrement(nextNodeCounter);

  // Is there space left in the buffer?
  if( nodeIdx < MaxNodes ) {
    // Update the head pointer image
    uint prevHead = imageAtomicExchange(headPointers, 
                           ivec2(gl_FragCoord.xy), nodeIdx);

    // Set the color and depth of this new node to the color
    // and depth of the fragment.  The next pointer points to the
    // previous head of the list.
    nodes[nodeIdx].color = vec4(shadeFragment(), Kd.a);
    nodes[nodeIdx].depth = gl_FragCoord.z;
    nodes[nodeIdx].next = prevHead;
  }
}

Before rendering the second pass, we need to be sure that all of the data has been written to our buffers. In order to ensure that is indeed the case, we can use a memory barrier.

glMemoryBarrier( GL_ALL_BARRIER_BITS );

In the second pass, we don't render the scene geometry, just a single, screen-filling quad in order to invoke the fragment shader for each screen pixel. In the fragment shader, we start by copying the linked list for the fragment into a temporary array.

struct NodeType frags[MAX_FRAGMENTS];
int count = 0;

// Get the index of the head of the list
uint n = imageLoad(headPointers, ivec2(gl_FragCoord.xy)).r;

// Copy the linked list for this fragment into an array
while( n != 0xffffffff && count < MAX_FRAGMENTS) {
  frags[count] = nodes[n];
  n = frags[count].next;
  count++;
}

Then, we sort the fragments using insertion sort:

// Sort the array by depth (largest to smallest).
for( uint i = 1; i < count; i++ )
{
  struct NodeType toInsert = frags[i];
  uint j = i;
  while( j > 0 && toInsert.depth > frags[j-1].depth ) {
    frags[j] = frags[j-1];
    j--;
  }
  frags[j] = toInsert;
}

Finally, we blend the fragments "manually", and send the result to the output variable:

// Traverse the array, and blend the colors.
vec4 color = vec4(0.5, 0.5, 0.5, 1.0);  // Background color
for( int i = 0; i < count; i++ ) { 
  color = mix( color, frags[i].color, frags[i].color.a);
}
  
// Output the final color
FragColor = color;

To clear our buffers, prior to the first pass, we bind clearBuf to the GL_PIXEL_UNPACK_BUFFER binding point, and call glTexSubImage2D to copy data from clearBuf to the the head pointer texture. Note that when a non-zero buffer is bound to GL_PIXEL_UNPACK_BUFFER, glTexSubImage2D treats the last parameter as an offset into the buffer that is bound there. Therefore, this will initiate a copy from clearBuf into headPtrTex. Clearing the atomic counter is straightforward, but the use of glBindBufferBase may be a bit confusing. If there can be several buffers bound to the binding point (at different indices), then how does glBufferSubData know which buffer to target? It turns out that when we bind a buffer using glBindBufferBase, it is also bound to the "generic" binding point as well.

In the fragment shader during the first pass, we start with the layout specification enabling the early fragment test optimization.

layout (early_fragment_tests) in;

This is important because if any fragments are obscured by the opaque geometry, we don't want to add them to a linked list. If the early fragment test optimization is not enabled, the fragment shader may be executed for fragments that will fail the depth test, and hence will get added to the linked list. The previous statement ensures that the fragment shader will not execute for those fragments.

The definition of struct NodeType specifies the type of data that is stored in our linked list buffer. We need to store color, depth, and a pointer to the next node in the linked list.

The next three statements declare the objects related to our linked list storage. The first, headPointers, is the image object that stores the locations of the heads of each linked list. The layout qualifier indicates that it is located at image unit 0 (refer to the Getting ready section of this recipe), and the data type is r32ui (red, 32-bit, unsigned integer). The second object is our atomic counter nextNodeCounter. The layout qualifier indicates the index within the GL_ATOMIC_COUTER_BUFFER binding point (refer to the Getting ready section of this recipe), and the offset within the buffer at that location. Since we only have a single value in the buffer, the offset is 0, but in general, you might have several atomic counters located within a single buffer. Third is our linked-list storage buffer linkedLists. This is a shader storage buffer object. The organization of the data within the object is defined within the curly braces here. In this case, we just have an array of NodeType structures. The bounds of the array can be left undefined, the size being limited by the underlying buffer object that we created. The layout qualifiers define the binding and memory layout. The first, binding, indicates that the buffer is located at index 0 within the GL_SHADER_STORAGE_BUFFER binding point. The second, std430, indicates how memory is organized within the buffer. This is mainly important when we want to read the data back from the OpenGL side. As mentioned previously, this is documented in the OpenGL specification document.

The first step in the fragment shader during the first pass is to increment our atomic counter using atomicCounterIncrement. This will increment the counter in such a way that there is no possibility of memory consistency issues if another shader instance is attempting to increment the counter at the same time.

The return value of atomicCounterIncrement is the previous value of the counter. It is the next unused location in our linked list buffer. We'll use this value as the location where we'll store this fragment, so we store it in a variable named nodeIdx. It will also become the new head of the linked list, so the next step is to update the value in the headPointers image at this pixel's location gl_FragCoord.xy. We do so using another atomic operation: imageAtomicExchange. This replaces the value within the image at the location specified by the second parameter with the value of the third parameter. The return value is the previous value of the image at that location. This is the previous head of our linked list. We hold on to this value in prevHead, because we want to link our new head to that node, thereby restoring the consistency of the linked list with our new node at the head.

Finally, we update the node at nodeIdx with the color and depth of the fragment, and set the next value to the previous head of the list (prevHead). This completes the insertion of this fragment into the linked list at the head of the list.

After the first pass is complete, we need to make sure that all changes are written to our shader storage buffer and image object before proceeding. The only way to guarantee this is to use a memory barrier. The call to glMemoryBarrier will take care of this for us. The parameter to glMemoryBarrier is the type of barrier. We can "fine tune" the type of barrier to specifically target the kind of data that we want to read. However, just to be safe, and for simplicity, we'll use GL_ALL_BARRIER_BITS, which ensures that all possible data has been written.

In the second pass, we start by copying the linked list for the fragment into a temporary array. We start by getting the location of the head of the list from the headPointers image using imageLoad. Then we traverse the linked list with the while loop, copying the data into the array frags.

Next, we sort the array by depth from largest to smallest, using the insertion sort algorithm. Insertion sort works well on small arrays, so should be a fairly efficient choice here.

Finally, we combine all the fragments in order, using the mix function to blend them together based on the value of the alpha channel. The final result is stored in the output variable FragColor.

As mentioned previously, we've skipped anything that deals with opaque geometry. In general, one would probably want to render any opaque geometry first, with the depth buffer enabled, and store the rendered fragments in a texture. Then, when rendering the transparent geometry, one would disable writing to the depth buffer, and build the linked list as shown previously. Finally, you could use the value of the opaque texture as the background color when blending the linked lists.

This is the first example in this book that makes use of reading and writing from/to arbitrary (shared) storage from a shader. This capability, only recently introduced, has given us much more flexibility, but that comes at a price. As indicated previously, we have to be very careful to avoid memory consistency and coherence issues. The tools to do so include atomic operations and memory barriers, and this example has just scratched the surface. There's much more to come in Chapter 10, Using Compute Shaders when we look at compute shaders, and I recommend you read through the memory chapter in the OpenGL Programming Guide for much more detail than I can provide here.