ACM Transactions on Graphics

Capacity-constrained Point Distributions: A Variant of Lloydś Method

M. Balzer, T. Schlömer, O. Deussen

Material

Abstract

We present a new general-purpose method for optimizing existing point sets. The resulting distributions possess high-quality blue noise characteristics and adapt precisely to given density functions. Our method is similar to the commonly used Lloyd’s method while avoiding its drawbacks. We achieve our results by utilizing the concept of capacity, which for each point is determined by the area of its Voronoi region weighted with an underlying density function. We demand that each point has the same capacity. In combination with a dedicated optimization algorithm, this capacity constraint enforces that each point obtains equal importance in the distribution. Our method can be used as a drop-in replacement for Lloyd’s method, and combines enhancement of blue noise characteristics and density function adaptation in one operation.

BibTeX

@article{Balzer2009CapacityconstrainedPoint,
  acmid      = {1531392},
  address    = {New York, NY, USA},
  articleno  = {86},
  author     = {M. Balzer, T. Schlömer, O. Deussen},
  doi        = {10.1145/1531326.1531392},
  issn       = {0730-0301},
  issue_date = {August 2009},
  journal    = {ACM Transactions on Graphics},
  keywords   = {Lloyd's method, Poisson disk point sets, Voronoi tessellations, blue noise, capacity constraint, importance sampling},
  month      = {jul},
  number     = {3},
  numpages   = {8},
  pages      = {86:1--86:8},
  publisher  = {ACM},
  title      = {Capacity-constrained Point Distributions: A Variant of Lloydś Method},
  url        = {http://graphics.uni-konstanz.de/publikationen/2009/capacityconstrainedpointdistributions/website/},
  volume     = {28},
  year       = {2009}
}