优化变形能的平面多边形同构剖分
|
摘要
平面多边形间的同构三角剖分是平面形状渐进过渡与插值的基础,降低对应三角形的变形程度是获得高质量应用的关键.文中提出一种基于变形能优化的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.
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.
引文
[1]Whited B,Noris G,Simmons M,et al.An interactive tool for tight inbetweening[J].Computer Graphics Forum,2010,29(2):605-614
[2]Yang Wenwu,Feng Jieqing,Wang Xun.2Dshape blending based on multi-level feature structures[J].Journal of Computer-Aided Design&Computer Graphics,2012,24(5):563-573(in Chinese)(杨文武,冯结青,王勋.基于多层次特征结构的二维形状渐变[J].计算机辅助设计与图形学学报,2012,24(5):563-573)
[3]Yang W W,Feng J Q,Wang X.Structure preserving manipulation and interpolation for multi-element 2D shapes[J].Computer Graphics Forum,2012,31(7):2249-2258
[4]Aronov B,Seidel R,Souvaine D.On compatible triangulations of simple polygons[J].Computational Geometry,1993,3(1):27-35
[5]Gupta H,Wenger R.Constructing piecewise linear homeomorphisms of simple polygons[J].Journal of Algorithms,1997,22(1):142-157
[6]Kranakis E,Urrutia J.Isomorphic triangulations with small number of Steiner points[J].International Journal of Computational Geometry and Applications,1999,9(2):171-180
[7]Surazhsky V,Gotsman C.High quality compatible triangulations[J].Engineering with Computers,2004,20(2):147-156
[8]Zhang Dongmei,Liu Ligang.Efficient approach for high quality compatible triangulations between polygons[J].Journal of Zhejiang University:Engineering Science,2008,42(5):780-784(in Chinese)(张冬梅,刘利刚.多边形高质量同构三角剖分的有效算法[J].浙江大学学报:工学版,2008,42(5):780-784)
[9]Alexa M,Cohen-Or D,Levin D.As-rigid-as possible shape interpolation[C]Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH.New York:ACM Press,2000:157-164
[10]Baxter W V,Barla P,Anjyo K-i.Compatible embedding for2Dshape animation[J].IEEE Transaction on Visualization and Computer Graphics,2009,15(5):867-879
[11]Paul Chew L.Constrained Delaunay triangulations[J].Algorithmica,1989,4(1-4):97-108
[12]Li Lin.Generalized barycentric coordinates based mesh editing[D].Guangzhou:South China University of Technology,2010(in Chinese)(李琳.广义重心坐标网格编辑[D].广州:华南理工大学,2010)
[13]Floater M S.Mean value coordinates[J].Computer Aided Geometric Design,2003,20(1):19-27
[14]Li Guiqing,Wu Zhuangzhi,Ma Weiyin.Research advances in adaptive subdivision techniques[J].Journal of ComputerAided Design&Computer Graphics,2006,18(12):1789-1798(in Chinese)(李桂清,吴壮志,马维银.自适应细分技术研究进展[J].计算机辅助设计与图形学学报,2006,18(12):1789-1798)
[15]Dyn N,Levin D,Gregory J.A 4-point interpolatory subdivision scheme for curve design[J].Computer Aided Geometric Design,1987,4(4):257-268
[16]Liang Jinghong,Wu Guangchao,Qiu Dongtao,et al.Natural boundary conditions of 4-point theory for surface design[J].Journal of South China University of Technology:Natural Science Edition,2003,31(11):88-91(in Chinese)(梁景鸿,吴广潮,丘东涛,等.四点法曲面造型的自然边界条件[J].华南理工大学学报:自然科学版,2003,31(11):88-91)
[17]Kobbelt L,Campagna S,Vorsatz J,et al.Interactive multiresolution modeling on arbitrary meshes[C]Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH.New York:ACM Press,1998:105-114
[18]Taubin G.A signal processing approach to fair surface design[C]Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH.New York:ACM Press,1995:351-358
[19]Sarrate J,Palau J,Huerta A.Numerical representation of the quality measures of triangles and triangular meshes[J].Communications in Numerical Methods in Engineering,2003,19(7):551-561
[20]Li Haifeng,Wu Jichuan,Liu Jianbo,et al.Finite element mesh generation and decision criteria of mesh quality[J].China Mechanical Engineering,2012,23(3):368-377(in Chinese)(李海峰,吴冀川,刘建波,等.有限元网格剖分与网格质量判定指标[J].中国机械工程,2012,23(3):368-377)
[21]Li G,Yang L,Wu S H,et al.Planar shape interpolation using relative velocity fields[J].Computers&Graphics,2013,37(5):364-375
[22]Iagrashi T,Moscovich T,Hughes J F.As-rigid-as-possible shape manipulation[J].ACM Transactions on Graphics,2005,24(3):1134-1141
[2]Yang Wenwu,Feng Jieqing,Wang Xun.2Dshape blending based on multi-level feature structures[J].Journal of Computer-Aided Design&Computer Graphics,2012,24(5):563-573(in Chinese)(杨文武,冯结青,王勋.基于多层次特征结构的二维形状渐变[J].计算机辅助设计与图形学学报,2012,24(5):563-573)
[3]Yang W W,Feng J Q,Wang X.Structure preserving manipulation and interpolation for multi-element 2D shapes[J].Computer Graphics Forum,2012,31(7):2249-2258
[4]Aronov B,Seidel R,Souvaine D.On compatible triangulations of simple polygons[J].Computational Geometry,1993,3(1):27-35
[5]Gupta H,Wenger R.Constructing piecewise linear homeomorphisms of simple polygons[J].Journal of Algorithms,1997,22(1):142-157
[6]Kranakis E,Urrutia J.Isomorphic triangulations with small number of Steiner points[J].International Journal of Computational Geometry and Applications,1999,9(2):171-180
[7]Surazhsky V,Gotsman C.High quality compatible triangulations[J].Engineering with Computers,2004,20(2):147-156
[8]Zhang Dongmei,Liu Ligang.Efficient approach for high quality compatible triangulations between polygons[J].Journal of Zhejiang University:Engineering Science,2008,42(5):780-784(in Chinese)(张冬梅,刘利刚.多边形高质量同构三角剖分的有效算法[J].浙江大学学报:工学版,2008,42(5):780-784)
[9]Alexa M,Cohen-Or D,Levin D.As-rigid-as possible shape interpolation[C]Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH.New York:ACM Press,2000:157-164
[10]Baxter W V,Barla P,Anjyo K-i.Compatible embedding for2Dshape animation[J].IEEE Transaction on Visualization and Computer Graphics,2009,15(5):867-879
[11]Paul Chew L.Constrained Delaunay triangulations[J].Algorithmica,1989,4(1-4):97-108
[12]Li Lin.Generalized barycentric coordinates based mesh editing[D].Guangzhou:South China University of Technology,2010(in Chinese)(李琳.广义重心坐标网格编辑[D].广州:华南理工大学,2010)
[13]Floater M S.Mean value coordinates[J].Computer Aided Geometric Design,2003,20(1):19-27
[14]Li Guiqing,Wu Zhuangzhi,Ma Weiyin.Research advances in adaptive subdivision techniques[J].Journal of ComputerAided Design&Computer Graphics,2006,18(12):1789-1798(in Chinese)(李桂清,吴壮志,马维银.自适应细分技术研究进展[J].计算机辅助设计与图形学学报,2006,18(12):1789-1798)
[15]Dyn N,Levin D,Gregory J.A 4-point interpolatory subdivision scheme for curve design[J].Computer Aided Geometric Design,1987,4(4):257-268
[16]Liang Jinghong,Wu Guangchao,Qiu Dongtao,et al.Natural boundary conditions of 4-point theory for surface design[J].Journal of South China University of Technology:Natural Science Edition,2003,31(11):88-91(in Chinese)(梁景鸿,吴广潮,丘东涛,等.四点法曲面造型的自然边界条件[J].华南理工大学学报:自然科学版,2003,31(11):88-91)
[17]Kobbelt L,Campagna S,Vorsatz J,et al.Interactive multiresolution modeling on arbitrary meshes[C]Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH.New York:ACM Press,1998:105-114
[18]Taubin G.A signal processing approach to fair surface design[C]Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH.New York:ACM Press,1995:351-358
[19]Sarrate J,Palau J,Huerta A.Numerical representation of the quality measures of triangles and triangular meshes[J].Communications in Numerical Methods in Engineering,2003,19(7):551-561
[20]Li Haifeng,Wu Jichuan,Liu Jianbo,et al.Finite element mesh generation and decision criteria of mesh quality[J].China Mechanical Engineering,2012,23(3):368-377(in Chinese)(李海峰,吴冀川,刘建波,等.有限元网格剖分与网格质量判定指标[J].中国机械工程,2012,23(3):368-377)
[21]Li G,Yang L,Wu S H,et al.Planar shape interpolation using relative velocity fields[J].Computers&Graphics,2013,37(5):364-375
[22]Iagrashi T,Moscovich T,Hughes J F.As-rigid-as-possible shape manipulation[J].ACM Transactions on Graphics,2005,24(3):1134-1141