G1-smooth splines on quad meshes with 4-split
macro-patch elements

arXiv:1703.06717v1 [] 20 Mar 2017

Ahmed Blidia a Bernard Mourrain a Nelly Villamizar b
a UCA,

Inria Sophia Antipolis Méditerranée, aromath, Sophia Antipolis, France
b Swansea

University, Swansea, UK

Abstract
We analyze the space of differentiable functions on a quad-mesh M, which are
composed of 4-split spline macro-patch elements on each quadrangular face. We describe explicit transition maps across shared edges, that satisfy conditions which
ensure that the space of differentiable functions is ample on a quad-mesh of arbitrary topology. These transition maps define a finite dimensional vector space of G1
spline functions of bi-degree 6 (k, k) on each quadrangular face of M. We determine the dimension of this space of G1 spline functions for k big enough and provide
explicit constructions of basis functions attached respectively to vertices, edges and
faces. This construction requires the analysis of the module of syzygies of univariate
b-spline functions with b-spline function coefficients. New results on their generators and dimensions are provided. Examples of bases of G1 splines of small degree
for simple topological surfaces are detailed and illustrated by parametric surface
constructions.
Key words: geometrically continuous splines, dimension and bases of spline spaces,
gluing data, polygonal patches, surfaces of arbitrary topology

1

Introduction

Quadrangular b-spline surfaces are ubiquitous in geometric modeling. They
are represented as tensor products of univariate b-spline functions. Many of
Email addresses: Ahmed.Blidia@inria.fr (Ahmed Blidia),
Bernard.Mourrain@inria.fr (Bernard Mourrain),
n.y.villamizar@swansea.ac.uk (Nelly Villamizar).

the properties of univariate b-splines extend naturally to this tensor representation. They are well suited to describe parts of shapes, with features organized along two different directions, as this is often the case for manufactured
objects. However, the complete description of a shape by tensor product bspline patches may require to intersect and trim them, resulting in a geometric
model, which is inaccurate or difficult to manipulate or to deform.
To circumvent these difficulties, one can consider geometric models composed
of quadrangular patches, glued together in a smooth way along their common
boundary. Continuity constraints on the tangent planes (or on higher osculating spaces) are imposed along the share edges. In this way, smooth surfaces
can be generated from quadrilateral meshes by gluing several simple parametric surfaces. By specifying the topology of a quad(rilateral) mesh M and the
geometric continuity along the shared edges via transition maps, we obtain a
(vector) space of smooth b-spline functions on M.
Our objective is to analyze this set of smooth b-spline functions on a quad
mesh M of arbitrary topology. In particular, we want to determine the dimension and a basis of the space of smooth functions composed of tensor product
b-spline functions of bounded degree. By determining bases of these spaces,
we can represent all the smooth parametric surfaces which satisfy the geometric continuity conditions on M. Any such surface is described by its control
points in this basis, which are the coefficients in the basis of the differentiable
functions used in the parametrization.
The construction of basis functions of a spline space has several applications.
For visualization purposes, smooth deformations of these models can be obtained simply by changing their coefficients in the basis, while keeping satisfied
the regularity constraints along the edges of the quad mesh. Fitting problems
for constructing smooth models that approximate point sets or satisfy geometric constraints can be transformed into least square problems on the coefficient vector of a parametric model and solved by standard linear algebra
tools. Knowing a basis of the space of smooth spline functions of bounded
degree on a quad mesh can also be useful in Isogeometric Analysis. In this
methodology, the basis functions are used to describe the geometry and to approximate the solutions of partial differential equations on the geometry. The
explicit knowledge of a basis allows to apply Galerkin type methods, which
project the solution onto the space spanned by the basis functions.
In the last decades, several works have been focusing on the construction of G1
surfaces, including [CC78], [Pet95], [Loo94], [Rei95], [Pra97], [YZ04], [GHQ06],
[HWW+ 06], [FP08], [HBC08], [PF10], [BGN14], [BH14]. Some of these constructions use tensor product b-spline elements. In [Pet95], biquartic b-spline
elements are used on a quad mesh obtained by middle point refinement of a
general mesh. These elements involve 25 control coefficients. In [Rei95], bi2

quadratic b-spline elements are used on a semi-regular quad mesh obtained
by three levels of mid-point refinements. These correspond to 16-split macropatches, which involve 81 control points. In [Pet00], bicubic b-spline elements
with 3 nodes, corresponding to a 16-split of the parameter domain are used.
The macro-patch elements involve 169 control coefficients. In [LCB07], biquintic polynomial elements are used for solving a fitting problem. They involve 36
control coefficients. Normal vectors are extracted from the data of the fitting
problem to specify the G1 constraints. In [SWY04] biquintic 5-split b-spline elements are involved. They are represented by 100 control coefficients or more.
In [FP08], bicubic 9-split b-spline elements are involved. They are represented
by 100 control coefficients. In [PF10], it is shown that bicubic G1 splines with
linear transition maps requires at least a 9-split of the parameter domains. In
[HBC08], bicubic 4-split macro-patch elements are used. They are represented
by 36 control coefficients. The construction does not apply for general quad
meshes. In [BH14], biquartic 4-split macro-elements are used. They involve 81
control coefficients. The construction applies for general quad meshes and is
used to solve the interpolation problem of boundary curves. In these constructions, symmetric geometric continuity constraints are used at the vertices of
the mesh.
Much less work has been developed on the dimension analysis. In [MVV16],
a dimension formula and explicit basis constructions are given for polynomial
patches of degree > 4 over a mesh with triangular or quadrangular cells. In
[BM14], a similar result is obtained for the space of G1 splines of bi-degree
> (4, 4) for rectangular decompositions of planar domains. The construction of
basis functions for spaces of C 1 geometrically continuous functions restricted
to two-patch domains, has been considered in [KVJB15]. In [CST16], the approximation properties of the aforementioned spaces are explored, including
constructions over multi-patch geometries motivated by applications in isogeometric analysis.
In this paper we analyze the space of G1 splines on a general quad mesh M,
with 4-split macro-patch elements of bounded bi-degree. We describe explicit
transition maps across shared edges, that satisfy conditions which ensure that
the space of differentiable functions is ample on the quad mesh M of arbitrary topology. These transition maps define a finite dimensional vector space
of G1 b-spline functions of bi-degree 6 (k, k) on each quadrangular face of M.
We determine the dimension of this space for k big enough and provide explicit constructions of basis functions attached respectively to vertices, edges
and faces. This construction requires the analysis of the module of syzygies
of univariate b-spline functions with b-spline coefficients. New results on their
generators and dimensions are provided. This yields a new construction of
smooth splines on quad meshes of arbitrary topology, with macro-patch elements of low degree.
3

Examples of bases of G1 splines of small degree for simple topological surfaces
are detailed and illustrated by parametric surface constructions.
The techniques developed in this paper for the study of geometrically smooth
splines rely on the analysis of the syzygies of the glueing data, similarly to
the approach used in [MVV16] for polynomial patches. However an important difference is that we consider here syzygies of spline functions with spline
coefficients. The classical properties of syzygy modules over the ring of polynomials used in [MVV16] do not apply to spline functions. New results on syzygy
modules over the ring of piecewise polynomial functions (with one node and
prescribed regularity) are presented in Sections 4.1, 4.2. In particular, Proposition 4.8 describes a family of gluing data with additional degrees of freedom,
providing new possibilities to construct ample spaces of spline functions in
low degree. The necessary notation and constrains from the case of polynomial patches are used in the course of the paper. But, properties of Taylor
maps exploited in [MVV16] are incoherent in our context. In our setting, the
construction of the spline space requires to extend the results on these Taylor
maps to the context of macro-patches. Sections 4.3, 4.4, 4.5 present an alternative analysis adapted to our needs. Exploiting these properties, vertex basis
functions and face basis functions can then be constructed in the same way
as in the polynomial case.
The paper is organized as follows. The next section recalls the notions of topological surface M, differentiable functions on M and smooth spline functions
on M. In Section 3, we detail the constraints on the transition maps to have
an ample space of differentiable functions and provide explicit constructions.
In Section 4, 5, 6, we analyze the space of smooth spline functions around respectively an edge, a vertex and a face and describe basis functions attached
to these elements. In Section 7, we give the dimension formula for the space
of spline functions of bi-degree 6 (k, k) over a general quad mesh M and
describe a basis. Finally, in Section 7, we give examples of such smooth spline
spaces.

2

Definitions and basic properties

In this section, we define and describe the objects we need to analyze the
spline spaces on a quad mesh.

2.1

Topological surface

Definition 2.1 A topological surface M is given by
4

(1, 0)

(0, 1)

σ1

σ0
τ1
τ1′

(0, 1)

u1

τ0
γ1

γ0

v1 (0, 0)

v0

(0, 0) u0

τ0′
(1, 0)

Fig. 1. Given an edge τ of a topological surface M that is shared by two polygons
σ0 , σ1 ∈ M, we associated a different coordinate system to each of these two faces
and consider τ as the pair of edges τ0 and τ1 in σ0 and σ1 , respectively.

• a collection M2 of polygons (also called faces of M) in the plane that are
pairwise disjoint,
• a collection of homeomorphisms φi,j : τi 7→ τj between polygonal edges from
different polygons σi and σj of M2 ,
where a polygonal edge can be glued with at most one other polygonal edge, and
it cannot be glued with itself. The shared edges (resp. the points of the shared
edges) are identified with their image by the corresponding homeomorphism.
The collection of edges (resp. vertices) is denoted M1 (resp. M0 ).
For a vertex γ ∈ M0 , we denote by Mγ the submesh of M composed of the
faces which are adjacent to γ. For an edge τ ∈ M1 , we denote by Mτ the
submesh of M composed of the faces which are adjacent to the interior of τ .
Definition 2.2 (Gluing data) For a topological surface M, a gluing structure associated to M consists of the following:
• for each edge τ ∈ M1 of a cell σ, an open set Uτ,σ of R2 containing τ ;
• for each edge τ ∈ M1 shared by two polygons σi , σj ∈ M2 , 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 ;
Let τ be an edge shared by two polygons σ0 , σ1 ∈ M2 , τ = τ0 in σ0 , τ = τ1
in σ1 respectively and let γ = (γ0 , γ1 ) be a vertex of τ corresponding to γ0 in
σ0 and to γ1 in σ1 . We denote by τ10 (resp. τ00 ) the second edge of σ1 (resp. σ0 )
through γ1 (resp. γ0 ). We associate to σ1 and σ0 two coordinate systems (u1 , v1 )
and (u0 , v0 ) such that γ1 = (0, 0), τ1 = {(u1 , 0), u1 ∈ [0, 1]}, τ10 = {(0, v1 ), v1 ∈
[0, 1]} and γ0 = (0, 0), τ0 = {(0, v0 ), v0 ∈ [0, 1]}, τ00 = {(u0 , 0), u0 ∈ [0, 1]}, see
Figure 1. Using the Taylor expansion at (0, 0), a transition map from Uτ,σ1 to
Uτ,σ0 is then of the form


v12 ρ1 (u1 , v1 )



v1 bτ,γ (u1 ) +

φσ0 ,σ1 : (u1 , v1 ) −→ (u0 , v0 ) = 


2
u1 + v1 aτ,γ (u1 ) + v1 ρ2 (u1 , v1 )
5

(1)

where aτ,γ (u1 ), bτ,γ (u1 ), ρ1 (u1 , v1 ), ρ2 (u1 , v1 ) are C 1 functions. We will refer to
it as the canonical form of the transition map φ0,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 γ ∈ M0 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

We define now the differentiable functions on M and the spline functions on
M.
Definition 2.4 (Differentiable functions) A differentiable function on a
topological surface M is a collection f = (fσ )σ∈M2 of differentiable functions
such that for each two faces σ0 and σ1 sharing an edge τ with φ0,1 as transition
map, the two functions fσ1 and fσ0 ◦ φ0,1 have the same Taylor expansion of
order 1. The function fσ is called the restriction of f on the face σ.
This leads to the following two relations for each u1 ∈ [0, 1]:
f1 (u1 , 0) = f0 (0, u1 )
∂f0
∂f0
∂f1
(u1 , 0) = bτ,γ (u1 )
(0, u1 ) + aτ,γ (u1 )
(0, u1 )
∂v1
∂u0
∂v0

(2)
(3)

wheref1 = fσ1 , f0 = fσ0 are the restrictions of f on the faces σ0 , σ1 .
For r ∈ N, let U r = S r ([0, 12 , 1]) be the space of piecewise univariate polynomial
functions (or splines) on the subdivision [0, 12 , 1], which are of class C r . We
denote by Ukr the spline functions in U r whose polynomial pieces are of degree
6 k. We denote by R[u] the ring of polynomials in one variable u, with
coefficients in R.
Let Rr (σ) be the space of spline functions of regularity r in each parameter
over the 4-split subdivision of the quadrangle σ (see Figure 2), that is, the
tensor product of U r with itself.
For k ∈ N, the space of b-spline functions of degree 6 k in each variable, that
is of bi-degree 6 (k, k) is denoted Rrk (σ). A function fσ ∈ Rrk (σ) is represented
6

(1/2, 1)

(0, 1)
b

b

b

b

b

b

(0, 1/2)

(0, 0)

(1, 1)
b

(1/2, 1/2)

(1, 1/2)
b

(1/2, 0)
b

(1, 0)

Fig. 2. 4-split of the parameter domain

in the b-spline basis of σ as
fσ :=

X

cσi,j (fσ )Ni (uσ )Nj (vσ ),

06i,j6m

where cσi,j (fσ ) ∈ R and N0 , . . . , Nm are the classical b-spline basis functions of
Ukr with m = 2k − r. The dimension of Rrk (σ) is (m + 1)2 = (2k − r + 1)2 .
The geometric continuous spline functions on M are the differentiable functions f on M, where each component fσ on a face σ ∈ M2 is in Rr (σ). We
denote this spline space by S 1,r (M). The set of splines f ∈ S 1,r (M) with
fσ ∈ Rrk (σ) is denoted Sk1,r (M).
2.3

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. For each face σ the space of spline
functions over a subdivision onto 4 parts as in the figure above will be denoted
Rr (σ). Let γ ∈ M0 be a vertex on a face σ ∈ M2 belonging to two edges
τ, τ 0 ∈ M1 of σ. We define the ring of γ on σ by Rσ (γ) = R(σ)/(`2τ , `2τ 0 ) where
(`2τ , `2τ 0 ) is the ideal generated by the squares of `τ and `τ 0 , the equations
`τ (u, v) = 0 and `τ 0 (u, v) = 0 are respectively the equations of τ and τ 0 in
Rr (σ) = S r .
The Taylor expansion at γ on σ is the map
Tγσ : f ∈ Rr (σ) 7→ f

mod (`2τ , `2τ 0 ) in Rσ (γ).

Choosing an adapted basis of Rσ (γ), one can define Tγσ by
h

i

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
7

b-spline coefficients by
h

Tγσ (f ) = cσ0,0 (f ), cσ1,0 (f ), cσ0,1 (f ), cσ1,1 (f )

i

where c0,0 , c1,0 , c0,1 , c1,1 are the first b-spline coefficients associated to f on σ
at γ = (0, 0).
We define the Taylor map Tγ on all the faces σ that contain γ,
Tγ : f = (fσ ) ∈ ⊕σ Rr (σ) → (Tγσ (fσ )) ∈ ⊕σ⊃γ Rσ (γ).
Similarly, we define T as the Taylor map at all the vertices on all the faces of
M.
If τ ∈ M1 is the edge of the face σ(uσ , vσ ) ∈ M2 associated to vσ = 0, we
define the restriction along τ on σ as
Dτσ : Rrk (σ) → Rrk (σ)
f=

cσi,j (f )Ni (uσ )Nj (vσ ) 7→

X
06i,j6m

cσi,j (f )Ni (uσ )Nj (vσ ).

X
06i6m,06j61

The restrictions along the edges vσ = 1, uσ = 0, uσ = 1 are defined similarly
by symmetry. By convention if τ is not an edge of σ, Dτσ = 0.
For a face σ ∈ M2 , we define the restriction along the edges of σ as
Dσ : Rrk (σ) → Rrk (σ)
f=

cσi,j (f )Ni (uσ )Nj (vσ ) 7→

X
06i, j6m

X

cσi,j (f )Ni (uσ )Nj (vσ ).

i>1, or
i<m−1, j>1,
or j<m−1

The edge restriction map along all edges of M is given by
D : f = (fσ ) ∈ ⊕σ Rrk (σ) → (Dσ (fσ )) ∈ ⊕σ Rrk (σ).

3

Transition maps

The spline space on the mesh M is constructed using the transition maps
associated to the edges shared by pair of polygons in M. The transition map
b(u)
accross an edge τ is given by formula (1), where a(u) = a(u)
, b(u) = c(u)
and
c(u)
[a(u), b(u), c(u)] is a triple of functions, called gluing data. In the following,
the transition maps will be defined from spline functions in Ulr , of class C r and
degree l, with nodes 0, 21 , 1 for the gluing data. We assume that the dimension
8

of Ulr is bigger than 4, that is, 2l + 1 − r > 4 and r > 0 so that l > 12 (3 + r),
which implies that l > 2.
We denote by d0 (u), d1 (u) ∈ Ulr two spline functions such that d0 (0) = 1,
d0 (1) = 0, d1 (0) = 0, d1 (1) = 1 and d00 (0) = d00 (1) = d01 (0) = d01 (1) = 0. We
can take, for instance,
d0 (u) = N0 (u) + N1 (u)
d1 (u) = Nm−1 (u) + Nm (u)

(4)

where m = 2l − r. For l = 2, r = 1, these functions are

1 − 2u2

d0 (u) = 
d1 (u) =

0 6 u 6 21
1
6u61
2

2(1 − u)2


2u2

0 6 u 6 12
1
6 u 6 1.
2

1 − 2 (1 − u)2

For l = 2, r = 0, these functions are

1 − 4u2

d0 (u) = 
d1 (u) =

0 6 u 6 12
1
6u61
2

0


0

0 6 u 6 12
1
6 u 6 1.
2

1 − 4 (1 − u)2

To ensure that the space of spline functions is sufficiently ample (i.e., it contains enough regular functions, see [MVV16, Definition 2.5]), we impose compatibility conditions.
First around an interior vertex γ ∈ M0 , which is common to faces σ1 , . . . , σF
glued cyclically around γ, along the edges τi = σi ∩ σi−1 for i = 2, . . . , F + 1
(with σF +1 = σ1 ), we impose the condition: Jγ (φ1,2 ) ◦ · · · ◦ Jγ (φN −1,N ) = I2
where Jγ is the jet or Taylor expansion of order 1 at γ. It translates into the
following condition (see [MVV16]):
Condition 3.1 If γ ∈ M0 is an interior vertex and belongs to the faces
σ1 , . . . , σF that are glued cyclically around γ, then the gluing data [ai , bi ] at γ
on the edges τi between σi−1 and σi satisfies
F
Y
i=1





0







=

1 

bi (0) ai (0)

1



0

01

.

This gives algebraic restrictions on the values ai (0), bi (0).
9

(5)

In addition to Condition 3.1, we also consider the following condition around
a crossing vertex:
Condition 3.2 If the vertex γ is a crossing vertex with 4 edges τ1 , . . . , τ4 , the
gluing data [ai , bi ] i = 1 . . . 4 on these edges at γ satisfy
b0 (0)
= −b1 (0) a03 (0) +
+ 4
b4 (0)
b01 (0)
0
a2 (0) +
= −b2 (0) a04 (0) +
b1 (0)
a01 (0)

b02 (0)
,
b2 (0)
!
b03 (0)
.
b3 (0)
!

(6)
(7)

Let us notice that we can write the previous conditions on the gluing data
(which in our setting is given by spline functions) as in [MVV16] since they
depend on the value of the functions defining the gluing data and not on the
particular type of functions. The conditions (6) and (7) were introduced in
[MVV16] in the context of gluing data defined from polynomial functions,
they generalize the conditions of [PF10], where bi (0) = −1. The conditions
come from the relations between the derivatives and the cross-derivatives of
the face functions across the edges at a crossing vertex.
An additional condition of topological nature is also considered in [MVV16].
It ensures that the glued faces around a vertex γ are equivalent to sectors
around a point in the plane, via the reparameterization maps. We will not
need it hereafter.
To define transition maps which satisfy these conditions, we first compute the
values of the transition functions aτ , bτ of an edge τ at its end points and then
interpolate the values:
(1) For all the vertices γ ∈ M0 and for all the edges τ1 , . . . , τF of M1 that
contain γ, choose vectors u1 , . . . , uF ∈ R2 such that the cones in R2
generated by ui , ui+1 form a fan in R2 and such that the union of these
cones is R2 when γ is an interior vertex. The vector ui is associated to the
edge τi , so that the sectors ui−1 , ui and ui , ui+1 define the gluing across
the edge τi at γ.
The transition map φi−1,i at γ = (0, 0) on the edge τi is constructed as:




 0 bi (0) 

J(0,0) (φi−1,i )t = S ◦ [ui , ui+1 ]−1 ◦ [ui−1 , ui ] ◦ S = 


0
where S = 

1



1 ai (0)



1
, [ui , uj ] is the matrix which columns are the vectors ui
0

10

u0+
γ

τ

u0
b

u1

u0−

u1−
b

γ′

u1+

Fig. 3. The edge τ = (γ, γ 0 ) is associated to the vectors u0 and u1 at the points γ
and γ 0 , respectively.

and uj , and |ui , uj | is the determinant of the vectors ui , uj . Thus,
ai (0) =

|ui+1 , ui−1 |
|ui , ui−1 |
, bi (0) = −
,
|ui+1 , ui |
|ui+1 , ui |

(8)

so that ui−1 = ai (0)ui + bi (0)ui+1 . This implies that Condition 3.1 is
satisfied.
(2) For all the shared edges τ ∈ M1 , we define the functions aτ = acττ , bτ = cbττ
on the edges τ by interpolation as follows. Assume that the edge τ is
associated to the vectors u0 and u1 , respectively at the end point γ and
γ 0 corresponding to the parameters u = 0 and u = 1. Let us− , us+ ∈ R2 ,
s = 0, 1 be the vectors which define respectively the previous and next
sectors adjacent to usi at the point γ and γ 0 , see Figure 3. We define the
gluing data so that it interpolates the corresponding value (8) at u = 0
and u = 1 as:
aτ (u) = u0+ , u0− d0 (u) + u1+ , u1− d1 (u)

bτ (u) = − u0 , u0− d0 (u) − u1 , u1− d1 (u)

(9)

cτ (u) = u0+ , u0 d0 (u) + u1+ , u1 d1 (u)

where d0 (u), d1 (u) are two Hermite interpolation functions at u = 0 and
u = 1.
Since the derivatives of aτ , bτ , cτ vanish at u = 0 and u = 1, the
conditions (6) and (7) are automatically satisfied at an end point if it is
a crossing vertex.
Another possible construction, with a constant denominator cτ (u) = 1
is:
aτ (u) =

u0+ , u0−
u0+ , u0

bτ (u) = −

d0 (u) −

u1+ , u1−

d0 (u) +

u1 , u1−

u0 , u0−
u0+ , u0

u1+ , u1
u1+ , u1

d1 (u)
d1 (u)

(10)

cτ (u) = 1
The construction (10) specializes to the symmetric gluing used for instance in
11

[Hah89, §8.2], [HBC08], [BH14]:
aτ = d0 (u) 2 cos

2π
2π
− d1 (u) 2 cos
n0
n1

bτ = −1
cτ = 1

(11)

where n0 (resp. n1 ) is the number of edges at the vertex γ0 (resp. γ1 ). It
corresponds to a symmetric gluing, where the angle of two consecutive edges
.
at γi is 2π
ni

4

Splines along an edge

The space Sk1,r (M) of splines over the mesh M can be splitted into three
linearly independent components: Ek , Hk , Fk (see Section 7) attached respectively to vertices, edges and faces. The objective of this section is to give a
dimension formula for the component E(τ )k attached to the edge τ and an
explicit base, where τ is an interior edge, shared by two faces σ1 , σ2 ∈ M2 .
We denote by Mτ the sub-mesh of M composed of the two faces σ1 , σ2 .
An important step is to analyse the space Syzr,r,r
(a, b, c) of Syzygies over the
k
(a, b, c)
base ring U r . The relation of this space with E(τ )k and a basis of Syzr,r,r
k
are presented in Sections 4.1 and 4.2.
Next in Section 4.3, we study the effect, on E(τ )k , of the Taylor map at the
two end points of τ and we determine when they can be separated by the
Taylor map.
The Section 4.4 shows how to decompose the space Sk1,r for the simple mesh
Mτ , using this Taylor maps at the end points of τ . The same technique will
be used to decompose the space Sk1,r (M), for a general mesh M.

4.1

Relation with Syzygies

Given spline functions a, b, c ∈ Uls defining the gluing data accross the edge
τ ∈ M, and (f1 , f2 ) ∈ Sk1 (Mτ ), from (3) we have that:
A(u1 )a(u1 ) + B(u1 )b(u1 ) + C(u1 )c(u1 ) = 0
12

where
∂f2
0
,
(0, u1 ) ∈ Uk−1
∂v2
∂f2
B(u1 ) =
(0, u1 ) ∈ Uk1 ,
∂u2
∂f1
C(u1 ) = −
(u1 , 0) ∈ Uk1 .
∂v1
A(u1 ) =

These are the conditions imposed by the transition map across τ . According
to such data, and if the topological surface Mτ contains two faces with one
transition map along the shared edge τ , then any differentiable spline functions
f = (f1 , f2 ) over Mτ of bi-degree 6 (k, k) is given by the formula:


f1 (u1 , v1 ) = N1 (v1 ) + N0 (v1 )
−



a0 +

0



A(t)dt

(12)

1
N1 (v1 )C(u1 ) + E1 (u1 , v1 )
2k





f2 (u2 , v2 ) = N1 (u2 ) + N0 (u2 )
+

Z u1

a0 +

Z v2
0



A(t)dt

(13)

1
N1 (u2 )B(v2 ) + E2 (u2 , v2 ),
2k

since N0 (0) = 1, N1 (0) = 0, N00 (0) = −2k, and N10 (0) = 2k.
Here a0 ∈ R, the functions Ei ∈ ker Dτσi for i = 0, 1, and A, B, C are spline
functions of degree at most k − 1, k, k and class C 0 , C 1 , C 1 , respectively.
For r1 , r2 , r3 , k ∈ N and a, b, c ∈ Uls , we denote
n

o

r1
Syzkr1 ,r2 ,r3 (a, b, c) = (A, B, C) ∈ Uk−1
× Ukr2 × Ukr3 | A a + B b + C c = 0 .

We denote this vector space simply by Syzrk1 ,r2 ,r3 when a, b, c are implicitly
given.
By (12) and (13), the splines in Sk1 (Mτ ) with a support along the edge τ are
in the image of the map:
13

Θτ : R × Syz0,1,1
→ Skr (Mτ )
k
(a0 , (A, B, C)) 7→



a0 +


(14)

Z u1
0

+ a0 +



A(t)dt N0 (v1 )

Z u1

 0

A(t)dt −

N0 (u2 ) a0 +

Z v2



+N1 (u2 ) a0 +

0

Z v2
0

1
C(u1 ) N1 (u1 ),
2k


A(t)dt

!

1
A(t)dt +
B(v2 )
2k

.

The classical results on the module of syzygies on polynomial rings described in
[MVV16] (see Proposition 4.3. in the reference), will be used in order to prove
the corresponding statements in the context of syzygies on spline functions.
First, we recall the notation and results concerning the polynomial case. Let
a, b, c be polynomials in R = R[u], such that gcd(a, c) = gcd(b, c) = 1,
then Z = Syz(a, b, c) is the R-module defined by Syz(a, b, c) = {(A, B, C) ∈
R[u]3 : Aa + Bb + Cc = 0}. The degree of an element in Syz(a, b, c) is defined
as deg(A, B, C) = max{deg(A), deg(B), deg(C)}, and we are interested in
studying the subspace Zk ⊂ Syz(a, b, c) of elements of degree less than or
equal to k − 1. Let us denote n = max{deg(a), deg(b), deg(c)}, and
e=


0 ,

if min n + 1 − deg(a), n − deg(b), n − deg(c) = 0 and

1 ,

otherwise.





Lemma 4.1 Using the notation above we have:
• Z is a free R[u]-module of rank 2.
• If µ and ν are the degree of the two free generators of Syz(a, b, c) with µ
minimal, then µ + ν = n.
• dim Zk = (k − µ + 1)+ + (k − n + µ + e)+ where t+ = max(0, t) for any
t ∈ Z.
A basis with minimal degree corresponds to what is called a µ-basis in the
literature.
The proof of Lemma 4.1 can be found in [MVV16].
In the following we state the analogous to Lemma 4.1 in the context of syzygies
on spline funtions. We consider Syzr,r,r
as defined above, it is the set of spline
k
r
r
r
functions (A, B, C) ∈ Uk−1 ×Uk ×Uk such that A a+B b+C c = 0. An element
of Syzr,r,r
is a triple of pairs of polynomials ((A1 , A2 ), (B1 , B2 ), (C1 , C2 )). Let
k
R = R[u], Rk = {p ∈ R | deg(p) 6 k}, Qr = R/((2u − 1)r+1 ) and Qrk =
Rk /((2u − 1)r+1 ).
14

The elements f = (f1 , f2 ) of Ukr+1 are pairs of polynomials f1 , f2 ∈ Rk such
that f1 − f2 ≡ 0 mod (2u − 1)r+1 . Let a = (a1 , a2 ), b = (b1 , b2 ), c = (c1 , c2 ) ∈
U r with gcd(a1 , c1 ) = gcd(a2 , c2 ) = gcd(b1 , c1 ) = gcd(b2 , c2 ) = 1. We consider
the following sequence:
ψ

φ

0 −→ Syzr,r,r
−→ Syz1,k × Syz2,k −→ Qrk−1 × Qrk × Qrk −→ Qrn1 +k −→ 0 (15)
k
where Syz1,k = Syzk (a1 , b1 , c1 ), Syz2,k = Syzk (a2 , b2 , c2 ), and
• ψ(f, g, h) = a1 f + b1 g + c1 h,
• φ(A, B, C) = (A1 − A2 , B1 − B2 , C1 − C2 ) (mod (2u − 1)r+1 ).
Lemma 4.2 The sequence (15) is exact for k > n1 +r where n1 = max{deg(a1 ),
deg(b1 ), deg(c1 )}.
Proof. Since b1 , c1 are coprime, the map ψ : (f, g, h) ∈ Rk−1 × Rk × Rk 7→
a1 f + b1 g + c1 h ∈ Rn1 +k is surjective for k > n1 − 1. The map φ, obtained by
working modulo (2u − 1)r+1 , remains surjective.
We have to prove that ker(ψ) = Im(φ). If (A, B, C) ∈ Syz1 × Syz2 then
ψ ◦ φ(A, B, C) = (A1 a1 + B1 b1 + C1 c1 ) − (A2 a1 + B2 b1 + C2 c1 ) = −(A2 a1 +
B2 b1 + C2 c1 ). Because a, b, c ∈ U r , we have a1 ≡ a2 (mod (2u − 1)r+1 ), b1 ≡ b2
(mod (2u − 1)r+1 ) and c1 ≡ c2 (mod (2u − 1)r+1 ), so that
ψ ◦ φ(A, B, C) ≡ −(A2 a2 + B2 b2 + C2 c2 ) ≡ 0

(mod (2u − 1)r+1 ).

This implies that Im(φ) ⊂ ker(ψ).
Conversely, if ψ(f, g, h) = 0 with deg(f ) 6 r, deg(g) 6 r, deg(h) 6 r then
f a1 + gb1 + hc1 = d (2u − 1)r+1 for some polynomial d ∈ R of degree 6 n1 − 1.
Since gcd(b1 , c1 ) = 1, there exists p, q ∈ Rn1 −1 such that d = p b1 + q c1 , we
deduce that:
(2u − 1)r+1 d = (2u − 1)r+1 (p b1 + q c1 ) = f a1 + g b1 + h c1 ,
with deg((2u − 1)r+1 p) 6 n1 + r. This yields
f a1 + (g − p(2u − 1)r+1 ) b1 + (h − (2u − 1)r+1 q) c1 = 0.

(16)

Since k > n1 + r, this implies that ((f, 0), (g − (2u − 1)r+1 p, 0), (h − (2u −
1)r+1 q, 0)) ∈ Syz1,k × Syz2,k and its image by φ is (f, g, h). This shows that
ker(ψ) ⊂ Im(φ) and implies the equality of the two vector spaces.
By construction, the kernel of φ is the pair of triples ((A1 , B1 , C1 ), (A2 , B2 , C2 ))
in Syz1,k × Syz2,k such that A1 − A2 ≡ B1 − B2 ≡ C1 − C2 ≡ 0 (mod (2u −
r
1)r+1 ), that is, the set Syzr,r,r
of triples (A, B, C) ∈ Uk−1
× Ukr × Ukr such that
k
A a + B b + C c = 0.
15

This show that the sequence (15) is exact.

2

We deduce the dimension formula:
Proposition 4.3 Let (p1 , q1 ) (resp. (p2 , q2 )) be a basis of Syz1 (resp. Syz2 ) of
minimal degree (µ1 , ν1 ) (resp. (µ2 , ν2 )) and e1 , e2 defined as above for (a1 , b1 , c1 )
and (a2 , b2 , c2 ). For k > min(n1 , n2 ) + r,
dim(Syzr,r,r
) = (k − µ1 + 1)+ + (k − n1 + µ1 + e1 )+ + (k − µ2 + 1)+
k
+ (k − n2 + µ2 + e2 )+ − min(r + 1, k) − (r + 1).
This dimension is denoted dτ (k, r).
Proof. By symmetry, we may assume that n1 = min(n1 , n2 ). For k > n1 + r,
the sequence (15) is exact and we have
dim Syzr,r,r
= dim Syz1,k + dim Syz2,k − dim Qrk−1 − 2 dim Qrk + dim Qrn1 +k .
k
We have dim Qrk−1 = min(r + 1, k) and dim Qrk = dim Qrn1 +k = r + 1, since
k > n1 + r. This leads to the formula, using Lemma 4.1.
2

4.2

Basis of the syzygy module

The diagram (15) allows to construct a basis for the space of syzygies Syzr,r,r
k
associated to the gluing data a, b, c ∈ U r . In the rest of this section we will
show how to construct such a basis.
Lemma 4.4 Assume that k > n1 + r. Using the notation of Proposition 4.3,
we have the following assertions:
• For any p2 ∈ Syz2,k , there exists p1 ∈ Syz1,k such that (p1 , p2 ) ∈ ker(φ).
S
• There exist t, s ∈ N such that if G = {(p1 (2u−1)i , 0) : 0 6 i 6 t} {(q1 (2u−
1)j , 0) : 0 6 j 6 l} then φ(G) is a basis of the vector space ker(ψ).
L
• ker(φ) hGi = Syz1,k × Syz2,k .
Proof. Let p2 = (A2 , B2 , C2 ) ∈ Syz2,k . As φ((0, p2 )) = (f, g, h) is in ker(ψ)
(since ψ ◦ φ = 0), we can construct p1 ∈ Syz1,k such that φ((p1 , 0)) = φ((0, p2 ))
as we did in the proof of Lemma 4.2 for (f, g, h) ∈ ker(ψ) using relation
(16). This gives an element of the form (p1 , 0) ∈ Syz1,k × {0}, and finally
(p1 , p2 ) ∈ ker(φ), this proves the first point.
The second point follows from the fact that φ(Syz1,k × {0}) = ker(ψ) (since
by Lemma 4.2, the sequence (15) is exact) and that {(p1 (2u − 1)i , 0) : i 6
16

k − µ1 } {(q1 (2u − 1)j , 0)j 6 k − ν1 } is a basis of Syz1,k × {0} as a vector
space, thus the image of this basis is a generating set for ker(ψ). Since it is a
R-module, it has a basis as described in the second point of this lemma.
S

The third point is a direct consequence of the second one.

2

Considering the map in (15), the first point of the lemma has an intuitive
meaning: any function defined on a part of Mτ and that satisfies the gluing
conditions imposed by a1 , b1 , c1 can be extended to a function over Mτ that
satisfies the gluing conditions a, b, c. The third point allows us to define the
projection π1r of an element on ker(φ) along hGi.
Let (p˜2 , p2 ), (q˜2 , q2 ) be the two projections of (0, p2 ) and (0, q2 ) by π1r respectively. We denote:
•
•
•
•
•
•
•

Z1r
Z2r
Z3r
Z4r
Z5r
Z6r
Zr

= {(0, (2u − 1)i p2 ) : r + 1 6 i 6 k − µ2 }
= {(0, (2u − 1)i q2 ) : r + 1 6 i 6 k − ν2 }
= {((2u − 1)i q1 , 0) : r + 1 6 i 6 k − µ1 }
= {((2u − 1)i p1 , 0) : r + 1 6 i 6 k − ν2 }
= {(2u − 1)i (p˜2 , p2 ) : 0 6 i 6 r}
= {(2u − 1)i (q˜2 , q2 ) : 0 6 i 6 r}
S
S
S
S
S
= Z1r Z2r Z3r Z4r Z5r Z6r

Proposition 4.5 Using the notation above we have the following:
• The set Z r is a basis of the vector space Syzr,r,r
.
k
• The set Y = {(0, (2u − 1)r+1 p2 ), (0, (2u − 1)r+1 q2 ), (p˜2 , p2 ), (q˜2 , q2 ), ((2u −
1)r+1 q1 , 0), ((2u − 1)r+1 p1 , 0)} is a generating set of the R-module Syzr,r,r .
Proof. The cardinal of Z r is equal to the dimension of Syzr,r,r
, we have to
k
prove that it is a free set. Let a = (ai ), b = (bi ), c = (ci ), d = (di ), e = (ei ),
f = (fi ) for i ∈ {0, . . . , k} a set of coefficients. Suppose that:

0=
+
+

r
X

i

ai (2u − 1) (p˜2 , p2 ) +

i=0
k−r−ν
X1
i=0
k−r−µ
X 2

r
X

bi (2u − 1)i (q˜2 , q2 )

i=0
i+r+1

ci ((2u − 1)

q1 , 0) +

k−r−µ
X 1

di (0, (2u − 1)r+i+1 p2 ) +

i=0

i=0
k−r−ν
X2
i=0

17

ei ((2u − 1)i+r+1 p1 , 0)
fi (0, (2u − 1)i+r+1 q2 ).

Then we have the following equations,
0=

r
X

ai (2u − 1)i p˜2 +

i=0
k−r−µ
X 1

+

r
X

bi (2u − 1)i q˜2 +

i=0

k−r−ν
X1

ci (2u − 1)r+1+i q1

i=0

ei (2u − 1)r+1+i p1

(17)

i=0

0=

r
X

ai (2u − 1)i p2 +

i=0
k−r−ν
X2

+

r
X

bi (2u − 1)i q2 +

i=0

k−r−µ
X 2

di (2u − 1)r+1+i p2

i=0

fi (2u − 1)r+1+i q2

(18)

i=0

we know that p2 and q2 are free generators of Syz2 , by (18) this means that all
the coefficients ai , bi , di , fi that are used in the equation are zero. Replacing
in the equation(17) we get in the same way that the other coefficients ci , ei
are zero, so the set is free. Finally since the set Y does not change when k
changes, then Y generates Syzr,r,r .
2
We have similar results if we proceed in a symmetric way exchanging the role
of the first and second polynomial components of the spline functions. The
is denoted Z 0r and the generating set of the
corresponding basis of Syzr,r,r
k
R-module is
Y0 =

n

 

 



0, (2u − 1)r+1 p2 , 0, (2u − 1)r+1 q2 , p1 , p˜1 ,


 

 

o

q1 , q˜1 , (2u − 1)r q1 , 0 , (2u − 1)r p1 , 0

.

It remains to compute the dimension and a basis for Syzkr−1,r,r , we deduce
, and it will depend on the gluing data
and Syzr,r,r
them those of Syzr−1,r−1,r−1
k
k
as we explain in the following.
Proposition 4.6
• If a(1/2) 6= 0 then Syzr,r,r
= Syzr−1,r,r
, otherwise we have that dim(Syzr−1,r,r
)=
k
k
k
dim(Syzr,r,r
)
+
1.
k
• For the second case, an element in Syzr−1,r,r
\ Syzr,r,r
is of the form: α(2u −
k
k
r
r
1) (0, p2 ) + β(2u − 1) (0, q2 ), with α, β ∈ R.
For the proof of this proposition we need the following lemma that can be
proven exactly in the same way as Proposition 4.5 above.
Lemma 4.7 The set Z̃ r−1 = Z 0r {(2u − 1)r (0, p2 ), (2u − 1)r (0, q2 )} is a basis
of Syzkr−1,r−1,r−1 .
S

Proof.[Proof of Proposition 4.6.] We denote p1 = (p11 , p21 , p31 ), and q1 = (q11 , q12 , q13 ),
18

where pji and qij are polynomials. Suppose that there exists (A, B, C) ∈ Syzkr−1,r,r \
Syzr,r,r
, then by the previous lemma we can choose (A, B, C) = α(2u −
k
1)r (0, p2 ) + β(2u − 1)r (0, q2 ) with α, β ∈ R, that is:




A




B







= α(0, (2u − 1)r p12 ) + β(0, (2u − 1)r q21 )
= α(0, (2u − 1)r p22 ) + β(0, (2u − 1)r q22 )

C = α(0, (2u − 1)r p32 ) + β(0, (2u − 1)r q23 )

But since B, C ∈ U r , we deduce:


(2u − 1)r+1

divides B2 − B1 = (2u − 1)r (αp22 + βq22 )


 (2u − 1)r+1

divides C2 − C1 = (2u − 1)r (αp32 + βq23 )

This means that



αp2 ( 1 ) + βq 2 ( 1 )

=0


αp3 ( 1 ) + βq 3 ( 1 )

=0

2 2

2 2

2 2

2 2

As the determinant of this system is exactly p22 ( 21 )q23 ( 12 ) − p32 ( 21 )q22 ( 12 ) = a( 12 ),
we deduce the two points of the proposition.
2
Lemma 4.7 implies the following proposition:
is d˜τ (k, r) = dτ (k, r) + δτ with
Proposition 4.8 The dimension of Syzr−1,r,r
k
1
δτ = 1 if a( 2 ) = 0 and 0 otherwise.
4.3

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 = (f1 , f2 ) ∈ R(σ1 ) ⊕ R(σ2 ) of the form fi (ui , vi ) = pi + qi ui + q̃i vi +
si ui vi + ri u2i + r̃i vi2 + · · · . Then
Tγ (f ) = [p1 , q1 , q̃1 , s1 , p2 , q2 , q̃2 , s2 ].
If f = (f1 , f2 ) ∈ Skr (Mτ ), then taking the Taylor expansion of the gluing
condition (3) centered at u1 = 0 yields
q2 + s1 u1 = (a(0) + a0 (0)u1 + · · · ) (q̃2 + 2 r̃2 u1 + · · · )
+(b(0) + b0 (0)u1 + · · · ) (q2 + s2 u1 + · · · )
19

(19)

Combining (19) with (2) yields
p1 = p2
q1 = q̃2
r1 = r̃2
q̃1 = a(0) q̃2 + b(0) q2
s1 = 2 a(0) r̃2 + b(0) s2 + a0 (0) q̃2 + b0 (0) q2 .
Let H(γ) be the linear space spanned by the vectors [p1 , q1 , q̃1 , s1 , p2 , q2 , q̃2 , s2 ],
which are solution of these equations.
If a(0) 6= 0, it is a space of dimension 5 otherwise its dimension is 4. Thus
dim H(γ) = 5 − cτ (γ).
In the next proposition we use the notation of the previous section.
Proposition 4.9 For k > ν1 +1 we have Tγ (Sk1,r (Mτ )) = H(γ). In particular
dim(Tγ (Sk1,r (Mτ ))) = 5 − cτ (γ).
Proof. By construction we have Tγ (Sk1,r (Mτ )) ⊂ H(γ). Let us prove that
they have the same dimension. If (A, B, C) ∈ Syzr,r,r
with A = (A1 , A2 ),B =
k
(B1 , B2 ),C = (C1 , C2 ), then (A1 , B1 , C1 ) is an element of the R-module spanned
by p1 = (p11 , p21 , p31 ), q1 = (q11 , q12 , q13 ), ie (A, B, C) = a1 ((1 − 2u)r+1 p1 , 0) +
P (p1 , p˜1 ) + Q(q1 , q˜1 ). Let f = (f1 , f2 ) = Θτ (a0 , (A, B, C)) (see (14)), then it is
easy to see that:


Tγ (f ) =




















1


=

f1 (γ)
∂u1 f1 (γ)
∂u2 f2 (γ)
−∂v1 f1 (γ)
∂u2 ∂v2 f2 (γ)
−∂u1 ∂v1 f1 (γ)
0



















(20)

0

0

0



0   a0


0 
  a1







0
p11 (0)
p11 (0) q11 (0) 0









2
2
2
0


p1 (0)
p1 (0) q1 (0) 0
0   P (0) 








3
3
3
0



p
(0)
p
(0)
q
(0)
0
0
Q(0)
1
1
1







 0 p2 0 (0) − 2(r + 1)p2 (0) p2 0 (0) q 2 0 (0) p2 (0) q 2 (0)   P 0 (0) 




1
1
1
1
1
1



0

0

0

0 p31 (0) − 2(r + 1)p31 (0) p31 (0) q13 (0) p31 (0) q13 (0)

20

Q0 (0)

The second column of the matrix is linearly dependent on the third and fifth
columns. Using the same argument as in the proof of [MVV16, Proposition
4.7] on the first and 4 last columns of this matrix, we prove that its rank
is 5 − cγτ . By taking P, Q ∈ R1 of degree 6 1, which implies that k >
max(deg(P p1 ), deg(Q q1 )) = ν1 + 1, the vector [a0 , P (0), Q(0), P 0 (0), Q0 (0)]
can take all the values of R5 and we have Tγ (Sk1,r (Mτ )) = H(γ). This ends
the proof.
2
We consider now the separability of the Taylor map at the two end points
γ, γ 0 .
Proposition 4.10 Assume that k > max(ν1 + 2, ν2 + 2, µ1 + r + 1, µ2 + r + 1).
Then Tγ,γ 0 (Sk1,r (Mτ )) = (H(γ), H(γ 0 )) and dim Tγ,γ 0 (Sk1,r (Mτ )) = 10−cτ (γ)−
cτ (γ 0 ).
Proof. The inclusion Tγ,γ 0 (Sk1,r (Mτ )) ⊆ (H(γ), H(γ 0 )) is clear by construction.
For the converse, we show that the image of Tγ,γ 0 ◦ Θτ contains (H(γ), 0)
and then by symmetry we have that (0, H(γ)) is in the image of Tγ,γ 0 ◦ Θτ .
Let f = (f1 , f2 ) = Θτ (a0 , (A, B, C)) ∈ Sk1,r (Mτ ) with (A, B, C) = a1 ((1 −
2u)r+1 p1 , 0) + P (p1 , p˜1 ) + Q(q1 , q̃1 ) and P, Q ∈ U2r . The image of f by Tγ is of
the form (20). The image of f by Tγ 0 is of the form


Tγ 0 (f ) =



1 t1


=


0



0



0


0






















f1 (γ 0 )
0

∂u1 f1 (γ )
∂u2 f2 (γ 0 )
−∂v1 f1 (γ 0 )
∂u2 ∂v2 f2 (γ 0 )
−∂u1 ∂v1 f1 (γ 0 )
0

0


















0

0 p̃11 (1) q̃11 (1)

0

0 p̃21 (1) q̃12 (1)

0

0 p̃31 (1) q̃13 (1)

0

0 p̃21 0 (1) q̃12 0 (1) p̃21 (1)



0   a0


0 
  a1






 
 
 

 

 



0   P (1) 
 

+

 
 Q(1)  
0 

 

 
2
0



q̃1 (1)   P (1) 
 

 

0 0 p̃31 0 (1) q̃13 0 (1) p̃31 (1) q̃13 (1)

Q0 (1)

R 1/2

R



L (P ) + L2 (Q) 
 1
















0
0
0
0
0

with t1 = 0 (1 − 2u)r+1 p11 du, L1 (P ) = 01 P p̃11 du, L2 (Q) = 01 Q q̃11 du. By
choosing P (1) = P 0 (1) = Q(1) = Q0 (1) = 0 and a0 + t1 a1 = 0, we have an
element in the kernel of this matrix. By choosing a0 , P (0), P 0 (0), Q(0), Q0 (0)
21

R

and a1 such that a0 + t1 a1 + L1 (P ) + L2 (Q) = 0, we can find a solution to
the system (20) for any f ∈ Sk (Mτ ). Therefore, constructing spline coefficients P, Q ∈ U2r which interpolate prescribed values and derivatives at 0, 1,
we can construct spline functions f ∈ Sk (Mτ ) such that Tγ (f ) span H(γ)
and Tγ 0 (f ) = 0. The degree of the spline is k > max(ν1 + 2, µ1 + r + 1). By
symmetry, for k > max(ν2 + 2, µ2 + r + 1), we have (0, H(γ 0 )) ⊂ Tγ,γ 0 (Sk1 (Mτ ),
which concludes the proof.
2
Definition 4.11 The separability s(τ ) of the edge τ is the minimal k such
that Tγ,γ 0 (Sk1,r (Mτ )) = (Tγ (Sk1,r (Mτ )), Tγ 0 (Sk1,r (Mτ ))).
The previous proposition shows that s(τ ) 6 max(ν1 + 2, ν2 + 2, µ1 + r + 1, µ2 +
r + 1).

4.4

Decompositions and dimension

Let τ ∈ M1 be an interior edge τ shared by the cells σ0 , σ1 ∈ M2 . The Taylor
map along the edge τ of Mτ is
Dτ : Rk (σ0 ) ⊕ Rk (σ1 ) → Rk (σ0 ) ⊕ Rk (σ1 )


(f0 , f1 ) 7→ (Dτσ0 (f0 ), Dτσ1 (f1 ) .
Its image is the set of splines of Rrk (σ1 )⊕Rrk (σ2 ) with support along τ . The kernel is the set of splines of Rrk (σ1 ) ⊕ Rrk (σ2 ) with vanishing b-spline coefficients
along the edge τ . The elements of ker(Dτ ) are smooth splines in Skr (Mτ ). Let
Wk (τ ) = Dτ (Skr (Mτ )). It is the set of splines in Skr (Mτ ) with a support along
τ . As Dτ is a projector, we have the decomposition
Skr (Mτ ) = ker(Dτ ) ⊕ Wk (τ ).

(21)

From the relations (12) and (13), we deduce that Wk (τ ) = Im Θτ . Since Θτ is
injective, thus dim(Wk (τ )) = dim Syzr,r,r
k−1 + 1 = dτ (k, r) + 1 and Wk (τ ) 6= {0}
when k > µ1 and k > µ2 (Lemma (4.1) (iii)).
The map Tγ,γ 0 defined in Section 2.3 induces the exact sequence
Tγ,γ 0

0 → Kk (τ ) → Sk1,r (Mτ ) −→ H(τ ) → 0

(22)

where Kk (τ ) = ker(Tγ,γ 0 ) and H(τ ) = Tγ,γ 0 (Sk1,r (Mτ )).
Definition 4.12 For an interior edge τ ∈ Mo1 , let Ek (τ ) = ker(Tγ,γ 0 ) ∩
Wk (τ ) = ker(Tγ,γ 0 ) ∩ Im Dτ be the set of splines in Skr (Mτ ) with their support
along τ and with vanishing Taylor expansions at γ and γ 0 . For a boundary
22

edge τ 0 = (γ, γ 0 ), which belongs to a face σ, we also define Ek (τ 0 ) as the set
of elements of Rrk (σ) with their support along τ 0 and with vanishing Taylor
expansions at γ and γ 0 .
Notice that the elements of Ek (τ ) have their support along τ and that their
Taylor expansion at γ and γ 0 vanish. Therefore, their Taylor expansion along
all (boundary) edges of Mτ distinct from τ also vanish.
As ker(Dτ ) ⊂ Kk (τ ), we have the decomposition
Kk (τ ) = ker(Dτ ) ⊕ Ek (τ ).

(23)

We deduce the following result
Lemma 4.13 For an interior edge τ ∈ Mo1 and for k > s(τ ), the dimension
of Ek (τ ) is
dim Ek (τ ) = d˜τ (k, r) − 9 + cτ (γ) + cτ (γ 0 ).
Proof. From the relations (21), (22) and (23), we have
dim Ek (τ ) = dim Kk (τ ) − dim ker(Dτ )
= dim Sk1,r (Mτ ) − dim Hk (τ ) − dim Sk1,r (Mτ ) + dim Wk (τ )
= dim Wk (τ ) − dim Hk (τ ),
2

which gives the formula using Proposition 4.10.

Remark 4.14 When τ is a boundary edge, which belongs to the face σ ∈ M2 ,
we have Skr (Mτ ) = Rrk (σ) and dim Ek (τ ) = 2(m + 1) − 8 = 4k − 2r − 6.

4.5

Basis functions associated to an edge

Suppose that Bkr = {βi }i=0...l with l = dim Syzr−1,r,r
and βi = (βi1 , βi2 , βi3 ), is a
k−1
basis of Syzr−1,r,r
. We know also that Ek = {f = Θτ (a0 , (A, B, C)) : Tγ,γ 0 (f ) =
k−1
0, (A, B, C) ∈ Syzr−1,r,r
}, but we have:
k−1




 Tγ 

Tγ,γ 0 (f ) =  
Tγ 0


0

0



c0 , A(0), −C(0), −C (0),
c0 , B(0), A(0), B (0) 

=

R1
R
c0 + 0 A(u)du, A(1), −C(1), C 0 (1), c0 + 01 A(u)du, B(1), A(1), B 0 (1)

23

P

Suppose that (A, B, C) =
bi βi1 ,
0 is equivalent to the system:






















P

bi βi2 ,

P



bi βi3 with bi ∈ R, then Tγ,γ 0 (f ) =

a0 = 0
P

bi βi1 (0)

P

bi βi2 (0) = 0

=0

P
bi βi3 (0) = 0




P
0


bi βi2 (0) = 0





P
0


bi βi3 (0) = 0






P b R 1 β (t)dt = −a
i 0


P


bi βi1 (1) = 0





P



bi βi2 (1) = 0



P
bi βi3 (1) = 0




P
0


bi βi2 (1) = 0





P

 bi β 30 (1) = 0

i

(24)

i

0

The system (24) directly depends on the gluing data (1) along the edge via
equations (12) and (13), see Section 4.1 above. An explicit solution requires
the computation of a basis for the syzygy module, which is constructed in
Section 4.2. The image by Θτ (defined in (14)) of a basis of the solutions of
this system yields a basis of Ek .

5

Splines around a vertex

In this section, we analyse the spline functions, attached to a vertex, that is,
the spline functions which Taylor expansions along the edges around the vertex
vanish. We analyse the image of this space by the Taylor map at the vertex,
and construct a set of linearly independant spline functions, which images span
the image of the Taylor map. These form the set of basis functions, attached
to the vertex.
Let us consider a topological surface Mγ composed by quadrilateral faces
σ1 , . . . , σF (γ) sharing a single vertex γ, and such that the faces σi and σi−1
have a common edge τi = (γ, δi ), for i = 2, . . . , F (γ). If γ is an interior vertex
then we identify the indices modulo F (γ) and τ1 is the common edge of σF (γ)
and σ1 , see Fig. 4.
The gluing data attached to each of the edges τi will be denoted by ai = acii ,
bi = cbii . By a change of coordinates we may assume that γ is at the origin
(0, 0), and the edge τi is on the line vi = 0, where (ui−1 , vi−1 ) and (ui , vi )
are the coordinate systems associated to σi−1 and σi , respectively. Then the
24

δ2

σ1
b

δ1

τ1

σ2

σ5

γ
b

τ3
δ3

b

τ2

b

τ5
b

τ4
σ3

δ5

σ4
b

δ4

Fig. 4. Topological surface Mγ composed by F (γ) = 5 quadrilateral faces glued
around the vertex γ.

transition map at γ across τi from σi to σi−1 is as given by




vi bi (ui )

φτi : (ui , vi ) → 
;
ui + vi ai (ui )




following the notation in (1), we have φτi = φi−1,i .
The restriction along the boundary edges of Mγ is defined by
F (γ)

Dγ :

M

M

R(σi ) →

i=1
F (γ)

τ ∈∂Mγ
τ 63γ



Rσi (τ )


(fi )i=1 7→ Dτσi (fi )

τ 63γ

where Dτσi is the Taylor expansion along τ on σi , see Section 2.3.
Let Vk (γ) be the set of spline functions of degree 6 k on Mγ that vanish at
the first order derivatives along the boundary edges:
Vk (γ) = ker Dγ ∩ Sk1 (Mγ ).

(25)

The gluing data and the differentiability conditions in (3) lead to conditions
on the coefficients of the Taylor expansion of fi , namely
fi (ui , vi ) = p + qi ui + qi+1 vi + si ui vi + ri u2i + ri+1 vi2 + · · ·

(26)

with p, qi , si , ri ∈ R, and for i = 2, . . . , F the following two conditions are
satisfied
qi+1 = ai (0)qi + bi (0)qi−1
si = 2ai (0)ri + bi (0)si−1 + a0i (0)qi + b0i (0)qi−1 .

(27)
(28)

Let H(γ) be the space spanned by the vectors h = [p, q1 , . . . , qF (γ) , s1 , . . . , sF (γ) ]
such that p, q1 , . . . , qF (γ) , s1 , . . . , sF (γ) , r1 , . . . , rF (γ) ∈ R give a solution for (27)
25

and (28). The following result was proved in [MVV16, Proposition 5.1] in the
case of polynomial splines.
Proposition 5.1 For a topological surface Mγ consisting of F (γ) quadrangles
glued around an interior vertex γ,
dim H(γ) = 3 + F (γ) −

X

cτ (γ) + c+ (γ),

τ 3γ

where cτ (γ), c+ (γ) are as in Definition 2.3.
Since the vectors in H(γ) only depend on the Taylor expansion of f at γ, and
f can be seen as a polynomial spline in a neighborhood of γ, then the proof
of Proposition 5.1 follows the same argument as the one in [MVV16].
Proposition 5.2 For a topological surface Mγ as before, if s(τi ) denotes the
separability of the edge τi as in Definition 4, then




Tγ Vk (γ) = H(γ),
for every k > max{s(τi ) : i = 1, . . . , F (γ)}.
Proof. By definition (see (25)), the elements of Vk (γ)
the conditions
 satisfy

(27) and (28) on the Taylor expansion of f , then Tγ Vk (γ) ⊆ H(γ).
Let us consider a vector h = [p, q1 , . . . , qF (γ), s1 , . . . , sF (γ) ] ∈ H(γ), we need
to prove that this vector is in the image Tγ Vk (γ) . In fact, by Proposition
τi
) ∈ Sk1,r (Mτi ) such that
4.10 applied to τi = [γ, δi ], there exists (fiτi , fi−1
τi
τi
τi
) = 0 for k > s(τi ),
Tγ (fi , fi−1 ) = [p, qi , qi+1 , si , p, qi−1 , qi , si−1 ] and Tδi (fiτi , fi−1
τ
for i = 2, . . . , F . Let us notice that in such case, Tγσi (fiτi ) = Tγσi (fi i+1 ).
Thus, it follows that there exists gi ∈ Rk (σi ) such that Tτσii (gi ) = fiτi and
τ
i
Tτσi+1
(gi ) = fi i+1 . The spline gi is constructed by taking the coefficients of
τ
fiτi and fi i+1 in Rσi (τi ) and Rσi (τi+1 ), respectively (see Section 2.3). Since
τ
i
i
Tδσii (fiτi ) = Tδσii (gi ) = 0 and Tδσi+1
(fi i+1 ) = Tδσi+1
(gi ) = 0 then Tτσi (gi ) = 0 for
every edge τ ∈ σi such that γ ∈
/ τ . Let g = [g1 , g2 , . . . , gF (γ) ] where gi ∈ Rk (σi )
is as previously constructed. Then g and their first derivatives vanish on the
edges in ∂Mγ , and g satisfies the gluing conditions along all the interior edges
τi of Mγ , i.e. g ∈ Sk1 (Mγ ) ∩ ker Dγ . Hence g ∈ Vk (γ), and by construction
Tγ (g) = h.
2
Given a topological surface M, let T be the Taylor map at all the vertices of
M, as defined in Section 2.3. We have the following exact sequence
T

0 → Kk (M) → Sk1 (M) −
→ Hk (M) → 0
26

(29)





where Hk (M) = T Sk1 (M) and Kk (M) = ker T ∩ Sk1 (M). Let us define
s∗ = max{s(τ ) : τ ∈ M1 }. From Proposition 4.10, we know that s∗ 6 2 +
max{viτ : for i = 1, 2 and τ ∈ M1 } + min(3, r), where (uτi , viτ ) for i = 1, 2 are
the degrees of the generators of Syz1 and Syz2 , respectively, with uτi 6 viτ .
Proposition 5.3 Let F (γ) and H(γ) be as defined above for each vertex γ ∈
Q
M0 , then for every k > s∗ we have T (Sk1 (M)) = γ H(γ) and
dim T (Sk1 (M)) =

X

X X

(F (γ) + 3) −

γ∈M0 τ 3γ

γ∈M0

cτ (γ) +

X

c+ (γ).

γ∈M0

Proof. The statement follows directly applying Propositions 5.2 and 5.1 to
each vertex γ ∈ M0 , with Mγ the sub-mesh of M which consists of the quadrangles in M containing the vertex γ.
2

5.1

Basis functions associated to a vertex

Given a topological surface M, for each vertex γ ∈ M0 , let us consider the
sub-mesh Mγ consisting of all the faces σ ∈ M such that γ ∈ σ, as before,
we denote this number of such faces by F (γ). From Proposition 5.3 we know
the dimension of T (Sk1 (M)) for k > s∗ . In the following, we construct a set
of linearly independent splines B0 ⊆ Sk1 (M) such that span{T (f ) : f ∈ B0 } =
T (Sk1 (M)).
Let us take a vertex γ ∈ M0 and consider the b-spline representation of the
elements fσ ∈ Rk (σ) for σ ∈ Mγ . We construct a set B0 (γ) ⊂ Sk1 (Mγ ) of
linearly independent spline function as follows:
• First we add one basis function f attached to the value at γ, such that
Tγσ (fσ )(γ) = 1 for every σ ∈ Mγ . Let us notice that if we define gσ =
P
06i,j61 Ni (uσ )Nj (vσ ) for every σ ∈ Mγ , and g on Mγ such that g|σ = gσ ,
then g(γ) = 1. We lift g to a spline f on Mγ such that f is in the image of
the map Θτ defined in (14), for every τ ∈ M1 attached to γ.
• We add two basis functions g, h supported on Mγ and attached
to the

first derivatives at γ. Namely, let us consider gσ1 = (1/2k) N0 (uσ1 ) +






N1 (uσ1 ) N1 (vσ1 ), and hσ1 = (1/2k)N1 (uσ1 ) N0 (vσ1 ) + N1 (vσ1 ) . The conditions (27) and (28) allow us to find gσi and hσi , for i = 2, . . . , F (γ) from
gσ1 and hσ1 , respectively. Thus, we define g and h on Mγ by taking g|σ = gσ
and h|σ = hσ . Since g and h by construction satisfy the gluing conditions
(2) and (3) along the edges, then they are splines in the image Sk1 (Mγ ) of
Θτ for every interior edge τ ∈ Mγ .
27

• For each edge τi for i = 1, . . . , F (γ), let us define the function gσi =
i
i
cσ1,1
(gσi )N1 (uσi )N1 (vσi ), where cσ1,1
(gσi ) = 1/4k 2 if τi is not a crossing edge,
and equal to zero otherwise. Then, for every fix edge τi ∈ Mγ attached to
γ we construct a spline g on Mγ such that g|σi = gσi , and g|σj for j 6= i are
determined by gσi and the gluing data at γ, according to (27) and (28). The
P
previous construction produces F (γ) − τ 3γ cτ (γ) (non-zero) spline functions. These splines, by construction, are in the image of Θτ (14) along all
the edges τ ∈ M1 attached to γ.
• If γ is a crossing vertex, by definition all the edges attached to γ are crossing
edges. In this case, we define gσ1 = (1/4k 2 )N1 (uσ1 )N1 (vσ1 ), and determine
gσi for i = 2, . . . , F (γ) using the gluing data at γ and conditions (27) and
(28). Defining g on Mγ by g|σi = gσi we obtain a spline in Sk1 (Mγ ).
Let us notice that if τi is a crossing edge then, following the notation in the
Taylor expansion of gi (ui , vi ) in (26), the coefficient si = ∂uσi ∂vσi gi (ui , vi )|γ
becomes dependent on si−1 , qi and qi−1 and therefore there is no additional
basis function associated to the edge τi .
Applying the previous construction to every γ ∈ M0 , we obtain a collection
of splines B0 (γ) ⊆ Sk1 (Mγ ) for each γ ∈ M0 . We lift the splines f ∈ Sk1 (Mγ )
to functions on M by defining fσ = 0 for every σ ∈
/ Mγ . To simplify the
exposition, we abuse the notation, and will also call f the lifted spline on M,
and B0 (γ) the collection of those splines.
Definition 5.4 For a topological surface M, let B0 ⊆ Sk1 (M) be the set of
linearly independent functions defined by
B0 =

[

B0 (γ),

(30)

γ∈M0

where B0 (γ) ⊆ Sk1 (Mγ ), for each vertex γ ∈ M.
By construction, the collection of splines in B0 (γ), for each vertex γ ∈ M0 ,
and B0 , are linearly independent. Moreover, the number of elements in B0
coincides with the dimension of Hk (M) and hence they constitute a basis for
the spline space Sk1 (M) whose Taylor map T (29) is not zero.

6

Splines on a face

Let Fk (M) be the spline functions in Skr (M) with vanishing Taylor expansion
along all the edges of M, that is, Fk (M) = Skr (M) ∩ ker D.
An element f is in Fk (M) if and only if cσi,j (f ) = 0 for i 6 1 or i > m − 1,
j 6 1 or j > m − 1 for all σ ∈ M2 .
28

0

Let Fk (σ) be the elements in Fk (M) with cσi,j (f ) = 0 for 0 6 i, j 6 m and
σ 0 6= σ.
• The dimension of Fk (σ) is (2 k − r − 3)2+ .
• A basis of Fk (σ) is Ni (uσ )Nj (vσ ) for 1 < i, j < m − 1.
We easily check that Fk (M) = ⊕σ Fk (σ), which implies the following result:
Lemma 6.1 The dimension of Fk (M) is (2k − r − 3)2+ F2 , where F2 is the
number of (quadrangular) faces of M.
Basis functions associated to a face. The set Fk (M) of basis functions
associated to faces is obtained by taking the union of the bases of Fk (σ) for
all faces σ ∈ M2 , that is,
B2 := {Ni (uσ )Nj (vσ ), 1 < i, j < m − 1, σ ∈ M2 }.

7

(31)

Dimension and basis of Splines on M

We have now all the ingredients to determine the dimension of Sk1,r (M) and
a basis.
Theorem 7.1 Let s∗ = max{s(τ ) | τ ∈ M1 }. Then, for k > s∗ ,
dim Sk1 (M) = (2k − r − 3)2 F2 +

P

τ ∈M1

d˜τ (k, r) + 4F2 − 9F1 + 3F0 + F+

where
• d˜τ (k) is the dimension of the syzygies of the gluing data along τ in degree
6 k,
• F2 is the number of rectangular faces,
• F1 is the number of edges,
• F0 (resp. F+ ) is the number of (resp. crossing) vertices,
Proof. By construction, Kk (M) = Sk1,r (M) ∩ ker T is the set of splines in
Sk1,r (M), which Taylor expansion at all the vertices vanish and Hk (M) is the
image of Sk1,r (M) by the Taylor map T . Thus we have the following exact
sequence:
T

0 → Kk (M) → Sk1,r (M) −→ Hk (M) → 0.

(32)

By construction, Ek (M) is the set of splines in Kk (M) with a support along
the edges of M, so that D(Kk (M)) = Ek (M). The kernel of D : ⊕σ Rk (M) →
29

⊕σ Rk (M) is Fk (M). As Fk (M) ⊂ Kk (M), we have the exact sequence
D

0 → Fk (M) → Kk (M) −→ Ek (M) → 0.

(33)

From the exact sequences (32) and (33), we have

dim Sk1,r (M) = dim Hk (M) + dim Kk (M)
= dim Hk (M) + dim Ek (M) + dim Fk (M)
We deduce the dimension formula using Lemma 4.13, Proposition 5.1 and
Lemma 6.1, as in [MVV16, proof of Theorem 6.3].
2
Basis of Sk1,r (M). A basis of Sk1,r (M) is obtained by taking
• the basis B0 of Vk (M) attached to the vertices of M and defined in (30),
• the basis B1 of Ek (M) attached to the edges of M and defined in (24),
• the basis B2 of Fk (M) attached to the faces of M and defined in (31).

8

Examples

To illustrate the construction, we detail an example of a simple mesh, where
a point of valence 3 is connected to a crossing point. The construction can be
extended to points of arbitrary valencies, in a more complex mesh.
We consider the 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 δ1 , δ2 , δ3 , 1 , 2 , 3 . We use the symmetric glueing
ǫ3
b

δ1

σ3
b

τ1

τ2

σ1
ǫ1
b

τ3
b

δ3

γ
σ2

b

b

δ2

ǫ2

Fig. 5. Smooth corner.

corresponding to the angle

2π
3

at γ and
30

π
2

at δ1 , δ2 , δ3 .

We choose the gluing data [a, b, c] along an edge τi given by Formula (10):
a(u) = d0 (u)
b(u) = −d0 (u) − d1 (u)
c(u) = d0 (u) + d1 (u)
where d0 = Ñ0 (u) + Ñ1 (u), d1 = Ñ2 (u) + Ñ3 (u) + Ñ4 (u) for the b-spline basis
Ñ0 , . . . , Ñ5 of U20 and where u = 0 corresponds to γ. This gives
a(u) =



2

 −1 + 4 u

06u6



0

1
2

1
2

, b(u) = −1,

c(u) = 1;

6u61

The degrees of the µ-bases of the different components are respectively µ1 =
0, ν1 = 2, µ2 = 0, ν2 = 0. Thus the separability is reached from the degree
k > 4.
We are going to analyze the spline space S41,1 (M) for specific gluing data. An
element f ∈ S41,1 (M) is represented on each cell σi (i = 1, 2, 3) by a tensor
product b-spline of class C 1 with 8 × 8 b-spline coefficients:
X

fk :=

cki,j (f )Ni,j (uk , vk ),

06i,j67

where Ni,j (u, v) = Ni (u)Nj (v) and {N0 (u), . . . , N7 (u)} is the basis of Uk1 . We
describe an element f ∈ S41,1 (M) as a triple of b-spline functions
"

#
X
06i,j67

c1i,j Ni,j

,

c2i,j Ni,j

X
06i,j67

,

X

c3i,j Ni,j

.

06i,j67

The separability is reached at degree 4 and we have the following basis elements, described by a triple of functions which are decomposed in the b-spline
bases of each face:
• The number of basis functions attached to γ is 6 = 1 + 2 + 3.
– The basis function associated to the value at γ is

1
1
N0,0 + N0,2 + N0,3 + N0,4 + 2 N1,3 + 2 N1,4 + N2,0 + N3,0 + N4,0 ,
3
3
1
31
N0,0 + N2,0 + N3,0 + N4,0 + 3 N0,1 +
N0,2 + 17 N0,3 + 17 N0,4
3
3
+ 14 N1,2 + 34 N1,3 + 34 N1,4 ,
31
1
N0,0 + 3 N1,0 +
N2,0 + 17 N3,0 + 17 N4,0 + N0,2 + N0,3 + N0,4
3
3

+ 2 N1,3 + 2 N1,4 .

31

– The two basis functions associated to the derivatives at γ are


10
16
16
14
32
32
N0,2 +
N0,3 +
N0,4 +
N1,2 +
N1,3 +
N1,4 ,
3
3
3
3
3
3
10
16
16
N1,0 +
N2,0 +
N3,0 +
N4,0 ,
3
3
3
10
16
16
16
32
32
− N0,1 −
N0,2 −
N0,3 −
N0,4 −
N1,2 −
N1,3 −
N1,4
3
3
3
3
3
3

16
16
10
N2,0 −
N3,0 −
N4,0 ,
− N1,0 −
3
3
3

10
16
16
N1,0 +
N2,0 +
N3,0 +
N4,0 ,
3
3
3
16
16
14
32
32
10
N0,2 −
N0,3 −
N0,4 −
N1,2 −
N1,3 −
N1,4 ,
− N0,1 −
3
3
3
3
3
3
10
16
16
10
16
− N1,0 −
N2,0 −
N3,0 −
N4,0 + N0,1 +
N0,2 +
N0,3
3
3
3
3
3

16
14
32
32
+
N0,4 +
N1,2 +
N1,3 +
N1,4 .
3
3
3
3

N0,1 +

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


8
8
4
16
16
4
N0,2 − N0,3 − N0,4 + N1,1 − N1,2 −
N1,3 −
N1,4 ,
3
3
3
3
3
3

4
8
8
− N2,0 − N3,0 − N4,0 , 0 ,
3
3
3

4
8
8
− N2,0 − N3,0 − N4,0 ,
3
3
3
4
8
8
4
16
16
− N0,2 − N0,3 − N0,4 − N1,2 −
N1,3 −
N1,4 ,
3
3
3
3
3
3
4
8
8
4
8
8
− N2,0 − N3,0 − N4,0 + N1,1 − N0,2 − N0,3 − N0,4
3
3
3
3
3
3

4
16
16
− N1,2 −
N1,3 −
N1,4 ,
3
3
3

4
8
8
− N2,0 − N3,0 − N4,0 , 0 ,
3
3
3

4
8
8
4
16
16
− N0,2 − N0,3 − N0,4 − N1,2 −
N1,3 −
N1,4 .
3
3
3
3
3
3
−

• There are 4 = 1 + 2 + 2 − 1 basis functions attached to δi :

[N0,7 ,

N7,0 + 2 N7,1 , 0], [N0,6 , N6,0 + 2 N6,1 , 0 ], [N1,7 , −N7,1 , 0 ], [N1,6 , −N6,1 , 0 ].

The basis functions associated to the other boundary points δ2 , δ3 are obtained
by cyclic permutation.
• There are 5 = 14 − 5 − 4 basis functions attached to edge τ1 :

[ − N1,2 ,
[ − N1,5 ,

N2,1 , 0 ], [ − N1,3 , N3,1 , 0 ], [ − N1,4 , N4,1 , 0 ],
N5,1 , 0 ], [N0,5 + 2 N1,5 , N5,0 , 0 ].

32

The basis functions associated to the other edges τ2 , τ3 are obtained by cyclic
permutation.
• For the remaining boundary points, boundary edges and faces, we have the
following 36 × 3 basis functions

[Ni,j ,

0 , 0 ], [0 , Ni,j , 0 ], [0 , 0 , Ni,j ],

for 2 6 i, j 6 7.

The dimension of the space S41,1 (M) is 6 + 3 × (4 + 5 + 36) = 141.
A similar construction applies for an edge of a general mesh connecting an
interior vertex γ of any valency 6= 4 to another vertex γ 0 . If γ 0 is a crossing
vertex, the numbers of basis functions attached to the vertices and the edge
do not change. If γ 0 is not a crossing vertex, the number of basis functions
attached to the non-crossing vertex γ 0 becomes 5 and there are 4 basis functions attached to the edges. In the case, where the edge connects two crossing
vertices, there are 4 basis functions attached to each crossing vertex and 8
basis functions attached to the edge.
The glueing data used in this construction require a degree 4 for the separability. For the mesh of Figure 5, it is possible to use linear glueing data
and bi-cubic b-spline patches. The dimension of bi-cubic G1 splines with the
linear glueing data is 72. Depending on topology of the mesh, it is possible to
construct and the choice of the glueing data, it is possible to use low degree
b-spline patches for the construction of G1 splines. In Figure 6, examples of
G1 bicubic spline surfaces are shown, for meshes with valencies at most 3, 4
and 6. The G1 surface is obtained by least-square projection of a G0 spline
onto the space of G1 splines.

Fig. 6. Examples of bi-cubic G1 surfaces

Concluding remarks

We have studied the set of smooth b-spline functions defined on quadrilateral
meshes of arbitrary topology, with 4-split macro-patch elements. Our study
33

has focused on determining the dimension of the space of geometrically continuous G1 splines of bounded degree. We have provided a construction for the
basis of the space composed of tensor product b-spline functions. We have also
illustrated our results with examples concerning parametric surface construction for simple topological surfaces. Further extensions include the explicit
construction of transition maps which ensure that the differentiability conditions are fulfilled, and the study of spline spaces with different macro-patch
elements leading to a lower degree of the basis functions, the analysis of the
numerical conditioning of the representation of the G1 -splines in the chosen
basis, the use of these basis functions for approximation, in particular, in fitting problems and in iso-geometric analysis.
Acknowledgements: The work is partial supported by the Marie SklodowskaCurie Innovative Training Network ARCADES (grant agreement No 675789)
from the European Union’s Horizon 2020 research and innovation programme.

References

[BGN14]

Carolina Vittoria Beccari, Daniel E. Gonsor, and Marian Neamtu.
RAGS: Rational geometric splines for surfaces of arbitrary topology.
Computer Aided Geometric Design, 31(2):97–110, 2014.

[BH14]

Georges-Pierre Bonneau and Stefanie Hahmann.
Flexible G1
interpolation of quad meshes. Graphical Models, 76(6):669–681, 2014.

[BM14]

Michel Bercovier and Tanya Matskewich. Smooth Bézier Surfaces over
Arbitrary Quadrilateral Meshes. Preprint available at arXiv:1412.1125,
2014.

[CC78]

Edwin Catmull and Jim Clark. Recursively generated B-spline surfaces
on arbitrary topological meshes. Computer-Aided Design, 10(6):350–
355, 1978.

[CST16]

Annabelle Collin, Giancarlo Sangalli, and Thomas Takacs. Analysissuitable G1 multi-patch parametrizations for C 1 isogeometric spaces.
Comput. Aided Geom. Design, 47:93–113, 2016.

[FP08]

Jianhua Fan and Jörg Peters. On smooth bicubic surfaces from quad
meshes. In International Symposium on Visual Computing, pages 87–96.
Springer, 2008.

[GHQ06]

Xianfeng Gu, Ying He, and Hong Qin. Manifold splines. Graphical
Models, 68(3):237–254, 2006.

[Hah89]

Jörg M. Hahn. Geometric continuous patch complexes. Computer Aided
Geometric Design, 6(1):55–67, 1989.

34

[HBC08]

Stefanie Hahmann, Georges-Pierre Bonneau, and Baptiste Caramiaux.
Bicubic G1 interpolation of irregular quad meshes using a 4-split. In
International Conference on Geometric Modeling and Processing, pages
17–32. Springer, 2008.

[HWW+ 06] Ying He, Kexiang Wang, Hongyu Wang, Xianfeng Gu, and Hong Qin.
Manifold T-spline. In International Conference on Geometric Modeling
and Processing, pages 409–422. Springer, 2006.
[KVJB15] Mario Kapl, Vito Vitrih, Bert Jüttler, and Katharina Birner.
Isogeometric analysis with geometrically continuous functions on twopatch geometries.
Computers & Mathematics with Applications,
70(7):1518–1538, 2015.
[LCB07]

Hongwei Lin, Wei Chen, and Hujun Bao. Adaptive patch-based mesh
fitting for reverse engineering. Computer-Aided Design, 39(12):1134–
1142, 2007.

[Loo94]

Charles Loop. Smooth spline surfaces over irregular meshes. In
Proceedings of the 21st Annual Conference on Computer Graphics and
Interactive Techniques, pages 303–310. ACM, 1994.

[MVV16]

Bernard Mourrain, Raimundas Vidunas, and Nelly Villamizar.
Dimension and bases for geometrically continuous splines on surfaces
of arbitrary topology. Computer Aided Geometric Design, 45:108–133,
2016.

[Pet95]

Jörg Peters.
Biquartic C 1 -surface splines over irregular meshes.
Computer-Aided Design, 27(12):895–903, 1995.

[Pet00]

Jörg Peters. Patching catmull-clark meshes. In Proceedings of the 27th
Annual Conference on Computer Graphics and Interactive Techniques,
SIGGRAPH ’00, pages 255–258, New York, NY, USA, 2000. ACM
Press/Addison-Wesley Publishing Co.

[PF10]

Jörg Peters and Jianhua Fan. On the complexity of smooth spline
surfaces from quad meshes.
Computer Aided Geometric Design,
27(1):96–105, 2010.

[Pra97]

Hartmut Prautzsch. Freeform splines.
Design, 14(3):201–206, 1997.

[Rei95]

Ulrich Reif. Biquadratic G-spline surfaces. Computer Aided Geometric
Design, 12(2):193–205, 1995.

[SWY04]

Xiquan Shi, Tianjun Wang, and Piqiang Yu. A practical construction
of G1 smooth biquintic B-spline surfaces over arbitrary topology.
Computer-Aided Design, 36(5):413–424, 2004.

[YZ04]

Lexing Ying and Denis Zorin. A simple manifold-based construction
of surfaces of arbitrary smoothness. In SIGGRAPH’04, pages 271–275.
ACM Press, 2004.

35

Computer Aided Geometric

