“As-rigid-as-possible shape manipulation” by Igarashi, Moscovich and Hughes

We present an interactive system that lets a user move and deform a two-dimensional shape without manually establishing a skeleton or freeform deformation (FFD) domain beforehand. The shape is represented by a triangle mesh and the user moves several vertices of the mesh as constrained handles. The system then computes the positions of the remaining free vertices by minimizing the distortion of each triangle. While physically based simulation or iterative refinement can also be used for this purpose, they tend to be slow. We present a two-step closed-form algorithm that achieves real-time interaction. The first step finds an appropriate rotation for each triangle and the second step adjusts its scale. The key idea is to use quadratic error metrics so that each minimization problem becomes a system of linear equations. After solving the simultaneous equations at the beginning of interaction, we can quickly find the positions of free vertices during interactive manipulation. Our approach successfully conveys a sense of rigidity of the shape, which is difficult in space-warp approaches. With a multiple-point input device, even beginners can easily move, rotate, and deform shapes at will.

1. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-Rigid-As-Possible Shape Interpolation. In Proceedings of ACM SIGGRAPH 2000, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 157–164. Google ScholarDigital Library
2. Angelidis, A., Cani, M., Wyvill, G. and King, S. 2004. Swirling-Sweepers: Constant-Volume Modeling. Pacific Graphics 2004, 10–15. Google ScholarDigital Library
3. Barrett, W. A., and Cheney, A. S. 2002. Object-based Image Editing. ACM Transactions on Graphics, 21, 3, 777–784. Google ScholarDigital Library
4. Beier, T. and Neely, S. 1992 Feature-based image metamorphosis, In Computer Graphics (Proceedings of SIGGRAPH 92), 26, 2, 35–42. Google ScholarDigital Library
5. Bookstein, F. L. 1989. Principal Warps: Thin-Plate Splines and the Decomposition of Deformations, IEEE Transactions on Pattern Analysis and Machine Intelligence, 11, 6, 567–585. Google ScholarDigital Library
6. Bruce, H. T., and Calder, P. 1995. Animating Direct Manipulation Interfaces. In Proceedings of UIST ’95, 3–12. Google ScholarDigital Library
7. Celniker, G., and Gossard, D. 1991. Deformable Curve and Surface Finite Elements for Free-form Shape Design. In Computer Graphics (Proceedings of ACM SIGGRAPH 91), 25, 4, ACM, 257–266. Google ScholarDigital Library
8. Davis, T. A. 2003. Umfpack Version 4.1 User Guide. Technical report TR-03-008, University of Florida.Google Scholar
9. Gibson, S. F., and Mirtich, B. 1997. A Survey of Deformable Models in Computer Graphics. Technical report TR-97-19, Mitsubishi Electric Research Laboratories.Google Scholar
10. Hornung, C. 1984. A Method for Solving the Visibility Problem. IEEE Computer Graphics and Applications, 4, 7, 26–33.Google ScholarDigital Library
11. James, D. L., and Pai, D. K. 1999. ArtDefo Accurate Real Time Deformable Objects, In Proceedings of SIGGRAPH 1999, 65–72. Google ScholarDigital Library
12. Lewis, J. P., Cordner, M., and Fong, N. 2000. Pose Space Deformations: A Unified Approach to Shape Interpolation and Skeleton-driven Deformation. In SIGGRAPH 2000 Conference Proceedings, 165–172. Google ScholarDigital Library
13. Llamas, I., Kim, B., Gargus, J., Rossignac, J., and Shaw, C. D. 2003. Twister: A Space-Warp Operator for the Two-Handed Editing of 3D Shapes. In Proceedings of SIGGRAPH 2003, ACM Press/ACM SIGGRAPH, Ed., Computer Graphics Proceedings, Annual Conference Series, ACM, 663–668. Google ScholarDigital Library
14. Maccracken, R., and Joy, K. I. 1996. Free-form Deformations with Lattices of Arbitrary Topology. In Proceedings of ACM SIGGRAPH 1996, ACM Press / ACM SIGGRAPH, Ed., Computer Graphics Proceedings, Annual Conference Series, ACM, 181–188. Google ScholarDigital Library
15. Markosian, L., Cohen, J. M., Crulli, and Hughes, J. F. 1999. Skin: a Constructive Approach to Modeling Free-form Shapes. In Proceedings of ACM SIGGRAPH 1999, ACM Press/ACM SIGGRAPH, Los Angeles, Ed., Computer Graphics Proceedings, Annual Conference Series, ACM, 393–400. Google ScholarDigital Library
16. Milliron, T., Jensen, R., Barzel, R. and Finkelstein, A. 2002. A Framework for Geometric Warps and Deformations. ACM Transactions on Graphics, 21, 1, 20–51. Google ScholarDigital Library
17. Ngo, T., Cutrell, D., Dana, J., Donald, B., Loeb, L. and Zhu, S. 2000. Accessible Animation and Customizable Graphics via Simplicial Configuration Modeling. In Proceedings of SIGGRAPH 2000, ACM Press/ACM SIGGRAPH, Ed., Computer Graphics Proceedings, Annual Conference Series, ACM, 403–410. Google ScholarDigital Library
18. Rekimoto, J. 2002. SmartSkin: An Infrastructure for Freehand Manipulations on Interactive Surfaces. In Proceedings of CHI’02, 113–120. Google ScholarDigital Library
19. Shewchuk, J. R. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Proceedings of First Workshop on Applied Computational Geometry, 124–133. Google ScholarDigital Library
20. Sheffer, A., and Kraevoy, V. 2004. Pyramid Coordinates for Morphing and Deformation. In Proceedings of 3D Data Processing. Visualization, and Transmission, 2nd International Symposium on (3DPVT’04), 68–75. Google ScholarDigital Library
21. Shoemake K. and Duff, T. 1992. Matrix Animation and Polar Decomposition. Proceedings of Graphics Interface ’92, 258–264. Google ScholarDigital Library
22. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rossl, C., and Seidel, H. 2004. Laplacian Surface Editing. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 179–188. Google ScholarDigital Library
23. Sumner, R. W., and Popovic, J. 2004. Deformation Transfer for Triangle Meshes, ACM Transaction on Graphics, 23, 3, 399–405. Google ScholarDigital Library
24. Yamane, K., and Nakamura, Y. 2003. Natural Motion Animation Through Constraining and Deconstraining at Will. IEEE Transaction on Visualization and Computer Graphics, 9, 3, 352–360. Google ScholarDigital Library
25. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B. and Shum, H. Y. 2004. Mesh Editing with Poisson-Based Gradient Field Manipulation. ACM Transactions on Graphics, 23, 3, 641–648. Google ScholarDigital Library