# A Rapid Hierarchical Radiosity Algorithm for Unoccluded Environments

Pat Hanrahan and David Salzman. Eurographics 1990

### 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 $F_\epsilon$ and minimum area $A_\epsilon$, 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 $n^2$ form factors.