In a shader, how to store fragment coordinates in a spatial partitioning from one pass to the next?

Question

I have a post-effect camera-shader in which I want to implement a simple spatial partitioning of the screen between two passes of the fragment shader.

The first pass should divide the screen into cells of size = 30x30 pixels, and then for each green fragment, store somehow which of those screen cells the coordinate of such green fragment is located. That information should then be available for the second pass to work with.

Well, merely dividing the screen into cells is trivial, considering that it's easy to calculate the row and column indexes of such screen-grid:

static float2 _Pixels = float2(_ScreenParams.x, _ScreenParams.y);
float2 griduv = round(input.uv * _Pixels) * _invPixels; //pixel-screen space coordinate of the current fragment being evaluated
half cellsize = 30.0f;

float gridX = griduv .x/cellsize;
float gridY = griduv .y/cellsize;

int gridrow = gridX  - frac(gridX);
int gridcol = gridY  - frac(gridY);

If that was not a shader task but rather a standard CPU code, it would be just a matter of saving the ith griduv into an array-of-list or array-of-array (e.g. float2[][] grid = new float2[gridrow*gridcol][maxNfloat2]) at position grid[gridrow*gridcol+gridrow][i].

However, in a shader, for most hardwares and most DirectX and OpenGL versions, it seems to me that 1) we can't have multi-dimensional arrays, 2) we can't have resizable containers like lists and 3) we also can't pass variables and containers from one pass to the next.

As one can easily see, this situation is also not well suited for using a simple texture to store values from one pass to the next, since I would need multiple float2 into each grid cell and I can have quite many floats to store.

So, how could I proceed in such a situation? In other words, how could I store the pixel-screen coordinates of given fragments in a spatial-partitioning of the screen (in this case a simple fixed size grid of the screen), to be passed from one shader pass to the next?

Answer 1

Though I have never used them myself OpenGL in modern versions gives you something called "Shader Storage Buffer Object" These are buffers that you can fill with your data. They are guaranteed to be able to hold up to 16 MB of data and most implementations seem to have no problem with them taking up the whole GRAM.

This feature is core since OpenGL version 4.3. The SSBOs are basically just a buffer that you can put any datatype in (a struct for example) and a huge amount of them.

I cannot really tell you how to use them, but I think with the name you will find some resource in the web.

Answer 2

As you analyzed correctly, GPUs aren't particularly good at dynamically sized data structures. A common approach to situations like this is speparating the problem into multiple passes, first computing the data in a rigid fashion and then compacting it for further processing. Off the top of my head, one way to approach this would be:

1. First disregard the sparseness and tiling and basically just store a full boolean grid where each pixel just stores if it is green or not, could basically just be a 0/1 uchar per pixel. Fortunately, since it's a post-processing step and you're not e.g. working on rendered geometry directly, you know that you don't need more storage for possible true fragments than the image resolution.

2. Then perform a so-called stream compaction step, which is a common step in GPU computing where you basically compact the full array of flags into a tight array of indices (i.e. coordinates) of the actually set pixels. This is usually done by two sub-steps:

   1. A scan, basically a partial sum (specifically a prefix sum), that for each element computes the number of all the true values preceding it. This is actually the index of that value in the final compacted array.

   2. The actual compaction step, which writes each true value to the position it belongs at, of course now storing its index in the original array rather than just its flag value.

   While still inherently dependent on the preceding/surrounding elements, these steps are rather easy and efficient to implement in a block-based manner in the usual GPU computing frameworks like CUDA/OpenCL or OpenGL/Direct3D Compute Shaders and there's many resources on optimized algorithms for doing that. If using CUDA, there might even be ready-made computing primitives available for that. For a good introduction, see this GPU Gems article.

The only problem left here is the tiling issue. Of course together with the compaction step you might also want to compute the boundaries (i.e. start and end indices) of your individual tiles inside the big coordinate array. But that should be integratable into the general stream compaction/prefix sum algorithm since that is already inherently block-based and maybe just using the tile size as actual block size in the stream compaction would be the easiest approach there, since the per-block sums of the true elements are already a by-product of the straight-forward approaches for block-based stream compaction (of course 32x32 tiles would be much cooler in this case ;-)).

It might be further simplified by actually storing your tiles not in a 2D-grid rather than one tile after the other in a linear array already when doing the first analysis step of the pixels. On the other hand, it might also be evaluated how far the first step, which afterall just looks at a pixel and creates a boolean flag value could already be intergrated into the stream compaction step. But you can do all that once the general framework is up and running.

---

But of course all this also depends on how you actually want to proceed with processing your found per-tile generated green pixels. This way you still end up with a varying number of pixels in each tile, but at least they're laid out linearly in memory and you alleviated the impact of that "dynamicality" on the generation of those per-tile lists, however you go about processing them now. But maybe all you want is just the sum of all green pixels or some avergae weight of their coordinates?

An option you might also consider is simply ignoring all that and just restructuring the next processing step in a way that works on a sparse boolean array. This gives you a fixed number of pixels but a scattered layout of the relevant data. As said, heavily depends on how you proceed with the data.