Copyright © 2005 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Permissions Dept, ACM Inc., fax +1 (212) 869-0481 or e-mail [email protected]. © 2005 ACM 0730-0301/05/0700-1134 $5.00 As-Rigid-As-Possible Shape Manipulation Takeo Igarashi1, 3 Tomer Moscovich2 John F. Hughes2 1The University of Tokyo 2 Brown University 3 PRESTO, JST 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. CR Categories: I.3.6 [Computer Graphics]: Methodology and Techniques – Interaction Techniques; I.3.3 [Computer Graphics]: Picture/Image Generation – Display algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling – Geometric algorithms. Keywords: Shape Manipulation, Deformation, Image Editing, Mesh Editing, Animation, Interaction 1 Introduction With a 2D image or drawing at hand, a user might want to manipulate it—move, rotate, stretch, and bend it. The primary application we have in mind is an editing tool for drawing or image-editing systems, but our interactive shape manipulation technique is also useful in various applications such as real-time live performance [Ngo et al. 2000] and enriching graphical user interfaces [Bruce and Calder 1995]. One popular approach for shape manipulation is to use a pre-defined skeleton. The user manipulates the skeleton configuration and the system adjusts the overall shape relative to the skeleton. However, defining a skeleton structure for a shape is not a trivial task [Lewis et al. 2000] and is not effective for objects, such as jellies, that lack an obvious jointed structure. Another popular method is free-form deformation (FFD) [MacCracken and Joy 1996] in which the user explicitly divides the space into several domains and manipulates each domain by moving control points defining it. But setting FFD domains is tedious and the user must laboriously manipulate many control vertices. This paper presents an interactive system that allows the user to manipulate a shape without using a skeleton or FFD. The user chooses several points inside of the shape as handles and moves each handle to a desired position. The system then moves, rotates, and deforms the overall shape to match the given handle positions while minimizing distortion. By taking the interior of the shape into account, our approach can model its rigidity, making the result much closer to the behavior of real-world objects than in space-warp approaches as in [Barrett and Cheney 2002; Llamas et al. 2003]. We use a two-step closed-form algorithm for finding the shape configuration that minimizes distortion. The typical approach is to use a physically based simulation or nonlinear optimizations [Sheffer and Kraevoy 2004], but these techniques are too slow for interactive manipulation. A key aspect of our approach is the design of a quadratic error metric so that the minimization problem is formulated as a set of simultaneous linear equations. The system solves the simultaneous equations at the beginning, and can therefore quickly find a solution during interaction. Ideally we would like a single quadratic error function that handles all properties of a shape, but no such function exists (see Appendix A). We therefore split the problem into a rotation part and a scale part. This divides the problem into two least-squares minimization problems that we can solve sequentially. This method can be seen as a variant of the method proposed by Sorkine et al. [2004]. Our technique can be useful in standard dragging operations with a mouse, but it is particularly interesting when using a multiple-point input device such as a SmartSkin touchpad [Rekimoto 2002] (Figure 1). With such a device, one can interactively move, rotate, and deform an entire shape as if manipulating a real object using both hands. This is difficult with existing shape deformation tools because most allow only local modification while the overall position and orientation of the shape is fixed. Figure 1: Shape manipulation using a SmartSkin touchpad. The user can interactively move, rotate, and deform the shape using both hands as if manipulating a real object. 11342 Related Work Shape manipulation techniques fall roughly into two categories. One is to deform the space in which the target shape is embedded; the other is to deform the shape while taking its structure into account. Deformation using skeletons, FFD, and other space-warp approaches belong to the first category. With skeletons, each point in the shape is associated with a coordinate frame defined by a bone [Lewis et al. 2000]. In FFD, each point is associated with a closed region in a FFD grid [MacCracken and Joy 1996]. Other space warp techniques deform the global space [Milliron et al. 2002]. Beier and Neely used space