Article

Efficient clustering and visibility calculation for global illumination

Authors:

Daniel Meneveaux,

Kadi Bouatouch,

Gilles Subrenat,

Philippe BlasiAuthors Info & Claims

AFRIGRAPH '03: Proceedings of the 2nd international conference on Computer graphics, virtual Reality, visualisation and interaction in Africa

Pages 87 - 94

https://doi.org/10.1145/602330.602347

Published: 03 February 2003 Publication History

Abstract

Using a radiosity method to estimate light inter-reflections within large scenes still remains a difficult task. The two main reasons are: (i) the computations entailed by the radiosity method are time consuming and (ii) the large amount of memory needed is very large. In this paper, we address this problem by proposing a new clustering technique as well as a new method of visibility computation for complex indoor scenes. Our clustering algorithm groups polygons that are close to each other in each room (or corridor) of the building. It relies on a classification method of k-mean type and allows the use of several kinds of distance functions. For each group of polygons (or cluster), we estimate the set of potentially visible clusters with the help of openings such as doors or windows. This computation results in a graph in which the nodes correspond to clusters and the edges express visibility relationships between the corresponding clusters. We use this graph for computing radiosity in complex buildings while reducing both the amount of memory needed and the computing time. Our global illumination method is a MWRA (multi-wavelet radiosity algorithm). Unlike cluster-based radiosity methods, our MWRA does not approximate (but computes accurately) the light energy impinging or leaving a cluster after multiple reflections. We provide results for 3 different test scenes containing a high number of polygons.

References

[1]

Airey, J. M. 1990. Increasing Update Rates in the Building Walkthrough System with Automatic Model-Space Subdivision and Potentially Visible Set Calculation. PhD thesis, University of North Carolina at Chapel hill.]]

Digital Library

[2]

Amanatides, J., and Woo, A. 1987. A fast voxel traversal algorithm for ray tracing. In Eurographics'87.]]

[3]

Bouatouch, K., and Pattanaik, S. N. 1995. Discontinuity meshing and hierarchical multiwavelet radiosity. Graphics Interface'95.]]

[4]

Cazals, F., Drettakis, G., and Puech, C. 1995. Filtering, clustering and hierarchy construction: a new solution for ray tracing complex scenes. Computer Graphics Forum (Eurographics '95) 14, 3.]]

[5]

Chin, N., and Feiner, S. 1989. Near real-time shadow generation using bsp trees. Computer Graphics 23, 3 (July), 99-106.]]

Digital Library

[6]

Cleary, J., and Wyvill, G. 1988. Analysis of an algorithm for fast distributed ray tracing using uniform space subdivision. The Visual Computer 4, 2 (July), 65-83.]]

[7]

Coorg, S., and Teller, S. 1997. Real-time occlusion culling for models with large occluders. ACM Symposium on Interactive 3D graphics.]]

Digital Library

[8]

Drettakis, G., and Fiume, E. 1994. A fast shadow algorithm for area light sources using backprojection. ACM SIGGRAPH'94.]]

Digital Library

[9]

Drettakis, F. D. G., and Puech, C. 1997. The visibility skeleton: A powerful and efficient multi-purpose global visibility tool. SIGGRAPH'97.]]

Digital Library

[10]

Funkhouser, T. 1996. Coarse-grained parallelism for hierarchical radiosity using group iterative methods. ACM SIGGRAPH'96 proceedings (Aug.), 343-352.]]

Digital Library

[11]

Gibson, S., and Hubbold, R. 1996. Efficient hierarchical refinement and clustering for radiosity in complex environments. Computer Graphics Forum 15, 297-310.]]

[12]

Gigante, M. 1990. Accelerated ray tracing using non-uniform grids. In AusGraph'90.]]

[13]

Goldsmith, J., and Salmon, J. 1987. Automatic creation of object hierarchies for ray tracing. In IEEE Computer Graphics and Applications, vol. 7, 14-20.]]

Digital Library

[14]

Goral, C., Torrance, K., Greenberg, D., and Battaile, B. 1984. Modeling the interaction of light between diffuse surfaces. Computer Graphics 18, 3 (July), 213-222.]]

Digital Library

[15]

Gortler, S. J., Schroder, P., Cohen, M. F., and Hanrahan, P. 1993. Wavelet radiosity. In Computer Graphics Proceedings, Annual Conference Series, ACM, Ed., 221-230.]]

Digital Library

[16]

Haber, J., Stamminger, M., and Seidel, H.-P. 2000. Enhanced automatic creation of multi-purpose object hierarchies. In Pacific Graphics'2000, 52-61.]]

Digital Library

[17]

Haines, E. A., and Wallace, J. R. 1991. Shaft culling for efficient ray-cast radiosity. In Proceedings of 2nd Workshop on Rendering, 122-138.]]

[18]

Hall, D. J., and Ball, G. H. 1965. Isodata a novel method of data analysis and pattern classification. Tech. Rep. 5 RI project 5533, Stanford Research Institute, CA, USA.]]

[19]

Hanrahan, P., Salzman, D., and Aupperle, L. 1991. A rapid hierarchical radiosity algorithm for unoccluded environments. Computer Graphics 25, 4 (July), 197-205.]]

Digital Library

[20]

Hasenfratz, J.-M., Damez, C., Sillion, F., and Drettakis, G. 1999. A practical analysis of clustering strategies for hierarchical radiosity. In Computer Graphics Forum (Proc. of Eurographics '99), P. Brunet and R. Scopigno, no. 18(3), 221-232.]]

[21]

John M. Airey, John H. Rohlf, F. P. B. 1990. Towards image realism with interactive update rates in complex virtual building environments. ACM Siggraph (May), 41-50.]]

Digital Library

[22]

Kay, T. L., and Kajiya, J. T. 1986. Ray tracing complex scenes. ACM SIGGRAPH'86., 269-278.]]

Digital Library

[23]

Klimaszewski, K. S. 1997. Faster ray tracing using adaptive grids. IEEE Computer Graphics and Applications 17, 1 (Jan.), 42-51.]]

Digital Library

[24]

Leblanc, L., and Poulin, P. 2000. Guaranteed occlusion and visibility in cluster hierarchical radiosity. In Eurographics Workshop on Rendering 2000, 89-100.]]

Digital Library

[25]

Meneveaux, D., and Bouatouch, K. 1999. Synchronisation and load balancing for parallel hierarchical radiosity of complex scenes on a heterogeneous computer network. Computer Graphics Forum 18, 4 (Dec.).]]

[26]

Meneveaux, D., Bouatouch, K., and Maisel, E. 1998. Memory management schemes for radiosity computation in complex environments. In Computer Graphics International.]]

Digital Library

[27]

Meneveaux, D., Maisel, E., Delmont, R., and Bouatouch, K. 1998. A new partitioning method for architectural environments. Journal of Vizualisation and Computer Animation, 3148 (Nov.).]]

[28]

Müller, G., Schfer, S., and Fellner, D. W. 2000. Automatic creation of object hierarchies of radiosity clustering. Computer Graphics Forum 19, 4 (Dec), 213-221. Sabine Coquillart, David J. Duke: Editorial. 194.]]

[29]

Salam, I., Nehlig, P., and Andres, E. 1999. Discrete raycasting. In 8th International Workshop on Discrete geometry for Computer Imagery (DGCI'99).]]

Digital Library

[30]

Sauvée, M. 1994. Maillage de discontinuités pour le modele de radiosité. Tech. rep., IRISA, Sept.]]

[31]

Sillion, F., and Drettakis, G. 1995. Feature-based control of visibility error: A multi-resolution clustering algorithm for global illumination. ACM SIGGRAPH'95.]]

Digital Library

[32]

Sillion, F. 1994. Clustering and volume scattering for hierarchical radiosity calculations. 5th Eurographics Workshop on Rendering.]]

[33]

Sillion, F. 1995. A unified hierarchical algorithm for global illumination with scattering volumes and objects clusters. IEEE Transaction On Graphics 1, 3.]]

Digital Library

[34]

Smits, B., Arvo, J., and Greenberg, D. 1994. A clustering algorithm for radiosity in complex environments. In Computer Graphics Proceedings, Annual Conference Series, 435-442.]]

Digital Library

[35]

Snyder, J., and Barr, A. 1987. Ray tracing complex models containing surface tesselations. In Computer Graphics ACM SIGGRAPH, 119-128.]]

Digital Library

[36]

T. Funkhouser, S. Teller, C. S., and Khorramabadi, D. 1996. The uc berkeley system for interactive visualization of large architectural models. Presence 5, 1, 13-44.]]

Digital Library

[37]

Teller, S., and Hanrahan, P. 1993. Global visibility algorithms for illumination computations. In Computer Graphics Proceedings, Annual Conference Series, 239-246.]]

Digital Library

[38]

Teller, S., Fowler, C., Funkhouser, T., and Hanrahan, P. 1994. Partitioning and ordering large radiosity computations. In Computer Graphics Proceedings, Annual Conference Series, 443-450.]]

Digital Library

[39]

Teller, S. 1992. Computing the antipenumbra of an area light source. In SIGGRAPH'92.]]

Digital Library

[40]

Teller, S. J. 1992. Visibility Computations in Density Occluded Polyhedral Environments. PhD thesis, University of California at Berkeley.]]

Digital Library

Cited By

Fradin DMeneveaux DHorna S(2005)Out of core photon-mapping for large buildingsProceedings of the Sixteenth Eurographics conference on Rendering Techniques10.5555/2383654.2383662(65-72)Online publication date: 29-Jun-2005
https://dl.acm.org/doi/10.5555/2383654.2383662
Wald IBenthin CSlusallek PDutré PSuykens FChristensen PCohen-Or D(2003)Interactive global illumination in complex and highly occluded environmentsProceedings of the 14th Eurographics workshop on Rendering10.5555/882404.882415(74-81)Online publication date: 25-Jun-2003
https://dl.acm.org/doi/10.5555/882404.882415

Index Terms

Efficient clustering and visibility calculation for global illumination
1. Computing methodologies
  1. Computer graphics
    1. Rendering
      1. Reflectance modeling

Recommendations

Implicit visibility and antiradiance for interactive global illumination
SIGGRAPH '07: ACM SIGGRAPH 2007 papers

We reformulate the rendering equation to alleviate the need for explicit visibility computation, thus enabling interactive global illumination on graphics hardware. This is achieved by treating visibility implicitly and propagating an additional ...
Precomputed illuminance composition for real-time global illumination
I3D '16: Proceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games

In this paper we present a new real-time approach for indirect global illumination under dynamic lighting conditions. We use surfels to gather a sampling of the local illumination and propagate the light through the scene using a hierarchy and a set of ...
An efficient GPU-based approach for interactive global illumination
SIGGRAPH '09: ACM SIGGRAPH 2009 papers

This paper presents a GPU-based method for interactive global illumination that integrates complex effects such as multi-bounce indirect lighting, glossy reflections, caustics, and arbitrary specular paths. Our method builds upon scattered data sampling ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AFRIGRAPH '03: Proceedings of the 2nd international conference on Computer graphics, virtual Reality, visualisation and interaction in Africa

February 2003

184 pages

ISBN:1581136439

DOI:10.1145/602330

Conference Chairs:
James Gain
University of Cape Town
,
Alan Chalmers
University of Bristol

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 February 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

AFRIGRAPH03

Sponsor:

SIGGRAPH

AFRIGRAPH03: 2nd International Conference on Computer Graphics, Virtual Reality, Visualization and Interaction in Africa

February 3 - 5, 2003

Cape Town, South Africa

Acceptance Rates

AFRIGRAPH '03 Paper Acceptance Rate 24 of 40 submissions, 60%;

Overall Acceptance Rate 47 of 90 submissions, 52%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
529
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fradin DMeneveaux DHorna S(2005)Out of core photon-mapping for large buildingsProceedings of the Sixteenth Eurographics conference on Rendering Techniques10.5555/2383654.2383662(65-72)Online publication date: 29-Jun-2005
https://dl.acm.org/doi/10.5555/2383654.2383662
Wald IBenthin CSlusallek PDutré PSuykens FChristensen PCohen-Or D(2003)Interactive global illumination in complex and highly occluded environmentsProceedings of the 14th Eurographics workshop on Rendering10.5555/882404.882415(74-81)Online publication date: 25-Jun-2003
https://dl.acm.org/doi/10.5555/882404.882415

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents