Modélisation des sols par la génération de fractales

La synthèse d’images s’intéresse depuis longtemps à la modélisation des sols, autrement dit à la reproduction et à la représentation visuelle des variations apparemment infinies du terrain naturel grâce à des techniques de modélisation et de rendu. Dès les années soixante, Benoît Mandelbrot a fait le lien entre les formes naturelles qui possèdent un certain niveau d’autosimilarité — telles que les lignes de côte (littoral) — et certaines constructions mathématiques.[1] Depuis, les progrès les plus notables dans ce domaine ont exploité les fractales pour parvenir à une approximation visuelle de terrains à l’aide de procédés stochastiques tels que le mouvement brownien fractionnaire (fractional Brownian motion, fBm). Dans cet article, nous utiliserons plusieurs des techniques de génération de terrain proposées par F. Kenton Musgrave [2] ainsi que le mélange de textures (texture blending) et le nuanceur Shader Model 3.0 pour réaliser une scène en images de synthèse sur des solutions graphiques telles que les jeux de composants de la famille des chipsets Intel® 965 Express pour PC de bureau ou portables.

En premier lieu, nous dresserons la liste des travaux existants dans ce domaine, puis nous aborderons la démarche présidant à notre implémentation, celle-ci exploitant, pour le rendu de la scène en question, tant le processeur (CPU) que le moteur graphique (GPU). Par ailleurs, on trouvera à la fin de cet article un lien vers le code source qui l’accompagne, à utiliser dans les extensions et les implémentations de rendu de terrain.

Un certain nombre de chercheurs se sont penchés sur la génération de terrain (ou « modélisation de terrain ») sous l’angle des fractales, pour « perturber » les surfaces à deux et trois dimensions. Mandelbrot a ainsi obtenu certaines des premières représentations fractales de terrain en comparant l’autosimilarité d’un terrain montagneux à un mouvement brownien, avec un rendu réaliste des cartes d’horizon pour la modélisation d’un cheminement 2D aléatoire. Les travaux ultérieurs de Mandelbrot et Musgrave ont ensuite abouti à des approximations de plus en plus convaincantes, en employant le mouvement brownien fractionnaire en espace tridimensionnel avec bruit de Perlin et multifractales.[2].

Pourtant, les systèmes de génération fractale de terrain à base de bruit tels que proposés par [2] et [4] n’excluent pas la possibilité de réaliser de bonnes approximations de paysages réels, et l’on est effectivement parvenu à des représentations tout à fait agréables à l’œil par d’autres méthodes de calcul. La plus intéressante de celles-ci est la méthode dite de « déplacement du point milieu » (mid-point displacement), avec notamment des algorithmes de subdivision de losanges carrés et de côtés de triangles, un processus de Poisson et une transformée de Fourier rapide.

Si certains de ces systèmes produisent effectivement des scènes réalistes, c’est en revanche la méthode de la synthèse du bruit proposée en référence [2] qui sera utilisée ici, car les calculs correspondants procurent un ensemble intéressant de contrôles du terrain résultant d’un modèle mathématique. Or, si ces propriétés ne fournissent pas nécessairement un mécanisme de contrôle absolu de la scène rendue[5] en le contraignant à se limiter à des propriétés réalistes, elles n’en débouchent pas moins sur de nombreux résultats intéressants, pour la représentation du réel comme pour l’expression artistique. Nous présentons donc ici un jeu d’algorithmes à traitement CPU qui réalise l’équilibre entre ces contrôles et un mélange de textures par paliers réguliers dans le nuanceur de pixels, avec traitement GPU via DirectX* 9 et Shader Model 3.0.

Notre implémentation s’inspire des travaux de Musgrave[2] et reprend trois méthodes extraites de cet ouvrage — fBm simple, fBm hybride et algorithme multifractal à crêtes —, qui s’appuient toutes sur l’algorithme du bruit de Perlin. Le résultat de ces méthodes sert à perturber la direction Z d’un maillage de polygones de taille fixe.

Figure 3-1. Terrain fractal, fBm simple.

Notre implémentation est présentée en figure 3-1. A droite, on remarquera les contrôles utilisés pour régler les propriétés de chaque algorithme fBM, sélectionnées dans la boîte combinée. Notre démonstration est adaptée de la démo BasicHLSL de [7], les paramètres par défaut de l’algorithme étant fixés de manière à mettre en évidence des particularités de terrain intéressantes.

Paramètres

(H) indice de Hurst – Dans la littérature informatique, il classe le fBm et définit la dimension fractale.

(Lacunarity) – La lacunarité définit les vides entre fréquences successives.

(Octaves) – Elles définissent le nombre de fréquences et le niveau de détail (Level of Detail) de la scène.

(Offset) – C’est le décalage par rapport à l’élévation la plus basse. Il détermine la « multifractalité »[2].

(Gain) – Il définit l’amplitude de la fréquence.

Les pixels sont échantillonnés à partir d’images de textures et interpolés par une spline d’Hermite {0..1} sur des régions d’existence basées sur l’élévation transmise à la fonction de nuançage des pixels. C’est l’opération de mélange multitexture proposée en [3] qui a été retenue aux dépens d’opérations de mélange de textures à fonction fixe plus anciennes, implémentées sans mappe de mélange. Bien qu’une telle mappe produise un mélange plus fin et plus réaliste de la texture de chaque région de surface multitexturée (cf. [3]), la méthode retenue assure un mélange raisonnable pour des scènes d’altitude plus élevée, qui manquent inévitablement d’un niveau de détail plus for, en raison de la hauteur du point de vue que l’on peut avoir dans un simulateur de vol. Chaque zone d’élévation est séparée par des constantes qui simulent le passage graduel entre zones sableuses, herbeuses, rocheuses et neigeuses pour ainsi créer un effet de mélange sur l’ensemble des élévations, les zones limitrophes adoptant la teinte des pixels d’échantillons de cette zone (méthode suggérée par [9]) dans le fichier des effets du nuanceur.

Il reste toute une série de problèmes intéressants à résoudre dans le domaine de la génération de terrain fractal. Les applications de la modélisation automatique de paysage sont confrontées à des décisions liées aux conflits entre des éléments du gameplay dans le scénario ou à des caractéristiques irréalistes que produit le fBm et d’autres types de modélisation fractionnaire de terrain.

En outre, la majorité des méthodes de génération de terrain sont lourdes en calcul et n’interviennent pas en temps réel. Bien que certains algorithmes fractals se prêtent facilement au parallélisme de traitement, le résultat n’en est pas moins chronophage, comme c’est le cas de ceux de Mandelbrot [10], ou bien ils réduisent le nombre d’itérations inspectées. L’un de ces problèmes difficiles mais intéressants est celui du traitement parallèle d’une implémentation en mouvement brownien fractionnaire, car il s’agit d’une opération globale, qui prend en compte plusieurs domaines de la variable. On pourrait scinder le traitement par rangée ou colonne en couvrant les valeurs Z d’une surface, voire par quadrants pour le traitement, avec des résultats qui biaisent les contrôle des paramètres de l’algorithme et qui rendent plus visibles les régions de terrain disjointes.

C’est l’interdépendance aux précédentes valeurs par rapport au calcul qui instaure ces mêmes propriétés demandées au fBm, introduites par l’intermédiaire de l’indice de Hurst, de la lacunarité et de l’octave. Par conséquent, il devient difficile de scinder les calculs entre unités physiques de traitement. Les recherches sur ce concept menées par Mandelbrot [8] montrent cependant qu’il peut exister une solution au problème de parallélisation, à savoir par troncature du fBm. En revanche, il peut en résulter un certain niveau d’erreurs dans le calcul, mais, si la scène obtenue grâce au processus de rendu est esthétiquement satisfaisante, une certaine imprécision dans l’opération être acceptable. Nous souhaiterions déterminer l’effet d’un algorithme fBm parallélisé sur un rendu de terrain et analyser ses performances pour les processeurs multicœurs avec un code optimisé à cet effet.

1. [Mandelbrot67] B. Mandelbrot, « How Long Is the Coast of Britain? Statistical Self-Similarity and Fractional Dimension », Science, nouvelle série, vol. 156, n° 3775, pages 636-638, 5 mai 1967.
2. [EMPPW94] Ebert, Musgrave, Peachey, Perlin, Worley, Texturing and Modeling: A Procedural Approach, Academic Press Inc., 1994, chapitres 7-9 pour Musgrave, chapitre 6 pour Perlin.
3. [Luna06] Frank Luna, Introduction to 3D Game Programming with DirectX 9.0c: A Shader Approach, Wordware Publishing Inc., chapitre 11.
4. [MKM89] Musgrave, Kolb, Mace, « The Synthesis and Rendering of Eroded Fractal Terrains », Proceedings of SIGGRAPH’89, ACM Computer Graphics, Vol 23, n° 3, juillet 1989.
5. [SS05] Stachniak, Stuerzlinger, « An Algorithm for Automated Fractal Terrain Deformation », Computer Graphics and Artificial Intelligence, Ed. D Plemenos, mai 2005 (ISBN 291425607-8, 64-76).
6. [HR06] Hardy, Roberts. Blend Maps: Enhanced Terrain Texturing. Proceedings of SAICSIT 2006. pp 61-70.
7. [MSSDK07] SDK de Microsoft DirectX (novembre 2007) http://www.microsoft.com/downloads/details.aspx?familyid=4b78a58a-e672-4b83-a28e-72b5e93bd60a&displaylang=en.
8. [Mandelbrot07] B. Mandelbrot, communication personnelle par e-mail, novembre 2007.
9. Hayes07] Hayes, Jeremy (jeremy.hayes@intel.com), décembre 2007.
10. [Intel05] « Using SSE3 Technology in Algorithms with Complex Arithmetic », 23 février 2005 (http://software.intel.com/en-us/articles/using-sse3-technology-in-algorithms-with-complex-arithmetic).

Jeff Freeman est ingénieur logiciel au Software & Solutions Group d’Intel, où, au sein de l’équipe Client Scale Enabling, il est chargé des solutions graphiques intégrées. Il possède une licence (B.S.) en informatique du Rensselaer Polytechnic Institute. On peut lui écrire à l’adresse jeffrey.m.freeman@intel.com.

Steve Pitzel (steve.pitzel@intel.com) pour les illustrations/textures.

Jeremy Hayes (jeremy.hayes@intel.com) pour ses conseils en matière de nuançage de terrain.

Cet article est également disponible en téléchargement [PDF de 283 ko]

Fichier <IntegratedGFX_FractalTerrain_Demo.zip> [ZIP de 4,9 Mo]