Par Frdric Mazu

Sur le CD ROM

Crez votre gnrateur de fractales

Les informaticiens eux aussi, ont le droit de donner libre cours leur crativit et leur sens artistique. Un peu de finesse dans un monde de brutes

et article se propose d'exposer les bases ncessaires au dveloppement d'un gnrateur de fractales complexes. Les fractales ont t trs la mode dans les annes 1980 la suite des travaux du polytechnicien Benot Mandelbrot au centre de recherche d'IBM. Les fractales sont des ensembles mathmatiques fascinants, car une portion d'un tel ensemble est identique la totalit. La puissance des ordinateurs d'aujourd'hui permet de calculer et de reprsenter ces ensembles rptitifs l'esthtique indniable (figure 1).
> Figure 1: De nombreuses galeries de fractales existent sur le Net. Cette image provient de http://perso.club-internet.fr/dreamp/fractal/, une galerie qui vaut le dtour.

Les ensembles de Mandelbrot et de Julia

Ces ensembles sont des collections de points. L'ensemble de Mandelbrot est l'ensemble de tous les complexes (encadr 1) c tels que l'itration : z' = z^2 + c ne tend pas vers l'infini. Pratiquement, on fait un calcul itratif
Encadr 1

Les nombres complexes

Les nombres complexes sont des entits mathmatiques dotes d'une partie relle et d'une partie imaginaire. On note un nombre complexe ainsi : c = a + ib o a est la partie relle et b la partie imaginaire d'un nombre complexe c. Le nombre imaginaire pur i est trs particulier car : i^2 = -1 La plupart des langages informatiques (C++, Java, Python, Lisp, etc.) ont un type complexe qui reprsente un nombre complexe sous la forme d'une paire (a, b) o a est la partie relle du nombre et b la partie imaginaire, comme expliqu plus haut. Les langages disposant d'un type complexe savent bien entendu effectuer des oprations avec. Si votre langage de prdilection ne connat pas le type complexe, ces quelques formules vous seront utiles : c = a + ib c^2 = a2 - b2 + I*(2*a*b) c1 = a1 + ib1, c2 = a2 + ib2 c1+c2 = (a1+a2) + i(b1+b2) norme de c = a^2+ b^2

NIVEAU : INTERMDIAIRE
72
Programmez N54 JUIN 2003

C++

pour chaque point du plan complexe. On appelle plan complexe, un plan dans lequel on porte la partie relle d'un nombre complexe sur l'axe des abscisses, et la partie imaginaire sur l'axe des ordonnes. Pour chaque point c du plan, on calcule : z0 = 0 (nombre complexe de partie relle et imaginaire nulle) z1 = z0^2 + c z2 = z1^2 + c z3 = z2^2 + c et ainsi de suite. Ceci pos, soit le calcul tend vers l'infini et dans ce cas le point c du plan complexe n'appartient pas l'ensemble de Mandelbrot, soit le calcul ne tend pas vers l'infini et nous avons un point de l'ensemble. Dans la pratique, ce test d'appartenance l'ensemble est simple, puisque les mathmaticiens ont dmontr que si, au cours de l'itration, un nombre complexe zn <<< je dis bien zn >>> a une norme suprieure 4, alors l'itration tendra vers l'infini et le point n'appartiendra pas l'ensemble. Bien sr il n'est pas question de faire itrer l'ordinateur ternellement. On choisira donc un nombre d'itration maximum, et si l'issue de toutes les itrations, la norme du nombre complexe ne dpasse pas 4, on considrera que le point fait partie de l'ensemble de Mandelbrot. Comme le bon sens le suggre, le nombre limite d'itrations influencera grandement les rsultats. De la mme manire, il est vident qu'il ne sert strictement rien de s'occuper de nombres complexes c dont la norme est ds le dpart suprieure ou gale 4. La non appartenance de ces points l'ensemble de Mandelbrot est certaine et l'on ne travaille donc que dans la petite surface ainsi dlimite pour calculer des fractales. Les esprits curieux peuvent lgitimement se demander pourquoi commencer l'itration avec un nombre complexe nul. Exprimentez avec les programmes sur le Cd-Rom et vous constaterez qu'un nombre complexe z non nul au dpart dforme l'ensemble de

PRATIQUE

Mandelbrot. C'est donc un paramtre intressant explorer, de mme que le nombre maximal d'itrations. L'ensemble de Julia est dfini lgrement diffremment. Cette fois, on fixe le nombre c et l'on procde des itrations pour chaque point z du plan complexe. Ceci pos, la procdure de calcul reste la mme, et le test d'appartenance d'un point l'ensemble de Julia s'effectue comme prcdemment. Le choix du point c est dj un art par lui mme. De petites variations provoquent des rsultats tonnants. Pour vous faire la main, je vous suggre d'essayer les valeurs:

__fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { Reset(); } void TForm1::Clear() { Canvas->Brush->Color = clWhite; Canvas->FillRect(TRect(0, 0, 400, 400)); } void TForm1::DrawPoint(int x,int y) { Canvas->MoveTo(x, y); Canvas->LineTo(x+1, y); } void __fastcall TForm1::Button1Click(TObject *Sender) { bool test; double largeur = max_x - min_x; double hauteur = max_y - min_y; Clear();

Partie relle
-0.5 -0.5 -1 -0.12 0 -0.3 -0.775 0.44 -0.513

Partie imaginaire
0 0.3 0.16 0.765 1 0.7 0.177 0.29 -0.579

Les exemples
Vous trouverez de nombreux programmes d'exemple sur le CdRom. J'ai crit ces programmes avec C++Builder sous Windows. J'ai fait ce choix pour deux raisons: d'abord la rapidit de C++ permet de gnrer des images rapidement, ensuite, les sources peuvent tre repris directement avec l'dition personnelle de Kylix si vous tes sous Linux (mis part la macro RGB prsente dans le source,car clarifiant la lecture. Le type TColor de Borland permet lui aussi de travailler avec des valeurs RGB. Adaptez le code selon vos besoins) Si vous travaillez avec un autre environnement ou un autre langage, vous ne devriez pas avoir de grandes difficults transposer le code, car celui-ci est fort simple.
Encadr 2 // Gnrateur d'ensemble de Mandelbrot // (listing partiel) class TForm1 : public TForm { private: double min_x, max_x; double min_y, max_y; int iteration; int limite; void Clear(); void Reset(); void DrawPoint(int, int); bool isMandelbrot(double, double); }; #include <complex> using namespace std;

for(int i=0; i<400; i++) for(int j=0; j<400; j++) if(isMandelbrot(min_x+i*largeur/400.0 ,min_y+j*hauteur/400.0)) DrawPoint(i, j); } bool TForm1::isMandelbrot(double r, double i) { complex<double>c(r, i); complex<double>z(0, 0); for(int i=0; i<25; i++) { z = pow(z, 2); z = z + c; if(norm(z) > 4.0) return false; } return true; } void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y) { static bool premier = false; if(!premier) { min_x = (X - 200)/100.0; min_y =(Y - 200)/100.0; premier = true; return; } if(premier) { max_x = (X - 200)/100.0; max_y =(Y - 200)/100.0; premier = false; Invalidate(); return;
Programmez N54 JUIN 2003

73

} } void TForm1::Reset() { min_x = min_y = -2.0; max_x = max_y = 2.0; } void __fastcall TForm1::Button2Click(TObject *Sender) { Reset(); Invalidate(); } void __fastcall TForm1::FormPaint(TObject *Sender) { Button1Click(this); }

> Figure 3: Un ensemble de Julia pour c = -0.775 + 0.177i

z = z + c; if(norm(z) > 4.0) return false; } return true; }

> Figure 2: L'ensemble de Mandelbrot, la fameuse figure du "pou", dans notre programme d'exemple.

Ce programme modeste, qui pour l'instant ne travaille qu'en noir et blanc (figure 2) comporte toutefois une fonctionnalit de zoom. Visualisez mentalement la zone que vous souhaitez agrandir, cliquez sur le coin en haut et gauche puis sur le coin en bas et droite et observez le rsultat. Vous verrez par vous mme que le "pou", l'ensemble de Mandelbrot, se rpte l'infini l'intrieur de lui mme. Pour tracer un ensemble de Julia, il suffit de remplacer la mthode isMandelbrot, qui teste l'appartenance l'ensemble, par la mthode isJulia que voici :

PRATIQUE

bool TForm1::isJulia(double r, double i) { complex<double> z(r, i); for(int i=0; i<25; i++) { z = pow(z, 2);

> Figure 4: Le gestionnaire de palette de Fractal Explorer. Allez faire un petit tour http://www.eclectasy.com/Fractal-Explorer/

Vous obtenez alors, selon la valeur de c que vous avez choisie, un ensemble de Julia (figure 3).

Un peu de couleur

NIVEAU : INTERMDIAIRE
74
Programmez N54 JUIN 2003

C++

Ces premiers rsultats sont certes encourageants, mais bien ternes en comparaison de ce que l'on peut voir figure 1. C'est l que vous pourrez exprimer toute votre crativit, en dfinissant des algorithmes de coloration des fractales. Il y a deux points cls : L'algorithme lui mme et la palette de couleurs. Le caractre cyclique des fractales rend pertinente la cration d'une palette de

quant des fonctions trigonomtriques la norme du nombre complexe. La figure 6 montre le rsultat des oprations. Et voici ce petit code aux grands effets :
void TForm1::Mandelbrot(double r, double i) { complex<double>c(r, i); complex<double>z(0, 0); double n; for(int i=0; i<25; i++) { z = pow(z, 2); z = z + c; n = norm(z); if(n > 4.0) { Canvas->Pen->Color = (TColor)RGB((i*255)%500, (i*255)%300, (i*255)%300); return; } else Canvas->Pen->Color = (TColor)RGB(cos(n)*150, 0, sin(n)*255); } }

> Figure 5: Un algorithme tout simple et notre ensemble de Julia a dj fire allure.

couleur, elle mme cyclique. La plupart des gnrateurs de fractales que vous pouvez tlcharger sur le Net procdent ainsi (figure 4). Il existe toutefois quelques expdients pour se faire plaisir rapidement. Par exemple, on peut appliquer des fonctions trigonomtriques l'argument du nombre complexe, c'est dire l'angle entre l'axe des abscisses et la droite passant par l'origine et le point. les fonctions trigonomtriques sinus et cosinus ont la bonne ide de retourner une valeur comprise en -1 et 1, ce qui facilite la transposition en valeur RGB. Ainsi il est possible de modifier trs simplement le programme Julia comme ceci:
bool TForm1::isJulia(double r, double i) { complex<double> z(r, i); int j; for(j=1; j<25; j++) { z = pow(z, 2); z = z + c; if(norm(z) > 4.0) { Canvas->Pen->Color = clBlue; return false; } } Canvas->Pen->Color = (TColor)RGB(abs(sin(arg(z)))*255, 0, abs(sin(arg(z)))*255); return true; }

> Figure 6: Coloration de l'extrieur l'ensemble, partir d'un algorithme d'chappement.

Cela donne dj un rsultat sympathique, comme vous pouvez le constater figure 5.

Pour conclure
Les fractales complexes sont un domaine inpuisable pour celui qui aime exprimenter et explorer. N'hsitez pas tendre vos essais d'autres fonctions polynmes que z^2 + c. De mme, ne vous limitez pas au degr deux. Et soyez inventifs en ce qui concerne les algorithmes de coloration. Par exemple l'application des formules statistiques, donne de remarquables rsultats. Bonne informatique artistique et rcrative ! s Frdric Mazu frederic.mazue@programmez.com
Programmez N54 JUIN 2003

L'algorithme d'chappement
Cet algorithme a pour but d'viter de faire apparatre les fractales sur un fond de couleur uni. Il repose sur une ide toute simple. On prend en compte le nombre d'itrations ncessaires, pour constater qu'un point n'appartient pas l'ensemble de Mandelbrot ou de Julia, et l'on construit une couleur partir de cette valeur. Le morceau de code ci-dessous met ce principe en application et tant qu'on y est, on colore galement l'intrieur de la fractale, en appli-

75