Thibaut Le Naour
email: tlenaour@gmail.com

Nicolas Courty
email: courty@univ-ubs.fr

Sylvie Gibet
email: sylvie.gibet@univ-ubs.fr

Real-time mesh animation from low dimensional positional constraints

Keywords: Computer Graphics, Character Animation, Computational Geometry and Modeling

The challenge proposed by this study is to reconsider the entire animation pipeline for data-driven character animation. By observing that significant loss of information and precision occur in the traditional animation pipeline (skeleton reconstruction from markers, rigging and retargeting), our goal is to directly control at interactive framerates articulated meshes from a low number of positional constraints. Our method builds on top of efficient deformation techniques and proceeds as follows: an original mesh is embedded into a coarse volumetric control lattice which contains simplified information from the initial reference mesh, skeleton elements and marker locations. An iterative method is applied on this structure which preserves the geometry details, the bones lengths, and the associated joint limits. We show the ability of our approach to animate and interactively deform high resolution models from a low-number of markers while retaining the subtleties of the motion. It notably allows to entirely skip the tedious rigging phase.

I. INTRODUCTION

Interactive and natural looking shape animation and deformation of articulated bodies is one of the key topics in computer graphics. Many techniques have been proposed with different approaches from the perspective of data-driven animation, e.g. skeleton-based, or positional-constraints-based animation. The traditional pipeline of character animation is classically composed of two stages: first, the skeletondriven animation, i.e. joints rotations over time, is computed from positions of motion capture markers. This process can be rather approximate, in particular for determining articulatory centers and axis of rotation, especially for complex articulatory systems such as hands. It sometimes requires the intervention of designers or automatic processing involving inverse kinematics. Secondly, the mesh vertices of an existing 3D mesh are bound to one or several joints of the skeleton through a rigging operation. This last step is a tedious task which is often conducted manually by infographists. Several drawbacks characterize this animation pipeline: (i) difficulties to adapt the approximate skeleton with the mesh , generally implying retargeting techniques that tend to alter the original data; (ii) difficulties to deal with too few markers , which most often amplifies the manual post-processing and correction steps; (iii) limited control over the mesh through the skeleton; the inconsistency between the skeleton and mesh models leading consequently to some incoherencies (mesh collisions, unnatural foldings or deformations, etc.) along the animation.

The challenge proposed by this study is to re-consider the entire animation pipeline for data-driven character animation. We focus especially on the animation of complex systems driven by low dimensional positional constraints, and in particular by few trajectories of markers. Our approach is strongly inspired by shape deformation techniques which use markers as control points to animate the character's mesh [START_REF] Krayevoy | Boneless motion reconstruction[END_REF]], [START_REF] Stoll | A volumetric approach to interactive shape editing[END_REF] Stoll, de Aguiar, Theobalt and Seidel]. However our method differs from these works as it implicitly integrates all the properties induced by an underlying skeleton (the segment lengths and the joint limits) while preserving the details of the mesh geometry. The introduction of skeleton specific constraints compensates for the use of a small number of input data. As a consequence, our approach enables to control the mesh structure by using few trajectories of captured marker positions. It also gives the opportunity to drive the animation by editing manually some mesh vertices, or by using solely positions of the skeleton joints as control inputs. It is demonstrated over several examples of articulated bodies animation. We focus in particular on a difficult case which is the animation of high quality hand models. Indeed these complex articulated models include many degrees of freedom and constraints that make the operation of rigging tedious and pore to errors. Methodology. Our novel interactive mesh animation method relies on a volumetric control mesh, deformed by control points. The different steps of the approach are illustrated by the Figure 1. More specifically our method follows the following processes: (i) the control mesh is built as a tetrahedral mesh which has the property of two-manifold, implying no intersection and no hole, thus leading to consistent deformation properties. It includes the original mesh and takes into account internal constraints derived from the skeleton joints, and external control points representing the markers; (ii) Then, we apply a volumetric deformation preserving the surface details and skeleton properties; consequently the deformation process respects the constrained positions induced by the markers; (iii) Simultaneously, we use a skeleton described by a hierarchy of joints updated at each step of the deformation, and satisfying joint limits. These properties are then backward integrated into the previous step; (iv) As suggested by Borosan [START_REF] Borosán | Hybrid mesh editing[END_REF], we optionally improve this last step by using an intermediate and simplified coarse mesh including the skeleton and markers properties. More precisely, the method consists in applying the deformation on this coarse mesh that drives the original mesh by using a cage-based method called Green Coordinates (GC) [START_REF] Lipman | Green coordinates[END_REF]Lipman, Levin and Cohen-Or].

Fig. 1. Our animation pipeline: with a short number of markers' trajectories (left image), our method first start by building a volumetric control mesh (middle image) which embeds the rigidity information of the mesh expressed as a skeleton endowed with joint limits; this control mesh is then used to animate the full resolution mesh (right image)

Contributions. Our method builds on top of recent deformation and marker-based animation techniques. Its originality stems from a strong coupling of an internal skeleton structure with the deformation process. This coupling is operated inside an optimization procedure which alternates an efficient volumetric shape deformation and the enforcing of skeleton specific constraints. As a result, it allows to bypass the skeleton reconstruction of the original animation pipeline and control directly the mesh from the motion capture markers. Contrary to previous works, one of the main advantage is to allow the introduction of non-linear constraints such as the enforcing of joint limits. The resulting mesh animation is characterized by an enhanced rigidity and volume preservation of the mesh structure. Our method also implicitly embeds a retargeting step, which allows to conveniently transfer animations to multiple target meshes. Finally, it is robust and particularly well suited for interactive character animation.

After reviewing previous work in Section 2, we will describe in Section 3 the method for constructing the different mesh structures and explain how the deformation method can be applied to these structures for generating realistic animation. We will then show in Section 4 the benefits of our method in several practical applications with multiple sets of data, before concluding and giving perspectives of this work.

II. BACKGROUND

Many different approaches have been proposed to tackle the problem of generating realistic animation of characters while maintaining plausible shape deformation. Most of them concern the use of a skeleton as a guide to deform and animate the mesh, for example using linear skinning [START_REF] Lewis | Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation[END_REF]Lewis, Cordner and Fong] or using dual quaternions interpolation [START_REF] Kavan | Geometric skinning with approximate dual quaternion blending[END_REF] Kavan, Collins, Žára and O'Sullivan], and more recently a geometric technique to make realistic folding around joints [START_REF] Vaillant | Implicit skinning: Real-time skin deformation with contact modeling[END_REF]. However, these methods animate meshes only through the control of a skeleton. With our goal to drive the mesh with marker trajectories, we focus on the two following thematic: animation of models driven by markers, and mesh deformation using skeleton constraints.

Animation driven by markers

Several studies have investigated marker-driven animation techniques. In this line of research, Park et al. [START_REF] Park | Capturing and animating skin deformation in human motion[END_REF]] propose a technique to animate mesh models from 3D captured motion. The binding between the mesh and the markers is achieved by establishing a skinning relationship obtained through the segmentation of rigid areas of the mesh. The animation results, which integrate the geometry variations induced by muscles' deformations, are very realistic. However, their method requires a large number of markers (several hundred). On the contrary, the method proposed by Sumner et al. [START_REF] Sumner | Mesh-based inverse kinematics[END_REF] proposes the animation of a mesh from a low number of control points, thanks to a learning space determined from mesh samples. Recently [START_REF] Wheatland | Automatic hand-over animation using principle component analysis[END_REF]Wheatland, Jörg and Zordan] used also a learning method for producing high quality hand motion using a small number of markers by establishing the correspondence between markers and joint angle trajectories with the help of a reference database. Zordan et al. [Zordan and Van Der Horst(2003)] also propose a dynamical system driven by 3D captured motion, which guarantees several physical properties: the global rigidity of the system, the preservation of segment lengths and the consideration of joint limits. This approach is closely linked to ours, but is applied to physical bodies instead of geometrical shapes, and therefore it does not take into account all the geometrical details during the animation.

Closer to our approach, Krayevoy [START_REF] Krayevoy | Boneless motion reconstruction[END_REF]] and Stoll [START_REF] Stoll | A volumetric approach to interactive shape editing[END_REF]Stoll, de Aguiar, Theobalt and Seidel] use a deformation technique called Mean-value Encoding for the former one, and the Laplacian operator for the latter one to directly drive the mesh by markers. Their objectives are the same as ours, but the first approach does not take into account the properties of the skeleton and requires a morphology consistent with the cloud of markers as input. The second study proposes to use a coarse volumetric mesh that enables interactive shape editing. The method alternates a Laplacian deformation technique and a gradient-based differential update process, making it stable even for large deformations. It produces high-quality mesh animations from motion capture data. Although very promising, the method does not incorporate same skeleton properties such as the length of bones or joint limits, which are essential to guarantee natural deformations.

Mesh deformation

Other approaches directly focus on mesh deformation and edition techniques, without skeletal information. In order to produce high-quality deformations, several recent works have been interested in preserving surface details of the geometry. Some of them, based on Laplacian differential coordinates [START_REF] Sorkine | Laplacian surface editing[END_REF]Sorkine, Cohen-Or, Lipman, Alexa, Rössl and Seidel], [Alexa(2003)], [START_REF] Lipman | Differential coordinates for interactive mesh editing[END_REF]Lipman, Sorkine, Cohen-or, Levin, Rssl and peter Seidel], facilitate interactive mesh editing while producing natural-looking deformations, but they fail to handle large rotations. In order to solve the problem of large deformations, several methods derived from this approach have been developed. In particular, the ARAP deformation paradigm, which stipulates that the mesh is directly linked to the local rigidity of the shape, has been proposed to edit surface meshes subject to large amplitude rotations [Sorkine and Alexa(2007a)].

These surface differential methods have been extended to volumetric graph Laplacian representations, with the idea to preserve the volume during the deformation, and to enable large deformations (i.e [START_REF] Zhou | Large mesh deformation using the volumetric graph laplacian[END_REF]Zhou, Huang, Snyder, Liu, Bao, Guo et al.], [START_REF] Huang | Subspace gradient domain mesh deformation[END_REF], [START_REF] Stoll | A volumetric approach to interactive shape editing[END_REF]Stoll, de Aguiar, Theobalt and Seidel], [START_REF] Zhao | Rigidity constraints for large mesh deformation[END_REF]Zhao, Liu, Peng and Bao], [START_REF] Jacobson | Bounded biharmonic weights for real-time deformation[END_REF], [START_REF] Zhao | Volumetric subspace mesh deformation with structure preservation[END_REF]]). Among them, several include skeleton properties. For example, Huang et al. [START_REF] Huang | Subspace gradient domain mesh deformation[END_REF] present a subspace iterative solver for mesh deformation constrained by skeleton and volume properties. Their system enables to maintain the segment lengths during the deformation, but fails to preserve joint limits. This method has been recently extended by Zhao [START_REF] Zhao | Volumetric subspace mesh deformation with structure preservation[END_REF]] to reach the volume preservation during the deformation. Closer to our objectives, Shi et al. [START_REF] Shi | Mesh puppetry: Cascading optimization of mesh deformation with inverse kinematics[END_REF] present a technique that preserves the same previous properties with the approximate respect of joint limits. Indeed, their system enables to satisfy an angle constraint along a plane, but does not exactly preserve the joint limits on the three degrees of freedom. Recently [START_REF] Jacobson | Bounded biharmonic weights for real-time deformation[END_REF] use bounded biharmonic weights to intuitively deform geometries associated with a skeleton structure.

Concerning the methods using ARAP, Zhang et al. [START_REF] Zhang | Skeleton based as-rigid-as-possible volume modeling[END_REF] have demonstrated the benefit to introduce the concept of rigidity in the interior of the surface mesh to improve the preservation of the volume. Zhao [START_REF] Zhao | Rigidity constraints for large mesh deformation[END_REF] propose to apply ARAP with a volumetric graph associated with rigidity constraints in particularly to avoid unnatural volumetric distor-tions. Latter Borosan [START_REF] Borosán | Hybrid mesh editing[END_REF] combine ARAP with the mean coordinate values method to deform faster high-resolution meshes. Faraj and all [START_REF] Faraj | Robust and scalable interactive freeform modeling of high definition medical images[END_REF] also propose in a problem of volumetric data editing to use ARAP on cage structures before applying the deformation with the Green Coordinate method. The other benefit to use a lattice structure is to deform all kinds of meshes since the mesh to deform needs to be without self intersection and holes.

A more general method than the ARAP principle uses the concept of elastic energy. Introduced by Chao [START_REF] Chao | A simple geometric model for elastic deformations[END_REF], it allows to produce high quality deformation on tetrahedral models and presents several advantages as the preservation of the rotation and the robustness of the method for large transformations. This concept has been extended first in the work of [START_REF] Mcadams | Efficient elasticity for character skinning with contact and collisions[END_REF]McAdams, Zhu, Selle, Empey, Tamstorf, Teran et al.], and then in Kavan et al. work [Kavan and Sorkine(2012)] to solve the general problem of skinning around character articulation. However, as the classical skinning methods, these techniques need a good determination of the weights applied to each vertex of the mesh.

Our approach inherits the advantages of recent differential techniques, applied on volumetric meshes for animation of characters driven by captured motion points. We use a tetrahedral mesh representation of the articulated system, thus ensuring the preservation of the internal mesh volume and avoiding joint artifacts. In addition, we integrate within this mesh skeleton the internal skeleton structure with its rigidity properties: length of bones, joint limits, etc.

III. SYSTEM OVERVIEW

Our approach aims at animating and deforming articulated bodies. This deformation can be possibly driven by motion capture markers, and the following description does not make any assumption on the source of animation data. In Figure 2 an illustration of the pipeline is given through an example of a hand animated by motion capture markers. Those markers are located at specific places over the hand's skin, with no assumption on their positioning with respect to joints. From a highly detailed reference mesh of a hand, that can be morphologically different from the captured hand, a volumetric control mesh is automatically constructed. This volumetric control mesh is built by directly taking the reference mesh and by adding the skeleton structure and marker points (note that the binding between the markers and the reference mesh is established by the volumetric control mesh). In the remainder of this paper we will call original mesh the reference mesh, and control mesh, the volumetric mesh. The control mesh is deformed by minimizing over time the distances between the marker positions and the corresponding vertices of the control mesh. This deformation tends to preserve the shape of the original mesh while taking into account the rigidity constraints induced by the skeleton. Note that the original mesh is included into the control mesh, thus the deformation of the control mesh induces the deformation of the original mesh.

IV. VOLUMETRIC MESH DEFORMATION WITH SKELETON

CONSTRAINTS

In this Section, we detail the different operations of our animation pipeline. We first begin by explaining how the control mesh is built. We then proceed with the deformation pipeline, with a focus on the preservation of the skeleton properties. The deformation of the original mesh with Green coordinates is then detailed, before giving an overall view of the complete algorithm.

A. Pre-processing and mesh-skeleton coupling

Regarding the skeleton, several methods are available to automatically create it with respect to a reference mesh (e.g [START_REF] Au | Skeleton extraction by mesh contraction[END_REF]Au, Tai, Chu, Cohen-Or and Lee]), but it is also possible to construct it manually with a commercial software (this step takes a few minutes and does not require specific knowledges). At this step, no explicit relations exist between the mesh and the skeleton apart from the relative positioning in the 3D space.

Then we create the volumetric mesh by using a Delaunay tetrahedrization applied on the original surface mesh. This tetrahedrization also includes:

• the set of markers positions. They are associated to vertices of the control mesh. They are manually positioned at the right place according to the original hand markers (see Figure 2, step 3) (possibly outside of the original mesh), • the vertices and edges corresponding to a discretization of the skeleton (blue points and green edges in Figure 2). This discretization is performed by a spatially regular sampling of the skeleton. The length of the sampling step allows to control the number of points associated to the skeleton in the tetrahedrization process, and as such can act as a tradeoff parameter for the overall computational complexity. The Delaunay tetrahedrization is a complex process and several works have been proposed on the subject [START_REF] Bridson | Adaptive physics based tetrahedral mesh generation using level sets[END_REF]Bridson, Teran, Molino and Fedkiw], [START_REF] Cutler | Simplification and improvement of tetrahedral models for simulation[END_REF], [Shewchuk(1998)]. We chose the so-called piecewise linear complex (P LC) method designed by Miller et al. [START_REF] Miller | Control volume meshes using sphere packing: Generation, refinement and coarsening[END_REF]Miller, Talmor, Teng, Walkington and Wang], and implemented by Hang Si et al. [Si(2006)], which proved to be robust and flexible. In the end, the resulting mesh is closed and composed of triangles, which are then ready to be deformed by the following method.

B. Volumetric ARAP mesh deformation

We present here our volumetric mesh deformation process. We first begin by recalling the basic principles of Laplacian surface editing [START_REF] Sorkine | Laplacian surface editing[END_REF]Sorkine, Cohen-Or, Lipman, Alexa, Rössl and Seidel], before presenting an adaptation of the ARAP algorithm to consider volumetric cells. Laplacian Surface Editing (LSE) Let the closed triangularized structure, that is the control mesh characterized by V = (V , E), where E describes the connectivity, and V = v 1 , ..., v n are the Euclidian coordinates of the mesh vertices. From V and a set U = u 1 , ..., u m of control vertices, we can compute the new positions V = v 1 , ..., v n minimizing the quadratic function given by

E(V ) = E l (V ) + E p (V ).
(1)

The first term E l that penalizes the difference between the differential coordinates after reconstruction can be written as

E l (V ) = n i=1 δ i -L(v i ) 2 , ( 2
)
where L is the Laplace-Beltrami discrete operator with cotangent weights (for details, see [START_REF] Pinkall | Computing discrete minimal surfaces and their conjugates[END_REF]Pinkall, Juni and Polthier], [Meyer et al.(2002a)Meyer, Desbrun, Schröder and Barr]) and δ i = L(v i ) is the differential coordinate for the vertex i. The second term E p penalizes the changes of position of control points and is defined by

E p (V ) = m i=1 v i -u i 2 . ( 3
)
Equation 1 can then be minimized as a (n + m) × n overdetermined linear system

L I u V = ∆ U (4)
where I u is the index matrix of U . The reconstructed shape looks generally natural when low amplitude rotations are applied. For large transformations, Sorkine [Sorkine and Alexa(2007b)] proposes a non linear solution called ARAP to preserve the local rigidity of each cell of the mesh.

ARAP modeling From a first estimation of V given by Equation 1, the goal of ARAP is to find iteratively the new values of differential coordinates preserving the local rigidity. Thus, if the cell C i of the mesh corresponding to the vertex i is deformed into a cell C i , the approximate rigid transformation between C i and C i can be expressed as a rotation matrix which minimizes

E(C i , C i ) = j∈N (i) w ij (v i -v j ) -R i (v i -v j ) 2 (5)
where N is the set of vertices connected to the vertex i and w ij is the cotangent weight of vertices i et j defined by

w ij = 1 2 (cotα ij + cotβ ij ) (6)
(see [START_REF] Sorkine | Laplacian surface editing[END_REF]Sorkine, Cohen-Or, Lipman, Alexa, Rössl and Seidel], [START_REF] Meyer | Discrete differential-geometry operators for triangulated 2-manifolds[END_REF]Meyer, Desbrun, Schröder and Barr] for details). Finally, solving this problem can be rewritten as an iterative problem, each iteration being expressed as

E(V ) = E a (V ) + E p (V )
, with E a defined by:

E a (V ) = n i=1 δ A i -L(v i ) 2 (7)
where δ A i is a term evaluated at each iteration. In the remainder of the paper we use the shorthand notation ∆ A = δ A i . Volumetric ARAP This algorithm is efficient on surface meshes but can be improved by extending it to a volumetric setting. The cell can now be considered as an element of a 3-manifold, and as such its energy is thus linked not only to its volume but also to its global shape. The Laplace-Beltrami operator is also virtually defined anywhere on this manifold provided that it is differentiable everywhere, which is guaranteed by the tetrahedrization process.

As described by the work of Meyer [START_REF] Meyer | Discrete differential-geometry operators for triangulated 2-manifolds[END_REF]Meyer, Desbrun, Schröder and Barr], the surfacic Laplacian Beltrami operator can be readily generalized to 3Dmanifold. We therefore propose to extend the ARAP surfacic method by using this operator applied on 3D-manifold. The weight w ij is now defined by:

w ij = 1 6 k l k i,j cotα k ij ( 8
)
where k is the number of tetrahedrons sharing the edge (v i , v j ), l k i,j is the length of the edge opposite to (v i , v j ), and α k ij is the dihedral angle opposite to the edge (v i , v j ). Yet, while this method provides successful results, it does not implicitly allow a good preservation of the skeleton properties: rigidity around segments, length of segments and joints limits (see Figure 3). In the next section we will see how to consider those implicit constraints in the deformation process.

C. Preservation of skeleton properties

As illustrated by the Figure 2 (step 3), the skeleton structure is embedded into the tetrahedrization. The positions of joints are represented by a set of vertices and the segments between joints are decomposed into a set of edges that are included into the control mesh. Two steps are considered. First, we introduce a constraint that preserves simultaneously the collinearity between the edges of a same segment and the lengths of segment edges. This constraint produces a deformation induced by a novel rigidity constraint that follows the skeleton structure, as shown in Figure 3. Second, we propose to add joint limits to produce realistic postures. As these new constraints are not linear, and joint limits are hardly expressed with our formulation (no angular representation), we solve this problem in two steps through an alternating descent method:

1) From the current configuration of the skeleton provided by the deformation of the control mesh, we compute a new skeleton posture close to the current one but respecting the skeleton properties, 2) Then, the new posture is introduced into the previous problem in terms of differential constraints.

These two steps are then repeated until convergence. This formulation allows at the same time to deform the control mesh by minimizing the previously described volumetric ARAP constraint and maintain the correct properties of the skeleton. A formalization of this method is proposed below.

Skeleton constraints as a linear problem: Each segment of the skeleton is decomposed into several edges. Given e ab the edge between the vertices a and b, we consider the differential vector γ ab = -γ ba = v a -v b , and the length defined by γ ab = γ ba = d ab . Let us remark that those differential coordinates both encode the direction and the length of the edge. In the following we denote E S , the set of edges which belong to the skeleton. This can be formalized in the following quadratic energy function E d :

E d (V ) = e(i,j)∈E S γ ij -D ij (V ) 2 , ( 9
)
where

D ij (V ) = v i -v j .
Denoting by Γ the vector containing all possible values of γ ij that match the distances and colinearity criteria, Equation 9is therefore equivalent to solve the following linear system in the least square sense

DV = Γ ( 10
)
where D, matrix of size card(E S )×n, is a discrete differential operator which role is to compute all the differential coordinates of every segments of E S . More precisely, a row of D is given by the values 1 and -1 at the i -th and j -th indices, 0 elsewhere. Now we turn on to the determination of the Γ differential vector.

Determining Γ: The differential coordinates stored in Γ are extracted from a correct skeleton respecting the rigidity constraints as well as its joint limits. This is achieved through a two-steps procedure: (i) First, the current approximate posture of the skeleton S c is extracted from all the vertices that belong to the skeleton. The skeleton is traversed and for each segment, the edges orientations are given by averaging all of the edges of the segment. The lengths of the edges are also restored to their initial, constant values. This intermediate skeleton respects the rigidity constraints but may fail in respecting the joint limits. (ii) We then project S c into the space of admissible postures by simply thresholding the joint angular values to the closest acceptable value. This final step produces a new skeleton S a .

Γ is then directly computed from S a , through the direct computation of the vectors γ ij . Figure 4 illustrates the deformation of a hand before and after adding constraints. The posture of the hand looks more natural in the latter case, as the rigidity of all the fingers degrees of freedom is better preserve, and as unnatural rotations are forbidden along the fingers.

Projecting S c into the space of admissible postures: We present below: (i) first how we calculate the rotations from the displacement of the joints' positions, and (ii) second how we correct the postures of the skeleton during the deformation.

In a first step, we calculate the orthonormal basis for each joints as illustrated by the figure 5. For example, considering the positions p 0 , p 1 and p 2 of the joints j 0 , j 1 and j 2 , we define the Orthonormal basis B 1 of j 1 with the axis x 1 , y 1 et z 1 by:     

x 1 = p 12 / p 12 z 1 = x 1 × p 01 / p 01 y 1 = x 1 × z 1
x 1 is the orientational term and z 1 et y 1 compose the rotational of the joint rotation (see [START_REF] Aristidou | Fabrik: A fast, iterative solver for the inverse kinematics problem[END_REF]] for more details). Next we define manually for each joint the joint limits around each axis x i , y i and z i . Moreover, the skeleton is classically defined as an hierarchy of joints. Let the frame j and the joint i defined by J i , the absolute transformation of J i is defined by

B j i = B j i-1 * B j,Rel i
where the term Rel means that the transformation B Rel i is expressed in the coordinate system B j,Rel i-1 . Finally,

B j i = k=i k=0 B j,Rel k
where k = 0 corresponds to the root node of the skeleton.

Considering a skeleton with n joints and a vector of relative rotation θ j,Rel i = {θ j,Rel 0 , ..., θ j,Rel n } corresponding to the variation of rotation in each basis B i , the absolute transformation of J i is then

T θ i = k=i k=0 B Rel k * θ Rel i .
Note that T is composed by a rotation and a translation.

We follow then the method of Blow [Blow(2002)] to calculate the angle θ j,Rel i , by using a quaternion from the absolute posture of the skeleton. As illustrated by the figure 5, we consider for example the vector p 01 and the vector

p j 01 = B -1 i * p j,Abs

01

, where p j 01 is the vector expressed in the coordinate system of j i . We determinate the quaternion q 0 = (a 0 , α 0 ) by:

   a 0 = (p 01 / p 01 ) × (p j 01 / p j 01 ) α 0 = arccos (p 01 .p j 01 )/( p 01 × p j 01 )
As described in the work of Blow [Blow(2002)], it is now easy to correct each quaternions q i by respecting the joint limits given manually before. Finally, we calculate the final posture of the skeleton by:

T θ i = k=i k=0 B Rel k * θ Rel corrected i .
Control mesh deformation: Finally the system computes a new configuration of the control mesh by minimizing the quadratic function:

E(V ) = w l E a (V ) + w u E p (V ) + w d E d (V ), (11)
where the weights w l , w u and w d are used to balance between the three energies: Laplacian, positional constraints and distance constraints.

D. Optimization

Fig. 6. Examples of our mesh editing with user input deformations

Our system enables to produce realistic animations, but as suggested by Borosan [START_REF] Borosán | Hybrid mesh editing[END_REF]Borosán, Howard, Zhang and Nealen], the computation time can be easily improved by applying our method to a simplified control mesh which drives then the original mesh.

In this way, a coarse mesh usually known as the cage mesh [Meyer et al.(2002b)Meyer, Barr, Lee and Desbrun] is created, which covers the original mesh. Note that for complex structures such as hands, this cage mesh should preserve at best the morphology of the system; especially, it should take into account more details around the joints to best preserve the geometric features for large deformations. Some works have been proposed to create automatically this kind of structure (i.e [START_REF] Xian | Automatic generation of coarse bounding cages from dense meshes[END_REF]Xian, Lin and Gao], [START_REF] Xian | Automatic cage generation by improved obbs for mesh deformation[END_REF]Xian, Lin and Gao]). In our application, we simply combined a mesh simplification by edge collapsing and a global upscaling so that the cage mesh covers the original mesh. This resulting cage mesh is characterized by the absence of holes or self intersections. Then, the control mesh is built from this cage mesh and as presented in the section IV-A, we include into it the skeleton and markers information. Finally, as presented in the next paragraph, we use the Green Coordinates method (GC) [START_REF] Lipman | Green coordinates[END_REF]Lipman, Levin and Cohen-Or] to deform the original mesh.

Let the original mesh denoted by R = (X, F ), where F describes the set of faces of R and X the set of Euclidan coordinates of the vertices. The control mesh V is composed of a set of tetrahedrons, also called cages, produced by the Delaunay tetrahedrization. Each cage C is defined by C = (V c , F c ) where V c is the set of vertices of the cage (4 in our case), and F c the set of faces (4 also). The GC method determines an application A which computes the transformation of the vertex x belonging to the cage C into the vertex x as follows

x = A(x, C ) = i∈|V | φ i (x)v i + j∈|F | ψ j (x)s j n(f j ) (12)
where C is the deformed cage of C. The "coordinates" φ and ψ, as well as the coefficients s are calculated off line. Their determination is described in [START_REF] Lipman | Green coordinates[END_REF] Lipman, Levin and Cohen-Or]. As shown in Figure 6 and Table I, this technique allows us to reduce the preprocessing time as well as the computation time during the animation.

E. Algorithm

Finally, we propose to use an iterative algorithm to solve simultaneously the volumetric ARAP deformation and the preservation of skeleton constraints. We evaluate the general error of the algorithm by 0.5 * E RRM S + 0.5 * E ED where E RRM S is the relative root mean squared error given by Equation 5and

E ED = (i,j)∈E S |d ij -d ij |/d ij with d ij and
d ij are the lengths of the edge e ij respectively before and after the deformation. We test the convergence criteria of an iteration by evaluating the change of the general error compared to the previous iteration. The algorithm converges rapidly because of a good starting point is given by the previous step in the motion. The overall algorithm is given in algorithm 1.

Algorithm 1: Control mesh deformation with implicit skeleton constraints Data: X: Vector of original vertices of the original mesh X : Vector of positions of the original mesh after editing V : Vector of original vertices of the control mesh V : Vector of positions of the control mesh after editing U : A set of position constraints V: the original control mesh

1 ComputeGreenCoordinates(X, V)

2 //Laplacian and positionnal constraints (offline):

3 V = argmin V E l (V ) + E p (V )
4 while playing animation do 5 while not convergence do

6 form Γ from argmin V E s (V , V) (equation 9), preconditionned with V ; 7 V = argmin V   w l L w u I u w d D   V =   ∆ A w u U w d Γ   8 X = GreenCoordinates(V , V) V.

IMPLEMENTATION AND RESULTS

This Section shows the practical advantages of using our method to animate an articulated mesh driven by different sets of low dimensional input. Our C++ implementation uses the Cholmod sparse Cholesky solver [START_REF]Algorithm 887: Cholmod, supernodal sparse cholesky factorization and update/downdate[END_REF]Chen, Davis, Hager and Rajamanickam] on a Core2 Duo with 2.7GHz and 3GB RAM on Windows XP Pro. The Cholmod library is able to solve large sparse linear system using a Cholesky factorization. This resolution method is fast enough for real time animation or interactive mesh editing.

Model (percentage of mesh control information form original mesh)

Figure 6 (b) (0.24%) Figure 6 We show through various examples that our method is efficient to produce high quality animation in real time. These experiments require a preliminary step of creating a skeleton and a cage geometry corresponding to the mesh. These two elements are achieved rather fast (about 10-15 minutes) by a student.

In the first example, we apply the method to the animation of a mesh composed of 8256 vertex and 15198 triangles, driven by only 36 markers: eight markers for each hand, two for each foot, four for the head and twelve for the rest of the body). The markers are located inside and outside the target mesh according to the difference of morphology between the captured model and the target geometry. As shown in figure 7 and in the accompanying video, the movement of the markers are successfully tracked and the resulting deformations look very natural. For a quantitative evaluation of our algorithm, table I shows that the constraints are well preserved and figure 8 shows the good convergence of our alternating descent approach which minimizes simultaneously the deformation energies while respecting the skeleton properties.

In the second example, we animate two-hand meshes from a sign language motion. Sign language animation of hands is very critical: it requires high precision, especially for hand configurations. Small changes in some postures or trajectories might indeed modify the meaning of the produced signs [START_REF] Gibet | The signcom system for data-driven animation of interactive virtual signers: Methodology and evaluation[END_REF]. Each hand is represented by a geometry of a high resolution (5023 vertices for 10042 triangles) and driven by few control points (eight markers for each hand). The mesh model was acquired frorm the Aim@shape repository and symmetrized for the demonstration purpose. Our original hand motion is represented by some low dimensional and low quality signals extracted from markers trajectories. This poorness of the captured motion is due to several factors. First, occlusions occur frequently in sign language statements, and the low number of markers does not allow us to reconstruct complete trajectories. This takes the form of missing samples or markers inversion in some markers trajectories. Such motion data requires heavy post-processing which also introduces some errors. When observing the animations in the accompanying video, we thus notice at some points jerky motion, or inter-penetration effects introduced by motion retargeting. Skeleton errors or rigging artifacts due to approximate weights are also visible for some specific hand configurations.

Instead, as can be seen in figure 9 and in the accompanying video, our method animates successfully both hands. The meshes are subject to large deformations but as presented in table I, they preserve both geometric details and skeleton properties. Furthermore, the animations look very realistic. Finally, the accompanying video shows a comparison between the original motion played after a traditional motion capture postprocessing/mesh rigging by a skilled CG artist and the motion produced by our method. The results are very convincing and demonstrate the interest of such an animation pipeline for this kind of animation task.

VI. CONCLUSION

The challenge proposed by this paper was to reconsider the traditional animation pipeline of character driven by the control of a skeleton. Our main objective was both to improve the quality of the animation by reducing a number of postprocessing tasks and control the mesh with a low signal dimension. In this context, we presented an animation pipeline driven by a small number of constraints based on an iterative system involving a volumetric mesh with a skeleton structure. The originality of the method lies in this strong coupling that allows us to incorporate implicit skeleton constraints within the deformation process. The concept of rigidity is improved by several aspects of the approach. By extending the as-rigid-aspossible paradigm to volumetric mesh, we prevent unintuitive shape deformations and preserve the global volume of the object. When building the volumetric mesh, we include an internal structure resulting from a spatial discretization of the skeleton, which plays a central role in the tetrahedrization process. Furthermore, the rigidity properties of the system are enhanced by taking into account skeleton properties such as bone lengths and joint limits. As the skeleton constraints are not linear, our descent method alternates between a linear Laplacian deformation of the volumetric mesh and the computation of postures enforcing these constraints. In order to produce natural postures, we believe that the inclusion of such constraints is of paramount importance for the animation of articulated bodies, as illustrated for hand animations. Finally, our animation pipeline is stable and robust, and allows us to produce in real time high-quality mesh animations from a wide variety of motion capture inputs, even when the set of input points is strongly reduced. As a major advantage, it allows to bypass the tedious rigging phase, but also some of the traditional post-processing of motion capture process.

The thorough study of the coupling mesh / skeleton opens up promising perspectives for the animation of articulated characters. One possible extension might be to consider other types of constraints related to biomechanically plausible modeling of the articulations. The proposed alternate descent method might be challenged when strongly non-linear constraints are involved, which might require more sophisticated optimization schemes. Also, other types of low dimensional input constraints can be tested in our framework, such as using accelerometers or vision inputs from mono or multicamera, which would alleviate the need of costly infrared motion capture equipments.

Fig. 2 .

 2 Fig.2. Different steps of our method. 1: hand with reflexive markers. 2: the original mesh. 3: volumetric mesh integrating skeleton data and marker positions according to the original hand markers. 4: one posture produced by our system.

Fig. 3 .

 3 Fig. 3. Example of large deformation with surface ARAP (left) and volumetric (middle and right) methods (100 iterations). Volumetric representation preserves better the volume and is more robust to preserve the shape of the original mesh. The right model is the result of our method incorporating skeleton constraints.

Fig. 4 .

 4 Fig. 4. Example of respect of joint limits for the same control mesh and markers target: left) without joint limits and right) with

Fig. 5 .

 5 Fig. 5. At the top: example of coordinate systems for each joint of the hand. At the bottom: illustration of a rotation θ j,Rel1

Fig. 7 .

 7 Fig. 7. Animation of an arbitrary mesh. At left, first figure: the bind pose geometry and the manual positioning of markers. Next: five frame of our output system.