Potentially visible set

Pour les articles homonymes, voir PVS.

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 zones de l'espace (ou directement des groupes d'objets ou polygones) potentiellement visibles pré-calculés, puis lus à l'exécution pour avoir rapidement une estimation des zones et/ou polygones potentiellement 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. Quelle que soit la structure spatiale utilisée (bsp, octree, bvh, etc.) la plupart des algorithmes de calcul de pvs nécessitent de convertir temporairement les zones de l'espace en "secteurs" (zones définies par des polygones, les polygones à travers lesquels on peut voir sont appelés « portails »).

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^[1],[2].

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.

On trouve de nombreux documents et études sur ces algorithmes^{[3],[4],[5],[6]}.

L'un des algorithmes les plus performants, mais très complexe à implémenter, est la "méthode de fredo durand" qui permet de calculer directement des listes de polygones ou objets visibles, dans n'importe quelle structure de partitionnement. Il est basé sur le principe des "projections étendues" et il est accéléré par la carte vidéo: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.8373&rep=rep1&type=pdf

L'algorithme le plus connu, non générique mais assez facile, est celui utilisé par l'id Tech engine (moteur de quake). Il est similaire au clipping de portails en temps réel, à la différence que les plans de clipping ne partent pas d'un point de caméra, mais d'un portail (méthode des plans séparateurs). Pour plus d'informations, voir la source de l'id tech: http://www.shacknews.com/file/7443/quake-3-132-source-code

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^[7],[8]. 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...

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^[9].

• Calculer une subdivision optimale afin de maximiser l'occlusion^[10],[11].
• Compresser les listes de zones visibles afin d'optimiser la mémoire^[12].
• 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 efficace 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.

Pages des auteurs cités (incluant les publications) :

• Jiri Bittner
• Daniel Cohen-Or
• Fredo Durand
• Denis Haumont
• Shaun Nirenstein
• Seth Teller
• Peter Wonka

Autres :

• Selected publications on visibility

• Portail de l'informatique théorique
• Portail de l’imagerie numérique