Blue noise sampling of surfaces

We present an algorithm to generate point distributions with high-quality blue noise characteristics on discrete surfaces. It is based on the concept of Capacity-Constrained Surface Triangulation (CCST), which approximates the underlying continuous surface as a well-formed triangle mesh with uniform triangle areas. The algorithm takes a triangle mesh and the number of sample points as input, and iteratively alternates between optimization of the geometry (positions) of the points and optimization of their topology (connectivity) until convergence. Since the method is relaxation-based, it allows precise control over the number of sample points. Differential domain analysis shows that the point distribution of CCST exhibits typical blue noise characteristics, superior to other relaxation-based sampling methods and is very efficient compared to other traditional dart-throwing methods. We generalize CCST to non-uniform sampling by incorporating a density function. This can be useful in many geometry processing applications, such as curvature-aware remeshing.

Figure optionsDownload high-quality image (118 K)Download as PowerPoint slideHighlights
► A method efficiently samples points with blue noise property on discrete surfaces.
► The surface triangulation is well-formed with quite uniform triangle areas.
► The vertex set is comparable with other methods in quality of blue noise property.
► The method can easily control the number of sample points.
► It is compatible with arbitrary density to produce non-uniform distribution.