-=[Stochastic Progressive Photon Mapping]=- 

Project Proposal 

Photon Mapping [1] is a popular technique for global illumination. It is so widely used due to it being able to render a high quality image with stunning specular effects such as caustics, and the final image lacks the undesirable high frequency noise present in most Monte Carlo methods such as path tracing.

However, photon mapping suffers from the constraint of having the photon map fit into memory, and the estimator cannot be made consistent without having an infinite amount of memory. This constraint also prevents photon mapping from scaling onto parallel computing architectures such as GPUs, the Cell Broadband Engine (PS3) or hybrids such as Intel’s Larabee. Since the computing power of these architectures are predicted to increase exponentially with time, it would be wise to consider a version of the algorithm which is more scalable.

Fortunately, Hachisuka et. al developed 2 follow up algorithms which do not require the storage of the photon map, but instead do a number of photon mapping passes to make the estimator consistent. I will elaborate on the algorithms in more detail below.

A brief overview of the algorithms: 

In photon mapping, photons are fired from the light sources in the scene, and stored in a photon map. The N nearest photons are then used to estimate the flux density at where the eye ray intersects a surface. (by summing the flux and dividing by the radius of the bounding sphere.) However, this estimator is only consistent when the number of photons in the photon map tends to infinity (so that the radius of the sphere converges to zero). However, this is impossible due to a lack of memory.

Progressive Photon Mapping [2] (PPM), attempts to solve this by not having to store the entire photon map in memory. Rather, the photons from each photon tracing pass are collected if they fall into the radius of each ray's 'bucket'. The estimator is made consistent by gradually reducing the size of the radius of the buckets gradually.

Stochastic Progressive Mapping [3] (SPPM) is a further extension of Progressive Photon Mapping by allowing effects which are usually achieved by integration over another domain. (eg motion blur, depth of field etc.) SPPM achieves this by the use of shared statistics over a region instead of local densities over discrete points.

I propose to implement SPPM for YafaRay to increase its flexibility, scalability, and rendering capabilities. SPPM shows much promise to be able to deliver all 3 of these, and hence is a suitable candidate for implementation.

What I hope to accomplish:

I hope to implement a robust version of SPPM. It should work for a variety of albedos and in the least be able to render an image which is comparable or better than that produced by the current photon mapper in YafaRay.

It is also my hope that SPPM would considerably speed up rendering time, especially for detailed renderings of complex scenes. In the least, a progressive update can be rendered on the screen every couple of seconds till the user decides that the image is of a high enough quality. This feature would be very useful and would be one of the benefits of using a progressive method.

Difficulties

Technical and theory issues – Implementation of PPM and SPPM carries a considerable amount of difficulty, and a robust and correct solution requires a thorough understanding of both of these algorithms.

Data structures – The original k-d tree coded for the photon mapper might not work as well for PPM and SPPM and a grid based system might be better for locating the nearest bucket to a photon for collection.

Scene specifications – for motion blur effects, additional properties might have to be given to scene objects and materials. For depth of field, the camera lens and aperture size should be able to be changed. ie. some changes (additional fields etc.) will probably have to be made in YafaRay’s UI.

Tentative schedule. 

The project should take about 10 weeks.

A rough timeline is as follows:

Week 1 – familiarizing myself with YafaRay

Week 2 – Writing new data structures, refactoring code.

Weeks 3 - 5 - Implementing a progressive photon mapper. By the end of week 5, it does not have to be perfect yet, but should be able to render a image which looks similar to the reference copy.

Week 6 - Refactor code base, add test cases, iron out bugs.

Week 7 - Finish the progressive photon mapper.

Weeks 8 and 9 – Extend the progressive photon mapper by implementing SPPM.

Weeks 10 – Documentation and wrap up

Implementation details 

For the SPPM integrator, eye rays are traced and gathering "buckets" are created on the first diffuse surface created.
A number of photon passes are then done and collected in the buckets for the gathering step.
A hashed grid is used to effectively find which buckets the photons fall into.
It might be possible to use the current kd-tree implementation in YafaRay for this as well, and this issue certainly begs further investigation.

About me

I'm a computer graphics researcher with Square Enix Japan and I'm glad to be able to join the community! I'll be starting studies towards a Masters in Computer Science with a specialization in computer graphics in Stanford University from this fall, and my research interests are in real time rendering, global illumination techniques, and just algorithms in general. I was also a previous Google intern in 2008, working on Google's open source 3d project O3D.

I am most proficient in C++ and Java, and recently I've picked up CUDA and OpenCL for parallel computation in my line of work.

You can find out more by taking a look at my website.
My projects page (slightly outdated) lists a sample of the things that I've worked on before.

Here's a progressive version of the Instant Radiosity algorithm [4], that I wrote myself in C++ and GLSL.
It fully calculates the indirect illumination for the cornell box, uses important sampling for speedups, and an accumulation texture buffer for progressive rendering.

References

[1] Jensen, H. W. 1996. The Photon Map in Global Illumination. PhD dissertation.

[2] Hachisuka, T., Ogaki, S., and Jensen, H. W. 2008. Progressive photon mapping. In ACM SIGGRAPH Asia 2008 Papers (Singapore, December 10 - 13, 2008). J. C. Hart, Ed. SIGGRAPH Asia '08. ACM, New York, NY, 1-8.

[3] Hachisuka, T. and Jensen, H. W. 2009. Stochastic progressive photon mapping. In ACM SIGGRAPH Asia 2009 Papers (Yokohama, Japan, December 16 - 19, 2009). SIGGRAPH Asia '09. ACM, New York, NY, 1-8.

[4] Keller, A. 1997. Instant radiosity. In Proceedings of the 24th Annual Conference on Computer Graphics and interactive Techniques International Conference on Computer Graphics and Interactive Techniques. ACM Press/Addison-Wesley Publishing Co., New York, NY, 49-56.