Blue noise sampling of surfaces

Yin Xu, Ruizhen Hu, Craig Gotsman, Ligang Liu

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)232-240
Number of pages9
JournalComputers and Graphics (Pergamon)
Issue number4
StatePublished - Jun 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • General Engineering
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design


  • Blue noise
  • Capacity-Constrained Surface Triangulation (CCST)
  • Minimal area variance
  • Relaxation-based


Dive into the research topics of 'Blue noise sampling of surfaces'. Together they form a unique fingerprint.

Cite this