低差异序列

低差异序列 (low-discrepancy sequences) 是一类确定性的点序列，在 $[0,1)^d$ 中分布得比随机点更均匀（星差异度 $O((\log n)^d/n)$ ），用于拟蒙特卡洛 (QMC) 积分和渲染中的采样。常见构造是基于根反演 (radical inverse) 的 van der Corput、Halton、Hammersley，以及基于二进制生成矩阵的 Sobol'。实际渲染中会对它们做随机加扰 (scrambling)（随机数字置换、Owen 加扰），既能估计方差、去掉高维投影中的规则图案，又能提高收敛率。本页以 PBRT 4e 8.5–8.7 节为主。

根反演与 van der Corput

把非负整数 $a$ 写成 $b$ 进制 $a=\sum_i d_i(a)b^{i-1}$ ，再把数字沿小数点镜像： $\Phi_b(a)=0.d_1(a)d_2(a)\cdots=\sum_i d_i(a)b^{-i}.$ $b=2$ 时就是 van der Corput 序列：0, 1/2, 1/4, 3/4, 1/8, 5/8, ……，每次把现有区间对半分， $D_n^*=O(\log n/n)$ ，在一维中是最优阶。以 2 为底时，根反演就是位反转再除以 $2^{32}$ （或 $2^{64}$ ），不需要除法。

van der Corput / Halton 的核心是根反演：把整数的 $b$ 进制数位镜像到小数点后。

flowchart LR
  N["整数 a"] --> Dig["写成 b 进制数位 d_i"]
  Dig --> Flip["数位沿小数点镜像"]
  Flip --> Phi["得到 Φ_b(a) ∈ [0,1)"]
  Phi --> Halton["各维用不同素数底 → Halton 点"]

Halton 与 Hammersley

Halton：第 $k$ 维用第 $k$ 个素数为底， $x_a=(\Phi_2(a),\Phi_3(a),\Phi_5(a),\dots)$ 。任意前缀都分布良好，样本数为各底幂之积（如 $2^33^3=216$ ）时最好。
Hammersley：样本总数 $n$ 已知时把第一维换成 $a/n$ ，差异度略低，但不能增量追加样本。
缺点：每一位要做一次整数除法（慢）；底数大时二维投影出现明显规则图案（PBRT 图 8.28 的 $(\Phi_{29},\Phi_{31})$ ）。

像素到样本下标的反查（PBRT HaltonSampler）：前两维分别乘 $2^j$ 、 $3^k$ 覆盖图像，同一像素每隔 $2^j3^k$ 个样本被访问一次。例如 $2\times3$ 图像中，像素 $(0,0)$ 的样本下标为 0、6、12。自行计算书中表 8.3 前 13 行，全部吻合。求某像素的第一个下标要解同余方程组 $x_r\equiv i \bmod 2^j$ 、 $y_r\equiv i\bmod 3^k$ （Grünschloß 等 2012）。

加扰

Owen 加扰插在确定性低差异点集之后、真正使用样本之前：按数位依赖的随机置换打散规则图案，同时保留低差异结构。

flowchart LR
  Det["确定性点集 Halton/Sobol"] --> Scr["Owen / 数字置换加扰"]
  Scr --> Sample["供积分使用的样本"]
  Scr --> Var["可估计方差；改善高维投影"]

方法	做法	效果
随机数字置换	每个数位 $i$ 一个随机置换 $\pi_i$ ： $\Psi_b(a)=0.\pi_1(d_1)\pi_2(d_2)\cdots$	打散规则图案；PSD 改善但仍有尖峰
Owen 加扰	第 $i$ 位的置换还依赖前面各位 $d_1\cdots d_{i-1}$ （用哈希实现，不存表）	光滑函数的误差降到 $O(n^{-3/2}(\log n)^{(d-1)/2})$ ；PSD 高频接近 1
二进制下的简化	以 2 为底时置换只有两种，可用 XOR 一次处理所有位；FastOwen 利用"乘偶数只影响更高位"并行处理所有位（Laine–Karras 思路，Vegdahl 2021 的哈希）	快，频谱略逊于真正的 Owen

两个细节：尾部的 0 位也必须参与置换，否则加扰只是对原值的重排，不再在 $[0,1)$ 上均匀；每一位必须用不同的置换，否则所有值尾部会是同一个重复数字。

Sobol' 序列

所有维都以 2 为底，第 $k$ 维用一个 $32\times32$ 的二进制生成矩阵 $C_k$ ： $x_a=[2^{-1}\cdots2^{-32}]\,C_k\,[d_1(a)\cdots d_{32}(a)]^T$ （模 2 运算）。矩阵乘向量就是把 $a$ 的为 1 的位对应的列做异或；预先把每列位反转，就省掉最后的位反转。第一维的矩阵是单位阵（即 van der Corput）。PBRT 使用 Joe 与 Kuo（2008）改进二维投影的矩阵。

$(0,2)$ -序列：前两维对所有基 2 基本区间（面积 $2^{-(l_1+l_2)}$ 的轴对齐矩形）都分层：前 16 个点在 $4\times4$ 、 $16\times1$ 、 $1\times16$ 、 $2\times8$ 、 $8\times2$ 每种划分中都恰好每格一个，后续每段长 $2^{l_1+l_2}$ 的点也满足。自行验证：用 van der Corput 与帕斯卡矩阵（模 2）作为前两维生成的 16 个点，满足全部 5 种划分。

三种 Sobol' 采样器与填充

SobolSampler（全局）：直接用 $d$ 维 Sobol' 点，前两维乘 $2^k$ 覆盖图像。全维度低差异，但二维切片（如第 4、5 维）分布差，低采样率下出现棋盘格图案。
PaddedSobolSampler：每次 1D/2D 请求独立地用 Sobol' 前两维，再按像素和维度对样本下标做随机置换（填充 (padding)），保证每对维度分布好，不保证全维度。
ZSobolSampler（pbrt 默认）：利用 $(0,2)$ 性质，让相邻像素取相邻的 2 的幂长度样本段，整幅图的样本互相错开，误差呈蓝噪声。像素按莫顿码排序（见莫顿码与空间填充曲线），像素 $(2,1)$ 的莫顿码为 6，每像素 2 个样本时用下标 12、13；直接用莫顿序会出现结构，所以把莫顿码看成 4 进制数，自高位起逐位用依赖高位与维度的哈希选 24 种置换之一（类似 Owen 加扰，作用在下标上）；样本数是 2 的奇数次幂时最后一位单独用 XOR 处理（Ahmed 与 Wonka 2020）。

对比与取舍（PBRT 8.6.4、8.7.7）

低差异点的一维投影是分层的： $n$ 个 Halton/Sobol' 点在每一维都分层，而 $n$ 个二维抖动点只有 $\sqrt n$ 个保证在单一维度上分层。所以它们变换到细长四边形光源等区域后仍分布良好，而 $4\times4$ 抖动在窄方向上的分层没有用处。
未加扰的 Halton 和 Sobol' 的 PSD 很差，在高频有百倍差异；随机数字置换只略有改善，Owen 加扰才接近均匀。
书中的景深测试（16 spp，均用哈希 Owen 加扰，MSE 以分层采样器为 1）：Halton 1.44（二维投影不好）、PaddedSobol 0.96、Sobol 0.64（但有结构）、ZSobol 0.84（误差为蓝噪声，观感最好）。
对光滑高斯函数，Halton 在 4096 样本时 MSE 比独立采样低近 2000 倍；对几十维的复杂场景只低约 10%（书中 1.09 倍）。
采样维度要按固定顺序消耗，否则分支会让同一个数位时而取第 2 维、时而取第 3 维，破坏分布。采样器必须是确定性的（给定像素和样本下标，结果相同），便于从崩溃的像素直接复现。
与伪随机数生成的关系：PRNG 追求统计独立；低差异序列追求均匀覆盖，是相关的，不能当作独立随机数用于任意算法。
低差异是渐近性质；有些问题（如随机朝向的边缘）用盒子差异度衡量并不合适（Dobkin 等 1996）。

原书问题（参考文献）

PBRT 第 8 章文献表的拼写错误："Purgathofer 1987. A statistical mothod for adaptive stochastic sampling" 应为 method；"Yellot, J. I. 1983" 应为 Yellott。

采样技术总数（2026-10-13 审读新增）：8.2 节说本章 6 个 Sampler 类"共 17 种不同技术"。按书中自己的描述数：IndependentSampler 1 种；StratifiedSampler 抖动/不抖动 2 种；HaltonSampler 不支持 FastOwen（8.6.3），即 None、PermuteDigits、Owen 3 种；三个 Sobol' 采样器各 4 种（8.7.7 "共 12 种"）。合计 $1+2+3+12=18$ ，与 17 不符。属于小的计数不一致。