Computer Engineering and Applications 计算机工程与应用
2010，46（36）1引言
变形技术一直是计算机图形学中研究的重要课题，特别
是近年来，随着计算机硬件技术的不断发展，变形技术被广泛应用于计算机动画，模式匹配以及几何造型等领域。一个好的变形算法应当满足：（1）变形过程中产生的中间状态的一些特征，如边长、夹角、面积等应保持单调平滑的变换。（2）变形过程中产生的中间状态没有出现自交、收缩、内部区域发生扭曲等不自然现象。（3）中间状态要保持初始状态和目标状态的视觉特征。变形需要解决顶点对应问题和对应顶点的插值路径两个关键问题。本文主要解决对应定点的插值路径问题。
对于对应顶点的插值路径问题，最简单的处理方法就是顶点位置的线性插值，虽然算法简单速度快，但是用此方法产生的中间多边形往往会产生自交或收缩，效果不自然。Seder-berg [1]等人提出了平面多变形的内在解算法，线性插值相邻边的旋转角和边长，并采用优化的方法避免断口现象，该算法能够体现多边形的结构特征，但中间多边形容易产生内部区域扭曲。之后Shapria 和Rappor [2]采用星骨架方法来处理多边形的内部区域，虽然内部区域扭曲现象比内在解方法有了较大的改善，变形效果也比较自然，可是算法的复杂度也随之增
大。任绍忠等[3]提出了保特征形状过渡的伸缩内在量算法，此方法将多边形用一个伸缩内在矩阵表示，通过求解线性方程组得到结果。此方法可以比较有效地避免变形过程中多边形可能产生的萎缩、自交等现象。但是其不能直接地插值特征点，只能通过增大权值来近似地插值，而且其求解中间多边形的过程只是最小二乘意义下的，而并非真正意义上的最小二乘问题，当特征点过多时容易出现局部的不自然现象。基于此，在沿用文献[3]的多边形伸缩内在量表示的基础上，改进了其重构多边形的方法，提出了基于特征点约束的多边形变形算法，该算法从使得变形前后多边形尽量满足形变最小入手，首先对每个顶点定义误差函数，得到整体的误差函数，将中间多边形的重构转化为一个最小二乘问题，通过矩阵运算求解方程组，得到直接插值特征点的中间多边形。
2特征点约束下的多边形形状控制
对于一个用多边形表示的二维形状，当用户需要在保持
原有细节的情况下改变多边形的形状时，往往通过改变多边形上一部分点的位置来实现。这部分点通常为视觉特征比较明显的点，反映在图形上则往往是尖点、角点、拐点等高曲率
可控制形状的多边形变形算法
许婷1，刘占一2，胡玫瑰1
XU Ting 1，LIU Zhan-yi 2，HU Mei-gui 1
1.西北工业大学理学院，西安710072
2.西北工业大学航海学院，西安710072
1.College of Science ，Northwestern Polytechnical University ，Xi ’an 710072，China
2.College of Marine ，Northwestern Polytechnical University ，Xi ’an 710072，China E-mail ：xt10_2@16
https://www.doczj.com/doc/6c17558521.html,
XU Ting ，LIU Zhan-yi ，HU Mei-gui.2D polygon morphing based on polygonal shape https://www.doczj.com/doc/6c17558521.html,puter Engineering and Applications ，2010，46（36）：216-218.
Abstract ：This paper presents an approach to 2D polygon morphing based on polygonal shape controlling.The method speci-fies feature points in the source and target polygon ，then the changes of the position of the feature points bring the entire polygon changes.Under the constraint of the feature points ，the result middle polygon gets a smallest change.Experimental re-sults show that the morphing sequence produced by the solution can avoid the shrinkage commendably and achieve better morphing effects.
Key words ：morphing ；polygon ；shape controlling 摘
要：提出了一种可控制形状的多边形变形算法。该方法在源和目标多边形上指定对应的特征点，通过特征点的位置变化来
带动整个多边形变化。得到的中间多边形在特征点约束下保持原内在量相对关系的最小变化，有效去除了多余的形变。通过试验表明，该算法产生的变形序列能很好地避免萎缩、自交等不自然现象，取得了良好的变形效果。关键词：变形；多边形；形状控制
DOI ：10.3778/j.issn.1002-8331.2010.36.060
文章编号：1002-8331（2010）36-0216-03
文献标识码：Ａ
中图分类号：TP391
作者简介：许婷，硕士研究生，主要研究方向为图形变形算法。收稿日期：2009-04-22
修回日期：
2009-07-13
216万方数据