L'utilisation de BSP dans Doom est-elle vraiment une initiative ingénieuse?

Le summum de la technologie de l'époque.

En 1993, id Software a sorti Doom , un jeu de tir à la première personne qui s'est rapidement transformé en phénomène. Aujourd'hui, on pense que c'est l'un des jeux qui a eu le plus grand impact dans l'histoire.

Dix ans après la sortie de Doom , en 2003, le journaliste David Kouchner a publié un livre d'id Software intitulé Masters of Doom , qui est depuis devenu une description canonique du processus de création de Doom . J'ai lu Masters of Doom il y a quelques années et je ne me souviens de presque rien, mais une histoire d'un livre sur le programmeur principal John Carmack a été conservée dans ma mémoire. Ma description ne sera pas entièrement exacte (voir ci-dessous pour plus de détails), mais en bref, au début du développement de Doom , Carmack s'est rendu compte que le rendu 3D qu'il avait écrit pour le jeu commençait à ralentir lors du rendu de certains niveaux. C'était inacceptable, car Doom devait devenir un jeu actif et même effréné. Réalisant que le problème du moteur de rendu était si fondamental qu'il devrait chercher un algorithme de rendu plus optimal, Carmack a commencé à lire des articles de recherche. En conséquence, il a mis en œuvre une technique appelée partitionnement d'espace binaire (BSP), qui n'avait jamais été utilisée auparavant dans les jeux vidéo, et a ainsi considérablement accéléré le moteur Doom .

Cette histoire de la façon dont Carmack a appliqué la recherche scientifique de pointe aux jeux vidéo m'a toujours impressionné. À mon avis, c'est grâce à cela que Carmack est devenu une figure si légendaire. Il mérite d'être connu comme un brillant programmeur de jeux vidéo archétypal pour de nombreuses raisons, mais en tant que principal, je me souviens toujours de l'épisode avec la lecture d'articles scientifiques et la partition binaire de l'espace.

De toute évidence, cette histoire est impressionnante, car le terme «partition binaire de l'espace» semble être quelque chose de compliqué non seulement pour la mise en œuvre, mais même pour la compréhension. Pendant longtemps, j'ai supposé que Carmack avait fait un bond intellectuel, mais comme je ne savais pas ce qu'est une partition binaire de l'espace et à quel point cette technique était nouvelle lorsque Carmack a décidé de l'utiliser, je n'étais pas complètement sûr. Quelle a été l'ingéniosité de l'ajout d'une partition d'espace binaire à Doom à une échelle allant d'Homer Simpson à Albert Einstein?

Je me suis également demandé d'où venait le BSP et comment l'idée est arrivée à Carmack. Par conséquent, ce poste sera consacré non seulement à John Carmack et Doom , mais également à l'historique de la structure des données de «l'arbre de partition d'espace binaire» (ou arbre BSP). Il s'est avéré que l'arbre BSP, comme de nombreux autres aspects des sciences informatiques, trouve son origine dans des recherches menées pour l'armée.

Oui, c'est vrai: E1M1, le premier niveau Doom , est apparu grâce à l'US Air Force.

Tâche VSD

L'arbre BSP est une solution à l'une des tâches les plus difficiles en infographie. Pour rendre une scène en trois dimensions, le moteur de rendu doit déterminer ce qui est visible et ce qui ne l'est pas à partir du point courant. Ce n'est pas particulièrement difficile si vous avez beaucoup de temps, mais un moteur de jeu en temps réel qui se respecte devrait déterminer les parties visibles et invisibles du monde au moins 30 fois par seconde.

Cette tâche est souvent appelée tâche de détermination de la surface visible (VSD). Le programmeur Michael Abrash, qui a travaillé avec Carmack sur Quake (le prochain jeu d'ID Software après Doom ), a écrit sur la tâche VSD dans son célèbre livre Graphics Programming Black Book :

Je veux parler de la tâche graphique la plus difficile, à mon avis,: déterminer les surfaces visibles (dessiner la surface souhaitée dans chaque pixel) et son proche parent - la tâche d'élimination (le plus rapidement possible, lancer des polygones invisibles pour accélérer la détermination des surfaces visibles). Par souci de concision, je désignerai par l'abréviation VSD à la fois la définition des surfaces visibles et l'écrêtage.

Pourquoi est-ce que je considère VSD comme la tâche 3D la plus difficile? Bien que les problèmes de pixellisation, tels que le mappage de texture, soient également des tâches étonnantes et importantes, ce sont des tâches d'une échelle assez finie, dont la solution est déplacée vers l'apparition d'accélérateurs 3D sur l'équipement; en outre, ils ne s'adaptent que lorsque la résolution de l'écran est augmentée, ce qui est tout à fait supportable.

En revanche, VSD est une tâche illimitée, et maintenant des dizaines de solutions sont utilisées pour le résoudre. Plus important encore, les performances naïves du VSD s'adaptent directement à la complexité de la scène, qui augmente généralement en tant que fonction carrée ou cubique, de sorte qu'il devient rapidement le facteur limitant du rendu des mondes réalistes.

Abrash a écrit sur la complexité du problème VSD à la fin des années 90, quelques années après que Doom ait prouvé que les gens ordinaires voulaient pouvoir jouer à des jeux graphiquement lourds sur leurs ordinateurs personnels. Au début des années 90, lorsque id Software commençait tout juste à publier des jeux, ils devaient travailler efficacement sur des ordinateurs inappropriés: les machines personnelles étaient conçues pour fonctionner avec du texte, des feuilles de calcul et d'autres applications similaires. Pour atteindre cet objectif, la société a dû aborder la fiction, notamment dans le cas de plusieurs jeux 3D publiés par id Software avant Doom . Dans ces jeux, la conception de tous les niveaux était limitée de manière à simplifier la solution du problème VSD.

Par exemple, dans Wolfenstein 3D , le jeu qu'id Software a sorti juste avant Doom , chaque niveau était composé de murs alignés le long des axes. En d'autres termes, dans l'univers Wolfenstein, il pourrait y avoir des murs nord / sud ou des murs est / ouest, et pas d'autres. De plus, les murs pourraient être placés à des distances fixes dans la grille - tous les couloirs ont une largeur d'une cellule de grille, ou de deux, etc., mais jamais de 2,5 cellules. Bien que cela signifiait que l'équipe d'id Software pouvait créer des niveaux qui semblaient presque identiques, cette restriction a permis à Carmack d'écrire très facilement un moteur de rendu pour Wolfenstein .

Le rendu Wolfenstein a résolu le problème des VSD en déplaçant les rayons (ray marching) dans le monde virtuel depuis l'écran. En règle générale, les rendus rendus par rayons sont des rendus de diffusion de rayons - ils sont souvent lents car la résolution du problème VSD dans raycaster nécessite de trouver la première intersection entre le rayon et un objet dans le monde, ce qui nécessite beaucoup de calculs. Mais comme tous les murs de Wolfenstein sont bordés d'une grille, les seules lignes où une poutre peut traverser le mur seront les lignes de la grille. Par conséquent, il suffit que le moteur de rendu vérifie chacun de ces points d'intersection. Si le rendu commence par vérifier le point d'intersection le plus proche du point de vue du joueur, puis vérifie le second à proximité, etc., et se termine lorsqu'il rencontre le premier mur, le problème VSD est résolu de la manière la plus triviale. Le faisceau s'est simplement déplacé vers l'avant de chaque pixel jusqu'à ce qu'il rencontre quelque chose, ce qui est très bon marché en termes de vitesse d'horloge du processeur. Et comme tous les murs ont la même hauteur, il nous suffit d'émettre des rayons pour chaque colonne de pixels.

Cette simplification du rendu a rendu Wolfenstein assez rapide pour travailler sur les PC domestiques faibles de l'époque, alors qu'il n'y avait pas de cartes graphiques spécialisées. Mais une telle approche ne fonctionnerait pas dans Doom , car l'équipe d'id a décidé que dans son nouveau jeu, il y aurait de nouveaux éléments tels que des murs diagonaux, des escaliers et des plafonds de différentes hauteurs. La marche de rayons ne convenait plus, donc Carmack a écrit un autre type de rendu. Le rendu Wolfenstein , où le faisceau était utilisé pour chaque colonne de pixels, a été repoussé de l'image et le rendu Doom était censé être repoussé des objets. Cela signifiait qu'au lieu de traverser les pixels de l'écran et de déterminer leur couleur, le rendu Doom devait parcourir les objets de la scène et projeter chacun d'eux tour à tour sur l'écran.

Dans un tel moteur de rendu, un moyen simple de résoudre le problème VSD consiste à utiliser un z-buffer. Chaque fois que nous projetons un objet sur l'écran, une vérification est effectuée pour chaque pixel que nous voulons dessiner. Si la partie de l'objet à dessiner est plus proche du joueur que l'objet déjà dessiné dans le pixel, alors nous pouvons réécrire ses informations. Sinon, vous devez laisser le pixel inchangé. Cette approche est simple, mais le z-buffer nécessite beaucoup de mémoire et le moteur de rendu peut toujours dépenser un tas d'horloges de processeur pour projeter une géométrie de niveau que le joueur ne verra pas.

Au début des années 1990, la solution z-buffer avait un autre inconvénient: sur les PC compatibles IBM utilisant un système d'adaptateur vidéo appelé VGA, l'écriture dans le tampon de trame de sortie était une opération coûteuse. Par conséquent, le temps consacré au rendu des pixels, qui sera alors simplement écrasé, a considérablement réduit les performances du rendu.

Étant donné que l'écriture dans le tampon d'image était si chère, le rendu idéal était de commencer par dessiner les objets les plus proches du lecteur, puis les objets immédiatement derrière eux, et ainsi de suite, jusqu'à ce que l'écriture sur chaque pixel de l'écran soit terminée. À ce stade, le rendu aurait dû comprendre qu'il était temps de s'arrêter, économisant ainsi tout le temps qu'il pouvait passer à explorer des objets éloignés que le joueur ne voyait pas. Mais ordonner des objets de scène de cette manière, du plus proche au plus éloigné, revient à résoudre le problème VSD. La question se pose à nouveau devant nous: que peut voir un joueur?


Au début, Carmack a essayé de résoudre ce problème en s'appuyant sur le schéma de niveau Doom . Son rendu a commencé par dessiner les murs de la pièce dans laquelle se trouve le joueur, puis il a coulé dans les pièces voisines pour dessiner des murs dans ces pièces, qui pourraient être visibles depuis la pièce actuelle. Si chaque pièce était convexe, cela résoudrait le problème VSD. Les pièces non convexes peuvent être divisées en «secteurs» convexes. Vous pouvez voir à quoi cette technique de rendu pourrait ressembler à un fort ralentissement dans la vidéo ci - dessus , où un utilisateur YouTuber avec le surnom Bisqwit montre son propre moteur de rendu qui fonctionne selon le même algorithme général. Cet algorithme a été utilisé avec succès dans le jeu Duke Nukem 3D, sorti trois ans après Doom , lorsque les processeurs sont devenus plus puissants. Mais en 1993, à cette époque, le rendu Doom utilisant cet algorithme a rencontré des problèmes avec des niveaux complexes. Cela était particulièrement évident lorsque les secteurs étaient intégrés les uns aux autres, et c'était la seule façon de créer, par exemple, des escaliers circulaires. Les escaliers circulaires nécessitaient plusieurs descentes récursives vers le secteur déjà tracé, réduisant considérablement la vitesse du moteur.

À peu près à la même époque, lorsque l'équipe d'identification s'est rendu compte que le moteur Doom était peut-être trop lent, id Software a été invité à porter Wolfenstein 3D sur Super Nintendo. SNES était encore moins puissant que les PC compatibles IBM de l'époque, et il s'est avéré que le moteur de rendu Wolfenstein avec la technologie de défilement des rayons, malgré sa simplicité, ne fonctionnait pas sur un équipement Super Nintendo avec une vitesse suffisante. Par conséquent, Carmack a commencé à chercher un meilleur algorithme. En fait, c'est pour le port Super Nintendo de Wolfenstein que Carmack a d'abord exploré et implémenté le partitionnement de l'espace binaire. À Wolfenstein, c'était assez simple car tous les murs étaient parallèles aux axes; Doom rend plus difficile. Mais Carmack s'est rendu compte que les arbres BSP résoudraient également les problèmes de vitesse dans Doom .

Division d'espace binaire

Le partitionnement d'espace binaire simplifie la solution du problème VSD en pré-fractionnant la scène 3D. Pour l'instant, il vous suffit de comprendre pourquoi le partitionnement est utile: si vous tracez une ligne (qui est en fait un plan en 3D) à travers toute la scène, sachant de quel côté de la ligne se trouve le lecteur ou la caméra, nous saurons également que rien n'est l'autre côté de la ligne ne pourra pas obstruer les objets du côté de la ligne où se trouve la caméra. Si vous répétez le processus plusieurs fois, nous obtenons une scène 3D, divisée en plusieurs sections. Ce ne sera pas une amélioration par rapport à la scène d'origine, sauf que nous en savons maintenant plus sur la façon dont les différentes parties de la scène peuvent se chevaucher.

Les premiers à écrire sur cette division de la scène 3D ont été des chercheurs essayant de déterminer pour l'US Air Force si les graphiques informatiques sont suffisamment progressifs pour être utilisés dans les simulateurs de vol. Ils ont publié leurs résultats dans un rapport de 1969 intitulé «Recherche sur l'utilisation d'images générées par ordinateur dans la simulation visuelle». Le rapport conclut que les graphiques informatiques peuvent être utilisés pour former les pilotes; Dans le même temps, les chercheurs ont averti que la mise en œuvre du système serait compliquée par la tâche de VSD:

L'une des tâches les plus importantes qui devront être résolues lors du calcul des images en temps réel est la tâche prioritaire, ou lignes cachées. Dans notre perception visuelle quotidienne du monde qui nous entoure, la nature elle-même résout ce problème avec une simplicité triviale; le point d'un objet opaque chevauche tous les autres points qui se trouvent le long de la même ligne de visée et sont plus éloignés. Dans le cas d'un ordinateur, cette tâche est très difficile. La quantité de calcul nécessaire pour déterminer la priorité, dans le cas général, croît de façon exponentielle avec la complexité croissante de l'environnement, et dépasse rapidement la charge de calcul associée à la recherche d'images d'objets en tenant compte de la perspective.

Une solution mentionnée par ces chercheurs, qui selon eux a déjà été utilisée dans un projet de la NASA, est basée sur la création de ce que j'appellerai la «matrice de chevauchement». Les chercheurs soulignent qu'un avion divisant une scène en deux parties peut être utilisé pour résoudre "tout conflit de priorités" entre des objets situés sur les côtés opposés de l'avion. Dans le cas général, vous devrez peut-être ajouter ces plans à la scène de manière explicite, mais pour une certaine structure géométrique, vous pouvez vous fier aux faces existantes des objets. Les chercheurs démontrent l'exemple ci-dessous, où p1 , p2 et p3 sont des surfaces de division. Si le point de vue de la caméra est à l'avant ou sur le côté "vrai" de l'un de ces plans, alors pi vaut 1. La matrice montre la relation entre les trois objets en fonction des trois plans de séparation et de l'emplacement du point de vue de la caméra - si l'objet ai chevauche l'objet aj , alors l'élément aij de la matrice sera égal à 1.


Les chercheurs ont proposé d'implémenter cette matrice dans le matériel et de la recalculer dans chaque trame. En fait, la matrice devrait agir comme un grand commutateur ou une sorte de z-buffer intégré. Lors du rendu de l'objet actuel, la vidéo n'est pas sortie pour des parties de l'objet lorsque 1 est dans la colonne d'objet, mais l'objet de ligne correspondant est dessiné.

Un inconvénient sérieux de cette approche est qu'une matrice de taille n ^{2 est} nécessaire pour décrire une scène avec n objets. Par conséquent, les chercheurs ont décidé de vérifier s'il est possible de présenter la matrice de chevauchement sous la forme d'une «liste de priorités», qui aura une taille de n seulement et de spécifier l'ordre dans lequel les objets doivent être dessinés. Ils ont immédiatement remarqué que dans certaines scènes, par exemple, dans celle illustrée ci-dessus, la commande est impossible à réaliser (car il y a un cycle de chevauchement), ils ont donc consacré beaucoup de temps à la définition mathématique des scènes «bonnes» et «mauvaises». En fin de compte, ils sont arrivés à la conclusion qu'au moins pour les «bonnes» scènes (et le concepteur de scène peut facilement éviter les «mauvais» cas), une liste de priorités peut être générée. Mais ils ont quitté la génération de la liste comme un exercice pour le lecteur. Il semble que la principale contribution de ce travail de 1969 soit d'indiquer qu'au moins théoriquement, il devrait être possible d'utiliser des plans de division pour organiser les objets dans la scène.

Et ce n'est que dans un article de 1980 intitulé «Sur la génération de surfaces visibles par les structures d'arbres A Priori» qu'un algorithme spécifique a été démontré à cet effet. Dans cet article, écrit par Henry Fuchs, Zvi Kedem et Bruce Naylor, l'arbre BSP a été décrit pour la première fois. Les auteurs affirment que leur nouvelle structure de données est «une solution, une approche alternative, utilisée pour la première fois il y a dix ans, mais en raison de certaines difficultés moins répandues» - ils réagissent donc à la décision choisie dans les travaux de l'US Air Force en 1969. Après avoir construit une arborescence BSP, elle peut être facilement utilisée pour organiser les objets avec priorité dans la scène.

Fuchs, Kedem et Naylor ont fourni une description assez claire du fonctionnement de l'arborescence BSP, mais j'essaierai de donner un aspect moins formel, mais bref.

Nous commençons par sélectionner un polygone dans la scène et faisons du plan dans lequel le polygone se trouve un plan de division. Ce polygone unique devient également le nœud racine de l'arbre. Les polygones restants de la scène se trouveront d'un côté ou de l'autre du plan de division racine. Les polygones sur le côté "avant" ou dans le demi-espace "avant" du plan apparaissent dans le sous-arbre gauche du nœud racine, et les polygones sur le côté "arrière" ou dans le demi-espace "arrière" du plan apparaissent dans le sous-arbre droit. Ensuite, nous répétons récursivement ce processus, en sélectionnant des polygones des sous-arbres gauche et droit comme nouvelles surfaces de division pour leurs propres demi-espaces, qui génèrent d'autres demi-espaces et sous-arbres. Le processus se termine à la fin des polygones.

Disons que nous voulons rendre la géométrie de la scène d'avant en arrière.(Ceci est appelé «l'algorithme de l'artiste» car cela signifie que les polygones plus éloignés de la caméra seront remplis de polygones plus proches de la caméra, créant le rendu correct.) Pour ce faire, nous avons juste besoin de faire le tour de notre arbre BSP dans l'ordre; la décision de dessiner le sous-arbre gauche ou droit est basée sur la position du point de vue de la caméra - dans le demi-espace avant ou arrière par rapport au plan de division associé à ce nœud. C'est-à-dire que dans chaque nœud de l'arbre, nous rendons d'abord tous les polygones du côté "éloigné" du plan, puis le polygone du plan de séparation, puis les polygones du côté "proche" du plan. Les polygones «proche» et «éloigné» sont définis par rapport au point de vue de la caméra. Cela résout le problème VSD parce que, comme nous l'avons appris il y a quelques paragraphes,les polygones de l'autre côté du plan de séparation ne peuvent pas chevaucher quoi que ce soit de la face avant.

Le diagramme ci-dessous montre la construction et la traversée d'une arborescence BSP qui décrit une simple scène 2D. En 2D, des lignes de division sont utilisées à la place des plans de division, mais l'idée de base reste la même.




Une caractéristique très pratique de l'arborescence BSP que Fuchs, Kedem et Naylor soulignent à plusieurs reprises est qu'il ne doit être construit qu'une seule fois. Cela semble surprenant, mais un arbre BSP peut être utilisé pour rendre la scène quel que soit le point de vue de la caméra. L'arbre BSP reste utilisable jusqu'à ce que les polygones de scène se déplacent. C'est pourquoi l'arborescence BSP est si utile pour le rendu en temps réel - tout le travail complexe de construction d'un arbre peut être fait à l'avance, et non au moment du rendu.

Fuchs, Kedem et Naylor rapportent que des recherches plus poussées nécessitent la création d'un «bon» arbre BSP. La qualité de l'arborescence BSP dépend des polygones que vous choisissez pour définir les plans de séparation. Plus tôt, j'ai sauté ce point, mais si vous utilisez un plan qui intersecte d'autres polygones lors du fractionnement, alors pour que l'algorithme BSP fonctionne, vous devez diviser les polygones croisés en deux, de sorte qu'une moitié se réfère à un demi-espace et l'autre à l'autre. Si cela se produit souvent, la construction d'un arbre BSP augmente considérablement le nombre de polygones dans la scène.

Bruce Naylor, l'un des auteurs de l'article de 1980, a écrit plus tard à ce sujet dans son article de 1993, Constructing Good Partitioning Trees. Selon le collègue de Carmack et co-fondateur d'id Software, John Romero, cet article était l'une des œuvres que Carmack a lues lorsqu'il a essayé d'implémenter des arbres BSP dans Doom .

Arbres BSP dans Doom

Rappelons que dans la première version du rendu Doom , Carmack a essayé d'établir l'ordre de rendu de la géométrie de niveau en remplissant le rendu hors de la pièce où se trouve le joueur dans les pièces voisines. Les arborescences BSP étaient un moyen plus pratique de déterminer cet ordre, car elles évitaient le problème du rendu du rendu à plusieurs reprises dans une pièce (ou secteur), gaspillant ainsi les cycles du processeur.

«Ajouter des arbres BSP à Doom » dans la pratique signifiait ajouter un générateur d'arbre BSP à l'éditeur de niveau Doom . Après avoir terminé le niveau Doomun arbre BSP a été généré à partir de la géométrie de niveau. Selon Fabien Sanglar, le processus de génération pourrait prendre jusqu'à huit secondes pour un niveau et 11 minutes pour tous les niveaux du premier Doom . Le processus de génération a été si long en partie en raison du fait que l'algorithme de génération Carmack BSP essaie de trouver un «bon» arbre BSP en utilisant diverses heuristiques. Un retard de huit secondes serait impardonnable pendant le jeu, mais lors de la génération préliminaire, il semblait tout à fait acceptable, compte tenu de l'augmentation des performances que les arbres BSP fournissaient au moteur de rendu. L'arbre BSP généré d'un niveau individuel a été enregistré en tant que partie des données de niveau chargées dans le jeu lors de son lancement.

Carmack a apporté un changement important à l'algorithme d'arbre BSP décrit dans un article de 1980: après le lancement de Doomet en lisant l'arborescence BSP du niveau actuel dans la mémoire, le moteur de rendu utilise cet arbre pour dessiner des objets non pas d'avant en avant, mais d'avant en arrière. Dans un article de 1980, Fuchs, Kedem et Naylor ont montré comment un arbre BSP peut être utilisé pour implémenter un algorithme d'artiste avec un rendu dos à dos, mais une grande quantité de repeinture se produit dans l'algorithme de l'artiste, ce qui pourrait être coûteux sur les PC compatibles IBM. Par conséquent, le rendu Doom commence par une géométrie plus proche du joueur, puis dessine le plus loin. Un tel ordre inverse est facile à implémenter à l'aide d'une arborescence BSP, car vous pouvez simplement prendre une décision de retour arrière à chaque nœud de l'arborescence. Pour éviter que la géométrie la plus éloignée ne soit dessinée au-dessus du plus proche, le rendu Doomutilise une sorte de z-buffer implicite, qui offre de nombreux avantages d'un z-buffer normal, tout en consommant beaucoup moins de mémoire. Il existe un tableau qui suit le chevauchement dans la dimension horizontale et deux autres tableaux qui suivent le chevauchement dans la direction verticale au-dessus et en dessous de l'écran. Le moteur de rendu Doom pourrait se passer de l'utilisation d'un véritable z-buffer, car Doom , à proprement parler, n'était pas un jeu complètement en trois dimensions. Des structures de données moins coûteuses y travaillaient parce que certains éléments n'étaient pas possibles dans Doom : le tableau de chevauchement horizontal fonctionnait parce qu'il n'y avait pas de murs en pente, et les tableaux de chevauchement vertical fonctionnaient parce qu'il n'y avait pas de murs dans lesquels, par exemple, il y en avait deux l'une au-dessus des autres fenêtres.


Doom II , aussi complexe que son prédécesseur.


Mais personne ne s'est plaint de la répétition du sang.


Un nouveau mot dans les technologies Quake La

seule tâche délicate qui reste est de savoir comment intégrer les personnages Doom en mouvement dans la géométrie statique des niveaux dessinés à l'aide de l'arborescence BSP. Les ennemis dans Doom ne pouvaient pas faire partie de l'arbre BSP parce qu'ils se déplaçaient; L'arbre BSP ne fonctionne qu'avec une géométrie fixe. Par conséquent, le rendu Doomdessine d'abord la géométrie statique du niveau, en suivant (à l'aide d'une autre structure de données économe en mémoire) les segments de l'écran dans lesquels le dessin a été effectué. Il attire ensuite les ennemis de l'arrière vers l'avant, les tronquant le long des segments de l'écran qui les chevauchent. Ce processus n'est pas aussi optimal que le rendu avec un arbre BSP, mais comme il y a généralement moins d'ennemis que la géométrie, la vitesse n'est pas un problème ici.

L'utilisation d'arbres BSP dans Doom a été une grande victoire. De toute évidence, Carmack était assez vif d'esprit pour réaliser que les arbres BSP seraient la solution idéale. Mais cette décision était-elle ingénieuse ?

Dans son excellent livre sur le moteur de jeu DoomFabien Sanglar cite John Romero, qui a déclaré que l'article de Bruce Naylor «Construire de bons arbres de partitionnement» concernait principalement l'utilisation des arbres BSP pour couper les faces arrière des modèles 3D. Selon Romero, Carmack pensait que l'algorithme pourrait encore être utile pour Doom , alors il l'a implémenté. Ceci est tout à fait louable pour Carmack car il implique qu'il a vu l'utilité des arbres BSP dans les jeux vidéo en temps réel même lorsque d'autres personnes utilisaient encore cette technique pour rendre des scènes statiques. La même histoire flatteuse se trouve dans Masters of Doom: Kouchner a suggéré à Carmack de lire l'article de Naylor et s'est demandé: "Et si vous pouviez utiliser l'arborescence BSP pour créer non seulement une image 3D, mais un monde virtuel entier?"

Ces résultats ignorent l'histoire de l'arborescence BSP. Lorsque les chercheurs de l'US Air Force ont réalisé pour la première fois que le fractionnement d'une scène pouvait aider à accélérer le rendu, ils étaient intéressés par l' accélération en temps réel du rendu, car finalement ils ont essayé de créer un simulateur de vol. L'exemple du simulateur de vol est à nouveau mentionné dans un article de 1980. Fuchs, Kedem et Naylor écrivent que l'arbre BSP peut être utile dans un simulateur de vol que les pilotes utilisent pour effectuer plusieurs atterrissages sur le même aéroport. Comme la géométrie de l'aéroport ne change jamais, un arbre BSP ne peut être généré qu'une seule fois. De toute évidence, ils pensaient à la simulation en temps réel. Dans l'introduction de l'article, ils expliquent même leurs recherches en testant la possibilité d'utiliser un système graphique en temps réel pour créer des images en 1/30 seconde au maximum.

Autrement dit, Carmack n'a pas été le premier à penser à utiliser des arbres BSP dans la simulation graphique en temps réel. Bien sûr, prédire que les arbres BSP peuvent être utilisés de cette manière et les implémenter sont des choses complètement différentes. Mais même avec l'implémentation, Carmack pourrait avoir plus d'informations contextuelles qu'on ne le pense habituellement. L' article du WSP sur les arbres BSP suggère que Carmack a fait référence à l'article de 1991 de Chen et Gordon, ainsi qu'au manuel de 1990 Computer Graphics: Principles and Practice . Bien que cette déclaration ne soit pas étayée par une citation, elle peut être vraie. Un article de 1991 de Chen et Gordon décrit le rendu d'avant en arrière à l'aide d'arbres BSP, qui est essentiellement la même solution utilisée par Doom, jusqu'à la structure de données «z-buffer implicite», qui ne permet pas de tracer des polygones distants au-dessus des polygones voisins. L'article fournit une excellente vue d'ensemble des arbres BSP, ainsi qu'un pseudocode pour la construction et l'affichage d'un arbre. (Grâce à la merveilleuse bibliothèque de mon université, j'ai pu faire défiler l'édition 1990.) Le manuel Computer Graphics: Principles and Practice est un ouvrage classique sur l'infographie, donc Carmack pourrait en avoir un aussi.


Niveau sous-secteur E1M1: Hangar.

Quoi qu'il en soit, Carmack a fait face à une nouvelle tâche - "Comment puis-je créer un jeu de tir à la première personne qui fonctionne sur un ordinateur avec un processeur qui n'est même pas capable d'effectuer des opérations en virgule flottante?" - a mené ses propres recherches et a prouvé que les arbres BSP sont Il s'agit d'une structure de données utile pour les jeux vidéo en temps réel. Je pense toujours que c'est un résultat impressionnant, même si l'arbre BSP a été inventé dix ans plus tôt, et a été étudié théoriquement avec suffisamment de détails au moment où Carmack a lu à ce sujet. Peut-être que la principale réalisation que nous devrions louer est le moteur Doom dans son ensemble, qui est devenu un excellent exemple de code. J'en ai déjà parlé une fois, mais je répète que le livre de Fabien Sanglar sur le moteur de jeuDoom ( Game Engine Black Book: DOOM ) est un excellent aperçu de tous les composants réfléchis du moteur de jeu et de leur interaction. Nous ne devons pas oublier que la tâche VSD n'était qu'une des nombreuses tâches que Carmack devait résoudre pour que le moteur Doom fonctionne . Et qu'il a pu, en plus de tout, lire sur la structure de données complexe inconnue de la plupart des programmeurs, et l'implémenter. Cela en dit long sur le niveau de ses connaissances techniques et son engagement envers l'idéal.