13.7 Russian Roulette and Splitting

The efficiency of an estimator upper F is defined as

epsilon left-bracket upper F right-bracket equals StartFraction 1 Over upper V left-bracket upper F right-bracket upper T left-bracket upper F right-bracket EndFraction comma

where upper V left-bracket upper F right-bracket is its variance and upper T left-bracket upper F right-bracket is the running time to compute its value. According to this metric, an estimator upper F 1 is more efficient than upper F 2 if it takes less time to produce the same variance, or if it produces less variance in the same amount of time. The next few sections discuss a number of techniques for improving the efficiency of Monte Carlo.

Russian roulette and splitting are two related techniques that can improve the efficiency of Monte Carlo estimates by increasing the likelihood that each sample will have a significant contribution to the result. Russian roulette addresses the problem of samples that are expensive to evaluate but make a small contribution to the final result, and splitting is a technique that makes it possible to place more samples in important dimensions of the integrand.

As an example to motivate Russian roulette, consider the problem of estimating the direct lighting integral, which gives reflected radiance at a point due to radiance from direct illumination from the light sources in the scene,  upper L Subscript normal d Superscript :

upper L Subscript normal o Superscript Baseline left-parenthesis normal p Subscript Baseline comma omega Subscript normal o Baseline right-parenthesis equals integral Underscript script upper S squared Endscripts f Subscript normal r Baseline left-parenthesis normal p Subscript Baseline comma omega Subscript normal o Baseline comma omega Subscript normal i Baseline right-parenthesis upper L Subscript normal d Superscript Baseline left-parenthesis normal p Subscript Baseline comma omega Subscript normal i Baseline right-parenthesis StartAbsoluteValue cosine theta Subscript i Baseline EndAbsoluteValue normal d omega Subscript normal i Baseline period

Assume that we have decided to take upper N equals 2 samples from some distribution p left-parenthesis omega Subscript Baseline right-parenthesis to compute the estimator

one-half sigma-summation Underscript i equals 1 Overscript 2 Endscripts StartFraction f Subscript normal r Baseline left-parenthesis normal p Subscript Baseline comma omega Subscript normal o Baseline comma omega Subscript i Baseline right-parenthesis upper L Subscript normal d Superscript Baseline left-parenthesis normal p Subscript Baseline comma omega Subscript i Baseline right-parenthesis StartAbsoluteValue cosine theta Subscript i Baseline EndAbsoluteValue Over p left-parenthesis omega Subscript i Baseline right-parenthesis EndFraction period

Most of the computational expense of evaluating each term of the sum comes from tracing a shadow ray from the point normal p Subscript to see whether the light source is occluded as seen from normal p Subscript .

For all of the directions omega Subscript i where the integrand’s value is 0 because f Subscript normal r Baseline left-parenthesis normal p Subscript Baseline comma omega Subscript normal o Baseline comma omega Subscript i Baseline right-parenthesis is 0 for that direction, we should obviously skip the work of tracing the shadow ray, since tracing it won’t change the final value computed. Russian roulette makes it possible to also skip tracing rays when the integrand’s value is very low but not necessarily 0, while still computing the correct value on average. For example, we might want to avoid tracing rays when f Subscript normal r Baseline left-parenthesis normal p Subscript Baseline comma omega Subscript normal o Baseline comma omega Subscript i Baseline right-parenthesis is small or when omega Subscript i is close to the horizon and thus StartAbsoluteValue cosine theta Subscript i Baseline EndAbsoluteValue is small. These samples just can’t be ignored completely, however, since the estimator would then consistently underestimate the correct result.

To apply Russian roulette, we select some termination probability q . This value can be chosen in almost any manner; for example, it could be based on an estimate of the value of the integrand for the particular sample chosen, increasing as the integrand’s value becomes smaller. With probability q , the integrand is not evaluated for the particular sample, and some constant value c is used in its place ( c equals 0 is often used). With probability 1 minus q , the integrand is still evaluated but is weighted by a term, 1 slash left-parenthesis 1 minus q right-parenthesis , that effectively accounts for all of the samples that were skipped. We have the new estimator

upper F prime equals StartLayout Enlarged left-brace 1st Row 1st Column StartFraction upper F minus q c Over 1 minus q EndFraction 2nd Column xi Subscript Baseline greater-than q 2nd Row 1st Column c 2nd Column otherwise period EndLayout

The expected value of the resulting estimator is the same as the expected value of the original estimator:

upper E left-bracket upper F Superscript prime Baseline right-bracket equals left-parenthesis 1 minus q right-parenthesis left-parenthesis StartFraction upper E left-bracket upper F right-bracket minus q c Over 1 minus q EndFraction right-parenthesis plus q c equals upper E left-bracket upper F right-bracket period

Russian roulette never reduces variance. In fact, unless somehow c equals upper F , it will always increase variance. However, it does improve efficiency if probabilities are chosen so that samples that are likely to make a small contribution to the final result are skipped.

One pitfall is that poorly chosen Russian roulette weights can substantially increase variance. Imagine applying Russian roulette to all of the camera rays with a termination probability of .99 : we’d only trace 1% of the camera rays, weighting each of them by 1 slash .01 equals 100 . The resulting image would still be “correct” in a strictly mathematical sense, although visually the result would be terrible: mostly black pixels with a few very bright ones. One of the exercises at the end of this chapter discusses this problem further and describes a technique called efficiency-optimized Russian roulette that tries to set Russian roulette weights in a way that minimizes the increase in variance.

13.7.1 Splitting

While Russian roulette reduces the effort spent evaluating unimportant samples, splitting increases the number of samples taken in order to improve efficiency. Consider again the problem of computing reflection due only to direct illumination. Ignoring pixel filtering, this problem can be written as a double integral over the area of the pixel  upper A and over the sphere of directions script upper S squared at the visible points on surfaces at each left-parenthesis x comma y right-parenthesis pixel position:

integral Underscript upper A Endscripts integral Underscript script upper S squared Endscripts upper L Subscript normal d Superscript Baseline left-parenthesis x comma y comma omega Subscript Baseline right-parenthesis d w normal d upper A Subscript Baseline comma

where upper L Subscript normal d Baseline left-parenthesis x comma y comma omega right-parenthesis denotes the exitant radiance at the object visible at the position left-parenthesis x comma y right-parenthesis on the image due to incident radiance from the direction omega .

The natural way to estimate the integral is to generate upper N samples and apply the Monte Carlo estimator, where each sample consists of an left-parenthesis x comma y right-parenthesis image position and a direction omega Subscript toward a light source. If there are many light sources in the scene, or if there is an area light casting soft shadows, tens or hundreds of samples may be needed to compute an image with an acceptable variance level. Unfortunately, each sample requires that two rays be traced through the scene: one to compute the first visible surface from position left-parenthesis x comma y right-parenthesis on the image plane and one a shadow ray along omega Subscript to a light source.

The problem with this approach is that if upper N equals 100 samples are taken to estimate this integral, then 200 rays will be traced: 100 camera rays and 100 shadow rays. Yet, 100 camera rays may be many more than are needed for good pixel antialiasing and thus may make relatively little contribution to variance reduction in the final result. Splitting addresses this problem by formalizing the approach of taking multiple samples in some of the dimensions of integration for each sample taken in other dimensions.

With splitting, the estimator for this integral can be written taking upper N image samples and upper M light samples per image sample:

StartFraction 1 Over upper N EndFraction StartFraction 1 Over upper M EndFraction sigma-summation Underscript i equals 1 Overscript upper N Endscripts sigma-summation Underscript j equals 1 Overscript upper M Endscripts StartFraction upper L Subscript Superscript Baseline left-parenthesis x Subscript i Baseline comma y Subscript i Baseline comma omega Subscript i comma j Baseline right-parenthesis Over p left-parenthesis x Subscript i Baseline comma y Subscript i Baseline right-parenthesis p left-parenthesis omega Subscript i comma j Baseline right-parenthesis EndFraction period

Thus, we could take just 5 image samples but take 20 light samples per image sample, for a total of 105 rays traced, rather than 200, while still taking 100 area light samples in order to compute a high-quality soft shadow.

The purpose of the Sampler::Request1DArray() and Sampler::Request2DArray() methods defined in Section 7.2.2 can now be seen in the light that they make it possible for users of Samplers to apply splitting to some dimensions of the integrand.