(L) [2014/08/19] [tarlack] [GACV : robust numerical integration method] Wayback!Hi there,
we recently published a new method for Monte-Carlo-based numerical integration, named "Globally adaptive control-variate" (GACV). It has been published in the SISC journal (Society for industrial and applied mathematics - scientific computing). It's an hybrid between cubature rules and Monte-Carlo integration. As this journal may not be known by the computer graphics community, I point the preprint directly here.
[LINK https://www.researchgate.net/publication/264719192_Globally_Adaptive_Control_Variate_for_Robust_Numerical_Integration?ev=prf_pub]
Its strong points are:
- empirically, it exhibits a linear behavior with respect to variance (instead of quadratic for standard MC).
- numerically highly robust and accurate, fast, low memory footprint, highly stable in memory footprint and computation time. We show in the paper that it was not the case for the existing state of the art methods.
- C++ code is freely available for direct use ! [LINK http://www.irit.fr/~Loic.Barthe/transfer.php#Free] . You just have to code a simple functor evaluating the function at any point in the definition domain, call a function with this functor, and you're done. It's in majority templates, no external dependencies, only a few cpp files have to be added to your compilation process or you can use the provided Makefile to produce a shared library. An example is provided.
- can be optimally combined with importance sampling.
- simple (no need for aspirin to read and understand the paper, no complex equations).
Its weak points are :
- like all MC methods, not well fitted for highly-oscillatory non-positive functions with means close to zero (we tried it for electromagnetic scattering computation, and it behaved really badly).
- In practice, limited to dimensions at most 8.
Its possible extensions are :
- handle correlated integrals, to apply it directly to image rendering with 1 or 2 bounces, depth of field or motion blur.
- find a way to extend to arbitrary number of dimensions, or find a way to let some of the dimensions purely stochastic. The main problem is how to compute an accurate error in this case.
Here is the abstract :
Many methods in computer graphics require the integration of functions on low-to-middle-dimensional spaces. However, no available method can handle all the possible integrands accurately and rapidly. This paper presents a robust numerical integration method, able to handle arbitrary non-singular scalar or vector-valued functions de�fined on low-to-middle-dimensional spaces. Our method combines control variate, globally adaptive subdivision and Monte-Carlo estimation to achieve fast and accurate computations of any non-singular integral. The runtime is linear with respect to standard deviation while standard Monte-Carlo methods are quadratic. We additionally show through numerical tests that our method is extremely stable from a computation time and memory footprint point-of-view, assessing its robustness. We demonstrate our method on a participating media voxelization application, which requires the computation of several millions integrals for complex media.
Any comment welcome, I would be glad discussing it with you !