Bernard Mourrain
email: bernard.mourrain@inria.fr

AND Raimundas Vidunas
email: rvidunas@gmail.com

Nelly Villamizar
email: nelly.villamizar@oeaw.ac.at

DIMENSION AND BASES FOR GEOMETRICALLY CONTINUOUS SPLINES ON SURFACES OF ARBITRARY TOPOLOGY

Keywords: geometrically continuous splines, dimension and bases of spline spaces, gluing data, polygonal patches, surfaces of arbitrary topology

We analyze the space of geometrically continuous piecewise polynomial functions, or splines, for rectangular and triangular patches with arbitrary topology and general rational transition maps. To define these spaces of G 1 spline functions, we introduce the concept of topological surface with gluing data attached to the edges shared by faces. The framework does not require manifold constructions and is general enough to allow non-orientable surfaces. We describe compatibility conditions on the transition maps so that the space of differentiable functions is ample and show that these conditions are necessary and sufficient to construct ample spline spaces. We determine the dimension of the space of G 1 spline functions which are of degree k on triangular pieces and of bi-degree (k, k) on rectangular pieces, for k big enough. A separability property on the edges is involved to obtain the dimension formula. An explicit construction of basis functions attached respectively to vertices, edges and faces is proposed; examples of bases of G 1 splines of small degree for topological surfaces with boundary and without boundary are detailed.

Introduction

The accurate and efficient representation of shapes is a major challenge in geometric modeling. To achieve high order accuracy in the representation of curves, surfaces or functions, piecewise polynomials models are usually employed. Parametric models with prescribed regularity properties are nowadays commonly used in Computer Aided Geometric Design (CAGD) to address these problems. They involve so-called spline functions, which are piecewise polynomial functions on intervals of R with continuity and differentiability constraints at some nodes. Extensions of these functions to higher dimension are usually done by taking tensor product spline basis functions. Curves, surfaces or volumes are represented as the image of parametric functions expressed in terms of spline basis functions. For instance, surface patches are described as the image of a piecewise polynomial (or rational) map from a rectangular domain of R 2 to R n . But to represent objects with complex topology, such maps on rectangular parameter domains are not sufficient. One solution which is commonly used in Computer-Aided Design (CAD) is to trim the B-spline rectangular patches and to "stitch" together the trimmed pieces to create the complete shape representation. This results in complex models, which are not simple to use and to modify, since structural rigidity conditions cannot easily be imposed along the trimming curve between two trimmed patches.

To allow flexibility in the representation of shapes with complex topology, another technique called geometric continuity has been studied. Rectangular parametric surface patches are glued along their common boundary, with continuity constraints on the tangent planes (or on higher osculating spaces). In this way, smooth surfaces can be generated from quadrilateral meshes by gluing several simple parametric surfaces, forming surfaces with the expected smoothness property along the edges.

This approach builds on the theory on differential manifolds, in works such as [START_REF] Derose | Geometric continuity: a parametrization independent measure of continuity for computer aided geometric design[END_REF], [START_REF] Hahn | Geometric continuous patch complexes[END_REF], [START_REF] Gregory | Geometric continuity[END_REF]. The idea of using transition maps or reparameterizations in connection with building smooth surfaces had been used for instance by DeRose [START_REF] Derose | Geometric continuity: a parametrization independent measure of continuity for computer aided geometric design[END_REF] in CAGD, who gave one of the first general definitions of splines based on fixing a parametrization.

Since these initial developments, several works focused on the construction of such G 1 surfaces [START_REF] Peters | Constructing C 1 surface of arbitrary topology using biquadratic and bicubic splines[END_REF], [START_REF] Loop | Smooth spline surfaces over irregular meshes[END_REF], [START_REF] Reif | Biquadratic G-spline surfaces[END_REF], [START_REF] Prautzsch | Freeform splines[END_REF], [START_REF] Catmull | Seminal graphics. chapter Recursively Generated B-spline Surfaces on Arbitrary Topological Meshes[END_REF], [START_REF] Ying | A simple manifold-based construction of surfaces of arbitrary smoothness[END_REF], [START_REF] Gu | Manifold splines[END_REF], [START_REF] He | Manifold t-spline[END_REF], [START_REF] Gu | Manifold splines with a single extraordinary point[END_REF], [START_REF] Vecchia | A construction of rational manifold surfaces of arbitrary topology and smoothness from triangular meshes[END_REF], [START_REF] Tosun | Manifold-based surfaces with boundaries[END_REF], [START_REF] Bonneau | Flexible G 1 interpolation of quad meshes[END_REF], . . . with polynomial, piecewise polynomial, rational or special functions and on their use in geometric modeling applications such as surface fitting or surface reconstruction [START_REF] Eck | Automatic reconstruction of b-spline surfaces of arbitrary topological type[END_REF], [START_REF] Shi | Reconstruction of convergent G 1 smooth B-spline surfaces[END_REF], [START_REF] Lin | Adaptive patch-based mesh fitting for reverse engineering[END_REF], . . . The problem of investigating the minimal degree of polynomial pieces has also been considered [START_REF] Peters | C 2 free-form surfaces of degree (3, 5)[END_REF]. Other research investigates the construction of adapted rational transition maps for a given topological structure [START_REF] Beccari | RAGS: Rational geometric splines for surfaces of arbitrary topology[END_REF]. We refer to [START_REF] Peters | Geometric continuity[END_REF] for a review of these constructions. Constraints that the transition maps must satisfy in order to define regular spline spaces have also been identified [START_REF] Peters | On the complexity of smooth spline surfaces from quad meshes[END_REF]. But it has not yet been proved that these constraints are sufficient for the constructions.

The use of G k spline functions to approximate functions over computational domains with arbitrary topology received recently a new attention for applications in isogeometric analysis. In this context, describing the space of functions, its dimension and adapted bases is of particular importance. A family of bi-cubic spline functions was recently introduced by Wu et al [START_REF] Wu | Spline Spaces over Quadrangle Meshes with Complex Topologies[END_REF] for isogeometric applications, where constant transition maps are used, which induce singular spline basis functions at extraordinary vertices. Multi-patch representations of computational domains are also used in [START_REF] Buchegger | Adaptively refined multi-patch B-splines with enhanced smoothness[END_REF], with constant transition maps at the shared edges of rectangular faces, using an identification of Locally Refined spline basis functions. In [START_REF] Kapl | Isogeometric analysis with geometrically continuous functions[END_REF], G k continuous splines are described and the G 1 condition is transformed into a linear system of relations between the control coefficients. The case of two rectangular patches, which share an edge is analyzed experimentally. In [START_REF] Bercovier | Smooth Bézier surfaces over arbitrary quadrilateral meshes[END_REF], the space of G 1 splines of bi-degree 4 for rectangular decompositions of planar domains is analyzed. Minimal Determining Sets of points are studied, providing dimension formulae and dual basis for G 1 spline functions over planar rectangular meshes with linear gluing transition maps.

Our objective is to analyze the space of G 1 spline functions for rectangular and triangular patches with arbitrary topology and general rational transition maps. We are interested in determining the dimension of the space of G 1 spline functions which are of degree k on triangular pieces and of bi-degree (k, k) on rectangular pieces. To define the space of G 1 spline functions, we introduce the concept of topological surface with gluing data attached to the edges shared by the faces. The framework does not require manifold constructions and is general enough to allow non-orientable surfaces. We describe compatibility conditions on the transition maps so that the space of differentiable functions is ample and show that these conditions are necessary and sufficient to construct ample spline spaces. A separability property is involved to obtain a dimension formula of the G 1 spline spaces of degree k on such topological surfaces, for k big enough. This leads to an explicit construction of basis functions attached respectively to vertices, edges and faces.

For the presentation of these results, we structure the paper as follows. The next section introduces the notion of topological surface M, differentiable functions on M and constraints on the transition maps to have an ample space of differentiable functions. Section 3 deals with the space of spline functions which are piecewise polynomial and differentiable on M. Section 4 analyzes the gluing conditions along an edge. Section 5 analyzes the gluing condition around a vertex. In Section 6, we give the dimension formula for the space of spline functions of degree k over a topological surface M and describe explicit basis constructions. Finally, in Section 7, we detail an example with boundary edges and another one with no boundary edges. We also provide an appendix with an algorithmic description of the basis construction.

Differentiable functions on a topological surface

Typically in CAGD, parametric patches are glued into surfaces by splines (i.e., polynomial maps) from polygons in R 2 . The simplest C r construction is with the polygons in R 2 situated next to each other, so that C r continuity across patch edges comes from C r continuity of the coordinate functions across the polygon edges. This is called parametric continuity. A more general construction to generate a C r surface from polygonal patches is called geometric continuity [START_REF] Derose | Geometric continuity: a parametrization independent measure of continuity for computer aided geometric design[END_REF], [START_REF] Peters | Geometric continuity[END_REF]. Inspired by differential geometry, attempts have been made [START_REF] Hahn | Geometric continuous patch complexes[END_REF], [START_REF] Vidunas | Aspects of algorithmic algebra: Differential equations and splines[END_REF], [START_REF] Vidunas | Geometrically continuous octahedron[END_REF] to define geometrically continuous G r surfaces from a collection of polygons in R 2 with additional data to glue their edges and differentiations. They are defined by parametrization maps from the polygons to R 3 satisfying geometric regularity conditions along edges.

It is easy to define a C 0 surface from a collection of polygons and homeomorphisms between their edges. Definition 2.1. Given a collection M 2 of (possibly coinciding) polygons σ i in R 2 , a topological surface M is defined by giving a set of homeomorphisms µ : τ i → τ j between pairs of polygonal edges τ i ⊂ σ i , τ j ⊂ σ j (σ i , σ j ∈ M 2 ). Each polygonal edge can be paired with at most one other edge, and it cannot be glued with itself.

A G 0 -continuous function on the topological surface M is defined by assigning a continuous function f i to each polygon σ i , such that the restrictions to the polygonal edges are compatible with the homeomorphisms µ.

The topological surface M is the disjoint union of the polygons, with some points identified to equivalence classes by the homeomorphisms µ. The polygons are also called the faces of M and their set is denoted M 2 . Each homeomorphism µ identifies the edges τ i , τ j of the polygons σ i , σ j to an interior edge of M. We say that the edge is shared by the faces σ i and σ j . An edge not involved in any homeomorphism µ is a boundary edge of M. The edges of M are the equivalent classes of edges of the polygons of R 2 identified by the homeomorphisms µ. Their set is denoted M 1 . Similarly, let M 0 denote the set of M-vertices, that is, equivalence classes of polygonal vertices. An interior vertex is an equivalence class of polygonal vertices γ 0 , γ 1 , . . . , γ n = γ 0 such that the adjacent vertices γ i , γ i+1 are identified by an edge homeomorphism. The set of these equivalent classes of identified vertices of the polygons, or interior vertices of M, is denoted M • 0 . 2.1. Gluing data. The definition of a differential surface S typically requires an atlas of S, that is a collection {V p , ψ p } p∈J such that {V p } p∈J is an open covering of S [START_REF] Warner | Foundations of Differentiable Manifolds and Lie Groups[END_REF]. Each ψ p is a homeomorphism ψ p : U p → V p , where U p is an open set in R 2 . For distinct p, q ∈ J such that V p ∩ V q = ∅, let U p,q := ψ -1 p (V p ∩ V q ) and U q,p := ψ -1 q (V p ∩ V q ). Then the map ψ -1 q • ψ p : U p,q → U q,p is required to be a C 1 -diffeomorphism. The maps φ pq : ψ -1 q • ψ p are called transition maps. A differentiable function f on S is a function such that for any open set V p , the composition

f p = f • ψ -1 p : U p ⊂ R 2 → R is differentiable.
Our objective is to study the space of differentiable functions that can be constructed on a surface S associated to the topological surface M. Instead of an atlas of a differential surface S, we consider a topological surface M together with gluing data given by maps (that we call transition maps) between the pairs of faces of M that share an edge in M. We make this precise in the following definition. Definition 2.2. For a topological surface M, a gluing structure associated to M consists of the following:

• for each face σ ∈ M 2 an open set U σ of R 2 containing σ; • for each edge τ ∈ M 1 of a cell σ, an open set U τ,σ of R 2 containing τ ; • for each edge τ ∈ M 1 shared by two faces σ i , σ j ∈ M 2 , a C 1 -diffeomorphism called the transition map φ σ j ,σ i : U τ,σ i → U τ,σ j
between the open sets U τ,σ i and U τ,σ j , and also its correspondent inverse map φ σ i ,σ j ; • for each edge τ ∈ M 1 of a cell σ, the identity C 1 -diffeomorphism that defines the identity transition map φ σ,τ = Id between U σ and U τ,σ . A transition map as in Definition 2.2 differs from the usual notion of transition map in the context of differential manifolds (see [START_REF] Hahn | Geometric continuous patch complexes[END_REF]), since we do not require compatibility conditions at the vertices and across edges. The precise compatibility conditions that we need on these maps φ σ j ,σ i are given in Sections 2.3 ans 2.4.

σ 1 σ 2 τ 1 τ 2 γ 2 γ 1
Let τ = (τ 1 , τ 2 ) be an edge shared by two faces σ 1 , σ 2 ∈ M 2 and let γ = (γ 1 , γ 2 ) be a vertex of τ corresponding to γ 1 in σ 1 and to γ 2 in σ 2 , as in Figure 1. We denote by τ 1 (resp. τ 2 ) the second edge of σ 1 (resp. σ 2 ) through γ 1 (resp. γ 2 ) We associate to σ 1 and σ 2 two coordinate systems (u 1 , v 1 ) and (u 2 , v 2 ) such that γ 1 = (0, 0),

τ 1 = {(u 1 , 0), u 1 ∈ [0, 1]}, τ 1 = {(0, v 1 ), v 1 ∈ [0, 1]} and γ 2 = (0, 0), τ 2 = {(0, v 2 ), v 2 ∈ [0, 1]}, τ 2 = {(u 2 , 0), u 2 ∈ [0, 1]}. Using the Taylor expansion at (0, 0), a transition map from U τ,σ 1 to U τ,σ 2 is then of the form (1) φ σ 2 ,σ 1 : (u 1 , v 1 ) -→ (u 2 , v 2 ) = v 1 b τ,γ (u 1 ) + v 2 1 ρ 1 (u 1 , v 1 ) u 1 + v 1 a τ,γ (u 1 ) + v 2 1 ρ 2 (u 1 , v 1 ) where a τ,γ (u 1 ), b τ,γ (u 1 ), ρ 1 (u 1 , v 1 ), ρ 2 (u 1 , v 1 )
are C 1 functions. We will refer to it as the canonical form of the transition map φ σ 2 ,σ 1 at γ along τ . The functions [a τ,γ , b τ,γ ] are called the gluing data at γ along τ on σ 1 . Definition 2.3. An edge τ ∈ M which contains the vertex γ ∈ M is called a crossing edge at γ if a τ,γ (0) = 0 where [a τ , b τ ] is the gluing data at γ along τ . We define c τ (γ) = 1 if τ is a crossing edge at γ and c τ (γ) = 0 otherwise. By convention, c τ (γ) = 0 for a boundary edge. If γ ∈ M 0 is an interior vertex where all adjacent edges are crossing edges at γ, then it is called a crossing vertex. Similarly, we define c + (γ) = 1 if γ is a crossing vertex and c + (γ) = 0 otherwise. 2.2. Differentiable functions on a topological surface. We can now define the notion of differentiable function on M:

Definition 2.4. A differentiable function f on the topological surface M is a collection f = (f σ ) σ∈M of differentiable functions f σ : U σ → R such that ∀γ ∈ τ = σ 1 ∩ σ 2 , ∀u ∈ U τ,σ 1 , (2) J γ (f σ 1 )(u) = J γ (f σ 2 • φ σ 2 ,σ 1 )(u)
where J γ is the jet or Taylor expansion of order 1 at γ.

If f 1 , f 2 are the functions associated to the faces σ 1 , σ 2 ∈ M 2 which are glued along the edge τ with a transition map of the form (1), the regularity condition (2) leads to the following relations:

• f 1 (u 1 , 0) = f 2 • φ σ 2 ,σ 1 (u 1 , 0) for u 1 ∈ [0, 1]; that is (3) f 1 (u 1 , 0) = f 2 (0, u 1 ) • ∂f 1 ∂v 1 (u 1 , 0) = ∂(f 2 • φ) ∂v 1 (u 1 , 0) for φ = φ σ 2 ,σ 1 and u 1 ∈ [0, 1], which translates to (4) ∂f 1 ∂v 1 (u 1 , 0) = b τ,γ (u 1 ) ∂f 2 ∂u 2 (0, u 1 ) + a τ,γ (u 1 ) ∂f 2 ∂v 2 (0, u 1 ) for u 1 ∈ [0, 1], with a(u 1 ) = ∂φ 1 ∂v 1 (u 1 , 0), b(u 1 ) = ∂φ 2 ∂v 1 (u 1 , 0)
, where φ 1 and φ 2 are the components of φ at the first and the second variable respectively.

A convenient way to describe this regularity condition is to express the relation (4) as a relation between differentials acting on the space of differential functions on the edge τ :

(5)

a τ,γ (u 1 )∂ v 2 + b τ,γ (u 1 )∂ u 2 -∂ v 1 = 0
With this notation, at a crossing vertex γ with 4 edges we have b τ,γ (0)∂ u 2 -∂ v 1 = 0. The differentials along two opposite edges are "aligned", which explains the terminology of crossing vertex.

Definition 2.5. A subspace D of the vector space of differentiable functions on M is said to be ample if at every point γ of a face σ of M, the space of values and differentials at γ, namely f (γ),

∂ uσ (f )(γ), ∂ vσ f (γ) for f ∈ D, is of dimension 3.
This definition does not depend on the choice of the face σ to which γ belongs, since for γ on a shared edge, the value and differentials coincide after transformation by the invertible transition map.

2.3.

Compatibility condition at a vertex. Giving gluing data on the edges is not sufficient to ensure the existence of an ample space of differentiable functions on M. At vertices shared by several edges and faces, additional conditions on the transition maps need to be satisfied. We describe them in this section, and show that they are sufficient to construct an ample space of splines on M in the following sections.

For a vertex γ ∈ M • 0 , (see Fig. 2) which is common to faces σ 1 , . . . , σ F glued cyclically around γ, along the edges τ i = σ i+1 ∩ σ i for i = 1, . . . , F (with σ F +1 = σ 1 ), we impose the following condition:

(6) J γ (φ 1,F ) • • • • • J γ (φ 3,2 ) • J γ (φ 2,1 )(u, v) = (u, v),
where J γ is the jet or Taylor expansion of order 1 at γ. We can assume that for each

σ 4 τ 5 σ 5 τ 1 σ 1 τ 2 σ 2 τ 3 σ 3 τ 4 γ Figure 2
. The faces σ i for i = 1, . . . , 5 are glued cyclically around a vertex γ. i = 1, . . . , F , the edge τ i is defined (linearly) by v i = 0 in σ i . It is easy to check that the condition (6) on the Taylor expansion at γ leads to the following: Condition 2.6. If the vertex γ is on the faces σ 1 , . . . , σ F glued cyclically around γ, the gluing data [a i , b i ] at γ on the edges τ i between σ i-1 and σ i satisfies

(7) F i=1 0 1 b i (0) a i (0) = 1 0 0 1 .
This gives algebraic restrictions on the values a i (0), b i (0). At a crossing vertex γ (see Def. 2.3) of four incident edges, the equality (7) amounts to [START_REF] Eck | Automatic reconstruction of b-spline surfaces of arbitrary topological type[END_REF] b

1 (0)b 3 (0) = 1, b 2 (0)b 4 (0) = 1.
It turns out that Condition 2.6 is not sufficient around crossing vertices for ensuring an ample space of differentiable functions on M. An obstruction was noticed in [START_REF] Peters | On the complexity of smooth spline surfaces from quad meshes[END_REF] in a setting of rectangular patches. We write this constrain in a general setting:

Condition 2.7. If the vertex γ is a crossing vertex with 4 edges τ 1 , . . . , τ 4 , the gluing data [a i , b i ] i = 1 . . . 4 on these edges at γ satisfy

a 1 (0) + b 4 (0) b 4 (0) = -b 1 (0) a 3 (0) + b 2 (0) b 2 (0) , (9)
a 2 (0) + b 1 (0) b 1 (0) = -b 2 (0) a 4 (0) + b 3 (0) b 3 (0) . ( 10
)
Lemma 2.8. If the space of differentiable functions on M is ample and Condition 2.6 is satisfied, then the gluing data at every crossing vertex γ of 4 incident edges must also satisfy Condition 2.7.

Proof. The value and first derivatives at every point γ ∈ M of all differentiable functions on M should span a space of dimension 3.

If γ is a crossing vertex, then we have 4 restrictions on the Taylor expansions of a spline components (f 1 , f 2 , f 3 , f 4 ). Let us write the Taylor expansion of f i at γ = (0, 0) as f i = p i + q i u i + r i v i + s i u i v i + . . .. The gluing conditions imply the following. From (3), [START_REF] Gu | Manifold splines[END_REF] p 1 = p 2 = p 3 = p 4 , q 1 = r 2 , q 2 = r 3 , q 3 = r 4 and q 4 = r 1 this together with the Condition (4) on the first derivatives imply b 2 (0)q 1 -q 3 = 0, b 3 (0)q 2 -q 4 = 0.

When we consider the derivative of f i with respect to u i , again applying (4), we get the conditions

s 2 -b 2 (0)s 1 = b 2 (0)q 1 + a 2 (0)q 2 , s 3 -b 3 (0)s 2 = b 3 (0)q 2 + a 3 (0)q 3 , s 4 -b 4 (0)s 3 = b 4 (0)q 3 + a 4 (0)q 4 , s 1 -b 1 (0)s 4 = b 1 (0)q 4 + a 1 (0)q 1 .
By combining the last four equations respectively with the weights b 4 (0), b 1 (0)b 4 (0), b 1 (0), 1, together with Condition 2.6, we get

q 1 a 1 (0) + b 2 (0)b 4 (0) + q 3 b 1 (0) b 2 (0)a 3 (0) + b 2 (0) + q 2 b 1 (0)a 2 (0) + b 1 (0) + q 4 b 2 (0) a 4 (0) + b 1 (0)b 3 (0) = 0. ( 12
)
This relation does not involve the cross derivatives s 1 , s 2 , s 3 , s 4 , but gives an unwanted relation between the first order derivatives. After replacing [START_REF] Gu | Manifold splines[END_REF] and ( 8) in [START_REF] Hahn | Geometric continuous patch complexes[END_REF], we encounter conditions [START_REF] Gregory | Geometric continuity[END_REF] and [START_REF] Gu | Manifold splines with a single extraordinary point[END_REF]. Under these conditions, there is no relation between q 1 , q 2 , and there is one degree of freedom for (s 1 , s 2 , s 3 , s 4 ).

The restrictions ( 9) and ( 10) were noticed in [START_REF] Peters | On the complexity of smooth spline surfaces from quad meshes[END_REF] in the context of gluing tensor product rectangular patches with all b i (0) = -1. The restrictions are then simply

a 1 (0) = a 3 (0), a 2 (0) = a 4 (0).

Topological restrictions.

A guiding principle for the construction of geometric continuous functions is that G 1 properties are equivalent to C 1 properties in the plane after an adequate reparameterization of the problem. Gluing two faces along an edge is transformed locally via such reparameterization maps, into gluing two half-planes along a line. Each half-plane is in correspondence with the half-plane determined by one of the faces and the shared edge. A natural gluing is to have the half planes on each side of the line. In this case, the points of one face are mapped by the reparameterizations on one side of the line and the points of the other face on the other side of the line. This implies that the transition maps keep locally the points of a face on the same side of the edge and thus it should have a positive Jacobian at each point of the edge. Therefore the first topological restriction that we ask for each edge τ , using the canonical form (1), is the following: ∀u ∈ [0, 1], b τ (u) < 0. When the function b τ is positive on the edge; the transition map identifies interiors of the polygons. It corresponds to two patches of surfaces virtually pasted at a sharp edge (i.e., at angle 0) rather than in a proper continuously smooth manner (i.e., at the angle π). In some CAGD applications, it may be useful to model surfaces with sharp wing-like edges by the G 1 continuity restrictions with b τ > 0. But typical G 1 continuity applications should require b τ < 0 on the whole edge to prevent this degeneration. The regularity property across edges, considered irrespective of orientation, is called weak geometric continuity [7, §6.7] and the restriction we consider corresponds to coherently oriented parametrizations in [7, §6.8].

Similarly, gluing the faces around a vertex γ should be equivalent to gluing sectors around a point in the plane, via the reparameterization maps. Such sectors should form a fan around the parameter point, which can be identified with the local neighborhood of the vertex γ on the surface. Thus these sectors should not overlap. If this fan is defined by vectors u 1 , . . . , u F ∈ R 2 (u i+1 is supposed to be outside the union of the sectors defined by two consecutive vectors u j-1 , u j for 2 < j < i), we easily check that the coefficients a i (0), b i (0) of the transition map (1) across the edge τ i at γ are such that:

(13) u i-1 = a i (0)u i + b i (0) u i+1
or equivalently

[u i , u i-1 ] = 0 1 b i (0) a i (0) [u i+1 , u i ]
(see also the construction in the next section 2.5). If the sector angles are less than π (i.e. the sector u i , u i+1 coincides with the cone generated by u i , u i+1 ) the condition that the sectors form a fan and do not overlap translates as follows: the coefficients of the last row of

k i=j 0 1 b i (0) a i (0)
should not be both non-negative for 1 < j k < F .

A natural way to define transition maps at a vertex γ which satisfy this condition is to choose vectors in the plane that define a fan, as in Figure 2. Then the coefficients a i (0), b i (0) are uniquely determined from the relations [START_REF] He | Manifold t-spline[END_REF].

The topological constraints could be dropped in some applications, for example, when modeling analytical surfaces with branching points, or surfaces with sharp winglike interior edges, or with winding-up boundary. In these specific applications, the compatibility Condition 2.7 at crossing vertex might need to be extended, to allow winding up of 8, 12, etc., crossing edges, and take into account the sharp edges. Apart from this kind of consideration, the topological conditions do not essentially affect our algebraic dimension count.

The framework that we propose is more general than previous approaches used in Geometric Modeling to define G 1 splines (see e.g. [22, §3]) since it allows to define differentiable functions on topological surfaces such as a Möbius strip or a Klein bottle. Moreover, it does not rely on the construction of manifold surfaces and atlas, but only on compatible transition maps.

2.5.

Example. A simple way to define transition maps is to use a symmetric gluing as proposed in [12, §8.2] for rectangular patches. If τ = (γ 0 , γ 1 ) is the shared edge between σ 1 and σ 2 , the transition map can be of the form:

(14) φ(u, v) = -v u + 2v d 0 (u) cos 2π n 0 -d 1 (u) cos 2π n 1
where n 0 (resp. n 1 ) is the number of edges at the vertex γ 0 (resp. γ 1 ). Additionally, if γ 0 corresponds to u = 0 and γ 1 to u = 1, the functions a and b interpolate 0 and 1:

d 0 (0) = 1, d 0 (1) = 0, d 1 (0) = 0, d 1 (1) = 1
and their derivatives of order 1 should vanish at 0, 1. It corresponds to a symmetric gluing, where the angle of two consecutive edges at γ i is 2π n i . If d 0 (u) and d 1 (u) are polynomial functions, their degree must be at least 3. If d 0 (u) and d 1 (u) are rational functions with the same denominator, the maximal degree of the numerators and denominator must be at least 2. As we will see the dimension of the spline space decreases when the degree increases. Thus it is important to construct transition maps with low degree numerators and denominators. See e.g. [START_REF] Peters | Geometric continuity[END_REF][START_REF] Peters | On the complexity of smooth spline surfaces from quad meshes[END_REF] for low degree constructions, which depend on the structure of M.

A general construction of gluing data which satisfies the compatibility conditions is as follows.

(i) For all the vertices γ ∈ M 0 and for all the edges τ 1 , . . . , τ F of M 1 that contain γ, choose vectors u 1 , . . . , u F ∈ R 2 such that the cones generated by u i , u i+1 form a fan in R 2 and such that the union of these cones is R 2 when γ is an interior vertex.

Compute the transition map φ σ i ,σ i-1 at γ = (0, 0) on the edge τ i

φ σ i ,σ i-1 (0, 0) = S • [u i , u i+1 ] -1 • [u i-1 , u i ] • S = 0 b τ i (0) 1 a τ i (0)
where S = 0 1 1 0 , [u i , u i+1 ] is the matrix which columns are the vectors

u i , u i+1 , |u i , u j | is the determinant of the vectors u i , u j and
a τ i (0) = |u i-1 , u i+1 | |u i , u i+1 | , b τ i (0) = - |u i-1 , u i | |u i , u i+1 | .
(ii ) For all the edges τ ∈ M 1 , define the rational functions a τ = aτ cτ , b τ = bτ cτ on the edges τ by interpolation as follows: if there is no crossing edge in M 1 , then a linear interpolation of the value at the vertices is sufficient. If γ 1 , . . . , γ n is a sequence of crossing vertices, and γ 0 γ 1 , γ 1 γ 2 , . . . , γ n γ n+1 is a sequence of edges passing "straight" through them, we can choose linear gluing data on one edge, and quadratic data on the remaining edges of the sequence so that the constraints ( 9) and ( 10) are satisfied.

Therefore, for general meshes, gluing data which satisfy the compatibility condition and the topological condition can be constructed in degree 2.

Spline space on a topological surface

The main object of our study is the space of functions on the topological surface M, which are differentiable and piecewise polynomial. Such functions are called spline functions on M. Let R(σ) = R[u σ , v σ ] be the ring of polynomials in the variables (u σ , v σ ) attached to the face σ. A spline function f is defined by assigning to each face σ ∈ M 2 a polynomial f σ ∈ R(σ), and by imposing the regularity conditions across the shared edges.

We also consider rational gluing data on the interior edges τ ∈ M 1 :

(15)

a τ (u 1 ) = a τ (u 1 ) c τ (u 1 ) and b τ (u 1 ) = b τ (u 1 ) c τ (u 1 )
with a τ (u 1 ), b τ (u 1 ) and c τ (u 1 ) polynomials in the variable u 1 , where b τ (u 1 ) and c τ (u 1 ) do not vanish on τ (i.e. for u 1 ∈ [0, 1]). As b(u 1 ), c(u 1 ) do not vanish on τ , the transition map φ σ 2 ,σ 1 is a C 1 -diffeomorphism in a neighborhood of the edge τ = (τ 1 , τ 2 ) between σ 1 and σ 1 . The polynomial vector [a τ , b τ , c τ ] is also called hereafter the gluing data of the edge τ . We assume hereafter that the transition maps satisfy Conditions 2.6, 2.7 and all crossing vertices of M have 4 edges.

We can now define the space of splines on M: Definition 3.1. We denote by S 1 (M) the (R-linear) space of differentiable functions on the topological surface M which are defined by assigning polynomials to the faces σ ∈ M 2 satisfying the G 1 constrains (2). More precisely,

S 1 (M) := {f ∈ ⊕ σ∈M 2 R(σ) | J γ (f σ 1 ) = J γ (f σ 2 • φ σ 2 ,σ 1 ) ∀γ ∈ τ = σ 1 ∩ σ 2 },
where J γ is the jet or Taylor expansion of order 1.

A spline f ∈ S 1 (M) gives a piecewise-polynomial map, defined on every face of M, and the jets of order 1 coincide on the shared edges. This definition implies that a spline function

f ∈ S 1 (M) is C 1 on a neighborhood of a shared edge τ = σ 1 ∩ σ 2 if we use the re-parametrization f σ 2 • φ σ 2 ,σ 1 .
Definition 3.1 can be directly extended to splines of any order r but in this paper we only consider r = 1.

3.1. Polynomials on faces. On each face σ ∈ M 2 , we consider polynomials of degree bounded by k ∈ N.

If σ ∈ M 2 is a triangle (P, Q, R), we denote by R k (σ) the finite dimensional vector space of polynomials in R[u σ , v σ ] with total degree bounded by k.

After a change of coordinates, we may assume that the coordinate function u = u σ satisfies u σ (P R) = 0 and u σ

(Q) = 1, while v = v σ satisfies v σ (P Q) = 0 and v σ (R) = 1.
Introducing w = 1 -uv, we can express any polynomial in R k (σ) as a homogeneous polynomial of degree k in the barycentric coordinates u, v, w using the Bernstein-Bézier basis:

b ∆ i,j (u, v, w) = k! i!j!(k -i -j)! u i v j w k-i-j ,
for 0 i + j k. We verify directly that for a function

f (u, v) = 0 i+j k c i,j b ∆ i,j (u, v, 1 -u -v)
expressed in this basis, we have

f (0, 0) = c 0,0 , (16) ∂ u f (0, 0) = k(c 1,0 -c 0,0 ), ∂ v f (0, 0) = k(c 0,1 -c 0,0 ), ∂ u ∂ v f (0, 0) = k (k -1) (c 1,1 -c 1,0 -c 0,1 + c 0,0 ).
If σ ∈ M 2 is a rectangle (P, Q, R, S), we will denote by R k (σ) the finite dimensional vector space of polynomials in R[u σ , v σ ] with partial degree in u σ and v σ bounded by k, where u = u σ is chosen such that u σ (P S) = 0, u σ (QR) = 1, and v = v σ is chosen such that v σ (P Q) = 0, v σ (RS) = 1. Introducing ũ = 1 -u, ṽ = 1 -v, we can express any polynomial function of R k (σ) as a bi-homogeneous polynomial of degree k in u, ũ and degree k in v, ṽ, using the tensor product Bernstein-Bézier basis

b i,j (u, ũ, v, ṽ) = k!k! i!j!(k -i)!(k -j)! u i ũk-i v j ṽk-j .
for 0 i k, 0 j k. We verify directly that for a function f = 0 i,j k c i,j b i,j expressed in this basis, we have

f (0, 0) = c 0,0 , (17) ∂ u f (0, 0) = k(c 1,0 -c 0,0 ), ∂ v f (0, 0) = k(c 0,1 -c 0,0 ), ∂ u ∂ v f (0, 0) = k 2 (c 1,1 -c 1,0 -c 0,1 + c 0,0 ).
The finite dimensional vector space of spline functions f = (f σ ) σ∈M 2 ∈ S(M) of degree bounded by k ∈ N on each face (f σ ∈ R k (σ)) and of regularity r is denoted S r k (M) or simply S k (M) when r = 1.

3.2. Taylor maps. An important tool that we are going to use intensively is the Taylor map associated to a vertex or to an edge of M.

Let γ ∈ M 0 be a vertex on a face σ ∈ M 2 belonging to two edges τ, τ ∈ M 1 of σ. We define the ring of γ on σ by R σ (γ) = R(σ)/( 2 τ , 2 τ ) where ( 2 τ , 2 τ ) is the ideal generated by the squares of τ and τ , the equations τ (u, v) = 0 and τ (u, v) = 0 are respectively the equations of τ and

τ in R(σ) = R[u, v].
The Taylor expansion at γ on σ is the map

T σ γ : f ∈ R(σ) → f mod ( 2 τ , 2 τ ) in R σ (γ). Choosing an adapted basis of R σ (γ), one can define T σ γ by T σ γ (f ) = f (γ), ∂ u f (γ), ∂ v f (γ), ∂ u ∂ v f (γ)
. The map T σ γ can also be defined in another basis of R σ (γ) in terms of the Bernstein coefficients by

T σ γ (f ) = c 0,0 (f ), c 1,0 (f ), c 0,1 (f ), c 1,1 (
f ) where c 0,0 , c 1,0 , c 0,1 , c 1,1 are the first Bernstein coefficients associated to γ = (0, 0).

We define the Taylor map T γ on all the faces σ that contain γ,

T γ : f = (f σ ) ∈ ⊕ σ R(σ) → (T σ γ (f σ )) ∈ ⊕ σ⊃γ R σ (γ)
. Similarly, we define T 0 as the Taylor map at all the vertices on all the faces of M.

For an edge τ ∈ M 1 on a face σ ∈ M 2 , we define the ring of τ on σ by R

σ (τ ) = R(σ)/( 2 τ ) where τ (u, v) = 0 is the equation of τ in R(σ) = R[u, v].
The Taylor expansion along τ on σ is defined by

T σ τ : f ∈ R(σ) → f mod ( 2 τ ) in R σ (τ )
, and the Taylor map on all the faces σ that contain τ is given by

T τ : f = (f σ ) ∈ ⊕ σ R(σ) → (T σ τ (f σ )) ∈ ⊕ σ⊃τ R σ (γ)
. Similarly, we define T 1 as the Taylor map along all the edges on all the faces of M.

G 1 splines along an edge

To analyze the constraints imposed by gluing data along an edge, we consider first a simple topological surface N composed of two faces σ 1 , σ 2 glued along an edge τ .

A spline function

f ∈ S 1 k (N ) on N is represented by a pair of polynomials f = (f 1 , f 2 ) with f i ∈ R(σ i ) = R[u i , v i ] for i = 1, 2.
By a change of coordinates, we assume that the edge τ is defined by v 1 = 0 and u 1 ∈ [0, 1] in σ 1 and by u 2 = 0 and v 2 ∈ [0, 1] in σ 2 .

4.1. Splines and syzygies. With the transition map φ σ 2 ,σ 1 defined by the rational functions a = aτ cτ and b = bτ cτ as in [START_REF] Lin | Adaptive patch-based mesh fitting for reverse engineering[END_REF], the differentiability Condition (4) along the interior edge τ becomes a(u 1 )A(u 1 ) + b(u 1 )B(u 1 ) + c(u 1 )C(u 1 ) = 0, where

A(u 1 ) = ∂f 2 ∂v 2 (0, u 1 ), B(u 1 ) = ∂f 2 ∂u 2 (0, u 1 ), C(u 1 ) = - ∂f 1 ∂v 1 (u 1 , 0).
Thus, the G 1 -smoothness condition along an interior edge is equivalent to the condition on (A, B, C) of being a syzygy of the polynomials a(u 1 ), b(u 1 ), c(u 1 ).

More precisely, a G 1 spline (f 1 , f 2 ) on N is constructed from a syzygy (A, B, C) of a, b, c by defining:

f 1 (u 1 , v 1 ) = c 0 + u 1 0 A(t)dt -v 1 C(u 1 ) + v 2 1 E 1 (u 1 , v 1 ), ( 18
)
f 2 (u 2 , v 2 ) = c 0 + v 2 0 A(t)dt + u 2 B(v 2 ) + u 2 2 E 2 (u 2 , v 2 ), ( 19
)
where c 0 ∈ R is any constant, and

E 1 , E 2 are (any) polynomials in R[u i , v i ] for i = 1, 2, respectively.
We will use this representation for the splines on N to compute the dimension of the space of G 1 splines S 1 k (N ), see Proposition 4.6 below. Before, we introduce some notation, both for the proof and the dimension formula. By the formulas ( 18) and ( 19) representing a spline (f

1 , f 2 ) ∈ S 1 k (N ), let us notice that we need to consider syzygies (A, B, C) of a, b, c such that deg(A) k-1, deg(B) k -F ∆ (σ 2 ), and deg(C) k -F ∆ (σ 1
). The reason is that f i is of bidegree at most (k, k) if σ i is a rectangle and of total degree at most k if σ i is triangle. Definition 4.2. For k 0, we will denote by Z k the vector subspace of Z of syzygies of (a, b, c) defined as the set

Z k = {(A, B, C) ∈ Z : deg(A) k -1, deg(B) k -F ∆ (σ 2 ), and deg(C) k -F ∆ (σ 1 )}.
Let us consider the map

Θ τ : Z → S 1 (N ) (20) (A, B, C) → u 1 0 A(t)dt -v 1 C(u 1 ), v 2 0 A(t)dt + u 2 B(v 2 ) .
By construction, we have Θ τ (Z k ) ⊂ S 1 k (N ). The dimension of Z k , as a vector space over R, will be deduced from classical results on graded modules over S = R[u 0 , u 1 ]. We will study the module Syz

(i ) Z is a free R[u 1 ]-module of rank 2. (ii ) The module Z is generated by vectors (A 1 , B 1 , C 1 ), (A 2 , B 2 , C 2 ) of coefficient degree µ and ν = n -µ + 1 + F ∆ -e -2m
where µ is the smallest possible coefficient degree. (iii ) For k ∈ N, the dimension of Z k as vector space over R is given by

dim Z k = (k -µ -m + 1) + + (k -n + µ + m -F ∆ + e) + where t + = max(0, t) for t ∈ Z. (iv ) The generators (A 1 , B 1 , C 1 ), (A 2 , B 2 , C 2 ) of Z can be chosen so that (a, b, c) = (B 1 C 2 -B 2 C 1 , C 1 A 2 -C 2 A 1 , A 1 B 2 -A 2 B 1 ).
Proof. We study the syzygy module Z = Syz(a, b, c) using results on graded resolutions. For this purpose, we homogenize a, b and c in degree Proof. It is clear that if Āā+ Bb + Cc = 0, then by dehomogenization taking u 0 = 1, we get a syzygy (A, B, C) of (a, b, c).

d a = n + 1, d b = n + F ∆ (σ 2 )
Moreover, if deg( Āā) = deg( Bb ) = deg( Cc) = n + k, then deg( Ā) = k -1, deg( B) = k -F ∆ (σ 2 ) and deg( C) = k -F ∆ (σ 1 ). It follows that (A, B, C) ∈ Z k .
On the other hand, any syzygy (A, B, C) ∈ Z k is given by polynomials that satisfy the conditions in Definition 4. Let I = (ā, b, c) be the ideal generated by ā, b, c in S. If gcd(ā, b, c) = 1 then there exists t 0 ∈ N such that ∀t t 0 , I t = (u 0 , u 1 ) t and in that case, dim R (S/I) t = 0 for t sufficiently large. It follows that the Hilbert polynomial HP S/I of S/I is the zero polynomial.

(Aa + Bb + Cc)(u 1 /u 0 = u k-1 0 • u n+1 0 Aa u 1 /u 0 + u k-F ∆ (σ 2 ) 0 • u n+F ∆ (σ 2 ) 0 Bb u 1 /u 0 + u k-F ∆ (σ 1 ) 0 • u n+F ∆ (σ 1 ) 0 Cc u 1 /u 0 . It is easy to check that Ā = u k-1 0 A(u 1 /u 0 ), B = u k-F ∆ (σ 2 ) 0 B(u 1 /u 0 ), C = u k-F ∆ (σ 1 ) 0 C(u 1 /u 0 ) are all polynomials in R[u 1 , u 0 ],
For the second case, namely if gcd(ā, b, c) = u 0 , since gcd(a, b, c) = 1 then the polynomials ā/u 0 , b/u 0 and c/u 0 have gcd equal to 1. Hence there exists t 0 ∈ N such that ∀t t 0 , I t = u 0 (u 0 , u 1 ) t-1 . In this case dim R (S/I) t = 1 for t sufficiently large, and it follows that the Hilbert polynomial HP S/I is the constant polynomial equal to 1.

Then the exact sequence

0 → I → S → S/I → 0 implies that (21) HP I (t) = HP S (t) -HP S/I (t) = t + 1 1 -e,
where HP M is the Hilbert polynomial of the module M . By the Graded Hilbert Syzygy Theorem, we get a resolution of the form

0 -→ S(-d 1 ) ⊕ • • • ⊕ S(-d L ) λ --→ S(-d a ) ⊕ S(-d b ) ⊕ S(-d c ) -→ I -→ 0.
Notice that this resolution is not necessarily minimal. Since this is an exact sequence, then the Hilbert polynomial of the middle term is the sum of the other two Hilbert polynomials, and applying (21

) we get 3t -(d a + d b + d c ) + 3 = (t -d 1 + 1) + • • • + (t -d L + 1) + (t + 1) -e.
It follows that L = 2 which proves (i). Furthermore, we have that the degrees d In particular, it is straightforward to show that the dehomogenization (A i , B i , C i ) of ( Āi , Bi , Ci ) for i = 1, 2 generate Z = Syz(a, b, c) as a module over R[u 1 ]. This proves (ii).

By Claim 4.4, the space Z k is in correspondence with the space of homogeneous syzygies of degree n+k, which is spanned by the multiples of degree n+k of ( Ā1 , B1 , C1 ) and ( Ā2 , B2 , C2 ). Therefore,

dim Z k = (n + k -d 1 + 1) + + (n + k -d 2 + 1) + = (k -µ -m + 1) + + (k -ν -m + 1) + with ν = n -µ + 1 + F ∆ -e -2 m. This proves (iii).
The point (iv) is a consequence of Hilbert-Burch theorem. More details on this proof can be found in [6, Chapter 6, § 4.17]. Definition 4.5. For an interior edge τ in the topological surface M shared by the faces σ 1 , σ 2 with gluing data [a τ , b τ , c τ ], we denote by N τ the topological surface formed by the cells σ 1 , σ 2 glued along the edge τ with the same gluing data. Let µ τ be the smallest coefficient degree among the two generators of the module Z = Syz(a τ , b τ , c τ ). Let ν τ = n τ -µ τ + 1 + F ∆ (τ ) -e τ -2 m τ denote the complementary degree, where

n τ = max(deg(a τ ), deg(c τ ), deg(c τ )), m τ = min(F ∆ (σ 1 ), F ∆ (σ 2 )), e τ = min(n τ + 1 - deg(a τ ), n τ + F ∆ (σ 2 ) -deg(b τ ), n τ + F ∆ (σ 1 ) -deg(c τ )) F ∆ (τ ) = F ∆ (σ 1 ) + F ∆ (σ 2 ). The corresponding basis of the syzygy module Z of [a τ , b τ , c τ ] is called the µ τ -basis.
This construction allows us to determine the dimension of S 1 k (N τ ). Proposition 4.6. For F (resp. F ∆ ) the number of rectangles (resp. triangles) of N τ ,

dim S k (N τ ) = 1 + (k 2 -1)F + 1 2 (k 2 -k)F ∆ + d τ (k)
where

d τ (k) = (k -µ τ -m τ + 1) + + (k -n τ + µ τ + m τ -F ∆ + e τ ) +
Proof. Since the only constraints satisfied by the spline functions in S(N τ ) are the gluing conditions along the edge τ , the number of linearly independent splines on N τ can be easily counted by using ( 18) and ( 19), and the linearly independent terms in the Bernstein-Bézier representation of the polynomials f 1 and f 2 that conform a spline. The gluing data and the smoothness along the edge τ impose conditions on the terms in f 1 and f 2 which are linear in v 1 and v 2 , respectively. Thus, the dimension of the space of splines on N τ of degree exactly 1 in v 1 and v 2 , is given by dim Z k = d τ (k). The formula for d τ follows from Lemma 4.3, by considering Z = Syz(a τ , b τ , c τ ), where a τ , b τ , c τ define the gluing data along τ .

Separation of vertices.

We analyze now the separability of the spline functions on an edge, that is when the Taylor map at the vertices separate the spline functions.

Let

f = (f 1 , f 2 ) ∈ R(σ 1 ) ⊕ R(σ 2 ) of the form f i (u i , v i ) = p i + q i u i + qi v i + s i u i v i + r i u 2 i + ri v 2 i + • • • . Then T γ (f ) = [p 1 , q 1 , q1 , s 1 , p 2 , q 2 , q2 , s 2 ]. If f = (f 1 , f 2 ) ∈ S 1 k (N τ )
, then taking the Taylor expansion of the gluing condition (4) centered at u 1 = 0 yields

q1 + s 1 u 1 = (a(0) + a (0)u 1 + • • • ) (q 2 + 2 r2 u 1 + • • • ) (22) +(b(0) + b (0)u 1 + • • • ) (q 2 + s 2 u 1 + • • • )
Combining ( 22) with (3) yields

p 1 = p 2 q 1 = q2 r 1 = r2 q1 = a(0) q2 + b(0) q 2 s 1 = 2 a(0) r 2 + b(0) s 2 + a (0) q2 + b (0) q 2 .
Let H(γ) be the linear space spanned by the vectors [p 1 , q 1 , q1 , s 1 , p 2 , q 2 , q2 , s 2 ], which are solution of these equations. If a(0) = 0, it is a space of dimension 5 otherwise its dimension is 4. Thus dim

H(γ) = 5 -c τ (γ). Proposition 4.7. For k ν τ + m τ + 1, T γ (S 1 k (N τ )) = H(γ). Its dimension is dim T γ (S 1 k (N τ )) = 5 -c τ (γ). Proof. Let G(γ) = T γ (S 1 k (N τ ))
. By construction G(γ) ⊂ H(γ). We are going to prove that for k ν τ + m τ + 1, G(γ) and H(γ) have the same dimension and thus are equal.

By the decompositions ( 18) and ( 19), the elements of

T γ (S 1 k (N τ )) are of the form [c 0 , A(0), -C(0), -C (0), c 0 , B(0), A(0), B (0)] where c 0 ∈ R and [A, B, C] ∈ Z k . By Lemma 4.3, an element of Z k is of the form [A, B, C] = P [A 1 , B 1 , C 1 ] + Q [A 2 , B 2 , C 2 ] with P, Q ∈ R[u], deg(P ) k -µ τ -m τ and deg(Q) k -ν τ -m τ .
By removing the repeated columns, reordering and changing some signs, we see that G(γ) = T γ (S 1 k (N τ )) is isomorphic to the space spanned by the elements ( 23)

       f 1 (γ) ∂ u 1 f 1 (γ) ∂ u 2 f 2 (γ) -∂ v 1 f 1 (γ) ∂ u 2 ∂ v 2 f 2 (γ) -∂ u 1 ∂ v 1 f 1 (γ)        =        1 0 0 0 0 0 A 1 (0) A 2 (0) 0 0 0 B 1 (0) B 2 (0) 0 0 0 C 1 (0) C 2 (0) 0 0 0 B 1 (0) B 2 (0) B 1 (0) B 2 (0) 0 C 1 (0) C 2 (0) C 1 (0) C 2 (0)              c 0 P (0) Q(0) P (0) Q (0)       for P, Q ∈ R[u] with deg(P ) k -µ τ -m τ and deg(Q) k -ν τ -m τ . Let us assume that k ν τ + m τ + 1 so that k -µ τ -m τ k -ν τ -m τ 1.
As

A 1 B 2 -A 2 B 1 = c and A 1 (0)B 2 (0) -A 2 (0)B 1 (0) = c(0) = 0, we deduce that [B 1 (0), B 2 (0)] = [0, 0] and that dim G(γ) 4. If c τ (γ) = 0, then a(0) = B 1 (0)C 2 (0) -B 2 (0)C 1 (0) = 0 and dim G(γ) = 5 = 5 -c τ (γ) = dim H(γ). If c τ (γ) = 1, then a(0) = B 1 (0)C 2 (0) -B 2 (0)C 1 (0) = 0 and dim G(γ) = 4 = 5 -c τ (γ) = dim H(γ).
In both cases, we have dim G(γ) = dim H(γ), which implies that G(γ) = H(γ). This completes the proof of the proposition.

If γ is the other end point of τ , we have a Taylor map for each γ and γ , that we join together. Let

T γ,γ : R(σ 1 ) ⊕ R(σ 2 ) → R σ 1 (γ) ⊕ R σ 2 (γ) ⊕ R σ 1 (γ ) ⊕ R σ 2 (γ ) (24) f = (f 1 , f 2 ) → (T γ (f ), T γ (f ))
and let G(τ ) = T γ,γ (S 1 k (N τ )). Proposition 4.8. For k ν τ + m τ + 4, we have T γ,γ (S 1 k (N τ )) = (H(γ), H(γ )) and dim T γ,γ (S 1 k (N τ )) = 10 -c τ (γ) -c τ (γ ). Proof. By a change of coordinates, we can assume that the coordinates of γ (resp. γ ) are (0, 0) (resp. (1, 0)) in σ 1 and (0, 0) (resp. (0, 1)) in σ 2 .

Similarly to the proof of the previous proposition, T γ (S 1 k (N τ )) is spanned by the vectors

[c 0 + 1 0 A(u)du, A(1), -C(1), C (1), c 0 + 1 0 A(u)du, B(1), A(1), B (1)] for c 0 ∈ R and [A, B, C] = P [A 1 , B 1 , C 1 ] + Q [A 2 , B 2 , C 2 ] ∈ Z k with deg(P ) k -µ τ - m τ and deg(Q) k -ν τ -m τ .
For k ν τ + m τ + 4, we can find polynomials

P = p 0 (1 -3u 2 + 2u 3 ) + p 1 (u -2u 2 - u 3 ) + p 2 u 2 (1 -u) 2 , Q = q 0 (1 -3u 2 + 2u 3 ) + q 1 (u -2u 2 -u 3 ) + q 2 u 2 (1 -u) 2 , of degree 4 such that P (0) = p 0 , P (0) = p 1 , Q(0) = q 0 , Q (0) = q 1 , P (1) = 0, P (1) = 0, Q(1) = 0, Q (1) = 0 and 1 0 (P A 1 + QA 2 )(u)du = -c 0 .
This implies that (H(γ), 0) ⊂ G(τ ). By symmetry, we also have (0, H(γ )) ⊂ G(τ ). By construction G(τ ) ⊂ (H(γ), H(γ )), therefore we have G(τ ) = (H(γ), H(γ )) and dim G(τ ) = dim H(γ)+dim H(γ ). We deduce the dimension formula from Proposition 4.7.

Definition 4.9. The separability s(τ ) of the edge τ is the minimal k such that

T γ,γ (S 1 k (N τ )) = (T γ (S 1 k (N τ )), T γ (S 1 k (N τ ))).
Remark 4.10. The bound ν τ + m τ + 4 s(τ ) is not necessarily the minimal degree of separability. Separability can be attained as soon as d τ (k) 9 -c τ (γ) -c τ (γ ).

Decompositions and dimension.

Let τ ∈ M 1 be an interior edge τ shared by the cells

σ 1 , σ 2 ∈ M 2 . Let K 1 = (v 2 1 ) ∩ R k (σ 1 ) and K 2 = (u 2 2 ) ∩ R k (σ 2 ) be the polynomials of R k (σ 1 ) (resp. R k (σ 2 )) divisible by v 2 1 (resp. u 2 2
). Let L be the subspace of polynomials of R k (σ 1 ) ⊕ R k (σ 2 ) spanned by the Bernstein basis functions on σ 1 and σ 2 , which are not divisible by v 2 1 or u 2 2 and let π L be the projection of R k (σ 1 ) ⊕ R k (σ 2 ) on L along (K 1 , 0) ⊕ (0, K 2 ). The functions in L are said to have their support along τ . By construction, we have

R k (σ 1 ) ⊕ R k (σ 2 ) = (K 1 , 0) ⊕ (0, K 2 ) ⊕ L. The elements of (K 1 , K 2 ) are obviously in S 1 k (N τ ) since they vanish at the order 1 along τ . Let W k (τ ) = π L (Θ τ (Z k )) where Θ τ is defined in (20). Notice that W k (τ ) ⊂ S 1 k (N τ ) since ker π L ⊂ S 1 k (N τ ). Moreover, since ker π L does not intersect Θ τ (Z k ) and Θ τ is injective, the spaces W k (τ ), Θ τ (Z k ) and Z k have the same dimension. Therefore, we have dim(W k (τ )) = d τ (k) and W k (τ ) = {0} when k µ τ + m (Lemma 4.3 (iii)).
From the relations ( 18) and ( 19), we deduce the following decomposition:

(25) S 1 k (N τ ) = (K 1 , 0) ⊕ (0, K 2 ) ⊕ R u ⊕ W k (τ ) where u = π L ((1, 1)
). The sum of these spaces is direct, since the supports of the functions of each space do not intersect.

The map T γ,γ defined in [START_REF] Reif | Biquadratic G-spline surfaces[END_REF] induces the exact sequence k (N τ ) with their support along τ and with vanishing Taylor expansions at γ and γ . For a boundary edge τ = (γ, γ ), which belongs to a face σ, we also define E k (τ ) as the set of elements of R k (σ) with their support along τ and with vanishing Taylor expansions at γ and γ .

0 → K k (τ ) → S 1 k (N τ ) T γ,γ -→ G(τ ) → 0 where K k (τ ) = ker T γ,γ and G(τ ) = T γ,γ (S 1 k (N τ )). It is clear that (K 1 , K 2 ) ⊂ K k (τ ).
Notice that the elements of E k (τ ) have their support along τ and their Taylor expansion at γ and γ vanish. Therefore, their Taylor expansion along all (boundary) edges of N τ distinct from τ also vanish. Lemma 4.12. For an interior edge τ ∈ M o 1 , we have

K k (τ ) = (K 1 , 0)⊕(0, K 2 )⊕E k (τ ). Proof. As (K 1 , 0), (0, K 2 ) ⊂ ker T γ,γ = K k (τ ) and K k (τ ) ∩ (W k (τ ) ⊕ R u) = K k (τ ) ∩ W k (τ ) = E k (τ ), we have K k (τ ) = (K 1 , 0) ⊕ (0, K 2 ) ⊕ ((W k (τ ) ⊕ R u) ∩ K k (τ )) = (K 1 , 0) ⊕ (0, K 2 ) ⊕ E k (τ ).
Corollary 4.13. For an interior edge τ ∈ M o 1 and for k s(τ ), the dimension of

E k (τ ) is dim E k (τ ) = d τ (k) -9 + c τ (γ) + c τ (γ ).
Proof. By Lemma 4.12, we have

dim E k (τ ) = dim K k (τ ) -dim K 1 -dim K 2 .
As K k (τ ) is the kernel of T γ,γ and G(τ ) is its image, we have

dim K k (τ ) = dim S 1 k (N τ ) -dim G(τ ). As dim(W k (τ )) = d τ (k), we deduce from the decomposition (25) that dim S 1 k (N τ ) = 1 + d τ (k) + dim K 1 + dim K 2 . Using Proposition 4.8, G(τ ) = (H(γ), H(γ )) and we obtain dim E k (τ ) = dim S 1 k (N τ ) -dim G(τ ) -dim K 1 -dim K 2 = d τ (k) -9 + c τ (γ) + c τ (γ ).
Remark 4.14. When τ is a boundary edge, which belongs to the face

σ 1 ∈ M 2 , we have S k (N τ ) = R k (σ 1 ), K k (τ ) = K 1 ⊕ E k (τ ) and for k s(τ ) = 3 + F ∆ (σ 1 ), dim G(τ ) = 8 and dim E k (τ ) = k + 1 + (k + 1 -F ∆ (σ 1 )) -8 = 2 k -F ∆ (σ 1 ) -6.
Notice that this is also what we obtain if we attach a virtually rectangular face along τ with constant gluing data: n = µ = 0, m = 0, e = 2, c τ (γ) = c τ (γ ) = 0 and

d τ (k) = 2 k + 3 -F ∆ (σ 1 ), so that dim E k (τ ) = d τ (k) -9 + c τ (γ) + c τ (γ ).

G 1 splines around a vertex

We consider now a topological surface O composed of faces σ 1 , . . . , σ F ∈ O 2 sharing a single vertex γ, and such that σ i and σ i+1 share the edge τ i+1 = (γ, δ i+1 ). In particular τ i , τ i+1 are the two edges of σ i containing the vertex γ. The number of edges containing γ is denoted F . All the vertices of O different from γ are boundary vertices. The vertex γ is an interior vertex, iff σ F and σ 1 share the edge τ 1 . In this case, we identify the indices modulo F and we have F = F , otherwise we have F = F + 1. The gluing data for the interior edge τ i is

a i = a i c i , b i = b i c i .
The coordinates in the ring R(σ i ) are chosen so that the coordinates of γ are (0, 0) and τ i is defined by

v i = 0, u i ∈ [0, 1] and by u i-1 = 0, v i-1 ∈ [0, 1] in R(σ i-1
). The canonical form of the transition map at γ across the edge τ i is then

φ τ i : (u, v) -→ v i b i (u i ) u i + v i a i (u i ) Let f = (f i ) i=1,...,F ∈ S 1 (O).
The gluing condition (4) implies that the Taylor expansion of f i at γ is of the form By a computation similar to [START_REF] Peters | of Geometry and Computing[END_REF], Condition (4) implies that

f i (u i , v i ) = p + q i u i + q i+1 v i + s i u i v i + r i u 2 i + r i+1 v 2 i + • • • for p, q i , s i , r i ∈ R, i = 1, . . . , F (see Fig. 3). s s s s s s s s s σ i p q i q i+1 s i r i r i+1 τ i s i+1 r i+2 q i+2 σ i+1 τ i+1 τ i+2
q i+1 = a i (0) q i + b i (0) q i-1 (i = 2, . . . , F ) (26) s i = 2 a i (0) r i + b i (0) s i-1 + a i (0) q i + b i (0) q i-1 (i = 2, . . . , F ) (27)
Let H(γ) be the vector space spanned by the vectors h = [p, q 1 , . . . , q F , s 1 , . . . , s F ] for h = [p, q 1 , . . . , q F , s 1 , . . . , s F , r 1 , . . . , r F ] a solution of the linear system ( 26), [START_REF] Vecchia | A construction of rational manifold surfaces of arbitrary topology and smoothness from triangular meshes[END_REF].

Proposition 5.1. dim H(γ) = 3 + F (γ) - τ γ c τ (γ) + c + (γ)
where F = F (γ) is the number of faces around the vertex γ.

Proof. Notice that H(γ) is isomorphic to the projection of the solution set of system ( 26), ( 27) on the space of the variables [p, q, s] = [p, q 1 , . . . , q F , s 1 , . . . , s F ].

The solutions in q = (q 1 , . . . , q F ) of the first set of equations satisfy the induction relations

q i q i+1 = 0 1 b i (0) a i (0) q i-1 q i for i = 2, . . . , F.
As we have the compatibility condition 2.6 at an interior vertex, the solutions of ( 26) span a linear space of dimension 2, parametrized for instance by q 1 , q 2 . The system ( 27) is formed by linearly independent equations which involve r k and q i , s j when a k (0) = 0 and by equations which only involve s i , s i-1 and q j when a i (0) = 0.

Therefore the projection of the solution set of ( 27) on the space corresponding to the variables [p, q, s] is defined by the equations which only involve s i , s i-1 and q i , q i-1 when a i (0) = 0.

If one of the edges around γ is not a crossing edge, then the codimension of this space is τ γ c τ (γ), with the convention that c τ (γ) = 0 if τ is a boundary edge.

If all the edges around γ are crossing edges, then the compatibility conditions 2.7 at γ imply that one of these equations is dependent from the other. Therefore, the codimension of this space is τ γ c τ (γ) -c + (γ).

By intersecting it with the solution space of (26), we deduce that the dimension of H(γ) is precisely given by

1 + 2 + F - τ γ c τ (γ) + c + (γ).
Let T γ = σ γ T σ γ be the Taylor map at γ on O and let T ∂O = τ γ T σ τ be the Taylor map along all the boundary edges which do not contain γ.

For k ∈ N, we define V k (γ) = ker T ∂O ∩ S 1 k (O) the set of G 1 spline functions on O which vanish at the first order along the boundary edges (which do not contain γ).

Proposition 5.2. For k max i=1,...,F (s(τ i )), T γ (V k (γ)) = H(γ).
Proof. By construction, the elements of V k (γ) satisfy the equations ( 26), [START_REF] Vecchia | A construction of rational manifold surfaces of arbitrary topology and smoothness from triangular meshes[END_REF]. This implies that T γ (V k (γ)) ⊂ H(γ).

Consider an element h = (h 1 , . . . , h F ) ∈ H(γ). By Proposition 4.8, for k s(τ i ), there exists

(f i , fi ) ∈ S 1 k (N τ i ) such that T γ (f i , fi ) = (h i , h i-1
) and T δ i (f i , fi ) = 0. Let v i = 0 (resp. u i-1 = 0) be the equation of τ i in σ i (resp. σ i-1 ). As for any polynomials

p ∈ (v 2 i ) ∩ R k (σ i ), q ∈ (u i-1 ) 2 ∩ R k (σ i-1 ), T γ (p, q) = 0, we can assume that (f i , fi ) has its support in R σ i (τ i ) ⊕ R σ i-1 (τ i ).
By construction, we have

T σ i γ (f i ) = T σ i γ ( fi+1 ) = h i . Thus, there exist g i ∈ R k (σ i ) supported in R σ i (τ i ) + R σ i (τ i+1 ) such that T σ i τ i (g i ) = f i , T σ i τ i+1 (g i ) = fi+1 .
It is constructed by taking the coefficients of f i on R σ i (τ i ) and those of fi+1 on R σ i (τ i+1 ), the coefficients in R σ i (τ i ) ∩ R σ i (τ i+1 ) coinciding (see Fig. 4). As

T σ i δ i (f i ) = T σ i δ i (g i ) = 0, T σ i δ i+1 ( fi ) = T σ i δ i+1 (g i ) = 0 and g i is supported in R σ i (τ i ) + R σ i (τ i+1
), we have T σ i τ (g i ) = 0 for any edge τ of the face σ i , which does not contain γ. Let g = [g 1 , . . . , g F ] ∈ ⊕ σ i γ R k (σ i ). By construction, g vanishes at the first order along all the boundary edges of O, which do not contain γ. Moreover, T τ i (g) = (f i , fi ) ∈ S 1 k (N τ i ), thus g satisfies the gluing conditions along the edge τ i . We also have T τ (g) = 0 for any edge τ , which does not contain γ. Thus g satisfies the gluing conditions along all the edges and its image by T ∂O vanishes, i.e. g ∈ S 1 k (O) ∩ ker T ∂O = V k (γ). By construction, T γ (g) = h. This shows that H(γ) ⊂ T γ (V k (γ)) and concludes the proof.

G 1 splines on a general mesh

We consider now a general mesh M with an arbitrary number of faces, possibly with boundary edges.

We denote by T 0 = γ∈M 0 T γ the Taylor map at all the vertices of M and H = T 0 (S 1 k (M)). We have the following exact sequence:

0 → K k → S 1 k (M) T 0 → G → 0 where K k = ker T 0 ∩ S 1 k (M) and G = T 0 (S 1 k (M)). Let s * = max{s(τ ) | τ ∈ M 1 }. We have s * max{ν τ + m τ + 4 | τ ∈ M 1 } 6.
1. Splines at a vertex. Let γ ∈ M 0 be a vertex of M and let O γ be the sub-mesh associated to the faces of M which contain γ. Let V k (γ) be the set of spline functions in S 1 k (M) supported on the faces of O γ , which vanish at the first order along the edges that do not contain γ. This shows that T 0 (S 1 k (M)) = γ G(γ) = γ H(γ). We deduce the dimension formula from Proposition 5.1.

6.2. Splines on edges. For an interior edge τ = (γ, γ ) ∈ M 1 , let N τ be the submesh made of the faces σ 1 , σ 2 of M containing τ . Let E k (τ ) = ker T γ,γ ∩ Θ τ (Z k ) (see Definition 4.11). The elements of E k (τ ) correspond to splines of S 1 k (N τ ), which are in the kernel of T γ,γ and with a support in R σ 1 (τ ) ⊕ R σ 2 (τ ). Thus, E k (τ ) ⊂ ker T τ for any edge τ ∈ M 1 , distinct from τ . We deduce that any element of E k (τ ) satisfies the gluing condition along all edges of M 1 , and thus corresponds to a spline function in S 1 k (M). In other words, we have

E k (τ ) ⊂ S 1 k (M) ∩ ker T 0 = K k . The elements of E k (τ ) have a support in R σ 1 (τ ) ⊕ R σ 2 (τ )
and their Taylor coefficients at the end points of τ vanish.

Thus the support of the elements of E k (τ ) and E k (τ ) for two distinct edges τ, τ do not intersect, and their sum is direct.

Let E k = ⊕ τ ∈M 1 E k (τ ).
Let F k = ker T 1 ∩ S 1 k (M) be the set of spline functions, which Taylor expansions along all edges vanish. Proposition 6.2.

K k = F k ⊕ E k
Proof. Let f ∈ K k and take an interior edge τ ∈ M 1 . Let σ 1 , σ 2 be the two faces of

N τ . Then (f σ 1 , f σ 2 ) ∈ S 1 k (N τ ) ∩ ker T 0 = K k (τ ). By Lemma 4.12, (f σ 1 , f σ 2 ) = s τ + (k 1 , k 2 ) with s τ ∈ E k (τ ) and (k 1 , k 2 ) ∈ (K 1 , K 2 ). As s τ lifts to a spline ∈ S 1 k (M), f -s τ is an element of S 1 k (M)
, which image by the Taylor expansion T τ along the edge τ vanishes. If τ is a boundary edge of M, which belongs to the face σ 1 , we have a similar decomposition f 1 = s τ + k 1 with s τ ∈ E k (τ ) and k 1 ∈ K 1 , using the convention of Remark 4.14. Similarly s τ lifts to a spline ∈ S 1 k (M), fs τ is an element of S 1 k (M) in the kernel of T τ .

Repeating this process for all edges τ ∈ M 1 , we can construct an element f = fτ ∈M 1 s τ such that ∀τ ∈ M 1 , T τ ( f ) = 0, i.e. f belongs to ker

T 1 = F k . This shows that K k ⊂ F k + τ ∈M 1 E k (τ ). By construction, we have F k ⊂ K k and E k = ⊕ τ ∈M 1 E k (τ ) ⊂ K k .
Considering the support of the functions in F k and E k , we deduce that their sum is direct and equal to K k . 6.3. The dimension formula. We can now determine the dimension of S 1 k (M). Theorem 6.3.

Let s * = max{s(τ ) | τ ∈ M 1 }. Then, for k s * , dim S 1 k (M) = (k -3) 2 F + 1 2 (k -5)(k -4)F ∆ + τ ∈M 1 d τ (k) + 4F + 3F ∆ -9F 1 + 3F 0 + F + where • d τ (k)
is the dimension of the syzygies of the gluing data along τ in degree k, • F is the number of rectangular faces, F ∆ is the number of triangular faces, • F 1 is the number of edges, • F 0 (resp. F + ) is the number of (resp. crossing) vertices, Proof. By definition, we have

dim S 1 k (M) = dim H + dim K k . By Proposition 6.2, we have dim K k = dim F k + dim E k = dim F k + τ ∈M 1 dim E k (τ ) = (k -3) 2 F + 1 2 (k -5)(k -4)F ∆ + τ ∈M 1 (d τ (k) -9 + c τ (γ) + c τ (γ ))
From Proposition 6.1, we deduce that

dim S 1 k (M) = dim K k + dim H = (k -3) 2 F + 1 2 (k -5)(k -4)F ∆ + τ =(γ,γ )∈M 1 (d τ (k) -9 + c τ (γ) + c τ (γ )) + γ∈M 0 (F (γ) + 3) - γ∈M 0 τ γ c τ (γ) + γ∈M 0 c + (γ) = F (k -3) 2 + F ∆ 1 2 (k -5)(k -4) + τ ∈M 1 d τ (k) -9F 1 +4F + 3F ∆ + 3F 0 + F + since τ =(γ,γ )∈M 1 (c τ (γ) + c τ (γ )) = γ∈M 0 τ γ c τ (γ) and γ∈M 0 F (γ) = 4F + 3F ∆ .
As a direct corollary, we obtain the following result: Corollary 6.4. If M is a topological surface with gluing data satisfying the compatibility Conditions 2.6-2.7 and if all crossing vertices of M have 4 edges, then S 1 k (M) is an ample space of differentiable functions on M for k s * . 6.4. Basis. We are going now to describe an explicit construction of spline functions which form a basis of S 1 k (M). An algorithmic description of the computation of the Bernstein coefficients of these basis functions is provided in Appendix A.

We assume that k is bigger than the separability s * of all edges.

6.4.1. Basis functions associated to a vertex. Let γ ∈ M 0 be a vertex and σ 1 , . . . , σ F be the faces of M 2 adjacent to γ. We also assume that σ i and σ i-1 share the edge τ i ∈ M 1 and that τ 1 is not a crossing edge at γ if such an edge exists.

To compute the basis functions attached to γ, we compute first the Taylor coefficients of f σ i = p + q i u i + q i+1 v i + s i u i v i + • • • solutions of the system ( 26)-( 27) and then lift these Taylor coefficients to define a spline function with support in O γ . This leads to the following type of basis functions:

• 1 basis function attached to the value at γ: p = 1, q i = 0, s i = 0

• 2 basis functions attached to the derivatives at γ: p = 0, [q 1 , q 2 ] ∈ {[1, 0], [0, 1]} and s i = 0 if τ i is not a crossing edge at γ and determined by the relations ( 26)-( 27) if τ i is a crossing edge at γ. • F (γ)-F i=1 c τ i (γ)+c + (γ) basis functions attached to the free cross derivatives, with p = 0, q i = 0 and s i ∈ {0, 1} if τ i is not a crossing edge and determined by the relations ( 26)-( 27) if τ i is a crossing edge at γ. 6.4.2. Basis functions associated to an edge. Let τ be an edge of M 1 shared by two faces σ 1 , σ 2 with vertices γ, γ . Let us assume that the coordinates of these points in the face σ 1 are γ = (0, 0) and γ = (1, 0).

The elements of E k (τ ) are the image by Θ τ of the elements of Z k of the form

P [A 1 , B 1 , C 1 ] + Q [A 2 , B 2 , C 2 ] with degree deg(P ) k -µ τ -m τ , deg(Q) k -ν τ -m τ which are in the kernel of T γ and T γ .
From the relation [START_REF] Prautzsch | Freeform splines[END_REF], we deduce that P (0) = 0, Q(0) = 0. That is, P and Q are divisible by u.

• If c τ (γ) = 0, i.e. γ is not a crossing vertex, we have B 1 (0)C 2 (0)-B 2 (0)C 1 (0) = a(0) = 0 and the relation [START_REF] Prautzsch | Freeform splines[END_REF] implies that P (0) = 0, Q (0) = 0. That is

P = u 2 P , Q = u 2 Q. • If c τ (γ) = 1, then the kernel of T γ is generated by polynomials such that P (0) = 0, Q(0) = 0, P (0) = λC 2 (0), Q (0) = -λC 1 (0). That is P = u (λC 2 (0) + u P ), Q = u (-λC 1 (0) + u Q). That is P = u λ c τ (γ) C 2 (0) + u P , Q = u -λ c τ (γ) C 1 (0) + u Q .
By symmetry at γ , we see that P and Q are of the form:

P = u (1 -u) λ c τ (γ)C 2 (0) (1 -u) + λ c τ (γ ) C 2 (1) u + u (1 -u) P , Q = -u (1 -u) λ c τ (γ) C 1 (0) (1 -u) + λ c τ (γ ) C 1 (1) u + u (1 -u) Q , with λ, λ ∈ R, deg( P ) k -µ -m -4, deg( Q) k -ν -m -4.
We construct a basis of E k (τ ) by taking the image by Θ τ of a maximal set of linearly independent elements of this form (see Section 4.3). This yields d τ (k)-9+c τ (γ)+c τ (γ ) spline basis functions. For two faces σ 1 , σ 2 ∈ M 2 , which share an edge τ ∈ M 1 at a vertex γ, there is a linear map φ σ 2 ,σ 1 , which transforms the variables (u 1 , v 1 ) attached to σ 1 into the variables (u 2 , v 2 ) attached to σ 2 .

With γ = (0, 0) and v 1 = u 2 , the transition map φ σ 2 ,σ 1 is given by

u 2 v 2 = 0 b 1 a u 1 v 1
where a, b ∈ R and b = 0. We choose these constant transition maps to define the space of splines S 1 (M). The gluing conditions along the edges correspond then to C 1 conditions for the polynomials expressed in the same coordinate system. In this case, S 1 (M) is the vector space of piecewise polynomial functions on M, which are C 1 on Ω, that is, the classical C 1 -spline functions on Ω. If a = 0, the edge of σ 2 at γ distinct from τ is aligned with the edge of σ 1 at γ distinct from τ . The vertex γ is a crossing vertex (c + (γ) = 1; all the coefficients a in the transition maps around γ vanish) if there are 4 edges at γ, which are pair-wise aligned.

As for any interior edge τ ∈ M 1 the transition map is constant, we have n τ = 0, µ τ = 0, ν τ = 0, m τ = 1, s τ We deduce from Theorem 6.3 that for k 5, we have

dim S 1 k = 1 2 (k -5)(k -4)F ∆ + 2k F o 1 + (2k + 2) F b 1 + 3F ∆ -9 F 1 + 3 F 0 + F + = 1 2 (k + 2)(k + 1) F ∆ -6 (k -2) F ∆ + (2k -9) F o 1 + (2k -7) F b 1 + 3 F 0 + F + where F o 1 (resp.
S 1 k = 1 2 (k + 2)(k + 1) F ∆ -(2k + 1) F o 1 + 3 F o 0 + F + .
This coincides with the dimension formula of C 1 piecewise polynomials of degree k 5 on a triangular planar mesh, given in [START_REF] Morgan | A nodal basis for C 1 piecewise polynomials of degree n 5[END_REF]. Here F + counts the number of crossing vertices, also called singular vertices in [START_REF] Morgan | A nodal basis for C 1 piecewise polynomials of degree n 5[END_REF].

The basis functions constructed as in Section 6.4 are as follows:

• For each vertex γ, there are 3 basis functions associated to the evaluation and derivatives in x, y at γ. There are F (γ) - This basis description involves the Bernstein coefficients of polynomial on the triangles. The basis differs from the nodal basis proposed in [START_REF] Morgan | A nodal basis for C 1 piecewise polynomials of degree n 5[END_REF]. From the listed Bernstein coefficients, we can however recover the nodal basis of [START_REF] Morgan | A nodal basis for C 1 piecewise polynomials of degree n 5[END_REF], dual to the evaluation and derivatives at the vertices and at interior points of the edges and the triangles. 7.2. A round corner. We consider a mesh M composed of 3 rectangles σ 1 , σ 2 , σ 3 glued around an interior vertex γ, along the 3 interior edges τ 1 , τ 2 , τ 3 . There are 6 boundary edges and 6 boundary vertices. As a(0) = -1 (resp. a(1) = 0), γ is not a crossing vertex (c τ i (γ) = 0) and δ i is a crossing vertex of τ i (c τ i (δ i ) = 1).

We check that the separability of all the interior edges is 4. For k = 4, the dimension of S 1 k (M) is 3 × (4 -3) 2 + 3 × (2 × 4 + 1) + 6 × (2 × 4 + 2) + 4 × 3 -9 × 9 + 3 × 7 + 6 = 48.

The basis functions are constructed as in Section 6.4, using the algorithms of Appendix A.

• The number of basis functions attached to γ is 6 = 1 + 2 + 3.

-The basis function associated to the value at γ is XY of the two functions defined on the faces adjacent to XY coincide, there is no ambiguity in evaluating these linear functions on M. For a triangular face XYZ, we have u Y X + u Z Y + u X Z = 1. For a rectangular face XYZW, we have u Y X = u Z W and u W X = u Z Y . We denote by ∂ XY the derivative with respect to the variable u Y X . It is such that ∂ XY (u Y X ) = 1. On a triangular face XYZ, we have ∂ XY + ∂ Y Z + ∂ ZX = 0. We use a symmetric gluing at all the vertices and therefore the vertices A, C, E, F are crossing vertices. Let us describe how we construct the gluing data on the edges by interpolation at the vertices, in a smaller degree than the degree associated to the gluing [START_REF] Kapl | Isogeometric analysis with geometrically continuous functions[END_REF] proposed in [START_REF] Hahn | Geometric continuous patch complexes[END_REF].

In terms of differentials (see relation ( 5)), the symmetric gluing at the vertices translates as If c i 0,0 corresponds to the point γ, with coordinates (0, 0) in the face σ i and f σ i = p + q i u i + q i+1 v i + s i u i v i + • • • are c i , we use the relations p = c i 0,0 , q i = k c i 1,0 , q i+1 = k c i 0,1 , s i = e k (c i 1,1 -c i 1,0 -c i 0,1 ).

∂
Basis function for the value at vertex γ for i in [1,F] do let c i 0,0 := 1, c i 1,0 := 1, c i 0,1 := 1, c i 0,1 := 1 and c i l,m := 0 for (l, m) ∈ {(0, 0), (1, 0), (0, 1), ( Basis functions for the cross derivatives around γ for i in [1,F] do let c i 0,0 := 0, c i 1,0 := 0, c i 0,1 := 0; end if all edges τ i are crossing edges at γ then let c 1 1,1 := 1; for i in [2,F]

do c i 1,1 = eσ i-1
eσ i (k) b τ i (0) c i-1 1,1 ; end for i in [1,L] do lift(c i , c i-1 , τ i ); end else for j in [1,F] such that τ j is not a crossing edge at γ do let c j 1,1 = 1 and c l 1,1 = 0 for l = j; for i in [1,F'] do if τ i is a crossing edge then

c i 1,1 = eσ i-1 eσ i (k) b τ i (0) c i-1
1,1 end end for i in [1,L] do lift(c i , c i-1 , τ i ); end end end The function lift(c i , c i-1 , τ i ) used in the algorithm consists in computing the coefficient of a spline function with support along the edge τ i , from its first Taylor coefficients on the faces σ i-1 , σ i .

lift(c i , c i-1 , τ i ) for i in [1,F] do solve the systems:

k c i 1,0 k c i-1 1,0 = A 1 (0) A 2 (0) B 1 (0) B 2 (0) p i 0 q i 0 and e σ i-1 (k) (c i-1 1,1 -c i-1 1,0 -c i-1 0,1 ) -e σ i (k) (c i 1,1 -c i 1,0 -c i 0,1 ) - B 1 (0) B 2 (0) C 1 (0) C 2 (0) p i 0 q i 0 = B 1 (0) B 2 (0) C 1 (0) C 2 (0) p i 1 q i 1 .
compute P i := p i 0 (1 -3u 2 i + 2u 3 i ) + p i 1 (u -2u 2 i + u 2 i ), Q i := q i 0 (1 -3u 2 i + 2u 3 i ) + q i 1 (u -2u 2 i + u 2 i ); compute the image (g i , gi ) of P i S i 1 + Q i S i 2 by Θ τ i and update the coefficients of c i-1 , c i ; end

Figure 1 .

 1 Figure 1. Topological surface constructed from two triangles.

  The module of syzygies of a(u 1 ), b(u 1 ), c(u 1 ) over the ring R[u 1 ] is denoted by Z = Syz(a, b, c). For (A, B, C) ∈ Z, the maximum of the degrees, max(deg A, deg B, deg C) is called the coefficient degree of the syzygy.Each of the faces σ 1 and σ 2 in N can be a triangle or a rectangle. Let us denote by F the number of rectangles and by F ∆ the number of triangles in N .

Definition 4 . 1 .

 41 As before, let σ 1 , σ 2 be the faces of N . We definem = min F ∆ (σ 1 ), F ∆ (σ 2 ) , where F ∆ (σ i ) = 1 if σ i is atriangle and 0 otherwise. For the polynomials a, b, c ∈ R[u 1 ] defining the gluing data along the edge τ , let n = max deg(a), deg(b), deg(c) , d a = n + 1, d b = n + F ∆ (σ 2 ), and d c = n + F ∆ (σ 1 ), and e = 0 , if min d a -deg(a), d b -deg(b), d c -deg(c) = 0 and 1 , otherwise.

  (ā, b, c), where ā, b, c ∈ S are the homogenization of a, b and c in degree d a , d b and d c respectively. The elements in Syz(ā, b, c) in degree n + k will precisely lead to the syzygies in Z k . Lemma 4.3. For polynomials a, b, c ∈ R[u 1 ], with b, c = 0, gcd(a, b, c) = 1 and Z = Syz(a, b, c) as defined above,

Claim 4 . 4 .

 44 , and d c = n + F ∆ (σ 1 ), respectively, where F ∆ (σ i ) is as in Definition 4.1. Let u 0 , u 1 be the homogeneous coordinates, and ā, b, c the corresponding homogenizations of a, b, and c. We consider the module of homogeneous syzygies Syz(ā, b, c) over the polynomial ring S = R[u 0 , u 1 ]. For any k 0, the elements in Z k are exactly the syzygies of degree n + k in Syz(ā, b, c) after dehomogenization by setting u 0 = 1.

2 .

 2 Thus max{deg A, deg B, deg C} k, and since n = max{deg a, deg b, deg c} then we may consider the homogenization of the polynomial Aa + Bb + Cc in degree n + k. These polynomials satisfy 0 = u k+n 0

  and define a syzygy of ā, b, c of degree n + k. Let us also notice that the polynomials ā = u n+1 0 a(u 1 /u 0 ), b = u n+F ∆ (σ 2 ) 0 b(u 1 /u 0 ), and c = u n+F ∆ (σ 1 ) 0 c(u 1 /u 0 ) are precisely the homogenization of a, b, c in degree d a , d b , d c , respectively. As gcd(a, b, c) = 1, we have gcd(ā, b, c) = u 0 if e = 1, and gcd(ā, b, c) = 1 otherwise.

1 and d 2

 2 of the syzygies satisfy d 1 + d 2 = d a + d b + d c -e. The matrix Λ representing λ is a 3 × 2 matrix corresponding to the generator of degree d 1 and the second of degree d 2 . These two syzygies correspond to vectors of polynomial coefficients of degree µ = d 1 -min(d a , d b , d c ) and ν = d 2 -min(d a , d b , d c ). By Definition 4.1, min(d a , d b , d c ) = n + min 1, F ∆ (σ 1 ), F ∆ (σ 2 ) = n + m, and also d a + d b + d c = 3n + F ∆ + 1. Let us assume that d 1 d 2 , then µ is the smallest degree of the coefficient vector of a syzygy of (ā, b, c), and ν = nµ + 1 + F ∆ -e -2 m. By exactness, the two columns of Λ generate Syz(ā, b, c). The dehomogenization (by setting u 0 = 1) of the syzygies in Syz(ā, b, c) leads to syzygies of (a, b, c) over R[u 1 ].

Definition 4 . 11 .

 411 For an interior edge τ ∈ M o 1 , let E k (τ ) = ker(T γ,γ )∩W k (τ ) be the set of splines in S 1

Figure 3 .

 3 Figure 3. Taylor coefficients around a vertex.

Figure 4 .

 4 Figure 4. Lifting the edge functions.

Proposition 6 . 1 .

 61 For k s * , T 0 (S 1 k (M)) = γ H(γ) and dim T 0 (S 1 k (M)) = γ∈M 0 (F (γ) + 3) -γ∈M 0 τ γ c τ (γ) + γ∈M 0 c + (γ),where F (γ) is the number of faces of M that contain the vertex γ ∈ M 0 .Proof. By proposition 5.2, for k s * the image of V k (γ) by T 0 is G(γ), and T γ (V k (γ)) = 0 for any other vertex γ = γ.

6. 4 . 3 .

 43 Basis functions associated to a face. Finally, we define the basis functions attached to a face σ ∈ M 2 as the 2-interior Bernstein basis functions in degree k. There are (k -3) 2 such basis spline functions for a rectangular face and k-4

7 . Examples 7 . 1 .

 771 Splines on flat triangular tilings. We consider a subdivision of a planar domain Ω ⊂ R 2 into a partition of triangles and the topological surface M induced by this subdivision.

  5 and d τ (k) = 2 k. For the boundary edges, we have d τ (k) = 2 k + 2 (see Remark 4.14).

F b 1 )

 1 is the number of interior (resp. boundary) edges. Using the relations 3F ∆ = 2F o 1 + F b 1 (counting the edges per triangle, we count twice the interior edges shared by two triangles and once the boundary edges), F b 1 = F b 0 and F 0 = F o 0 +F b 0 where F o 0 (resp. F b 0 ) is the number of interior (resp. boundary) vertices, we obtain dim

  τ γ c τ (γ) + c + (γ) basis functions associated to the free cross-derivatives on the triangles containing γ. • For each interior edge τ = (γ, γ ), there are 2k-9+c τ (γ)+c τ (γ ) basis functions associated to k + 1 -6 = k -5 free interior Bernstein coefficients b 3,0 , . . . , b k-3,0 on the edge, k -4 free interior Bernstein coefficients b 2,1 , . . . , b k-2,1 on one triangle σ which contains τ and b 2,0 (resp. b k-2,0 ) if τ is a crossing vertex at γ (resp. γ ). • For each boundary edge τ , there are 2k -7 basis functions associated to k -3 free interior Bernstein coefficients b 2,0 , . . . , b k-2,0 on the edge τ , and k -4 free interior Bernstein coefficients b 2,1 , . . . , b k-2,1 on the triangle σ which contains τ . • For each triangle σ, there are k-4 2 basis functions associated to the interior Bernstein coefficients b i,j with 2 i, j k -2 and 0 i + j k.

3 Figure 5 .

 35 Figure 5. Smooth corner.We take symmetric gluing data at γ and at the crossing boundary vertices δ i . The transition map across the interior edge τ i is given by the polynomials: [a, b, c] = [(u -1), -1, 1] where γ is the end point with u = 0 and δ i is the end point with u = 1. The generating syzygies areS 1 = [0, 1, 1], S 2 = [1, u, 1]. For the interior edges τ i , we have n = 1, m = 0, µ = 0, ν = 1 and d τ i (k) = k + 1 + k = 2k + 1. For the boundary edges τ , we have n = 0, m = 0, µ = 0, ν = 0 and d τ (k) = 2 (k + 1).As a(0) = -1 (resp. a(1) = 0), γ is not a crossing vertex (c τ i (γ) = 0) and δ i is a crossing vertex of τ i (c τ i (δ i ) = 1).We check that the separability of all the interior edges is 4. For k = 4, the dimension of S 1 k (M) is 3 × (4 -3) 2 + 3 × (2 × 4 + 1) + 6 × (2 × 4 + 2) + 4 × 3 -9 × 9 + 3 × 7 + 6 = 48.

[b 0 1 ]-Figure 6 .

 016 Figure 6. A pruned octahedron

  EA + ∂ EC = 0, ∂ EB + ∂ EF = 0 at E, ∂ F A + ∂ F C = 0, ∂ F D + ∂ F E = 0 at F, ∂ AB + ∂ AF = 0, ∂ AE + ∂ AD = 0 at A,(28)∂ CB + ∂ CF = 0, ∂ CE + ∂ CD = 0 at C,and around the vertices of order 3:∂ BA + ∂ BC + ∂ BE = 0 at B, ∂ DA + ∂ DC + ∂ DF = 0 at D.For gluing the triangles EFA and EFC along EF , we interpolate the following relations between the derivatives:∂ EA + ∂ EC = 0 at E, ∂ EA + ∂ EC = 2 ∂ EF at F,where the second expression is∂ F A + ∂ F C = 0 rewritten using ∂ F A = ∂ EA -∂ EF , ∂ F C = ∂ EC -∂ EF .We choose the linear interpolation∂ EA + ∂ EC = 2u F E ∂ EF . Thereby we have a EF = 2u F E , b EF = -1 and the gluing data for the edge EF is [2 u F E , -1, 1]. For the edge EB between the triangles EBA and EBC, we interpolate the following relations:∂ EA + ∂ EC = 0 at E, ∂ EA + ∂ EC = 3 ∂ EB at B, where the latter relation is ∂ BA +∂ BC +∂ BE = 0 rewritten using ∂ BA = ∂ EA -∂ EB , ∂ BC = ∂ EC -∂ EB , ∂ BE = -∂ EB .Additionally, we have to take into account the compatibility conditions (9)-(10) since E is a crossing vertex. It translates as ∂ EB (a EB ) = ∂ EF (a EF )

1 , 1 = c i 1 ,0 + c i 0, 1 + 1 1 1,0 else c i 1 , 1 :

 11111111 1, 1)}; endBasis functions for the derivatives at vertex γfor [c 1 0,0 , c 1 0,1 ] in {[1, 0], [0, 1]} do for i in [2,F] do c i i (0) a τ i (0) all edges τ i are crossing edges at γ then let c 1 1,1 := 0; end for i in [2,F] do if τ i is a crossing edge at γ then c i eσ i (k) e σ i-1 (k)b τ i (0) (c i-1 1,1 -c i-1 1,0 -c i-1 0,1 ) +k a τ i (0) c i-1 0,1 + k b τ i (0) c i-= 0; end end for i in [1,F'] do lift(c i-1 , c i , τ i ) end end

-The three basis functions associated to the cross derivatives at γ are

The number of basis functions attached to δ i is 4 = 1 + 2 + 2 -1. Here are the 4 basis functions associated to δ 1 :

The basis functions associated to the other boundary points δ 2 , δ 3 are obtained by cyclic permutation. • The number of basis functions attached to the remaining boundary points is 4 = 1 + 2 + 1. For 1 , the 4 basis functions are

The basis functions associated to the other boundary points are obtained by cyclic permutation. • The number of basis functions attached to the edge

. The basis functions associated to the other interior edges are obtained by cyclic permutation.

• The number of basis functions attached to the boundary edges is 2(4 -3) = 2.

For the boundary edge ( 1 , δ 1 ) of σ 1 , the two basis functions are

• The number of basis functions attached to a face σ i is (4

and the two other ones are obtained by cyclic permutation.

7.3.

A pruned octahedron. We consider a mesh M with 6 triangular faces AEF, CEF, ABE, BCE, ADF, CDF and one rectangular face ABCD, depicted in Figure 6 as the Schlegel diagram of a convex polyhedron in R 3 . It is an octahedron where an edge BD is removed and two triangular faces are merged into a rectangular face (see [START_REF] Vidunas | Geometrically continuous octahedron[END_REF] for the complete octahedron, which involves only triangular faces).

We are going to use the following notation for the variables on the faces of M. For X, Y ∈ R 2 two vertices defining an edge XY of a face σ, let u Y X : R 2 → R be the linear function with u Y X (X) = 0, u Y X (Y ) = 1 and u Y X (Z) = 0 for all the points Z on the edge of σ through X and distinct from XY . We will use these linear functions u B E , u A F , etc., as variables on the different faces. As the restriction on a share edge and ∂ EC (a EC ) = ∂ EA (a EA ) at the vertex E. This leads to the following gluing data on the edge EB:

. Similarly, the gluing data of the edge FD is

. The edges EA, EC, F A, F C connect cross vertices just as EF and yield linear gluing data

We check that the compatibility conditions ( 9)-( 10) are satisfied across EA, EC and F A, F C. The gluing data along AB, AD, CB, CD looks the same:

. We have linear gluing data everywhere except on the edges EB and FD. Let us analyze the syzygies associated this data.

• For the edges EB and FD with one crossing vertex, the gluing data is of the form [2u + u 2 , -1, 1]. We have n = 2 and m = 1 since the edge is connecting two triangles, µ = 0 and ν = 2 and d(k dimensions and for the rectangular face (k -3) 2 . The dimension formula in degree k 6 is then

For k = 6, the dimension is 83. It turns out that this formula also holds for degree k = 4, k = 5.

The construction of basis functions can be done as described in Section 6.4. Let us give the basis functions associated to the value and first derivatives at the point A.

Here are the Bernstein coefficients in degree 4 of the basis function for the value at A with the vertex A represented in the center and the edges represented by horizontal and vertical central lines (in bold):

This gives the following specializations to the polygons ABE, AEF, AFD, ABCD (respectively), selectively de-homogenized:

and 0 on the other faces. The basis function associated to the first derivative in one of the directions at the cross vertices is:

The non-zero specializations to ABE, AEF, AFD, ABCD are, respectively:

The basis function for the derivative in the other direction is obtained by a mirror image of [START_REF] Vidunas | Geometrically continuous octahedron[END_REF].

The basis function corresponding to the cross derivatives is realized by 0 . . . 0 0 0 . . .

In this spline, we could modify the 0 entry next to two 1 24 entries to 1 36 , so to lower the degree of the specialization to the rectangle. After the modification, the 4 non-zero specializations would be

The local splines around C look the same. The local splines around other vertices involve the edges EB and F D, and we would need degree 6 splines.

Appendix A. Algorithms for the basis construction

Our input data is the topological surface M and the gluing data. For each edge τ of M, we are given the µ τ -basis of Z k :

. The rational map is then described by

The spline basis functions f = (f σ ) are represented on each face σ by their coefficients in the Bernstein basis of the face in degree k:

A.1. Vertex basis functions. Let γ be a vertex of M shared by the faces σ 1 , . . . , σ F and such that σ i and σ i+1 share the edge τ i+1 . We compute the Bernstein coefficients c i = [c i 0,0 , c i 1,0 , c i 0,1 , c i 1,1 , . . .] of the basis functions attached to a vertex σ i , using the equations ( 26), [START_REF] Vecchia | A construction of rational manifold surfaces of arbitrary topology and smoothness from triangular meshes[END_REF] and the relation between the Bernstein coefficients and the Taylor coefficients of the function at (0, 0), see ( 16), [START_REF] Morgan | A nodal basis for C 1 piecewise polynomials of degree n 5[END_REF].

As A 1 (0)B 2 (0) -A 2 (0)B 1 (0) = c(0) = 0, the first system has a unique solution. When B 1 (0)C 2 (0) -B 2 (0)C 1 (0) = a(0) = 0 (i.e. when τ i is not a crossing edge at γ), the second system has a unique solution. When a(0) = 0 (i.e. when τ i is a crossing edge at γ), the second system is degenerate, but it still has a (least square) solution.

The polynomials P i (resp. Q i ) are constructed so that P i (0) = p i 0 , P i (0) = p i 1 , P i (1) = 0, P i (1) = 0 (resp.

. By construction, the Taylor expansions of their image by Θ τ i vanish at γ and coincide with

)] at γ respectively on σ i-1 and σ i .

A.2. Edge basis functions.

Basis functions for the edge τ

the µ-basis of the syzygy module Z(τ ); if c τ (γ) = 1 then compute the image by Θ τ of u(1 -u) Basis functions for the face σ for 2 i k -2, 2 j k -2 (and i + j k -2 if σ is a triangle) do let c i,j := 1 and c i ,j = 0 for i = i or j = j. end