Ceci est la version imprimable de Les moteurs de rendu des FPS en 2.5 D.

Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.

Les moteurs de rendu des FPS en 2.5 D

Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Les_moteurs_de_rendu_des_FPS_en_2.5_D

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

L'historique des moteurs de FPS

Dans les années 2000, le FPS a subit de nombreuses transformations. Des Fast-FPS d'antan, nerveux et aux maps non-linéaires et "labyrinthiques", ont été progressivement passé à des jeux plus lents, plus scénarisés, plus scriptés, aux maps plus linéaires. Les FPS datant d'avant l'arrivée de la 3D ont marqué leur époque pour leur gameplay très nerveux, très bourrin, avec une grande variété d'armes et de déplacements, et des maps complexes et non-linéaires, qu'on ne retrouve plus dans les jeux vidéos d'aujourd'hui. C'en est au point où les FPS d'antan sont actuellement appelés des Boomer-shooters, terme quelque peu cavalier auquel nous préférerons le terme de Fast-FPS, en opposition aux Slow-FPS d'aujourd'hui. Les fast-FPS, aussi appelés Boomer-FPS, regroupent de nombreuses sagas : les DOOM (sauf le 3), les Quake, les Unreal (sauf le 2), Duke Nukem en FPS, les Serious Sam, Heretic/Hexen, Marathon, Tribes, etc.

L'histoire du FPS est intimement lié à celle des moteurs graphiques. L'invention des premiers FPS va de pair avec la création des premiers moteurs capables de rendre respectivement de la 2.5D et ensuite de la 3D. Après tout, difficile de faire de la vue subjective si l'on ne sait pas effectuer un rendu en 3D en temps réel. La technologie a donc joué un rôle déterminant au début du FPS. Et nous allons étudier les moteurs de ces vieux jeux en 2.5D.

Un aperçu des moteurs de jeux de l'époque

Il y a eu beaucoup de FPS en 2.5D et beaucoup utilisaient des moteurs graphiques fait maison. A l'époque, le marché des moteurs graphiques n'était pas concentré autour de quelques acteurs. Les entreprises utilisaient souvent leur propre moteur fait maison, elles n'hésitaient pas coder leur moteur dans leur coin. La technologie était assez rudimentaire pour qu'une équipe de quelques développeurs arrive à coder un moteur maison assez simple, mais optimisé et capable de rendre des graphismes impressionnants pour l'époque.

Mais cela ne signifie pas que ces moteurs n'étaient pas licenciés pour être utilisés par d'autres entreprises pour qu'elles fassent des jeux avec. Par exemple, le moteur de Wolfenstein 3D a été utilisé pour une dizaine de productions, le moteur de DOOM a été utilisé pour pas mal de doom-clones de l'époque, le moteur Build n'a été utilisé que pour trois jeux, etc. Les autres moteurs n'ont été utilisés que par leur entreprise créatrice, l'exemple type étant celui du moteur de Marathon, ou encore le Jedi Engine.

La variété des moteurs graphiques de l'époque se reflétait dans les méthodes utilisées pour calculer les images à afficher. Il existait des moteurs en vraie 3D, dès les années 90 : L'histoire a retenu que Quake était le premier jeu en vraie 3D temps réel, quelques personnes n'oublient pas que Mario 64, sorti un jour après Quake, avait de la vraie 3D texturée. Mais en réalité, le tout premier moteur graphique en vraie 3D date de 1983, avec le jeu I Robot sur borne d'arcade. C'était de la 3D non-texturée, mais de la vraie 3D quand même. En sortant du monde des salles d'arcade, le Freescape 3D engine, datant de 1987, a servi pour quelques jeux sortis sur PC -DOS, mais aussi sur Amiga, Commodore et quelques autres micro-ordinateurs de l'époque. Il s'agissait là encore de 3D non-texturée.

Si la 3D vraie existait, la plupart des premiers FPS utilisaient des moteurs qui ne sont pas totalement en 3D, mais sont plus des jeux en 2,5 D, à savoir qu'ils mélangent des éléments purement 2D, avec un rendu 2D simule un rendu 3D. L'illusion de la 3D est rendu par des techniques assez diverses. Il y a en gros trois techniques principales : le raycasting, le rendu avec un BSP et le portal rendering. Le portal rendering était la technique principale, les deux autres étaient assez spécifique des jeux Id Software. Au passage, que ce soit le raycasting, le portal rendering ou le rendu à BSP de DOOM, tous auront droit à un chapitre dédié qui explique dans le détail comment ils fonctionnent.

Liste des moteurs de jeu en 2.5D et en 3D utilisés par les FPS au cours du temps.

Les jeux Id Software

La grande famille des moteurs de rendu 2.5D des FPS est composée de plusieurs lignées. La première est celle des jeux IdSoftware, avec les moteurs des jeux Wolfenstein 2D et DOOM. Et contrairement à ce qu'on pourrait croire, les deux utilisent des moteurs très différents. Le premier moteur d'IdSoftware est celui de la saga Catacomb, qui précède Wolfenstein 3D. Oui, Wolfenstein 3D n'est pas le premier FPS inventé, nous en reparlerons. Le moteur de Catacomb a ensuite été remplacé par celui utilisé pour Wolfenstein 3D, qui été foncièrement différent : d'un système de rastérisation par ligne, il passait à une forme limitée de raytracing, appelée le raycasting.

Les deux moteurs de Catacomb 3D et de Wolfenstein 3D n'avaient pas de nom, contrairement à son successeur, le moteur des jeux DOOM, appelé l'IdTech 1. Les moteurs de jeux suivants seront l'Idtech 2, 3, 4, respectivement utilisées pour Quake 1/2, puis Quake 3, et enfin DOOM 3. Bien qu'ils portent des noms similaires, ce sont des moteurs indépendants, bâtis sur des fondations totalement différentes. Le code source de tout ces moteurs a été rendu public, on sait comment ils fonctionnent.

DOOM était le seul moteur à utiliser un système de rendu à base de BSP. Beaucoup de monde croit à tord que le moteur utilise une amélioration du raycasting de Wolfenstein, mais il n'en est rien. Il n'y a aucune trace de raycasting dans le code. La méthode de rendu est vraiment spécifique à DOOM et est distinctes de la technique du portal rendering utilisée par tous les jeux en 2.5 D de l'époque (à une exception dont nous reparlerons plus tard).

Les autres moteurs

Moins connu, le moteur Build a été utilisé pour les jeux de 3D Realms : Duke Nukem 3D, Blood, Shadow Warrior, mais aussi les jeux de la saga WitchHaven. Quelques jeux indépendants récents sont développés sur ce moteur, notamment le jeux Ion Fury développé par les anciens programmeurs de Duke Nukem 3D. Le code source a été rendu public, ce qui fait qu'on sait comment fonctionne le moteur. Il utilise la technique du portal rendering et non un rendu à BSP, comme le fait un DOOM pourtant sorti avant lui. Il est donc moins optimisé que DOOM, mais cela n'a pas posé problème car les jeux Build sont sortis quelques années après DOOM, dans une période où la technologie évoluait très vite et où les processeurs devaient très rapidement plus puissants.

Moins connu, il faut aussi citer les moteurs d'autres jeux plus confidentiels de l'époque. Et commençons par les jeux de l’entreprise Bungie, les créateurs de Halo, qui produisaient des jeux sur Macintosh. Inspiré par Wolfenstein 3D, les développeurs de Bungie eurent l'idée de créer leur propre moteur 3D maison, afin de sortir eux aussi des jeux en 3D. Leur premier titre était le FPS Pathways into Darkness, sorti en 1993, soit la même année que DOOM. Il fut suivi par la trilogie de jeux Marathon, qui ont eu un succès d'estime. Au passage, les, trois jeux sont disponibles gratuitement sur Steam et sur le site de Bungie, avec même une sorte de remaster non-officiel qui tourne à merveille sur les PC modernes (un source port, des textures améliorées, et pas mal d'améliorations de ce genre).

Les trois jeux Marathon sont sortis sur Macintosh, et n'étaient pas compatibles avec Windows. De là, on peut rapidement deviner qu'ils utilisaient un moteur de jeu fait maison, sur lequel la documentation est très rare. Les gens qui ont codé le remaster non-offociel Aleph One pourraient cependant savoir comment fonctionne ce moteur, s'ils ont effectué un travail de réingénieurie complet. Le moteur était cependant assez puissant et avec beaucoup de fonctionnalités : support des escaliers, d'une gestion de la hauteur, plafonds et sols de hauteur variable, des ascenseurs, etc. Il était aussi possible d'avoir plusieurs pièces superposées. On peut supposer qu'il utilisait le portal rendering, comme tous les autres jeux de l'époque à part DOOM et un autre que nous verrons sous peu.

La rumeur veut que le moteur de Pathways into darkness soit le même que celui de Marathon, avec évidemment une amélioration du moteur pour les jeux de la saga Marathon. Cependant, si vous essayer de jouer à Pathways into darkness avec le remaster non-officiel, le moteur amélioré par la communauté, le jeu crashe sans autre forme de procès. Cependant, il existe un remaster non-officiel, un source port de Pathways into darkness, qui utilise sa propre version d'Aleph One, modifée pour fonctionner avec ce jeu, qui porte le nom d'Aleph One: Pathways Into Darkness.

La société Lucas Art, connue pour ses jeux Point'click, a développé deux FPS de son temps. Le premier est le jeu Star Wars : Dark Forces dans lequel on incarne un soldat de la résistance dans l'univers de Star Wars, le second est le FPS Outlaws se passant dans un univers de Western. Les deux jeux utilisaient un moteur de jeu fait maison, appelé le Jedi engine. Ce furent les deux seuls jeux à utiliser ce moteur, Lucas Arts ayant abandonné les FPS par la suite. LE fait que Outlaws soit sorti alors que Quake était déjà sorti n'a pas aidé ses ventes, la 3D venait d'arriver, il n'y avait plus besoin d'un rendu en 2.5D. Le moteur a été abandonné après cela. Le code source du moteur n'est pas disponible et n'a jamais été rendu public, mais quelques fans de ces jeux ont effectué de la rétro-ingénierie pour retrouver un moteur équivalent. Le moteur de jeu utilise la technique du portal rendering, la même que le moteur Build.

Les jeux de la saga Ultima Underworld étaient des jeux utilisant un moteur en quasi-3D. Il s'agit d'une série de FPS-RPG sortis un tout petit peu après Wolfenstein 3D. Des tentatives de reverse enginnering du moteur sont encore en cours. La seule chose que l'on sait est que les niveaux du jeu sont stockés en 2D, mais qu'ils servaient de base pour un rendu en pure 3D. D'après les dires de Doug Church, un des programmeurs du jeu, voici comment fonctionnait ce moteur :

« However, let me second what Dan Schmidt said in the guestbook back in August about the description of the UW engine you guys have up on the page. Namely, UW _was not_ a raycasting engine. While UW did use a tilemap to store the world, that has nothing to do with the rendering model. In general, I'd suggest that the "world rep" and "rendering engine" be considered separate things when discussing game technology, because they very often are. In UW, we had a tile based world. The renderer used the tiles to explore the view cone and do a high level cull operation. From the list of visible tiles, we generated full 3d polygons, in the traditional XYZ sense, and handed them off to a rendering back end and rendered each poly in 3d as is. That is also how the 3d models like the ankh shrines or benches were done, which clearly aren't "raycast" model 3d objects. Now, in practice, many of our 3d primitives did things like normal checks first, and then chose which algorithim to rasterize with based on scale/normal/etc of the surface being rendered. »

Source : ultima Underworld Viewer

Enfin, il faut aussi citer quelques FPS sortis sur Amiga, qui utilisaient leur propre moteur de rendu. Des jeux comme Alien Breed 3D et quelques autres étaient dans ce genre. Le code machine de ces jeux est disponible et a été rendu public, on peut le trouver via ce line, mais peu d'informations sont connues à ce jour sur le fonctionnement de leur moteur. Il faut dire que le code en question est un mélange de code C et d'assembleur Amiga, qui n'est donc pas facile à lire et analyser. Apparemment, Alien Breed 3D numéro 2 était partiellement rendu en vraie 3D, alors qu'il est sortit avant Quake 1, bien que de peu.

id Software : Wolfenstein, DOOM, Quake

id Software est une entreprise de jeux vidéo crée en 1991, par ses quatre membres fondateurs : John Carmack, John Romero, Tom Hall, Adrian Carmack (pas de liens familiaux avec John Carmack). Les deux premiers membres, les plus connus, ont décidé de quitter l'entreprise SoftDisk dans laquelle ils codaient des jeux vidéo, pour fonder leur propre studio de développement. Ils recrutèrent alors les deux autres membres. Le récit de la vie de cette entreprise, de la création jusqu'à environ 1996, est raconté dans le livre "Masters of Doom: How Two Guys Created an Empire and Transformed Pop Culture", publié en 2004, qui est la référence pour tout fan des jeux de cette entreprise.

John Carmack est le créateur des moteurs graphiques utilisés dans Wolfenstein 3D, DOOM, Quake et bien d'autres. Il est le programmeur principal, même si les autres membres étaient doués en programmation (Romero a appris à coder en autodidacte et a participé activement au développement de tous les jeux id Software. Il est reconnu pour être capable d'implémenter des idées autrefois publiées dans la littérature académique en rendu graphique, d'une manière qui fait que ces algorithmes peuvent tourner en temps réel. Romero est le level-designer principal des jeux, aux côtés de Tom Hall, Sandy Petterson, et d'autres membres qui ont participé à la création des jeux d'id Software.

Les premiers jeux d'Id Software

Le tout premier jeu en vue subjective temps-réel d'id Software était Hovertank, un jeu de Tank en vue subjective qu'on trouve facilement en abandonware. Il a été le premier jeu à utiliser ce genre de rendu, et le moteur était très simpliste. Le gameplay est franchement pauvre et le jeu est clairement une démo technologique, qui permet de montrer ce que peut faire un moteur simple. Il n'y a même pas de gestion des textures, chaque mur, sol et plafond a une couleur unie, sans détails.

Wolfenstein 3D n'était pas le premier FPS, contrairement à ce qu'on pourrait croire. Catacomb 3D eu trois suites, The Catacomb: Abyss est sorti en même temps que Wolfenstein 3D, The Catacomb: Armageddon est sorti la même année, The Catacomb: Apocalypse est sorti en 1993, après W3D. Peu de choses sont connues sur ce moteur, mais quelques informations ont fuité dans une interview de Carmack par Fabien Sanglard, disponible via ce lien Doom3 Source Code Review: Interviews (Part 6 of 6). Apparemment, le moteur de Catacomb 3D utilisait une technique différente de celle utilisée dans le jeun suivant d'Id Software : Wolfenstein 3D.

The internal rendering was very different from Catacombs 3D. Catacombs used basically a line- rasterization approach, whii Wolfenstein used a much more robust ray-casting approach. But the end result was that they rendered the same pictures.

Wolfenstein 3D, est souvent pris à tord comme le premier FPS, car il a marqué les esprits, bien plus que les Catacomb, qui sont restés très confidentiels. Après la sortie de Wolfenstein 3D, d'autres entreprises ont utilisé ce moteur, avec l'aval d'id Software et moyennement rémunération. En somme, dès le début du FPS, on avait ce système où un moteur de jeu créé par une entreprise était vendu à d'autres pour que ces dernières créent leurs propres jeux vidéos avec. Le moteur de Wolfenstein 3D a été réutilisé dans de nombreuses productions, dont voici la liste :

Blake Stone: Aliens of Gold
Blake Stone: Planet Strike
Corridor 7: Alien Invasion
Cybertag
Hellraiser
Operation Body Count
Rise of the Triad
Super 3D Noah's Ark

Beaucoup de ces jeux tombèrent dans l'oubli, parce qu'ils étaient de véritables catastrophes vidéoludiques à la qualité plus que mauvaise. De plus, l'arrivée de DOOM l'année suivante fit que le moteur de Wolfenstein 3D était devenu trop limité et obsolète (après seulement un an...). Seuls baroud d'honneur, les jeux "ShadowCaster" et "In Pursuit of Greed", de Raven Software, utilisaient une version améliorée du moteur de Wolfenstein 3D. Le moteur ajoutait un éclairage limité, des murs de taille variable, des sols pentus et des sols/plafonds texturés.

DOOM : une révolution technologique

Wolfenstein 3D a ensuite été suivi par DOOM, puis par DOOM 2, deux jeux d'exception, dont le moteur était complétement différent de celui de Wolfenstein 3D. Le moteur de W3D utilisait une technique particulière de raycasting, mais pas le moteur de DOOM. Le développement de l'IdTech 1, le moteur de DOOM 1 et 2, a commencé peu après la sortie de Wolfenstein 3D et son histoire est assez intéressante.

John Carmack pensait à la base créer un moteur basé sur la technique dite du portal rendering, comme le fera Duke Nukem 3D quelques années plus tard. Mais John Romero, mappeur de l'équipe joua un mauvais tour à Carmack. Alors qu'il travaillait sur la fameuse map E1M2, il eu l'idée d'ajouter un escalier de grande taille. Rien de bien méchant au premier abord, sauf que cette petite structure faisait ramer le jeu tellement fort que Carmack dû retourner au travail et trouver une optimisation pour résoudre le problème.

Enfin presque, ce n'est pas la seule raison pour laquelle Carmack se remis au travail. En parallèle de son travail sur le moteur de DOOM, Carmack travaillait sur le portage de Wolfenstein 3D sur Super Nintendo. Mais la machine n'était même pas assez puissante pour faire tourner le jeu. Aussi, Carmack fi quelques recherches pour trouver une solution. Il découvrit dans plusieurs papiers de recherche la technique dite du BSP (Binary Space Partitioning), et décida de réécrire complétement le moteur de Wolfenstein 3D avec cette technique. La technique du raycasting était passée à la trappe au profit d'un système de rendu accéléré par BSP. Et c'est cette technique qui a été utilisée pour DOOM !

L'usage d'un BSP a perduré dans les moteurs d'Id Software ultérieurs, y compris dans les jeux en 3D ! Quake utilise un BSP pour déterminer ce qui est visible à l'écran et dans quel ordre rendre les objets (en fait des polygones/triangles, mais passons), idem pour Quake 2. La technique du BSP était omniprésente dans les moteurs de jeux des années 2000, pour les FPS du moins, la technique ayant été rendue publique et utilisables par les autres créateurs de moteurs de jeux. Rien d'étonnant à cela, le BSP est en fait une structure de données qui peut être utilisée par des algorithmes de rendu très différents les uns des autres. Vous comprendrez cela une fois que vous aurez lu le chapitre sur le moteur de DOOM. Pour le moment, tout ce que vous avez à savoir est que le BSP est une sorte de boite noire que différents moteurs de jeu peuvent utiliser.

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

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

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

Pour rappel, une map dans un FPS en 2.5D est un plan en deux dimensions, dans lequel le moteur d’un jeu vidéo place des objets et les fait bouger. Dans cette scène 2D, on place des murs infranchissables, des objets, des ennemis, mais aussi une caméra qui indique la position du joueur et la direction de son regard. 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 :

L'algorithme de raycasting : du lancer de rayon simplifié

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

Illustration de l'agorithme de Ray-casting.

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 :

D=(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}

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

Le rendu du sol et des plafonds est assez simple et peut être effectué avant ou après le reste du rendu. 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 :

La taille du mur perçue à l'écran est calculée avec le théorème de Thalès, comme vu il y a quelques chapitres. 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

Mettre à l'échelle les murs colonne par colonne, avec le théorème de Thalès, donne ce genre de résultat :

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.

Détermination taille d'un mur en raycasting

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

Le 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

Le 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

En 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 :

Lode's Computer Graphics Tutorial, Raycasting.

L'application des textures

Les 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

Pour 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 :

Le portal rendering

Le rendu à portails, aussi appelé portal rendering, était la méthode de rendu dominante durant les années 90. Il a notamment été utilisé sur le Build Engine, le moteur de jeu de Duke Nukem 3D, Shadow Warrior, Blood, et quelques autres excellents jeux des années 90. Elle a aussi été utilisée dans le jedi engine des FPS lucas art, à savoir Star Wars Dark Forces et Outlaws, et pour les jeux Marathon et Pathways to Darkness de Bungie. Le rendu à portail était moins performant que l'usage du Binary Space Partionning, mais permettait d'avoir des niveaux dynamiques et des maps à la géométrie non-euclidienne. Elle gère notamment les portails de téléportation naturellement, là où le moteur de DOOM, seul à utiliser les BSP, ne permettait pas de voir à travers un portail.

Dans ce chapitre, nous allons étudier le rendu à portail en prenant l'exemple du Build Engine, dont le code source est disponible depuis les années 2000.

Les secteurs et leur rendu

Le rendu à portail demande que de nombreuses informations concernant la map soient précalculées. L'idée est de découper la map 2D en polygones appelés 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 étage de bâtiment. le niveau est composé de couloirs reliant des pièces rectangulaires. Une pièce rectangulaire correspond à un polygone/secteur, 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, délimitée par des murs, avec des ouvertures comme des portes, des fenêtres transparentes, des ouvertures vers l'extérieur, etc. Un secteur 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.

Le rendu se fait secteur par secteur, mais nous laissons cela de côté pour le moment. Ce qui va nous intéresser est comment le jeu rend un secteur. Pour simplifier les explications, nous allons partir du principe que le joueur est physiquement dans un secteur, et que le jeu veut rendre ce secteur précisément. Le rendu qui nous pré-occupe est celui des murs du secteur, les ouvertures sont justement traitées à part. Nous verrons que ce sont elles qui permettent de passer d'un secteur à l'autre.

Les secteurs doivent idéalement être convexes

Pour rendre un secteur, le rendu affiche les murs, généralement en dessinant les murs un par un dans le framebuffer. Puis, il rend les sprites, du plus lointain au plus proche dans la pièce. Le rendu des murs doit être assez rapide. Et pour cela, il se fait généralement sans tenir compte des informations de profondeur. On dessine les murs un par un, dans le désordre. Mais cela demande qu'une condition bien précise soit respectée : le secteur n'a pas de murs qui en cache un autre.

Peu importe l'angle de vue, un mur ne doit pas en cacher un autre, même partiellement. Pour cela, il faut que le secteur soit convexe, les secteurs concaves sont interdits. Pour éviter de rentrer dans la définition mathématique de ce qu'est un truc concave, on va dire qu'il ne doit pas y avoir de "pointe" ou un angle qui rentre dans le polygone, et qui pourrait masquer un mur derrière. Par exemple, le polygone ci-contre est concave, en raison de la petite pointe à gauche.

Avec des secteurs garantis convexes, il est certain qu'aucun mur n'en masque un autre. Pas besoin de trier les murs selon leur profondeur. Un secteur est alors simplement définit par la liste de ses murs et des ouvertures vers les autres pièces. Il peut dessiner les murs dans le désordre, avant de passer au rendu des ouvertures.

Les portails

La distinction entre lignes pour les murs, pour les ouvertures pour les fenêtres/portes est très importante pour ce qui est du gameplay, mais aussi pour le rendu à portail. Elle colle assez bien à la distinction entre lignes opaques et lignes invisibles. Les lignes opaques sont concrètement les lignes des murs, infranchissables, n'ont pas de nom. Mais elles sont opposées aux lignes pour les ouvertures, qui sont en quelque sorte "transparentes". On peut voir à travers une fenêtre, une porte ouverte, ou toute autre ouverture. Elles ne sont pas forcément traversables : on peut traverser une porte ouverte, mais le jeu ne permettra pas de traverser une vitre ou une fenêtre fermée. Le jeu peut permettre de la casser, mais encore faut-il que les programmeurs aient prévu le coup. Les portails sont des lignes qui correspondent à des ouvertures, relient soit deux pièces entre elles, soit une pièce avec l'extérieur.

Le rendu par portail se fait secteur par secteur

L'idée du rendu par portail est de faire le rendu pièce par pièce, ou mieux dit : secteur par secteur. L'idée est de commencer le rendu dans le secteur où se trouve le joueur, puis de passer aux secteurs voisins, puis aux secteurs encore voisins, et ainsi de suite. Le rendu est donc récursif, terme barbare qui recouvre un concept assez simple. Chaque pièce pointe vers plusieurs pièces, qui pointent vers plusieurs pièces, qui elles-mêmes pointent vers plusieurs pièces, et ainsi de suite. Une fois qu'on a rendu une pièce, il ne faut, pas oublier de revenir en arrière, à la pièce précédente, pour reprendre le rendu à partir de celle-ci. Les programmeurs savent comment faire ce genre de chose : une fonction récursive, l'usage d'une pile de pièce, rien de compliqué.

Pour cela, la map doit contenir des informations de connectivité, à savoir : quel secteur est voisin de quel autre. La map mémorise, pour chaque secteur, la liste de ses portails. Et chaque portail indique vers quelle autre pièce il donne de la visibilité. Le rendu utilise les informations sur les portails pour passer d'une pièce à la suivante. Un point important est que ces informations de connectivité peuvent changer à la volée, ce qui permet de modifier le niveau en temps réel. Rien de compliqué, quelques scripts peuvent faire l'affaire. Il s'agit d'une possibilité que le moteur de DOOM ne permettait pas, du moins dans le moteur original, du fait de l'usage d'un BSP assez fixe. Mais passons.

Les informations de connectivité n'ont pas non plus à respecter un espace normal. Il est possible de connecter les pièces entre elles d'une manière qui ne fait pas sens en trois dimensions. Par exemple, il est possible de passer d'une pièce A vers une pièce B à travers un portail, mais le même portail renvoie vers une pièce C lorsqu'on le regarde/prend en sens inverse. Les portails peuvent agir comme des pseudo-téléporteurs si on gére les informations de connectivité convenablement. De telles géométries non-euclidiennes ont fait le sel de quelques jeux, notamment du premier Prey, un FPS des années 2000.

Avec les explications que je viens de donner, vous avez peut-être trouvé un défaut à cette méthode : elle marche bien pour les environnements fermés, où on ne voit pas l'extérieur. Mais dès qu'un niveau a beaucoup d'environnement en extérieur, sans rien pour bloquer la vision, ce mode de rendu ne fonctionne plus vraiment. Aussi, cette méthode de rendu a été utilisé pour quelques jeux bien précis. Les anciens FPS en 2.5D avaient peu d’environnement ouverts, et les rares environnements à l'extérieur simulaient ceux-ci avec des secteurs entourés de bâtiments. Dans Duke Nukem 3D, les environnements ouverts étaient surtout des rues, entourées de bâtiments, qui étaient bloquées à leurs extrémités.

Il faut noter que la méthode marche aussi en trois dimensions. Des jeux 3D utilisaient cette technique, bien que cela demandait un level-design adéquat. L'exemple caractéristique est le jeu en vraie 3D texturée Descent, paru quelques mois avant ce qui est souvent considéré à tord comme le premier en vraie 3D : Quake ! Mais des jeux plus complexes utilisaient le rendu à portails avec des graphismes plus élaborés. Le premier jeu Thief, un FPS orienté infiltration, utilisait le rendu à portail.

Les sous-secteurs reliés par des portails

Il est en théorie possible de gérer des pièces concaves, en les découpant en plusieurs sous-secteurs convexes, connectés entre eux par des portails. Les mathématiques nous disent que c'est toujours possible. Un polygone concave peut toujours être découpé en plusieurs triangles collés les uns aux autres. Et un triangle est naturellement convexe. Sans compter qu'on peut combiner plusieurs triangles en polygones convexes de plus grande taille, comme des rectangles, des quadrilatères, etc.

Mais les performances s'en ressentent, car le rendu d'une pièce demande alors de rendre un portail, voire plusieurs. Et les portails ne sont pas gratuits en termes de performance. En pratique, le cout en performance sera assez important. Il est aussi possible de trier les murs d'un secteur en fonction de leur distance, pour les rendre avec l'algorithme du peintre ou l'algorithme du peintre inversé. Le Build Engine triait les murs du plus proche au plus lointain, pour chaque secteur. Heureusement pour les performances, il y a peu de secteurs par pièces, ce qui rend ce tri assez rapide.

Le rendu par portail est une approximation de l'algorithme du peintre

Le rendu par portail permet d'approximer l'algorithme du peintre inversée. Et si j'ai dit approximer, c'est car l'ordre de rendu des objets n'est pas exactement du plus proche au plus lointain. Le rendu se fait secteur par secteur et le moteur tend à rendre les secteurs du plus proche au plus lointain. Par contre, le rendu des murs dans un secteur ne se fait pas forcément du plus proche au plus lointain. Tout dépend du moteur : le Build Engine trie bien les murs selon leur distance, d'autres moteurs s'en passent. Tout dépend de si les secteurs sont garantis convexes ou non.

De plus, même en rendant les murs dans l'ordre et les secteurs dans l'ordre, on peut avoir un résultat pas totalement ordonné. Imaginez l'exemple suivant : le joueur voit deux secteurs à travers deux portails séparés. Le secteur 1 contient un mur à 5 mètres et un autre à 50 mètres, le secteur 2 a un mur à 1 mètre et un autre à 15 mètres. L'ordre de rendu sera alors : mur à 5 mètre, puis à 50, puis celui à 1 mètre et celui à 15 mètres. Ou alors, on aura mur à à 1 mètre et celui à 15 mètres, puis celui à 5 mètres et celui à 50. L'ordre de profondeur n'est pas totalement conservé.

Mais le rendu à portail garantit cependant que ce n'est pas un problème. En effet, les deux portails sont par définition deux portions de l'écran qui ne se recouvrent pas. Par contre, si deux portails sont alignés, le rendu à portail garantir que l'on traitera les deux portails dans l'ordre. En fait, deux portails non-alignés sont des portions indépendantes de l'image, qui ne contiennent pas de mur ou de sprites commun. On peut les rendre indépendamment les uns des autres, sans problème.

Quelques moteurs graphiques utilisaient cependant l'algorithme du peintre, pas sa version inversée. Par exemple, le jeu Thief était un jeu en 3D qui utilisait une version 3D du rendu à portail. Et il dessinait ses surfaces en allant de la plus lointaine vers la plus proche. De plus, il ne séparait pas le rendu des murs et celui des objets, vu que c'était plus simple avec un algorithme du peintre normal, surtout qu'en plus le jeu était rendu en 3D.

La visibilité à travers les portails

Idéalement, le moteur n'est cependant pas stupide et ne parcours pas les secteurs invisibles. Quand il visite un secteur, il détermine si quels sont les murs et portails visibles par le joueur, depuis sa position initiale. Si un portail n'est pas visible par le joueur, la pièce voisine associée ne sera pas visitée. Et les murs du secteur qui ne sont pas visibles ne sont pas pris en compte. Le moteur du jeu Thief, un FPS orienté infiltration en 3D, appliquait cette optimisation. Lors du parcours secteur par secteur, le moteur du jeu vérifiait pour chaque secteur s'il était visible par le joueur. Si ce n'était pas le cas, le jeu abandonnait ce secteur et passait au secteur suivant. Bizarrement, le Build Engine n'appliquait pas cette optimisation.

Le rendu à portail résout un problème très important : déterminer ce qui est visible à l'écran. Le moteur du jeu analyse en premier le premier secteur, celui où se trouve le joueur. Il regarde alors quels sont les murs et les sprites qui sont dans le cône de vision du joueur. Le moteur de jeu dispose d'algorithmes de view frustrum clipping qui éliminent tout ce qui est en-dehors de ce cône de vision. Et ces algorithmes peuvent être adaptés pour déterminer ce qui est visible à travers un portail. L'idée est que pour chaque portail, le moteur détermine un cône de vision dont les bords sont ceux du portail. Il ré-utilise alors l'algorithme de view frustrum clipping pour éliminer ce qui est en-dehors de ce cône de vision à travers le portail. En faisant cela,

Le Build Engine n'utilisait pas cette méthode. Il faisait le strict minimum lors du rendu et se contentait d'éliminer les portails en-dehors du champ de vision du joueur. Par contre, il ajoutait une optimisation : les portails n'étaient pas pris en compte si ils font dos au joueur. En effet, un portail n'est pas qu'une ligne : il a aussi un sens, une direction qui indique par où le joueur peut regarder. Les portails pour les portes ont un double sens : ils font toujours face au joueur. Mais d'autres portails comme les fenêtres vers un extérieur inaccessible, n'ont qu'un seul sens. Si le portail fait dos au joueur, c'est signe qu'un mur est situé entre le joueur et le portail.

Pour accélérer l'élimination des portails invisibles, la map peut aussi contenir des informations de visibilité entre portails. Par exemple, imaginez une pièce avec deux portails, placés de telle sorte que si le joueur regarde à travers un portail, l'autre est invisible. Cette information est très importante, car elle indique que si le joueur regarde à travers le premier portail, le second n'est pas à prendre en compte. Cela fait un portail en moins à analyser avec le clipping. Pour en profiter, chaque portail d'un secteur, la map mémorise ce qui est potentiellement visible depuis ce portail. De telles informations sont regroupées sous le terme de Potentially visible set : l'ensemble potentiellement visible. Le potentiellement est important, car ce qui est visible dépend de la position du joueur et de l'angle que fait sa caméra.

L'ordre de rendu des secteurs

Pour simplifier les explications, nous partons du principe que le rendu se fait en deux phases : une phase où il détermine ce qui est visible, une phase où il dessine dans le framebuffer. Pour déterminer ce qui est visible, il parcourt la map, en passant d'une pièce à ses voisines. Pour chaque pièce visible, il mémorise les murs et les sprites dans cette pièce visibles depuis la caméra. Un algorithme de culling élimine les murs et les sprites non-visibles depuis la caméra, les murs/sprites qui restent sont regroupés dans un paquet, un bundle. Le résultat de cette étape de visibilité est un arbre de bundles, avec au sommet la pièce où se trouve le sujet, puis toutes les pièces visibles organisées de la plus lointaine à la plus proche. Les pièces sont d'autant plus loin qu'elles se trouvent sur les feuilles de l'arbre, d'autant plus proches qu'elles sont proches du sommet.

Exemple : la pièce où se trouve le joueur est au sommet, les pièces visibles sont en noir, les pièces invisibles sont en blancs.

L'arbre ainsi créé est ensuite parcouru pour afficher les pièces et dessiner dans le framebuffer. Le moteur du jeu parcours cet arbre, et traite chaque pièce visible une par une. Il y a plusieurs possibilités. La première parcours les pièces de la plus lointaine à la plus proche, ce qui permet d'afficher sprites et murs en même temps. Une autre possibilité parcours les pièces de la plus proche à la plus lointaine pour les murs, mais dans l'autre sens pour les sprites, en évitant tout sur-dessinage avec un algorithme distinct. La seconde méthode se marie mieux si les murs et les sprites sont séparés dans des arbres séparés, mais ce n'est pas toujours nécessaire.

Il y a deux grandes méthodes pour parcourir un arbre, appelées le parcours en largeur et le parcours en profondeur. Les deux schémas ci-dessous illustrent les deux parcours et indiquent dans quel ordre sont parcourus les pièces/bundles. Seul le parcours en largeur nous intéresse, car il permet d'implémenter un rendu du plus proche au plus lointain. Le moteur du jeu parcourt les secteurs du plus proche au plus lointain, mais le dessin des murs dans un secteur ne suit pas un ordre de profondeur. Deux murs dans deux secteurs différents peuvent être à des distances très différentes, leur ordre de dessin ne compte pas. Par exemple, si je dessine le secteur 1 avant le secteur 2, peu importe qu'un des murs du secteur 1 soit plus loin qu'un mur du secteur 2 : ce n'est pas pris en compte. En cela, le parcours en largeur est une approximation de l'algorithme du peintre inversé.

Le Build Engine

Le Build Engine utilise une version assez étrange du rendu par portail. Son rendu se fait en plusieurs phases.

La toute première étape détermine quels sont les murs potentiellement visibles. Elle se fait en parcourant tous les secteurs, en traversant les portails, à partir du secteur occupé par le joueur. Mais n'allez pas croire qu'il s'agit d'une phase de rendu : rien n'est dessiné. Il s'agit juste de faire la liste des murs potentiellement visibles. Les murs sont regroupés par paquets, avec un paquet de mur par secteur visité. L'algorithme d'élimination des murs invisibles pour cette première phase n'est pas très efficace. Il part du principe qu'un mur est potentiellement visible s'il est dans le cône de vision du joueur, qui fait 90°. Il élimine aussi les murs qui font dos au joueur. En somme, la première étape est juste une phase de clipping et de back-face culling.

Par la suite, les paquets murs sont rendus du plus proche au plus lointain, avec cependant un ordre approximatif. Précisément, il fait le rendu paquet de mur par paquet de mur, c'est à dire "secteur par secteur" mais sans tenir compte des murs potentiellement invisibles dans un secteur. Pour chaque secteur, il commence par rendre le premier paquet de mur qui n'est occludé par aucun mur. Ce n'est pas forcément le mur le plus proche, mais c'est généralement un mur assez proche, qui appartient au secteur occupé par le joueur.

Lors du dessin des murs dans le framebuffer, le moteur utilise un tableau d'occlusion, qui indique quelles portions de l'écran ont déjà été écrites. Lors du rendu d'un mur, le moteur dessine dans le framebuffer colonne par colonne pour les murs. Le tableau d'occlusion marque alors les pixels de la colonne qui ont été rendus, et ce n'est pas forcément toute la colonne.

Il faut noter que le moteur supporte des plafond/sols penchés. Par exemple, le sol d'une pièce peut être à l'horizontale, mais le plafond peut être penchés. Ou vous pouvez avoir un sol penché sur une plateforme dans un environnement ouvert. Les exemples sont nombreux. Dans le moteur original, le rendu des sols/plafonds penchés est effectué par raycasting. Et encore, il est utilisé pour déterminer la position des murs à l'écran, mais leur tracé est réalisé normalement.

La première étape : l'usage d'une pile de parcours

La première phase mémorise les bundloes (les murs et sprites dans une pièce) à rendre dans une structure de donnée sépcifique. Ce n'est pas un arbre comme vu plus haut, mais une structure différente appelée une pile de données, ou encore une pile. Ici, elle sert à simuler un arbre parcours en largeur. Les piles tirent leur nom de la comparaison avec une pile d'assiette. Les données ajoutées les plus récemment sont au sommet de la pile, les plus anciennes sont au fond de la pile. Il est possible d'ajouter une donnée : on dit qu'on empile la donnée. Il est aussi possible de récupérer la donnée qui est au sommet de la pile, à savoir la plus récemment ajoutée.

Ce système d'empilement/dépilement garantit que dans une pile, les données sont triées selon leur ordre d'ajout. Vu qu'on ne peut qu'enlever la donnée la plus récemment ajoutée. pour le Build Engine, les pièces sont parcourues avec le parcours en largeur, de la plus proche à la plus éloignée, et sont donc empilées dans ce même ordre.

Le build engine utilise deux piles : une pour les sprites et une autre pour les murs. Quand il visite un secteur, il trie les murs par ordre de profondeur et ajoute un par un dans la pile des murs. Il fait pareil avec les sprites : il les trie selon leur profondeur et les ajoute un par un dans la pile. Il vérifie alors les portails et place les portails du secteur dans une liste de portails à rendre plus tard. Précisons cependant que les explications sont simplifiées, dans le sens où le moteur du jeu ne mémorise pas des murs individuels, mais des paquets de murs, avec un paquet par secteur. Un paquet correspond aux murs potentiellement visibles dans un secteur.

En savoir plus

Pour en savoir plus sur le build engine, je conseille fortement la lecture des articles du blog de Fabien Sanglard :

Le peu d'information publique vulgarisée sur le Jedi Engine est disponible via ce lien :

Dark Forces (DOS) Rendering, Part I

Documentation incomplète du moteur de Thief, réalisée par un ancien programmeur du moteur :

The 3D Software Rendering Technology of 1998's Thief: The Dark Project

Le DOOM engine

Les chapitres précédents abordaient deux techniques de rendu : le rendu à portail, le raycasting. Le raycasting n'a été utilisé que pour le moteur de Wolfenstein 3D, mais était trop gourmand. Le rendu à portail est une technique très puissante, mais elle est surtout utile pour afficher des environnements fermés. La majorité des jeux de l'époque l'utilisaient, cependant. Il ne nous reste plus qu'à aborder une technique elle aussi très puissante : le Binary Space partitionning.

Le Binary Space partitionning sera abrévié BSP dans ce qui suit.

L'histoire du BSP, à ses débuts, suit plus moi celle des moteurs d'IdSoftware. Tout commence après la parution de Wolfenstein 3D, quelques mois après. John Carmack, programmeur du moteur des jeux IdSoftware, l'a introduitr pour la première fois lors du portage de Wolfenstein 3D sur NES. Puis, il a été réutilisé dans tous les jeux IdSoftware qui ont suivi : DOOM, mais aussi Quake 1, 2, 3 ! Il n'y a pas d'erreur, le BSP a été utilisé aussi bien dans des jeux au rendu 2.5D qu'en 3D pure. Les autres jeux basés sur le moteur de Quake, comme Half-life, utilisaient eux aussi le BSP.

Autres sources

GFDL

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.