Le ray-casting : les graphismes de DOOM et W3D

DOOM, Wolfenstein 3D, et les autres jeux de l'époque avaient un rendu relativement simpliste, anguleux, et osons le dire : moche d'après les standards actuels. Le rendu n'était pas totalement en 3D, le meilleur moyen pour s'en rendre compte étant de tourner autour d'un objet : la forme de l'objet ne change pas du tout. On s’aperçoit rapidement que les objets sont de simples images, placées au-dessus du décor : ce sont des sprites. J'ai déjà parlé de ces sprites dans mon tutoriel sur les cartes graphiques, aussi je passe cette partie du moteur graphique sous silence.

Mais bizarrement, ce n'est pas la même chose pour les murs : un déplacement dans la map change la forme des murs, comme si le décor était en 3D. En réalité, cette 3D des murs est simulée, par un mécanisme différent de celui utilisé pour représenter les objets et ennemis. Et oui, c'est choquant, mais c'est la vérité : les moteurs des vieux jeu utilisent des méthodes de rendu différentes pour les murs et les items/ennemis. Plus précisément, les moteurs de DOOM et autres utilisaient du ray-casting pour les murs, et des sprites pour les items et objets.

La map et le joueur : de la 2D pure

Avec cette méthode, la map doit respecter quelques contraintes :

• la map est un labyrinthe, avec des murs impossibles à traverser ;
• tout mur est composé de carrés de taille fixe sur la map 2D ;
• la map n'a qu'un seul niveau : pas d'escaliers, d'ascenseurs, ni de différences de hauteurs (du moins, sans améliorations notables, comme on en trouve dans le moteur de DOOM).

Si elle respecte ces contraintes, on peut la représenter en 2D, avec un simple tableau à deux dimensions, comme on en trouve dans tous les langages de programmation dignes de ce nom. Chaque case du tableau indique la présence d'un mur avec un bit (qui vaut 1 si le carré est occupé par un mur, et 0 sinon).

Le joueur n'est qu'un point dans la map, qui a une position X et Y. Pour calculer le rendu final, le jeu a besoin de connaître la direction du regard, en fonction des informations envoyées par la souris et de la direction précédente. Pour faire simple, le joueur est juste un vecteur dans cette scène, dont l'origine est la position du joueur et la direction est celle du regard. Ce que voit le joueur est définit par

• un angle (le champ de vision, ou FOV) ;
• et une ligne qui est l'équivalent 2D de ce que voit le joueur sur l'écran (l'écran est située à une certaine distance du joueur).

Ce qui correspond à l'écran correspond à un plan dans un monde 3D, qui est situé à une certaine distance de la caméra, cette distance étant fixée une fois pour toute. Dans le cas du ray-casting, ce plan devient une simple ligne, vu que la map est en 2D.

Simuler la verticale

Si la map est en 2D, sa représentation 3D doit être reconstruite à partir de l'image 2D de la map, et ajoutant des informations verticales. Pour simuler la verticale, le ray-casting a besoin de quelques contraintes sur la scène 3D à simuler :

• le sol et le plafond sont parfaitement plats ;
• tous les murs font un angle de 90° avec le sol et le plafond ;
• tous les murs du jeu sont supposés avoir la même hauteur ;
• le regard du joueur est situé à une hauteur fixe, généralement la moitié de la hauteur d'un mur : on ne peut pas sauter ni s'accroupir (c'est pour cela que l'on ne peut pas sauter dans DOOM).

Quelques jeux ont permis de se passer de ces contraintes, et de rajouter des textures sur les murs, ou de simuler des murs transparents et des miroirs. A partir de ces contraintes et de la carte en 2D, le moteur graphique peut afficher des graphismes de ce genre :

Calcul de la hauteur percue

Le principe de ce rendu est simple : on trace une colonne de pixels à la fois, chaque colonne étant coloriée indépendamment des autres. Il suffit de connaitre la hauteur du mur vue depuis l'écran, pour colorier convenablement une colonne : cette hauteur sera appelée la hauteur perçue dans ce qui va suivre.

Vu qu'on a supposé plus haut que la hauteur du regard était égale à la moitié de la hauteur d'un mur, on sait que le mur sera centré sur l'écran : il suffit de colorier avec la couleur du mur les pixels situés entre [ Hauteur du regard - ( hauteur du mur / 2) , Hauteur du regard + ( hauteur du mur / 2) ]. Les pixels situés au-dessus de cet intervalle correspondent au plafond, et sont colorié avec la couleur du plafond (souvent du bleu pour simuler le ciel). Les pixels dont les cordonnées verticales sont en-dessous de cet intervalle sont ceux du sol, et ils sont coloriés avec la couleur du sol.

La hauteur du mur perçue sur l'écran dépend de sa distance, par effet de perspective : plus un mur est proche, plus il paraitra "grand". Plus précisément, la hauteur perçue peut se calculer en utilisant le théorème de Thalès, comme illustré par le schéma ci-dessous. Si on pose $d_e$ la distance de l'écran, $d_m$ la distance du mur dans la scène 2D, $h_p$ la hauteur perçue du mur, et $h_m$ la hauteur réelle du mur, on sait que : $\frac{h_p}{d_e} = \frac{h_m}{d_m}$. Donc, on a : $h_p = d_e \times \frac{h_m}{d_m}$

Dans l'équation vue plus haut, la hauteur d'un mur $h_m$ est connue : on a supposé plus haut que tous les murs ont la même hauteur, qui fait partie des paramètres du jeu. De même, la distance entre écran et caméra est connue, et fait aussi partie des constantes du jeu. Il reste juste à calculer la distance entre le mur et la caméra pour pouvoir faire le calcul.

Calcul des distances avec le mur

Cependant, il faut remarquer que la distance $h_m$ dépend de l'endroit dans le champ de vision : elle varie rapidement suivant la structure de la map, l’angle avec lequel on regarde un mur, etc. Le calcul de distance doit donc s'effectuer pour toute portion verticale visible du champ de vision, c'est à dire : pour chaque colonne de pixels.

Pour cela, il va déterminer une ligne (un rayon)qui passe par le joueur et la colonne de pixel. Ce calcul de rayons est fait non pas pour tout pixel, mais pour toute colonne de pixel à l'écran : par exemple, pour une résolution de 320 par 240, il faudra lancer 320 rayons. Pour faire ce lancer de rayons, le moteur doit connaitre la direction du regard, la taille du champ de vision (un angle souvent fixé une fois pour toute par le moteur du jeu), et la résolution horizontale de l'écran.

Une fois ces lignes connues, il faut ensuite déterminer les coordonnées :

• du joueur, la position de la caméra ;
• l'intersection entre la ligne et le mur le plus proche.

Une fois ces deux coordonnées connues, calculer la distance revient à déterminer la distance entre deux points à partir de leurs coordonnées, ce que l'on sait faire depuis le collège : il faut calculer la différence des abscisses et des ordonnées, avant d'appliquer le théorème de Pythagore.

La position du joueur est connue : elle est initialisée par défaut à une valeur bien précise au chargement de la map (on ne réapparait pas n'importe où), et est mise à jour à chaque appui sur une touche de déplacement (avancer, reculer, strafer). Ce n'est pas le cas de la direction du mur, qui doit être calculée. L'algorithme utilisé pour calculer les intersections avec les murs est un algorithme nommé " Digital Differential Analyser ", qui calcule séparément les coordonnées horizontales et verticales de l'intersection.

Pour résumer, le moteur graphique doit :

• déterminer les équations des lignes à partir de la direction du regard ;
• détecter les intersections de ces lignes avec les murs ;
• en déduire les distances entre joueur et murs ;
• appliquer Thalès pour calculer la hauteur perçue du mur ;
• déterminer les couleurs des murs, du plafond, et du sol (avec ou sans usage de textures) ;
• etc.

Correction de perspective

En faisant ainsi, on obtient un rendu en œil de poisson (fish-eye), assez désagréable à regarder.

En soit, nous n'avons rien fait de mal, et les équations sont correctes. D'ailleurs, les poissons voient leur environnement ainsi (d'où le nom d'effet d’œil de poisson). Le problème est que les rayons du bord du regard parcourent une distance plus grande que les rayons situés au centre du regard. Ainsi, si on regarde un mur à la perpendiculaire, les bords seront situées plus loin que l'endroit au centre du regard : ils paraîtront donc plus plus petits.

Les humains disposent d'une lentille dans leur œil pour corriger cet effet d'optique (le cristallin). Il faut donc simuler l'effet de cette lentille en logiciel, sans quoi le rendu sera faussé par cet effet d’œil de poisson. Ainsi, dans le schéma qui suit, tous les rayons bleus doivent donner l'impression d'avoir la même longueur que le rayon rouge.

Pour comprendre quel calcul effectuer, il faut faire un peu de trigonométrie. Vous remarquerez que le rayon bleu et le rayon rouge forment un triangle rectangle avec un pan de mur. Dans ce cas, la hauteur corrigée (rayon rouge) peut se calculer avec des identités trigonométriques.

On sait que par définition, le cosinus de l'angle a est égal au rapport entre le rayon rouge et le rayon bleu d'où on en déduit que : $l_{rouge] = l_{bleu} \times cos{a}. On peut donc calculer la hauteur corrigée en multipliant la distance obtenue avec Thalès par le cosinus de l'angle entre le rayon et la perpendiculaire au mur. Le rendu est alors correct.