Le code dans cet article a été écrit avec Code::Blocks et la SDL 2.
Vous pouvez trouver
ici un guide pour installer ces logiciels.
Bien qu'il soit basé sur la SDL, je n'utilise pas ses fonctions directement. J'ai écrit une petite bibliothèque
avec quelques fonctions basiques pour faciliter la compréhension et la portabilité dans un autre langage.
Vous pouvez en apprendre plus sur cette bibliothèque
ici.
Dans cet article j'utilise la classe Vec2f dont j'ai parlé pour la première fois
ici.
Les metaballs sont un vieil effet utilisé dans les démos.
L'idée est d'afficher des cercles qui se déplacent et qui semblent fusionner ensemble comme s'ils étaient liquides.
Pour accomplir ça on va devoir colorier chaque pixel en fonction de sa distance à plusieurs points.
Alors commençons avec un seul point au centre de l'écran.
On va utiliser un vecteur pour définir sa position:
Vec2f blobPos(SCREEN_WIDTH / 2, SCREEN_HEIGHT / 2);
Puis on va boucler sur chaque pixel de l'écran
for (int y = 0; y < SCREEN_HEIGHT; y++)
for (int x = 0; x < SCREEN_HEIGHT; x++)
{
Vec2f p(x, y);
Et on va calculer la distance du pixel à notre point.
Vec2f delta = p - blobPos;
float dist = delta.mag();
En limitant cette valeur à 255, on peut l'utiliser comme couleur pour dessiner à l'écran.
if (dist > 255)
dist = 255;
int c = (int)dist;
gfx.setPixel(x, y, Color(c, c, c));
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Et voici ce qu'on obtient:
Plus tard on va afficher plusieurs de ces "blobs" et ils auront différentes tailles.
Alors ajoutons un rayon à ce point.
Vec2f blobPos(SCREEN_WIDTH / 2, SCREEN_HEIGHT / 2);
float blobRadius = 100.0f;
Je veux aussi inverser les couleurs de ce qu'on voit à l'écran. Alors je vais soustraire la distance à ce rayon.
float dist = blobRadius - delta.mag();
if (dist < 0)
dist = 0;
if (dist > 255)
dist = 255;
Télécharger le code source
Télécharger l'exécutable pour Windows
Et maintenant on peut voir ça:
Si on veut avoir plusieurs blobs, ça sera plus simple si on écrit une classe pour eux.
Alors je l'ai déclarée dans "main.h":
class CBlob
{
public:
CBlob();
Vec2f pos;
float radius;
};
Le constructeur de cette classe va mettre des valeurs aléatoire dans les membres:
CBlob::CBlob()
{
pos.x = rand() % SCREEN_WIDTH;
pos.y = rand() % SCREEN_HEIGHT;
radius = 50 + (rand() % 100);
}
Au début du programme on va allouer un tableau de ces blobs.
srand(time(NULL));
const int nbBlobs = 6;
CBlob* blobs = new CBlob[nbBlobs];
Et dans la boucle principale on va maintenant devoir ajouter les distances de chaque blob.
Vec2f p(x, y);
float power = 0;
for (int i = 0; i < nbBlobs; i++)
{
Vec2f delta = p - blobs[i].pos;
float dist = blobs[i].radius - delta.mag();
if (dist < 0)
dist = 0;
power += dist;
}
if (power > 255)
power = 255;
int c = (int)power;
gfx.setPixel(x, y, Color(c, c, c));
Télécharger le code source
Télécharger l'exécutable pour Windows
Et voilà le résultat:
On n'a pas encore utilisé la véritable formule des metaballs.
En fait on ne doit pas soustraire la distance du rayon, mais la diviser:
for (int i = 0; i < nbBlobs; i++)
{
Vec2f delta = p - blobs[i].pos;
power += blobs[i].radius / delta.mag();
}
Avec cette nouvelle formule, les blobs ont besoin de plus grands rayons:
radius = 2000 + (rand() % 6000);
Télécharger le code source
Télécharger l'exécutable pour Windows
Et voilà ce qu'on peut obtenir:
L'effet des metaballs est beaucoup plus impressionnant quand les blobs bougent.
Alors on va leur ajouter une vélocité et une fonction update() pour mettre à jour leurs positions.
class CBlob
{
public:
CBlob();
void update();
Vec2f pos;
Vec2f vel;
float radius;
};
La vélocité sera initialisée au hasard avec des valeurs entre -3 et 3:
CBlob::CBlob()
{
[...]
vel.x = ((rand() % 61) - 30) / 10.0f;
vel.y = ((rand() % 61) - 30) / 10.0f;
Dans la fonction de mise à jour, on va ajouter la vélocité à la position du blob tester chaque bord de l'écran pour
le faire rebondir.
void CBlob::update()
{
pos += vel;
if (pos.x < 0)
{
pos.x = 0;
vel.x = -vel.x;
}
if (pos.x > SCREEN_WIDTH - 1)
{
pos.x = SCREEN_WIDTH - 1;
vel.x = -vel.x;
}
if (pos.y < 0)
{
pos.y = 0;
vel.y = -vel.y;
}
if (pos.y > SCREEN_HEIGHT - 1)
{
pos.y = SCREEN_HEIGHT - 1;
vel.y = -vel.y;
}
}
Puis dans la boucle principale, on va appeler cette fonction de mise à jour pour chaque blob:
for (int i = 0; i < nbBlobs; i++)
blobs[i].update();
Télécharger le code source
Télécharger l'exécutable pour Windows
Maintenant essayons de colorer ces balles avec une simple formule de j'ai utilisé pour des fractales:
Color c;
float angle = (power + 214) * M_PI / 128;
c.r = 127 * (1 + sin(angle));
c.g = 127 * (1 + sin(angle + 2 * M_PI / 3));
c.b = 127 * (1 + sin(angle + 4 * M_PI / 3));
gfx.setPixel(x, y, c);
Télécharger le code source
Télécharger l'exécutable pour Windows
Les couleurs sont belles:
Mais ce programme est très très lent.
Alors c'est le moment d'optimiser.
Avant qu'on ne modifie le moindre code, on va chronométrer combien de temps les calculs prennent avec la fonction
SDL de chrono que j'ai déjà utilisée dans un précédent article.
Juste après le début de la boucle principale, on va lancer le chrono:
while (sys.isQuitRequested() == false)
{
sys.StartPerfCounter();
Et juste après qu'on ait mis à jour les blobs et avant qu'on fasse le rendu, on le stoppe et on affiche sa valeur.
for (int i = 0; i < nbBlobs; i++)
blobs[i].update();
float tim = sys.StopPerfCounter();
printf("%f\n", tim);
gfx.render();
Télécharger le code source
Télécharger l'exécutable pour Windows
Sur mon ordinateur avec un i7-4770K ça prend environ 93 ms pour calculer une frame. C'est vraiment lent.
Accélérer avec une palette
Evidemment la fonction sin() est beaucoup trop lente pour être calculée plusieurs fois pour chaque pixel.
Pour améliorer ça, on va pré-calculer une palette de 256 couleurs au début du programme:
static Color palette[256];
for (int i = 0; i < 256; i++)
{
float angle = (i + 64 + 150) * M_PI / 128;
palette[i].r = 127 * (1 + sin(angle));
palette[i].g = 127 * (1 + sin(angle + 2 * M_PI / 3));
palette[i].b = 127 * (1 + sin(angle + 4 * M_PI / 3));
}
Ensuite quand on dessine le pixel, on doit seulement prendre la couleur dans cette palette.
int c = (int)power;
gfx.setPixel(x, y, palette[c]);
Télécharger le code source
Télécharger l'exécutable pour Windows
Maintenant avec ce code une frame prend entre 24 et 25 ms.
Supprimer la racine carrée
La fonction mag() qu'un utilise pour avoir la distance utilise une racine carrée:
float Vec2f::mag()
{
return sqrt(squaredMag());
}
C'est une fonction très coûteuse. Mais on peut utiliser la fonction squaredMag() qui renvoie le carré de la
distance:
float Vec2f::squaredMag()
{
return x * x + y * y;
}
Maintenant le calcul de la distance dans la boucle principale aura l'air de ça:
for (int i = 0; i < nbBlobs; i++)
{
Vec2f delta = p - blobs[i].pos;
power += blobs[i].radius / delta.squaredMag();
}
Bien sur, utiliser le carré de la distance modifie radicalement le résultat des calculs.
Mais heureusement on peut compenser ça en changeant la fonction de la palette.
static Color palette[256];
for (int i = 0; i < 256; i++)
{
float angle = (pow(i, 0.64) + 78) * M_PI / 20;
Et on va devoir faire un réglage sur les rayons des blobs aussi:
radius = 4000 + (rand() % 12000);
radius *= 30;
Télécharger le code source
Télécharger l'exécutable pour Windows
Ca m'a pris du temps pour trouver la bonne formule pour la palette, et voilà le résultat:
Visuellement la fusion de 2 blobs est un peu moins impressionnante, et on peut voir un petit effet de bandes dans
la zone jaune.
Mais l'un dans l'autre on obtient quelque chose de très proche de ce qu'on avait dans le programme précédent.
Et cette version du code prend seulement 16 ms pour calculer une frame.
Maintenant on va faire quelque chose de très courant en optimisation: retirer les opérations en virgule flottante
et utiliser seulement des valeurs entières.
D'abord on va créer une structure SVec pour remplacer les vecteurs en virgule flottante.
On va l'utiliser pour la position et la vélocité des blobs. Et le rayon va être un entier aussi.
struct SVec
{
int x, y;
};
class CBlob
{
public:
CBlob();
void update();
SVec pos;
SVec vel;
int radius;
};
Le principal problème quand vous transformez tout en entiers est de garder assez de précision.
En particulier quand vous avez des vélocités. On veut être capables de bouger les blobs de moins d'un pixel par
frame.
Alors dans le constructeur je multiplie à la fois la position et la vélocité par 256.
Multiplier ou diviser par une puissance de 2 est très rapide car le compilateur peut remplacer ça par des
instructions de décalage de bits.
CBlob::CBlob()
{
pos.x = (rand() % SCREEN_WIDTH) * 256;
pos.y = (rand() % SCREEN_HEIGHT) * 256;
vel.x = (((rand() % 61) - 30) * 256) / 20;
vel.y = (((rand() % 61) - 30) * 256) / 20;
radius = 4000 + (rand() % 12000);
radius *= 30;
}
On utilise le même multiplicateur dans la fonction de mise à jour quand on teste la position avec les limites de
l'écran.
void CBlob::update()
{
pos.x += vel.x;
pos.y += vel.y;
if (pos.x < 0)
{
pos.x = 0;
vel.x = -vel.x;
}
if (pos.x > (SCREEN_WIDTH - 1) * 256)
{
pos.x = (SCREEN_WIDTH - 1) * 256;
vel.x = -vel.x;
}
if (pos.y < 0)
{
pos.y = 0;
vel.y = -vel.y;
}
if (pos.y > (SCREEN_HEIGHT - 1) * 256)
{
pos.y = (SCREEN_HEIGHT - 1) * 256;
vel.y = -vel.y;
}
}
Dans la boucle principale la variable power sera un entier aussi.
On réécrit les calcul de la distance sans utiliser les fonction de Vec2f.
Remarquez l'astuce pour arrondir la valeur de la position du blob quand on la divise par 256.
int power = 0;
for (int i = 0; i < nbBlobs; i++)
{
int dX = x - (blobs[i].pos.x + 128) / 256;
int dY = y - (blobs[i].pos.y + 128) / 256;
int dist = dX * dX + dY * dY;
Les calculs en virgule flottante géraient le cas de la division par 0. Maintenant qu'on utilise des entiers, on
doit ajouter un test pour éviter ça.
if (dist == 0)
power = 255;
else
power += blobs[i].radius / dist;
}
if (power > 255)
power = 255;
Et maintenant on n'a plus besoin de caster power en entier pour pouvoir l'utiliser comme un index de palette.
gfx.setPixel(x, y, palette[power]);
Télécharger le code source
Télécharger l'exécutable pour Windows
Maintenant on voit plus de bandes et d'interférences dans les parties jaunes à cause de la perte de précision.
On pourrait probablement faire mieux en conservant la précision à travers les opérations.
Mais le code prend seulement 10 ms par frame.
Supprimer le calcul de la position des blobs
On arrive à un point où même une simple addition et une division par une puissance de 2 commencent à être
importants comparé aux autres opérations de la boucle intérieure.
Le petit calcul que l'on fait pour la position des blobs ne semble pas être lourd, mais essayons de le sortir des
boucles qui traversent chaque pixel.
Comme les blobs se déplacent, on doit toujours le faire dans la boucle principale.
while (sys.isQuitRequested() == false)
{
sys.StartPerfCounter();
static int bX[nbBlobs];
static int bY[nbBlobs];
for (int i = 0; i < nbBlobs; i++)
{
bX[i] = (blobs[i].pos.x + 128) / 256;
bY[i] = (blobs[i].pos.y + 128) / 256;
}
for (int y = 0; y < SCREEN_HEIGHT; y++)
[...]
Puis dans la boucle intérieure on peut simplement utiliser les valeurs de ces tableaux:
int dX = x - bX[i];
int dY = y - bY[i];
int dist = dX * dX + dY * dY;
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code prend seulement 7.5 ms par frame. C'est un gain assez intéressant pour une opération si simple.
Comme la racine carrée, la division est une opération très coûteuse.
Celle qu'on utilise quand on divise le rayon par la distance n'est pas facile à supprimer.
Mais on peut essayer de la remplacer par une table pré-calculée.
Ca prendra un peu de mémoire pour chaque blob, mais l'optimisation est souvent un compromis entre l'efficacité et
l'utilisation mémoire.
Comme on divise par le carré d'une distance, c'est une grosse valeur. Alors pour éviter d'utiliser une grosse
table, on va d'abord la diviser par 128.
On ne devrait pas perdre trop de précision en faisant ça.
int dist = (dX * dX + dY * dY) / 128;
Ensuite, dans les lignes suivantes, on remplace la division par la valeur d'une table.
J'ai choisi d'utiliser une table de 2048 valeurs pour chaque blob.
if (dist == 0)
power = 255;
else if (dist < 2048)
power += div[i][dist];
Maintenant on doit juste remplir les valeurs de ces tables.
Comme elles ne changent pas on peut le faire en dehors de la boucle principale.
Remarquez que je divise le rayon par la même valeur 128 qu'on a utilisée avant.
static int div[nbBlobs][2048];
for (int i = 0; i < nbBlobs; i++)
for (int j = 1; j < 2048; j++)
div[i][j] = (blobs[i].radius / 128) / j;
while (sys.isQuitRequested() == false)
[...]
Télécharger le code source
Télécharger l'exécutable pour Windows
Visuellement il n'y a pas trop de différence par rapport à la dernière image qu'on a prise.
Mais ce code prend seulement 4 ms par frame.
Dans la boucle principale on doit tester s'il y a une division par 0.
if (dist == 0)
power = 255;
Mais on peut se débarrasser de ce test. Si vous avez remarqué on commence à remplir le tableau de divisions
pré-calculées à partir de 1, sinon on aurait eu une division par 0 dans le pré-calcul.
Mais le tableau a toujours un élément à l'index 0.
Alors on va simplement stocker le test à cet endroit.
for (int i = 0; i < nbBlobs; i++)
{
div[i][0] = 255;
for (int j = 1; j < 2048; j++)
[...]
Et dans la boucle intérieure on n'a maintenant besoin que d'un test:
int dist = (dX * dX + dY * dY) / 128;
if (dist < 2048)
power += div[i][dist];
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code prend environ 3.5 ms par frame.
Si on veut supprimer l'autre if on doit s'assurer que le tableau div sera assez grand pour stocker toutes les
valeurs possibles.
La résolution de notre écran est de 600*600. Donc la plus grande valeur pour "dX * dX + dY * dY" serait 600*600*2.
Un tableau de 2048 éléments semble un peu petit. Allons-y pour 4096.
On va devoir diviser dist par au moins 600*600*2 / 4096 = 175.
Comme avant, c'est mieux de diviser par une puissance de 2, alors on prendra 256.
Notre pré-calcul ressemblera à ça:
static int div[nbBlobs][4096];
for (int i = 0; i < nbBlobs; i++)
{
div[i][0] = 255;
for (int j = 1; j < 4096; j++)
div[i][j] = (blobs[i].radius / 256) / j;
}
Et la boucle intérieure ressemblera à ça:
for (int i = 0; i < nbBlobs; i++)
{
int dX = x - bX[i];
int dY = y - bY[i];
int dist = (dX * dX + dY * dY) / 256;
power += div[i][dist];
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Cette version a besoin d'environ 3.3 ms pour calculer une frame.
Réintégrer la racine carrée
A ce point on ne peut pas vraiment aller plus loin sans utiliser de l'assembleur.
Mais comme on a externalisé presque tous les calculs, on peut ramener la racine carrée dans le tableau de division
pré-calculé.
On va même réutiliser des flottants pour ce tableau et pour la variable power.
for (int j = 1; j < 4096; j++)
div[i][j] = (float)blobs[i].radius / sqrt(j * 256);
Notre boucle de pixel sera maintenant:
float power = 0;
for (int i = 0; i < nbBlobs; i++)
{
int dX = x - bX[i];
int dY = y - bY[i];
int dist = (dX * dX + dY * dY) / 256;
power += div[i][dist];
}
int p = int(power);
if (p > 255)
p = 255;
gfx.setPixel(x, y, palette[p]);
On doit aussi utiliser la palette d'origine:
float angle = (i + 64 + 150) * M_PI / 128;
Et les rayons d'origine:
radius = 2000 + (rand() % 6000);
Télécharger le code source
Télécharger l'exécutable pour Windows
Maintenant cette version prend environ 4.2 ms par frame, Mais le résultat est beaucoup plus impressionnant:
Vous remarquerez un peu d'effets de bandes sur les plus petits blobs. Ca vient de la pré-division de dist par 256
avant d'utiliser le tableau div.
Quoi qu'il en soit j'espère que vous avez apprécié cette session d'optimisation.
Vidéo: Metaballs en Processing