AS-rigid-as-possible shape manipulation
需积分: 37 156 浏览量
2012-03-10
00:19:48
上传
评论
收藏 642KB PDF 举报
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 permissions@acm.org
.
© 2005 ACM 0730-0301/05/0700-1134 $5.00
As-Rigid-As-Possible Shape Manipulation
Takeo Igarashi
1, 3
Tomer Moscovich
2
John F. Hughes
2
1
The 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.
1134
评论0