As-rigid-as-possible shape interpolation

ABSTRACT

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.

REFERENCES

• 1: M. Alexa. Merging Polyhedral Shapes with Scattered Features. The Visual Computer, 16, 1, 2000
• 2: Boris Aronov , Raimund Seidel , Diane Souvaine, On compatible triangulations of simple polygons, Computational Geometry: Theory and Applications, v.3 n.1, p.27-35, June 1993 [doi>10.1016/0925-7721(93)90028-5]
• 3: Thaddeus Beier , Shawn Neely, Feature-based image metamorphosis, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.35-42, July 1992
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 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: Daniel Cohen-Or , Amira Solomovic , David Levin, Three-dimensional distance field metamorphosis, ACM Transactions on Graphics (TOG), v.17 n.2, p.116-141, April 1998 [doi>10.1145/274363.274366]
• 9: Michal Etzion , Ari Rappoport, On Compatible Star Decompositions of Simple Polygons, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.87-95, January 1997 [doi>10.1109/2945.582388]
• 10: Michael S. Floater , Craig Gotsman, How to morph tilings injectively, Journal of Computational and Applied Mathematics, v.101 n.1-2, p.117-129, Jan. 15 1999 [doi>10.1016/S0377-0427(98)00202-7]
• 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. Gregory , A. State , M. Lin , D. Manocha , M. Livingston, Feature-based Surface Decomposition for Correspondence and Morphing Between Polyhedra, Proceedings of the Computer Animation, p.64, June 08-10, 1998
• 15: Taosong He , Sidney Wang , Arie Kaufman, Wavelet-based volume morphing, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
• 16: John F. Hughes, Scheduled Fourier volume morphing, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.43-46, July 1992
• 17: B. Joe. Geompack. ftp://ftp.cs.ualberta.ca/pub/geompack
• 18: T. Kanai , H. Suzuki , F. Kimura, 3D geometric metamorphosis based on harmonic map, Proceedings of the 5th Pacific Conference on Computer Graphics and Applications, p.97, October 13-16, 1997
• 19: James R. Kent , Wayne E. Carlson , Richard E. Parent, Shape transformation for polyhedral objects, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.47-54, July 1992
• 20: Aaron W. F. Lee , David Dobkin , Wim Sweldens , Peter Schröder, Multiresolution mesh morphing, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.343-350, July 1999 [doi>10.1145/311535.311586]
• 21: Seung-Yong Lee , Kyung-Yong Chwa , Sung Yong Shin, Image metamorphosis using snakes and free-form deformations, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.439-448, September 1995 [doi>10.1145/218380.218501]
• 22: Apostolos Lerios , Chase D. Garfinkle , Marc Levoy, Feature-based volume metamorphosis, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.449-456, September 1995 [doi>10.1145/218380.218502]
• 23: Thomas W. Sederberg , Eugene Greenwood, A physically based approach to 2–D shape blending, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.25-34, July 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: Michal Shapira , Ari Rappoport, Shape Blending Using the Star-Skeleton Representation, IEEE Computer Graphics and Applications, v.15 n.2, p.44-50, March 1995 [doi>10.1109/38.365005]
• 26: A. Shapiro and A. Tal. Polyhedron realization for shape transformation. The Visual Computer, 14, 8/9, 1998
• 27: Ken Shoemake , Tom Duff, Matrix animation and polar decomposition, Proceedings of the conference on Graphics interface '92, p.258-264, September 1992, Vancouver, British Columbia, Canada
• 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: Yuefeng Zhang, A Fuzzy Approach to Digital Image Warping, IEEE Computer Graphics and Applications, v.16 n.4, p.34-41, July 1996 [doi>10.1109/38.511850]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Size and shape

General Terms:
Design, Performance, Theory

Keywords:
compatible triangulation, shape blending, vertex path problem