Mariana Haragus
email: mharagus@univ-fcomte.fr

Gérard Iooss

Domain walls for the Bénard-Rayleigh convection problem with "rigid-free" boundary conditions

Keywords: Bénard-Rayleigh convection, rolls, domain walls, bifurcations c

 to show that bifurcating domain walls lie on an 8-dimensional invariant submanifold of the center manifold. Consequently, the heteroclinic connections were found as solutions of an 8-dimensional, instead of a 12-dimensional, dynamical system.

Running head: Domain walls for the Bénard-Rayleigh convection problem

Introduction

The classical Bénard-Rayleigh convection problem is concerned with the flow of a viscous fluid filling the region between two horizontal planes and heated from below. We consider the Boussinesq approximation in which the dependency of the fluid density ρ on the temperature T is given by the relationship

ρ = ρ 0 (1 -γ(T -T 0 )) ,
where γ is the (constant) volume expansion coefficient, T 0 and ρ 0 are the temperature and the density, respectively, at the lower plane. In Cartesian coordinates (x, y, z) ∈ R 3 , the fluid occupies the domain R 2 ×(0, d) between the lower horizontal plane z = 0 and the upper horizontal plane z = d. The mathematical problem consists in solving the Navier-Stokes equations coupled with an equation for energy conservation, for the particle velocity V = (V x , V y , V z ), the pressure p, and the deviation of the temperature from the conduction profile θ. In dimensionless variables, the system reads

∂ t V = R -1/2 ∆V + θe z -P -1 (V • ∇)V -∇p, (1.1)
0 = ∇ • V , (1.2)
∂ t θ = R -1/2 ∆θ + V z -(V • ∇)θ, (1.3)
in which e z = (0, 0, 1) is the unit vertical vector. The dimensionless constants R and P are the Rayleigh and the Prandtl numbers, respectively, defined as

R = γgd 3 (T 0 -T 1 ) νκ , P = ν κ ,
where ν is the kinematic viscosity, κ the thermal diffusivity, g the gravitational constant, and T 1 the temperature at the upper plane.

The equations (1.1)-(1.3) are completed by boundary conditions. Each of the two horizontal planar boundaries may be a rigid plane or a free boundary, hence leading to different possible types of boundary conditions: "rigid-rigid", "free-free" , "rigid-free", or "free-rigid". We consider here the case of a "rigid" boundary at z = 0 and a "free" boundary at z = 1,

V x | z=0 = V y | z=0 = 0, ∂ z V x | z=1 = ∂ z V y | z=1 = 0, V z | z=0,1 = θ| z=0,1 = 0.
(1.4)

Together with these boundary conditions, the equations (1.1)-(1.3) are invariant under horizontal translations, rotations, and reflections in both x and y. While in the cases of "rigid-rigid" and "free-free" boundary conditions the system is also invariant under the vertical reflection z → 1 -z, this reflection changes the "rigid-free" boundary conditions above into "free-rigid" boundary conditions, with a "free" boundary at z = 0 and a "rigid" boundary at z = 1.

In the hydrodynamic problem, there is a critical value R c of the Rayleigh number, below which the simple "conduction regime" is stable, the fluid is at rest and the temperature depends linearly on the vertical coordinate. Above this critical value, the "conduction regime" looses its stability and a "convective regime" appears. Steady patterns bifurcating in this "convective regime" have been extensively studied over the years. Mathematically, they are found as steady solutions of the Navier-Stokes-Boussinesq system (1.1)- (1.3). Already in the forties, Pellew and Southwell [START_REF] Pellew | On maintained convection motion in a fluid heated from below[END_REF] computed the numerical value of R c in the three cases of "rigid-rigid", "free-free", and "rigid-free" boundary conditions. The first existence results for regular patterns, such as rolls, hexagons, or squares, appeared in the sixties in the works by Yudovich et al [START_REF] Ukhovskii | On the equations of steady state convection[END_REF][START_REF] Yudovich | On the origin of convection[END_REF][START_REF] Yudovich | Free convection and bifurcation[END_REF][START_REF] Yudovich | Stability of convection flows[END_REF], Rabinowitz [START_REF] Rabinowitz | Existence and nonuniqueness of rectangular solutions of the Bénard problem[END_REF], Görtler et al [START_REF] Görtler | Branching solutions of the Bénard problem. Problems of hydrodynamics and continuum mechanics[END_REF]. We refer to [START_REF] Koschmieder | Bénard cells and Taylor vortices[END_REF] for further references on these types of patterns, and also to the recent work [START_REF] Braaksma | Existence of bifurcating quasipatterns in steady Bénard-Rayleigh convection[END_REF] on quasipatterns. Besides regular convection patterns, different types of defects are regularly observed in experiments [START_REF] Bodenschatz | Recent development in Rayleigh-Bénard convection[END_REF][START_REF] Manneville | Rayleigh-Bénard convection, thirty years of experimental, theoretical, and modeling work. In "Dynamics of Spatio-Temporal Cellular Structures. Henri Bénard Cen[END_REF]. Domain walls, or grain boundaries, are line defects which may occur between rolls with different orientations (see Figure 1.1), and are steady solutions of the system (1.1)-(1.3). In our previous work [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], we showed that symmetric domain walls bifurcate for the Navier-Stokes-Boussinesq system (1.1)-(1.3) with either "rigid-rigid" or "free-free" boundary conditions for Rayleigh numbers R > R c close to the critical value R c . These domain walls are solutions of the steady system which are periodic in y, symmetric in x and their limits as x → ∓∞ are rolls rotated by opposite angles ±α with α ∈ (0, π/3). Here, we prove that a similar result holds in the case of "rigid-free" boundary conditions. We point out that larger angles α ∈ [π/3, π/2) have been treated in the simpler case of the Swift-Hohenberg equation in [START_REF] Scheel | Small-amplitude grain boundaries of arbitrary angle in the Swift-Hohenberg equation[END_REF] (see also [START_REF] Lloyd | Continuation and Bifurcation of Grain Boundaries in the Swift-Hohenberg Equation[END_REF]).

For the analysis of the bifurcation problem we use the spatial dynamics approach developed for the Swift-Hohenberg equation in [START_REF] Haragus | Grain boundaries in the Swift-Hohenberg equation[END_REF] and adapted to the Navier-Stokes-Boussinesq system (1.1)-(1.3) in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF]. The steady system (1.1)-(1.3) is written as a dynamical system in which the evolutionary variable is the spatial variable x and a center manifold theorem is used to reduce this infinite dimensional dynamical system to a 12-dimensional system. The reduction holds for Rayleigh numbers R close to the critical value R c and any fixed Prandtl number P and rotation angle α ∈ (0, π/3). Domain walls are constructed as heteroclinic solutions of this 12dimensional system which connect suitably chosen periodic orbits. In [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], the vertical reflection symmetry has been used to further reduce this system to an 8-dimensional system. The loss of this symmetry in the case of "rigid-free" boundary conditions does not allow for this second reduction of dimension, here we have to analyze the full 12-dimensional system.

The first step in the construction of the heteroclinic connection for the reduced system consists in a normal form transformation. We prove a normal form theorem which is valid for general reversible and O(2)-equivariant 12-dimensional vector fields under a certain nonresonance condition. For our reduced system these symmetries are obtained from the invariance of the Navier-Stokes-Boussinesq system under reflections in the horizontal variables x and y and under translations in y, and the non-resonance condition is satisfied for angles α = π/6. Next, similarly to [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], we scale variables in the normal form and identify a leading order system for which we construct a heteroclinic connection. Finally, using the implicit function theorem we prove the persistence of this leading order heteroclinic connection for the full 12-dimensional system. We obtain a heteroclinic solution connecting two periodic solutions of the 12-dimensional system. The two periodic solutions correspond to the same roll of the Navier-Stokes-Boussinesq system but rotated by opposite angles ±α and the heteroclinic connection corresponds to a symmetric domain wall. The result holds under suitable conditions on two quotients g 1 and g 3 involving four coefficients of the normal form. While the conditions on the quotient g 3 are the same as the ones used in the persistence proof in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], the conditions on the quotient g 1 are specific to the present case of "rigid-free" boundary conditions. Both g 1 and g 3 depend on the rotation angle α and the Prandtl number P through complicated analytical formulas. The validity of the required conditions is checked symbolically (Maple computations; see Figure 4.1). Our main result is summarized in the following theorem.

Theorem 1. Consider the Navier-Stokes-Boussinesq system (1.1)-(1.3) with "rigid-free" boundary conditions (1.4). Denote by R c the critical Rayleigh number at which convective rolls with wavenumbers k c bifurcate from the conduction state. Then for any angle α ∈ (0, π/3), α = π/6, there exists P * (α) 0 such that, up to a finite set, for any Prandtl number P > P * (α), a symmetric domain wall bifurcates for Rayleigh numbers R = R c + , with > 0 sufficiently small. The domain wall connects two rotated rolls which are the rotations by opposite angles ±(α + O( )) of a roll with wavenumber k c + O( ), continuously linked to the amplitude which is of order O( 1/2 ).

In contrast to the cases of "rigid-rigid" and "free-free" boundary conditions in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], here we exclude the angle α = π/6, because of the non-resonance condition in the normal form theorem, and for each angle α ∈ (0, π/3), α = π/6, we exclude a finite number of values of the Prandtl number P, at most, because of the presence of the additional four dimensions in the reduced system.

The analysis being similar to the one in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], we focus in our presentation on the main differences, namely, the normal form analysis and the persistence proof. In Section 2 we recall the first steps of the approach which up to some computations are the same as in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF]. We give the formulation of the steady Navier-Stokes-Boussinesq system as a dynamical system in Section 2.1, briefly discuss the existence of rolls and rotated rolls in Section 2.2, and obtain the 12-dimensional reduced system in Section 2.3. In Section 3 we prove the general normal forms result for reversible and O(2)-equivariant 12-dimensional vector fields. The proof of Theorem 1 is completed in Section 4. In Section 4.1 we recall the connection between rotated rolls and periodic solutions of the normal form system. The leading order system is found in Section 4.2 and we construct the heteroclinic connection in Section 4.3. Finally, in Appendix A we compute the coefficients of the normal form and the quotients g 1 and g 3 .

Spatial dynamics approach

Following [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], we start in Section 2.1 by formulating the steady system (1.1)-(1.3) as a dynamical system. In Section 2.2 we recall the existence of rolls and rotated rolls, and in Section 2.3 we obtain the 12-dimensional reduced system by using the center manifold theorem. All these steps being similar to the ones in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], we only recall the results and refer to [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF] for further details.

As in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], we replace the Rayleigh number R in the system (1.1)-(1.3) by its square root

µ = R 1/2 ,
and denote by k y the wavenumber in y of the solutions.

Formulation as a dynamical system

We introduce the new variables

W = µ -1 ∂ x V -pe x , φ = ∂ x θ,
and set

V ⊥ = (V y , V z ), W ⊥ = (W y , W z ), U = (V x , V ⊥ , W x , W ⊥ , θ, φ).
Then the steady system (1.1)-(1.3) is equivalent to the system

∂ x U = L µ U + B µ (U , U ), (2.1)
in which the operators L µ and B µ are linear and quadratic, respectively, defined by

L µ U =            -∇ ⊥ • V ⊥ µW ⊥ -µ -1 ∆ ⊥ V x -µ -1 ∆ ⊥ V ⊥ -θe z -µ -1 ∇ ⊥ (∇ ⊥ • V ⊥ ) -∇ ⊥ W x φ -∆ ⊥ θ -µV z            , B µ (U, U ) =           0 0 P -1 (V ⊥ • ∇ ⊥ )V x -V x (∇ ⊥ • V ⊥ ) P -1 (V ⊥ • ∇ ⊥ )V ⊥ + µV x W ⊥ 0 µ (V ⊥ • ∇ ⊥ )θ + V x φ           .
The choice of the phase space takes into account the boundary conditions (1.4), the periodicity in y of solutions, and the property that the flux F(x) = Ωper V x dy dz, Ω per = (0, 2π/k y ) × (0, 1), is constant. Fixing the constant flux to 0 we take the phase space

X = U ∈ (H 1 per (Ω)) 3 × (L 2 per (Ω)) 3 × H 1 per (Ω) × L 2 per (Ω) ; V z = θ = 0 on z = 0, 1, V x = V y = 0 on z = 0, and Ωper V x dy dz = 0 ,
where Ω = R × (0, 1) and the subscript per means that the functions are 2π/k y -periodic in y.

The remaining boundary conditions are included in the domain of definition of L µ ,

Z = U ∈ X ∩ (H 2 per (Ω)) 3 × (H 1 per (Ω)) 3 × H 2 per (Ω) × H 1 per (Ω) ; W z = φ = 0 on z = 0, 1, ∇ ⊥ • V ⊥ = W y = 0 on z = 0, and ∂ z V x = ∂ z V y = 0 on z = 1 .
The phase space X is a closed subspace of the Hilbert space

X = (H 1 per (Ω)) 3 × (L 2 per (Ω)) 3 × H 1 per (Ω) × L 2 per (Ω),
so that it is a Hilbert space endowed with the usual scalar product of X and with the choice above, the linear operator L µ is closed in X with dense and compactly embedded domain Z. The latter property implies that L µ has purely point spectrum consisting of isolated eigenvalues with finite algebraic multiplicities.

The dynamical system (2.1) is reversible and O(2)-equivariant. The reflection x → -x gives the reversibility symmetry

S 1 U (y, z) = (-V x , V ⊥ , W x , -W ⊥ , θ, -φ)(y, z), U ∈ X ,
which anti-commutes with L µ and B µ , the reflection y → -y gives the symmetry

S 2 U (y, z) = (V x , -V y , V z , W x , -W y , W z , θ, φ)(-y, z), U ∈ X ,
which commutes with L µ and B µ , and the horizontal translations y → y + a/k y along the y direction give a one-parameter family of linear maps (τ a ) a∈ R/2πZ , τ a U (y, z) = U (y + a/k y , z), U ∈ X , which commute with L µ and B µ and satisfy

τ a S 2 = S 2 τ -a , τ 0 = τ 2π = I.
In addition, the pressure p in the system (1.1)-(1.4) being only defined up to a constant, the dynamical system is invariant upon adding any constant to the new variable W x , i.e., it is invariant under the action of the one-parameter family of maps (T b ) b∈R defined by

T b U = U + bϕ 0 , ϕ 0 = (0, 0, 0, 1, 0, 0, 0, 0) t , U ∈ X .
(2.2)

Rolls, rotated rolls and domain walls

The existence of convection rolls for the steady system (1.1)-(1.3) with any combination of "rigid"/"free" boundary conditions is well-known (e.g., see [5, Section 2.2]). We consider here rolls which are constant in x and periodic in y with wavenumber k (see Figure 1.1a). According to classical theory, convection rolls bifurcate supercritically at the instability threshold µ = µ c of the conduction state, for wavenumbers k close to a critical value k c and µ > µ 0 (k) such that µ 0 (k c ) = µ c . The value µ 0 (k) is the smallest value µ for which the boundary value problem

(D 2 -k 2 ) 2 V = µk 2 θ, V = DV = 0 in z = 0, V = D 2 V = 0 in z = 1, (2.3)
(D 2 -k 2 )θ = -µV, θ = 0 in z = 0, 1, (2.4)
where D = d/dz denotes the derivative with respect to z, possesses nontrivial real-valued so-

lutions (V, θ) = (V k (z), θ k (z)). The map k → µ 0 (k) is analytical in k and has a strict global minimum at k = k c . 1
These solutions being independent of x, they are equilibria of the dynamical system (2.1). For any k y = k > 0 fixed close enough to k c , we obtain a circle of equilibria τ a (U * k,µ ), for a ∈ R/2πZ, which bifurcate for µ > µ 0 (k) sufficiently close to µ 0 (k), belong to Z, and satisfy

S 1 U * k,µ = S 2 U * k,µ = U * k,µ .
Furthermore, we have the expansions (see [5, Sections 2.2 and 4.1])

U * k,µ (y, z) = δe ikyy U k (z) + δe -ikyy U k (z) + O(δ 2 ), µ = µ 0 (k) + µ 2 δ 2 + O(δ 3 ), (2.5)
in which δ > 0 is sufficiently small, µ 2 > 0, and

U k (z) = 0, i k DV k (z), V k (z), -p k (z), 0, 0, θ k (z), 0 T ,
where (V k , θ k ) is a solution of the boundary value problem (2.3)-(2.4) for µ = µ 0 (k) and the pressure p k is determined up to a constant from the stationary part of the equation (1.1).

The system (1.1)-(1.4) is invariant under horizontal rotations acting through

R α (V x , V y , V z , θ)(x, y, z) = (R α (V x , V y ), V z , θ)(R -α (x, y), z), (2.6)
where R α (x, y) = (x cos α -y sin α, x sin α + y cos α), and α ∈ R/2πZ is the rotation angle, and this rotation invariance is inherited by the dynamical system (2.1). 2 Consequently, the rotated rolls R α U * k,µ are solutions of both systems. As solutions of the dynamical system (2.1), they are 2π/k sin α-periodic solutions in x which belong to the phase space X for k y = k cos α. For the particular angles α ∈ {0, π} the rotated rolls are 1 Pellew and Southwell [START_REF] Pellew | On maintained convection motion in a fluid heated from below[END_REF] computed the numerical values of kc and µc = µ0(kc) and found in the case of "rigid-free" boundary conditions that kc ≈ 2.682 and µc ≈ 33.176. 2 We do not need here the more complicated representation formula for the 8-components vector U in (2.1).

equilibria in the phase-space X with k y = k, whereas for α ∈ {π/2, 3π/2} they are 2π/k-periodic solutions in x, for any k y > 0. Notice that rolls rotated by angles α and π + α coincide,

R α U * k,µ = R π+α U * k,µ ,
and that the actions of S 1 and S 2 on a roll rotated by an angle α / ∈ {0, π} gives the same roll but rotated by the opposite angle,

S 1 (R α U * k,µ (x)) = R -α U * k,µ (-x), S 2 R α U * k,µ = R -α U * k,µ . (2.7)
In particular, rotated rolls keep a reversibility symmetry,

S 1 S 2 (R α U * k,µ (x)) = R α U * k,µ (-x). (2.8)
Heteroclinic solutions of the dynamical system (2.1) connecting two rolls rotated by different angles are domain walls. We construct our symmetric domain walls as S 1 -reversible heteroclinic solutions of the dynamical system (2.1) which connect the rotated rolls R α U * k,µ at x = -∞ and R -α U * k,µ at x = ∞, for rotation angles α ∈ (0, π/3).

Reduced bifurcation problem

Following the bifurcation analysis in [5, Section 4], we consider the dynamical system (2.1) in the phase X with

k y = k c cos α, α ∈ (0, π/3),
fix the Prandtl number P and take µ = µ c + ε close to µ c as bifurcation parameter. We apply a center manifold theorem to construct a 12-dimensional invariant manifold which contains the small bounded solutions of the dynamical system (2.1). We write the dynamical system (2.1) in the form

∂ x U = L µc U + R( U , ε), (2.9)
where

R(U , ε) = (L µ -L µc )U + B µ (U , U ) is a smooth map from Z × I c , I c = (-µ c , ∞), into X , and
R(0, ε) = 0, D U R(0, 0) = 0.
The hypotheses of the center manifold theorem are checked in the same way as in [5, Section 5.1]. The only differences are the explicit formulas of the eigenvectors and generalized eigenvectors which are slightly changed because the boundary conditions are different, and the absence of a symmetry due to the loss of the vertical reflection symmetry z → 1 -z for the "rigid-free" boundary conditions. As shown in [5, Lemma 4.2], the center spectrum σ c (L µc ) of the linear operator L µc consists of five eigenvalues,

σ c (L µc ) = {0, ±ik c , ±ik x }, k x = k c sin α, (2.10)
with the following properties.

(i) The eigenvalue 0 is simple with associated eigenvector ϕ 0 given by (2.2), which is invariant under the actions of S 1 , S 2 , and τ a .

(ii) The complex conjugated eigenvalues ±ik c are algebraically double and geometrically simple with associated generalized eigenvectors of the form

ζ 0 (y, z) = U 0 (z), Ψ 0 (y, z) = Ψ 0 (z),
for the eigenvalue ik c , and the complex conjugated vectors for the eigenvalue

-ik c , such that (L µc -ik c )ζ 0 = 0, (L µc -ik c )Ψ 0 = ζ 0 ,
and

S 1 ζ 0 = ζ 0 , S 2 ζ 0 = ζ 0 , τ a ζ 0 = ζ 0 , S 1 Ψ 0 = -Ψ 0 , S 2 Ψ 0 = Ψ 0 , τ a Ψ 0 = Ψ 0 .
(iii) The complex conjugated eigenvalues ±ik x are algebraically quadruple and geometrically double with associated generalized eigenvectors of the form

ζ ± (y, z) = e ±ikyy U ± (z), Ψ ± (y, z) = e ±ikyy Ψ ± (z),
for the eigenvalue ik x , and the complex conjugated vectors for the eigenvalue

-ik x , such that (L µc -ik x )ζ ± = 0, (L µc -ik x )Ψ ± = ζ ± , and
S 1 ζ + = ζ -, S 2 ζ + = ζ -, τ a ζ + = e ia ζ + , S 1 ζ -= ζ + , S 2 ζ -= ζ + , τ a ζ -= e -ia ζ -, S 1 Ψ + = -Ψ -, S 2 Ψ + = Ψ -, τ a Ψ + = e ia Ψ + , S 1 Ψ -= -Ψ + , S 2 Ψ -= Ψ + , τ a Ψ -= e -ia Ψ -.
The explicit formulas of the eigenvectors ζ 0 and ζ ± needed for our computations are given in Appendix A.

As a consequence of the center manifold theorem, the small bounded solutions of the dynamical system (2.9), and in particular the heteroclinic solutions, belong to a center manifold

M c (ε) = {U c + Φ(U c , ε) ; U c ∈ X c }, (2.11)
where X c is the spectral subspace associated with the center spectrum (2.10) of L µc and Φ ∈ C k (X c × I c , Z h ), for any arbitrary, but fixed, k 4, with Z h = (I -P c )Z and P c the spectral projection onto X c . The invariant dynamics on the center manifold is determined by the reduced system

dU c dx = L µc Xc U c + P c R(U c + Φ(U c , ε), ε) def = f (U c , ε), (2.12)
where

f (0, ε) = 0, D Uc f (0, 0) = L µc Xc ,
and this reduced system inherits the symmetries of (2.9), i.e., the reduced vector field f (•, ε) anti-commutes with S 1 , commutes with S 2 and τ a , and is invariant under the action of T b . Writing

U c = wϕ 0 + A 0 ζ 0 + B 0 Ψ 0 + A + ζ + + B + Ψ + + A -ζ -+ B -Ψ - (2.13) + A 0 ζ 0 + B 0 Ψ 0 + A + ζ + + B + Ψ + + A -ζ -+ B -Ψ -,
with w ∈ R and X = (A 0 , B 0 , A + , B + , A -, B -) ∈ C 6 , the reduced system (2.12) leads to the system

dw dx = h(w, X, X, ε), (2.14
)

dX dx = F (w, X, X, ε), (2.15)
together with the complex conjugated equation of (2.15) for X, in which h is real-valued and F = (f 0 , g 0 , f + , g + , f -, g -) has six complex-valued components. The invariance of the reduced system under the action of T b ,

T b (w, A 0 , B 0 , A + , B + , A -, B -) = (w + b, A 0 , B 0 , A + , B + , A -, B -),
implies that the reduced vector field (h, F ) does not depend on w, so that we can first solve (2.15) for X, and then determine w by integrating (2.14). Consequently, we can restrict to solving the equation dX dx = F (X, X, ε), (2.16)

which together with the complex conjugate equation for X form a 12-dimensional system. Notice that the symmetries of the reduced system act on these variables through

S 1 (A 0 , B 0 , A + , B + , A -, B -) = (A 0 , -B 0 , A -, -B -, A + , -B + ), (2.17)
S 2 (A 0 , B 0 , A + , B + , A -, B -) = (A 0 , B 0 , A -, B -, A + , B + ), (2.18) τ a (A 0 , B 0 , A + , B + , A -, B -) = (A 0 , B 0 , e ia A + , e ia B + , e -ia A -, e -ia B -). ( 2

.19)

3 A cubic normal form for 12-dimensional vector fields

In this section we prove a normal form theorem for reversible and O(2)-equivariant 12-dimensional vector fields having the same linear part and symmetries as the one in (2.16).

Theorem 2. Consider a system of ordinary differential equations

dX dx = G(X, X, ε), (3.1)
in which X = (A 0 , B 0 , A + , B + , A -, B -) ∈ C 6 and the vector field G is of class C k , for some k 4, in a neighborhood

U 1 × U 1 × U 2 ⊂ C 6 × C 6 × R of the origin. Assume that G(0, 0, ε) = 0, D X G(0, 0, 0) = L 0 , D X G(0, 0, 0) = 0,
where L 0 is a Jordan matrix acting on X through

L 0 =    B 1 0 0 0 B 2 0 0 0 B 2    , B 1 = ik c 1 0 ik c , B 2 = ik x 1 0 ik x , with 1 < k c /k x = 2
, and that G(•, •, ε) anti-commutes with S 1 given by (2.17) and commutes with S 2 and τ a given by (2.18) and (2.19), respectively. There exist neighborhoods V 1 and V 2 of 0 in C 6 and R, respectively, such that for any ε ∈ V 2 , there is a polynomial P (•, •, ε) : C 6 × C 6 → 6 of degree 3 in the variables (Z, Z), such that for

Z ∈ V 1 , the change of variable X = Z + P (Z, Z, ε),
transforms the equation (3.1) into the normal form

dZ dx = L 0 Z + N (Z, Z, ε) + ρ(Z, Z, ε), (3.2)
with the following properties:

(i) the map ρ belongs to C k (V 1 × V 1 × V 2 , C 6 ), and
ρ(Z, Z, ε) = O(|ε| 2 Z + ε Z 3 + Z 4 );
(ii) both N (•, •, ε) and ρ(•, •, ε) anti-commute with S 1 and commute with S 2 and τ a , for any ε ∈ V 2 ;

(iii) the six components (N 0 , M 0 , N + , M + , N -, M -) of N are of the form

N 0 = iA 0 P 0 + α 5 (A + u 7 + A -u 8 ), M 0 = iB 0 P 0 + A 0 Q 0 + α 5 (B + u 7 + B -u 8 ) + ia 5 (A + u 7 + A -u 8 ), N + = iA + P + + β 7 A 0 u 7 + β 8 A -u 9 , M + = iB + P + + A + Q + + β 7 B 0 u 7 + ib 7 A 0 u 7 + β 8 B -u 9 + ib 8 A -u 9 , N -= iA -P -+ β 7 A 0 u 8 -β 8 A + u 9 , M -= iB -P -+ A -Q -+ β 7 B 0 u 8 + ib 7 A 0 u 8 -β 8 B + u 9 -ib 8 A + u 9 , with P 0 = α 0 ε + α 1 u 1 + α 2 u 2 + α 3 (u 3 + u 5 ) + α 4 (u 4 + u 6 ), Q 0 = a 0 ε + a 1 u 1 + a 2 u 2 + a 3 (u 3 + u 5 ) + a 4 (u 4 + u 6 ), P + = β 0 ε + β 1 u 1 + β 2 u 2 + β 3 u 3 + β 4 u 4 + β 5 u 5 + β 6 u 6 , Q + = b 0 ε + b 1 u 1 + b 2 u 2 + b 3 u 3 + b 4 u 4 + b 5 u 5 + b 6 u 6 , P -= β 0 ε + β 1 u 1 + β 2 u 2 + β 5 u 3 + β 6 u 4 + β 3 u 5 + β 4 u 6 , Q -= b 0 ε + b 1 u 1 + b 2 u 2 + b 5 u 3 + b 6 u 4 + b 3 u 5 + b 4 u 6 ,
where (A 0 , B 0 , A + , B + , A -, B -) are the six components of Z, the coefficients α j , a j , β j , b j are all real, and

u 1 = A 0 A 0 , u 2 = i(A 0 B 0 -A 0 B 0 ), u 3 = A + A + , u 4 = i(A + B + -A + B + ), u 5 = A -A -, u 6 = i(A -B --A -B -), u 7 = (A 0 B + -A + B 0 ), u 8 = (A 0 B --A -B 0 ), u 9 = (A + B --A -B + ).
Proof. From general normal form theorems (e.g., see [4, Sections 3.2.1, 3.3.1, and 3.3.2]), we obtain the existence of two polynomials P (•, •, ε) and N (•, •, ε) of degree 3 in the variables (Z, Z) such that the properties (i) and (ii) hold, the polynomial N is of the form

N (Z, Z, ε) = N 1 (Z, Z)ε + N 2 (Z, Z) + N 2 (Z, Z)ε + N 3 (Z, Z), (3.3)
with N p and N p homogeneous polynomials of degree p in (Z, Z), and satisfies the identity

D Z N (Z, Z, ε)L * 0 Z + D Z N (Z, Z, ε)L * 0 Z = L * 0 N (Z, Z, ε), ∀ (Z, ε) ∈ C 6 × V 2 , (3.4)
in which L * 0 is the adjoint of L 0 . Due to the equivariance of the normal form under the action of the symmetry S 2 , it is enough to determine the first four components (N 0 , M 0 , N + , M + ) of N , the result for (N -, M -) being obtained by exchanging the indices + and -in the expressions of (N + , M + ).

Monomials in N 0 are M 0 are of the form

A p 0 0 A 0 q 0 B r 0 0 B 0 s 0 A p + + A + q + B r + + B + s + A p - -A - q -B r - -B - s -, (3.5)
with nonnegative exponents such that

p 0 + q 0 + r 0 + s 0 + p + + q + + r + + s + + p -+ q -+ r -+ s -= m, m ∈ {1, 2, 3}. (3.6)
From the commutativity of N and τ a , we obtain that their exponents also satisfy the equality

(p + -q + + r + -s + ) -(p --q -+ r --s -) = 0, (3.7)
and we claim that we also have the equalities

p 0 -q 0 + r 0 -s 0 = 1, (p + -q + + r + -s + ) + (p --q -+ r --s -) = 0, (3.8)
when k c /k x = 2. Indeed, the identity (3.4) implies that N 0 and M 0 satisfy the equalities

(D * + ik c )N 0 = 0, (D * + ik c )M 0 = N 0 ,
in which

D * = -ik c A 0 ∂ ∂A 0 + (A 0 -ik c B 0 ) ∂ ∂B 0 + ik c A 0 ∂ ∂A 0 + (A 0 + ik c B 0 ) ∂ ∂B 0 -ik x A + ∂ ∂A + + (A + -ik x B + ) ∂ ∂B + + ik x A + ∂ ∂A + + (A + + ik x B + ) ∂ ∂B + -ik x A - ∂ ∂A - + (A --ik x B -) ∂ ∂B - + ik x A - ∂ ∂A - + (A -+ ik x B -) ∂ ∂B - ,
is a linear map which preserves the degree of homogeneous polynomials. For a fixed degree m, taking a basis of monomials ordered by decreasing exponents p 0 , q 0 , r 0 , s 0 , p + , q + , r + , s + , p -, q -, r -, and s -, the action of D * is represented by a lower triangular matrix with equal elements on the diagonal given by

-ik c (p 0 -q 0 + r 0 -s 0 ) -ik x (p + -q + + r + -s + ) -ik x (p --q -+ r --s -) .
Consequently, the polynomials N 0 and M 0 , which belong to the kernel and generalized kernel of D * + ik c , respectively, belong to the subspace spanned by monomials for which the quantity above is equal to -ik c . Taking into account that k c /k x > 1 and the properties (3.6)-(3.7), we conclude that (3.8) holds when k c /k x = 2. This proves the claim. Next, taking m = 1 in (3.6) and using (3.6)-(3.8) it is straightforward to check that the first two components of N 1 in (3.3) have the form given in (iii). For even integers m, and in particular for m = 2, from the equalities (3.6) and (3.7) we obtain that p 0 -q 0 + r 0 -s 0 must be an even integer. This contradicts the first equality in (3.7). Consequently, there are no monomials of even degree in the first two components of N . It remains to consider the cubic monomials, m = 3. Collecting all cubic monomials satisfying (3.6)-(3.8), we directly compute the action of (D * + ik c ) on all these monomials. Then we identify a basis for the kernel of (D * + ik c ) which gives the result for N 0 , and a basis for the generalized kernel of (D * + ik c ) which gives the result for M 0 .

For the components N + and M + of N the result is obtained in the same way. We only point out that for these polynomials the exponents of the monomials (3.5) satisfy (3.6), the equality

(p + -q + + r + -s + ) -(p --q -+ r --s -) = 1,
replacing (3.7), and

p 0 -q 0 + r 0 -s 0 = 0, (p + -q + + r + -s + ) + (p --q -+ r --s -) = 1, instead of (3.8).
Finally, taking into account the action of the reversibility S 1 , it is straightforward to check that the coefficients α j , a j , β j and b j are real. This completes the proof of the theorem. Remark 3.1. In the resonant case k c /k x = 2, the two polynomials N 0 and M 0 contain the additional quadratic terms α 6 A + A -and iα 6 (B + A -+ A + B -) + a 6 A + A -, respectively, with real coefficients α 6 and c 6 .

Applying the result in Theorem 2 to our reduced system (2.16) we obtain its normal form (3.2) for k c /k x = 2, i.e., for any angle α ∈ (0, π/3), α = π/6.

Existence of domain walls

In this section, we prove the existence of a heteroclinic connection for the normal form system (3.2). Following the analysis from [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF], we focus on the main differences and refer to [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF] for the technical details which remain the same.

We restrict to ε > 0, which corresponds to values µ > µ c for which rolls exist and exclude the resonant angle α = π/6 which requires a different analysis.

Rotated rolls and coefficients of the normal form

The rotated rolls R -β U * k,µ with rotation angle β ∈ (0, π/2) are 2π/k sin β-periodic solutions of the dynamical system (2.1) and belong to the phase X when their wavenumber in y is equal to k y ,

k cos β = k y = k c cos α.
For (k, µ) close enough to (k c , µ c ) they are small bounded solutions which belong to the center manifold (2.11) of (2.9). Projected on the center space X c they become 2π/k sin β-periodic solutions of the reduced system (3.1) and also of the normal form system (3.2). Comparing the formulas (2.5) and (2.6) for R -β U * k,µ with the formulas (2.11) and (2.13) for the solutions on the center manifold, we obtain a family Z ε,θ of 2π/k sin β-periodic solutions of the normal form system, where the parameters (ε, θ) are related to (k, µ) through the equalities

ε = µ -µ c , θ = k sin β -k x = k sin β -k c sin α = 1 sin α (k -k c ) + O(|k -k c | 2 ).
These solutions have the expansion

Z ε,θ (x) = 0, 0, δe i(kx+θ)x , 0, 0, 0 + O(|δ||θ| + |δ| 2 ),
with δ > 0 as in (2.5), and satisfying

δ 2 = 1 µ 2 ε - µ 0 (k c ) sin 2 α 2µ 2 θ 2 + O(|ε| 3/2 + |ε| 1/2 |θ| 2 + |θ| 3 ).
As shown in [5, Section 6.2], we can use this family of solutions to determine two coefficients of the normal form system

b 0 = - 2 µ 0 (k c ) sin 2 α < 0, b 3 = 2µ 2 µ 0 (k c ) sin 2 α > 0, (4.1)
where µ 0 (k) > 0 is the second order derivative of µ 0 (k) with respect to k and µ 2 > 0 is determined by the second equality in (2.5). The symmetry properties (2.7) and (2.8) of rotated rolls are preserved so that Z ε,θ is S 1 S 2 -reversible and the rolls R β U * k,µ rotated by the opposite angle β give the periodic solutions S 2 Z ε,θ . We refer to [5, Section 6.2] for more details.

Similarly, by taking the rotation angle β = π/2, from the rotated rolls R π/2 U * k,µ , which are constant in y and therefore 2π/k-periodic solutions of the dynamical system (2.1), we obtain a second family of periodic solutions for the normal form system. With the help of these solutions we can compute two other coefficients of the normal form system,

a 0 = - 2 µ 0 (k c ) < 0, a 1 = 2µ 2 µ 0 (k c ) > 0.
Notice that we have the following relationship between coefficients:

a 0 = b 0 sin 2 α < 0, a 1 = b 3 sin 2 α > 0. (4.2)

Leading order dynamics

We consider the new variables

x = |b 0 ε| 1/2 x, A 0 (x) = b 0 ε b 3 1/2 e ikcx C 0 ( x), B 0 (x) = |b 0 ε| |b 3 | 1/2 e ikcx D 0 ( x), (4.3)
A ± (x) = b 0 ε b 3 1/2 e ikxx C ± ( x), B ± (x) = |b 0 ε| |b 3 | 1/2 e ikxx D ± ( x). (4.4)
Replacing these variables into the normal form system (3.2) and taking into account the signs of b 0 and b 3 in (4.1) and the relationship (4.2), we obtain the new system

C 0 = D 0 + O(ε 1/2 ), (4.5)
D 0 = sin 2 α -1 + |C 0 | 2 + g 1 (|C + | 2 + |C -| 2 ) C 0 + O(ε 1/2 ), (4.6)
C + = D + + O(ε 1/2 ), (4.7)
D + = -1 + g 2 |C 0 | 2 + |C + | 2 + g 3 |C -| 2 C + + O(ε 1/2 ), (4.8)
C -= D -+ O(ε 1/2 ), (4.9)
D -= -1 + g 2 |C 0 | 2 + g 3 |C + | 2 + |C -| 2 C -+ O(ε 1/2 ), (4.10)
in which

g 1 = a 3 a 1 , g 2 = b 1 b 3 , g 3 = b 5 b 3 .
Solving the equations (4.5), (4.7) and (4.9) for D 0 , D + and D -, respectively, we rewrite the first order system (4.5)-(4.10) as a second order system,

C 0 = sin 2 α -1 + |C 0 | 2 + g 1 (|C + | 2 + |C -| 2 ) C 0 + O(ε 1/2 ), (4.11)
C + = -1 + g 2 |C 0 | 2 + |C + | 2 + g 3 |C -| 2 C + + O(ε 1/2 ), (4.12)
C -= -1 + g 2 |C 0 | 2 + g 3 |C + | 2 + |C -| 2 C -+ O(ε 1/2 ), (4.13)
in which the O(ε 1/2 )-terms are continuous in (C 0 , C ± , 1/2 ) and continuously differentiable in (C 0 , C ± ). 3From the periodic solutions Z ε,θ and S 2 Z ε,θ of the normal form system we obtain the S 1 S 2reversible solutions P ε,θ and Q ε,θ = S 2 P ε,θ , respectively, for the system (4.11)-(4.13) with expansions

P ε,θ (x) = 0, (1 -θ 2 ) 1/2 e iθx , 0 + O(ε 1/2 ), Q ε,θ (x) = 0, 0, (1 -θ 2 ) 1/2 e iθx + O(ε 1/2 );
(see also [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF]Lemma 6.3]). Notice that these solutions represent the rotated rolls R -β U * k,µ and R β U * k,µ . While they are periodic at leading order, the terms O(ε 1/2 ) are quasiperiodic in x due to the presence of the exponentials e ikcx and e ikxx in the change of variables (4.3)- (4.4).

An important property of the leading order system obtained by setting ε = 0 in (4.11)-(4.13) is that it leaves the four-dimensional subspace {(C 0 , C + , C -) ; C 0 = 0} invariant. Restricting to this subspace we recover the leading order system from [5, Section 7.1],

C + = -1 + |C + | 2 + g 3 |C -| 2 C + , (4.14)
C -= -1 + g 3 |C + | 2 + |C -| 2 C -. (4.15)
The existence of a heteroclinic solution for this system has been proved in [START_REF] Van Den Berg | A domain-wall between single-mode and bimodal states[END_REF]. According to [14, Theorem 5], for any g 3 > 1, the system (4.14)-(4.15) possesses a heteroclinic solution (C * + , C * -), with C * ± smooth real-valued functions defined on R, which is S 1 -reversible and connects the equilibrium (0, 1) as x → -∞ with the equilibrium (1, 0) as x → ∞. This heteroclinic solution represents the leading order part of the domain walls constructed in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF].

The invariance of the subspace {(C 0 , C + , C -) ; C 0 = 0} implies that the leading order system from (4.11)-(4.13) possesses the S 1 -reversible heteroclinic solution (0, C * + , C * -), with C * ± as above, which connects the equilibrium (0, 0, 1) as x → -∞ with the equilibrium (0, 1, 0) as x → ∞. Notice that the equilibria (0, 0, 1) and (0, 1, 0) are equal to Q 0,0 and P 0,0 and therefore represent the rotated rolls with wavenumber k c , R α U * kc,µ and R -α U * kc,µ , respectively.

Existence of heteroclinic solutions

The existence of domain walls is obtained by proving that the S 1 -reversible heteroclinic solution (0, C * + , C * -) found for ε = 0 persists for ε > 0. More precisely, we have the following result.

Theorem 3. Assume that g 1 > 1 and g 3 ∈ (1, 4 + √ 13). Except for at most a sequence of values g 1 converging to 1, for any ε > 0 sufficiently small, there exists θ = O(ε 1/2 ), continuously depending on ε 1/2 , such that the system (4.12)-(4.13) possesses a reversible heteroclinic solution

C ε = (C 0,ε , C +,ε , C -,ε ) connecting the solutions Q ε,θ , as x → -∞, to P ε,θ , as x → ∞.
The quotients g 1 and g 3 depend on the angle α and the Prandtl number P through the complicated analytical formulas (A.1) and (A.2) computed in Appendix A. Taking α = 0 in (A.2) we obtain that the limit as α → 0 of g 3 is equal to 2, just as in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF]. Consequently, the condition g 3 ∈ (1, 4 + √ 13) holds at least for small angles α ∈ (0, α * (P)), for some positive α * (P). For g 1 , we have the same property when α = π/2, but these angles are excluded from our analysis and it seems difficult to check analytically the inequality g 1 > 1 for angles α ∈ (0, π/3). Instead, we compute g 3 symbolically, using Maple, and obtain that g 3 > 1.3, for any positive Prandtl number P and any angle α ∈ (0, π/2), hence the inequality g 3 > 1 is always satisfied. By comparing the formulas (A.1) and (A.2) we then obtain that the inequality g 1 > 1.3 always holds, as well. This implies that we only have to exclude a finite number of values g 1 in Theorem 3. The same Maple computation also allows to determine the values (α, P) for which the second condition on g 3 is satisfied, i.e., g 3 < 4 + √ 13. We summarize these properties in The solutions Q ε,θ and P ε,θ in Theorem 3 representing the rotated rolls R β U * k,µ and R -β U * k,µ , respectively, the result in Theorem 1 is an immediate consequence of Theorem 3 and the properties of g 1 and g 3 in Figure 4.1.

The proof of Theorem 3 is based on the implicit function theorem applied in the space of S 1 -reversible exponentially decaying functions,

X r η = {(C 0 , C + , C -, C 0 , C + , C -) ∈ X η ; C 0 (x) = C 0 (-x), C + (x) = C -(-x), x ∈ R},
where, for η > 0,

X η = (C 0 , C + , C -, C 0 , C + , C -) ∈ (L 2 η ) 4 , L 2 η = f : R → C ; R e 2η|x| |f (x)| 2 < ∞ .
It turns out that the linear operator needed in the implicit function theorem has exactly the same properties as the one in [5, Lemma 7.3]. Therefore, the implicit function theorem can be applied in the same way as done in [5, Theorem 2] and we omit these details of proof here. We focus on the properties of this linear operator, which is obtained by linearizing the system (4.11)-(4.13) with ε = 0, together with the complex conjugated equations, at (0, C * + , C * -), i.e., the linear operator L * acting on (C 0 , C + , C -) through

L *    C 0 C + C -    =    C 0 -sin 2 α -1 + g 1 (C * 2 + + C * 2 -) C 0 C + --1 + 2C * 2 + + g 3 C * 2 -C + -C * 2 + C + -g 3 C * + C * -(C -+ C -) C ---1 + g 3 C * 2 + + 2C * 2 -C --C * 2 -C --g 3 C * + C * -(C + + C + )    .
We prove that this operator has the same properties as in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF]Lemma 7.3], which completes the proof of Theorem 3.

Lemma 4.1. Assume that g 1 > 1 and g 3 ∈ (1, 4 + √ 13). Except for at most a sequence of values g 1 converging to 1, for any η > 0 sufficiently small, the operator L * acting in X r η is Fredholm with index -1. The kernel of L * is trivial and the one-dimensional kernel of its L 2 -adjoint is spanned by (0, iC * + , -iC * -, 0, -iC * + , iC * -).

Proof. The action of the operator L * on the C 0 -component being decoupled from the action on the (C + , C -)-components, we may write

L * = L 0 0 0 L ± , with L 0 C 0 = C 0 -sin 2 α -1 + g 1 (C * 2 + + C * 2 -) C 0 , L ± C + C - = C + --1 + 2C * 2 + + g 3 C * 2 -C + -C * 2 + C + -g 3 C * + C * -(C -+ C -) C ---1 + g 3 C * 2 + + 2C * 2 -C --C * 2 -C --g 3 C * + C * -(C + + C + )
, and we have the complex conjugated actions on the components C 0 and (C + , C -). The operator L ± is precisely the one from [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF]Lemma 7.3]. For any g 3 > 1, it is a Fredholm operator with index -1, has a trivial kernel, and the one-dimensional kernel of its L 2 -adjoint is spanned by (iC * + , -iC * -, -iC * + , iC * -). To complete the proof it remains to show that the operator L 0 is invertible.

Taking as new variables

y = (sin α)x, U 0 = 1 2 (C 0 + C 0 ), V 0 = 1 2i (C 0 -C 0 ), C * ± (y) = C * ± (x),
we obtain the matrix operator

M 0 U 0 V 0 = U 0 + U 0 -g 1 ( C * 2 + + C * 2 -)U 0 V 0 + V 0 -g 1 ( C * 2 + + C * 2 -)V 0 , acting in X 0 η = (U 0 , V 0 ) ∈ (L 2 η ) 2 ; U 0 (y) = U 0 (-y), V 0 (y) = -V 0 (-y), y ∈ R .
The invertibility of L 0 is equivalent to the invertibility of the matrix operator M 0 . The action of M 0 on the two components U 0 and V 0 being the same its invertibility in X 0 η is equivalent to that of the scalar operator L 0 [g 1 ] = ∂ yy + 1 -g 1 ( C * 2 + + C * 2 -) acting in L 2 η . We show the invertibility of this operator in L 2 , except for at most a sequence of values g 1 converging to 1, which by a standard perturbation argument implies its invertibility L 2 η for sufficiently small η.

The function C * 2 + + C * 2 -converging towards 1 as x → ±∞, the operator L 0 [g 1 ] is a relatively compact perturbation of the asymptotic selfadjoint operator ∂ yy + 1 -g 1 . Consequently, they have the same essential spectrum, σ ess (L 0 [g 1 ]) = σ ess (∂ yy + 1 -g 1 ) = σ(∂ yy + 1 -g 1 ) = (-∞, 1 -g 1 ].

This implies that for any g 1 > 1 the operator L 0 [g 1 ] is Fredholm with index 0, so that its invertibility is equivalent to the property that its kernel is trivial.

We claim that if L 0 [g * 1 ] has a nontrivial kernel for some g * 1 > 1, then L 0 [g 1 ] is invertible for any g 1 = g * 1 + γ = g * 1 with sufficiently small γ. Indeed, consider an orthogonal basis {ξ * 1 , . . . , ξ * n } of the finite dimensional kernel of L 0 [g * 1 ], which is the spectral subspace associated with the eigenvalue 0, because 0 is an isolated eigenvalue and the operator is selfadjoint. For sufficiently small γ, the operator L 0 [g 1 ] has at most n eigenvalues close to 0, which are the continuation of the eigenvalue 0 of L 0 [g * 1 ], and the spectral subspace associated to these eigenvalues has a basis {ξ 1 (γ), . . . , ξ n (γ)} which is the smooth continuation of the basis above. These eigenvalues of L 0 [g 1 ] are the eigenvalues of the n × n-matrix M [γ] representing the action of L 0 [g 1 ] on the basis {ξ 1 (γ), . . . , ξ n (γ)}. A direct computation of this matrix shows that

M [γ] = M 1 γ + O(γ 2 ), M 1 = Bξ * i , ξ * j 1 i,j n , where B = d dg 1 L 0 [g 1 ] g 1 =g * 1 = -( C * 2 + + C * 2 -).
The function C * 2 + + C * 2 -being continuous and positive with limits equal to 1 at x = ±∞, it is bounded from below by a positive constant c * . This implies that B is a negative selfadjoint operator, so that the eigenvalues of M 1 are all negative. Consequently, 0 is not an eigenvalue of M [γ] for γ = 0 sufficiently small, which implies that L[g 1 ] is invertible, for g 1 close enough to g * 1 , g 1 = g * 1 , and proves the claim. As a consequence of this property, the set of values g 1 > 1 for which the operator L 0 [g 1 ] is not invertible is countable and has no accumulation point in (1, ∞). In addition, the function C * 2 + + C * 2 -being bounded from below by c * > 0, it is straightforward to check that the operator L 0 [g 1 ] is negative, and in particular invertible, for any g 1 > 1/c * . We conclude that the set of values g 1 > 1 for which L 0 [g 1 ] is not invertible is at most a sequence converging to 1, which completes the proof of the lemma.

In these formulas, V is a real-valued solution of the boundary value problem

(D 2 -k 2 c ) 3 V + µ 2 c k 2 c V = 0, V = DV = (D 2 -k 2 c ) 2 V = 0 in z = 0, V = D 2 V = D 4 V = 0 in z = 1,
A 51 (Θ) = 2µ 3 c (D 2 -4k 2 c Θ) 2 V 1 , R 1 , B 51 (Θ) = 4µ 3 c Θ ( V 1 , R 2 + V 2 , R 1 ) , C 51 (Θ) = - 2µ c Θ k 2

Figure 1 . 1 :

 11 Figure 1.1: Projection in the (x, y)-horizontal plane of a (a) two-dimensional roll (periodic in y and constant in x); (b) rotated roll; (c) symmetric domain wall.

Figure 4

 4

Figure 4 . 1 :

 41 Figure 4.1:In the (Θ, P)-plane, with Θ = sin 2 α, Maple plot of the curve along which g 3 = 4 + √ 13, for Θ ∈ (0, 1). The inequality g 3 < 4 + √ 13 holds in the shaded region, whereas g 3 > 1.3 and g 1 > 1.3, for any positive Prandtl number P and any angle α ∈ (0, π/2). Domain walls are constructed in the shaded region situated to the left of the vertical line Θ = sin 2 (π/3) = 0.75, except for the values on the vertical line Θ = sin 2 (π/6) = 0.25 which correspond to the resonant case k c /k x = 2, and perhaps a finite number of curves corresponding to the finite number of (unknown) values g 1 excluded by Theorem 3.

φD 3 V 1 2 1 2

 311 is the unique solution of the boundary value problem(D 2 -k 2 c )φ = V, φ = 0 in z = 0, 1,andD 3 V = Ωper (z) dy dz.After very long computations we obtain thatg 1 = a 3 a 1 = b 51 ( 1 2 (1 + sin α)) + b 51 ( 1 2 (1 -sin α)) + b 51(0) b 51 (1) + b 51 (0) , (A.1) g 3 = b 5 b 3 = b 51 (sin 2 α) + b 51 (cos 2 α) + b 51 (0) b 51 (1) + b 51 (0) , (A.2) in which b 51 (Θ) = A 51 (Θ) + B 51 (Θ)P -1 + C 51 (Θ)P -2 , with

This property of the O(ε 1/2 )-terms is less precise than the one from [5, Section 6.3] but it is enough for our purposes. It is used when applying the implicit function theorem in the proof of Theorem 3. We point out that the O(ε 1/2 )-terms which are only continuous in 1/2 could be excluded by considering a normal form to order 5, the remaining terms being then continuously differentiable in (C0, C±, 1/2 ).

Acknowledgments: MH was partially supported by the EUR EIPHI program (Contract No. ANR-17-EURE-0002) and the ISITE-BFC project (Contract No. ANR-15-IDEX-0003).

A Coefficients of the cubic normal form

The formulas for the coefficients b 3 and b 5 found in [START_REF] Haragus | Bifurcation of symmetric domain walls for the Bénard-Rayleigh convection problem[END_REF] remain the same, and we compute in the same way the coefficients a 1 and a 3 . We obtain

where ζ 0 and ζ ± are the eigenvectors of L µc from Section 2.3, Ψ * 0 and Ψ * + are eigenvectors of the adjoint operator L * µc associated to the eigenvalues -ik c and -ik x , respectively, and the vectors


Jamie Wither

Florence Bertails

Marie-Paule Cani

Realistic Hair from a Sketch

This paper explores a sketch-based interface for quickly yet accurately creating visually realistic hair for virtual characters. Recently, physically-based models have proved successful for generating a wide variety of hair types, but they do not provide a straightforward method for designing target hairstyles. The contribution of this paper is to propose a user-friendly method for controlling such a physically-based model, requiring no specific knowledge of mechanics or hair styling: the user sketches example hair strands over a side view of the character's head, or alternatively annotates a picture of real hair viewed from the side serving as a reference. We show how the sketch can be used to infer the geometric and mechanical properties of the hair strands, to adjust the shape of the scalp, and to generate an adequate hair volume. Our method is validated on a wide variety of hair styles, from straight to curly and short to long hair.

Introduction

With the ability of graphical engines to display more and more complex scenes, the creation of visually plausible digital content has become a major problem: asking designers to manually shape each element of a scene is labour intensive, while automatic generation methods can restrict the variety of generated shapes and only offer indirect control. With these methods, the user has to set high level parameters from which the global shape emerges, often a trial and error approach if a specific design is to be reached. This is particularly true in the case of hair generation, on which this paper focuses.

Hair modeling has become an important problem due to the number of digital characters needed in many applications of Computer Graphics, from 3D feature films to video games. The increasing requirement for realism means that the use of simple surface models which was acceptable in the early years is no longer adequate: 3D hair made of several thousand individual strands has to be rendered, even when no hair animation will be computed. Instancing all these strands using standard modeling systems is tedious. Moreover, the results may lack realism: the observed shape of a head of hair results from a physical phenomenon, namely the interaction of thousands of elastic hair fibers, subject to gravity and tending to recover their natural curliness. Achieving the same effect manually for arbitrary hair types is extremely difficult.

This paper proposes a practical solution for quickly designing a variety of natural hair styles: we achieve realism by relying on an existing physically-based engine for hair generation, but set up a completely novel interface for it: the user controls the design by sketching the shape of the scalp and a few sample strands over a fixed view of the head, possibly using a picture of real hair as a guide. The ability to sketch what he wants provides him with direct control over the result. This paper shows how the various elements of the sketch are used to infer the individual geometric and mechanical parameters of the generated strands. Our results demonstrate that this method can be used successfully for quickly generating a large variety of hair from different ethnic origins, which resemble the sketches while being visually plausible.

Previous work

Due to the number of individual strands needed for creating a full head of hair, all the methods available so far model hair by positioning a few hundred guide strands, from which extra strands are generated at the rendering stage, using either interpolation, wisp-based models or a combination of both [START_REF] Bertails | Super-helices for predicting the dynamics of natural hair[END_REF]. Both geometric and physically-based methods have been used in the past for shaping guide strands.

A number of dedicated, interactive modeling systems were proposed for hair design [START_REF] Chen | A system of 3d hairstyle synthesis based on the wisp model[END_REF][START_REF] Kim | A thin shell volume for modeling human hair[END_REF][START_REF] Xu | V-hairstudio: an interactive tool for hair design[END_REF]. Most of them provide the user with precise control of the length, position and curliness of hair, but require a large number of successive manipulations, from the delimitation of the scalp to the positioning and shaping of guide strands. This can lead to several hours for the creation of a single head of hair. This pro-cess can be made easier using multi-resolution editing [START_REF] Kim | Interactive multiresolution hair modeling and editing[END_REF].

Hair is shaped from coarse to fine using a hierarchy of hair wisps, and by copy-pasting some sub-wisp's style to others wisps. Skilled users can achieve visually realistic results but still requiring more than an hour for each head of hair.

An alternative to manually creating hair geometry is to reconstruct it from images [START_REF] Paris | Capture of hair geometry from multiple images[END_REF][START_REF] Wei | Modeling hair from multiple views[END_REF], an approach which achieves unsurpassed realism. However, using it to generate the desired hair for a CG character requires having a real life model with exactly the required style, in addition to the possible problems of adjusting the captured hair to a head of different morphology. In this work, we borrow the idea of re-using some data (such as hair color and examples of strand shapes) from a real photograph, but just use it as a guide and generate hair from scratch onto the desired 3D head.

Physically-based hair styling [START_REF] Anjyo | A simple method for extracting the natural beauty of hair[END_REF][START_REF] Hadap | Interactive hair styler based on fluid flow[END_REF][START_REF] Yu | Modeling realistic virtual hairstyles[END_REF][START_REF] Choe | A statistical wisp model and pseudophysical approaches for interactive hairstyle generation[END_REF] was introduced as a good alternative to purely geometric hair modeling, since it reduces the amount of work required by the user while enhancing realism. Recently, Bertails et al. [START_REF] Bertails | Predicting natural hair shapes by solving the statics of flexible rods[END_REF] presented a validated static model for hair and used it to generate a number of natural hair styles through the tuning of a few mechanical parameters. Such parameters can be tedious to set up by hand when all the strands do not have the same length, curliness or stiffness. To ease the generation of various hair styles, the authors demonstrated the ability of their model to reproduce a classical hair styling process, from growing hair to wetting, cutting and drying it. Ward and Lin [START_REF] Ward | Interactive virtual hair salon[END_REF] took the same idea even further, they plugged a haptic interface into their physically-based engine for hair [START_REF] Ward | Modeling hair influenced by water and styling products[END_REF], enabling the user to feel hair while combing and styling it.

Here our goal is different: we do not aim to reproduce the process skilled hair-stylists have to go through in the real world, instead we want to provide CG artists with a straightforward method to control the generation of realistic hair. Therefore, we propose a sketch-based interface in which the user roughly sketches the desired result, and from this sketch we infer parameters which drive a physicallybased hair generator (we are currently using the one in [START_REF] Bertails | Predicting natural hair shapes by solving the statics of flexible rods[END_REF]).

Sketching systems have drawn increasing attention in the past few years. Seminal works have demonstrated their usefulness for quickly modeling and editing free-form shapes [START_REF] Igarashi | Teddy: a sketching interface for 3d freeform design[END_REF][START_REF] Alexe | Shape modeling by sketching using convolution surfaces[END_REF][START_REF] Schmidt | Shapeshop: Sketch-based solid modeling with blobtrees[END_REF][START_REF] Nealen | A sketch-based interface for detail-preserving mesh editing[END_REF][START_REF] Karpenko | SmoothSketch: 3D freeform shapes from complex sketches[END_REF]. Sketching was also used in specific applications, where a priori knowledge ofthe object being sketched helps in making inferences about complex 3D shapes [START_REF] Ijiri | Floral diagrams and inflorescences: interactive flower modeling using botanical structural constraints[END_REF][START_REF] Fabricio Anastacio | Modeling plant structures using concept sketches[END_REF][START_REF] Turquin | A sketch-based interface for clothing virtual characters[END_REF]. Such specific sketching approaches have been used previously for modeling geometric hairstyles, specifically Mao et al. [START_REF] Mao | Interactive hairstyle modeling using a sketching interface[END_REF][START_REF] Mao | Sketchy hairstyles[END_REF] and Malik [START_REF] Malik | A sketching interface for modeling and editing hairstyles[END_REF].

Mao et al. [START_REF] Mao | Interactive hairstyle modeling using a sketching interface[END_REF] present a system for creating geometric models of cartoon character hairstyles. The user first sketches the scalp boundary through a series of strokes directly onto a 3D model of the head from user chosen view-points, he then draws one stroke specifying the silhouette of the hairstyle viewed face on. This stroke is used to infer hair volume and global shape. In [START_REF] Mao | Sketchy hairstyles[END_REF] this work is extended to allow greater local control. Global shape is now controlled by specifying four silhouette strokes and a hair partition line. Hair clusters are created which conform to this global shape. Individual clusters can then be reshaped by sketching strokes onto either a front or side view of the head if desired.

Malik [START_REF] Malik | A sketching interface for modeling and editing hairstyles[END_REF] presents a comprehensive suite of sketching tools for creating and editing virtual hairstyles. The approach emulates the real-world hairstyling process by providing operations such as cutting, combing, curling, frizzing and twisting -controlled by gestures sketched onto arbitrary views of a 3D head model. A tablet is required as pen pressure is used to determine the scope of many operations.

In both of these previous works the ultimate goal is to create a geometric model for a head of hair which in some way corresponds to the set of sketched inputs. Our goal is different. Our ultimate goal is to create a set of parameters which control a physical model, which would in turn generate a geometric hair model corresponding to the set of sketched inputs.

Although our goal is different, we share the desire to make the whole process easy to use. We also use the idea of generating hair from a few strokes drawn from a fixed view of a head. However, we ask the user to draw some sample guide hairs rather than only a silhouette in order to allow more variety in the resulting hair styles, and we use the sketch to infer some mechanical parameters rather than to create geometry directly.

We don't currently offer as comprehensive a range of manipulation tools as Malik [START_REF] Malik | A sketching interface for modeling and editing hairstyles[END_REF]. For example we don't currently support the concept of hairpins and so can't create pony-tails. However our approach doesn't preclude the development of such tools as future work. By constraining our manipulations to only the parameters required by the physical model we are effectively setting the initial state for a head of hair which could later be used for animation.

Overview

This paper presents the first sketching interface for physically-based hair styling. To our knowledge, combining sketching and physically-based modeling has never been done in the past. Relying on a physically-based engine for designing hairstyles has clear advantages over geometric methods, such as the ability to quickly change hair properties afterwards (dry/wet hair, smooth/curly hair ...) as well as animating the resulting hair style later on, in a straightforward way. However, this combination raises a major difficulty: the user would expect to get a hair style very close to what is conveyed by his sketch, while the final shape given by the method will result from the convergence of a physically-based simulation. The main issue is thus to infer physically-based parameters from a sketch, while keeping this process completely hidden from the user. Our contributions for solving this issue are:

• A system for inferring the geometric and elastic parameters of individual hair fibers from just a 2D line sketching the final aspect of a sample hair strand.

• The generalization to the sketch-based generation of a full head of hair. Many guide strands are parameterised from a few drawn examples. The hair volume is inferred from the sketch of the hair silhouette, which can also be used to refine the cutting. The shape of the scalp is inferred from the sketch.

• A user friendly interface in which the user can either sketch hair from scratch over a 3D head model (as done in previous work [START_REF] Malik | A sketching interface for modeling and editing hairstyles[END_REF][START_REF] Mao | Sketchy hairstyles[END_REF]) or over a photo of real hair.

In the latter case, the photo is used as a guide: the user can trace the main wisps of hair, but may easily deviate from the photo if he wants to. The photo can also serve as a reference for hair color. The inferred hair is created on a 3D head, and an image of the result can be compared to the original photo for validation.

Hair strand from a sketch

In this section we outline a system for inferring 3D, physically-based strands from 2D sketches of hair strands drawn over a 2D side view of the head model.

In the case of hair, considering the strand the user draws as a target shape to be exactly fitted by a physically-based model -as in standard inverse engineering problems -would not be appropriate: due to the large number of hair strands, our system will need to generate a large number of plausible 3D strands from only a few sketched ones. Therefore, the strands the user sketches are rather interpreted as examples, used to infer the high level, local properties in terms of length, curliness and final shape under gravity the user wants. In practice, the system will interpolate these parameters to get the appropriate strand parameters everywhere on the scalp, and then generate physically-based strands, which will have the same overall visual aspect, but not fit exactly with any of the sketched strokes.

Our work relies on the physically-based system presented Bertails et al. [START_REF] Bertails | Predicting natural hair shapes by solving the statics of flexible rods[END_REF]. It provides a set of strand parameters: length l, natural curvature κ 0 (a constant value along the strand, representing the way it would curl without gravity), ellipticity e and stiffness1 k. The ellipticity stands for the shape of the strand's cross-section, which, as demonstrated in [START_REF] Bertails | Predicting natural hair shapes by solving the statics of flexible rods[END_REF] (denoted "eccentricity" here), affects the distribution of curls along a strand hanging under gravity: with elongated cross-sections (none zero ellipticity), curls tend to be evenly distributed as in African hair, while the strand tends to be straight at the top and curly at the bottom when the cross-section is circular (zero ellipticity). The last parameter, stiffness, controls how strongly the hair fiber tends to recover its natural curliness, and thus how much curliness balances the effect of gravity. Although this parameter value can be measured on natural hair, curls can be made stiffer using styling products, so we need to infer stiffness from the sketch for allowing the design of fancy hair styles.

As shown in Bertails et al. and depicted in Figure 2, hair strands under gravity tend to take helical shapes at rest, where the helical parameters vary along the strand. This gives us the main clue we are using for inferring the strand's parameters from a sketched 2D strand: we first detect the inflection points along the 2D stroke, and use them to cut the stroke into sections representing a half turn of a helix; we assume each section is modelled by a half helix of constant parameters, infer the arc length of such a helix, and use the sum of the inferred lengths to infer the total length of the hair strand in 3D; we use the inverse of the maximum radius of the helical segments to estimate the natural curvature κ 0 . We infer the ellipticity parameter from the distribution of inflection points along the length of the strand. We get the stiffness parameter by matching the span of the strand the user has drawn to the span of a physically modeled strand given the length and curvature values already determined. If the span cannot be matched by adjusting stiffness, as a final step we can adjust the mass per unit volume of the hair to find a better span match. The remainder of this section details each of these steps.

Cutting a 2D stroke into half helical segments

We wish to divide the stroke into segments representing one half turn of a helix.

We make the assumption that the user will draw a stroke along a roughly straight centre axis. Given this assumption we can apply principal component analysis to the positions of the stroke samples to determine the direction of this principal axis and the orthogonal secondary axis. By translating our points to this new set of axes we determine the points of inflection along the stroke by looking for a change in sign in the first derivative along the secondary axis.

We now identify separate half helical segments as the bounding boxes aligned to the principal axis and covering the regions between successive zero crossings of the principal axis. The width of each bounding box is defined by the position of the inflection point. The ends of the stroke (outside these bounding boxes) could be assumed to be straight and their length measured in 2D. In practice we include the first and last samples of the stroke as inflection points when performing the calculations.

We could remove the requirement that the user's stroke be along a roughly straight line by instead analyzing the 2D geometric curvature of the drawn stroke. The points of max-imum curvature would correspond to the inflection points of the analysis above. The principal axis for each helical section could be defined as the direction between successive points where the curvature value changes sign. However in practice we found the first approach gave reasonable results.

Fitting a half helix to each segment

This step is, again, purely geometric and does not require any optimization process. We wish to infer the physical length and curvature of the helix modeled by the half helical segment identified in the previous section.

The equation for a circular helix can be expressed parametrically in Cartesian coordinates as:

x = r cos(t) y = r sin(t) z = ct for t ∈ [0, 2π
), where r is the radius of the helix and 2πc is the vertical distance between consecutive loops (known as the "step" ∆ [3] ). The arc length of the helix is given by s = ( √ r 2 + c 2 )t. Thus the arc length of one complete turn of the helix is given by s when t = 2π, and a half turn is given by t = π. Therefore the physical length of the half helical segment can be estimated if we measure r and c.

As shown in Figure 3a the parameters r and c can be easily measured on an orthographic 2D projection of a helix when viewed from a direction perpendicular to its main axis. For each half helical segment we measure the extent of the bounding box along the principal axis to give πc and the extent of the box along the secondary axis to give r.

By taking the sum of the arc lengths for each half helical segment we have an estimate for the actual length of the hair strand. We estimate the natural curvature κ 0 of the hair strand as being 1/max(r) measured from the set of all segments.

Identifying straight strands

As the radius of a helix decreases, the projected image of the helix approaches the appearance of a straight line. Also -if the user draws a very straight stroke then many inflection points will be detected due to freehand sketching as the stroke will closely follow the major axis. These inflection points will have very little variation along the secondary axis and thus create narrow segments which imply high curvature. To discriminate between these cases and thus correctly detect straight strokes we apply the following tests.

1. Sum of squared errors (SSE). If the SSE of the stroke samples with respect to the secondary axis is below a small threshold -we assume the line is close to parallel to the axis and so this is a straight line. Set the curvature to zero.

2. Ratio of mean segment length to segment width. We measure the mean segment length and widths. If the ratio of length to width is above a threshold (we use 20) then we assume we have detected few narrow segments which implies a straight hair strand and we set the curvature to zero.

Inferring ellipticity, stiffness and mass per unit volume

We estimate ellipticity from the distribution of all the inflection points measured along the strand. We take the median point from the set of inflection points and measure it's displacement along the major axis. If it is positioned towards the end of the strand then we assume the curls form at the end of the strand which implies a low ellipticity. If it is positioned before or around the middle of the segment we assume evenly distributed curls which implies a high ellipticity. The range of eccentricies observed for real hair is 0.0 (European) to around 0.2 (African), so we chose to use a linear scale for ellipticity clamped in a similar range [0,0.3] as the displacement of the median inflection points varies from 50% to 70% of the strand extent.

Stiffness and mass per unit volume are the only parameters for which we need to run an optimization process. The span of a strand of hair is the distance between the root and the tip. Assuming we have made close to correct estimates for the length and curliness of the strand then matching the span of the example to the span of the model by varying the stiffness will give a good visual correspondence for realistic example strokes. This matching allows the user to set much higher values of stiffness than would be found in natural hair. We use a routine that models the hair using a range of stiffness values and chooses the value that minimises the difference in span between model and example. Values of stiffness far from natural are penalised using a simple linear weighting scheme that ensures that when a range of stiffness values produce similar spans the closest to a natural value is chosen.

Should the stiffness determination routine not find a good span match -then we assume the user has drawn an unrealistically large radius of curvature. Natural hair would be too heavy to hold the curls drawn for any reasonable value of stiffness. In this case we use a similar fitting routine but this time alter the mass per unit volume to make the hair lighter and more able to hold the curl (Figure 4g).

Figure 4 shows various examples of sketched hair strands.

Note that our method focuses on realistic hairstyles, and thus only allows for the creation of natural curls, which mostly follow helical shapes in the real world. The handling of unnatural hair shapes such as waves lying in a plane for example, obtained by using shaping tools like hair irons is beyond the scope of this paper.

Full head of hair

This section generalizes the sketch-based generation technique we have just described for hair strands to the case of a full head of hair.

Overview of the user interaction

To keep the whole process as simple as possible and in contrast to previous work, we restrict all stroke input to a side view of the head. Such a restriction removes the need for the user to position the viewpoint, while still allowing the user to draw strokes in all important regions of the head (fringe, side, back).

Throughout the process two viewports are provided. One is a fixed side view input area where strokes are entered. The other is a result view where the camera position can be freely altered by the user. The whole modeling process consists of three steps.

1. Define the scalp area 2. Provide example strands and optional volume stroke 3. Generate the full head of hair and view the result First, the scalp is defined by drawing one stroke delimiting the scalp extent on one side of the head (step one above). The other side is deduced by symmetry. The user can redraw this stroke until happy with the scalp shape. At this point the scalp shape is fixed for the rest of the process and the user progresses to the second step. The user then draws example strands anywhere within the defined scalp area (step two above). These examples can be replaced or deleted. Each time an example stroke is drawn a corresponding physically modelled strand is updated in the corresponding area of the result viewport. The update is immediate (roughly a tenth of a second).

By selecting the volume stroke mode the user can also draw an optional volume stroke. This stroke determines the global volume of the style and can be redrawn at any point.

The user can request an update of the full head of hair using a keypress at any time (step three above). At this point all the guide hairstrands in the result view are updated using information from all the input strokes and the volume stroke (this takes a few seconds depending on the number of guide strands, roughly ten seconds2 for the 40 guide strands in Fig 6). The user can continue to add, adjust or remove guide strands or the volume stroke once this has been done. The whole process is thus iterative, with the user moving back and forth between steps two and three until he is happy with the result.

The rest of this section describes each step of the whole process in more detail.

Defining the scalp

In contrast with [START_REF] Bertails | Predicting natural hair shapes by solving the statics of flexible rods[END_REF], where the scalp region was predefined as a set of full triangles of the head mesh, our sketching system provides the user with an easy way to shape the scalp, which is delimited by an arbitrary curve lying on the mesh. This approach is similar to [START_REF] Mao | Interactive hairstyle modeling using a sketching interface[END_REF] except we usually restrict the curve to be drawn from the side view.

The 3D scalp is inferred using the following steps: 1. The stroke is first projected on the 3D head mesh, following the view direction. We duplicate it using symmetry to get a closed 3D curve which delimitates the scalp.

2. We use the orientation of this curve, given by the direction of the user's gesture, to characterize the scalp, i.e. the closed region of the 3D head model delimited by the contour.

3. Finally, we generate two separate lists of triangles from the head mesh: the ones which are entirely within the scalp and the ones intersected by the contour line.

More precisely, let Γ Γ Γ 3D (s) be the closed and oriented scalp contour projected on the head mesh, defined as the ordered set of sample points {P k } k∈ [1..N] (the projections on the mesh of the 2D stroke points and their mirror image on the other side of the head).

The mesh triangle T k to which a projected point {P k } belongs is computed on the fly. We define T Γ Γ Γ as the list of triangles that intersect the scalp contour line, built by adding to {T k } k∈ [1..N] the set of triangles that intersect the hairline without containing any of the {P k }. This is performed through a search of neighbouring triangles along the closed hairline: finding intersecting triangles between two consecutive points P k and P k+1 is achieved by projecting this segment onto T k and finding the neighbouring mesh triangle in the direction given by the projected, oriented segment.

Then, the set T int scal p of triangles lying entirely within the scalp region is computed using the contour curve's orientation and a propagation mechanism towards the center of the scalp: we compute an oriented vector {b k } k∈ [1..N] lying on each T k on the contour as the cross product between the normal to the triangle and of an oriented tangent direction t k = P k+1 -P k P k+1 -P k . This vector points towards the center of the scalp. We use it to propagate the property of belonging to the scalp to the inward triangles, and stopping each time the border is reached again:

if T ∈ T Γ Γ Γ search for T ′ = neighbour(T ) along b k propagate to T ′ else    if(T )belongs to T int scal p stop else, add(T )to T int scal p
propagate to all the neighbours of T.

Finally, the set of scalp triangles T scal p is defined as the union of T int scal p and T Γ Γ Γ .

Clamping hair over the scalp

A regular triangulation of the scalp region will be needed to evenly clamp hair over the scalp. This new triangulation is computed using an algorithm inspired from Turk [START_REF] Turk | Re-tiling polygonal surfaces[END_REF]: a given number N of particles are spread over the scalp triangles and uniformly distributed using a repulsion mechanism. This 3D set of vertices we get after convergence is tessellated using a Delaunay tetrahedralisation, from which we keep only the surface triangles.

As the scalp region is bounded by an arbitrary curve, care must be taken when spreading the particles on the triangles belonging to T Γ Γ Γ : each time a particle crosses the contour curve of the scalp, it is projected back onto it. In order to generate a realistic looking head of hair the model requires at least twenty to thirty guide strands. However we do not want the user to have to supply an example strand for every guide strand. Therefore -having obtained the parameters for one or a few example strands sketched by the user -we need to extrapolate from this information in order to assign sensible values for all guide strands on the head.

Distributing hair parameters over the scalp

We don't want to constrain the user more than necessary and so the minimum input requirement is just one example strand. We set no maximum constraint. Each example strand is required to start in the valid scalp zone and consist of a continuous stroke. An example strand can be replaced by redrawing the strand starting close to the root, or deleted by double clicking on its root. The user chooses when to update the result view using a keypress. We use the following scheme to extrapolate from the input:

1. One example strand -Assign parameters inferred from this example to all guide strands in model 2. Two example strands -Project guide strand root positions onto the vertical plane bisecting the head. Then project these points onto the line joining the two example root points. Linearly interpolate between the two sets of example parameters at this point. A more complex interpolation scheme such as projecting onto a sphere and using spherical barycentric coordinates could be envisioned. However this simpler scheme provides visually convincing results, as illustrated in Figure 8.

Setting hair volume

To control the hair volume we use the multiple layer hulls model of [START_REF] Lee | Natural hairstyle modeling and animation[END_REF], also used in [START_REF] Bertails | Predicting natural hair shapes by solving the statics of flexible rods[END_REF], which models the hair volume due to self interactions while avoiding the computations of collision detection and response between wisps of hair. In this model hair strands with roots higher up the head are tested for collisions against larger offsets of the head model. The controlling factor is the hair volume scaling factor. Larger values generate larger volumes of hair.

When the user enters a volume stroke we project the stroke onto the vertical plane bisecting the model of the head. This projected stroke is then interpreted in two ways. The first way is to determine the hair volume scaling factor. The second way is to determine which hairs to cut.

To determine the hair volume from the projected volume stroke we consider only points above the lowest point of the scalp model. For each of these points we calculate the distance from the nearest point of the head model (using a pre-calculated distance field of the head). We take the largest of these distances as the maximum offset of the hulls model and calculate the hair volume scaling factor which will produce this maximum offset.

Cutting the hair

To determine which hairs to cut we form line segments from the projected volume stroke samples according to the order in which they were drawn and flip the line segment normals so that they are all on the 'interior' side of the line. This is done via a simple voting system where for each segment we take the dot product of the segment normal with the vector from the centre of the volume stroke bounding box to the mid-point of the segment. If the dot product is positive then the normal is pointing away from the interior and the segment votes to flip all of the segment normals. If the ma- We then test the orientation of these normals to determine the action of this section of the stroke. If the normal is pointing roughly upwards (in a direction within 90 • of the positive y-axis) then we wish to use this section to cut the hair. We form a plane by projecting the points along the xaxis and testing the modeled wisps for intersection with this plane. Any intersecting hairs are cut back to their length at the intersection point.

We also provide separate cut stroke functionality similar to that of Malik [START_REF] Malik | A sketching interface for modeling and editing hairstyles[END_REF]. The user selects a cut stroke mode and draws strokes which are projected onto the hair model. Guide strands which intersect a cut stroke are cut back to that length.

Pushing back hair from the face

For long hair styles without a short fringe we need a method to ensure hair does not fall in front of the face. To address this we add an optional spherical force field tool in front of the face that the user can see, move and resize. If enabled this spherical force field is accounted for in the body colli-sions routine. Ideally this spherical tool should be inferred from the sketch. This will be addressed in future work.

Such force fields could be used to create a 'comb' tool similar to Malik [15], allowing the user to influence the position of individual guide strands in the resulting model.

Annotation of photographs

As we emphasized in the introduction, the sketching system we just described is much easier to use for a designer than tuning indirect physically-based parameters, using hair-dresser tools, or shaping the hair by hand. However users with little sketching skill may like to use a real image as a guide. This can be useful if we want to quickly create a hairstyle inspired from a photograph. The user can reuse some aspects of the photo and modify others. The hair colour can be taken from the photo. It also enables visual validation of the resulting model.

When using a photo we must address the problem of the correspondance between the photo and the digital head. For average human heads, simply positioning and scaling the photo with the mouse is often adequate. This is the approach we have taken here. However more complex image registration techniques would be required for non-human head models. Figures 1 and9 show various hairstyles generated from the annotation of photographs. As demonstrated in our results, the method allows for the quick creation of many different hairstyles involving various hair types (smooth, curly), only from the sketch of a few strokes. Note that Figure 1 depicts the importance of the hairline shape on the final hairstyle. The punk hairstyle in Figure 9 is an example which is hard to model using our constraints -obviously some form of stiffening product has been used for the top of the hair. However by setting a large volume offset using the volume stroke we can approximate it fairly well. A future improvement would be to allow the hull volume to vary according to the stroke drawn so that such volume discontinuities could be modeled, instead of picking just one offset value for the whole head. Again, the last hairstyle above shows an unnatural style, as the woman has had strong curls put in. However, the automatic fitting does a good job of matching the stiffness value and produces similar looking curls.

Conclusion

This paper presented the first sketching system for hair that targets realistic hair models. Various hairstyles from arbitrary ethnic origins can be created in a few minutes each without specialized user knowledge, either by over sketching on a view of the targeted 3D model or by annotating a photo, used as a guide. To reach this goal, we infer from the user's sketch the parameters of a physically-based model for hair. The latter can be seen as an easy way to incorporate the a priori knowledge of hair we have.

Although designed for realism, our system can also achieve fancy hair styles, since any mesh could be used as an input for the head and since quite artificial stiffness and volume values can be set up.

As future work, handling hair styles with some partings and constraints (ponytails, braids, etc.) would be very useful to achieve the generation of more fancy hairstyles. We also plan to allow for locally varying clamping directions as currently, hair root orientation is taken as being the surface normal vector at the root position, whereas in reality these directions don't vary so uniformly: they can be directly visible and affect the resulting hair shape. They could be specified, together with the possible parting, using an extra sketch over a front view of the head. Currently some of the physically-based strands we produce may end up crossing vertical sections of the desired silhouette line. This could be avoided by artificially reducing their stiffness if they do so. Regarding the interface, having to sketch several lines of different nature (i.e. the scalp line and the volume line in addition to sample strands) provides good control of the result, but may be distracting for skilled designers. An alternative would be to adjust generic version of these lines according the location and length of the sample strands, a process that could be made completely transparent to the user. We have however to evaluate whether too many samples would be needed in this case. Finally we would like to perform a user evaluation of our system. The feedback supplied by artists who regularly have to parameterise hair models would be useful in improving our system.

In conclusion, we believe that the combination of sketching and annotation interfaces with procedural methods expressing a priori knowledge (such as physically-based models) is a promising approach for allowing artists to quickly create realistic digital content, while providing adequate levels of user control.

Figure 1 .

 1 Figure 1. A quick process (10 min) for designing a hairstyle from a photograph, requiring only a few strokes from the user.

Figure 2 .

 2 Figure 2. A physically-based hair strand is controlled by 4 main parameters: length, natural curliness, ellipticity and stiffness. Several strands hanging under the effect of gravity are depicted. All have the same length and natural curliness, but different values for the ellipticity e and the stiffness k. x=1.6GPa

Figure 3 .

 3 Figure 3. a. The orthogonal projection of a circular helix, and the measurements which can be made on it. b. Inferring the length of a stroke using half helical segments.

Figure 4 .

 4 Figure 4. Single strands inferred from sketches: the sketch is interpreted as an example of the desired shape, our system generates similar, physically-based 3D strands. The unnaturally large strand (g) required automatic fitting of the mass per unit volume.

Figure 5 .

 5 Figure 5. Generation of the hair scalp from a sketched hairline. (a) Generation of the scalp triangles T scal p from the hairline. (b) Triangular tessellation of the scalp area. (c) Clamping hair on the scalp. (d) Growing hair.

Figure 6 .

 6 Figure 6. The input and resulting hairstyle from different viewpoints.

3 .

 3 Three or more example strands -Generate a Delaunay triangulation of the example root locations on the vertical plane bisecting the head. Interpolate between triangle vertices by projecting model strand root locations onto the Delaunay triangulation and determining the barycentric coordinates within the intersected triangle. For points outside the triangulation -project to the nearest edge of the triangulation.

3. 5

 5 Setting the hair volume and adapting the hair cut So far the user provides local parameters for the hair model by providing examples of individual strands. However the volume of the overall hairstyle is a useful global parameter we would also like to be able to provide in a simple manner. To allow this we introduce a second type of stroke -the volume stroke. With this stroke the user roughly indicates the outer boundary for the silhouette of the hair style. The part of the stroke above the scalp is used to determine a parameter controlling the volume of the style. Parts of the stroke below the scalp are used to trim back hairs which are longer than desired without having to redraw examples.

Figure 7 .

 7 Figure 7. The effect of increasing the size of the volume stroke. Note the hairs at the back of the head have been cut where they extend below the stroke.

Figure 8 .

 8 Figure 8. Styles from 1927, 1945, 1965 and 1971. Top: Drawings from [20].

Figure 9 .

 9 Figure 9. Results of annotating photographs.

To ease understanding, in contrast with[START_REF] Bertails | Predicting natural hair shapes by solving the statics of flexible rods[END_REF], we are considering that the natural twist is always zero; we use the term stiffness here for the sake of simplicity, but it stands for the Young modulus in Bertails et al.'s model.

Using a 2.8GHz Intel R Xeon R processor

Acknowledgments We thank Basile Audoly for his original code for computing the statics of a single hair fiber. We are also grateful to Steve Marschner who provided us with his code for calculating hair local illumination and to DH Kong for the use of his Flaming Hair image (Fig 9). Jamie Wither is supported by a grant from the European Community under the Marie-Curie project VISITOR.