python - Python 中的快速泊松圆盘采样 [Robert Bridson]

Question

首先，我在 2D 平面中实现了普通的、缓慢的 Poisson Disk Sampling 算法，它工作得很好。这个慢速版本会计算所有点之间的距离，并检查您希望放置的点与所有其他点之间的距离是否至少为 R。

Robert Bridson 的快速版本，可在此处获取:https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf ，建议将您的 2D 平面离散化为长度 = R/sqrt(2) 的二次元胞，因为这样每个元胞最多可以包含一个有效点，并且您需要检查距离计算的元胞数量变为常数。它还有一个优点是您知道可以精确放置在给定的有限二维平面和距离 R 上的最大点数。我希望我理解正确...

但是，我在 Python 中实现的快速泊松圆盘采样算法不起作用，我也不知道为什么。它比较慢，可能是因为我还没有对它进行矢量化，但是当我没有完全检查每一点时它也会给出不正确的结果。即，生成无效点。我将从提出一些在 Robert Brindson 的论文中没有回答的问题开始。

Q1:假设你想在一个单元格中放置一个点 X，并且每个单元格都是一个长度为 R/sqrt(2) 的正方形，你需要检查哪些单元格是否被点 Y 占据，以确定是否点 X 至少与所有 Y 相距 R？

只是在纸上画圆圈和网格我想到了这个:

   [ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][X][ ][ ]
[ ][ ][ ][ ][ ]
   [ ][ ][ ]

谁能确认这是正确/不正确的？

问题 2:您将如何计算点 X 应该占据哪个单元格？论文中没有提到这一点，但在点 X 靠近单元格边界的情况下似乎很棘手。我是否应该在细胞周围制作一定厚度的“皮肤”，以便仅考虑不在其细胞皮肤内的点？此外，如果您改为生成索引，对于如上所示的从点 X 开始的单元格，然后随机化单元格内新点 Y 的位置，它仍然是泊松圆盘采样算法吗？

Answer 1

A1:是的，如果单元格大小等于 r/√2，检查这些单元格就足够了。

仅通过查看 x 坐标，可以排除另外三个细胞，同样可以排除三个细胞，因为它们的 y 坐标，但这值得努力吗？直到您实现了算法并可以测试性能。

A2: 不，我认为这不会很棘手。 (x, y) 处的点占据单元格 (⌊√2 x/r⌋, ⌊√2 y/r⌋)。如果新点位于已占用的单元格中，或者如果 21 个单元格中的任何一个包含太近的点，则新点将被拒绝。