Reboot

Introduction

After a long break because of examinations and vacation, I'm back for the second semester. For a summary of my work in the first semester, I'll refer to my paper in the previous blog post Probabilistic Visibility using the Occlusion Map.

The focus of this semester is integrating importance sampling to achieve faster convergence.
Furthermore we will try to improve the efficiency of the occlusion map by depositing photons in more interesting locations.

In the past week I've started with reading a couple of papers on importance sampling. Two interesting approaches came up which are based upon particle maps. I'll first explain the idea behind importance sampling. Then I will summarize the ideas of the papers in the next two sections.

Mathematical background

The integral

can be evaluated with Monte Carlo sampling. It has been proven that the following estimator

converges to the exact value of the integral when the number of samples approaches infinity. The error is depends on the choice of the probability density function p(x), but for uniform sampling the standard deviation is proportional to:

The optimal choice for the probability density function is given by:

However this function requires knowledge of the exact integral. Fortunatly the error of the integral already decreases a lot when we use a probability density function which matches the shape of the integrand.

Importance Driven Path Tracing using the Photon Map

This paper describes an approach to generate a probability density function using the photon map.  In this case the probability density function should be proportional to the product of the bidirectional reflection distribution function (brdf) and the incoming radiance:

To construct the probability density function at a location x, the N nearest photons are located. Each photon stores it's incoming direction and it's radiance value.

The incoming direction of all the photons are projected on a 2D grid and each cell of the grid stores the accumulated radiance value (see for example the following figure):

Figuur 1: Radiance waarden in het grid.

To generate an outgoing direction, a cell of the grid is chosen proportional to the radiance registered in the grid. Then a random outgoing direction inside the cell is generated.

The result is that more directions will be generated in the cell with the highest radiance value. In order to remain unbiased, a part of the total energy in all the cells is distributed to the cells with zero radiance.

source: Hendrik Wann Jensen., 1995. Importance Driven Path Tracing using the Photon Map. In Eurographics Rendering Workshop, Springer-Verlag, 326-335

Importance Sampling with Hemispherical Particle Footprints

The approach in this paper makes an estimation of the directional particle density on the hemisphere at a location x from the N nearest photons. The estimation is performed by projecting all the directions of the nearest photons on a grid on the ground plane of the hemisphere. The grid on the ground plane is divided in 32x32 cells, and each projected photon is splatted in 3x3 cells, increasing the count in each cell by one.

To generate a random outgoing direction, we select one of the photons proportional to the radiance carried by the photon. The grid on the ground plane is consulted to retrieve the directional particle density. Based upon this density, a radius is assigned to the photon, where a high density will result in smaller radii. The outgoing direction is then generated to be in the cone around the direction of the photon where the cone has the previously calculated radius.

In order to remain unbiased, there is also a chance p_BRDF that the outgoing direction is selected sampling the bidirectional reflection distribution function.

source: Hey Heinrich., Werner Purgathofer., 2002. Importance Sampling with Hemispherical Particle Footprints. In Proceedings of the 18th spring conference on Computer Graphics, ACM New York, NY, USA, SCCG '02, 107-114.