Scrambled后的序列依然具有radical inversion的性质

原文中陈述了很多具体的例子，而缺乏了一些Halton序列本身的说明，使用场景、以及与其他序列使用对比的差异，故在此处进行补充

Halton和Hammersley可以生成在无穷维度上分布均匀的点集，它们都基于Van der Corput序列 Halton序列的定义很简单：

Xi:=(Φb1(i),...,Φbn(i))Xi:=(Φb1(i),...,Φbn(i))

既是每一个维度都是一个基于不同底数bnbn的Van der Corput序列，其中b1...bnb1...bn互为质数（例如第11到第nn个质数） Hammersley点集的定义和Halton非常相似 以下是Hammersley点集的定义

Xi:=(iN,Φb1(i),...,Φbn−1(i))Xi:=(iN,Φb1(i),...,Φbn−1(i))

唯一不同的就是把第一个维度变成iNiN，其中ii为样本点的索引，NN为样本点集中点的个数。根据定义，Hammersley点集只能生成固定数目个样本，而Halton序列则可以生成无穷个样本（当然在计算机里我们只有有限的bit去表示有限个样本点）

上面左边的图为第1-100个Halton序列中的二维的样本点，(Φ2(i),Φ3(i))99i=0(Φ2(i),Φ3(i))i=099，右边则为数量为100的二维Hammersley样本点集，(i100,Φ2(i))99i=0(i100,Φ2(i))i=099。可以看出来它们的分布都远比一般的伪随机数更加均匀。Hammersley的差异性比Halton更稍低一些，但是代价是必须预先知道点的数量，并且一旦固定无法更改虚幻引擎4中对环境贴图的Filter采样就是用的点集大小固定为1024的Hammersley点集。Halton虽然差异性稍高，但可以不受限制的生成无穷多个点，更适合于没有固定样本个数的应用，例如任何progressive或者adaptive的过程。 基于radical inversion的序列还都具有Stratified样本的性质。因为每一个维度都是一个radical inversion，所以每一维度都具有所有之前提到的radical inversion的性质。其中之一就是点集个数到达bmbm个点时对[0,1)[0,1)会形成uniform的划分。下图是第1-12个Halton序列的二维点集，可以看出点0-7在X轴的投影和0-8在Y轴的投影都是均匀覆盖。这也意味着在样本数量等于每个维度底数的公倍数的适合，样本会自然在每个维度上底数的倍数的strata中自然的形成stratified采样。例如下图中的第0-5个点，刚好在图中落在2x3的strata中。

`Halton`序列的一个缺点是，在用一些比较大的质数作为底数时，序列的分布在点的数量不那么多的时候并不会均匀的分布，只有当点的数量接近底数的幂的时候分布才会逐渐均匀。例如下图中以29和31为底的序列，一开始的点会分别是

129,229,329...129,229,329...所以造成了点都集中落在了一条直线上面。解决这个问题的方法也很简单，Scrambling。Scrambling的方法有许多种，例如最简单的XOR Scrambling适用于以2为底数的序列。对于Halton来说，一个比较常用的方法是Faure Scrambling。

Φb(i)=∑l=0M−1σb(al(i))b−l−1Φb(i)=∑l=0M−1σb(al(i))b−l−1

如上面的公式所写，Faure Scrambling的做法就是在做radical inverse的时候不直接将数字镜像到小数点右边，而在镜像前先把每个数字通过一个permutationσbσb转换成另一个数字。不同的底数bb有不同的permutationσσ。例如σ4=[0,2,1,3]σ4=[0,2,1,3]。至于σbσb如何具体计算这里不再展开，下一篇专栏在讲实现时会给出参考链接。这里值得一提的时Scrambling完全不会影响radical inversion序列分布的随机性，因为radical inversion会自然的将空间均等划分成底数bb的整数次幂个部分，scrambling本质上就是在交换这些均等划分的部分，所以Scrambled后的序列依然具有radical inversion的性质。