Gros probléme d'emails avec Yahoo

Yahoo refuse tous les emails du site. Si vous avez une adresse chez un autre prestataire, c'est le moment de l'utiliser ;)

En cas de soucis, n'hésitez pas à aller faire un tour sur la page de contact en bas de page.

par skywodd, le

Afficher la fractale de Mandelbrot dans un navigateur web en utilisant un moteur d'affichage cartographique

Ce projet n'était pas sensé aller aussi loin ...

Image d'entête

par skywodd | | Licence (voir pied de page)

Catégories : Projets | Mots clefs : C/C++ Mandelbrot Fractale Python Leaflet Flask Lua Nginx GMPlib

Cet article n'a pas été mis à jour depuis un certain temps, son contenu n'est peut être plus d'actualité.

Dans mes précédents articles, j'avais présenté divers codes pour afficher la fractale de Mandelbrot sur PC et sur cartes Arduino / Genuino. Durant la rédaction de ces articles, je me suis dit qu'il serait intéressant d'essayer de faire une version web. Et c'est ainsi que cet article a vu le jour.

Sommaire

Bonjour à toutes et à tous !

Dans mes précédentsarticles, je vous avais présenté divers extraits de codes permettant d'afficher la fractale de Mandelbrot sur un ordinateur ou sur une carte Arduino / Genuino.

À mon grand plaisir, j'ai remarqué que vous étiez nombreux à apprécier ces articles. Je me suis donc laissé tenter par un projet un peu fou qui me faisait envie depuis longtemps : afficher une version zoomable de la fractale de Mandelbrot, directement dans un navigateur web.

Afficher une fractale dans un navigateur web

Commençons cet article par une petite séance de brainstorming ;)

Pour afficher une page web, il faut un navigateur web (du côté client) et un serveur web (du côté serveur), ça parait assez logique.

Maintenant, comment afficher une fractale dans un navigateur web ? En réalité, il n'y a pas beaucoup de solutions :

  • Soit on utilise du code Javacript côté client pour générer et afficher la fractale,

  • Soit on utilise du code côté serveur pour générer la fractale sous forme d'image et la transmettre comme telle au navigateur web,

  • Soit on fait un mix des deux solutions ci-dessus.

Calculer en temps réel la fractale de Mandelbrot côté client serait beaucoup trop lent. Sur un PC de bureau haut de gamme ou un PC de jeu, les performances de calcul seraient sûrement suffisantes pour faire les calculs sans que l'utilisateur se rende compte de quoi que ce soit. Mais sur un smartphone, une tablette ou même un PC un peu ancien, cela serait affreusement lent. De plus, même dans le cas où l'ordinateur aurait suffisamment de puissance, il ne serait pas très bien vu qu'une simple page web utilise toutes les ressources processeur au point de faire ramer l'ordinateur tout entier.

La seconde solution parait plus simple. Une fractale n'est rien de plus qu'une image en soit. Pourrait-on imaginer précalculer une (ou plusieurs) image(s) gigantesque(s) et les envoyer au navigateur web pour qu'il zoome dedans ?

Précalculer des images gigantesques serait une solution intéressante, mais malheureusement peu efficace. Le temps de calcul de chaque image prendrait des années et se conclurait par des fichiers d'images de plusieurs centaines de méga-octets, voir giga-octets. À moins d'avoir la fibre optique et plusieurs dizaines de giga-octets de mémoire vive, ces images seraient tout simplement impossible à afficher.

Ne reste donc qu'une seule solution : la solution mixte. L'idée ici est de générer les images côté serveur en fonction de la demande, en découpant l'image gigantesque en petits morceaux. Après tout, pourquoi calculer une image entière si l'utilisateur a zoomé comme un malade pendant des heures sur une zone bien précise ? De plus, générer des portions de la fractale de Mandelbrot est trivial.

Cependant, il reste un problème avec cette solution mixte : comment agencer et afficher les morceaux d'images côté client ? Côté client, il faut calculer les numéros des portions d'images à afficher, les agencer dans le bon ordre, gérer l'action de zoom, etc. Tout cela n'est possible qu'en utilisant un morceau de code côté client.

Afficher des images géantes par petits morceaux

Après avoir lu le chapitre précédent, vous devez sûrement vous dire : "arf, il va falloir faire du Javascript super compliqué pour calculer des indices en X et Y, des niveaux de zoom et gérer tout un tas d'animations … ça va être ennuyeux au possible !". Eh bien oui, il va falloir faire tout ça … ou pas !

Capture d'écran du site Open Street Map

Capture d'écran du site Open Street Map

Il y a des applications qui font exactement ce que l'on cherche à faire : afficher une portion d'une image gigantesque en la découpant en images de taille égale puis en recollant plein de petits morceaux d'images. Ces applications s'appellent Google Maps JS, Open Layers, Leaflet, etc.

Toutes ces applications sont des moteurs d'affichage cartographique. Vous les avez probablement déjà utilisés si vous avez un jour fait un tour sur Google Map ou sur Open Street Map.

Quelle est la différence entre afficher une carte du monde et afficher une fractale ? Aucune, c'est techniquement la même chose !

PS La seule différence réside dans la gestion des coordonnées au sein de la "carte". Une longitude / latitude n'a pas grand intérêt en dehors d'une carte du monde. Mais comme l'on n’utilise pas ces coordonnées pour l'affichage, cela ne pose aucun problème.

Réutiliser le moteur d'affichage de Google Maps serait un peu compliqué (même si cela est faisable), car celui-ci a été conçu dans la seule optique d'afficher des cartes routières en provenance des serveurs de Google. Cependant, il existe un projet similaire à Google Maps est complètement Open Source : Open Street Map. Je suis certain que vous avez déjà entendu parler de ce projet ;)

Rendez à César ce qui appartient à César

Il y a souvent une confusion au sujet du projet Open Street Map. Je vais donc mettre au clair un détail très important.

Non, Open Street Map n'est pas un moteur d'affichage cartographique. C'est une "simple" base de données d'informations cartographiques. Celle-ci est disponible sous la forme d'un fichier XML compressé de presque 50Go (plus de 650Go une fois décompressés).

Pour afficher les informations routières du projet Open Street Map, il faut utiliser d'autres projets open source comme Open Layers ou encore Leaflet, pour ne citer que les plus connus. Ce sont ces projets qui permettent l'affichage des données cartographiques.

Pour résumer, Open Street Map est la base de données des informations cartographiques et Open Layers / Leaflet sont les moteurs d'affichage web.

N.B. Entre les deux, il y a un troisième morceau de code, qui tourne généralement sur un serveur web, pour convertir les données XML en images.

Tous ces moteurs d'affichage cartographique fonctionnent via le même principe : un serveur web fourni des "tuiles" (des fragments d'image de taille fixe) classées sur trois niveaux : X, Y et Z. X et Y représentent la position de la tuile dans l'image d'origine et Z représente le zoom désiré par l'utilisateur.

Afficher une image géante se résume à redimensionner l'image à une taille bien précise puis à la découper en tuiles carrées de 256 pixels de côté (la taille standard d'une tuile). La taille de l'image source et le nombre de tuiles varie en fonction du zoom :

  • 1 x 1 tuiles pour le zoom 0 (soit une image totale de 256 x 256 pixels),

  • 2 x 2 tuiles pour le zoom 1 (soit une image totale de 512 x 512 pixels),

  • 4 x 4 tuiles pour le zoom 2 (soit une image totale de 1024 x 1024 pixels),

  • 8 x 8 tuiles pour le zoom 3 (soit une image totale de 2048 x 2048 pixels),

  • etc.

Les lecteurs attentifs auront remarqué que la taille de l'image d'origine est liée à une puissance de deux en fonction du zoom. Une carte Open Street Map peut atteindre le niveau de zoom 18 (ce qui équivaut à un zoom au niveau d'une rue) soit 262 144 x 262 144 tuiles au total. Cela équivaut à une image carrée de 67 108 864 pixels de côtés. Outch !

Si l'on devait stocker tous les fragments de cette image, ainsi que ceux des niveaux de zoom inférieurs, il faudrait plusieurs pétaoctets d'espace disque (un pétaoctets = 1000 téra-octets = 1 000 000 giga-octets). De plus, il y aurait tellement de fichiers par dossier qu'il faudrait utiliser un système de fichiers spécialisés comme ZFS, car les systèmes de fichiers "classiques" ne peuvent pas indexer autant de fichiers sur un même disque.

Les serveurs fournissant les tuiles pour les cartes Open Street Map génèrent à la volée les tuiles demandées par les utilisateurs. Comme une grande majorité des tuiles ne sont jamais demandées, cela permet de réduire drastiquement le temps de calcul et l'espace disque requis. Qui s'amuse à regarder l'océan en zoom 18 sur Google maps ou Open Street Map ?

Jsuis la carte, jsuis la carte.

Pour ce projet, j'ai décidé d'utiliser le moteur d'affichage Leaflet. J'ai fait ce choix pour une raison très simple : ce moteur d'affichage a été conçu pour fonctionner avec n'importe qu'elle source d'informations cartographiques, que se soit Open Street Map ou autre.

Afficher une carte Leaflet en plein écran se résume à écrire ces quelques lignes : 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
<!DOCTYPE html>
<html>
<head>
    <!-- Les métadonnées de la page web -->
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">

    <title>Mandelbrot explorer</title>
    
    <!-- Le fichier CSS de Leaflet -->
    <link rel="stylesheet" href="http://cdn.leafletjs.com/leaflet/v0.7.7/leaflet.css" />
    
    <!-- Quelques instructions CSS pour l'affichage en plein écran de la carte -->
    <style>
        body {
            padding: 0;
            margin: 0;
        }
        
        html, body, #map {
            height: 100%;
            width: 100%;
        }
    </style>
</head>
<body>

    <!-- L'emplacement pour la carte -->
    <div id="map"></div>

    <!-- Le fichier JavaScript de Leaflet -->
    <script src="http://cdn.leafletjs.com/leaflet/v0.7.7/leaflet.js"></script>
 
    <!-- Le code JavaScript pour l'affichage de la carte -->
    <script>
        var mymap = L.map('map').setView([0, 0], 0);

        L.tileLayer('tiles/{z}/{x}/{y}.png', {
            minZoom: 0,
            maxZoom: 31,
            attribution: 'TamiaLab &copy; 2016',
            noWrap: true
        }).addTo(mymap);
    </script>
</body>
</html>

La partie intéressante du code ci-dessus est celle-ci (le reste n'est rien de plus qu'un copier coller de l'exemple fourni avec Leaflet) : 

1
2
3
4
5
6
7
8
var mymap = L.map('map').setView([0, 0], 0);

L.tileLayer('tiles/{z}/{x}/{y}.png', {
    minZoom: 0,
    maxZoom: 31,
    attribution: 'TamiaLab &copy; 2016',
    noWrap: true
}).addTo(mymap);

La première ligne permet de créer une carte Leaflet à l'emplacement voulu dans la page. Cette première ligne spécifie aussi la position X et Y, ainsi que le zoom par défaut.

La seconde ligne permet de spécifier à Leaflet l'URL du serveur à contacter pour télécharger les tuiles qui serviront à l'affichage de la "carte". C'est aussi cette ligne qui permet d'assigner diverses options à la carte, comme le zoom minimum et maximum, le copyright et ici l'option "noWrap" qui désactive le mode "globe" (normalement quand on dépasse d'un côté de la carte on revient de l'autre).

Et c'est la tuile …

Maintenant que la partie affichage dans le navigateur web est prête, il faut un serveur capable de générer à la volée les tuiles pour l'affichage de la fractale.

J'ai donc repris le code de mes précédents articles, ainsi qu'un algorithme anciennement disponible sur le Site du Zéro pour faire un code Python qui calcule une tuile en fonction de sa position X et Y et du zoom Z. La tuile générée est ensuite convertie en image PNG au moyen de la bibliothèque Pillow.

Comme le processus de calcul d'une tuile est relativement long, j'ai prévu dans le code un système de cache. Chaque tuile générée est stockée dans un dossier après le calcul, ainsi, au calcul suivant, l'image précédemment calculée est renvoyée sans refaire le calcul.

Pour la partie web, j'ai utilisé un micro-framework web très connu des développeurs Python : Flask. Flask s'occupe de la communication avec le navigateur web et de la gestion des URLs, mon code n'a qu'à utiliser les fonctions du framework pour transmettre l'image une fois celle-ci générée.

Le code complet : 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
"""
Générateur de fractale de Mandelbrot sous forme de tuiles pour Leaflet.
Conçu à partir de l'algorithme disponible ici :
http://sdz.tdct.org/sdz/dessiner-la-fractale-de-mandelbrot.html
"""

# Dépendances
import os
from io import BytesIO
from PIL import Image
from flask import Flask
from flask import send_file


# Fenêtre de dessin dans le plan réel / complexe de mandelbrot
WINDOW_X1 = -2.5   # Gauche
WINDOW_X2 =  1.0   # Droite
WINDOW_Y1 = -1.75  # Haut
WINDOW_Y2 =  1.75  # Bas
# N.B. La zone de dessin doit être carrée pour la génération de tuiles

# Taille des tuiles (obligatoirement carrées)
TILE_SIZE_SQ = 256

# Nombre de couleurs
MAX_ITERATION = 142

# Tableaux de couleurs (142 couleurs, tiré d'un nuancier trouvé sur le web)
COLOR_TABLE = (
    0xf7df, 0xff5a, 0x07ff, 0x7ffa, 0xf7ff, 0xf7bb, 0xff38, 0xff59, 0x001f, 0x895c, 
    0xa145, 0xddd0, 0x5cf4, 0x7fe0, 0xd343, 0xfbea, 0x64bd, 0xffdb, 0xd8a7, 0x07ff, 
    0x0011, 0x0451, 0xbc21, 0xad55, 0x0320, 0xbdad, 0x8811, 0x5345, 0xfc60, 0x9999, 
    0x8800, 0xecaf, 0x8df1, 0x49f1, 0x2a69, 0x067a, 0x901a, 0xf8b2, 0x05ff, 0x6b4d, 
    0x1c9f, 0xd48e, 0xb104, 0xffde, 0x2444, 0xf81f, 0xdefb, 0xffdf, 0xfea0, 0xdd24, 
    0x8410, 0x0400, 0xafe5, 0xf7fe, 0xfb56, 0xcaeb, 0x4810, 0xfffe, 0xf731, 0xe73f, 
    0xff9e, 0x7fe0, 0xffd9, 0xaedc, 0xf410, 0xe7ff, 0xffda, 0xd69a, 0x9772, 0xfdb8, 
    0xfd0f, 0x2595, 0x867f, 0x839f, 0x7453, 0xb63b, 0xfffc, 0x07e0, 0x3666, 0xff9c, 
    0xf81f, 0x8000, 0x6675, 0x0019, 0xbaba, 0x939b, 0x3d8e, 0x7b5d, 0x07d3, 0x4e99, 
    0xc0b0, 0x18ce, 0xf7ff, 0xff3c, 0xff36, 0xfef5, 0x0010, 0xffbc, 0x8400, 0x6c64, 
    0xfd20, 0xfa20, 0xdb9a, 0xef55, 0x9fd3, 0xaf7d, 0xdb92, 0xff7a, 0xfed7, 0xcc27, 
    0xfe19, 0xdd1b, 0xb71c, 0x8010, 0xf800, 0xbc71, 0x435c, 0x8a22, 0xfc0e, 0xf52c, 
    0x2c4a, 0xffbd, 0xa285, 0xc618, 0x867d, 0x6ad9, 0x7412, 0xffdf, 0x07ef, 0x4416, 
    0xd5b1, 0x0410, 0xddfb, 0xfb08, 0x471a, 0xec1d, 0xd112, 0xf6f6, 0xffff, 0xf7be, 
    0xffe0, 0x9e66, 0x0000
)

# Flask application
app = Flask(__name__)


def draw_mandelbrot(output_filename,
                    window_x1, window_x2, window_y1, window_y2,
                    output_width, output_height):
    """
    Fonction de dessin d'une fractale de Mandelbrot.
    """

    # Taille de l'image de sortie
    zoom_x = output_width / (window_x2 - window_x1)
    zoom_y = output_height / (window_y2 - window_y1)

    # Alloue l'espace pour l'image de sortie
    im = Image.new('RGB', (output_width, output_height))
    framebuffer = im.load()

    # Pour chaque pixel en Y
    for y in range(output_height):

        # Pour chaque pixel en X
        for x in range(output_width):

            # Variables de calcul
            c_r = x / zoom_x + window_x1
            c_i = y / zoom_y + window_y1
            z_r = z_i = i = 0

            # Magie noir mathématique
            while (z_r * z_r + z_i * z_i) < 4.0 and i < MAX_ITERATION:
                tmp = z_r
                z_r = z_r * z_r - z_i * z_i + c_r
                z_i = 2.0 * z_i * tmp + c_i
                i += 1

            # Dessine le pixel (avec conversion RGB565 -> RGB888)
            color = COLOR_TABLE[i]
            r = ((color >> 11) & 0x1F) << 3
            g = ((color >> 5) & 0x3F) << 2
            b = (color & 0x1F) << 3
            framebuffer[x, y] = r, g, b

    # Sauvegarde l'image finale dans le fichier de sortie
    im.save(output_filename, 'PNG')


def draw_mandelbrot_tile(output_file,
                         window_x1, window_x2, window_y1, window_y2,
                         x, y, z, tile_size_sq):
    """
    Fonction de dessin d'une tuile représentant une portion de la fractale de Mandelbrot.
    """
    
    # Taille absolue de la zone de dessin dans le plan réel / complexe de mandelbrot
    window_x = abs(window_x1) + abs(window_x2)
    window_y = abs(window_y1) + abs(window_y2)
    if window_x != window_y:
        raise ValueError("La zone de dessin doit être carrée.")

    # Calcul du nombre de tuiles nécessaire pour couvrir la zone de dessin
    nb_tiles_xy = pow(2.0, z)

    # Taille de la zone de dessin de chaque tuile
    tile_window_x = window_x / nb_tiles_xy
    tile_window_y = window_y / nb_tiles_xy
    
    # Calcul de la plage de dessin de la tuile
    tile_x = tile_window_x * x + min(window_x1, window_x2)
    tile_y = tile_window_y * y + min(window_y1, window_y2)

    # Dessine la tuile
    draw_mandelbrot(output_file,
                    tile_x, tile_x + tile_window_x,
                    tile_y, tile_y + tile_window_y,
                    tile_size_sq, tile_size_sq)


# Page principale
@app.route("/")
def index():
    return send_file('index.html', mimetype='text/html')


# Générateur de tuiles
@app.route("/tiles/<int:z>/<int:x>/<int:y>.png")
def tiles(z, x, y):

    # Génére le chemin du fichier de sortie
    output_file = "tiles/{}/{}/{}.png".format(z, x, y)

    # Vérifie que l'image n'existe pas déjà
    if os.path.exists(output_file):
        return send_file(output_file, mimetype='image/png')

    # Créé les dossiers de sortie si nécessaire
    os.makedirs("tiles/{}/{}".format(z, x), exist_ok=True)

    # Génére l'image
    draw_mandelbrot_tile(output_file,
                         WINDOW_X1, WINDOW_X2, WINDOW_Y1, WINDOW_Y2,
                         x, y, z, TILE_SIZE_SQ)
    return send_file(output_file, mimetype='image/png')


# Point d'entrée du programme
if __name__ == "__main__":
    app.run()

L'extrait de code ci-dessus est disponible en téléchargement ici MandelbrotMapTilesFlask.zip.

Si vous voulez tester ce code, il vous faudra l'interpréteur Python 3.x, les bibliothèques Flask et Pillow, ainsi que le contenu de l'archive en lien ci-dessus ci-dessus.

N.B. Le code est conçu pour lancer le serveur de test par défaut quand on l'exécute. Ce serveur de test est très pratique pour faire des tests, mais pas pour une utilisation "réelle" sur un serveur web.

Capture d'écran du projet "Mandelbrot Explorer"

Capture d'écran du projet

En dirigeant son navigateur web sur l'URL http://localhost:5000/ après avoir lancé le code, on découvre avec joie la fractale de Mandelbrot. On peut zoomer, se déplacer dans la fractale, c'est super, mais … C'est très lent.

Le langage Python est très pratique et relativement rapide, mais calculer la fractale de Mandelbrot est un processus très gourmand en calcul. Le code Python met ainsi entre une demi-seconde et plusieurs dizaines de secondes pour générer une seule tuile. Sur un écran 24", il faut pas moins de 32 tuiles pour couvrir tout l'écran. Autant dire qu'il ne faut pas être pressé …

Pour faire simple, le concept est là, il ne manque plus qu'un peu de vitesse.

On passe la vitesse supérieure

Le code Python est trop lent. Il faut quelque chose de plus rapide !

Une première solution serait de déporter le code de calcul de la fractale dans un module Python compilé écrit en langage C. Cela serait beaucoup plus rapide, mais aussi beaucoup plus complexe. Faire des extensions compilées pour Python est une vraie plaie.

Une autre solution envisageable serait de convertir le code entièrement en langage C et d'utiliser la bibliothèque FastCGI pour permettre au code de communiquer avec un serveur web comme Apache ou Nginx. Cela serait très rapide, mais aussi très lourd à mettre en oeuvre.

Je me suis donc gratté la tête un instant et je me suis rappelé d'une fonctionnalité très intéressante du serveur web que j'utilise quotidiennement (Nginx) : le scripting Lua.

Lua est un langage de script (comme Python), mais beaucoup plus simpliste et avec la capacité de charger des modules compilés très facilement. Comme Nginx intègre l'interpréteur Lua (doc), il devrait être possible d'écrire un script Lua pour charger une version compilée du code est laissé Nginx et Lua s'occuper de tout le reste.

Étape 1 : le serveur web

J'ai donc commencé par écrire un fichier de configuration pour Nginx : 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
lua_package_cpath ";;/var/www/html/mandelbrot.so";

server {
    listen 80 default_server;
    listen [::]:80 default_server;

    root /var/www/html;

    index index.html;

    server_name _;

    location / {
        # First attempt to serve request as file, then
        # as directory, then fall back to displaying a 404.
        try_files $uri $uri/ =404;
    }

    location ~/tiles/(\d+)/(\d+)/(\d+).png {
        try_files $uri @tilegenerator;

        add_header Pragma "public";
        add_header Cache-Control "public, max-age=31536000";
        expires 1y;
        access_log off;
        log_not_found off;
    }

    location @tilegenerator {
        set $output_dir "/var/www/html/tiles";
        content_by_lua '
            local mandelbrot = require "mandelbrot"
            local dirpath = ngx.var.output_dir
            local imgpath = ngx.var.uri
            local z, x, y = string.match(imgpath, "/tiles/(%d+)/(%d+)/(%d+)[.]png")
            if tonumber(z) > 31 then
                ngx.exit(404)
            end
            local ret = mandelbrot.render_tile(dirpath, tonumber(z), tonumber(x), tonumber(y))
            if ret ~= 0 then
                ngx.status = 500
                ngx.say("Erreur " .. ret)
                ngx.exit(ngx.HTTP_OK)
            end
            ngx.exec(imgpath)
        ';
    }
}

Ce fichier de configuration commence par renseigner l'emplacement du fichier compilé pour Lua avec l'instruction lua_package_cpath ";;/var/www/html/mandelbrot.so";.

Ensuite dans le bloc server (là où on déclare les instances de chaque site que le serveur doit gérer), j'ai déclaré un site web par défaut (c'est à dire sans nom de domaine). 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
listen 80 default_server;
listen [::]:80 default_server;

root /var/www/html;

index index.html;

server_name _;

location / {
    # First attempt to serve request as file, then
    # as directory, then fall back to displaying a 404.
    try_files $uri $uri/ =404;
}

Ce site web est disponible en HTTP sur le port 80. Les fichiers du site se trouvent dans /var/www/html et la page d'accueil se nomme index.html. Le site n'a pas de nom de domaine. Il est accessible uniquement via l'adresse IP locale du serveur.

Le premier bloc location permet d'afficher la page d'accueil et les fichiers statiques se trouvant dans le dossier /var/www/html. Si le fichier demandé n'existe pas, le serveur affiche une page d'erreur 404. 

1
2
3
4
5
6
7
8
9
location ~/tiles/(\d+)/(\d+)/(\d+).png {
    try_files $uri @tilegenerator;

    add_header Pragma "public";
    add_header Cache-Control "public, max-age=31536000";
    expires 1y;
    access_log off;
    log_not_found off;
}

La où les choses deviennent intéressante, c'est au niveau du second bloc location. Celui-ci définit les règles d'accès aux fichiers d'images des tuiles.

Via l'instruction try_files, je demande à Nginx de vérifier si le fichier image existe sur le disque dur. Si le fichier existe, Nginx transmettra le fichier au navigateur web, sans rien faire d'autre. Si le fichier n'existe pas, la requête sera transférée à un autre bloc location nommé tilegenerator qui se chargera de générer la tuile à la volée.

Dans les deux cas (image existante ou générée à la volée), je demande à Nginx de préciser au navigateur web que l'image qu'il vient de recevoir doit être gardée en mémoire pour une durée maximum d'un an. Cela permet d'éviter des demandes inutiles quand l'utilisateur zoom et dé-zoom.

Je demande aussi à Nginx de ne pas écrire dans les fichiers de logs l'accès aux fichiers d'images des tuiles, pour éviter de me retrouver avec plusieurs centaines de giga-octets de fichiers de logs. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
location @tilegenerator {
    set $output_dir "/var/www/html/tiles";
    content_by_lua '
        local mandelbrot = require "mandelbrot"
        local dirpath = ngx.var.output_dir
        local imgpath = ngx.var.uri
        local z, x, y = string.match(imgpath, "/tiles/(%d+)/(%d+)/(%d+)[.]png")
        if tonumber(z) > 31 then
            ngx.exit(404)
        end
        local ret = mandelbrot.render_tile(dirpath, tonumber(z), tonumber(x), tonumber(y))
        if ret ~= 0 then
            ngx.status = 500
            ngx.say("Erreur " .. ret)
            ngx.exit(ngx.HTTP_OK)
        end
        ngx.exec(imgpath)
    ';
}

Le dernier bloc location nommé tilegenerator ne gère pas l'accès à une URL. Ce genre de bloc sert normalement à afficher des pages d'erreurs, générer des réponses dynamiques ou faire du filtrage.

Dans mon cas, le bloc permet de générer une tuile à la volée en chargeant un script Lua minimaliste. Le script Lua en question charge le module compilé "mandelbrot", récupère les valeurs de X, Y et Z depuis l'URL, fait un test rapide sur Z et laisse le gros du travail au module compilé. Une fois l'image générée, le script demande à Nginx de transmettre l'image au navigateur web en rééxécutant la requête d'origine (sauf que cette fois, l'image existe sur le disque).

PS Le test sur la valeur de Z est obligatoire, car les nombres entiers en Lua sont des nombres signés de 31 bits + signe. Il est donc impossible de dépasser le niveau de zoom 31 (rappel, X et Y sont liés au niveau de zoom par une puissance de 2). De plus, même en utilisant des nombres sur 64 bits, la précision des calculs est trop faible pour aller au-dessus du niveau de zoom 31.

Étape 2 : le module Lua compilé

Le serveur web est prêt à répondre aux navigateurs web du monde entier. Leaflet est prêt à afficher autant de tuiles que nécessaire. Il ne manque plus qu'un module Lua compilé pour générer les fameuses tuiles !

Attention aux yeux, ça va piquer : 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
/**
 * Générateur de fractale de Mandelbrot.
 * Conçu à partir de l'algorithme disponible ici : http://sdz.tdct.org/sdz/dessiner-la-fractale-de-mandelbrot.html
 */

/* Dépendances standards */
#include <math.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#ifdef _WIN32
#include <direct.h>
#include <windows.h>
#define PATH_MAX MAX_PATH
#define mkdir(p, m) mkdir(p)
#define EXPORT __declspec(dllexport)
#elif defined __linux__
#include <sys/stat.h>
#include <sys/types.h>
#include <linux/limits.h>
#define EXPORT __attribute__ ((visibility ("default")))
#endif

/* Dépendances bonus pour l'extension LUA */
#include <lua.h>
#include <lualib.h>
#include <lauxlib.h>

/* Dépendances locales */
#include "lodepng.h"


/* Default mode for created directories */
#if defined __linux__
const mode_t DIR_PERMS = S_IRWXU | S_IRWXG | S_IROTH | S_IXOTH; // 0755
#endif

/* Fenêtre de dessin dans le plan réel / complexe de mandelbrot */
const double WINDOW_X1 = -2.5;  // Gauche
const double WINDOW_X2 =  1.0;  // Droite
const double WINDOW_Y1 = -1.75; // Haut
const double WINDOW_Y2 =  1.75; // Bas
// N.B. La zone de dessin doit être carrée pour la génération de tuiles

/* Niveau de zoom minimum et maximum (0 = 1x1 tuiles, 1 = 2x2, 2 = 4x4, 3 = 8x8, etc) */
const unsigned int MIN_ZOOM_LEVEL = 0;
const unsigned int MAX_ZOOM_LEVEL = 8;

/* Taille des tuiles (obligatoirement carrées) */
const unsigned int TILE_SIZE_SQ = 256;

/* Nombre de couleurs */
const unsigned int MAX_ITERATION = 142;

/* Tableaux de couleurs (142 couleurs, tiré d'un nuancier trouvé sur le web) */
const unsigned int COLOR_TABLE[] = {
    0xf7df, 0xff5a, 0x07ff, 0x7ffa, 0xf7ff, 0xf7bb, 0xff38, 0xff59, 0x001f, 0x895c,
    0xa145, 0xddd0, 0x5cf4, 0x7fe0, 0xd343, 0xfbea, 0x64bd, 0xffdb, 0xd8a7, 0x07ff,
    0x0011, 0x0451, 0xbc21, 0xad55, 0x0320, 0xbdad, 0x8811, 0x5345, 0xfc60, 0x9999,
    0x8800, 0xecaf, 0x8df1, 0x49f1, 0x2a69, 0x067a, 0x901a, 0xf8b2, 0x05ff, 0x6b4d,
    0x1c9f, 0xd48e, 0xb104, 0xffde, 0x2444, 0xf81f, 0xdefb, 0xffdf, 0xfea0, 0xdd24,
    0x8410, 0x0400, 0xafe5, 0xf7fe, 0xfb56, 0xcaeb, 0x4810, 0xfffe, 0xf731, 0xe73f,
    0xff9e, 0x7fe0, 0xffd9, 0xaedc, 0xf410, 0xe7ff, 0xffda, 0xd69a, 0x9772, 0xfdb8,
    0xfd0f, 0x2595, 0x867f, 0x839f, 0x7453, 0xb63b, 0xfffc, 0x07e0, 0x3666, 0xff9c,
    0xf81f, 0x8000, 0x6675, 0x0019, 0xbaba, 0x939b, 0x3d8e, 0x7b5d, 0x07d3, 0x4e99,
    0xc0b0, 0x18ce, 0xf7ff, 0xff3c, 0xff36, 0xfef5, 0x0010, 0xffbc, 0x8400, 0x6c64,
    0xfd20, 0xfa20, 0xdb9a, 0xef55, 0x9fd3, 0xaf7d, 0xdb92, 0xff7a, 0xfed7, 0xcc27,
    0xfe19, 0xdd1b, 0xb71c, 0x8010, 0xf800, 0xbc71, 0x435c, 0x8a22, 0xfc0e, 0xf52c,
    0x2c4a, 0xffbd, 0xa285, 0xc618, 0x867d, 0x6ad9, 0x7412, 0xffdf, 0x07ef, 0x4416,
    0xd5b1, 0x0410, 0xddfb, 0xfb08, 0x471a, 0xec1d, 0xd112, 0xf6f6, 0xffff, 0xf7be,
    0xffe0, 0x9e66, 0x0000
};


/**
 * Fonction de dessin d'une fractale de Mandelbrot.
 */
int draw_mandelbrot(const char* output_filename,
                    const double window_x1, const double window_x2,
                    const double window_y1, const double window_y2,
                    const unsigned int output_width, const unsigned int output_height) {

    /* Taille de l'image de sortie */
    const double zoom_x = (double) output_width / (window_x2 - window_x1);
    const double zoom_y = (double) output_height / (window_y2 - window_y1);

    /* Tableau temporaire pour les pixels RGB888 */
    unsigned char* framebuffer = (unsigned char*) malloc(output_width * output_height * 3);
    if (framebuffer == NULL) {
        puts("ERREUR: Impossible d'allouer l'espace mémoire pour l'image");
        return -1;
    }

    /* Pour chaque pixel en Y */
    for (unsigned int y = 0; y < output_height; ++y) {

        /* Pour chaque pixel en X */
        for (unsigned int x = 0; x < output_width; ++x) {

            /* Variables de calcul */
            double c_r = (double) x / zoom_x + window_x1;
            double c_i = (double) y / zoom_y + window_y1;
            double z_r = 0, z_i = 0;
            unsigned int i = 0;

            /* Magie noir mathématique */
            while ((z_r * z_r + z_i * z_i) < 4.0 && i < MAX_ITERATION) {
                double tmp = z_r;
                z_r = z_r * z_r - z_i * z_i + c_r;
                z_i = 2.0 * z_i * tmp + c_i;
                ++i;
            }

            /* Dessine le pixel (avec conversion RGB565 -> RGB888) */
            unsigned int color = COLOR_TABLE[i];
            unsigned int offset = (y * output_width + x) * 3;
            framebuffer[offset] = ((color >> 11) & 0x1F) << 3;
            framebuffer[offset + 1] = ((color >> 5) & 0x3F) << 2;
            framebuffer[offset + 2] = (color & 0x1F) << 3;
        }
    }

    /* Sauvegarde l'image finale dans le fichier de sortie */
    unsigned error = lodepng_encode24_file(output_filename, framebuffer, output_width, output_height);
    if(error) {
        printf("ERROR: Impossible d'écrire le fichier de sortie (%s)\n", lodepng_error_text(error));
        return -2;
    }

    /* Libére la mémoire */
    free(framebuffer);

    /* Pas d'erreur */
    return EXIT_SUCCESS;
}

/**
 * Fonction de dessin d'une tuile représentant une portion de la fractale de Mandelbrot.
 */
int draw_mandelbrot_tile(const char* tiles_directory, 
                         const double window_x1, const double window_x2,
                         const double window_y1, const double window_y2,
                         const unsigned int x, const unsigned int y, const unsigned int z, 
                         const unsigned int tile_size_sq) {
    
    /* Taille absolue de la zone de dessin dans le plan réel / complexe de mandelbrot */
    const double window_x = fabs(window_x1) + fabs(window_x2);
    const double window_y = fabs(window_y1) + fabs(window_y2);
    if (window_x != window_y) {
        puts("ERREUR: La zone de dessin doit être carrée.");
        return -3;
    }

    /* Calcul du nombre de tuiles nécessaire pour couvrir la zone de dessin */
    const double nb_tiles_xy = pow(2.0, z);

    /* Taille de la zone de dessin de chaque tuile */
    const double tile_window_x = window_x / nb_tiles_xy;
    const double tile_window_y = window_y / nb_tiles_xy;
    
    /* Créé le dossier de sortie pour Z si nécessaire */
    char filename[PATH_MAX];
    snprintf(filename, PATH_MAX, "%s/%u", tiles_directory, z);
    if (mkdir(filename, DIR_PERMS) && EEXIST != errno) {
        printf("Impossible de créer le dossier de destination \"%s\"\n", filename);
        return -4;
    }
    
    /* Créé le dossier de sortie pour x si nécessaire */
    snprintf(filename, PATH_MAX, "%s/%u/%u", tiles_directory, z, x);
    if (mkdir(filename, DIR_PERMS) && EEXIST != errno) {
        printf("Impossible de créer le dossier de destination \"%s\"\n", filename);
        return -4;
    }
    
    /* Calcul de la plage de dessin de la tuile */
    const double tile_x = tile_window_x * x + fmin(window_x1, window_x2);
    const double tile_y = tile_window_y * y + fmin(window_y1, window_y2);

    /* Génére le nom de fichier */
    snprintf(filename, PATH_MAX, "%s/%u/%u/%u.png", tiles_directory, z, x, y);

    /* Dessine la tuile */
    int ret = draw_mandelbrot(filename,
                              tile_x, tile_x + tile_window_x,
                              tile_y, tile_y + tile_window_y,
                              tile_size_sq, tile_size_sq);
    if (ret)
        return ret;

    /* Pas d'erreur */
    return EXIT_SUCCESS;
}

/**
 * Fonction de génération d'une carte compléte.
 */
int render_zoom_level(unsigned int zoom_level) {

    /* Calcul du nombre de tuiles nécessaire pour couvrir la zone de dessin */
    const unsigned int nb_tiles_xy = 1 << zoom_level;

    /* Pour chaque tuile en X et Y */
    printf("Map is made of an array of %u square tiles (zoom level %u)\n", nb_tiles_xy, zoom_level);
    for (unsigned int x = 0; x < nb_tiles_xy; ++x) {
        for (unsigned int y = 0; y < nb_tiles_xy; ++y) {

            /* Progression */
            printf("INFO: Rendering tile %u x %u (of %u x %u)...\n", x, y, nb_tiles_xy, nb_tiles_xy);

            /* Génére la tuile */
            int ret = draw_mandelbrot_tile("tiles", 
                                           WINDOW_X1, WINDOW_X2, WINDOW_Y1, WINDOW_Y2,
                                           x, y, zoom_level, TILE_SIZE_SQ);
            if (ret)
                return ret;
        }
    }

    /* Pas d'erreur */
    return EXIT_SUCCESS;
}

/**
 * Point d'entrée du programme.
 */
int main(void) {

    /* Génére tous les niveaux de zoom désirés */
    for (unsigned int zoom_level = MIN_ZOOM_LEVEL; zoom_level <= MAX_ZOOM_LEVEL; ++zoom_level) {

        /* Génére la carte */
        int ret = render_zoom_level(zoom_level);
        if (ret)
            return ret;
    }

    /* Pas d'erreur */
    return EXIT_SUCCESS;
}

/**
 * API du module d'extension LUA
 */
int l_render_mandelbrot_tile(lua_State *L) {
    
    /* Récupére les arguments obligatoires */
    const char* output_dirpath = luaL_checkstring(L, 1);
    const unsigned int z = luaL_checkint(L, 2);
    const unsigned int x = luaL_checkint(L, 3);
    const unsigned int y = luaL_checkint(L, 4);
    
    /* Récupére les arguments optionnels */
    const double window_x1 = luaL_optnumber(L, 5, WINDOW_X1);
    const double window_x2 = luaL_optnumber(L, 6, WINDOW_X2);
    const double window_y1 = luaL_optnumber(L, 7, WINDOW_Y1);
    const double window_y2 = luaL_optnumber(L, 8, WINDOW_Y2);
    const unsigned int tile_size_sq = luaL_optint(L, 9, TILE_SIZE_SQ);

    
    /* Génére la tuile */
    int ret = draw_mandelbrot_tile(output_dirpath,
                                   window_x1, window_x2, window_y1, window_y2,
                                   x, y, z, tile_size_sq);
    lua_pushinteger(L, ret);
    
    /* Return the number of results */
    return 1;  
}

/**
 * Point d'entrée du module d'extension LUA
 */

static const luaL_Reg mandelbrot_funcs[] = {
    {"render_tile", l_render_mandelbrot_tile},
    {NULL, NULL}
};

int EXPORT luaopen_mandelbrot(lua_State * L) {
#if LUA_VERSION_NUM > 501
    luaL_newlibtable(L, mandelbrot_funcs);
    luaL_setfuncs(L, mandelbrot_funcs, 0);
#else
    luaL_register(L, "mandelbrot", mandelbrot_funcs);
#endif
    return 1;
}

La première étape a été de convertir le code Python en code C. Je ne m'attarderai pas sur le sujet. Les commentaires dans le code expliquent les grandes lignes.

La seconde étape a été de trouver une bibliothèque de code C capable de manipuler des images PNG. J'ai dans un premier temps essayé d'utiliser la libpng qui est la bibliothèque de code de référence pour manipuler des images PNG en C, sans réel succès. Je suis donc allé à la recherche d'une autre bibliothèque de code et je suis tombé sur LodePNG. Deux fichiers de code source, des fonctions ultras simples et efficaces, un pur bonheur. L'intégration de LodePNG m'a pris moins de cinq minutes.

PS J'ai ajouté un morceau de code pour tester le bon fonctionnement de mon code en ligne de commande. Ceci explique la présence de la fonction main() alors que le code final est compilé comme un module.

Et puis est venu le temps de l'ultime étape : l'intégration du code avec Lua. Et là, autant dire que j'ai eu du mal.

En soi, faire un module Lua compilé est très simple. Il suffit de déclarer une fonction nommée luaopen_LENOMDUMODULE() et un tableau avec les différentes fonctions du module que l'on souhaite rendre accessible.

Seulement, entre les versions 5.1 et 5.2 de Lua, une grosse modification a eu lieu. Quand j'ai voulu charger mon module Lua 5.2 dans Nginx (utilisant Lua 5.1), Nginx, Lua et mon module ont planté. Un bon gros crash, sans message d'erreur, sans indice pour le debug, rien.

Au final, il s'agissait juste d'une ligne à modifier … J'ai dû chercher pendant plus d'une heure le pourquoi du crash qui était bien évidemment expliqué à la toute fin de la documentation dans un chapitre expliquant les modifications entre les versions 5.1 et 5.2. Grrrrrr.

PS Pour les plus curieux qui voudraient comprendre à quoi servent les diverses fonctions luaL_XXX, voici le lien vers la référence technique de Lua.

Étape 3 : enjoy

Une fois le code compilé, le serveur Nginx relancé et le navigateur pointant sur la page web adéquate, on obtient un aperçu fluide de la fractale de Mandelbrot.

Pour ceux qui voudraient tester le code, j'ai fait une archive du projet avec le code source complet, le fichier de compilation et un script Vagrant permettant de mettre en place une machine virtuelle Linux avec Debian, Nginx et le code du projet automatiquement. L'archive est disponible ici : MandelbrotMapTilesLua.zip.

Pour utiliser le script Vagrant, il faudra disposer de la dernière version de Vagrant et de VirtualBox. Ensuite il suffira d'ouvrir un terminal de commande dans le dossier du projet et exécuter la commande vagrant up.

N.B. Le téléchargement de l'image disque de la machine virtuelle demande une bonne connexion internet. L'image compléte fait environ 450Mo.

Bonus : Ça tourne au ridicule …

J'aurai pu m'arrêter là (et j'aurai dû), mais ne pas pouvoir dépasser le niveau de zoom 31 me laissait un gout d'inachevé dans la bouche. J'avais envie de pouvoir zoomer comme un fou dans les recoins de la fractale de Mandelbrot.

J'ai donc repris le code pour intégrer la libGMP. Il s'agit d'une bibliothèque de code un peu spéciale qui permet de faire normalement des calculs cryptographiques avec des nombres à plusieurs centaines de digits.

Avec la libGMP il est possible d'additionner des nombres de tailles arbitrairement longues sans problème. De plus, avec les dernières versions, il est aussi possible de faire des calculs avec des nombres à virgules d'une précision quelconque.

La conversion du code pour la libGMP a demandé pas mal de bricolage. Pour ceux qui seraient intéressés, une archive du code (avec le fichier Vagrant qui va bien) est disponible ici : MandelbrotMapTilesGmp.zip.

Cette version permet de zoomer dans la fractale comme un dingue sans perdre en précision. Mais cette version est loin d'être fluide. Les calculs en nombres flottant sur 128 bits sont si couteux en calculs que le code final (compilé) est encore plus lent que la version Python en début d'article !

Conclusion

Ce projet est désormais terminé.

Je ne pourrai malheureusement pas fournir de version "live" des codes ci-dessus pour des raisons de sécurité et de performances.

Si vous voulez tester le résultat du projet, il faudra lancer les scripts Vagrant fournis avec le code pour mettre en place une machine virtuelle sur votre ordinateur. Cela nécessite un PC assez puissant avec au moins un processeur à quatre coeurs, 8Go de RAM et le support de la virtualisation matérielle.

Si ce projet vous a plu, n'hésitez pas à le commenter sur le forum, à le diffuser sur les réseaux sociaux et à soutenir le site si cela vous fait plaisir.

Articles en relation avec celui-ci

Cliquez ici pour accéder aux commentaires de l'article.