Hierarchical Radiosity  An Analysis of Computational Complexity for a Simple Scene

Robert Garmann:
Hierarchical Radiosity  An Analysis of Computational Complexity for a Simple Scene (talk),
Dagstuhl
Seminar
on Rendering, June, 1014, 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 userspecified error parameter
F_{e}
They state that the number of links is linear in the number
of patches if F_{e} is
assumed to be a constant.
Here we show a more natural result, based upon the assumption that
the geometry is constant and F_{e} approaches 0 in
a multigriddingprocedure.
For two initial patches the algorithm generates
N = Theta(F_{e}^{0.5}) subpatches and
L = Theta(N^{2})
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