“Feature-based control of visibility error: a multi-resolution clustering algorithm for global illumination” by Drettakis and Sillion

In this paper we introduce a new approach to controlling error in hierarchical clustering algorithms for radiosity. The new method ensures that just enough work is done to meet the user’s quality criteria. To this end the importance of traditionally ignored visibility error is identified, and the concept of features is introduced as a way to evaluate the quality of an image. A methodology to evaluate error based on features is presented, which leads to the development of a multi-resolution visibility algorithm. An algorithm to construct a suitable hierarchy for clustering and multi-resolution visibility is also proposed. Results of the implementation show that the multiresolution approach has the potential of providing significant computational savings depending on the choice of feature size the user is interested in. They also illustrate the relevance of the feature based error analysis. The proposed algorithms are well suited to the development of interactive lighting simulation systems since they allow more user control. Two additional mechanisms to control the quality of a simulation are presented: The evaluation of internal visibility in a cluster produces more accurate solutions for a given error bound; a progressive multi-gridding approach is introduced for hierarchical radiosity, allowing continuous refinement of a solution in an interactive session.

1. James Arvo, Kenneth Torrance, and Brian Smits. A framework for the analysis of error in global illumination algorithms. In Computer Graphics Proceedings, Annual Conference Series: SIGGRAPH ’94 (Orlando, FL), pages 75-84, 1994.
2. Michael E Cohen and John R. Wallace. Radiosity and Realistic Image Synthesis. Academic Press, Boston, 1993.
3. J. Goldsmith and J. Salmon. Automatic creation of object hierarchies for ray tracing. IEEE Computer Graphics and Applications, 7(5):14-20, May 1987.
4. Eric A. Haines. Shaft culling for efficient ray-traced radiosity. In R Brunet and EW. Jansen, editors, Photorealistic Rendering in Computer Graphics, pages 122-138. Springer Verlag, 1993. Proceedings of the Second Eurographics Workshop on Rendering (Barcelona, Spain, May 1991).
5. Pat Hanrahan, David Saltzman, and Larry Aupperle. A rapid hierarchical radiosity algorithm. Computer Graphics, 25(4):197-206, August 1991. Proceedings SIGGRAPH ’91 in Las Vegas.
6. Nicolas Holzschuch, Francois Sillion, and George Drettakis. An efficient progressive refinement strategy for hierarchical radiosity. In Fifth Eurographics Workshop on Rendering, Darmstadt, Germany, June 1994.
7. Arjan J. F. Kok. Grouping of patches in progressive radiosity. In Proceedings of Fourth Eurographics Workshop on Rendering, pages 221-231. Eurographics, June 1993. Technical Report EG 93 RW.
8. Dani Lischinski, Brian Smits, and Donald R Greenberg. Bounds and error estimates for radiosity. In Computer Graphics P1vceedings, Annual Conference Series: SIGGRAPH ’94 (Orlando, FL), pages 67-74, July 1994.
9. Dani Lischinski, Filippo Tampieri, and Donald R Greenberg. Discontinuity meshing for accurate radiosity. IEEE Computer Graphics and Applications, 12(6):25-39, November 1992.
10. Dani Lischinski, Filippo Tampieri, and Donald R Greenberg. Combining hierarchical radiosity and discontinuity meshing. In Computer Graphics P~vceedings, Annual Conference Series: SIGGRAPH ’93 (Anaheim, CA), pages 199-208, August 1993.
11. Holly Rushmeier, Charles Patterson, and Aravindan Veerasamy. Geometric simplification for indirect illumination calculations. In P~vceedings Graphics Interface ‘ 93. Morgan Kaufmann, 1993.
12. J. Serra. Image analysis and mathematical morphology : 1. Academic Press, London, 1982.
13. Francois Sillion. A unified hierarchical algorithm for global illumination with scattering volumes and object clusters, to appear in IEEE Transactions on Visualization and Computer Graphics, 1(3), September 1995. (a preliminary version appeared in the fifth Eurographics workshop on rendering, Darmstadt, Germany, June 1994).
14. Francois Sillion, George Drettakis, and Cyril Soler. A clustering algorithm for radiance calculation in general environments. In Sixth Eurographics Workshop on Rendering, Dublin, Ireland, June 1995.
15. Francois Sillion and Claude Puech. Radiosity and Global Illumination. Morgan Kaufmann publishers, San Francisco, 1994.
16. Brian Smits, James Arvo, and Donald R Greenberg. A clustering algorithm for radiosity in complex environments. In Computer Graphics Proceedings, Annual Conference Series: SIGGRAPH ’94 (Orlando, FL), pages 435-442, July 1994.
17. Brian E. Smits, James R. Arvo, and David H. Salesin. An importance-driven radiosity algorithm. Computer Graphics, 26(4):273-282, July 1992. Proceedings of SIGGRAPH ’92 in Chicago.
18. Seth J. Teller and Patrick M. Hanrahan. Global visibility algorithms for illumination computations. In Computer Graphics P1vceedings, Annual Conference Series: SIGGRAPH ’93 (Anaheim, CA), pages 239-246, August 1993.
19. John R. Wallace, Kells A. Elmquist, and Eric A. Haines. A ray tracing algorithm for progressive radiosity. Computer Graphics, 23(3):315-324, July 1989. Proceedings SIGGRAPH ’89 in Boston.