Blue-Noise Point Sampling Based On Centroidal Delaunay Triangulation

Blue noise distribution refers to a sampling pattern that has a uniform and unbiased distribution in the spatial domain as well as prevent low frequency noise and structured bias in the frequency domain.Because of its desirable spatial and spectral properties,blue noise sampling has been widely used in computer graphics including modeling,rendering,image reconstruction and Non-photorealistic rendering.The efficacy of these applications crucially depends upon the distribution quality of the underlying samples,so the generation of high quality blue noise sampling and distribution has always been an important research topic.The existing algorithms based on dart throwing can generate blue noise sampling distribution,but it is often computationally expensive and can not precisely control the number of sampling points.Iterative relaxation is another important technique.But some of the relaxation-based algorithms may produce the distribution of regularity,resulting in the occurrence of aliasing artifacts.And the capacity is approximated by discrete methods,which greatly influences the efficiency of the algorithm.We study a blue noise sampling algorithm based on Centroidal Delaunay Triangulation(CDT),which effectively generates high-quality blue noise sample distribution.The algorithm has the advantages of simple principle,fast convergence rate and good robustness.The main idea of our method is to combine the topological structure of Delaunay triangulation with the distribution of sampling points based on the relaxation algorithm.For the uniform sampling and nonuniform sampling,the algorithm is divided into three steps,the first step is the initialization process,initializing the sampling distribution with the adaptive algorithm;The second step aims to build the Delaunay triangulation.And the third step is to optimize the location and the connectivity between the samples iteratively.Calculate the centroidal patch triangulation(CPT)of the sampling point,and move the sampling point to the barycenter of the patch through iteratively update the point location and the connectivity of the sample points to achieve global convergence,and ultimately access to a high-quality blue noise sampling distribution.In the case of planar nonuniform sampling,we propose to use a rendering method to classify triangles,so that the algorithm achieves higher execution efficiency.Then,the algorithm is extended to the surface to solve the blue noise sampling problem.Using the same idea as sampling on the planar,the geometric position and topology of the sampling point are iteratively optimized on the surface.In order to verify the effectiveness of our method,the algorithm is compared with other existing competitive algorithms in the case of two-dimensional uniform sampling.From the spectrum analysis,we conclude that our method can generate high-quality blue noise sampling distribution.In the case of non-uniform sampling,the CCDT method with the same topology is compared by generating stippling of a certain image.The experimental results show that the proposed method can also exhibit the blue noise characteristic.While different types of models are tested in the case of surface sampling with uniformity and nonuniformity.The corresponding outputs also have blue noise characteristics,besides,both the robustness and the efficiency of the algorithm are proved in the experiments.