0xBADDC0DE

L’ensemble de Mandelbrot est une fractale bien connue pour son aspect si particulier en forme de cardioïde :

Cet ensemble est défini selon une formule relativement simple que nous verrons plus loin. Mais comme cette formule fait intervenir les nombres complexes, un petit rappel ne fera pas de mal.

Les nombres complexes

Si l’on se limite à l’ensemble des nombres réels (), il est impossible de calculer la racine carrée d’un nombre négatif, comme par exemple .

L’ensemble des nombres complexes () permet de résoudre ce genre de problème. L’idée est de nommer le résultat de par la lettre i. Cette lettre représente la partie imaginaire du nombre. Ainsi :

$$\sqrt{-16}=\sqrt(-1\cdot 16)=\sqrt(-1)\cdot\sqrt(16)=i4$$

On dit que i4 est la partie imaginaire d’un nombre. Rien n’empêche qu’un nombre complexe possède également une partie réelle. On note donc un nombre complexe sous la forme (a + ib), où a est la partie réelle et b la partie imaginaire.

Comme les nombres réels sont constitués de deux composantes (la partie réelle et la partie imaginaire), il est facile de les représenter graphiquement sur un plan. Par convention, la partie réelle du nombre est dessinée en abscisse et la partie imaginaire en ordonnée. Voici par exemple la représentation du nombre complexe (3 + i4) :

Plutôt que d’utiliser la forme (a + ib), il est également possible de représenter un nombre complexe par son module (la longueur du segment) et son argument (l’angle). On parle de notation polaire.

Le module, noté |z|, se calcule facilement au moyen du théorème de Pythagore :

$$|z|=\sqrt{a^{2}+b^{2}}$$

Opérations utiles

L’addition et la multiplication de nombres complexes est associative, commutative et distributive, au même titre qu’avec les nombres réels.

L’addition de deux nombres complexes (a+ib) et (a’+ib’) est une opération très simple :

$$(a + ib) + (a{}’ + ib{}’) = a+a{}’ + i(b+b{}’)$$

La multiplication de deux nombres complexes est une opération également relativement simple :

$$(a + ib) \cdot (a{}’ + ib{}’) = aa{}’ + aib{}’ + iba{}’ + i^{2}bb{}’$$

Comme i²= -1, on peut donc écrire :

$$(a + ib) \cdot (a{}’ + ib{}’) = aa{}’ – bb{}’ + i(ab{}’+a{}’b)$$

Pour représenter graphiquement l’ensemble de Mandelbrot, nous n’aurons pas besoin d’autres opérations.

L’ensemble de Mandelbrot

Un nombre complexe C fait partie de l’ensemble de Mandelbrot si la suite < ne tend pas vers l'infini (en module). . Il a été démontré en 1990 que cet ensemble a une dimension de Hausdorff de 2. Cela signifie que dès que le module de cette suite dépasse 2, c’est que le nombre en question ne fait pas partie de l’ensemble de Mandelbrot.

À savoir également que l’ensemble de Mandelbrot est compris entre les nombres complexes (-2.1 – i1.2) et (0.6 + i1.2).

Représentation de l’ensemble de Mandelbrot

Pour afficher à l’écran l’ensemble de Mandelbrot, l’idée est d’associer à la surface de la fenêtre un intervalle de nombres complexes. Ainsi, chaque pixel de la fenêtre représente un nombre complexe pour lequel on pourra déterminer s’il appartient ou non à l’ensemble.

Il faut donc, pour chaque pixel de l’écran déterminer à quel nombre complexe il correspond, puis vérifier si ce nombre fait partie de l’ensemble de Mandelbrot. Si c’est le cas, le pixel sera affiché en noir. Sinon, il restera en blanc.

La plupart des langages de programmation ne permettent pas de manipuler en standard les nombres complexes. Toutefois, le calcul de la suite étant assez simple, il est facile de la calculer au moyen de nombres réels uniquement.

Posons et .

Calculons :

$$Z_{n+1}=Z_{n}\cdot Z_{n} + C=(Za_{n}+iZb_{n})\cdot (Za_{n}+iZb_{n}) + (Ca+ib)$$

$$Z_{n+1}=Za{_{n}}^{2}-Zb{_{n}}^{2}+i(2\cdot Za_{n} \cdot Zb_{n}) + Ca+iCb$$

Nous obtenons donc les calculs réels suivants :

$$Za_{n+1}=Z{_{na}}^{2}-Z{_{nb}}^{2}+Ca$$

$$Zb_{n+1}=2\cdot Za_{n} \cdot Zb_{n} + Cb$$

Reste à calculer cette suite pour déterminer si elle converge vers l’infini ou pas.

Nous avons vu plus haut que dès que le module de Z dépasse 2, il est certain que le nombre complexe en question ne fait pas partie de l’ensemble de Mandelbrot.

Il faut tester si le module est inférieur à 2 :

$$|z| < 2$$

Donc :

$$\sqrt{a^{2}+b^{2}} < 2$$

Nous pouvons simplifier le calcul en élevant les deux termes au carré :

$$a^{2}+b^{2} < 4$$

Par contre, si le nombre fait partie de l’ensemble, il faudrait calculer la suite à l’infini, ce qui n’est bien sûr pas réaliste. L’idée est donc de calculer les éléments de la suite jusqu’à un nombre d’itérations maximal, par exemple 200. Si après 200 itérations, le module de Z ne dépasse pas 2, on considère que la suite ne tend pas vers l’infini et que le nombre complexe fait partie de l’ensemble de Mandelbrot.

Il est donc impossible de dessiner cet ensemble de façon exacte. Sa représentation est une approximation dont l’exactitude dépend du nombre maximal d’itérations.

Algorithme

Voici l’algorithme permettant de vérifier si un nombre complexe C fait partie de l’ensemble de Mandelbrot :

procédure déterminant si C fait partie de l'ensemble de Mandelbrot
données : C : complexe
          Ca, Cb, Za, Zb, ZaTemp : réels
          Iteration, MaxIteration : entiers

début
   MaxIteration ← 200
   Ca ← partie réelle de C
   Cb ← partie imaginaire de C

   Za ← 0
   Zb ← 0

   Iteration ← 0

   tant que Za*Za + Zb*Zb < 4 et Iteration < MaxIteration faire
      ZaTemp ← Za*Za-Zb*Zb+Ca
      Zb ← 2*Za*Zb+Cb
      Za ← ZaTemp
      Iteration ← Iteration+1
   fin tant que

   si Iteration = MaxIteration alors
      le point fait partie de l'ensemble de Mandelbrot
   sinon
      le point ne fait pas partie de l'ensemble de Mandelbrot
   fin si
fin

Reste à utiliser cet algorithme pour dessiner quelque chose à l’écran. Il faut donc passer en revue chaque pixel de l’écran, déterminer à quels nombres complexes ils correspondent et les afficher s’ils appartiennent à l’ensemble de Mandelbrot.

Pour simplifier les choses, et comme l’ensemble de Mandelbrot est symétrique par l’abscisse, nous pouvons inverser l’orientation mathématique de l’axe imaginaire (l’ordonnée, axe vertical) afin qu’il soit dans la même direction que l’axe vertical d’affichage de l’écran.

procédure dessin de l'ensemble de Mandelbrot
données : LargeurEcran, HauteurEcran, Ligne, Colonne : entiers
          IntervalleComplexeGauche, IntervalleComplexeHaut,
          IntervalleComplexeDroite, IntervalleComplexeBas : réels
début
   IntervalleComplexeGauche ← -2.1
   IntervalleComplexeHaut ← 1.2
   IntervalleComplexeDroite ← 0.6
   IntervalleComplexeBas ← -1.2

   pour Ligne allant de 0 à HauteurEcran faire
      pour Colonne allant de 0 à LargeurEcran faire
         Ca ← Colonne * (IntervalleComplexeDroite - IntervalleComplexeGauche) / LargeurEcran + IntervalleComplexeGauche
         Cb ← Ligne * (IntervalleComplexeBas - IntervalleComplexeHaut) / HauteurEcran + IntervalleComplexeHaut

         si (Ca,Cb) fait partie de l'ensemble de Mandelbrot faire
            dessiner en Colonne, Ligne un point noir
         sinon
            dessiner en Colonne, Ligne un point blanc
         fin si
      fin pour
   fin pour
fin

 Implémentation en C++ avec Qt

Voici une implémentation simple en C++ et Qt des algorithmes présentés ci-dessus.

#include <QtGui/QApplication>

#include <QImage>
#include <QLabel>

const int IMAGE_WIDTH = 1024;
const int IMAGE_HEIGHT = 1024;

const int MAX_ITERATION = 200;

const unsigned int WHITE = 0x0FFFFFFFF;
const unsigned int BLACK = 0x0FF000000;

bool isInMandelbrotSet(double Ca, double Cb);

// Programme principal
int main(int ArgC, char *ArgV[]) {
    QApplication App(ArgC, ArgV);

    // Construit une image vide
    QImage Image(IMAGE_WIDTH, IMAGE_HEIGHT, QImage::Format_RGB32);
    Image.fill(WHITE);

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

    // Vérifie si les points font partie de l'ensemble de Mandelbrot
    for (int Line = 0; Line < IMAGE_HEIGHT; ++Line) {
        for (int Col = 0; Col < IMAGE_WIDTH; ++Col) {
            double Ca = Col * ComplexArea.width() / IMAGE_WIDTH + ComplexArea.left();
            double Cb = Line * ComplexArea.height() / IMAGE_HEIGHT + ComplexArea.top();

            if (isInMandelbrotSet(Ca, Cb))
                Image.setPixel(Col, Line, BLACK);
        }
    }

    // Affiche l'image dans une fenêtre
    QPixmap MandelbrotPixmap = QPixmap::fromImage(Image);
    QLabel Label;
    Label.setWindowTitle("Mandelbrot");
    Label.setPixmap(MandelbrotPixmap);
    Label.setMinimumSize(IMAGE_WIDTH, IMAGE_HEIGHT);
    Label.show();

    return App.exec();
}

// Détermine si le nombre complexe défini par Ca+iCb fait
// partie de l'ensemble de MandelBrot.
bool isInMandelbrotSet(double Ca, double Cb) {
    double Za = 0;
    double Zb = 0;

    int Iteration = 0;

    while (Za*Za + Zb*Zb < 4. && Iteration < MAX_ITERATION) {
        double ZaTemp = Za * Za - Zb * Zb + Ca;
        Zb = 2. * Za * Zb + Cb;
        Za = ZaTemp;
        ++Iteration;
    }

    return Iteration == MAX_ITERATION;
}

Et voilà le résultat :

Représentation colorée

Si vous avez déjà vu des représentations de l’ensemble de Mandelbrot, vous serez sans doute déçus par le résultat austère, noir et blanc, obtenu.

Toutefois, la représentation ci-dessus est conforme à la donnée mathématique : les points noirs sont ceux qui font partie de l’ensemble de Mandelbrot.

Par contre, ce qui est intéressant, ce sont les points qui ne font pas partie de l’ensemble. Au bout d’un certain nombre d’itérations, ces points sont exclus. L’idée est alors de leur donner un couleur, différente selon le nombre d’itérations qu’il a fallu pour les exclure.

Solution simple

Un ordinateur est capable de recréer des millions de couleurs en mélangeant (synthèse additive) les trois couleurs primaires rouge, vert et bleu.

Pour chaque couleur primaire, il est possible de donner une intensité comprise en zéro (noir) et 255 (couleur vive).

Nous pourrions donc fixer à 256 le nombre maximal d’itérations dans notre algorithme. Dès lors, il suffit d’utiliser directement le nombre d’itérations obtenu comme intensité d’une des couleurs de base, par exemple le rouge.

Si le nombre maximal (256) est atteint le point sera dessiné en noir.

Le programme doit être modifié de telle sorte que la méthode isInMandelbrotSet() retourne un paramètre supplémentaire contenant le nombre d’itérations.

#include <QtGui/QApplication>

#include <QImage>
#include <QLabel>

const int IMAGE_WIDTH = 1024;
const int IMAGE_HEIGHT = 1024;

const int MAX_ITERATION = 256;

const unsigned int WHITE = 0x0FFFFFFFF;
const unsigned int BLACK = 0x0FF000000;

bool isInMandelbrotSet(double Ca, double Cb, int* pIterationCount = 0);

// Programme principal
int main(int ArgC, char *ArgV[])
{
    QApplication App(ArgC, ArgV);

    // Construit une image vide
    QImage Image(IMAGE_WIDTH, IMAGE_HEIGHT, QImage::Format_RGB32);
    Image.fill(WHITE);

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

    // Vérifie si les points font partie de l'ensemble de Mandelbrot
    for (int Line = 0; Line < IMAGE_HEIGHT; ++Line) {
        for (int Col = 0; Col < IMAGE_WIDTH; ++Col) {
            double Ca = Col * ComplexArea.width() / IMAGE_WIDTH + ComplexArea.left();
            double Cb = Line * ComplexArea.height() / IMAGE_HEIGHT + ComplexArea.top();

            int Iteration = 0;
            if (isInMandelbrotSet(Ca, Cb, &Iteration))
                Image.setPixel(Col, Line, BLACK);
            else
               Image.setPixel(Col, Line, Iteration*256*256);
        }
    }

    // Affiche l'image dans une fenêtre
    QPixmap MandelbrotPixmap = QPixmap::fromImage(Image);
    QLabel Label;
    Label.setWindowTitle("Mandelbrot");
    Label.setPixmap(MandelbrotPixmap);
    Label.setMinimumSize(IMAGE_WIDTH, IMAGE_HEIGHT);
    Label.show();

    return App.exec();
}

// Détermine si le nombre complexe défini par Ca+iCb fait
// partie de l'ensemble de MandelBrot.
bool isInMandelbrotSet(double Ca, double Cb, int* pIterationCount) {
    double Za = 0;
    double Zb = 0;

    int Iteration = 0;

    while (Za*Za + Zb*Zb < 4. && Iteration < MAX_ITERATION) {
        double ZaTemp = Za * Za - Zb * Zb + Ca;
        Zb = 2. * Za * Zb + Cb;
        Za = ZaTemp;
        ++Iteration;
    }

    if (pIterationCount)
       *pIterationCount = Iteration;
    return Iteration == MAX_ITERATION;
}

Voilà le résultat obtenu :

Il y a sans doute moyen de faire mieux !

Le problème vient du fait que la surface éloignée de l’ensemble de Mandelbrot est très sombre, car il faut peu d’itérations pour déterminer que ces points ne font pas partie de l’ensemble.

Par contre, pour les points proches de la frontière de l’ensemble, les variations du nombre d’itérations sont plus marquées, mais le choix des couleurs ne rend pas compte de cette diversité.

Solution avancée

La meilleure solution est donc de mettre au point un dégradé de couleurs. Toute la difficulté sera de choisir judicieusement les couleurs constituant ce dégradé.

Voici un dégradé possible :

Les couleurs clés sont les suivantes :

Position	Couleur	R	V	B	Hexadécimal
0 %	rouge foncé	128	0	0	800000h
20 %	jaune	255	255	0	FFFF00h
40 %	orange	255	165	0	FFA500h
60 %	pourpre	160	32	240	A020F0h
80 %	bleu nuit	25	25	112	191970h
100 %	rouge foncé	128	0	0	800000h

Et voilà le résultat correspondant :

Le rendu est bien plus satisfaisant !

La principale difficulté consiste donc à programmer le dégradé de couleur, en particulier en ce qui concerne les couleurs intermédiaires.

Pour ce faire, le plus simple est de coder une classe capable de gérer un dégradé entre certaines couleurs clé.

Le code étant trop long pour être affiché sur cette page, il peut être téléchargé : Projet Qt : MandelBrotGUI

À la découverte de la fractale

La partie amusante peut maintenant commencer : changer l’intervalle affiché afin d’admirer de magnifiques figures fractales.

C’est la ligne suivante qui détermine l’intervalle qui sera affiché :

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

Le premier nombre indique la limite gauche de l’intervalle (-2.2). Le deuxième nombre, sa limite haute (-1.5). Les deux derniers nombres indiquent la largeur et la hauteur de l’intervalle (3). Pour un affichage dans une fenêtre carrée, il faudrait que la largeur et la hauteur soient identiques.

Observons ce que l’on obtient avec les valeurs suivantes : -0.83, -0.21, 0.05, 0.05. La ligne de code devient QRectF ComplexArea(-0.83, -0.21, 0.05, 0.05);

Lissage des couleurs

Cette vue spectaculaire souffre toutefois encore d’un petit défaut : le dégradé de couleurs présente un effet d’escaliers. C’est la conséquence d’utiliser directement le nombre d’itérations pour obtenir une couleur, qui est un nombre entier. Le résultat est donc discret (à l’opposé de continu), ce qui provoque  dans certaines situations ces escaliers disgracieux.

Pour y remédier il existe différents algorithmes dont le normalized iteration count*. Il permet de calculer une variation décimale du nombre d’itérations pour obtenir un dégradé plus fin.

La formule est la suivante :

$$n+\frac{\log (\log b)-\log(\log \left | Z_{n} \right |)}{\log 2}$$

où n est le nombre d’itérations et b le rayon de sortie (qui correspond à la dimension de Hausdorff et qui vaut donc 2 dans notre cas).

L’amélioration est nette :

Essayons d’autres valeurs : -0.749, -0.177488, 0.02, 0.02. La ligne de code devient QRectF ComplexArea(-0.749, -0.177488, 0.02, 0.02);

Nombre d’itérations

Nous avons vu plus haut que pour déterminer si un nombre fait partie de l’ensemble ou pas, il faudrait théoriquement calculer la suite à l’infini. Une approximation est donc réalisée en limitant le nombre d’itérations effectué lors du calcul de la suite.

Le problème d’une telle approximation, c’est que lorsqu’on veut afficher des détails, elle a un impact direct sur la précision obtenue.

Voici, pour les valeurs -0.726277, -0.257609, 0.000332257, 0.000332257 le résultat avec une limite de 256 itérations :

La cardioïde est passablement déformée. Voici une meilleure approximation avec une limite de 512 itérations :

Avec une limite de 1024 itérations :

Et enfin avec une limite de 2048 itérations :

Toute la difficulté revient à trouver une limite qui donne de bons résultats, en un temps acceptable !

---

Sources :

Wikipédia : Ensemble de Mandelbrot

Wikipedia : Mandelbrot set

Coloring dynamical systems in the complex plane, Garcia, Fernandez, Barrallo, Martin

Tags: C++, maths, Qt

This entry was posted on Saturday, February 18th, 2012 at 10:43 pm and is filed under Développement. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.