Teaser: Generating a uniform CCDT of 286 sites. The x-axis of the graph is the number of passes over the image. The red stars indicate a Delaunay triangulation phase (end of an iteration).
Abstract
Sample point
distributions possessing blue noise spectral characteristics play a
central role in computer graphics, but are notoriously difficult to
generate. We describe an algorithm to very efficiently generate these
distributions. The core idea behind our method is to compute a
Capacity-Constrained Delaunay Triangulation (CCDT), namely, given a
simple polygon P in the plane, and the desired number of points n,
compute a Delaunay triangulation of the interior of P with n Steiner
points, whose triangles have areas which are as uniform as possible.
This is computed iteratively by alternating update of the point geometry
and triangulation connectivity. The vertex set of the CCDT is shown to
have good blue noise characteristics, comparable in quality to those of
state-of-the-art methods, achieved at a fraction of the runtime. Our
CCDT method may be applied also to an arbitrary density function to
produce nonuniform point distributions. These may be used to half-tone
grayscale images.
This work is partly
supported by the National Natural Science Foundation of China (61070071)
and the Fundamental Research Funds for the Central Universities
(2010QNA3039).
title = {Capacity-Constrained Delaunay Triangulation for Point Distributions},
author = {Yin Xu and Ligang Liu and Craig Gotsman and Steven J. Gortler}
journal = {Computers & Graphics (Proceedings of Shape Modeling International)},
volume = {35},
number = {3},
pages = {510-516},
year = {2011}
}