Comme je voulais tester un peu les canvas JS, pour faire comme quand on écrivait dans un écran VGA pour faire des rotozooms, j’ai décidé de voir ce que je pouvais en faire. J’ai vu passer ces 2 derniers jours des jolies images animées de reclassement de couleurs, je me suis dit que j’allais faire ça.
Comme en plus je n’ai pas accès à Internet, ça me permet de bricoler localement en attendant.
Première chose à regarder, comment écrire un pixel dans un canvas. Apparemment on ne peux pas…
Il semble que ce ne soit pas implémenté. Donc j’ai cherché une alternative https://stackoverflow.com/questions/4899799/whats-the-best-way-to-set-a-single-pixel-in-an-html5-canvas et d’après les tests effectué ici http://plnkr.co/edit/tww6e1VY2OCVY4c4ECy3?p=preview il semble que la méthode putImage soit la plus rapide, donc je vais utiliser celle-là.
Pour commencer, je crée la fonction et je teste que ça fonctionne en remplissant de pixels au hasard
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 // Remplir l'image de couleur au hasard
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>Ça fonctionne, ça remplis les lignes en environ 1⁄8 de secondes sur mon Firefox.
Du coup je me prépare une ligne avec une palette de couleurs :
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++;
}
C’est déjà plus joli :-)
Maintenant il faut mélanger chaque ligne, puisqu’on veut les reclasser pour donner un effet visuel.
Donc dans la partie où on génère l’image, on rajoute une fonction pour trier le tableau aléatoirement
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;
}
Et pour chaque ligne on mélange le tout
for (y=0; y<ch; y++) {
// On génère une ligne mélangée
colorLine = shuffleArray(colors);
for (x=0; x<cw; x++) {
putPixel(colorLine[x][0], colorLine[x][1], colorLine[x][2], x, y);
}
}
Voilà. Maintenant on a un gros truc qui ne ressemble plus à rien.
L’heure est venue de le classer.
Pour tester les performances, j’ai commencé par reclasser la première ligne. Histoire de voir ce que ça donnera après.
J’ai donc une fonction appelée sur le click d’un bouton que j’ai rajouté
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");
}
Je fais juste un tri à bulle de base (ce qui fait déjà un million d’opérations… on va y revenir), je récupère les couleurs dans le canvas et je teste si elle sont classées comme il faut.
function testColors(x1, y1, x2, y2) {
// Récupérer les informations du pixel
p1 = myContext.getImageData(x1, y1, 1, 1).data;
// Retrouver son index
i1 = colorsIndex[(p1[0] * 65536) + (p1[1] * 256) + p1[2]];
// Récupérer les informations du voisin
p2 = myContext.getImageData(x2, y2, 1, 1).data;
// Retrouver son index
i2 = colorsIndex[(p2[0] * 65536) + (p2[1] * 256) + p2[2]];
// Tester s'il faut swapper
if (i1>i2) swapColors(x1, y1, p1, p2);
}
Si elles ne le sont pas, je les échange
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);
}
Ça fonctionne. Et pour ranger la première ligne, il lui faut environ.. 10 secondes ! Donc il va lui falloir 3H pour tout ranger. Pas cool.
En plus, on ne voit pas la progression. C’est Javascript, c’est mono-thread, donc tant qu’il est coincé dans sa boucle, il ne fait rien d’autre, du coup on ne voit que quand c’est fini. Pas cool non plus, moi je voulais voir une jolie évolution.
Première chose que j’essaye, vérifier si le compilateur javascript oublierai d’optimiser mes multiplications.
J’essaye le décalage de bits pour voir
i1 = colorsIndex[(p1[0] << 16) | (p1[1] << 8) | p1[2]];
Pas de surprise, ça ne change rien. J’aurai essayé :-)
Donc le soucis vient très probablement soit de la lecture, soit de l’écriture dans l’image. On a vu que l’écriture était assez rapide (0,127s pour écrire 1024 lignes de 1024 pixels), dont je vote lecture.
Par acquis de conscience, je fais un test sans écrire dans mon image, résultat 9,356 secondes. Pas mieux
Je fais donc un autre test, en ne lisant qu’un seul pixel sur les 2. Résultat, 4,787 secondes. Ok, on tient notre coupable.
Donc aller relire à chaque fois n’est pas la solution.
Du coup il faut trouver autre chose. Peut-être ne relire que si on change quelque chose ? On évitera tout un tas de relectures inutiles. Mais du coup que stocker ?
L’ImageData a une propriété data contenant la totalité des valeurs des pixels, classée les unes derrières les autres. data[0] contient le rouge du premier pixel, data[1] le vert, data[2] le bleu et data[3] le canal alpha, data[4] le rouge du second pixel, etc..
Je modifie donc mon code pour lire toute la ligne dans une variable à chaque passage dans la boucle
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);
}
}
Du coup je vais lire directement dedans
function testColors(x1, y1, x2, y2) {
// Récupérer les informations du pixel
x = x1 * 4;
r1 = myLine[x];
g1 = myLine[x+1];
b1 = myLine[x+2];
// Retrouver son index
i1 = colorsIndex[(r1 << 16) | (g1 << 8) | b1];
// Récupérer les informations du voisin
x = x2 * 4;
r2 = myLine[x];
g2 = myLine[x+1];
b2 = myLine[x+2];
i2 = colorsIndex[(r2 << 16) | (g2 << 8) | b2];
// Tester s'il faut swapper
if (i1>i2) swapColors(x1, y1, x2, y2, r1, g1, b1, r2, g2, b2);
}
Et je ne relis la ligne qu’en cas de modification
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;
}
On avance, on n’est plus qu’à 3,7 secondes. On a divisé le temps par trois. Et oui, c’est stupide de faire comme ça (on fait ce qu’on peut), car perdre du temps à relire un tableau qu’on peut modifier soi-même c’est pas malin !
Du coup je le modifie moi.
function swapColors(x1, y1, x2, y2, r1, g1, b1, r2, g2, b2) {
// Afficher les changements
putPixel(r1, g1, b1, x1+1, y2);
putPixel(r2, g2, b2, x1, y1);
// Modifier le pixel 1 dans le tableau
x = x1 * 4;
myLine[x] = r2;
myLine[x+1] = g2;
myLine[x+2] = b2;
// Modifier le pixel 2 dans le tableau
x = x2 * 4;
myLine[x] = r1;
myLine[x+1] = g1;
myLine[x+2] = b1;
}
Pouf, 0.14 secondes. On vient de diviser le temps par plus de 20. Mieux ! Je lance un test sur les 20 premières lignes, 2,5 secondes. Du coup je lance un test sur l’intégralité, 133,9 secondes. Pour ranger 1024 lignes de 1024 points avec un tri à bulle de base. Ça me va.
Maintenant c’est pas beau. On passe de la version toute mélangée à la version classée sans voir les étapes. Aucun intérêt, autant ne pas le mélanger au départ !
Donc nous voilà coincés avec le classique problème du mono thread de Javascript. Donc il faut lui laisser de l’espace pour souffler. La solution est de passer par des fonctions de temps, et ici unsetTimeout. Au lieu de boucler sur ma première variable, je vais en faire une variable globale et créer une fonction à appeler en timeout. Comme si c’est joli on ne s’ennuie pas devant, je vais commencer par un intervalle de 100ms entre chaque appel.
function iteration() {
// Traiter le cas de sortie
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);
}
}
// Lancer l'itération suivante
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();
}
On voit bien l’évolution, c’est joli, le rouge à droite se remplis jusqu’à évoluer tandis que la gauche s’assombrit… Mais c’est un peu lent (324,16 secondes pour terminer). Donc on va réduire à 10ms et voir si ça se rafraîchit joliment quand même.
145,67 secondes. On n’est plus très loin du temps que ça prend pour trier sans l’afficher, on ne fera probablement pas mieux. Je lance à 2ms par curiosité, mais à mon avis c’est vain.
143 secondes. On est arrivé au bout de cette version.
Donc plus le choix, on va utiliser toute l’image, et plus ligne à ligne, en modifiant les références au tableau
function testColors(x1, y1, x2, y2) {
// Récupérer les informations du pixel
x = (y1 * 4096) + (x1 * 4);
r1 = myImgData[x];
g1 = myImgData[x+1];
b1 = myImgData[x+2];
// Retrouver son index
i1 = colorsIndex[(r1 << 16) | (g1 << 8) | b1];
// Récupérer les informations du voisin
x = (y2 * 4096) + (x2 * 4);
r2 = myImgData[x];
g2 = myImgData[x+1];
b2 = myImgData[x+2];
i2 = colorsIndex[(r2 << 16) | (g2 << 8) | b2];
// Tester s'il faut swapper
if (i1>i2) swapColors(x1, y1, x2, y2, r1, g1, b1, r2, g2, b2);
}
On tombe à 123 secondes. Toujours lent, mais c’est un tri à bulle. J’ai grappillé après une paire de secondes en sortant les calculs (y1 * 4096) des boucles, mais rien de probant.
J’ai aussi essayé sur Chromium. Lui, par contre, affiche chaque étape. Très lentement. Du coup c’est inutilisable.
Et du coup, il faut faire autrement. Probablement en utilisant un double buffering.
Mais ça, ça sera pour une autre fois, dans classer des couleurs 2ème partie.
Crédit photo : Dmitri Popov
