Manifold Differential Evolution (MDE): A Global Optimization Method for Geodesic Centroidal Voronoi Tessellations on Meshes

Yong-Jin Liu Tsinghua University Chun-Xu Xu Tsinghua University Ran Yi Tsinghua University Dian Fan Tsinghua University Ying He Nanyang Technological University

Computational Geometry Geometric Modeling and Processing mathscidoc:1804.09004

ACM Transactions on Graphics (SIGGRAPH ASIA 2016), 35, (6), 243, 2016.12
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.
Differential Evolution, 2-manifold, Centroidal Voronoi tessellation, Global optimization
[ Download ] [ 2018-04-04 10:07:26 uploaded by liuyongjin ] [ 833 downloads ] [ 0 comments ]
@inproceedings{yong-jin2016manifold,
  title={Manifold Differential Evolution (MDE): A Global Optimization Method for Geodesic Centroidal Voronoi Tessellations on Meshes},
  author={Yong-Jin Liu, Chun-Xu Xu, Ran Yi, Dian Fan, and Ying He},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180404100726109246028},
  booktitle={ACM Transactions on Graphics (SIGGRAPH ASIA 2016)},
  volume={35},
  number={6},
  pages={243},
  year={2016},
}
Yong-Jin Liu, Chun-Xu Xu, Ran Yi, Dian Fan, and Ying He. Manifold Differential Evolution (MDE): A Global Optimization Method for Geodesic Centroidal Voronoi Tessellations on Meshes. 2016. Vol. 35. In ACM Transactions on Graphics (SIGGRAPH ASIA 2016). pp.243. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180404100726109246028.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved