! Update ! :
L'article ayant commencé sur ce forum, le texte complet et mis à jour avec le code source est disponible sur ma page web :
 
En Français :
Moteur de terrain en voxel et C++ - première page (LeGreg)
Moteur de terrain en voxel et C++ - deuxième page (LeGreg)
et en Anglais :
Voxel terrain engine in C++ - first part (LeGreg)
Voxel terrain engine in C++ - second part (LeGreg)
 
Merci de vous y réferer. Je garde ce thread ouvert pour raisons historiques pour ceux qui veulent s'y référer.
 
-------------------------------------
 
 
Chose promis, première partie du tutoriel sur les terrains en voxel. La suite avec le source code et l'exécutable dans pas longtemps.
 
Qu'est-ce qu'un voxel ?
 
Commençons par le commencement, qu'est-ce qu'un voxel ? Le mot voxel est la contraction de "volume element". En fait pas vraiment mais c'est pour que le nom sonne pareil que pixel (picture element). Il y a plusieurs sortes de voxels. Celui que nous ne considèrerons pas ici est l'unité indivisible d'un objet volumétrique. C'est l'équivalent pour les objets en 3D du pixel pour l'image en 2D. Un bitmap tridimensionnel à la place des vecteurs habituels (utilisés dans les objets polygonaux). Ce sont les briques de legos. Les petites briques constituent un objet plus grand, de la même façon que les pixels forment une grande image.
 
Mais notre moteur de terrain en voxel est d'un autre genre. Celui qui a été mis en oeuvre dans des jeux classiques comme Outcast ou Comanche. Le moteur de terrain en voxel est un moteur 2,5D il lui manque quelques degrés de liberté par rapport à un moteur 3D classique. Il a les mêmes degrés de liberté qu'un moteur de raycasting (comme dans Doom). Ils sont si proches qu'en fait on pourrait utiliser la méthode du raycasting pour visualiser notre terrain en voxel. Mais ce n'est pas la méthode utilisée ici, en fait on va plutot faire une rasterisation avec quelques astuces pour que ce soit rapide. Pourquoi ça s'appelle aussi voxel ? Simplement parce que notre terrain est également constitué de petites briques que l'on extirpe d'une image en 2D et que l'on étire verticalement. C'est bien un voxel, juste une définition un peu restrictive par rapport la première.
 
Introduction
 
J'avais débuté le projet de rendre un moteur de terrain similaire aux screenshots de Outcast que j'avais découvert en 1999 en même temps que tout le monde. C'était un projet assez important pour quelqu'un qui débutait et qui ne connaissait rien au C++ ou à la programmation 3D mais les maths semblaient largement faisables. La version détaillée ici ne change que peu de choses par rapport au design original, j'ai juste converti le projet pour tourner en Win32 plutot qu'en direct draw (d'ailleurs j'utilise beaucoup de notations Win32 et je m'en excuse auprès de ceux qui y sont allergiques. Bon on peut passer à autre chose maintenant..). Les algos sont indépendants de la plateforme utilisée et peuvent être retranscrits facilement.
 
Voxel terrain engine in C++ - algorithms and source code
 
Ci dessus c'est la version actuelle et ci dessous c'est la version de l'époque avec du "progammer art" du plus bel effet (et un pentium peu performant et sous utilisé).
 
Voxel terrain engine in C++ - algorithms and source code
 
Pourquoi auriez vous besoin de programmer un moteur de rendu de terrain par voxel à l'heure actuelle ? Réponse courte, vous n'en avez pas besoin. Si vous possédez une carte accélératrice 3D comme tout le monde sur PC à l'heure actuelle, vous pouvez rendre des terrains super détaillés avec du multitexturing, de l'occlusion avec un z-buffer, des langages de shaders puissant et le travail est déjà maché (clipping, rasterisation, transformation, etc.). C'est probablement plus rapide que tout ce que vous pouvez espérer faire en software. Tout ce qui suit est un simple exercice pour le fun : il y a de meilleurs outils servez-vous en.
 
Voilà pour l'avertissement, on peut commencer à s'amuser.  
 
Au commencement il y avait la height map
 
Le height map ou carte d'élévation est la façon la plus simple et la plus compact de représenter un terrain quelconque. Cette carte associe implicitement une élévation fixe à un jeu de coordonnée 2D. On ne peut pas représenter toutes sortes de terrain de cette manière; aucun moyen d'obtenir une arche, une grotte ou toute formation de terrain qui viole la règle d'"une seule élévation par position sur la carte". Si vous avez besoin de choses plus complexes, passez votre chemin, notre moteur de voxel n'est pas pour vous. Vous aurez problablement besoin d'un moteur un peu plus générique comme un moteur polygonal (et de l'accélération 3D).
 
Voxel terrain engine in C++ - algorithms and source code
L'Utah est trop complexe pour notre moteur de terrain par voxel ( photos et images copyright Grégory Massal)
 
Créer une carte d'élévation (CE) est un peu complexe, bien entendu il y a des données de terrain réélles disponibles gratuitement ou pour un peu d'argent, mais que se passe-t-il si l'on veut rendre une région qui n'existe que dans notre imagination ? Demander à un artiste de faire un simple terrain avec des failles, montagnes, crevasses, plaines, peut être douloureux. Heureusement il y a des outils disponibles qui vous permettent de générer des terrains inédits de manière aléatoire. Pour cette article j'ai utilisé la version gratuite de World Machine et Terragen. Avec un peu d'huile de coude ou l'aide de scripts préexistants  vous pouvez générer des zones suffisament réalistes (allez voir leurs galleries pour plus d'infos)
 
À chaque position sur la carte, on a une élévation encodée sous forme d'un entier de 8 bits. Les valeurs de 0 à 255 peuvent sembler ne pas être assez pour votre vision initiale mais on peut bien entendu faire varier l'intervalle d'élévations représentées par ces nombres sur 8 bits (compression), et si ça n'est vraiment pas assez il reste la possibilité d'éncoder la hauteur du terrain sous forme d'entiers sur 16 bits, ou encore des nombres à virgule flottante sur 32 bits. C'est une décision à prendre en fonction de vos données originales et n'oubliez pas qu'il y a des façons de compresser qui réduiront votre encombrement disque/mémoire. Je ne rentre pas trop dans les détails. On continue.
 
Voxel terrain engine in C++ - algorithms and source code
 
Assurez vous que la carte que vous avez créé utilise le plein intervalle de nombres de de 0 à 255, c'est suffisamment petit pour que vous n'ayez pas envie de perdre de précieux bits d'infromation dans le processus. Pour les besoins de ce moteur je me suis aussi arrangé pour que ma carte soit répétable ("tileable" ). Cela veut dire que si je dépasse la limite de ma carte je veux pouvoir me retrouver à l'origine de ma carte sur l'autre bord sans tomber d'une falaise, pour cela il faut que le bord droit soit une parfaite copie du bord gauche et le bord haut une parfaite copie du bord bas. Je ne rentre pas trop dans les détails ici mais il y a plusieurs moyen de s'assurer de cela, la première est de prendre une carte non répétable et d'en faire une copie mirroir de chaque coté (carte finale 4 fois plus grande). De cette manière chaque bord est exactement égal à celui qui lui fait face puisque c'est sa copie conforme. L'inconvénient c'est que l'info est hautement redondante de cette façon puisque chaque quadrant de la carte est une copie de tous les autres. Une autre solution est de prendre juste une bande sur les bords haut et gauche, d'en faire une copie en fondant le résultat sur le coté droit et bas. Utiliser un gradient progressif comme terme de blending comme ça les images seront parfaitement intégrée l'une dans l'autre (en supposant que la différence ne soit pas trop marquée) et les bords se correspondront à cent pour cent également. Pour cette article, j'ai tout fait à la main et c'est pas exactement parfait mais avec un peu de pratique vous pouvez avoir un résultat où vous devrez vraiment bien chercher pour y trouver des défauts. Il y a également des algorithmes complexes qui essaient de préserver les caractéristiques de l'image en en générant une entièrement nouvelle qui minimise les artefacts liés à la répétitions mais c'est un peu trop lourd pour ce petit projet.
 
Le deuxième jour vint la visibilité
 
Avant de tracer tous les éléments constitutifs de notre terrain vous devrez déterminer ce qui est visible et ce qui ne l'est pas. C'est à la fois un problème de performance et de correction. Si un élément de terrain qui est partiellement visible ou totalement caché est tracé, alors il y a un problème de correction. Si vous demandez à tracer un élément de terrain qui est situé derrière votre caméra ou dehors de votre champ de vision alors vous avez dépensé de précieux cycles de votre processeur pour rien.
 
Voxel terrain engine in C++ - algorithms and source code
 
L'image ci dessus représente ce que vous pouvez voir depuis un point de vue donné (en rouge), la plupart des zones noires seront en dehors de votre écran et quelques parties qui peuvent être sur votre écran à l'intérieur de votre champ de vision (frustum) sont en fait caché par des parties du terrain qui se trouvent en face d'elles. Ce n'est pas réaliste en temps de calcul de prendre chaque petit élément de notre carte et déterminer s'ils sont clippés en dehors du frustum. À la place on va utiliser une représentation hiérarchique de notre terrain à deux niveau. Un niveau détaillé (detailed level) et un niveau grossier (coarse level). Je considèrerai les pixels du niveau détaillé que lorsque j'aurai déterminé au niveau grossier qu'ils sont totalement visibles ou partiellement visibles (ambigu).
 
On pourrait avoir plus de niveaux mais le bénéfice de l'ajout d'un niveau, n'est plus aussi intéressant quand on a déjà une structure hiérarchique en place. Bien entendu, le niveau grossier doit être suffisamment petit pour ne pas avoir à faire tout le travail de clipping au niveau le plus bas (limiter le cas ambigu) et doit être suffisamment grand pour que tout clipping d'une zone grossière apporte un gain en performance suffisant. J'ai opté pour des grandes zones de 256x256 éléments de terrain dont je peux déterminer rapidement la visibilité.  
 
Voxel terrain engine in C++ - algorithms and source code
 
En rouge pur, vous avez les zones qui sont à 100% à l'intérieur du frustum (le frustum est le cone de visibilité, ou encore la zone délimitée par nos deux lignes en vert où se trouve la partie potentiellement visible de notre monde pour une position et rotation donnée). En rose ce sont les zones qui ne sont pas entièrement à l'intérieur du frustum mais que l'on doit inclure parce que certains de leurs éléments seront visibles. Dans le cas le pire cela veut dire que seul un élément de terrain peut être visible sur les 65536 que constitue notre zone. C'est mal mais on est obligé de vivre avec à moins d'aller pour une grille de départ moins grossière.
 
Voxel terrain engine in C++ - algorithms and source code
 
Le clipping est une opération assez simple, vous avez à tester chaque angle d'un quadrangle qui délimite une zone contre les trois droites que j'ai appelé "left, right et near" (gauche droite proche). J'ai mis la droite "near" à une courte distance de notre position de caméra, parce que je devrai diviser plus tard par z (la distance le long de l'axe de vue) et je veux éviter les divisions par zéro. Remarquez que plus on pousse notre droite "near" loin, meilleures seront les performances mais le risque est d'augmenter les artefacts de clipping.
 
Avant de clipper il faut déterminer les équations de chacune de ces droites. Trouver l'équation est équivalent à chercher les normales à chacune des droites dans le plan 2D. Les normales sont définies en terme de fov et rho, les deux angles caractéristiques de notre configuration.
 
Voxel terrain engine in C++ - algorithms and source code
 
Si je pose x1, y1, x2, y2 les quatre coordonnées de notre boite d'encadrement (bounding box) aligné sur les axes. Alors nous utiliserons le code suivant pour clipper selon le plan proche :
 

 
On répète l'opération pour chaque ligne (plan). Nous avons travaillé uniquement en 2D jusqu'ici. Nous n'aborderons la troisième dimension que quand on commencera à projeter des choses sur notre écran (temporairement avant de revenir à la 2D de notre écran).

Peintre inversé
 
Aparté.. L'algorithme du peintre et une méthode très simple à comprendre pour tracer des éléments 3D qui se dissimulent les uns les autres. Cela consiste à trier tous les éléments du monde de l'arrière vers l'avant. Chaque nouvel élément tracé ne se soucie pas de ce qui a été tracé auparavant et les nouveaux pixels touchés par notre objet remplaceront les pixels précédents. La garantie que cela soit correct tient dans le tri initial parce que tout nouvel objet est garanti être situé devant tous les objets tracés précédemment. Un inconvénient majeur de cet algorithme c'est qu'il est très couteux parce que nous devons tracer tout le monde meme les objets qui pourraient être cachés par d'autres. Ce phénomène est appelé overdraw (je ne sais pas s'il y a un équivalent français). Il y a de rares occasions où l'overdraw est bon c'est quand on trace des objets transparents, dans ce cas il ne s'agit pas à proprement parler d'overdraw puisque les objets ne sont pas dissimulés. Un autre inconvénient qui le rend peu pratique dans le monde réel c'est que même si l'overdraw était gratuit il n'est pas toujours possible de trier de l'arrière vers l'avant. Le problème n'est pas soluble de manière simple dans le cas général (il peut être nécessaire de subdiviser des polygones en cours de triage pour une précision au pixel). Fin de l'aparté.
 
Nous ne voulons pas d'overdraw, en fait on peut avoir zéro overdraw sans rien sacrifier d'autre. Ce que j'appelle peintre inversé est un jeu de mot sur l'algo du peintre ci dessus parce que nous faisons tout à l'envers. Tout d'abord nous trions tous nos éléments de l'avant vers l'arrière. Ensuite quand on touche un pixel on s'assure tout d'abord que rien n'a été tracé sur ce pixel précédemment. Comme c'est trié de l'avant vers l'arrière tout objet précédemment sur ce pixel dissimule l'objet courant, donc on n'a pas à écrire notre couleur dans notre buffer.  
 
Trier c'est facile dans notre cas, on a des gros blocs de données rectangulaires qui ne s'intersectent pas. Au début de chaque nouveau rendu, je considère toutes les zones autour de la caméra, je les place dans une structure triée de l'avant vers l'arrière (une std::map ferait l'affaire). Ensuite je parcours la structure dans l'ordre et je les trace élément par élément encore une fois en utilisant un ordre particulier pour que l'affichage soit correct au final.
 
Voxel terrain engine in C++ - algorithms and source code
 
Ce que je veux dire par ordre correct, c'est que l'on a un rectangle de 256x256 éléments que je ne peux pas tracer dans n'importe quel ordre. Celui utilisé par le stockage a une chance sur quatre d'être bon (cela dépend de la vue !), mais au final ce n'est pas bien dur, nous avons quatre cas possibles :
 
Voxel terrain engine in C++ - algorithms and source code
 
La flèche indique dans quelle direction l'observateur regarde la zone concernée. Vous pouvez vous demander si le fait de faire un déplacement de chaque élément ne va pas bouleverser cet ordre prédéfini. Ce serait le cas si le déplacement pouvait être arbitraire (avec des problèmes de continuité) mais ici le déplacement ne se fait que dans une direction constante et dans un axe qui ne change pas la relation d'ordre par rapport à la caméra et c'est tout ce qui importe.  
 
Si vous êtes familier avec l'accélération 3D, vous connaissez probablement l'algorithme du Z-Buffer. Cet algorithme assure que si vous tracez votre géométrie dans un ordre arbitraire indépendemment de votre vue le z-buffer se chargera de déterminer les pixels visibles et les pixels cachés. Cela pourrait marcher pour notre terrain bien entendu mais on n'a pas besoin de ça. Le ZBuffer a un surcout. Le cout est la consultation du buffer, son écriture et le fait que si vous ne triez pas comme on le fait alors le cas le pire est aussi mauvais en terme d'overdraw que l'algorithme du peintre que l'on a abordé plus haut (si par accident vous triez toute de l'arrière vers l'avant). De plus vous êtes limité par la résolution de votre Zbuffer et deux éléments très proches ne peuvent pas être correctement tracés. Sans compter que l'on doit allouer un zbuffer de taille égale à la taille du tampon de couleur multiplié par le supersampling (suréchantillonnage pour l'antialiasing). On peut accélerer les calculs d'occlusion avec une structure de Z hiérarchique mais encore une fois cela n'est vraiment pas nécessaire avec tout ce que l'on a fait jusqu'à présent et pour la suite. Meme dans la situation où j'ai besoin de l'information du ZBUffer pour un rendu ultérieur où j'utilise une méthode plus classique pour afficher des objets sur mon terrain (méthode dite de frankenrender), alors je peux générer l'information de Z de manière optimale une fois par pixel, exactement de la même façon dont je génére l'information de couleur. Mais si l'on reste dans les voxels, on n'a pas besoin de cette information de Z pour traiter l'occlusion.
 
Y-Buffer
 
Comment déterminer de manière optimale si un pixel a déjà été tracé ? De manière générale, on peut s'en sortir en stockant un seul bit par pixel qui indique si le pixel est "on" ou "off". En groupant ces bits par groupes de données sur 32 bits ou 64 bits (tiles de 32 ou 64 pixels) on peut rapidement éliminer des parties entières du rendu. Mais on peut faire mieux que ça encore parce que l'on se contente de tracer une série de lames verticales alignées sur l'écran. J'ai appelé cet algorithme YBuffer en référence au ZBuffer plus général décrit plus haut. On n'a qu'à maintenir une simple ligne de données entières qui indiqueront pour chaque colonne verticale de pixel, combien de ces pixels ont été tracés par notre moteur.
 
Comment cela fonctionne ? Chaque lame de terrain, occupe la zone située sous son sommet vertical. La seule condition selon laquelle ça ne descend pas jusqu'èn bas de l'écran, c'est si cette lame de terrain est dissimulée tout ou partie par un tracé précédent sur la même colonne (meme X). Cela signifie que quand on trace une lame à la position X,Y, alors on la compare au Y stocké précédemment pour cette colonne X. Si la précédente lame était à un Y supérieur au Y courant, alors on passe le tracé (occlusion) ou sinon on trace une couleur simple depuis le Y courant jusqu'au niveau du Y précédent. De cette manière on trace chaque pixel seulement une fois et la visibilité de chaque pixel est correcte grâce à toutes les dispositions prises précédemment.
 
Voxel terrain engine in C++ - algorithms and source code
 
Niveau de détail
 
Parce que l'on utilise une perspective conique, les zones qui sont le plus loin de notre point de vue vont couvrir une zone assez petite sur l'écran. Il n'y a pas besoin de passer à travers une carte de 65536 éléments quand seul un ou deux pixels seront au final tracé.  
 
Nous utiliserons donc un système assez basique de niveau de détail (LOD). Ce système s'appelle mip mapping (multum in parvo, beaucoup dans peu). À la place de considérer les 256x256, nous allons estimer grossièrement combien d'espace cette zone peut couvrir horizontalement sur l'ecran, et on va choisir la plus petite représentation qui permet de mettre encore une fois grossièrement un élément par pixel horizontal (on peut aussi choisir de couvrir plusieurs pixels ce qui accélère pas mal les calculs mais pour une qualité moindre). Donc si le terrain couvre 16 pixel sur l'écran horizontalement, on décide d'utiliser une version réduite de 16x16. Chaque représentation de NxN est une version préfiltrée de la représentation plus large de 2Nx2N.  
 
Cela signifie que pour chaque zone de terrain de 256x256, nous avons 8 autres représentations possibles de plus petite taille (128x128, 64x64, 32x32 etc.). On filtre à la fois l'info de couleur (albedo) et l'élévation.
 
Mapping de texture
 
Habituellement, texturer un objet en 3D est un peu complexe, parce que l'on a de la correction de perspective à appliquer aux UV dans l'espace de l'écran, du filtrage à faire etc. Maintenant on est plutot chanceux parce qu'à cause de notre algorithme on peut travailler dans l'espace de la texture directement sans devoir faire d'interpolation des données de texture autrement que de manière linéaire. On traverse notre zone de 256x256 avec un pas fixe et on ne prend aucun raccourci pour projeter l'élément sur l'écran. À chaque élément de terrain, on lit une nouvelle élévation de notre carte d'élévation, et une simple couleur diffuse de notre carte de diffusion et la position sur l'écran sera calculée de manière précise par notre processus de projection.
 
Résumé
 
Voxel terrain engine in C++ - algorithms and source code
 
Voilà ce qui sort de notre moteur jusqu'ici. Nous avons ajouté en prime un peu de perspective aérienne (teinte bleue qui croit avec la distance), je traiterai ça dans la deuxième partie. Nous avons toujours une faible qualité parce que j'utilise une selection de niveau de détail qui fait couvrir en moyenne deux pixels horizontalement à chaque élément de terrain.
 
Maintenant, que faut-il faire pour améliorer la qualité ? En premier on peut faire que chaque élément couvre un pixel ou moins horizontalement (malheureusement on ne peut pas faire de détermination très fine pour le détail vertical, parce qu'il est plus complexe de déterminer en avance de combien il sera étendu sur l'écran). Ensuite on peut utiliser du suréchantillonnage (supersampling) et tracer un ciel un peu moins plat. Je rentrerai dans ce genre de détail dans la deuxième partie. À suivre.
 
Liens:
World machine http://www.world-machine.com/
Terragen http://www.planetside.co.uk/terragen/

Un peu en retard la deuxième partie de l'article.
 
Suréchantillonnage horizontal : la force brute
 
Faire du suréchantillonnage (supersampling ou oversampling en anglais) est facile. Il s'agit de multiplier la définition du rendu par deux (ou quatre ou plus). Maintenant ce que cela signifie c'est que deux fois plus de mémoire est occupée par les différents buffers, et bien entendu il faut tracer deux fois plus de pixels, ou multiplie les besoins en calcul et en bande passante, etc. Tout n'est pas multiplié par deux, on ne choisit pas un niveau de détail plus fin parce qu'à la fin ces échantillons vont être compressés en un seul pixel à l'écran. Cela veut dire que, toutes choses égales par ailleurs, les calculs avant l'écriture dans le frame buffer seront équivalents à la version non suréchantillonnée. Bien entendu on pourrait choisir un niveau de détail plus fin pour améliorer la qualité encore plus mais cela ne sera pas nécessaire.
 
Par exemple, lors d'un de mes tests avec tout les effets activés par ailleurs aux niveaux les plus haut, j'ai activé par dessus le suréchantillonnage 4x (horizontal) et j'ai vu une augmentation de 50% des cycles de rendu d'une frame. Nous n'avons heureusement pas vu une augmentation par quatre des coûts tout simplement parce que l'on ne passe pas cent pour cent de notre temps à tracer les pixels finaux et que les autres coûts comme on a expliqué plus haut n'ont pas augmenté.
 
La passe finale est une passe de résolution, en utilisant un filtre boite : on ajoute les quatre échantillons et on diviser la couleur résultante par quatre. C'est suffisammment bon pour l'instant. Il y a des filtres meilleurs qui minimisent les effets d'escaliers (roping effect), en résolvant plus de quatre samples par pixels, mais je ne rentre pas trop dans les détails ici (vous pouvez aller voir ma série d'articles sur le raytracer pour avoir une idée d'un meilleur filtre).
 
Suréchantillonnage vertical : la version rapide
 
L'avantage d'un filtre séparable c'est que vous pouvez filtrer selon X et selon Y séparément, en fait grâce à cela on peut appliquer deux méthodes différentes pour l'antialiasing selon l'axe des X et l'axe des Y. L'axe des X a eu droit à la force brute, l'axe des Y sera un peu plus efficace.
 
On va tirer encore une fois profit de l'algorithme de Y-Buffer décrit dans la première partie. À la place de stocker la valeur de Y entière dans le Y buffer, on va stocker des fractions de pixels. Donc si l'on touche à un pixel, on peut déterminer grâce à la valeur fractionnelle de Y, quelle portion du pixel est couverte.
 
Voxel terrain engine in C++ - algorithms and source code
 
Le pixel final sera écrit seulement quand les quatre sous-échantilons (dans ce cas) seront couvert. On prendra là encore la valeur de couleur moyenne. C'est un processus incrémental, nul besoin comme pour l'axe des X de faire une passe supplémentaire à la fin pour la résolution. C'est garanti de marcher à cent pour cent, parce que la variation des Y sur une simple colonne de pixels est monotone.
 
Le coût n'est pas élevé, pour quatre sous-échantillons horizontaux par ligne et tout le reste activé par ailleurs, on a au final 15% de cycles en plus que le rendu normal.
 
Interpolation linéaire
 
Initialement nos lames de terrain étaient de simples blocs rectangulaires alignés dans l'espace de l'écran. Mais pour avoir un effet de transition plus doux entre les lames, nous avons besoin d'interpoler entre deux éléments de terrain. Ce que j'ai utilisé ici est une interpolation linéaire, ce qui nous donne un aspect polygonal à distance. J'interpole uniquement entre les deux hauteurs, mais on peut bien entendu imaginer interpoler la couleur diffuse ou d'autres attributs.
 
Voxel terrain engine in C++ - algorithms and source code
 
Brouillard et plan d'eau
 
Dans le monde réel, à grande distance toute semble être légèrement teinté en bleu et désaturé. C'est l'effet que les peintres appellent perspective aérienne. C'est causé par les particules et les molécules dans l'air qui modifient les couleurs qui parviennent jusqu'à votre oeil. Si vous regardez la photo du paysage de l'Utah présenté plus haut, vous pouvez voir que les montagnes les plus lointaines ont l'air bleu, tout en sachant très bien que ce n'est pas leur "vraie" couleur. C'est aussi vrai pour le ciel, il a l'air bleu quand on sait que l'espace derrière lui est vraiment noir. La couleur que l'on voit est donc réfléchie par les molécules de l'air entre ici et là bas.
 
Il y a plusieurs façons d'implémenter cela dans notre code, on va choisir la plus facile. Il suffit de prendre le Z du point de vue de l'oeil et de le diviser par un Z maximal et interpoler linéairement entre la vraie couleur du terrain et une couleur de brouillard qui est bleue insaturée. Ce n'est pas du tout correct physiquement mais ça rend suffisamment bien pour ce que l'on veut faire et surtout c'est rapide.
 
Nous avons également des aires de terrain couvertes d'eau. On choisit de représenter ainsi les aires de terrain qui sont sous un certain niveau prédéfini. L'eau vu sous cet angle devrait principalement refléter l'environnement mais on va oublier ça, je vais juste la faire réfléchir la couleur du ciel et la combiner avec la couleur du terrain qui se trouve sous le niveau de l'eau. Si cela vous intéresses de savoir comment l'eau et autres matériaux transparents reflètent la lumière, vous pouvez aller lire mon article sur le raytracing, tout y est expliqué (Fresnel, Descartes, etc.).
 
Dessin du ciel
 
La modélisation du ciel est assez complexe. Dans les grandes lignes vous avez deux types de dispersion de lumière (Mie et Rayleigh), Rayleigh disperse principalement les ondes bleues et ceci dans toutes les directions, Mie disperse les ondes en avant et en arrière, créant un halo blanc autour du soleil dont la taille dépend de la concentration de particules/molécules dans l'air. La lumière qui traverse plusieurs couches de dispersions devient elle-même teintée et affecte les particules et le sol en les éclairant. La lumière qui parvient à votre oeil a donc pu être réflechi plusieurs fois depuis son départ depuis le soleil.
 
Pour résumer : le ciel a l'air bleu, saturé quand vous regardez à la verticale et de plus en plus insaturé, quelquefois blanc ou grisâtre quand vous regardez horizontalement. Il a l'air plus blanc également autour du soleil.
 
Voxel terrain engine in C++ - algorithms and source code
 
C'est vrai de jour et pour un ciel dégagé sans nuage, brouillard ou autres. Lors du crépuscule ou l'aube, la lumière du soleil a traversé tellement de couches d'air qu'elle a perdu la plupart de son bleu et commence à teinter tout ce qu'elle touche en orange ou en rouge. Pendant la journée la lumière du soleil est presque blance ou jaune très claire, et ce qui n'est pas éclairé directement par le soleil est presque bleu parce que la principale source de lumière secondaire est le ciel bleu.
 
Plutot que d'intégrer le modèle complexe (voir les liens), on va se contenter de dessiner le ciel de manière explicite. On va choisir un bleu saturé (1) et un bleu insaturé (2) faire un dégradé du haut vers le bas de saturé à insaturé (l'horizon et ce qui se trouve en dessous étant coloré en bleu numéro 2). Le soleil n'est pas physiquement présent à l'image mais je garde trace de sa position et en particulier de son angle. Le bleu saturé est mélangé avec plus ou moins de blanc selon que l'on s'approche de l'angle du soleil. (cosinus de l'angle de vue moins l'angle du soleil à la puissance N).
 
Voxel terrain engine in C++ - algorithms and source code
 
Conclusion et travaux dérivés
 
Voici, l'image finale de ce tutorial. Nous avons démarré avec une carte d'élévation et une carte d'albedo (diffusion) que nous avons découpé en petits morceaux pour pouvoir facilement déterminer les parties de terrain non visibles. Nous utilisons une détection rapide d'occlusion qui nous permet de mettre à jour un pixel en une seule fois et nous donne de l'antialiasing vertical en bonus. L'arrière plan est un simple modèle procédural du ciel et du soleil.
 
Voxel terrain engine in C++ - algorithms and source code
 
Qu'est-ce qu'il reste à améliorer dans ce moteur ?
 
Pour commencer à ce niveau de qualité ce n'est pas forcément rapide et presque non interactif (3 images par secondes sur ma machine en extra haute quality, un peu plus de 20 images par secondes dans la version basse qualité). Il y a définitivement de la marge pour gagner en performance. En utilisant des algorithmes encore plus efficaces, en faisant un profil du code pour éliminer les failles plus ou moins visibles, voire retravailler certaines des parties critiques en assembleur (en utilisant les dernières extensions du CPU).
 
Aussi le terrain est entièrement chargé en mémoire au début ce qui est OK pour une simple démo technique. Mais ce qui se passerait si l'on voulait rendre une région entière avec un fort niveau de détail avec des gigaoctets de data c'est que l'on devrait se passer de tout charger. Par exemple pousser l'algorithme de LOD pour ne plus charger que les parties qui sont visibles et au niveau de détail le plus bas pour diminuer l'empreinte mémoire. Si l'on avait conservé la formule utilisée pour construire le terrain il est même envisageable de construire le terrain au fur et à mesure de l'avancée et donc ne plus avoir à monopoliser du disque pour ça (bien entendu il faut que la formule utilisée pour reconstruire le terrain soit suffisamment simple pour pouvoir y gagner quelque chose).
 
L'éclairage et l'ombrage sont statiques parce qu'ils sont fait durant la phase de création par un renderer offline. Celui-ci est de très bonne qualité mais n'est pas forcément très rapide. Nous pourrions abandonner un peu de cette qualité pour faire un environnement où la lumière serait dynamique et les conditions de lumière mise à jour en temps réel. Nous pourrions également implémenter un modèle plus complexe du ciel, être capable d'avoir un ciel plus réaliste à des heures de la journée différentes ou avec des saisons, des nuages procéduraux ou préfaits etc.
 
Je finirai cet article sur cette touche, savoir que les possibilités d'améliorations sont innombrables et peuvent être implémentés comme un exercice par les lecteurs s'ils veulent découvrir plus.
 
Liens:
Un modèle analytique du ciel : http://www.cs.utah.edu/vissim/papers/sunsky/

Bravo pour ce tuto

tiens, j'en avais fait un y'a longtemps, a partir d'un truc qui trainait sur le net. Avec vu bilinear pour les hauteurs / textures ca rendait tout de suite super mieux

Oui j'utilise du linéaire pour les hauteurs. Dans ma précédente version j'utilisais du linéaire pour la couleur aussi, ça coute pas grand chose à rajouter dans le code.
 
J'ai mis en ligne l'exécutable et le source code pour ceux qui veulent essayer (j'espère que ça marchera chez vous, il faut juste une machine  x86 32 bits sous windows) :
Moteur de terrain en voxel et C++ - algorithmes et code source
Moteur de terrain en voxel et C++ - niveau de détail, filtrage bilinéaire et antialiasing
 
J'essaie de traduire la suite dans les jours qui viennent dans la case réservée .

drapal

Bon je suis un peu fatigué..  
Pour ceux qui essaient de télécharger le programme :
 
les commandes sont les touches directionnelles pour tourner, avancer, reculer. La touche page up page down, pour elever baisser le point de vue (à la duke nukem 3D). et Escape pour quitter de manière précipitée.
 
Si vous rencontrez un pb signalez le moi, merci.

c'est normal que compilé en debug, y'aies des pics anormaux de terrain dans le rendu ?

c'est pas corrigé dans la derniere version ?

je le repompes et je te dit...

ouep ça a disparu (recompil VC++ 7.1 de VS 2003).
 
par contre en quittant il y a une violation d'accès dans voxe.lcpp ligne 483:
 
DWORD c = currentZone.m_diffuseheightmap[mapindex];

ouaip, code à l'arrache...
 
je regarde et je te dirai ça.

c'est marrant ça le fait pas toujours

j'ai essayé de voir si c'était lié a une orientation précise, mais c'est pas contant.
 
une fois qu'il y a une violation, j'essayes avec la même orientation, et ça le  fait pas a chaque coup.

c'est le destroy il arrive à un mauvais moment.
Je posterai le bon code demain.

Edit : non bon c'était bien débile

excellent legreg    
 
²

 
j'ai mis à jour le source, pas eu le temps de le faire hier soir, mais ce soir c'est bon.
 
Le thread se fait proprement terminer maintenant

J'ai posté la deuxième partie (voir troisième poste plus haut).
 
Enjoy.

Et hop, flag, pour cet excellent topic, comme d'hab.
 
Notons que les Voxels 3D ont l'avantage de pouvoir reconstruire un modèle 3D à partir d'une pile de tranches 2D ou réaliser des tranches quelconques dans un volume, comme dans les logiciels de visualisation médicale d'aujourd'hui.