Robert Bridson的O（n）算法的两个多线程增强。
罗伯特·布里德森（Robert Bridson）的O（n）算法是一种相当简单且快速的生成泊松磁盘采样模式的算法。 在此基础上，我将讨论两种使用并行性来加快速度的方法。 两种方法都易于实现且速度很快。 至少在目视检查中，结果是无法区分的，但是甚至更快。
但是首先，我强烈建议您阅读Bridson的算法。 这也是原始算法的动画效果：
所有白点和红点都是到目前为止生成的样本。 但是，红点是活动列表的一部分。 黄色边框是指定的范围。
查看上面算法的动画预览，可以想到使用多个线程来填充单独的区域。 而这正是第一种方法的作用。
基本上，尽可能平均地划分指定区域，并为每个实例实例化算法的单独实例，然后让它们运行。 这些单独的实例此后简称为内核。 这些内核中的每一个都可以被视为工人。
每个内核都实现为不会填充超出边距的点。 这消除了争用，因为不需要对可能在另一个内核中的点进行相交测试。
一旦所有内核完成运行，边界就会相交，在这里可以容纳更多点。 到目前为止是这样的：
接下来，将相邻的内核合并为新内核。 此新内核具有适合合并大小的哈希网格。 该哈希网格预先填充了由合并的内核生成的样本。 然后将靠近合并边界的样本重新添加到活动列表中。 我们得到这个：
然后，再次让内核运行至完成并再次合并，直到我们只剩下一个内核。 现在完成了：
再次注意，在每个步骤中，内核都是并行执行的。 因此，如果工人人数是4 x 4，最初将有16名工人参加工作，然后是8名，然后是4名，依此类推，直到一个。 最后一个内核在主线程上依次完成。
与串行（原始）版本的比较：
通过预先生成指定数量的包含点的唯一图块，可以进一步提高速度。 这些图块会加盖到指定的范围内。 这样就消除了最初的铲斗填充。 可以将其视为重复使用存储桶。
标记图块之后，我们就让该过程像“存储桶方法”一样运行，合并-一次又一次地生成。
Tiled方法的性能特征很有趣。 它们根据图块的大小和唯一图块的数量而变化。 就独特瓷砖的数量而言，第四似乎是最好的。
当图块大小较小时，我们将花费大量时间来合并它们。 随着图块大小变大，由于算法需要填充更多区域，因此花在创建图块上的时间更多。 当要填充的区域是256 x 256以及512 x 512时，最好使用32的瓦片大小。
现在与其他两种方法的性能比较，平铺方法的速度是Bucket方法的四倍：
平铺方法似乎足以生成许多泊松磁盘采样点。 无论是大面积还是小面积，最小距离都较小。 在外观检查中，平铺方法看起来确实很棒。 如果我们密切注意，实际上可以发现一些重复。 通过对图块应用随机旋转和/或镜像变换，可以在很大程度上解决此问题。 这将使重复变得不那么明显。
