Robust Monte Carlo Methods for Light Transport Simulation
Reference: Eric Veach, Ph.D. dissertation,
Stanford University,
December 1997.
Light transport algorithms generate realistic images by simulating the
emission and scattering of light in an artificial environment.
Applications include lighting design, architecture, and computer
animation, while related engineering disciplines include neutron
transport and radiative heat transfer. The main challenge with these
algorithms is the high complexity of the geometric, scattering, and
illumination models that are typically used. In this dissertation, we
develop new Monte Carlo techniques that greatly extend the range of
input models for which light transport simulations are practical. Our
contributions include new theoretical models, statistical methods, and
rendering algorithms.
We start by developing a rigorous theoretical basis for
bidirectional light transport algorithms (those that combine
direct and adjoint techniques). First, we propose a linear operator
formulation that does not depend on any assumptions about the physical
validity of the input scene. We show how to obtain mathematically
correct results using a variety of bidirectional techniques. Next we
derive a different formulation, such that for any physically valid
input scene, the transport operators are symmetric. This symmetry is
important for both theory and implementations, and is based on a new
reciprocity condition that we derive for transmissive materials.
Finally, we show how light transport can be formulated as an integral
over a space of paths. This framework allows new sampling and
integration techniques to be applied, such as the Metropolis sampling
algorithm. We also use this model to investigate the limitations of
unbiased Monte Carlo methods, and to show that certain kinds of paths
cannot be sampled.
Our statistical contributions include a new technique called
multiple importance sampling, which can greatly increase the
robustness of Monte Carlo integration. It uses more than one sampling
technique to evaluate an integral, and then combines these samples in a
way that is provably close to optimal. This leads to estimators that
have low variance for a broad class of integrands. We also describe a
new variance reduction technique called efficiency-optimized
Russian roulette.
Finally, we link these ideas together to obtain new Monte Carlo light
transport algorithms. Bidirectional path tracing uses a family
of different path sampling techniques that generate some path vertices
starting from a light source, and some starting from a sensor. We show
that when these techniques are combined using multiple importance
sampling, a large range of difficult lighting effects can be handled
efficiently. The algorithm is unbiased, handles arbitrary geometry and
materials, and is relatively simple to implement.
The second algorithm we describe is Metropolis light transport,
inspired by the Metropolis sampling method from computational physics.
Paths are generated by following a random walk through path space, such
that the probability density of visiting each path is proportional to the
contribution it makes to the ideal image. The resulting algorithm is
unbiased, uses little storage, handles arbitrary geometry and materials,
and can be orders of magnitude more efficient than previous unbiased
approaches. It performs especially well on problems that are usually
considered difficult, e.g. those involving bright indirect light, small
geometric holes, or glossy surfaces. To our knowledge, this is the
first application of the Metropolis method to transport problems of any
kind.
Click on any chapter heading to retrieve an individual chapter
(Postscript with low-resolution grayscale images). The full dissertation can also be downloaded
as a single file. It is formatted for two-sided printing, so
don't worry if you see an occasional blank page.
If you are having trouble downloading the files because of an
unreliable network connection, please note that they are also
available by ftp.
- Front Matter (Postscript, 69K)
- Abstract
- Acknowledgements
- Contents
- List of Tables
- List of Figures
- Chapter 1: Introduction (Postscript, 121K)
- The light transport problem
- Why light transport is important
- Assumptions about the transport model
- Summary of original contributions
- Bidirectional light transport theory in computer graphics
- General-purpose Monte Carlo techniques
- Robust light transport algorithms
- Thesis organization
- Light transport algorithms
- A brief history
- Monte Carlo vs. deterministic approaches
- View-dependent vs. view-independent algorithms
- Unbiased vs. consistent Monte Carlo algorithms
- Models of light and their implications for graphics
- Geometric optics
- Wave optics
- Quantum optics
- Related problems from other fields
- Neutron transport
- Heat transfer
- Radar and acoustics problems
- Many-body problems
- Chapter 2: Monte Carlo Integration
(Postscript, 248K)
- A brief history
- Quadrature rules for numerical integration
- A bit of probability theory
- Cumulative distributions and density functions
- Expected value and variance
- Conditional and marginal densities
- Basic Monte Carlo integration
- Convergence rates
- Sampling random variables
- Estimators and their properties
- Variance reduction I: Analytic integration
- The use of expected values
- Importance sampling
- Control variates
- Variance reduction II: Uniform sample placement
- Stratified sampling
- Latin hypercube sampling
- Orthogonal array sampling
- Quasi-Monte Carlo methods
- Variance reduction III: Adaptive sample placement
- Adaptive sampling
- Russian roulette and splitting
- Variance reduction IV: Correlated estimators
- Antithetic variates
- Regression methods
- Chapter 3: Radiometry and Light Transport (Postscript, 908K)
- Domains and measures
- The phase space
- The trajectory space and photon events
- Radiometric quantities
- Power
- Irradiance
- Radiance
- Spectral radiance
- Incident and exitant radiance functions
- The bidirectional scattering distribution function
- The scattering equation
- The BRDF and BTDF
- Angular parameterizations of the BSDF
- Introduction to light transport
- The measurement equation
- The light transport equation
- Importance and adjoint methods
- Bidirectional methods
- Sampling and evaluation of non-symmetric BSDF's
- The adjoint BSDF
- Appendix A: Field and surface radiance functions
- Appendix B: Measure-theoretic radiometry
- Measure spaces
- The photon event space
- The geometric measure
- The energy measure
- Defining radiometric quantities as a ratio of measures
- Examples of measure-theoretic definitions
- Discussion: fundamental vs. derived quantities
- Chapter 4: A General Operator Formulation of Light Transport (Postscript, 550K)
- Ray space
- Functions on ray space
- The scattering and propagation operators
- The light transport and solution operators
- Sensors and measurements
- Importance transport via adjoint operators
- Summary of the operator framework
- Appendix A: A new characterization of particle tracing
- Appendix B: Properties of the operators G, K, T, and S
- Invertibility
- Adjoints
- Norms
- Chapter 5: The Sources of Non-Symmetric Scattering (Postscript, 2244K)
- Introduction
- The problems caused by non-symmetric scattering
- Elementary sources of non-symmetric scattering
- Non-symmetry due to refraction
- Background material
- The BSDF for refraction
- The adjoint BSDF for refraction
- Results
- Discussion
- Non-symmetry due to shading normals
- How shading normals modify the BSDF
- The adjoint BSDF for shading normals
- Examples of shading normal BSDF's and their adjoints
- Pseudocode for the correct use of shading normals
- Shading normals violate conservation of energy
- Shading normals can cause brightness discontinuities
- Results
- Alternatives to shading normals
- Appendix A: Dirac distributions for general measures
- Linear functionals and distributions
- General Dirac distributions
- Identities for evaluating general Dirac distributions
- Appendix B: Derivation of the adjoint BSDF for refraction
- Appendix C: Angular forms of perfect specular BSDF's
- The BSDF for a mirror
- The BSDF for refraction
- Chapter 6: Reciprocity and Conservation Laws for General BSDF's (Postscript, 585K)
- Thermodynamics, Kirchhoff's laws, and detailed balance
- A reciprocity principle for general BSDF's
- Conservation of energy
- Appendix A: Helmholtz reciprocity
- Summary of the principle
- Helmholtz' original statement
- Further reading on Helmholtz reciprocity
- Appendix B: Lord Rayleigh's reciprocity principle
- Appendix C: Time reversal invariance and the irreversibility of light scattering
- Appendix D: Exceptions to reciprocity
- Magnetic fields and the Faraday effect
- Transmission between absorbing media
- Chapter 7: A Self-Adjoint Operator Formulation of Light Transport (Postscript, 590K)
- Concepts of the new framework
- The self-adjoint operator formulation
- Consequences for implementations
- Appendix A: Classical optical invariants
- The Smith-Helmholtz invariant
- The invariance of basic throughput
- The invariance of basic radiance
- Appendix B: Properties of the new operators
- Appendix C: The basic BSDF for refraction
- Chapter 8: A Path Integral Formulation of Light Transport (Postscript, 631K)
- The three-point form of the transport equations
- The path integral formulation
- Advantages of the path integral formulation
- Applying the path integral formulation
- The limitations of path sampling
- Heckbert's regular expression notation for paths
- Full-path regular expressions
- The limitations of local path sampling
- Approaches to non-local sampling
- Appendix A: Other measures on path space
- Appendix B: Subclassification of specular vertices
- Chapter 9: Multiple Importance Sampling (Postscript, 1714K)
- Application: glossy highlights from area light sources
- The glossy highlights problem
- Two sampling strategies
- Comparing the two strategies
- Discussion
- Multiple importance sampling
- The multi-sample model
- The balance heuristic
- Improved combination strategies
- The one-sample model
- Results
- The glossy highlights problem
- The final gather problem
- Discussion
- Relationship to classical Monte Carlo techniques
- Allocation of samples among the techniques
- Issues for direct lighting problems
- Conclusions and recommendations
- Appendix A: Proofs
- Chapter 10: Bidirectional Path Tracing (Postscript, 1685K)
- Overview
- Mathematical formulation
- Implementation issues
- Image sampling and filtering
- Estimation of the image function
- Determining the subpath lengths
- Special cases for short subpaths
- Handling specular surfaces
- Approximating the weighting functions
- Reducing the number of visibility tests
- Efficiency-optimized Russian roulette
- Implementation
- Results
- Comparison with related work
- Conclusions
- Chapter 11: Metropolis Light Transport (Postscript, 2642K)
- Overview of the MLT algorithm
- The Metropolis sampling algorithm
- The stationary distribution
- Detailed balance
- The acceptance probability
- Comparison with genetic algorithms
- Theoretical formulation of Metropolis light transport
- Eliminating start-up bias
- Initialization
- Convergence tests
- Spectral sampling
- Good mutation strategies
- Desirable mutation properties
- Bidirectional mutations
- Perturbations
- Lens subpath mutations
- Selecting between mutation types
- Refinements
- Results
- Conclusions
- Appendix A: Proof of Unbiased Initialization
- Chapter 12: Conclusion (Postscript, 33K)
- Bidirectional light transport theory
- General-purpose Monte Carlo techniques
- Robust light transport algorithms
- Bibliography (Postscript, 65K)
- Index (Postscript, 51K)
- PDF of full dissertation, with
JPEG-compressed color images (5238K)
- PDF of full dissertation, with
low-resolution grayscale images (2800K)
- Postscript of full dissertation,
with low-resolution grayscale images (11621K)
Also available:
Last modified: January 22, 1998
Eric Veach