Abstract: The 2-d shape interpolation or shape morphing which involves the creation of a smooth transition from a source planar polygon to a target one, has gained widespread application in recent years. In this study, we implemented an interpolation framework. As for an interpolating key issue which is correspondence between the source and target shape, we proposed a scheme for corresponding and improving the interpolation. We only triangulate the source shape and find the position of vertex in target shape by the technology of deformation with constraints. Our method avoids the shape remeshing for correspondence. As for large rotation and small strain problem, our method can work well. This method is easy to implement in the exiting FEM code. Experiments show that the proposed framework is effective for as-rigid-as-possible interpolation.
INTRODUCTION
Two-dimensional morphing or shape interpolation algorithms have many practical applications. This technique is also called shape blending or shape averaging which is used to generate a sequence of intermediate shapes from source shape to target shape. In recent years, 2D morphing technique plays an important role in computer animation and is also widely used in computer games, movie and other related fields.
Strictly speaking, the intermediate shapes change from source shape to target shape is not unique and there is no standard answer to whether the sequence is best and it always depends on some rules as followed: Firstly, the morphing is natural and smooth. Secondly, the boundary of the shape should preserve details of the shapes. Finally, any distortion and unnecessary deformation should be avoided.
Recently, a variety of algorithms that preserve shape rigidity have been introduced. The as-rigid-as-possible shape interpolation methods (Alexa et al., 2000; Alexa, 2002; Liu et al., 2011) generate series of intermediate frames whose results are natural. In most cases, rigidity preserving interpolation, works well and is a very practical way to generate high-quality intermediate shapes.
In these methods, the vertex correspondence of triangles between the source and target shape is important. In the large rotation case, there is a serve artificial effect if the correspondence is not perfect including the vertex order in a triangle. The common practice is triangulating the source and target shape, respectively and mapping the vertex. However, the correspondence issue is usually not simply requires frequently remeshing and mapping during solving the problem.
In this study, we proposed a scheme to solve the corresponding for improving the interpolation. We only triangulate the source shape and find the position of vertex in target shape by the technology of deformation with constraints. Our method avoids the remeshing of the shape. As for large rotation and small strain problem, our method can get favorable corresponding effects. Compared the corresponding base with other geometric methods for the interior vertex, our method is more simple and efficient.
Shape morphing is firstly achieved by using the methods of image morphing processing such as Cross-dissolve, mesh warping (Wolberg, 1998) etc. Then the study on 2D graph morphing emerged. Most previous studies are mainly concerned with the correspondence problem and just simply adopted linear interpolation to generate vertex trajectory (Wang et al., 2013). It would cause artificial effects because the shape morphing contains rotation and some other non-linear factors and cannot be simply expressed as linear factor. In order to solve the shrinkage problem, some methods were proposed by Sedkerberg et al. (1993), Sederberg and Greenwood (1992) which relied on the angles and edges of the polygons. The intermediate shapes were reconstructed by solving a Lagrange equation with constraint optimization problem and make the in-betweens of the polygon remain closed (Huang et al., 2011). As the algorithm of Sederberg et al. (1993) cannot solve the object-space problem, a new method called star-skeleton was introduced by Gotsman and Surazhsky (2001) to deal with this problem. The method is: First, divide the source shape and target shape into isomorphism star skeleton, then divide the original polygon into sub-polygons, finally interpolate the angles and edges of the polygon linearly. The defect of the star-skeleton method is that it’s hard and sometime impossible to find the star-skeleton. And a new non-self-intersecting polygon morphing method is presented by Surazhsky and Gotsman (2003), the isomorphic triangulation is interpolated and the algorithm of Gotsman and Surazhsky would be non-self-intersecting. Zhang (1996), Carmel and Cohen-Or (1998) divided the shape into two parts; rigid component and elastic component. The rotational component should be interpolated separately from the elastic part (Shoemake and Duff, 1992). The deformation of the rigid-elastic shape may not be able to get a smooth transition effects. Object-space morphing gains more and more attention in recent study. Alexa et al. (2000) presented a new method to preserve rigidity and Alexa, (2002) introduces the Frobenius norm to accomplish shape reconstruction. Then a new method is presented by Xu et al. (2005) to reconstruct the intermediate shapes through solving Poisson equation.
INTERPOLATION METHODS
In this study, the as-rigid-as-possible interpolation is applied to solve the shape interpolation.
Given the existing two meshes P and Q composed of corresponding triangles PT and QT (T = 1 . . .M), which are source and target shape, respectively. Intermediate shapes are built based on the premise of preserving rigidity. In this scheme, PT is obtained by triangulating the source shape, QT is the deformed PT with the constraints which are the boundaries of the target shape.
During the calculation for interpolation, firstly, as for the each triangle PT , the affine matrix related the triangles from source to target AT, is introduced for each triangle pair. We compose the vertex coordinates matrix PT (pi, pj, pk) and QT (qi, qj, qk) of the source triangle and corresponding target triangle, respectively. So, AT can be computed as following in Eq. 1:
| (1) |
where, p and q are vertices vector of the triangles, x and y are 2-d coordinate components. Then, factor AT into rotation RT and scale-shear parts ST by polar decomposition. That is AT = RTST.
As for each interpolation coefficient t(0≤t≤1), the coordinate matrix of the the intermedia triangle V(t), the affine matrix
Minimize the quadratic error between actual matrices BT(t) and ideal matrix AT. The Ev(t) is the quadratic error function which can be expressed as:
| (2) |
Setting uT = (1, v2x (t), v2y (t), ……., vnx (t), vny (t)) and Ev(t) can also be expressed in matrix form as:
| (3) |
According to previous work (1,16), the minimization problem can be solved by setting the gradient over the free variables to zero, then it will get A Ax = B form as:
| (4) |
Where, H is independent of t and G is linear coefficient. From the error function Ev(t) , we have:
| (5) |
By calculating the Eq. 3 and 4, we can get the H and G, where H is a 2nx2n matrix and G is a 2nx1 matrix. They are independent of the interpolation parameter t.
CORRESPONDENCE OF VERTEX
Constructing isomorphic dissection is a key in the shape interpolation and morphing. Although, a plenty of work has been presented previous literatures, the correspondence between source and target shape is always complex problem. In literature (Alexa et al., 2000), an effective method was given in an as-rigid-as-possible shape interpolation keyframe. However, remeshing which is implemented by many time triangulations, is still necessary. During solving, the vertex order corresponding is a difficult problem because a great majority triangulating method is only for a single shape. In detail, the interpolation probably has a serious drawback when the vertex order is not same between corresponding triangles. As for the interior vertex, we locate its position in the target shape by solving the deformation problem with the boundary constraint.
Discussion of the existing approach: Intermediate shapes are out of control when the traditional as-rigid-as-possible interpolation algorithm is used in some extreme situations. One is large rotation problem and the other is mirror symmetry problem, as showed in Fig. 1 and 2.
From the results of this experiment, it can be found that it is too hard to preserve rigidity under two situations, one is when the correspondence triangles are mirror symmetry (Fig. 2), the other is the pair of triangle has large rotation problem (Fig. 1). The affine matrix cannot correctly reflect the deformation of a pair of large rotation situation. And it would cause severe distortion in as-rigid-as-possible interpolation (Fig. 3). It also can be seen from Fig. 2, the morphing between two mirror symmetry seems very strange and the in-between shapes seem to be turned into the inner space which is impossible in two dimentional space. In Fig. 4, a intermediate shape of the complex shape is showed and we can find the artifact effect in the domain marked by red curve.
The cause of generating artifact effects is wrong correspondence including the wrong vertex order in correct triangle mapping (Fig. 1 and 2). From the affine matrix, matrix AT depends on the vector of the edge without considering the relationship of the vertices orientation of the triangle. In fact, above problem is an orientation independence problem which is an advantage in shape morphing. It will cause shape defects in the morphing procedure. From the study of Baxter et al. (2008), it is a difficult task to extract a rotation angle from a rotation matrix in the large rotation situation while the answer of angle is not unique. As to the mirror symmetry, there is no way to solve such problem under that circumstance. Therefore, we proposed a scheme to solve the correspondence and avoid above case.
Source triangulation and boundary correspondence: Firstly, we triangulate the source shape by Delauny method. We express the triangulating results into a boundary vertex set B, an interior vertex set I and a triangles set P. Our goal is to find the corresponding set in target shape. Firstly, we found the boundary correspondence by interactive method. We set several key-vertex corresponding between source and target shape. As for other boundary vertex in B, we applied to curve corresponding based on arc length proportion. In detail, the key-vertex can split the boundary of the source shape into some broken. Similarly, the corresponding vertex split the boundary of the target into some arc.
| Fig. 1: | Large rotation problem |
| Fig. 2: | Two triangles with mirror symmetry and morphing |
| Fig. 3: | Morphing of the triangles (showed in Fig. 1) |
| Fig. 4: | Artificial effect for wrong correspondence |
We find the vertex in B by the same proportion relation between vertex in broken line and corresponding vertex in mapping arc.
Figure 5 is a sketch of the corresponding method. A-A’ and B-B’ is the key vertex set by user. In order to calculate the corresponding vertex C’ of vertex C in the target shape, we have
Correspondence of interior vertex: We constructed the corresponding vertex of the interior of the source shape in the target shape by deforming the source shape with boundary constrains.
| Fig. 5(a-b): | Correspondence of boundary vertex, (a) Source shape and (b) Target shape |
Our deforming calculation is implemented by using FEM method.
We follow the deformation law in continuum mechanics by applying FEM. In the source shape, the triangles are taken as linear triangle elements. We consider any element Tt whose coordinate is xT = (pi, pj, pk) in the source shape. Assuming its deformed coordinate as xT = (qi, qj, qk), we can express the deformation gradient of the element as:
where, the calculation of FT is the same as AT in a linear element. So, we can obtain the Green strain:
By applied Vigot expression, the strain can be rewritten as 6-d vector.
Assuming the material is St. Venant-Kirchhoff material and according to all elements, we write the deformation energy between the source and target shapes as:
| (6) |
where, X and x is the vector consisting of the source and target coordinates of all the vertex, respectively, μ and λ are material coefficients and V(•) measures the volume of a given configuration as the sum of elemental volumes. Therefore, determining the position of interior vertex in the target shape can be converted into the following optimization problem:
| (7) |
Infact, above equation is a solving deformation with boundary constraints by using nonlinear finite element. The solving processing can be founded in any relevant textbook.
| Fig. 6(a-b): | (a) Inverse and degeneration of triangle source shape and deformed shape and (b) Red triangles are probably inverse and degenerated |
In our implementation, we applied Newton-Raphson method to solve the nonlinear problem and LU decomposition to solve the linear system in every iterative step.
Our nonlinear optimization is solved once in the interpolation for the correspondence of vertex. However, the possible problem is inverse and degeneration of triangles in nonlinear calculation and interpolation (Fig. 6). In practice, we adopt the sign of deformation det(F) to judge the inverse or degeneration. That is, if det(F)≤0, the triangle is inverse or degeneration. Moreover, we applied the invertible finite element method to circumventing the case (Schmedding and Teschner, 2008).
RESULTS AND DISCUSSION
As for the 2D shape interpolation, our method can obtain the correspondence between source and target shape by deformation calculation with constraints. In summary, the interpolation can be implemented as follows:
| • | We triangulate the source shape by using Delaunay method |
| • | By the user interactive, the boundary correspondence is set between the source and target shape |
| • | According to Eq. 7, we solve the deformation problem with boundary constrain by using Newton-Raphson |
| • | By using polar decomposition of AT, we calculate the rotation and scale-shear matrix of each triangle |
| • | As every given t, we obtain the interpolation matrix BT of each triangle. Then, solving the Eq. 5 and obtain the interpolating coordinates of every vertex is implemented |
| Fig. 7(a-b): | Comparison of intermediate shape by, (a) Method proposed in literature and (b) Our method (t = 0.8) |
| Fig. 8: | Interpolating results (t = 0.2, 0.4, …, 1.0) |
We implemented all aforementioned methods in Microsoft windows 7 and Visual Studio 2008. The Intel MKL library for matrix calculation and the PARDISO API for solving linear systems were applied. All of the implementation is finished in a common laptop with an Intel i5 2540M CPU and 3GB memory.
Figure 7 shows the comparison between the method proposed in literature (Alexa et al., 2000) and our method when interpolating parameter t is 0.8. Our result in the domain market by red curve in Fig. 4 is more natural.
We showed the results in Fig. 8 of the simple shapes (vertex and triangles are 532 and 1029, respectively. Number of the boundary vertex is 128). During the calculation, the correspondence of the interior vertex cost 256 m sec. After the correspondence, the calculation of interpolation for each t cost 42 m sec. In comparison, the correspondence has more effect and efficiency.
CONCLUSION
This study mainly focused on the research and improvement on the algorithm of as-rigid-as-possible shape interpolation.
In 2-d shape interpolation and morphing, the correspondence between a source and target is always active research issue. After analyzing the existing rigid persevering algorithm, we give a solving scheme for the corresponding. In the scheme, the interior vertex mapping between a source and target shape is regarded as a deformation with boundary constraints from the source to target shape. Moreover, we apply the nonlinear FEM to solve the deformation problem. The corresponding problem is effectively solved. Experiments showed that our scheme can avoid remeshing mesh and improve the effect and efficiency of interpolation.
Our interpolating framework has mainly two limitations. One is that holding local feature of the source shape has not been concerned. The other is the option for physical parameters μ and λ has probably greater impact to the corresponding result. These problems will be research in our future study.
ACKNOWLEDGMENT
This study was supported by Zhejiang Provincial Natural Science Foundation (No. Y1091084), the Natural Science Foundation of China (No. 61170098), the foundation of Zhejiang Province Education Department (No. Y200804713) and Zhejiang province science and technology project (No. 2010C03015-2).