Python中的快速泊松磁盘采样[Robert Bridson] [英] Fast Poisson Disk Sampling [Robert Bridson] in Python
问题描述
首先，我在2D平面上实现了普通的，缓慢的泊松磁盘采样算法，并且效果很好。此慢速版本计算所有点之间的距离，并检查您希望放置的点是否与所有其他点至少相距R。
Robert Bridson的快速版本，可在此处找到：
只需查看x坐标，就可以再得到三个像元因为它们的y坐标而排除了三个单元格，但是值得吗？直到您实现算法并可以测试性能。
A2：不，我认为这并不棘手。 （x，y）处的点占据像元（⌊√2x /r⌋，⌊√2y /r⌋）。如果新点位于占用的单元格中，或者21个单元格中的任何一个包含的点太近，则将拒绝这些新点。
First of all, I implemented the ordinary, slow, Poisson Disk Sampling algorithm in the 2D plane and it works just fine. This slow version calculates the distances between all points and checks that the point you wish to place is at least R away from all the others.
The fast version by Robert Bridson, available here: https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf, suggests discretizing your 2D plane into quadratic cells with length = R/sqrt(2) since each cell can at most contain a single valid point this way and the number of cells you need to check for distance calculations becomes constant. It also has the advantage of you knowing the maximum number of points which can be placed exactly on a given finite 2D plane and a distance R. I hope I have understood this correctly...
My implementation in Python of the Fast Poisson Disk Sampling algorithm does not work however, and I can not figure out why. It is slower, probably because I haven't vectorized it yet, but it also gives incorrect results when I do not check absolutely every point. That is, invalid points are generated. I'll start with asking some questions which were not answered in Robert Brindson's paper.
Q1: Given that you wish to place a point X in a cell, and that each cell is a square with length R/sqrt(2), what cells do you need to check if occupied by a point Y to determine if the point X is at least R away from all the Y?
Just drawing circles and grids on paper I came up with this:
[ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][X][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][ ]
Can anyone confirm this is correct/incorrect?
Q2: How would you go about calculating what cell a point X should occupy? There is no mention of this in the paper, but it seems tricky in cases where the point X is near the boundary of cells. Should I make a 'skin' of a certain thickness around the cells so that a point is only considered if isn't inside the skin of its cell? Also, if you were to generate indexes instead, for such cells as shown above from a point X, then randomize the location of your new point Y inside the cell, would it still be the Poisson Disk Sampling algorithm?
A1: yes, checking these cells is sufficient if the cell size equals r/√2.
Just by looking at the x coordinates, three more cells could be excluded, and likewise three cells because of their y coordinates, but is it worth the effort? Not until you've implemented the algorithm and can test performance.
A2: No, I don't think this will be tricky. The point at (x, y) occupies cell (⌊√2 x/r⌋, ⌊√2 y/r⌋). New points will be rejected if they are either in an occupied cell, or if any of the 21 cells contains a point that is too close.
这篇关于Python中的快速泊松磁盘采样[Robert Bridson]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
