Implementation of VCM/UPS in Lightmetrica: Part 1

Posted on Jul 20, 2016
Development Lightmetrica

(This article is written for ray-tracing camp 4 Advent Calender)

Introduction

One of the major purpose of developing Lightmetrica is to offer the researcher to a way to compare the existing techniques without unnecessary implementation. So we are trying to implement various rendering techniques as much as possible in one framework. Recent update of Lightmetria includes an implementation of a set of rendering techniques based on photon density estimation. These techniques is originated from photon mapping developed by Jensen et al. [1996]. From the invention of photon mapping, various techniques have been actively developed so far.

Specifically, the photon mapping based techniques is known to be efficient for the scene containing specular-diffuse-specular (SDS) paths. This kind of lighting effect is important for some scenes, e.g., the caustics in the surface under water seen from the outside is an typical example. The rendering techniques based on independent path sampling (e.g., bidirectional path tracing [Veach & Guibas 1994]) often suffer from rendering these scenes. This is because independent sampling techniques need to sample SDS paths with low probability, if the size of light source is small. If the light source is spatially degenerated one (e.g., point light source), the sampling become theoretically impossible and requires special extension to the path space to handling these cases [Kaplanyan et al. 2011].

Recent advance in developing photon mapping based techniques succeeded to incorporate bidirectional path sampling in the framework of photon density estimation. This technique is independently developed by two research groups: vertex connection and merging (VCM) by Georgiev et al. [2012] and unified path sampling (UPS) by Hachisuka et al. [2012]. So in this article, as a mark of respect to both groups, we call this technique by VCM/UPS.

They integrated two approaches originally developed independently based on different formulations into one so that to be combinable via multiple importance sampling (MIS) [Veach & Guibas 1995]. MIS is an widely used technique in rendering researches to combine two or more different way of sampling. For example, path tracing with next event estimation often combines two different way of the sampling a path with a compensation to the probability measure; sampling from the density associated with BSDF and from the direct sampling of the light sources.

Also, the combined approach is naturally extended to progressive photon density estimation framework by Knaus and Zwicker [2011]. The progressive photon density estimation is originally developed by Hachisuka et al. [2008, 2009], achieving the consistent estimation of the photon mapping. The technique is later simplified by Knaus and Zwicker [2011] and both VCM and UPS papers utilizes the framework to achieve the progressive estimation.

In Lightmetrica, we implemented various the photon mapping based rendering algorithms to make it possible to compare algorithms in the consistent manner, without introducing uncertainty in comparison. Our implementation includes:

We achieved the implementation of VCM/UPS with only ~800 lines of code excluding the shared codes. Because the main focus of our framework is not the optimization, we attempted to implement the code so that we can understand easily. The implementation follows the mathematical formulation so that we can grasp the connection between the formulation and the implementation. As for the optimized implementation utilizing the recursive formulations, we can refer to the technical paper by Georgiev [2012] and smallvcm.

In this article, I attempt to describe the implementation of these techniques from the theoretical background to the implementation detail. The description in this article is based on the implementation when this article is written and it might be changed by the following updates.

Formulation

Light transport simulation

Here we will introduce the formulation of the light transport. We will begin with the famous path integration formulation by Veach [1997]. In the formulation, the pixel intensity can be written as $$ \begin{equation} I = \int_{\Omega} f(\bar{x}) d\mu(\bar{x}), \end{equation} $$ where $\bar{x}=\mathbf{x}_1\dots\mathbf{x}_{k-1}$ is the path with length $k$, $\Omega$ is a set of all paths in any length and $\mu$ is the product area measure. $f$ is the measurement contribution function. See Veach [1997] for the detailed definition.

Desigining path sampling techniques

We will design two types of path sampling techniques: vertex connection which constructs a path with connecting two different path vertices, and vertex merging which constructs a path by merging two different path vertex within the specified range. In this discussion, we will focus on sampling the path with the length $k$.

Vertex connection: In order to sample a path with vertex connection, initially we sample the two different paths originated from the light source and the sensor, and connect the two path vertices from each subpath to construct a path. Given a path $\bar{x}$ with the length $k$, there is $k+2$ ways of sampling the path. These sampling strategy is often indexed by using the number of vertices $s$ and $t$ counting from the light source and the sensor respectively. The pdf for sampling with the strategy $(s,t)$ is defined as $$ \begin{equation} p^{VC}_{s,t}(\bar{x}) = p_L(\mathbf{x}_{1}\dots\mathbf{x}_{s}) \cdot p_E(\mathbf{x}_{k+1}\dots\mathbf{x}_{s+1}), \end{equation} $$ where $$ \begin{align} p_L(\mathbf{x}_{1}\dots\mathbf{x}_{s}) &= \begin{cases} 1, & s = 0 \\ p(\mathbf{x}_1) \prod_{i=1}^{s-1} p(\mathbf{x}_{i}\to\mathbf{x}_{i+1}), & \text{otherwise}. \end{cases} \\ p_E(\mathbf{x}_{1}\dots\mathbf{x}_{s}) &= \begin{cases} 1, & t = 0 \\ p(\mathbf{x}_{k+1}) \prod_{i=1}^{t-1} p(\mathbf{x}_{k+1-i}\to\mathbf{x}_{k-i}), & \text{otherwise}. \end{cases} \end{align} $$ Here $p$ is the pdf defined on area measure.

Vertex merging: The essential point of VCM/UPS is taking photon density estimation as path sampling techniques. We can think of the path introduced in the process of the photon density estimation as the extended path. Similar to vertex connection, we can think of two subpaths originated from the light source and the emitter. We let each subpaths be $x_L=\mathbf{x}_1\dots\mathbf{x}_s\mathbf{x}^{*}_{s+1}$ and $x_E=\mathbf{x}_{s+1}\dots\mathbf{x}_{k}$. Here we consider one extra path vertex $\mathbf{x}^{*}_{s+1}$, which is the position of photon in the context of photon mapping. We define the extended path $\bar{x}=\mathbf{x}_1\dots\mathbf{x}_s\mathbf{x}^{*}_{s+1}\mathbf{x}_{s+1}\dots\mathbf{x}_{k}$ concatenating two subpaths. The evaluation of the measurement contribution function $f$ given the extended path just ignore the path vertex $\mathbf{x}^{*}_{s+1}$, that is, evaluates $f(\mathbf{x}_1\dots\mathbf{x}_s\mathbf{x}_{s+1}\dots\mathbf{x}_{k})$.

However in order to combine the extended path with the path generated by vertex connection, we need to express the pdf in the same measure. So we consider the density estimation as the process to decide whether to merge two vertices by Russian roulette with the given radius $r$. This process is similar to calculating the marginal density with respect to area measure around the position of the photon $\mathbf{x}_s$ within the radius $r$, making the pdf for extended path be same as $p^{VC}_{s,t}(\bar{x})$: $$ \begin{align} p^{VM}_{s,t}(\bar{x}) &= p^{VC}_{s,t}(\bar{x}) \cdot \mbox{Pr}(\| \mathbf{x}_{s+1} - \mathbf{x}^{*}_{s+1} \| < r) \\ &= p^{VC}_{s,t}(\bar{x}) \int_{A_r} p(\mathbf{x}_{s}\to\mathbf{x}) d\mathbf{x}, \end{align} $$ where $A_r$ is a set of points in the scene surfaces around $\mathbf{x}_{s}$ within the range $r$. If $K_r$ is constant kernel with radius $r$, this equation can be approximated as $$ \begin{equation} p^{VM}_{s,t}(\bar{x}) \approx \pi r^2 \, p(\mathbf{x}_{s-1}\to\mathbf{x}^*_s) \cdot p^{VC}_{s,t}(\bar{x}). \end{equation} $$

Combined estimator

Now we can design an estimate of $I$ combining vertex connection and merging utilizing multiple importance sampling. We will combine single path from vertex connection and $N_{VM}$ paths from vertex merging. This is because we can make use of efficient path reusal with spacial data structure for range queries such as Kd-tree or hash grid. Indeed we can consider multiple paths with vertex connection, in our implementation we decided not to do so because vertex connection involves in relatively high-cost triangle intersection queries. The combined estimate can be written as $$ \begin{equation} \langle I \rangle = \underbrace{ \sum_{s,t\geq 0} w_{VC,s,t}(\bar{x}) \frac{f(\bar{x})}{p^{VC}_{s,t}(\bar{x})} \frac{1}{N_{VM}}}_{\langle I \rangle_{VC}} + \underbrace{ \sum_{l=1}^{N_{VM}} \sum_{s,t\geq 2} \chi_{s,t}(\bar{x}_l) w_{VM,s,t}(\bar{x}_l) \frac{f(\bar{x}_l)}{p^{VM}_{s,t}(\bar{x}_l)}}_{\langle I \rangle_{VM}}, \end{equation} $$ where $\chi_{s,t}$ is the characteristic function that equals to one if $\| \mathbf{x}_{s+1} - \mathbf{x}^{*}_{s+1} \| < r$, otherwise zero. $w_{v,s,t}$ is the power heuristics weight defined as $$ \begin{equation} w_{v,s,t}(\bar{x}) = \frac{p^{v}_{s,t}(\bar{x})^\beta}{ \sum_{s',t'\geq 0} p^{VC}_{s',t'}(\bar{x})^\beta + N_{VM} \sum_{s',t'\geq 2} p^{VM}_{s',t'}(\bar{x})^\beta }. \end{equation} $$ If $\beta=1$, the weight becomes the balance heuristics. In the actual implementation, the summation $\sum_{l=1}^{N_{VM}}$ and the selection of the path satisfying $\chi_{s,t}$ is achieved via range query structure.

(continue to part 2)

References