Raycasting

En 1991, le jeu vidéo PC était dominé par deux approches : les jeux 2D vue de dessus (comme Commander Keen) et les simulateurs 3D ultra-lents (comme Ultima Underworld). Les rares tentatives de 3D temps réel se heurtaient à un mur physique : les processeurs Intel 386 et 486 de l'époque, cadencés à 25-33 MHz, n'avaient aucune unité de calcul dédiée aux graphismes.

Le ray tracing, la technique de rendu 3D réaliste, existait déjà depuis les années 70 mais nécessitait des minutes, voire des heures, pour calculer une seule image sur les supercalculateurs de l'époque. L'idée de l'utiliser pour un jeu en temps réel à 30 images par seconde semblait pure science-fiction.

C'est dans ce contexte qu'id Software, un petit studio de quatre personnes, a commencé à travailler sur un prototype qui allait tout changer. Leur ambition ? Créer un jeu d'action à la première personne fluide sur des machines grand public. Leur arme secrète ? Un jeune programmeur de 21 ans nommé John Carmack.

En 1992, John Carmack a accompli l'impossible : créer une illusion de 3D fluide sur des processeurs Intel 286 et 386, des machines qui n'avaient aucune capacité de rendu 3D matériel. Son secret ? Le raycasting, une technique astucieuse qui simule la 3D en ne calculant que ce qui est strictement nécessaire.

« Le raycasting n'est pas de la vraie 3D, c'est une illusion brillante qui exploite les limitations de notre perception. » — John Carmack

La beauté du raycasting réside dans sa dualité 2D/3D : tous les calculs se font dans un plan 2D (la carte vue de dessus), mais le résultat crée une illusion de profondeur saisissante. Le processus transforme une simple distance (1D) en hauteur de mur à l'écran (2D), qui elle-même génère la perception de perspective (3D). Cette cascade de transformations — distance → hauteur → perspective — est le cœur de l'illusion.

Contrairement au ray tracing qui lance des rayons capables de rebondir (réflexion, réfraction, ombres), le raycasting s'arrête au premier obstacle rencontré. C'est précisément cette absence de calcul de rebond qui permet la performance : on lance un rayon par colonne de pixels, on trouve le premier mur touché, et on dessine une bande verticale proportionnelle à la distance. Le résultat ? Wolfenstein 3D, le jeu qui a lancé l'ère des FPS.

Le monde du raycasting est fondamentalement une grille 2D vue de dessus. Chaque cellule de cette grille (appelée map) est soit vide, soit occupée par un mur. Cette simplification est la clé de la performance.

La map est un simple tableau 2D d'entiers. La valeur 0 représente un espace vide, et toute valeur positive représente un type de mur (utile pour les textures) :

Le joueur est défini par sa position $(x, y)$ dans la grille et sa direction de regard. La direction est représentée par un vecteur unitaire $\vec{dir}$, et le champ de vision par un vecteur perpendiculaire $\vec{plane}$ (le plan de la caméra) :

Le facteur $fov$ contrôle l'amplitude du champ de vision. Une valeur de 0.66 donne un FOV d'environ 66°, similaire à la vision humaine.

La longueur du vecteur $\vec{plane}$ détermine directement l'angle de vue : un vecteur court produit un effet de zoom (FOV étroit), tandis qu'un vecteur long crée un effet grand-angle (FOV large). Mathématiquement, l'angle de vue est $2 \times \arctan(|\vec{plane}| / |\vec{dir}|)$. Avec $|\vec{dir}| = 1$ et $|\vec{plane}| = 0.66$, on obtient environ 66°. Doubler la longueur du plane doublerait presque l'angle de vue, mais introduirait une distorsion aux bords.

Le cœur du raycasting est l'algorithme DDA. L'approche naïve serait d'avancer le rayon pixel par pixel jusqu'à toucher un mur, mais c'est terriblement inefficace.

Imaginez un rayon qui doit parcourir 100 unités avant de toucher un mur. Avec un pas de 0.01, il faudrait 10 000 itérations ! L'astuce du DDA est de sauter directement d'une ligne de grille à la suivante.

Au lieu de petits pas, on calcule la distance jusqu'à la prochaine ligne verticale ET la prochaine ligne horizontale, puis on avance vers la plus proche. On répète jusqu'à toucher un mur.

Pour un rayon de direction $(rayDirX, rayDirY)$, la distance entre deux lignes verticales consécutives est :

Et pour les lignes horizontales :

Intuitivement, $\Delta dist_x$ représente l'hypoténuse du triangle rectangle formé par le rayon lorsqu'il traverse exactement une unité de grille horizontalement. Si le rayon est presque horizontal ($rayDirX \approx 1$), cette distance est proche de 1. Si le rayon est presque vertical ($rayDirX \approx 0$), cette distance tend vers l'infini — logique, car un rayon vertical ne croisera jamais de ligne verticale !

L'efficacité du DDA vient de sa simplicité arithmétique : la boucle principale n'utilise que des additions. Une fois les valeurs $\Delta dist_x$ et $\Delta dist_y$ précalculées (une seule division par rayon), chaque itération se résume à comparer deux nombres et en incrémenter un. Sur les processeurs des années 90, où une multiplication coûtait des dizaines de cycles contre un seul pour une addition, cette optimisation était cruciale pour atteindre des framerates jouables.

Une fois le mur trouvé, il faut calculer sa hauteur à l'écran. C'est ici que la magie de la perspective entre en jeu.

La hauteur du mur est inversement proportionnelle à la distance. Mais attention : on utilise la distance perpendiculaire au plan de la caméra, pas la distance euclidienne directe. C'est le secret de la correction fisheye.

La hauteur du mur à l'écran est simplement :

Plus le mur est loin, plus $perpDist$ est grand, donc plus $lineHeight$ est petit. C'est la perspective !

Sans correction, les rayons aux bords de l'écran parcourent une distance plus longue que ceux au centre, créant une distorsion en "œil de poisson". La distance perpendiculaire résout ce problème en projetant la distance sur l'axe de la caméra.

Pourquoi la distance euclidienne échoue-t-elle ? Imaginez un mur parfaitement plat face à vous. Les rayons au centre de l'écran le touchent perpendiculairement, mais les rayons aux bords doivent parcourir un chemin plus long pour atteindre le même mur — ils voyagent en diagonale. Si on utilisait cette distance euclidienne (l'hypoténuse) pour calculer la hauteur, les bords du mur apparaîtraient plus petits que le centre, créant une courbure artificielle. La distance perpendiculaire "annule" cet effet en mesurant uniquement la composante de la distance parallèle à la direction de regard, comme si tous les rayons étaient parallèles.

Visuellement, imaginez que vous mesurez la distance non pas en ligne droite vers le mur, mais perpendiculairement au plan de votre écran. C'est cette astuce qui donne des murs parfaitement droits.

Prenons un exemple concret : un rayon au bord de l'écran qui touche un mur à 10 unités en distance euclidienne (hypoténuse). Si ce rayon fait un angle de 30° avec l'axe central, sa distance perpendiculaire est $10 \times \cos(30°) \approx 8.66$ unités. C'est cette valeur plus courte qu'on utilise pour calculer la hauteur du mur, évitant ainsi qu'il paraisse plus petit qu'il ne devrait.

Utilisez le toggle pour basculer entre les deux modes. En rouge (distance euclidienne), observez comment les murs aux bords semblent courbés vers l'intérieur. En vert (distance perpendiculaire), les murs restent parfaitement droits.

Pour chaque colonne de l'écran, on lance un rayon et on dessine une bande verticale. Voici la boucle principale :

Sur un processeur 386 cadencé à 33 MHz sans FPU (unité de calcul flottant), chaque cycle compte. Voici les optimisations utilisées par John Carmack pour atteindre 30 FPS sur ces machines antédiluviennes.

Les processeurs 386 sans coprocesseur mathématique (FPU) calculaient les nombres à virgule flottante de manière logicielle, rendant chaque opération 50 à 100 fois plus lente qu'avec des entiers. La solution ? Utiliser des entiers à virgule fixe.

Calculer $\sin$ et $\cos$ à chaque frame est prohibitif. L'astuce : précalculer toutes les valeurs possibles dans un tableau et les lire instantanément.

Le Mode 13h (320×200, 256 couleurs) permettait d'écrire directement dans la VRAM, évitant les appels système coûteux. Chaque pixel = 1 octet à l'adresse correspondante.

Explorez le raycasting en action ! La vue de gauche montre la map 2D avec les rayons, la vue de droite montre le rendu 3D. Utilisez ZQSD ou les flèches pour vous déplacer.

Le raycasting de base peut être enrichi de nombreuses façons. Voici quelques extensions classiques :

Pour ajouter des textures, on calcule la position exacte où le rayon touche le mur (entre 0 et 1), puis on utilise cette valeur pour échantillonner une colonne de la texture :

Un effet simple mais efficace : assombrir les murs orientés Nord/Sud (ou Est/Ouest). Cela donne une impression de profondeur et aide à distinguer les coins :

Les sprites (ennemis, objets, items) sont des images 2D qui restent toujours face à la caméra. Contrairement aux murs, ils nécessitent un tri en profondeur et un z-buffer pour l'occlusion.

Texturer le sol et le plafond est plus coûteux que les murs : au lieu d'un rayon par colonne, on doit calculer la position 3D pour chaque pixel. On utilise le raycasting horizontal pour optimiser.

Dans Wolfenstein 3D, le joueur ne peut pas regarder en haut ou en bas. Ce n'est pas une limitation technique arbitraire : le raycasting classique projette tous les rayons sur un plan horizontal. Permettre de regarder vers le haut ou le bas nécessiterait de recalculer la projection verticale de chaque colonne, introduisant une distorsion majeure ou un coût de calcul prohibitif pour l'époque. DOOM a contourné ce problème avec un astucieux "Y-shearing" qui décale simplement l'image verticalement — une illusion qui fonctionne tant qu'on ne regarde pas trop haut !

Le raycasting, malgré son ingéniosité, impose des contraintes strictes qui définissent son esthétique distinctive. Ces limitations ne sont pas des défauts, mais des compromis délibérés pour maximiser les performances.

Le raycasting classique exige une grille parfaitement alignée. Pas de murs diagonaux, pas de courbes, pas de pièces non-rectangulaires. Chaque cellule est soit vide, soit occupée. Cette contrainte découle directement de l'algorithme DDA qui parcourt les lignes de grille horizontales et verticales.

Tous les murs montent du sol au plafond à la verticale parfaite. Pas de pentes, pas d'escaliers, pas de plafonds à hauteur variable. La hauteur du mur est calculée par une simple division (hauteur écran / distance), ce qui suppose une projection cylindrique verticale.

Impossible de regarder en haut ou en bas — la caméra est verrouillée sur l'horizon. Cette limitation n'est pas arbitraire : permettre le pitch nécessiterait de recalculer les hauteurs de murs pour chaque colonne avec une projection en perspective, multipliant le coût par un facteur prohibitif.

Le raycasting pur ne peut gérer qu'un seul étage. Pas de ponts, pas de pièces au-dessus d'autres pièces, pas de balcons. Le rayon s'arrête au premier mur rencontré — il ne peut pas "voir à travers" pour détecter un deuxième niveau.

Plaçons le raycasting dans le contexte des techniques de rendu 3D disponibles à l'époque et aujourd'hui.

Le ray tracing est la technique de rendu 3D photoréaliste par excellence. Il simule physiquement le trajet de la lumière en lançant des rayons qui rebondissent sur les surfaces, calculant réflexions, réfractions, ombres portées et éclairage indirect. Le raycasting en est une version ultra-simplifiée : un rayon par colonne, pas de rebond, juste "premier mur touché".

• Ray Tracing : Rayons multiples par pixel, calcul de l'éclairage global, réflexions/réfractions infinies. Coût : O(millions de rayons × profondeur de rebond).
• Raycasting : Un rayon par colonne de pixels, pas de rebond, pas d'éclairage. Coût : O(largeur d'écran × distance moyenne au mur).

DOOM (1993) a abandonné le raycasting pur au profit des BSP trees. Cette approche permet des murs non-orthogonaux, des secteurs de hauteurs différentes, et des formes géométriques arbitraires. Le coût ? Une complexité algorithmique bien supérieure.

Les GPU modernes utilisent la rasterisation, l'inverse du raycasting : au lieu de lancer des rayons depuis l'œil, on projette des triangles 3D sur l'écran. C'est l'approche dominante depuis les années 2000 car elle parallélise parfaitement sur les architectures GPU.

Le raycasting est un exemple brillant d'optimisation créative. En exploitant les contraintes (monde en grille, murs verticaux, pas de pentes), John Carmack a créé une illusion de 3D qui a révolutionné le jeu vidéo.

Aujourd'hui, avec les GPU modernes, le ray tracing temps réel est devenu possible. Mais comprendre le raycasting reste essentiel : c'est une leçon magistrale sur comment contourner les limitations techniques par l'ingéniosité algorithmique.

• Wolfenstein 3D (1992) : Le premier FPS commercial utilisant le raycasting. A lancé le genre FPS et prouvé qu'un jeu 3D fluide était possible sur PC.
• DOOM (1993) : Évolution avec le BSP tree pour des niveaux non-orthogonaux. Conserve l'esprit du raycasting mais ajoute la flexibilité géométrique.
• Duke Nukem 3D (1996) : Moteur Build Engine avec secteurs inclinés, miroirs, pièces au-dessus d'autres pièces (portails).
• Comanche (1992) : Raycasting pour le terrain en voxels. Au lieu de murs, chaque rayon échantillonne une heightmap pour créer des paysages 3D.
• Ken's Labyrinth (1993) : Raycasting pur avec textures de sol/plafond.