Gradient Domain Path Tracing

Dario Seyb

January 22, 2017

Abstract

In recent years the popularity of the path tracing rendering algorithm has risen dramatically. Especially

the movie industry appreciates the accuracy and relative simplicity of physically based rendering. Un-

fortunately the drawbacks of path tracing are still holding back artistic expression. For complex scenes

rendering times can be prohibitive. Hence extensions of path tracing which address these issues have to be

found. In this report we will present ”Gradient Domain Path Tracing”, one of the more recent extensions.

We will describe the algorithm, its advantages over classical path tracing and recent work in gradient

domain rendering. Additionally we will provide an implementation of the algorithm in the rendering

framework ”zaphod” [Sey17].

Keywords Path Tracing, Physically Based Rendering, Gradient Domain Light Transport

Contents

1 Introduction 2

2 A Brief Introduction to Path Tracing 2

3 Introduction to Gradient Domain Light Transport 3

3.1 Symmetric Gradient Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4 Shift Mappings 6

4.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4.1.1 Shift via Manifold Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.1.2 Improved Shift via Manifold Exploration . . . . . . . . . . . . . . . . . . . . . . . . 7

4.1.3 Half Vector Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.1.4 Discussion of Shift Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.2 Computing the Jacobian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.3 Multiple Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5 Solving Screened Poisson Equations 10

6 A Theoretical Analysis of Gradient Domain Light Transport 11

6.1 A Math Primer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6.1.1 The Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6.1.2 Power Spectra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

6.1.3 Dirac Delta Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

6.2 Analyzing the Components of Gradient Domain Methods . . . . . . . . . . . . . . . . . . 13

6.2.1 The Gradient Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6.2.2 Stochastic Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6.2.3 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

6.2.4 Poisson Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1

7 Recent Work 16

7.1 Gradient Domain Bidirectional Path Tracing . . . . . . . . . . . . . . . . . . . . . . . . . 16

7.1.1 Shift Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

7.1.2 Connection Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

7.2 Temporal Gradient-Domain Path Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.2.1 Shift Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.2.2 Spatio-temporal Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

8 Discussion 18

8.1 Equal Time Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

8.2 Analysing Shift Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9 Acknowledgements 20

1 Introduction

Gradient domain methods are a rather recent research area in light transport simulation. Especially

in the last two years there have been multiple extensions to the original algorithm, applying gradient

rendering to existing light transport strategies. This report intends to be a survey of the state of the

art in gradient domain rendering. We will start by describing the basic algorithm and the components

needed to implement it. Next we will present a theoretical analysis of gradient rendering which provides

a mathematical explanation for the empirical results. Finally we will compare the various gradient

domain adaptions. We are especially interested in the diﬀerence between Gradient Domain Metropolis

Light Transport (MLT) and Gradient Domain Bidirectional Path Tracing (BDPT) [Vea98]. We focus

on these algorithms because their non-gradient domain versions are popular in research and production.

Additionally both MLT and BDPT are unbiased, sampling-based algorithms that handle a large variety

of scenes. Even traditionally hard to render scenes are handled robustly. As such, the scenes chosen

for analysis should be handled similarly well between algorithms, and the comparison can focus on the

inﬂuence of gradient rendering on their results.

2 A Brief Introduction to Path Tracing

Path tracing is a technique used for light transport simulation which uses Monte Carlo sampling to

evaluate the integral in the rendering equation by [Kaj86]

I(x, x

0

) =

Geometry Term

z }| {

g(x, x

0

)[(x, x

0

)

| {z }

Emission

+

Z

S

BRDF

z }| {

ρ(x, x

0

, x

00

)

Incoming light

z }| {

I(x

0

, x

00

) dx

00

| {z }

Light reﬂected at x

0

in direction

−→

x

0

x

] (1)

I(x, x

0

) is the radiance arriving from point x

0

at x. It depends on the light that is being reﬂected at

x

0

and it is deﬁned recursively. In modern literature the prevalent mathematical framework to describe

light transport problems is the path integral formulation introduced by [Vea98].

I

j

=

Z

Ω

f

j

(¯x)dµ(¯x) (2)

I

j

is the amount of radiance arriving at a pixel j on the sensor and f

j

is the measurement contribution

function which assigns an amount of transported energy to each path ¯x. The main diﬀerence between

Equations (1) and (2) is that instead of describing a measurement I by a local recursive integral we

describe it by globally integrating over Path Space Ω, that is, the set of all paths ¯x = x

1

x

2

. . . x

n

that are

sampled by a path tracer.

In this context Monte Carlo simulation corresponds to drawing random samples in path space. To

compute a pixel value we randomly generate paths that connect a point on the sensor to a point on a

light source. This is usually done by recursively tracing a ray through the scene and calculating a new

outgoing direction at each intersection point. Once a path is sampled we can calculate its contribution

to the image. Figure 1 illustrates this process.

x

1

x

0

x

2

x

4

x

3

Figure 1: Sampling a ray that contributes to a certain pixel on the sensor.

While the sampling process is identical whether we are using the path integral or the recursive scat-

tering formulation, working in path space allows us to develop algorithms that work on complete paths

and are decoupled from the path generation strategy.

The main issue with the Monte Carlo simulation approach is that naively sampling the high di-

mensional path space results in high variance between samples. This is visible in the ﬁnal image as a

characteristic high frequency noise. Because of the high number of samples required for a convergent

image, path tracing was prohibitively expensive for many applications. The high variance is in part due

to the fact that many paths never hit a light source. Figure 2 a) shows the distribution of light paths in

a scene with diﬀuse materials. Blue paths never hit a light; yellow paths do. As you can see, since the

light source is small and out of the way, very few paths hit it randomly. The result is a noisy image as

shown in Figure 2 b).

1

(a) Path Density (b) Resulting Noisy Image

Figure 2: A scene illuminated by a small light source rendered with standard

path tracing. A high sample count is necessary because very few of the paths

contribute to the image.

3 Introduction to Gradient Domain Light Transport

The goal of almost any new light transport method is to reduce the variance in the evaluated samples

since this leads to faster converging images which need less time to render. While there are many ways

to reduce the variance of a given sampler, for example via importance sampling [Vea98], these are often

1

The 2D ﬁgures in this report are created with a tool we created speciﬁcally for this purpose. You can ﬁnd it

at https://darioseyb.com/pathgraph. It is inspired by the paper ”Theory, Analysis and Applications of 2D Global

Illumination” [Jar+12].