Takeo Igarashi
Tomer Moscovich
Abstract
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.
Supplemental Material
- 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 Scholar
Digital Library
- Angelidis, A., Cani, M., Wyvill, G. and King, S. 2004. Swirling-Sweepers: Constant-Volume Modeling. Pacific Graphics 2004, 10--15. Google ScholarDigital Library
- Barrett, W. A., and Cheney, A. S. 2002. Object-based Image Editing. ACM Transactions on Graphics, 21, 3, 777--784. Google ScholarDigital Library
- Beier, T. and Neely, S. 1992 Feature-based image metamorphosis, In Computer Graphics (Proceedings of SIGGRAPH 92), 26, 2, 35--42. Google ScholarDigital Library
- 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
- Bruce, H. T., and Calder, P. 1995. Animating Direct Manipulation Interfaces. In Proceedings of UIST '95, 3--12. Google ScholarDigital Library
- 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
- Davis, T. A. 2003. Umfpack Version 4.1 User Guide. Technical report TR-03-008, University of Florida.Google Scholar
- 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
- Hornung, C. 1984. A Method for Solving the Visibility Problem. IEEE Computer Graphics and Applications, 4, 7, 26--33.Google ScholarDigital Library
- James, D. L., and Pai, D. K. 1999. ArtDefo Accurate Real Time Deformable Objects, In Proceedings of SIGGRAPH 1999, 65--72. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- 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
- Rekimoto, J. 2002. SmartSkin: An Infrastructure for Freehand Manipulations on Interactive Surfaces. In Proceedings of CHI'02, 113--120. Google ScholarDigital Library
- 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
- 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
- Shoemake K. and Duff, T. 1992. Matrix Animation and Polar Decomposition. Proceedings of Graphics Interface '92, 258--264. Google ScholarDigital Library
- 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
- Sumner, R. W., and Popovic, J. 2004. Deformation Transfer for Triangle Meshes, ACM Transaction on Graphics, 23, 3, 399--405. Google ScholarDigital Library
- 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
- 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
Index Terms
- As-rigid-as-possible shape manipulation
Recommendations
As-rigid-as-possible shape manipulation
SIGGRAPH '05: ACM SIGGRAPH 2005 PapersWe 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 ...
2D Shape Manipulation Using Equilateral Triangle Mesh
ICDH '12: Proceedings of the 2012 Fourth International Conference on Digital HomeThis paper presents an improved algorithm to achieve 2D image shape manipulation by real-time control. The shape is discretized as regular equilateral triangles mesh. User places handles on triangle vertices and manipulates the shape by dragging the ...
2D shape manipulation via topology-aware rigid grid
CASA' 2009 Special IssueThis paper presents a new method which allows user to manipulate a two-dimensional shape in an intuitive and flexible way. The shape is discretized as a regular grid. User places handles on the grid and manipulates the shape by moving the handles to the ...
Comments