Accurate and reliable algorithms for global illumination

The simulation of global illumination is one of the most fundamental problems in computer graphics, with applications in a wide variety of areas, such as architecture and lighting design, computer-aided design, and virtual reality. This problem concerns the transport of light energy between reflective surfaces in an environment. During the past decade, radiosity has become the method of choice for simulating global illumination in diffuse environments. Despite much recent progress in efficiency and applicability of radiosity methods, there are several very important open issues remaining: 1) Radiosity images suffer from many visual artifacts, resulting from lack of reliable automatic discretization algorithms; and 2) Current radiosity algorithms do not provide the user with guaranteed bounds or reliable estimates of the approximation errors. As a result, current radiosity systems require very careful and time-consuming user intervention in the discretization process, and the accuracy of the resulting solutions can only be assessed by visual appearance. This thesis presents new radiosity algorithms for diffuse polyhedral environments that address the open problems mentioned above. First, we have improved and combined together two recently developed radiosity approaches: hierarchical radiosity and discontinuity meshing. An improved hierarchical radiosity algorithm that is based on a discontinuity-driven subdivision strategy to achieve better numerical accuracy and faster convergence is used to compute the global distribution of light energy in an environment. Then, a new algorithm based on discontinuity meshing uses the hierarchical solution to reconstruct a visually accurate approximation to the radiance function. Thus, results of high visual quality can be obtained even from coarse global illumination simulations. The solution is performed entirely in object-space, which enables users to "walk" through high-fidelity shaded virtual environments in real time, using appropriate display hardware. Second, we have developed algorithms that compute a posteriori error bounds and estimates for local and total errors in hierarchical radiosity solutions. A conservative algorithm computes guaranteed upper bounds on the errors. A non-conservative algorithm is capable of computing more realistic error estimates more efficiently. These error estimates are used in a new error-driven refinement strategy for hierarchical radiosity, resulting in faster convergence.