[raytracer] j'arrive à afficher des pixels

Bonjour,

Depuis ma jeunesse, j’avais envie d’écrire un raycaster façon Wolfenstein3D.

À l’époque (2005–2010), j’avais essayé de faire des trucs. Il fallait utiliser du C, OpenGL, savoir déchiffrer des ressources en anglais (notez le copyright initial de 2004. Je connais cette page depuis plus de 10 ans. Cela ne me rajeuni pas) et comprendre des trucs en maths. je n’ai jamais réussi à faire mieux que dessiner une vue de dessus du niveau à coup de carrés… Plus Bomberman que wolfeinstein…

Pendant mes congés d’hiver 2021–2022, j’ai lu les deux Game Engine Black Book de Fabien Sanglard sur WolfEinstein3D et Doom. Je vous les recommande, ils sont vraiment très instructifs sur ces deux jeux, mais aussi sur l’architecture des ordinateurs de l’époque et comment les exploiter aux mieux pour faire des rendus 3D à 30fps sans utiliser de cartes graphiques parce qu’elles n’existaient pas encore?!

Récemment, j’ai été amené à évaluer TypeScript pour le travail. L’idée était que si j’arrivais à l’utiliser, à priori tout le monde dans l’équipe devrait s’en sortir. Ce n’est pas tellement que je sois un mauvais développeur. C’est plutôt que je suis totalement réfractaire au front-end et tout ce qui tourne autour. Voyez-vous, je suis plutôt un développeur backend et système. Je fais surtout dans l’automation, les trucs qui font leurs vies tous seuls dans leur coin, sans interagir avec un utilisateur. Je n’ai que très rarement à me soucier des questions d’ergonomies ou d’expérience utilisateur. L’important est que ça marche bien, et vite. Pis j’aime pas JavaScript. Le langage a des concepts très intéressants qui parfois me manquent en Python. Mais je trouve qu’il y a aussi beaucoup trop de trucs wtf pour avoir envie de travailler avec.

Je me suis dit vu que je vais devoir découvrir des trucs relous comme nodejs, grunt, babel, … autant faire un PoC fun. Je refusais de me prendre la tête avec le DOM, donc l’affichage serait minimaliste. Vu qu’au taf on fait pas mal de maths dans le front pour générer de jolis graphiques, il fallait que j’arrive à caser des calculs. Vous me voyez venir ?

En quelques jours, je suis arrivé à ce résultat:

Le code est ici. Une démo est disponible là. Attention, c’est auto-hébergé @home sur un vieux netbook de récupération sous OpenBSD, aucune garantie de disponibilité Vous pouvez vous déplacer avec ZQSD en AZERTY. Ça utilise les emplacement physique des touches, donc ça sera WASD en QWERTY et ÉAUI en bépoè (bépo est votre ami. bépo est normalisé par l'AFNOR. utilisez bépo).

Bon, c’est moche, y’a un gros bug de perspective (ma formule de projection ne marche que pour les champs de vue de 90° maximun là on est à 120° parce que je voulais expérimenter avec l’effet fish-eye), ça donne le mal de mer. Mais je m’en fou. Ça fait plus de 10 ans que je voulais faire ça. Un rêve d’ado s’est enfin réalisé. Je suis content quoi

Le moteur utilise le même principe que celui de WolfEinstein3D. Pour chaque colonne de pixels du canvas à dessiner, on va lancer un "rayon" à partir de la camera et en direction de cette partie du champs de vue pour savoir à quelle distance se situe le mur le plus proche. Une fois qu’on connait la distance du mur, on peut calculer sa hauteur apparente pour savoir la longueur de la ligne à dessiner. Avec cette technique, une frame est toujours dessiné avec 2 rectangles gris (le sol et le plafond) et de x lignes bleus verticales, x étant la largeur du canvas, quelque soit la scène à rendre. Le truc marrant, c’est que le moteur est purement 2D. La scène est décrite due de dessus, façon plan d’architecte. La notion de hauteur n’apparaît qu’à la toute dernière étape, juste avant de dessiner la ligne. Littéralement. Allez voir par vous même. Même si il est beaucoup plus complexe et permet bien plus de choses, Doom utilisent la même idée de scene en 2D avec la notion de hauteur qui apparaît très tard dans le processus de rendu

Plus récemment, j’ai acheté Computer Graphics from Scratch via un bundle HumbleBundle. Il explique comment écrire un raytracer. Un raytracer est la version avancée du raycaster. Au lieu de lancer un rayon par colonne de pixels, on lance un rayon par pixel, et on retrace son chemin inverse pour savoir quels objets il a touché afin de déterminer sa couleur. Cela permet des rendus photoréalistes. Le bouquin est très sympathique. Les maths sont expliqués de façon à ce qu’un idiot comme moi comprenne ce qu’il fasse avec beaucoup d’exemples visuels pour mieux appréhender les vecteurs et la trigonométrie (je pense qu’un niveau terminal S scientifique est suffisant pour s’en sortir). Les parties importante des algorithmiques sont données en pseudo-c facilement transposable dans n’importe quel langage (j’ai choisi rust) et tous les détails de l’implémentation sont laissé en exercice au lecteur ("on supposera l’existence de la méthode Canvas::draw(x, y, color) permettant de dessiner un pixel sur le canvas"). J’ai choisi de dessiner dans un framebuffer stocké en mémoire vive et de faire l’affichage avec la SDL en utilisant mon framebuffer pour créer une texture qui occupe tout l’écran ^^’.

Mon objectif principal est de pouvoir se déplacer dans les niveaux de Doom. Je ne suis pas intéressé par réimplémenter tout le jeu, seulement m’amuser avec des images générés par ordinateur. Si vous voulez jouer à Doom, il existe déjà un projet pour ça.

J’ai deux objectifs secondaires qui sont mutuellement incompatibles et qui implique des choix architecturaux différents.

D’un côté, je veux que ça puisse tourner sur un maximum d’ordinateurs différents, dont le vénérable Commodore 64. Pré-requis minimums: un processeur et un peu de mémoire. Rien de plus. Cela m’orienterai vers un rendu dans un framebuffer en mémoire comme actuellement. Il y a même moyen de se passer des nombres à virgules flottantes en utilisant les entier pour stocker des nombres à virgules fixes. Ils ont une précision suffisante pour ce projet.

D’un autre côté, j’ai envie de tenter un truc totalement absurde, en faisant le rendu uniquement par des fragments shaders pour rendre les pixels en parallèle grâce à la carte graphique, le CPU ne servant qu’à actualiser la positon de la caméra en fonction des inputs de utilisateur et demander à la carte graphique de dessiner la nouvelle frame.

J’ai beaucoup plus envie de voir marcher la version à base de shader. C’est mon amour de la philosophie "pourquoi je l’ai fait ? mais tout simplement parce que je pouvais !" Mais j’ai aussi beaucoup moins envie de travailler sur des shaders. Je pense donc plutôt m’orienter vers l’option minimaliste.

Un objectif tertiaire est d’ajouter wasm en tant que plateforme officiellement supportée. J’ai envie de découvrir et jouer avec ce truc.

Il est à noter que les scènes sont décrites en utilisant des "signed distance functions". C’est une représentation vectoriel. Il n’y a pas de notion de polygones, seulement de surfaces dans l’espace décrites par des équations paramétriques. Non, ne fuyez pas, ce n’est pas aussi effrant que ça en a l’air. Dans la manière habituelle de modéliser une sphère avec des polygones, on assemble plein de petits triangles. Plus il y a de triangles, plus la sphère apparaît lisse mais demande aussi plus de calculs. Avec les SDF, une sphere est simplement l’ensemble des points situé à une certaine distance appelé rayon d’un point appelé le centre ``. Avec une empreinte extrêmement faible (nous ne stockons que la position du centre de la sphère et son rayon, sont 4 scalaires, 128 bits sur nos ordinateurs tournant), nous avons accès à l’ensemble des points de la sphère, permettant en théorie une précision absolue pour dessiner une sphère ! Évidemment, dans la pratique, on se content d’un nombre plus restreint de points afin d’avoir une précision suffisante en un temps raisonnable. Oui, l’informatique est toujours une histoire de compris entre CPU et mémoire. Il n’y aura jamais de solution optimal sur les deux points.

Pour l’instant, le moteur ne sait afficher que des sphères. J’arrive gérer des matériaux solides et les lumières de type ambiantes, directionnelles et omnidirectionnelles. Cela permet d’arriver à ce résultat:

La prochaine étape immédiate est l’ajout des ombres et la réflexion façon miroir.

Un chantier futur sera de trouver comment transformer les niveaux de doom décrits avec des polygons en signed distance functions. Ça devrait être fun

Le projet est disponible ici

Je ne suis pas venu ici pour faire la pub du projet. Mon but est plus pédagogique. A 16 ans, j’aurais été incapable d’arriver ne serait-ce qu’au 10ème de ce que j’ai là. Et pourtant, maintenant à 31 ans, ce fut plutôt facile en fait. Je n’y ai pas passé tant de soirées que ça. Il m’a fallut 15 ans pour assimiler toutes les connaissances nécessaires. Apprendre l’anglais. Bouffer de la trigo et des vecteurs. Lire des tonnes de pages web (wikipedia <3) sur les ordinateurs, leurs fonctionnement internes, leurs histoires (que voulez-vous j’aime apprendre). Avoir eu l’opportunité de travailler professionnellement dans des projets en rapport avec le jeu vidéo (TL;DR: Ubisoft Montpellier avait sous-traité à ma boite la création d’un prototype du jeu just dance pour les iphones. Le téléphone est connecté à une Apple TV pour faire l’affichage sur une TV et on s’en sert de capteur façon wiimote pour évaluer la performance du joueur. Possibilité de jouer à 4 avec chacun son iphone ou chacun son tour. J’ai fait une battle avec les devs de la licence chez Ubisoft et même leur director qui supervisait le projet. Tu peux pas tests les trucs de fous que j’ai fait dans ma vie). Pleins de trucs quoi. Et maintenant, j’ai envie de partager d’une manière ou d’une autre toute cette connaissance et expérience accumulée, et ce site m’a l’air le bon endroit pour ça. Je n’ai pas envie de faire un tutoriel sur comment faire votre moteur 2.5D vectoriel en rust qui fait tourner les assets de doom sur commodore 64 avec des shaders dans WASM (mais ça serait un projet SUPER intéressant). Plutôt d’échanger avec vous sur des points ou d’autres. Des points précis tel que pourquoi j’ai choisi d’utiliser un for plutôt qu’un while là car le compilateur aurait pu s’assurer une amélioration ou des trucs plus vague tel que pourquoi l’Univers ? Le choix est votre

C’est un beau projet, mais je ne comprends pas exactement ce que tu attends comme retours.

J’aime beaucoup le raytracing, c’est une méthode qui m’a toujours fasciné notamment par sa simplicité apparente (je n’ai jamais aimé devoir représenter des objets de l’espace par des polygones). J’ai eu l’occasion de coder différents petits moteurs, ça n’allait jamais très loin parce que les techniques plus avancées finissaient par me lasser.

Et ça rejoint au final ce que je reproche aussi à cette méthode rendu : pour avoir un rendu vraiment réaliste, il faut empiler plein de couches de traitements différents sur la gestion des lumières et des couleurs qui l’éloignent vraiment du côté simpliste "je lance des rayons que je fais rebondir".

C’est un beau projet, mais je ne comprends pas exactement ce que tu attends comme retours.

Moi non plus J’aimerai contribuer au partage du savoir en transmettant les connaissances que j’ai pu accumuler au cours de ma vie. Je pensais faire ça sous forme d’une session questions/réponses sur les concepts et technos plus ou moins directement liés au projet (rust, maths, 3D, les moteurs de jeu, wolfeinstein, commodore 64, wasm, …) et même plus large. J’aimerai que quelqu’un qui passe par hasard sur cette page apprennent des trucs sur l’informatique. Si tu utilises Linux, tu as du croiser la commande awk. On le considère souvent comme une alternative à sed. Mais savais-tu qu’il s’agissait en réalité d’un interpréteur pour un langage Turing-complet ? Ça en fait un outil puissant et plus simple que perl pour traiter du texte. Je vous recommande le livre The AWK Programming Language par Aho, Kernigham et Weinbeirg. Il commence à être difficile de le trouver en version papier mais il existe des versions PDF facilement trouvable. Ça me fait toujours un petit quelque chose de lire "This book was typeset (…) using a DEC VAX 8550 running the 9th Edition of Unix® operating system" dans les mentions légale de la page de garde. J’ai l’impression d’être le gardien d’une relique sacrée du passée ^^’. Todo: écrire un cours pour ce magnifique outil. Anecdote : j’ai déjà écrit un compilateur brainfuck avec. Techniquement un transpiler vers c.

J’aime beaucoup le raytracing, c’est une méthode qui m’a toujours fasciné notamment par sa simplicité apparente (je n’ai jamais aimé devoir représenter des objets de l’espace par des polygones). J’ai eu l’occasion de coder différents petits moteurs, ça n’allait jamais très loin parce que les techniques plus avancées finissaient par me lasser.

Et ça rejoint au final ce que je reproche aussi à cette méthode rendu : pour avoir un rendu vraiment réaliste, il faut empiler plein de couches de traitements différents sur la gestion des lumières et des couleurs qui l’éloignent vraiment du côté simpliste "je lance des rayons que je fais rebondir".

Et ce moteur n’ira pas tellement beaucoup plus loin que ce que me propose le bouquin Computer Graphics from Scratch. Je ne suis pas intéressé par faire le moteur absolu. Je voulais comprendre comment avec des maths on arrivait à générer de jolis pixels représentant une scène. Objectif atteint. Maintenant, on va essayé d’en faire un truc cool (le port vers commodore 64 et la possibilité de lire les .wad de doom). Ça ne sert à rien. J’abandonnerai probablement en cours. Mais en chemin, j’aurai appris de nouveaux trucs et me serait amusé.