Radiosity Algorithms Running in Sub-quadratic Time

Szirmay-Kalos László, Fóris Tibor
Department of Process Control, Technical University of Budapest,
Budapest, Muegyetem rkp. 11, H-1111, HUNGARY


This paper presents an iterative radiosity algorithm that is capable to determine the radiosity of the patches in O(n log n) time and using only O(n) space. The basic idea is to compute the radiosity updates of all patches in a single direction parallely, requiring only one complete solution of the visibility problem per directions. The visibility problem is solved by painter's algorithm that is responsible for the O(n log n) time complexity, and thus it does not require large amount of z-buffer memory.


Radiosity method, iterative techniques, transillumination, complexity, painter's algorithm.