UC San Diego

This dissertation introduces a new light transport simulation framework that significantly expands a class of scene configurations that we can handle. The main contribution is a novel density estimation method, called progressive density estimation, which addresses fundamental limitations of existing density estimation methods. The key feature of progressive density estimation is that the method does not need to store a full set of samples to guarantee convergence to the correct solution. Progressive density estimation led to a new light transport algorithm which can simulate many optical configurations that would be impractical to handle with any existing algorithm. In particular, the algorithm can efficiently simulate complex lighting fixtures from the filament/LED-level for the first time. This dissertation also extends this basic framework of progressive density estimation. We first introduce a practical error estimator for progressive density estimation. This method can estimate how much expected error exists for a given computed solution without needing any knowledge of the correct solution. Since we often need to estimate average illumination over a region that is unknown before computation in computer graphics, we developed stochastic progressive density estimation which provides a simple solution to this problem. This estimator extends progressive density estimation for computing average density over unknown region with provable convergence. In order to improve computational efficiency of the proposed framework, we applied an adaptive Markov chain Monte Carlo method to light transport simulation. With this adaptive algorithm, we can focus computation on only to the visible region. To our knowledge, this is the first application of adaptive Markov chain Monte Carlo methods in light transport simulation. We also propose a novel framework that achieves the adaptive combination of progressive density estimation and other approaches based on Monte Carlo integration. In order to develop this framework, we conducted theoretical analysis of a provably good combination of density estimation methods and Monte Carlo integration. For parallel computation of the proposed framework, we developed a new spatial hashing method. This new hashing algorithm is designed to work correctly regardless of the result of contentions in parallel processes as opposed to avoiding the contentions