Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes. (January 2015)

• Record Type: Journal Article
• Authors: Wang, Xiaoning; Ying, Xiang; Liu, Yong-Jin; Xin, Shi-Qing; Wang, Wenping; Gu, Xianfeng; Mueller-Wittig, Wolfgang; He, Ying
• Is Part Of: Computer aided design. Volume 58(2015)
• Page Start: 51
• Page End: 61
• Publication Date: 2015-01
• Subjects: Voronoi diagram -- Centroidal Voronoi tessellation (CVT) -- Discrete geodesics -- Exponential map -- Riemannian center -- The L-BFGS method; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2014.08.023
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: 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. Highlights: We propose two intrinsic methods for computing centroidal Voronoi tessellation (CVT) on triangle meshes. Thanks to their intrinsic nature, our methods compute CVT using metric only. Our results are independent of the embedding space.