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

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}
}