“Interactive update of global illumination using a line-space hierarchy” by Drettakis and Sillion

Interactively manipulating the geometry of complex, globally illuminated scenes has to date proven an elusive goal. Previous attempts have failed to provide interactive updates of global illumination and have not been able to offer well-adapted algorithms controlling the frame rate. The need for such interactive updates of global illumination is becoming increasingly important as the field of application of radiosity algorithms widens. To address this need, we present a novel algorithm which provides interactive update rates of global illumination for complex scenes with moving objects. In the context of clustering for hierarchical radiosity, we introduce the idea of an implicit line-space hierarchy. This hierarchy is realized by augmenting the links between hierarchical elements (clusters or surfaces) with shafts, representing the set of lines passing through the two linked elements. We show how line-space traversal allows rapid identification of modified links, and simultaneous cleanup of subdivision no longer required after a geometry move. The traversal of line-space also limits the amount of work required to update and solve the new hierarchical system after a move, by identifying the modified paths in the scene hierarchy. The implementation of our new algorithm allows interactive updates of illumination after object motion for scenes containing several thousand polygons, including global illumination effects. Finally, the line-space hierarchy traversal provides a natural control mechanism allowing the regulation of the tradeoff between image quality and frame rate.

1. N. Amenta. Finding a line transversal of axial objects in three dimensions. In Proc. 3rd ACM-SIAM Sympos. Discrete Algorithms, pages 66-71, 1992.
2. James Arvo and David Kirk. Fast ray tracing by classification. Computer Graphics, 21(4):55-64, July 1987. Proceedings SIGGRAPH ’87 in Anaheim.
3. Daniel R. Baum, John R. Wallace, Michael F. Cohen, and Donald P. Greenberg. The back-buffer algorithm : an extension of the radiosity method to dynamic environments. The Visual Computer, 2:298-306, 1986.
4. Shenchang Eric Chen. Incremental radiosity: An extension of progressive radiosity to an interactive image synthesis system. Computer Graphics, 24(4):135- 144, August 1990. Proceedings SIGGRAPH ’90 in Dallas.
5. Fredo Durand, George Drettakis, and Claude Puech. The 3d visibility complex, a new approach to the problems of accurate visibility. In X. Pueyo and P. Shroeder, editors, Rendering Techniques ’96, pages 245-257. Springer Verlag, June 1996. Proc. 7th EG Workshop on Rendering in Porto.
6. David Forsyth, Chien Yang, and Kim Teo. Efficient radiosity in dynamic environments. In Sakas et al., editor, Photorealistic Rendering Techniques, Darmstadt, D, June 1994. Springer Verlag. Proc. 5th EG Workshop on Rendering.
7. David W. George, Francois Sillion, and Donald P. Greenberg. Radiosity redistribution for dynamic environments. IEEE Computer Graphics and Applications, 10(4), July 1990.
8. Cindy M. Goral, Kenneth E. Torrance, Donald P. Greenberg, and Bennett Battaile. Modeling the interaction of light between diffuse surfaces. Computer Graphics, 18(3):213-222, July 1984. Proc. SIGGRAPH ’84 in Minneapolis.
9. Eric A. Haines. Shaft culling for efficient ray-traced radiosity. In Brunet and Jansen, editors, Photorealistic Rendering in Comp. Graphics, pages 122-138. Springer Verlag, 1993. Proc. 2nd EG Workshop on Rendering (Barcelona, 1991).
10. Pat Hanrahan, David Saltzman, and Larry Aupperle. A rapid hierarchical radiosity algorithm. Computer Graphics, 25(4):197-206, August 1991. SIG- GRAPH ’91 Las Vegas.
11. Stefan Muller and Frank Scho~fel. Fast radiosity repropagation for interactive virtual environments using a shadow-form-factor-list. In Sakas et al., editor, Photorealistic Rendering Techniques, Darmstadt, D, June 1994. Springer Verlag. Proc. 5th EG Workshop on Rendering.
12. Erin Shaw. Hierarchical radiosity for dynamic environments. Master’s thesis, Cornell University, Ithaca, NY, August 1994.
13. Francois Sillion. A unified hierarchical algorithm for global illumination with scattering volumes and object clusters. IEEE Trans. on Vis. and Comp. Graphics, 1(3), September 1995.
14. Francois Sillion and George Drettakis. Feature-Based Control of Visibility Error: A Multiresolution Clustering Algorithm for Global Illumination. In Robert Cook, editor, SIGGRAPH 95 Conference Proceedings, Annual Conference Series, pages 145-152. ACM SIGGRAPH, August 1995.
15. Brian E. Smits, James R. Arvo, and David H. Salesin. An importance-driven radiosity algorithm. Computer Graphics, 26(4):273-282, July 1992. Proc. SIG- GRAPH ’92 in Chicago.
16. Seth J. Teller. Computing the antipenumbra of an area light source. Computer Graphics, 26(4):139-148, July 1992. Proc. SIGGRAPH ’92 in Chicago.
17. Seth J. Teller and Patrick M. Hanrahan. Global visibility algorithms for illumination computations. In J. Kajiya, editor, SIGGRAPH 93 Conf. Proc. (Anaheim), Annual Conf. Series, pages 239-246. ACM SIGGRAPH, August 1993.