2.2 提高性能

分层采样

分层采样将积分域 $\Lambda$ 分为 $n$ 互不重叠区域 $\Lambda_1, \Lambda_2, \dots, \Lambda_n$，每个区域称为一层，且它们覆盖原始域 $$ \bigcup_{i=1}^n\Lambda_i=\Lambda. $$

要从 $\Lambda$ 中抽取样本，可根据每层的密度 $p_i$，从 $\Lambda_i$ 中抽取 $n_i$ 个样本。

例子

对像素进行超采样时，像素的周围区域会被划分为 $k\times k$ 的网格，并在每个单元内均匀抽取一个样本。这比进行 $k^2$ 次随机采样更优。

在层 $\Lambda_i$ 内，蒙特卡洛估计量为 $$ F_i = \dfrac{1}{n_i}\sum_{j=1}^{n_i}\dfrac{f(X_{i,j})}{p_i(X_{i,j})}, $$ 其中 $X_{i,j}$ 是从密度 $p_i$ 中抽取的第 $j$ 个样本。整体估计量为 $F = \sum_ov_iF_i$，其中 $v_i\in(0, 1]$ 是层 $i$ 的占比。

层 $i$ 内，被积函数的真实值为 $$ \mu_i = E[f(X_{i,j})] = \dfrac{1}{v_i}\int_{\Lambda_i}f(x)\mathrm{d}x, $$ 且层内方差为 $$ \sigma_i^2 = \dfrac{1}{v_i}\int_{\Lambda_i}(f(x) - \mu_i)^2\mathrm{d}x. $$

因此，若层内有 $n_i$ 个样本，分层估计量的方差为 $\sigma_i^2/n_i$。因此可知整体估计量的方差为 $$ \begin{aligned} V[F] &= V\left[\sum v_iF_i\right] \\ &= \sum V[v_iF_i] \\ &= \sum v_i^2V[F_i] \\ &= \sum\dfrac{v_i^2\sigma_i^2}{n_i}. \end{aligned} $$

若令 $n_i = v_in$，则有 $$ V[F_n] = \dfrac{1}{n}\sum v_i\sigma_i^2. $$

注意到，选择一个不分层的样本，相当于先根据由 $v_i$ 定义的离散概率分布选择一个随机分层 $I$，然后在 $\Lambda_I$ 中选择一个随机样本 $X$。从这个角度看，$X$ 是在 $I$ 给定的条件下选择的。因此由条件概率可知 $$ V[F] = \dfrac{1}{n}\left[\sum v_i\sigma_i^2 + \sum v_i(\mu_i-Q)^2\right], $$ 其中 $Q$ 是 $f$ 在整个域 $\Lambda$ 上的均值。这表明分层采样总会减少方差，除非右侧的总和恰好为 $0$，此时 $f$ 在每层的均值都相同。为了使分层采样效果最佳，我们希望最大化右侧的总和，因此最好让各分层的均值尽可能不同。故在对 $f$ 一无所知时应采取紧凑的分层。

分层采样会遇到维度灾难。在 $D$ 维空间中，若每个维度设置 $S$ 个分层，完整分层就需要 $S^D$ 个样本，这很快就会变得难以实现。通常可以对部分维度独立进行分层，再将不同维度的样本随机关联。选择需要分层的维度时，应优先对那些对被积函数值影响相关性最强的维度进行分层。

重要性采样

对于蒙特卡洛估计量 $$ F_n = \dfrac{1}{n}\sum_{i=1}^n\dfrac{f(X_i)}{p(X_i)}, $$ 若样本取自与被积函数 $f(x)$ 形状相似的分布 $p(x)$，其收敛速度会更快。

注解

考虑 $p(x) = cf(x)$。由归一化要求，有 $$ \dfrac{1}{c} = \int f(x)\mathrm{d}x $$ 若能从该分布中采样，估计量总和中的每一项均为 $$ \dfrac{f(X_i)}{p(X_i)} = \dfrac{1}{c} = \int f(x)\mathrm{d}x $$ 此时估计量的方差为零。当然这并不现实，因为若能直接对 $f(x)$ 积分，就无需使用蒙特卡洛方法了。

多重重要性采样

对于形如 $$ \int f_a(x)f_b(x)\mathrm{d}x $$ 的积分，很难找到与它们的乘积形状相似的采样策略。假设有与 $f_a, f_v$ 分布完全匹配的 $p_a, p_b$ 采样分布，对于上式，若使用 $p_a$ 采样，得到估计量 $$ \dfrac{f(X)}{p_a(X)} = \dfrac{f_a(X)f_b(X)}{p_a(X)} = cf_b(X), $$ 此时该估计量的方差与 $f_b$ 的方差成正比，而 $f_b$ 的方差可能很大，反之亦然。

而从每个分布中抽取一些样本并对两个估计量取平均的方案也并不好，因为方差具有可加性，一旦估计量中引入了方差，就无法通过与另一个低方差估计量相加来消除。

多重重要性采样 MIS 的核心思想是，在估计积分时，应从多个采样分布中抽取样本；希望即使不知道哪个分布最合适，至少有一个能较好地匹配被积函数的形状。MIS 接着对每类样本进行加权，消除因被积函数值与采样密度不匹配而导致的大幅方差波动。我们甚至鼓励使用仅针对特殊情况的专用采样程序，因为它们能在特殊情况出现时减少方差，且总体成本较低。

若有两个采样分布 $p_a, p_b$ 以及抽取的单样本 $X \sim p_a, Y \sim p_b$，MIS 蒙特卡洛估计量为 $$ w_a(X)\dfrac{f(X)}{p_a(X)} + w_b(Y)\dfrac{f(Y)}{p_b(Y)}, $$ 其中 $w_a, w_b$ 是权重函数，其选择需满足该估计量的期望值等于 $f(x)$ 的积分。

更一般地，给定 $n$ 个采样分布 $p_i$，从第 $i$ 个分布中抽取 $n_i$ 个样本 $X_{i, j}$，则 MIS 的蒙特卡洛估计量为 $$ F_n = \sum_{i = 1}^n\dfrac{1}{n_i}\sum_{j = 1}^{n_i}w_i(X_{i,j})\dfrac{f(X_{i,j})}{p_i(X_{i,j})}. $$

该估计量无偏对权重函数的要求是，当 $f(x)\neq 0$ 时，$\sum_{i = 1}^nw_i(x) = 1$，且若 $p_i(x) = 0$，有 $w_i(x) = 0$。

若设 $w_i(X) = 1/n$，则对应于对各个估计量取平均的情况，已知这是一种低效的方差缩减方法。更理想的情况是，当某个采样方式与被积函数匹配较好时，其权重函数值应较大；反之则较小，这样就能减少高方差样本的贡献。

在实际应用中，一种优质的权重函数选择是平衡启发式。第 $i$ 中采样方式的平衡启发式权重函数为 $$ w_i(x) = \dfrac{n_ip_i(x)}{\sum_jn_jp_j(x)}. $$

对于上文各取一个样本的例子，上式的估计量为 $$ \dfrac{f(X)}{p_a(X)+p_b(X)} + \dfrac{f(Y)}{p_a(Y)+p_b(Y)}. $$ 此时，若 $p_a$ 在某点以低概率生成了样本而 $p_b$ 在此点高，那么除以 $p_a(X) + p_b(X)$ 会降低该样本的贡献。这实际上是承认 $p_b$ 在该点更有效。只要有一个采样方式在被积函数值较大的区域有合理的采样概率，MIS 就能显著降低方差。

幂启发式通常能进一步降低方差。对于指数 $\beta$，有 $$ w_i(x) = \dfrac{(n_ip_i(x))^\beta}{\sum_j(n_jp_j(x))^\beta} $$ 幂启发式与平衡启发式形式相似，但它会进一步降低相对低概率样本的贡献。$\beta = 2$ 在实际应用中通常表现良好。

即使不从所有分布中采样，多重重要性采样也能应用。这种方法称为单样本模型。可以证明，对于被积函数 $f(x)$，若从一组采样方式中以概率 $q_i$ 选择方式 $p_i$ 并抽取样本 $X$，则单样本估计量 $$ \dfrac{w_i(X)}{q_i}\dfrac{f(X)}{p_i(X)} $$ 能给出积分的无偏估计。对于单样本模型，平衡启发式是最优的。

多重重要性采样的一个缺点是：若某个采样方式与被积函数匹配极佳，多重重要性采样可能会略微增加方差。但在渲染应用中，多重重要性采样几乎总能在可能出现高方差的场景中有效降低方差，因此总体而言非常值得使用。

MIS 补偿

在使用 MIS 时，并不要求所有 PDF 在被积函数非零处都非零，只需其中一个满足即可。MIS 补偿的核心动机是：若所有采样分布都在被积函数值较小的区域分配了部分采样概率，那么这些区域的被积函数往往会被过度采样，而被积函数值较大的区域则会采样不足。

MIS 补偿基于锐化一个或多个（但不是全部）概率分布的思想，如通过调整分布，使其在原本低概率的区域概率为零。

例子

可以定义新的采样分布 $$ p'(x) = \dfrac{\max(0, p(x)-\delta)}{\int\max(0, p(x)-\delta)\mathrm{d}x}, $$ 其中 $\delta$ 为指定常数。

俄罗斯轮盘赌

俄罗斯轮盘赌 RR 跳过对最终结果贡献小的样本的计算，以此提高蒙特卡洛估计效率。在渲染中，估计量通常具有如下形式： $$ \dfrac{f(X)v(X)}{p(X)}, $$ 其中被积函数由一些易于计算的因子 $f(X)$（如与表面如何散射光线相关的因子）和一些计算成本更高的因子 $v(X)$ （如需要追踪光线的二元可见性因子）组成。在这种情况下，计算估计量的大部分成本都集中在 $v$ 上。

若 $f(X) = 0$，显然值得跳过 $v(x)$ 的计算。但若 $f(X)$ 很小但非零时也跳过，则会引入误差，导致系统性低估被积函数值。RR 允许在 $f(X)$ 很小且不必为零时也跳过光线追踪，同时仍能保证平均结果正确。

应用 RR 时，需要选择一个终止概率 $q$。$q$ 几乎可以任意选择，例如可以基于对特定样本被积函数值的估计，随被积函数值减小而增大。

以概率 $q$，不对该样本计算估计量，而以某个常数代替（通常用 $c=0$）
以概率 $1-q$，仍计算估计量，但会乘以因子 $1/(1-q)$，补偿被跳过的样本

于是得到新估计量 $$ F'=\begin{cases} \dfrac{F - qc}{1-q}\quad &\xi>q \\ c&\mathrm{otherwise}. \end{cases} $$

易证其期望与原始估计量的期望相同 $$ E[F']=(1-q)\left(\dfrac{E[F]-qc}{1-q}\right)+qc=E[F]. $$

除非 $c=F$，否则 RR 总会增加方差。不过若能合理选择概率，使得那些可能对最终结果贡献较小的样本被跳过，它确实能提高蒙特卡洛方法的效率。

分裂

如果说 RR 减少样本数量，那么分裂技术则通过增加多维积分中某些维度的样本数量来提高效率。考虑如下形式的积分： $$ \int_A\int_Bf(x,y)\mathrm{d}x\mathrm{d}y. $$ 对于标准 MSI，可以从独立分布中抽取 $n$ 个样本 $X_i\sim p_x, Y_i\sim p_y$，并计算 $$ \dfrac{1}{n}\sum_{i=1}^n\dfrac{f(X_i,Y_i)}{p_x(X_i)p_y(Y_i)}. $$

对于在 $A$ 上抽取的每个样本，分裂技术对于 $B$ 上的积分使用不止一个样本。也即为每个样本 $X_i$ 抽取 $m$ 个样本 $Y_{i,j}$，得到估计量 $$ \dfrac{1}{n}\sum_{i=1}^n\dfrac{1}{m}\sum_{j=1}^m\dfrac{f(X_i,Y_{i,j})}{p_x(X_i)p_y(Y_{i,j})}. $$ 如果能够针对每个 $X_i$ 对 $f(X_i,\cdot)$ 进行求值，那么计算总共 $mn$ 个样本的效率，会高于标准 MSI 抽取 $mn$ 个独立的 $X_i$ 的效率。

例子

渲染中计算像素颜色时，首先对像素区域 $A$ 进行积分，在像素内的每个点 $x$ 处，向场景中发射一条光线，然后通过对半球 $B$ 的积分来计算交点处的反射辐射度，这一过程中会追踪一条或多条光线。借助分裂技术，可以为每个光照积分采用多个样本，通过分摊从相机发射初始光线的成本，来提高效率。