<p>For a fixed strategy, you can end up consuming a different number of samples depending on your mutation. This can happen for at least two reasons. If your perturbation changes some material along the path to, say, a multi-lobe BSDF, you would need more samples to account for the lobe choice. This would shift everything by the number of extra samples used. If your ray eventually escapes the scene as you are tracing your mutation, or it hits a light source prematurely, you would use fewer samples. In these cases, you'd have to reject this proposal automatically.</p>

<p>One way of mitigating this issue in practice is to separate the two random number vectors for the camera and light subpaths and always mutate <em>all</em> dimensions of the unit hypercube <span class="math-container">$\mathcal{U}^{o(k)}$</span>, regardless if they are being used or not by the mutation. This doesn't remove the shift caused by BSDF changes (which is unavoidable) but at least you're not spilling your samples between camera and light subpaths.</p>

<p>Note that changing the strategy can also lead to an undesired rippling effect as primary samples will be used to perform a slightly different task (i.e. tracing a different strategy). This can be handled by introducing inverse mappings to preserve the geometry of the path, which is what is done by <a href="https://dl.acm.org/doi/10.1145/3132704" rel="nofollow noreferrer">Reversible Jump MLT</a>.</p>

CC BY-SA 4.0
2020-01-07T16:12:03.533Z
Thank you for your answer! "If your ray [...] hits a light source prematurely, you would use fewer samples.": Consider the $(s,t)$-strategy so that we generate a camera subpath with *exactly* $t$ vertices. If we hit a light source prematurely, then the `GenerateCameraSubpath` routine returns a vertex count less than $t$ and the PBR implementation returns $0$ radiance. So, "In these cases, you'd keep the subpart of the path that is relevant to avoid discarding the full state.", seems to be wrong. Am I missing something?
0xbadf00d
CC BY-SA 4.0
2020-01-07T16:30:27.167Z
You're right, I've edited my answer. There _might_ be a way to actually recycle but you'd have to adjust the MH ratio accordingly and I'm not sure how. In my experience, this recycling is probably not worth doing.
Hubble
CC BY-SA 4.0
2020-01-07T19:31:04.230Z
I think that I still don't understand the citation: Say the current primary sample space state is $u\in[0,1)^\mathbb N$ and we generated a path $x$ of length $k=s+t-1$ with $s$ and $t$ vertices on the light and camera subpath, respectively, from it. Say the camera subpath was generated using $u_1,\ldots,u_{d_1}$ and the light subpath using $u_{d_1+1},\ldots,u_{d_2}$. In the next iteration $u$ is mutated to $v\in[0,1)^\mathbb N$ (i.e. all dimensions are mutated). If I got you right, then - no matter whether we are still using the $(s,t)$-strategy in the next iteration or any other strategy -
0xbadf00d
CC BY-SA 4.0
2020-01-07T19:31:08.903Z
it might be the case that a subset of $v_1,\ldots,v_{d_1}$ is now used for the light subpath and a subset of $v_{d_1+1},\ldots,v_{d_2}$ is now used for the camera subpath (and any dimension $>d_2$ might be used for the light subpath as well). Is this correct? (a) If so, how does the index scheme described in the paragraph solve this problem? (b) You've mentioned the inversion described in RJ-MLT: How does this solve the problem? (c) Is there an implementation of the inversion in PBR available? See also my other question for that: https://computergraphics.stackexchange.com/q/9443/9254.
0xbadf00d
CC BY-SA 4.0
2020-01-07T19:38:56.790Z
Or let me put question (a) otherwise: If I understand correctly what they are doing, they actually have three separate vectors for each "stream" so that never a component of the camera stream vector is used for sampling the light subpath (and vice versa). If that's the case, I don't understand why they use the (somehow complicated) indexing scheme of a single vector.
0xbadf00d
CC BY-SA 4.0
2020-01-07T16:03:04.170Z
2020-01-07T16:26:45.430Z
2020-01-07T16:26:45.430Z
Hubble
<p>In the Multiplexed Metropolis Light Transport implementation of the book <em>Physically Based Rendering</em>, the proposal samples are generated by the <a href="http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Metropolis_Light_Transport.html#PrimarySampleSpaceSampler" rel="nofollow noreferrer">Primary Sample Space Sampler</a> <code>MLTSampler</code>.</p>

<p>I'm not sure if I really understand what the authors mean in the following paragraph:</p>

<blockquote>
  <p>In the context of MLT, the resulting sequence of sample requests creates a mapping between components <span class="math-container">$X$</span> of and vertices on the camera or light subpath. With the process described above, the components <span class="math-container">$X_0,\ldots,X_n$</span> determine the camera subpath (for some <span class="math-container">$n\in\mathbb N_0$</span>), and the remaining values <span class="math-container">$X_{n+1},\ldots,X_m$</span> determine the light subpath. If the camera subpath requires a different number of samples after a perturbation (e.g., because the random walk produced fewer vertices), then there is a shift in the assignment of primary sample space components to the light subpath. This leads to an unintended large-scale modification to the light path.</p>
</blockquote>

<p>Does this mean that even for a fixed strategy with <span class="math-container">$n\in\mathbb N_0$</span> vertices on the camera subpath, the number of random numbers needed to generate such a subpath may vary? Or do they mean that the shift in the assignment is happening only when we switch to an other strategy?</p>

<raytracing><pathtracing><global-illumination><monte-carlo>
In bidirectional path tracing, is a camera subpath with $n$ vertices determined by a fixed number of random numbers?
0xbadf00d
# In bidirectional path tracing, is a camera subpath with $n$ vertices determined by a fixed number of random numbers?

(Asked by: username_0 on 2020-01-07)

In the Multiplexed Metropolis Light Transport implementation of the book *Physically Based Rendering*, the proposal samples are generated by the [Primary Sample Space Sampler](http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Metropolis_Light_Transport.html#PrimarySampleSpaceSampler) `MLTSampler`.

I'm not sure if I really understand what the authors mean in the following paragraph:

> In the context of MLT, the resulting sequence of sample requests creates a mapping between components $X$ of and vertices on the camera or light subpath. With the process described above, the components $X\_0,\ldots,X\_n$ determine the camera subpath (for some $n\in\mathbb N\_0$), and the remaining values $X\_{n+1},\ldots,X\_m$ determine the light subpath. If the camera subpath requires a different number of samples after a perturbation (e.g., because the random walk produced fewer vertices), then there is a shift in the assignment of primary sample space components to the light subpath. This leads to an unintended large-scale modification to the light path.

Does this mean that even for a fixed strategy with $n\in\mathbb N\_0$ vertices on the camera subpath, the number of random numbers needed to generate such a subpath may vary? Or do they mean that the shift in the assignment is happening only when we switch to an other strategy?

**Tags:** raytracing, pathtracing, global-illumination, monte-carlo


---

## 1 answers

### Answer by username_1 on 2020-01-07. Score: 2

For a fixed strategy, you can end up consuming a different number of samples depending on your mutation. This can happen for at least two reasons. If your perturbation changes some material along the path to, say, a multi-lobe BSDF, you would need more samples to account for the lobe choice. This would shift everything by the number of extra samples used. If your ray eventually escapes the scene as you are tracing your mutation, or it hits a light source prematurely, you would use fewer samples. In these cases, you'd have to reject this proposal automatically.

One way of mitigating this issue in practice is to separate the two random number vectors for the camera and light subpaths and always mutate *all* dimensions of the unit hypercube $\mathcal{U}^{o(k)}$, regardless if they are being used or not by the mutation. This doesn't remove the shift caused by BSDF changes (which is unavoidable) but at least you're not spilling your samples between camera and light subpaths.

Note that changing the strategy can also lead to an undesired rippling effect as primary samples will be used to perform a slightly different task (i.e. tracing a different strategy). This can be handled by introducing inverse mappings to preserve the geometry of the path, which is what is done by [Reversible Jump MLT](https://dl.acm.org/doi/10.1145/3132704).

> **Comments:**
> **username_0**: Thank you for your answer! "If your ray [...] hits a light source prematurely, you would use fewer samples.": Consider the $(s,t)$-strategy so that we generate a camera subpath with *exactly* $t$ vertices. If we hit a light source prematurely, then the `GenerateCameraSubpath` routine returns a vertex count less than $t$ and the PBR implementation returns $0$ radiance. So, "In these cases, you'd keep the subpart of the path that is relevant to avoid discarding the full state.", seems to be wrong. Am I missing something?  
> **username_1**: You're right, I've edited my answer. There _might_ be a way to actually recycle but you'd have to adjust the MH ratio accordingly and I'm not sure how. In my experience, this recycling is probably not worth doing.  
> **username_0**: I think that I still don't understand the citation: Say the current primary sample space state is $u\in[0,1)^\mathbb N$ and we generated a path $x$ of length $k=s+t-1$ with $s$ and $t$ vertices on the light and camera subpath, respectively, from it. Say the camera subpath was generated using $u_1,\ldots,u_{d_1}$ and the light subpath using $u_{d_1+1},\ldots,u_{d_2}$. In the next iteration $u$ is mutated to $v\in[0,1)^\mathbb N$ (i.e. all dimensions are mutated). If I got you right, then - no matter whether we are still using the $(s,t)$-strategy in the next iteration or any other strategy -  
> **username_0**: it might be the case that a subset of $v_1,\ldots,v_{d_1}$ is now used for the light subpath and a subset of $v_{d_1+1},\ldots,v_{d_2}$ is now used for the camera subpath (and any dimension $>d_2$ might be used for the light subpath as well). Is this correct? (a) If so, how does the index scheme described in the paragraph solve this problem? (b) You've mentioned the inversion described in RJ-MLT: How does this solve the problem? (c) Is there an implementation of the inversion in PBR available? See also my other question for that: https://computergraphics.stackexchange.com/q/9443/9254.  
> **username_0**: Or let me put question (a) otherwise: If I understand correctly what they are doing, they actually have three separate vectors for each "stream" so that never a component of the camera stream vector is used for sampling the light subpath (and vice versa). If that's the case, I don't understand why they use the (somehow complicated) indexing scheme of a single vector.  

---

