How to write a fragmented shader in GLSL to sort an array of 9 floating point numbers

Question

I am writing a fragment shader to join 9 images together.

I had never worked with GLSL before, but it seemed like the right tool for the job, since OpenCL is not available on iOS and the median on the processor is inefficient. Here is what I still have:

uniform sampler2D frames[9]; uniform vec2 wh; void main(void) { vec4 sortedFrameValues[9]; float sortedGrayScaleValues[9]; for (int i = 0; i < 9; i++) { sortedFrameValues[i] = texture2D(frames[i], -gl_FragCoord.xy / wh); sortedGrayScaleValues[i] = dot(sortedFrameValues[i].xyz, vec3(0.299, 0.587, 0.114)); } // TODO: Sort sortedGrayScaleValues float gray = sortedGrayScaleValues[4]; gl_FragColor = vec4(gray, gray, gray, 0); } 

Answer 1

Well, I finished the implementation of sorting bubbles and used the average value.

This is what my solution looks like:

 uniform sampler2D frames[9]; uniform vec2 wh; vec4 frameValues[9]; float arr[9]; void bubbleSort() { bool swapped = true; int j = 0; float tmp; for (int c = 0; c < 3; c--) { if (!swapped) break; swapped = false; j++; for (int i = 0; i < 3; i++) { if (i >= 3 - j) break; if (arr[i] > arr[i + 1]) { tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; swapped = true; } } } } void main(void) { for (int i = 0; i < 9; i++) { frameValues[i] = texture2D(frames[i], -gl_FragCoord.xy / wh); arr[i] = dot(frameValues[i].xyz, vec3(0.299, 0.587, 0.114)); } bubbleSort(); float gray = arr[4]; gl_FragColor =vec4(gray, gray, gray, 0); } 

Answer 2

A bit late, but the fastest way I found is to sort the insert . Reducing the complexity and divergence of shaders is key. Bitonic and bubble work well for small numbers. When you get up at around 100, switch to sorting.

Since you know the number of things to sort (9), sorting the net is the best choice. You can use this handy tool to generate it ...

 There are 27 comparators in this network, grouped into 11 parallel operations. [[0,1],[2,3],[4,5],[7,8]] [[0,2],[1,3],[6,8]] [[1,2],[6,7],[5,8]] [[4,7],[3,8]] [[4,6],[5,7]] [[5,6],[2,7]] [[0,5],[1,6],[3,7]] [[0,4],[1,5],[3,6]] [[1,4],[2,5]] [[2,4],[3,5]] [[3,4]] 

A convenient way to use this declaration is to declare a comparison and replacement macro ...

 #define CMP(a, b) ... #define SWAP(a, b) ... #define CSWAP(a, b) if (CMP(a, b)) {SWAP(a, b);} CSWAP(0, 1); CSWAP(2, 3); ... 

Combining both approaches, sorting the network to quickly sort small blocks of data, and then merging the sort if you have many blocks works very well, as described in Quick Sort for Exact OIT complex scenes (disclaimer: I'm the author). Scrolling loops (essentially creating a sorting network) can be especially useful, which allows you to sort the registers. Dynamically indexed arrays are placed in local memory slowly. To prevent the compiler from doing this, you can manually declare vec4 array0, array1 ... Macros can concatenate text, which is useful here #define CMP(a, b) (array##a < array##b) . The example is pretty ugly but quick here .

Answer 3

• This is a common sorting problem, right? The fastest way I know to find a median is through the Median of Medians .

• It may make sense to not put your values ​​in your "sorted" array until they are sorted.

• You don't need the sortedFrameValues variable, which will be an array, at least since you are using it here - you will never use any stored values ​​again. You just need this as the only variable.

Answer 4

You can use OpenGL ES in your iOS application to find the median pixel value in the radius of the neighborhood of the source pixel of your choice; it looks like this:

 kernel vec4 medianUnsharpKernel(sampler u) { vec4 pixel = unpremultiply(sample(u, samplerCoord(u))); vec2 xy = destCoord(); int radius = 3; int bounds = (radius - 1) / 2; vec4 sum = vec4(0.0); for (int i = (0 - bounds); i <= bounds; i++) { for (int j = (0 - bounds); j <= bounds; j++ ) { sum += unpremultiply(sample(u, samplerTransform(u, vec2(xy + vec2(i, j))))); } } vec4 mean = vec4(sum / vec4(pow(float(radius), 2.0))); float mean_avg = float(mean); float comp_avg = 0.0; vec4 comp = vec4(0.0); vec4 median = mean; for (int i = (0 - bounds); i <= bounds; i++) { for (int j = (0 - bounds); j <= bounds; j++ ) { comp = unpremultiply(sample(u, samplerTransform(u, vec2(xy + vec2(i, j))))); comp_avg = float(comp); median = (comp_avg < mean_avg) ? max(median, comp) : median; } } return premultiply(vec4(vec3(abs(pixel.rgb - median.rgb)), 1.0)); } 

Less complicated without sorting. It includes only two steps: 1. Calculate the average value of the pixels surrounding the original pixel in a neighborhood of 3x3; 2. Find the maximum pixel value for all pixels in the same area that is less than average. 3. [OPTIONAL] Subtract the average pixel value from the value of the original pixel to detect the edge.

If you use the median value to detect the edge, there are several ways to modify the code above to get better results, namely: hybrid median filtering and filtering of cut media (replacement and more efficient filtering of the mode). If you are interested, ask.