Efficient maximal poisson-disk sampling
Efficient maximal poisson-disk sampling
复制标题
DOI：
10.1145/1964921.1964944
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
Mohamed S. Ebeida;Andrew A. Davidson;Anjul Patney;P. Knupp;S. Mitchell;John Douglas Owens
中科院分区：
文献类型：
--
作者：
Mohamed S. Ebeida;Andrew A. Davidson;Anjul Patney;P. Knupp;S. Mitchell;John Douglas Owens
我们解决了在有界非凸域上生成最大无偏均匀泊松盘抽样的问题。据我们所知，这是第一个可证明正确的算法，时间和空间仅取决于产生的点的数量。我们的方法有两个阶段，都是基于经典的飞镖投掷。第一阶段使用正方形细胞的背景网格来快速创建一个无偏的、接近最大的域覆盖。第二阶段通过计算剩余未覆盖空隙的连接分量，并利用它们的几何形状有效地放置覆盖它们的无偏样本，完成最大覆盖。第二阶段迅速收敛，克服了飞镖投掷方法中的一个常见困难。确定性内存为O(n)，预期运行时间为O(n log n)，其中n为输出大小，即最终样本中的点数。我们的串行实现验证了log n依赖性很小，并且在实践中实现了接近O(n)的时间和内存性能。我们还提出了一个gpu上的并行实现，以展示我们方法的并行友好性，其性能是串行版本的2.4倍。
We solve the problem of generating a uniform Poisson-disk sampling that is both maximal and unbiased over bounded non-convex domains. To our knowledge this is the first provably correct algorithm with time and space dependent only on the number of points produced. Our method has two phases, both based on classical dart-throwing. The first phase uses a background grid of square cells to rapidly create an unbiased, near-maximal covering of the domain. The second phase completes the maximal covering by calculating the connected components of the remaining uncovered voids, and by using their geometry to efficiently place unbiased samples that cover them. The second phase converges quickly, overcoming a common difficulty in dart-throwing methods. The deterministic memory is O(n) and the expected running time is O(n log n), where n is the output size, the number of points in the final sample. Our serial implementation verifies that the log n dependence is minor, and nearly O(n) performance for both time and memory is achieved in practice. We also present a parallel implementation on GPUs to demonstrate the parallel-friendly nature of our method, which achieves 2.4x the performance of our serial version.