Delaunay Mesh Simplification with Differential Evolution

Ran Yi Tsinghua University Yong-Jin Liu Tsinghua University Ying He Nanyang Technological University

Computational Geometry Geometric Modeling and Processing mathscidoc:1903.09002

ACM Transactions on Graphics (SIGGRAPH ASIA 2018), 37, (6), 263, 2018.12
Delaunay meshes (DM) are a special type of manifold triangle meshes --- where the local Delaunay condition holds everywhere --- and find important applications in digital geometry processing. This paper addresses the \yongjin{general} DM simplification problem: given an arbitrary manifold triangle mesh M with n vertices and the user-specified resolution m(< n), compute a Delaunay mesh M* with m vertices that has the least Hausdorff distance to M. To solve the problem, we abstract the simplification process using a 2D Cartesian grid model, in which each grid point corresponds to triangle meshes with a certain number of vertices and a simplification process is a monotonic path on the grid. We develop a novel differential-evolution-based method to compute a low-cost path, which leads to a high quality Delaunay mesh. Extensive evaluation shows that our method consistently outperforms the existing methods in terms of approximation error. In particular, our method is highly effective for small-scale CAD models and man-made objects with sharp features but less details. Moreover, our method is fully automatic and can preserve sharp features well and deal with models with multiple components, whereas the existing methods often fail.
Delaunay mesh, mesh simplification, 2D Cartesian grid model, differential evolution
[ Download ] [ 2019-03-19 23:13:07 uploaded by liuyongjin ] [ 532 downloads ] [ 0 comments ]
  title={Delaunay Mesh Simplification with Differential Evolution},
  author={Ran Yi, Yong-Jin Liu, and Ying He},
  booktitle={ACM Transactions on Graphics (SIGGRAPH ASIA 2018)},
Ran Yi, Yong-Jin Liu, and Ying He. Delaunay Mesh Simplification with Differential Evolution. 2018. Vol. 37. In ACM Transactions on Graphics (SIGGRAPH ASIA 2018). pp.263.
Please log in for comment!
Contact us: | Copyright Reserved