Abstract: 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.