On The Computational Complexity Of Hierarchical Radiosity

Robert Garmann, Heinrich Müller:
On The Computational Complexity Of Hierarchical Radiosity,
in: Computer Science in Perspective  Essays
Dedicated to Thomas Ottmann, R. Klein, H.W. Six, L. Wegner (eds.),
LNCS 2598, SpringerVerlag, Berlin, 2003, 167178
Abstract:
The hierarchical radiosity algorithm is an efficient approach
to simulation of light with the goal of photorealistic image
rendering. Hanrahan et. al.
describe the initialization and the refinement of links between
the scene's patches based upon a userspecified error parameter
F_{e}.
They state that the number of links is linear in the number
of elements if F_{e} is assumed to be a constant.
We present a result based upon the assumption that
the geometry is constant and F_{e} approaches 0 in
a multigriddingprocedure.
Then the algorithm generates L = Theta(N^{2}) links where
N denotes the number of elements generated by the algorithm.
Text:
pdf (347K)