VoxelSpace : algorithme de rendu de terrain implémenté en moins de 20 lignes (2020)

Voxel Space

Démo web : moteur Voxel Space

Histoire

• En 1992, le CPU était jusqu’à 1000 fois plus lent qu’aujourd’hui et l’accélération GPU n’était pas encore connue ou était très chère.
• Les jeux 3D étaient calculés uniquement sur le CPU, et le moteur de rendu affichait des polygones d’une seule couleur.
• En 1991, le jeu Gunship 2000 de MicroProse et, en 1992, le jeu Comanche de NovaLogic ont été publiés.
• Comanche offrait des graphismes impressionnants pour l’époque, avec textures, ombrages et ombres.

Algorithme de rendu

• Comanche utilise une technique appelée Voxel Space, basée sur une idée proche du ray casting.
• Le moteur Voxel Space est un moteur 2.5D et ne fournit pas toutes les libertés d’un moteur 3D classique.

Height map et color map

• La façon la plus simple de représenter un terrain consiste à utiliser une height map et une color map.
• Le jeu Comanche utilise des maps de hauteur et de couleur de taille 1024 * 1024 en 1 octet.
• Ces maps sont périodiques et ne peuvent pas représenter des structures complexes, mais la color map inclut déjà les ombrages et les ombres, ce qui évite de recalculer l’éclairage pendant le rendu.

Algorithme de base

• L’algorithme de rendu d’un moteur 3D est très simple.
• Le moteur Voxel Space rasterise les height maps et color maps, puis dessine des lignes verticales.
• L’écran est effacé, puis le rendu est effectué de l’arrière vers l’avant pour garantir l’occlusion.
• Les lignes de la carte correspondant à la distance optique depuis l’observateur sont déterminées.
• Les lignes sont rasterisées en fonction du nombre de colonnes de l’écran.
• La hauteur et la couleur associées au segment de la ligne dans la carte 2D sont récupérées.
• Une projection perspective est appliquée aux coordonnées de hauteur.
• Une ligne verticale est tracée avec la hauteur issue de la projection perspective et la couleur associée.

Ajout de la rotation

• Avec cet algorithme, on ne peut regarder que vers le nord.
• Pour regarder sous d’autres angles, il suffit de quelques lignes de code pour faire pivoter les coordonnées.

Amélioration des performances

• De nombreuses astuces existent pour améliorer les performances.
• Il est possible de dessiner de l’avant vers l’arrière au lieu de l’arrière vers l’avant.
• Un y-buffer supplémentaire est nécessaire pour garantir l’occlusion.
• Le niveau de détail est ajusté : plus de détails sont rendus de près, moins de détails au loin.

Liens

• Page de démonstration du projet web
• Présentation du moteur de terrain Voxel
• Site personnel

Cartes

• Couleur
• Hauteur

Licence

• La partie logicielle est sous licence MIT.
• La technologie Voxel Space peut encore être brevetée dans certains pays.
• Les color maps et height maps ont été reverse-engineered à partir du jeu Comanche et sont exclues de la licence.

[GN⁺]

Commentaires Hacker News

• On a tous la nostalgie d’une époque où des algorithmes originaux et élégants offraient des expériences magiques. Quand les ressources matérielles étaient limitées, les développeurs poussaient les jeux plus loin grâce à de nouvelles techniques et à leur créativité.

  • Aujourd’hui, des plateformes plus fantaisistes comme le PICO-8 me semblent plus intéressantes que les jeux répétitifs des studios AAA.
  • Des algorithmes comme VoxelSpace montrent qu’il est possible de rendre un terrain avec moins de vingt lignes de code.

• La vidéo liée au programme mars.com est intéressante.

  • On peut trouver des infos sur le site Pouet.

• Cette technique de rendu est intéressante, mais comme elle ne peut pas afficher des volumes arbitraires, il est difficile de la classer comme du voxel. C’est une implémentation élégante d’un renderer de heightmap.

• La discussion mentionnant 2020 ou 2017 peut être celle qui apparaît dans le titre. En 2021, il y a aussi eu une discussion sur le même repo.

• Quand j’ai commencé à coder, je me souviens avoir écrit, en QBasic, un programme qui générait une heightmap de terrain et la rendait en style isométrique. C’était l’un des éléments qui m’ont donné envie de poursuivre la programmation.

• J’ai utilisé cette technique pour faire un jeu avec Adventure Game Studio. Ce n’était pas optimisé pour l’ancienne version du moteur, mais je prévois de le mettre à jour un jour.

• Dans la plupart des jeux modernes, les montagnes sont souvent vides à l’intérieur ; avec cette méthode, elles ont l’air plus remplies.

• Je me souviens de l’impact de la première fois que j’ai joué à Comanche. Cela donnait vraiment une impression de science-fiction, comme venu du futur ou du cinéma.

• Les projets de renderer logiciel sont amusants et parfaits pour un projet de week-end. J’ai déjà implémenté un algorithme similaire par le passé, mais celle-ci est bien plus simple et nettement plus performante.

• J’aimerais vivre dans une timeline alternative où le GPU serait basé sur des voxels.