metropolisTutorial.pdf

A Practical Introduction to Metropolis Light

Transport

David Cline

Brigham Young University

Parris Egbert †

Brigham Young University

May 6, 2005

Abstract

Most descriptions of Metropolis Light Transport (MLT) currently in the liter-

ature focus on theoretical completeness rather than readability. In fact, the core

concepts of MLT are not difﬁcult to understand, but available descriptions of these

concepts tend to be steeped in statistical terminology and light transport jargon.

In this paper, we take a different approach, concentrating on giving a working un-

derstanding of the algorithm rather than theoretical concerns. It is hoped that this

work will help to uncover the simplicity of MLT, and serve as a tutorial for those

wishing to implement the algorithm or understand its theoretical underpinnings.

Introduction

One of the most interesting global illumination algorithms to emerge in the past decade

is Metropolis Light Transport. First introduced by Veach and Guibas in 1997 [8],

MLT uses a statistical integration technique called Metropolis Transport [5] to solve

the general global illumination problem. The main strength of MLT lies in its ability

to explore local portions of the space of light paths in an unbiased way. This makes

MLT particularly attractive for hard sampling problems in global illumination such as

caustics and light shining through small aperatures.

Since the original paper, several papers have been published that extend the basic

MLT algorithm. Pauly, Kollig and Keller [6] show how Metropolis Light Transport can

be used to render scenes with participating media such as smoke and fog. Kelemen et

al. [3] improve the convergence characteristics of MLT by creating a novel mutation

strategy. Other work that has been done, such as that by Ashikim et al. [1] seeks

to describe the statistical properties of the Metropolis algorithm. In addition to these

works, Pharr [7] recently published an excellent tutorial on Metropolis Sampling.

Despite the popularity of MLT as a discussion topic, relatively few implementa-

tions of it exist compared to other global illumination algorithms such as standard path

e-mail: cline@rivit.cs.byu.edu

† e-mail: egbert@cs.byu.edu

tracing or photon mapping. Futhermore, while good practical tutorials exist on how to

implement other global illumination algorithms, simple descriptions of how to imple-

ment MLT seem hard to come by. Instead, most treatments of the MLT tend to take a

rigorous theoretical approach, which makes them inaccessible to those not well versed

in statistical and light transport terminology. This is unfortunate, since the core con-

cepts of MLT are not difﬁcult to understand once the terminology in which they are

cast is understood.

With this paper we attempt to strip away some of the more difﬁcult terminology,

and instead concentrate on giving a working knowledge of the concepts needed to

implement MLT. Our hope is that after reading this paper, a student who has previously

implemented a basic path tracer will have no trouble extending it to do bidirectional

path tracing and Metropolis Light Transport. The paper should also serve as a primer

for those wishing to understand the theoretical underpinnings of MLT.

The remainder of the paper will be presented as follows: we will ﬁrst present the

idea of Metropolis Transport in the context of image sampling, and then expand this

idea to produce a version of MLT based on standard path tracing. We then give an intro-

duction to bidirectional path tracing, which is used as the underlying sampling mecha-

nism for MLT. Finally, we show how to link bidirectional path tracing and Metropolis

sampling to produce a complete implementation of MLT.

Metropolis Transport

Suppose that you want to approximate a function f . One way to do this is to produce

a sampling distribution proportional to f and then make a histogram of samples taken

from the distribution. The resulting histogram will be proportional to f (obviously), so

it only needs to be scaled to approximate f . Metropolis Transport uses this method to

approximate functions, and can be summarized as follows:

• Create a sampling distribution proportional to f .

• Make a histogram of samples taken from the sampling distribution.

• Scale the histogram to approximate f .

In the case of an image, f is deﬁned on some subset of R 2 , and the histogram contains

one bin for each pixel in the image approximation. The scale factor, s , needed to make

the histogram approximate f is the ratio of the average value of f over the sampling

domain, f ave , to the average number of samples per bin in the histogram, h ave :

s = f ave / h ave

(1)

In practice, f ave can be estimated by averaging a large number of samples selected at

random from the sampling domain.

2.1 Creating a Sampling Distribution

Detailed balance. The Metropolis algorithm uses an idea called detailed balance to

create a distribution proportional to f . An intuitive way to think about detailed balance

is to imagine that a histogram proportional to f already exists. This distribution of

samples is called the stationary distribution . Now imagine that a transition function

exists that allows samples to ﬂow between bins in the histogram. The stationary distri-

bution will be maintained as long as the number of samples ﬂowing from one bin in the

histogram to another is the same as the number of samples ﬂowing back. This property

is called detailed balance . We will use K to denote a transition function that obeys the

detailed balance condition. (See ﬁgure 1.)

Figure 1: Detailed balance. The desired (stationary) distribution will be maintained as

long as the number of samples ﬂowing between any two bins x and y in the histogram

is balanced. In other words K ( y | x ) = K ( x | y ) .

An important consequence of detailed balance is that if a single sample is allowed

to migrate in the domain of f according to K , it will produce a distribution of samples

equal to the stationary distribution (proportional to the function we want to approxi-

mate). The strategy adopted by Metropolis Transport is to create a suitable K function

and then use it to migrate a single sample though the domain of f . As the sample

moves, a histogram is kept of its location, and this histogram is used to approximate f .

Deﬁning the transition function. The function K is deﬁned by using a tentative

transition function T , also known as a mutation strategy . T ( y | x ) gives the probability

of choosing point y as the proposed next sample location if x is the current sample

location. To complete K , a tentative sample location y is chosen based on T and x , f is

evaluated at x and y , and the next sample location either migrates to y with probability

a ( y | x ) , or remains at x with probability 1 − a ( y | x ) , where

f ( y ) T ( x | y )

f ( x ) T ( y | x )

a ( y | x ) = min

1 ,

(2)

The makeHistogram function in ﬁgure 2 uses Metropolis Transport to copy an im-

age. (This is not a very useful way to copy an image, but it does provide a good example

of Metropolis sampling in action.) MakeHistogram uses a very simple mutation strat-

egy, namely choosing a random point on the image plane with a uniform probability,

void makeHistogram(ﬂoat F[w][h], ﬂoat histogram[w][h], int mutations)

{

int i, x0, x1, y0, y1;

ﬂoat Fx, Fy, Txy, Tyx, Axy;

// Create an initial sample point

x0 = randomInteger(0, w-1);

x1 = randomInteger(0, h-1);

Fx = F[x0][x1];

// In this example, the tentative transition function T simply chooses

// a random pixel location, so Txy and Tyx are always equal.

Txy = 1.0 / (w * h);

Tyx = 1.0 / (w * h);

// Create a histogram of values using Metropolis sampling.

for (i=0; i < mutations; i++) {

// choose a tentative next sample according to T.

y0 = randomInteger(0, w-1);

y1 = randomInteger(0, h-1);

Fy = F[y0][y1];

Axy = MIN(1, (Fy * Txy) / (Fx * Tyx)); // equation 2.

if (randomReal(0.0, 1.0) < Axy) {

x0 = y0;

x1 = y1;

Fx = Fy;

}

histogram[x0][x1] += 1;

}

Figure 2: The makeHistogram function. This function uses Metropolis sampling to

make a histogram from an image passed in the F array. It is assumed that the his-

togram array is initialized to be all zeros. After the function returns, the histogram

can be scaled to approximate F . Below the code are several images created using the

makeHistogram function. The original image is approximated using an average of 1

(left), 8 (middle) and 256 samples per pixel (right).

but a wide range of transition functions can be used. Later we will see that the power

of MLT lies in choosing good mutation strategies.

Using detailed balance to produce the stationary distribution is very robust in the

limit. It will even work if f can only be evaluated statistically (i.e. f cannot be directly

evaluated but a random variable with expected value f can be). This will become an

important point when the Metropolis algorithm is adapted to handle light transport.

2.2

Color Images

Up to now we have only considered how to create grayscale images using Metropolis

sampling. However, the Metropolis framework can easily be extended to handle color

images by redeﬁning the histogram to accumulate in color. The luminance of the color

samples at points x and y is used to deﬁne a ( y | x ) , and colors added to the histogram are

scaled to have a luminance of 1. Figure 3 shows how this might look in code. Note that

any additive color space can be used for the histogram. In the common case of RGB,

luminance is deﬁned as (0.299 R + 0.587 G + 0.114 B ).

DomainLocation X,Y;

for (i=0; i < mutations; i++) {

Y = mutateAccordingToT(X);

Tyx = T(Y, X);

Txy = T(X, Y);

colorY = F[Y.xloc][Y.yloc];

Fy = colorY.luminance();

colorY /= Fy; // scale colorY to have luminance 1

Axy = MIN(1, (Fy * Txy) / (Fx * Tyx));

if (randomReal(0.0, 1.0) < Axy) {

X = Y;

Fx = Fy;

colorX = colorY;

}

histogram[X.xloc][X.yloc] += colorX;

}

Figure 3: Accumulating in color. Compare to ﬁgure 2. The image and histogram have

both been converted to color arrays. Fx and Fy are redeﬁned to be luminance values,

and colors added to the histogram have a luminance of 1. In addition, the mutation

strategy and pixel coordinates of each sample have been encapsulated. In the case of

MLT, the DomainLocation structure will not only contain a pixel location, but will

include an entire light path as well.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: