原文中陈述了很多具体的例子,而缺乏了一些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
的性质。