Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/89445
Title: Intrinsic computation of Centroidal Voronoi Tessellation (CVT) on meshes
Authors: Wang, Xiaoning
Ying, Xiang
Liu, Yong-Jin
Xin, Shi-Qing
Wang, Wenping
Gu, Xianfeng
Mueller-Wittig, Wolfgang
He, Ying
Keywords: Voronoi Diagram
Centroidal Voronoi tessellation (CVT)
DRNTU::Engineering::Computer science and engineering
Issue Date: 2015
Source: Wang, X., Ying, X., Liu, Y. J., Xin, S. Q., Wang, W., Gu, X., ... He, Y. (2015). Intrinsic computation of Centroidal Voronoi Tessellation (CVT) on meshes. Computer-Aided Design, 5851-61. doi:10.1016/j.cad.2014.08.023
Series/Report no.: Computer-Aided Design
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.
URI: https://hdl.handle.net/10356/89445
http://hdl.handle.net/10220/46261
ISSN: 0010-4485
DOI: http://dx.doi.org/10.1016/j.cad.2014.08.023
Rights: © 2014 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by Computer-Aided Design, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1016/j.cad.2014.08.023].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Intrinsic Computation of Centroidal Voronoi Tessellation (CVT) on Meshes.pdf24.66 MBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.