Compatible Triangulations of Planar Polygons Based on Deformed Energy Optimization

Compatible triangulation of two planar polygonal regions is an important operation for shape morphing and interpolation.This paper proposes an efficient algorithm to compatibly triangulate two given isomorphic planar polygonal shapes, which alternatively performs two operations, compatible triangulation and deformed energy minimization.The first operation consists of the following steps:1) it firstly establishes a one-to-one correspondence between vertices of two polygons;2) it generates a triangulation for the first shape by using constrained Delaunay triangulation;3) the triangulation is then deformed using mean-value coordinates editing by moving its boundary vertices to overlap the corresponding vertices of the second shape.To reduce the shape distortion between the original triangle in the first triangulation and the deformed triangle in the second triangulation, we apply the second operation to optimize the compatible triangulations by introducing topological and geometric operations, such as adaptively refining seriously distorted triangle pairs, flipping slim triangle edges and smoothing mesh vertices, to improve the first shape and then repeating the deformation process to generate the second triangulation again.Experimental results demonstrate that the approach can improve the compatible triangulation greatly.