Potentially visible set

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir PVS.

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

C'est une forme d'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.

[modifier] avantages / inconvénients

L'avantage de précalculer la visibilité est:

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 le culling d'occlusion 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 processeurs 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.

[modifier] Problème principal

Le premier problème du calcul de pvs peut se décrire ainsi: soit ensemble de régions polyhèdrales, pour chaque région calculer un ensemble de régions visibles.

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

S. Nirenstein, E. Blake, and J. Gain. Exact from-region visibility culling. In Proceedings of the 13th workshop on Rendering, pages 191–202. Eurographics Association, June 2002.

Daniel Cohen-Or, Yiorgos Chrysanthou, Cl´audio T. Silva, and Fr´edo Durand. A survey of visibility for walkthrough applications. IEEE TVCG, 9(3):412–431, July-September 2003.

[modifier] 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.

La liste de ce type d'algorithmes est importante, on trouve une bonne documentation sur les deux plus connus:

-algorithme de cohen-or et al. Basé sur les portails http://sibgrapi.sid.inpe.br/rep-/sid.inpe.br/banon/2002/10.25.09.12 http://www.imr.sandia.gov/papers/imr13/ernst.pdf http://www.cg.tuwien.ac.at/research/vr/occfusion/wonka_EGWR2000.pdf

-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). http://www.tml.tkk.fi/Opinnot/Tik-111.500/2003/paperit/MikkoLaakso.pdf

[modifier] 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. Ils sont utilisés lorsque la vitesse de rendu est prioritaire sur la qualité d'image: simulations, recherche...

Le point dur est de réduire cette marge d'erreur au minimum.

Shaun Nirenstein and Edwin Blake, Hardware Accelerated Aggressive Visibility Preprocessing using Adaptive Sampling, Rendering Techniques 2004: Proceedings of the 15th Eurographics Symposium on Rendering, 207- 216, Norrköping, Sweden, June 2004.

Peter Wonka, Michael Wimmer, Kaichi Zhou, Stefan Maierhofer, Gerd Hesina, Alexander Reshetov. Guided Visibility Sampling, ACM Transactions on Graphics. volume 25. number 3. pages 494 - 502. 2006. Proceedings of SIGGRAPH 2006.

[modifier] 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.

Craig Gotsman, Oded Sudarsky, and Jeffrey A. Fayman. Optimized occlusion culling using five-dimensional subdivision. Computers & Graphics, 23(5):645–654, October 1999.

[modifier] Problèmes Secondaires

Calculer une subdivision optimale afin de maximiser l'occlusion

D. Haumont, O. Debeir and F. Sillion, Graphics Forum, Volumetric Cell-and-Portal Generation Computer, Volume 22, Number 3, pages 303-312, September 2003

>Oliver Mattausch, Jiri Bittner, Michael Wimmer, Adaptive Visibility-Driven View Cell Construction. In Proceedings of Eurographics Symposium on Rendering 2006.

Compresser les listes de zones visibles afin d'optimiser la mémoire.

Michiel van de Panne and A. James Stewart, Effective Compression Techniques for Precomputed Visibility, Eurographics Workshop on Rendering, 1999, pg. 305-316, June.

Optimisation de l'encodage du pvs, qui peut être très long.

-La principale optimisation est de s'appuyer sur un pathfinder de type first depth search, de façon à faire le minimum de tests. Pour tout culling basé sur des portails, le pathfinder est requis 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 kd tree ou octree pour des terrains naturels).

[modifier] Notes

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.