# Count number of green fragments that are within a given distance from each screen fragment

First of all, let me explain what I am really trying to achieve. In a post-effect shader acting on a camera-renderer, I want to change the color of each fragment depending on how many green (RGBA = 0,~1,0,1) fragments there are nearby.

So, for the sake of simplicity, let's imagine my screen is all black, with some (~10k) green points spread around. In the fragment shader, for each fragment I have to find how many green fragments there are within a given distance and then change the color of the current fragment being evaluated depending on that number of surrounding green fragments.

I began with the most naïve approach one could think of: for each fragment, I calculated the coordinates of the 10th neighbor fragments to each side: right, left, up and down (which gives a surrounding square, then I discarded the corners from the computation to get a surrounding circle of radius ~10pixels, centered at the current fragment). Then I tested which of the fragments within such "surrounding bounding circle" was green (i.e. color.g > 0.9f). In affirmative case, I increased a counter variable.

In my way of thinking, that would be doing a brute force and in order to visualize the result, I then painted each fragment with the RGBA color (counter*0.1f, 0, counter*0.1f, 1). Here is the code snippet:

uniform sampler2D _MainTex;
static float2 _Pixels = float2(_ScreenParams.x, _ScreenParams.y); //gets the Screen width and height
static half sx = 1 / _ScreenParams.x; //defines the measure of a fragment at the X axis of the viewport
static half sy = 1 / _ScreenParams.y; //defines the measure of a fragment at the Y axis of the viewport

float4 frag(v2f_img input) : COLOR{
fixed2 uv = round(input.uv * _Pixels) / _Pixels;

float counter = 0.0f;
float i; float j;
float thrsh = 0.8f;

[unroll(10)]for (i = zero; i<10;i++) //loop trough 10 fragments horizontally
{
[unroll(10)]for (j = zero; j < 10; j++) //loop trough 10 fragments vertically
{
//the following lines cut (very roughly) the corners of the surrounding square ixj to approximate a surrounding circle of radius ~10fragments. But this is less important: if such lines are commented, the problem that I will show later will still happen, just with a surrounding square instead of a surrounding circle
if ((i == 4 || i == 5) && j > 9) j = 0; else if ((i == 6) && j > 8) j = 0; else if ((i == 7) && j > 7) j = 0;
else if ((i == 8) && j > 6) j = 0; else if ((i == 9) && j > 5) j = 0; else if (i == 10 && j > 4) j = 0;

else if (j > 0) { //so, let's continue only if current iteration does not relate to the corners of the surrounding square, i.e. outside the surrounding circle with radius ~10 fragments

float tl = tex2D(_MainTex, uv + fixed2(-sx*i, +sy*j)).g; //gets the top-left neighbor times i and j
float cl = tex2D(_MainTex, uv + fixed2(-sx*i, 0)).g; //gets the center-left neighbor times i and j
float bl = tex2D(_MainTex, uv + fixed2(-sx*i, -sy*j)).g; //gets the bottom-left neighbor times i and j
float tc = tex2D(_MainTex, uv + fixed2(0, +sy*j)).g; //gets the top-center neighbor times i and j
float cc = tex2D(_MainTex, uv + fixed2(0, 0)).g;  //gets the current fragment bein evaluated (i.e. center-center)
float bc = tex2D(_MainTex, uv + fixed2(0, -sy*j)).g;  //gets the bottom-center neighbor times i and j
float tr = tex2D(_MainTex, uv + fixed2(+sx*i, +sy*j)).g; //gets the top-right neighbor times i and j
float cr = tex2D(_MainTex, uv + fixed2(+sx*i, 0)).g; //gets the center-right neighbor times i and j
float br = tex2D(_MainTex, uv + fixed2(+sx*i, -sy*j)).g;  //gets the bottom-right neighbor times i and j

//Now, for each fragment surrounding that is above the Green threshold, we increase the counter
if (tl > thrsh) counter++;
if (cl > thrsh) counter++;
if (bl > thrsh) counter++;
if (tc > thrsh) counter++;
if (bc > thrsh) counter++;
if (tr > thrsh) counter++;
if (cr > thrsh) counter++;
if (br > thrsh) counter++;

}
}

}

if (counter > 0)
{
return float4(counter *0.1f, 0, counter *0.1f, 1); //in case at least one surrounding fragment was green, paint the fragments pink-ish in proportion to how many green there were in the surrounding circle
} else {
return tex2D(_MainTex, float4(0,0,0,1)); //otherwise, paint black
}


However, besides very inefficient, the solution above is also not working correctly. Obvioulsy, I was expecting to get, around each green point at the screen, something like a pink-ish circle that is of stronger intensity when close to the center and fades away at the border, i.e. away from the center. Instead, this is what I get (in actual and zoomed sizes): Now, I tried everything I could think of but I don't get:

1) why it is not working properly. What am I doing wrong? Could anyone shed some light?

2) also, if there is any obvious more performant way of achieving what I want, please do let me know too (the current solution is taking 12ms in a non HD resolution). Or if you prefer, I can come with a different question for that later, after the operational problem described above is solved.

You're getting a cross shape in the output because in your loop, you're counting pixels on the center row and column multiple times. For example the pixel at (0, 0) offset will be counted on every iteration of the inner loop, so 100 times. Similarly, (±i, 0) and (0, ±i) will be counted on every iteration of the inner loop, so 10 times for each value of i.

A better way to write the loop is like this:

[unroll] for (int i = -10; i <= 10; i++)
{
[unroll] for (int j = -10; j <= 10; j++)
{
float sample = tex2D(_MainTex, input.uv + float2(sx*i, sy*j)).g;
if (sample > thrsh) counter++;
}
}


This will weight all pixels equally within a box. To make a more circular shape you can change the j iteration bounds based on the value of i.

Also, I doubt you need or want to round off uv to the nearest pixel as you're doing. The UVs coming into the fragment shader should already be correct, and moreover they are not multiples of the pixel size; they are the coordinates of pixel centers, so they contain a half-pixel offset (which is exactly what you want for sampling a screen-sized texture).

For a more efficient algorithm, you could downsample the original image 2x, then run a 5px-radius neighbor search on that one instead of a 10px-radius search on the original. This will make the circle shape somewhat less precise but depending on what you're doing, it may not matter that much.

Another approach that's less brute-force but still precise would be to build a spatial hierarchy of the green points. This could be as simple as a uniform grid where each grid square stores a list of the points inside it, or as complicated as a kd-tree. Your fragment shader could then walk this data structure to efficiently search the nodes within a radius of the fragment, and count the points it finds.

• Many thanks for your answer! So, in the meanwhile I was able to come with the exact same solution for the cross-shape problem, but in a messier way. So, I am glad I was not thinking it wrong, but happy to see a cleaner solution. Thanks! About the performance, it's currently terrible: ~14ms now, which is of course unacceptable for real time simulations. I got interested in both your suggestions. Would care to elaborate a bit more? (just a PS: I am trying to implement the intensity of halos of point lights depending on the aggregation of how many point lights are close to each other). – blipblop May 22 '16 at 1:45
• By down-sampling (with which I would be totally fine and would be even welcome) you mean something like this stackoverflow.com/questions/14366672/… or something simpler? And I the spatial hierarchy was what I though in the first place, but I though there wasn't a way to save an array of arrays from one pass to the next that would hold the quad-tree. Isn't that the case? I don't see how I would populate the quad-tree in the first pass but then store the info for the second pass (unless using a compute shader). – blipblop May 22 '16 at 1:47
• @GiovannS For this I think you would start with a simple 2x box filter downsample. It can be done by just copying a texture into a 2x smaller render target, using bilinear filtering; that will average together 2x2 pixels in the source to 1 pixel in the destination. For the spatial hierarchy approach, if the points are generated on the GPU then you probably want to build the data structure on the GPU. It's going to be a more complicated endeavor with append buffers, compute shaders, etc. If you google "build quadtree on GPU" or similar, there's a number of articles and papers on it. – Nathan Reed May 22 '16 at 21:02