Delaunay Mesh Simplification with Differential Evolution
TimeThursday, 6 December 20184:15pm - 4:41pm
DescriptionDelaunay meshes (DM) are a special type of manifold triangle meshes where the local Delaunay condition holds everywhere, and have 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 target 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 can be viewed as a monotonic path on the grid. We develop a novel differential-evolution-based method to compute the optimal 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 CAD models and man-made objects with sharp features but less geometric 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.