Browse Prior Art Database

Quasi-Monte Carlo Rendering with Adaptive Sampling

IP.com Disclosure Number: IPCOM000118124D
Original Publication Date: 1996-Sep-01
Included in the Prior Art Database: 2005-Apr-01

Publishing Venue

IBM

Related People

Aono, M: AUTHOR [+2]

Abstract

Disclosed is a Quasi-Monte Carlo (QMC) method, which employs deterministic Low-Discrepancy Sequences (LDSs), to solve the global illumination problem. Characteristics of two LDSs are described first. Then, in a distribution ray-tracing setting, it shows that the QMC integral with LDSs converges significantly faster than the Monte Carlo (MC) integral and about as fast as the Stratified-Monte Carlo (SMC) integral with a typical pseudo-random sequence. Finally, described is an adaptive Error-Bounded Luminaire Sampling (EBLS) method. The EBLS algorithm exploits two advantages of QMC: (1) convergence is faster and more accurate than MC, and (2) unlike SMC, samples can be added incrementally in small increments.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 13% of the total text.

Quasi-Monte Carlo Rendering with Adaptive Sampling

      Disclosed is a Quasi-Monte Carlo (QMC) method, which employs
deterministic Low-Discrepancy Sequences (LDSs), to solve the global
illumination problem.  Characteristics of two LDSs are described
first.  Then, in a distribution ray-tracing setting, it shows that
the QMC integral with LDSs converges significantly faster than the
Monte Carlo (MC) integral and about as fast as the Stratified-Monte
Carlo (SMC) integral with a typical pseudo-random sequence.  Finally,
described is an adaptive Error-Bounded Luminaire Sampling (EBLS)
method.  The EBLS  algorithm exploits two advantages of QMC: (1)
convergence is faster and more accurate than MC, and (2) unlike SMC,
samples can be added incrementally in small increments.  Experiments
showed that, given a budget of luminaire samples per image, the EBLS
algorithm produces higher-quality images, especially in the
penumbrae, than a method in which the numbers of samples per
luminaire was predetermined.

      Many problems in computer graphics can be formulated as
integrals.  Global light-energy transfer can be expressed as an
integral equation, which is sometimes called the rendering equation
(5), and super-sampling screen pixels in the ray-tracing and the
Z-buffer rendering algorithms are convolution integrals.  The Monte
Carlo (MC) integral is often used to compute these integrals,
especially if the integrand is complex or higher-dimensional.

      The MC integral approximates an integral I(f) of a function
f(x) by the Equation (1):

      The function is evaluated at N randomly selected points
ti.  While the MC method is quite effective, slow convergence is an
issue; the absolute value of the error has an average magnitude of
O(N**(-1/2)).

      Various methods have been employed to reduce the error of the
MC method, such as importance sampling, stratified sampling,
antithetic variates, and non-random sequences (5, 11, 17, 2).  These
methods are mostly concerned with finding point sets that yield
smaller integration  errors.  Importance sampling concentrates
samples in the area where they are more effective by using a priori
knowledge of the function.  Stratified sampling tries to distribute
samples evenly by subdividing the domain into subregions, such as
grids.  Note that it is possible to combine some of these techniques,
or to apply them adaptively.  For example, uniformly distributed
samples generated by stratification can be employed for importance
sampling.

      Since it has been observed that random point sets tend to take
wasteful samples because of clumps and empty spots, error reduction
by means of non-random point sets try to use more uniformly
distributed points.  In computer graphics, non-random sequences
generated by the n-rooks, Poisson disk, and other algorithms have
been tried with some success (8, 13, 2).  However, these point sets
have disadvantages. For  example, the n-rooks can...