中国科学技术大学：NEW PROOF OF DIMENSION FORMULA OF SPLINE SPACES OVER T-MESHES VIA SMOOTHING COFACTORS.pdf_大学文库

Journal of Computational Mathematics, Vol.24, No.2, 2006, ??–??. NEW PROOF OF DIMENSION FORMULA OF SPLINE SPACES OVER T-MESHES VIA SMOOTHING COFACTORS ∗ Zhang-jin Huang Jian-song Deng Yu-yu Feng Fa-lai Chen (Department of Mathematics, University of Science and Technology of China, Hefei 230026, China) Abstract A T-mesh is basically a rectangular grid that allows T-junctions. Recently, Deng etal introduced splines over T-meshes, which are generalizations of T-splines invented by Sederberg etal, and proposed a dimension formula based on the B-net method. In this paper, we derive an equivalent dimension formula in a different form with the smoothing cofactor method. Mathematics subject classification: Key words: Spline space, T-mesh, Smoothing cofactors. 1. Introduction T-meshes are formed by a set of horizontal line segments and a set of vertical line segments, where T-junctions are allowed. See Figure 1 for examples. Traditional tensor-product B-spline functions, which are a basic tool in the design of freeform surfaces, are defined over special T-meshes, where no T-junctions appear. B-spline surfaces have the drawback that arises from the mathematical properties of the tensor-product B-spline basis functions. Two global knot vectors which are shared by all basis functions, do not allow local modification of the domain partition. Thus, if we want to construct a surface which is flat in the most part of the domain, but sharp in a small region, we have to use more control points not only in the sharp region, but also in the regions propagating from the sharp region along horizontal and vertical directions to maintain the tensor-product mesh structure. The superfluous control points are a big burden to modelling systems. In [5], Sederberg etal explained the troubles made by these superfluous control points in details. To overcome this limitation, we need the local refinement of B-spline surfaces, i.e. to insert a single control point without propagating an entire row or column of control points. In [4] hierarchical B-splines were introduced, and two concepts were defined: local refinement using an efficient representation and multi-resolution editing. In principle, Hierarchical B-splines are the accumulation of tensor-product surfaces with different resolutions and domains. Weller and Hagen [8] discussed tensor-product splines with knot segments. In fact, they defined a spline space over a more general T-mesh, where crossing, T-junctional, and L-junctional vertices are allowed. But its dimensions are estimated and its basis functions are given over the mesh induced by some semi-regular basis functions. In 2003, Sederberg etal [5] invented T-spline. It is a point-based spline, i.e., for every vertex, a blending function of the spline space is defined. Each of the blending functions comes from some tensor-product spline space. Though this type of splines supports many valuable operations within a consistent framework, but some of them, say, local refinement, are ∗ Received May 18, 2005; Final revised November 20, 2005. 1) The authors are supported by the Outstanding Youth Grant of NSF of China (No.60225002), a National Key Basic Research Project of China (2004CB318000), NSF of China (No. 60473132), the TRAPOYT in Higher Education Institute of MOE of China, and SRF for ROCS, SEM

2 Z.J. HUANG, J.S. DENG, Y.Y. FENG AND F.L. CHEN not simple. In the T-spline theory, the local refinement is dependent on the structure of the mesh, and its complexity is uncertain. Whether T-spline blending functions are always linearly independent is an open question [6]. The reason leading to these problems is that the spline over every cell of the mesh is not a polynomial, but a piecewise polynomial. In [2], Deng etal formulated the concept of T-meshes, and studied the spline space over T-meshes. They forced the spline on every cell to be a tensor-product polynomial and achieve the specified smoothness across common edges, and derived a dimension formula when the smoothness is less than half of the degree of polynomials with a method based on B-nets. In the theory of multivariate spline, smoothing cofactor method [7] is another dominant approach to calculate the dimension of some specified spline space. In this paper, we derive a dimension formula equivalent to Deng’s formula with the smoothing cofactor method. The proof is longer than the B-net version, but it is revelatory. Based on some results in this paper, we have implemented a quasi-real-time algorithm, which will be explored in another forthcoming paper, to calculate the dimension of a general spline space over T-meshes. And we expect that we can generalize Deng’s formula based on the smoothing cofactor method in the future. The paper is organized as follows. Section 2 presents a brief review of the spline spaces over T-meshes. In Section 3, by introducing the concepts of vertex cofactor and in-line, we derive a dimension formula for the spline space S(m, n, α, β, T ) when m 2α + 1 and n 2β + 1 with the smoothing cofactor method, and prove that it is equivalent to Deng’s formula. In the final section, we conclude the paper with some further research problems. 2. Spline spaces over T-meshes In this section, we first present some concepts related with T-meshes, and then review spline function spaces over T-meshes. 2.1 T-mesh a b Figure 1: Examples of T-mesh A T-mesh is basically a rectangular grid that allows T-junctions [5]. The longest possible horizontal or vertical line segments to make up a T-mesh are called grid lines. We assume that the endpoints of each grid line in the T-mesh must be on two other grid lines, and each cell or facet (the area without any line segment inside it) in the grid must be a rectangle. Figure 1 illustrates two examples of T-meshes, while in Figure 2 two examples of non-T-meshes are shown. A grid point in a T-mesh is also called a vertex of the T-mesh. If a vertex is on the boundary grid line of a T-mesh, then is called a boundary vertex. Otherwise, it is called an interior vertex. For example, bi, i = 1,..., 10 in Figure 3 are boundary vertices, and all the

New Proof of Dimension Formula of Spline Spaces over T-meshes via Smoothing Cofactors 3 a b Figure 2: Examples of non-T-mesh b1 b2 b3 b4 b5 b8 b7 b6 b9 b10 b11 v1 v2 v3 v4 v5 v6 v7 Figure 3: A T-mesh with notations other vertices vi, i = 1,..., 5 are interior vertices. Interior vertices have two types. One is crossing, for example, v2 in Figure 3; and the other is T-junctional, for example, v1 in Figure 3. We call them crossing vertices and T-vertices respectively. The line segment connecting two adjacent vertices on a grid line is called an edge of the T-mesh. If an edge is on the boundary of the T-mesh, then it is called a boundary edge; otherwise it is called an interior edge. For example, in Figure 3, b11v1 and v1v2 are interior edges while b1b2 is a boundary edge. Except the boundary grid lines, there are three types of grid lines. We call a grid line a cross-cut or a ray, if both or only one of its endpoints lies on the boundaries, respectively. For example, in Figure 3, b5b10 and b4b11 are cross-cuts, while v5b2 , v4b7 and v7b9 are rays. Now we define the third type of grid lines. A grid line is called a in-line, if none of its endpoints lie on the boundaries. For example, in Figure 3, v1v6 is a in-line. For any grid line, it consists of one or several edges. We define its valence as the number of edges on the grid line. Two cells are called adjacent if they share a common edge as part of their boundaries. If one cell is above(below) the other, then they are called adjacent vertically. If one cell is on the left(right) of the other, then they are called adjacent horizontally. A cell is called adjacent to a grid line (an edge or composition of several edges) if some boundary line of the cell is part of the grid line. As in [2], we consider only T-meshes whose boundary grid lines form a rectangle, see Figure 1(b). We call this type of T-meshes regular T-meshes. 2.2 The spline space Given a T-mesh T , we use F to denote all the cells in T and Ω to denote the region occupied

New Proof of Dimension Formula of Spline Spaces over T-meshes via Smoothing Cofactors 5 According to the smoothing cofactor theory, if the common edge e is on the straight line x − x0 = 0(see Figure 4(a)), then there exists λ(x, y) ∈ Pm−α−1,n such that s2(x, y) − s1(x, y) = λ(x, y)(x − x0) α+1. (2) If the common edge e is on the straight line y − y0 = 0(see Figure 4(b)), then there exists μ(x, y) ∈ Pm,n−β−1 such that s2(x, y) − s1(x, y) = μ(x, y)(y − y0) β+1. (3) Here λ(x, y) and μ(x, y) are called the smoothing cofactors of s(x, y) across the corresponding edges, respectively. vi λi1 λi2 μi1 μi2 a vi λi1 λi2 μi vi λi1 λi2 μi b μi1 vi μi2 λi μi1 vi μi2 λi c Figure 5: Conformality conditions We use λ(x, y) to denote the smoothing cofactor across a vertical interior edge from left to right, and μ(x, y) to denote the smoothing cofactor across a horizontal interior edge from bottom to top. Let V = {ν1,...,νV }, Eh = {εh 1 ,...,εh Eh }, Ev = {εv 1,...,εv Ev }. be the set of interior vertices, interior horizontal edges and interior vertical edges, respectively. Hence the set of interior edges E = Eh ∪ Ev. Suppose νi = (xi, yi) is a interior vertex of T , which is a crossing vertex or a T-vertex(see Figure 5). The horizontal T-vertex on the left of Figure 5(b) is called a right T-vertex, while the one on the right of Figure 5(b) is called a left T-vertex. The vertical T-vertex on the top of Figure 5(c) is called a down T-vertex, while the one on the bottom of Figure 5(c) is called an up T-vertex. If νi is a crossing vertex(Figure 5(a)), then the conformality condition of s(x, y) at νi is (λi1(x, y) − λi2(x, y))(x − xi) α+1 + (μi1(x, y) − μi2(x, y))(y − yi) β+1 ≡ 0; (4) if νi is a horizontal T-vertex (Figure 5(b)), then the conformality condition of s(x, y) at νi is (λi1(x, y) − λi2(x, y))(x − xi) α+1 ∓ μi(x, y)(y − yi) β+1 ≡ 0, (5) for a right T-vertex, the sign before μi(x, y) is ‘−’, otherwise ‘+’; if νi is a vertical T-vertex (Figure 5(c)), then the conformality condition of s(x, y) at νi is ∓λi(x, y)(x − xi) α+1 + (μi1(x, y) − μi2(x, y))(y − yi) β+1 ≡ 0, (6)

6 Z.J. HUANG, J.S. DENG, Y.Y. FENG AND F.L. CHEN for a down T-vertex, the sign before λi(x, y) is ‘−’, otherwise ‘+’. Here λi(x, y), λi1(x, y), λi2(x, y) ∈ Pm−α−1,n, and μi(x, y), μi1(x, y), μi2(x, y) ∈ Pm,n−β−1. We analysis further the conformality conditions in Equation (4), (5) or (6). For Equation (4), since (x − xi)α+1 and (y − yi)β+1 are prime, we have λi1(x, y) − λi2(x, y) = vi(x, y)(y − yi) β+1, μi1(x, y) − μi2(x, y) = hi(x, y)(x − xi) α+1 for some hi(x, y), vi(x, y) ∈ Pm−α−1,n−β−1. Putting these back into Equation (4) gives (vi(x, y) + hi(x, y))(x − xi) α+1(y − yi) β+1 ≡ 0. Hence, vi(x, y) = −hi(x, y) = ci(x, y) ∈ Pm−α−1,n−β−1. We call ci(x, y) the vertex cofactor of s(x, y) corresponding to an interior vertex νi. Then the conformality condition at a crossing vertex in Equation (4) can be rewritten as λi1(x, y) − λi2(x, y) = ci(x, y)(y − yi) β+1, μi1(x, y) − μi2(x, y) = −ci(x, y)(x − xi) α+1. (7) Similarly, the conformality condition at a horizontal T-vertex in Equation (5) can be rewritten as λi1(x, y) − λi2(x, y) = ci(x, y)(y − yi) β+1, ∓μi(x, y) = −ci(x, y)(x − xi) α+1; (8) and the conformality condition at a vertical T-vertex in Equation (6) can be rewritten as ∓λi(x, y) = ci(x, y)(y − yi) β+1, μi1(x, y) − μi2(x, y) = −ci(x, y)(x − xi) α+1. (9) We note that, even if all the vertex cofactors ci(x, y), i = 1,...,V are determined, for each cross-cut, there is still one interior edge whose smoothing cofactor is completely free. Let Ec h and Ec v be the number of horizontal cross-cuts and the number of vertical cross-cuts respectively, and σ be the number of independent free coefficients of the vertex cofactors. Then the number of free coefficients of the smoothing cofactors of all interior edges is Ec h(m + 1)(n − β) + Ec v(m − α)(n + 1) + σ, hence, we have the following dimension formula of the spline space over a T-mesh: dim S(m, n, α, β, T )=(m + 1)(n + 1) + Ec h(m + 1)(n − β) + Ec v(m − α)(n + 1) + σ (10) 3.2 In-line conformality conditions If there are no in-lines in T , namely, T is a simple quasi-cross-cut partition, the vertex cofactors are relatively independent. Then we have σ = V (m − α)(n − β), and the dimension formula (10) becomes dim S(m, n, α, β, T )=(m+ 1)(n+ 1)+Ec h(m+ 1)(n−β)+Ec v(m−α)(n+ 1)+V (m−α)(n−β)