Hierarchical Radiosity - An Analysis of Computational Complexity for a Simple Scene
Hierarchical Radiosity - An Analysis of Computational Complexity for a Simple Scene (talk),
on Rendering, June, 10-14, 1996.
Detailed information about the talk is available in the following technical report.
Hierarchical Radiosity - an analysis of computational complexity,
Technical Report No. 584/1995, August 1995
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
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
For two initial patches the algorithm generates
N = Theta(Fe-0.5) subpatches and
L = Theta(N2)
Beside the proof we present an intuitive interpretation of
the hierarchical radiosity algorithm as a procedure that subdivides
a rectangle in the plane.