Show simple item record

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.identifier.issn1467-8659
dc.identifier.urihttps://doi.org/10.1111/cgf.14606
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf14606
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.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
dc.description.seriesinformationComputer Graphics Forum
dc.description.sectionheadersTools and Data
dc.description.volume41
dc.description.number5
dc.identifier.doi10.1111/cgf.14606
dc.identifier.pages101-111
dc.identifier.pages11 pages


Files in this item

Thumbnail

This item appears in the following Collection(s)

  • 41-Issue 5
    Geometry Processing 2022 - Symposium Proceedings

Show simple item record