A Rapid Hierarchical Radiosity Algorithm for Unoccluded Environments

Abstract:

This paper presents a linear-time radiosity algorithm for scenes containing large mutually unoccluded polygonal patches. It subdivides pairs of patches adaptively to build a hierarchical data structure with n elements at the leaves, and it encodes all the light transport between component polygonal elements. Given a required numerical precision, determined here by the specified bounds for maximum solid angle Ft, and minimum area At, our algorithm reduces the number of form factor calculations and interactions to O(n) in the worst case and O(sqrt n) in the best case. Standard techniques for shooting and gathering can then be used with the data structure. The best previous radiosity algorithms represented the element-to-element transport interactions with n2 form factors.