Quasi-Monte Carlo (QMC) Samplers

Halton

A very fast C++ implementation of the Halton sequence that supports both Faure-permutations and random digit permutations. Together with the component (i / N) this will yield a Hammersley point set. Comes with a Python script to generate optimized code for arbitrary dimensions. It also includes code to enumerate samples in a 2D domain, for example pixels.

MCQMC LFSR

A C++ implementation of the small linear feedback shift registers (LFSR) for use in a Markov chain quasi-Monte Carlo context, as described in S. Chen, M. Matsumoto, T. Nishimura, and A. Owen: New inputs and methods for Markov chain quasi-Monte Carlo.

Sobol’

A C++ implementation of a simple and fast random-access Sobol’-sequence generator, based on the direction numbers published in S. Joe and F. Y. Kuo: Constructing Sobol sequences with better two-dimensional projections.

Publications

SIGGRAPH 2012 course: Advanced (Quasi-) Monte Carlo Methods for Image Synthesis

with S. Premoze, A. Keller, and M. Raab.

Enumerating Quasi-Monte Carlo Point Sequences in Elementary Intervals

with M. Raab and A. Keller.

In H. Wozniakowski and L. Plaskota (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2010, Springer-Verlag, Berlin, 2012.

Abstract: Low discrepancy sequences, which are based on radical inversion, expose an intrinsic stratification. New algorithms are presented to efficiently enumerate the points of the Halton and (t,s)-sequences per stratum. This allows for consistent and adaptive integro-approximation as for example in image synthesis.

Parallel Quasi-Monte Carlo Integration by Partitioning Low Discrepancy Sequences

with A. Keller.

In H. Wozniakowski and L. Plaskota (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2010, Springer-Verlag, Berlin, 2012.

Abstract: A general concept for parallelizing quasi-Monte Carlo methods is introduced. By considering the distribution of computing jobs across a multiprocessor as an additional problem dimension, the straightforward application of quasi-Monte Carlo methods implies parallelization. The approach in fact partitions a single low-discrepancy sequence into multiple low-discrepancy sequences. This allows for adaptive parallel processing without synchronization, i.e. communication is required only once for the final reduction of the partial results. Independent of the number of processors, the resulting algorithms are deterministic, and generalize and improve upon previous approaches.

Quasi-Monte Carlo Point Progressive Photon Mapping

with A. Keller and M. Droske.

In H. Wozniakowski and L. Plaskota (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2010, Springer-Verlag, Berlin, 2012.

Abstract: The simulation of light transport often involves specular and transmissive surfaces, which are modeled by functions that are not square integrable. However, in many practical cases unbiased Monte Carlo methods are not able to handle such functions efficiently and consistent Monte Carlo methods are applied. Based on quasi-Monte Carlo integration, a deterministic alternative to the stochastic approaches is introduced. The new method for deterministic consistent functional approximation uses deterministic consistent density estimation.

MSBVH: An Efficient Acceleration Data Structure for Ray Traced Motion Blur

with M. Stich, S. Nawaz, and A. Keller.

In Proceedings of the Conference on High Performance Graphics (HPG ‘11).

Abstract: When a bounding volume hierarchy is used for accelerating the intersection *of rays and scene geometry, one common way to incorporate motion blur is to interpolate node bounding volumes according to the time of the ray. However, such hierarchies typically exhibit large overlap between bounding volumes, which results in an inefficient traversal. This work builds upon the concept of spatially partitioning nodes during tree construction in order to reduce overlap in the presence of moving objects. The resulting hierarchies are often significantly cheaper to traverse than those generated by classic approaches.

(t, m, s)-Nets and Maximized Minimum Distance, Part II

with A. Keller.

In P. L’Ecuyer and A. Owen (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, Springer-Verlag, Berlin, 2009.

Abstract: The quality parameter t of (t,m,s)-nets controls extensive stratification properties of the generated sample points. However, the definition allows for points that are arbitrarily close across strata boundaries. We continue the investigation of (t,m,s)-nets under the constraint of maximizing the mutual distance of the points on the unit torus and present two new constructions along with algorithms. The first approach is based on the fact that reordering (t,s)-sequences can result in (t,m,s+1)-nets with varying toroidal distance, while the second algorithm generates points by permutations instead of matrices.

Motion Blur

Diploma thesis at Ulm University, Germany, 2008.

Supervisors: A. Keller and M. Weber.

(t, m, s)-Nets and Maximized Minimum Distance

with J. Hanika , R. Schwede, and A. Keller.

In A. Keller, S. Heinrich, and H. Niederreiter (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer-Verlag, Berlin, 2008.

Abstract: Many experiments in computer graphics imply that the average quality of quasi-Monte Carlo integro-approximation is improved as the minimal distance of the point set grows. While the definition of (t,m,s)-nets in base b guarantees extensive stratification properties, which are best for t=0, sampling points can still lie arbitrarily close together. We remove this degree of freedom, report results of two computer searches for (0,m,2)-nets in base 2 with maximized minimum distance, and present an inferred construction for general m. The findings are especially useful in computer graphics and, unexpectedly, some (0,m,2)-nets with the best minimum distance properties cannot be generated in the classical way using generator matrices.

Benchmarking Ray Tracing for Realistic Light Transport Algorithms

with M. Raab, J. Hanika, M. Finckh, and A. Keller.