| Computer graphics has shown great success in the last few decades. Antialiasing, which is an important subfield of computer graphics, has also seen great development.; Besides supersampling and filtering, people have found that nonuniform sampling can trade structured aliasing for noise, which is much less objectionable to human visual system.; The term "blue noise" shows the desired spectral property of the nonuniform point samples, i.e., the spectrum should vanish in the low frequencies and remain roughly uniform in the high frequencies, which resembles the spectrum of the blue color. It has been found that good blue noise characteristic is obtained by points from Poisson disk distribution, where the points are random and are not too close to each other. Naturally, the dart throwing algorithm can be used to generate Poisson disk samples. However, this algorithm is very slow, so various modifications have been developed to generate blue noise samples more quickly.; One fast alternative is Lloyd's relaxation, which starts with an initial point set, computes the Voronoi diagram, moves each point to its Voronoi cell's centroid and iterates. However, Lloyd's relaxation suffers from the convergence to an aliasing-prone hexagonal grid after a moderate number of iterations. We developed a new sampling algorithm called the thin blue noise sampling (TBN) which is similar to Lloyd's relaxation in spirit but circumvents this convergence. We use a special kind of weighted Voronoi diagram called the power diagram instead of the ordinary Voronoi diagram in the iterations. The thin blue noise algorithm has about the same computational complexity as Lloyd's relaxation and outperforms Lloyd's relaxation in the sense of blueness.; Blue noise sampling is also studied in 3d and higher dimensional spaces. Another interesting geometric object is the sphere, which is also fundamental in computer graphics, e.g., sampling reflected light rays. Various sampling algorithms are studied for the sphere with the powerful tool of spherical Fourier analysis.; Related areas in mathematics and statistics include discrepancy, quasi-Monte Carlo method, numerical integration, covering and packing, etc. Relationship between blue noise sampling and these subjects is studied in this treatment too. |
