A clustering algorithm for radiosity in complex environments.

In Andrew Glassner, editor, SIGGRAPH 94 Conference Proceedings, Computer Graphics Proceedings, Annual Conference Series, pages 435--442. ACM SIGGRAPH, ACM Press, July 1994.

We present an approach for accelerating hierarchical radiosity by clustering objects. Previous approaches constructed effective hierarchies by subdividing surfaces, but could not exploit a hierarchical grouping on existing surfaces. This limitation resulted in an excessive number of initial links in complex environments. Initial linking is potentially the most expensive portion of hierarchical radiosity algorithms, and constrains the complexity of environments that can be simulated. The clustering algorithm presented here operates by estimating energy transfers between collections of objects while maintaining reliable error bounds on each transfer. Two methods of bounding the transfers are employed with different tradeoffs between accuracy and time. In contrast with the O(s2) time and space complexity of the initial linking in previous hierarchical radiosity algorithms, the new methods have complexities of O(s log s) and O(s) for both time and space. Using these methods we have obtained speedups of two orders of magnitude for environments of moderate complexity while maintaining comparable accuracy.

This paper is available as a compressed Postscript file SAG94.ps.gz ( 59K).