Implementing Vertex Connection and Merging

Iliyan Georgiev

Technical report, November 2012 (revision 1)

[technical report][bibtex][code]



Bidirectional path tracing (BPT) and photon mapping (PM) are probably the two most versatile physically based rendering algorithms available today. It has been acknowledged that BPT and PM are complementary in terms of the types of light transport effects they can efficiently capture. Our recently proposed vertex connection and merging (VCM) algorithm aims to leverage the advantages of both methods by combining vertex connection techniques from BPT and vertex merging techniques from PM via multiple importance sampling [Georgiev et al. 2012]. We showed that this combined algorithm can efficiently capture a wide range of effects, and can be substantially more robust than either BPT or PM alone, while preserving the higher asymptotic performance of BPT.

The focus of our original paper is on the formal derivation, analysis, and evaluation of the combined VCM algorithm. In this technical report, we address the most technically challenging part of its practical implementation – the multiple importance sampling (MIS) weighting. Indeed, correctly implementing MIS is already taxing in BPT, and VCM increases the complexity by adding even more path sampling techniques. More importantly, the efficient light sub-path reuse with vertex merging allows for cheaply constructing large amounts of full paths for each pixel, which in turn significantly increases the impact of path weight evaluation on the overall performance. The traditional way of computing the MIS weights by iterating over all path vertices can therefore become inefficient. We derive a new scheme to accumulate partial weight sums in the vertices of the light and eye sub-paths. This allows us to efficiently compute the weight for a full path only using data stored at the two vertices that are connected or merged. The scheme is similar to the one independently developed by van Antwerpen [2011] for BPT, but in addition accounts for vertex merging techniques.

We also discuss how to handle infinite light sources and orthographic cameras with MIS, as well as light sources and materials involving delta distributions (e.g. point lights and glass).