Mandelbulb

Piste rouge 16 janvier 2010  - Rédigé par  Jos Leys Voir les commentaires (2)

... ou la quête de l’ensemble Mandelbrot en trois dimensions.

Il y a un mois, on voyait apparaître un peu partout sur internet des images d’une nouvelle famille d’ensembles fractals. C’est un groupe d’amateurs, enthousiastes d’images fractales, qui en ont fait la découverte en collaborant dans un forum. Une discussion en ligne sur le sujet du « vrai Mandelbrot 3D » a démarré en septembre et avait plus de 500 contributions vers la fin de novembre. Des dizaines de personnes ont participé en faisant des suggestions de modifications sur les formules et sur les techniques de visualisations, mais on doit attribuer l’idée pour le Mandelbulb , le « bulbe Mandelbrot » à Daniel White et Paul Nylander .

De quoi s’agit-il ?


De nombreux lecteurs connaissent probablement l’image de gauche qui est l’ensemble Mandelbrot en 2D. Pour chaque nombre complexe $c$, on considère la transformation du plan complexe définie par $z \mapsto z^2+c$. Partant de $z_0=0$, on itère cette transformation, c’est-à-dire qu’on construit la suite $z_n$ avec $z_{n+1}= z_n^2+c$. L’ensemble de Mandelbrot est l’ensemble des $c$ qui sont tels que la suite $z_n$ ne tend pas vers l’infini quand l’entier $n$ tend vers l’infini.

Prendre le carré du nombre complexe $z$ revient à doubler l’argument et à élever au carré le module . On ajoute ensuite $c$. On obtient un nouveau point et on répète les mêmes opérations. Certains points vont rester près de l’origine, même après beaucoup d’itérations, et d’autres s’envolent vers l’infini. L’ensemble de Mandelbrot est donc la figure formée par les points $c$ tels que l’origine $0$ ne s’envole pas dans ce processus.

La figure est fractale : même élargie à l’extrême on voit des détails époustouflants (voir par exemple ce film, extrait de Dimensions, où on peut aussi voir l’effet de prendre le carré d’un nombre complexe sur une photo).

Il ne faut pas se limiter au carré d’un nombre complexe. Si on itère $z\mapsto z^p+c$, avec n’importe quel nombre $p$, on obtiendra aussi un ensemble de Mandelbrot. Voici les ensembles avec $p=3$, $p=4$ et $p=8$. Sur cette dernière image, remarquez les « bulbes » qui entourent la figure. Nous les rencontrerons à nouveau dans ce qui suit.

Depuis sa découverte en 1979 par Benoît Mandelbrot, de très nombreux amateurs ont créé des images fractales basées sur la simple formule d’itération que nous avons vue. Voilà donc une chose dont on a des millions de peintures, mais aucune sculpture !

Une question est devenue comme le Graal des amateurs de fractales : existe-t-il un équivalent en trois dimensions de l’ensemble Mandelbrot ?

L’ensemble Mandelbrot consiste d’une cardioïde entourée de cercles de toutes tailles, qui à leur tour sont entourés de différentes formes, comme des spirales, qui deviennent de plus en plus petites. Il y a des vrilles où poussent des copies minuscules de l’ensemble.

En trois dimensions, on imagine donc un corps principal muni de quelques sphères, et sur les sphères des sphères plus petites, etc. Il va de soi qu’on aimerait voir des vrilles où poussent des copies minuscules de l’ensemble qui à leur tour ont des vrilles microscopiques, etc.

Il faut dire tout de suite que personne n’a encore trouvé un tel objet mais, d’autre part, on n’a pas encore démontré qu’un tel objet n’existe pas. Cela donne la motivation aux amateurs de fractales de continuer leur quête !

Le « Bristorbrot »

Comment pourrait-on essayer de trouver un tel objet ? Voici un premier effort :

Pour l’ensemble de Mandelbrot, on a besoin de nombres complexes $z=a+ib$, avec $i^2=-1$. On a donc :
\[z^2=(a+ib)^2=a^2-b^2+i2ab.\]
On met la partie réelle $a^2-b^2$ sur l’axe $x$, et la partie imaginaire $2ab$ sur l’axe $y$. En trois dimensions il nous faudrait donc un nombre « supercomplexe » comme $w=a+ib+jc$, pour qu’on ait quelque chose à mettre sur une troisième axe $z$. Appelons les trois composantes simplement $x,y,z$.

Définissons ces nombres à trois composantes. On impose que $i^2=-1$, $j^2=-1$, $ji=i$, $ij=-j$. La multiplication de $i$ et $j$ n’est donc pas commutative.
Si nous calculons $w^2=(a+ib+jc)^2$, on obtient
\[x=a^2-b^2-c^2,\]
\[y=2ab-bc,\]
\[z=2ac+bc.\]
Si on a $c=0$, on se trouve dans le plan $xy$ et on a la même expression pour le carré que pour les nombres complexes habituels. Si on a $b=0$, on se trouve dans le plan $xz$ et là encore on a la même expression.
On peut donc s’attendre au fait qu’une itération $w\mapsto w^2+c$, où $c$ est aussi un tel nombre « triplex », donne un objet 3D dont les coupes avec les plans $xy$ et $xz$ soient des ensembles de Mandelbrot.

C’est Doug Bristor, un programmeur anglais qui a proposé ce système en 1995 : voici ce que ça donne.

Voici les coupes à travers les plans $xy$ (à gauche) et $xz$ (à droite) :

Ici non plus, il ne faut pas se limiter à prendre le carré de ces nombres « triplex », on peut aussi dessiner des « Bristorbrot » de plus haut degré.

Si, dans $z\mapsto z^2+c$, $c$ est une constante, on obtient un « ensemble de Julia ». Voici en dessous un ensemble de Julia selon Bristor de troisième degré.

Le système de Bristor est un bel effort mais on ne peut pas dire qu’on ait trouvé le Saint Graal !

Dessiner des objets fractals en 3D

Avant de revenir au Mandelbulb , parlons un peu des méthodes pour visualiser de tels objets 3D. Pour les fractales 2D il suffit de faire une itération pour chaque pixel de l’image. Si le point s’éloigne de l’origine il sera en dehors de l’ensemble et il reste à décider quelle couleur on donnera à ce pixel. On pourrait simplement colorer tous les pixels « en dehors » en blanc et les pixels « dedans » en noir, mais il y a beaucoup d’autres méthodes. On déclare un pixel comme « en dehors » si son module devient plus grand qu’un nombre qu’on a choisi à l’avance. Les méthodes pour colorer les pixels sont souvent basées sur le nombre d’itérations avant que le module ne devienne assez grand pour être déclaré « en dehors ».

Pour représenter un objet 3D, on doit penser à l’image comme un plan de projection. On choisit un point de vue virtuel et on tire des rayons de ce point de vue vers chaque point du plan de projection, donc vers chaque pixel de l’image. Pour chaque rayon, il faut maintenant découvrir si le rayon rencontre l’objet fractal et, si oui, à quel endroit sur le rayon.

Le plus simple serait de bouger un point sur un rayon vers le plan de projection à petits pas, faire l’itération à chaque pas, et s’arrêter quand l’itération du point sur le rayon nous dit qu’on est « dedans ». Le problème, évidemment, c’est qu’on ne sait pas a priori où se trouve l’objet fractal et on devrait prendre des pas infinitésimaux pour ne rien manquer (rappelez-vous que notre objet pourrait avoir des vrilles très fines) et on risque de prendre un grand nombre de pas inutiles si le rayon ne coupe même pas l’objet. Cela « coûte très cher » en temps de calcul.

Si par contre on connaît une estimation de la distance entre un point sur un rayon et l’objet fractal, on peut d’abord avancer avec un pas plus grand et ajuster les pas lorsqu’on s’approche de l’objet. Heureusement, on peut calculer une telle estimation, ce qui permet de dessiner les objets très rapidement. Vous trouverez les principes de deux méthodes en dépliant : la méthode « analytique » et une méthode développée par David Makin.

L’estimation de distance

Estimation de distance analytique

Quand on itère $z\mapsto z^2+c$, on s’arrête quand le module de $z$ devient plus grand qu’une valeur $M$. A ce moment on a fait $n$ itérations, et le module de $z$ est devenu $|z_n|$. On peut montrer qu’on obtient une estimation de la distance entre le point z et le point le plus proche de l’ensemble fractal par
\[d=\frac{|z_n|ln(|z_n|)}{|z'_n|}\]
où $z'_n$ est la dérivée de $z_n$.

On peut calculer la dérivée itérativement : $z'_n=2z_{n-1}z'_{n-1}+1$ car on a $z'_0=0$, $z'_1=1$, $z'_2=2z_1z'_1+1$, ...)

Les images ci-dessous montrent des contours de points équidistants de l’ensemble fractal :

On peut donc déplacer un point à l’extérieur de l’ensemble n’importe où dans un cercle de rayon $d$ et on ne sera jamais « à l’intérieur » de l’ensemble fractal. La même chose est vraie en trois dimensions. On peut alors se déplacer dans une sphère de rayon $d$, ce qui permet de s’approcher rapidement de l’objet fractal.

En pratique, on ne peut avancer qu’avec des pas de taille $fd$ ($f<1$) car la formule pour la distance donne des valeurs trop grandes si le nombre d’itérations $n$ est trop bas. On doit donc choisir la valeur $M$ assez grande.

Estimation de distance méthode « delta » de David Makin

Quand l’itération $z\mapsto z^2+c$ s’arrête car le module de $z$ est devenu plus grand qu’une valeur $M$, on a fait $n$ itérations. Si le point $z$ en question est proche de l’ensemble, il faudra plus d’itérations pour que le module de $z$ devienne plus grand que $M$. Si $z$ est sur le bord de l’ensemble, $n$ va même devenir infiniment grand.

L’inverse du nombre d’itérations est donc aussi une mesure pour la distance. Comme le nombre d’itérations est un nombre entier, il nous faut quelque chose pour interpoler entre ces nombres entiers pour avoir une mesure plus fine.

On définie le « nombre d’itérations lisses » comme [1]
\[s = n +1+\frac{1}{\ln 2}\ln\frac{\ln M}{\ln|z_n|}\]
Pour trouver l’intersection d’un rayon avec un objet fractal, on déplace un point sur ce rayon. On se trouve sur un point $P_1$ sur un rayon et on calcule le nombre d’itérations lisse $s_1$. On avance une petite distance « delta » plus loin sur le rayon et on calcule le nombre d’itérations lisses $s_2$ à ce point $P_2$.
On définie alors
\[d=\frac{1}{1+\frac{abs(s_2-s_1)}{delta}}\]
On va déplacer le point d’une distance $fd$ sur le rayon avec $f<1$.

Avec cette méthode, on n’a donc pas besoin de calculer la dérivée mais on doit effectuer deux itérations par pas sur le rayon pour calculer $s_1$ et $s_2$.

Quand on a trouvé le point d’intersection d’un rayon avec l’objet, on doit encore colorer le pixel qui correspond à ce rayon. Heureusement, les fractales n’ont pas de couleur préférée, on peut donc choisir, mais ce sont bien des objets 3D dont la couleur va varier selon la lumière qui tombe sur ce point. Il faut aussi décider si le point est dans l’ombre ou pas. C’est pourquoi il faut savoir à quel endroit sur le rayon se trouve l’intersection, car cela va permettre de mettre en rapport la position du point et la position d’une source de lumière virtuelle. Pour faire tout cela correctement, il nous faut aussi la normale sur la surface fractale. Problème ! Les surfaces fractales n’ont pas de normale car elles sont a priori très irrégulières. On résout cela en trouvant quelques autres points d’intersection très près du point principal et en considérant la surface comme étant lisse localement. Avec les coordonnées de ces points on peut calculer un produit vectoriel pour approximer une normale.

Cette technique de « raytracing » est assez rapide. Les images ci-dessous prennent environ une minute à calculer (taille 1000*1000 pixels) [2]. À noter qu’il est possible de programmer de tels algorithmes sur les processeurs de la carte graphique de l’ordinateur, ce qui permet de calculer ces images en une fraction d’une seconde !

Le « Mandelbulb »

Revenons sur la quête du Mandelbrot 3D.

Un point dans l’espace à trois dimensions est décrit par trois coordonnées $x,y,z$ mais on peut aussi décrire la position du point par ses coordonnées sphériques. La position d’un point $P$ à distance $R$ de l’origine peut être décrit par deux angles $t$ et $p$ comme :
\[x=R\sin (p)\cos (t)\]
\[y=R\sin (p)\sin (t)\]
\[z=R\cos (p)\]
On obtient les angles par $t=\arctan{\frac{y}{x}}$ et $p=\arctan{\frac{z} {\sqrt{x^2+y^2}}}$. [3]

Voici l’idée de Daniel White : comme le passage au carré consiste de doubler l’angle et à prendre le carré du module, on définit le « carré » d’un point en coordonnées sphériques comme

$x'=R^2\sin (2p)\cos (2t)$, $y'=R^2\sin (2p)\sin (2t)$, $z'=R^2\cos (2p)$.

ou plus généralement : $x'=R^q\sin (qp)\cos (qt)$, $y'=R^q\sin (qp)\sin (qt)$, $z'=R^q\cos (qp)$. Cela permet donc d’effectuer une itération $w\mapsto w^q+c$.

L’itération en détail

  • On prend un point $x_0,y_0,z_0$ sur un rayon entre le point de vue et un point du plan de projection..
  • On calcule $t=\arctan{\frac{y_0}{x_0}}$ et $p=\arctan{\frac{z_0} {\sqrt{x_0^2+y_0^2}}}$ et $R=\sqrt{x_0^2+y_0^2+z_0^2}$
  • On calcule
    \[x'=R^q\sin (qp)\cos (qt)+x_0\]
    \[y'=R^q\sin (qp)\sin (qt)+y_0\]
    \[z'=R^q\cos (qp)+z_0\]
  • On calcule $t=\arctan{\frac{y'}{x'}}$ et $p=\arctan{\frac{z'} {\sqrt{x'^2+y'^2}}}$ et $R=\sqrt{x'^2+y'^2+z'^2}$
  • Si $R>M$ on s’arrête et on déclare le point « en dehors ». ($M$ à choisir). On calcule une estimation de la distance vers l’objet, ce qui donne un nouveau point $x_0,y_0,z_0$. On a trouvé un point sur le bord de l’objet si l’estimation de la distance est inférieure à une valeur à choisir.
  • Sinon on calcule les nouveaux $x',y',z'$ avec les nouvelles valeurs de $t$ et $p$. On s’arrête si on atteint un certain nombre d’itérations (à choisir).

Pour calculer la distance avec la methode analytique on calcule à chaque pas :
\[dR_{nouveau}=qR^{q-1}dR_{ancien}+1,\]
et la distance devient
\[\frac{1}{2}\frac{R\ln R}{dR}\]

Voici ce qu’on obtient avec $q=2$.

Une déception ! L’objet ne ressemble même pas l’ensemble de Mandelbrot. Il est vrai qu’on repère quelques éléments fractals sur l’objet, comme les petits « arbres » sur le côté gauche mais si on veut trouver le fameux Graal, il va falloir chercher ailleurs, semble-t-il.

Mais pourquoi ne pas essayer ce que ça donne avec d’autres valeurs de $q$ ? Essayons $q=3$ :

Cela va dans la bonne direction, c’est-à-dire que l’objet devient plus régulier. Alors on essaie $q=4$ :

En augmentant le degré il semble que de plus en plus de « bulbes » poussent sur l’objet. Prenons $q=5$ :

... et sautons vers $q=8$ :

C’est ce Mandelbulb de degré 8 qui est devenu le plus populaire mais rien ne nous empêche de dessiner le Mandelbulb de degré 16 :

Pour mieux apprécier les détails de l’objet, voici encore quelques vues de plus près :

L’animation en bas prouve que l’objet est bien fractal : c’est un zoom d’ordre $10^{12}$, ce qui veut dire que si la première image a la taille de la Terre, la dernière montre des détails d’un centième de millimètre...

Regardez aussi quelques autres images sur le site de l’auteur.
On peut aussi admirer une image géante par Daniel White ici.

On n’a donc pas encore trouvé ce Saint Graal et la quête continue ; mais on a fait cette belle découverte du Mandelbulb en route. Si vous voulez participer et suivre quelles autres choses concoctent tous ces amateurs, il suffit de s’inscrire sur Fractalforums.com. Vous y serez le bienvenu !

Notes

[1Jussi HARKONEN. On smooth fractal coloring techniques. (Master’s thesis)

[2Les images de cet article ont été calculées avec le logiciel Ultrafractal sur un ordinateur à double cœur.

[3Dans les algorithmes des logiciels, on utilise la fonction atan2(x,y) qui est équivalente à $\arctan{\frac{y}{x}}$, mais qui prend en compte les signes de $x$ et $y$ afin de mettre le résultat dans le bon quadrant.

Partager cet article

Pour citer cet article :

Jos Leys — «Mandelbulb» — Images des Mathématiques, CNRS, 2010

Commentaire sur l'article

  • Mandelbulb

    le 16 janvier 2010 à 23:29, par Michelle Schatzman

    Magnifiques images, et ce qui est étonnant, c’est à quel point certaines d’entre elles rappellent la décoration des temples hindous. Voir par exemple sur wikipedia en anglais beaucoup de photos de cette architecture.

    Répondre à ce message
  • Mandelbulb

    le 27 mai 2010 à 19:32, par Jean-François Colonna

    Je rappelle que les formules qui sont données au sujet de Doug Bristor :

    i^2=-1, j^2=-1, ji=i et ij=-j

    sont précisemment celles qui ont interdit la généralisation des nombres complexes à l’espace tridimensionnel. En effet, cette généralisation aurait du ammener à une addition et à une multiplication associatives. Or malheureusement, l’associativité et les formules précédentes (ainsi que toutes leurs variantes qu’il est facile de lister exhaustivement) conduisent, dans les tous les cas possibles, à des contradictions. Ainsi par exemple :

    ji=i => i(ji)=ii => (ij)i=ii => -ji=-1 => -i=-1 => i=1

    Il a fallu l’idée de génie d’Hamilton (passer à l’espace à quatre dimensions avec les quaternions) pour résoudre le problème.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Dossiers

Cet article fait partie du dossier «Benoît Mandelbrot et les objets fractals» voir le dossier

Suivre IDM