Premium
Fast Generation of Approximate Blue Noise Point Sets
Author(s) -
Kalantari Nima Khademi,
Sen Pradeep
Publication year - 2012
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2012.03149.x
Subject(s) - parallelizable manifold , noise (video) , poisson distribution , computer science , sampling (signal processing) , algorithm , convolution (computer science) , bounded function , sample (material) , function (biology) , set (abstract data type) , mathematics , artificial intelligence , mathematical analysis , computer vision , statistics , image (mathematics) , physics , filter (signal processing) , evolutionary biology , biology , artificial neural network , thermodynamics , programming language
Poisson‐disk sampling is a popular sampling method because of its blue noise power spectrum, but generation of these samples is computationally very expensive. In this paper, we propose an efficient method for fast generation of a large number of blue noise samples using a small initial patch of Poisson‐disk samples that can be generated with any existing approach. Our main idea is to convolve this set of samples with another to generate our final set of samples. We use the convolution theorem from signal processing to show that the spectrum of the resulting sample set preserves the blue noise properties. Since our method is approximate, we have error with respect to the true Poisson‐disk samples, but we show both mathematically and practically that this error is only a function of the number of samples in the small initial patch and is therefore bounded. Our method is parallelizable and we demonstrate an implementation of it on a GPU, running more than 10 times faster than any previous method and generating more than 49 million 2D samples per second. We can also use the proposed approach to generate multidimensional blue noise samples.