Python中的快速Poisson圆盘采样[Robert Bridson]

2024-06-01 00:00:43 发布

您现在位置:Python中文网/ 问答频道 /正文

首先,我在二维平面上实现了普通的、慢的、泊松圆盘采样的算法,它工作得很好。这个慢版本计算所有点之间的距离,并检查要放置的点与所有其他点的距离是否至少为R。在

Robert Bridson的fast版本在这里提供:https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf,建议将二维平面离散成长度为R/sqrt(2)的二次型单元,因为这样每个单元最多只能包含一个有效点,并且需要检查距离计算的单元数也变为常量。它还有一个优点,就是你知道在给定的有限二维平面上可以精确放置的最大点数和距离R。。。在

但是,我在Python中实现的快速Poisson磁盘采样算法不起作用,我也不知道为什么。它比较慢,可能是因为我还没有对它进行矢量化,但是当我没有绝对检查每个点时,它也会给出错误的结果。也就是说,生成无效点。我先问一些罗伯特·布林森论文中没有回答的问题。在

Q1:假设您希望在一个单元格中放置一个点X,并且每个单元格都是一个长度为R/sqrt(2)的正方形,那么您需要检查哪些单元格是否被点Y占据,以确定X点是否至少距离所有Y点R?在

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

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

有人能确认这是正确的/不正确的吗?在

问题2:你将如何计算一个点X应该占据的单元格?本文中没有提到这一点,但在X点靠近单元边界的情况下,这似乎很棘手。我是不是应该在细胞周围做一个一定厚度的“皮肤”,这样一个点只有在它细胞的皮肤内才被考虑?另外,如果您要为如上所示的从点X开始的单元格生成索引,然后将新点Y在单元格内的位置随机化,它还会是Poisson磁盘采样算法吗?在


Tags: 版本算法距离sqrtrobert磁盘平面单元
1条回答
网友
1楼 · 发布于 2024-06-01 00:00:43

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

binned Poisson disk sampling

只要看一下x坐标,就可以排除另外三个单元格,同样还有三个单元格是因为它们的y坐标,但是值得这样做吗?直到你实现了算法并能测试性能。在

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

相关问题 更多 >