Sorting Pixels With WebGL

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
  srf(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 dp

// If hue of left neighbour is bigger of current pixel
if h(nleft) > h(p) then
  // Move left neighbour to current position
  dnleft

// If hue of right neighbour is smaller of current pixel
else if h(nright) < h(p) then
  // Move right neighbour to current position
  dnright

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?

Eureka!

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 dp

if a and h(nleft) > h(p) then
  dnleft

if not a and h(nright) < h(p) then
  dnright

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.