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.

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é).

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).

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.

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.

Voir la partie II : Moteur de terrain par voxel - Visibilité, occlusion.