Spoke Darts for Efficient High Dimensional Blue Noise Sampling
share
Blue noise refers to sample distributions that are random and well-spaced, with a variety of applications in graphics, geometry, and optimization. However, prior blue noise sampling algorithms typically suffer from the curse-of-dimensionality, especially when striving to cover a domain maximally. This hampers their applicability for high dimensional domains. We present a blue noise sampling method that can achieve high quality and performance across different dimensions. Our key idea is spoke-dart sampling, sampling locally from hyper-annuli centered at prior point samples, using lines, planes, or, more generally, hyperplanes. Spoke-dart sampling is more efficient at high dimensions than the state-of-the-art alternatives: global sampling and advancing front point sampling. Spoke-dart sampling achieves good quality as measured by differential domain spectrum and spatial coverage. In particular, it probabilistically guarantees that each coverage gap is small, whereas global sampling can only guarantee that the sum of gaps is not large. We demonstrate advantages of our method through empirical analysis and applications across dimensions 8 to 23 in Delaunay graphs, global optimization, and motion planning.
READ FULL TEXT