Calcul de la visibilité ...

1. Etat de l'art

On constate depuis les débuts de la synthèse d'images que les scènes développées sont de plus en plus complexes et contenant toujours plus d'objets. Parallèlement à cette évolution, les algorithmes de visualisation et de rendu se sont perfectionnés. Très rapidement, on a cherché à regrouper les objets suivant différents critères afin d'optimiser les traitements. Les approches les plus anciennes et les plus connues sont les volumes englobants [RUBI 80] [KAY 86] [GOLD 87], les subdivisions spatiales régulières [FUJI 86] [AMAN 87] [CLEA 88] et les subdivisions spatiales hiérarchiques ("octree") [GLAS 84] [SAME 89] [SPAC 91]. D'autres approches dédiées plus précisément à la radiosité ont été développées. On peut penser par exemple aux algorithmes de [MARK 90] et [HAIN 91] essayant de déterminer la visibilité entre un objet émetteur et un objet récepteur, au tampon de profondeur ("z-buffer") hiérarchique [GREE 93], aux notions de cellules et de portails introduites par [TELL 94] et [LUEB 95]. Enfin, les recherches les plus récentes concernent l'animation et plus particulièrement le déplacement au sein de mondes virtuels. Dans ce domaine, on peut citer cinq techniques :

2. La solution fondée sur les faisceaux

L'utilisation du lancer de faisceaux permet d'écarter rapidement une grande partie des objets non visible depuis un point de vue donné.
Les principaux avantages de cette optimisation sont les suivants :

Nos essais ont été effectué dans le cadre d'un algorithme de radiosité de [WALL 89]. Nous avons utilisé une subdivision spatiale régulière pour optimiser le lancer de rayons nécessaire a la détermination de la visibilité.

Nous avons comparé un algorithme de radiosité de [WALL 89] non optimisé avec ce même algorithme optimisé par nos faisceaux. L'Images 1 présente les résultats des temps de calcul pour différentes résolution de la subdivision spatiale régulière. L'Images 2 présente la scène utilisée (maillage régulier de plus 40.000 carreaux).

Comparaison entre une radiosité de [WALL 89] optimisée et non optimisée Image 1 : Comparaison en temps entre une radiosité conventionnelle et une radiosité optimisée avec des faisceaux.
On remarque de plus que les temps d'exécution sont globalement en faveur de la version optimisée et ce, quels que soient les paramètres. On notera que les meilleurs temps sont 346 secondes pour l'algorithme de [WALL 89] et 254 secondes pour notre solution, c'est-à-dire un gain de temps de plus de 25%. Ce rapport, relativement important, montre donc la pérennité de cette approche.
[Graphique extrait de [HASE 98]]
Scene teste utilisée pour nos comparaisons. Scene teste utilisée pour nos comparaisons. Image 2 : La scène test que nous utilisons comporte 14957 polygones et 42317 carreaux. Elle représente un étage d'une maison. Cette scène a été construite de sorte à être la moins particulière possible. Elle contient un nombre important de carreaux et les objets (bureaux, chaises, lampes) ont été répartis de manière homogène dans toute la maison. Ainsi, on retrouve ce mobilier au moins une fois dans chacune des pièces, indépendamment de leur éclairage. De plus, certains objets, comme la lampe, sont denses : ils sont petits et composés de 1200 carreaux, d'autres sont plus grands et modélisés de manière plus grossière comme les bureaux (560 carreaux) et les chaises (400 carreaux).
[Image extraite de [HASE 98]]

3. Bibliographie (extrait)

[AMAN 84] John AMANATIDES, "Ray Tracing with Cones", Computer Graphics (Proceedings of SIGGRAPH '84), july 1984, 18(3), pp. 129-135.
[AMAN 87] John AMANATIDES, Andrew WOO, "A Fast Voxel Traversal Algorithm for Ray-Tracing", Proceedings of Eurographics Conference, August 1987, pp. 27-38.
[CLEA 88] john G. CLEARY, Geoff WYVILL, " Analysis of an algorithm for fast ray tracing using uniform space subdivision ", Journal of the Visual Computer,1988, 4(1), pp. 65-83.
[COOR 96] Satyan COORG, Seth TELLER, "Temporally Coherent Conservative Visibility", Proceedings of the Twelfth Annual ACM Symposium on Computational Geometry, Philadelphia, PA May 1996.
[COOR 97] Satyan COORG, Seth TELLER, "Real-Time Occlusion Culling for Models with Large Occluders", Proceedings of the 1997 Symposium on Interactive Graphics, 1997, pp. 83-90 and 189.
[FUJI 86] Akira FUJIMOTO, Takayuki TANAKA, Kansei IWATA, "ARTS: Accelearted Ray-Tracing System", IEEE Jouranl of Computer Graphics and Applications, April 1986,6(2), pp. 16-26.
[FUNK 93] Thomas A. FUNKHOUSER, Carlo H. SEQUIN, "Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments", SIGGRAPH '93. Conference proceedings on Computer graphics, 1993,pp. 247-254.
[GLAS 84] Andrew GLASSNER, " Space Subdivision for Fast Ray Tracing ", IEEE Journal of Computer Graphics and Applications, October 1984, 4(5), pp. 15-22.
[GOLD 87] Jeffrey GOLDSMITH, John SALMON, "Automatic Creation of Object Hierarchies for Ray Tracing", IEEE Journal of Computer Graphics and Applications, may 1987, pp. 14-20 .
[GREE 93] Ned GREENE, Michael KASS, Gavin MILLER, "Hierarchical Z-buffer visibility", SIGGRAPH '93. Conference proceedings on Computer graphics, 1993, pp. 231-238.
[HAIN 91] Eric A. HAINES, John R. WALLACE, "Shaft Culling for Efficient Ray-Cast Radiosity", Second Eurographics Workshop on Rendering, may 1991.
[HASE 98] Jean-Marc HASENFRATZ, "Lancer de Faisceaux en Synthèse d'Images", Mémoire de thèse en Informatique de l'Université de Limoges, Jan. 1998, 140 PAGES.
[HUDS 97] Thomas C. HUDSON, Ming C. LIN, Jonathan COHEN, Stefan GOTTSCHALK, Dinesh MANOCHA, "V-COLLIDE: Accelerated Collision Detection for VRML", Proc. of VRML'97, 1997.
[KAY 86] Timothy L. KAY, James T. KAJIYA, "Ray Tracing Complex Scenes", Computer Graphics, august 1986, 20(4), pp. 269-278.
[LUEB 95] David P. LUEBKE, Chris GEORGES, "Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets", ACM Interactive 3D Graphics Conference, Monterey, CA 1995.
[MARK 90] Joseph MARKS, Robert J. WALSH, John CHRISTENSEN, Mark FRIEDEL, "Image and Intervisibility Conherence in Rendering", Proceedings of Graphics Interface '90, may 1990, pp. 17-30.
[SAME 89] Hanan SAMET, " Neighbor Finding in Images Represented by Octrees ", Computer Vision Graphics and Image Processing, 1989, 46, pp. 367-386.
[SHAD 96] Jonathan SHADE, Dani LISCHINSKI, David H. SALESIN, Tony DEROSE, John SNYDER, "Hierarchical image caching for accelerated walkthroughs of complex environments", SIGGRAPH '96. Proceedings of the SIGGRAPH 96 conference on Computer graphics, 1996, pp. 75-82.
[SILL 97] François X. SILLION, George DRETTAKIS, Benoit BODELET, "Efficient Impostor Manipulation for Real-Time Visualization of Urban Scenery", Proceedings of Eurographics'97, Budapest, Hungary 1997, 16(3), pp 207-218..
[SPAC 91] John SPACKMAN, Philip WILLIS, "The {SMART} Navigation of a Ray Through an Oct-Tree", Computers and Graphics, 1991, 2(15), pp. 185-194.
[TELL 94] Seth J. TELLER, Celeste FOWLER, Thomas A. FUNKHOUSER, Pat HANRAHAN, "Partitioning and ordering large radiosity computations", SIGGRAPH '94. Proceedings of the conference on Computer graphics, 1994, pp. 443-450.
[YAGE 95] Roni YAGEL, William RAY, "Visibility computation for efficient walkthrough of complex environments", Presence: Teleoperators and Virtual Environments, 1995, 5(1).

[Recherche] [Rendu Réaliste] [Aliassage] [Pénombre] [Visibilité]