Franck Hétroy
email: franck.hetroy@imag.fr

Cédric Gérot
email: cedric.gerot@gipsa-lab.inpg.fr

Lin Lu

Boris Thibert
email: boris.thibert@imag.fr

SIMPLE FLEXIBLE SKINNING BASED ON MANIFOLD MODELING

Keywords: skinning, manifold atlas, covering

In this paper we propose a simple framework to compute flexible skinning weights, which allows the creation from quasi-rigid to soft deformations. We decompose the input mesh into a set of overlapping regions, in a way similar to the constructive manifold approach. Regions are associated to skeleton bones, and overlaps contain vertices influenced by several bones. A smooth transition function is then defined on overlaps, and is used to compute skinning weights. The size of overlaps can be tuned by the user, enabling an easy control of the desired type of deformations.

INTRODUCTION

Skeletal animation is a widespread technique to deform articulated shapes. It uses a joint hierarchy called skeleton; during the animation, joints are translated and/or rotated then each vertex of the shape (usually represented by a mesh) is deformed with respect to the closest joints. The process that describes the skin deformation is called skinning. Many skinning techniques attach joint (or bone) weights to each vertex of the mesh; a weight specifies the amount of influence of the corresponding joint on the vertex. Defining proper values for joint weights is often time-consuming for the animator. Usually, weights are defined using the Euclidean distance between the vertices and the joints. A basic painting tool (or equivalent) can be applied manually to quantify which vertices are influenced by a given joint. Careful manual tuning is then required to set up weights that give the desired deformation.

In this paper, we propose a simple framework to automatically compute skinning weights, with a user control on the type of deformation. We get inspiration from the concept of constructive manifold atlas [START_REF] Grimm | Surface modeling and parameterization with manifolds[END_REF]. Contrary to piecewise modeling, an atlas allows to construct a surface from pieces of surface which overlap substantially instead of abutting only along their boundaries. As a consequence, when one piece is stretched or moved, the overlapping pieces follow this deformation or motion. We use this idea to compute skinning weights for any shape, proceeding in two steps. Firstly, a covering of the mesh, with regions associated to skeleton bones, is defined (Section 3). This covering can be controlled on the overlapping areas. Secondly, a partition of the unity is defined on this covering for each vertex of the mesh, providing the weights for the skinning (Section 4).

Our weight computation scheme is both simple and fast. Control is easy since only one parameter has to be tuned in order to move from a quasi-rigid deformation to a soft one, and no manually tuned example nor additional tool is required as input. We demonstrate the effectiveness of our framework on a set of examples (Section 5).

RELATED WORK

Flexible skinning

Most skinning weight computation methods try to generate ideal weights for realistic character animation. They can rely on geometric features, such as the medial axis of the object [START_REF] Bloomenthal | Medial-based vertex deformation[END_REF] or a mesh segmentation [START_REF] Katz | Hierarchical mesh decomposition using fuzzy clustering and cuts[END_REF][START_REF] Attene | Hierarchical mesh segmentation based on fitting primitives[END_REF], or on example poses (e.g. [START_REF] Merry | Animation space: a truly linear framework for character animation[END_REF][START_REF] Wang | Realtime enveloping with rotational regression[END_REF][START_REF] Weber | Context-aware skeletal shape deformation[END_REF]). An increasingly popular solution is to solve a heat equation for each joint in order to automatically set the weights associated to this joint [START_REF] Baran | Automatic rigging and animation of 3d characters[END_REF][START_REF] Weber | Context-aware skeletal shape deformation[END_REF]. However, these solutions usually do not allow for flexible skinning.

To the best of our knowledge, only a few skinning methods allow different kinds of deformations. One of them is to Overlaps and weights were computed using a geodesic distance, and deformations were created using the technique of [START_REF] Kavan | Skinning with dual quaternions[END_REF].

use spline-aligned deformations instead of the traditional Linear Blend Skinning (LBS), which can be mixed with user-designed deformation styles [START_REF] Forstmann | Deformation styles for splinebased skeletal animation[END_REF].

Another solution is to compute the set of possible new locations for a vertex deformed with LBS and let the user choose the one he wants [START_REF] Mohr | Direct manipulation of interactive character skins[END_REF]. Recently, Rohmer et al. proposed a local volume preservation technique which enables the creation of both rubber-like and realistic deformations for organic shapes, depending on the correction map applied to skinning weights [START_REF] Rohmer | Local volume preservation for skinned characters[END_REF]. The solution we suggest is more flexible in the sense that any deformation, from quasi-rigid to soft, can be created, and any skinning method can be used: for instance LBS, [START_REF] Merry | Animation space: a truly linear framework for character animation[END_REF][START_REF] Kavan | Skinning with dual quaternions[END_REF]. It also lies in the general (rigid) skeleton-based animation framework, and do not need the creation of new tools such as spline curves.

Our method can be related to the "mesh forging" approach of Bendels and Klein [START_REF] Bendels | Mesh forging: Editing of 3d-meshes using implicitly defined occluders[END_REF], except that we propose a Hermite function as a transition function between two bones, while they let the user draw the function.

Modeling with an atlas

Surface modeling with an atlas has properties which lends itself to the skinning problem. Indeed constructive manifold definitions [START_REF] Grimm | Surface modeling and parameterization with manifolds[END_REF] represent a surface as a set of blended embedded planar disks. The blending is performed as a convex combination whose weights are defined as a partition of the unity overall the planar disks. Hence the surface is made up with 3D regions which overlap substantially and are glued together. As a consequence, when an embedded planar disk is stretched or moved, the overlapping re-gions are stretched or moved accordingly. Defining such a set of regions per joint of the skeleton provides a skinning.

However, this construction makes sense only if the planar disks are linked together with transition functions. These functions indicate which embedded points have to be combined together in the blending process. To do so, either a proto-manifold associated with a mesh with a large number of pieces (at least one per vertex) is defined [START_REF] Grimm | Modeling surfaces of arbitrary topology[END_REF][START_REF] Navau | Modeling surfaces from meshes of arbitrary topology[END_REF][START_REF] Ying | A simple manifoldbased construction of surfaces of arbitrary smoothness[END_REF], or a pre-defined manifold with a small number of pieces, but in general not adapted to the particular geometry to be represented is used [START_REF] Grimm | Parameterization using manifolds[END_REF]. These constructions target a global highly-continuous parameterization of the surface. This implies major contraints on the definition of the transition functions. Reversely, an atlas can be constructed from the final surface to be represented. The global parameterization of the surface is used for high-quality sampling, texture mapping or reparameterization [START_REF] Praun | Lapped textures[END_REF]. In this case again, the components of the atlas have to be defined explicitly and with continuity constraints.

Real-time constraints impose to deal with small structures and to consider meshes as C 0 -surfaces. Hence, we propose to adapt this parameterization-oriented framework onto a lighter one, sufficient for skinning and providing a better control on the overlapping influences of different skeleton bones than other skinning algorithms.

C 0 ATLAS DEFINITION

Our work takes as input a closed mesh and an embedded animation skeleton. As stated in Section 2.2, we adapt the manifold modeling with an atlas onto a lighter framework sufficient for skinning. Following constructive manifold approach, we decompose the mesh into overlapping regions. Despite the fact that these regions are not necessarily homeomorphic to discs, they will be interpreted as charts with transition functions implicitely defined by the shared faces.

In order to control these overlapping areas, we first segment the mesh into a partition of regions associated to skeleton bones, and then stretch these regions onto a covering of the mesh. Note that regions are not restricted to cylindrical shapes with at most two boundaries.

Initial mesh segmentation

To decompose the mesh into overlapping regions, we need as a preprocess its segmentation into regions associated to skeleton bones. Any skeleton-based segmentation method can be used, such as for instance [START_REF] Katz | Hierarchical mesh decomposition using fuzzy clustering and cuts[END_REF][START_REF] De Goes | A hierarchical segmentation of articulated bodies[END_REF] which also use segmentation to create animations. In our implementation, we use a simple yet robust automatic mesh segmentation algorithm. Our approach is to first find the boundaries of the regions, which should be associated to skeleton joints since regions are associated to skeleton bones. The boundary B associated to joint J is defined as the intersection between the input mesh and a plane P going through J and orthogonal to a plane Q (see Figure 2). Q is defined by the two bones incident to J. In case more than two bones are incident to J (this is for instance the case of the pelvis joint for a human model), we can use the skeleton's hierarchy to select two of them. There is an infinite number of possible planes P, but each one can be defined by its normal n, which lies in the plane Q. In practice we compute a discrete set of planes P 0 , . . . , P k-1 , by selecting a random n 0 normal vector and then rotating it around J with an angle 2πi/k, 1 ≤ i < k. Then we keep the plane such that the length of the corresponding boundary curve B is minimum.

Figure 2: Each boundary is defined with respect to a plane P going through a joint J.

Although this method is quite simple, it provides segmentations which are robust to noise on the input mesh, to the initial pose of the character and to the location of joints, as can be seen on Figure 3. Once again, we emphasize that any other skeleton-based segmentation method can be applied instead of this one, as a pre-processing step for overlap generation.

Overlap generation

We now describe how we generate a mesh decomposition into overlapping pieces from this segmentation.

Suppose that the mesh M is decomposed into r regions {R j } r j=1 ; we note {B i } b i=1 the b boundaries between these regions. Besides, each B i has 2 adjacent regions denoted by R i 1 and R i 2 ; each R j has m boundaries, denoted by {B j,k }, with ∀ j, k, B j,k = B k, j . Generation of overlaps consists in growing each region R j into a new region R j with a distance criterion: R j is connected and R j ⊂ R j . This is done by integrating vertices of neighbouring regions to R j . Thus, each boundary B j,k of R j is modified into a new boundary B j,k of R j , with B j,k = B k, j (the new boundary of R k ). Vertices between B j,k and B k, j are in the overlap area of R j and R k . Note that a whole region R k may belong to the overlap area of a neighbouring region R j (see Figure 4).

To compute the overlap areas, we compute for each vertex v of the mesh its distance to all B j,k , and we let the user choose a size parameter K. Then, we use the length L j,k of B j,k as the criterion to generate the overlap area between R j and R k : we mark each vertex with distance to B j,k lower than K * L j,k /π as in this overlap area. [START_REF] Baran | Automatic rigging and animation of 3d characters[END_REF] claims that the range of a transition between two bones (that is to say, the area of the region where vertices are influenced by both bones) must be roughly proportional to the distance from the joint to the surface. This corresponds to K = 0.5.

In our implementation, the same parameter is used for all areas, but other solutions can be applied: for instance, K can be chosen according to the type of skeleton joint, in case semantic information is attached to joints [START_REF] Aujay | Harmonic skeleton for realistic character animation[END_REF].

Different kinds of distances can be used: Euclidean distance, approximated geodesic distance or distance based on a harmonic function, for instance. We tested several of them and discuss results in Section 5.2.

COMPUTATION OF SKINNING WEIGHTS

In the manifold constructive approach, a partition of the unity defined on a proto-manifold is used to blend embedded pieces. In the same way, we define skinning weights as a partition of the unity on the covering defined in Section 3.

We define weights that depend on the mesh covering {R j } r j=1 defined in Section 3.2. In each extended region R j a distance map d j (v) is specified. It gives to every vertex v of the region R j its distance to the boundary of the region (computed as the lowest distance from v to all B j,k ). As in Section 3.2, this can be a Euclidean or geodesic distance, or anything else. We tested Euclidean, approximated geodesic and harmonic distances; see Section 5.2 for results and a discussion.

Let δ j be the maximal distance to the boundary in R j : δ j = max v∈R j d j (v). Let s(l) be the cubic function which satisfies the Hermite conditions s(0) = 0, s(1) = 1, s (0) = s (1) = 0: s(l) = -2l 3 + 3l 2 . This cubic function lets us define weights which decrease smoothly towards 0 as the vertex v is closer to the region boundary, providing visually better results (see Section 5.3). However, weights can be defined with any function such that s(0) = 0 and s(1) = 1.

We define unnormalized weights σ j (v) as σ j (v) = s(

d j (v) δ j
).

Let I (v) be the set of indices of regions the vertex v belongs to

I (v) = { j ∈ {1, . . . , n} : v ∈ R j }. Normalized weights ω j (v) are then defined as ω j (v) = σ j (v) ∑i∈I(v) σ i (v) .
Because the regions R j define a covering of the surface and s in monotonic from [0, 1] onto [0, 1], the denominator is never equal to zero and ω j (v) ∈ [0, 1]. Moreover these well-defined weights define a partition of the unity associated to this covering: for every vertex v of the mesh,

∑ j∈I (v) ω j (v) = 1.
Note that for non-overlapped vertices, I (v) is reduced to a singleton { j} and ω j (v) = 1. For a vertex v belonging to the boundary of a region R j , we have d j (v) = 0, thus σ j (v) = 0 and ω j (v) = 0.

RESULTS AND DISCUSSION

Some deformation results are shown on Figures 1,4, 6 and 7. In all cases the Dual Quaternion technique [START_REF] Kavan | Skinning with dual quaternions[END_REF] was used to deform the meshes. The segmentation pre-processing step is done in real-time, and so is done the weight computation. Time to compute the overlap areas highly depends on the chosen distance function: it is almost real time using a Euclidean distance, but lasts a few seconds using an approximated geodesic distance, on a low-end PC.

Figure 4 shows the mesh covering defined for two standard models, and examples of deformations that can be generated in a few minutes using our framework. K was set to 0.5 (resp. 0.2) for all joints of the human (resp. Homer) model. Overlaps as well as skinning weights were computed with an approximated geodesic distance, using Dijkstra's algorithm on the mesh's vertices. As input we only used the two mesh models and their corresponding animation skeletons.

Influence of the overlap size

As can be seen on Figure 1, the overlap size K * L j,k /π influences the behavior of the deformation around a joint. For a small value of K, only a few number of vertices around the joint are smoothly bended out: the deformation is quasirigid. As K becomes larger, the deformation becomes elastic. Thus tuning K allows for various kinds of deformations.

Choice of the distance function

As stated in Section 3, several distance functions can be used to compute both overlap areas and skinning weights.

Using the Euclidean distance is the simplest and fastest solution. However, in some cases it generates artefacts (see Figure 5). For instance, if some part of the input mesh is close to a joint related to other regions, vertices in this part can be wrongly set to be in an overlap area of the joint. This drawback can sometimes be corrected using the skeleton's hierarchy, by preventing vertices from belonging to overlap areas of joints that are far from their bone in the hierarchy, but this is not always possible. Euclidean distance can also generate artefacts for weight computation, in case of curved regions: see for instance Figure 6 shows the deformation around a pelvis joint using Euclidean (first row), approximate geodesic (second row) or harmonic (third row) distance. Approximated geodesic distance has been computed with Dijkstra's algorithm. Following an idea from [START_REF] Aujay | Harmonic skeleton for realistic character animation[END_REF], we set two boundary conditions for the computation of the harmonic distance: the points on boundary curves have zero distance and the farthest points to these curves have a distance set to their approximated geodesic distance to these curves. Although the overlap areas between the three regions (waist and both thighs) are quite similar, a small artefact can be noticed for the Euclidean distance, due to the high influence the right thigh has on vertices close to the left thigh/pelvis boundary.

Choice of the weight function

Comparison with standard methods

Deformations obtained using two standard weight computation methods and Dual Quaternion technique are shown on Figure 7 (c,d). Using the paint tool (available in common software such as Autodesk's Maya or Blender), it took approximately half an hour to get a relatively decent result.

The painted area corresponds to the overlap area shown on Figure 1 (b). The use of a harmonic function [START_REF] Baran | Automatic rigging and animation of 3d characters[END_REF] is as fast as our technique, but do not allow for accurate control over the size of the deformed region.

We have presented a simple way to compute flexible skinning weights for skeleton-based animation, based on the concept of manifold modeling. Starting from a segmentation of the input mesh into regions corresponding to skeleton bones, we generate overlaps by extending each region around joints. Size of these overlaps is controlled by a simple parameter, that can be user-chosen or automatically computed. Then, vertices belonging to an overlap area are influenced by bones related to all regions that overlap. Skinning weights are defined using a simple smooth function based on the distance to the overlap boundary.

Results show that this framework allows to create from quasi-rigid to soft deformations, depending on the overlap size. Using a geodesic distance instead of a Euclidean one to create overlaps and compute skinning weights is more time-consuming, but avoids some artefacts. We believe our method can be especially useful for non-expert animators, since it is simple (only one parameter is to set) and fast to use.

Further work includes anatomic information into the overlapping width definition. Such information can be derived from semantic information associated with skeleton [START_REF] Aujay | Harmonic skeleton for realistic character animation[END_REF]. Besides, providing a skinning framework for multiresolution animated meshes, founded on our pseudoparameterization on the initial mesh, would be a further development in the similarity with manifold parameterization.

Figure 1 :

 1 Figure 1: Rest pose, medium deformation and large deformation around an elbow. K = 0.1, 0.5, 1.0 and 2.0 for (a), (b), (c) and (d) respectively. Overlap areas are shown in black. Overlaps and weights were computed using a geodesic distance, and deformations were created using the technique of[START_REF] Kavan | Skinning with dual quaternions[END_REF].

Figure 3 :

 3 Figure 3: Segmentation results for (a) a human model, (b) the same model with a different pose (and no hand nor arm joint in the skeleton), (c) the same model with different right shoulder and left hip joint locations, and (d) the same model with noised vertex locations.

Figure 4 :

 4 Figure 4: Computed covering (a,c) and deformation (b,d) for two models. Overlap areas are shown in black. Note that some vertices may belong to three or more overlapping areas, especially around the spine and the pelvis.

FigureFigure 5 :

 5 Figure 5: Artefacts using the Euclidean distance (overlap areas are shown in black). (a) For the overlap generation: an overlap area around a joint can be disconnected. (b) For the weight computation: the point represented by a square is closest to the boundary of the region than the point represented by a triangle.

Figure 6 :

 6 Figure 6: Overlap areas (a,b,c) and deformation (d,e,f) around a pelvis joint using Euclidean (a,d), approximated geodesic (b,e) and harmonic (c,f) distance. K was set to 0.5 in the first two cases, and to 0.4 in the harmonic case.

ACKNOWLEDGEMENTS

This work was partially supported by the IMAG, ELESA and INRIA through the MEGA project and the ANR through the MADRAS project (ANR-07-MDCO-015). Part of this work was done while Lin Lu was visiting INRIA with an INRIA Internship grant.