研究者提出SZ序列矩阵的直接构造新算法

这篇文章先会介绍什么是 SZ 序列，以及为什么我认为 4D shuffled-scrambled SZ 序列应该成为许多人在实现路径追踪器之类东西时默认采用的采样序列。然后我会在“在你的渲染器中使用 SZ 序列”一节指向包含它们的开源代码。

之后，我猜文章剩下的部分可能只对大约十几个人有意思。但真正的贡献也在这里：“新的矩阵构造算法”一节定义了一个比 Ahmed 等人的论文简单得多、也快得多的过程。最后，在“分层 Faure-Niederreiter 序列”一节中，我会把构造扩展到其他素数基。SZ 序列其实就是基 2 的 HFN 序列。

一个基 2 的 ((0,2)) 序列意味着，对于 (2^k) 个点，它们在每一个 2 的幂次大小的 2D 网格上都是分层的。例如，对于前 8 个点，它们在 8x1 网格、2x4 网格、4x2 网格和 1x8 网格上都是分层的。这个交互式图示展示了一个随机化基 2 ((0,2)) 序列的分层情况。

这种分层加上每个网格单元内部的随机性，能为渲染用的 2D 渐进采样序列带来几乎最低的误差。

所以对于渲染器中的二维序列，当前最先进的选择（也是许多渲染器的默认选择）是 shuffled + scrambled 的基 2 ((0,2)) 序列。它要么被称为（shuffled）PMJ02 序列，要么被称为 Shuffled-Scrambled Sobol' ((0,2)) 序列。Shuffling 指的是随机化采样点顺序（也就是它们的索引）的一种特定方式，而 scrambling 指的是在不破坏其渐进分层性质的前提下随机化点的位置。关于这一点，更多信息链接在“前置知识”一节中。

顺便说一句，在 shuffling 和 scrambling 之后，PMJ02 和 Sobol' ((0,2)) 实际上是相同的：得到任何一个特定序列的概率密度都完全一样。这两个序列只是彼此不同的 shuffle 和 scramble。

既然 ((0,2)) 序列对 2D 来说是最好的，那如果你想要更高维度呢？在写路径追踪器时，每次弹射都需要随机数，所以你的采样实际上有上百个维度。据我所知，生产级的离线渲染器通常采用以下两种方法之一：

这样会得到 4D 或 5D 序列，然后再用 shuffling 把这些序列“并置”起来。并置的意思是，要做一个 8D 序列，你只需把两个 4D 序列组合起来。

“Scrambling”是一种在每个网格单元内随机化点的技术，而“shuffling”是一种随机化点的顺序（索引）的技术，两者都能高效完成，同时保持序列的分层性。在使用并置时，shuffling 绝对至关重要，否则两个 4D 序列会高度相关，可能永远无法收敛，即使采样数无限也是如此。

SZ 序列，由 Ahmed 等人在《SZ Sequences: Binary-Based (0, 2^q)-Sequences》中定义，是实现方法 #2 的最佳方式。

Ahmed 等人讨论的是“SZ 序列”，但在这篇文章中，我要讨论的是“规范 SZ 序列”，或者就叫“SZ 序列”，我认为这是最容易构造、也是最显然会被发现的序列。而且我相信，所有 SZ 序列都可以通过对规范 SZ 序列进行 Owen-shuffling 和 Owen-scrambling 得到。

总之，SZ 序列实际上是一个无限维序列，但对于渲染，你很可能只想用前四个维度。其性质如下：

不仅第一对和第二对维度具有理想的分层性，所有 4 个维度合在一起也具有理想的分层性（包括所有低维投影）。不仅如此，它们还具有高维分层性质：(16^k) 个点总是在 (2^k \times 2^k \times 2^k \times 2^k) 上分层。

考虑前 16 个点，它们具有以下分层情况：

随着点数增加，更高维的分层会逐渐被填满。例如，在 64 个点时，所有 3D 投影在 4x4x4 分层中都恰好有一个点。这有点难以可视化，但也许这个会有帮助。

在分层方面，实际上不可能做得比这更好——它比 4D Sobol 好得多。而且因为它是基 2 序列，生成、scrambling 和 shuffling 都可以用快速的二进制运算完成。

我提到过 SZ 序列是无限维的。嗯，它实际上具有这种扩展嵌套性质。它的工作方式是这样的。所有奇偶对（互不相交的二维组）的维度都是一个基 2 ((0,2)) 序列，也就是说，对于任意整数 (k \geq 0)，任意两个维度 (2k, 2k+1) 都是。所有互不相交的 4 维组，即任意 (4k, 4k+1, 4k+2, 4k+3)，都是一个基 4 ((0,4)) 序列。所有互不相交的 16 维组都是一个基 16 ((0,16)) 序列。例如，前 256 个点在每一对维度上都在 16x16 网格上具有 2D 分层性。不只是前 16 个维度，而是其后的 16 个、再其后的 16 个，依此类推。所有互不相交的 256 维组都是一个基 256 ((0,256)) 序列。依此类推，每次把维度数平方，直到无限多个维度。

SZ 序列的更高维形式在路径追踪器中可能没什么用。但它们在离线用途上仍然可能非常有用，比如预计算某些积分。我怀疑它们在其他领域也可能有用（比如金融，或者物理）。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）