Q139：PBRT-V3，Metropolis Light Transport (MLT)（16.4章节）

看这篇文章之前，可以先看看小编之前转载的一篇博文：
Metropolis Light Transport学习与实现

后文内容的结构不是“教程”样式的，而是个人完成初步学习之后对学习结果的简单总结样式。主要是对个人理解的沉淀。

一、概述

前面已经学过BDPT（Bidirectional Path Tracing, 双向路径追踪）。
BDPT的基本思路是：
1，对每个像素点进行多次采样；
2，每个采样点对应：一条CameraSubpth（含t个顶点）；一条LightSubpath（含s个顶点）；连接CameraSubpath和LightSubpath，则可能产生（t*s）条完整路径。
3，计算每一条完整路径的贡献。累加这（t*s）条完整路径的贡献作为当前像素点最终的颜色值。

BDPT中存在一个较为严重的效率问题：每个采样点对应的（t*s）条完整路径中的大部分完整路径的贡献可能是0。
MLT为了改善这个效率问题，采取了两个措施。
措施1：每个采样点只对应一条完整路径。
措施2：基于当前采样点进行Metropolis采样获得下一个采样点。（这个措施能够提高效率的前提是：“当前采样点”的那条完整路径上的贡献相对比较大。另外，有个默认假设：在贡献比较大的完整路径附近找到另一条完整路径的贡献也会比较大。）
（关于“Metropolis 采样”可以参考前面链接的转载博文，也可参考“Q137”中的3.3节）

关于MLT，咱先看一张示意图。

红色路径：是初始路径，即“当前路径”；（先不要管“当前路径”在Film上的采样点（红点）是怎么确定的，后面会有解释）。
（红色路径附近的）黑色路径：是红色路径经过small_step变异采样得到的。
（离红色路径较远的）绿色路径：是红色路径经过large_step变异采样得到的。

关于“small_step”和“large_step”即是“采样间距”。
如图中Film部分所示，对红色点进行小间距的Metropolis采样得到的是红色点附近的黑色点；对红色点进行大间距的Metropolis采样得到的是绿色点。
发现：在Metropolis采样中引入了“大间距”，只要给定一个初始采样点（红点），然后经过若干次“small_step”、“large_step”采样之后，足以完成对整个Film的采样。

虽然，只需要给定一个初始采样点，经过若干次Metropolis采样之后得到的后续采样点是分布在整个Film上的，但是，存在两个问题：
问题1：初始采样点唯一确定的话，风险是不是有点大呢？提供多个初始采样点，然后分别进行Metropolis采样，然后对结果进行加权，风险是不是小得多呢？
问题2：从示意图中可以看出，对初始路径进行Metropolis采样得到的后续路径（不管是黑色路径，还是绿色路径）的长度都是和初始路径的长度相同的。由初始路径的长度确定了后续采样采样路径的长度，明显欠妥。怎么弥补呢？提供多条不同长度的初始路径。

解决这两个问题的方案是：对多条不同长度的初始路径分别进行Metropolis采样，然后对结果进行加权。

考虑到MLT的默认假设：在贡献比较大的完整路径附近找到另一条完整路径的贡献也会比较大。
初始路径多了之后，带来另一个问题：
怎么在所有初始路径中选出贡献比较大的路径呢？

有木有觉得这个问题貌似和咱之前遇到过的某个问题比较相似呢？
是滴，那就是“怎么在所有光源中选出能量比较大的光源呢？”
参考Q137：PBRT-V3，各种采样（Sampling）之间的逻辑
中的“三、采样4，从所有光源中随机选取一个光源；”章节。

所以，同样，咱们将所有初始路径的贡献值添加到“一维阶梯分布”中。然后，对“一维阶梯分布”进行采样即可以比较大的概率选出贡献比较大的初始路径啦。

OK， 知道怎么选择初始路径之后，就可通过for循环反复对该“一维阶梯分布”进行采样，
每次得到一个初始路径，然后通过Metropolis采样产生新的路径（这里也有个循环，如示意图中红点附近有多个黑点，即进行了多次Metropolis采样），然后将新路径上的贡献累加到Film上对应采样点的颜色值上。
然后对“一维阶梯分布”进行下一次采样得到新的初始路径。循环……

一直在说“Metropolis采样”，那么“Metropolis采样”到底是怎么实现的呢？？？

二、Metropolis采样

从“宏观”（其实，也没多“宏观”）上来看，“Metropolis采样”作用的是路径。
正如MLT的默认假设：在贡献比较大的完整路径附近找到另一条完整路径的贡献也会比较大。我们要做的就是对“贡献比较大的完整路径”进行“Metropolis采样”，以便得到“另一条贡献比较大的完整路径”。
另外，如示意图所示，对“红色路径”进行“Metropolis采样”得到“黑色路径”。（当然，给“Metropolis采样”加入large_step后，对“红色路径”进行“Metropolis采样”还能得到“绿色路径”）

从“微观”上来看，“Metropolis采样”具体具体具体作用的路径上需要采样的点。
如示意图所示，对“红色路径”进行“Metropolis采样”得到“黑色路径”的过程是：对“红色路径”上所有需要采样的点都进行“Metropolis采样”得到新的采样点，新的采样点对应就是“黑色路径”。
“需要采样的点”，貌似不太好理解，听起来也怪怪的。简化一下，只考虑路径上的顶点吧。对“红色路径”进行“Metropolis采样”的过程可以简单理解为：
对“红色路径”对应的CameraSubpath、LightSubpath的顶点分别进行“Metropolis采样”。

“Metropolis采样”在PBRT-V3中对应的类是MLTSampler。

2.1 MLTSampler::rng

RNG是PBVT-V3的伪随机数发生器。参考：
Q138：PBRT-V3，伪随机数发生器（pseudo-random number generator，RNG）（A.1.2章节）
从参考博文中，可以知道任意RNG对象对应的具体的伪随机数数列都是由一个被称为“种子”的sequenceIndex唯一确定。
每一个MLTSampler对象对应唯一的一个RNG对象，即对应一个唯一的独一无二的自己的伪随机数数列。所以，在实例化一个MLTSampler对象时需要设置一个sequenceIndex，以便实例化RNG对象。这样一来，sequenceIndex相当于同时是MLTSampler对象的ID和MLTSampler对象对应的RNG对象的ID。即，sequenceIndex唯一确定一个MLTSampler对象及其内部的RNG对象。

这里之所以反复说到“sequenceIndex唯一确定MLTSampler对象”，是因为在MLTIntegrator的具体实现中确实需要通过sequenceIndex保证前后MLTSampler对象是同一个对象。
比如，在计算初始路径的贡献时会实例化一个MLTSampler对象，此时没有必要将整个MLTSampler对象保存下来，只要知道其对应的sequenceIndex即可。前面已经知道，为了较大概率地选出所有初始路径中贡献较大的，我们会先将所有的初始路径的贡献添加到一个“一维阶梯分布”中，然后对该“一维阶梯分布”进行采样来获取初始路径。那么问题来了，怎么保证采样获取的初始路径和之前初始化时的初始路径对应到同一个MLTSampler对象呢？这个时候就需要用到“sequenceIndex唯一确定MLTSampler对象”。

2.2 MLTSampler::streamCount、streamIndex、sampleIndex、X

咱从X着眼来进行说明吧。

    std::vector<PrimarySample> X;

X向量容器中存放的是一条完整的采样路径上用到的所有“随机数”。

好像还是有点抽象，提前看看MLTIntegrator的相关代码。
看看产生CameraSubpath时需要用到哪些随机数。

现在可以看到，前面之所以说“将采样点理解为路径的顶点”是简化地理解，是因为顶点和采样点（随机数）并不存在一对一或者一对多的关系（或者说是，没有直接关系。）

另外，X中每个元素的数据类型是PrimarySample。

    struct PrimarySample {
        Float value = 0;
        // PrimarySample Public Methods
        void Backup() {
            valueBackup = value;
            modifyBackup = lastModificationIteration;
        }
        void Restore() {
            value = valueBackup;
            lastModificationIteration = modifyBackup;
        }

        // PrimarySample Public Data
        int64_t lastModificationIteration = 0;
        Float valueBackup = 0;
        int64_t modifyBackup = 0;
    };

X的每个元素不是对应一个随机数就好？为什么还要定义为为PrimarySample数据类型呢？

因为……，考虑到如下情况：

也就是，当GenerateCameraSubpath()返回的值不等于t，则直接return 0。这种情况下，一方面原本后续存在的GenerateLightSubpath()和ConnectBDPT()都不用执行了；另一方面，“return 0”意味着这次“变异”失败，也就是，这次“变异”无效，Camera Stream相关的通过Metropolis采样已经更新的随机数（即，X中对应的元素）需要被还原。

另外，就算新采样得到的路径一切正常，而且贡献大于零，但是，根据Metropolis采样的算法，这次采样是有概率被拒绝的。当这次采样被拒绝，所有已经更新的随机数都需要被还原。

这样一来，MLTSampler在根据X中某元素的“当前值”来“变异”产生“新值”前，有必要将“当前值”进行备份。如果“变异”失败，需要根据备份值将该元素的值还原。

至于PrimarySample中的lastModificationIteration成员。

在正常采样得到新路径而且这次采样被接受了（即，最终有效）的情况下：
在产生新路径的过程中，很多使用随机数的地方是用if()条件包住的。这就是说，这些随机数对应的X中的元素在一切正常的情况下，有时候会被更新，有时候不会被更新。
所以，X的元素中需要lastModificationIteration来标记上一次被更新的时候（迭代编号）。
为什么要标记？为了在下一次被更新时，一起算总账（把那些年错过的“更新”全部补回来）。
假设“变异”函数是正态分布，即。若在下一次更新时，发现已经错过（n-1)次“更新”，算上当前这一次总共是(n)次“更新”，所以这次的“变异”函数是：

2.3 MLTSampler::currentIteration

currentIteration：当前这次迭代（变异）的编号。

2.4 MLTSampler::largeStepProbability、largeStep、sigma

largeStepProbability：大步长变异的概率。如最前的示意图所示，从红色路径变异到绿色路径的概率。

largeStep：当前这次变异是否为大步长变异。这个布尔值在当前这次变异开始时就已设置好，以便确定路径中所有点的变异方式（largeStep or smallStep）。设置largeStep的相关代码：

void MLTSampler::StartIteration() {
    currentIteration++;
    largeStep = rng.UniformFloat() < largeStepProbability;
}

另外，largeStep=true（即大步长变异），通过“随机采样”产生新路径；largeStep=false（即小步长变异），通过“正态分布采样”产生新路径。

sigma：前面也已经提到，MLT中小步长变异的变异函数是正态分布函数。如最前的示意图所示，由红色路径变异得到附近一条黑色路径的方式和由一条黑色路径变异得到附近另一条黑色路径的方式都是对以当前路径为中心的正态分布的采样。正态分布的表示：。这里的sigma就是对应正态分布表达式中的σ。

2.5 MLTSampler::lastLargeStepIteration

lastLargeStepIteration：上一次发生大步长变异的迭代（变异）编号。如最前的示意图所示，当从红色路径变异到绿色路径时，就得用lastLargeStepIteration将这次变异编号保存起来。保存起来有什么用呢？
“2.2”中不是提到“lastModificationIteration……算总账”么？但是，你这个绿色路径附近的总账只能在绿色路径附近算，不能算到红色路径附近去啊。其实“算总账”是累积的正态分布采样，但是大步长变异（红色路径变异到绿色路径）的过程中发生了随机采样。发生了“随机采样”，就相当于另起炉灶重新开始啦。
但是，发生大步长变异时，X[]中的某些元素可能不会被用到，所以对应的数据没有被重新初始化。等到后续（在这个“炉灶”中第一次）用到该元素时，需要重新初始化。相关代码：

    // Reset $\VEC{X}_i$ if a large step took place in the meantime
    if (Xi.lastModificationIteration < lastLargeStepIteration) {
        Xi.value = rng.UniformFloat();
        Xi.lastModificationIteration = lastLargeStepIteration;
    }

“ (Xi.lastModificationIteration < lastLargeStepIteration)”即表示“上次更新这个元素Xi的值发生在上次大步长之前（也就是在上一个“炉灶”）“

2.6 MLTSampler的构造函数

2.6 MLTSampler::StartIteration()、StartStream()

void MLTSampler::StartIteration() {
    currentIteration++;
    largeStep = rng.UniformFloat() < largeStepProbability;
}

这个函数是在迭代开始时调用。注意是“迭代”开始时，也就是说在发生迭代前计算初始路径的贡献时是不调用这个函数的。初始状态，currentIteration=0、largeStep=true。在“2.4”中，已经知道largeStep=true（即大步长变异）时，通过“随机采样”产生新路径。所以，不要再问“初始路径是怎么得到的？”相关代码：

    if (largeStep) {
        Xi.value = rng.UniformFloat();
    }

---

void MLTSampler::StartStream(int index) {
    CHECK_LT(index, streamCount);
    streamIndex = index;
    sampleIndex = 0;
}

index=0表示CameraStream；
index=1表示LightStream；
index=2表示ConnectionStream；

这里设置streamIndex，是为了在后续GetNextIndex()能够以此得到X容器中stream对应的元素的编号。

2.7 MLTSampler::Get1D()、Get2D()

Get1D()、Get2D()分别表示从MLTSampler对象中获取一个采样点、两个采样点。

// MLTSampler Method Definitions
Float MLTSampler::Get1D() {
    ProfilePhase _(Prof::GetSample);
    int index = GetNextIndex();
    EnsureReady(index);
    return X[index].value;
}

Point2f MLTSampler::Get2D() { return {Get1D(), Get1D()}; }

先回头看看“2.2”中那张关于X向量容器的图，然后咱看看通过Get1D()是怎么获取一个采样点的。

假设通过GetNextIndex()计算得到的X向量容器中元素的编号是“9”。EnsureReady(9)做的事情是：若X容器的大小比9还小，就增加X容器的大小，然后初始化X[9]；若X[9]已经存在，对X[9]的值进行变异得到新的采样点。

2.8 MLTSampler::Accept()、Reject()

void MLTSampler::Accept() {
    if (largeStep) lastLargeStepIteration = currentIteration;
}

---

void MLTSampler::Reject() {
    for (auto &Xi : X)
        if (Xi.lastModificationIteration == currentIteration) Xi.Restore();
    --currentIteration;
}

当此次迭代（变异）被拒绝，则需要将此次迭代过程中所有更新过的X的元素的数据全部还原。
另外，迭代编号减一（也就是被拒绝的迭代是不计数的）。

三、MLTIntegrator

在“一、概述”中已经大概讲述了MLTIntegrator的算法。

对多条不同长度的初始路径分别进行Metropolis采样，然后对结果进行加权。

将所有初始路径的贡献值添加到“一维阶梯分布”中。然后，对“一维阶梯分布”进行采样即可以比较大的概率选出贡献比较大的初始路径啦。

整理一下，所有步骤如下：

步骤1，计算多条不同长度的初始路径的贡献；
步骤2，将所有初始路径的贡献值添加到“一维阶梯分布”中；
步骤3，对“一维阶梯分布”进行采样，以比较大的概率选出贡献比较大的初始路径；
步骤4，对选出的初始路径进行Metropolis采样，计算贡献，累加贡献；
步骤5，循环“步骤4”，对选出的初始路径进行多次Metropolis采样；
步骤6，循环“步骤3”~“步骤5”，对“一维阶梯分布”进行采样，以比较大的概率选出贡献比较大的多条不同长度的初始路径。

3.1 MLTIntegrator::Render(）

MLTIntegrator::Render(）截图如下：
（截图解释中留了几个坑，标记为“坑X”，后文来填）

接下来是填坑时间。

“坑1”：给定MLTSampler对象和路径长度，怎么求路径的贡献？

对应MLTIntegrator::L()。

在“一、概述”中说明了MLT提高效率的措施中有：
措施1：每个采样点只对应一条完整路径。
这里的“每个采样点”指的是“一次变异”。也就是“一次变异”只得到一条完整路径。
由于depth（假设是5）是确定，如果MLT不采取此项优化措施，可能对应如下几种连接策略：

既然，MLT只需要一条完整路径，那么就在这nStrategies（此例中为7）中随机选一条吧。

确定了连接策略之后，可以开始产生“确定长度的”CameraSubpath和“确定长度”的LightSubpath，然后按照“确定的”连接策略进行连接。

坑2：贡献的大小是什么？

我们知道“贡献”是个RGB颜色值，而“大小”是个标量值。
那么用什么来表示“贡献的大小”呢？

一般是用“贡献”的这个RGB颜色值对应的“亮度”（Illumination）来表示“贡献的大小”。
亮度的计算：

    Float RGBSpectrum::y() const { const Float YWeight[3] = {0.212671f, 0.715160f, 0.072169f};
        return YWeight[0] * c[0] + YWeight[1] * c[1] + YWeight[2] * c[2];
    }

坑3：常数b=bootstrap.funcInt * (maxDepth + 1)是什么鬼？

按照书上说，这个b是Film的平均亮度。（乘以（maxDepth+1)，是考虑单个像素点的实际效果是（maxDepth+1)条完整路径的贡献）。

最后为什么要乘以b（Film的平均亮度）呢？
因为在在给Film添加采样路径的贡献时，都除以了其贡献的亮度。

四、其他

就小编个人而言，学习MLT这一部分的内容着实费劲。
码了这么多字，其实对MLT的理解还只是个大概。
先记录这些“大概”，免得连这些不多的“大概”都不记得了。

路漫漫其修远兮，……