Deterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximation

Simple item page
dc.contributor.authorMitchell, Scott A.en_US
dc.contributor.editorCampen, Marcelen_US
dc.contributor.editorSpagnuolo, Michelaen_US
dc.date.accessioned2022-06-27T16:19:53Z
dc.date.available2022-06-27T16:19:53Z
dc.date.issued2022
dc.description.abstractWe 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.en_US
dc.description.number5
dc.description.sectionheadersTools and Data
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume41
dc.identifier.doi10.1111/cgf.14606
dc.identifier.issn1467-8659
dc.identifier.pages101-111
dc.identifier.pages11 pages
dc.identifier.urihttps://doi.org/10.1111/cgf.14606
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf14606
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectCCS Concepts: Mathematics of computing --> Distribution functions; Computing methodologies --> Rendering; Theory of computation --> Randomness, geometry and discrete structures
dc.subjectMathematics of computing
dc.subjectDistribution functions
dc.subjectComputing methodologies
dc.subjectRendering
dc.subjectTheory of computation
dc.subjectRandomness
dc.subjectgeometry and discrete structures
dc.titleDeterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximationen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
v41i5pp101-111.pdf
Size:
2.44 MB
Format:
Adobe Portable Document Format
Download
Collections
41-Issue 5