Blue Noise through Optimal Transport

被引：152

作者：

de Goes, Fernando ^{[1
]}

Breeden, Katherine

Ostromoukhov, Victor ^{[2
]}

Desbrun, Mathieu ^{[1
]}

机构：

[1] CALTECH, Pasadena, CA 91125 USA

[2] Lyon 1 U CNRS, Lyon, France

来源：

ACM TRANSACTIONS ON GRAPHICS | 2012年 / 31卷 / 06期

基金：

美国国家科学基金会;

关键词：

Blue noise; power diagram; capacity constraints; WANG TILES;

D O I：

10.1145/2366145.2366190

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present a fast, scalable algorithm to generate high-quality blue noise point distributions of arbitrary density functions. At its core is a novel formulation of the recently-introduced concept of capacity-constrained Voronoi tessellation as an optimal transport problem. This insight leads to a continuous formulation able to enforce the capacity constraints exactly, unlike previous work. We exploit the variational nature of this formulation to design an efficient optimization technique of point distributions via constrained minimization in the space of power diagrams. Our mathematical, algorithmic, and practical contributions lead to high-quality blue noise point sets with improved spectral and spatial properties.

引用

页数：11