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

 (github.com/s-macke)
4 points par GN⁺ 2025-01-05 | 1 commentaires | Partager sur WhatsApp
  • Voxel Space est une technique de rendu de terrain en 2,5D utilisée dans Comanche de NovaLogic en 1992, qui permettait de représenter des montagnes et des vallées texturées uniquement avec le CPU à une époque où l’accélération GPU n’existait pas ou coûtait trop cher
  • Le terrain est représenté par une height map et une color map, et Comanche utilisait une height map 1024×1024 sur 1 octet et une color map 1024×1024 sur 1 octet
  • La color map contient déjà l’éclairage et les ombres, ce qui évite tout calcul de lumière pendant le rendu, mais comme chaque position de la carte ne peut avoir qu’une seule hauteur, il est difficile de représenter des structures géométriques complexes comme des bâtiments ou des arbres
  • Le rendu de base rasterise des segments de la carte de l’arrière vers l’avant, puis lit la hauteur et la couleur pour chaque colonne de l’écran afin de tracer des lignes verticales ; un angle de vue de 90° et la projection en perspective sont implémentés en quelques lignes de code
  • Les performances peuvent être améliorées en dessinant de l’avant vers l’arrière, en sautant les parties masquées grâce à un y-buffer par colonne, et en réduisant le niveau de détail au loin

Contexte d’apparition de Voxel Space

  • En 1992, les CPU étaient 1000 fois plus lents qu’aujourd’hui, et l’accélération GPU était inconnue ou trop coûteuse
  • Les jeux 3D étaient calculés uniquement par le CPU, et les moteurs de rendu dessinaient généralement des polygones remplis d’une seule couleur
  • NovaLogic a sorti Comanche en 1992, et sa représentation des textures, de l’éclairage et des ombres sur les montagnes et les vallées se distinguait des graphismes de jeu de l’époque
  • Le README fournit une Web Demo of the Voxel Space Engine

Représentation du terrain : height map et color map

  • Dans Voxel Space, la manière la plus simple de représenter le terrain consiste à utiliser une height map et une color map
  • Comanche utilise les deux cartes suivantes
    • height map 1 octet de 1024×1024
    • color map 1 octet de 1024×1024
  • Ces cartes se répètent de manière périodique
  • Chaque position de la carte ne peut avoir qu’une seule hauteur
    • Il est impossible de représenter des structures géométriques complexes comme des bâtiments ou des arbres
    • En revanche, comme l’éclairage et les ombres sont déjà intégrés dans la color map, aucun calcul de lumière n’est nécessaire pendant le rendu

Algorithme de rendu de base

  • Le moteur Voxel Space rend le terrain en rastérisant la height map et la color map puis en traçant des lignes verticales à l’écran
  • La procédure de base est la suivante
    • effacer l’écran
    • dessiner de l’arrière vers l’avant pour garantir la gestion des occultations
    • trouver sur la carte la ligne correspondant à une même distance optique par rapport à l’observateur
    • prendre en compte l’angle de vue et la projection en perspective
    • découper cette ligne selon le nombre de colonnes de l’écran
    • lire la hauteur et la couleur dans la carte 2D à chaque position du segment
    • appliquer la projection en perspective à la coordonnée de hauteur
    • tracer une ligne verticale avec la hauteur projetée et la couleur de la color map
  • Dans sa forme Python la plus simple, la boucle principale réduit z de la distance la plus lointaine vers la plus proche et appelle DrawVerticalLine pour chaque colonne de l’écran
  • L’appel d’exemple passe la position, la hauteur de caméra, la position de l’horizon, l’échelle de hauteur, la distance maximale, ainsi que la largeur et la hauteur de l’écran

Ajout de la rotation

  • L’algorithme de base ne permet de regarder que vers le nord
  • Pour regarder dans d’autres directions, on ajoute du code pour faire tourner les coordonnées
  • La version avec rotation prend phi comme angle de vue et précalcule sin(phi) et cos(phi)
  • Les coordonnées tournées sont appliquées au calcul des points limites gauche et droite du champ de vision, et x et y sont incrémentés ensemble le long de chaque colonne de l’écran
  • La structure essentielle du rendu reste identique
    • calcul des segments par distance
    • rastérisation adaptée aux colonnes de l’écran
    • consultation de la height map et de la color map
    • tracé de lignes verticales après projection en perspective

Méthodes d’amélioration des performances

  • Au lieu de dessiner de l’arrière vers l’avant, il est possible de dessiner de l’avant vers l’arrière pour réduire les zones occultées
  • Cette méthode nécessite un y-buffer qui stocke, pour chaque colonne de l’écran, la position y la plus haute
    • la valeur initiale du y-buffer est fixée à la hauteur de l’écran
    • on ne dessine la partie visible que lorsque le nouveau height_on_screen est plus haut que la valeur existante dans le y-buffer
    • après le dessin, le y-buffer est mis à jour avec cette nouvelle position plus haute
  • La distance z augmente du proche vers le lointain
  • En augmentant progressivement dz, on peut échantillonner à intervalles plus grands au loin et obtenir un effet de Level of Detail
  • Le principe consiste à rendre les zones proches avec plus de détails et les zones lointaines avec moins de détails

Ressources fournies et licence

  • Le dépôt inclut plusieurs paires de color maps et de height maps
  • La partie logicielle est sous licence MIT
  • La technologie Voxel Space peut encore être couverte par des brevets dans certains pays
  • Les color maps et les height maps sont des données rétroconçues à partir du jeu Comanche et sont donc exclues de la licence
  • Parmi les ressources liées figure le lien Voxel terrain engine - an introduction

À lire aussi

1 commentaires

 
GN⁺ 2025-01-05
Avis de Hacker News

  • Très cool. L’époque où ce genre d’algorithmes nouveaux et élégants créait des expériences magiques me manque.
    C’est peut-être juste l’âge qui me fait voir les choses ainsi, mais j’ai l’impression que les jeux de l’époque où les ressources matérielles étaient limitées avaient davantage de magie qu’aujourd’hui. Dans les années 80, 90 et au début des années 2000, presque chaque année, ou au moins à chaque génération, les jeux faisaient avancer le média lui-même, et les développeurs tiraient le maximum du matériel avec de nouvelles techniques et des optimisations relevant de la pure magie.
    Aujourd’hui, je trouve les plateformes fantaisie comme PICO-8 bien plus intéressantes que les sorties répétitives des studios AAA, et je ne comprends pas vraiment pourquoi des jeux qui ne changent en gros que les assets rencontrent un tel succès année après année.

    • Les jeux AAA modernes contiennent encore beaucoup de techniques magiques. En réalité, l’industrie du jeu est l’un des rares domaines qui se soucient sérieusement des performances, parfois même davantage que de la sûreté ou de l’exactitude.
      Simplement, aujourd’hui c’est beaucoup plus complexe et moins visible. Avant, on voyait les progrès, par exemple le passage de triangles plats à des textures grâce à des astuces mathématiques ingénieuses ; aujourd’hui, il s’agit plutôt d’améliorer l’ombrage dans le coin d’une pièce. Tout le monde remarque immédiatement une amélioration des textures, mais l’ombre dans un coin est difficile à pointer du doigt si l’on n’est pas du métier. Pourtant, ces éléments s’additionnent et améliorent le rendu global, même si c’est moins impressionnant qu’avant.
      L’industrie AAA est un gros business, les jeux coûtent énormément cher à produire, et les investisseurs veulent un retour. On étudie donc généralement le marché, on regarde ce qui se vend bien, puis on crée quelque chose dans la même direction. C’est moins original, mais moins risqué.
      À l’inverse, l’industrie du jeu indé compte des milliers de studios et ne peut pas battre le AAA sur la quantité de contenu ou le niveau de finition ; elle a donc besoin d’autres armes, comme des idées originales, pour sortir du lot. Mais aujourd’hui, dépasser des limites techniques n’est souvent plus le principal moteur. Il y a moins de contraintes qu’avant. Au contraire, il est courant de pousser moins loin techniquement que les productions AAA, parce que le coût serait impossible à assumer.
      Je ne connais pas bien la scène PICO-8, mais je me demande quelle part consiste à surmonter des limitations techniques artificielles, et quelle part consiste à utiliser la plateforme de la manière prévue en se concentrant sur le gameplay.
    • Ça ressemble surtout à des souvenirs vus à travers des lunettes de soudure rose bonbon d’un quart de pouce. Les jeux AAA modernes ont eux aussi des moments à couper le souffle, et même s’ils souffrent de la maladie des suites répétitives, il existe aussi des œuvres originales, rendues clairement possibles par la technologie.
      Je me souviens aussi qu’autrefois, il y avait vraiment, vraiment, vraiment beaucoup de jeux catastrophiques.
    • J’étais en train de faire un Mario Kart 3D sur calculatrice avec cet algorithme. Cette calculatrice avait déjà du mal avec des graphismes 2D ordinaires, donc c’était assez amusant, mais je ne l’ai jamais terminé.
      L’un des prototypes est ici : https://youtu.be/9Z8Bm8ZmWKI
    • J’étais en train de faire un Mario Kart 3D sur calculatrice avec cet algorithme. Cette calculatrice avait déjà du mal avec des graphismes 2D ordinaires, donc c’était assez amusant, mais je ne l’ai jamais terminé.
      L’un des prototypes est ici : https://media.discordapp.net/attachments/953383695908216843/...
    • Il y a encore beaucoup d’innovations impressionnantes dans la technologie des jeux. Il suffit de regarder des jeux comme Noita, Dreams ou Teardown, et parmi les jeux plus récents, Tiny Glade.
      La récente présentation technique de Tiny Glade est pleine de choses magiques : https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      De belles technologies émergent aussi à des niveaux plus fondamentaux, dans les moteurs et frameworks. Par exemple Nanite/Lumen/MegaLights dans UE5.

  • Quelques liens liés. Y en a-t-il d’autres ?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - octobre 2023, 2 commentaires
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - mars 2021, 71 commentaires
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - janvier 2020, 116 commentaires
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - novembre 2017, 93 commentaires
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - septembre 2017, 2 commentaires

  • mars.com me vient tout de suite à l’esprit. Ce n’est pas un domaine, mais un programme. Vidéo : https://www.youtube.com/watch?v=_zSjpIyMt0k
    Ajout : il est aussi sur Pouet : https://www.pouet.net/prod.php?which=4662

    • J’ai aussi trouvé une implémentation JavaScript de cette démo : http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • Ça m’a fait remonter une énorme vague de nostalgie. Vers 1998, quand il m’est arrivé, il était contenu dans un fichier Microsoft Word et se contrôlait à la souris
      À l’époque je trouvais ça génial, mais comme j’étais un gamin qui ne connaissait rien à la demoscene ni à la programmation, j’étais déçu que ce ne soit pas un jeu complet. Avec le recul, je pensais que c’était juste une pauvre démo DirectX qui circulait par e-mail ; je ne savais pas que c’était un vrai truc existant
    • Pour être précis, mars.com tournait de façon fluide même sur un 286 à 8 MHz
    • Aïe. Je me souviens l’avoir lancé sur un 286 et avoir été bluffé. Et, en même temps, avoir été déçu que Wing Commander 3 ne tourne pas sur la même machine

  • Le mode de rendu est élégant, mais je ne sais pas si on peut vraiment appeler ça des voxels. On ne peut pas rendre un volume arbitraire, et le mode de stockage des données ne permet qu’une seule position pour un x,y donné
    N’est-ce pas simplement une chouette implémentation d’un moteur de rendu de heightmap ?

    • Je pense clairement qu’on peut le considérer comme un moteur voxel. Une heightmap ne gère pas les surplombs comme un octree, mais au final la hauteur est une pile de voxels
      Un octree sans surplombs aurait exactement cette forme
    • Pour autant que je sache, voxel signifie quelque chose comme volume element. Un peu comme pixel vient de picture element, et le x est plutôt là pour le style
      Dans ce mode de rendu, chaque colonne est une boîte 3D, donc ça ne me choque pas de parler de matrice de voxels 2x2
    • Ce genre de moteur de rendu de heightmap était clairement appelé « voxel » à l’époque
    • Oui, le nom donné à cet algorithme prête à confusion

  • Dans les années 1990, au lycée, pendant que j’apprenais la trigonométrie nécessaire, j’ai un très bon souvenir d’avoir créé ce genre de visualiseur de terrain. D’abord en Pascal, puis en C et en Assembly
    À l’époque, il fallait toutes sortes d’optimisations bas niveau pour réussir à le faire tourner
    Comprendre comment l’implémenter et l’optimiser sans livres de référence ni Internet reste pour moi l’une des choses les plus gratifiantes que j’aie faites

  • J’ai fait un jeu avec cette technique : https://eri0o.itch.io/i-rented-a-boat
    Il est fait avec Adventure Game Studio, et a été réalisé avec une version antérieure du moteur, pas encore optimisée. J’ai la flemme de mettre à jour la page itch, donc je la laisse comme ça, mais je le ferai un jour
    J’y ai écrit un billet expliquant comment je l’ai fait, et il y a davantage de détails sur les forums AGS

    • Impressionnant que ce soit possible dans AGS

  • On pourrait mettre [2020] dans le titre, et à en juger par d’autres commentaires dans le lien de discussion ci-dessous, [2017] semble aussi possible
    Il y a aussi eu une discussion en 2021 sur le même dépôt : https://news.ycombinator.com/item?id=26631995
    Ce fil renvoie lui aussi vers d’autres discussions
    Ce n’est pas exactement la même chose, mais je me souviens qu’à l’époque où j’apprenais tout juste à programmer, j’avais écrit un programme qui générait des heightmaps de terrain et les rendait dans un style isométrique avec une technique similaire. C’était en QBasic, sur les machines DOS 386 de mon collège, et j’utilisais la mémoire graphique comme espace de travail temporaire
    C’était incroyablement lent, mais le résultat me fascinait, et c’est l’une des choses qui m’ont donné envie de continuer à programmer

  • Je me souviens avoir lu ça quelque part auparavant ; cette fois je laisse un commentaire pour ne pas le perdre
    En tant que fan de simulateurs de vol, je me souviens encore du choc quand j’ai joué à Comanche pour la première fois. On aurait dit que ça venait du futur ou d’un film, et j’avais vraiment l’impression de vivre à l’ère de l’informatique

    • Novalogic a utilisé cette technique assez longtemps pour le rendu de terrain, et mon préféré reste le tout premier Delta Force
      Avec Comanche 4 et le Black Hawk Down original, ils semblent avoir abandonné cette approche pour passer à un moteur polygonal : https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Je me souviens de Comanche. Ça m’a rappelé l’époque où, sur Atari 8 bits, j’étais émerveillé par la génération procédurale de Rescue on Fractalus[0], dont le titre de prépublication était Behind Jaggi Lines
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg la scène d’atterrissage sur Terre apparaît à 1:00

  • Vraiment génial
    Dans la plupart des jeux modernes, à cause d’angles de caméra bizarres ou de problèmes de clipping, on voit parfois que les montagnes sont des structures creuses
    Mais avec cette méthode, les montagnes sont pleines et bien solides >:)

  • Je recommande vivement de créer ce genre de renderer logiciel pour le plaisir. Les ray tracers sont un projet courant, mais ce type de code de rendu temps réel rétro fait aussi un bon projet de week-end
    Il y a longtemps, j’ai implémenté presque le même algorithme. Plus exactement, j’ai porté du code SDL comme exercice pour apprendre canvas2d : http://namuol.github.io/earf-html5/
    Bien sûr, l’implémentation liée est bien plus rapide et beaucoup plus simple que la mienne, donc si vous cherchez une référence, je ne recommande pas mon vieux code CoffeeScript…