优化变形能的平面多边形同构剖分  

Compatible Triangulations of Planar Polygons Based on Deformed Energy Optimization

作　　者：林晓穗 李桂清[1] 尹梦晓[1,2] 张智邦[1] 冼楚华[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510006 [2]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机辅助设计与图形学学报》2014年第12期2115-2125,共11页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61300136);广东省自然科学基金重点项目(S2013020012795);教育部博士点基金(20130172110041);中央高校基本科研业务费专项资金(2013ZM087)

摘　　要：平面多边形间的同构三角剖分是平面形状渐进过渡与插值的基础,降低对应三角形的变形程度是获得高质量应用的关键.文中提出一种基于变形能优化的2个平面多边形的同构剖分算法,其中包含同构剖分生成和变形能最小化2个模块.首先根据用户指定的对应特征点对多边形进行顶点重采样,得到顶点一一对应的2个多边形;然后利用带约束的Delaunay剖分对其中的一个多边形进行三角化,得到源网格;再用重心坐标将源网格的内部顶点嵌入到另一个多边形得到同构剖分(目标网格);最后逐一检查三角形的变形能,对源网格中变形能超过阈值的三角形进行细分,用同构剖分模块生成新的目标网格.实验及数据统计分析表明,该算法可以得到较好的同构三角剖分,提升网格质量,并能很好地避免纹理细节失真.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.

关 键 词：同构三角剖分 自适应细分 均值坐标 网格变形 形状插值 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]