wiki:InsiaProgCProjetMandelbrot

Sommaire

Projet 2A SRT - Ensemble de Mandelbrot

  1. But du projet
  2. Algorithme de calcul
  3. Affichage
  4. Interface CGI
    1. Changement de repère
    2. Mode HTML
    3. Mode PNG

But du projet

Le but du projet est de réaliser un programme qui génère une image de l'ensemble mathématique de Mandelbrot. Comme cet ensemble est vaste et qu'il est amusant à explorer interactivement, ce programme sera réalisé sous la forme d'un CGI utilisant le navigateur pour afficher l'image et permettre à l'utilisateur de "cliquer pour zoomer".

Vous trouverez des ressources pour vous aider dans source:/insia/c/projet-mandelbrot

Une version de ce programme (150 lignes commentées) peut être testée en ligne. Son code source sera diffusé à la rentrée.

Algorithme de calcul

On utilisera l'algorithme du "temps de sortie" (exit time): celui-ci calcule pour chaque point de l'image les valeurs de la suite de Mandelbrot, et détecte à quelle itération la suite diverge. C'est cette valeur d'itération qu'on utilise pour coder la couleur affichée pour le point en question, avec plus ou moins d'imagination.

Vous définirez donc une fonction ayant le prototype suivant:

int mandelbrot(float x, float y, int iteration_max);

Cette fonction a les propriétés suivantes:

  • les paramètres x et y correspondent respectivement aux valeurs réelles et imaginaires de la constante c dans le calcul de la suite (Zn+1 = Zn²+c) - en d'autres termes c = x + i.y.
  • le nombre d'itérations de la suite est borné par iteration_max
  • la valeur de retour est le nombre d'itérations de la suite avant que celle-ci ne diverge ou atteigne iteration_max, donc toujours comprise entre 0 et iteration_max inclusivement.

L'ensemble de départ sur lequel les valeurs (x,y) seront choisies se situe sur l'intervalle [-2, 1] x [-1, 1], ce qui correspond à la représentation graphique affichée sur cette page.

Affichage

On produira un fichier PNG à l'aide de la bibliothèque libpng 1.2. Celle-ci permet de produire facilement un fichier image, compressé ou non, à partir d'une représentation ligne par ligne (vecteurs) ou complète (matrice) en mémoire de l'image à produire.

Dans un premier temps, utilisez un format de sortie en niveaux de gris sur 8 bits (un pixel = un octet de type entier non signé): ils vous suffit de limiter les itérations de l'algorithme à 255 et d'afficher la valeur telle quelle (vous verrez alors l'ensemble de Mandelbrot en nuances de gris).

Dans un deuxième temps vous pourrez si vous le désirez produire une image couleur (RGB), dans ce cas il faudra faire appel à votre imagination pour produire 3 composantes (rouge, vert, bleu) à partir de la valeur de retour de la fonction mandelbrot (vous pouvez utiliser des fonctions trigonométriques et/ou logarithmiques pour produire des "palettes de couleur").

Pour la sortie, utilisez le mécanisme qui permet d'écrire le résultat dans un fichier de type FILE*, et utilisez simplement le fichier prédéfini stdout pour écrire sur la sortie standard. Exécutez alors votre programme comme suit:

$ ./mandelbrot >test.png

La gestion des erreurs de libpng est également complexe et délicate, vous pourrez l'ignorer (appels à setjmp).

Consultez le programme de référence source:/insia/c/projet-mandelbrot/image-cgi.c qui fournit les détails d'utilisation de libpng. Notes sur les techniques de production d'image:

  • L'image est écrite ligne par ligne à l'aide de la fonction png_write_row, on utilise donc un tableau pour mémoriser les résultats des calculs sur une ligne complète
  • Il faut bien entendu évaluer la fonction mandelbrot pour tous les pixels de l'image, vous aurez donc besoin des boucles imbriquées qui génèrent les valeurs (x,y) des coordonnées des pixels
  • Attention: les coordonnées de l'image utilisent un repère différent de celui nécessaire au calcul de l'ensemble de Mandelbrot (voir Changement de repère).

Interface CGI

Afin d'obtenir un programme interactif où on peut zoomer sur une partie de l'ensemble de Mandelbrot en cliquant dessus, nous allons utiliser le navigateur web. Dans ce scenario, notre programme doit pouvoir être invoqué par un serveur web selon deux modes différents:

  • Le premier mode produira un contenu HTML qui indiquera au navigateur web que:
    1. on veut afficher l'image générée par notre programme (tag <img src="mandelbrot/image?...">)
    2. on veut également que notre programme soit invoqué lorsque l'on clique sur l'image (tag <a href="mandelbrot?...">)
    3. les coordonnées du pointeur de la souris soient fournis en paramètre de l'appel du programme (attribut ismap="ismap") (cf. client side mapping).
  • Le deuxième mode produira une image PNG de l'ensemble de Mandelbrot, où le repère de cet ensemble sera paramétrable à l'aide d'un facteur de zoom et des coordonnées du centre de l'image (voir Changement de repère plus bas).

Pour distinguer le mode dans lequel le programme s'exécute, on choisit par convention de lui passer l'option /image pour le mode PNG, et rien pour le mode HTML. Ceci peut se programmer ainsi:

if (strcmp(getenv("PATH_INFO"), "image") == 0) {
  /* on est en mode PNG */
} else {
  /* on est en mode HTML */
}

Dans les deux cas, veillez à ce que vos programmes précisent bien dans l'entête HTTP (la première ligne produite par votre programme et qui finir par un double retour chariot \r\n\r\n) le type MIME de l'information renvoyée: text/html pour un contenu HTML, image/png pour une image PNG.

Changement de repère

Vous aurez besoin de passer de l'espace de l'image, où l'unité est le pixel et l'origine toujours en haut à gauche, au repère orthonormé de Mandelbrot centré sur des coordonnées données (x0, y0) et dont l'échelle est zoom pixels/unité. Vous pouvez utiliser le code suivant:

/* Dimensions de l'image, constante */
const int width  = 600;
const int height = 400;

float mandelbrot_x(int pixel_x, int zoom, float x0) {
  return x0 + (pixel_x - width / 2) / (float)zoom;
} 

float mandelbrot_y(int pixel_y, int zoom, float y0) {
  return y0 - (pixel_y - height / 2) / (float)zoom;
}

Mode HTML

Pour le premier mode, vous aurez besoin de produire une sortie HTML similaire à source:/insia/c/projet-mandelbrot/mandelzoom.html dont voici l'extrait intéressant:

  <a href="mandelbrot?zoom=200&x=-0.5&y=0">
    <img src="mandelbrot/image?zoom=200&x=-0.5&y=0" ismap="ismap" />
  </a>

Une page HTML qui contient ce code se lit comme suit:

  • L'image affichée est entièrement définie par le facteur de zoom 200 et les coordonnées du centre de l'image (-0.5, 0), et c'est le mode PNG du programme qui s'en charge (src="mandelbrot/image...).
  • La prochaine image à afficher sera définie à partir du repère actuel (paramètres zoom, x et y) et des coordonnées du pointeur de la souris lorsque l'utilisateur clique sur l'image - qui seront passées par le navigateur en rajoutant ?i,j à la référence, où i et j sont des coordonnées (entières) dans le repère de l'image.

Cela signifie que votre mode HTML doit être capable de lire 5 paramètres en entrée. Vous pouvez procéder comme suit:

int zoom, clic_x, clic_y;
float x0, y0;
char* query_string;

query_string = getenv("QUERY_STRING");
if (sscanf(query_string, "/mandelbrot?zoom=%d&x=%f&y=%f?%d,%d", &zoom, &x0, &y0, &clic_x, &clic_y) < 5) {
  /* Il semble qu'il manque des paramètres (cas du lancement initial), utilisez des valeurs par défaut! */ 
   ...
}

Mode PNG

Il s'agit ni plus ni moins du programme élaboré dans la partie précédente, mais avec une convention précise sur le changement de repère entre image (pixels) et ensemble de Mandelbrot. Vous pouvez réutiliser un mécanisme similaire au mode HTML pour récupérer les paramètres avec scanf.


Pensez à vérifier les propriétés suivantes:

  • Utilisez une image avec un ratio 4/3, par exemple 600x400 pixels (pour accomoder le repère initial de [-2, 1]x[-1, 1])
  • La coordonnée centrale de l'ensemble initial est [-0.5, 0]
  • Le zoom initial est donc dans notre exemple de 600/3 = 400/2 (cad. 200 pixels par unité)
Last modified 14 years ago Last modified on Dec 20, 2006, 4:54:56 PM

Attachments (1)

Download all attachments as: .zip