【作者】 刘光惠；

【导师】 陈传波；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2007， 博士

【摘要】 作为计算机动画的主要手段,渐变(morphing或metamorphosis)技术近年来成为研究热点。渐变技术除应用于计算机动画外,在工业造型设计、虚拟现实、科学计算可视化、电影特技制作等领域都有着广泛的应用。渐变研究分为基于对象空间和基于图像的渐变研究两大分支。平面多边形渐变作为物体渐变的重要组成部分,受到研究者们的广泛关注。已有的平面多边形渐变算法大都有一定的局限,且普遍存在计算量大的问题。因此,针对对象空间的二维渐变展开研究,旨在提高渐变算法的适用性和在提高渐变质量的同时减少计算量,为实现对象空间的自然渐变开辟道路。如何在渐变过程中避免多边形边界自交及如何较好地保持多边形内在几何属性的均匀变化是两个具有挑战性的渐变研究问题。Surazhsky等首次给出基于同构三角剖分的可避免自交的多边形渐变算法,然而为进行相同凸边界的同构三角剖分需要大量的辅助点,在始末对象形状差异较大的情况下更是如此,且渐变效果未必令人满意。其后,保凸渐变算法的提出固然能够减少一定数量的辅助点,但计算量仍然较大。为最大限度地利用可避免自交的渐变方法的优点,确定采用基于同构三角剖分的渐变算法,对减少渐变计算量和提高渐变质量两方面均进行了研究。为进一步减少同构三角剖分所需的辅助点数,给出改进的相似同构三角剖分算法,对基于凹顶点凸分解的同构三角剖分算法进行了改进。对基于顶点可见性的凹多边形快速凸分解算法中所涉及的多边形中给定点的可见多边形的求解、给定顶点间的最短链路的求解等关键问题进行修改和完善。提出基于相似同构剖分的混合渐变算法,在减少渐变计算量的同时获得较为自然的渐变效果。提出以保留对象的视觉特征为目的的基于遗传算法的多边形近似算法来近似始末对象的轮廓,为获得自然渐变效果打下基础。采用指定对应起始点的方法对始末多边形进行对应,提高渐变方法的适用性。为加速和化简最简始末多边形至其放大凸包的同构三角剖分,分别提出了新的凸包算法和新的求核算法来加速放大凸包的求解,解决放大凸包边界新增顶点的位置调整问题。为提高渐变质量,提出几何向导的渐变算法,该算法在保持多边形内在几何属性的均匀变化方面要优于Surazhsky等提出的可控制的凸组合渐变算法和内在渐变算法。实验表明,基于相似同构三角剖分的混合渐变算法不仅计算量小,即使是在源、目标对象形状差异较大的情况下仍然能够得到较好的渐变效果。混合渐变算法所表现出的较强的适用性和时效性,为对象空间自然渐变的进一步研究打下坚实的基础。更多还原

【Abstract】 As one of the key techniques for computer animation, morphing technique has attracted much attention in research recently. Despite of computer animation, morphing technique has also been widely applied to areas such as industrial modeling, virtual reality, science computation visualization, film stunt and so on.There are two main branches of morphing research, one is based on object space, and the other is based on images. The morphing of planar polygon is an important component of object morphing, which is also a hotspot. A lot of approaches have been proposed for morphing planar polygon, but most of them have a certain limits and hard computational loads. Therefore, this paper makes researches on two-dimensional morphing of object space, in order to improve the applicability and to get more natural morphing result while reducing the computational work needed for metamorphosis.In the morphing process, how to make edge self-intersection-free and how to preserve the geometrical properties of the intermediate states are two challenges. Surazhsky and his colleagues first gave their guaranteed intersection-free polygon morphing approach based on convex combination. However, to get the compatible triangulations in a common convex boundary is time-consuming, especially when the shapes of source and target object are quite different, and usually the morphing result is not satisfied. Although the convexity-preserving metamorphosis method proposed later has further reduced the number of Steiner points needed for compatible triangulation, the computational work needed for metamorphosis is still hard. In order to get the benefit of intersection-free polygon morphing method furthest, the morphing approach based on compatible triangulation is determined to be adopted. Researches both for reducing the computational work and improving the quality of morphing have been done in this paper.In order to reduce the number of Steiner points, an improved similarly compatible triangulation method is proposed, and the compatible triangulation method based on polygon convex decomposition is improved. The improvements for both the computation of visible polygon for given point in a simple polygon and the minimum link distance path between given vertex pair in a simple polygon have been made, which are used in the fast polygon decomposition algorithm based on point visibility. A hybrid morphing approach has been proposed to reduce the computation load and get more natural morphing effects.A polygonal approximation approach based on Genetic Algorithm (GA) is proposed, whose aim is to preserve the visual features of contours of source and target objects, and help for getting more natural morphing effects. By appointing the starting correspondent vertex pair for solving the correspondence problem, the applicability of the morphing method has been strengthened. A new convex hull algorithm and a new kernel algorithm have been proposed to speed up the computation of the convex hull and simplify the adjustment to locations of the newly added Steiner points on boundaries of the magnified convex hulls respectively. In order to improve the quality of morphing, a geometrically guided morphing approach has been presented, which preserves the geometrical properties of the intermediate polygon more uniformly than controllable convex combination morphing and intrinsic morphing approaches proposed by Surazhsky and his partners. Through experiments, it is verified that the hybrid morphing approach based on similarly compatible triangulation not only has low computational complexity, but also could get natural morphing effects even if the shapes of source and target object are quite different. The stronger applicability and higher efficiency of the hybrid morphing approach have made a massive basis for further researches on natural morphing of object space.更多还原