Implementing vertex connection and merging

Iliyan Georgiev
Technical report, November 2012 (revision 2, July 2013)

An overview of our combined vertex connection and merging (VCM) algorithm. Rendering an image is performed in two stages. In the first stage, we trace sub-paths from the light sources, store their vertices, connect them to the eye, and additionally build a range search acceleration structure over them. In the second stage, we trace an eye sub-path for each pixel, and with each eye vertex we construct full paths via vertex connection (VC) and vertex merging (VM), evaluate their associated multiple importance sampling (MIS) weights, and accumulate the weighted contributions. The path weight evaluation is an important implementation aspect and is the main focus of this report. We present a way to efficiently evaluate the weight for a path using only data that is available at the two vertices being connected or merged, avoiding access to any other path vertices in memory. This also allows us to avoid storing the eye sub-path vertices, effectively making the second stage of the algorithm an extension of traditional path tracing with next event estimation, adding light vertex connection and merging techniques.

Abstract

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 and singular light sources, cameras and materials with MIS, how to use per-pixel merging radii, and how to implement VCM in a memory efficient way.

Downloads and links

  • technical report – revision 2 (PDF, 1.2 MB)
  • citation (BIB)
  • code (SmallVCM) – a (not too) small open source physically based renderer that implements our algorithm
  • original paper – Light Transport Simulation with Vertex Connection and Merging [Georgiev et al. 2012]

BibTeX reference

@TechReport{Georgiev:ImplementingVCM,
  author = {Iliyan Georgiev},
  title = {Implementing Vertex Connection and Merging},
  year = {2012},
  url = {http://www.iliyan.com/publications/ImplementingVCM},
  institution = {Saarland University}
}