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

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?

• Will you always have a fixed number of floats to store per cell? If so, would using one texture for each float work? For example, using 3 textures to store 9 floats per cell (3 per texture using the R, G, and B channels). – trichoplax Jun 1 '16 at 0:12
• @trichoplax Thanks for your comment! No, I won't have a fixed number of floats, unfortunately. But even if I could fix it for those purposes, that solution wouldn't works since I will have high number of floats - which would result in great memory overhead due to the high number of textures to be used in order to implement your suggestion – blipblop Jun 1 '16 at 20:00
• This is very relevant information - I'd recommend editing the question to include this. – trichoplax Jun 1 '16 at 21:19
• @trichoplax Thanks! I did it, in order to better clarify that particular detail – blipblop Jun 3 '16 at 0:20

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.

• Thanks for your answer! Yes you are right, and I know them: they were introduced with the Compute Shaders and indeed they solve part of the problem because they allow saving values from one shader pass to the next. However, I don't think they solve the main problems I described: the array-of-arrays or array-of-lists issue – blipblop Jun 3 '16 at 20:05
• Doh you have the same number of floats for all pixel? I mean just in a single frame the number could change between frames if necessary. If you have you could unpack the 2D data structure into a 1D array by index shifting. This could then be written as a buffer. If the amount of data varies you could write some raw data Ald just bytes and then an additional index structure which pixel has what amount of data... That would be just one not per pixel overhead. – Dragonseel Jun 5 '16 at 23:46

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.