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

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