I wanted to test JS canvas, to see if I could do stuff like we were making rotozooms back in the days. I’ve seen lately animation of color sorting, so I decided to give it a try.
First thing first, how do you write a pixel in a canvas. Well… you don’t.
It seems it’s not implemented (yet ?), so I looked for an alternative https://stackoverflow.com/questions/4899799/whats-the-best-way-to-set-a-single-pixel-in-an-html5-canvas and based on the tests done there http://plnkr.co/edit/tww6e1VY2OCVY4c4ECy3?p=preview it seems that the putImage method is the fastest, so I gave it a try.
First, I created the function and tested it with filling with random colors
1<!DOCTYPE html>
2<html>
3 <head>
4
5 </head>
6 <body>
7 <canvas id="myCanvas" width="1024" height="1024"></canvas>
8
9 <script>
10
11 myCanvas = document.getElementById("myCanvas");
12 myContext = myCanvas.getContext("2d");
13
14 cw = myCanvas.width;
15 ch = myCanvas.height;
16
17 myImg = myContext.getImageData(0, 0, 1, 1);
18
19 function putPixel(r, g, b, x, y) {
20
21 myImg.data[0] = r;
22 myImg.data[1] = g;
23 myImg.data[2] = b;
24 myImg.data[3] = 255; // Alpha
25
26 myContext.strokeStyle = 'rgb(' + r + ',' + g + ',' + b + ')';
27 myContext.putImageData(myImg, x, y);
28
29 }
30
31
32 // Fill the image with random colors
33 for (y=0; y<ch; y++) {
34 for (x=0; x<cw; x++) {
35 putPixel(Math.floor(Math.random() * 256), Math.floor(Math.random() * 256), Math.floor(Math.random() * 256), x, y);
36 }
37 }
38 </script>
39
40 </body>
41</html>It works, it fills my 1024x1024 in about 1⁄8 of a seconde on my Firefox.
So I prepare a line with a color palette :
var colors = [];
var cpt = 0;
for (i=0; i<=255; i++) {
var color = [0, 0, i];
colors[cpt] = color;
cpt++;
}
for (i=0; i<=255; i++) {
var color = [0, i, 255-i];
colors[cpt] = color;
cpt++;
}
for (i=0; i<=255; i++) {
var color = [i, 255, 0];
colors[cpt] = color;
cpt++;
}
for (i=255; i>=0; i--) {
var color = [255, i, 0];
colors[cpt] = color;
cpt++;
}
Much nicer.
Now, I have to scramble each line, as I want to reclass them later for visual effect.
So in the part where we fill the image, I added a function to shuffle randomly
function shuffleArray(array) {
for (var i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
And for each line I shuffled it
for (y=0; y<ch; y++) {
// Make a shuffled line
colorLine = shuffleArray(colors);
for (x=0; x<cw; x++) {
putPixel(colorLine[x][0], colorLine[x][1], colorLine[x][2], x, y);
}
}
Now we’ve got a big scrambled image.
Now it’s time to sort it.
To test the speed, I started to only work on the first line.
So I made a function on click of a button I added
function sortColors() {
console.log("Start");
for (i=0; i<1024; i++) {
for (j=0; j<1024-i; j++) {
testColors(j, 0, (j+1), 0);
}
}
console.log("Done");
}
I simply used a bubble sorting, I get the color from the canvas and test if they’re sorted correctly.
function testColors(x1, y1, x2, y2) {
// Get informations from pixel
p1 = myContext.getImageData(x1, y1, 1, 1).data;
// Find its index
i1 = colorsIndex[(p1[0] * 65536) + (p1[1] * 256) + p1[2]];
// Get informations from the next one
p2 = myContext.getImageData(x2, y2, 1, 1).data;
// Find its index
i2 = colorsIndex[(p2[0] * 65536) + (p2[1] * 256) + p2[2]];
// Test if swap needed
if (i1>i2) swapColors(x1, y1, p1, p2);
}
If they’re not sorted, I swap them
function swapColors(x, y, p1, p2) {
putPixel(p1[0], p1[1], p1[2], x+1, y);
putPixel(p2[0], p2[1], p2[2], x, y);
}
It works. And for sorting only the first line, it tooked…10 seconds ! So we gonna need around 3 hours to sort the whole image. Not cool.
If more, we can’t see the evolution. It’s in Javascript, so it’s mono-threaded, so while we are in the loop, nothing happens until it’s over. Again, not cool. I wanted to see the evolution.
First thing that I tried, checking if JS Compiler forgets to optimize multiplication.
I tried some bit shift
i1 = colorsIndex[(p1[0] << 16) | (p1[1] << 8) | p1[2]];
No surprise, nothing changed. Well, I tried :-)
So the problem is in the reading or the writing of the pixel in the image. We saw that writing was pretty fast (0.127s to write 1024 lines of 1024 pixels), so my vote goes on reading.
To be sure, I ran a test without writing, 9.356 secondes.
So I tried another test with only writing one of the two pixel during swap. 4.787 secondes. Ok, we’ve got our villain.
So reading each time is a bad idea. We have to find another way.
Perhaps reading only if something change ? It will save unuseful reading. But then, what do we have to keep ?
ImageData has a property data with all the pixels colors values. data[0] has red value for the first pixel, data[1] green value, data[2] blue value and data[3] alpha value, data[4] has red value for the second pixel, etc..
So I change my code to read the whole line in a variable each time I pass in the loop
for (i=0; i<1024; i++) {
myLine = myContext.getImageData(0, 0, 1024, 1).data;
for (j=0; j<1023-i; j++) {
testColors(j, l, (j+1), l);
}
}
So I can read directly in it
function testColors(x1, y1, x2, y2) {
// Get informations from pixel
x = x1 * 4;
r1 = myLine[x];
g1 = myLine[x+1];
b1 = myLine[x+2];
// Find its index
i1 = colorsIndex[(r1 << 16) | (g1 << 8) | b1];
// Get informations from the next one
x = x2 * 4;
r2 = myLine[x];
g2 = myLine[x+1];
b2 = myLine[x+2];
// Find its index
i2 = colorsIndex[(r2 << 16) | (g2 << 8) | b2];
// Test if swap needed
if (i1>i2) swapColors(x1, y1, x2, y2, r1, g1, b1, r2, g2, b2);
}
And I only read if there’s a swap
function swapColors(x1, y1, x2, y2, r1, g1, b1, r2, g2, b2) {
putPixel(r1, g1, b1, x1+1, y2);
putPixel(r2, g2, b2, x1, y1);
myLine = myContext.getImageData(0, y1, 1024, 1).data;
}
It’s better. We are now at 3.7 seconds. We divided the time needed by 3. And yes, it’s a little bit stupid to do like that, becaus in fact we are reading all other again an array we can modify on our own !
So let’s do that
function swapColors(x1, y1, x2, y2, r1, g1, b1, r2, g2, b2) {
// Show the change
putPixel(r1, g1, b1, x1+1, y2);
putPixel(r2, g2, b2, x1, y1);
// Change pixel 1 in the line array
x = x1 * 4;
myLine[x] = r2;
myLine[x+1] = g2;
myLine[x+2] = b2;
// Change pixel 2 in the line array
x = x2 * 4;
myLine[x] = r1;
myLine[x+1] = g1;
myLine[x+2] = b1;
}
Tadaaa, 0.14 seconds. We just divided time by more than 20. It’s better ! So I ran a test on the 20 first lines, 2.5 seconds. So I ran a full test, 133.9 seconds. To sort 1024 lines of 1024 pixels with a basic bubble sort algorithm. Seems legit.
But it’s still not pretty. We go from the unsorted image to the sorted image (still on Firefox, we’ll see that later) without seeing all the steps. Worthless, why shuffling after all !
So here comes back the mono threaded Javascript problem. We have to left him some time to breathe and to update the canvas. The solution is to use time functions, here asetTimeout. Instead of my main loop, I made the variable a global one and created a function to call with asetTimeout. It now look nicer, you’re not bored in front of it, something happens. So I started with a 100ms interval.
function iteration() {
// Test if over
if (boucle != 1024) {
for (l=0; l<1024; l++) {
myLine = myContext.getImageData(0, l, 1024, 1).data;
for (j=0; j<1023-boucle; j++) {
testColors(j, l, (j+1), l);
}
}
// Launch next iteration
boucle++;
setTimeout(iteration, 100);
} else {
t1 = new Date().getTime();
output = document.getElementById("output");
output.innerHTML = "Done in " + (t1 - t0)/1000 + " seconds";
}
}
function sortColors() {
t0 = new Date().getTime();
console.log("Start");
boucle = 0;
iteration();
}
We cans see the evolution, it’s pretty, the reds are filling on the right, the blue and black are shifting on the left… But it’s a bit slow. 324.16 seconds to finish. So let’s go down to 10ms interval.
145.67 seconds. We’re not far from the times it takes without showing anything. I tried 2ms but it falls down only to 143 seconds. That’s the bottom of this version.
So no choice left, we have to use the whole image instad of the lines
function testColors(x1, y1, x2, y2) {
// Get informations from pixel 1
x = (y1 * 4096) + (x1 * 4);
r1 = myImgData[x];
g1 = myImgData[x+1];
b1 = myImgData[x+2];
// Find its index
i1 = colorsIndex[(r1 << 16) | (g1 << 8) | b1];
// Get informations from pixel 2
x = (y2 * 4096) + (x2 * 4);
r2 = myImgData[x];
g2 = myImgData[x+1];
b2 = myImgData[x+2];
// Find its index
i2 = colorsIndex[(r2 << 16) | (g2 << 8) | b2];
// Test if swap needed
if (i1>i2) swapColors(x1, y1, x2, y2, r1, g1, b1, r2, g2, b2);
}
We are down to 123 seconds. Still pretty slow but hey, it’s a bubble sorting algorithm ! I downed it of a pair of more seconds with get the calculation (y1 * 4096) of the loops, but that’s all.
And then, I tried on chromium. And it’s show every steps. Very slowly. Very. In fact, the first fill of the image takes more than 2 minutes where Firefox deal with it in 0.125s. So it’s unusable :-(
So I guess I have to do some double buffering.
But it’s for the next time on sort some colors part 2.
Photo credit : Dmitri Popov
