Rendu de terrain fractal en OpenGL

Alexandre Cruz, Julien Hognon, Jérôme Petazzoni

Introduction

Le but de ce projet est de générer et d'afficher un terrain fractal en utilisant OpenGL.

Nous avons décidé de nous appuyer sur un modèle original : la lamination géodésique. Il s'agit d'une transformation qui déforme une sphére (ou un ensemble quelconque de points). En l'itérant assez longtemps, on peut obtenir un sphéroïde pouvant passer pour une planète.

La planète étant modélisée par des triangles, afin de bénéficier d'un rendu fin (mais gourmand) ou bien grossier (mais rapide), nous partons d'une sphère comportant un petit nombre de facettes. Nous avons implémenté un système permettant d'affiner à volonté le rendu (par création de triangles plus petits).

Lamination géodésique

La génération de terrain sphérique est une opération très simple.

Pour Chaque itération Faire
    Déterminer aléatoirement l'équation d'un plan passant à proximité du centre de la sphère.
    Pour Chaque point de la sphère Faire
        Si le point est "devant" le plan Alors
            Éloigner le point du centre de la sphère
        Sinon
            Rapprocher le point du centre
        Fin Si
    Fin Pour
Fin Pour

Nous pouvons voir que l'algorithme de base est très intuitif et facile à implanter. Or, il n'est pas suffisant d'en effectuer une implantation stricte pour obtenir des résultats satisfaisants. Il faut en effet tenir compte d'un grand nombre de paramètres comme le nombre d'itérations, l'éloignement par rapport au centre, le pas de déplacement des points, etc. Les pages mises en références fournissent un très bon exemple de ce concept.

Problèmes liés au mécanisme de lamination

Nous avons brièvement évoqué précédement le fait que le mécanisme de lamination, s'il n'était pas contrôlé, pouvait donner de mauvais résultats.
Par exemple, étant donné que la lamination consiste à éloigner ou rapprocher les points d'une sphère par rapport au centre, on risque de dilater ou contracter la sphère de départ. Pour cela, on ajoute une phase à la suite des laminations consistant à recalibrer la distance au centre de tous les points grâce à une analyse statistique. Par ailleurs, on utilisera cette analyse pour déterminer les différentes pages de couleurs appliquées au terrain.
D'autre part, il se peut que le relief soit beaucoup trop accidenté. Ceci est encore une fois une conséquence de l'opérateur de lamination. En effet, d'un coté d'un plan, les points sont éloignés, de l'autre, ils sont approchés, donc, on assiste à chaque itération à la création de "falaises locales". Ce phénomêne est de plus accentué par le grand nombre de répétition du processus. Il faut donc, par pur soucis esthétique, lisser le terrain en faisant une moyenne pondérée locale pour chaque point de la sphère.
En bref, voici le résumé des opérations à éffectuer :

Lamination
Lissage
Analyse statistique
Recalibrage
Attribution des couleurs

Résultats

Voici les différents résultats que l'on peut obtenir grâce à l'implantation de l'algorithme décrit ci-dessus.

	20 itérations		50 itérations
	200 itérations		500 itérations

Gestion du niveau de détail

Nous avons quelques contraintes quant au modèle à utiliser pour le rendu :

Il faut modéliser une sphère.
Le modèle doit pouvoir être affiné à volonté (par ajout de sommets, de faces...)
On souhaite pouvoir intercaler des laminations et des affinements. En effet, le temps d'une lamination est proportionnel au nombre de sommets, il est donc préférable de les réaliser avec un petit nombre de sommets, puis affiner le modèle afin d'obtenir un rendu plus fin. On peut alors ajouter quelques laminations afin d'éviter d'obtenir un terrain trop "lisse".
Enfin, le modèle doit permettre de jouer en temps réel sur le niveau de détail, afin d'obtenir soit une bonne qualité d'image, soit une fluidité maximale.

Nous avons choisi de modéliser une sphère par un polyhèdre initial à facettes triangulaires. Ensuite, lorsqu'on souhaite raffiner la sphère, on subdivise chaque face en quatre triangles plus petits. Cette opération peut être réalisée autant de fois qu'on le désire.

Lors de l'insertion de nouveaux sommets (au milieu de chaque segment), ceux-ci sont interpolés par rapport aux extrémités du segment. Le nouveau sommet est placé exactement au milieu du segment, puis il est multiplié par un coefficient calculé de façon à ce que sa distance au centre de la sphère soit la moyenne des distances des deux extrémités (dans la figure ci-dessous, P' est le milieu de MN, et on place P de façon à ce que OP soit la moyenne de OM et ON). interpolons un sommet à partir de ses voisins

La structure de données utilisée conserve la relation d'arborescence existant entre une grande face et les quatre faces plus petites qui la composent. Cette propriété sera utilisée pour l'optimisation de l'affichage (voir plus bas).

Un petit exemple (le nombre de faces affiché est le nombre de faces réellement envoyées à OpenGL - voir plus bas) :

Mouvements de caméra

Les différentes opérations applicables à une caméra sont les suivantes :

look around : la caméra ne se déplace pas et regarde dans toutes les directions
dolly : la caméra se déplace d'avant en arrière
pan : la caméra latéralement et en hauteur
turn around : la caméra tourne autour de sa cible
changement de zoom
changement de focale

Afin de pouvoir effectuer ces opérations, il a fallut utiliser une structure spécifique permettant de placer et d'orienter la caméra dans l'espace. Une caméra a donc été définie à l'aide des champs suivants :

eye : position de la caméra
target : position du point visé par la caméra
dir : vecteur représentant la direction dans laquelle la caméra est orientée
up : vecteur
fov : distance focale de la caméra

Note : le vecteur "right" que l'on peut voir sur la figure est utile mais il n'a pas besoin d'être stocké car il peut être retrouvé à l'aide du produit vectoriel de "dir" et "up".

Les différents mouvements de caméra sont donc définis en appliquant des rotations ou des translations aux vecteurs et points représentant une caméra.
exemple : dans le cas du look around, on effectue une rotation des vecteurs "dir" et "up" ainsi que du point "target" autour du point "eye".

Note : toutes ces opérations sont définies à l'aide de matrices de rotation et de translation

Optimisation du rendu

Nous avons apporté une attention toute particulière à la vitesse d'exécution de notre programme. Voici donc les facteurs limitants (bottlenecks) que nous avons identifiés, et les réponses apportées à chacun des problèmes :

Mémoire réquise pour le stockage des sommets et des faces.
- Utilisation de float au lieu de double pour le stockage des coordonées.
- Stockage des normales et des couleurs aux sommets, mais pas aux faces.
Un grand nombre de faces cachées ou hors de l'écran sont envoyées inutilement au moteur de rendu OpenGL.
- Les faces cachées ne sont pas envoyées à OpenGL (on détermine à partir des normales aux sommets et de la caméra si une facette triangulaire fait face à la caméra ou pas).
- Lors du raffinement du niveau de détail de la sphère, on conserve en mémoire toutes les informations concernant les niveaux précédents. À tout instant, on dispose donc d'une sphère aussi fine ou aussi grossère qu'on le désire. En fonction de la distance à la caméra, on peut donc réduire le nombre de faces affichées.
- Toujours lors du raffinement de la sphère, on stocke pour chaque facette la référence de la facette plus grande dont elle est issue, et inversement, lorsqu'une face est divisée en quatre, on conserve les références de ses "filles". Ainsi, au lieu d'examiner toutes les petites facettes pour les envoyer à OpenGL, on examine une grande facette : si elle est totalement visible, on affiche inconditionnellement toutes ses filles ; si elle est totalement cachée, on ne poursuit pas la récursion ; enfin, si elle est partiellement visible, on examine ses quatre filles.

Enfin, nous avons utilisé diverses techniques OpenGL suggérées par le Red Book ; par exemple les tableaux de sommets, de normales et de couleurs (chaque sommet appartient à six triangles ; au lieu de l'envoyer six fois, on l'envoie la première fois, puis on le référence par son indice).

Conclusion

Le résultat est relativement plaisant à l'oeil, ce qui valide les méthodes choisies. Ensuite, on peut imaginer de nombreux prolongements :

Au lieu de partir d'un nuage de points et de le laminer, se baser sur un modèle de terrain. Pour effectuer l'affichage, on calcule les deux angles délimitant une portion de surface de sphère, et on maille cette portion de surface en générant un nombre arbitraire de points à la surface de la sphère (si on désire 400 points par exemple, on peut faire un maillage de quadrilatères de 20x20). Ensuite, on applique à chaque point une mise à l'échelle afin de le conformer au modèle de terrain.
Optimiser encore un peu le choix des faces envoyées à OpenGL, et vérifier que dans les cas extrêmes (pentes très rudes), l'optimiseur actuel n'est pas mis en défaut.
Permettre de déformer la sphère à la main (enfin, à la souris), par simple drag and drop d'un sommet. Nous implémentons déjà la sélection OpenGL (voir plus bas), ce n'est donc pas compliqué.
Doubler les facettes correspondant à la mer, afin d'avoir une facette pour le fond de l'eau et une autre, transparente, pour la surface.
Implémenter le suivi du relief : la possibilité d'attacher une caméra à la sphère, afin de "marcher" sur la sphère. Nous avons écrit des fonctions permettant de "coller" un point sur la sphère, donc encore une fois il n'y a pas d'obstacle majeur.

Enfin, ce projet nous a permis de mettre en pratique un certain nombre de techniques de programmation liées à OpenGL. Par exemple, nous avons redéveloppé un petit système de gestion d'événements comparable à celui de la Xlib, mais se basant exclusivement sur le dispatch de GLU, donc théoriquement parfaitement portable (quelqu'un a-t-il encore un Winmachin pour vérifier cette phrase ?). Ce système permet à chaque module du programme de définir en quelques lignes les associations entre les touches du clavier (ou les mouvements/clics de souris) et des callbacks à appeler. D'autre part, nous avons implémenté un mécanisme de sélection permettant de mettre en évidence une facette (utilisation de GL_SELECTION, pour le sport).

Références

Spherical Landscapes Hugo Elias
Modelling Fake Planets Paul Bourke