Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/89444
Title: Manifold Differential Evolution (MDE) : A global optimization method for geodesic Centroidal Voronoi Tessellations on meshes
Authors: Liu, Yong-Jin
Xu, Chun-Xu
Yi, Ran
Fan, Dian
He, Ying
Keywords: Centroidal Voronoi Tessellation
Geodesic Voronoi Diagram
DRNTU::Engineering::Computer science and engineering
Issue Date: 2016
Source: Liu, Y. J., Xu, C. X., Yi, R., Fan, D., & He, Y. (2016). Manifold differential evolution (MDE). ACM Transactions on Graphics, 35(6), 1-10. doi:10.1145/2980179.2982424
Series/Report no.: ACM Transactions on Graphics
Abstract: Computing centroidal Voronoi tessellations (CVT) has many applications in computer graphics. The existing methods, such as the Lloyd algorithm and the quasi-Newton solver, are efficient and easy to implement; however, they compute only the local optimal solutions due to the highly non-linear nature of the CVT energy. This paper presents a novel method, called manifold differential evolution (MDE), for computing globally optimal geodesic CVT energy on triangle meshes. Formulating the mutation operator using discrete geodesics, MDE naturally extends the powerful differential evolution framework from Euclidean spaces to manifold domains. Under mild assumptions, we show that MDE has a provable probabilistic convergence to the global optimum. Experiments on a wide range of 3D models show that MDE consistently outperforms the existing methods by producing results with lower energy. Thanks to its intrinsic and global nature, MDE is insensitive to initialization and mesh tessellation. Moreover, it is able to handle multiply-connected Voronoi cells, which are challenging to the existing geodesic CVT methods.
URI: https://hdl.handle.net/10356/89444
http://hdl.handle.net/10220/46265
ISSN: 0730-0301
DOI: http://dx.doi.org/10.1145/2980179.2982424
Rights: © 2016 Association for Computing Machinery (ACM). This is the author created version of a work that has been peer reviewed and accepted for publication by ACM Transactions on Graphics, Association for Computing Machinery (ACM). 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.1145/2980179.2982424].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Google ScholarTM

Check

Altmetric

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