Efficient Hierarchical Radiosity in Complex Environments.

PhD thesis, Cornell University, 1994.

This thesis presents methods for speeding up the global illumination computations by using bounds on error to eliminate work that is not needed for a solution of a given accuracy. This work makes the hieerarchical radiosity approach feasible for complex environments. First, a new radiosity algorithm for efficiently computing global solutions with respect to a constrained set of views is presented. Radiosities of directly visible surfaces are computed to high acccuracy, while those of surfaces having only an indirect effect are computed to an accuracy commensurate with their contribution. The algorithm uses an adaptive subdivision scheme that is guided by the interplay between two closely related transport processes: one propagating power from the light sources, and the other propagating importance from the visible surfaces. By simultaneously refining approximate solutions to the dual transport equations, computation is significantly reduced in areas that contribute little to the region of interest. This approach is very effective for complex environments in which only a small fraction is visible at any time. Our statistics show dramatic speedups over the fastest previous radiosity algorithms for diffuse environments with details at a wide range of scales. A new approach for accelerating hierarchical radiosity by clustering objects is also presented. 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 the environments that can be simulated. The clustering algorithm presented here operates by estimating energy transfers between collections of objects which 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(s^2) 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. Finally, the thesis describes a method for reconstructing the radiance functions across the visible surfaces given a global solution to the energy balance equations. This approach greatly reduces artifacts resulting from the choice of constant basis functions used for the global solution.

The Thesis is available online from the Cornell University Department of Computer Science as Technical Report TR94-1443.