“As-rigid-as-possible shape interpolation” by Alexa, Cohen-Or and Levine

  • ©Marc Alexa, Daniel Cohen-Or, and David B. Levine




    As-rigid-as-possible shape interpolation



    We present an object-space morphing technique that blends the interiors of given two- or three-dimensional shapes rather than their boundaries. The morph is rigid in the sense that local volumes are least-distorting as they vary from their source to target configurations. Given a boundary vertex correspondence, the source and target shapes are decomposed into isomorphic simplicial complexes. For the simplicial complexes, we find a closed-form expression allocating the paths of both boundary and interior vertices from source to target locations as a function of time. Key points are the identification of the optimal simplex morphing and the appropriate definition of an error functional whose minimization defines the paths of the vertices. Each pair of corresponding simplices defines an affine transformation, which is factored into a rotation and a stretching transformation. These local transformations are naturally interpolated over time and serve as the basis for composing a global coherent least-distorting transformation.


    1. M. Alexa. Merging Polyhedral Shapes with Scattered Features. The Visual Computer, 16, 1, 2000
    2. B. Aronov, R. Seidel, and D. Souvaine. On compatible triangulations of simple polygons. Computational Geometry: Theory and Applications 3, pp. 27-35, 1993
    3. T. Beier and S. Neely. Feature-based Image Metamorphosis. SIGGRAPH ’92 Proceedings, pp. 35-42, 1992
    4. M. de Berg, M. van Krefeld, M. Overmars, and O. Schwarzkopf. Computational Geometry – Algorithms and Applications. Springer, Berlin, 1997
    5. B. Chazelle. Triangulating a simple polygon in linear time. Proc/ 31st Symp. on Foundations of Computer Science (FOCS), pp. 220-230, 1990
    6. E. Carmel, D. Cohen-Or. Warp-guided Object Space Morphing. The Visual Computer, 13, 1997
    7. S. Cohen, G. Elber, R. Bar Yehuda. Matching of freeform curves. CAD, 19, 5, pp. 369-378, 1997
    8. D. Cohen-Or, D. Levin, and A. Solomovici. Three dimensional distance field metamorphosis. ACM Transactions on Graphics, 1998
    9. M. Etzion and A. Rappoprt. On Compatible Star Decompositions of Simple Polygons. IEEE Transactions on Visualization and Computer Graphics, 3, 1, pp. 87-95, 1997
    10. M. S. Floater and C. Gotsman. How to Morph Tilings Injectively. J. Comp. Appl. Math., 101, pp. 117-129, 1999
    11. L.A. Freitag, M.T. Jones, and P.E. Plassmann. An efficient parallel algorithm for mesh smoothing. 4th Int. Meshing Roundtable, pp. 47-58, 1995
    12. G.H. Golub and C.F. van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, 1983
    13. E. Goldstein and C. Gotsman. Polygon Morphing using a Multiresolution Representation. Graphics Interface ’95, pp. 247- 254, 1995
    14. A. Greogory, A. State, M. Lin, D. Manocha, and M. Livingston. Feature-based surface decomposition for correspondence and morphing between polyhedra. Proceedings of Computer Animation ’98, pp. 64-71, 1998
    15. T. He, S. Wang, and A. Kaufman. Wavelet-basedVolume Morphing. Proceedings of Visualization, IEEE Computer Society, pp. 85-91, 1994
    16. J.F. Hughes. Scheduled Fourier Volume Morphing. Computer Graphics (SIGGRAPH ’92 Proceedings), 26, 2, pp. 43-46, 1992
    17. B. Joe. Geompack. ftp://ftp.cs.ualberta.ca/pub/geompack
    18. T. Kanai, H Suzuki, and F. Kimura. 3D geometric metamorphosis based on harmonic maps. Proceedings of Pacific Graphics ’97, pp. 97-104, 1997
    19. J.R. Kent, W.E. Carlson, and R.E. Parent. Shape Transformation for polyhedral objects. Computer Graphics, 26, pp. 47-54, 1992
    20. A.W.F. Lee, D. Dobkin, W. Sweldens, and P. Schr6der. Multiresolution Mesh Morphing. SIGGRAPH ’99 Proceedings, pp. 343-350, 1999
    21. S.Y. Lee, K.Y. Chwa, S.Y. Shin, and G. Wolberg. Image Metamorphosis Using Snakes and Free-Form Deformations. SIG- GRAPH ’95 Proceedings, pp. 439-448, 1995
    22. A. Lerios, C.D. Garfinkle, and M. Levoy. Feature-Based Volume Metamorphis. SIGGRAPH ’95 Proceedings, pp. 449- 456, 1995
    23. T.W. Sederberg and E. Greenwood. A physically based approach to 2D shape blending. Computer Graphics, 26, pp. 25- 34, 1992
    24. T.W. Sederberg, P. Gao, G. Wang, and H. Mu. 2-D shape blending: An intrinsic solution to the vertex-path problem. Computer Graphics, 27, pp. 15-18, 1993
    25. M. Shapira and A. Rappoport. Shape blending using the starskeleton representation. IEEE CG&A, 15, pp. 44-51, 1993
    26. A. Shapiro and A. Tal. Polyhedron realization for shape transformation. The Visual Computer, 14, 8/9, 1998
    27. K. Shoemake and T. Duff. Matrix Animation and Polar Decomposition. Proceedings of Graphics Interface ’92, pp. 258- 264, 1992
    28. A. Tal and G. Elber. Image Morphing with Feature Preserving Texture. Computer Graphics Forum (Eurographics ’99 Proceedings), 18, 3, pp. 339-348, 1999
    29. G. Wolberg. Digital Image Morphing. IEEE Computer Society Press, 1990
    30. G. Wolberg. Image Morphing Survey. The Visual Computer, 14, 8/9, 1998
    31. Y. Zhang. A Fuzzy Approach to Digital Image Warping. IEEE Computer Graphics and Applications, pp. 33-41, 1996

ACM Digital Library Publication: