Fractales

 


Objectif : réaliser une fractale par David Cobac


Quelques liens pour mieux comprendre

Sur le forum fr.comp.text.tex dédié à (La)TeX une question revient régulièrement : avec quel outil tracez-vous vos courbes ? Je regardai attentivement les réponses, ayant moi-même composé un petit traceur tkparam. Et parmi les différents logiciels proposés, il y a eu Equation Grapher [1] réalisé par des français et traçant notamment les fractales par l'intermédiaire de scripts propriétaires à SEG. L'idée m'est alors venue de voir si on pouvait faire des fractales en Tcl/Tk

L'idée de base

On prend tous les points du plan complexe, on applique alors une petite suite récurrente complexe dont le premier terme est l'affixe du point considéré.

De deux choses l'une : soit la récurrence fait diverger la suite avant 255 itérations soit la récurrence ne fait pas diverger la suite Dans les deux cas on note simplement le nombre d'itérations faites, ce nombre donnera une couleur ! C'est tout...et bien oui...c'est tout !

La formule

Je suis parti avec comme base la récurrence suivante :

qui donne un type particulier de fractale, on pourra adapter alors à d'autres formulations.

Une affixe de point M est de la forme

, on part alors d'une affixe quelconque

. Pour considérer chaque point du plan, j'ai pris un canevas et je l'ai parcouru pixel par pixel (en adaptant l'échelle pour qu'on se retrouve toujours quelquesoit la dimension en pixels sur un carré de côté 2 centré en O) avec ses coordonnées canevas (x;y) ; la relation liant les affixes et les coordonnées cartésiennes est

, la mise au carré donnant :

que l'on sépare en partie réelle qui donne l'abscisse

et en partie imaginaire qui donne l'ordonnée :

.

Mise en place

De par mon expérience sur le champ d'étoiles, il m'a paru tout de suite évident que les performances seraient assez médiocres. Je portai mon attention sur les moyens d'interfacer Tcl et le C, suite à une discussion avec Gaëlle, je décidai d'aller voir http://www.swig.org.

Aspect global du script

Le script se décomposera en 3 procédures : gui : procédure principale, mettant en place le canvas et la procédure de calcul ; elle prendra en arguments : le pas d'avancement du canevas : si égal à 1 on parcourt tous les pixels du canevas, si égal à 2 on parcourt un pixel sur deux (aussi bien horizontalement que verticalement) etc. la dimension du canevas, plus il sera grand, plus il y aura de calculs, plus ce sera lent carre : procédure qui renverra une liste à deux éléments qui sont les parties réelles et imaginaires du carré d'une affixe macouleur : procédure qui d'un entier compris entre 0 et 255 fait un hexadécimal sous le format xx, cette procédure renverra une chaine de la forme #xxxxxx qui représente pour Tk une couleur acceptable.

'La procédure gui'

Je nomme par pas et echelle ses deux arguments, la création du canvas et son affichage :

     pack [canvas .c -width $echelle -height $echelle -bg white]
     update

Le parcours du canvas se fera classiquement par :

     for {set i 0} {$i<=$echelle} {incr i $pas} {
         for {set j 0} {$j<=$echelle} {incr j $pas} {

i désigne ici une colonne et june ligne.

On s'intéresse donc maintenant à un point particulier du canvas. On fixe à 0 la variable couleur qui sera aussi le compteur d'itérations, ensuite comme le canvas représente un carré de côté 1 avec en haut à gauche l'origine (l'axe des ordonnées étant orienté vers le bas) on cherche les véritables coordonnées de notre point. On fixe alors les variables x et y sur notre point, ces variables serviront pour notre récurrence :

     set couleur 0
     set x0 [expr {$i*1.0/$echelle}];set y0 [expr {$j*1.0/$echelle}]
     set x $x0;set y $y0

Voici donc notre récurrence :

     while {[expr {$x*$x+$y+$y}]<4 && $couleur<255} {
         incr couleur
         set moncarre [carre $x $y]
         set x [expr {[lindex $moncarre 0] + (-0.26)}]
         set y [expr {[lindex $moncarre 1] + 0.5}]
     }

Le test d'arrêt s'effectue sur la norme de notre affixe (qui ne doit pas dépasser 2 donc au carré ça donne 4) ou sur le nombre d'itérations ici fixé au maximum à 255. On incrémente à chaque fois le compteur couleur. On calcule notre partie réelle et notre partie imaginaire du carré de notre affixe, puis on applique notre récurrence en renommant x et y les calculs obtenus. Les décimaux -0.26 et 0.5 sont les parties respectivement réelle et imaginaire de l'affixe constante zc (cf. formule de récurrence dans la page précédente). Changer cette constante, c'est changer l'allure de la fractale (vous pouvez changer ces 2 valeurs à loisir en n'oubliant pas que les prendre grands signifie vite diverger !).

On crée alors notre point qui n'est rien d'autre que le point de départ mais avec une couleur particulière, le pas sert ici d'épaisseur (si vous prenez autre chose que 1 il y aura le fond du canevas qui va apparaître donc on epaissit le point). On notera l'utilisation de l'option outline et non pas fill car le point est tellement petit qu'on ne verra du rectangle que le contour ainsi c'est bien le contour qu'il faut coloriser et pas l'intérieur !!

     .c create rectangle [expr {$x0*$echelle}] [expr {$y0*$echelle}] [expr {$x0*$echelle}]\
       [expr {$y0*$echelle}] -outline "\#[macouleur $couleur]" -width $pas
     update

Le update sert à voir évoluer les choses au fur et à mesure : cette commande met à jour l'affichage du canvas.

'La procédure carre'

Pas de problème particulier, sauf qu'on aurait pu faire autrement : soit deux procédures, soit les formules directement dans la procédure gui, bon...c'est dicutable.

 proc carre {x y} {
     return [list [expr {$x*$x-$y*$y}] [expr {2*$x*$y}]]
 }

'La procédure macouleur'

La valeur passée en argument est comprise entre 0 et 255, on la transforme tout d'abord en hexadécimal avec 2 items obligatoirement donc si jamais la valeur vaut b, on rajoute un 0 devant qui nous donnera finalement 0b. Tout cela pour pouvoir avoir une couleur acceptable avec 3 fois 2 items. L'idée est maintenant de faire de cette valeur une couleur, si on joint 3 fois la valeur de la variable hexadécimale, on va récupérer un gris :-( alors je joins une chaine ici 00 pour que ça fasse un peu coloré...

 proc macouleur {val} {
     set hex [format %02x $val]
     set coul "00"
     return "$coul$hex$hex"
 }

Le code final

http://wfr.tcl.tk/fichiers/pub/fractale_tcl.tcl

 proc gui {pas echelle} {
         pack [canvas .c -width $echelle -height $echelle -bg white]
         update
         for {set i 0} {$i<=$echelle} {incr i $pas} {
                 for {set j 0} {$j<=$echelle} {incr j $pas} {
                         set couleur 0
                         set x0 [expr {$i*1.0/$echelle}];set y0 [expr {$j*1.0/$echelle}]
                         set x $x0;set y $y0
                         while {[expr {$x*$x+$y+$y}]<4 && $couleur<255} {
                                 incr couleur
                                 set moncarre [carre $x $y]
                                 set x [expr {[lindex $moncarre 0] + (-0.26)}]
                                 set y [expr {[lindex $moncarre 1] + 0.5}]
                         }
                         .c create rectangle [expr {$x0*$echelle}] [expr {$y0*$echelle}] [expr {$x0*$echelle}]\
                          [expr {$y0*$echelle}] -outline "\#[macouleur $couleur]" -width $pas
                         update
                 }
         }
 }
 proc carre {x y} {
     return [list [expr {$x*$x-$y*$y}] [expr {2*$x*$y}]]
 }
 proc macouleur {val} {
         set hex [format %02x $val]
         set coul "00"
         return "$coul$hex$hex"
 }
 gui 1 150

Résultats et performances

Voici ce que donne le programme avec les paramètres : pas=1 et echelle=150 :

Améliorations

Il s'agit de privilégier une approche plus orienté vers le C, c'est-à-dire laisser au C le maximum de calculs et passer à Tcl/Tk pour tracer nos points. En effet, on remarque que nos fractales ne sont pas aussi "belles" que celles que l'on peut voir sur certaines illustrations du phénomène. Nous allons donc nous pencher sur deux aspects : ré-écriture du code des couleurs écriture de la forme #RRGGBB par une fonction C importée grâce à swig

Le code de la couleur

Nous allons complexifier notre code couleur, on va maintenant considérer non plus 256 itérations possibles mais 766 (=3x255+1), avec le principe suivant pour obtenir le code couleur : entre 0 et 255 je vais de #000000 à #0000ff entre 256 et 510 je vais de #0001ff à #00ffff entre 511 et 765 je vais de #01ffff à #ffffff Cette méthode m'assure aussi de la progressivité du dégradé au fur et à mesure des itérations.

le code Tcl correspondant

 proc macouleur {val} {
         for {set i 0} {$i<=2} {incr i} {set valeur($i) "00"}
         set val_entier [expr {int($val/255.0)}]
         set hex [format %02x [expr {$val % 255}]]
         set valeur($val_entier) $hex
         set i 0
         while {$i<$val_entier} {
                 set valeur($i) "ff"
                 incr i
         }
         return "\#$valeur(0)$valeur(1)$valeur(2)"
 }

Une évaluation du temps de travail nous donne pour cette procédure :

 380 microseconds per iteration

le code C correspondant

Codons alors en C pour "voir si la différence sera significative : Pour ce faire petit regard sur le guide de l'utilisateur SWIG chapitre 10 (SWIG and Tcl), on y apprend que trois types de données sont sans problème supportés par Tcl : int, double et char *. Ce dernier type est celui qu'il nous faut puisque nous allons renvoyer à Tcl une chaine de caractères. Voici donc une possibilité de codage C (avec string.h) :

 char * lajoliecouleur (int couleur) {
         int valentier;
         char *debut = malloc(8*sizeof(char));
         char *monhex = (char *) calloc(3,sizeof(char));
         valentier=(int) ((double) couleur/255);
         sprintf(monhex,"%02x",couleur % 255);
         strcpy(debut,"#");
         if (valentier==0) {
                 strcat(debut,monhex);
                 strcat(debut,"0000");
         } else if (valentier==1) {
                 strcat(debut,"ff");
                 strcat(debut,monhex);
                 strcat(debut,"00");
         } else if (valentier==2) {
                 strcat(debut,"ffff");
                 strcat(debut,monhex);
         } else strcat(debut,"ffffff");
         return debut;
 }

Quoique un peu "simplet" ce code est aussi rapide que d'autres plus astucieux et surtout, il s'agit, dans l'esprit, du code correspondant au code Tcl (comparons ce qui est comparable). La rapidité en import avec swig nous donne :

 309 microseconds per iteration

Ce qui peut paraître un gain modeste, mais n'oublions pas que ce gain donne une amélioration d'environ 19% par point du plan et, sur un canvas de 150x150, cela nous fait 22500 couleurs à calculer...donc cela ne devient plus tellement négligeable !

Code simple de ma fractale

le source C

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 double carrezreel (double x, double y) {
         return (x*x-y*y);
 }
 double carrezimag (double x, double y) {
         return (2*x*y);
 }
 int fonctcouleur (double xinit, double yinit ,double xc ,double yc) {
         double carrezimag (double x, double y);
         double carrezreel (double x, double y);
         int couleur;
         double x,y,rx;
         x=xinit;y=yinit;
         couleur=0;
         while (x*x+y*y<1 && couleur<765) {
                 couleur++;
                 rx=carrezreel(x,y)+xc;
                 y=carrezimag(x,y)+yc;
                 x=rx;
         }
         return couleur;
 }
 char * lajoliecouleur (int couleur) {
         int valentier;
         char *debut = calloc(8,sizeof(char));
         char *monhex = (char *) calloc(3,sizeof(char));
         valentier=(int) ((double) couleur/255);
         sprintf(monhex,"%02x",couleur % 255);
         strcpy(debut,"#");
         if (valentier==0) {
                 strcat(debut,monhex);
                 strcat(debut,"0000");
         } else if (valentier==1) {
                 strcat(debut,"ff");
                 strcat(debut,monhex);
                 strcat(debut,"00");
         } else if (valentier==2) {
                 strcat(debut,"ffff");
                 strcat(debut,monhex);
         } else strcat(debut,"ffffff");
         return debut;
 }

le fichier .i

 %module fractales
 %{
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 %}
 extern double carrezreel (double x,double y);
 extern double carrezimag (double x,double y);
 extern int fonctcouleur (double xinit, double yinit ,double xc ,double yc);
 extern char * lajoliecouleur (int couleur);

la compilation

Dans les lignes qui suivent le symbole $ n'est pas à taper, il s'agit de l'invite de la ligne de commande.

 $ swig -tcl fractamelior.i
 $ gcc -c fractamelior.c
 $ gcc -c fractamelior_wrap.c
 $ gcc -shared fractamelior.c fractamelior_wrap.c -o fractamelior.so

le source tcl

 load ./fractamelior.so fractamelior
 proc gui {pas} {
         global echelle
         pack [canvas .c -width $echelle -height $echelle -bg white]
         update
         set xc 0.25;set yc -0.4
         for {set i 0} {$i<=$echelle} {incr i $pas} {
                 set x0 [expr {$i*1.0/$echelle}]
                 for {set j 0} {$j<=$echelle} {incr j $pas} {
                         set y0 [expr {$j*1.0/$echelle}]
                         set coul [lajoliecouleur [fonctcouleur $x0 $y0 $xc $yc]]
                         .c create rectangle $i $j $i $j -outline $coul
                         update
                 }
         }
 }
 set echelle 150
 gui 2

Téléchargement

http://wfr.tcl.tk/fichiers/pub/fractamelior.c

http://wfr.tcl.tk/fichiers/pub/fractamelior.i

http://wfr.tcl.tk/fichiers/pub/fractamelior.tcl

Idée pour rechercher une belle fractale

À récurrence égale, images différentes !

Sur une même relation de récurrence, en l'occurence celle qui nous donne cette forme particulière de fractale, le résultat dépend intimement de l'affixe du point C pris comme constante. Bref, si on a un mauvais point C, la fractale ne sera pas très belle. Il convient donc de rechercher à tâtons une bonne affixe c'est-à-dire ici xc et yc.

Pour ce faire, nous allons simplement faire varier pour un yc choisi la valeur de xc et dessiner la fractale correspondante.

Mise en oeuvre

Il faut donc : établir une boucle sur les valeurs de xc ouvrir une nouvelle fenêtre pour chaque xc et y tracer notre fractale

On va donc passer la valeur de xc comme argument de la fonction gui, en choisissant 0.26 comme point de départ et en établissant 10 figures de 0.1 en 0.1, l'appel se fera par :

 for {set u 0.25} {$u<0.35} {set u [expr {$u+.01}]} {
         gui $u 2
 }

On prendra une résolution de 2 dans un premier temps ce qui nous permettra de repérer rapidement le ou les valeurs de xc intéressantes.

La création d'une nouvelle fenêtre à chaque valeur de xc sera réglé par une toplevel qui prendra comme nom le nombre d'itérations faites, on créera donc une variable globale fois qui s'incrémentera dans notre procédure gui.

De plus la fenêtre mère . ne servant plus à rien, on l'iconifiera par un petit wm iconify . De plus pour augmenter la rapidité d'affichage je n'"update" pas systèmatiquement. Voilà il n'y a plus qu'à !

Code tcl modifié

 load ./fractamelior.so fractamelior
 proc gui {xc pas} {
         global echelle fois
         set yc -.4
         toplevel .$fois
         pack [canvas .$fois.c -width $echelle -height $echelle -bg white]
         update
     for {set i 0} {$i<=$echelle} {incr i $pas} {
                 set x0 [expr {$i*1.0/$echelle}]
                 for {set j 0} {$j<=$echelle} {incr j $pas} {
                         set y0 [expr {$j*1.0/$echelle}]
                         set coul [lajoliecouleur [fonctcouleur $x0 $y0 $xc $yc]]
                         .$fois.c create rectangle $i $j $i $j -outline "$coul"
                 }
         }
         incr fois
 }
 set echelle 150;set fois 1
 wm iconify .
 for {set u 0.25} {$u<0.35} {set u [expr {$u+.01}]} {
         gui $u 2
 }

Résultats

On remarque que la 9e itération semble intéressante (correspondant à xc=0.33), on pourrait ainsi réitèrer l'opération en choisissant une autre plage de valeurs pour xc correspondant à des valeurs proches de 0.33. Je me suis limité à xc=0.33, et ainsi j'ai remis une résolution maximale et un format de fenêtre plus ambitieux pour obtenir cette image :

Avec SWIG

On va tout simplement faire faire les calculs par des fonctions C et le tracé par Tcl/Tk.

Le pourquoi ?

Si on reprend la taille de la fenêtre dans l'article sur le code 100% Tcl/Tk, c'est-à-dire 150, avec un pas de 1 : cela nous fait donc 150*150=22500 points sur lesquels on effectue des itérations ... bref tout cela s'annonçait dès le départ fort lent :-(

Que nous offre un interfaçage avec C ?

Regardons une simple procédure Tcl renvoyant le discriminant d'un trinôme du second degré : b^2-4ac :

         proc discriminant {a b c} {
                 expr {$b*$b-4*$a*$c}
         }

Le test de "rapidité" nous renvoie :

 puts [time {discriminant 1 2 3} 100000]
 6 microseconds per iteration

(Remarquons que l'emploi de la fonction pow s'avère plus lent ce qui paraît plus logique)

En utilisant http://www.swig.org, nous arrivons avec une fonction C écrite de la même manière à une vitesse :

 puts [time {discriminant 1 2 3} 100000]
 3 microseconds per iteration

Éloquent, sur un simple calcul nous gagnons 50% de temps d'execution.

Mes fonctions C

Voilà les trois fonctions C écrites pour mon script sur mon dessin de fractales, les deux premières séparent la procédure du script Tcl qui faisait le calcul du carré d'un complexe dans une seule et même procédure :

 /* Mes fonctions C dans le fichier fractales.c */
 double carrezreel (double x, double y) {
         return (x*x-y*y);
 }
 double carrezimag (double x, double y) {
         return (2*x*y);
 }
 int fonctcouleur (double xinit, double yinit ,double xc ,double yc) {
         double carrezimag (double x, double y);
         double carrezreel (double x, double y);
         int couleur;
         double x,y,rx,ry;
         x=xinit;y=yinit;
         couleur=0;
         while (x*x+y*y<4 && couleur<255) {
                 couleur++;
                 rx=carrezreel(x,y);
                 ry=carrezimag(x,y);
                 x=rx+xc;
                 y=ry+yc;
         }
         return couleur;
 }

On reconnaîtra dans ces fonctions les procédures Tcl écrites auparavant dans le 100% Tcl.

Voici ensuite le fichier qui sert à définir les "nouvelles commandes" Tcl et éventuellement (ce n'est pas la cas ici) les nouvelles constantes :

 /* Mes prototypes de mes fonctions C dans le fichier fractales.i
 On commence avec une ligne définissant le nom de la librairie */
 %module fractales
 /* puis viennent mes prototypes avec un extern pour l'exportation */
 extern double carrezreel (double x,double y);
 extern double carrezimag (double x,double y);
 extern int fonctcouleur (double xinit, double yinit ,double xc ,double yc);

Phase de compilation

Trois phases de compilation que je vous livre brutes :

 $ swig -tcl fractales.i
 $ gcc -c fractales.c
 $ gcc -c fractales_wrap.c
 $ gcc -shared fractales.o fractales_wrap.o -o fractales.so

Voilà ! La première ligne de compilation crée le fichier testerapidite_wrap.c d'interfaçage qu'on compile ensuite avec notre fichier pour créer finalement notre librairie .so (ou .dll sous .indow$.

Le fichier Tcl

Notre fichier Tcl/Tk se trouve considérablement alléger ! N'oublions pas d'y mettre le chargement de notre librairie avec la commande load. Le script devient alors :

 load ./fractales.so
 proc gui {pas echelle} {
         pack [canvas .c -width $echelle -height $echelle -bg white]
         update
         for {set i 0} {$i<=$echelle} {incr i $pas} {
                 for {set j 0} {$j<=$echelle} {incr j $pas} {
                         set x0 [expr {$i*1.0/$echelle}];set y0 [expr {$j*1.0/$echelle}]
                         .c create rectangle [expr {$x0*$echelle}] [expr {$y0*$echelle}]\
                          [expr {$x0*$echelle}] [expr {$y0*$echelle}]\
                          -outline "\#[macouleur  [fonctcouleur $x0 $y0 0.26 -0.5]]" -width $pas
                         update
                 }
         }
 }
 proc macouleur {val} {
         set hex [format %02x $val]
         set coul "00"
         return "$coul$coul$hex"
 }
 gui 1 150

On voit très bien sur ce simple exemple que les fonctions C créées s'utilisent comme n'importe quelle commande Tcl.

Pour télécharger :

http://wfr.tcl.tk/fichiers/pub/fractales.c

http://wfr.tcl.tk/fichiers/pub/fractales.i

http://wfr.tcl.tk/fichiers/pub/fractales.tcl

Conclusion et remerciements

Je n'y connais pas grand chose en C et finalement on arrive à faire des truc simples et sympas avec Tcl/Tk et C. Les performances ont été décrites plus haut et dans l'autre page : on atteint presque la moitié du temps sur du 100% Tcl (qui garde l'avantage d'être du 100% Tcl). Je remercie Gaëlle sur le chat de m'avoir indiquer l'existence de http://www.swig.org qui m'a permis d'écrire cette première page sur cet outil magnifiquement simple à prendre en main pour un novice comme moi.

2004-06-07 jcw - Voir aussi Critcl [2], [3], [4].