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.
L'ensemble de Mandelbrot est un objet mathématique célèbre que vous avez probablement déjà vu.
En dehors de ses qualités esthétiques c'est une représentation graphiques de certaines propriétés des nombres qui
ont un sens profond dans plusieurs branches des mathématiques.
C'est surement la fractale la plus célèbre. Et on peut y trouver une grande variété de formes.
A pleine échelle, on peut clairement voir l'autosimilarité des formes circulaires et les branches qui ressemblent à
des éclairs.
Si vous zoomez sur une se ses parties, vous découvrirez des spirales et des motifs ressemblant à de la dentelle.
Il y a de bons logiciels créés pour vous permettre d'explorer cet ensemble en détail. Je vais seulement expliquer
ici un petit programme pour le dessiner à pleine échelle, et quelques trucs pour l'afficher plus rapidement et le
rendre plus beau.
Bien que ça ait l'air d'être une forme complexe, l'ensemble de Mandelbrot n'est pas si difficile à dessiner. Ca
demande seulement un peu d'arithmétique.
Pour dessiner l'ensemble de Mandelbrot il faut que vous sachiez ce qu'est un nombre complexe.
Les nombres complexes ont été inventés au 16
ième siècle pour résoudre des équations polynomiales.
Ils sont communément notés "z" et ils ressemblent à ça:
z = a + b*i
a et b sont des nombres rééls.
i est appelée l'unité imaginaire (ou parfois la base des imaginaires purs). La seule chose qu'on ait besoin de
savoir à propos d'elle c'est que:
i2 = -1
Comme vous le savez, le carré d'un nombre est toujours positif. Donc un nombre comme i ne devrait pas exister, mais
il s'avère que si on accepte qu'un nombre comme ça existe, ça nous permet de résoudre des équations très
compliquées.
Dans le nombre z, "a" est appelé la partie réelle et "b*i" est la partie imaginaire.
Maintenant, il va falloir comprendre 2 opérations qu'on peut effectuer sur ces nombres: l'addition et la
multiplication.
Alors considérons qu'on a 2 nombres complexes:
z1 = a1 + b1*i
z2 = a2 + b2*i
Quand on les additionne
z1 + z2 = a1 + b1*i + a2 + b2*i
si on regroupe ensemble les termes réels et imaginaires:
z1 + z2 = (a1 + a2) + (b1 + b2)*i
On obtient un nouveau nombre complexe dont la partie réelle est (a
1+a
2) et la partie imaginaire (b
1+b
2)*i
Maintenant multiplions-les:
z1 * z2 = (a1 + b1*i) * (a2 + b2*i)
= a1*a2 + a1*b2*i + b1*a2*i + b1*b2*i2
Comme i
2 = -1. Alors on a:
z1 * z2 = (a1*a2 - b1*b2) + (a1*b2 + b1*a2)*i
Encore une fois on obtient un nombre complexe avec une partie réelle et une partie imaginaire.
En particulier, si on multiplie un nombre par lui-même, on a:
z2 = (a2 - b2) + (2*a*b)*i
Maintenant pensons à une autre façon de voir les nombres complexes.
On a dit qu'un nombre complexe contient 2 nombres réels (un dans la partie réelle et un dans la partie imaginaire).
Si on considère ces 2 nombres réels comme des coordonnées, on pourrait représenter le nombre complexe à l'écran.
D'abord on va réfléchir à un système de coordonnées pour localiser nos nombres.
Disons qu'on a un axe horizontal pour la partie réelle du nombre. Une unité le long de cet axe représente le nombre réel 1.
L'axe vertical sera pour la partie imaginaire. Une unité le long de cet axe sera i.
Alors chaque nombre complexe apparaîtra comme un point dans ce système de coordonnées.
Par exemple, le nombre 3 + 2*i sera représenté comme ça.
Maintenant, imaginons que notre écran représente une partie limitée de ce plan.
Disons par exemple qu'il est centré sur l'origine et qu'il s'étend de -2 à 2 le long de chaque axe.
Pour chaque pixel sur notre écran, on peut retrouver les coordonnées correspondantes dans le plan et ça nous donne
un nombre complexe.
L'idée pour dessiner l'ensemble de Mandelbrot est de parcourir chaque pixel et de mettre sa couleur en fonction
d'un calcul sur le nombre complexe correspondant.
Appelons c le nombre complexe associé à notre pixel.
On va calculer les valeurs successives de la fonction définie par:
z0 = 0
zn+1 = zn2 + c
où les valeurs de z sont des nombres complexes.
On va faire ça jusqu'à ce que z devienne trop grand ou que n atteigne une valeur maximale n
max.
Ensuite on mettra la couleur du pixel en fonction du nombre d'itérations "n" qu'on a atteint au moment où z a
dépassé la limite.
Ou on le mettra en noir si on a atteint n
max et que z n'est jamais devenu trop grand.
Mais qu'est-ce que ça veut dire "devenir trop grand" pour un nombre complexe ?
Eh bien, comme on peut représenter un nombre complexe comme un point dans le plan, on va définir son "module" comme
la distance de ce point à l'origine.
Donc si z = a + b*i, en appliquant le théorème de Pythagore son module est √(a
2+b
2).
Comme on veut juste vérifier si le module devient plus grand qu'une certaine valeur, on peut se passer de la racine
carrée et tester si (a
2+b
2) est plus grand que disons 16.
Voici un petit exemple. Supposons que c = 2 + 2*i. On va calculer:
z0 = 0
z1 = 02 + (2 + 2*i) = 2 + 2*i
z2 = (2 + 2*i)2 + (2 + 2*i)
...
Et ainsi de suite jusqu'à ce que z devienne trop grand ou que l'on atteigne le n
max-ième terme.
Comme on va utiliser n pour la couleur, choisir n
max à 256 serait pratique.
Alors voici notre premier programme
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "main.h"
#include "Graphics.h"
#include "System.h"
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define MAX_ITERATIONS 256
int main(int argc, char* argv[])
{
// init the window
gfx.init("Mandelbrot", SCREEN_WIDTH, SCREEN_HEIGHT);
gfx.init2D();
gfx.clearScreen(Color(0, 0, 0, SDL_ALPHA_OPAQUE));
for (int y = 0; y < SCREEN_HEIGHT; y++)
for (int x = 0; x < SCREEN_WIDTH; x++)
{
// convert the pixel pos to a complex number
double c_re = (x - SCREEN_WIDTH / 2.0) * 4.0 / SCREEN_WIDTH - 0.7;
double c_im = (y - SCREEN_HEIGHT / 2.0) * 4.0 / SCREEN_WIDTH;
double z_re = 0;
double z_im = 0;
int iteration = 0;
while (z_re * z_re + z_im * z_im <= 16 &&
iteration < MAX_ITERATIONS)
{
// compute the new value
double zn_re = z_re * z_re - z_im * z_im + c_re;
double zn_im = 2 * z_re * z_im + c_im;
// copy back the result to z
z_re = zn_re;
z_im = zn_im;
iteration++;
}
// draw the pixel
Color col;
if (iteration == MAX_ITERATIONS)
col = Color(0, 0, 0);
else
col = Color(iteration, iteration, iteration/2 + 128);
gfx.setPixel(x, y, col);
// display and process the events
gfx.render();
sys.processEvents();
if (sys.isQuitRequested() == true)
exit(EXIT_SUCCESS);
}
// wait until we quit
while (sys.isQuitRequested() == false)
{
sys.processEvents();
sys.wait(50);
}
gfx.quit();
return EXIT_SUCCESS;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Remarquez qu'à chaque pixel on appelle gfx.render() parce que je voulais que ça soit animé et qu'on puisse voir
comment le programme travaille.
Mais ça semble être un peu trop lent.
Le résultat de ce programme est l'image au début de cet article.
Dessiner en suivant un motif
Pour accélérer le dessin, je voulais changer l'ordre des pixels qu'on dessine.
On va dessiner seulement 1 pixel sur 8 le long de l'axe x et de l'axe y puis on va répéter ça avec un point de
départ différent.
On va faire ça de façon à remplir l'écran uniformément en suivant un motif de tramage.
Voici les pixels qui seront dessiné dans les 4 premières étapes.
De cette façon, on pourra voir le contour de l'ensemble très tôt, puis les détails apparaîtront petit à petit.
D'abord on doit modifier notre dessin du Mandelbrot pour qu'il ne dessine qu'1 point sur 8.
void drawMandelbrot(int offsetx, int offsety)
{
for (int y = 0; y < SCREEN_HEIGHT; y += 8)
{
for (int x = 0; x < SCREEN_WIDTH; x += 8)
{
// convert the pixel pos to a complex number
double c_re = (x + offsetx - SCREEN_WIDTH / 2.0) * 4.0 / SCREEN_WIDTH - 0.7;
double c_im = (y + offsety - SCREEN_HEIGHT / 2.0) * 4.0 / SCREEN_WIDTH;
double z_re = 0;
double z_im = 0;
int iteration = 0;
while (z_re * z_re + z_im * z_im <= 16 &&
iteration < MAX_ITERATIONS)
{
// compute the new value
double zn_re = z_re * z_re - z_im * z_im + c_re;
double zn_im = 2 * z_re * z_im + c_im;
// copy back the result to z
z_re = zn_re;
z_im = zn_im;
iteration++;
}
// draw the pixel
Color col;
if (iteration == MAX_ITERATIONS)
col = Color(0, 0, 0);
else
col = Color(iteration, iteration, iteration/2 + 128);
gfx.setPixel(x + offsetx, y + offsety, col);
}
}
}
Ensuite, le code principal appellera cette fonction avec un offset qui viendra d'une table.
Cette table est une matrice de Bayer utilisée pour le tramage ordonné. J'écrirai probablement un article à propos
de ça un jour.
int main(int argc, char* argv[])
{
// init the window
gfx.init("Mandelbrot 2", SCREEN_WIDTH, SCREEN_HEIGHT);
gfx.init2D();
gfx.clearScreen(Color(0, 0, 0, SDL_ALPHA_OPAQUE));
static Uint8 pattern[64] =
{
0, 32, 8, 40, 2, 34, 10, 42,
48, 16, 56, 24, 50, 18, 58, 26,
12, 44, 4, 36, 14, 46, 6, 38,
60, 28, 52, 20, 62, 30, 54, 22,
3, 35, 11, 43, 1, 33, 9, 41,
51, 19, 59, 27, 49, 17, 57, 25,
15, 47, 7, 39, 13, 45, 5, 37,
63, 31, 55, 23, 61, 29, 53, 21
};
for (int i = 0; i < 64; i++)
{
int j = 0;
while (pattern[j] != i)
j++;
drawMandelbrot(j % 8, j / 8);
// display and process the events
gfx.render();
sys.wait(50);
sys.processEvents();
if (sys.isQuitRequested() == true)
exit(EXIT_SUCCESS);
}
// wait until we quit
while (sys.isQuitRequested() == false)
{
sys.processEvents();
sys.wait(50);
}
gfx.quit();
return EXIT_SUCCESS;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ensuite j'ai écrit une classe pour les nombres complexes.
class Complex
{
public:
Complex(double _re = 0.0, double _im = 0.0);
double squareMag();
double mag();
void operator=(const Complex rhs);
Complex operator+(const Complex rhs);
Complex operator*(const Complex rhs);
double re;
double im;
};
Ca simplifie grandement la fonction de dessin.
void drawMandelbrot(int offsetx, int offsety)
{
for (int y = 0; y < SCREEN_HEIGHT; y += 8)
{
for (int x = 0; x < SCREEN_WIDTH; x += 8)
{
// convert the pixel pos to a complex number
Complex c;
c.re = (x + offsetx - SCREEN_WIDTH / 2.0) * 4.0 / SCREEN_WIDTH - 0.7;
c.im = (y + offsety - SCREEN_HEIGHT / 2.0) * 4.0 / SCREEN_WIDTH;
Complex z;
int iteration = 0;
while (z.squareMag() <= 16 &&
iteration < MAX_ITERATIONS)
{
// compute the new value
z = z * z + c;
iteration++;
}
// draw the pixel
Color col;
if (iteration == MAX_ITERATIONS)
col = Color(0, 0, 0);
else
col = Color(iteration, iteration, iteration/2 + 128);
gfx.setPixel(x + offsetx, y + offsety, col);
}
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Et maintenant on peut facilement changer la formule. Par exemple, voilà ce que z
n+1 = z
n3 + c donne:
Jusqu'à maintenant j'ai mis la couleur des pixel en utilisant une formule simple pour avoir un dégradé du bleu au
blanc.
Mais avec les bonnes couleurs on peut voir beaucoup plus de détails de l'ensemble de Mandelbrot.
Comme dans notre cas n
max = 256, on va utiliser une palette de 256 couleurs.
Il y a beaucoup de techniques pour calculer cette palette. Il apparaît que pour avoir le plus de détails, les
couleurs ne devraient pas suivre une distribution linéaire.
Je ne voulais pas faire quelque chose de trop complexe. Alors j'ai seulement joué un peu avec des sinus pour avoir
une palette un peu plus colorée.
// set up the palette
for (int i = 0; i < 256; ++i)
{
float angle = 2.0 * M_PI * (float)i / 256.0;
float offset = 2.0 * M_PI / 3.0;
angle += 40.0 * M_PI / 128.0;
angle *= 1.3;
palette[i].r = 128 + 128 * sin(angle);
palette[i].g = 128 + 128 * sin(angle * 1.1 - offset);
palette[i].b = 128 + 128 * sin(angle * 1.5 + offset);
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Et voilà à quoi ça ressemble:
Chaque fois que vous regardez une image de l'ensemble de Mandelbrot, seul l'extérieur est coloré. L'intérieur est
toujours noir.
Je voulais voir ce qui se cachait dans cette partie noire.
Mais on choisit la couleur des pixels en fonction du nombre d'itérations.
Et les pixels de l'intérieur ont tous atteint le nombre d'itérations maximum n
max.
Alors on va les colorier en fonction du module du z qu'on a atteint après ces itérations.
// draw the pixel
Color col;
if (iteration == MAX_ITERATIONS)
{
int v = (int)(z.mag() * 128.0) % 256;
col = palette[v];
}
else
{
col = Color(0, 0, 0);
}
gfx.setPixel(x + offsetx, y + offsety, col);
Télécharger le code source
Télécharger l'exécutable pour Windows
Et voilà à quoi ressemble l'intérieur.
Vidéo: Ensemble de Mandelbrot en p5.js