Improving spatial coverage while preserving the blue noise of point sets

摘要

We explore the notion of a Well-spaced Blue-noise Distribution (WBD) of points, which combines two desirable properties. First, the point distribution is random, as measured by its spectrum having blue noise. Second, it is well-spaced in the sense that the minimum separation distance between samples is large compared to the maximum coverage distance between a domain point and a sample, i.e. its Voronoi cell aspect ratios 2β~i are small. It is well known that maximizing one of these properties destroys the other: uniform random points have no aspect ratio bound, and the vertices of an equilateral triangular tiling have no randomness. However, we show that there is a lot of room in the middle to get good values for both. Maximal Poisson-disk sampling provides β = 1 and blue noise. We show that a standard optimization technique can improve the well-spacedness while preserving randomness. Given a random point set, our Opt-β~i algorithm iterates over the points, and for each point locally optimizes its Voronoi cell aspect ratio 2β~i. It can improve β~i to a large fraction of the theoretical bound given by a structured tiling: improving from 1.0 to around 0.8, about half-way to 0.58, while preserving most of the randomness of the original set. In terms of both β and randomness, the output of Opt-β~i compares favorably to alternative point improvement techniques, such as centroidal Voronoi tessellation with a constant density function, which do not target β directly. We demonstrate the usefulness of our output through meshing and filtering applications. An open problem is constructing from scratch a WBD distribution with a guarantee of β < 1.