Les moteurs de rendu des FPS en 2.5 D/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

◄ Retour vers « Le moteur de Wolfenstein 3D »

Sommaire du livre

Continuer vers « Le DOOM engine » ►