(论文)[2023-SIG-Course] A Gentle Introduction to ReSTIR: Path Reuse in Real-time (1)

Posted on Edited on Views:
ReSTIR 的理论基础（蒙特卡洛积分、重要性采样、重采样）

ReSTIR

  • 主页
  • update：March 4, 2024

Abstract

  • Reservoir-based Spatio-Temporal Importance Resampling
  • 内容
    • ReSTIR 的动机与应用、理论、局限、实现
    • 理论
    • 算法例子，实现可能的坑
    • 引擎集成，问题与挑战

1-Introduction

  • sample reuse 并不罕见，例如 denoiser、upsampler
  • ReSTIR：unbiased
  • 直观：filters PDFs（例如 path guiding 也能这么理解）
    • aggregating multiple samples into one with a better PDF

Motivation of ReSTIR

  • path integral
    • \(h_i\)：image filter
      • 例如 box-filter：per-pixel domain \(\Omega_i\)

\[ I_i=\int_\Omega h_i(x)f(x)\;\mathrm{d}x \]

  • 试图让 \(p\propto f\)，但是很难

\[ \langle I_i\rangle=\frac{1}{N}\sum_{j=1}^N\frac{f(X_j)}{p(X_j)} \]

  • ReSTIR 的前提
    • a good path for pixel \(a\), when reused for pixel \(b\) with minor modifications, tends to be useful for pixel \(b\)
    • good：\(f\) 值大
  • 不能直接使用 good path，会引入 bias
    • RIS：resampled importance sampling
  • RIS：多个样本，分配权重，重新采样生成一个样本
    • RIS is an aggregation machine
  • 使用 \(1\) 个样本比不过使用 \(M\) 个样本
    • 但是好处是，输出只有 \(1\) 个样本，后续处理代价小

2-Preliminaries

Monte Carlo integration

\[ I=\int_\Omega f(x) \mathrm{d}x \]

  • \(M\) 个样本：\(X_1,\cdots,X_{M}\)
  • uniform distribution：\(p=\dfrac{1}{\Omega}\)

\[ I\approx\langle I\rangle=|\Omega| \frac{1}{M}\sum_{i=1}^{M}f(X_{i}) \]

  • general

\[ \langle I\rangle=\sum_{i=1}^M\frac{1}{M}\frac{f(X_i)}{p_i(X_i)} \]

  • 单样本

\[ \langle I\rangle=\frac{f(X)}{p(X)} \]

  • 无偏：\(\mathbb{E}[\langle I\rangle]=I\)
  • perfect PDF(zero variance)：\(f(X)/p(X),\forall X\in\Omega\) 是常数
  • variance：评估 quality/accuracy of an MC estimator
  • 降低方差
    • 更好的 \(p\)
    • 更多的 \(M\)

Supports

  • \(\text{supp}(f)\)
    • function’s support：函数值非 0
  • \(\text{supp}(X)\)
    • random variable’s：样本采样空间
  • MC 估计的无偏性保证：\(\text{supp}(f)\subseteq \text{supp}(X)\)
  • ReSTIR 复用了周围的样本，需要额外注意无偏性

Multiple Importance Sampling

\[ \langle I\rangle=\sum_{i=1}^Mm_i(X_i)\frac{f(X_i)}{p_i(X_i)} \]

  • 条件
    • \(\sum_im_i(x)=1,\forall x\in \text{supp}(f)\)
    • \(m_i(x)=0,\forall x\notin \text{supp}(X_i)\)
  • 无偏条件：\(\text{supp}(f)\subseteq \bigcup \text{supp}(X_i)\)
  • balance heuristic（平衡启发式）

\[ m_i(x)=\frac{p_i(x)}{\sum_jp_j(x)} \]

Unbiased Contribution Weights

  • 不能显式计算出 \(p(x)\)，如果可计算出 \(1/p(x)\) 的期望也行
    • 这个是定义：\(\mathbb{E}[W_X|X]=1/p(X)\)

\[ \langle I\rangle=f(X)\cdot W_X\quad\text{with}\quad\mathbb{E}[f(X)\cdot W_X]=\mathbb{E}[f(X)/p(X)]=I. \]

  • \(W_X\) 而不是 \(W(X)\)
    • 因为其不能在任意点求值，不能用在 MIS 参数中
    • 是估计，不是函数

3-Resampled Importance Sampling

  • MC 难点：没有好的便于采样的 pdf
  • RIS 流程
    • 输入一个候选样本序列 ：\(X_1,\cdots,X_M\)
    • 给每一个样本一个重采样权重 \(w_i\)
    • 根据权重重新生成一个样本
  • 需要 \(W_X\)，但是不一定是 pdf
    • 使用 \(W_X\) 替换掉 \(f(x)/p(x)\) 中的 \(1/p(x)\)
    • Unbiased Contribution Weights
  • 上面这个式子就是 ReSTIR 早期论文用的重采样权重
    • \(\hat{p}(x)\) is the target function that the PDF of \(X\) approximates better and better with more and more candidates.
    • \(\hat{p}(x)\) 虽然很难算，但是存在
    • 这里的 \(\dfrac{1}{M}\) 就是后面说的 MIS 权重【可以理解为 \(X_i\) 中可能有一样的，因此需要 MIS，\(1/M\) 的设置具体见下面这里】

\[ w_i=\frac{\hat{p}(X_i)}{p(X_i)}\quad\mathrm{and}\quad W_X=\frac{1}{\hat{p}(X)}\left(\frac{1}{M}\sum_{i=1}^{M}w_i\right) \]

  • 泛化版本：重采样时正比于 \(w_i\)，因此都一样

\[ w_i=\frac{1}{M}\frac{\hat{p}(X_i)}{p(X_i)}\quad\mathrm{and}\quad W_X=\frac{1}{\hat{p}(X)}\left(\sum_{i=1}^{M}w_i\right) \]

  • \(\sum_{i=1}^Mw_i\) 估计了 \(\hat{p}\) 的归一化因子

\[ \begin{aligned} \Rightarrow &\quad\sum_{i=1}^Mw_i=\hat{p}(X)W_X\\ \Rightarrow &\quad\mathbb{E}\left[\sum_{i=1}^Mw_i\right]=\mathbb{E}\left[\hat{p}(X)W_X\right]=\int_\Omega\hat{p}(x) \mathrm{d}x\\ \end{aligned} \]

  • 当 \(\sum_{i=1}^{M}w_i\) 的方差趋近于 0 时（样本数足够多）
    • output PDF 趋近于 target PDF（\(\bar{p}=\hat{p}/\int\hat{p}\)）
    • \(W_X\) 趋近于 \(1/\bar{p}(X)\)
    • 完全近似成 target function
  • 选择 \(\hat{p}=f\) 可以实现零方差

Resampled Importance Sampling

  • 流程如下
    • 注意：这里的 \(m_i(X_j)\) 也是存在的，外面和里面的下标含义不一样

  • 如果生成 \(X_i\) 的 pdf 已知，都为 \(p\)，那么 \(W_{X_i}=\dfrac{1}{p(X_i)}\)
  • 正确性保证
    • 这里 \(m_i\) 的含义是假定样本来自于 \(M\) 个不同的分布（通用的假设）

\[ \mathbb{E}[W_X] =\dfrac{1}{\hat{p}(X)}\cdot\mathbb{E}\left[\sum_{i=1}^Mw_i\right] =\dfrac{1}{\hat{p}(X)}\cdot\mathbb{E}\left[\sum_{i=1}^Mm_i(X_i)\hat{p}(X_i)W_{X_i}\right] \]

  • 分析

\[ \begin{aligned} \mathbb{E}[f(X)W_X] &=\mathbb{E}_{X_j}\left[\sum_{j=1}^{M}\left(f(X_j)\cdot\left(\dfrac{1}{\hat{p}(X_j)}\cdot\sum_{i=1}^Mw_i\right)\cdot\dfrac{w_j}{\sum_{i=1}^Mw_j}\right)\right]\\ &=\mathbb{E}_{X_j}\left[\sum_{j=1}^{M}\left(f(X_j)m_j(X_j)W_{X_j}\right)\right] \end{aligned} \]

  • 还需要保证 \(X_i\) 能够覆盖到整个样本空间（\(f\) 的 support）（需要找到所有可能的样本）
  • 如果所有样本的 \(w_i\) 都是 0，那么没有样本生成，算法返回 a null sample \(\emptyset\)（\(W_{\emptyset}=0\)）
    • 特殊处理而不是直接替换，替换会导致 bias（为啥？）
  • 独立同分布：如果生成样本 \(X_i\) 的 pdf 已知为 \(p(x)\)，MIS 权重可以设置为 \(\dfrac{1}{M}\)
    • 期望含义上，\(\mathbb{E}[W_X]=\dfrac{\int\hat{p}(X)}{\hat{p}(X)}\)，\(M\to\infty\)

\[ \begin{aligned} \mathbb{E}[W_X] &=\dfrac{1}{\hat{p}(X)}\cdot\mathbb{E}\left[\sum_{i=1}^M\dfrac{1}{M}\dfrac{\hat{p}(X_i)}{p(X_i)}\right]\\ &=\dfrac{1}{\hat{p}(X)}\cdot\mathbb{E}\left[\dfrac{\hat{p}(X)}{p(X)}\right]\\ &=\dfrac{1}{\hat{p}(X)}\cdot\int\hat{p}(X)\;\mathrm{d}X\\ \end{aligned} \]

\[ \begin{aligned} \mathbb{E}[f(X)W_X] &=\mathbb{E}_{X_j}\left[\sum_{j=1}^{M}\left(f(X_j)\cdot\dfrac{1}{M}\cdot \dfrac{1}{p(X_j)}\right)\right]\\ &=\mathbb{E}_{X_j}\left[\dfrac{1}{M}\cdot\sum_{j=1}^{M}\dfrac{f(X_j)}{p(X_j)}\right]\\ &=\mathbb{E}_{X_j}\left[\dfrac{f(X_j)}{p(X_j)}\right]\\ \end{aligned} \]

例子：Simple integration

  • 函数 \(f\)，根据已知的 pdf \(p\) 生成样本序列 \(X_1,\cdots,X_M\)
  • 使用方式
    • 已知 \(p\)，于是 \(W_{X_i}=\dfrac{1}{p(X_i)}\)
    • \(m_i(x)=\dfrac{1}{M}\)
      • can only be used if all samples individually cover \(\text{supp}(f)\)
      • 如果一个样本有两种采样方式，而且他们并不是都完全覆盖 \(\text{supp}(f)\)，\(1/M\) 带来 bias
        • 例如 BSDF + light
  • 计算

\[ w_i=\dfrac{1}{M}\dfrac{\hat{p}(X_i)}{p(X_i)} \]

  • 根据 \(w_i\) 生成新样本 \(Y\)

\[ W_Y=\dfrac{1}{\hat{p}(Y)}\sum_{j=1}^{M}w_j \]

  • 此时正确性保证容易证明
    • 最后的结果就是我们常用的 MC 无偏估计

\[ \begin{aligned} \mathbb{E}\left[f(Y)W_Y\right] &=\sum_{i=1}^{M}\left(\left(f(X_i)\cdot\dfrac{1}{\hat{p}(X_i)}\sum_{j=1}^{M}w_j\right)\cdot\left(\dfrac{w_i}{\sum_{j=1}^{M}w_j}\right)\right)\\ &=\dfrac{1}{M}\sum_{i=1}^{M}\dfrac{f(X_i)}{p(X_i)}\\ \end{aligned} \]

  • 使用 \(\hat{p}=f\) 的时候效果最好，使用其它值也能保证正确，但是效果变差（方差分析？）
    • 计算 \(f\) 复杂度比较高的时候，使用其他近似

例子：BSDF importance sampling

  • 我们不知道具体的 \(f\)，使用简单的替代：\(\hat{p}=\text{BSDF}\cdot\cos\)
    • 证明和上面类似的，上面并没有用到 \(\hat{p}=f\) 的条件
  • 效果并不一定好

MIS weights

  • \(m_i(x)=\dfrac{1}{M}\) 只有在一种采样方式的时候无偏
    • 或者说所有的采样方式都能完全覆盖整个定义域的时候，无偏
    • 否则则是有偏的
      • \(\sum_{1}^{M}m_i(x)\) 小于 1 了（有些采样方式采样不到 \(x\)）
  • 如果样本生成的 pdf 已知，则可以使用平衡启发式

\[ m_i(x)=\frac{p_i(x)}{\sum_{j=1}^Mp_j(x)} \]

  • MIS 权重如果考虑了其他样本 \(x_j\) 的信息，多半是错误的
    • 只考虑当前样本 \(x\) 的信息
  • 在正确计算 MIS 之后，我们只需要满足所有方法的采样空间的并集包含 \(f\) 的定义域即可
    • 不要求每一个都包含
    • 容易实现：只需要并上一个保守实现即可
  • 算 MIS 权重很慢，需要改进

例子：RIS between BSDF and NEE

  • BSDF（\(p_1\)）采样得到 \(M_1\) 个样本，light（\(p_2\)）采样得到 \(M_2\) 个样本
  • BSDF 为例
    • 相当于这里看作有 \(M_1+M_2\) 种采样方案
    • \(i=1,\cdots,M_1\) 时，\(m_i,w_i\) 如下

\[ m_i(x)=\frac{p_1(x)}{M_1p_1(x)+M_2p_2(x)} \]

\[ \begin{aligned} w_{i}(X_i)& =m_{1}(X_{i}) \hat{p}(X_{i})W_{X_{i}} \\ &= \left(\frac{p_{1}(X_{i})}{M_{1}p_{1}(X_{i})+M_{2}p_{2}(X_{i})}\right)\hat{p}(X_{i})\frac{1}{p_{1}(X_{i})} \end{aligned} \]

  • light 类似，\(i=M_1+1,\cdots,M_1+M_2\) 时选 light
  • \(W_X\)

\[ W_X=\dfrac{1}{\hat{p}(X)}\sum_{j=1}^{M_1+M_2}w_j \]

  • 证明类似

\[ \begin{aligned} \mathbb{E}[f(X)W_X] &=\mathbb{E}_{X_j}\left[\sum_{j=1}^{M}\left(f(X_j)m_j(X_j)W_{X_j}\right)\right]\\ &=\mathbb{E}_{X_j}\left[\sum_{j=1}^{M_1}\left(f(X_j)\cdot m_j(X_j)\cdot\dfrac{1}{p_1({X_j})}\right)+\cdots\right]\\ &=\mathbb{E}_{X_j}\left[\left(\dfrac{f(X_j)}{p_1({X_j})}\cdot m_j(X_j)\right)+\cdots\right]\\ &=\mathbb{E}_{X_j}\left[\left(\dfrac{f(X_j)}{p_1({X_j})}\cdot m_j(X_j)\right)\right]+\cdots\\ 独立随机变量 &=\int\left(\dfrac{f(X_j)}{p_1({X_j})}\cdot m_j(X_j)\right)\cdot p_1(X_j)\;\mathrm{d}X_j+\cdots\\ &=\int\left(f(X_j)\cdot m_j(X_j)\right)\;\mathrm{d}X_j+\cdots\\ &=\int\left(f(X_j)\cdot\sum_j m_j(X_j)\right)\;\mathrm{d}X_j\\ &=\int f(X_j)\;\mathrm{d}X_j\\ \end{aligned} \]

\[ \begin{aligned} \mathbb{E}[f(X)W_X] &=\mathbb{E}_{X_j}\left[\sum_{j=1}^{M}\left(f(X_j)m_j(X_j)W_{X_j}\right)\right]\\ &=\mathbb{E}_{X_j}\left[\sum_{j=1}^{M_1}\left(f(X_j)\cdot\frac{p_1(X_j)}{M_1p_1(X_j)+M_2p_2(X_j)}\cdot\dfrac{1}{p_1({X_j})}\right)+\cdots\right]\\ &=\mathbb{E}_{X_j}\left[\left(\dfrac{f(X_j)}{p_1({X_j})}\cdot\frac{M_1p_1(X_j)}{M_1p_1(X_j)+M_2p_2(X_j)}\right)+\cdots\right]\\ &=\mathbb{E}_{X_j}\left[\left(f(X_j)\cdot\frac{M_1}{M_1p_1(X_j)+M_2p_2(X_j)}\right)\right]+\cdots\\ 独立随机变量 &=\int\left(f(X_j)\cdot\frac{M_1}{M_1p_1(X_j)+M_2p_2(X_j)}\right)\cdot p_1(X_j)\;\mathrm{d}X_j+\cdots\\ &=\int\left(f(X_j)\cdot\frac{M_1 p_1(X_j)}{M_1p_1(X_j)+M_2p_2(X_j)}\right)\;\mathrm{d}X_j+\cdots\\ &=\int\left(f(X_j)\cdot\frac{M_1 p_1(X_j)+M_2p_2(X_j)}{M_1p_1(X_j)+M_2p_2(X_j)}\right)\;\mathrm{d}X_j\\ &=\int f(X_j)\;\mathrm{d}X_j\\ 也等价于使用\ p_{12}\ 进行采样 &=\dfrac{M_1}{M_1+M_2}\mathbb{E}_{X_j}\left[\left(\frac{(M_1+M_2)f(X_j)}{M_1p_1(X_j)+M_2p_2(X_j)}\right)\right]+\cdots\\ &=\dfrac{M_1}{M_1+M_2}\mathbb{E}_{X_j}\left[\left(\frac{f(X_j)}{p_{12}(X_j)}\right)\right]+\cdots\\ &=\mathbb{E}_{X_j}\left[\left(\frac{f(X_j)}{p_{12}(X_j)}\right)\right] \end{aligned} \]

Inputs with unknown PDFs

  • 不知道采样样本所使用的 pdf，但是知道 UCW（unbiased contribution weights）
    • \(W_{X_1},\cdots,W_{X_M}\)
    • 并且假定输入是通过 RIS 得到的
    • 根据 UCW 定义：\(\mathbb{E}[W_{X_i}]=\dfrac{1}{p_i(X_i)}\)
  • 此时整体流程都一样，但是算不出来 MIS 权重
  • 因为 RIS 得到，使用 \(\hat{p}_i(x)\) 作为代理
  • generalized balance heuristic

\[ m_i(x)=\frac{\hat{p}_i(x)}{\sum_{j=1}^M\hat{p}_j(x)} \]

  • 迭代的时候，我们保证变量的定义域（原始的 \(p\) 采样得到的）和 target function \(\hat{p}\) 的定义域完全相同
    • \(\hat{p}=0\) exactly when \(p=0\)
    • 通过使用一个 canonical sample \(X_c\) 保证（通过在一个覆盖 \(\text{supp}(\hat{p})\) 的 pdf RIS 实现）
  • 如此便能实现重用