Inside Quake: Toujours envisager des alternatives

Le programmeur Michael Abrash, qui a été invité par John Carmack à travailler sur le moteur du premier tremblement de terre au milieu des années 90, a écrit une série d'articles pendant le processus de développement. Ceci est la deuxième colonne de cette série. La traduction du premier est ici .

Je dois avouer: je me suis lassé du rock classique. La dernière fois, j'étais heureux d'écouter quelque chose de Cars ou de Boston depuis longtemps, il y a environ 20 ans. De plus, je n'ai jamais été particulièrement attiré par Bob Seager et Queen, sans parler d'Elvis, donc peu de choses ont changé. Mais j'ai réalisé que quelque chose a changé quand j'ai voulu changer de radio quand j'ai entendu Allman Brothers, ou Steely Dan, ou Pink Floyd, ou, Dieu, pardonnez-moi, les Beatles (mais seulement sur des choses comme "Bonjour au revoir" et "Je vais Pleurez plutôt, pas Ticket to Ride ou A Day in the Life; je ne suis pas encore allé si loin). Il n'a pas fallu longtemps pour en trouver les raisons; J'ai écouté les mêmes chansons pendant un quart de siècle et je m'en lasse.

Je raconte tout cela parce que lorsque ma fille et moi sommes sortis du café un soir, la station de radio «Il n'y a pas d'alternative» a été allumée pour la première fois dans la voiture.

Nous parlons d'une fillette de dix ans qui a grandi avec un régime constant de vieux tubes. Elle aime les mélodies, les chansons entraînantes et les bons chanteurs. Vous ne trouverez rien de tout cela en écoutant une station de rock alternative. Par conséquent, il n'est pas surprenant que lorsque j'ai allumé la radio, elle ait d'abord dit: "Fu!"

Mais voici ce qui m'a surpris: après avoir écouté pendant un moment, elle a dit: "Tu sais, papa, mais c'est vraiment intéressant."

Cela ne m'a pas seulement laissé entendre quel genre de musique grondait dans la maison quand elle était adolescente. Son adoption rapide du rock alternatif (par rapport à ma fascination pour la musique de ma propre jeunesse pendant dix ans) m'a rappelé quelque chose qui est facilement oublié quand on vieillit et que le style de vie s'installe. Cela m'a rappelé qu'il était nécessaire de garder l'esprit ouvert et de se préparer - en plus, de s'efforcer - pour essayer de nouvelles choses. Les programmeurs ont tendance à être attachés à des approches familières et sont enclins à les utiliser s’ils s’acquittent correctement des tâches. Mais il y a toujours des alternatives à la programmation, et je trouve qu'elles valent souvent la peine d'être explorées.

Mais étant donné la nature en constante évolution de Quake , je ne devrais vraiment pas avoir besoin d'un tel rappel.

Flux créatif

En janvier, j'ai décrit un flux créatif qui a conduit John Carmack à décider d'utiliser des polygones d'ensemble potentiellement visible (PVS) précalculés pour chaque point de vue possible dans Quake (un jeu que nous développons conjointement dans id Software). Le calcul préliminaire de PVS signifie qu'au lieu de passer beaucoup de temps à rechercher dans la base de données des polygones visibles du point de vue actuel dans la base de données mondiale, nous pouvons simplement dessiner tous les polygones dans le PVS en arrière (en prenant l'ordre de l'arbre BSP du monde; discussion sur BSP- voir les arbres dans nos colonnes pour mai, juillet et novembre 1995), et obtenir le rendu de la scène correctement sans recherche, permettant un rendu en arrière pour effectuer la dernière étape de suppression de la surface cachée (HSR). C'était une idée géniale, mais pour l'architecture Quake, le chemin n'est pas encore terminé.

Dessin d'objets en mouvement

Par exemple, il y a toujours eu une question sur la façon de trier et de dessiner correctement les objets en mouvement; en fait, cette question après la chronique de janvier a été posée avant tout, je vais donc lui donner du temps. Le problème principal est qu'un modèle en mouvement peut tomber dans plusieurs feuilles BSP, et lorsque le modèle se déplace, ces feuilles changent; avec la possibilité de trouver plusieurs modèles dans une feuille, cela signifie qu'il n'y a pas de moyen facile d'utiliser l'ordre BSP pour dessiner des modèles dans un ordre correctement trié. Lorsque j'ai écrit la colonne de janvier, nous avons dessiné des sprites (comme des explosions), des modèles BSP mobiles (comme des portes) et des modèles polygonaux (comme des monstres), tronquant chacun d'eux avec les feuilles qu'ils touchent, puis dessinant les pièces correspondantes lorsque chaque feuille BSP atteignait votre tour lorsque vous vous déplacez de l'arrière vers l'avant. Cependant, cela n'a pas résolu le problème du tri de plusieurs modèles mobiles dans une feuille les uns par rapport aux autres, et a également laissé des problèmes désagréables avec les modèles polygonaux complexes.

John a résolu le problème de tri des sprites et des modèles de polygones de manière étonnamment low-tech: nous les écrivons maintenant dans le z-buffer. (C'est-à-dire qu'avant de dessiner chaque pixel, nous comparons la distance à celui-ci, ou z, avec la valeur z du pixel déjà sur l'écran. Un nouveau pixel n'est dessiné que s'il est plus proche que celui existant.) Premièrement, nous dessinons le monde principal - murs, plafonds, etc. comme ça. A ce stade, aucun test du z-buffer n'est utilisé (comme nous le verrons bientôt, la définition des surfaces visibles du monde est effectuée d'une autre manière); cependant, nous remplissons le z-buffer avec des valeurs z (en fait 1 / z, comme décrit ci-dessous) pour tous les pixels dans le monde. Remplir un tampon Z est un processus beaucoup plus rapide que ne le ferait le tampon Z dans le monde entier, car il n'y a pas de lecture, pas de comparaison, il suffit d'écrire des valeurs z. Après avoir terminé le dessin et rempli le z-buffer du monde, nous pouvons simplement dessiner des sprites et des modèles polygonaux en utilisant le z-buffer et obtenir le tri parfait.

Lorsque vous utilisez le z-buffer, des questions se posent inévitablement: comment cela affecte-t-il la mémoire occupée et les performances? À une résolution de 320x200, il nécessite 128 Ko de mémoire, ce qui n'est pas anodin, mais pas tant pour un jeu qui nécessite 8 Mo pour fonctionner. Impact sur les performances: environ 10% lors du remplissage du z-buffer du monde, et environ 20% (les indicateurs varient considérablement) lors du rendu des sprites et des modèles polygonaux. En retour, nous obtenons un monde parfaitement trié, ainsi que la possibilité de créer des effets supplémentaires, par exemple, des explosions et de la fumée de particules, car le z-buffer vous permet de trier facilement ces effets dans le monde. En général, l'utilisation du z-buffer a considérablement augmenté la qualité visuelle et la flexibilité du moteur Quake, ainsi que considérablement simplifié le code, au prix de coûts de mémoire et de performances tout à fait raisonnables.

Nivellement et augmentation de la productivité

Comme je l'ai dit ci-dessus, l'architecture Quake dessine d'abord le monde lui-même, sans lire ni comparer le z-buffer, remplissant simplement le z-buffer avec les valeurs des polygones du monde en z. Après cela, les objets en mouvement sont dessinés au-dessus du monde à l'aide de la mise en mémoire tampon z complète. Jusqu'à présent, je n'ai parlé que de la façon de dessiner des objets en mouvement. Dans le reste de la colonne, je vais parler d'une autre partie de l'équation de rendu - dessiner le monde lui-même, lorsque le monde entier est stocké dans un seul arbre BSP et ne bouge jamais.

Comme vous vous en souvenez de la colonne de janvier, nous étions inquiets à la fois des performances brutes et de sa moyenne. Autrement dit, nous voulions que le code de rendu soit exécuté le plus rapidement possible, mais en même temps, afin que la différence entre la vitesse de rendu de la scène du milieu et la plus lente dans le rendu de la scène soit aussi petite que possible. Il n'y a rien de bon dans les 30 images par seconde en moyenne si 10% des scènes sont dessinées à 5 ips, car les secousses dans ces scènes seront extrêmement visibles par rapport à la scène moyenne. Il est préférable de faire la moyenne de la fréquence avec 15 images par seconde dans 100% des cas, même si la vitesse de rendu moyenne sera deux fois moins élevée.

Les PVS pré-calculés étaient une étape importante vers des performances plus élevées et plus équilibrées, car ils éliminaient la nécessité de déterminer des polygones visibles - une étape plutôt lente qui se manifestait le plus mal dans les scènes les plus complexes. Néanmoins, dans certains endroits où les niveaux de jeu sont réels, les PVS pré-calculés contiennent cinq fois plus de polygones qu'on ne le voit réellement; en conjonction avec le retrait de la surface de masquage vers l'arrière (HSR), cela a créé des «zones chaudes» dans lesquelles la fréquence d'images a été sensiblement réduite. Des centaines de polygones ont été dessinés vers l'avant et la plupart d'entre eux ont été immédiatement redessinés par des polygones plus proches. Les performances brutes dans leur ensemble ont également diminué en moyenne de 50% du redessin causé par le rendu de tout dans le PVS. Par conséquent, bien que le rendu des ensembles PVS en arrière ait fonctionné comme la dernière étape du HSR et était une amélioration par rapport à l'architecture précédente, il n'était pas idéal. John pensait qu'il y avait probablement une meilleure façon d'utiliser PVS que de dessiner d'avant en arrière.

Et il a en fait été retrouvé.

Intervalles triés

La dernière étape HSR idéale pour Quake était de supprimer tous les polygones du PVS qui se sont révélés être invisibles et de dessiner uniquement les pixels visibles des polygones restants sans redessiner. Autrement dit, chaque pixel serait dessiné exactement une fois et sans perte de performances, bien sûr. Une solution (nécessitant toutefois des coûts) consiste à dessiner d'avant en arrière, enregistrer la zone qui décrit les parties de l'écran qui se chevauchent actuellement et tronquer chaque polygone avec les bordures de cette zone avant le rendu. Cela semble prometteur, mais en fait, cela rappelle à peu près la solution d'arbre de bundle que j'ai décrite dans la colonne de janvier. Comme nous l'avons découvert, cette approche nécessite un gaspillage de ressources supplémentaires et présente de graves problèmes d'équilibrage de charge.

Vous pouvez faire beaucoup mieux si vous déplacez la dernière étape HSR du niveau du polygone au niveau de l'intervalle et utilisez la solution avec des intervalles triés. Essentiellement, cette approche consiste à transformer chaque polygone en un ensemble d'intervalles, comme le montre la figure 1, puis à trier et à tronquer les intervalles les uns par rapport aux autres, jusqu'à ce que seules les parties visibles des intervalles visibles restent pour le rendu, comme le montre la figure 2. Cela peut sembler très similaire à la mise en mémoire tampon z (qui, comme je l'ai dit ci-dessus, est trop lente pour être utilisée dans le rendu du monde, bien qu'elle convienne aux petits objets en mouvement), mais il existe des différences importantes. Contrairement à la mise en mémoire tampon z, seules les parties visibles des intervalles visibles sont balayées pixel par pixel (bien que toutes les arêtes des polygones doivent encore être pixellisées). Encore mieux, le tri effectué par mise en mémoire tampon z pour chaque pixel devient une opération d'intervalle avec des intervalles triés, et comme une propriété intégrale de la liste d'intervalles est la connectivité, chaque bord est trié uniquement par rapport à certains intervalles de la même ligne, et n'est tronqué que par quelques intervalles lorsque superposition horizontale. Bien que les scènes complexes aient pris plus de temps à traiter que les scènes simples, les pires cas n'étaient pas aussi mauvais que lors de l'utilisation d'arborescences de faisceaux ou lors du tri d'arrière en avant, car il n'y a pas de redessin et de balayage pour les pixels cachés, la complexité est limitée par la résolution en pixels et la connectivité par intervalles limite le tri des pires cas dans n'importe quelle zone de l'écran. En prime, la sortie des intervalles triés est exactement sous la forme dont un rasteriseur de bas niveau a besoin: sous la forme d'un ensemble de descripteurs d'intervalle, dont chacun consiste en une coordonnée de début et de longueur.



Génération d'intervalle

Bref, la solution à intervalles triés est assez proche de nos critères d'origine; bien que cela n'économise pas les coûts, ils ne sont pas encore entièrement terribles. Il élimine complètement le redessin et le balayage des pixels des parties superposées des polygones et est susceptible d'égaliser les performances dans les pires cas. Nous ne nous baserions pas uniquement sur des intervalles triés comme mécanisme pour éliminer les surfaces cachées, mais les PVS pré-calculés réduisent le nombre de polygones à un niveau que les intervalles triés gèrent suffisamment bien.

Nous avons donc trouvé l'approche dont nous avons besoin; il ne reste plus qu'à écrire le code et c'est fini, non? Oui et non. L'approche conceptuelle avec des intervalles triés est simple, mais étonnamment difficile à mettre en œuvre: vous devez prendre quelques décisions de conception importantes, cela prend un peu de calcul et il y a des pièges rusés. Examinons d'abord les solutions de conception.

Côtes vs intervalles

La première décision est de choisir quoi trier: intervalles ou arêtes (ces deux concepts appartiennent à la catégorie générale des «intervalles triés»). Bien que les résultats dans les deux cas soient les mêmes (une liste d'intervalles à dessiner sans redessiner), les implémentations et les implications en termes de performances sont très différentes, car le tri et la troncature sont effectués par des structures de données très différentes.

Lors du tri des intervalles, ces intervalles sont stockés dans des segments de mémoire triés par x listes liées, généralement un segment par ligne raster. Chaque polygone, à son tour, est pixellisé en intervalles, comme le montre la figure 1. Chaque intervalle est trié et tronqué dans le segment de mémoire de la ligne raster dans laquelle l'intervalle est situé, comme le montre la figure 2, de sorte qu'à tout moment, chaque segment contient les intervalles les plus proches rencontrés , toujours sans superpositions. Avec cette approche, il est nécessaire de générer à tour de rôle tous les intervalles pour chaque polygone, et chaque intervalle est immédiatement trié, tronqué et ajouté au segment de mémoire correspondant.



Figure 2: les intervalles du polygone A de la figure 1 sont triés et tronqués à intervalles du polygone B, tandis que le polygone A est à une distance constante de 100 le long de l'axe Z, et le polygone B est à une distance constante de 50 le long de l'axe Z (le polygone B est plus proche de la caméra). )

Lors du tri des bords, ces bords sont stockés dans des segments de mémoire triés par x listes liées en fonction de leur ligne raster initiale. Chaque polygone, à son tour, est divisé en arêtes, créant ensemble une liste de toutes les arêtes de la scène. Lorsque tous les bords de tous les polygones de la pyramide de visibilité sont ajoutés à la liste des bords, la liste entière est numérisée en une seule passe de haut en bas, de gauche à droite. Une liste de la liste des bords actifs (AEL) est enregistrée. À chaque étape vers une nouvelle ligne raster, les bords qui apparaissent sur cette ligne raster sont supprimés de l'AEL, les bords actifs vont à leurs nouvelles coordonnées x, les bords commençant à partir de la nouvelle ligne raster sont ajoutés à l'AEL et les bords sont triés par la coordonnée x actuelle.

Pour chaque ligne raster, une liste de polygones active (APL) triée par z est stockée. Il va dans l'ordre trié par x AEL. Lors de la rencontre avec chaque nouvelle arête (c'est-à-dire lorsque chaque polygone commence ou se termine lors du déplacement de gauche à droite), le polygone qui lui est associé est activé et trié en APL (dans le cas d'une arête de départ), comme illustré à la figure 3, ou désactivé et supprimé d'APL ( dans le cas d'un bord de fuite), comme le montre la figure 4. Si le polygone le plus proche a changé (c'est-à-dire le plus proche est un nouveau polygone ou le polygone le plus proche s'est terminé), pour le polygone qui vient de cesser d'être le plus proche, un intervalle est créé à partir du point où le polygone n'est pas vym parce qu'il est le plus proche et la fin coordonnée x des bords actuels et les x coordonnées actuelles sont enregistrées dans la décharge, qui est maintenant le plus proche. Cette coordonnée stockée est ensuite utilisée comme début de l'intervalle créé lorsque le nouveau polygone le plus proche cesse d'être devant.



Figure 3: activation d'un polygone lorsqu'un bord de départ est détecté dans AEL.



Figure 4: désactivation du polygone lorsqu'un bord de fuite est détecté dans AEL.

Ne vous inquiétez pas si vous ne comprenez pas complètement ce qui précède; ce n'est qu'un aperçu rapide des tris de tri afin que le reste de la colonne soit plus clair. Une explication détaillée figurera dans la colonne suivante.

Les intervalles générés par le tri des bords semblent être exactement les mêmes intervalles qui résulteraient du tri des intervalles; la différence réside dans les structures de données intermédiaires utilisées pour trier les intervalles dans la scène. Lors du tri des arêtes, les intervalles sont stockés à l'intérieur des arêtes jusqu'à ce que l'ensemble final d'intervalles visibles soit généré, de sorte que le tri, le rognage et la création d'intervalles sont effectués lorsque chaque arête ajoute ou supprime un polygone, en fonction de l'état de l'intervalle défini par l'arête et de l'ensemble de polygones actifs. Lors du tri des intervalles, les intervalles deviennent instantanément apparents lorsque chaque polygone est pixellisé, et ces intervalles intermédiaires sont ensuite triés et tronqués par rapport aux intervalles de la ligne de trame pour créer les intervalles finaux; par conséquent, les états des intervalles sont constamment définis de manière explicite et tout le travail est effectué directement à intervalles.

Le tri par intervalles et le tri par bord fonctionnent bien; ils ont été utilisés avec succès dans des projets commerciaux. Pour Quake, nous avons choisi le tri par bord, en partie parce qu'il semble être plus efficace et dispose d'une excellente connectivité horizontale qui fournit le temps de tri minimum, contrairement au tri potentiellement coûteux en listes liées, qui peut être nécessaire lors du tri des intervalles.Cependant, une raison plus importante était que lors du tri des bords, nous pouvons diviser les bords entre des polygones adjacents, ce qui réduit le tri, le rognage et la pixellisation des bords d'environ la moitié, et réduit également considérablement la base de données mondiale du fait que les bords deviennent communs.

Et le dernier avantage du tri des arêtes est qu'il ne fait pas de distinction entre les polygones convexes et concaves. Pour la plupart des moteurs graphiques, ce n'est pas un aspect très important, mais dans Quake, le rognage, la transformation, la projection et le tri des bords sont devenus le principal goulot d'étranglement, nous faisons donc tout notre possible pour réduire le nombre de polygones et de bords, et les polygones concaves sont très utiles à cet égard. Bien que les polygones concaves puissent également être traités par intervalles de tri, cela entraîne une baisse significative des performances.

Cependant, il n'y a pas de réponse définitive sur la meilleure approche. En fin de compte, les intervalles de tri et les bords de tri remplissent une fonction, et le choix entre eux est une question de convivialité. Dans la colonne suivante, je parlerai davantage du tri des bords avec son implémentation complète. Dans le reste de cette colonne, je poserai les bases de la prochaine en parlant des clés de tri et du calcul de 1 / z. Dans le processus, je ferai plusieurs références aux aspects du tri des bords, qui n'ont pas encore été discutés en détail; Je m'excuse, mais c'est inévitable, et tout ne deviendra clair qu'à la fin de la colonne suivante.

Clés de tri des côtes

Maintenant que nous savons que nous allons sélectionner le tri des arêtes et l'utiliser pour créer les intervalles des polygones les plus proches du spectateur, la question se pose: comment savoir si ces polygones sont les plus proches? Idéalement, nous devrions simplement stocker la clé de tri de chaque polygone, et lorsqu'une nouvelle arête apparaît, nous comparerions la clé de sa surface avec les clés des autres polygones actifs actuels afin de déterminer facilement lequel des polygones est le plus proche.

Cela semble trop beau, mais c'est possible. Si, par exemple, votre base de données mondiale est stockée sous forme d'arbre BSP et que tous les polygones sont tronqués en feuilles BSP, alors l'ordre de parcours BSP sera l'ordre de rendu correct. Par conséquent, par exemple, si vous contournez BSP d'avant en arrière, en attribuant à chaque polygone une valeur de clé incrémentielle plus grande lorsqu'il l'atteint, les polygones avec des valeurs de clé plus élevées seraient garantis devant des polygones avec des clés plus petites. Cette approche est utilisée dans Quake depuis un certain temps, mais maintenant une solution différente est appliquée pour des raisons que je vais expliquer brièvement.

Si vous n'avez pas de BSP ou une structure de données similaire, ou si vous avez de nombreux polygones en mouvement (le BSP ne traite pas les polygones en mouvement de manière très efficace), alors une autre façon d'atteindre les objectifs est de trier tous les polygones les uns par rapport aux autres avant de rendre la scène et d'attribuer les clés correspondantes en fonction de leur espace relations dans la fenêtre. Malheureusement, dans le cas général, c'est une tâche extrêmement lente, car chaque polygone doit être comparé les uns aux autres. Il existe des techniques pour améliorer les performances de tri des polygones, mais je ne connais personne qui effectuerait un tri général des polygones sur un PC en temps réel.

Une alternative consiste à trier par distance z du spectateur dans l'espace écran; cette solution correspond bien à la connectivité spatiale supérieure des bords de tri. Lorsque vous rencontrez chaque nouvelle arête sur la ligne raster, vous pouvez calculer la distance z du polygone correspondant et comparer avec les distances des autres polygones, après quoi le polygone peut être enregistré dans APL.

Cependant, obtenir des distances le long de z peut être une tâche difficile. N'oubliez pas que nous devons être capables de calculer z à n'importe quel point arbitraire du polygone, car une arête peut se produire et entraîner le tri du polygone dans l'APL n'importe où sur l'écran. Nous pouvons calculer z directement à partir des coordonnées d'écran x et y et des équations du plan du polygone, mais, malheureusement, cela ne peut pas être fait très rapidement, car z pour le plan ne change pas linéairement dans l'espace d'écran; cependant, 1 / z varie linéairement, nous utilisons donc cette valeur. (Pour une discussion sur la linéarité dans l'espace d'écran et les gradients pour 1 / z, voir la série de Chris Hecker sur la cartographie de texture dans le magazine Game Developer l'année dernière.) Un autre avantage de l'utilisation de 1 / z est que la résolution augmente avec une distance décroissante, c'est-à-dire qu'avec 1 / z, nous aurons toujours la meilleure résolution de profondeur pour les objets proches les plus importants.

Une façon évidente d'obtenir la valeur 1 / z à n'importe quel point arbitraire du polygone consiste à calculer 1 / z aux sommets, à les interpoler sur les deux bords du polygone et à interpoler entre les bords pour obtenir la valeur au point souhaité. Malheureusement, cela nécessite beaucoup de travail à faire le long de chaque côte; pire, cela nécessite une division pour calculer le pas 1 / z par pixel dans chaque intervalle.

Il serait préférable de calculer 1 / z directement à partir de l'équation du plan et de l'écran x et y du pixel qui nous intéresse. L'équation a la forme suivante:

$$

$$1/z = (a/d)x' - (b/d)y' + c/d$$

où z est la coordonnée dans l'espace z du point sur le plan qui est projeté dans les coordonnées d'écran (x ', y') (l'origine des coordonnées pour ces calculs est le centre de projection, le point sur l'écran juste en face du point de vue), [abc] est normale au plan dans la fenêtre, et d est la distance entre l'origine de la fenêtre et le plan le long de la normale. La division n'est effectuée qu'une seule fois pour chaque plan, car a, b, c et d sont des constantes pour les plans.

Un calcul 1 / z complet nécessite deux multiplications et deux ajouts, et chaque opération doit être effectuée avec une virgule flottante pour éviter les erreurs de plage. Un tel volume de calculs en virgule flottante semble coûteux, mais en fait il ne l'est pas, en particulier sur les processeurs Pentium, où la valeur du plan 1 / z à tout moment peut être calculée en langage d'assemblage en seulement six cycles.

Si vous êtes intéressé, voici une dérivation rapide de l'équation 1 / z. L'équation de l'avion pour l'avion a la forme suivante:

$$

$$ax + by + cz - d = 0$$

où x et y sont les coordonnées de l'espace de vue, a, b, c, d et z sont définis ci-dessus. Si nous faisons la substitution$$$x=x'z$ et $$$y=-y'z$(à partir de la définition de la projection en perspective; y change de signe car il augmente dans la fenêtre, mais vers le bas dans l'espace écran). En effectuant une permutation, on obtient:

$$

$$z = d / (ax' - by' + c)$$

En inversant et en développant l'équation, nous obtenons:

$$

$$1/z = ax'/d - by'/d + c/d$$

Plus tard, je montrerai le tri 1 / z en action.

Séisme et tri par z

J'ai mentionné ci-dessus que Quake n'utilise plus l'ordre BSP comme clé de tri; en fait, 1 / z est maintenant appliqué comme clé. Malgré l'élégance des dégradés, le calcul de 1 / z d'entre eux est évidemment plus lent que la simple comparaison avec la clé de commande BSP, alors pourquoi avons-nous décidé d'utiliser 1 / z dans Quake?

La raison principale est la diminution du nombre de polygones. Pour le rendu dans l'ordre BSP, il est nécessaire de suivre certaines règles, y compris les polygones lorsque l'intersection avec les plans BSP doit être divisée. Cette séparation augmente considérablement le nombre de polygones et d'arêtes. Grâce au tri par 1 / z, nous pouvons laisser les polygones indivis, mais toujours obtenir l'ordre de dessin correct, nous devons donc traiter beaucoup moins d'arêtes; tandis que le rendu est généralement accéléré, malgré le surcoût de tri par 1 / z.

Un autre avantage du tri 1 / z est qu'il résout les problèmes de tri mentionnés au début de cet article: les modèles en mouvement, qui sont eux-mêmes de petits arbres BSP. Le tri dans l'ordre mondial BSP ne fonctionnera pas ici car ces modèles sont des BSP distincts et il n'y a pas de moyen facile de les incorporer dans l'ordre séquentiel du monde BSP. Nous ne voulons pas utiliser la mise en mémoire tampon z pour ces modèles car ce sont souvent de gros objets (par exemple, des portes), et nous ne voulons pas perdre les avantages de réduire le redessin que les portes fermées fournissent lors du rendu dans la liste des bords. Lorsque vous utilisez des intervalles triés, les arêtes des modèles BSP en mouvement sont simplement placées sur la liste des arêtes (tronquant d'abord les polygones afin qu'ils ne se croisent pas avec les surfaces solides du monde pour éviter la complexité,liés à la pénétration mutuelle) au lieu de tous les bords du monde, et le reste est trié par 1 / z.

Aller de l'avant

L'article, sans aucun doute, contient une énorme quantité d'informations, et beaucoup n'a pas encore été mis dans votre tête. Le code et l'explication du prochain article vous aideront; si vous voulez jeter un coup d'œil à l'avance, au moment où vous lisez cet article, le code devrait être disponible sur ftp.idsoftware.com/mikeab/ddjsort.zip. Il vaut également la peine de jeter un œil à Computer Graphics Foley et Van Dam ou à Elements de procédure pour Computer Graphics Rogers.

On ne sait pas pour l'instant comment le résultat de Quakedoit trier les bords - dans l'ordre BSP ou 1 / z. En fait, rien ne garantit que les intervalles triés sous quelque forme que ce soit seront la solution finale. Parfois, il semble que nous changeons les moteurs graphiques aussi souvent qu'ils mettent Elvis sur les stations de radio dédiées aux tubes des années 50 (mais, espérons-le, avec des résultats beaucoup plus esthétiques!), Et nous envisagerons sans aucun doute des alternatives jusqu'à la date de sortie les jeux.