Potentially visible set

Un Potentially Visible Set est une technique utilisée pour accélérer le rendu des environnements en trois dimensions.

C'est une forme de détermination des surfaces cachées (ou occlusion culling), basée sur des groupes de polygones potentiellement visibles pré-calculés, puis lus à l'exécution pour avoir rapidement une estimation des polygones visibles.

Le terme PVS est parfois utilisé pour faire référence à tout type d'occlusion culling (sachant que c'est toujours ce que ces algorithmes calculent), bien qu'on l'emploie le plus souvent pour parler d'un culling d'occlusion basé sur des listes pré-calculées de relations de visibilité entre des régions de l'espace. Afin de faire cette association, l'espace où évolue la caméra est subdivisé en régions (en général convexes) et un PVS est calculé pour chaque région.

Les avantages de pré-calculer la visibilité sont les suivants :

• L'application a juste à consulter la liste pré-calculée de la zone où se trouve la caméra. Cette liste sera réduite avec le culling de frustum avant l'affichage. C'est beaucoup plus rapide que de calculer l'occlusion culling en temps réel.
• Le temps de rendu d'une image est limité à la fréquence de l'écran et s'il est dépassé le programme ne rend pas toutes les images ou ralentit. Par exemple pour un écran de 200 Hz, seulement 5 millisecondes sont disponibles pour déterminer la visibilité, envoyer les images à la carte vidéo, et calculer l'intelligence artificielle, la physique, et toutes sortes de routines. Le pré-calcul de l'occlusion libère les ressources processeur pour garantir une vitesse maximale.

Les inconvénients sont :

• Le stockage des PVS consomme plus de mémoire (cela s'optimise avec un encodage de booléens dans des nombres entiers).
• Le temps d'encodage des PVS peut être très long si l'environnement est grand.
• Plus les zones de l'espace sont grandes, moins l'occlusion est précise par rapport au temps réel.

Le premier problème du calcul de PVS peut se décrire ainsi : à partir d'un ensemble de régions polyédrales, calculer un ensemble de régions visibles pour chaque région.

Il existe différents groupes d'algorithmes, selon le type de visibilité qu'ils pré-calculent.

Algorithmes conservatifs

Ce sont les algorithmes utilisés dans les applications où la qualité d'image est prioritaire : jeux vidéo, cd-rom, multimédia...

Ils surestiment la visibilité afin de n'avoir aucun trou à l'affichage. Le résultat est qu'aucune erreur d'image n'est possible, cependant, il est possible de surestimer la visibilité de façon importante et ralentir le rendu à cause de nombreuses faces recouvertes. La difficulté est de réduire cette surestimation.

Ce type d'algorithmes est très répandu, on trouve une bonne documentation sur les deux plus connus :

• algorithme de cohen-or et al.
• algorithme de Durand, plus générique. Proche de l'occlusion en temps réel. Basé sur des caméras virtuelles et du clipping à 2 ou 1 dimensions qui peut être intersection (portails) ou soustraction (antiportails).

Algorithmes agressifs

Ils sous-estiment la visibilité de façon conséquente de telle sorte qu'aucun polygone recouvert ne soit référencé dans un PVS, d'où des trous visibles en raison de polygones partiellement visibles et non référencés. Le point dur est de réduire cette marge d'erreur au minimum.

Ils sont utilisés lorsque la vitesse de rendu est prioritaire sur la qualité d'image : simulations, recherche...

Algorithmes approximatifs

Plus rapides à calculer que les deux groupes précédents mais génèrent à la fois des trous et des faces recouvertes. Sont utilisés lorsque la rapidité de l'encodage du PVS est prioritaire sur la qualité de l'image et la vitesse du rendu.

• Calculer une subdivision optimale afin de maximiser l'occlusion.
• Compresser les listes de zones visibles afin d'optimiser la mémoire.
• Optimisation de l'encodage du PVS, qui peut être très long.
• La principale optimisation est de s'appuyer sur une recherche de chemin de type parcours en profondeur (depth first search), de façon à faire le minimum de tests. Pour tout culling basé sur des portails, la recherche de chemin est requise d'office afin de trouver les suites de portails.
• Pour les maillages complexes on simplifie la géométrie au préalable. Pour un intérieur on choisit les portails dans les zones étranglées (portes, fenêtres), on simplifie leur géométrie avec des polygones convexes englobants. Pour un extérieur on modélise des boites englobées qui servent d'occluders (on peut les calculer avec une grille de discrétisation de type arbre kd ou octree pour des terrains naturels).

• Plutôt que de calculer des listes de polygones visibles, il est plus optimal de calculer des listes de groupes de polygones visibles.
• Calculer des listes de zones visibles plutôt que d'objets visibles permet de trouver la visibilité d'objets mobiles qui se déplacent à travers ces zones.
• Pour les grands espaces, on peut retrancher encore des zones au PVS avec un depth culling (agressif) pour limiter la profondeur de champ.
• Pour les grands espaces un PVS peut être codé sur deux niveaux d'affichage : les zones de l'arrière plan sont plus grandes et/ou contiennent une version simplifiée du maillage.
• Pour les applications multijoueur le PVS permet d'optimiser le transfert de données : un joueur n'envoie ses données détaillées qu'aux joueurs présents dans son PVS.