辅助知识点——低差异序列

https://zhuanlan.zhihu.com/p/20197323?columnSlug=graphics
高效的生成在高纬空间分布均匀的随机数在计算机程序中非常常见的组成部分。对于一切需要采样的算法来说，分布均匀的随机数就意味着更加优秀的样本分布。光线传递的模拟（渲染）基于蒙特卡洛积分（monte carlo integration）,这个过程采样无处不在，所以好的样本分布直接影响积分过程的收敛速度。

与常见的伪随机数对比，低差异序列（low discrepency sequence）非常的广泛的被用在图形，甚至于金融领域。它们除了在高纬空间中的分布更加均匀以外还有许多其他的性质更利于渲染程序的执行。

上图中，左右两边分别用32个sobol序列和伪随机书作为样本分布渲染，可以看出左边的噪点比右边少许多。

下面介绍常见的低差异序列的定义。

什么是Discrepancy 差异
首先说说这里均匀分布里的“均匀”指的是什么。一个直观的理解可以看下面的图片，左边为伪随机数组成的二维点集，右边则是由低差异序列点集的对整个空间的覆盖更加完整。

更加严谨的定义则要引入Discrepancy（Definition of Discrepancy）的概念：

对于一个在
空间中的点集，任意选取一个空间中的区域B，