Delaunay Mesh Simplification with Differential Evolution
Published in ACM Transactions on Graphics, 2018
Abstract: 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$ ($\lt 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.
Recommended citation: Ran Yi, Yong-Jin Liu*, Ying He. Delaunay Mesh Simplification with Differential Evolution. ACM Transactions on Graphics (SIGGRAPH ASIA 2018), Vol. 37, No. 6, Article No. 263, 2018.