Les moteurs de rendu des FPS en 2.5 D/Les généralités : le rendu 2D

Les tout premiers First Person Shooters, comme DOOM ou Wolfenstein 3D, avaient un rendu relativement simpliste. Et contrairement à ce que voient nos yeux, le rendu n'était pas de la vraie 3D, mais une méthode de rendu hybride entre 2D et 3D. Quelques rares moteurs utilisaient un moteur en 3D, avec rendu d'objets en polygones, comme le moteur d'Ultima Underworld, mais ils sont l'exception qui confirme la règle. Pour comprendre comment ces moteurs de rendu fonctionnaient, il faut faire une petite introduction sur les méthodes de rendu 3D en général.

Le rendu en 2.5D : les bases communes à tous les moteurs

Calculer un monde en 3D ou en 2.5D, demande de faire beaucoup de choses différentes : calculer la géométrie des niveaux, appliquer les textures sur les modèles 3D, calculer les lumières, les ombres, etc. La distinction entre géométrie, textures et éclairage est assez intuitive, surtout que les moteurs de jeu savent relativement bien gérer ces trois aspects. Voyons ce qu'il en est pour les jeux en 2.5D.

La géométrie, les niveaux, les objets et la caméra

Une map dans un FPS en 2.5D est un environnement en deux dimensions, à savoir qu'elle est décrite sur un plan 2D, 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. Ils ont une coordonnée bien précise, ce sont des points sur la map 2D.

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.

La géométrie du niveau est généralement très simple, à savoir qu'elle est composées de lignes, qui sont connectées entre elles et ne laissent pas de trous. Elles délimitent un espace fermé, le niveau, duquel on ne peut pas sortir. Pour donner un exemple, voici un exemple de map dans le jeu libre FreeDOOM :

Tous les jeux, sauf ceux utilisant le moteur de Wolfenstein 3D, découpaient la map en zone polygones appelées secteurs (dans la doc de DOOM) ou encore polygones (dans la doc du Build Engine). Par exemple, prenez un niveau qui se passe dans un bâtiment : chaque pièce aura une forme rectangulaire. Une pièce rectangulaire correspond à un polygone, dont les murs et la porte d'entrée sont représentés par une ligne. Mais des niveaux plus complexes, comme des forêts, des niveaux d'enfer ou autres, peuvent utiliser des polygones plus complexes.

Un secteur est globalement une pièce fermée, dont les ouvertures sont des portes, des fenêtres transparentes, des ouvertures vers l'extérieur, etc. Un secteur est définit plusieurs lignes qui ferment le secteur. Les murs qui l'entourent sont des lignes infranchissables, sauf à activer un cheat passe-muraille. D'autres lignes infranchissables permettent de définir des fenêtres et autre ouvertures qui permettent de voir une autre pièce ou l'extérieur. Mais il faut aussi utiliser une ligne pour chaque porte, qui sont cette fois-ci des lignes que le joueur peut traverser. De telles lignes franchissables sont nécessaires pour découper la map en polygones.

La caméra et l'écran

Outre les objets proprement dit, on trouve une caméra, qui représente les yeux du joueur. Cette caméra est définie au minimum par la position du joueur et la direction de son regard. La position du joueur est un simple point, avec donc deux coordonnées, mais la direction du regarde est un vecteur.

La caméra est complétée par le champ de vision du joueur (un angle). Il y a aussi un plan qui représente l'écran du joueur. En effet, vous êtes à une certaine distance de votre écran, et cela doit se refléter dans le jeu. Ce que vous voyez sur votre écran est une image, qui a la même résolution que votre écran. Et cette image est prise à une certaine distance de la caméra, qui correspond approximativement à la distance entre vous et l'écran, mais transposée dans le niveau du jeu. Si vous êtes à 50 cm de votre écran en moyenne, le plan correspondant à l'écran est lui aussi à l'équivalent de 50 cm dans le niveau.

Il faut noter que vu que le jeu est en 2D, la caméra est censée rester à l'horizontale. De nombreux FPS 2.5D, comme Wolfenstein 3D ou DOOM, ne permettent pas la visée libre, aussi appelée free look, à laquelle vous êtes habitués. Avec la visée libre, on peut regarder à gauche, à droite, mais aussi en haut et en bas. Mais vu que les jeux 2.5D ne sont pas de la vraie 3D, ils ne permettaient pas de regarder en haut et en bas. Les joueurs de DOOM savent que ces jeux utilisaient une mal-nommée "visée automatique" qui permettait de tirer sur des ennemis en hauteur ou en contrebas. Le regard restait à la verticale, mais les tirs touchaient les ennemis en haut ou en bas. Vous tiriez sur un mur, mais l'ennemi situé à la vertical du tir était touché.

Initialement, c'est comme cela que ça marchait, l'absence de visée libre était systématique. Mais quelques petites modifications des moteurs de rendu ont permis d'ajouter un système de visée libre aux moteurs de jeu en 2.5D. Des jeux comme Heretic ou Hexen en étaient capables. Cependant, cette visée libre n'est pas parfaite : la perspective est faussée. Le tout est illustré avec l'animation ci-dessous. A gauche, ce qu'on devrait obtenir avec un rendu en 3D, à droite le résultat avec un moteur de rendu en 2.5D.

Concrètement, l'astuce utilisée pour gérer la visée libre était rudimentaire. Le moteur rendait le jeu avec une résolution verticale plus importante que la normale, mais n'affichait que ce qui était dans une fenêtre de même résolution que l'écran. La fenêtre pouvait se déplace verticalement dans le framebuffer, afin de simuler un regard qui se déplace vers le haut ou le bas. Vous remarquez qu'à droite, le jeu se contente de déplacer l'image affichée sur la verticale, en la faisant monter ou descendre.

Un défaut ce cette méthode est qu'une ligne verticale reste verticale en regardant en haut ou en bas, au lieu de pencher comme à gauche. On devine assez facilement que le rendu en 2.5D se fait colonne par colonne, à savoir qu'on déplace verticalement les textures/murs/objets, sans gérer la moindre perspective en 3D. Et cela nous donne des indices sur la manière dont est réalisé un rendu en 2.5D. Le caractère colonne par colonne est primordial pour un rendu en 2.5D. Toujours est-il que cela permet de faire la différence entre un moteur en vraie 3D et en 2.5D :

La perspective est gérée en 2D avec un moteur 2.5D, ce qui pose des problèmes avec la perspective verticale

Les sprites et l'environnement

Un point important des FPS 2.5D est qu'ils font une distinction entre l'environnement et les objets/ennemis. L'environnement correspond au niveau lui-même. A l'écran, il correspond aux murs, au ciel, au sol, au plafond, etc. Il s'agit souvent d'éléments statiques, encore que certains jeux de l'époque avaient des environnement dynamiques. Duke Nukem 3D avait des éléments dynamiques, les maps pouvaient changer en temps réels, encore que tout était scripté. Mais pour simplifier, l'environnement sert de décor statique dans lequel on place des objets dynamiques.

Par contre, un niveau contient des éléments dynamiques qui ne peuvent pas être gérés par des scripts. Les ennemis, les objets, items, power-up, medikits et autres. Prenez un médikit pour vous soigner, il va disparaitre, et doit disparaitre en temps réel. Idem avec par exemple les ennemis : ils se déplacent en temps réel, on peut les tuer. Pour gérer ces éléments dynamiques, le jeu utilise des sprites, de simples images placées au-dessus de l'environnement. 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. Les objets sont de simples pancartes sur lesquelles on plaque une image.

Les sprites sont partiellement transparents, pour ne pas écraser l'environnement qui est derrière. Par exemple, prenez le sprite de Pacman ci-contre. Le Pacman jaune est colorié, mais tout ce qu'il y a autour est transparent. Vous ne le voyez pas car la transparence afficher la page web derrière, mais passer en dark mode ou en light mode et vous devriez voir que ce qu'il y autour du Pacman change de couleur avec l'arrière-plan.

Les ennemis sont généralement animés : ils bougent, ils sont "stun" quand on tire dessus, ils peuvent tirer des projectiles, ils ont une animation de mort, etc. Et il y a une animation pour chaque action. Pareil pour certains objets de l'environnement : pensez aux fameux barils explosifs qui explosent quand on tire dessus ! Ces animations sont réalisées en enchainant une succession de sprites, qui est toujours identique. Il suffit de dérouler la bonne succession de sprite et le tour est joué !

L'arme du joueur est aussi un sprite, qui est rendu comme tous les autres sprites. Mais il y a une différence avec les autres sprites : il est toujours à l'avant-plan, devant tout le reste de l'image. Et il en est de même pour le HUD, qui est souvent rendu avec des sprites 2D placés à l'avant-plan.

Un HUD de FPS normal ressemble à ce qu'il y a dans la capture d'écran à droite : quelques chiffres et icônes superposées sur le reste du rendu. Les icônes pour la vie, l'armure et les munitions ; ne sont ni plus moins que des sprites. Ce n'est pas évident, mais c'est pareil pour les chiffres. Le HUD est mis à jour à chaque fois que le joueur tire (compteur de munitions), perd de la vie, prend de l'armure, etc. Il est idéalement rendu à la toute fin du rendu, son sprite étant superposé à tout le reste.

Mais dans Wolfenstein 3D et quelques jeux anciens, on a ce qui est illustré dans l'animation de droite. Le HUD est un gros rectangle qui prend tout le bas de l'écran. On peut bouger autant qu'on veut, le bas de l'écran associé au HUD reste le même. Le HUD n'a pas de transparence, les textures et l'environnement se se voient pas à travers. Avec cette contrainte, on peut dessiner le HUD et le reste de l'image séparément. Le HUD est donc rendu à part du reste. Cela signifie aussi que l'image calculée est en réalité plus petite. Si le HUD prend 10% de l'écran, alors on a juste à dessiner les 90% restants. Sans cette contrainte, on doit calculer 100% de l'image, pour ensuite superposer un HUD partiellement transparent.

Le framebuffer et son remplissage

Le rendu calcule une image, qui est affichée à l'écran. Le rendu doit se faire de manière à avoir 30 images par secondes, voire plus, toujours est-il qu'un jeu affiche une succession ultra-rapide d'images qui donne une impression de mouvement. L'image à afficher est enregistrée soit dans la mémoire RAM de l'ordinateur, soit dans la mémoire vidéo. Toujours est-il qu'elle est mémorisée dans une portion de la mémoire dédiée, qui s'appelle le framebuffer.

Vous pouvez voir le framebuffer comme une sorte de tableau sur lequel le moteur du jeu dessine. Le tableau a la même taille que l'écran. Le tableau est en réalité un tableau de pixel, qui a la même résolution que l'écran. Par exemple, pour un écran de résolution 1920 par 1080, le framebuffer est un tableau rectangulaire de 1920 pixels de large et de 1080 pixels de haut. Le moteur du jeu dessine dans le frambuffer soit pixel par pixel, soit par blocs de pixels. Tours est-il qu'il colorie les pixels, il remplit chaque pixel du frambuffer avec une couleur.

Pour simplifier, le framebuffer est initialement vide, rempli avec une couleur d'arrière-plan. Le rendu s'effectue alors comme suit :

Le moteur graphique calcule une image sans les sprites, avec seulement l'environnement, et l'enregistre dans le framebuffer.
Puis, il dessine les sprites sur l'image de l'environnement, sauf là où les sprites sont transparents.
L'arme et le HUD étant à l'avant-plan, il sont rendus dans une phase à part du reste, souvent après ou avant tout le reste.

Le rendu d'un FPS en 2.5D est donc réalisé en deux-trois phases de dessin : le rendu de l'environnement, le rendu des sprites. Il y a parfois des étapes en plus. Par exemple, DOOM calcule l'environnement en deux phases : une pour dessiner les murs, une autre pour dessiner le sol et le plafond/ciel.

Le rendu des sprites : la mise à l'échelle

Cependant, il ne suffit pas de superposer des sprites sur l'environnement pour que cela fonctionne. Il faut aussi les mettre à l'échelle, en fonction de leur distance. Rappelons que plus un objet/ennemi est loin, plus il nous parait petit à l'écran. Et cela vaut pour les sprites, mais aussi pour les murs de l'environnement.

Les sprites doivent donc être mis à l'échelle suivant la distance : rapetissés pour les ennemis lointains, et zoomés pour les ennemis proches. Pour cela, on utilise une relation mathématique très simple : la loi de Thalès.

Dans un jeu vidéo, et comme dans le monde réel, si on multiplie la distance d'un objet par deux, trois ou quatre, celui-ci devient respectivement deux, trois ou quatre fois plus petit. Dit autrement, un objet de hauteur H situé à une distance D aura une hauteur perçue identique à celle d'un objet de hauteur double/triple/quadruple situé deux/trois/quatre fois plus loin. En clair, pour un objet de hauteur $h_{1}$ , situé à une distance $d_{1}$ , et un autre objet de hauteur $h_{2}$ et de distance $d_{2}$ , les deux auront la même hauteur perçue :

{\frac {h_{1}}{d_{1}}}={\frac {h_{2}}{d_{2}}}

Tout sprite est une image, avec une résolution. Elle a un certain nombre de pixels à l'horizontale, un autre à la verticale. La taille verticale en pixel du sprite dépend du sprite, mettons qu'elle est égale à 50 pixels de large pour 60 de haut. Il s'agit de la taille réelle du sprite déterminée lors de la conception du jeu (aussi bien en vertical et horizontal). Nous allons noter sa taille en vertical comme suit : $T_{s}$ .

Cette taille correspond à une distance précise. Pour un sprite 50 pixels de large pour 60 de haut, le sprite aura la même taille à l'écran à une certaine distance, que nous allons noter $D_{s}$ .

Maintenant, d'après la relation vue plus haut, on peut calculer la taille affichée à l'écran du sprite, notée H. Pour cela, il suffit de connaitre la distance D, et on a la relation :

{\frac {T}{D}}={\frac {T_{s}}{D_{s}}}

On peut la reformuler comme suit :

T=D\times {\frac {T_{s}}{D_{s}}}

Quelques multiplications, et le tour est joué. Le terme ${\frac {T_{s}}{D_{s}}}$ peut même être mémorisé à l'avance pour chaque sprite, ce qui économise quelques calculs.

Le rendu de l'environnement : le rendu des murs

Le rendu de l'environnement est assez simple. Il consiste à dessiner les murs dans le framebuffer, puis le ciel/plafond et le sol. Les deux sont souvent séparés, notamment dans le moteur de DOOM qui dessine les murs avant de dessiner les visplanes (ciel, plafond, sol). Par contre, Wolfenstein 3D fait le rendu colonne par colonne, sans distinguer les deux. Cependant, le rendu de l'environnement est gouverné par le rendu des murs. Pour simplifier, on dessine d'abord le mur, le plafond et le sol correspondent à ce qui reste une fois le mur rendu. Le ciel/plafond correspond à ce qui est au-dessus du mur, le sol est en-dessous.

Le rendu des murs est assez simple. Partons du principe que les murs ont une certaine hauteur, qui est encodée pour chaque mur. Aussi, le sol et le plafond sont plats. Le sol et le plafond peuvent avoir leur propre hauteur, mais laissons-cela de côté pour le moment. 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. À partir de ces contraintes et de la carte en 2D, le moteur graphique peut afficher des graphismes de ce genre :

Les murs aussi subissent un processus de mise à l'échelle, avec quelques subtilités. Partons du principe que le regard du joueur est à une hauteur fixe au-dessus du sol, généralement au milieu de l'écran. La taille du mur est mise à l'échelle en fonction de la distance, et on place le mur au milieu de l'écran. En pratique, c'est ce qui était dans Wolfenstein 3D, mais DOOM autorisait d'avoir des murs plus hauts que d'autres. Le mur n'était alors pas centré sur l'écran, mais dépassait plus vers le haut que vers le bas. Les maths pour ça sont assez simples, mais nous allons les mettre de côté.

Pour comprendre comment se fait la mise à l'échelle, nous allons voir deux cas : celui où l'écran est devant nous, perpendiculaire au regard. Nous verrons ensuite comment passer au cas général, où le mur est de biais. La raison est que le premier cas est plus simple et introduit les concepts importants pour comprendre le cas général.

Voyons d'abord le cas où vous avez un mur plat devant vous, à votre perpendiculaire. Le mur est rectangulaire, avec une certaine largeur et une certaine hauteur. Il occupe un certain rectangle à l'écran, vu qu'il est vu à la perpendiculaire, il n'y a pas d'angle. La hauteur du mur perçue sur l'écran dépend de sa distance, par effet de perspective : plus le mur est loin, plus le rectangle visible à l'écran sera petit. Il faut donc le mettre à l'échelle en fonction de sa distance. 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.

Mais il s'agit là d'un cas idéal. Dans le cas général, le mur est vu avec un certain angle. Et cet angle modifie implique un effet de perspective. Les portions du mur plus proche de nous seront perçues comme plus grandes, le mur donnera l'impression de rétrécir avec la distance. Le mur rectangulaire est alors un trapèze sur l'écran.

Pour gérer cela, il y a plusieurs méthodes. Wolfenstein 3D faisait le rendu colonne par colonne sur l'écran, et il calculait la hauteur perçue avec Thalès, pour chaque colonne de l'écran. Mais ce n'était possible que parce qu'il utilisait la technique du raycasting. Les autres jeux faisaient le rendu mur par mur. Pour chaque mur, ils calculaient la position des quatre sommets du trapèze qu'occupe le mur à l'écran, avec un algorithme de rastérisation. Puis la texture du mur était dessinée dans ce trapèze, après mise à l'échelle. Pour cela, prenaient la largeur du mur, sa position (à partir du milieu du mur), calculaient l'angle que fait le mur avec l'écran.

Les FPS 2.5D dessinaient les murs colonne par colonne. Le rendu était donc mur par mur, colonne par colonne. Le fait de rendre un mur colonne par colonne facilite la mise à l'échelle, qui se fait en modifiant la hauteur, donc la verticale du mur. D'ailleurs, afin de faciliter la mise à l'échelle, les textures sont mémorisées colonnes par colonnes en mémoire. Et même sur le disque dur, les fichiers WAD mémorisent les textures colonnes par colonne. L'habitude pour l'époque était de mémoriser les textures et images ligne par ligne, afin de faciliter l'affichage sur un écran CRT, qui affichait chaque image ligne par ligne, mais DOOM faisait l'inverse.

La détermination des surfaces visibles

Enfin, il faut parler d'un point très important, qui est absolument central pour le rendu 2D comme 3D : la visibilité des objets à l'écran. Un moteur de jeu doit déterminer ce qui est visible à l'écran : quels murs sont visibles, quels sont les objets visibles à l'écran, quels ennemis sont visibles, etc. Et cela regroupe trois choses différents :

Un objet/mur en-dehors du champ de vision doit être éliminé du rendu : c'est ce qu'on appelle le frustrum cliping.
Un objet/mur a une face visible et une face cachée qui fait dos à la caméra : la face cachée n'est pas rendue grâce à des techniques de back-face culling.
Si un objet/mur est masqué par un autre, totalement ou partiellement, il ne faut pas rendre ce qui est masqué. : on parle d'occlusion culling.

Et ce qui est intéressant, c'est que la détermination de la visibilité est un problème central, qui détermine comment fonctionne le moteur d'un jeu. Un moteur de jeu est souvent construit autour d'un algorithme qui détermine la visibilité des objets, le reste se greffant autour. Après tout, avant de se demander comment afficher quelque chose, le moteur doit d'abord savoir quoi afficher ! Les autres problèmes sont en quelque sorte secondaire, la manière dont un moteur de jeu fonctionne dans les grandes lignes est gouvernée par ce problème de visibilité.

A ce propos, il est intéressant de regarder ce qu'en dit Michael Abrash, un des programmeurs ayant codé les moteurs de Quake et d'autres jeux Id Software aux côtés de John Carmack, dont la postérité n'a pas retenu son nom. Voici une citation tirée de son livre "Graphics Programming Black Book Special Edition", où il parle de son expérience sur le moteur de Quake:

...but for the here and now I want to talk about what is, in my opinion, the toughest 3-D problem of all: visible surface determination (drawing the proper surface at each pixel), and its close relative, culling (discarding non-visible polygons as quickly as possible, a way of accelerating visible surface determination). In the interests of brevity, I’ll use the abbreviation VSD to mean both visible surface determination and culling from now on.

Why do I think VSD is the toughest 3-D challenge? Although rasterization issues such as texture mapping are fascinating and important, they are tasks of relatively finite scope, and are being moved into hardware as 3-D accelerators appear; also, they only scale with increases in screen resolution, which are relatively modest.

In contrast, VSD is an open-ended problem, and there are dozens of approaches currently in use. Even more significantly, the performance of VSD, done in an unsophisticated fashion, scales directly with scene complexity, which tends to increase as a square or cube function, so this very rapidly becomes the limiting factor in rendering realistic worlds. I expect VSD to be the increasingly dominant issue in realtime PC 3-D over the next few years, as 3-D worlds become increasingly detailed. Already, a good-sized Quake level contains on the order of 10,000 polygons, about three times as many polygons as a comparable DOOM level.

Voyons maintenant dans le détail comment la visibilité des objets/environnements est déterminée.

Les méthodes de détermination des surfaces visibles en 3D

Les solutions à ce problème de visibilité sont assez nombreuses. Heureusement, elles peuvent se classer en quelque grand types assez larges. Les techniques les plus utilisées sont le tampon de profondeur (z-buffer), le tri de polygones par profondeur (Depth sorting), le lancer de rayon (raytracing). Elles résolvent le problème de la visibilité d'une manière fort différente.

Les jeux 3D modernes utilisent un tampon de profondeur, aussi appelé z-buffer, car c'est une technique supportée par les cartes graphiques modernes. Elles peuvent donc l'utiliser avec de bonnes performances, vu que le GPU fait la grosse partie du travail. Mais les premières cartes graphiques ne géraient pas de tampon de profondeur, ce n'est que vers la fin des années 90 que la technique a été intégrée aux GPU. Et une implémentation logicielle du tampon de profondeur aurait été beaucoup trop lente.

A vrai dire, les GPU de l'époque ne géraient pas grand chose. Les cartes accélératrices 3D n'existaient pas encore et les GPU ne faisaient que de la 2D. Et cette 2D était souvent très rudimentaire. Les cartes graphiques des PC de l'époque étaient optimisées pour rendre du texte, avec un support minimal du rendu d'images par pixel. En conséquence, les jeux vidéos de l'époque devaient faire tous les calculs graphiques sur le CPU, on parlait alors de rendu logiciel, de rendu software. Et les contraintes faisaient qu'ils devaient utiliser des algorithmes particuliers pour résoudre la visibilité.

Le moteur de Wolfenstein 3D a été le seul à utiliser la technique du lancer de rayons, bien qu'adaptée à des maps 2D. Et encore, il ne l'utilisait que d'une manière bien particulière, avec des optimisations qui rendaient son calcul bien plus simple : les niveaux étaient alignés sur une grille 2D, le moteur découpait le niveaux en blocs de taille fixe, et j'en passe. Mais la technique était très gourmande en puissance de calcul. Mais le vrai problème est que les optimisations appliquées bridaient les concepteurs de niveaux. Impossible de faire autre chose qu'un labyrinthe aux murs à 90°...

Tous les autres jeux vidéos, que ce soit DOOM ou le Build engine, ou tous les autres moteurs de l'époque, utilisaient des méthodes dites de rendu ordonné, qui consistent à rendre les objets à rendre du plus proche au plus lointain ou inversement. La méthode la plus simple pour cela est celle de l’algorithme du peintre. Et les premiers FPS utilisaient une version fortement améliorée de cet algorithme.

L'algorithme du peintre : le rendu loin-vers-proche

Pour rappel, la base d'un rendu en 2D ou 2.5D est de superposer des images 2D pré-calculées les unes au-dessus des autres, pour obtenir l'image finale. Par exemple, on peut avoir une image pour l’arrière-plan (le décor), une image pour le monstre qui vous fonce dessus, une image pour le dessin de votre personnage, une image pour chaque mur, etc. L'image final est rendue dans une portion de mémoire RAM appelée le framebuffer, superposer une image dessus revient à la copier dans cette zone de mémoire. La copie peut être partielle ou totale, tout dépend des besoins.

Pour éliminer les surfaces cachées, la solution la plus simple consiste simplement à rendre les objets à rendre du plus lointain au plus proche. L'idée est que si deux objets se recouvrent totalement ou partiellement, on doit dessiner celui qui est derrière, puis celui qui est devant. Le dessin du second va recouvrir le premier. Il s'agit de l'algorithme du peintre.

Un problème est que la solution ne marche pas avec certaines configurations particulières, dans le cas où des polygones un peu complexes se chevauchent plusieurs fois. Il se présente rarement dans un rendu 3D normal, mais c'est quand même un cas qu'il faut gérer. Le problème est suffisant pour que cette solution ne soit plus utilisée dans le rendu 3D normal.

Avec l'algorithme du peintre, il arrive qu'on dessine des objets qui sont ensuite écrasés par un objet plus proche qui redessine par dessus. Ou encore, on dessine un objet en entier, mais une partie de celui-ci est ensuite masquée par un objet plus proche. On dessine donc inutilement. Et ces dessins correspondent à écrire des pixels dans le framebuffer, donc à de la puissance de calcul, des transferts mémoire inutiles. Des pixels sont écrits pour ensuite être écrasés. C'est le problème de l'overdraw, que nous traduiront en français par le volontairement ridicule terme de sur-dessinage. Mais ce défaut peut être mitigé avec une variante de l'algorithme du peintre, appelée l'algorithme du peintre inversé, qu'on va voir dans ce qui suit.

Il existe quelques jeux qui ont utilisé ce système de rendu. Par exemple, la version SP1 de DOOM utilise l'algorithme du peintre, contrairement à la version PC qui fonctionne totalement différemment.

L'algorithme du peintre inversé : le rendu proche-vers-lointain

Les anciens jeux en 2.5D comme DOOM ou les DOOM-like, utilisaient une variante de l'algorithme du peintre. L'idée était de rendre l'image dans le sens inverse de l'algorithme du peintre, à savoir du plus proche au plus lointain. En conséquence, nous allons la désigner sous le terme d'algorithme du peintre inversé. La technique fonctionnait car elle ne modifiait pas les portions de l'image déjà dessinée. Les techniques pour cela sont assez nombreuses, mais elles garantissaient que chaque pixel est écrit une seule et unique fois, le sur-dessinnage disparait ! L'avantage est que cet algorithme fait moins d'écriture.

Une des ces techniques mémorisait quelles pixels de l'image ont déjà été écrits, afin qu'ils ne soient pas modifiés ultérieurement. A chaque fois que le moteur de jeu veut modifier la couleur d'un pixel, il vérifie si celui-ci est déjà occupé ou s'il est vide. Le dessin du pixel ne se fait que s'il est vide. Ainsi, si on veut rendre un objet lointain partiellement caché par un objet proche, la portion non-cachée correspondra à une portion vierge de l'image, mais la portion cachée correspondra à une portion déjà écrite. La portion non-cachée écrira ses pixels dans le framebuffer, pas la portion cachée.

L'occlusion est donc gérée convenablement. Mais cela demande de mémoriser, pour chaque pixel, s'il a déjà été remplit ou s'il est vide. Pour cela, le moteur du jeu utilise un tableau d'occlusion, à savoir un tableau qui a les mêmes dimensions que l'écran, les mêmes dimensions que le framebuffer. Il mémorise, pour chaque pixel, s'il a déjà été remplis ou s'il est vide.

Cependant, l'algorithme du peintre inversé échoue si les objets rendus sont transparents. Dès que de la transparence est impliquée, l'algorithme du peintre inversé ne marche plus. DOOM gérait la situation assez simplement en mélangeant algorithme du peintre normal et inversé. les murs étaient rendus avec l'algorithme du peintre inversé, alors que les sprites et les murs transparents étaient rendus avec l'algorithme du peintre normal.

Les approximations rapides de l'algorithme du peintre

Un problème de l'algorithme du peintre est qu'il demande de trier les murs/sprites d'une scène selon leur profondeur, du plus profond au moins profond. Trier les polygones demande d'utiliser un algorithme de tri, qui est exécuté par le processeur. Le CPU est en effet plus efficace que le GPU pour trier des trucs. Par contre, le nombre d'opérations est assez important. Pour trier N entités, le temps de calcul est proportionnel à $N\times \log {N}$ , d'après la théorie de la complexité algorithmique.

Heureusement, quelques optimisations permettent de réduire ce nombre d'opération d'une manière assez drastique et de passer à un temps de calcul dit linéaire, simplement proportionnel à N. De plus, ces optimisations permettent de faire ce tri très facilement, sans avoir à tout retrier quand le joueur tourne la caméra ou se déplace. Par contre, ces optimisations font que l'ordre de rendu n'est pas parfaitement conservé. Les objets sont globalement rendus du plus proche au plus lointain, mais l'ordre est cependant approximatif. Les optimisations profitent du fait que dans certains cas, l'ordre de rendu n'a pas d'impact sur le rendu final.

De nombreux jeux de l'époque utilisaient néanmoins ces optimisations, car le gain en performance en valait la peine. Mais le défaut est que les approximations pouvaient occasionnellement causer quelques défauts d'affichage. Il arrivait que les objets deviennent visibles à travers des murs opaques ou invisibles à travers des surfaces transparentes. Mais ces artefacts graphiques étaient assez mineurs. Et la plupart du temps, c'était le signe que le concepteur du niveau avait laissé une coquille dans le niveau.

Une optimisation de ce type est l'usage du Binary Space Partionning. Concrètement, elle est utilisée pour précalculer des informations spatiales, qui permettent de trier les objets selon leur profondeur. Le BSP est formellement un arbre binaire dont le parcours permet de trier naturellement les objets/murs soit du plus proche au plus loin, soit, au contraire du plus loin au plus proche. Tout dépend de comment on le parcours, il y a deux méthodes différentes, une par sens de transfert. Elle a été utilisée dans le moteur de DOOM 1 et 2, qui étaient formellement en 2.5D, mais aussi dans des jeux 3D d'Id Software comme Quake 1, Quake 2, et même DOOM 3. DOOM PSX utilisait un BSP pour accélérer un rendu loin vers proche, alors que DOOM PC faisait l'inverse.

Les autres jeux en 2.5D de l'époque de DOOM faisaient autrement. Ils utilisaient la technique du portal rendering. Elle aussi précalculait des informations spatiales qui permettaient de trier naturellement les objets du plus lointain au plus proche. Pour simplifier, la map était coupées en pièces, connectées les unes aux autres par des portails. Il y avait un portail pour chaque porte, fenêtre, ouverture dans une pièce. Le moteur commençait le rendu dans la pièce actuellement occupée et rendait les objets. Puis, il déterminait les portalvisibles depuis la caméra, les portails visibles par le joueur. Pour chaque portail visible, il rendait alors la pièce voisine visible depuis ce portail et continuait récursivement le rendu dans les pièces voisines.

Le défaut du BSP est qu'ils marchent bien quand la géométrie du niveau est statique, qu'elle n'est pas modifiée. Par contre, si le niveau doit subir des modifications dynamiques, c'est plus compliqué. Avec un BSP, les niveaux dynamiques sont compliqués à concevoir, car modifier un BSP dynamiquement n'est pas chose facile. A la rigueur, si les modifications peuvent être scriptées, les choses sont plus faciles. Avec des portals, modifier un niveau est plus simple, plus facile.

Dans un FPS, il y a une classe d'objets qui ne peuvent pas être rendus avec la technique du BSP ou du portal rendering : les ennemis. Ils bougent d'une manière qui n'est pas prévue par un script, mais par un système d'IA, aussi rudimentaire soit-il. Impossible de précalculer le mouvement des ennemis ou autres. Autant les murs peuvent être rendus avec un BSP ou des portals, autant il faut trouver une autre solution pour les ennemis. La solution retenue est de rendre les ennemis à part du reste. DOOm faisait ainsi : il rendait les murs, puis les ennemis et autres objets basiques, en utilsant des sprites.

Le rendu des sprites se fait une fois que l'environnement a été dessiné, c'est à dire après les murs, le sol et les plafonds. Les sprites des ennemis et items sont donc superposé sur l'arrière-plan calculée par l'étape précédente. Cependant, certains sprites peuvent se recouvrir : il faut impérativement que le sprite le plus proche soit affiché au-dessus de l'autre. Pour cela, les sprites sont superposés avec l'algorithme du peintre, à savoir du plus lointain au plus proche, même si l'environnement est rendu dans l'autre sens. Faire demande évidemment de trier les sprites à rendre en fonction de la distance des objets/ennemis.

L'usage de l'alpha-testing pour le rendu des sprites

Néanmoins, précisons que ce n'est pas systématique, surtout sur le matériel moderne. Par exemple, DOOM a été porté sur de nombreuses machines, au point où le même "can it run DOOM ?" est né. Et chaque port utilise les possibilités du hardware pour simplifier le moteur. DOOM et Dukem 3D ont par exemple leurs ports sources qui fonctionnent avec au choix un rendu logiciel, ou un rendu sous Open Gl, voir parfois un rendu sous Vulkan pour les port source les plus avancés. Ils peuvent alors profiter des fonctionnalités du matériel moderne pour simplifier le rendu.

La plupart des ports altèrent fortement le rendu des sprites. Les ports source modernes ne se préoccupent pas de rendre les sprites dans l'ordre, du plus lointain au plus proche. En effet, les cartes graphiques gérent la transparence nativement. Elles peuvent superposer plusieurs sprites ou textures partiellement transparents, dans le framebuffer, grâce à une technique appelée l'alpha blending. En conséquence, les sprites sont rendus dans le désordre, sans que cela ne pose le moindre problème.

Un exemple est le cas du portage de DOOM sur iPhone, qui rend les textures dans un ordre tout sauf intuitif. Les textures du jeu sont numérotées, chacune ayant un identifiant de texture ou Texture ID. Le jeu rend les textures par Texture ID croissant, sans se préoccuper de leur profondeur. Au passage, le processus est illustré dans les animations à la fin de cet article, qui décrit en détail le fonctionnement de ce portage : [1].

◄ Retour vers « L'historique des moteurs de FPS »

Sommaire du livre

Continuer vers « Le moteur de Wolfenstein 3D » ►