Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (5): 1109-1122.doi: 10.1007/s11390-019-1963-3

Special Issue: Computer Graphics and Multimedia

• Computer Graphics and Multimedia • Previous Articles     Next Articles

CR-Morph: Controllable Rigid Morphing for 2D Animation

Wen-Wu Yang1, Member, CCF, Jing Hua1,2, Kun-Yang Yao1   

  1. 1 School of Computer and Information Engineering, Zhejiang Gongshang University, Hangzhou 310012, China;
    2 Department of Computer Science, Wayne State University, Michigan 48202, U.S.A
  • Received:2018-12-03 Revised:2019-07-24 Online:2019-08-31 Published:2019-08-31
  • About author:Wen-Wu Yang is currently an associate professor at the School of Computer and Information Engineering, Zhejiang Gongshang University, Hangzhou. Dr. Yang received his Ph.D. degree in computer science from the State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou, in 2009. His research interests include cartoon animation, motion capture and motion synthesis.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61003189, U1609215 and 61472363, and the US National Science Foundation under Grant Nos. 0915933, 0937586, and 1647200.

This paper presents a rigidity-preserving morphing technique that blends a pair of 2D shapes in a controllable manner. The morphing is controllable in two aspects:1) motion dynamics in the interpolation sequences can be effectively enhanced through an intuitive skeleton control and 2) not only the boundaries but also the interior features of the source and target shapes are precisely aligned during the morphing. We introduce a new compatible triangulation algorithm to decompose the source and target shapes into isomorphic triangles. Moreover, a robust and motion-controllable rigiditypreserving transformation scheme is proposed to blend the compatible triangulations, ultimately leading to a morphing sequence which is appearance-preserving and with the desired motion dynamics. Our approach constitutes a powerful and easy-to-use morphing tool for two-dimensional animation. We demonstrate its versatility, effectiveness and visual accuracy through a variety of examples and comparisons to prior work.

Key words: compatible triangulation; disc-based interpolation; rigid morphing; skeleton-based dynamics;

[1] Fekete J D, Bizouarn É, Cournarie É, Galas T, Taillefer F. TicTacToon:A paperless system for professional 2D animation. In Proc. the 22nd Annual Conference on Computer Graphics and Interactive Techniques, August 1995, pp.79-90.
[2] Yang W. Context-aware computer aided inbetweening. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(2):1049-1062.
[3] Beier T, Neely S. Feature-based image metamorphosis. In Proc. the 19th Annual Conference on Computer Graphics and Interactive Techniques, July 1992, pp.35-42.
[4] Lee S Y, Chwa K Y, Shin S Y. Image metamorphosis using snakes and free-form deformations. In Proc. the 22nd Annual Conference on Computer Graphics and Interactive Techniques, August 1995, pp.439-448.
[5] Wolberg G. Image morphing:A survey. The Visual Computer, 1998, 14(8/9):360-372.
[6] Fang H, Hart J C. Detail preserving shape deformation in image editing. ACM Transactions on Graphics, 2007, 26(3):Article No. 12.
[7] Glocker B, Komodakis N, Tziritas G, Navab N, Paragios N. Dense image registration through MRFs and efficient linear programming. Medical Image Analysis, 2008, 12(6):731-741.
[8] Liao J, Lima R S, Nehab D, Hoppe H, Sander P V, Yu J. Automating image morphing using structural similarity on a halfway domain. ACM Trans. Graph., 2014, 33(5):Article No. 168.
[9] Sederberg T W, Gao P, Wang G, Mu H. 2-D shape blending:An intrinsic solution to the vertex path problem. In Proc. the 20th Annual Conference on Computer Graphics and Interactive Techniques, August 1993, pp.15-18.
[10] Fu H, Tai C l, Au K C. Morphing with Laplacian coordinates and spatial-temporal texture. In Proc. the 13th Pacific Conference on Computer Graphics and Applications, October 2005, pp.100-102.
[11] Sumner R W, Zwicker M, Gotsman C, Popović J. Meshbased inverse kinematics. ACM Trans. Graph., 2005, 24(3):488-495.
[12] Xu D, Zhang H, Wang Q, Bao H. Poisson shape interpolation. In Proc. the 9th ACM Symposium on Solid and Physical Modeling, June 2005, pp.267-274.
[13] Alexa M, Cohen-Or D, Levin D. As-rigid-as-possible shape interpolation. In Proc. the 27th Annual Conference on Computer Graphics and Interactive Techniques, July 2000, pp.157-164.
[14] Hahmann S, Bonneau G P, Caramiaux B, Cornillac M. Multiresolution morphing for planar curves. Computing, 2007, 79(2/3/4):197-209.
[15] Yang W, Feng J. 2D shape morphing via automatic feature matching and hierarchical interpolation. Computers and Graphics, 2009, 33(3):414-423.
[16] Dym N, Shtengel A, Lipman Y. Homotopic morphing of planar curves. Computer Graphics Forum, 2015, 34(5):239-251.
[17] Tal A, Elber G. Image morphing with feature preserving texture. Computer Graphics Forum, 1999, 18(3):339-348.
[18] Floater M, Gotsman C. How to morph tilings injectively. Journal of Computational and Applied Mathematics, 1999, 101(1/2):117-129.
[19] Surazhsky V, Gotsman C. Intrinsic morphing of compatible triangulations. International Journal of Shape Modelling, 2003, 9(2):191-201.
[20] Baxter Ⅲ W, Barla P, Anjyo K. Rigid shape interpolation using normal equations. In Proc. the 6th International Symposium on Non-Photorealistic Animation and Rendering, June 2008, pp.59-64.
[21] Baxter Ⅲ W V, Barla P, Anjyo K. Compatible embedding for 2D shape animation. IEEE Transactions on Visualization and Computer Graphics, 2009, 15(5):867-879.
[22] Aronov B, Seidel R, Souvaine D. On compatible triangulations of simple polygons. Computational Geometry, 1993, 3:27-35.
[23] Surazhsky V, Gotsman C. High quality compatible triangulations. Engineering with Computers, 2004, 20(2):147-156.
[24] Liu Z, Leung H, Zhou L, Shum H P H. High quality compatible triangulations for 2D shape morphing. In Proc. the 21st ACM Symposium on Virtual Reality Software and Technology, November 2015, pp.85-94.
[25] Huang J, Tong Y, Zhou K, Bao H, Desbrun M. Interactive shape interpolation through controllable dynamic deformation. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(7):983-992.
[26] Whited B, Noris G, Simmons M, Sumner R W, Gross M, Rossignac J. BetweenIT:An interactive tool for tight inbetweening. Computer Graphics Forum, 2010, 29(2):605-614.
[27] Ruprecht D, Müller H. Image warping with scattered data interpolation. IEEE Comput. Graph. Appl., 1995, 15(2):37-43.
[28] Reeves W T. Inbetweening for computer animation utilizing moving point constraints. In Proc. the 8th Annual Conference on Computer Graphics and Interactive Techniques, August 1981, 263-269.
[29] Popović J, Seitz S M, Erdmann M, Popović Z, Witkin A. Interactive manipulation of rigid body simulations. In Proc. the 27th Annual Conference on Computer Graphics and Interactive Techniques, July 2000, pp.209-217.
[30] Zhu Y, Popović J, Bridson R, Kaufman D M. Planar interpolation with extreme deformation, topology change and dynamics. ACM Trans. Graph., 2017, 36(6):Article No. 213.
[31] Burtnyk N, Wein M. Interactive skeleton techniques for enhancing motion dynamics in key frame animation. Commun. ACM, 1976, 19(10):564-569.
[32] Baxter W. Point-based rigid shape interpolation. In Proc. the 33rd International Conference on Computer Graphics and Interactive Techniques, July 2006, Article No. 92.
[33] Sorkine O, Alexa M. As-rigid-as-possible surface modeling. In Proc. the 5th Eurographics Symposium on Geometry Processing, July 2007, pp.109-116.
[34] Igarashi T, Moscovich T, Hughes J F. As-rigid-as-possible shape manipulation. ACM Transactions on Graphics, 2005, 24(3):1134-1141.
[35] Craig J. Introduction to Robotics:Mechanics and Control (3rd edition). Pearson, 2004.
[36] Joshi P, Meyer M, DeRose T, Green B, Sanocki T. Harmonic coordinates for character articulation. ACM Trans. Graph., 2007, 26(3):Article No. 71.
[37] Shewchuk J R. Triangle:Engineering a 2D quality mesh generator and delaunay triangulator. In Proc. the 1st ACM Workshop on Applied Computational Geometry, May 1996, pp.203-222.
[38] Floater M S. Generalized barycentric coordinates and applications. Acta Numerica, 2015, 24:161-214.
[39] Jacobson A, Baran I, Popovic J, Sorkine O. Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics, 2011, 30(4):Article No. 78.
[40] Jacobson A. Bijective mappings with generalized barycentric coordinates:A counterexample. Journal of Graphics Tools, 2013, 17(1/2):1-4.
[41] Schneider T, Hormann K, Floater M S. Bijective composite mean value mappings. Comput. Graph. Forum, 2013, 32(5):137-146.
[42] Davis T A. Algorithm 832:UMFPACK V4.3-An unsymmetric-pattern multifrontal method. ACM Transactions on Mathematical Software, 2004, 30(2):196-199.
[43] Zhang Z, Luo P, Loy C C, Tang X. Learning deep representation for face alignment with auxiliary attributes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(5):918-930.
No related articles found!
Full text



[1] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[2] Zheng Yuhua; Xie Li; Sun Zliongxiu;. Full Or-Parallemism and Restricted And-Parallelism in BTM[J]. , 1994, 9(4): 373 -381 .
[3] Hock C. Chan;. Translational Semantics for a Conceptual Level Query Language[J]. , 1995, 10(2): 175 -187 .
[4] SHEN Yidong;. A General Scheme for Formalizing Defaults Usingthe Predicate ab(I,S)[J]. , 1999, 14(2): 159 -164 .
[5] WANG Bingshan; LI Zhoujun; CHEN Huowang;. Universal Abstract Consistency Class and Universal Refutation[J]. , 1999, 14(2): 165 -172 .
[6] Sheng-En Li and Shan Wang. Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time[J]. , 2005, 20(3): 367 -372 .
[7] Hua Li, Shui-Cheng Yan, and Li-Zhong Peng[1]. Robust Non-Frontal Face Alignment with Edge Based Texture[J]. , 2005, 20(6): 849 -854 .
[8] Katerina Asdre and Stavros D. Nikolopoulos. P-Tree Structures and Event Horizon: Efficient Event-Set Implementations[J]. , 2006, 21(1): 19 -26 .
[9] Ye-Kui Wang. AVS-M: From Standards to Applications[J]. , 2006, 21(3): 332 -344 .
[10] Issam W. Damaj. Higher-Level Hardware Synthesis of the KASUMI Algorithm[J]. , 2007, 22(1): 60 -70 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved