对象空间的自然渐变技术研究
|
摘要
作为计算机动画的主要手段,渐变(morphing或metamorphosis)技术近年来成为研究热点。渐变技术除应用于计算机动画外,在工业造型设计、虚拟现实、科学计算可视化、电影特技制作等领域都有着广泛的应用。
渐变研究分为基于对象空间和基于图像的渐变研究两大分支。平面多边形渐变作为物体渐变的重要组成部分,受到研究者们的广泛关注。已有的平面多边形渐变算法大都有一定的局限,且普遍存在计算量大的问题。因此,针对对象空间的二维渐变展开研究,旨在提高渐变算法的适用性和在提高渐变质量的同时减少计算量,为实现对象空间的自然渐变开辟道路。
如何在渐变过程中避免多边形边界自交及如何较好地保持多边形内在几何属性的均匀变化是两个具有挑战性的渐变研究问题。Surazhsky等首次给出基于同构三角剖分的可避免自交的多边形渐变算法,然而为进行相同凸边界的同构三角剖分需要大量的辅助点,在始末对象形状差异较大的情况下更是如此,且渐变效果未必令人满意。其后,保凸渐变算法的提出固然能够减少一定数量的辅助点,但计算量仍然较大。为最大限度地利用可避免自交的渐变方法的优点,确定采用基于同构三角剖分的渐变算法,对减少渐变计算量和提高渐变质量两方面均进行了研究。为进一步减少同构三角剖分所需的辅助点数,给出改进的相似同构三角剖分算法,对基于凹顶点凸分解的同构三角剖分算法进行了改进。对基于顶点可见性的凹多边形快速凸分解算法中所涉及的多边形中给定点的可见多边形的求解、给定顶点间的最短链路的求解等关键问题进行修改和完善。提出基于相似同构剖分的混合渐变算法,在减少渐变计算量的同时获得较为自然的渐变效果。
提出以保留对象的视觉特征为目的的基于遗传算法的多边形近似算法来近似始末对象的轮廓,为获得自然渐变效果打下基础。采用指定对应起始点的方法对始末多边形进行对应,提高渐变方法的适用性。为加速和化简最简始末多边形至其放大凸包的同构三角剖分,分别提出了新的凸包算法和新的求核算法来加速放大凸包的求解,解决放大凸包边界新增顶点的位置调整问题。为提高渐变质量,提出几何向导的渐变算法,该算法在保持多边形内在几何属性的均匀变化方面要优于Surazhsky等提出的可控制的凸组合渐变算法和内在渐变算法。实验表明,基于相似同构三角剖分的混合渐变算法不仅计算量小,即使是在源、目标对象形状差异较大的情况下仍然能够得到较好的渐变效果。混合渐变算法所表现出的较强的适用性和时效性,为对象空间自然渐变的进一步研究打下坚实的基础。
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.
渐变研究分为基于对象空间和基于图像的渐变研究两大分支。平面多边形渐变作为物体渐变的重要组成部分,受到研究者们的广泛关注。已有的平面多边形渐变算法大都有一定的局限,且普遍存在计算量大的问题。因此,针对对象空间的二维渐变展开研究,旨在提高渐变算法的适用性和在提高渐变质量的同时减少计算量,为实现对象空间的自然渐变开辟道路。
如何在渐变过程中避免多边形边界自交及如何较好地保持多边形内在几何属性的均匀变化是两个具有挑战性的渐变研究问题。Surazhsky等首次给出基于同构三角剖分的可避免自交的多边形渐变算法,然而为进行相同凸边界的同构三角剖分需要大量的辅助点,在始末对象形状差异较大的情况下更是如此,且渐变效果未必令人满意。其后,保凸渐变算法的提出固然能够减少一定数量的辅助点,但计算量仍然较大。为最大限度地利用可避免自交的渐变方法的优点,确定采用基于同构三角剖分的渐变算法,对减少渐变计算量和提高渐变质量两方面均进行了研究。为进一步减少同构三角剖分所需的辅助点数,给出改进的相似同构三角剖分算法,对基于凹顶点凸分解的同构三角剖分算法进行了改进。对基于顶点可见性的凹多边形快速凸分解算法中所涉及的多边形中给定点的可见多边形的求解、给定顶点间的最短链路的求解等关键问题进行修改和完善。提出基于相似同构剖分的混合渐变算法,在减少渐变计算量的同时获得较为自然的渐变效果。
提出以保留对象的视觉特征为目的的基于遗传算法的多边形近似算法来近似始末对象的轮廓,为获得自然渐变效果打下基础。采用指定对应起始点的方法对始末多边形进行对应,提高渐变方法的适用性。为加速和化简最简始末多边形至其放大凸包的同构三角剖分,分别提出了新的凸包算法和新的求核算法来加速放大凸包的求解,解决放大凸包边界新增顶点的位置调整问题。为提高渐变质量,提出几何向导的渐变算法,该算法在保持多边形内在几何属性的均匀变化方面要优于Surazhsky等提出的可控制的凸组合渐变算法和内在渐变算法。实验表明,基于相似同构三角剖分的混合渐变算法不仅计算量小,即使是在源、目标对象形状差异较大的情况下仍然能够得到较好的渐变效果。混合渐变算法所表现出的较强的适用性和时效性,为对象空间自然渐变的进一步研究打下坚实的基础。
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.
引文
[1] LEE A W F, Dobkin D, Sweldens W, et al. Multiresolution Mesh Morphing. In SIGGRAPH '99 Proceedings, 1999. 343~350
[2] Kent J R, Carlson W E, Parent R E. Shape Transformation for Polyhedral Objects. In SIGGRAPH '92 Proceedings, 1992. 26(2): 47~54
[3] Alexa M. Merging polyhedral shapes with scattered features. The Visual Computer, 2000,16 (1): 26~37
[4] Cohen S, Elber G., Yehuda R. Matching of freeform curves. Computer Aided Design, 1997, Vo1.29, No.5: 369~378
[5] Sederberg T W, Greenwood E. A physically based approach to 2-D shape blending. In Proceedings of SIGGRAPH 92, Computer Graphics, 1992, 26(2): 25~34
[6] Johan H, Koiso Y, Nishita T. Morphing Using Curves and Shape Interpolation Techniques. In Proceedings of Pacific Graphics 2000, 8th Pacific Conference on Computer Graphics and Application, 2000, 348~358
[7] Jiang X Y, Bunke H, Abegglen K, et al. Curve Morphing by Weighted Mean of strings. In Proceedings of the Sixteenth Conference on Pattern Recognition (ICPR 2002), IEEE Press, 2002. 4: 192~195
[8] Wagner R A, Fischer M J. The String-to-String correction problem. Journal of the ACM, 1974, 21(1): 168~173
[9] Bunke H, Jiang X, Abegglen K, et al. On the weighted mean of a pair of strings. Pattern Analysis and Applications, 2002, 5: 23~30
[10] Liu L G, Wang G P, Zhang B, et al. Perceptually Based Approach for Planar Shape Morphing. In Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (PG’04), 6-8 Oct, 2004, 111~120
[11] Chetverikov D, Szabo Z. A simple and efficient algorithm for detection of high curvature points in planar curves. In Proc. 23rd Workshop of the Austrian Pattern Recognition Group, 1999.175~184
[12] Levy B, Mallet J L. Non-distorted texture mapping for sheared triangulated meshes. In Proceedings of the 25th annual conference on Computer graphics and interactivetechniques: NY USA, ACM Press, July 1998. 343~352
[13] Tutte W T. How to draw a graph. In Proc London Mathematical Society, 1963.13: 743~768
[14] Floater M S. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 1997,14(3):231~250
[15] Kanai T, Suzuki H, Kimura F. 3D Geometric metamorphosis based on harmonic map. The Visual Computer, 1998, 14(4): 166~176
[16] Pinkall U, Polthier K. Computing discrete minimal surfaces and their conjugates. Experimanetal Mathematics, 1993, 2(1): 15~36
[17] Polthier K. Conjugate harmonic maps and minimal surfaces. Technical Report Preprint No. 446, TU Berlin, SFB 288, 2000.
[18] Gregory A, State A, Ming C, et al. Interactive surface decomposition for polyhedral morphing. The Visual Computer, 1999,15(9): 453~470
[19] Kent J, Parent R, Carlson W E. Establishing correspondences by topological merging: A new approach to 3-d shape transformation. In Graphics Interface'91, June 1991, 271~278
[20] Shapiro A, Tal A. Polyhedron realization for shape transformation. The Visual Computer, 1998, 14(8-9): 429~444
[21] DeCarlo D, Gallier J. Topological evolution of surfaces. In Proceedings of Graphics Interface'96, Toronto, Canada: 1996, 194~203
[22] Beier T, Neely S. Feature-based Image Metamorphosis. In SIGGRAPH'92 Proceedings, 1992, 35~42
[23] Kaul A, Riossignac J. Solid interpolating deformations: construction and animation of PIPS. In: Post, F. H. and Barth, W., eds., Proceedings of Eurographics'91. Elsevier Science Pulishers, B. V., 1991.
[24] Sederberg T W, Gao P, Wang G, et al. 2-D shape blending: an intrinsic solution to the vertex path problem. In Proceedings of SIGGRAPH'93, ACM, 1993, 27: 15~18
[25]王国瑾,汪国昭,郑建民.《计算机辅助几何设计》,施普林格出版社,高等教育出版社, 2001.
[26] Shapira M, Rappoport A. Shape blending using the star-skeleton representation.IEEE Transactions on Computer Graphics and Application, 1995, 15: 44~51
[27] Goldstein E, Gotsman C. Polygon Morphing Using a Multiresolution Representation. In Graphics Interface’95, 1995, 247~254
[28] Carmel E, Cohen-Or D. Warp-guided object-space morphing. The Visual Computer, 1997,13: 465~478
[29] Cohen-Or D, Levin D, Solomovoci A. Three-dimensional distance field metamorphosis. ACM Transactions on G raphics, 1998,17 (2):116~141
[30] Alexa M, Cohen-Or D, Levin D. As-rigid-as-possible shape interpolation. In Proceedings of SIGGRAPH'2000, Computer Graphics, 2000, 157~163
[31] Surazhsky T, Elber G. Metamorphosis of Planar Parametric Curves via Curvature Interpolation. International Journal of Shape Modeling, 2002, 8(2): 201~216
[32] Zhang Y F, Huang Y. Wavelet Shape blending. The Visual Computer, 2000,16 (2): 106~115
[33] Floater M S, Gotsman C. How to morph tilings injectively. Journal of Computational and Applied Mathematics, 1999, 101:117~129
[34] Surazhsky V, Gotsman C. Guaranteed intersection-free polygon morphing. Computers and Graphics, 2001, 25(1): 67~75
[35] Surazhsky V, Gotsman C. Controllable morphing of compatible planar triangulations. ACM Transactions on Graphics, 2001,20(4): 203~231
[36] Surazhsky V, Gotsman C. Morphing stick figures using optimized compatible triangulations. In Proceedings of Pacific Graphics, Oct.2001, 40~49
[37] Surazhsky V, Gotsman C. Intrinsic Morphing of Compatible Triangulations. International Journal of Shape Modeling, 2003, Vol. 9, No. 2,191~201
[38]宋伟杰.同构平面三角网格和平面多边形渐变的研究: [硕士学位论文].保存地点:西北工业大学图书馆, 2004.
[39]张则剑.同构三角网格的渐变研究: [硕士学位论文].保存地点:西北工业大学图书馆, 2005.
[40]危才华.平面多边形渐变算法研究: [硕士学位论文].保存地点:西北工业大学图书馆, 2006.
[41] Erten C, Kobourov S G, Pitta C. Morphing Planar Graphs. Symposium onComputational Geometry, 2004. 451~452
[42] Erten C, Kobourov S G, Pitta C. Intersection-Free Morphing of Planar Graphs, In Proc. 11th International Symposium on Graph Drawing (GD), LNCS 2912, 2003. 320~332
[43] G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. Technical Report 98-036, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, 1998.
[44] Lin P H, Lee T Y. A Fast 2D Shape Interpolation Technique. Lecture Notes on Computer Science (LNCS 3482) volume 3482, Springer-Verlag, 2005.1050~1059
[45] Hahmann S, Bonneau G P, Caramiaux B, et al. Multiresolution morphing for planar curves. Computing, 2007, 79, 197~209
[46] Adams J A. The intrinsic method for curve definition. Computer Aided Design, 1975, 7(4): 243~249
[47] Dunham J G. Optimum uniform piecewise linear approximation of planar curves, IEEE Trans. on PAMI, Jan, 1986, 8 (1): 67~75
[48] Ray B K, Ray K S. An algorithm for detecting dominant points and polygonal approximation of digitized curves, Pattern Recognition Letters, 1992,13: 849~856
[49] Salotti M. An efficient algorithm for the optimal polygonal approximation of digitized curves, Pattern Recognition Letters, 2001, 22: 215~221
[50] Perez J C, Vidal E. Optimum polygonal approximation of digitized curves, Pattern Recognition Letters, 1994,15: 743~750
[51] Pikaz A, Dinstein I. Optimal polygonal approximation of digital curves, Pattern Recognition, 1995, 28 (3): 373~379
[52] Marji M, Siy P. Polygonal representation of digital planar curves t through dominant point detection—a nonparametric algorithm, Pattern Recognition, 2004, 37: 2113~2130
[53] Marston R E, Shih J C, Polygonal approximation of outlines by scale-based dominant point detection. In Fifth International Conference on Image Processing and its Applications, Jul 1995, 350~354
[54] Alkaabi S, Deravi F. Candidate pruning for fast corner detection, Electronics Letters, 2004, 40 (1)
[55] Chetverikov D, Szabo Z. A simple and efficient algorithm for detection of high curvature points in planar curves. In Proc. 23rd Workshop of the Austrian Pattern Recognition Group, 1999.175~184
[56] Lin H C, Wang L L, Yang S N. Fast heuristics for polygonal approximation of a 2D shape boundary, Signal Processing, 1997, 60: 235~241
[57] Yin P Y. A discrete particle swarm algorithm for optimal polygonal approximation of digital curves. J. Vis. Commun. Image R, 2004,15: 241~260
[58] Huang S C, Sun Y N. Polygonal approximation using genetic algorithm. In Proceedings of IEEE International Conference on Evolutionary Computation, May, 1996, 469~474
[59] Tsai C T, Liaw C Y, Chen M P, et al. Polygonal approximation using an annealed chaotic Hopfield network. In 9th International Workshop on Cellular Neural Networks and Their Applications, May, 2005, 122 ~125
[60] Choi JG, Lee S W, Kang H S. Dynamic programming approach to optimal vertex selection for polygon-based shape approximation. In IEE Proc.-Vis. Image Signal Process, October, 2003, 150 (5): 287~291
[61] Yin P Y. Ant colony search algorithms for optimal polygonal approximation of plane curves. Pattern Recognition, 2003, 36: 1783~1797
[62] Yin P Y. A new method for polygonal approximation using genetic algorithms. Pattern Recognition Letters, 1998,19: 1017~1026
[63] Ho S Y, Chen Y C. An efficient evolutionary algorithm for accurate polygonal approximation. Pattern Recognition, 2001, 34: 2305~2317
[64] Sarkar B, Singh L K, Sarkar D. Approximation of digital curves with line segments and circular arcs using genetic algorithms. Pattern Recognition Letters, 2003, 24: 2585~2595
[65] Tsai Y H. Fast polygonal approximation based on genetic algorithms. In 1st IEEE/ACIS International Workshop on Component-Based Software Engineering, Software Architecture and Reuse, July, 2006. 322~326
[66] Liu G H, Chen C B. A new approach for polygonal approximation of shape contours using genetic algorithm. In the 2nd IEEE Conference on Industrial Electroics and Applications, 2007.
[67] Goldberg D E. Genetic Algorithms: Search, Optimization and Machine Learning. MA: Addison-Wesley, 1989.
[68] Feschet F. Fast guaranteed polygonal approximations of closed digital curves. In SCIA 2005, LNCS 3540, 2005, 910~919
[69] Pavlidis T. Algorithms for Graphics and Image Processing. Rockville, MD: Computer Science Press, 1982. 281~292
[70] Teh C H. On the detection of dominant points on digital curves. IEEE Trans. on PAMI, 1989, 11(8): 859~872
[71] Huang S C, Sun Y N. Determination of Optimal Polygonal Approximation Using Genetic Algorithms. In IEEE International Conference on Evolutionary, May,1998, 24~129
[72] Saalfeld A. Joint triangulations and triangulation maps. In Proceedings of Third Annual ACM Symposium on computational Geometry, 1987,195~204
[73] Aronov B, Seidel R,Souvaine D L. On compatibletriangulations of simple polygons. Computational Geometry: Theory and Applications, 1993, 3: 27~35
[74] Yan Ke. An Efficient Algorithm for Link Distance Problems. In the fifth annual symposium on Computational geometry, 1989. 69~78
[75] Suri S. On some link distance problems in a simple polygon. IEEE Journal of Robotics and Automation, 1990, 6(1): l08~113
[76]刘海涛.相容三角剖分及网格优化的算法研究: [硕士学位论文].保存地点:浙江大学图书馆, 2006.
[77] Surazhsky V,Gotsman C. High Quality Compatible Triangulations. Engineering with Computers, 2004, 20 (2):147~156
[78] Kranakis E, Urrutia J. Isomorphic triangulations with small number of Steiner points. International Journal of Computational Geometry and Applications, 1999, 9(2):171~180
[79] Gupta H, Wenger R. Constructing piecewise linear homeomorphisms of simple polygons. Journal of Algorithms, 1997, 22(1): 142~157
[80] Seidel R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Computational Geometry:Theory and Applications, 1991, 1(1): 51~64
[81]肖忠晖,卢振荣,张谦.简单多边形凸单元剖分的编码算法.计算机学报, 1996, 19 (6): 477~481
[82]金文华,何涛,唐卫清等.简单多边形可见点问题的快速求解算法.计算机学报, 1999, 22 (3): 275~282
[83] Fáry I. On straight line representation of planar graphs. Acta Univ. Szeged Sect. Sci. Math. 1948. 11: 229~233
[84] Tutte W T. How to draw a graph. Proc. London Math. Soc. 1963, 13: 743 ~768
[85] Floater M S. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 1997,14(3):231~250
[86] Floater M S. Mean Value Coordinates. Computer Aided Geometric Design, 2003, (20): 19~27
[87] Liu G H, Chen C B. Geometrically Guided Morphing of Compatible Triangulations. In ICYCS'05, 2005, 461~466.
[88] Van Der Vorst A H. BI-CGSTAB: A fast and smoothly converging variant of BI-CG for the solution of nonsymmtric linear systems. SIAM Jounal of Sci. Stat. Comput. 1992, 13(2): 631-644
[89] O′Rourke J. Computational Geometry in C (2nd Edition). Cambridge: Cambridge University Press, 1998
[90] Sklansky J. Measuring Concavity on a Rectangular Mosaic. IEEE Transactions on Computing, 1972, C-21(12):1355~1364
[91] McCallum D, Davis D. A linear algorithm for finding the convex hull of a simple polygon, Info. Proc. Letters 9, 1979,201~206
[92] Yao C A. A lower bound to finding convex hulls. Journal of the ACM, 1981, 28 (4):780~787
[93] Lee T D. On finding the convex hull of a simple polygon. Int'l J. Comp. & Info, 1983, 12 (2): 87~98
[94] Kirkpatrick D G, Seidel R. The ultimate planar convex hull algorithm? SIAM Journal of Computers, 1986, 15 (1): 287~299
[95] Melkman A. On-line construction of the convex hull of a simple polygon. Info. Proc.Letters 25, 1987, 11~12
[96] Binay K, Bhattacharya, Sandeep S. On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm. Journal of Algorithms, 1997, 25: 177~193
[97]崔国华,洪凡,余祥宣.确定平面点集凸包的一类最优算法.计算机学报, 1997, 20(4): 330~334
[98]金文华,何涛,刘小平等.基于有序简单多边形的平面点集凸包快速求取算法.计算机学报, 1998, 21(6): 533~539
[99]王志强,洪嘉振,肖立瑾.平面点集凸包的最优实时算法.计算机学报, 1998, 21(增刊): 351~356
[100]刘金义.关于求平面点集凸包的一个O(n)时间算法的商榷.计算机学报, 2002, 25(6): 670~672
[101]刘光惠,陈传波.求解简单多边形和平面点集凸包的新算法.计算机科学, 2007年第12期
[102]Liu G H, Chen C B. A New Algorithm for Computing the Convex Hull of a Planar Point Set. Journal of Zhejiang University SCIENCE A, 2007, 8(8): 1210~1217
[103]Babikov M, Souvaine DL, Wenger R. Constructing piecewise linear homeomorphisms of polygons with holes. In Proceedings of Ninth Canadian Conference on Computational Geometry, 1997.
[104]Preparata P F, Shamos I M. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.
[105]Lee T D, Preparata P F. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM, 1979, 26(3): 415~421
[106]周培德.确定任意多边形的核的算法.工程图学学报, 1995, 2: 28~30
[107]王钲旋,徐长青,庞云阶.判断简单多边形的核是否为空的一个快速算法.计算机辅助设计与图形学学报, 2000, 12(9): 656~659
[108]陈炳发,廖文和.自适应扫描线的简单多边形核填充算法.南京航空航天大学学报, 2004, 36(4): 477~481
[109]刘光惠,陈传波,吕泽华.一种求解简单多边形核的新算法.华中科技大学学报,2007年第12期
[110]李伟青.凸多边形窗口线裁剪的折半查找算法.计算机辅助设计与图形学学报, 2005, (17)5: 962~965
[2] Kent J R, Carlson W E, Parent R E. Shape Transformation for Polyhedral Objects. In SIGGRAPH '92 Proceedings, 1992. 26(2): 47~54
[3] Alexa M. Merging polyhedral shapes with scattered features. The Visual Computer, 2000,16 (1): 26~37
[4] Cohen S, Elber G., Yehuda R. Matching of freeform curves. Computer Aided Design, 1997, Vo1.29, No.5: 369~378
[5] Sederberg T W, Greenwood E. A physically based approach to 2-D shape blending. In Proceedings of SIGGRAPH 92, Computer Graphics, 1992, 26(2): 25~34
[6] Johan H, Koiso Y, Nishita T. Morphing Using Curves and Shape Interpolation Techniques. In Proceedings of Pacific Graphics 2000, 8th Pacific Conference on Computer Graphics and Application, 2000, 348~358
[7] Jiang X Y, Bunke H, Abegglen K, et al. Curve Morphing by Weighted Mean of strings. In Proceedings of the Sixteenth Conference on Pattern Recognition (ICPR 2002), IEEE Press, 2002. 4: 192~195
[8] Wagner R A, Fischer M J. The String-to-String correction problem. Journal of the ACM, 1974, 21(1): 168~173
[9] Bunke H, Jiang X, Abegglen K, et al. On the weighted mean of a pair of strings. Pattern Analysis and Applications, 2002, 5: 23~30
[10] Liu L G, Wang G P, Zhang B, et al. Perceptually Based Approach for Planar Shape Morphing. In Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (PG’04), 6-8 Oct, 2004, 111~120
[11] Chetverikov D, Szabo Z. A simple and efficient algorithm for detection of high curvature points in planar curves. In Proc. 23rd Workshop of the Austrian Pattern Recognition Group, 1999.175~184
[12] Levy B, Mallet J L. Non-distorted texture mapping for sheared triangulated meshes. In Proceedings of the 25th annual conference on Computer graphics and interactivetechniques: NY USA, ACM Press, July 1998. 343~352
[13] Tutte W T. How to draw a graph. In Proc London Mathematical Society, 1963.13: 743~768
[14] Floater M S. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 1997,14(3):231~250
[15] Kanai T, Suzuki H, Kimura F. 3D Geometric metamorphosis based on harmonic map. The Visual Computer, 1998, 14(4): 166~176
[16] Pinkall U, Polthier K. Computing discrete minimal surfaces and their conjugates. Experimanetal Mathematics, 1993, 2(1): 15~36
[17] Polthier K. Conjugate harmonic maps and minimal surfaces. Technical Report Preprint No. 446, TU Berlin, SFB 288, 2000.
[18] Gregory A, State A, Ming C, et al. Interactive surface decomposition for polyhedral morphing. The Visual Computer, 1999,15(9): 453~470
[19] Kent J, Parent R, Carlson W E. Establishing correspondences by topological merging: A new approach to 3-d shape transformation. In Graphics Interface'91, June 1991, 271~278
[20] Shapiro A, Tal A. Polyhedron realization for shape transformation. The Visual Computer, 1998, 14(8-9): 429~444
[21] DeCarlo D, Gallier J. Topological evolution of surfaces. In Proceedings of Graphics Interface'96, Toronto, Canada: 1996, 194~203
[22] Beier T, Neely S. Feature-based Image Metamorphosis. In SIGGRAPH'92 Proceedings, 1992, 35~42
[23] Kaul A, Riossignac J. Solid interpolating deformations: construction and animation of PIPS. In: Post, F. H. and Barth, W., eds., Proceedings of Eurographics'91. Elsevier Science Pulishers, B. V., 1991.
[24] Sederberg T W, Gao P, Wang G, et al. 2-D shape blending: an intrinsic solution to the vertex path problem. In Proceedings of SIGGRAPH'93, ACM, 1993, 27: 15~18
[25]王国瑾,汪国昭,郑建民.《计算机辅助几何设计》,施普林格出版社,高等教育出版社, 2001.
[26] Shapira M, Rappoport A. Shape blending using the star-skeleton representation.IEEE Transactions on Computer Graphics and Application, 1995, 15: 44~51
[27] Goldstein E, Gotsman C. Polygon Morphing Using a Multiresolution Representation. In Graphics Interface’95, 1995, 247~254
[28] Carmel E, Cohen-Or D. Warp-guided object-space morphing. The Visual Computer, 1997,13: 465~478
[29] Cohen-Or D, Levin D, Solomovoci A. Three-dimensional distance field metamorphosis. ACM Transactions on G raphics, 1998,17 (2):116~141
[30] Alexa M, Cohen-Or D, Levin D. As-rigid-as-possible shape interpolation. In Proceedings of SIGGRAPH'2000, Computer Graphics, 2000, 157~163
[31] Surazhsky T, Elber G. Metamorphosis of Planar Parametric Curves via Curvature Interpolation. International Journal of Shape Modeling, 2002, 8(2): 201~216
[32] Zhang Y F, Huang Y. Wavelet Shape blending. The Visual Computer, 2000,16 (2): 106~115
[33] Floater M S, Gotsman C. How to morph tilings injectively. Journal of Computational and Applied Mathematics, 1999, 101:117~129
[34] Surazhsky V, Gotsman C. Guaranteed intersection-free polygon morphing. Computers and Graphics, 2001, 25(1): 67~75
[35] Surazhsky V, Gotsman C. Controllable morphing of compatible planar triangulations. ACM Transactions on Graphics, 2001,20(4): 203~231
[36] Surazhsky V, Gotsman C. Morphing stick figures using optimized compatible triangulations. In Proceedings of Pacific Graphics, Oct.2001, 40~49
[37] Surazhsky V, Gotsman C. Intrinsic Morphing of Compatible Triangulations. International Journal of Shape Modeling, 2003, Vol. 9, No. 2,191~201
[38]宋伟杰.同构平面三角网格和平面多边形渐变的研究: [硕士学位论文].保存地点:西北工业大学图书馆, 2004.
[39]张则剑.同构三角网格的渐变研究: [硕士学位论文].保存地点:西北工业大学图书馆, 2005.
[40]危才华.平面多边形渐变算法研究: [硕士学位论文].保存地点:西北工业大学图书馆, 2006.
[41] Erten C, Kobourov S G, Pitta C. Morphing Planar Graphs. Symposium onComputational Geometry, 2004. 451~452
[42] Erten C, Kobourov S G, Pitta C. Intersection-Free Morphing of Planar Graphs, In Proc. 11th International Symposium on Graph Drawing (GD), LNCS 2912, 2003. 320~332
[43] G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. Technical Report 98-036, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, 1998.
[44] Lin P H, Lee T Y. A Fast 2D Shape Interpolation Technique. Lecture Notes on Computer Science (LNCS 3482) volume 3482, Springer-Verlag, 2005.1050~1059
[45] Hahmann S, Bonneau G P, Caramiaux B, et al. Multiresolution morphing for planar curves. Computing, 2007, 79, 197~209
[46] Adams J A. The intrinsic method for curve definition. Computer Aided Design, 1975, 7(4): 243~249
[47] Dunham J G. Optimum uniform piecewise linear approximation of planar curves, IEEE Trans. on PAMI, Jan, 1986, 8 (1): 67~75
[48] Ray B K, Ray K S. An algorithm for detecting dominant points and polygonal approximation of digitized curves, Pattern Recognition Letters, 1992,13: 849~856
[49] Salotti M. An efficient algorithm for the optimal polygonal approximation of digitized curves, Pattern Recognition Letters, 2001, 22: 215~221
[50] Perez J C, Vidal E. Optimum polygonal approximation of digitized curves, Pattern Recognition Letters, 1994,15: 743~750
[51] Pikaz A, Dinstein I. Optimal polygonal approximation of digital curves, Pattern Recognition, 1995, 28 (3): 373~379
[52] Marji M, Siy P. Polygonal representation of digital planar curves t through dominant point detection—a nonparametric algorithm, Pattern Recognition, 2004, 37: 2113~2130
[53] Marston R E, Shih J C, Polygonal approximation of outlines by scale-based dominant point detection. In Fifth International Conference on Image Processing and its Applications, Jul 1995, 350~354
[54] Alkaabi S, Deravi F. Candidate pruning for fast corner detection, Electronics Letters, 2004, 40 (1)
[55] Chetverikov D, Szabo Z. A simple and efficient algorithm for detection of high curvature points in planar curves. In Proc. 23rd Workshop of the Austrian Pattern Recognition Group, 1999.175~184
[56] Lin H C, Wang L L, Yang S N. Fast heuristics for polygonal approximation of a 2D shape boundary, Signal Processing, 1997, 60: 235~241
[57] Yin P Y. A discrete particle swarm algorithm for optimal polygonal approximation of digital curves. J. Vis. Commun. Image R, 2004,15: 241~260
[58] Huang S C, Sun Y N. Polygonal approximation using genetic algorithm. In Proceedings of IEEE International Conference on Evolutionary Computation, May, 1996, 469~474
[59] Tsai C T, Liaw C Y, Chen M P, et al. Polygonal approximation using an annealed chaotic Hopfield network. In 9th International Workshop on Cellular Neural Networks and Their Applications, May, 2005, 122 ~125
[60] Choi JG, Lee S W, Kang H S. Dynamic programming approach to optimal vertex selection for polygon-based shape approximation. In IEE Proc.-Vis. Image Signal Process, October, 2003, 150 (5): 287~291
[61] Yin P Y. Ant colony search algorithms for optimal polygonal approximation of plane curves. Pattern Recognition, 2003, 36: 1783~1797
[62] Yin P Y. A new method for polygonal approximation using genetic algorithms. Pattern Recognition Letters, 1998,19: 1017~1026
[63] Ho S Y, Chen Y C. An efficient evolutionary algorithm for accurate polygonal approximation. Pattern Recognition, 2001, 34: 2305~2317
[64] Sarkar B, Singh L K, Sarkar D. Approximation of digital curves with line segments and circular arcs using genetic algorithms. Pattern Recognition Letters, 2003, 24: 2585~2595
[65] Tsai Y H. Fast polygonal approximation based on genetic algorithms. In 1st IEEE/ACIS International Workshop on Component-Based Software Engineering, Software Architecture and Reuse, July, 2006. 322~326
[66] Liu G H, Chen C B. A new approach for polygonal approximation of shape contours using genetic algorithm. In the 2nd IEEE Conference on Industrial Electroics and Applications, 2007.
[67] Goldberg D E. Genetic Algorithms: Search, Optimization and Machine Learning. MA: Addison-Wesley, 1989.
[68] Feschet F. Fast guaranteed polygonal approximations of closed digital curves. In SCIA 2005, LNCS 3540, 2005, 910~919
[69] Pavlidis T. Algorithms for Graphics and Image Processing. Rockville, MD: Computer Science Press, 1982. 281~292
[70] Teh C H. On the detection of dominant points on digital curves. IEEE Trans. on PAMI, 1989, 11(8): 859~872
[71] Huang S C, Sun Y N. Determination of Optimal Polygonal Approximation Using Genetic Algorithms. In IEEE International Conference on Evolutionary, May,1998, 24~129
[72] Saalfeld A. Joint triangulations and triangulation maps. In Proceedings of Third Annual ACM Symposium on computational Geometry, 1987,195~204
[73] Aronov B, Seidel R,Souvaine D L. On compatibletriangulations of simple polygons. Computational Geometry: Theory and Applications, 1993, 3: 27~35
[74] Yan Ke. An Efficient Algorithm for Link Distance Problems. In the fifth annual symposium on Computational geometry, 1989. 69~78
[75] Suri S. On some link distance problems in a simple polygon. IEEE Journal of Robotics and Automation, 1990, 6(1): l08~113
[76]刘海涛.相容三角剖分及网格优化的算法研究: [硕士学位论文].保存地点:浙江大学图书馆, 2006.
[77] Surazhsky V,Gotsman C. High Quality Compatible Triangulations. Engineering with Computers, 2004, 20 (2):147~156
[78] Kranakis E, Urrutia J. Isomorphic triangulations with small number of Steiner points. International Journal of Computational Geometry and Applications, 1999, 9(2):171~180
[79] Gupta H, Wenger R. Constructing piecewise linear homeomorphisms of simple polygons. Journal of Algorithms, 1997, 22(1): 142~157
[80] Seidel R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Computational Geometry:Theory and Applications, 1991, 1(1): 51~64
[81]肖忠晖,卢振荣,张谦.简单多边形凸单元剖分的编码算法.计算机学报, 1996, 19 (6): 477~481
[82]金文华,何涛,唐卫清等.简单多边形可见点问题的快速求解算法.计算机学报, 1999, 22 (3): 275~282
[83] Fáry I. On straight line representation of planar graphs. Acta Univ. Szeged Sect. Sci. Math. 1948. 11: 229~233
[84] Tutte W T. How to draw a graph. Proc. London Math. Soc. 1963, 13: 743 ~768
[85] Floater M S. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 1997,14(3):231~250
[86] Floater M S. Mean Value Coordinates. Computer Aided Geometric Design, 2003, (20): 19~27
[87] Liu G H, Chen C B. Geometrically Guided Morphing of Compatible Triangulations. In ICYCS'05, 2005, 461~466.
[88] Van Der Vorst A H. BI-CGSTAB: A fast and smoothly converging variant of BI-CG for the solution of nonsymmtric linear systems. SIAM Jounal of Sci. Stat. Comput. 1992, 13(2): 631-644
[89] O′Rourke J. Computational Geometry in C (2nd Edition). Cambridge: Cambridge University Press, 1998
[90] Sklansky J. Measuring Concavity on a Rectangular Mosaic. IEEE Transactions on Computing, 1972, C-21(12):1355~1364
[91] McCallum D, Davis D. A linear algorithm for finding the convex hull of a simple polygon, Info. Proc. Letters 9, 1979,201~206
[92] Yao C A. A lower bound to finding convex hulls. Journal of the ACM, 1981, 28 (4):780~787
[93] Lee T D. On finding the convex hull of a simple polygon. Int'l J. Comp. & Info, 1983, 12 (2): 87~98
[94] Kirkpatrick D G, Seidel R. The ultimate planar convex hull algorithm? SIAM Journal of Computers, 1986, 15 (1): 287~299
[95] Melkman A. On-line construction of the convex hull of a simple polygon. Info. Proc.Letters 25, 1987, 11~12
[96] Binay K, Bhattacharya, Sandeep S. On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm. Journal of Algorithms, 1997, 25: 177~193
[97]崔国华,洪凡,余祥宣.确定平面点集凸包的一类最优算法.计算机学报, 1997, 20(4): 330~334
[98]金文华,何涛,刘小平等.基于有序简单多边形的平面点集凸包快速求取算法.计算机学报, 1998, 21(6): 533~539
[99]王志强,洪嘉振,肖立瑾.平面点集凸包的最优实时算法.计算机学报, 1998, 21(增刊): 351~356
[100]刘金义.关于求平面点集凸包的一个O(n)时间算法的商榷.计算机学报, 2002, 25(6): 670~672
[101]刘光惠,陈传波.求解简单多边形和平面点集凸包的新算法.计算机科学, 2007年第12期
[102]Liu G H, Chen C B. A New Algorithm for Computing the Convex Hull of a Planar Point Set. Journal of Zhejiang University SCIENCE A, 2007, 8(8): 1210~1217
[103]Babikov M, Souvaine DL, Wenger R. Constructing piecewise linear homeomorphisms of polygons with holes. In Proceedings of Ninth Canadian Conference on Computational Geometry, 1997.
[104]Preparata P F, Shamos I M. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.
[105]Lee T D, Preparata P F. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM, 1979, 26(3): 415~421
[106]周培德.确定任意多边形的核的算法.工程图学学报, 1995, 2: 28~30
[107]王钲旋,徐长青,庞云阶.判断简单多边形的核是否为空的一个快速算法.计算机辅助设计与图形学学报, 2000, 12(9): 656~659
[108]陈炳发,廖文和.自适应扫描线的简单多边形核填充算法.南京航空航天大学学报, 2004, 36(4): 477~481
[109]刘光惠,陈传波,吕泽华.一种求解简单多边形核的新算法.华中科技大学学报,2007年第12期
[110]李伟青.凸多边形窗口线裁剪的折半查找算法.计算机辅助设计与图形学学报, 2005, (17)5: 962~965