Trier les faces transparentes de manière efficace à l'heure de la 3D accélérée. v2.02 - 07/2001 (c) 2001 Jean-Michel Hervé / Rivage Games Mise à jour : après la vaste incompréhension de l'utilisation de l'algorithme de tri lui même, une section décrivant ce tri a été rajouté afin de mettre un terme à la polémique. Cette documentation peut donc maintenant se suffir à elle même. Jean-Michel Hervé (jm.herve@rivagegames.com) 3D Programmer Rivage Games (http://www.rivagegames.com) Introduction ------------ A l'époque des moteurs 3D software, on préférait généralement trier les faces plutôt que d'utiliser un ZBuffer, beaucoup plus lourd en calcul. Le tri était alors un passage "obligé" de tout moteur 3D se respectant. Avec l'apparition du ZBuffer, le tri s'est avéré moins souvent nécessaire, puisque presque tous les problèmes étaient solutionnés par le ZBuffer. Cependant, il restait toujours les faces "transparentes" à afficher dans le bon ordre. A l'époque, ça ne posait pas de problème particulier, puisque de toute façon tout était fait en soft, et dans de nombreux cas, en entiers, la FPU étant alors vue comme quelque chose d'assez lent et peu pratique. Or, trier des entiers rapidement, c'est facile et bien documenté. Avec l'apparition des cartes 3D, on ne s'est mis qu'à utiliser du flottant, complexifiant du même coup le tri des faces. En effet, trier des valeurs flottantes n'est pas aussi évident que trier des valeurs entières. De plus, les cartes 3D ont apporté de nouvelles contraintes à respecter le plus possible. Dans ce contexte, on s'aperçoit donc que le tri de faces transparentes n'est pas un problème trivial à résoudre à la va-vite, sous peine de pénaliser le moteur entier. Note : le tri des faces alpha n'a d'interet que lorsque plusieurs modes de blending différents sont utilisés sur la même scène, ou lorsque le blending utilisé est dépendant de l'ordre dans lequel il est effectué. En effet, si l'on utilise uniquement des faces en additif le tri devient dès lors inutile : il suffit d'afficher les faces sans mise à jour du ZBuffer, mais en conservant le test, et ce après toutes les faces non transparentes. Cependant, lorsque l'on mélange de l'additif avec du multiplicatif, du srcalpha et autres modes de blending, le tri s'avére dès lors indispensable pour obtenir un résultat cohérent. Note : cet article ne s'interessera pas aux optimisations possibles spécifiques au 3Dnow! ou au SSE. Je suppose qu'il est possible de trouver de nouvelles optims utilisant ces jeux d'instructions, mais ils nécessitent beaucoup plus de travail de mise en place, et seront donc éventuellement étudiés dans un article ultérieur si nécessaire. Note : cet algorithme a été, à la base, pensé par David Alloza (de Rivage Games également), et implémenté par moi même. Il existait sans doute déjà auparavent, mais ne le connaissant pas à l'époque, nous avons mené notre propre réflexion personnelle à ce sujet. Les problèmes ------------- Sur plateforme x86, avec coprocesseur intégré x87 (intégré seulement depuis le 486DX), on peut noter plusieurs problèmes potentiels : - d'une part, les comparaisons de flottants quelconques sont assez lentes, principalement à cause de l'architecture du couple x86/x87. - d'autre part, les conversions flottant->entier et entier->flottant sont loin d'être rapide également (notamment sur les processeurs plus modestes tels que les Pentium II et autres K6). Ceci concerne donc les restrictions du coté CPU du problème. Il va nous falloir éviter au maximum les comparaisons de flottants, et également éviter de les convertir en entier. Mais il existe d'autres limitations, que l'on doit aux cartes 3D cette fois ci : - Nécessité de limiter au maximum les changements de renderstate. - Nécessite de limiter au maximum les changements de texture. - Nécessité d'envoyer des batchs de plusieurs faces plutôt qu'une seule face à la fois. Nous avons donc toute une série de contraintes dont nous devons tenir compte pour pouvoir bénéficier d'une vitesse de traitement optimale. Une petite chose à signaler au passage : lorsque la carte 3D travaille, il ne faut pas perdre de vue que le processeur central peut, lui aussi, travailler. On appelle ça le "parallélisme". L'idéal est donc de paralléliser le travail du CPU avec le travail du GPU au maximum. Les solutions ------------- Intéressons nous d'abord aux problèmes purement CPU. Premièrement, prenons le problème de la conversion flottant->entier. Il est interessant de constater que, de part son encodage, le float (32bits donc) est organisé de la manière suivante : - 1 bit de signe - 8 bits d'exposant - 23 bits de mantisse pour un total de 32bits donc, très logiquement. On peut remarquer que, dans le cas très précis qui nous intéresse actuellement, le bit de signe ne représente aucun intéret pour nous. De plus, on peut remarquer que, étant donné que l'on utilise un ZBuffer, il est très facile de normaliser la valeur Z entre le ZMin et le ZMax (les plans de clipping respectifs), pour les faire correspondre à une valeur entre 0 et 1. Ou, plus précisement, entre ZMin/ZMax et 1. Ce qui limite fortement les variations de la mantisse, que l'on peut donc facilement prévoir, connaissant ZMin et ZMax. Il est alors interessant de constater, une fois de plus, que relativement peu de bits deviennent significatifs pour nous ! Il suffit alors de récupérer juste ces bits la, et nous obtenons une valeur tout à fait cohérente avec la progression du Z, bien qu'évidemment moins précise. Lors de la mise en place, nous avons essayé diverses valeurs, et nous avons finalement opté pour ce résultat : #define ALPHAPRECBIT 11 #define ALPHAPREC (1 << ALPHAPRECBIT) #define ALPHAMASK (ALPHAPREC - 1) typedef union { int ValeurEntiere; float ValeurFlottante; } Float; Float Valeur.ValeurFlottante = 0.5f; ZListIndex = ((Valeur.ValeurEntiere >> 16) & ALPHAMASK); On peut donc remarquer que l'on prends ici 7 bits de la mantisse, et 4 bits de l'exposant, ce qui devrait suffir pour la plupart des utilisations. On à donc au final 2048 valeurs Z différentes seulement. En cas de besoin, il est toujours possible d'augmenter cette précision. Cependant, des tests en condition réelle nous ont permis de constater que ces valeurs étaient suffisantes. Voilà donc résolu le problème de la conversion en entier ! Elle se fait maintenant à très peu de frais, et nous donne une valeur très cohérente, probablement davantage cohérente que lors d'une bete conversion float->integer. Le tri ------ Maintenant que l'on a fait ce traitement, on va travailler avec des valeurs très petites. Il est donc envisageable d'utiliser un tri par insertion pour trier efficacement tout ce petit monde. Etant donné que peu de monde a fait le lien entre ma description et l'algo de tri utilisé proprement dit, je vais donc décrire le principe du tri dit "par insertion", bient qu'il différe de la variante "généraliste" du tri par insertion, étant donné qu'il s'agit d'une implémentation pour laquelle on a une bonne connaissance de la plage (très limitée) des valeurs. Description du tri ------------------ Connaissant déjà toute la plage des valeurs possible, il devient alors facile d'éviter d'avoir à les trier. Ces valeurs étant relativement peu nombreuses, on peut directement les placer à la bonne "case". Le principe du Radix est un peu similaire, sauf qu'il implique de compter le nombre de valeurs avant pour savoir où les placer. Cette fois ci on évite ce problème : on va directement utiliser autant de listes chainées qu'il y a de valeurs possibles au Z. Mettons qu'il y ait 2048 valeurs possibles : on va donc faire 2048 listes chainées. Pour chaque face, on va la rajouter à la liste chainée correspondant à son Z : on l'insert. On a donc quelque chose dans ce gout la : 0 : Face1, Face2, Face3 1 : Face4, Face5 2 : - 3 : Face6, Face7, Face8, Face9 Dans cet exemple, on a 9 faces, pour 4 valeurs possibles de Z. Elles sont donc mises directement dans la bonne liste. Maintenant, rajoutons une face supplémentaire, Face10, ayant Z = 1 : On choisit la bonne liste : 1 : Face4, Face5 Et on rajoute la face à cette liste : 1 : Face4, Face5, Face10 On a donc au final : 0 : Face1, Face2, Face3 1 : Face4, Face5, Face10 2 : - 3 : Face6, Face7, Face8, Face9 On voit que, une fois la face ajoutée, la liste est prête, aucune opération n'a besoin d'être effectuée pour la trier. Il existe de nombreuses manières d'eviter les problèmes de vitesse diminuant avec le nombre de faces triées. Par exemple, il suffit, pour chaque liste chainées, de stocker en permanence l'endroit où stocker une nouvelle face potentielle. Ainsi, plus besoin de parcourir la liste pour la rajouter ! Le tri devient alors d'une simplicité enfantine. Pour gérer les listes chainées, plutôt que d'avoir une "zone mémoire" par liste, il suffit de créer une seule liste, assez grande pour accueillir toutes les faces potentielles. Les 1ères entrées de la listes sont les entrées correspondant aux valeurs possibles du Z, ensuite les autres sont affectées au fur et à mesure de l'arrivée des faces. En chainant les entrées entre elles, on obtient une jolie liste pour chaque valeur, avec pour seul défaut que les éléments ne soient pas contigues, ce qui n'est pas un réel problème. De plus, pour remettre à zéro la liste de tri, il suffit donc de réinitialiser les 1ères valeurs, le reste n'étant alors plus lié de manière "naturelle", et donc ne nécessitant aucune intervention. Pour relire la liste maintenant, il suffit de parcourir, pour chacune des valeurs possibles, la liste associées. L'avantage énorme : les faces ont conservé l'ordre dans lequel elles ont été inserées dans la liste ! Si vous avez pris la précaution de trier vos faces par matériaux auparavant (dans un outil par exemple, ou au chargement), vous pouvez alors très facilement faire des batchs de faces ayant le même matériaux, et donc augmenter encore les performances. Justification de l'utilisation de ce tri ---------------------------------------- Je vais plutôt maintenant justifier ce choix, par rapport à d'autres tris plus "classiques" tels que le radix et autres. L'un des gros avantages du tri par insertion, c'est que le temps d'insertion d'une face est très constant, et donc est idéal pour trier un grand nombre de faces. De plus, ce temps est très court. Autre avantage, il n'y a pas de "tri final" avant affichage : la liste est EN PERMANENCE triée convenablement. L'avantage ici, c'est que le plus gros du temps du tri est pris par l'insertion des faces, or cette insertion est dispatchée sur l'ensemble du temps d'affichage de la scène, ce qui permet donc de paralléliser un maximum ce travail avec le travail de la carte 3D ! On pourrait craindre de voir le temps de parcours de la liste, au moment de l'affichage final, constituer ce "noyaux dur", équivalent du "traitement final" des autres algorithmes. Cependant, il est interessant de remarquer que, pendant tout le parcours de la liste, des faces sont envoyées, et que donc, une fois encore, ce travail est bien parallélisé avec le travail de la carte 3D elle même, réduisant d'autant l'impact de ce parcours final. D'autre part, il est interessant de constater que, étant donné que l'on a que peu de valeurs possibles pour chaque Z, il est tout à fait envisageable de parcourir la liste pour toutes les valeurs d'un Z donné, pour afficher les faces en "groupes de faces" utilisant la même texture, le même materiau, etc. et donc de fournir des performances améliorées encore en évitant les changements de renderstate et de texture au maximum et en faisant des batchs de faces de taille plus consequente qu'une seule face. Conclusion ---------- C'est à vous d'implementer, voir d'améliorer cet algorithme. Il est interessant de voir qu'il a été conçu, à l'époque, pour traiter des faces dont les transformations étaient faites en soft, puis envoyées à Direct3D. La valeur "normalisée" du Z était donc, très logiquement, disponible, ce qui réduisait encore le coup total du tri en lui même. De nos jours, il faut compter avec le T&L... ce qui rends les choses un peu plus compliquées encore. Si vous trouvez mieux, n'hésitez pas à me le faire savoir :) A propos de l'auteur -------------------- Je suis actuellement développeur, spécialisé dans le développement de moteurs 3D, dans la société que j'ai co-fondé avec Martin Korolczuk et David Alloza, Rivage Games. Auparavent, j'ai été développeur 3D chez Lankhor durant un an et demi environ, pour qui j'ai travaillé sur F1 World Grand Prix (PC) et WarmUp! (PC et PSX).