Les moteurs de rendu des FPS en 2.5 D/Le moteur de Wolfenstein 3D
Le moteur de Wolfenstien utilisait toutes les techniques du chapitrre précédent pour rendre ses graphismes. Mais il nous reste à voir comment il faisait pour rendre les murs, le plafond et le sol, et les environnements en général. Tout le reste est réalisé avec des sprites, mais pas l'environnement en 2.5D.
Le ray-casting : l’algorithme général
modifierPour les murs, la 3D des murs est simulée par un mécanisme différent de celui utilisé pour les objets et ennemis. Le principe utilisé pour rendre les murs s'appelle le ray-casting. Il s'agit d'un rendu foncièrement différent de celui des sprites. Formellement, le ray-casting est une version en 2D d'une méthode de rendu 3D appelée le lancer de rayons. Mais avant de détailler cette méthode, parlons de la caméra et des maps de jeux vidéo.
La map et la caméra
modifierUne map dans un FPS en 2.5D est un environnement totalement en deux dimensions, dans lequel le moteur d’un jeu vidéo place des objets et les fait bouger. Cette scène est, en première approche, un simple rectangle. Un des coins de ce rectangle sert d’origine à un système de coordonnées : il est à la position (0, 0), et les axes partent de ce point en suivant les arêtes.
Dans cette scène 2D, on place des murs infranchissables, des objets, des ennemis, etc. Les objets sont placés à des coordonnées bien précises dans ce parallélogramme, pareil pour les murs. Le fait que la scène soit en 2D fait que la carte n'a qu'un seul niveau : pas d'escalier, d'ascenseur, ni de différence de hauteur. Du moins, sans améliorations notables du moteur graphique. Il est en fait possible de tricher et de simuler des étages, mais nous en parlerons plus tard. Pour donner un exemple, voici un exemple de map dans le jeu libre FreeDOOM :
Outre les objets proprement dit, on trouve une caméra, qui représente les yeux du joueur. Cette caméra est définie par :
- une position ;
- par la direction du regard (un vecteur) ;
- le champ de vision (un angle) ;
- un plan qui représente l'écran du joueur.
L'algorithme de raycasting : du lancer de rayon simplifié
modifierLe ray-casting colorie une colonne de pixels à la fois sur l'écran. Pour cela, on émet des lignes droites, des rayons qui partent de la caméra et qui passent chacun par une colonne de pixel de l'écran.
Les rayons font alors intersecter les objets, les items, mais aussi les murs, comme illustré ci-contre. Le moteur du jeu détermine alors, pour chaque rayon, quel est le point d'intersection le plus proche. Les coordonnées du point d'intersection sont calculées à l'aide d'un algorithme spécialisé, qui varie selon la méthode de raycasting utilisée.
Une fois le point d'intersection connu, on peut alors déterminer la distance de l'ennemi/item/mur. Rien de plus simple : il suffit de récupérer la coordonnée de ce point d'intersection, celle du joueur, et d'appliquer le théorème de Pythagore. Si le joueur est à la position de coordonnées (x1 ,y1), et l'intersection aux coordonnées (x2, y2), la distance D se calcule avec cette équation :
La position du joueur est connue : elle est initialisée par défaut à une valeur bien précise au chargement de la carte (on ne réapparait pas n'importe où), et est mise à jour à chaque appui sur une touche de déplacement. On peut alors calculer la distance très simplement. Une fois la distance connue, on peut déterminer la taille des sprites, des murs, et de tout ce qu'il faut afficher.
Le rendu de l'environnement : murs, sol et plafond
modifierLe rendu du sol et des plafonds est assez simple et est effectué avant tout le reste. Le sol a une couleur bien précise, pareil pour le plafond. Elle est la même pour tout le niveau, elle ne change pas quand on change de pièce ou qu'on se déplace dans la map. Le sol et le plafond sont dessinés en premier, et on superpose les murs dessus. Le dessin du sol et du plafond est très simple : on colorie la moitié haute de l'écran avec la couleur du plafond, on colorie le bas avec la couleur du sol, et on ajoute les murs ensuite.
Passons maintenant au rendu des murs. Et il faut maintenant préciser que le rendu est simplifié par plusieurs contraintes. La première est que l'on part du principe que tous les murs ont la même hauteur. En conséquence, le sol et le plafond sont plats, les murs font un angle de 90° avec le sol et le plafond. La seconde contrainte est que le regard du joueur est à une hauteur fixe au-dessus du sol, généralement au milieu de l'écran. Cela garantit que le plafond est situé au sommet de l'écran, le sol est en bas de l'écran, et les murs sont au milieu. Mais cela implique l'impossibilité de sauter, s'accroupir, lever ou baisser le regard. À partir de ces contraintes et de la carte en 2D, le moteur graphique peut afficher des graphismes de ce genre :
Le mur est centré au milieu de l'écran, vu que le regard est au milieu de l'écran et que tous les murs ont la même hauteur. Par contre, la hauteur du mur perçue sur l'écran dépend de sa distance, par effet de perspective. C'est comme pour les sprites : plus ils sont loin, plus ils semblent petits. Et bien plus un mur est proche, plus il paraîtra « grand ». La formule pour calculer la taille d'un mur à l'écran est la même que pour les sprites : on utilise le théorème de Thalés pour calculer la taille du mur à l'écran.
Vu qu'on a supposé plus haut que la hauteur du regard est égale à la moitié de la hauteur d'un mur, on sait que le mur sera centré sur l'écran. Les pixels situés au-dessus de cet intervalle correspondent au plafond : ils sont coloriés avec la couleur du plafond, souvent du bleu pour simuler le ciel. Les pixels dont les coordonnées verticales sont en dessous de cet intervalle sont ceux du sol : ils sont coloriés avec la couleur du sol.
La taille du mur est calculée pour chaque colonne de pixel de l'écran. Ainsi, un même mur vu d'un certain angle n'aura pas la même taille perçue : chaque colonne de pixel donnera une hauteur perçue différente, qui diminue au fur et à mesure qu'on s'éloigne du mur.
La correction d'effet fisheyes
modifierL'algorithme utilisé ci-dessus donne ce genre de rendu :
Le rendu est assez bizarre, mais vous l'avez peut-être déjà rencontré. Il s'agit d'un rendu en œil de poisson (fish-eye), assez désagréable à regarder. Si ce rendu porte ce nom, c'est parce que les poissons voient leur environnement ainsi. Et certaines caméras ou certains appareils photos peuvent donner ce genre de rendu avec une lentille adaptée.
Pour comprendre pourquoi, imaginons que nous regardions un mur sans angle, le regard à la perpendiculaire d'un mur plat. Les rayons du bord du regard parcourent une distance plus grande que les rayons situés au centre du regard. Si on regarde un mur à la perpendiculaire, les bords seront situés plus loin que le centre : ils paraîtront plus petits. Prenons un joueur qui regarde un mur à la perpendiculaire (pour simplifier le raisonnement), tel qu'illustré ci-dessous : le rayon situé au centre du regard sera le rayon rouge, et les autres rayons du champ de vision seront en bleu.
Pourtant, nous sommes censés voir que tous les points du mur sont situés à la même hauteur. C'est parce que les humains ont une lentille dans l'œil (le cristallin) pour corriger cet effet d'optique, lentille qu'il faut simuler pour obtenir un rendu adéquat.
Pour comprendre quel calcul effectuer, il faut faire un peu de trigonométrie. Reprenons l'exemple précédent, avec un regard perpendiculaire à un mur.
Or, vous remarquerez que le rayon bleu et le rayon rouge forment un triangle rectangle avec un pan de mur.
Pour éliminer le rendu en œil de poisson, les rayons bleus doivent donner l'impression d'avoir la même longueur que le rayon rouge. Dans un triangle rectangle, le cosinus de l'angle a est égal au rapport entre le côté adjacent et l'hypoténuse, qui correspondent respectivement au rayon rouge et au rayon bleu. On en déduit qu'il faut corriger la hauteur perçue en la multipliant par le cosinus de l'angle a.
Les textures des murs
modifierLe ray-casting permet aussi d'ajouter des textures sur les murs, le sol, et le plafond. Comme dit précédemment, les murs sont composés de pavés ou de cubes juxtaposés. Une face d'un mur a donc une hauteur et une largeur. Pour se simplifier la vie, les moteurs de ray-casting utilisent des textures dont la hauteur est égale à la hauteur d'un mur, et la largeur est égale à la largeur d'une face de pavé/cube.
En faisant cela, chaque colonne de pixels d'une texture correspond à une colonne de pixels du mur sur l'écran (et donc à un rayon lancé dans les étapes du dessus).
Reste à trouver à quelle colonne de texture correspond l'intersection avec le rayon, et la mettre à l'échelle (pour la faire tenir dans la hauteur perçue). L'intersection a comme coordonnées x et y, et est située soit sur un bord horizontal, soit sur un bord vertical d'un cube/pavé. On sait que les murs, et donc les textures, se répètent en vertical et en horizontal toutes les lmur (largeur/longueur d'un mur).
En conséquence, on peut déterminer la colonne de pixels à afficher en calculant :
- le modulo de x avec la longueur du mur, si l'intersection coupe un mur horizontal ;
- le modulo de y avec la largeur d'un mur si l'intersection coupe un mur vertical.
Le raymarching de Wolfenstein 3D
modifierLe ray-casting est très gourmand en calculs, surtout pour les ordinateurs de l'époque. Aussi, pour Wolfenstein 3D, la map a quelques contraintes pour rendre les calculs d'intersection plus simples. Déjà, la carte est un labyrinthe, avec des murs impossibles à traverser. Les murs sont fixes, on ne peut pas les changer à la volée.
Mais surtout : tout mur est composé en assemblant des polygones tous identiques, généralement des carrés de taille fixe. La totalité des lignes du niveau qui délimitent les murs sont perpendiculaires, leurs semgnets sont tous orientés nord-sud ou ouest-est. Si elle respecte ces contraintes, on peut la représenter en 2D, avec un tableau à deux dimensions, dont chaque case indique la présence d'un mur avec un bit (qui vaut 1 si le carré est occupé par un mur, et 0 sinon).
De telles contraintes permettent de fortement simplifier l’algorithme de raycasting, au point où il en est méconnaissable. Sans cela, Wolfenstein 3D n'aurait pas réussit à tourner sur les PCs de l'époque. Dans ce qui suit, nous allons détailler l'algorithme général de raycasting, avant de voir comment il a été modifié pour Wolfenstein 3D.
L'algorithme de calcul d'intersection
modifierEn faisant ainsi, le calcul des intersections est grandement simplifié. L'idée est de partir de la position du joueur et de sauter d'une unité de distance. L'unité de distance est la largeur/longueur d'une case de la map, d'un carré. On part donc de la position du joueur et on se déplace d'une unité en suivant la direction du rayon : cela demande juste de faire une addition vectorielle. Là, on vérifie si le point se situe dans un mur ou non. Si c'est le cas, on calcule le position de l'intersection entre le rayon et le carré du mur en question. Si ce n'est pas le cas, on poursuit d'une unité supplémentaire.
Pour résumer, on avance pas par pas à partir de la caméra, et on s'arrête quand on est dans un mur. Cette idée est très simple, mais elle rate certaines intersections avec des géométries de murs un peu tordues. Aussi, le moteur de Wolfenstein 3D utilisait une autre méthode. Avec elle, les coordonnées du point d'intersection sont calculées à l'aide d'un algorithme nommé Digital Differential Analyser, décrit en détail dans ce lien :
L'application des textures
modifierLes calculs pour appliquer des textures sont grandement simplifiés avec le raymarching. Pour se simplifier la vie, les moteurs de ray-casting utilisent des textures dont la hauteur est égale à la hauteur d'un mur, et la largeur est égale à la largeur d'une face de pavé/cube. En faisant cela, chaque colonne de pixels d'une texture correspond à une colonne de pixels du mur sur l'écran (et donc à un rayon lancé dans les étapes du dessus). La seule difficulté est de trouver à quelle colonne de texture correspond l'intersection avec le rayon, et la mettre à l'échelle (pour la faire tenir dans la hauteur perçue).
L'intersection a comme coordonnées x et y, et est située soit sur un bord horizontal, soit sur un bord vertical d'un cube/pavé. On sait que les murs, et donc les textures, se répètent en vertical et en horizontal toutes les lmur (largeur/longueur d'un mur). En conséquence, on peut déterminer la colonne de pixels à afficher en calculant :
- le modulo de x avec la longueur du mur, si l'intersection coupe un mur horizontal ;
- le modulo de y avec la largeur d'un mur si l'intersection coupe un mur vertical.
Sources
modifierPour en savoir plus sur les moteurs de ce jeu, je conseille vivement la lecture du Black Book rédigé par Fabien Sanglard, et ses articles de blog :