Paper Review—As-Rigid-As-Possible Shape Manipulation

Main Contribution

The research problem in this paper is interactive image editing and shape deformation. This research problem is important in animation and image editing GUIs where real-time interaction is desired. The main contributions include the proposal of an interactive system allowing users to manipulate a shape without a predefined structure which is compatible with multiple-point input devices.

As-rigid-as-possible refers to the modelling of the internal resistance to deformation of a shape, it is achieved in this work by minimizing the geometric distortion from each triangle in the mesh. Besides, the two-step closed-form algorithm is the key to achieve real-time interaction, as it uses quadratic error metrics to establish a system of simultaneous linear equations.

Method

The overall system proposed has several components, including firstly, triangulation to generate a mesh inside the shape (referred to as rest shape in the paper) and pre-computed registration to accelerate computation, secondly compilation when adding or removing new handles, and finally, manipulation when the handles are moved. One limitation of this system is that, in the compilation step, users can only place handles at existing mesh vertices which limits the flexibility of this model. For each interaction, this system updates the handle configuration by solving the quadratic error functions to minimize global distortion. Thus, the key problem is de-scoped to designing a quadratic error metric that represents the overall distortion. The input is the XY-coordinates of the given handles, and the output is the XY-coordinates of the free vertices.

The authors propose to break this down into two steps, a rotation part and a scale part. Each part is tackled by a quadratic error function individually and these two least-score problems can be run sequentially. In the first step of scale-free construction, the goal is to mimic the orientation and translation distortion while retaining the original scale. This step is based on the 2D case in Laplacian editing where a triangle takes the place of a vertex. After summing all the errors for each triangle, the minimizing problem becomes finding the partial derivatives of the error function. Noteworthy here that most of the terms in the matrix manipulation can be pre-computed during registration and compilation, the makes this step as fast as one matrix multiplication per interaction.

To complement the scale-independent distortion, the second step focuses on scale adjustment. Given the intermediate result from the first step and the original triangle in the rest shape, the authors consolidate the fitted triangle congruent to the original triangle minimizing the error. This is first approximated by uniform scaling and then adjusted by a scaling factor. Then, a final quadratic edge error function is used to minimize the distance between the fitted triangle with the corresponding original triangles for each edge. Putting things together, the authors triangulate the input image and produce deformations that are globally smooth by solving a linear system of equations.

What do I think?

Overall, the paper proposes an interactive system that allows the user to deform a 2D shape by manipulating a few points as the constrained handles. This problem is made linear by a two-step closed-form algorithm for rotation and scale. One interesting property of this work is the integration of multiple-point input devices for easy and direct manipulation, such as a touchpad. This will make the tool accessible for beginners and non-artists, which possibly lowers the barrier to entry for animation.

However, this wouldn’t handle the presence of occlusions and topology variation due to the lack of 3D information in these 2D triangulations, as this work is intended not to use physical simulations. I think one possible future work is to obtain depth information of a layered representation of the image to extend this work to the 3rd dimension.

Future Work

At the end of the paper, the authors mentioned a meaningful future work would be extending this to 3D shapes, which is non-trivial because the energy (error) function cannot be linearly parameterized. This is actually solved in a 2007 paper by Sorkine et al [1] with an iterative approach that enables a 3D mesh deformation also using As-Rigid-As-Possible technique. Upon some research, I find As-Rigid-As-Possible as a popular technique in geometry processing to preserve the geometric details. A more recent 2017 paper [2] proposed to enhance the consistency of adjacent rigid transformations by applying larger local neighbourhoods, compared to the 1-ring neighbourhood from this paper.

Intuitively, this can make the deformation more natural and more tolerant of edge cases. However, I don’t think it can substitute for the skeleton or dynamic motion data in animation frames as As-Rigid-As-Possible is still a static method independent from physics.

Reference

[1] Sorkine, O., & Alexa, M. (2007, July). As-rigid-as-possible surface modeling. In Symposium on Geometry processing (Vol. 4, pp. 109-116).

[2] Chen, S. Y., Gao, L., Lai, Y. K., & Xia, S. (2017). Rigidity controllable as-rigid-as-possible shape deformation. Graphical Models, 91, 13-21.