Delaunay mesh simplification with differential evolution

• Main Authors: Yi, Ran, Liu, Yong-Jin, He, Ying
• Other Authors: School of Computer Science and Engineering
• Format: Article
• Language: English
• Published: 2020
• Subjects: Engineering::Computer science and engineering; Computing Methodologies; Computer Graphics
• Online Access: https://hdl.handle.net/10356/144750
• Institution: Nanyang Technological University

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 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 Hausdorffdistance 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.