Parallel hierarchical radiosity rendering

The radiosity equation is examined, and is found to contain a previously unexploited symmetry. This symmetry is formalized, and a solution method previously unusable in the field of computer graphics (conjugate gradients) is shown to be superior to all methods currently in use. A detailed analysis of all solution techniques previously applied to the radiosity problem is conducted, and results presented;So-called hierarchical methods have reduced the operational complexity of the N-body problem from O(N[superscript]2) to O(N log N) assuming a pre-set error tolerance. An algorithm following the same basic tenets has been applied to radiosity rendering by other researchers, and has reduced the operational complexity from O(N[superscript]2) to (arguably) O(N);Shortcomings in the state-of-the-art hierarchical radiosity method are pointed out, and enhancements are offered. A consistent treatment of various types of error is found to be absent from present methods. Catastrophic error is possible in the visibility assessment between two polygons. A self-consistency check is possible during the solution process, but never exploited;Until now, supercomputer-class computers have not been used to solve radiosity problems at a production-quality level even though realistic image synthesis has always been a prodigious consumer of computer time. A state-of-the-art hierarchical radiosity code is implemented on an nCUBE-2 parallel computer, and discussed in detail. The algorithm is found to have ample sources of parallelism, in both data- and operational modes. Its performance is analyzed in detail;The hierarchical method has only been applied to realistic image synthesis since 1991. Not surprisingly, many avenues of further research are open. Some are pointed out, and include: analytic determination of coupling factors, quantifying discretization error, incorporating specular light reflection modes into the hierarchical treatment, and exploring what other important physical problems might benefit from the hierarchical approach