Miguel Couceiro

AND Stephan Foldes

Gerasimos C Meletiou

On homomorphisms between products of median algebras

Homorphisms of products of median algebras are studied with particular attention to the case when the codomain is a tree. In particular, we show that all mappings from a product A 1 ˆ¨¨¨ˆAn of median algebras to a median algebra B are essentially unary whenever the codomain B is a tree. In view of this result, we also characterize trees as median algebras and semilattices by relaxing the defining conditions of conservative median algebras.

Introduction

Median algebras have been investigated by several authors in the context of distributive algebras, semilattices, graphs and hypergraphs and in the framework of convex and metric spaces (see, e.g., [START_REF] Avann | Metric ternary distributive semi-lattices[END_REF][START_REF] Bandelt | Median algebras[END_REF][START_REF] Barthélemy | Caractérisation médiane des arbres[END_REF][START_REF] Birkhoff | A ternary operation in distributive lattices[END_REF][START_REF] Evans | Median lattices and convex subalgebras[END_REF][START_REF] Sholander | Medians, lattices, and trees[END_REF]). A median algebra is a structure A " xA, my for a set A and a ternary symmetric operation m : A 3 Ñ A, called median, such that mpx, x, yq " x, mpmpx, y, zq, t, uq " mpx, mpy, t, uq, mpz, t, uqq.

In fact, axiom systems using only 4 variables are also known [START_REF] Bandelt | Median algebras[END_REF][START_REF] Isbell | Median algebra[END_REF].

It is well known [START_REF] Sholander | Medians, lattices, and trees[END_REF] that each element a of a median algebra A gives rise to a median semilattice xA, ď a y where ď a is given by x ď a y ðñ mpa, x, yq " x.

In this semilattice a is the bottom element and the associated binary operation, denoted ^a, is defined by x^a y " mpa, x, yq. As shown in [START_REF] Sholander | Medians, lattices, and trees[END_REF], median semilattices coincide exactly with those ^-semilattices whose principal ideals Ó x :" ty P A : y ď a xu are distributive lattices, and such that for any a, b, c P A, a ^b, b ^c, c ^a have a supremum whenever each pair of these meets is bounded above. In such a case, we can define a median operation by (1.1) m ď px, y, zq " px ^yq _ px ^zq _ pz ^yq, for every x, y, z P A. Moreover, m " m ďa for every median algebra A " xA, my, and every a P A [START_REF] Avann | Metric ternary distributive semi-lattices[END_REF]. Similarly, every distributive lattice gives rise to a median algebra using (1.1) and the converse also holds whenever there are a, b P A such that mpa, x, bq " x for every x P A.

Another noteworthy connection is to median graphs, i.e., connected graphs having the property that for any three vertices a, b, c, there is exactly one vertex x which lies on a shortest path between each pair of vertices in ta, b, cu. As shown in [START_REF] Avann | Metric ternary distributive semi-lattices[END_REF], the covering graph (i.e., undirected Hasse diagram) of every median semilattice whose intervals are finite is a median graph. Conversely, every median graph is the covering graph of a median semilattice. For further background see, e.g., [START_REF] Bandelt | Median algebras[END_REF].

In [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF] the authors studied conservative median algebras, i.e., median algebras that satisfy mpx, y, zq P tx, y, zu, for all x, y, z P A. Apart from the 4-element Boolean algebra, it was shown that conservative median algebras can be represented by two lower bounded chains whose least elements are identified (thus, they can always be regarded as chains). The authors in [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF] also provided complete descriptions of median-homomorphisms between conservative median algebras (with at least 5 elements). We recall the main results of [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF] in the two following theorems.

Theorem 1.1 ([8]). Let A and B be two conservative median algebras (thought of as chains) with at least five elements. A map f : A Ñ B is a median homomorphism if and only if f is monotone (i.e., order-preserving or order-reversing).

This result was then lifted, by making use of dual topological spaces of median algebras, to median-homomorphisms between products of conservative median algebras. For each positive integer n, we set rns " t1, . . . , nu.

Theorem 1.2 ([8]

). Let A " C 1 ˆ¨¨¨ˆC n and B " D 1 ˆ¨¨¨ˆD k be two finite products of conservative median algebras (thought of as chains). Then f : A Ñ B is a median homomorphism if and only if there exist σ : rks Ñ rns and monotone maps f i : C σpiq Ñ D i for i P rks, such that f " pf σp1q , . . . , f σpkq q.

In the particular case when k " 1,

f : C 1 ˆ¨¨¨ˆC n Ñ D
is a median homomorphism if and only if there is j P rns and a monotone map g : C j Ñ D such that f " g ˝πj .

In this paper we generalize in particular these results from [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF]. Instead of conservative median algebras (thought of as chains) we deal with trees (i.e., acyclic undirected graphs) when thought of as semilattices: a ^-semilattice (resp. _semilattice) is said to be a tree if no pair of incomparable elements have an upper (resp. lower) bound. As we will see, such median algebras are obtained by relaxing the condition of being conservative: we say that a median algebra A is a p2 : 3q-median semilattice if mpx, y, zq P tx ^y, y ^z, z ^xu for all x, y, z P A.

Preliminary results

As discussed in Section 1, when there is no danger of ambiguity, we will not distinguish between median algebras and median semilattices. They will be denoted by bold roman capital letters A, B, . . ., while their universes will be denoted by italic roman capital letters A, B, . . .. We will assume that universes of structures are nonempty, possibly infinite, sets.

Let A " xA, my be a median algebra and let a, b P A. The convex hull of ta, bu or the interval from a to b, denoted by ra, bs, is defined by ra, bs :" tt P A : t " mpa, t, bqu " tmpa, t, bq : t P Au.

Proposition 2.1 ([5]

). Let A " xA, my be a median algebra, and consider a, b, c P A. Then ra, bs X rb, cs X ra, cs " tmpa, b, cqu.

Every interval ra, bs in a median algebra can be endowed with a distributive lattice structure. To this purpose, for a P A recall the binary operation ^a : A 2 Ñ A defined by:

x ^a y :" mpa, x, yq, for px, yq P A 2 . It is easy to verify that xra, bs, ^a, ^by is a distributive lattice with a and b as the least and greatest elements, respectively.

Moreover, we also have a general description of median-preserving mappings between two median algebras. Theorem 2.2. Let A and B be median algebras, and consider a mapping f : A Ñ B. Then the following assertions are equivalent. piq f is a median-homomorphism. piiq For all p P A, f : xA, ^py Ñ xB, ^fppq y is a semilattice-homomorphism. piiiq For all p P A, f : xA, ď p y Ñ xB, ď f ppq y is an order-homomorphism. pivq For all a, b P A, f pra, bsq Ď rf paq, f pbqs.

Proof. piq ùñ piiq: Suppose that f is a median-homomorphism and p P A. Then f pa ^p bq " f pmpp, a, bqq " mpf ppq, f paq, f pbqq " f paq ^fppq f pbq. piiq ùñ piiiq: Straightforward. piiiq ùñ pivq: Let t P ra, bs. Then a ď a t ď a b, and thus f paq ď f paq f ptq ď f paq f pbq from which it follows that f ptq P rf paq, f pbqs. In other words, f pra, bsq Ď rf paq, f pbqs. pivq ùñ piq: Let a, b, c P A. By Proposition 2.1, we have tmpa, b, cqu " ra, bs X rb, cs X rc, as.

By pivq, we then conclude that f pmpa, b, cqq P rf paq, f pbqs X rf pbq, f pcqs X rf pcq, f paqs " tmpf paq, f pbq, f pcqqu.

Therefore, f pmpa, b, cqq " mpf paq, f pbq, f pcqq.

Corollary 2.3. Let f : A Ñ B be a median homomorphism between two median algebras A and B. Then, for every a, b P A, f is also a lattice homomorphism from xra, bs, ^a, ^by to xrf paq, f pbqs, ^fpaq , ^fpbq y.

A relaxation of conservativeness: trees as median algebras

In this section we focus on median algebras that are trees. In the particular case of chains, it was shown that these median algebras are exactly those that are conservative, i.e., mpx, y, zq P tx, y, zu, x, y, z P A. To characterise median semilattices that are trees, we propose the following relaxation of conservativeness. We say that a median algebra, thought of as a median semilattice A " xA, ^y, is a p2 : 3q-median semilattice if for every x, y, z P A, we have mpx, y, zq :" px ^yq _ px ^zq _ pz ^yq P tx ^y, y ^z, z ^xu.

We start with a simple yet useful observation.

Remark 3.1. Let A " xA, my be a median algebra such that xA, ď c y is a tree for some (or, equivalently, all) c P A. Then, for all a, b P A, the convex hull ra, bs is a chain from a to b. Theorem 3.2. Let A " xA, my be a median algebra. Then the following assertions are equivalent.

piq There is p P A such that A " xA, ď p y is a p2 : 3q-median semilattice. piiq For all p P A, A " xA, ď p y is a p2 : 3q-median semilattice. piiiq There is p P A such that A " xA, ď p y is a tree. pivq For all p P A, A " xA, ď p y is a tree. pvq For all a, b P A, the bounded distributive lattice xra, bs, ^a, ^by is a chain.

Proof. piiq ùñ piq: Straightforward.

piq ùñ piiiq: Suppose that A " xA, ď p y is a p2 : 3q-median semilattice. To show that it is a tree it suffices to show that for every pair a, b P A with a common upper bound, we have a ď p b or b ď p a.

So suppose that c P A is a common upper bound of a and b, that is, mpp, a, cq " a and mpp, b, cq " b. Since A " xA, ď p y is a p2 : 3q-median semilattice and c is an upper bound of a and b,

(3.1)
mpc, a, bq P tmpp, a, bq, a, bu.

Note that since m is a median, mpp, mpa, c, bq, aq " mpb, mpa, a, pq, mpc, a, pqq " mpb, a, aq " a, and thus a ď p mpc, a, bq. Similarly, we have b ď p mpc, a, bq. Now, if mpc, a, bq " mpp, a, bq in (3.1), then mpc, a, bq ď p a since mpp, a, bq ď p a. Hence, a " mpc, a, bq. Similarly, we also have b " mpc, a, bq, and thus a " b.

If mpc, a, bq " a in (3.1), then mpp, a, bq " mpmpc, a, bq, p, bq " mpa, mpc, p, bq, mpb, p, bqq " mpa, b, bq " b, and thus b ď p a. Similarly, if mpc, a, bq " b in (3.1), we conclude that a ď p b.

Since in all possible cases we have that a ď p b or b ď p a, A " xA, ď p y is a tree. piiiq ùñ pivq: Straightforward. pivq ùñ pvq: Let s, t P ra, bs. Thus a ď a s, t ď a b, and s, t have a common upper bound in xA, ď a y. As xA, ď a y is a tree, s and t cannot be incomparable, and hence the interval ra, bs is a chain.

pvq ùñ pivq: Let a, b, p P A and suppose that a and b are incomparable in A " xA, ď p y. Note that p ď p a, b.

To obtain a contradiction, suppose that a and b have a common upper bound d P A, that is, p ď p a, b ď p d. However, by pvq the interval rp, ds is a chain and thus we must have a ď p b or b ď p a, which constitutes the desired contradiction.

pivq ùñ piiq: Let p P A. As A " xA, ď p y is a tree, for every a, b, c P A, we have that a ^b, b ^c and c ^a are pairwise comparable, and thus mpa, b, cq P ta ^b, b ^c, c ^au.

Hence, A " xA, ď p y is a p2 : 3q-median semilattice.

Remark 3.3. As mentioned, conservative median semilattices A are p2 : 3q-median semilattices, whenever |A| ě 5. Hence, Lemma 3 and Theorem 3 in [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF] follow as corollaries of Theorem 3.2. In fact, the conservative median semilattice t0, 1u 2 is the only "pathological" case.

Median-homomorphisms over trees

In [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF] the authors presented a study of median-homomorphims of the form (4.1)

f : A 1 ˆ¨¨¨ˆA n Ñ B 1 ˆ¨¨¨ˆB k ,
in the case where the median algebras A 1 , . . . , A n and B 1 , ¨¨¨, B k are conservative.

In the current paper we seek to generalise the results of [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF] to arbitrary median algebras. To do so, we shall make use of the following general fact in universal algebra that we briefly recall; for further background see, e.g., [START_REF] Burris | A course in universal algebra[END_REF][START_REF] Grätzer | General lattice theory[END_REF].

Let A 1 , ¨¨¨, A n and B 1 , ¨¨¨, B k be arbitrary algebras of the same type. For each j P rks, let π j denote the j-th projection on B 1 ˆ¨¨¨ˆB k , i.e., the mapping

π j : B 1 ˆ¨¨¨ˆB k Ñ B j .
Clearly, π j is a homomorphism. Also, for a function

f : A 1 ˆ¨¨¨ˆA n Ñ B 1 ˆ¨¨¨ˆB k , let f j , j P rks, denote the composition f j " π j ˝f : A 1 ˆ¨¨¨ˆA n Ñ B j ,
so that f " pf 1 , . . . , f k q. Then f is a homomorphism if and only if every f j , j P rks, is a homomorphism.

Hence, in the particular case when A 1 , ¨¨¨, A n and B 1 , ¨¨¨, B k are median algebras, the description of median-homomorphisms (4.1) is reduced to the description of median-homorphisms of the form (4.2)

f : A 1 ˆ¨¨¨ˆA n Ñ B
from a finite product of median algebras A 1 , ¨¨¨, A n (thought of as median semilattices) to a median algebra B. Now a general characterization of homomorphisms of the form (4.2) still eludes us, however we can provide explicit descriptions of such mappings when B is of a special type, namely, when B is a p2 : 3q-semilattice or, equivalently, when B is a tree.

Theorem 4.1. Let A 1 , ¨¨¨, A n be median algebras and let B be a tree. A mapping f : A 1 ˆ¨¨¨ˆA n Ñ B is a median-homomorphism if and only if there is an i P rns and a median-homomorphism g : A i Ñ B such that f px 1 , . . . , x n q " gpx i q, for all px 1 , . . . , x n q P A 1 ˆ¨¨¨ˆA n .

In other words, f is an essentially unary median-homomorphism.

Proof. Clearly, sufficiency holds. To prove necessity we show that f cannot depend on two different arguments. For the sake of a contradiction suppose that f depends on at least 2 of its arguments. Without loss of generality, we may assume that they are the first two. Hence, there are a, b P A 1 and c P A 1 ˆ¨¨¨ˆA n such that f pc a 1 q ‰ f pc b 1 q, where c x i denotes the tuple obtained from c by setting its i-th component to x.

Note that if f pc a 1 q ‰ f pc b 1 q, then the same holds for all d P A 1 ˆ¨¨¨ˆA n . Indeed, suppose to the contrary that there is d P A 1 ˆ¨¨¨ˆA n such that f pd a 1 q " f pd b 1 q. Then, from the fact that f is median-preserving, it would follow that f pc a 1 q " f pc b 1 q (a contradiction) since

mpf pd a 1 q, f pc a 1 q, f pc b 1 qq " mpf pd b 1 q, f pc a 1 q, f pc b 1 qq ô f pmpd a 1 , c a 1 , c b 1 qq " f pmpd b 1 , c a 1 , c b 1 qq ô f pc a 1 q " f pc b 1 q. Hence, we must have f pd a 1 q ‰ f pd b 1 q. Similarly, if the second argument of f is essential, then are a 1 , b 1 P A 2 and c 1 P A 1 ˆ¨¨¨ˆA n such that f pc 1 a 1 2 q ‰ f pc 1 b 1 2 q.
Once again, we have in fact that f pd 1 a 1 2 q ‰ f pd 1 b 1 2 q, for all d 1 P A 1 ˆ¨¨¨ˆA n . Hence, we have that f pc x,y 1,2 q for px, yq P ta, bu ˆta 1 , b 1 u, are pairwise distinct. By picking p of the form f pc x,y 1,2 q, it then follows that the four points f pc x,y 1,2 q P B form a square as in Figure 4. This contradicts the fact that B is a tree. By Theorem 4.1 to describe median-homomorphisms of the form

f : A 1 ˆ¨¨¨ˆA n Ñ B
in the case when A 1 , ¨¨¨, A n are median algebras and B is a tree, it suffices to describe median homomorphisms f : A Ñ B for a median algebra A and a tree B. Such descriptions follow from Theorem 2.2.

In the case when both A and B are trees, Theorem 2.2 together with Corollary 2.3 and Theorem 3.2, imply the following proposition. Proposition 4.2. Suppose that the median algebras A and B are trees, and consider a mapping f : A Ñ B. Then the following assertions are equivalent. piq f is a median-homomorphism. piiq For all a, b P A, the induced mapping f : xra, bs, ď a y Ñ xrf paq, f pbqs, ď f paq y is an isotone function between chains.

' p " f pc b,b 1 1,2 q ' f pc a,b 1 1,2 q ' f pc a,a 1 1,2 q ' f pc b,a 1 1,2 q
In the case when A is a tree and B is an arbitrary median algebra, Theorem 2.2 can be strengthened by an additional and equivalent assertion, namely, the existential variant of its assertion piiq. Theorem 4.3. Let A be a tree and B an arbitrary median algebra. Then the equivalent assertions in Theorem 2.2 are also equivalent to pii 1 q There is a p P A such that f : xA, ^py Ñ xB, ^fppq y is a semilatticehomomorphism.

Proof. Obviously, piiq ùñ pii 1 q. So to show that pii 1 q ùñ piq, suppose that xA, ^py is a tree and that and the proof of pii 1 q ùñ piq, and thus of the theorem, is now complete.

Remark 4.4. Note that the existential variant of piiiq in Theorem 2.2 is not equivalent to piq even in the case when A is a tree. To see this, consider the function on A 1 (see Figure 2(a)) that maps a, b to a, and leaves c and d fixed. Then it is an order-homomorphism for p " a, but it is not a median-homorphism.

Remark 4.5. Note also that Theorem 4.3 does not necessarily hold in the case when A is not a tree, even if B is conservative. For instance, let A be the median algebra given in Figure 2(b) and B the 4-element chain 1, 2, 3, 4, and consider the mapping that sends d, d 1 to 4, b, c to 2, and a to 1. Then, for all p P A, f : xA, ^py Ñ xB, ^fppq y is an order-homomorphism, but it is not a semilatticehomorphism for p " a (although it is a semilattice-homorphism for p " d 1 ). Problem. Given an arbitrary median algebra B, describe those median algebras A for which Theorem 4.3 holds.

' a ' b ' c ' d (a) A 1 ' d 1 ' a ' b ' c ' d (b) A 2
Another natural question is to determine whether Theorem 4.1 still holds for a given median algebra B. More precisely: Given arbitrary median algebras A 1 , ¨¨¨, A n , describe those median algebras B for which all median-homomorphisms f : A 1 Ân Ñ B are essentially unary.

To answer this question, consider the following example. Suppose that B is an arbitrary median algebra thought as a ^-semilattice that is not a tree. Thus, there are a, b P B with a nontrivial upper bound c, i.e., c ą a, b ą a ^b. Set p " a _ b, q " a ^b. Note that, together with a and b, they form a square. Now, consider the median algebras A 1 " A 2 " t0, 1u. Then f : A 1 ˆA2 Ñ B given by f p1, 1q " p, f p0, 1q " a, f p1, 0q " b, f p0, 0q " q is a median homomorphism that depends on both of its variables. Now this example can be easily extended to mappings f : A 1 ˆ¨¨¨ˆA n Ñ B and, as we have seen, the condition that B is a p2 : 3q-semilattice (i.e., a tree or, equivalently, does not contain a square as an order substructure) forces such median-preserving mappings to be essentially unary.

From these considerations, we have the following description of those median algebras B for which all median-homomorphisms f : A 1 ˆ¨¨¨ˆA n Ñ B are trivial. Corollary 4.6. All median-homomorphisms f : A 1 ˆ¨¨¨ˆA n Ñ B are essentially unary if and only if B is a tree.

Figure 1 .

 1 Figure 1. A square as in proof of Theorem 4.1.

f

  : xA, ^py Ñ xB, ^fppq y is a semilattice-homomorphism. In particular, for every a, b, c P A, we have that mpa, b, cq P ta ^p b, b ^p c, c ^p au, and that f : xA, ď p y Ñ xB, ď f ppq y is an order-homomorphism. Without loss of generality, assume that mpa, b, cq " a ^p b. Hence, a ^p b " mpa, b, cq " pa ^p bq _ p pb ^p cq _ p pc ^p aq ě p b ^p c, c ^p a, and, from the assumption that f is a semilattice-homomorphism, f pmpa, b, cqq " f pa ^p bq " f paq ^fppq f pbq ě f ppq f pbq ^fppq f pcq, f pcq ^fppq f paq. Therefore, m pf paq, f pbq, f pcqq " pf paq ^fppq f pbqq _ f ppq pf pbq ^fppq f pcqq _ f ppq pf pcq ^fppq f paqq " f paq ^fppq f pbq " f pmpa, b, cqq

Figure 2 .

 2 Figure 2. Examples of ^-semilattices.


diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Ludovic Dutreve

Alexandre Meyer

Veronica Orvalho

Saïda Bouakaz

Easy Rigging of Face by Automatic Registration and Transfer of Skinning Parameters

Preparing a facial mesh to be animated requires a laborious manual rigging process. The rig specifies how the input animation data deforms the surface and allows artists to manipulate a character. We present a method that automatically rigs a facial mesh based on Radial Basis Functions (RBF) and linear blend skinning approach. Our approach transfers the skinning parameters (feature points and their envelopes, ie. point-vertex weights), of a reference facial mesh (source)already rigged -to the chosen facial mesh (target) by computing an automatic registration between the two meshes. There is no need to manually mark the correspondence between the source and target mesh. As a result, inexperienced artists can automatically rig facial meshes and start right away animating their 3D characters, driven for instance by motion capture data.

Introduction and Related Work

Modeling 3D faces is becoming more and more automatic and common with systems based on photos [START_REF] Stylianou | Image based 3d face reconstruction: a survey[END_REF] or on user-friendly interactions [START_REF] Ersotelos | Building highly realistic facial modeling and animation: a survey[END_REF]. Consequently, many applications in the area of games or virtual reality offer to novices the capacity to generate or customize a 3D facial avatar. Indeed, avatar with better ability to depict his owner in the virtual community will provide a better immersion. However, setup a facial mesh in order to animate it requires fastidious manual rigging to specify how the input animation data deforms the surface. For instance, the first stage of a rigging process, which is to manually place some feature points (FP) on the face, takes around 2 minutes [START_REF]Pick the landmarks with face robot[END_REF]. Thus, in the same way that [START_REF] Baran | Automatic rigging and animation of 3d characters[END_REF] does for the body, we aspire to a system that automates the face rigging task, to make animations more accessible for children, educators, researchers, and other non-expert animators.

For the real-time facial mesh deformation, we have chosen to focus on the traditional Linear Blend Skinning1 (LBS) [START_REF] Magnenat-Thalmann | Joint-dependent local deformations for hand animation and object grasping[END_REF][START_REF] Lewis | Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation[END_REF]. Indeed, with Blendshape [START_REF] Deng | Computer Facial Animation: A Survey[END_REF] which consists on morph between key meshes, they remain the most popular methods used in practice in real-time 3D engines. Although both methods provide realistic animations, it seemed more tractable for our purpose to deal with skinning parameters than key shapes, and more pertinent to stay compatible with recent mesh deformation based on skinning [START_REF] Feng | Real-time data driven deformation using kernel canonical correlation analysis[END_REF] for a potential extension. Skinning binds controllers to vertices in order to deform the mesh according to the controllers deformations. Usually, these controllers are bones or skeleton for the body and feature points (FP) or landmarks for the face2 . In most case, a vertex may be influenced by several FP by using a convex combination of weights.

In this paper, we propose a method which takes as input a mesh of face (target) and provides as output skinning parameters, i.e. a FP set and the associated point-vertex influences (weights). These skinning parameters are transferred without human intervention from a reference mesh (source) already rigged. Comparing to procedural approaches mostly used in automatic body rigging approaches like [START_REF] Baran | Automatic rigging and animation of 3d characters[END_REF], transfer-based approaches has the advantage, in the specific case of face, to reuse fine manual work designed specially to tackle subtle facial animation. Moreover, previous transfer approach for face [START_REF] Costa Orvalho | Transferring the rig and animations from a character to different face models[END_REF] has validated the transfer based concept. Comparing to [START_REF] Costa Orvalho | Transferring the rig and animations from a character to different face models[END_REF], our main contribution is the fully automatic registration which provides a landmark correspondence between the two meshes (See Section 2). Once the 3D target mesh is rigged with our method, it may be directly animated by any FP-based animations coming for instance from a motion capture system based on webcam as illustrated in our results (See Figure 4). Or, it may be used by any 3D engines and major 3D Softwares.

An important aspect of the automatic transfer of facial animation parameters is the registration which tries to find a transformation that optimally fits points from the source surface to the target surface. Registration of range images of the same object [START_REF] Salvi | A review of recent range image registration methods with accuracy evaluation[END_REF] is often tackled by variant of the Iterative Closest Points algorithm [START_REF] Besl | A method for registration of 3-d shapes[END_REF][START_REF] Rusinkiewicz | Efficient variants of the ICP algorithm[END_REF][START_REF] Eisert | Algorithms for automatic and robust registration of 3d head scans[END_REF]. Although we represent the frontal face view with a depth image which is similar to a range image, our problem has to be classified in the area of registering two instances of objects belonging to the same family: variation of faces morphologies. Our case is also more general than the class of non-rigid registrations problems aiming at fitting a template [START_REF] Allen | The space of human body shapes: reconstruction and parameterization from range scans[END_REF][START_REF] Deng | Computer Facial Animation: A Survey[END_REF][START_REF] Weise | Face/off: live facial puppetry[END_REF][START_REF] Eisert | Algorithms for automatic and robust registration of 3d head scans[END_REF] model to scanned or motion capture surface. These methods are often based on variational approaches minimizing surfaces differences from morphable shape model computed from a database.They provide good results when faces are close which is not necessary our case. And, for the sake of generality, we preferred working on an approach without a priori on the surfaces which allows to register two cartoon faces as illustrated in Figure 2d and2e.

Overview A reference facial mesh is previously rigged for skinning animation. Our method automatically registers the reference mesh (source) to the facial mesh to rig (target) in order to transfer the skinning parameters (FP and pointvertex influences) without human intervention. The result is a rigged facial mesh ready to be animated by skinning. The transfer is done in four phases. Firstly, the method we present addresses the correspondence issue using a new approach registering the result of a sequence of watershed segmentations described in Section 2. Then, these landmarks are used in a radial basis functions (RBF) learning process to transfer the FP from the source to the target and in the third phase (Section 3) to computes a dense registration. And finally, the pointvertex influences are transferred.

Surface Correspondence

The first issue of our transfer approach is the computation of the landmark correspondence on both meshes, which may be tricky if the anthropometric lengths are slightly different. To find this landmark correspondence, our approach runs a sequence of preprocessing, watershed segmentation and region-based registration on the frontal depth images of the faces.

We have chosen to register the two faces using a depth images representation for several reasons. We start from the observation that a frontal part of a face is 2.5D, so the depth image representation should keep the important information for registration. Depth image allows to be easily independent on the mesh resolution which is essential for the usefulness of the method. A low polygon facial model may be registered with a high polygon model. Comparing to complex remeshing, computing the depth map representation of a face can be done easily using an orthogonal projection (as for instance the Z-buffer) and the reprojection of a 2D pixel position on the mesh allows to return in 3D. And finally, working on regular 2D grids (images) is more convenient and more efficient in computation time than working directly with the mesh.

One

Step of Watershed Segmentation At each step, to compute new landmark correspondences, we perform a watershed segmentation where the regions are registered. The depth image is segmented by the watershed algorithm [START_REF] Mangan | Partitioning 3d surface meshes using watershed segmentation[END_REF] interpreting it as a topographic surface and gradually immerses it in a water container [START_REF] Mangan | Partitioning 3d surface meshes using watershed segmentation[END_REF]. After the segmentation, the surface will be divided into its catchment basins meaning every pixels is assigned to a region as illustrated in Figure 1c. The local minimum point (seed) of each basin is the representant of the basin. Since the segmentations are computed using the global image information, our method can localize the landmark correspondence more accurately than local detection/grouping methods [START_REF] Varsha Hedau | Matching images under unstable segmentation[END_REF]. For instance, the SIFT descriptor algorithm selects landmarks only on the border which is less precise than our method as illustrated in Figure 2b and2c. The assumption of our method is that objects of a same family will provide mostly similar segmentation which are more easy to register than directly the meshes.

At step 0, to initialize the sequence, we set landmarks around the respective bounding box of each face. In this paragraph, we assume that k steps of the sequence of watershed segmentation/registration have already been done and have provided a set of landmarks. These landmarks are used as learning points for a RBF interpolation as described in [START_REF] Dutreve | Feature Points Based Facial Animation Retargeting[END_REF] defining the transformation RBF src->tar k , just noted RBF, which transforms a point of the source image to the target image. By inverting the landmarks, we compute RBF tar->src k noted RBF -1 . We consider the next step of the sequence, the k + 1 th watershed segmentation/registration. The watershed segmentation computes on the two depth images, two sets of regions with their associated seeds (See Figure 1c). A seed of the source segmentation will be selected as landmark if it can be associated with a seed of the target segmentation. The correspondence criteria between two watershed is described in Figure 2a. Two watersheds W S src i and W S tar j match if the seed P src i (resp. P tar i ) falls into the watershed W S tar j (resp. W S src i ) after being transformed by the RBF (resp. RBF -1 ) defined by the previous steps. i.e. if RBF (P src i ) ∈ W S tar j and RBF -1 (P tar j ) ∈ W S src i we add P src i and P tar j to the set of landmarks defining the correspondence. For instance, in Figure 2a, the bottom right watershed regions match, top ones not. At the end of this step, we recompute the RBF with the added landmarks for the next step. This criteria is fast to compute and has the advantage to quickly registers similar regions. According to our tests, it is enough efficient to not considering an other criteria more complicated to compute.

Sequence of Segmentation/Registration as a Descriptor Problem

The watershed segmentation applied on depth image combined with our registration criteria has the advantage to provide a global approach which can be easily iterated with different preprocessing. Indeed, in this Section we propose to take advantage of various descriptors to catch different regions of a face, for instance regions of high curvature or of high symmetry, etc.. Nevertheless, this general framework may be refined by any kind of surface descriptors and is related to the classical issue of choosing pertinent descriptors for image or surface registration [START_REF] Zitova | Image registration methods: a survey[END_REF][START_REF] Salvi | A review of recent range image registration methods with accuracy evaluation[END_REF]. The choose of descriptors order have to be from coarse to fine.

The first preprocessing we apply is a Gaussian filter on the depth images to remove the issue of small regions during the segmentation. This will register the global appearance (local maxima) of the face, mainly the nose and often the forehead (See Figure 1e). In second, we apply a Laplacian filter followed by a Gaussian filter with different radius. It generally registers edges like borders of the face or of the nose (See Figure 1g). Finally, since a face included many symmetric regions, we compute two descriptors of symmetry, horizontal and vertical, as illustrated in Figure 1i. In practice, results of Figure 3 have been computed by these preprocessing also illustrated in the bottom row of Figure 1. But, reader may define other interesting descriptors for different class of shape.

Transfer of Feature Points and Point-Vertex Influences

The sequence of watershed segmentations/registrations previously described provides as output two sets of landmarks on the mesh defining a correspondence as illustrated in the bottom row of Figure 2. We use these landmarks to define a RBF interpolation RBF src->tar f inal to transfer each FP position of the source face to the target face as illustrated in the top row of Figure 3.

Rigging the target mesh with common skinning techniques requires to attach each vertex to one or more FP with influence values. As for the FP, we perform this task by transferring this information from the source mesh by defining a dense registration in a similar way than in [START_REF] Noh | Expression cloning[END_REF][START_REF] Costa Orvalho | Transferring the rig and animations from a character to different face models[END_REF]. To compute this dense registration, each vertex V of the target mesh is transformed by the RBF interpolation: V = RBF tar->src f inal (V ). Since V does not fall necessary exactly on the source mesh, it is projected 3 on the source mesh to falls into a point P of a triangle T src which defines our dense registration. Notice that P is a 3D position on the triangle and is not necessary a vertex. We compute the FP influences of V by interpolating the ones of the 3 vertices of the triangle T src . We have tested the Inverse Distance Weighting interpolation and the barycentric interpolation which both provide similar and enough accurate results in our case. The bottom row of the Figure 3 shows an example of influences transfer for some FP.

Results and Conclusion

Figure 3 shows a sample of our facial mesh database used for our experiments which includes 15 face variations with a large scale of characteristics: 3D meshes count from about thousand triangles to several tens of thousand triangles; bounding box sizes are also quite variable; some meshes include only the face, others include the whole head; and some models are computer generated, others are scanned faces (like the last on the right). The only constraint we ask to the models is that the face has to be manually set to look in the Z axis direction to be able to compute the depth image of the frontal view. We also tested our registration on cartoon faces as illustrated in Figure 2d and 2e. To measure the quality of the landmark correspondence, we have manually defined twenty FP on representative positions for animation for each 3D mesh (See Figure 3a). We define an error criteria by summing the distance between each FP of the transferred rig and the manually set ones normalized by the diagonal of the bounding box to be able to compare results on different mesh size. Notice that the result of the automatic FP transfer may be manually edited if the user feels the need, without changing the rest of the method. Our results in Figure 3, 4 and on the provided video are not manually adjusted.

Computing the depth image representation of the mesh is instantaneous using the GPU/Z-buffer of the frontal view. The landmark correspondence determination is computationally dependant on the depth image resolution and on the number of steps in the sequence of segmentations/registrations. In our experiments, we used depth images of 512 × 512 with the sequence of preprocessings/segmentations/registrations described in Figure 1 and in Section 2. It takes about 20s on a Athlon X2 3800+ with 2GB of RAM. The dense registration is computationally dependent on the number of triangles of the two meshes and takes for instance about 30s for a mesh with 12000 triangles. Once the dense registration is done, the time of skinning parameters transfer is immediate. And finally to illustrate our results, Figure 4 and the provided video show an animation applied on two faces, the first was rigged manually while the second was automatically rigged by our method in a minute without human intervention. The animation is provided on the fly by a motion capture system using a simple webcam and the Lucas-Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] marker tracker. Notice that any other motion capture system may be used and that the markers on the face may be different than the FPusing retargeting adaptation [24, ?].

These results prove the viability of such an automatic transfer approach based on depth image representation of the mesh which makes the implementation easier, lets use efficiently several descriptors with an approach based on segmentation, and allows to easily deal with mesh of different resolutions. Nevertheless, fully automatic transfer of rigging from a generic reference human face to a large range of faces like cartoons or animals is still delicate because of the landmark correspondence issue. A solution would be to rig several types of reference faces (human, cartoon, animal, etc.) as preprocess and rig a new face by transfer of parameters from the nearest reference face.

Fig. 1 :

 1 Fig. 1: Top row: one step of our landmark based registration. Bottom row: a sequence of the watershed segmentation/registration process with different preprocessing. (e) and (f): Gaussian filters with different radius. (g) and (h): a Laplacian filter followed by a Gaussian filter with different radius. (i) and (j): vertical and horizontal anti-symmetric filters.

Fig. 2 :

 2 Fig. 2: In (a), the criteria to match two segmented regions. In (b), the SIFT descriptors algorithm [21] selects landmarks only on the border. In (c), (d) and (e), our sequence of segmentations/registrations provides a set of 2D pair of landmarks. (d) and (e) illustrate the registration on cartoon faces.

Fig. 3 :

 3 Fig. 3: Top row: examples of transfer of the set of FP . Bottom row: examples of transfer of the point-vertex influences from the reference face (the color scale of the weights starts from blue (0.) to red (1.)).

Fig. 4 :

 4 Fig. 4: Top: motion capture animation. Middle: reference model previously rigged. Bottom: the same animation applied on a face automatically rigged by our method, rigging is transferred from the reference without intervention.

also known as skinning or enveloping or Skeletal Subspace Deformation(SSD)

as the ones defined by the Facial Definition Parameters of the MPEG4 standard[START_REF] Zhong | Flexible face animation using mpeg-4/snhc parameter streams[END_REF].

We apply a spherical projection but our tests with a cylindrical projection do not lead to significant differences.


L Dutreve

A Meyer

S Bouakaz

Real-Time Dynamic Wrinkles of Face for Animated Skinned Mesh

This paper presents a method to add fine details, such as wrinkles and bulges, on a virtual face animated by common skinning techniques. Our system is based on a small set of reference poses (combinations of skeleton poses and wrinkle maps). At runtime, the current pose is compared with the reference skeleton poses, wrinkle maps are blended and applied where similarities exist. The poses evaluation is done with skeleton's bones transformations. Skinning weights are used to associate rendered fragments and reference poses. This technique was designed to be easily inserted into a conventional real-time pipeline based on skinning animation and bump mapping rendering.

Introduction

Recent rendering and animation advances improve the realism of complex scenes. However, a realistic facial animation for real-time applications is still hard to obtain. Some reasons could explain this difficulty. The first one remains from the lack of computational and memory resources supplied by an interactive system, and another one remains from the difficulty to simulate small deformations of the skin like wrinkles and bulges when muscles deform its surface. As small as considered details are, they greatly contribute to the recognition of facial expressions, and thus to the realism of virtual faces.

Since many works have been proposed for large-scale animations and deformations, only a few of them deal with real-time animation of small-scale details. We denote small-scale details in an animation context, i.e. wrinkles and bulges appearing while muscles contractions, instead of the micro-structures of the skin independent to facial expressions. Recent progress in motion capture or wrinkles generation techniques allow the production of these details in a form of highresolution meshes that are not fully usable for real-time animation applications such as video games. Nevertheless, converting these detailed meshes into few wrinkle maps may be a good input for our real-time and low-memory technique.

Oat [START_REF] Oat | Animated wrinkle maps[END_REF] proposed a technique to blend wrinkle maps to render animated details on a human face. A mask map defines different facial areas, coefficients are manually tuned for each area to blend the wrinkle maps. This technique provides good results at an interactive time, but the task of defining wrinkle maps coefficients at each frame or key-frame of the animation is a long and tedious work. Furthermore, a new animation will require new coefficients and previous work could not be reused. It is why we intend to improve and adapt it to a face animated by skinning techniques.

Our dynamic wrinkling system is based on a small set of reference poses. A reference pose is a pair of a large-scale deformation (a skeleton pose) and its associated small-scale details (stored in the form of a wrinkle map). During the animation, the current pose is compared with reference poses and coefficients are automatically computed. Notice that comparison is done at a "bone level" resulting in local blends and independence between areas of the face.

The main contribution of our approach is that we propose a technique to easily add animation details on a face animated by skinning technique. Wrinkle maps coefficients are computed automatically by using a small set of reference poses. We do not use a mask map to separate areas of the face, we propose to use skinning weights as a correlation between bones movements and reference wrinkle maps influences. Moreover, it was designed to be easily inserted into a conventional runtime pipeline based on skinning and bump mapping such as new generation video game engines or any other interactive applications. Indeed, by blending wrinkle map on the GPU, our approach does not modify the per-pixel lighting, no additional rendering pass is required. And by only taking the bones positions as input, our approach does not need to change the animation aspect by skinning. Thus, the implementation requires a few efforts. The supplementary material needed compared to a skinning-based animation system is only a few set of reference poses, two are sufficient for the face. The runtime computation cost is not much more important than for classical animation and rendering pipelines. Finally as results, our approach greatly improves the realism by increasing the expressiveness of the face.

Related Work

Although many articles have been published on the large scale facial animation, adding details to an animation in real-time remains a difficult task. Some methods proposed physical models for skin aging and wrinkling simulation [START_REF] Wu | Simulation of static and dynamic wrinkles[END_REF][START_REF] Boissieux | Simulation of skin aging and wrinkles with cosmetics insight[END_REF][START_REF] Kono | Wrinkle generation model for 3d facial expression[END_REF][START_REF] Venkataramana | A kinematic-variational model for animating skin with wrinkles[END_REF]. Some research focused on details acquisition from real faces, based on intensity ratio images which are then convert to normal maps [START_REF] Tu | Surface detail capturing for realistic facial animation[END_REF], shape-from-shading [START_REF] Lo | Capturing facial details by space-time shape-from-shading[END_REF] or other similar self-shadowing extraction techniques [START_REF] Bickel | Multi-scale capture of facial geometry and motion[END_REF][START_REF] Bickel | Pose-space animation and transfer of facial details[END_REF], or with the help of structured light projectors [START_REF] Zhang | Spacetime faces: High-resolution capture for modeling and animation[END_REF][START_REF] Na | Hierarchical retargetting of fine facial motions[END_REF]. Some works proposed details transfer technique to use existing details to new faces [START_REF] Tu | Surface detail capturing for realistic facial animation[END_REF][START_REF] Na | Hierarchical retargetting of fine facial motions[END_REF][START_REF] Bickel | Pose-space animation and transfer of facial details[END_REF]. We focus this state of the art on wrinkling systems for animated mesh.

Volino et al. [START_REF] Volino | Fast geometrical wrinkles on animated surfaces[END_REF] presented a technique to add wrinkles on an existed animated triangulate surface. Based on the edges length variations, the amplitudes of applied height-maps are modified. For each edge and texture map, a shape coefficient is calculated to know the influence of an edge with the given map. More the edge is perpendicular to wrinkles, and more its compression or elongation will disturb the height map. The rendering is done by a ray-tracer with bump mapping shading and an adaptive mesh refinement. Bando et al. [START_REF] Bando | A simple method for modeling wrinkles on human skin[END_REF] proposed a method to generate fine and large scale wrinkles on human body parts. Fine scale wrinkles are rendered using bump mapping and are obtained by using direction field defined by user. Large scale wrinkles are rendered by displacing vertices of a high-resolution mesh and obtained by using Bezier curves manually drawn by user. Wrinkles amplitudes are modulated along mesh animation by computing triangle shrinkage. Na et al. [START_REF] Na | Hierarchical retargetting of fine facial motions[END_REF] extended the Expression Cloning technique [START_REF] Noh | Expression cloning[END_REF] to allow a hierarchical retargeting. Transfer could be apply to different animation level of details, from a low-resolution up to a high-resolution mesh where dynamic wrinkles appear.

While some techniques were proposed to generate wrinkles, few approaches focused on real-time applications [START_REF] Larboulette | Real-time dynamic wrinkles[END_REF][START_REF] Oat | Animated wrinkle maps[END_REF]. Larboulette et al. [START_REF] Larboulette | Real-time dynamic wrinkles[END_REF] proposed a technique to simulate dynamic wrinkles. The user defines wrinkling areas by drawing a perpendicular segment of wrinkles (wrinkling area), following by the choice of a 2D discrete control curve (wrinkle template). The control curve conserve its length while the mesh deformation, generating amplitude variations. Wrinkles are obtained by mesh subdivision and displacement along the wrinkle curve.

Many methods need a high resolution mesh or a costly on-the-fly mesh subdivision scheme to generate or animate wrinkles [START_REF] Bickel | Pose-space animation and transfer of facial details[END_REF][START_REF] Lo | Capturing facial details by space-time shape-from-shading[END_REF][START_REF] Na | Hierarchical retargetting of fine facial motions[END_REF][START_REF] Kono | Wrinkle generation model for 3d facial expression[END_REF]. Due to real-time constraints, these techniques are difficult to use in an efficient way. Recent advances in GPU computing allow to render efficiently fine details by using bump maps for interactive rendering.

Oat presented in [START_REF] Oat | Animated wrinkle maps[END_REF] a GPU technique to easily blend wrinkle maps applied to a mesh. Maps are subdivided in regions, for each region, coefficients allow to blend between the wrinkle maps. This technique requires few computational and storage costs, three normal maps are used for a neutral, a stretched and a compressed expressions. Furthermore it is easily implemented and added to an existing animation framework. As we explain in the introduction, the main drawback of this method is that it requires manual tuning of the wrinkle maps coefficients for each region. Our method aims to propose a real-time dynamic wrinkling system for skinned face generating automatically wrinkle maps coefficients and without the requirement of a mask map.

Overview

Figure 1 shows the complete framework of our wrinkling animation technique. The first step is to create o reference poses. Each of them consists on a skeleton pose (large scale deformation) and a wrinkle map (fine scale deformation). While the runtime animation, the current skeleton pose is compared with reference poses and coefficients are calculated for each bones of each reference poses. Skinning and reference poses/bones weights are used to blend wrinkle maps with the default normal map and render the face with surface lighting variations. This last step is done on the GPU while the per-pixel lighting process.

The remainder of this paper is organized as follows. In Section 4, we briefly present the existing large-scale deformation technique and the input reference poses. The section 5 presents the main part of the paper, we show how we use the reference poses in real-time to obtain dynamic wrinkling and fine details animation. In Section 6, we present some results and conclude this paper.

Fig. 1. Required input data are a classic skinned mesh in a rest pose and some reference poses (reference pose = skeleton pose + wrinkle map). In runtime, each pose of the animation is compared with the reference poses, bone by bone, then skinning influence is used as masks to apply the bones poses evaluation. Wrinkle maps are blended on the GPU and a per-pixel lighting allows to render the current frame with dynamic wrinkles and details.

Large-Scale Deformations and Reference Poses

As mentioned above, our goal is to adapt the wrinkle maps method to the family of skinning techniques which perform the large scale deformations of the face. They offer advantages in terms of memory cost and simplicity of posing. Many algorithms have been published [START_REF] Lewis | Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation[END_REF][START_REF] Kry | Eigenskin: Real time large deformation character skinning in hardware[END_REF][START_REF] Kurihara | Modeling deformable human hands from medical images[END_REF][START_REF] Rhee | Real-time weighted pose-space deformation on the gpu[END_REF] about skinning and its possible improvements. Our dynamic wrinkling technique could be used with any of the skinning methods cited. We only need that mesh vertices are attached to one or more bones with a convex combination of weights.

Reference poses are manually created by CG artist. He deforms the facial "skeleton" to obtain the expressions where he want to wrinkles appear. These expressions should be strongly pronounced to provide better results, i.e. , if artist wants that wrinkles appear while eyebrows rise up, he should pose the face with the maximum eyebrows rising up, when wrinkles furrows are deepest.

Since influences work with bones or group of bones, it is possible to define a pose where wrinkles appear in various areas of the face. Having details in different areas will not cause that all of these details appear at the same time at an arbitrary frame. For example, details around the mouth would appear independently with forehead details, even if they are described in a same reference pose.

Animated Wrinkles

Our goal is to use preprocessed wrinkles data to generate visual dynamic fine deformations of the face surface, instead of computing costly functions and algorithms in order to generate wrinkles on the fly. We explain in this section how reference poses are used in real-time and at arbitrary poses. The runtime algorithm consists on three main steps:

-Computing influences of each reference pose on each bone.

-Associating reference poses and vertices by using skinning weights and influences computed at the first step. -Blending wrinkle maps and the default normal map while the per-pixel lighting process.

Pose Evaluation

The first step is to compute the influence of each reference pose on each bone. This consists to find how the bone position at an arbitrary frame differs from its position at the reference poses 1 . Computing these influences at the bone level instead of a full pose level allows to determine regions of interest. This offers the possibility to apply different reference poses at same time. Resulting in the need of less reference poses (only 2 are sufficient for face: a stretched and a compressed expression).

We define the influence of the pose P k for the bone J i at an arbitrary frame f by this equation:

I P k (J if ) =        0 if J iP0 = J iP k α ikf if 0 ≤ α ikf ≤ 1 0 if α if k < 0 1 if α if k > 1 with α if k = (J if -J iP0 ) ⊙ (J iP k -J iP0 ) || (J iP k -J iP0 ) ||
where ⊙ denotes the dot product and ||.|| denotes the euclidean distance. This computation consists on projecting orthogonally J if onto the segment (J iP0 , J iP k ).

So, at each frame, reference poses influences for bone J i could be written as a vector of dimension o + 1 (o reference poses plus the rest pose)

α if =< α if 0 , α if 1 , ..., α if k , ...α if o >. α if 0 is the influence of the rest pose. α if 0 = max 0, 1 - o k=1 α if k
1 Notice that we deal with bones positions in the head root bone coordinates system, so we could assume that head rigid transformation will not cause problems while pose evaluation.

Bones Masks

Once we know the reference poses influences for each bone, we could use them for the per-pixel lighting. The main idea is to use skinning weights to compute the influence of reference poses for each vertex, and by the interpolation done during the rasterization phase, for each fragment (Fig. 2). Since wrinkles and expressive details are greatly related to the face deformations, we can deduce that these details are related with bones transformations too. So we associate bones influence with reference poses influences. We assume that skinning weights are convex, resulting in a simple equation (influence of the pose P k for vertex v jf at frame f ): Skeletons may greatly move along applications, complex animations require a lot of bones per face. This could generate some redundancy between bones transformations. If CG artist defines a pose which require a similar displacement of 3 adjacent bones, a wrinkle would appear along these 3 bones areas. At runtime, it may appears artifacts or wrinkle breaks if the 3 bones don't move similarly. To avoid this, we simply give the possibility to group some bones together. Their transformations still leave independent, but their poses weights are linked, i.e. the average of their coefficients is use instead of their initial values.

Inf (v jf , P k ) = n i=1 (w ji × I P k (J if ))

Details Blending

The final step of our method is to apply wrinkle maps to our mesh by using coefficients Inf (v jf , P k ) computed at the next step. Two methods can be used depending on how wrinkle maps have been generated:

-Wrinkle maps are neutral map improvements (i.e. details of the neutral map such as pores, scares and other static fine details are present in the wrinkle map). -Wrinkle maps only contain deformations associated with the expression.

In the first case, a simple blending is used. Since same static details are present in both neutral and wrinkle maps, a blending will not produce a loss of static deformations while in the second case, a simple averaging will cause it. For example, a fragment influenced by 100 percents of a wrinkle map will be drawn without using the neutral map, resulting in the fact that details of the neutral map will not appear. A finest blending is required. [START_REF] Oat | Animated wrinkle maps[END_REF] proposed one for normal map in tangent space, let --→ W N the final normal, W the normal provided by the blending of the wrinkle maps and N the normal provided by the default normal map:

-

-→ W N = normalize (W .x + N .x, W .y + N .y, W .z × N .z)
The addition of the two first coordinates makes a simple averaging between the direction of the two normals, given the desired direction. The z components are multiplied, this leads to increase details obtained from the two normals. Smaller the z value is, and more bumpy is the surface, multiplication allows to add the neutral surface variation to the wrinkled surface.

Results and Conclusion

Our test model Bob contains 9040 triangles for the whole body which is a current size for video-games. The face is rigged with 21 bones. Animation runs at more than 100 fps on a laptop equipped with a Dual Core 2.20GHz CPU, 2Go RAM and a NVidia 8600MGT GPU. Rendering is done using OpenGL and NVidia Cg for GPU programming. We use tangent space normal maps as wrinkle maps in our experiments. We focus our tests on the forehead wrinkles because they are the most visible expressive wrinkles and generate the higher visual deformations. Furthermore, this area is subjected to different muscles actuations, compressed and stretched expressions generate different small surface variations. Similar to [START_REF] Dutreve | Feature points based facial animation retargeting[END_REF], we use a feature-points based animation transfer to animate our characters. This facial animation retargeting algorithm is based on feature-points displacements and Radial Basis Function regression (Fig 3). Figure 4 shows 4 facial expressions with and without dynamic wrinkling. By analyzing the top row, you may notice that expression recognition is not easy. The neutral and the angry expressions of the eyebrows are not very distinct. However, the bottom row shows that wrinkles improve the expression recognition. Figure 5 shows the independence between facial areas without additional mask maps. Pose evaluation is done on the CPU, resulting coefficients are send to the GPU. The bones Masks step is perform into the vertex shader, i.e. skinning weights are multiplied by poses coefficients, resulting in o values (one value for each reference pose). The rasterization step is done and we obtain the interpolated values for each fragment in the pixel shader where we use these coefficients to blend normal maps and compute the lighting. Large scale deformation as well as the rendering are not modified, the addition of our method to an existing implementation is easy. No additional rendering pass is required, only few functions should be add to the different steps cited above. Data send to GPU equals o × n floating values with o the number of reference poses and n the number of bones.

Our technique is greatly artist-dependent. Three steps are important to obtain good results. First, a good rigging is primary since we directly use skinning weights as bones masks, and so, it defines how each vertex will be influenced by the different reference poses. Second, the reference poses should consist on an orthogonal set of skeleton poses as much as possible, to avoid an over fitting. Notice that blending reference poses in a same area is possible (last column of Fig. 4), but it becomes a problem if similar bones displacements lead to different fine-details. Finally, detail maps quality greatly influences the visual results.

Our choice to use skinning weights as bones masks offers many advantages. They allow us to relate large scale and small scale deformations, and so, we do not need additional mask textures. They ensure that vertices influenced by reference poses are vertices which are displaced accordingly with bones too. However, weights become smaller when they are far away from the bones location, and so wrinkles depth become smaller too, even if they should be as visible as those near bones.

We have presented a technique to use pre-generated reference poses to generate in real-time wrinkles and fine-details appearing while an arbitrary skinned face animation. In addition to providing interesting visual results, the requirements that we considered necessary and/or important have been met. Our dynamic animation wrinkles runs in real-time, the use of per-pixel lighting allows us to dispense with high-resolution meshes or costly subdivision techniques. Furthermore, it is based on widely-used techniques such as skinning and bump mapping. Its implementation does not present technical difficulties and does not modify usual animation and rendering pipeline. However, results depend greatly of the quality of the input data provided by the CG artist. We plan to investigate this issue by developing specific tools to help him/her in the reference poses creation.

Fig. 2 .

 2 Fig. 2. The two left images show the skinning influences of the two bones of the right eyebrow. A reference pose has been set with this two bones rising up. The last image shows the influence of this reference pose for each vertex attached to these bones.

Fig. 3 .

 3 Fig. 3. Example frames of an animation providing by a 2D tracker and transfer in real-time to our skinned face improved with our wrinkling system.

Fig. 4 .

 4 Fig. 4. The first row shows our character without dynamic wrinkles. The second rows shows reference poses influences. The last row shows our character with details. Notice that the second and the third column define the two reference poses.

Fig. 5 .

 5 Fig. 5. This figure demonstrates that reference poses influences are independent between areas of the face. Only the right area of the forehead is influenced by the stretch wrinkle map on the middle image while the whole forehead is influenced on the right image.


Arnault Lassin
email: a.lassin@brgm.fr

Laurent André
email: l.andre@brgm.fr

Nicolas Devau
email: n.devau@brgm.fr

Adeline Lach
email: a.lach@brgm.fr

Thomas Beuvier
email: tbeuvier@yahoo.fr

Alain Gibaud
email: alain.gibaud@univ-lemans.fr

Stéphane Gaboreau
email: s.gaboreau@brgm.fr

Mohamed Azaroual
email: m.azaroual@brgm.fr

Reactive transport modelling of calcium carbonate formation in a Lab-on-a-Chip device at 25°C

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

A mechanistic kinetic law for the successive formation of amorphous calcium carbonate (ACC) and calcite is developed at room temperature. It relies on a detailed description of aqueous speciation and a combination of transition-statetheory (TST) and surface complexation model (SCM) equations [1]. The proposed law aims at describing several inter-related mechanisms: i) formation of ACC seeds with the creation of surface complexation sites, ii) formation of calcite initiated by surface complexation and creation of new surface complexation sites, iii) growth of calcite at the expanse of ACC, iv) progressive disappearance of ACC.

The TST-SCM equations are implemented in the geochemical calculation software PhreeqC-3 [2] which allows managing complex kinetic laws. The calibration of the model is first performed on published data acquired on batch experiments [3]. Then, it is applied to a dynamic system which consists in the simultaneous injection of two aqueous solutions of CaCl 2 and Na 2 CO 3 , respectively, into a microchannel. The dimensions of the system and the conditions of injection are representative of a recently published experimental work [4] performed on a Lab-On-a-Chip device. The reactive transport modelling is done using the PHAST software [5] since it is full coupled with PhreeqC.

The numerical simulations could satisfactorily describe these observations. Obviously, there is room for further improvements like the use of more adequate flow equations (i.e. Navier-Stokes), as well as the implementation of the transport of particles.

Bibliographic references

  [1] Schott et al. (2009) Rev. Miner. Geochem., 70, 207-258. [2] Parkhurst & Appelo (2013) http://pubs.usgs.gov/tm/06/a43/ [3] Gebauer et al. (2008) Science, 322 (5909), 1819-1822. [4] Beuvier et al. (2015) Lab on a Chip, 15, 2002-2008 [5] Parkhurst et al. (2004) https://www.usgs.gov/software/phast