采样

      首先我们来欣赏一下梵高同学的名画《星空》的一部分

      关于光是怎样在人的视网膜上成像涉及到物理和生物的一些知识，这里我们不作讨论。但是其中有很重要的一个过程就是人眼把连续的光信号变成了离散的信号，并将其反馈给大脑。这个过程就称为采样。

采样在计算机图形学中扮演着非常重要的角色。即使是简单的调整图像大小也要用到采样。因此如何进行采样就显得十分重要，一方面要保证采样点要均匀分布，另一方面要避免采样点重复或产生规律（否则会产生混叠）。人的视网膜在采样上做的非常出色，看下面这张视网膜在显微镜下的图，图中的较大的视锥细胞探测颜色，较小的视杆细胞对弱光较为敏感。

      这些细胞稠密且均匀的分布在视网膜上，而且它们之间的相对位置是无规律的。我们称之为泊松圆盘分布，因为任意细胞间的最小距离总是一定的。

      但是构造一个泊松圆盘分布并不容易，我们先来看看米切尔最佳候选算法(Mitchell’s best-candidate algorithm)，它是泊松圆盘分布的一个近似，方便起见，我们就称之为best-candidate算法吧~

      从图上来看best-candidate算法形成的采样点还算令人满意，至少随机性是不错。不过缺点也很明显，有的区域采样点非常多（过采样），而有的区域则较稀疏（欠采样）。当然即使这样也是相当不错的，因为这个算法易于实现。

      我们来看看这个算法的原理

      best-candidate算法，顾名思义，是从一堆候选采样点中选取一个最佳采样点。首先，生成固定数量（上图中为10）的候选采样点，用灰色表示，每一个候选采样点是在采样区域随机生成的。然后寻找最佳候选采样点，用红色表示。什么是最佳候选采样点呢？就是距离已固定的采样点（黑色表示）最远的那个点。这么说大家可能还是不太明白，其实就是把已固定的采样点整体看成一个集合，候选采样点与这个集合中每一个元素都有一个距离，我们把最小的那个距离定义为该候选采样点到已固定采样点的距离。

      从图上来说就是对每一个灰点（候选采样点），寻找离它最近的黑点（已固定的采样点），在它们之间划一条线，线的长度就是它们的距离。红点（最佳候选采样点）就是在当前所有灰点中这个距离最大的那个点。当这一轮结束这后，把红点标为黑点（把最佳候选采样点作为已固定的采样点），然后进行下一轮的选取，如此循环下去。

下面是实现代码

      其中numCandidates表示一次生成的候选采样点个数，numCandidates越小，算法运行速度越快。相反，numCandidates越大，算法运行速度越慢，但是采样质量越高。

      distance函数也非常简单，如下所示

      findClosest函数返回距离当前灰点最近的黑点（距离当前候选采样点最近的已固定采样点）。我们可以用暴力搜索来实现，即遍历所有黑点，计算当前灰点与它们之间的距离，找出最小值。当然也可以采用一些快速的搜索算法，如四叉树搜索算法。暴力搜索简单，但是时间复杂度太高。而四叉树搜索算法需要一个前期建立四叉树的过程。

uniform random

---

      下面我们来看看另一种随机采样算法uniform random。uniform random算法是最简单的一种随机采样的实现，它的效果如下

      uniform random算法虽然简单，但是它的结果实在有点惨不忍睹，采样点重叠，过采样，欠采样等等。

      那么除了通过采样点的分布规律来鉴别采样质量，还有没有其他方法呢？这里我们可以通过取距离采样点最近的颜色并对采样点所在色块进行着色的方法，也可以使用沃罗诺伊图

      先来看看在uniform random算法生成的6667个采样点下的《星空》是什么样的

      效果果然很一般，采样点分布不均导致色块大小不一、细节丢失严重等一系列问题。左下角还有一些粉红色的色块，而原作中是没有这种颜色的。

      再来看看best-candidate算法采样后的《星空》

      尽管仍有一些细节丢失等问题，但明显要比上一幅效果要好。

      我们也可以用沃罗诺伊图更直观的衡量采样质量，通过对每个色块的大小对其进行着色，色块越大颜色越深，色块越小颜色越浅。最佳的采样模式应该有几乎统一的着色，同时又保证不规律的采样点分布。下图是uniform random的效果

      色块之间的差别非常大，原因不再赘述。

       best-candidate的效果如下：

      颜色明显均匀多了~

      那么有没有什么算法能比best-candidate算法效果更好呢？当然有了，这就是我们下面要讨论的Bridson泊松圆盘采样算法，这次可不是近似了哦~先来看看Poisson-disc算法的效果

      看起来是不是非常均匀和舒服？它与前面两个算法最大不同在于，它是充分利用现有采样点逐步生成新的采样点，而不是在整个采样区域随机生成新的采样点。同时也注意到，任意两个采样点的最小距离都是一定，没有特别靠近的两个点（正如泊松圆盘分布所定义的那样），这些都是由算法的执行过程严格保证的。来看看算法的执行过程

      我们用红点表示活跃采样点，在每一轮的循环中从所有活跃采样点中随机选取一个点，然后以该点为圆心，分别以r和2r为半径作两个同心圆，其中r为两个采样点之间所允许的最小间距。然后我们在r与2r之间的环形区域随机生成一些候选采样点（白点），接下来的步骤就是从这些候选采样点中筛选出一个满足条件的采样点了。

      注意到图中的灰色区域，它们是由已固定的采样点（包括红点和黑点）为圆心，r为半径作圆所形成的区域，我们可以称之为“禁区”。如果候选采样点落在灰色区域，那么表明它一定与某个已固定的采样点的距离不足r，这是不允许的，因此可以将这样的候选采样点排除掉。当我们找到一个没有落在灰色区域的候选采样点之后，便把它标为红点作为一个新的活跃采样点，原来的活跃采样点不变。如果生成的所有候选采样点都落在灰色区域内，那么就认为在r到2r的区域内不存在满足最小距离为r的点（当然实际情况不一定如此），然后把作为圆心的活跃采样点标为即不活跃采样点（从红点变成黑点）。当所有点都变成黑点之后，算法结束。

下图是Poisson-disc算法的沃罗诺伊图

颜色更加匀称了是不是？ 再看看Poisson-disc算法下的星空

美不胜收！（来源，小象学院）