The developer’s diary part 2 : Système de détermination de visibilité
| Introduction Dans cet opus du journal de développement, je vais aborder une solution de visibility determination system (VSD) que j'ai récemment intégrée dans le moteur de El Matador.
Pour la plupart des jeux en 3D (sauf quelques exceptions évidemment) le système VSD est un élément clé qui affecte la rapidité d'affichage. Son rôle est capital : parmi des milliers d'objets, qui représentent au total des millions de polygones, le système VSD doit déterminer lesquels sont visibles par le joueur. Si tout ce qui se trouvait dans une pyramide de vision était calculé dans un environnement complexe, les FPS
obtenues ne seraient guère interactives, même avec le plus puissant des PC. Si vous ne me croyez pas, vous pouvez lancer Doom 3, taper "noclip" dans la console puis sortir de la pièce et regarder un peu autour de vous. Si vous réussissez à avoir plus de 1 FPS, bravo ! |
|
 |
Le système VSD est très important pour les jeux qui se déroulent dans un décor intérieur (Doom 3), tandis que les jeux se déroulant en extérieur (Farcry) utilisent davantage un système de Level of Detail (LOD). Si le jeu se déroule dans un décor mixte, ce qui est notre cas, les choses se complique.
J'ai toujours été intéressé par les systèmes VSD et les problèmes qui y sont liés. J'ai suivi le développement des tendances actuelles depuis à peu près 10 ans, et je dois dire que quand j'avais intégré un système BSP-PVS pour notre premier moteur 3D il y a quelques années, je n'aurais jamais imaginer que nous trouverions une méthode aussi exotique que celle que nous utilisons à présent pour gérer les visibilités ;o)
| “Base de données spatiale” & VSD La scène 3D doit inclure des informations sur l'agencement spatial des objets : c'est ce qu'on appelle l'index spatial (ou base de données spatiale si vous préférez). Cela autorise toute sorte d'activités classiques (représentations, calculs de collisions etc.). Cet index spatial est une structure de données qui permet d'effectuer certaines opérations de manière très
efficace.
Vous pouvez l'imaginer comme un répertoire téléphonique classé par ordre alphabétique (c'est à dire un index unidimensionnel). Si vous essayez de trouver un numéro de téléphone dans un répertoire qui n'est pas classé par ordre alphabétique, vous aurez probablement du mal.
C'est la même chose pour un index spatial sauf qu'il existe de nombreuses méthodes d'en mettre un en place. D'un point de vue pratique et non-technique, la principale différence qui nous intéresse (surtout les designers), c'est de savoir si cet index est statique ou dynamique. Si le découpage spatial de la scène est statique, représenté par exemple par des arbres BSP (la méthode BSP est utilisés par les moteurs basés sur
Quake), vous devez compiler la scène au format final après chaque modification conséquente de la carte, ce qui peut s'avérer peu pratique, lent et potentiellement générateur d'erreurs. Nous avons conçu un découpage spatial inédit dans notre moteur pour Matador (nous utilisions aussi la BSP auparavant) : un arbre AABB dynamique. Cette structure est complètement dynamique et toute manipulation des objets de la carte est
immédiatement répercutée. Vous pouvez insérer, déplacer ou effacer des objets sans jamais devoir "compiler". |
|
|
Les méthodes statiques de représentation du décor utilisent généralement des structures précalculées (statiques) pour déterminer la visibilité. Dans le cas du moteur Quake et de ses dérivés, nous avons utilisé la célèbre structure Potentially Visible Set (PVS), qui inclut des informations indiquant quelle partie de la carte est visible depuis tel ou tel endroit. Une telle structure est très efficace, ce qui
compense le recalcul fastidieux après chaque changement conséquent de la carte. Comme nous utilisons une méthode dynamique de partage de la scène, la détermination de la visibilité est également totalement dynamique.
Au lieu de déterminer ce que nous pouvons voir, le système calcule ce que nous ne pouvons pas voir. Tout cela fonctionne bien. Les systèmes PVS utilisent ce qu'on appelle des portails (ce sont en fait des fenêtres par lesquelles le système décide ce que nous pouvez voir), et notre système utilise ce que nous appelons des anti-portails (ou des écrans), qui déterminent ce qui n'est pas visible.
L'occlusion culling
Le système de visibilité de notre moteur tombe dans la catégorie des systèmes d'image space occlusion culling, qui exploite le fait que certains objets masquent la vue très efficacement et interdisent donc l'affichage des objets qui se trouvent derrière. Ce qui est appréciable dans de tels systèmes, c'est qu'ils sont facilement utilisables (moyennement quelques optimisations) dans n'importe quel environnement 3D, qu'il
s'agisse de décors intérieurs ou extérieurs.
Il est presque toujours possible de trouver des objets pour bloquer la vue. Le moteur Typhoon2 utilise un système de Hierarchical Occlusion Maps (HOM), ce qui est une manière très efficace de gérer la sélection d'occlusion : les objets, qui bloquent efficacement l'image (qui s'intègrent bien dans le décor), sont décrits à un z-buffer spécial, à partir duquel un zbuffer hiérarchique est créé (comme pour la création de
mipmaps sur les textures, mais les règles de filtrage sont différentes) pour la visibilité des autres éléments de la scène (encore d'une manière hiérarchique, à cause de l'index spatial).
Les z-buffers hiérarchiques sont utilisés par presque toutes les cartes graphiques récentes au niveau des pixels, car cette structure permet de déterminer très efficacement si une partie de la scène est occultée par une autre partie plus proche et qu'il est dont inutile de la calculer.
Certains lecteurs trouvent peut-être que cette histoire de hiérarchie devient trop compliquée, mais pour simplifier, cela s'applique à tout algorythme ou programmation : le hiérarchique est rapide, le non-hiérarchique est lent ;o)
De l'exotisme dans l'occlusion culling ;o)
Certaines choses sont nécessaires pour faire fonctionner le système d'occlusion aussi efficacement que possible.
Tout d'abord il faut qu'une rasterisation des occulteurs dans le z-buffer spécial (bien inférieure à une résolution résultante de l'image) soit aussi efficiente que possible. C'est très facile à obtenir en utilisant des éléments de décor et des objets spécialement modelés avec très peu de polygones pour les occulteurs, et en dessinant ces occulteurs avec un logiciel rasteriseur écrit à la main et optimisé (utilisation
d'instructions SSE) (de telles choses étaient programmées lorsque les accélérateurs graphiques n'existaient pas encore).
Bien que le moteur utilise ce système, la modélisation de versions simplifiées des modèles - occulteurs était trop longue, alors nous avons tout intégré d'une manière un peu différente. Le système actuel fonctionne de la manière suivante : les occulteurs sont dessinés par un accélérateur graphique très rapide, qui ne requiert pas l'utilisation de versions simplifiées des modèles. Il ne peut cependant pas gérer (en tout cas
pas sur bus AGP ni avec la version actuelle de Direct3D) la lecture de données du z-buffer de la carte graphique vers le stockage principal du PC.
En comparant les résultats, l'utilisation actuelle d'occulteurs GPU compense la rasterisation.
Le seul inconvénient des système d'occlusion culling est peut-être qu'ils fonctionnent bien dans un environnement où de nombreux objets viennent bloquer la vue, mais pêchent en présence de grandes quantités d'objets qui ne bloquent pas la vue. Evidemment, ce sont ces objets que les designers adorent placer par milliers sur les cartes (caisses, bidons, chaises etc.).
Le problème, c'est que si vous entrez dans une salle avec des centaines de ces objets, le système d'occlusion passe tellement de temps à déterminer quel objet doit être visible qu'il perd toute efficacité.
Nous avons résolu ce problème dans notre moteur en conservant des statistiques de visibilité dans un cache spécial, ce qui permet d'optimiser les demandes de calcul de visibilité de chaque objet. Par exemple si vous passez à côté d'un tas de petits objets, le système sait qu'ils ont été visibles pendant les dernières X secondes et il les dessine automatiquement sans se poser la question.
Voilà, je pense que ça suffit pour aujourd'hui, il faut en garder assez pour la prochaine fois.
Merci d'avoir lu tout ça !
Petr
Lire la première partie
|
