A Method For Generating Planar Compatible Triangulations Based On Deformed Optimization

Compared with quadrilateral meshes,Voronoi diagrams and other planar expressions,the triangular meshes have high degree of freedom,simple data structure,and so on.The triangular meshes are widely used in computer graphics,animation,computer games,and other fields.The compatible triangular meshes are the core of computer animation,shape interpolation and other applications,and it is still a research hotspot to find a good compatible mapping relationship between two planar shapes.The previous compatible triangulations algorithms have many disadvantages,such as the generated triangular meshes have poor quality and the application of the triangular meshes are very limited.In order to improve the quality of the triangular meshes,we use a method of generating compatible triangulations based on locally injective mappings,and use the preprocessing optimization based on the initial mapping of the target triangular meshes and the optimization based on the areas of the corresponding triangle of the source triangular meshes and the target triangular meshes are as equal as possible.Our method is divided into two parts.First,the formation of compatible triangulation.We select feature points of the source shape and the target shape and manually match the feature points on the source shape and the target shape.We use constrained Delaunay triangulation to generate the triangular meshes of the source shape polygon.The boundary vertices of triangular meshes of the source shape are mapped onto the boundary of the target shape,then the vertices inside the triangular meshes of the source shape are mapped to the inside of the target shape polygon by using the locally injective mappings,thus we will get the compatible triangulations of the source polygon and the target polygon.Second,the optimization of triangular meshes of the target shape polygon.Our approach is to map the vertices inside the source shape polygon to the inside of the target shape polygon by the locally injective mappings.It can be seen as a question of finding the new vertices coordinates of the triangular meshes after the triangular meshes are deformed,and it is actually a deformation problem.However,for some special examples,the triangular meshes of the source shape 'S' can not smoothly transition to the triangular meshes of the target shape 'U'.This problem can be solved by using the preprocessing optimization based on the initial mapping of the target triangular meshes.Finally,high quality compatible triangulations are obtained by using the optimization based on the areas of the corresponding triangle of the source triangular meshes and the target triangular meshes are as equal as possible.Compared with the previous compatible triangulations algorithms,our algorithm improves the quality of the triangular meshes,and reduces the number of narrow triangles and the distortion and degeneration of triangles,and makes the compatible triangulations more widely used in interpolation.It also makes the deformation process more smooth and continuous.