As-Rigid-As-Possible Shape Manipulation

The problem of shape manipulation is of interest to many domains, including but not limited to: image editing platforms, usage in real-time live performances, and enhancing graphical user interfaces. The goal of shape manipulation is to impart the ability to move and deform shapes in a manner that is akin to interacting with an object in the real world. Previous approaches to shape manipulation can be broadly categorized into (a) space-warp and (b) physics based techniques.

• Space warp based approaches such as deformation using skeletons, thin plate splines, and free form deformation deform the space in which the shape is embedded, thus deforming the shape itself. This is a compute-efficient approach, but results in unrealistic deformations.

• Physics based approaches such as the mass-spring model simulate real-world behavior and are easy to implement, but are slow to converge and require parameter tuning, in addition to being “too elastic” for many applications.

This paper addresses these shortcomings by using a geometric approach instead of physics based models and introduces “internal model rigidity” into shape manipulation, and proposes, unlike previously proposed iterative solutions, a closed form solution for manipulating shape configurations while minimizing shape distortion.

Given a shape, it is converted into a triangulated mesh within the shape boundary using a particle-based algorithm, after which it undergoes “registration” using pre-computation to accelerate updates during interaction. The user can then place handles on mesh vertices to drag them to manipulate the shape. With each handle being added or removed, another set of pre-computations called “compilation” generates a function which can use the handle configuration to output the resulting shape. The algorithm therefore takes as input the coordinates of the constrained mesh vertices (handles) and outputs the coordinates of the ‘free’ mesh vertices while minimizing the distortion associated with all the triangles in the mesh. The authors present a proof by contradiction that no single quadratic error metric (quadratic to make it a least-squares problem, simplifying computation) exists which can represent the overall distortion, and therefore use two complementary error functions sequentially: the first ($E_1$) which allows translation, rotation, and uniform scaling but penalizes shearing and non-uniform stretching, thus allowing for scale-free reconstruction, and the second (comprised of $E_f$ and $E_2$) which adjusts the scales of the resulting triangles. Therefore, first, given a set of input positions, the intermediate results are obtained by minimizing $E_1$ calculated using the $\mathcal{L}_2$ distance of all the vertices of the triangles. This minimizes shearing and stretching but allows scaling since $E_1$ does not capture scale changes. This is fixed in the next step where another quadratic error function $E_f$ is used to fit the correct sized triangles to the result by using the congruence property of triangles and minimizing the error of the vertex positions. Finally, the coordinates of the free vertices are computed using a third quadratic error function $E_2$ to minimize the difference in the vertex coordinates between the fitted triangles from the previous step and the resulting triangles in the mesh. All the three set of operations described here are based on a linear system of matrix operations, and therefore fast enough that interactive operation can be achieved for coarse meshes upto 100 vertices on quite modest hardware, with excellent performance achieved even in challenging scenarios such as irregularly spaced triangle meshes (i.e., meshes with uneven traingle density). The authors also discuss some extensions to improve the shape manipulation experience and make it more realistic. First, they continuously monitor the mesh for instance of self-intersection and dynamically update the depth during interactive manipulation, thus avoiding collision. Second, because their approach is based on error minimization, they make it possible to add weights to different mesh regions to control the “local rigidity” of the shape, making deformation results more realistic. The interactive response time of the updates allows for designing performance driven animations where a user can move a control cursor to manipulate a pose by interpolating nearby key poses generated using a radial basis function, allowing for a smooth and ’lively’ animation that is easier and faster than temporal keyframing based techniques. Finally, the two-step algorithm can also be applied to curve editing where the input is a polyline instead of a triangle mesh. The use of scale adjustment introduces the notion of inherent rigidity in the curve, leading to realistic shape changes. The authors also allow a peeling interface where the user can control the influence region, allowing for shape changes in only certain regions, which is superior in versatility to Macromedia Flash’s similar offering.

This paper proposes a two-step closed form geometry-based algorithm for shape manipulation that allows users to interact with shapes in real-time by placing handles as constraints and deforming the shape akin to a real-world interaction. The method is quite easy to understand, and its simplicity offers fast shape updates. The paper is very well written and easy to follow, with sufficient implementation details. The definition of $\mathrm{\textbf{G}}$ though is not explicit and although possible to infer, it should have been included. The method admittedly does have some shortcomings: (a) inability to place handles at non-vertex points, (b) difficulty with linear shapes with handles on edges, and (c) inability to generalize to 3D volumes. Of these, the ability to manipulate 3D shapes arguably holds the most value, and is therefore a promising extension. FiberMesh (co-authored by Takeo Igarashi, ACM SIGGRAPH 2007) proposed using 3D curves to design freeform 3D surfaces.