Robert Bridson的O(n)算法的两个多线程增强。
罗伯特·布里德森(Robert Bridson)的O(n)算法是一种相当简单且快速的生成泊松磁盘采样模式的算法。 在此基础上,我将讨论两种使用并行性来加快速度的方法。 两种方法都易于实现且速度很快。 至少在目视检查中,结果是无法区分的,但是甚至更快。
- 反思我对IF的深入研究
- 开始雇用Unity游戏开发人员-综合指南
- Binary Moon Star Raid独家开发人员专访
- CalQ的故事:在没有UA预算的情况下我如何得到20万名下属
- 如何在Unity中为真菌讲故事创建自定义对话框
但是首先,我强烈建议您阅读Bridson的算法。 这也是原始算法的动画效果:

所有白点和红点都是到目前为止生成的样本。 但是,红点是活动列表的一部分。 黄色边框是指定的范围。
查看上面算法的动画预览,可以想到使用多个线程来填充单独的区域。 而这正是第一种方法的作用。
基本上,尽可能平均地划分指定区域,并为每个实例实例化算法的单独实例,然后让它们运行。 这些单独的实例此后简称为内核。 这些内核中的每一个都可以被视为工人。
每个内核都实现为不会填充超出边距的点。 这消除了争用,因为不需要对可能在另一个内核中的点进行相交测试。
一旦所有内核完成运行,边界就会相交,在这里可以容纳更多点。 到目前为止是这样的:

接下来,将相邻的内核合并为新内核。 此新内核具有适合合并大小的哈希网格。 该哈希网格预先填充了由合并的内核生成的样本。 然后将靠近合并边界的样本重新添加到活动列表中。 我们得到这个:

然后,再次让内核运行至完成并再次合并,直到我们只剩下一个内核。 现在完成了:

再次注意,在每个步骤中,内核都是并行执行的。 因此,如果工人人数是4 x 4,最初将有16名工人参加工作,然后是8名,然后是4名,依此类推,直到一个。 最后一个内核在主线程上依次完成。
与串行(原始)版本的比较:

通过预先生成指定数量的包含点的唯一图块,可以进一步提高速度。 这些图块会加盖到指定的范围内。 这样就消除了最初的铲斗填充。 可以将其视为重复使用存储桶。


标记图块之后,我们就让该过程像“存储桶方法”一样运行,合并-一次又一次地生成。
Tiled方法的性能特征很有趣。 它们根据图块的大小和唯一图块的数量而变化。 就独特瓷砖的数量而言,第四似乎是最好的。

当图块大小较小时,我们将花费大量时间来合并它们。 随着图块大小变大,由于算法需要填充更多区域,因此花在创建图块上的时间更多。 当要填充的区域是256 x 256以及512 x 512时,最好使用32的瓦片大小。

现在与其他两种方法的性能比较,平铺方法的速度是Bucket方法的四倍:

平铺方法似乎足以生成许多泊松磁盘采样点。 无论是大面积还是小面积,最小距离都较小。 在外观检查中,平铺方法看起来确实很棒。 如果我们密切注意,实际上可以发现一些重复。 通过对图块应用随机旋转和/或镜像变换,可以在很大程度上解决此问题。 这将使重复变得不那么明显。