Bidirectional Path Tracing 5 - More than one way to form a path

Plug in the area space light transport equation:

$$L( x'\to x'' )=L_{e}( x'\to x')+\int_{A }L_{i}( x \to x' )f_{s}(x \to x' \to x'')G(x \leftrightarrow  x')dx$$

into the measurement equation:

$$I = \int_{A_{lens}} \int_{A_{film}} W_{e}(x_{film}\rightarrow  x_{lens})L(x_{film}\rightarrow  x_{lens}) G(x_{film}\leftrightarrow  x_{lens}) dx_{film} dx_{lens}$$

recursive expand it, we get:

$I = \sum_{k=1}^{\infty}\int_{A^{k+1}}L_{e}(x_{0}\rightarrow x_{1})G(x_{0}\leftrightarrow x_{1})\prod_{i=1}^{k-1}f_{s}(x_{i-1} \rightarrow x_{i} \rightarrow x_{i+1})G(x_{i} \leftrightarrow x_{i+1})$

$\:\:\:\:\:\:\:\:W_{e}(x_{k-1} \rightarrow x_{k}) dA(x_{0})...dA(x_{k})$

$= \int_{A^{2}}L_{e}(x_{0}\rightarrow x_{1})G(x_{0}\leftrightarrow x_{1})W_{e}(x_{0} \rightarrow x_{1})dA(x_{0})dA(x_{1})$

$+ \int_{A^{3}}L_{e}(x_{0}\rightarrow x_{1})G(x_{0}\leftrightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})G(x_{1}\leftrightarrow x_{2})$

$\:\:\:\:\:\:\:\:W_{e}(x_{1} \rightarrow x_{2})dA(x_{0})dA(x_{1})dA(x_{2})$

$+ \int_{A^{4}}L_{e}(x_{0}\rightarrow x_{1})G(x_{0}\leftrightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})G(x_{1}\leftrightarrow x_{2})f_{s}(x_{1} \rightarrow x_{2} \rightarrow x_{3})$

$\:\:\:\:\:\:\:\:G(x_{2}\leftrightarrow x_{3})W_{e}(x_{2} \rightarrow x_{3})dA(x_{0})dA(x_{1})dA(x_{2})dA(x_{3})$

$+\:\: ............$

In English:

measurement result (radiance)

= integrate all measured value with path length 1 to path length infinity

= integrated path length 1 measured value ( direct visible light)

+ integrated path length 2 measured value ( direct lighting )

+ integrated path length 3 measured value ( first bounce lighting )

+ ....

All these paths can be built by tracing ray from camera or from light, or from both and connect together, there are many (be more specific, n + 1 methods if the path contains n vertices) ways to form a path. We can pick out a length 3 (first bounce, 4 vertices) path $x_{0}x_{1}x_{2}x_{3}$as case study (for all different lengths it's still the same thing, just feel length 3 is on a sweet spot to cover the idea). Follow Veach's naming convention, $s$ stands for the path vertices start tracing from light, $t$ stands for the path vertices start tracing from camera (or eye). For path length 3, s + t = 4, we have 5 kinds of ways to form the path:

$s = 0, t = 4$  trace ray from camera until it hits the light (naive path tracing)

$s = 1, t = 3$  trace ray from camera and connect to a sample on light (commonly used path tracing)

$s = 2, t = 2$  trace ray from both light and camera, connect them together
$s = 3, t = 1$  trace ray from light and connect to a sample on camera lens ( t = 1 style light tracing )

$s = 4, t = 0$  trace ray from light until it hits the camera lens (t = 0 style light tracing )

The function to be integrated for path $x_{0}x_{1}x_{2}x_{3}$ is the same for any s, t combinations:

$f(\bar{x}) = L_{e}(x_{0}\rightarrow x_{1})G(x_{0}\leftrightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})G(x_{1}\leftrightarrow x_{2})f_{s}(x_{1} \rightarrow x_{2} \rightarrow x_{3})$

$\:\:\:\:\:\:\:\:G(x_{2}\leftrightarrow x_{3})W_{e}(x_{2} \rightarrow x_{3})$

The pdf to form the path is different from one combination to another combination though. In Veach97 the pdf usually measured in "projection solid angle" space. It is defined as:

$$pdf_{\omega^{\perp}}(x, \omega) = pdf_{\omega}(x, \omega) / \cos\theta$$

and since we can transform pdf from solid angle space to area space as:

$$pdf_{A}(x, {x}') = pdf_{\omega}(x, \omega)\cos\theta_{{x}'}/d(x\leftrightarrow{x}')^{2}$$

The introduction of projection solid angle brings the geometry term $G$ into battle:

$$pdf_{A}(x, {x}') = pdf_{\omega^{\perp}}(x, \omega)G(x\leftrightarrow{x}')$$

With this projection solid angle $pdf_{\omega^{\perp}}$, the $pdf_{A}$ for different s, t combination can be written as:

$pdf_{A}(\bar{x}_{s=0,t=4}) =pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{3}\rightarrow x_{2})G(x_{2}\leftrightarrow x_{3}) pdf_{\omega^{\perp}}(x_{2}\rightarrow x_{1})G(x_{1}\leftrightarrow x_{2})$

$\:\:\:\:\:\:\:\:pdf_{\omega^{\perp}}(x_{1}\rightarrow x_{0})G(x_{0}\leftrightarrow x_{1})$

$pdf_{A}(\bar{x}_{s=1,t=3}) =pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{3}\rightarrow x_{2})G(x_{2}\leftrightarrow x_{3}) pdf_{\omega^{\perp}}(x_{2}\rightarrow x_{1})G(x_{1}\leftrightarrow x_{2})$

$\:\:\:\:\:\:\:\:pdf_{A}(x_{0})$

$pdf_{A}(\bar{x}_{s=2,t=2}) =pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{3}\rightarrow x_{2})G(x_{2}\leftrightarrow x_{3}) pdf_{\omega^{\perp}}(x_{1}\leftarrow x_{0})G(x_{0}\leftrightarrow x_{1})$

$\:\:\:\:\:\:\:\:pdf_{A}(x_{0})$

$pdf_{A}(\bar{x}_{s=3,t=1}) =pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{2}\leftarrow x_{1})G(x_{1}\leftrightarrow x_{2}) pdf_{\omega^{\perp}}(x_{1}\leftarrow x_{0})G(x_{0}\leftrightarrow x_{1})$

$\:\:\:\:\:\:\:\:pdf_{A}(x_{0})$

$pdf_{A}(\bar{x}_{s=4,t=0}) =pdf_{\omega^{\perp}}(x_{3}\leftarrow x_{2})G(x_{2}\leftrightarrow x_{3})pdf_{\omega^{\perp}}(x_{2}\leftarrow x_{1})G(x_{1}\leftrightarrow x_{2})$

$\:\:\:\:\:\:\:\:pdf_{\omega^{\perp}}(x_{1}\leftarrow x_{0})G(x_{0}\leftrightarrow x_{1})pdf_{A}(x_{0})$

Divide $f(\bar{x})$ by $pdf_A$, we got five different Monte Carlo estimators $C_{s,t}^{*}$for path  $x_{0}x_{1}x_{2}x_{3}$:

$C_{0,4}^{*} =\frac{ L_{e}(x_{0}\rightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})f_{s}(x_{1} \rightarrow x_{2} \rightarrow x_{3})W_{e}(x_{2} \rightarrow x_{3}) }{pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{3}\rightarrow x_{2})pdf_{\omega^{\perp}}(x_{2}\rightarrow x_{1})pdf_{\omega^{\perp}}(x_{1}\rightarrow x_{0})}$

$C_{1,3}^{*} =\frac{ L_{e}(x_{0}\rightarrow x_{1})G(x_{0}\leftrightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})f_{s}(x_{1} \rightarrow x_{2} \rightarrow x_{3})W_{e}(x_{2} \rightarrow x_{3}) }{pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{3}\rightarrow x_{2}) pdf_{\omega^{\perp}}(x_{2}\rightarrow x_{1})pdf_{A}(x_{0})}$

$C_{2,2}^{*} =\frac{ L_{e}(x_{0}\rightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})G(x_{1}\leftrightarrow x_{2})f_{s}(x_{1} \rightarrow x_{2} \rightarrow x_{3})W_{e}(x_{2} \rightarrow x_{3}) }{pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{3}\rightarrow x_{2}) pdf_{\omega^{\perp}}(x_{1}\leftarrow x_{0})pdf_{A}(x_{0})}$

$C_{3,1}^{*} =\frac{ L_{e}(x_{0}\rightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})f_{s}(x_{1} \rightarrow x_{2} \rightarrow x_{3})G(x_{2}\leftrightarrow x_{3})W_{e}(x_{2} \rightarrow x_{3}) }{pdf_{A}(x_{3})pdf_{\omega^{\perp}}(x_{2}\leftarrow x_{1}) pdf_{\omega^{\perp}}(x_{1}\leftarrow x_{0})pdf_{A}(x_{0})}$

$C_{4,0}^{*} =\frac{ L_{e}(x_{0}\rightarrow x_{1})f_{s}(x_{0} \rightarrow x_{1} \rightarrow x_{2})f_{s}(x_{1} \rightarrow x_{2} \rightarrow x_{3})W_{e}(x_{2} \rightarrow x_{3}) }{pdf_{\omega^{\perp}}(x_{3}\leftarrow x_{2})pdf_{\omega^{\perp}}(x_{2}\leftarrow x_{1}) pdf_{\omega^{\perp}}(x_{1}\leftarrow x_{0})pdf_{A}(x_{0})}$

all geometry terms got cancelled out except the one that connect end points between light path and eye path. The 5 estimators show beautiful symmetry between each opposite side (s1t3 vs s3t1, s0t4 vs s4t0 ). In fact, Veach made all path length cases into a generalized equation and it is one of the largest building block for bidirectional path tracing:

For a path $\bar{x}_{s,t} = y_{0}...y_{s-1}z_{t-1}...z_{0}$, the unweighted contribution can be computed as $C_{s,t}^{*} = \alpha_{s}^{L}c_{s,t}\alpha_{t}^{E}$, where light path factor:

$\alpha_{0}^{L} = 1$

$\alpha_{1}^{L} = L_{e}^{(0)}(y_{0}) / P_{A}(y_{0})$

$\alpha_{i}^{L} = \frac{f_{s}(y_{i-3} \rightarrow y_{i-2} \rightarrow y_{i-1})}{P_{\omega^{\perp}}(y_{i-2} \rightarrow y_{i-1})} \alpha_{i-1}^{L}$ for $i \geq 2$

and eye path factor:

$\alpha_{0}^{E} = 1$

$\alpha_{1}^{E} = W_{e}^{(0)}(z_{0}) / P_{A}(z_{0})$

$\alpha_{i}^{E} = \frac{f_{s}(z_{i-3} \rightarrow z_{i-2} \rightarrow z_{i-1})}{P_{\omega^{\perp}}(z_{i-2} \rightarrow z_{i-1})} \alpha_{i-1}^{E}$ for $i \geq 2$

and connection factor:

$c_{0,t} = L_{e}(z_{t-1} \rightarrow z_{t-2})$

$c_{s,0} = W_{e}(y_{s-2} \rightarrow y_{s-1})$

$c_{s,t} = f_{s}(y_{s-2} \rightarrow y_{s-1} \rightarrow z_{t-1})G(y_{s-1} \leftrightarrow z_{t-1}) f_{s}(y_{s-1} \rightarrow z_{t-1} \rightarrow  \rightarrow z_{t-2} )$ for $s, t > 0$

One notation looks a bit weird is that $L_{e}^{(0)}$ and $W_{e}^{(0)}$. Veach97 call this "spatial component" and define the radiance/importance as:

$L_{e}(y_{0} \rightarrow y_{1}) = L_{e}^{(0)}(y_{0})L_{e}^{(1)}(y_{0} \rightarrow y_{1})$

$W_{e}(z_{1} \rightarrow z_{0}) = W_{e}^{(0)}(z_{0})W_{e}^{(1)}(z_{1} \rightarrow z_{0})$

$f_{s}(y_{-1} \rightarrow y_{0} \rightarrow y_{1}) =  L_{e}^{(1)}(y_{0} \rightarrow y_{1})$

$f_{s}(z_{1} \rightarrow z_{0} \rightarrow z_{-1}) =  W_{e}^{(1)}(z_{1} \rightarrow z_{0})$

The purpose of this notation, according to Veach, is to reduce the number of special cases that need to be considered, by interpreting the directional component of emission as a BSDF. Though personally, I don't feel this particular tempting to me. Writing a branch VS writing another bsdf interface for light and camera, I prefer a branch.

My fingers are aching by typing latex equation now and it's kinda dry to go through the math, but at this point we have all the stuff I need to implement light tracing : importance, filter, path contribution $C_{s,t}^{*}$. The next post will focus on the light tracing implementation, and some (not that academic) ways to verify the result.