Periodic Centroidal Voronoi Tessellation on Universal Covering Spaces (Spherical, Euclidean, Hyperbolic Spaces)

Project Members

Guodong Rong1, Liang Shuai1, Xiaohu Guo1, Miao Jin2

1: University of Texas at Dallas

2: University of Louisiana at Lafayette


The centroidal Voronoi tessellation (CVT) has found versatile applications in geometric modeling, computer graphics, and visualization, etc. In this paper, we first extend the concept of CVT from Euclidean space to spherical space and hyperbolic space, and then combine all of them into a unified framework – the CVT in universal covering space. The novel spherical and hyperbolic CVT energy functions are defined, and the relationship between minimizing the energy and the CVT is proved. We also show by our experimental results that both spherical and hyperbolic CVTs have the similar property as their Euclidean counterpart where the sites are uniformly distributed with respect to given density values. As an example of the application, we utilize the CVT in universal covering space to compute uniform partitions and high-quality remeshing results for genus-0, genus-1, and high-genus (genus>1) surfaces.

Keywords: Centroidal Voronoi Tessellation, Universal Covering Space, Euclidean Space, Spherical Space, Hyperbolic Space, Remeshing




  1. Guodong Rong, Miao Jin, Xiaohu Guo, "Hyperbolic Centroidal Voronoi Tessellation", in Proceedings of ACM Symposium on Solid and Physical Modeling (SPM 2010), pp. 117-126, Haifa, Israel, September 2010.
  2. Guodong Rong, Miao Jin, Liang Shuai, Xiaohu Guo, "Centroidal Voronoi Tessellation in Universal Covering Space of Manifold Surfaces", in Computer Aided Geometric Design, Vol. 28, No. 8, pp. 475-496, 2011.
  3. Liang Shuai, Xiaohu Guo, Miao Jin, "GPU-Based Computation of Discrete Periodic Centroidal Voronoi Tessellation in Hyperbolic Space", in Computer-Aided Design (SPM 2012 Special Issue), Vol. 45, No. 2, pp. 463-472, 2013.

Errata in "Hyperbolic Centroidal Voronoi Tessellation" [1]:

The original definition of hyperbolic CVT energy (equation (8) in [1]), and the corresponding proof of Lemma 2 (Appendix B in [1]) are not correct:

In our latest journal version [2], we have corrected the hyperbolic CVT energy as:

Note that the main difference is that: instead of using sinh2(dH(p,si)) in the integral, we use cosh(dH(p,si)). Remember the distance in hyperbolic space is dH(p,q)= cosh-1(<p,q>M). So cosh(dH(p,q))= <p,q>M. Since <p,p>M=-x2-y2+z2, cosh(dH(p,q)) has the same dimension (i.e. square of length) as its Euclidean counterpart (dE(p,q))2 used in the traditional CVT energy definition. The hyperbolic CVT energy convergence is proved in Lemma 7 of the journal version [2].

Since sinh(x) and cosh(x) are both monotonically increasing functions when x≥0, so luckily the L-BFGS energy optimization method still works for the CVT energy with sinh2(dH(p,si)) in [1]. The reason is that if the CVT energy with sinh2(dH(p,si)) decreases, the CVT energy with cosh(dH(p,si)) will decrease as well, and vice versa.