Research Article
A Corotational Finite Element Method for Example-based Deformation
School of Computer and Information Engineering, Zhejiang Gongshang University, Hanagzhou, Zhejiang, 310058, People`s Republic of China
Simulating the deformation of models is one of the active issues in computer graphics and has widely application including the movie industry, data entertainment etc. So, researchers have done a lot of excellent work around the model deformation simulation, editing and materials, interactive and other related issues. With the repaid development of obtaining a deformable model and three dimensions scanning, the example-based deformation method attracts more and more attention.
Most of existing technologies in example-based deformation mainly constructed energy functional reflecting examples effect. Then, calculate the model the position by solving the energy functional. Generally, the effect of the examples is make by construct a example deformation space. The energy functional includes two parts, which are deformation energy and the energy produced by examples. Both of parts can be constructed by a geometric method and physical methods. Moreover, the later can reflect the physical properties of the model material and has more realistic effect in some applications. In this paper, a framework for example-based deformation was presented. We construct the target energy functional in physical based context. In the deformation metric, we adopt the linear Cauchy and corotational compensation, or named warping stiffness technology is applied to tackle with non-linear problem. Our space discretization of the model adopts linear tetrahedron finite element.
Compared the previous methods, our method is simple and avoids calculation of the complex nonlinear optimization. Moreover, the proposed method is based on linear strain and the induced optimization can be worked out quickly by simply solving a linear system. In addition, our method is more forward and easier to implement in the existing code such as FEM and warping stiffness.
RELATED WORK
We will briefly review some related work on physically-based animation, example-based deformation and the other related topics.
Pioneering work in the field of physically-based animation was present by Terzopoulos et al. (1987). Later, a large number of work have been done including FEM, mass-spring and meshless etc. Lots of issues have been research which include such us the approximate solution of control PDE, the processing on large deformation and the technique of increasing speed and stability of the calculation (Witkin, 1997; Nealen et al., 2006). Specially, the co-rotation method (Hauth and Strasser, 2004), also named warping stiffness (Muller et al., 2002; Muller and Gross, 2004), has been widely apply to tackle the non-linear in large deformation. This method separates the large deformation into two parts which are the linear deformation and rigid rotation. In every simulating step, the stiffness matrix composes the linear stiffness and rotation compensation matrix. So, the nonlinear can be simplified and speeded up. Recently, the co-rotation technology has been a mainly method which be used to tackle non-linear problem in computer graphics.
In Frohlich and Botsch (2011) propose a framework example-driven deformation based on discrete shells which can generate statics deformation of triangle mesh combining examples and physical law. Recent, Sebastian Martin et al. (2011) propose a method of example-based method for elastic materials which implements the dynamics deformation following the physical laws. They adopted nonlinear green strain to create deformation metric space and constructed the solved energy functional including elastic deformation energy and the energy reflecting the examples effects. Then, they solve and get the deformable shapes of the elastic models which used the Newton-Raphson method. In their works, the nonlinear optimization solving is the nickel of calculating.
In the later, Schumacher et al. (2012) implemented a similar method for elastic-plastic deformation.
Inspired by previous work, we present a example-based deformation framework, which adopt Cauchy strain to metric deformation and co-rotation technology to compensate the artifact induced by large deformation. The advantage of this technology is reduce the amount of simulating calculate.
ENERGY FUNCTIONAL OF EXAMPLE-BASED DEFORMATION
Without loss of generality, the space discretization of models adopts a linear tetrahedron finite element in our method. As for a elastic model, firstly, we generate tetrahedron solid mesh including n nodes and m elements by using the tools such as TetGen, NetGen etc. Moreover, let X0∈R3n and x∈R3n denote position vectors describing undeformed and deformed configurations, respectively. x1, , xk∈R3n represents the position vectors of the example 1 to k.
In the following, we will construct deformable examples space, then define the solved energy functional by using Cauchy strain and co-rotation method.
Deformable examples space: As for a model domain Ω⊂R3, the movement of any point p∈Ω can be denote as p:ΩxR→R3: (X, 0)→x(X, t) where X is the initial coordinate, also called material coordinate, x is the coordinate after deformation. The deformation gradient can be calculated by F = ∂x/∂X. In order to metric deformation, we introduce linear Cauchy strain ε = (FT+F)/2-I. As for large deformation, the calculation based on strain can produce artifact. Following the warping stiffness technology, we will do rotation compensation in this study.
In a tetrahedron element, we calculate the co-rotation gradient as:
where, the 3x3 matrix R denotes the element rotation with respect to the initial position. I is 3x3 identity matrix. R can be gotten by the polar decomposition of deformation gradient. Let us rewrite the Cauchy strain as:
which is a rotation invariant.
Following the finite element method, the element strain is εe = B(RTx-X), where B is constant for a given element. In this paper, we denote the 3x3 strain matrix as a vector by using Voigt notation.
As for any shape of deformable model, There is a unique strain vector:
If given two deformation examples x1, x2 we can get the corresponding strain vectors ε1, ε2, respectively, we can construct the interpolation shape with geodesic interpolation method. That is:
(1) |
where, E(.) is the deformation energy between two shapes in the bracket. w is a given weight. If the material properties matrix of the model is D, the energy can be write as:
where, denotes the strain of the i-th element. is the element volume. So, solving equation 1 can be converted to solving a equation:
In the above equation:
is adopted co-rotation method, where K is a linear stiffness in FEM, , is the element rotation matrix of in m-th shape and n-th shape respectively. R is the whole rotation matrix of current shape in the calculation. In our method, the R is gotten a by iterative method. Similar to be used to simulation implementation in plenty of literatures, the effect in our interpolation is acceptable as long as the calculating step, that is the incremental of w is sufficiently large. Figure 1 show a interpolation of a twist and bend cube model.
As above, our interpolation is iterative and need not to interpolate the rotation as MeshIK. In fact, following the tetrahedron FEM, the element strain added by weight ε(w) = wB(RTx-X), where B is a constant matrix related on element geometry.
Fig. 1: | Interpolation of a twist and bend cube |
The advantage of our framework is avoiding the nonlinear solving induced by interpolating rotation.
So, our deformation space will adopt the rotation and coordinate. That is, as for given deformation example xi, we will refer to as base quantity in following example-based deformation.
Energy functional of example-based deformation: Our deformation functional includes deformation energy and kinetic energy, where the deformation energy affected by examples called example energy. The kinetic energy can be calculated by kinetics. According to continuum mechanics theory, our example energy adopt following which denotes the elastic potential energy between current shape and the closest shape in the example space:
(2) |
where, w = [w1, , wk]T is the weight vector of the examples, η is a coefficient between 0 and 1. η should be set according to specific application, that is, If η = 0, the deformation is not affected by the example and. and if η = 1, the deformation is only driven by examples, while the elastic deformation is omitted.
Instead of using:
we use Eq. 2 for more conveniently setting energy weight latterly and more explicit physical meaning. In addition, strictly, the Eq. 2 should be added constraints which are:
And wi≥0. These constrains restrict the example space to interpolations. But in the implementation, we may relax appropriately this condition. We will talk about it in the later.
Follow the minimum energy principle, the energy functional of example-based can be written as:
(3) |
T is the kinetics energy and:
is the work of the external fext.
EXAMPLE BASED DEFORMATION
We can consider example based deformation to optimization for the energy J. That is, we will solve following:
(4) |
we will respectively introduce the solution in the case of the dynamics and statics.
We apply implicit Euler integration scheme to kinetics energy, i.e.,:
where, v is velocity vector, the subscript represents the mapping time step. In addition, as mentioned in EBEM, small extrapolations are in general not harmful, so we exert the constraints weakly by add simple quadratic energies. The energy (Eq. 3) can be written as:
(5) |
where, the coefficient λ is a Lagrange multiplier and σ is a penalty parameter.
Fig. 2(a-d): | Example-based deformation of a cat (a) Fixed right hind leg, drag the right front leg, (b) Fixed two hind legs, drag the head, (c) Fixed three legs, drag the fourth leg, (d) Fixed two hind legs, drag two front legs a and c are initial models b and d are example models |
Fig. 3(a-b): | Deformation of a horse, (a) Fix the both hind legs and drag the head and (b) Fix the both hind legs and drag the right front leg, a is initial while b is example model |
Note that small extrapolations are in general not harmful, we enforce also weakly the constraint wi≥0 by adding simple quadratic energies:
to Eq. 5, where the parameter σ is set reasonably by a user. In our experiments, we adopt:
where, E is a Yangs modulus of the materials and V is the volume of the model for simulation.
After expanding Eq. 5 by substituting Eq. 2, minimizing it corresponds to estimate that the gradient of Π, which is subject to x, w and λ, is zero. Thus, the optimization can be deduced and converted to solving a linear system as Eq. 6:
(6) |
In the above equation, the parameter η is the importance metric of examples during the deformation generation. After exerting enough constraints including position etc., we can solve the system and get the value x which is coordinate vector of the deformable models nodes.
Compared with the previous method in literatures, our method directly change the example based deformation into iterative linear system and avoid calculation of the Hessen matrix in non-linear solution. In addition, our method is more forward and easier to implement in the existing code such as FEM and warping stiffness.
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. The performance of our results is listed in Table 1. All data are collected in a common laptop with an Intel i5 2540M CPU and 3GB memory.
Figure 2 and 3 give the simulating results for example-based deformation of a cat and horse. The performance of calculation is shown Table 1.
Table 1: | Performance of simulation |
We presented a corotational FEM for example driven deformation in this paper. By constructing an example deformation space with corotational technique, we proposed an efficient simulation solver of the deformation energy function based on linear Cauchy strain metric. Moreover, we converted the optimization into solving a system and simplified the problem. Comparing with the previous nonlinear optimization solutions, our computing method is easier to implement and is able to achieve much higher performance.
The example driven deformation has many applications for generating special effects in computer graphics and other relevant domain. In the future, we will extend our work to study on mesh based deformation for special materials such as plastic and anisotropic materials.
This research was supported Zhejiang Provincial Natural Science Foundation (No. Y1091084), Zhejiang Province Science and Technology project (No. 2010C03015-2). Zhejiang province Department of Education Research Foundation (No. Y200804713).