More Web Proxy on the site http://driver.im/

Article

Free access

As-rigid-as-possible shape interpolation

Authors:

Daniel Cohen-Or,

David LevinAuthors Info & Claims

SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques

Pages 157 - 164

https://doi.org/10.1145/344779.344859

Published: 01 July 2000 Publication History

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

Digital Library

[2]

B. Aronov, R. Seidel, and D. Souvaine. On compatible triangulations of simple polygons. Computational Geometry: Theory and Applications 3, pp. 27-35, 1993

Digital Library

[3]

T. Beier and S. Neely. Feature-based Image Metamorphosis. SIGGRAPH '92 Proceedings, pp. 35-42, 1992

Digital Library

[4]

M. de Berg, M. van Krefeld, M. Overmars, and O. Schwarzkopf. Computational Geometry - Algorithms and Applications. Springer, Berlin, 1997

Digital Library

[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

Digital Library

[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

Digital Library

[10]

M. S. Floater and C. Gotsman. How to Morph Tilings Injectively. J. Comp. Appl. Math., 101, pp. 117-129, 1999

Digital Library

[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

Digital Library

[15]

T. He, S. Wang, and A. Kaufman. Wavelet-basedVolume Morphing. Proceedings of Visualization, IEEE Computer Society, pp. 85-91, 1994

Digital Library

[16]

J.F. Hughes. Scheduled Fourier Volume Morphing. Computer Graphics (SIGGRAPH '92 Proceedings), 26, 2, pp. 43-46, 1992

Digital Library

[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

Digital Library

[19]

J.R. Kent, W.E. Carlson, and R.E. Parent. Shape Transformation for polyhedral objects. Computer Graphics, 26, pp. 47-54, 1992

Digital Library

[20]

A.W.F. Lee, D. Dobkin, W. Sweldens, and P. Schr6der. Multiresolution Mesh Morphing. SIGGRAPH '99 Proceedings, pp. 343-350, 1999

Digital Library

[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

Digital Library

[22]

A. Lerios, C.D. Garfinkle, and M. Levoy. Feature-Based Volume Metamorphis. SIGGRAPH '95 Proceedings, pp. 449- 456, 1995

Digital Library

[23]

T.W. Sederberg and E. Greenwood. A physically based approach to 2D shape blending. Computer Graphics, 26, pp. 25- 34, 1992

Digital Library

[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

Digital Library

[25]

M. Shapira and A. Rappoport. Shape blending using the starskeleton representation. IEEE CG&A, 15, pp. 44-51, 1993

Digital Library

[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

Digital Library

[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

Digital Library

Cited By

Horimoto ASato SSakurai KNakamoto K(2025)A shape control method for soap bubble simulation using external forcesScientific Reports10.1038/s41598-025-90850-215:1Online publication date: 6-Mar-2025
https://doi.org/10.1038/s41598-025-90850-2
Ye HLiu TNi HChen J(2025)Robust Full-Layer Prismatic Mesh Generation based on Bijective MappingJournal of Computational Physics10.1016/j.jcp.2025.113744(113744)Online publication date: Jan-2025
https://doi.org/10.1016/j.jcp.2025.113744
Meulemans WSimons AVerbeek K(2025)Visual Complexity of Point Set MappingsSOFSEM 2025: Theory and Practice of Computer Science10.1007/978-3-031-82697-9_12(157-171)Online publication date: 16-Feb-2025
https://doi.org/10.1007/978-3-031-82697-9_12
Show More Cited By

Index Terms

As-rigid-as-possible shape interpolation
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision representations
        Shape representations
  2. Computer graphics
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
  2. Mathematical analysis
    1. Numerical analysis
      1. Interpolation

Recommendations

As-Rigid-As-Possible Shape Interpolation
Seminal Graphics Papers: Pushing the Boundaries, Volume 2

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 ...
Topology-varying 3D shape creation via structural blending

We introduce an algorithm for generating novel 3D models via topology-varying shape blending. Given a source and a target shape, our method blends them topologically and geometrically, producing continuous series of in-betweens as new shape creations. ...
As-rigid-as-possible shape deformation and interpolation

We provide a detailed analysis of the 2D deformation algorithm based on non-linear least squares optimization, and prove that different mesh structure is of critical importance to deforming result. Based on triangle mesh, preserving the length of edges ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques

July 2000

547 pages

ISBN:1581132085

Chairmen:
Judith R. Brown
Coralville, IA
,
Kurt Akeley

Seminal Graphics Papers: Pushing the Boundaries, Volume 2
August 2023
893 pages
ISBN:9798400708978
DOI:10.1145/3596711
Editor:
Mary C. Whitton
Department of Computer Science, UNC Chapel Hill, USA

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM Press/Addison-Wesley Publishing Co.

United States

Publication History

Published: 01 July 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Seminal Paper

Author Tags

Qualifiers

Article

Conference

SIGGRAPH00

Sponsor:

SIGGRAPH

SIGGRAPH00: The 27th Internationl Conference on Computer Graphics and Interactive Techniques Conference

Acceptance Rates

SIGGRAPH '00 Paper Acceptance Rate 59 of 304 submissions, 19%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

421
Total Citations
View Citations
4,156
Total Downloads

Downloads (Last 12 months)552
Downloads (Last 6 weeks)62

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Horimoto ASato SSakurai KNakamoto K(2025)A shape control method for soap bubble simulation using external forcesScientific Reports10.1038/s41598-025-90850-215:1Online publication date: 6-Mar-2025
https://doi.org/10.1038/s41598-025-90850-2
Ye HLiu TNi HChen J(2025)Robust Full-Layer Prismatic Mesh Generation based on Bijective MappingJournal of Computational Physics10.1016/j.jcp.2025.113744(113744)Online publication date: Jan-2025
https://doi.org/10.1016/j.jcp.2025.113744
Meulemans WSimons AVerbeek K(2025)Visual Complexity of Point Set MappingsSOFSEM 2025: Theory and Practice of Computer Science10.1007/978-3-031-82697-9_12(157-171)Online publication date: 16-Feb-2025
https://doi.org/10.1007/978-3-031-82697-9_12
Zhu XChen ZHu RHan X(2024)Controllable Shape Modeling with Neural Generalized CylinderSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687617(1-11)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3680528.3687617
Lin HChitalu FKomura T(2024)Analytic rotation-invariant modelling of anisotropic finite elementsACM Transactions on Graphics10.1145/366608643:5(1-20)Online publication date: 9-Aug-2024
https://dl.acm.org/doi/10.1145/3666086
Mo HGao CWang R(2024)Joint Stroke Tracing and Correspondence for 2D AnimationACM Transactions on Graphics10.1145/364989043:3(1-17)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.1145/3649890
Tang PHinchet RPoranne RThomaszewski BCoros S(2024)Modal Folding: Discovering Smooth Folding Patterns for Sheet Materials using Strain-Space ModesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657401(1-9)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657401
Cao DEisenberger MEl Amrani NCremers DBernard F(2024)Spectral Meets Spatial: Harmonising 3D Shape Matching and Interpolation2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00351(3658-3668)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00351
Li SPan Y(2024)Interactive geometry editing of Neural Radiance FieldsDisplays10.1016/j.displa.2024.10281084(102810)Online publication date: Sep-2024
https://doi.org/10.1016/j.displa.2024.102810
Huang ZLiu SFu X(2024)High-order Shape InterpolationComputer Aided Geometric Design10.1016/j.cagd.2024.102301(102301)Online publication date: Apr-2024
https://doi.org/10.1016/j.cagd.2024.102301
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten