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 difference 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
influence 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 reflected 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 reflected at
x
0
and it is defined 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)(¯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 difference 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 final 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 diffuse 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 figures in this report are created with a tool we created specifically for this purpose. You can find it
at https://darioseyb.com/pathgraph. It is inspired by the paper ”Theory, Analysis and Applications of 2D Global
Illumination” [Jar+12].