Hierarchical Radiosity - An Analysis of Computational Complexity for a Simple Scene
switch to german Deutsche Version

Robert Garmann:
Hierarchical Radiosity - An Analysis of Computational Complexity for a Simple Scene (talk),
Dagstuhl Seminar on Rendering, June, 10-14, 1996. Detailed information about the talk is available in the following technical report.

Robert Garmann:
Hierarchical Radiosity - an analysis of computational complexity,
Technical Report No. 584/1995, August 1995

Abstract: The hierarchical radiosity algorithm is an efficient algorithm for the simulation of light. Hanrahan et. al. describe the initialization and the refinement of links between the scene's patches based upon an user-specified error parameter Fe They state that the number of links is linear in the number of patches if Fe is assumed to be a constant. Here we show a more natural result, based upon the assumption that the geometry is constant and Fe approaches 0 in a multigridding-procedure. For two initial patches the algorithm generates N = Theta(Fe-0.5) subpatches and L = Theta(N2) links. Beside the proof we present an intuitive interpretation of the hierarchical radiosity algorithm as a procedure that subdivides a rectangle in the plane.

Text: pdf
Robert Garmann, June 10, 2007
HOME