Centroidal Voronoi tessellation (CVT) is a special type of Voronoi diagram such that the generating point
of each Voronoi cell is also its center of mass. The CVT has broad applications in computer graphics, such
as meshing, stippling, sampling, etc. The existing methods for computing CVTs on meshes either require
a global parameterization or compute it in the restricted sense (that is, intersecting a 3D CVT with the
surface). Therefore, these approaches often fail on models with complicated geometry and/or topology.
This paper presents two intrinsic algorithms for computing CVT on triangle meshes. The first algorithm
adopts the Lloyd framework, which iteratively moves the generator of each geodesic Voronoi diagram
to its mass center. Based on the discrete exponential map, our method can efficiently compute the Riemannian
center and the center of mass for any geodesic Voronoi diagram. The second algorithm uses the
L-BFGS method to accelerate the intrinsic CVT computation. Thanks to the intrinsic feature, our methods
are independent of the embedding space, and work well for models with arbitrary topology and complicated
geometry, where the existing extrinsic approaches often fail. The promising experimental results
show the advantages of our method.