Dmitry Berdinsky

Tae-Wan Kim

Cesare Bracco

Durkbin Cho

Min-Jae Oh

Yeong-Hwa Seo

Sutipong Kiatpanichgij

Iterative refinement of hierarchical T-meshes for bases of spline spaces with highest order smoothness

Keywords: hierarchical T-mesh, spline space, local refinement

In this paper we propose a strategy for generating consistent hierarchical T-meshes which allow local refinement and offer a way to obtain spline basis functions with highest order smoothness incrementally. We describe the required ordering of line-segments during refinement and the construction of spline basis functions. We give our strategy for generating consistent hierarchical T-meshes over any shape of a two-dimensional domain.

Introduction

Local mesh refinement algorithms are useful for their ability to localize changes in the set of control points to a limited region; due to their construction, basic tensor-product representation does not allow local refinement. If we allow a row of control points to terminate at a T-junction, we can refine an underlying domain locally. The spline representations based on a T-mesh as an underlying structure appear to be efficient for surface modeling and isogeometric analysis introduced in 2005 by T.J.R. Hughes et al. [START_REF] Hughes | Isogeometric analysis: CAD, finite elements, NURBS, exact geometry, and mesh refinement[END_REF][START_REF] Cottrell | Isogeometric Analysis: Toward Integration of CAD and FEA[END_REF]. For the interested reader, let us give a short overview of some of the results related to the spline representation techniques using T-meshes.

T-splines were introduced in 2003 by Sederberg et al. [START_REF] Sederberg | T-splines and T-NURCCS[END_REF]. A practicable refinement algorithm of T-splines is described in [START_REF] Sederberg | T-splines simplification and local refinement[END_REF]. The issue of the linear independence of T-splines [START_REF] Buffa | Linear independence of the T-spline blending functions associated with some particular T-meshes[END_REF], which is relevant to using T-splines in isogeometric analysis [START_REF] Bazilevs | Isogeometric analysis using tsplines[END_REF], has been resolved lately by considering analysissuitable T-splines by Li et al. [START_REF] Li | On linear independence of the T-spline blending functions[END_REF]. The refinement algorithm for analysissuitable T-splines is presented in [START_REF] Scott | Local refinement of analysis-suitable T-splines[END_REF]. Dual-compatible T-splines, which include analysis-suitable T-splines, have been introduced in [START_REF] Beirao Da Veiga | Analysis-suitable Tsplines are Dual-Compatible[END_REF].

Multilevel B-splines for surface modeling were originally introduced in 1988 by Forsey and Bartels [START_REF] Forsey | Hierarchical B-spline refinement[END_REF]. In 1995 Kraft [START_REF] Kraft | Adaptive und linear unabhängige multilevel B-splines und ihre Anwendungen[END_REF] suggested a selection mechanism for hierarchical B-splines, which ensures their linear independence while permitting local control of refinement. Kraft's construction has been further elaborated in [START_REF] Vuong | A hierarchical approach to adaptive local refinement in isogeometric analysis[END_REF][START_REF] Giannelli | THB-splines: The truncated basis for hierarchical splines[END_REF]. Dokken et al. [START_REF] Dokken | Polynomial splines over locally refined box-partitions[END_REF] have lately proposed locally refinable splines (LR-splines) and the refining process based on so-called hand-in-hand LR-refinement which starts with a tensor-product mesh.

Polynomial splines over T-meshes were introduced in 2005 by Deng et al. [START_REF] Deng | Dimension of spline spaces over T-meshes[END_REF]. PHT-splines [START_REF] Deng | Polynomial splines over hierarchical T-meshes[END_REF], which are bicubic polynomial splines with the order of smoothness (1, 1) over T-meshes, were introduced in 2006. For applications of PHT-splines in surface modeling and isogeometric analysis see eg. [START_REF] Li | Surface modeling with polynomial splines over hierarchical T-meshes[END_REF][START_REF] Nguyen-Thanh | Isogeometric analysis using polynomial splines over hierarchical T-meshes for two-dimensional elastic solids[END_REF]. Bases of spline spaces of bi-degree (m, m ) with the order of smoothness (r, r ) (if it is supposed that m 2r + 1 and m 2r + 1) over T-meshes have been constructed in terms of the Bernstein-Bézeier representation by Schumaker et al. [START_REF] Schumaker | Approximation power of polynomial splines on T-meshes[END_REF].

The issue of describing splines of bi-degree (m, m ) with the order of smoothness (r, r ) (if it is supposed that m < 2r + 1 and m < 2r + 1) over an arbitrary T-mesh seems hardly solvable in a simple and regular way. The dimension of the spline space may itself depend on the geometry of a T-mesh, and not only on its topology [START_REF] Li | On the instability in the dimension of splines spaces over T-meshes[END_REF][START_REF] Berdinsky | On the problem of instability in the dimension of a spline space over a T-mesh[END_REF]. Therefore, it is desirable to gain an insight into the topology of T-meshes which admit practicable algorithm for generating spline basis functions.

In this paper we will focus on a certain type of T-meshes with a multilevel structure. In particular, we will describe an iterative strategy to construct consistent hierarchical T-meshes for splines with highest order smoothness; namely, for splines of bi-degree (m, m) with the order of smoothness (m -1, m -1). Wu et al. [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF][START_REF] Wu | Hierarchical bases of spline spaces with highest order smoothness over hierarchical T-subdivisions[END_REF] have recently introduced consistent hierarchical T-meshes. A consistent hierarchical T-mesh is generated by a sequence of edge insertions such that each new edge insertion into the mesh satisfies so-called surjection condition; in essence that means that one is able to add all new basis functions of a spline space with highest order smoothness at each iteration of edge insertion. The concept of a consistent hierarchical T-mesh seems to offer natural way to add spline basis functions incrementally. A consistent hierarchical T-mesh might be generated for any shape of two-dimensional domain, and not just for rectangular domains. However, the generation of a consistent hierarchical T-mesh and the ordering of the edges or line-segments remain open questions. As an implementation of a consistent hierarchical T-mesh, Wu et al. [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF] suggest a particular type of crosswise hierarchical T-mesh that contains a nested sequence of domains.

The essence of our iterative strategy can be described as follows. At each iteration step, the portion of a T-mesh to be refined is chosen to be as follows: it creates a partition of some domain into cells of a tensor-product mesh. The partition of this domain into cells is of restricted configuration and the constraint on configuration will be given in terms of offset region and curve, which have been recently introduced by Giannelli and Jüttler [START_REF] Giannelli | Bases and dimensions of bivariate hierarchical tensor-product splines[END_REF]. We will determine the ordering of the line-segments to be inserted at each iteration step and give the construction of spline basis functions. This strategy provides framework in which the concept of consistent hierarchical T-meshes is feasible. We will show that particular classes of consistent hierarchical Tmeshes [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF] can be obtained by applying this strategy.

Overall, this paper is in the scope of the methods and tools introduced in [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF], [START_REF] Giannelli | Bases and dimensions of bivariate hierarchical tensor-product splines[END_REF] and [START_REF] Mourrain | On the dimension of spline spaces on planar T-meshes[END_REF], and as a consequence the results presented can be considered as an extension of the construction of classical hierarchical Bsplines originally introduced in [START_REF] Kraft | Adaptive und linear unabhängige multilevel B-splines und ihre Anwendungen[END_REF].

The rest of this paper is organized as follows. In Section 2 we provide the background needed to explain our strategy, which we then introduce at the beginning of Section 3. We describe the required ordering of line-segments and the construction of spline basis functions for splines of degrees 2 and 3 in Subsections 3.1 and 3.2 respectively. We make necessary remarks and discuss the relevant modifications of our strategy in Subsection 3.3. We conclude the paper in Section 4.

Preliminaries

A T-mesh T is formed by a set of horizontal and vertical line-segments that creates a partition of a closed domain Ω into axis-aligned boxes, called the cells of the T-mesh, in which T-junctions are allowed [START_REF] Deng | Dimension of spline spaces over T-meshes[END_REF]. We do not assume that the boundary ∂Ω of Ω is rectangular. However, we assume that a T-mesh T is regular (see [START_REF] Schumaker | Approximation power of polynomial splines on T-meshes[END_REF], Definition 2.2); or, in other words, we assume that the boundary ∂Ω, which is a collection of piecewise-linear curves, is free of self-intersections. A maximal segment of a T-mesh is the longest possible line-segment that can be constructed from several collinear edges; in Fig. 1 2.1. Spline space with highest order smoothness over a T-mesh and smoothing cofactor method In Subsection 2.1 we will state the results that will be used in analysis of spline space with highest order smoothness defined as follows.

Definition 1 ([15]). Let S(m, m, m -1, m -1)(T ) be a space of functions f (x, y) of class C m-1,m-1 (Ω) which are polynomials of bi-degree (m, m) in x and y, defined in each cell of a T-mesh T .

To analyze the dimension and basis functions of a space S(m, m, m -1, m -1)(T ), we follow the smoothing cofactor method [START_REF] Li | On the instability in the dimension of splines spaces over T-meshes[END_REF][START_REF] Huang | New proof of dimension formula of spline spaces over T-meshes via smoothing cofactors[END_REF][START_REF] Li | Improvement on the dimension of spline spaces on T-mesh[END_REF].

For a given element f (x, y) ∈ S(m, m, m -1, m -1)(T ) and inner vertex v(x 0 , y 0 ), the conformality factor k v is defined as follows. Suppose that the bivariate function f (x, y) is respectively equal to the polynomials P 1 (x, y), P 2 (x, y), P 3 (x, y), P 4 (x, y) in each of four cells which form a neighborhood of v(x 0 , y 0 ) (see Fig. 2). In the case of T-junction the corresponding polynomials are supposed to be the same. Provided that the function f (x, y) is of class C m-1 with respect to x and y, the following equalities hold:

P 2 -P 1 = λ 1,2 (x)(y -y 0 ) m , (1)
P 3 -P 2 = λ 2,3 (y)(x -x 0 ) m , (2)
P 4 -P 3 = λ 3,4 (x)(y -y 0 ) m , (3)
P 1 -P 4 = λ 4,1 (y)(x -x 0 ) m , (4)
for some univariate polynomials λ 1,2 (x), λ 2,3 (y), λ 3,4 (x) and λ 4,1 (y) of degree m. From equations (1) to (4), we can assert:

P 2 -P 1 + P 4 -P 3 = (λ 1,2 (x) + λ 3,4 (x))(y -y 0 ) m = -(λ 2,3 (y) + λ 4,1 (y))(x -x 0 ) m . (5)
Thus, for some constant k v we obtain:

λ 1,2 (x) + λ 3,4 (x) = k v (x -x 0 ) m , λ 2,3 (y) + λ 4,1 (y) = -k v (y -y 0 ) m . (6)
In addition, the constant k v can be represented in terms of the derivatives on the left-hand side of (5). Indeed, from ( 5) and ( 6) we can obtain the following representation for k v :

k v = 1 (m!) 2 ∂ 2m (P 2 (x, y) + P 4 (x, y) -P 1 (x, y) -P 3 (x, y)) ∂x m ∂y m | x=x 0 ,y=y 0 . ( 7
)
This means that k v is uniquely defined for a given f ∈ S(m, m, m -1, m -1)(T ) and inner vertex v.

Suppose that E is a maximal horizontal interior segment with endpoints at the vertices v 1 , v n , and at the inner vertices v 2 , . . . , v n-1 (see Fig. 3). For a given function f ∈ S(m, m, m -1, m -1)(T ), let P ij (x, y), i = 1 . . . n, j = 1 . . . 4 denote the polynomials that correspond to the vertices v i , following Fig. 2. We can then note the following relation:

n i=1 P i2 -P i1 + P i4 -P i3 = 0. ( 8
)
From equations ( 5),( 6) and (8), we obtain the zero identity:

n i=1 k v i (x -x i ) m ≡ 0, (9)
where x i , i = 1 . . . n is the x-coordinate of the vertex v i . This identity ( 9) is equivalent to the following linear system in terms of the conformality factors

k v i , i = 1 . . . n:          n i=1 k i = 0, n i=1 k i x i = 0, . . . n i=1 k i x m i = 0. ( 10
)
An analogous linear system for a maximal vertical interior segment can be derived:

         n i=1 k i = 0, n i=1 k i y i = 0, . . . n i=1 k i y m i = 0. ( 11
)
Definition 2 ( [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF]). For a given T-mesh T , let v 1 , . . . , v N be vertices of T belonging to maximal interior segments of T . The conformality vector space W [T ] is the space of conformality factors k v 1 , . . . , k v N which satisfy the linear systems [START_REF] Forsey | Hierarchical B-spline refinement[END_REF] and [START_REF] Kraft | Adaptive und linear unabhängige multilevel B-splines und ihre Anwendungen[END_REF] for all horizontal and vertical maximal interior segments.

Note that, unlike the similar definition given elsewhere [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF][START_REF] Wu | Hierarchical bases of spline spaces with highest order smoothness over hierarchical T-subdivisions[END_REF], this does not involve the conformality factors of boundary vertices.

Thus, by virtue of ( 10) and [START_REF] Kraft | Adaptive und linear unabhängige multilevel B-splines und ihre Anwendungen[END_REF], and using the direct formula [START_REF] Li | On linear independence of the T-spline blending functions[END_REF], it is possible to define a linear map correctly [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF][START_REF] Wu | Hierarchical bases of spline spaces with highest order smoothness over hierarchical T-subdivisions[END_REF]:

K : S(m, m, m -1, m -1)(T ) -→ W [T ]. ( 12
)
The definition of a conformal vector space in the univariate case is the following:

Definition 3 ([22]
). Given a univariate knot vector (x 1 , . . . , x n ) without repeated knots, and the corresponding line-segment E = [x 1 , x n ], W [E] is the space of conformality factors k 1 , . . . , k n which satisfy the linear system [START_REF] Forsey | Hierarchical B-spline refinement[END_REF].

Note that the space W [E] is isomorphic to the space of functions of the class C m-1 which are polynomials of degree m within each segment [x j , x j+1 ], j = 1 . . . n-1 and identically zero outside the segment E = [x 1 , x n ]; following previous authors [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF][START_REF] Wu | Hierarchical bases of spline spaces with highest order smoothness over hierarchical T-subdivisions[END_REF], we call this space S(m, m -1)(E). If we further suppose that f (x) ∈ S(m, m -1)(E) such that f (x) = P j (x), when x ∈ [x j , x j+1 ], j = 1. . . n -1 and f ≡ 0, for x ∈ R\[x 1 , x n ]. Since f (x) is of class C m-1 , we can write

P 1 -0 = k 1 (x -x 1 ) m , P 2 -P 1 = k 2 (x -x 2 ) m , . . . , P n-1 -P n-2 = k n-1 (x -x n-1 ) m , 0 -P n-1 = k n (x -x n ) m . ( 13
)
This implies that n i=1 k i (x-x i ) m ≡ 0; and the conformality factors k 1 , . . . , k n can be obtained by solving the linear system [START_REF] Forsey | Hierarchical B-spline refinement[END_REF]. Note that dim

W [E] = n -m -1 if n > m + 1, and dim W [E] = 0 if n m + 1.

Definition 4 ([22]

). Let E be a maximal interior segment in the T-mesh T . Then we define P E : W [T ] → W [E] to be the projection that preserves the conformality factors of the vertices belonging to E. Indeed, by Definition 2, the conformality factors of the vertices of a linesegment E satisfy the system (10) for any conformality vector in W [T ]. We are ready to prove the following simple lemma: Lemma 1. For a maximal interior segment E of a given T-mesh T , let T denote the new T-mesh that is obtained from T by removing line-segment E. Assume that there is a set of functions f 1 , . . . , f l ∈ S(m, m, m -1, m -1)(T ) such that the conformality vectors P E (K(f 1 )), . . . , P E (K(f l )) form the basis of a subspace

P E (im K) ⊂ W [E], where im K ⊂ W [T ].
Then the spline space S(m, m, m -1, m -1)(T ) can be expressed as follows:

S(m, m, m -1, m -1)(T ) = S(m, m, m -1, m -1)(T ) span{f 1 , . . . , f l } Proof: The equality S(m, m, m -1, m -1)(T ) ∩ span{f 1 , . . . , f l } = 0 follows from the simple observation that P E (K(f )) = 0 for any f ∈ S(m, m, m - 1, m -1)(T ). It is then only necessary to represent the spline function f ∈ S(m, m, m-1, m-1)(T ) as the sum of a spline function g ∈ S(m, m, m- 1, m -1)(T ) and some linear combination of f 1 , . . . , f l . For a given function f ∈ S(m, m, m -1, m -1)(T ), the corresponding projection P E (K(f )) is a linear combination of P E (K(f i )), i = 1 . . . l; thus, for some c 1 , . . . , c l , the projection P E (K(f -l i=1 c i f i )) = 0. Thus the func- tion g = f -l i=1 c i f i is an element of S(m, m, m -1, m -1)(T )
. Indeed, since P E (K(g)) = 0, all the conformality factors of K(g) belonging to E are zero. Without loss of generality, we may suppose that E is the horizontal maximal interior segment that traverses the vertices v 1 , . . . , v n (see Fig. 3), and that all its conformality factors k v 1 , . . . , k vn are zero. Following Fig. 2, P ij , i = 1 . . . n, j = 1 . . . 4 are polynomials representing f in the neighborhoods of the vertices v 1 , . . . , v n respectively. Since the T-mesh T has a T-junction at the vertex v 1 , P 13 -P 14 = 0 and, by virtue of ( 5) and ( 6), P 12 -P 11 = 0, or equivalently P 23 -P 24 = 0; since k v 2 = 0, a similar argument yields P 22 -P 21 = 0. Going further, to the vertex v n , we see that g is of class C ∞ with respect to y along the whole line-segment E. Thus

g ∈ S(m, m, m -1, m -1)(T ) and f = g + l i=1 c i f i . The Lemma 1 is proved. Remark 1. Note that, if the projection P E : im K → W [E] is surjective, then span{f 1 , . . . , f l } is isomorphic to W [E].
Corollary 1. Suppose that for a given T-mesh T , there is an ordered sequence of maximal interior segments [START_REF] Vuong | A hierarchical approach to adaptive local refinement in isogeometric analysis[END_REF]. Let {f i1 , . . . , f il i } ⊂ S(m, m, m -1, m -1)(T i ), i = 1 . . . n be a set of spline functions such that the projections

E 1 ≺ • • • ≺ E n , such that successive deletion of E n • • • E 1 from the T-mesh T produces the T-mesh T 0 ; let the T-mesh T i , i = 1 . . . n -1 be obtained by successive deletion of the line-segments E n • • • E i+1 from T ; and let T n = T . Suppose that all the projections P E i : im K i → W [E i ], i = 1 . . . n are surjective, where lin- ear maps K i : S(m, m, m -1, m -1)(T i ) → W [T i ] are given by
P E i (K i (f ij )), j = 1 . . . l i form the basis of W [E i ].
Then, by virtue of Lemma 1:

S(m, m, m -1, m -1)(T ) = S(m, m, m -1, m -1)(T 0 ) n i=1 span{f i1 , . . . , f il i }. (14)
One consequence of Corollary 1 is a method of constructing basis functions of a spline space for those classes of T-meshes that satisfy the conditions of the corollary.

This approach to the construction of basis functions, provided by corollary next section we will discuss the problem of generating T-meshes to satisfy the conditions of Corollary 1, and then to construct basis functions of the corresponding spline space.

Definition 5 ([25]

). For a given ordered sequence of maximal interior segments

E 1 ≺ • • • ≺ E l , let λ(E i
) be the number of vertices of E i which are not on a maximal interior segment of index greater than i.

We will use Lemma 2 below in the proof of Lemma 4 in Subsection 3.2.

Lemma 2 ([25]

). Let T be a T-mesh on some rectangular domain. Assume that, for a given order of its maximal interior segments, the following inequality holds:

λ(E i ) m + 1,
for every maximal interior segment

E i , i = 1 . . . l. Then, dim S(m, m, m -1, m -1)(T ) = (m + 1) 2 C -m(m + 1)E 0 + m 2 V 0 , ( 15
)
where C is the number of cells, E 0 is the number of inner edges, and V 0 is the number of inner vertices of T .

W

Figure 4: A hatched domain Ω formed by the cells of a tensor-product mesh.

Offset from a domain

In Subsection 2.2 we will recall Giannelli and Jüttler's definition [START_REF] Giannelli | Bases and dimensions of bivariate hierarchical tensor-product splines[END_REF] of the offset region and curve from a domain Ω that will be necessary to describe the refinement strategy in Section 3. In addition, we will state the results that will be used in Lemmas 3 and 4 in Subsections 3.1 and 3.2, respectively.

Suppose that Ω is a domain formed by the cells of an infinite tensorproduct mesh (see Fig. 4). The offset region R k can be defined recursively as follows: an offset region R k+1 is defined to be the set of cells k j=0 R j which have at least one point in common with the boundary ∂ k j=0 R j ; the zero offset region R 0 is defined to be Ω. The offset curve from a domain Ω is the piecewise linear curve defined as follows: Definition 6 ( [START_REF] Giannelli | Bases and dimensions of bivariate hierarchical tensor-product splines[END_REF]). The offset curve C 0 at a distance 0 from a domain Ω is defined to be its boundary ∂Ω. Given the offset regions R k and R k+1 , for a nonnegative integer k, then:

1. We say that Ω admits an offset at a distance k + 1 2 if any cell in R k+1 is related to R k by one of the three connections shown in Fig. 5; then the offset curve at a distance k

+ 1 2 , written C k+ 1 2
, is a piecewise linear curve obtained by collecting together the contributions of every cell, as shown in Fig. 5. 2. We say that Ω admits an offset at a distance k + 1 if the relationship between any cell in R k+1 and R k falls into one of the three cases shown in Fig. 6; then the offset curve at a distance k + 1, written C k+1 , is the piecewise linear curve that forms the exterior boundary of R k+1 , as shown in Fig. 6.

We say that Ω does not admit an offset at a distance greater than or equal to k + 1 2 or k + 1 if the above conditions 1 or 2 respectively are not satisfied. In Definition 6 the conditions 1 or 2 respectively allow us to be sure that the offset curves C k+ 1 2 or C k+1 are free of self-intersections. Fig. 7 shows an example of the offset region R 1 from the domain Ω (shown in Fig. 4 as well) and the corresponding offset curve C1 2 (dashed red lines). Note that the definition above means that Ω in Fig. 7 does not admit an offset at a distance greater or equal than 1.

Definition 6 constraints the configuration of a domain Ω in a way which makes it relatively easy to specify the basis functions of a spline space over a T-mesh.

k R 2 1 + k C 2 1 + k C 2 1 + k C k R k R
k R 1 + k C 1 + k C 1 + k C k R k R Figure 6:
Admissible connections between a cell of the offset region R k+1 and R k : a shared corner (left), one shared side (center) and two shared sides (right). Two adjacent sides (left), one side (center) and one dot (right), which are shown as the solid portions of the green lines, must be free, where free means that the edge or the vertex belongs to the boundary of k+1 j=0 R j . The piecewise linear contributions to the offset curve resulting from each of the three admissible cases are also shown as the solid portions of the green lines, and the green dot. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.) Figure 7: The region R 1 (gray cells) is the offset region from the domain Ω; the corresponding offset curve C 1 2 is shown as red dashed lines. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.) Theorem 1 ( [START_REF] Giannelli | Bases and dimensions of bivariate hierarchical tensor-product splines[END_REF]). Let T be a T-mesh which subdivides a bounded domain Ω into cells of a tensor-product mesh (see Fig. 4). For a given integer m 2, suppose that Ω admits an offset at a distance m-1 2 . Let B be a set of tensorproduct B-splines generated from the given tensor-product mesh. Then, the following set provides the basis of the spline space S(m, m, m -1, m -1)(T ):

{τ | Ω : τ ∈ B ∧ supp τ ∩ int Ω = ∅}.
The following definition of the configuration of a domain Ω, which is the dual of Definition 6, will be used extensively in the next section. Definition 7. Let m be an integer 2. We say that a domain Ω admits an inner offset at a distance m-1 2 if its complement R 2 \ Ω admits an offset at a distance m-1 2 . We say that a domain Ω does not admit an inner offset at a distance greater than or equal to m-1 2 if its complement R 2 \ Ω does not admit an offset at a distance greater than or equal to m-1 2 . The inner offset curve of Ω at a distance m-1

2 is Cm-1 2 of R 2 \ Ω.
A condition that Ω admits an inner offset at a distance m-1 2 allows us to be sure that the inner offset curve of Ω at a distance m-1 2 is free of selfintersections. Examples of domains which admit inner offset at distances 1 2

W

Figure 9: A line-segment Ω ∩ L is shown as a red, solid line; its extension up to line L is shown as red, dashed lines. The inner offset curve at a distance 1 2 from the domain Ω for the refined tensor-product mesh is shown with green dashed lines. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.) and 1 are shown in Fig. 8, together with domains which do not admit an inner offset at distances greater than or equal to 1 2 and 1. We can make the following simple observation about a domain which admits an inner offset: Proposition 1. For a given integer m 2, suppose that a domain Ω admits an inner offset at a distance m-1 2 . Further suppose that the corresponding tensor-product mesh is refined by inserting a line L. Then, Ω admits an inner offset at a distance m-1 2 for the refined tensor-product mesh as well. Proposition 1 is illustrated, for m = 2, in Fig. 9. The following proposition plays a significant role in proving lemmas in the next section. Proposition 2. Let T be a T-mesh and Ω be a domain composed by a subset of cells of T . Suppose that the set of cells comprising Ω is a subset of cells of some tensor-product mesh. For a given integer m 2, we suppose that Ω admits an inner offset at a distance m-1 2 . Suppose further that T is refined by the line-segment E ⊂ Ω such that E is a maximal interior segment of the refined T-mesh T = T E. Then we can assert:

W

S(m, m, m -1, m -1)(T ) = S(m, m, m -1, m -1)(T ) span{f 1 , . . . , f l },
where f 1 , . . . , f l are tensor-product B-splines which have supports within the domain Ω.

Proof: Before proving Proposition 2 let us illustrate its nature, for the case m = 3, in Fig. 10. We will prove the proposition for m = 3; the proof for other positive integers m is analogous. Following Lemma 1, we need to provide tensor-product B-splines f 1 , . . . , f l ∈ S(m, m, m -1, m -1)(T ) such that a column of four adjacent cells divided by E and the corresponding linesegment V with knots (y 1 , y 2 , y 3 , y 4 , y 5 ).

P E (K(f 1
Since Ω admits an inner offset at a distance 1, then at least one of the three configurations shown in Fig. 11 must occur. Consider the following tensor-product B-spline having a support within the domain Ω (see Fig. 11):

f (x, y) = N [x 1 , x 2 , x 3 , x 4 , x 5 ](x)N [y 1 , y 2 , y 3 , y 4 , y 5 ](y); (16)
then

P E (K(f (x, y))) is a nontrivial element (k 1 , . . . , k 5 ) of the one-dimensional space of conformality factors W [V ] ⊂ W [E]
. Indeed, k i = 0, i = 1 . . . 5, because otherwise (k 1 , . . . , k 5 ) = 0 and then, as we saw in the proof of Lemma 1, f (x, y) would be of class C ∞ with respect to x along the line-segment E, which contradicts the definition of f (x, y) in [START_REF] Deng | Polynomial splines over hierarchical T-meshes[END_REF]. From this simple treatment, it is readily apparent that the conformality vectors P E (K(f i )), i = 1 . . . l for the B-splines f i , i = 1 . . . l corresponding to all rows of four con-secutive cells divided by E, form a basis of the space W [E]. Proposition 2 is proved.

Refinement strategy

We now describe general refinement strategy that satisfies the conditions introduced in Corollary 1, which allow spline basis functions to be constructed incrementally. We will concentrate on m = 2 and m = 3. However, we will start by describing the generic inductive refinement procedure. Definition 8. Let m be an integer 2. We say that a T-mesh T is of type m if it is derived from an initial T-mesh T 0 by repeating step 2 of the following algorithm from j = 0 until j = N -1 and T = T N , for some integer N 1.

1. The initial T-mesh T 0 occupies the domain Ω 0 , which is composed of the cells of a tensor-product mesh and admits an offset at a distance m-1 2 . 2. Induction from any j 0 to j + 1 proceeds as follows. For a given T-mesh T j , it is necessary to find domains Ω j ⊂ Ω j which satisfy the following assumptions: domains Ω j and Ω j are both constructed from the cells of some tensor-product mesh, such that each cell in Ω j is also a cell of the T-mesh T j ; and Ω j admits an inner offset at a distance m-1 2 . The refined T-mesh T j+1 is derived from T j by dividing each cell of the domain Ω j following the rule illustrated in Fig. 12, such that the line-segments E j1 , . . . , E jn j refining T j have endpoints on ∂ Ω j . It is supposed that the line-segments E j1 , . . . , E jn j are maximal interior segments of the T-mesh T j+1 , i.e. E j1 , . . . , E jn j do not intersect with the boundary ∂Ω 0 . A step 2 for an iteration from j to j + 1 for m = 3 is shown in Fig. 13. The examples of realization of the refinement strategy are demonstrated in Remarks 2 and 3 below for the cases m = 2 and m = 3, respectively.

Since Ω 0 admits an offset at a distance m-1 2 , the basis functions of a spline space S(m, m, m -1, m -1)(T 0 ) can always be obtained using Theorem 1. In order to show that a T-mesh T of type m satisfies the the conditions of Corollary 1, we only need to prove that the induction step (step 2 in the refinement strategy above) satisfies those conditions. We start with the case m = 2. j W j W Figure 13: The boundary of Ω j is shown in green; the boundary of Ω j is blue; and the line-segments E j1 , . . . , E jnj are red. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

The case m = 2

Let T = T N be a T-mesh of type 2 for some integer N 1 (see Definition 8). We consider the induction step from T j to T j+1 , for a given 0 j N -1, such that T j+1 is derived from T j by refining with maximal interior segments E j1 , . . . , E jn j , in compliance with step 2 of the algorithm in Definition 8. For a given order of the line-segments E j1 ≺ • • • ≺ E jn j , the T-mesh T ji , 1 i n j is derived from T j by successive introduction of the line-segments E j1 , . . . , E ji ; in particular, T jn j = T j+1 .

In the following lemma we omit the index j to simplify the notations, observing that the proof is the same for any 0 j N -1; thus T i corresponds to T ji , E i to E ji , Ω and Ω to Ω j and Ω j respectively. In formulating the basis functions, we will presume that the cells of the domain Ω are of the same size and any line-segment that divides a cell of the domain Ω connects the mid-points of opposite edges of that cell. Lemma 3. There exists an ordered sequence of maximal interior segments

E 1 ≺ • • • ≺ E n which refine T 0 such that the projections P E i : W [T i ] → W [E i ]
are surjective for all i = 1 . . . n, so for any i = 1 . . . n there is a set of spline functions {f i1 , . . . [START_REF] Vuong | A hierarchical approach to adaptive local refinement in isogeometric analysis[END_REF]. Moreover, these spline functions can be chosen such that their supports are contained within Ω.

f il i } ⊂ S(2, 2, 1, 1)(T i ), such that {P E i (K i (f i1 )), . . . , P E i (K i (f il i ))} forms a basis of W [E i ], where K i : S(2, 2, 1, 1)(T i ) → W [T i ] is given in
Proof. The proof could be found in Section 5.

Remark 2. Wu et al. [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF] describe a special classes T m,m of hierarchical Tmeshes. If m = 2, then T 2,2 is the ordinary class of crosswise hierarchical Tmeshes with a level structure, which is the same to one used for PHT-splines [START_REF] Deng | Polynomial splines over hierarchical T-meshes[END_REF]. The following procedure, shown in Fig. 14, can be used to generate a Tmesh of class T 2,2 . We begin with a tensor-product mesh over a rectangular domain (the cells of this mesh are defined to be of level 0). In order to generate a cell at level j + 1, a cell at level j must be subdivided into four subcells (which are defined to be at level j + 1). A cell is divided by two line-segments connecting the mid-points of opposite edges.

We observe that a hierarchical T-mesh of class T 2,2 is of type 2, following Definition 8. Let T be a hierarchical T-mesh of class T 2,2 . The domain Ω j , which is to be divided to obtain cells at level j + 1, is composed of cells at level j. We create a domain Ω j ⊃ Ω j by unifying all the cells at level j. If j 1, then the construction of T means that Ω j is composed of 2 × 2 blocks of cells at level j (each corresponding to a single cell at level j -1). In order to prove that Ω j admits an inner offset at a distance 1 2 , we need to show that R 2 \ Ω j admits an offset at a distance 1 2 . The domain R 2 \ Ω j is also composed of 2 × 2 blocks of cells. It is apparent that the cells from the offset region R 1 of a domain R 2 \ Ω j are related to R 2 \ Ω j through the connections shown in Fig. 5. This observation implies that R 2 \ Ω j admits an offset at a distance 1 2 . If j = 0, then it suffices to suppose that the original tensor-product mesh extends at least 2 cells in both coordinate directions to guarantee that Ω 0 admits an inner offset at a distance 1 2 . We assume that the cells at level 0 having common edges with the boundary of T are not divided, i.e. starting at level 1, all introduced line-segments will be maximal interior segments of T . Thus, by Definition 8, T is of type 2. The spline basis functions of S(2, 2, 1, 1)(T ) can be obtained by Lemma 3.

The case m = 3

Let T = T N be a T-mesh of type 3 for some integer N 1 (see Definition 8). As we did in the previous subsection, we will consider the induction step from T j to T j+1 , for a given 0 j N -1, which allows us to derive T j+1 from T j by refining the T-mesh T j by introducing maximal interior segments E j1 , . . . , E jn j , as we did in step 2 of the algorithm in Definition 8. For a given ordering of the line-segments E j1 ≺ • • • ≺ E jn j , the T-mesh T ji , 1 i n j can be derived from T j through the consistent refinement by the line-segments E j1 , . . . , E ji ; in particular, T jn j = T j+1 .

In the following lemma we will omit the index j. In addition, we will suppose that the cells of the domain Ω are of the same size and any linesegment that divides a cell of the domain Ω connects the mid-points of opposite edges of that cell, as we did in Lemma 3. Lemma 4. There exists an ordered sequence of maximal interior segments

E 1 ≺ • • • ≺ E n which refine T 0 such that the projections P E i : W [T i ] → W [E i ]
are surjective for all i = 1 . . . n, so for any i = 1 . . . n there is a set of spline functions {f i1 , . . . [START_REF] Vuong | A hierarchical approach to adaptive local refinement in isogeometric analysis[END_REF]. Moreover, these spline functions can be chosen such that their supports are contained within Ω.

f il i } ⊂ S(3, 3, 2, 2)(T i ) such that {P E i (K i (f i1 )), . . . , P E i (K i (f il i ))} forms a basis of W [E i ], where K i : S(3, 3, 2, 2)(T i ) → W [T i ] is given in
Proof. The proof could be found in Section 6.

Remark 3. Let us briefly revisit the construction of T-meshes of class T 3,3 , as described by Wu et al. [START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF], and illustrated in Fig. 15. Their procedure starts with a tensor-product mesh over a rectangular domain (containing cells that are defined to be at level 0). In order to generate a cell at level j + 1, one has to subdivide a quad of four neighboring cells at level j into sixteen subcells (which are defined to be at level j + 1). Any two 2 × 2 blocks of cells at level j which are to be subdivided must either have two common boundary edges, one common boundary vertex, or no common vertices. It must also be assumed that each cell is subdivided by two straight lines connecting the mid-points of the two opposite edges. We see from Definition 8 that a hierarchical T-mesh of class T 3,3 is of type 3. Let T be a hierarchical T-mesh of class T 3,3 . The domain Ω j , which is to be divided to obtain cells at level j + 1, is composed of 2 × 2 blocks of cells at level j. We can create a domain Ω j ⊃ Ω j by unifying all the cells at level j. If j 1, then, because of the way in which T was constructed, Ω j is composed of 4 × 4 blocks at level j (originally the 2 × 2 blocks at level j -1). In order to prove that Ω j admits an inner offset at a distance 1, we need to show that R 2 \Ω j admits an offset at a distance 1. The domain R 2 \Ω j is also composed of 4 × 4 blocks of cells. It is apparent that the cells from the offset region R 1 of a domain R 2 \ Ω j are related to R 2 \ Ω j through the connections shown in Fig. 6. This observation implies that R 2 \ Ω j admits an offset at a distance 1. If j = 0, then it suffices to suppose that the original tensorproduct mesh has at least 3 cells in both coordinate directions to guarantee that Ω 0 admits an inner offset at a distance 1. We assume that the cells at level 0 having common edges with the boundary of T are not divided, i.e. starting at level 1, all introduced line-segments will be maximal interior segments of T . Thus, by Definition 8, T is of type 3. From Lemma 4 we have that for the T-mesh T , the line-segments, which are used to divide the cells of level j, may be arranged in the following simple way. The line-segments of length 4 need not be ordered. Then, the remaining line-segments, which are of length 2, may also be ordered arbitrarily, except for isolated quads (see Fig. 22, right), which can simply be ordered in a clockwise direction. The spline basis functions of S(3, 3, 2, 2)(T ) can be obtained by Lemma 4.

Some necessary remarks on a modification of the refinement strategy

From the proof of Lemma 4, we see that spline basis functions can be obtained; but, for example, this may involve the sophisticated construction shown in Fig. 21 (center). It is more practical to use configurations in which the line-segments can be ordered in a simple or even arbitrary way. From this point of view, it is reasonable to assume that all maximal interior segments are of length m. This latter assumption ensures us that the corresponding T-mesh is regular, defined as in Mourrain [START_REF] Mourrain | On the dimension of spline spaces on planar T-meshes[END_REF]; in particular, it satisfies the conditions of Lemma 2 and the dimension dim S(m, m, m -1, m -1)(T ) can be obtained trough the formula [START_REF] Deng | Dimension of spline spaces over T-meshes[END_REF].

This assumption enables us to order the line-segments within a step 2 of the refinement strategy in arbitrary way. Moreover, it enables us not to assume that the line-segments E j1 , . . . , E jn j refining T j have endpoints on ∂ Ω j . In addition, we do not need to assume that each cell of Ω j is divided following the rule illustrated in Fig. 12; we may admit that a cell of Ω j is divided by several line-segments in both directions. A step 2 of this modified refinement strategy is illustrated in Fig. 16. From the proofs of Lemmas 3 and 4 we see that the spline basis functions are tensor-product B-splines except probably those which correspond to the line-segments intersecting in vertices that are close enough to the boundary ∂Ω j . In order to guarantee that all the spline basis functions are tensor-product B-splines, we need to extend the line-segments intersecting in each vertex Z, for which f Z cannot be represented as a tensor-product B-spline, until the boundary of a domain Ω Z (see eg. Fig. 20). The domain Ω j is composed of all the black cells. This configuration is suitable for m = 2 and m = 3, because Ω j admits an inner offset at a distance 1 and all red line-segments are of length 3. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Conclusions

We have described an iterative strategy for generating consistent hierarchical T-meshes. It is based on the concept of a domain of restricted configuration, which is composed of the cells of a tensor-product mesh, and which is divided in successive steps. We have described the required ordering of line-segments during refinement, and the construction of basis functions for splines of degree 2 and 3.

We have shown that hierarchical T-meshes of classes T 2,2 and T 3,3 are produced by this strategy for degrees 2 and 3 respectively. We have described the relevant modifications of our strategy which substantially simplify the ordering of line-segments and the corresponding construction of basis functions.

The concept of consistent hierarchical T-meshes is promising for applications as long as they allow local refinement and offer a simple way for describing spline basis functions. Our iterative strategy provides feasible framework for generating consistent hierarchical T-meshes. We believe that the results of this paper might help in selection and processing of possible implementations of consistent hierarchical T-meshes. In our future work we intend to propose analogues of consistent hierarchical T-meshes for trivariate case and offer a strategy for generating of such meshes.

Appendix A

In this appendix we will give the proof of Lemma 3. Proof. Given a maximal interior segment E ∈ {E 1 , . . . , E n }, let L(E) denote the number of cells of Ω ⊂ Ω that are divided by the line-segment E; we will call L(E) the length of E. An admissible ordering of the linesegments E 1 , . . . , E n can be obtained quite simply by ensuring that all the line-segments of length 2 precede those of length 1.

However, this issue is more easily understood if we arrange the linesegments E 1 , . . . , E n as follows. Let E 1 ≺ • • • ≺ E k 1 be all the vertical line-segments of length 2, ordered from left to right; similarly let

E k 1 +1 ≺ • • • ≺ E k 2 be
all the horizontal line-segments of length 2, ordered from bottom to top. The remaining line-segments E k 2 +1 ≺ • • • ≺ E n of length 1 do not need to be ordered.

Since Ω admits an inner offset at a distance 1 2 , the lemma statement above applies to the line-segments

E 1 ≺ • • • ≺ E k 1 as a direct consequence of Proposition 2.
For a given horizontal line-segment E i , k 1 + 1 i k 2 , let Z be the location of the intersection with a vertical line-segment E j , j k 1 . Consider two short subsegments H from E i and V from E j length 2, which intersect at Z; such subsegments always exist because L(E i ), L(E j ) 2. Since Ω admits an inner offset at a distance 1 2 , one of the two configurations of cells shown in Fig. 17 projections under the map P E i • K i that form the basis of the space W [E i ]; moreover, because of the way they are constructed, these functions have supports within the domain Ω. There is nothing to prove for the remained line-segments

E k 2 +1 ≺ • • • ≺ E n , because W [E i ] = 0 for any k 2 + 1 i n.
Thus, Lemma 3 is proved.

Appendix B

In this appendix we will give the proof of Lemma 4. Proof. As we did in the proof of Lemma 3, we arrange the line-segments

E 1 ≺ • • • ≺ E n in order of their lengths L(E i ), i = 1 . . . n. Line-segments of length
3 can be arranged in an arbitrary way; but we will suppose that

E 1 ≺ • • • ≺ E k 1 are all the vertical line-segments of length 3, arranged from left to right. Similarly, E k 1 +1 ≺ • • • ≺ E k 2 are
all the horizontal linesegments of length 3, arranged from bottom to top. The required ordering for line-segments of length 2 will be specified later.

Since Ω admits an inner offset at a distance 1, the lemma statement above applies to the line-segments

E 1 ≺ • • • ≺ E k 1 as a direct consequence of Proposition 2.
Let Z be the vertex at which a horizontal line-segment E i , k 1 +1 i k 2 intersects with a vertical line-segment E j , which has index j k 1 . We will suppose that Z is not inside the leftmost or the rightmost cell divided by the horizontal line-segment E i . Consider two short subsegments, H from E i and V from E j , both of length 3, which intersect at Z, such that the cell that contain Z is the middle cell divided by H.

Let Ω Z be the possible minimal domain composed of cells from domain Ω, which contains subsegments H and V , and admits an inner offset at a distance 1. The possible configurations of the domain Ω Z are shown in Fig. 18 and 20 (left). For spline function f Z corresponding to the configuration in Fig. 20 (left) is:

f Z (x, y) = N [x 1 , x 2 , x 3 , x 4 , x 5 ](x)N [y 2 , y 3 , y 4 , y 5 , y 6 ](y)+ 3 5 N [x 2 , x 3 , x 4 , x 5 , x 6 ](x)N [y 2 , y 3 , y 4 , y 5 , y 6 ](y)+ 3 5 N [x 1 , x 2 , x 3 , x 4 , x 5 ](x)N [y 1 , y 2 , y 3 , y 4 , y 5 ](y). ( 19
)
This function is defined in the space S(3, 3, 2, 2)(T i ) because functions: are all of class C ∞ at the points x 4 and y 3 , with respect to x and y respectively.

N [x 1 , x 2 , x 3 , x 4 , x 5 ](x) + 3 5 N [x 2 , x 3 , x 4 , x 5 , x 6 ](x),
We will now suppose that the vertex Z is inside either the leftmost or the rightmost cell divided by the horizontal line-segment E i . Again H and V are subsegments, both of length 3, of E i and E j respectively, which intersect at Z. The possible configurations of the domain Ω Z are shown in the Fig. 19 and Fig. 20 (right). The spline function f Z corresponding to the configuration in the Fig. 20 (right) is:

f Z (x, y) = -N [x 1 , x 2 , x 3 , x 4 , x 5 ](x)N [y 3 ,
) 20
This function is in the space S(3, 3, 2, 2)(T i ) because the functions For the sake of brevity, we will not provide formulas for the spline function f Z ∈ S(3, 3, 2, 2)(T i ) for all possible configurations of the domain Ω Z (these configurations are shown in Figs. 18 and19). However, we will prove that the function f Z exists by means of the following simple consideration. We extend the subsegments H and V inside Ω Z until they meet the boundary ∂Ω Z ; let H and V denote the extended line-segments. Further, let R denote some tensor-product mesh over a rectangular domain, such that each cell of Ω Z is a cell of R , and the boundary ∂Ω Z has no common edges with the boundary of R . Applying Lemma 2 to the T-mesh R = R H V , we find that dim S(3, 3, 2, 2)(R) = dim S(3, 3, 2, 2)(R ) + 1 (Deploying Lemma 2 to deal with such a simple case is like using a steam-hammer to crack a nut; but it wide come into its own when we arrive at a more complicated construction shortly).

N [x 1 , x 2 , x 3 , x 4 , x 5 ](x) -N [x 3 , x 4 , x 5 , x 6 , x 7 ](x), N [y 1 , y 2 ,
Let R denote the T-mesh R H V . Applying Proposition 1 and 2 to refine R using the subsegments H and V , we obtain S We can now see how to order the line-segments E k 2 +1 ≺ • • • ≺ E k 3 of length 2, from the following observation. Since the line-segments E 1 , . . . , E n refining T 0 have endpoints on ∂ Ω, the set of line-segments of length 2 can be decomposed into chains of three types. A chain of the first type connects two (possibly identical) line-segments of length 3 (see Fig. 21). A chain of the second type intersects with a line-segment of length 3 at just one vertex

11 bFigure 1 :

 111 Figure 1: Example of a T-mesh.

  the line-segments b 4 b 6 , b 2 b 10 are maximal. A maximal interior segment is a maximal segment that does not intersect with the boundary ∂Ω; in Fig.1 v 3 v 4 and v 2 v 5 are maximal interior segments.

Figure 2 :

 2 Figure 2: Four cells adjacent to the vertex v.

Figure 3 :

 3 Figure 3: The maximal interior segment E. The vertical dashed lines mean that these are T-junctions at the points v 3 and v 4 .

Figure 5 :

 5 Figure 5: Admissible connections between a cell of the offset region R k+1 and R k : a shared corner (left), one shared side (center) and two shared sides (right). The piecewise linear contributions to the offset curve resulting from each of the three cases are the solid portions of the red lines. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Figure 8 :

 8 Figure 8: Domains which admit inner offset at distances 1 2 and 1 are shown at the top left and right respectively; domains which do not admit inner offset at distances grater than or equal to 1 2 and 1 are shown at the bottom left and right respectively. The inner offset curves are the red dashed lines and self-intersections are red dots. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.

Figure 10 :

 10 Figure 10: The line-segment E is shown as a red line; the inner offset curve at a distance 1 from the domain Ω is shown as green dashed lines. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

4 yFigure 11 :

 411 Figure 11: The cells of the domain Ω are shown in black, and line-segment V is the red line. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Figure 12 :

 12 Figure 12: Three types of subdivision of a cell: horizontal (left), vertical (center), and crosswise (right). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Figure 14 :

 14 Figure 14: Generation of a hierarchical T-mesh of class T 2,2 starts with a tensor-product mesh over a rectangular domain (left); 3 cells at level 0 are subdivided by the red linesegments into 12 cells at level 1 (center); 6 cells at level 1 are subdivided by the green line-segments into 24 cells at level 2 (right). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Figure 15 :

 15 Figure 15: The generation of a hierarchical T-mesh of class T 3,3 starts with a tensorproduct mesh over a rectangular domain (left); 3 quads of cells at level 0 are subdivided by the red line-segments into 48 cells at level 1 (center); 4 quads of cells at level 1 are subdivided by the green line-segments into 64 cells at level 2 (right). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

  j

Figure 16 :

 16 Figure16: The domain Ω j is composed of the black cells crossed by red line-segments. The domain Ω j is composed of all the black cells. This configuration is suitable for m = 2 and m = 3, because Ω j admits an inner offset at a distance 1 and all red line-segments are of length 3. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

  must occur.

4 yFigure 17 :

 417 Figure17:The subsegments H and V are drawn in red, and their possible extensions are shown dashed; the black cells belong to the domain Ω. In both the left and right configurations, the H has the endpoints (x 1 , y 3 ) and (x 4 , y 3 ), and the endpoints of V are (x 3 , y 1 ) and (x 3 , y 4 ). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

3 5 N

 35 [y 1 , y 2 , y 3 , y 4 , y 5 ](y) + N [y 2 , y 3 , y 4 , y 5 , y 6 ](y)

  y 3 , y 4 , y 5 ](y) -N [y 3 , y 4 , y 5 , y 6 , y 7 ](y) are all of class C ∞ at the points x 4 and y 4 , with respect to x and y respectively.

  [START_REF] Sederberg | T-splines and T-NURCCS[END_REF][START_REF] Sederberg | T-splines and T-NURCCS[END_REF][START_REF] Cottrell | Isogeometric Analysis: Toward Integration of CAD and FEA[END_REF][START_REF] Cottrell | Isogeometric Analysis: Toward Integration of CAD and FEA[END_REF]( R) = S(3, 3, 2, 2)(R ) span{f 1 , . . . , f l }, where f 1 , . . . , f l are tensor-product B-splines that have supports within the domain Ω Z . Since S(3, 3, 2, 2)(R )⊂ S(3, 3, 2, 2)(R) ⊂ S(3, 3, 2, 2)( R), an appropriate spline function f Z ∈ S(3, 3, 2, 2)(R) (such that S(3, 3, 2, 2)(R) = S(3, 3, 2, 2)(R ) span{f Z }) can be obtained by taking a linear combination of f 1 , . . . , f l , which will have support within the domain Ω Z . Thus the existence of a function f Z for the subsegments H ⊂ E i , V ⊂ E j and H V = {Z} is proved. By exactly the same arguments as we used in Lemma 3, we extend this lemma to all the line-segmentsE k 1 +1 ≺ • • • ≺ E k 2 .

Figure 18 :Figure 19 :

 1819 Figure 18: The black cells form the domain Ω Z ⊂ Ω; subsegments H and V are shown in red. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

Figure 20 :Figure 21 :Figure 22 :

 202122 Figure 20: The black cells form the domain Ω Z ⊂ Ω; subsegments H and V are shown in red with possible extensions shown as dashed lines. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)

  y 4 , y 5 , y 6 , y 7 ](y)+ +N [x 3 , x 4 , x 5 , x 6 , x 7 ](x)N [y 3 , y 4 , y 5 , y 6 , y 7 ](y)+ +N [x 1 , x 2 , x 3 , x 4 , x 5 ](x)N [y 1 , y 2 , y 3 , y 4 , y 5 ](y).

	(

but originally introduced by Wu et al.[START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF], has been formulated[START_REF] Wu | Hierarchical bases of spline spaces with highest order smoothness over hierarchical T-subdivisions[END_REF] there in terms of ordered sequence of edges, rather than maximal interior segments. But in demonstrating their concept of consistent hierarchical T-meshes, Wu et al.[START_REF] Wu | Hierarchical bases of spline spaces with highest order smoothness over hierarchical T-subdivisions[END_REF] refer only to a particular class of hierarchical T-meshes[START_REF] Wu | Dimension of spline spaces with highest order smoothness over hierarchical T-meshes[END_REF]. In the

Acknowledgment This research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST)(No. 2012-00005043) and partially funded by the Ministry of Knowledge Economy (MKE, Korea) (No. 10035474). Durkbin Cho was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (No. 2012-R1A1A1006109).

We can now obtain a spline function f Z (x, y) ∈ S(2, 2, 1, 1)(T i ), using one of two formulas, depending on which of the configurations shown in Fig. 17 actually occurs. For the first configuration, on the left in Fig. 17, the function f Z (x, y) is defined as follows:

and for the second configuration, on the right in Fig. 17, as follows:

This latter function is defined in the space S(2, 2, 1, 1)(T i ), because the functions:

are all of class C ∞ at the points x 3 and y 3 , with respect to x and y respectively. The conformality factor k Z for the vertex Z, corresponding to the function f Z (x, y), is nonzero. Indeed, proving this by contradiction, if we suppose that k Z = 0, then the conformality factors for the vertices on the line-segments H and V are zero (because only three knots remain on H and three on V ), and the function f Z (x, y) is of class C ∞ with respect to x and y along the line-segments V and H respectively using similar reasoning to Lemma 1, which contradicts formulas ( 17) and [START_REF] Nguyen-Thanh | Isogeometric analysis using polynomial splines over hierarchical T-meshes for two-dimensional elastic solids[END_REF]. Let U i denote the set of vertices in line-segment E i , such that each element of U i is an intersection of E i with a vertical line-segment E j , j k 1 . Thus, for any vertex Z ∈ U i , there is a spline function f Z ∈ S(2, 2, 1, 1)(T i ), such that the corresponding conformality factor k Z = 0; and k Z = 0 for any other vertex Z ∈ U i , Z = Z. Let E i denote the line-segment which is obtained from E i by eliminating vertices belonging to the set U i . By virtue of Proposition 2, there are

is defined by ( 12)) forms a basis of the space W [ E i ]. Thus, there are


Jérôme Molimard
email: molimard@emse.fr

Tristan Delettraz
email: tristan.delettraz@etu.mines-stetienne.fr

Etienne Ojardias
email: etienne.ojardias@chu-st-etienne.fr

Development of a miniaturized motion sensor for tracking warning signs of low-back pain

Keywords: Low-back pain (LBP), Inertial measurement unit (IMU), Hip & shoulder dissociation, Lumbar lordosis angle, measuring device

Low-back pain (LBP) is a widespread disease which can also be highly disabling, but physicians lack of basic understanding and diagnosis tools. During this study, we have designed and built a new wearable device capable of detecting features helpful in LBP follow-up while being non-invasive. The device has been carefully validated, and shows good metrological features, with small noise level (σ = 1°) and n ) and no observable drift. Two simple exercises were proposed to two young volunteers, one of them with LBP history. These exercises are designed to target two characteristics: the lumbar lordosis angle and the hip & shoulder dissociation. Even if no general rules can be extracted from this study, we have shown that Inertial Measurement Units (IMU) are able to pick up those characteristics and the obtained values are meaningful refereeing to LBP disease. Henceforth, we are confident in going to clinical studies to investigate the link between back related feature and LBP, in particular the hip & shoulder dissociation which is poorly documented.

1.

INTRODUCTION

Low-back pain (LBP) is a widespread affliction in most developed and industrialized countries. It is a major disability factor both at work and in everyday life [START_REF] Bauer | The effect of muscle fatigue and low back pain on lumbar movement variability and complexity[END_REF]. Worldwide, it is the most reported reason for seeking care from a primary care physician [START_REF] Traeger | Diagnosis and management of low-back pain in primary care[END_REF]. LBP is accountable for the most sick leaves and it touches 70% of people at least once in his/her life [START_REF] Koes | Diagnosis and treatment of low back pain[END_REF]. Therefore, it costs the French government more than one billion euros each year [START_REF] Depont | Medical and non-medical direct costs of chronic low back pain in patients consulting primary care physicians in France[END_REF]. LBP care is difficult since about 90% of all patients suffer "non-specific low-back pain" which means that while the pain is apparent, its cause remains unknown [START_REF] Koes | Diagnosis and treatment of low back pain[END_REF]. Furthermore, 73% of patients experiencing LBP will go through an other episode within a year [START_REF] Koes | Diagnosis and treatment of low back pain[END_REF] which will usually be more painful than the last one [START_REF] Riihimäki | Low-back pain, its origin and risk indicators[END_REF].

Hence, a lot of scientific studies have been made in order to find a way to better monitor the condition of patients afflicted by LBP, among them the lumbar lordosis angle [START_REF] Evcik | Lumbar lordosis in acute and chronic low back pain patients[END_REF]. Likewise, since people afflicted by LBP may have trouble performing normal muscle activities, like bending their back sideways. The detection and quantification of some abnormal minute back movements, like the hip & shoulder dissociation [START_REF] Park | Factors affecting shoulder-pelvic integration during axial trunk rotation in subjects with recurrent low back pain[END_REF], could establish a new method to label the beginning of a serious illness. Both subjects generated great interest in the medical community [START_REF] Baek | Posture monitoring system for context awareness in mobile computing[END_REF].

Many methods to monitor those characteristics have been put forward.

For instance, Electromyography (EMG) is the most popular technique for muscle activity observation. EMGs can measure various movements at a high rate, with almost no added weight. Their most commonly reported drawbacks are the difficulties to set up the device and its sensors need to by applied sometimes invasively under the skin of the patient [START_REF] Butler | Directed attention alters the temporal activation patterns of back extensors during trunk flexion-extension in individuals with chronic low back pain[END_REF]. Moreover, the results given by EMG still need to be processed to get the desired displacement or angle.

A popular alternative solution is the use of optical motion capture system. Nevertheless, the high cost of the cameras and markers may be a limiting factor to its usage, as well as the fact that it can only handle movements contained in a closed and limited area [START_REF] Nakamoto | Wearable lumbar-motion monitoring device with stretchable strain sensors[END_REF].

Recently, strain sensors were successfully used to monitor lumbar motion. They also can be made wearable, unlike the previous two techniques. Besides, they are lightweight and inexpensive, which reinforce their portability [START_REF] Nakamoto | Wearable lumbar-motion monitoring device with stretchable strain sensors[END_REF]. But their usage still is limited in space and along one plane only. At the moment, an application to accurately measure movements of the back from top to bottom along three axes is still out of reach.

Last, inertial measurement units (IMUs) are electronic devices composed of 2 or 3 sensors (3axes accelerometer, 3-axes gyroscope and optionally 3-axes magnetometer) that can report the acceleration and orientation of one object using Attitude and Heading Reference System (AHRS) algorithm. They are small and can easily be integrated in a wearable devices [START_REF] Baek | Posture monitoring system for context awareness in mobile computing[END_REF]. In addition, they can measure small motions and rotations of the back along the axes with ease [START_REF] Zhao | IMU-based gait analysis for rehabilitation assessment of patients with gait disorders[END_REF] and can be combined to tackle a larger array of movements and be more accurate [START_REF] Chhikara | Wearable device for monitoring disability associated with low back pain[END_REF]. Last, the physical values obtained from IMUs are very close to the displacements and angles that are usually sought.

Many works emphased the real time features that IMUs can provide in order to design a portable measuring device to gather data on the everyday life of an affected patient to better his treatment and warn him of unsafe positions. Recently, [START_REF] Beange | Concurrent validity of a wearable IMU for objective assessments of functional movement quality and control of the lumbar spine[END_REF] or [START_REF] Graham | Between-day reliability of IMU-derived spine control metrics in patients with low back pain[END_REF] proposed applications of IMU to monition the spine in the context of LBP.

The goal of this study is to provide physician a measuring instrument that could be used to detect and monitor back disorders. As such, the solution must be low-cost, usable in a closed environment without highly-dedicated technical skills. In the following, we will present an IMU-based solution, with detailed validation protocol, and give two first application examples on movement tracking and hip & shoulder dissociation.

MATERIAL AND METHODS

Device elements

BackMonitor is an in-house system built on the Feather M0 development board (Adafruit Industries © , New York, USA), an Arduino compatible processor that includes a Bluetooth Low Energy (BLE) module. The sensor (BNO055 Bosch Sensortec -Kusterdingen, Germany) is a 9 DOF (accelerometer, gyroscope, and magnetometer) IMU embedding an AHRS processing. Each sensor has a size of 20mm×27mm×4mm, and weights 3 g; the micro-controller board, can easily to be placed in the trousers pocket (60mm×30mm×25mm, 30g).

Metrology

In the context of low-back pain monitoring, both linear acceleration and Euler angles are useful, respectively for hip & shoulder dissociation detection and for the lumbar lordosis angle followup. Those two quantities can be directly gathered from the BNO055 (via an internal fusion algorithm).

BNO055 comes with autocalibration feature. This process is a black box that ought to be verified anyway. Acceleration can be 2-points checked easily by using gravity, but rotation must be studied in more details. Thus, a calibration protractor with IMU holder was 3D printed to set angles with an accuracy of 0.5°) and n .

The angles were measured form each sensor and in each axis between 0°) and n and 165°) and n every 5°) and n for X and Z directions and from 0°) and n to 90°) and n for Y direction according to Euler angle definition. Moreover, the board was initialized while being at 0°) and n .

Assembly

The hardware layout for the simultaneous measurement of data from two sensors is presented in Fig. 1, that shows the electronic circuit diagram.

The two BNO055s are connected to the Feather M0 Bluefruit by I2C bus. Each BNO055 has a specific address (respectively 0x29 and 0x28 from left to right) depending on its ADR pin level.

Besides, a 110 mAh battery was followed by a switch connected directly to the processor's power. It is necessary, since the goal is to conceive a portable system. A changeover diode soldered onto the board allows both the USB port and the battery to be connected without any risks as the battery acts as a backup power.

Three switches named A, B and C and a blue LED were added for the user to select the reading mode (hip & shoulder dissociation detection/lumbar lordosis angle measure, serial/BLE connection, raw / AHRS data). The sensor position along the patient's back has been set according to physicians usual practice (Fig. 2). Each sensor is stuck on the patient's skin with bio-compatible double-sided adhesive tape.

The lumbar lordosis angle is defined as the angle formed by the tangent to the superior plate of the transitional thoraco-lumbar vertebra the most inclined on the horizontal, usually L1, and the tangent to the inferior plate L5. Thus, one IMU should be put over the L1 vertebra and one over the L5 vertebra. The lumbar lordosis angle θLL can be defined as the difference between the Euler angles of the IMUs along the Z axis θ28 and θ29.

Detecting hip & shoulder dissociation is picking up some conflicting accelerations between the upper part of the back and the lower part of the back. As a first suggestion, one IMU is placed over the highest vertebra on the patient's back T1, and one over the lowest L5. The hip & shoulder dissociation will be characterized as the phase difference between the analytic signals obtained from IMU antero-posterior accelerations A28 and A29 at T1 and L5.

Experimental protocol

A first feasibility test is designed. The system is tested on two volunteers. They are both youth women with the same morphology, one with a medical history of LBP and scoliosis (subject 1) and the other one without any reported back-related issue (subject 2).

Two simple exercises were proposed to the subjects.

First, each subject was asked to sit down on a chair for about 10 seconds, then, to stand up and to stand still for the next 10 seconds. An object was placed 50 cm in front of him and the subject was asked to bend his back in order to pick it up. After that, the patient stood up for 10 seconds once more and then sat down for 10 seconds (Exercise 1).

Second, a time-up-and-go test is done: after 10 seconds on the chair, the patient was asked to walk for about 3 m, turn back and then go back to the chair and stay sit for 10 seconds (Exercise 2).

RESULTS

Metrology

Table 1 presents the slope and offset between the angle given by the protractor and the measured one. Most of the coefficients of determination R 2 are higher that 0.99. The slope is close to 1 -and can be corrected easily. X axis presents the higher sensitivity drift for both sensors. The residue between the best linear fit and the experimental results are the same for 0x28 and 0x29. For Y and Z directions, the residues are essentially random. In the X direction, a 2 nd order bias appears and can be easily corrected. In these conditions, the standard deviation σ is less than 1°) and n (Fig. 3).

The IMUs did not show any measurable drift over a time period of 10 min. Identically, the calibration procedure was performed 10 days after the fist measure, and results were in close agreement. Therefore, it was concluded that reproducibility was good enough and that this point was not an issue.

Last, the BNO055 coming with an autocalibration feature running after every starting up, it is worth checking the BON055 measurement stability. Measurement at 0°) and n and 75°) and n were performed while varying the starting position. For the Y and Z direction, and for both IMUs, the returned value barely changed with the starting position but it was concluded that the X value was zeroed at the start whatever the real starting angle. Hence, it is required to build a stand for the IMUs so that the initial value for the X axis to be stable for both sensors.

Feasability tests

Fig. 4 presents the sensor 0x28 and 0x29 orientations versus time for the two subjects performing Exercise 1. Sensors are represented by a stick corresponding to their longitudinal axis (Y * ). The lumbar lordosis angle is calculated from the angle over the Z axis as follow: θLL = -180°) and n -θ28 -θ29

(1)

Finally, the lumbar lordosis angle corresponding to each subject was obtained by averaging the values while standing up. For the hip & shoulder dissociation detection, charts of linear accelerations along all axis have been produced. The parts where the subject was sat down were remove because they were irrelevant (mostly null) and to better focus on the moving part of the experiment. As the goal is to pick up an offset between the two IMUs, analytical signals on the linear accelerations for the Z axis were calculated with OCTAVE [START_REF] Eaton | GNU Octave version 5.2.0 manual: a high-level interactive language for numerical computations[END_REF] in order to find raw phase differences (Fig. 5).

DISCUSSION

The metrological results showed that the sensor arrangement gives reliable results, with a repeatability σ = 1°) and n and no observable drift.

A first test was done, with two women of comparable age and morphology, one with LBP history and the other without. Of course, these results cannot have any statistical meaning; nevertheless, they have a demonstrative interest.

During Exercise 1, the patient afflicted by LBP (subject 1) has a mean lumbar lordosis angle in stand-up phase of -19°) and n and the other -48°) and n . The lumbar lordosis angle being considered as natural in the range -45°) and n ±9°) and n , subject 1 is out of the safe interval, unlike subject 2 who is not afflicted by LBP. Fig. 4 shows a difference between the lumbar lordosis angle value in stationary stand-up phase between the 2 subjects. While subject 2's angle varies from -25°) and n to -60°) and n , subject 1's angle stays always close to -20°) and n . Subject 1's movements appear as more restricted in range than subject 2's. More, subject 1's movements are slower than subject 2's. This is in agreement with previous works stating a decrease both in speed and in range of motion for LBP patients [START_REF] Errabity | Lumbar spine kinematics in people with and without low back pain: a systematic review[END_REF].

Exercise 2 focuses on acceleration, and it is possible to extract basic gait analysis information. For example here, subject 1 was about 2s slower than subject 2. But, much detailed observations can be done: while subject 1's steps keep a similar shape and range through time, subject 2's are fluctuating through time. The pain might force subject 1 to limit her walking strategy to few movements while subject 2 can freely adapt her movements to the current stance.

The hip & shoulder dissociation presented as a phase difference on Fig. 5 discriminates the two subjects. Indeed, at the turning point (t ≈ 6.5 s), the T1 and L5 vertebrae of subject 1 are nearly in opposition of phase with the lower part of the back lagging behind the upper part. This is not seen in subject 2's case as the phase when turning back (t ≈ 5.5 s) is not much different than when subject 2 is walking. Henceforth, the hip & shoulder dissociation could be detected for the subject with LBP and not for the healthy one using phase analysis.

CONCLUSION

During this study, we have designed and built a new wearable device capable of detecting features helpful in LBP follow-up while being non-invasive. The metrological validation of BackMonitor arrangement shows good features, with small noise level (σ = 1°) and n ) and no observable drift.

Two simple exercises, one combining stand-up, sit and bending movements, the other being a classical time-up-and-go test, were proposed to two young volunteers, one of them with a LBP history. Signal was processed to extract the lordosis angle and hip & shoulder dissociation. Even if no general rules can be extracted from this study, we have shown that IMUs are able to pick up those characteristics and the obtained values are meaningful refereeing to LBP disease.

Hence, we are confident in going to clinical studies to elaborate the link between back related feature and LBP, in particular the hip & shoulder dissociation which is poorly documented.

FigureFigure 2 .

 2 Figure 1. Electrical circuit diagram

Figure 3 .

 3 Figure 3. Residues for Euler angles (in degrees) on 0x28

  Sensor orientation and lumbar lordosis angle for subject 1 and 2 during Exercise 1.

Figure 5 .

 5 Figure 5. Hip & shoulder phase difference for anteroposterior (Z) acceleration.

Table 1 .

 1 Linearity parameters.

	Sensor name Axis offset Slope	R 2
	0x28	X -0.5122 0.9312 0.9995
		Y 1.2707 0.9844 0.9999
		Z	1.6358 0.9879 0.9999
	0x29	X -1.9851 0.9065 0.9973
		Y 1.0071 0.9692 0.9998
		Z	6.1829 0.9411 0.9993