Advanced Monte Carlo and Quasi-Monte Carlo Sampling for Computer Graphics Applications – AMCQMCSCGA
Advanced Monte Carlo and Quasi-Monte Carlo Sampling for Computer Graphics Applications
New approaches to sampling theory
New approaches to sampling theory
Stochastic and quasi-stochastic sampling is a key component of Monte Carlo and Quasi-Monte Carlo (MCQMC) integration, a technique widely used in applications that require the evaluation of complex integrands, which cannot be calculated analytically, such as the light-transport calculations commonly encountered in computer graphics. Stochastic sampling methods should exhibit four crucial characteristics: (a) absence of bias, guaranteeing that the integral converges to the correct value as the number of samples increases; (b) the method should prevent aliasing, ensuring that the reconstructed integral does not contain false signals arising from components of the integrand beyond the Nyquist frequency; (c) low variance, so that the computed result is as noiseless as possible within the constraints of an inherently stochastic integration process, and (d) computational efficiency. The present ANR project «Advanced Monte Carlo and Quasi-Monte Carlo Sampling for Computer Graphics Applications« addresses one of the most fundamental problems related to Monte-Carlo and Quasi-Monte Carlo methods: the near-optimal way to diminish the variance in Monte-Carlo Integration.
In the framework of this project we studied in depth several innovative approaches, proposed by the author of the proposal in a few last years. A new theoretical framework has been established; a large spectrum of extremely tangible applications, at the heart of many computer graphics or numerical simulation applications, greatly benefit from the results of this research. The proposed approach is based on self- similar systems generated by substitution rules. One of the proposed approaches is purely geometrical, based on the theory of aperiodic tiling. This approach further develops and improves a novel approach, based on Penrose aperiodic tilings, proposed in 2004.
In the present project, we were able to expect to extend our prior approach to multi-dimensional case, and to better control spectral properties of the tilings. We were able to develop a new theory of stochastic sampling which provides better understanding of the phenomenon of variance in Monte Carlo integration, and allows to formulate design principles for future samplers.
We plan to submit a project to the European Commission ( ERC) .
Several extremely prestigious publications, namely ACM SIGGRAPH papers, have been produced in the framework of the present project. AMCQMCSCGA project is a fundamental research project, coordinated by Professor Ostromoukhov. The project began in December 2010 and lasted 48 months. It has been granted by the ANR with 760 000 € for a total cost of about 1,8 M€.
The present proposal addresses one of the most fundamental problems related to Monte-Carlo and Quasi-Monte Carlo methods: the near-optimal way to diminish the variance in Monte-Carlo Integration. We propose to study in depth several innovative approaches, proposed by the author of the proposal in a few last years. A new theoretical framework will be established; a large spectrum of extremely tangible applications, et the heart of many computer graphics or numerical simulation applications, will greatly benefit from the results of this research. The proposed approach is based on self-similar systems generated by substitution rules. Radical-invertible number systems in non-integer bases will be associated with the system. Based on this core theory, several approaches will be explored in depth. The first approach is purely geometrical, based on the theory of aperiodic tiling. This approach will further develop and improve a novel approach, based on Penrose aperiodic tilings, proposed in 2004. In the present project, we expect to extend our prior approach to multi-dimensional case, and to better control spectral properties of the tilings. The second approach is combinatorial; it follows a recent work performed by the author of the present proposal, in which a considerable improvement of asymptotic terms of extreme and star discrepancies in dimension one has been achieved. These extreme and star discrepancies are the best asymptotic discrepancies known today. In the current proposal, we expect to extend the methodology of combinatorial search for possible permutation, to more general cases of non-integer-based number systems. The third approach is algebraic; it is based on digital scrambling of our generalized radical invertible non-integer-based number systems. We expect to improve the variance of similar known approaches based on generalized Halton, generalized Hammersley, or generalized Niederreiter multidimensional sequences.
Project coordination
Victor Ostromoukhov (UNIVERSITE CLAUDE BERNARD - LYON I)
The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.
Partnership
LIRIS - UCBL UNIVERSITE CLAUDE BERNARD - LYON I
Help of the ANR 760,000 euros
Beginning and duration of the scientific project:
- 48 Months
