# A Polynomial Splines Identification Method Based on Control Nets

Authors: Zhihua Wang; Hongmei Kang
Journal: Complexity
 (2020)

---

## Abstract

In this study, based on Polynomial Splines with control nets, an identification method is investigated. We introduce polynomial splines with control nets defined over T-mesh. The basic idea is to extend T-vertices such that those T-vertices become interior cross vertices or boundary vertices. To this end, we introduce the design-suitable T-mesh for constructing polynomial splines with control net. In design-suitable T-meshes, there are no extra basis vertices produced by an appropriate extension of T-vertices. The basis functions are defined over each vertex in a design-suitable T-mesh by the means of constructing PHT-splines basis functions.


---

## Body

## 1. Introduction

T-splines [1, 2] are introduced to overcome the weakness of NURBS by allowing T-junctions. T-splines are considered as a generalization of NURBS surfaces and capable of local refinement, which makes T-splines a powerful modeling tool for advanced geometric modeling and adaptive isogeometric analysis (IGA) [3, 4]. Stimulated by the advent of T-splines and isogeometric analysis, locally refinable splines are born and now becoming flourishing. Currently, there are Hierarchical B-splines [5–7], truncated hierarchical B-splines (THB-splines) [8], truncated T-splines [9], truncated hierarchical tricubic C0 spline [10], blended B-spline based on unstructured quadrilateral and hexahedral meshes [11], analysis-suitable T-splines (AST-splines) [12], LR B-splines [13], modified T-splines [14], and polynomial splines over hierarchical T-meshes (PHT-splines) [15].PHT-splines are introduced in [15] as bicubic C1 continuous polynomial splines spaces defined over hierarchical T-meshes. PHT-splines possess a set of nonnegative and linearly independent basis functions and allow for very efficient local refinement. PHT-splines have been widely applied in geometric processing and analysis. The finite element discretization of elliptic equations based on PHT-splines was discussed in [16], where numerical solutions are refined adaptively and have the optimal convergence rate. PHT-splines are also favored in isogeometric analysis for solving elastic problems [3, 17, 18] and adaptive isogeometrican analysis [19]. PHT-splines are also applied in reconstructing surface models efficiently. PHT-splines were used in stitching several surface patches to construct complex models in paper [20] and PHT-splines were also applied in surface reconstruction from a very large set of point clouds in implicit form [21]. IGA collocation approaches are introduced in paper [22], and PHT-splines have been used as basis functions for the adaptive collocation method [23].In order to make PHT-splines better suited for analysis and geometric processing, some improvements and extensions have been made to PHT splines in recent years. In [24], the authors discussed the decay phenomenon of PHT-splines basis functions. They found some of the basis functions will tend to zero as the refinement level increases under certain types of refinement. Such a decay makes the stiffness matrix in isogeometric analysis be ill-conditioned, which is not expected by analysis. Thus a new basis construction method is proposed for PHT-splines to avoid the decay. The extension of PHT-splines to general T-meshes is considered in [25], where the bicubic C1 continuous polynomial splines are defined over general T-meshes. The basis functions are constructed by computing the geometric information at basis vertices such that the resulting basis functions are nonnegative and linearly independent and form a partition of unity. PHT splines were defined over hierarchical T-meshes without irregular vertex in [15], and then the bicubic C1 continuous splines construction based on irregular quad layout were discussed in [26]. Current implementation of PHT-splines stores the basis functions in Bézier forms, which saves some computational costs but consumes a lot of memories. In [27], an algorithm to evaluate PHT-splines is provided where only the information about the control coefficients and the hierarchical mesh structure is given. The evaluation algorithm takes about the same computational costs while requiring much less amount of memory compared with the Bézier representations.For PHT-splines, there is no one-to-one correspondence between the vertices in the underlying T-mesh and PHT-splines basis functions. The boundary vertices and interior cross vertices are called basis vertices. Each basis vertex is associated with four basis functions. The control net concept is essential in computer aided geometric design (CAGD), because the control net makes editing models easily and intuitively. In this paper, we introduce polynomial splines with control polygon to complement PHT-splines. The proposed splines defined over all the vertices of the underlying T-meshes, such that there is a one-to-one correspondence between control points and vertices in T-meshes. The basis idea is to extend T-vertices to be basis vertices. In order to avoid generating extra basis vertices when extending T-vertices, we introduce a subset of T-meshes, called design-suitable T-meshes. Over design-suitable T-meshes, the T-vertices can be extended appropriately without generating extra basis vertices. For a given T-mesh, it needs to connect some T-vertices to be a design-suitable T-mesh. We define polynomial splines basis functions over the design-suitable T-mesh. The resulting splines not only inherit the nice properties of PHT-splines, but also have control nets.The paper is organized as follows. In Section2, we review some preliminary knowledge about polynomial splines over T-meshes. In Section 3, we proposed a subset of T-mesh called design-suitable T-mesh and prove that there are no extra basis vertices produced by an appropriate extension. In Section 4, we present an algorithm of local refinement of the proposed splines. Finally, we give a conclusion of this paper in Section 5.


## 2. Preliminary Knowledge

### 2.1. T-Meshes

A T-mesh is a rectangular grid with T-junctions. The cells in a T-mesh must be rectangles. A grid point in a T-mesh is called avertex. And the vertex on a boundary grid line is called a boundary vertex; otherwise, it is called an interior vertex. Interior vertices consist of cross vertices and T-vertices. We adopt the notations ⊤, ⊥, ⊢, and ⊣ to indicate the four possible orientations of T-vertices. The T-vertices of type ⊢ and ⊣ are called horizontal T-vertices and the T-vertices of type ⊤ and ⊥ are called vertical T-vertices.


### 2.2. BicubicC1 Continuous B-Splines

Let(1)t0,t0=t1,t1<t2,t2<⋯<tj,tj<⋯<tn−1,tn−1=tn,tn,be a knot vector with interior knots of multiplicity two. Then each knot tj is associated with two cubic B-splines Nj1t=N3tj−1,tj−1,tj,tj,tj+1t and Nj2t=N3tj−1,tj,tj,tj+1,tj+1t. Both Nj1t and Nj2t together with their derivatives have the same support tj−1,tj+1. Except for Nj1t and Nj2t, all the other cubic B-splines and their derivatives vanish at tj.For given a tensor product meshT, the two associated global knot vectors in s-direction and t-direction are(2)U=s0,s0=s1,s1<s2,s2<⋯<sj,sj<⋯<sm−1,sm−1=sm,sm,V=t0,t0=t1,t1<t2,t2<⋯<tj,tj<⋯<tn−1,tn−1=tn,tn,respectively. The bicubic C1 continuous B-splines surface defined over T is spanned by the Ni,jki=0,j=0,k=0i=m,j=n,k=3, where Ni,jks,t=Nik%2sNjk/2t, k=0,1,2,3 are the four B-splines associated with the vertex si,tj.For a functionfx,y, the function value, the first partial derivatives, and the mixed partial derivative are called the geometric information of fx,y, denoted by(3)Gfx,y=fx,y,fxx,y,fyx,y,fxyx,y.For the basis functionNi,jk defined above, it has GNi,jksp,tq=δipδjq and δip=1, if i=p; otherwise, δip=0. That is the geometric information of Ni,jk vanishes at other vertices in T except its associated vertex si,tj.


## 2.1. T-Meshes

A T-mesh is a rectangular grid with T-junctions. The cells in a T-mesh must be rectangles. A grid point in a T-mesh is called avertex. And the vertex on a boundary grid line is called a boundary vertex; otherwise, it is called an interior vertex. Interior vertices consist of cross vertices and T-vertices. We adopt the notations ⊤, ⊥, ⊢, and ⊣ to indicate the four possible orientations of T-vertices. The T-vertices of type ⊢ and ⊣ are called horizontal T-vertices and the T-vertices of type ⊤ and ⊥ are called vertical T-vertices.


## 2.2. BicubicC1 Continuous B-Splines

Let(1)t0,t0=t1,t1<t2,t2<⋯<tj,tj<⋯<tn−1,tn−1=tn,tn,be a knot vector with interior knots of multiplicity two. Then each knot tj is associated with two cubic B-splines Nj1t=N3tj−1,tj−1,tj,tj,tj+1t and Nj2t=N3tj−1,tj,tj,tj+1,tj+1t. Both Nj1t and Nj2t together with their derivatives have the same support tj−1,tj+1. Except for Nj1t and Nj2t, all the other cubic B-splines and their derivatives vanish at tj.For given a tensor product meshT, the two associated global knot vectors in s-direction and t-direction are(2)U=s0,s0=s1,s1<s2,s2<⋯<sj,sj<⋯<sm−1,sm−1=sm,sm,V=t0,t0=t1,t1<t2,t2<⋯<tj,tj<⋯<tn−1,tn−1=tn,tn,respectively. The bicubic C1 continuous B-splines surface defined over T is spanned by the Ni,jki=0,j=0,k=0i=m,j=n,k=3, where Ni,jks,t=Nik%2sNjk/2t, k=0,1,2,3 are the four B-splines associated with the vertex si,tj.For a functionfx,y, the function value, the first partial derivatives, and the mixed partial derivative are called the geometric information of fx,y, denoted by(3)Gfx,y=fx,y,fxx,y,fyx,y,fxyx,y.For the basis functionNi,jk defined above, it has GNi,jksp,tq=δipδjq and δip=1, if i=p; otherwise, δip=0. That is the geometric information of Ni,jk vanishes at other vertices in T except its associated vertex si,tj.


## 3. Polynomial Splines with Control Nets Defined over T-Meshes

PHT-splines span the polynomial splines spaceS3,3,1,1 over a T-mesh and are defined over cross interior vertices and boundary vertices (called basis vertices), resulting in PHT-splines lacking control net. Our aim is to equip PHT-splines with control net. For any given control mesh, we parameterize the control mesh into a T-mesh in 2D domain and then extend all T-vertices in the T-mesh such that they become basis vertices and no extra basis vertices is introduced, and finally construct basis functions of S3,3,1,1 over the extended T-mesh. Thus, there is a one-to-one correspondence between the control mesh and parameter T-mesh. For arbitrary T-mesh, it is inevitable that extra basis vertices are produced by directly extending T-vertices. Therefore, in order to avoid extra basis vertices, we introduce design-suitable T-meshes for defining basis functions.


### 3.1. Design-Suitable T-Meshes

For a given T-meshT, we shall adopt some definitions and notations (Figure 1).(i)
Extension of T-vertex. The closed line segment created by extending a T-vertex in the missing direction until it intersects with an edge is called the extension of this T-vertex. Particularly, if the edge is an edge in T, then the extension is called a full-extension. The extension of a horizontal (vertical) T-vertex is called the horizontal (vertical) extension, respectively. In Figure 1(b), the dotted line segments are full-extensions of T-vertices.(ii)
Full-Extension Mesh. A T-mesh together with the full-extensions of all T-vertices in this T-mesh forms the full-extension mesh. Figure 1(b) shows the full-extension mesh of the T-mesh in Figure 1(a).(iii)
Edge-Type Intersections. The intersection between two same type extensions and the intersection between an extension and a boundary edge is called an edge-type intersection (E-intersection for short). In Figure 1(b), v0,v1,…,v7 are all E-intersections.(iv)
Face-Type Intersections. The intersection between a horizontal extension and a vertical extension is called a face-type intersection (F-intersection for short). In Figure 1(b), v8,v9,…,v13 are all F-intersections.(v)
Connectable Vertex. Two vertices can be connected if the line segment formed by these two vertices splits the lying face into two subrectangles. If two T-vertices can be connected, then they are called connectable T-vertices (CT-vertex for short). The vertices are marked by blue solid circles in Figure 1(a).(vi)
E-Connectable T-Vertex. For a T-vertex, if its extension intersects with the extension of another same type T-vertex or with a boundary edge, then the T-vertex is called an e-connectable T-vertex (ECT-vertex). The vertices marked by yellow solid circles in Figure 1(a) are ECT-vertices.(vii)
Normal T-Vertex. For a T-vertex, if it is either a CT-vertex or an ECT-vertex, then it is called a normal T-vertex.(viii)
T-Element. If there are T-vertices lying on the edges of an element, then the element is called a T-element.(ix)
C-Element. For a T-element in T, if there are ECT-vertices on the edges of this element, then the element is called a C-element. Those elements F1,F2,…,F6 in Figure 1(a) are connectable elements.(x)
S-Element. For a C-element, if there exists a normal vertical (horizontal) T-vertex in the element such that its extension subdivides the element into two subelements and one subelement contains all the horizontal (vertical) ECT-vertices, then the connectable element is called a S-element and the normal vertical (horizontal) T-vertex is called a ST-vertex. The element F6 is a S-element, while F1,…,F5 are not S-elements.Figure 1
Full-extension T-mesh. (a) T-mesh; (b) full-extension T-meshText.
(a)(b)Definition 1.
For a given T-meshT, the corresponding full-extension T-mesh is denoted by Text, if(i)
there are no connectable T-vertices inT(ii)
for each edge-type intersection inText, the underlying edge is attached to a S-element;
thenT is called a design-suitable T-mesh.
The diagonal T-mesh (the diagonal elements are refined in the diagonal direction) shown in Figure2(a) is a design-suitable T-mesh. The T-mesh shown in Figure 1(b) is not a design-suitable T-mesh. But if we connect all the CT-vertices and ECT-vertices, then the resulting mesh is a design-suitable T-mesh which is shown in Figure 3(a).
For a design-suitable T-mesh, there are no extra basis vertices produced by extending T-vertices appropriately. The intuitive way is to extend a T-vertex in the missing direction, until it intersects with an edge in the underlying mesh instead of the original T-mesh. We call such a way of extending T-vertices as p-extending to distinguish from the extension mentioned above. For the design-suitable T-mesh shown in Figure2(a), the new T-mesh produced by p-extending T-vertices is shown in Figure 2(b). We also plot the full-extension T-mesh in Figure 2(c) for comparison. This p-extending way is not enough for the T-meshes containing ECT-vertices. It still requires an order of extending T-vertices. Thus, we introduce the following algorithm to extend T-vertices in a given T-mesh, and the resulting T-mesh is denoted by Te.(i)
Step one: p-extend T-vertices in S-elements and the adjacent elements of S-elements(a)
S-element: First p-extend the ST-vertices of an S-element; then p-extend the rest of T-vertices in the element(b)
Adjacent elements: First p-extend ECT-vertices; then p-extend the normal T-vertices(ii)
Step two: p-extend T-vertices in the rest of T-elements(a)
First p-extend horizontal T-vertices; then p-extend vertical T-vertices
We take Figure3 as an example to explain the above algorithm. In the T-mesh shown in Figure 3(a), F1,F2,…,F6 are T-elements. We need to extend the T-vertices in these elements. The element F3 is an S-element. We start from extending T-vertices in this element. The vertex v5 is a ST-vertex, and it is extended until it intersects with an existing edge. Then we extend the vertex v4, and the first edge it intersects with is the extension of v5. The element F6 is the adjacent element of F3. The vertex v8 is p-extended. For the rest T-elements, if there are horizontal T-vertices, then extend them first. Thus, in F3, v3 is extended first and then v2 is extended. The resulting extended T-mesh is shown Figure 3(b).Figure 2
A design-suitable T-mesh and the p-extending. (a) Diagonal T-mesh, (b) p-extending, and (c) full-extension T-mesh.
(a)(b)(c)Figure 3
The proposed algorithm for extending T-vertices. (a) Design-suitable T-mesh; (b) extended T-meshTe.
(a)(b)Theorem 1.
For a design-suitable T-meshT, extend the T-vertices in T as above. Then there is a one-to-one correspondence between basis vertices in Te and vertices in T, which means there are no extra basis vertices produced in Te by extending T-vertices in T appropriately.Proof.
We only need to deal with T-elements. We extend T-vertices element by element. We need to prove there are no edge-type intersections and face-type intersections inTe. In a design-suitable T-mesh, only extending ECT-vertices may produce edge-type intersections. Furthermore, there are no face-type intersections produced by p-extending. S-elements are extended first according to the above algorithm. Since ST-vertices are normal T-vertices, then their extensions intersect with existing edges and the intersections are T-vertices. According to the definition of ST-vertices, the extensions of ST-vertices prevent the intersection between ECT-vertices. Then extending T-vertices in the adjacent T-elements of S-elements will not produce new basis vertices. For the rest T-elements, there are no basis vertices produced by p-extending.


### 3.2. Construct Basis Functions overTe

LetBis,t=Bi1s,t,Bi2s,t,Bi3s,t,Bi4s,t be the basis functions associated with Vi needed to be constructed. There are mainly three steps for constructing Bis,t in [25]:(i)
Find a rectangle containing all the vertices at whichBis,t which do not vanish in Te(ii)
Set the geometric information of bicubicC1 continuous B-splines associated with Vi over the rectangle as the geometric information of Bis,t(iii)
Set the geometric information at other basis vertices in the rectangle as zeros and representBis,t in the Bézier form or B-splines formThe method for finding a rectangle for each basis vertex inTe is stated as follows. For a basis vertex vi=si0,ti0 in Te, first put vi into Ki, then check the neighboring vertices of the vertices in Ki and put the T-vertices into Ki recursively until there is no vertex added into Ki. The minimal rectangle containing all the vertices in Ki is denoted by RV=s0,s1×t0,t1, then RV together with the knot lines s=si0 and t=ti0 forms a 2×2 tensor product mesh MV=s0,si0,s1×t0,ti0,t1. For the sake of clearness, we call Mv as the support mesh of basis vertex vi. Figure 4 shows the support meshes of four basis vertices v13, v17, and v4 in the extended T-mesh, where the support meshes are shaded. In Figure 4(a), v13 is a basis vertex and among the neighbors of v13, v48 is a T-vertex; thus, it is put into Ki. Then we check the neighbors of v48, and v49 is a T-vertex which is put into Ki. For v49, there are no more vertices needed to be added into Ki. Thus, the set Ki=v13,v48,v49. Similarly for v17 in Figure 4(b), now ki=v17,v50,v51. For the basis vertex v4 shown in Figure 4(c), Ki=v4,v53.Figure 4
The support meshes of three basis verticesv13, v17 and v4. (a) T-mesh, (b) extended T-mesh, and (c) extended T-mesh.
(a)(b)(c)The four B-spline basis functions defined overMv are denoted by Nks,t, k=0,1,2,3, and(4)Nks,t=N3s0,s0,si0,si0,s1,s1s×N3t0,t0,ti0,ti0,t1,t1t.Then the geometric information of four basis functionsBis,t at Vi is defined as the geometric information of Nks,t, k=0,1,2,3. The geometric information of Bis,t at the other basis vertices in Mv is set as zero. And the geometric information of Bis,t at T-vertices in Mv is computed by C1 constraints. According to the known geometric information of Bis,t at the vertices in Mv, then Bis,t can be easily represented in Bézier form or B-splines form.


### 3.3. Polynomial Splines with Control Net Defined on T-Meshes

With the help of index T-mesh, there is a one-to-one correspondence between vertices and basis functions. The index T-mesh is adopted in [3] for ease of constructing T-splines. It is constructed by plotting the knots at equally spaced intervals regardless of their actual spacing and labeling each knot line with integer values [3]. Figure 5(b) shows the index T-mesh of the mesh shown in Figure 5(a). Figure 5(c) shows a control net in ℝ3 corresponding to the T-mesh shown in Figure 5(a). Figure 5(d) shows the polynomial splines surface with control net Figure 5(c) defined on the design-suitable T-mesh Figure 5(a). Notice the knots in this paper are of multiplicity two; thus, if we view the T-mesh in index space, each vertex in T-meshes corresponds to four vertices in index T-mesh. In a design-suitable T-mesh, it happens that each vertex is associated with four basis functions. Thus, there is a one-to-one correspondence between vertices and basis functions exactly in a design-suitable T-mesh. For convenience, in this paper, we still use T-meshes for constructing T-meshes and local refinement. The index T-mesh is used only to explain the control net.Figure 5
The index space and the control mesh. (a) A Design-suitable T-mesh. (b) The index mesh. (c) The control net. (d) The surface generated by the control net shown in (c).
(a)(b)(c)(d)For a design-suitable T-meshT, we construct basis functions on the extended T-mesh Te as stated in section 3.2. The polynomial splines surface defined over T is defined as follows:(5)Su,v=∑i=1n∑k=14PikBiku,v,u,v∈a,b×c,d,where Biku,v are basis functions constructed in section 3.2 and Pik∈ℝ3 are the corresponding control points. Figure 6 presents the polynomial splines model with control nets. The construction method is based on the above polynomial splines with control nets defined over T-meshes; we design a goblet model and a dolphin model; see Figures 7 and 8.Figure 6
A model of the polynomial splines with control nets.Figure 7
A goblet model designed by the polynomial splines with control nets.Figure 8
A dolphin model designed by the polynomial splines with control nets.For a design-suitable T-mesh, we define four basis functions at each vertex. If we need to adjust the surface part corresponding to a T-vertex, we can adjust the control point corresponding to the basis functions defined at the T-vertex to modify the surface directly. But for PHT-spline surface, it can only be adjusted indirectly by adjusting the control points corresponding to the basis functions defined at other basis vertices. Figure9 shows the modification of the surface by adjusting the position of the control points corresponding to the T-vertices and the normal basis vertices.Figure 9
The index space and the control mesh. (a) Adjusting the position of the control points corresponding to the T-vertices in the Figure5(c). (b) The surface figure obtained by adjusting the position of the control point corresponding to the T-vertices. (c) Adjusting the position of the control points corresponding to the basis vertices in the Figure 5(c). (d) The surface figure obtained by adjusting the position of the control point corresponding to the basis vertices.
(a)(b)(c)(d)


## 3.1. Design-Suitable T-Meshes

For a given T-meshT, we shall adopt some definitions and notations (Figure 1).(i)
Extension of T-vertex. The closed line segment created by extending a T-vertex in the missing direction until it intersects with an edge is called the extension of this T-vertex. Particularly, if the edge is an edge in T, then the extension is called a full-extension. The extension of a horizontal (vertical) T-vertex is called the horizontal (vertical) extension, respectively. In Figure 1(b), the dotted line segments are full-extensions of T-vertices.(ii)
Full-Extension Mesh. A T-mesh together with the full-extensions of all T-vertices in this T-mesh forms the full-extension mesh. Figure 1(b) shows the full-extension mesh of the T-mesh in Figure 1(a).(iii)
Edge-Type Intersections. The intersection between two same type extensions and the intersection between an extension and a boundary edge is called an edge-type intersection (E-intersection for short). In Figure 1(b), v0,v1,…,v7 are all E-intersections.(iv)
Face-Type Intersections. The intersection between a horizontal extension and a vertical extension is called a face-type intersection (F-intersection for short). In Figure 1(b), v8,v9,…,v13 are all F-intersections.(v)
Connectable Vertex. Two vertices can be connected if the line segment formed by these two vertices splits the lying face into two subrectangles. If two T-vertices can be connected, then they are called connectable T-vertices (CT-vertex for short). The vertices are marked by blue solid circles in Figure 1(a).(vi)
E-Connectable T-Vertex. For a T-vertex, if its extension intersects with the extension of another same type T-vertex or with a boundary edge, then the T-vertex is called an e-connectable T-vertex (ECT-vertex). The vertices marked by yellow solid circles in Figure 1(a) are ECT-vertices.(vii)
Normal T-Vertex. For a T-vertex, if it is either a CT-vertex or an ECT-vertex, then it is called a normal T-vertex.(viii)
T-Element. If there are T-vertices lying on the edges of an element, then the element is called a T-element.(ix)
C-Element. For a T-element in T, if there are ECT-vertices on the edges of this element, then the element is called a C-element. Those elements F1,F2,…,F6 in Figure 1(a) are connectable elements.(x)
S-Element. For a C-element, if there exists a normal vertical (horizontal) T-vertex in the element such that its extension subdivides the element into two subelements and one subelement contains all the horizontal (vertical) ECT-vertices, then the connectable element is called a S-element and the normal vertical (horizontal) T-vertex is called a ST-vertex. The element F6 is a S-element, while F1,…,F5 are not S-elements.Figure 1
Full-extension T-mesh. (a) T-mesh; (b) full-extension T-meshText.
(a)(b)Definition 1.
For a given T-meshT, the corresponding full-extension T-mesh is denoted by Text, if(i)
there are no connectable T-vertices inT(ii)
for each edge-type intersection inText, the underlying edge is attached to a S-element;
thenT is called a design-suitable T-mesh.
The diagonal T-mesh (the diagonal elements are refined in the diagonal direction) shown in Figure2(a) is a design-suitable T-mesh. The T-mesh shown in Figure 1(b) is not a design-suitable T-mesh. But if we connect all the CT-vertices and ECT-vertices, then the resulting mesh is a design-suitable T-mesh which is shown in Figure 3(a).
For a design-suitable T-mesh, there are no extra basis vertices produced by extending T-vertices appropriately. The intuitive way is to extend a T-vertex in the missing direction, until it intersects with an edge in the underlying mesh instead of the original T-mesh. We call such a way of extending T-vertices as p-extending to distinguish from the extension mentioned above. For the design-suitable T-mesh shown in Figure2(a), the new T-mesh produced by p-extending T-vertices is shown in Figure 2(b). We also plot the full-extension T-mesh in Figure 2(c) for comparison. This p-extending way is not enough for the T-meshes containing ECT-vertices. It still requires an order of extending T-vertices. Thus, we introduce the following algorithm to extend T-vertices in a given T-mesh, and the resulting T-mesh is denoted by Te.(i)
Step one: p-extend T-vertices in S-elements and the adjacent elements of S-elements(a)
S-element: First p-extend the ST-vertices of an S-element; then p-extend the rest of T-vertices in the element(b)
Adjacent elements: First p-extend ECT-vertices; then p-extend the normal T-vertices(ii)
Step two: p-extend T-vertices in the rest of T-elements(a)
First p-extend horizontal T-vertices; then p-extend vertical T-vertices
We take Figure3 as an example to explain the above algorithm. In the T-mesh shown in Figure 3(a), F1,F2,…,F6 are T-elements. We need to extend the T-vertices in these elements. The element F3 is an S-element. We start from extending T-vertices in this element. The vertex v5 is a ST-vertex, and it is extended until it intersects with an existing edge. Then we extend the vertex v4, and the first edge it intersects with is the extension of v5. The element F6 is the adjacent element of F3. The vertex v8 is p-extended. For the rest T-elements, if there are horizontal T-vertices, then extend them first. Thus, in F3, v3 is extended first and then v2 is extended. The resulting extended T-mesh is shown Figure 3(b).Figure 2
A design-suitable T-mesh and the p-extending. (a) Diagonal T-mesh, (b) p-extending, and (c) full-extension T-mesh.
(a)(b)(c)Figure 3
The proposed algorithm for extending T-vertices. (a) Design-suitable T-mesh; (b) extended T-meshTe.
(a)(b)Theorem 1.
For a design-suitable T-meshT, extend the T-vertices in T as above. Then there is a one-to-one correspondence between basis vertices in Te and vertices in T, which means there are no extra basis vertices produced in Te by extending T-vertices in T appropriately.Proof.
We only need to deal with T-elements. We extend T-vertices element by element. We need to prove there are no edge-type intersections and face-type intersections inTe. In a design-suitable T-mesh, only extending ECT-vertices may produce edge-type intersections. Furthermore, there are no face-type intersections produced by p-extending. S-elements are extended first according to the above algorithm. Since ST-vertices are normal T-vertices, then their extensions intersect with existing edges and the intersections are T-vertices. According to the definition of ST-vertices, the extensions of ST-vertices prevent the intersection between ECT-vertices. Then extending T-vertices in the adjacent T-elements of S-elements will not produce new basis vertices. For the rest T-elements, there are no basis vertices produced by p-extending.


## 3.2. Construct Basis Functions overTe

LetBis,t=Bi1s,t,Bi2s,t,Bi3s,t,Bi4s,t be the basis functions associated with Vi needed to be constructed. There are mainly three steps for constructing Bis,t in [25]:(i)
Find a rectangle containing all the vertices at whichBis,t which do not vanish in Te(ii)
Set the geometric information of bicubicC1 continuous B-splines associated with Vi over the rectangle as the geometric information of Bis,t(iii)
Set the geometric information at other basis vertices in the rectangle as zeros and representBis,t in the Bézier form or B-splines formThe method for finding a rectangle for each basis vertex inTe is stated as follows. For a basis vertex vi=si0,ti0 in Te, first put vi into Ki, then check the neighboring vertices of the vertices in Ki and put the T-vertices into Ki recursively until there is no vertex added into Ki. The minimal rectangle containing all the vertices in Ki is denoted by RV=s0,s1×t0,t1, then RV together with the knot lines s=si0 and t=ti0 forms a 2×2 tensor product mesh MV=s0,si0,s1×t0,ti0,t1. For the sake of clearness, we call Mv as the support mesh of basis vertex vi. Figure 4 shows the support meshes of four basis vertices v13, v17, and v4 in the extended T-mesh, where the support meshes are shaded. In Figure 4(a), v13 is a basis vertex and among the neighbors of v13, v48 is a T-vertex; thus, it is put into Ki. Then we check the neighbors of v48, and v49 is a T-vertex which is put into Ki. For v49, there are no more vertices needed to be added into Ki. Thus, the set Ki=v13,v48,v49. Similarly for v17 in Figure 4(b), now ki=v17,v50,v51. For the basis vertex v4 shown in Figure 4(c), Ki=v4,v53.Figure 4
The support meshes of three basis verticesv13, v17 and v4. (a) T-mesh, (b) extended T-mesh, and (c) extended T-mesh.
(a)(b)(c)The four B-spline basis functions defined overMv are denoted by Nks,t, k=0,1,2,3, and(4)Nks,t=N3s0,s0,si0,si0,s1,s1s×N3t0,t0,ti0,ti0,t1,t1t.Then the geometric information of four basis functionsBis,t at Vi is defined as the geometric information of Nks,t, k=0,1,2,3. The geometric information of Bis,t at the other basis vertices in Mv is set as zero. And the geometric information of Bis,t at T-vertices in Mv is computed by C1 constraints. According to the known geometric information of Bis,t at the vertices in Mv, then Bis,t can be easily represented in Bézier form or B-splines form.


## 3.3. Polynomial Splines with Control Net Defined on T-Meshes

With the help of index T-mesh, there is a one-to-one correspondence between vertices and basis functions. The index T-mesh is adopted in [3] for ease of constructing T-splines. It is constructed by plotting the knots at equally spaced intervals regardless of their actual spacing and labeling each knot line with integer values [3]. Figure 5(b) shows the index T-mesh of the mesh shown in Figure 5(a). Figure 5(c) shows a control net in ℝ3 corresponding to the T-mesh shown in Figure 5(a). Figure 5(d) shows the polynomial splines surface with control net Figure 5(c) defined on the design-suitable T-mesh Figure 5(a). Notice the knots in this paper are of multiplicity two; thus, if we view the T-mesh in index space, each vertex in T-meshes corresponds to four vertices in index T-mesh. In a design-suitable T-mesh, it happens that each vertex is associated with four basis functions. Thus, there is a one-to-one correspondence between vertices and basis functions exactly in a design-suitable T-mesh. For convenience, in this paper, we still use T-meshes for constructing T-meshes and local refinement. The index T-mesh is used only to explain the control net.Figure 5
The index space and the control mesh. (a) A Design-suitable T-mesh. (b) The index mesh. (c) The control net. (d) The surface generated by the control net shown in (c).
(a)(b)(c)(d)For a design-suitable T-meshT, we construct basis functions on the extended T-mesh Te as stated in section 3.2. The polynomial splines surface defined over T is defined as follows:(5)Su,v=∑i=1n∑k=14PikBiku,v,u,v∈a,b×c,d,where Biku,v are basis functions constructed in section 3.2 and Pik∈ℝ3 are the corresponding control points. Figure 6 presents the polynomial splines model with control nets. The construction method is based on the above polynomial splines with control nets defined over T-meshes; we design a goblet model and a dolphin model; see Figures 7 and 8.Figure 6
A model of the polynomial splines with control nets.Figure 7
A goblet model designed by the polynomial splines with control nets.Figure 8
A dolphin model designed by the polynomial splines with control nets.For a design-suitable T-mesh, we define four basis functions at each vertex. If we need to adjust the surface part corresponding to a T-vertex, we can adjust the control point corresponding to the basis functions defined at the T-vertex to modify the surface directly. But for PHT-spline surface, it can only be adjusted indirectly by adjusting the control points corresponding to the basis functions defined at other basis vertices. Figure9 shows the modification of the surface by adjusting the position of the control points corresponding to the T-vertices and the normal basis vertices.Figure 9
The index space and the control mesh. (a) Adjusting the position of the control points corresponding to the T-vertices in the Figure5(c). (b) The surface figure obtained by adjusting the position of the control point corresponding to the T-vertices. (c) Adjusting the position of the control points corresponding to the basis vertices in the Figure 5(c). (d) The surface figure obtained by adjusting the position of the control point corresponding to the basis vertices.
(a)(b)(c)(d)


## 4. Local Refinement

Given a design-suitable T-meshT1, denote the extended T-mesh as Te1. The edge insertion is to insert edges into T1, the resulting T-mesh is denoted by T2. The local refinement is attributed to how to construct the extended T-mesh Te2 such that S3,3,1,1,Te1⊆S3,3,1,1,Te2, which is equivalent to Te1⊆Te2.Suppose a vertical edgee=v0v1¯ is inserted into a element F, and the 2-neighboring elements of F in vertical direction are denoted by Fi, i=1,2,…,l (if existing). The local refinement algorithm is described as follows:(1)
Ifv0v1 is a CT-vertex or a ECT-vertex, then extend them until it is either a CT-vertex or ECT-vertex.(2)
Among the T-vertices inFii=1l and F, if the extension of a T-vertex in Te1 intersects with e, then p-extend the T-vertex. The resulting T-mesh is denoted by T2.(3)
Construct the extended T-meshTe2.(i)
Update the new T-vertices which are inT2 but not in T1 by p-extending.(ii)
Keep the extensions inTe1 of the original T-vertices.We use Figure10 to demonstrate the local refinement algorithm as proposed above. A design-suitable T-mesh T1 is shown in Figure 10(a) and the corresponding extended T-mesh Te1 is shown in Figure 10(b). A vertical edge v0v1¯ (marked by red line) is inserted in T1, which is shown in Figure 10(c). Now v0 is a CT-vertex and v1 is a ECT-vertex; then they are extended as shown in Figure 10(d). For the horizontal T-vertices in F1 and F, their extensions with respect to Te1 intersect with e, extend them as shown in Figure 10(e). The resulting T-mesh is a design-suitable T-mesh, denoted by T2. Finally, we construct the extended T-mesh corresponding to T2. We only need to update the extension of the new T-vertices. Figure 10(f) shows the extended T-mesh Te2.Figure 10
Steps of local refinement algorithm. (a) Design-suitable T-meshT1, (b) extended T-mesh Te1, (c) insert an edge (red line), (d) first step: extend v0 and v1, (e) design-suitable T-mesh T2, (f) extended T-mesh Te2.
(a)(b)(c)(d)(e)(f)Figure11 shows the local refinement of a diagonal T-mesh. The inserted edges are marked by red line segments and the additional inserted edges are marked by blue line segments in Figures 11(c) and 11(e). Figures 10(d) and 10(f) show the extended T-meshes of Figures 11(c) and 11(e), respectively. Obviously, the extended T-mesh of the diagonal T-mesh shown in Figure 11(a) is contained in both the extended T-meshes shown in Figures 10(d) and 10(f). Notice there are at most 1 neighboring elements of the element F are need to be inserted into edges; thus, the refinement are local.Figure 11
Local refinement of a diagonal T-mesh. (a) Design-suitable T-meshT1. (b) Extended T-mesh Te1. (c) Insert an edge (red line) T2. (d) Extended T-mesh Te2. (e) Insert an edge (red line) T2. (f) Extended T-mesh Te2.
(a)(b)(c)(d)(e)(f)


## 5. Conclusions

In this paper, we present an algorithm for extending bicubicC1 polynomial spline spaces defined over any given T-meshes such that there is a one-to-one correspondence between basis functions and vertices in the T-meshes. The key idea is to extend the T-junctions such that the T-junctions become basis vertices. Thus how to extend these T-junctions to avoid extra basis vertices produced is the main challenge. In this paper, we proposed a subset of T-meshes called design-suitable T-meshes. For design-suitable T-meshes, we first extend T-vertices through an appropriate order and then construct basis functions on the extended T-meshes. There is a one-to-one correspondence between basis functions and vertices in the T-mesh. Furthermore, it is easy to modify a given T-mesh such that it becomes a design-suitable T-mesh.



---

*Source: 7103963-2020-08-19.xml*