I love challenging myself to build stuff I never imagined developing. Sometimes I get to do that on CodePen. This year, I was amazed by the computational power of GPUs. It made me develop a GPGPU 2D forcefield, GPGPU 3D forcefield and a Mandelbrot.
One day, my colleague opted to write a CodePen that sorts pixels by hue.
Doing this with a 2D Canvas isn’t too hard. Consider the following pseudo-code:
input: Canvas image data d, Sort function f output: Sorted canvas image data s // Iterate through each row for each r in d do // Sort pixels in row and put in sorted image data sr ← f(r) return s
Like the example my colleague sent, I wanted to animate this. That means the sorting function should iterate through the list once and to make the animation even prettier, it should only compare each element with its neighbour. Above pseudo-code should execute for every frame.
Reading, manipulating and writing pixel data from and to a canvas is slow and would significantly reduce performance.
The simplicity of comparing each pixel with their direct neighbour and the need for performance, I thought this would be a perfect use-case for WebGL.
The Naive Approach
I quickly started to write a sorting algorithm in a WebGL fragment shader.
A fragment shader is responsible for colouring fragments. WebGL converts these into pixels. It cannot change the state of any other fragment.
input: Current pixel colour p, Neighbour pixel colours n, Function that calculates hue from an RGB colour h output: New pixel colour d // Assign current pixel colour to d let d ← p // If hue of left neighbour is bigger of current pixel if h(nleft) > h(p) then // Move left neighbour to current position d ← nleft // If hue of right neighbour is smaller of current pixel else if h(nright) < h(p) then // Move right neighbour to current position d ← nright return d
While writing above logic, I ran into some issues. A fragment shader can only modify the state of the fragment. Instead of swapping pixels, I can only assign a new colour to “current” fragment. Above code wasn’t going to work. Consider following visualisation:
1 3 2 1 ↑ ↗ ↖ ↖ 1 2 3 2 - 1st iteration ↑ ↑ ↗ ↖ 1 2 2 3 - 2nd iteration
Yes! After two iterations the list is sorted! But when I ran the program, I noticed a loss of colour as time passed. Look again. How many ones did we start with?
This problem had me thinking for a while. I also discussed it with some colleagues but had a hard time explaining fragment shaders in the first place. Not fully understanding the problem myself probably contributed to their lack of understanding.
I had a priority issue. To swap two numbers, both have to agree to swap implicitly. If digits are in reversed order and are unequal, they never will, as shown by the following visualisation:
3 2 1 ↗ ↖ ↖ 2 3 2 - 1 disappears magically
At some point I realised I had to make pairs and have a pixel only compare with the other pixel in the same pair. This makes sure that two numbers are truly swapped. Consider following pseudo-code:
input: Frame number f, Current pixel colour p, Current pixel coordinate c, Neighbour pixel colours n, RGB colour to hue function h output: New pixel colour d // Determine if pairs are even or odd let a ← (f + cx) % 2 = 0 let d ← p if a and h(nleft) > h(p) then d ← nleft if not a and h(nright) < h(p) then d ← nright return d
let a ← (f + x) % 2 = 0 defines a boolean whether current fragment should compare with left or right fragment, esentially offsetting the pairs every frame. Let’s see how that works:
1 3 | 2 1 ↑ ↑ | ↗ ↖ 1 3 | 1 2 - 1st iteration 1 | 3 1 | 2 ↑ | ↗ ↖ | ↑ 1 | 1 3 | 2 - 2nd iteration 1 1 | 3 2 ↑ ↑ | ↗ ↖ 1 1 | 2 3 - 3rd iteration
This works like a charm.
Disclaimer: this demo doesn’t sort pixels by hue, but by light and colour intensity.
At this point I’m psyched. I invented an algorithm! I will call this the Severien sort and will be known as a smart person and computer scientist.
Weeks later, I discovered a computer scientist called Nico Habermann beat me to it. In 1972 Nico developed the odd–even sort algorithm. It’s the very same thing I invented. I never studied computer science or algorithms or whatever, so I didn’t know.
And that’s how I sorted pixels with WebGL.