Deterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximation
Loading...
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and John Wiley & Sons Ltd.
Abstract
We show how to sample uniformly within the three-sided region bounded by a circle, a radial ray, and a tangent, called a ''chock.'' By dividing a 2D planar rectangle into a background grid, and subtracting Poisson disks from grid squares, we are able to represent the available region for samples exactly using triangles and chocks. Uniform random samples are generated from chock areas precisely without rejection sampling. This provides the first implemented algorithm for precise maximal Poisson-disk sampling in deterministic linear time. We prove O(n.M(b) log b); where n is the number of samples, b is the bits of numerical precision and M is the cost of multiplication. Prior methods have higher time complexity, take expected time, are non-maximal, and/or are not Poisson-disk distributions in the most precise mathematical sense. We fill this theoretical lacuna.
Description
CCS Concepts: Mathematics of computing --> Distribution functions; Computing methodologies --> Rendering; Theory of computation --> Randomness, geometry and discrete structures
@article{10.1111:cgf.14606,
journal = {Computer Graphics Forum},
title = {{Deterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximation}},
author = {Mitchell, Scott A.},
year = {2022},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.14606}
}