Le ray-casting : les graphismes de DOOM et W3D

a marqué ce sujet comme résolu.
Auteur du sujet

Bonjour à tous. J'ai commencé il y a peu la rédaction d'un article sur le ray-casting, une technique utilisée par les moteurs 3D des anciens jeux pour donner une illusion de 3D. Celle-ci était utilisée par les moteurs des jeux DOOM et Wolfenstein 3D. L'article rédigé est placé dans la balise secret ci-dessous. J'attends des retours, ayant rédigé le tout rapidement, et n'ayant pas vraiment travaillé la pédagogie.

EDIT : corrections effectuées depuis le dernier message de Kje.

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).

Une map fictive d'un jeu avec ray-casting - couleurs = zones visitables et items

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 :

Principe du ray-casting

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.

Calcul de la couleur d'une colonne

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}$

Taille des murs à l'écran en fonction de la distance

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.

Distance en fonction de la position dans le champ de vision

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.

Lancer de rayon

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.

Effet de rendu en œil de poisson

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.

Origine de l'effet de vision en fish-eye

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.

Correction de perspective

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.

Triangle formé par le champ de vision et le mur

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.

Rendu correct, sans effet d’œil de poisson

Édité par anonyme

+0 -0

Avant tout je dois dire que je trouve le sujet vraiment interessant. Je me rappel avoir fait mon propre petit moteur de ray-casting il y a plusieurs années, c'est drôle à faire. Ensuite quelques remarques rapide :

Tu mélange l'utilisation de carte et de map dans le texte, peut être qu'une uniformisation serait intéressante.

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.

Au lieu de la direction précédente ce ne serait pas la position du joueur ?

Je trouve tes explications mathematiques un peu rapide. Certaines sont très rapidement donné sans vraiment d'explication.

Enfin on reste un peu sur notre fin. Il manque peut être une partie supplémentaire.

En tout cas c'est un bon sujet et il est bien illustrer dans l'ensemble.

+1 -0

Hello,

J'ai pris ton sujet en validation, mais comme ce topic existe, je vais en profiter pour l'utiliser, ce sera plus simple :)

Remarques générales

Tu as là un bon sujet bien illustré et plutôt clair. Néanmoins pour moi il reste quelques améliorations à faire avant que ce soit publiable.

  • Comme Kje, j'ai l'impression qu'il manque quelque chose, notamment dans les paragraphes des textures et celui des sprites.
  • De la même manière, tu passes très rapidement sur certains points mathématiques (l'application de la déformation fish-eye entre autres)
  • Ton style, et donc la qualité de lecture de tes écrits, gagnerait pas mal à simplifier certaines phrases. Exemple : " Mais quand on regarde les graphismes des anciens jeux, il devient rapidement évident que leurs murs sont recouverts de textures." (le gras est de moi).
  • Si tu connais des ressources permettant de coder facilement un moteur de ray-casting, ça peut être intéressant de les donner en fin d'article, parce que c'est simple à faire et permet de mettre tout ça en pratique.

Retours au fur et à mesure de la lecture

  • Personnellement je connais les jeux dont tu parles pour y avoir joué, mais ça risque de ne pas être le cas de bon nombre de nos lecteurs. Une indication sur l'année et un exemple de rendu (cf Freedoom, un screenshot ici) permettrait sans doute de mieux comprendre de quoi on parle sans avoir joué à ces jeux.
  • Il reste encore un "carte" dans le texte. Personnellement j'ai du mal à comprendre pourquoi tu utilises le terme anglais "map", mais ce n'est pas critique.
  • N'hésite pas à utiliser les formules mathématiques en ligne quand le cas se présente $ ta formule $ (c'est parfois fait et parfois non)
  • Si tu as des formules mathématiques sur plus de 1 ligne (typiquement des division) mieux vaut les mettre sur un paragraphe isolé, sinon elles sont vraiment très petites à lire.
  • Le "etc." dans le résumé est très étrange. Soit il veut dire "recommencer la procédure" auquel cas il faut dire ça, soit il manque des éléments et il faut les indiquer.

Comme d'hab, je reste à ta disposition pour parler de tout ça et en discuter si tu veux (ici ou en MP).

Auteur du sujet

Le problème, c'est que je ne vois pas quoi ajouter sur les textures (j'ai quand même une petite idée pour les sprites), et encore moins ce qu'il faudrait développer dans les explications mathématiques… Je veux dire, il ne s'agit que d'applications très simples de théorèmes connus depuis le collège : ce devrait être totalement intuitif.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte