Capacity-Constrained Point Distributions: A Variant of Lloyd's Method
Michael Balzer, Thomas Schlömer, Oliver Deussen
In ACM Transactions on Graphics, 28(3), July 2009.
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.
Keyword(s): Lloyd's method, Poisson disk point sets, Voronoi tessellations, blue noise, capacity constraint, importance sampling
@article{Balzer:2009:CPD,
author = {Michael Balzer and Thomas Schlömer and Oliver Deussen},
title = {Capacity-Constrained Point Distributions: A Variant of Lloyd's Method},
journal = {ACM Transactions on Graphics},
volume = {28},
number = {3},
pages = {86:1--86:8},
month = jul,
year = {2009},
}
Return to the search page.
graphbib: Powered by "bibsql" and "SQLite3."