ACM Transactions on Graphics (Proceedings of SIGGRAPH), 2009

Capacity-Constrained Point Distributions: A Variant of Lloyd's Method

Michael Balzer       Thomas Schlömer       Oliver Deussen
University of Konstanz, Germany





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.


Video


Downloads

Paper
PDF (8.9 MB)
 
Video
Quicktime (104.9 MB)
DivX AVI (78.7 MB)
Source Code
Visit our open source
project at Google Code

Additional Material

Our Method
Illustration
 
Point Sets
Results
 
Stippling
Results
 
Spectral Analysis
Results
 
Convergence
Results
 
Analysis Tool
New open source
analysis tool

Bibtex

@article{Balzer.etal:2009:CCPDAVoLM,
    author    = {Michael Balzer and Thomas Schl\"omer and Oliver Deussen},
    title     = {Capacity-Constrained Point Distributions: A Variant of {L}loyd's Method},
    journal   = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2009)},
    volume    = {28},
    number    = {3},
    year      = {2009},
    issn      = {0730-0301},
    pages     = {86:1--8},
    doi       = {http://doi.acm.org/10.1145/1531326.1531392},
    publisher = {ACM},
    address   = {New York, NY, USA}
}