Inside Quake: Définir des surfaces visibles

Le vétéran de la programmation graphique en trois dimensions Michael Abrash, en utilisant l'exemple du développement du premier Quake, parle de la nécessité d'une pensée créative dans la programmation.

Il y a de nombreuses années, j'ai travaillé pour la société d'adaptateurs vidéo Video Seven, aujourd'hui disparue. Là, j'ai aidé à développer un clone VGA. Mon collègue Tom Wilson, qui a travaillé pendant de nombreux mois 24 heures sur 24 pour développer la puce Video Seven VGA, a essayé de rendre le VGA aussi rapide que possible et était sûr que ses performances étaient optimisées presque au maximum. Cependant, alors que Tom introduisait déjà la touche finale à la conception des puces, nous avons entendu des rumeurs selon lesquelles notre concurrent Paradise avait atteint des performances encore plus élevées dans son clone de développement en y ajoutant FIFO.

C'était la fin des rumeurs - nous ne savions pas ce qu'était le FIFO, ni combien il aidait, rien d'autre. Cependant, Tom, généralement une personne amicale et détendue, est devenu un fanatique actif et obsédé avec trop de caféine dans le sang. Sur la base de ces informations, il a essayé de comprendre ce que Paradise pouvait faire. En fin de compte, il est arrivé à la conclusion que Paradise a probablement inséré un tampon d'écriture FIFO entre le bus système et VGA, de sorte que lorsque le CPU enregistrait dans la mémoire vidéo, les données en cours d'écriture iraient immédiatement au FIFO, ce qui permettrait au CPU de continuer le traitement plutôt que de rester inactif à chaque fois quand il écrivait dans la mémoire d'affichage.

Tom n'avait ni éléments logiques, ni assez de temps pour implémenter une FIFO complète, mais il a réussi à implémenter FIFO avec une seule profondeur d'opération, ce qui a permis au processeur de dépasser la puce VGA par une opération d'écriture. Tom n'était pas sûr que cela donnerait de bons résultats, mais c'était la seule chose qu'il pouvait faire, alors il a implémenté ce système et transféré la puce en production.

Il s'est avéré que FIFO pour une opération fonctionne incroyablement cool: à cette époque, les puces vidéo Seven VGA étaient les plus rapides du marché; ils sont devenus la preuve du génie de Tom et la preuve de ce dont le créateur est capable sous la pression des circonstances. Cependant, la grande chose à propos de cette histoire est que le design du Paradise FIFO n'avait rien à voir avec le design de Tom, et cela n'a pas fonctionné du tout . Paradise a inséré un tampon FIFO de lecture entre la mémoire d'affichage et l'étage de sortie vidéo de la puce VGA, ce qui a permis de lire la sortie vidéo à l'avance de sorte que lorsque le CPU avait besoin d'accéder à la mémoire d'affichage, les pixels pouvaient être pris du FIFO et la commande du CPU était exécutée instantanément. Cela a en fait amélioré les performances, mais pas autant que le tampon d'écriture FIFO de Tom.

Et ce cas peut être considéré comme une bonne parabole sur la nature même du processus créatif qu'une personne peut réaliser. Des morceaux de nouvelles sur la puce Paradise ne contenaient presque aucune information factuelle, mais ils ont forcé Tom à dépasser les limites qu'il avait inconsciemment fixées, développant la conception initiale de la puce. Je crois que c'est l'élément le plus important de toute conception ingénieuse, que ce soit dans le domaine du matériel, des logiciels ou de toute autre sphère créative, et c'est lui qui est né dans les nouvelles de Tom sur Paradise: la capacité de détecter les limites que vous avez construites dans le processus de travail sur le projet et de les surmonter frontières.

Le problème, bien sûr, est de savoir comment surmonter les frontières, dont vous ne connaissez même pas l'existence. Il n'y a pas de formule pour réussir, mais deux principes peuvent bien servir cet objectif: premièrement, simplifier, deuxièmement, essayer constamment quelque chose de nouveau.

Habituellement, lorsque vous sentez que le code se complique, vous commencez à apporter des modifications mineures à la structure figée, et il y a une forte probabilité que vous puissiez augmenter la productivité et réduire la quantité de code en réinventant la conception. Une très bonne structure devrait apporter un moment de profonde satisfaction lorsque tout se met en place, et vous êtes surpris de voir à quel point la quantité de code est petite et à quel point tous les cas limites fonctionnent bien.

Dans le processus de révision de la structure, il est important d'étudier toutes les idées qui vous viennent à l'esprit, aussi folles qu'elles puissent paraître. Beaucoup des idées vraiment géniales que j'ai entendues au début semblaient absurdes parce qu'elles ne correspondaient pas à mon image actuelle du monde. Souvent, ces idées sont vraiment folles, mais tout comme les nouvelles de la puce Paradise ont stimulé l'imagination de Tom, l'exploration agressive d'idées apparemment délirantes peut vous ouvrir de nouvelles possibilités.

Bonne illustration: l'évolution du moteur graphique Quake 3D.

La tâche graphique 3D la plus complexe au monde

J'ai passé les sept derniers mois à travailler sur Quake, l'héritier de DOOM d'id Software, et je suppose que trois mois plus tard, au moment où vous lirez cet article, Quake sera publié en tant que shareware.

En termes de graphisme, Quake sera pour DOOM ce que DOOM était pour son prédécesseur, Wolfenstein 3D. Quake ajoute une véritable 3D arbitraire (le joueur peut regarder de haut en bas, se pencher sur les côtés et même tomber d'un côté), un éclairage et des ombres détaillés, des monstres et des personnages 3D au lieu des sprites DOOM. Bientôt, je parlerai de tout cela plus en détail, mais ce mois-ci, je veux parler du problème, que dans mon livre j'appelle le plus difficile dans les graphiques en trois dimensions: déterminer les surfaces visibles (dessiner la surface correspondante pour chaque pixel), et d'une tâche très proche de lui - à propos de écrêtage (en éliminant le plus rapidement possible les polygones invisibles afin d'accélérer la détermination des surfaces visibles). Par souci de concision, je vais utiliser l'abréviation VSD pour désigner la définition de la détermination de la surface visible et de l'abattage.

Pourquoi est-ce que je considère VSD comme la tâche la plus difficile des graphiques 3D? Bien que les tâches de pixellisation, par exemple, le mappage de texture, soient tout aussi étonnantes et importantes, leur portée est assez limitée et, après l'avènement des accélérateurs 3D, leur solution sera transférée au matériel; de plus, leur échelle ne dépend que de la résolution de l'écran, c'est-à-dire qu'elles sont assez modestes.

En revanche, VSD est une tâche illimitée et des dizaines d'approches sont utilisées pour le résoudre. Mais plus important encore, les performances VSD dans une solution naïve évoluent en fonction de la complexité de la scène, qui augmente généralement en fonction quadratique ou cubique, et devient donc rapidement le facteur limitant dans la création de mondes réalistes. Je crois que dans les prochaines années, VSD deviendra un problème de plus en plus dominant dans les graphiques 3D en temps réel pour PC, car le détail des mondes 3D augmentera constamment. Aujourd'hui encore, un niveau Quake de taille solide peut contenir environ 10 000 polygones, soit près de trois fois plus qu'un niveau DOOM comparable.

Structure du niveau de tremblement de terre

Avant de plonger dans le VSD, permettez-moi de mentionner que chaque niveau de Quake est stocké sous la forme d'un énorme arbre BSP en trois dimensions. Cet arbre BSP, comme tout autre BSP, divise l'espace, dans ce cas, le long des plans des polygones. Cependant, contrairement à l'arbre BSP que j'ai démontré plus tôt, l'arbre Quake BSP ne stocke pas les polygones dans les nœuds d'arbre dans le cadre des plans de division, mais dans des feuilles vides (non remplies), comme le montre la figure 1 dans la vue de dessus.


Figure 1. Dans Quake, les polygones sont stockés dans des feuilles vides. Les zones sombres sont des feuilles remplies (volumes remplis, tels que l'intérieur des murs)

L'ordre de rendu correct peut être obtenu en rendant les feuilles dans l'ordre BSP «d'avant en arrière» ou «d'arrière en avant». De plus, comme les feuilles BSP sont toujours convexes et que les polygones sont les limites des feuilles BSP qui regardent vers l'intérieur, les polygones de n'importe quelle feuille ne peuvent jamais se chevaucher et peuvent être dessinés dans n'importe quel ordre. (Il s'agit d'une propriété générale des polyèdres convexes.)

Détourage et définition des surfaces visibles

Idéalement, le processus VSD devrait fonctionner comme suit: tout d'abord, vous devez supprimer tous les polygones qui se trouvent en dehors de la pyramide de visibilité, et également couper toutes les parties invisibles des polygones qui sont partiellement visibles. Ensuite, vous devez dessiner uniquement les pixels de chaque polygone qui sont réellement visibles depuis le point de vue actuel, comme le montre la figure 2 dans la vue de dessus, sans perdre de temps à redessiner à plusieurs reprises les pixels; remarquez combien de polygones dans la figure 2 vous devez dessiner. Et enfin, dans un monde idéal, la vérification de la visibilité de parties de polygones devrait être peu coûteuse et le temps de traitement devrait être le même pour tous les points de vue possibles, afin que le jeu fonctionne correctement.


Figure 2. L'architecture VSD idéale ne rend que les parties visibles des polygones visibles.

Dans le processus d'accomplissement de cette tâche, il est facile de déterminer lesquels des polygones sont complètement hors de portée de la pyramide de visibilité ou partiellement coupés, et il est tout à fait possible de savoir exactement quels pixels dessiner. Hélas, le monde est loin d'être idéal, et tous ces contrôles sont coûteux, donc l'astuce consiste à accélérer ou à sauter différents contrôles, tout en créant le résultat nécessaire.

Comme je l'ai expliqué en détail dans les articles précédents, avec un BSP, vous pouvez facilement et à peu de frais faire le tour du monde dans un ordre avant ou arrière. La solution VSD la plus simple consiste à simplement traverser l’arbre vers l’arrière, à tronquer chaque polygone avec une pyramide de visibilité et à le dessiner si son visage est dirigé vers la caméra et n’est pas complètement coupé (algorithme de l’artiste). Mais est-ce une solution adéquate?

Pour les mondes relativement simples, c'est tout à fait applicable. Cependant, il n'est pas à l'échelle. L'un des problèmes est que lorsque de nouveaux polygones sont ajoutés au monde pour couper les polygones invisibles, de plus en plus de transformations et de contrôles sont nécessaires; après un certain seuil, cela commencera à ralentir considérablement les performances.

Heureusement, ce problème particulier a une bonne solution de contournement. Comme mentionné ci-dessus, chaque feuille de l'arborescence BSP décrit un sous-espace convexe, et les nœuds connectés à la feuille limitent l'espace. Moins évident est que chaque nœud dans l'arborescence BSP décrit également un sous-espace - un sous-espace composé de tous les enfants du nœud, comme le montre la figure 3. Vous pouvez le prendre de cette façon: chaque nœud divise en deux parties le sous-espace créé par les nœuds situés au-dessus dans arbre, et les éléments enfants du nœud encadrant davantage ce sous-espace dans toutes les feuilles provenant du nœud.


Figure 3: Le nœud E décrit un sous-espace sombre qui contient les feuilles 5, 6, 7 et le nœud F.

Puisque le sous-espace du nœud est borné et convexe, nous pouvons vérifier s'il est complètement en dehors de la pyramide de visibilité. Si tel est le cas, tous les enfants du nœud seront définitivement coupés et pourront être supprimés sans traitement supplémentaire. Étant donné que la majeure partie du monde est généralement située en dehors de la pyramide de visibilité, de nombreux polygones du monde peuvent être coupés presque sans coût par d'énormes fragments de sous-espaces de nœuds. Effectuer une vérification idéale pour les sous-espaces de découpage est assez coûteux, par conséquent, généralement pour chaque nœud, des parallélogrammes ou des sphères contraignantes sont utilisés pour les contrôles de découpage.

Autrement dit, l'écrêtage le long de la pyramide de visibilité n'est pas un problème, et vous pouvez utiliser BSP pour dessiner vers l'arrière. Alors quel est le problème?

Redessiner

Le problème auquel l'auteur principal des technologies DOOM et Quake John Carmack a été confronté lors du développement de Quake était que dans un monde complexe, de nombreuses scènes de la pyramide de visibilité ont un grand nombre de polygones. La plupart de ces polygones sont partiellement ou complètement chevauchés par d'autres polygones, mais l'algorithme de l'artiste décrit ci-dessus nécessite de dessiner chaque pixel de chaque polygone dans la pyramide de visibilité. Cependant, ils sont souvent rendus uniquement pour être redessinés par d'autres. À un niveau Quake de 10 000 polygones, il est facile d'obtenir le pire des cas de redessin lorsque les pixels sont dessinés 10 fois ou plus; c'est-à-dire que dans certains cadres, chaque pixel sera dessiné en moyenne 10 fois ou plus. Aucun rasterizer n'est assez rapide pour compenser l'ordre de grandeur nécessaire au rendu d'une scène; pire, l'algorithme de l'artiste crée d'énormes différences de performances entre les meilleurs et les pires cas, ce qui entraîne un changement significatif de la fréquence d'images lors du déplacement du spectateur.

Ainsi, John a été confronté au problème de réduire la quantité de redessin à des niveaux acceptables. Idéalement, chaque pixel ne devrait être dessiné qu'une seule fois, mais pas plus de deux ou trois fois dans le pire des cas. En ce qui concerne le découpage à travers la pyramide de visibilité, il était idéalement nécessaire que tous les polygones invisibles dans la pyramide soient coupés sans frais supplémentaires. Un plus serait également qu'il serait possible de dessiner uniquement les parties visibles de polygones partiellement visibles, mais en même temps un équilibre devrait être maintenu: l'opération devrait dépenser moins que redessiner.

Lorsque je suis arrivé à id au début du mois de mars, John avait déjà un prototype du moteur et un plan d'ensemble, alors j'ai supposé que notre travail serait simplement de terminer et d'optimiser ce moteur. Cependant, si je connaissais l'histoire de l'ID, je pourrais comprendre quoi. John a créé non seulement DOOM, mais aussi des moteurs pour Wolf 3D et plusieurs autres jeux précédents, et pendant le processus de développement, il a fait plusieurs versions différentes de chaque moteur (une fois qu'il a créé quatre moteurs en quatre semaines), c'est-à-dire qu'en quatre ans, il a écrit environ 20 moteurs . Le désir infatigable de John pour de plus en plus de technologies nouvelles et de haute qualité du moteur Quake ne prendra fin qu'après la sortie du jeu.

Trois mois après mon arrivée, un seul élément de la structure VSD d'origine est resté dans le moteur, et le désir de John «d'essayer de nouvelles choses» est allé si loin que je n'avais jamais vu une telle chose auparavant.

Arbre bouquet

Dans le projet Quake d'origine de John, le rendu était effectué d'avant en arrière à l'aide d'un deuxième arbre BSP qui suit les parties déjà dessinées et encore vides de l'écran qui devaient être remplies avec les polygones restants. Logiquement, cet arbre BSP peut être considéré comme une région bidimensionnelle décrivant les parties remplies et vides de l'écran, comme le montre la figure 4, mais en fait il s'agit d'un arbre tridimensionnel, connu sous le nom d '«arbre de faisceau». Un arbre de faisceau est un ensemble de secteurs 3D (grappes) délimités par des plans projetés à partir d'un point central (dans notre cas, le point de vue), comme le montre la figure 5.


Figure 4. L'arbre de faisceau Quake divise efficacement l'écran en une zone 2D


Figure 5. L'arbre de poutres Quake se compose de secteurs ou poutres 3D, projetés du point de vue jusqu'aux bords des polygones.

Dans le projet de John, un arbre à gerbes consiste initialement en une seule gerbe décrivant la pyramide de visibilité; tout ce qui se trouve à l'extérieur de ce paquet est considéré comme rempli (c'est-à-dire qu'il n'est pas nécessaire de dessiner quoi que ce soit là-bas), et tout ce qui se trouve à l'intérieur du paquet est considéré comme vide. Lorsqu'un nouveau polygone atteint en faisant le tour de l'arbre BSP du monde d'avant en arrière, ce polygone est converti en poutre en dessinant des plans à partir de ses bords à travers le point de vue, et toutes les parties du faisceau traversant des poutres vides dans l'arbre de poutres sont considérées comme dessinées et ajoutées à l'arbre de poutres en tant que poutre remplie. Cela a continué, soit jusqu'à la fin des polygones, soit jusqu'à ce que la gerbe soit complètement pleine. Une fois l'arbre des poutres terminé, les parties visibles des polygones piégés dans l'arbre des poutres ont été dessinées.

L'avantage de travailler avec un arbre de faisceaux en trois dimensions au lieu de la région 2D était que pour déterminer de quel côté du plan de faisceaux se trouve le sommet du polygone, il suffit de vérifier le signe du produit vectoriel du rayon vers le sommet et la normale au plan, car tous les plans de faisceaux passent par le début. coordonnées (point de vue). De plus, comme le plan du faisceau est complètement décrit par une seule normale, pour générer un faisceau à partir du bord du polygone, seul le produit scalaire du bord et le faisceau de ce bord au point de vue sont suffisants. Enfin, pour l'écrêtage de groupe par la pyramide de visibilité décrite ci-dessus, on peut utiliser les sphères englobantes des nœuds BSP.

Au début, la propriété d'arbre de bundle (se terminant lorsque l'arborescence de bundle est pleine) semblait attrayante car elle semblait limiter les performances dans les pires cas. Malheureusement, des scènes étaient encore possibles dans lesquelles vous pouviez tout voir jusqu'au ciel ou le mur du fond du monde, donc dans le pire des cas, vous deviez toujours vérifier tous les polygones dans la pyramide de visibilité par rapport à l'arbre de bouquet. Des problèmes similaires peuvent également survenir avec de petites fissures en raison des limitations de la précision numérique. Beaucoup de temps est consacré à la coupure dans l'arborescence des faisceaux, et dans les scènes avec une plage de visibilité élevée, par exemple, vu du haut du niveau, le coût total du traitement des faisceaux a réduit la fréquence d'images de Quake à la vitesse des tortues. C'est-à-dire qu'en fin de compte, il s'est avéré que la solution avec les arbres de faisceaux souffre presque des mêmes maladies que l'algorithme de l'artiste: le pire des cas est bien pire que le cas moyen, et il ne s'adapte pas bien avec une complexité croissante du niveau.

Nouveau moteur 3D tous les jours

Après que l'arbre à poutres a commencé à fonctionner, John a travaillé sans relâche pour accélérer le moteur 3D, essayant constamment d'améliorer sa structure, plutôt que d'apporter des modifications à la mise en œuvre. , , : « , ...», , . , , , . , . , . . , , , FIFO- Paradise .

raycast : , 8x8, ; , , BSP-, , . , , , , ; , , . , , . : , .

: Le monde est représenté comme un ensemble de plans de surface. Les polygones apparaissent indirectement aux intersections des plans et sont supprimés des plans à la dernière étape avant le rendu. Cela permet un découpage rapide et une très petite quantité de données (par rapport aux polygones, les plans sont décrits de manière beaucoup plus compacte), mais il faut beaucoup de temps pour extraire les polygones des plans.

Tampon de dessin : z-, , , . , , , , . : , 256 0-8 ; x86 8 .

: , , . , . , ; , .

: , , . , , , . , .

, — , , BSP- , BSP- . , DOOM (2D), BSP- DOOM 2D- . 3D , . BSP , , . , , BSP.

, , , - . BSP, , , . 3:30 , , , , , , , .

: (potentially visible set, PVS) . PVS 1 . . BSP , . , , , , . , BSP , , PVS 20 .

20 ( PVS), (PVS , , , 50%, 150%). , PVS ; , VSD, . , — , , , .

, PVS , , «» . , , , , , «» , .

-

Qu'est-ce que cela signifie? , : - . PVS , ( PVS — , ). , PVS — . , ?

Pas du tout. , , . , , .

, , . : — , . , , «» . , « »; . VSD, , . , « » , ( , ) PVS .

La chose la plus difficile au monde est de s'éloigner de la solution habituelle assez bonne à un problème complexe et d'essayer de trouver une autre meilleure solution. Il me semble que pour cela il vaut mieux essayer de nouvelles idées folles et toujours, toujours essayer de simplifier. L'un des objectifs de John était d'avoir moins de code dans chaque jeu 3D suivant que dans le précédent; il pensait que s'il en apprenait davantage, il serait en mesure de résoudre les problèmes plus efficacement avec une plus petite quantité de code.

Et tandis que ce système fonctionne assez bien pour lui.

Apprenez maintenant, payez à l'avance

, . , Dr. Dobb's Journal , — . , Tiny C , D-Flat , - DDJ . ( , .) — , DDJ .

Grâce à cette philosophie, id Software m'a permis de dire dans cet article comment fonctionne Quake avant même sa sortie. Et c'est pourquoi id a publié le code source complet de Wolfenstein 3D sur ftp.idsoftware.com/idstuff/source [env. transl.: maintenant les codes source sont affichés sur github ] ; vous ne pouvez pas simplement recompiler le code et le vendre, mais vous pouvez découvrir comment fonctionne un jeu réussi à grande échelle; examinez le fichier wolfsrc.txt du répertoire ci-dessus pour plus de détails sur la façon dont le code peut être utilisé.

: , . , , , , , . ; — , . , !

Les références

Foley, James D., et al. , Computer Graphics: Principles and Practice , Addison Wesley, 1990, ISBN 0-201-12110-7 (, BSP-, VSD).

Teller, Seth, Visibility Computations in Densely Occluded Polyhedral Environments (), http://theory.lcs.mit.edu/~seth/ .

Teller, Seth, Visibility Preprocessing for Interactive Walkthroughs , SIGGRAPH 91 proceedings, pp. 61-69.