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
  sr ← f(r)

return s

Like the example my colleague sent, I wanted this animate to be animated. That means that instead of sorting the entire image, the program should only swap two pixels per frame on each row.

To achieve this, I would have to read, manpulate and write individual pixel from and to the canvas, something the 2D canvas isn’t bad at, but comes with a significant performance penalty.

Considering the performance, and the seemingly simple task of swapping two neighbour pixels make me thing it would be a perfect use-case for WebGL.

The Naive Approach

I quickly started to write a sorting algorithm in a WebGL fragment shader.

FYI: A fragment shader is responsible for colouring individual fragments. WebGL mixes several fragments into one pixel. Because a shader is executed for each fragment in parallel, one cannot calculate a new value for another fragment and the new state of any other fragment is unknown. Each fragment is a tiny black box.
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

After writing above logic, it appeared it was sorting, but many colours were lost in the process. Some colours appeared to bleed out over others. After a couple of days wondering what was wrong with my implementation, it hit me. Consider following visualisation:

1 3 2 1
↓ → ← ←
1 2 3 2 - 1st iteration
↓ ↓ → ←
1 2 2 3 - 2nd iteration

Look closely. How many 1s did we start with? How many 1s are left after the second iteration?

Eureka!

This problem had me pondering 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 didn’t help me explaining it.

To swap two things in parallel, both have to agree to swap independently. They also cannot swap with their other neighbour. Consider this simplified visualisation of my naive implementation:

3 2 1
→ ← ←
2 3 2 - 1 disappears magically

Each fragment should look at one neighbour per frame. I decided to make pairs of fragments to avoid fragments trying to swap with an arbitrary neighbour. This enables each fragment to be “aware” which neighbour to potentially swap with. Now both fragments in a pair can compare itself with the other, agreeing to swap or not.

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

Above visualisation in 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 the fragment should compare with the left or right neighbour.

Disclaimer: unlike the example given by my colleague, my CodePen doesn’t sort pixels by hue, but by light and colour intensity.

I invented an algorithm! Hence forth I will call this the “Severien sort” and will be known as a smart person and computer scientist. Or not.

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.

Was this helpful?

🍺 Buy me a beer