Page 1 of 1

GACV : robust numerical integration method

Posted: Tue Aug 19, 2014 6:00 pm
by tarlack
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. ... 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 ! . 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 !

Re: GACV : robust numerical integration method

Posted: Tue Sep 02, 2014 3:38 pm
by andersll
This sounds interesting! Can you share the preprint any other way? I can't create an account on that site to be able to view it.

Re: GACV : robust numerical integration method

Posted: Wed Sep 03, 2014 6:43 am
by tarlack
Hi ! you can download it directly from here : ... -et-al.pdf