Version naïve

La base pour faire de l'affichage avec niveaux d'alpha, c'est d'extraire les 3 composantes RGB du pixel, avec un truc du genre

r = pixel & 31;

g = (pixel >> 5) & 31;

b = (pixel >> 10) & 31;

Tout dépend de si les composantes sont en RGB ou BGR, mais globalement ici on s'en fout, ce n'est pas le but du billet. On extrait donc les composantes pour chaque pixel, et de façon naïve, pour blender le tout (étant donné un niveau d'alpha "alpha"), on fait

r = (r_dst * alpha + r_src * (ALPHA_MAX - alpha)) / ALPHA_MAX;

(et pareil pour g et b)

Puis on écrit le pixel résultat :

pixel = r | (g << 5) | (b << 10)

On a donc pour l'instant au total les opérations suivantes :

  • 6 décalages de bits/masks pour extraires les infos
  • 6 multiplications, 3 divisions, et 3 soustractions (2 multiplications, 1 division, et une soustraction par composante)
  • 3 décalages de bits pour réécrire le pixel

On va voir si on peut faire mieux... 

Version optimisée

Etant donné la vitesse des décalages et masks par rapport aux multiplications/divisions, on va se concentrer sur ces dernières.

Une première étape est de supprimer la division, qui va être par une valeur foireuse (car en général on stocke le niveau d'alpha sur 8bit, soit les valeurs 0-255, et 255 est une division couteuse...). Plusieurs solutions sont envisageables :

  • Remplacer 255 par 256, pour avoir un décalage de bit (>> 8) au lieu d'une division. Mais on perd alors un peu de couleur, et une image opaque devient partiellement transparente
  • Remplacer l'intervalle 0-255 par un intervalle plus adapté à ce qu'on fait, comme 0-128. On peut alors faire un décalage de bits, mais cette fois-ci une image opaque reste parfaitement opaque. On perd cependant en précision, car on a moitié moins de niveaux d'alphas
  • Remplacer la division par une recherche dans un tableau. Bien mais pas top

Pour rester dans l'optique des optimisations qui vont suivre, je vais prendre pour l'instant la solution 2. Je vous grâce de l'implémentation, elle est assez simple, mais nécessite d'effectuer une passe de pré-traitement au chargement de l'image.

On a alors les mêmes opérations que précédemment, mais avec 3 divisions en moins et 3 décalages en plus (virtuellement gratuits, donc). Il reste donc à voir si on peut améliorer les 6 multiplications.

Une première optimisation permet de diviser par 2 le nombre de multiplication, en faisant une simple factorisation.

r = (r_dst * alpha + r_src * (ALPHA_MAX - alpha)) / ALPHA_MAX;

devient

r = ((r_dst - r_src) * alpha + r_src * ALPHA_MAX) / ALPHA_MAX;

ou encore

r = (((r_dst - r_src) * alpha) / ALPHA_MAX) + r_src;

Vérification rapide : si alpha = 0, on a r = r_src. Si alpha = ALPHA_MAX, on a r = r_dst - r_src + r_src = r_dst.

Version optimisée à mort

Bon, ça commence à devenir intéressant, on a réduit pas mal le temps CPU a priori... Mais est-ce qu'on peut faire mieux ? ^^ Ce qui parait dommage ici, c'est qu'on bosse sur une couleur en 15bits, et qu'au final ça nous coûte plus cher que si on avait eu du 32bit, puisqu'on a l'extraction de couleur à faire, puis le calcul du pixel final... Donc si on avait une méthode pour rendre le 15bit plus rapide que le 32bit, ça serait quand même assez royal... Et bien, je ne dirai qu'une chose : c'est possible !

J'ai trouvé cette astuce sur un forum PPC avec des gars qui se prenaient la tête pour améliorer au maximum les performances, et je dois dire que c'est assez génial (d'où ce billet). Ca part du constat qu'on bosse sur des images 32bit (en général, et éventuellement 64bit sur des PC de nos jours), et qu'on pourrait probablement tirer parti de cela pour limiter les opérations.

Car si on a 15bits de couleur, c'est qu'on a en fait 5 bits par composante. Donc quand on fait des multiplications en 32bits, finalement on a beaucoup de bits qui ne servent à rien, et c'est dommage ^^ L'astuce consiste donc à faire des "paquets" suffisamment intelligement pour limiter le nombre de multiplications.

La couleur d'un pixel se présente sous la forme suivante :

0 BBBBB GGGGG RRRRR

Donc quand on passe sur du 32bit, ça donne ça :

00000000 00000000 0 BBBBB GGGGG RRRRR

Et quand on multiplie les composantes une par une, on a ça : 

00000000 00000000 0 00000 00000 RRRRR

En gros on n'utilise presque rien !!! On pourrait, de façon un peu folle, imaginer placer les différentes composantes de façon un peu écarte sur notre 32bit, du genre

0000000 GGGGG 00000 BBBBB 00000 RRRRR

Là, on a 32 bits, et on remarque qu'on a des trous entres les composantes... Que se passe-t-il si je multiplie tout ça par 2 ?

000000G GGGG0 0000B BBBB0 0000R RRRR0

On voit que finalement tout se passe pour le mieux dans le meilleur des mondes, que tout se décale, et que rien ne se chevauche... En fait, on a 5 bits de "trous" entre chaque composante avec cette disposition, donc techniquement on peut décaller 5 fois avant que ça ne se marche dessus. Ce qui représente une multiplication par 32...

L'idée géniale est alors de faire comme précédemment, mais en combinant toutes les composantes de la sorte, et en ne faisant la multiplication qu'une fois. La seule contrainte est qu'on n'a que peu de bits de rab, donc on ne peut plus avoir un intervalle de 0 à 128, et on va devoir se contenter d'un niveau d'alpha de 0 à 32... Mais avec ça, on ne va plus avoir qu'une seule multiplication (contre 6 au début et 3 précédemment). Niveau performance le gain est assez énorme.

On gagne aussi à d'autres niveaux :

  • Plus besoin d'extraire les composantes, on a juste a appliquer un masque pour virer le vert (le rouge et le bleu restent en place) et à la décaler pour le rajouter plus loin
  • Pour reconstituer la couleur complète, il suffit de faire pixel = r | (r >> 20), ce qui est aussi moins coûteux que ce qu'on avait au départ.

On gagne donc en fait à tous les niveaux. Je n'ai pas de bench avec moi pour illustrer tout ça (ce qui est assez dommage, je verrai peut-être pour en faire), mais en gros dans mon cas les routines d'affichage en alpha étaient passées de "trop lente pour être utilisées" à "suffisamment rapides pour être utilisées à outrance". C'est donc un gain assez majeur ^^

Conclusion

Tout cela n'est cependant pas parfait. En effet, passer à 32 niveaux d'alpha commence à se ressentir. Déjà qu'avec du 15bit les dégradés sont bien visible, avec 32 niveaux d'alpha c'est assez flagrant. Utilisé à outrance dans Skinz Sudoku (un background fullscreen tout en alpha pour le menu ingame), il a fallu que je fasse un coup de photoshop pour faire du dithering sur le layer alpha histoire de casser l'effet de "marches d'escaliers"... Mais bon, avoir autant de choses à l'écran, avec alpha, et le tout sans carte graphique, c'est assez surprenant pour un appareil de 200 à 400Mhz en gardant un framerate constant, donc ça montre bien que c'est super rapide :p

Voilà, depuis ce jour je me demande quand j'aurai l'occasion de trouver/faire une optimisation