# Convergence Analysis of Regular Dynamic Loop-Like Subdivision Scheme

Authors: Xiangjun Zhao; Xiaoyang Liu; Mei Lu
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

This paper is concerned with the regular dynamic loop-like subdivision scheme based on the extension of Box-Spline method. The purpose of the addressed problem is to prove the convergence of the subdivision scheme and verify theC0 and C1 continuity by calculating the eigenvalues of the 2-neighbor subdivision matrix. Compared with the loop subdivision scheme in previous references, the designed scheme can generate exact revolving surfaces and hold a stronger modeling capability because the subdivision matrix can update regularly with the iteration procedure. Finally, some examples are given to illustrate the effectiveness of the proposed method.


---

## Body

## 1. Introduction

It is well known that the subdivision method is a powerful tool in the fields of free-form surface modeling and tensor product surfaces for a long time. Starting from an arbitrary initial control mesh, subdivision schemes can produce a sequence of finer and finer meshes converging to a originally described surface. If the sequence of control nets converges in a certain sense, such procedure can be used to generate surfaces. The subdivision operations are efficient and could be well applied to arbitrary topology polygon meshes. In addition, there exist adequate theoretical tools for analyzing its convergence and continuity. Therefore, the subdivision method has become a standard technique in both academic and industrial communities.In recent decades, there has been a tremendous progress in scheme construction [1–3]. Since the introduction of Catmull-Clark subdivision surfaces [4] at the end of the 1970s, many subdivision schemes have been proposed for various applications [5–8]. A unified framework with various essential and basic refinement operations has also been constructed in [9]. Recently, a subdivision method for triangle meshes has become an important research issue, because such meshes are well supported by software and hardware graphics systems and can be easily derived by most other representations. It is well known that the loop scheme originally proposed by Charles [8, 10] is a simple face-split approximation scheme for triangle meshes. Based on the triangular splines, the scheme produces surfaces which are always C2 continuous everywhere except at the extraordinary vertices where they are only C1 continuity. Boundary rules produce a cubic spline curve along the boundary, which only depends on control points on the boundary. An interior vertex with valence 6 and a boundary vertex with valence 4 are called as a regular vertex, while the others are irregular or extraordinary ones. The masks for the Loop scheme is shown in Figure 1. The scheme works as follows. (i)
Vertex updating rule: for every original vertex, a new vertex is calculated by using the suitable coefficients for 1-neighbor control points as shown in Figures1(a), 1(c), and 1(d).(ii)
Edge splitting rule: for every edge in the original mesh, a new vertex is calculated by using the masks as shown in Figure1(b).(iii)
Face splitting rule: every triangle in the original mesh produces six new vertices, three from original vertices and the others from original edges. These six vertices are constructed into four new triangles.Masks for loop scheme witha=1/8, b=3/8, c=1-nd, d=(1/n)(5/8-(3/8+(1/4)cos(2π/n))2), and e=6.
(a)
(b)
(c)
(d)The common feature of these methods lies in their parameters which are fixed in each step of subdivision operation, which is called as stationary subdivision. Unfortunately, since the shape of a stationary subdivision surface is totally determined by control meshes, it is not convenient to add further control except mesh modification. Hence, some nonstationary subdivision schemes should be introduced; for example, the authors in [11] extended the Doo-Sabin scheme to the nonstationary case and [12] proposed a nonstationary butterfly interpolatory subdivision scheme. However, the previous subdivision scheme cannot accurately represent some ordinary surfaces in engineering, such as cylinder, cone, or other revolving surfaces. In order to find a subdivision uniform method to represent quadric surfaces, revolve surfaces, and traditional subdivision ones, [13] proposed a method called semistationary subdivision, which can remedy the shortage of the traditional ones well. But, the above method can only be applied to the quadrilateral mesh and needs the further study for the triangle mesh. So, it is an urgent issue to find a subdivision method for triangle meshes to represent quadric surface, revolving surface, and traditional subdivision surface uniformly.On the other hand, the convergence is an important topic when studying subdivision surfaces. Doo and Sabin [5] first performed the convergence analysis by investigating the eigenstructure of subdivision matrices based on a discrete Fourier transformation. Ball and Storry [14] further exploited an approach based on the matrix eigenstructure for a tangential continuity analysis. However, their results could not guarantee that subdivision surfaces were regular at extraordinary vertices because it did not take the properties of basis functions into account [15]. For this, Reif [9] explored a method to deal with the continuity issue by establishing a characteristic map, which could be used to ensure the C1 continuity for subdivision schemes. Under the above framework, Peters and Reif [16] established a strict theoretical analysis about both the Doo-Sabin scheme and the Catmull-Clark one, while Umlauf [17] thoroughly examined the continuity of the Loop subdivision scheme. The approach described in [18] is an extension of Reif's work for subdivision schemes without a closed parametric form. In [19], Zorin proposed another method based on Z-polynomials when considering the C1 continuity of arbitrary subdivisions and developed a numerical algorithm for the C1 continuity verification. However, because the regular dynamic subdivision matrix is not fixed, it is impossible to use the classic criterion for subdivision convergence.Motivated by the above discussion, we will investigate the subdivision method for triangle mesh which can represent a revolving surface exactly. Firstly, a new subdivision scheme based on Box-Splines is proposed, and the subdivision matrix is constructed. Secondly, the characteristic spectrum of global subdivision matrix is analyzed, and the detailed analysis forC0 and C1 continuity is given. Finally, several illustrative examples are provided to demonstrate the effectiveness of the proposed approach.The main contribution of this paper is summarized as follows. (1) A novel subdivision scheme with a stronger modeling ability is proposed based on the new extended Box-Splines. (2) TheC0 and C1 continuity is strictly proved by calculating the characteristic spectrum of the global subdivision matrix. (3) An anisotropy subdivision scheme and a special control net pattern are constructed, and then the revolving surface is generated exactly.


## 2. Regular Dynamic Loop-Like Subdivision Scheme

In this section, we will introduce the regular dynamic loop-like subdivision scheme. Similar to the loop scheme, after one step of subdivision, the number of irregular vertices is fixed. If the mesh is further subdivided, irregular vertices will be isolated. In other words, each face contains at most one irregular vertex. In the following, we will assume that the sufficient subdivision steps have finished to generate the local subdivision structure just as shown in Figure2. The vertex marked as 0 is an irregular vertex with valence n. Its neighbors are separated by incident edges into n subregions, which are called as segments and marked in counterclockwise order. In each segment, from center to outside, the control vertices are also numbered in counterclockwise order. After k times subdivision, the vertex sequence around the irregular vertex is denoted as
(2.1)V(k)≜[V0(k);V1(k);…;Vn-1(k)]T,
where Vj(k)≜[vj,0(k),vj,1(k),…,vj,m-1(k)]T is the vertex subsequence in segment j.Figure 2
The subdivision stencil for continuity analysis.For L-level neighbors,m=(L+1)L/2+1. In order to analyze the first order continuity, we consider the 2-level vertex neighbors of the irregular vertex, that is, m=4. Here, we define v0(k)≜v0,0(k)=v1,0(k)=⋯=vn-1,0(k).Similar to the loop subdivision schemes [8], two successive vertex sequences hold the following relationship:
(2.2)V(k)=S(k)V(k-1),
where S(k) is a 4n×4n matrix related to the subdivision level index k. Obeying the former segmented control vertices coding rules, the subdivision matrix S(k) is made up of n×n matrix blocks Sj,j'(k) which size is 4×4. Thus, we have
(2.3)Vj(k)=∑j'=0n-1‍Sj,j'(k)Vj'(k-1).The subdivision matrix has the following properties.(1)
The sum of elements of each row is equal to 1.(2)
The matrix is cyclic symmetry, that is,(2.4)Sj(k)≜Sj,0(k)=Sj+j′,j′(k)j,j′∈ℤn.Based on the property (2), (2.2) can be rewritten as
(2.5)Vj(k)=∑j'=0n-1‍Sj+j'(k)Vj'(k-1),
where
(2.6)S0(k)=[(1-nβn(k))nβn(k)00b(k)b(k)00β6(k)1-6β6(k)β6(k)β6(k)a(k)b(k)0a(k)],S1(k)=[(1-nβn(k))nβn(k)000a(k)000β6(k)000b(k)00],Sl(k)=[(1-nβn(k))nβn(k)00000000000000],l=2,…,n-2,Sn-1k=[(1-nβn(k))nβn(k)000a(k)000β6(k)0β6(k)0000].Based on theC-Box-Splines [20–22], the generation function of a regular dynamic loop-like subdivision [13] and each parameter of the above formula could be obtained as follows:
(2.7)a=f4f+4f2,b=f+2f24f+4f2,c=2+8f3,d=(10-(3/2+cos(2π/n))2)n,βn=dc+nd,
where the kernel function is chosen as
(2.8)f(k)=cos(2-kα0)(k∈ℤ+).
Of course, the kernel function could be some others with the same or faster convergence rate.It is known that the characteristic spectrum ofS(k) is needed when studying the convergence of the subdivision scheme [9]. Next, we will analyze the characteristic spectrum of S(k) in detail.For the block circulant matrix(2.9)S=[S0S1⋯Sn-1Sn-1S0⋯Sn-2⋮⋮⋱⋮S1S2⋯S0],
where Sl=(sij)m×m(l=0,1,…,n-1), we denote S≜bcirc(S0,S1,…,Sn-1), ωn=e2π-1/n, Wij=ϖn-ijIm×m(i,j∈{0,1,…,n-1}), and W=(Wij)n×n for simplicity.Let(2.10)S~=W-1SW,
which is indeed a similarity transformation of matrix S.Denote(2.11)S~=diag(S~0,S~1,…,S~n-1),
where S~l=(1/n)∑i=0n-1‍SiWil.Then, we have the following Lemma.Lemma 2.1.
The matricesS~ and S have the same eigenvalues.The above lemma is easy to be verified (see [23] for details) and we omit its proof here.Theorem 2.2.
The eigenvalues of the subdivision matrix(2.12)S(k)=bcirc(S0(k),S1(k),…,Sn-1(k))
are δi,0, β6(k), a(k), and b(k)+a(k)(ϖni(1-δi,0)+ϖn-i(1-δi,0))-nβn(k)δi,0, where i=1,…,n-1, and δi,j is the Kronecker delta.Proof.
Let(2.13)S~(k)=W-1S(k)W=diag(S~0(k),S~1(k),…,S~n-1(k)).
By (2.11), we have
(2.14)S~0(k)=S0(k)+S1(k)+(n-3)Sl(k)+Sn-1(k)=[1-nβn(k)nβn(k)00b(k)b(k)+2a(k)00β6(k)1-4βn(k)β6(k)2β6(k)a(k)2b(k)0a(k)],S~i(k)=S0(k)+ϖn-iS1(k)-(1+ϖni+ϖn-i)Sl(k)+ϖniSn-1(k)=[0000b(k)b(k)+a(k)(ϖni+ϖn-i)00β6(k)1-6β6(k)+(ϖni+ϖn-i)β6(k)β6(k)(1+ϖni)β6(k)a(k)b(k)+b(k)ϖn-i0a(k)].
Hence, the eigenvalues of the submatrixS~0(k) are 1, b(k)-2a(k)-nβn(k), β6(k), and a(k). The eigenvalues of the submatrix S~i(k) are 0, b(k)+a(k)(ϖni+ϖn-i),β6(k), and a(k).
Then, we can obtain the eigenvalues ofS(k) as follows:
(2.15)δi,0,β6(k),a(k),b(k)+a(k)(ϖni(1-δi,0)+ϖn-i(1-δi,0))-nβn(k)δi,0.


## 3. Analysis on Convergence of the Subdivision Scheme

In this section, we mainly focus on the convergence of the subdivision case around irregular vertices. At the regular vertices, the generated surfaces have similar properties as theC-Box-Splines in [22], which is C2 continuity. In the following, the convergence of the subdivision scheme will be firstly discussed, and then the continuity of the subdivision surfaces.


### 3.1. Convergence of the Subdivision Scheme

In this subsection, we will analyze the convergence of regular dynamic loop-like subdivision scheme. The subdivision process can be expressed as(3.1)V(k)=S(k)V(k-1)=S(k)S(k-1)V(k-2)=⋯=∏i=1k‍S(i)V(0).
Let
(3.2)M(k)≜∏i=1k‍S(i).
By induction, we can conclude that the sum of each row of M(k) is equal to 1.DefineT(m)=S(m)-S,S=limm→∞S(m), and sumi(m)=∑l=14n|(S(m)-S)i,l|, by (2.7), we have
(3.3)sumi(m)∈limk→∞{2|βn(m)-βn(k)|,2|b(m)-b(k)|,9|β6(m)-β6(k)|,2|a(m)-a(k)|+|b(m)-b(k)|,|a(m)-a(k)|,|β6(m)-β6(k)|,|b(m)-b(k)|,2|β6(m)-β6(k)|},
where i is the row number of the matrix.Whenf=cos(2-kα0), we have
(3.4)max{sumi(m)}⩽C14m,
where C is a constant number.Theorem 3.1.
If subdivision stepk→∞ and the kernel function f(k) converges to 1 with a geometric series rate, then a regular dynamic loop-like subdivision scheme is convergent.Proof.
Under an identical transformation toM(m), we get
(3.5)M(m)=Sm+∑j=1m-1‍Sm-jT(j)M(j-1)+T(m)M(m-1).
For the k dimensional column vector x, the Smx is convergent. Next, we only need to prove that T(m)M(m-1)x and ∑j=1m-1Sm-jT(j)M(j-1)x are convergent.
First of all, let∥x∥≜max1⩽i⩽k∥xi∥, where xi is the ith component of x. Since all elements of the matrix S(j) are nonnegative and the sum of the row element is always equal to 1, we have
(3.6)|(S(j)x)i|⩽∥x∥,i=1,…,k,∥S(j)x∥⩽∥x∥.
Thus, we have
(3.7)∥M(m-1)x∥=∥∏j=1m-1‍S(j)x∥⩽∥x∥.
By (3.4), we get
(3.8)∥T(m)M(m-1)x∥⩽C14m∥M(m-1)x∥⩽C114m∥x∥,
where C1 is a constant.
Secondly, let(3.9)ym=∑j=1m-1‍Sm-jT(j)M(j-1)x.
We claim that {∥y1∥,∥y2∥,…} is Cauchy sequence and prove it as follows.
Form,l⩾1, one has
(3.10)∥ym+l-ym∥⩽∑j=1m-1‍∥Sm+l-jT(j)M(j-1)x-Sm-jT(j)M(j-1)x∥+∑j=mm+l-1‍∥Sm+l-jT(j)M(j-1)x∥.
Denotev(j)=T(j)M(j-1)x, we have v(j)=v1β1+v2β2+⋯+v4nβ4n for some βi∈ℝ, where v1,…,v4n are the eigenvectors of S. Then,
(3.11)∥Sm+l-jv(j)-Sm-jv(j)∥=∥λ2m-j(λ2l-1)v2β2+⋯+λnm-j(λ4nl-1)v4nβ4n∥⩽λ2m-j(4n-1)max2⩽l⩽4n∥vlβl∥.
Using the standard results in a numerical analysis, we get(3.12)max2⩽l⩽4n∥vlβl∥⩽∥T∥∥T-1∥∥v(j)∥,
where ∥T∥ and ∥T-1∥ are row sum norms of T and T-1, respectively. T is the transformation, which transforms the basis {e1,…,e4n} of ℝ4n to the basis {v1t,…,v4nt} of ℝ4n.
Then, by (3.4), (3.8), and (3.11), we have
(3.13)∥Sm+l-jv(j)-Sm-jv(j)∥=(k-1)C2λ2m-j(14)j∥T∥∥T-1∥∥x∥,
where C2 is a constant.
Similarly, we have(3.14)∥Sm+l-jT(j)M(j-1)x∥⩽C3δ1j∥x∥,
where C3 also is a constant.
By Theorem2.2 and (2.7), one obtains
(3.15)38⩽λ2⩽58.
Substituting (2.4), (3.8), and (3.14) into (3.10), we obtain
(3.16)∥ym+l-ym∥⩽∥x∥{C2′(k-1)∑j=1m-1‍{λ2m-j14j}+C3′∑j=mm+l-1‍14j}.
From 4λ2>1, then both ∑j=1∞(1/(4λ2)j) and ∑j=1∞(1/4j) are convergent.
Then we get(3.17)limm→∞∥ym+l-ym∥=0,
that is to say, {∥y1∥,∥y2∥,…} is a Cauchy sequence, that is, ∑j=1m-1Sm-jT(j)M(j-1)x is convergent. Hence, the subdivision scheme is convergent.


### 3.2. Continuity of the Subdivision Surface

#### 3.2.1. Subdivision Matrix Analysis

Firstly, we need to prove the following lemma.Lemma 3.2.
Let(3.18)Ξ~(k)=∏k=nt,nt-1,…,n1‍[1-a(k)a(k)b(k)1-b(k)].
Their eigenvalues are
(3.19)∏k=nt,nt-1,…,n1‍(1-a(k)-b(k)).Proof.
Since(3.20)[1-a(k)a(k)b(k)1-b(k)]=I+b(k)[-c(k)c(k)1-1],
where c(k)=a(k)/b(k), and
(3.21)A(k)=b(k)[-c(k)c(k)1-1],
then
(3.22)Ξ~(k)=I+A(nt)+A(nt-1)+⋯+A(n1)+A(nt)A(nt-1)+⋯+A(n2)A(n1)+⋯+∏k=nt,nt-1,…,n1‍A(k).
From
(3.23)A(k2)A(k1)=bk2bk1[c(k2)(c(k1)+1)-c(k2)(c(k1)+1)-(c(k1)+1)c(k1)+1]=-b(k1)(c(k1)+1)A(k2),
we have
(3.24)Ξ~(k)=I+∑1⩽k1⩽t‍A(nk1)+∑1⩽k2⩽t1⩽k1⩽t1k1<k2∏j=nk2,nk1‍A(j)+⋯+∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki∏j=nki,…,nk1‍A(j)+⋯+∑1⩽kt⩽t⋯1⩽k1⩽tk1<⋯<kt‍∏j=nkt,…,nk1‍A(j)=I+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(A(nki)∏j=nki-1,…,nk1‍b(j)(-c(j)-1))=[1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))].
Furthermore, their eigenvalues could be obtained as follows:
(3.25)λ0=1,λ1=1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j))+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j))=1+∑i=1t∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍∏j=nki,…,nk1‍(-a(j)-b(j))=∏k=nt,nt-1,…,n1‍(1-a(k)-b(k)).Theorem 3.3.
The eigenvalues ofM(k) are 1,0, ∏j=1k(b(j)+a(j)(ϖni+ϖn-i)), ∏j=1k(1-nβn(j)-b(j)), ∏j=1kβ6(j), and ∏j=1ka(j), and the last two eigenvalues are the repeated ones.Proof.
SinceS(k) is a block circulant matrix, so is M(k). Let
(3.26)M~=W-1MW,
we know M~ is a block circulant matrix, and
(3.27)M~=bcirc(∏j=1k‍S~0(j),∏j=1k‍S~1(j),…,∏j=1k‍S~n-1(j)).
Denote(3.28)M~(k)≜diag(M~0(k),M~1(k),…,M~n-1(k)),
we have
(3.29)M~i(k)≜∏j=1k‍S~i(j)=[M~i,0(k)0M~i,2(k)M~i,1(k)],
and the eigenvectors of M~i(k) only relate to S~i,0(k),S~i,1(k). The following two cases need to be discussed separately.
(1) Ifi=0, then
(3.30)M~0,0(k)=∏j=1k‍[1-nβn(j)nβn(j)b(j)1-b(j)],M~0,1(k)=[∏j=1k‍β6(j)x0∏j=1k‍a(j)].
By Lemma3.2, we can get the eigenvalues of M~0,0(k):
(3.31)λ0=1,λ1=∏j=1k‍(1-nβn(j)-b(j)).
The eigenvalues of M~0,1(k) are
(3.32)λ2=∏j=1k‍β6(j),λ3=∏j=1k‍a(j).
(2) Ifi≠0, then
(3.33)M~i,0(k)=[00x∏j=1k‍(b(j)+a(j)(ϖni+ϖn-i))],M~i,1(k)=[∏j=1k‍β6(j)y0∏j=1k‍a(j)],
where x, y are real numbers. Their eigenvalues are
(3.34)λ0=∏j=1k‍(b(j)+a(j)(ϖni+ϖn-i)),λ1=0,λ2=∏j=1k‍β6(j),λ3=∏j=1k‍a(j),
respectively.Theorem 3.4.
If the eigenvalues of matrixM(k) are ordered from the greatest to the least, then one has
(3.35)λ0=1>λ1=λ2>λ3⩾⋯⩾λ4n-1=0,(3.36)limk→∞λi=0,i≠0.Proof.
Since each row sum ofM(k) is equal to 1, then (1,1,…,1)T must be one of eigenvectors corresponding to the eigenvalue 1.
(1) We prove the (3.35) firstly.
Let(3.37)λ1=∏j=1k‍(b(j)+2a(j)cos2πn),λ2=∏j=1k‍(b(j)+2a(j)cos2(n-1)πn).
It is easy to derive that
(3.38)λ1=λ2=∏j=1k‍(b(j)+2a(j)cos2πn).
In order to prove that the absolute value ofλ1 is the maximum value among all eigenvalues except for λ0, we need to prove
(3.39)|λ1|⩾∏j=1k‍(b(j)+2a(j)cos(2πin)),i=1,…,n-1,(3.40)|λ1|>|∏j=1k‍(1-nβn(j)-b(j))|,
and then
(3.41)|λ1|⩾∏j=1k‍β6(j)⩾∏j=1k‍a(j)⩾0.
(a) For the inequality (3.39), if n=3, the group has eigenvalues λ1 and λ2, then the inequality is obvious to be obtained. If n≠3, since
(3.42)cos(2π(n-i)n)=cos(2πin),
and according to the monotonicity of the function cos(2πi/n), we have that
(3.43)λ1=λ2=∏j=1k‍(b(j)+2a(j)cos(2πn))
is the maximum value in the group.
(b) For the inequality (3.40), we only need to prove
(3.44)|b(j)+2a(j)cos(2πn)|>|1-nβn(j)-b(j)|,
where
(3.45)nβn(j)=nd2+8fj3+nd=10-(3/2+cos(2π/n))22+8fj3+(10-(3/2+cos(2π/n))2).
Whenn=3, we have
(3.46)1-nβn(j)-b(j)=16fj5+24fj4-14fj2-3fj4fj(11+8fj3)(1+fj),b(j)+2a(j)cos(2πn)=b(j)-a(j)=4fj28fj+8fj2.
Then,
(3.47)(b(j)-a(j))-(1-nβn(j)-b(j))=3fj(1+12fj-8fj3)4fj(11+fj3)(1+fj).
Since 1/2<fj⩽1, the above formula is positive; that is, when n=3, inequality (3.40) holds.
Whenn>3, since
(3.48)10-(3/2+1)22+8fj3+(10-(3/2+1)2)⩽nβn(j)⩽10-(3/2+0)22+8fj3+(10-(3/2+0)2),
that is
(3.49)1523+32fj3⩽nβn(j)⩽3139+32fj3,
then we have
(3.50)1-nβn(j)-b(j)⩽1-1523+32fj3-2fj+4fj28fj+8fj2=9fj-14fj2+96fj4+64fj54fj(23+32fj3)(1+fj),b(j)+2a(j)cos(2πn)⩾b(j)+2a(j)×0=2fj+4fj28fj+8fj2,b(j)-(1-nβn(j)-b(j))=fj(7+30fj-32fj3)2fj(23+32fj3)(1+fj).
By 1/2<fj⩽1 again, the conclusion could be obtained naturally.
To Sum up, we have(3.51)|λ1|>|∏j=1k‍(1-nβn(j)-b(j))|.
(c) For the inequality (3.41), we have
(3.52)λ1=∏j=1k‍(b(j)+2a(j)cos(2πin))⩾∏j=1k‍(b(j)-a(j)).
Since
(3.53)(bj-aj)-β6=(2fj+4fj28fj+8fj2-2fj8fj+8fj2)-18+8fj3=4fj4+3fj-18(1+fj)(1+fj3),
and 1/2<f⩽1, we have
(3.54)λ1>∏j=1k‍β6(j).
From(3.55)(bj-aj)-aj=4fj2-2fj8fj+8fj2=2fj-14+4fj,
we have
(3.56)λ1>∏j=1k‍a(j)>0.
Then, the eigenvalues ofM(k) hold the properties (2). That is to say, λ0=1,λ1=λ2=∏j=1k(b(j)+2a(j)cos(2πi/n)), and 1=|λ0|>|λ1|=|λ2|>|λ3|⩾⋯⩾|λ4n-1|=0.
(2) We verify (3.36).
Since(3.57)|b(j)+2a(j)cos(2πn)|⩽|b(j)+2a(j)|=ς<1,
we have
(3.58)limk→∞|∏j=1k‍(b(j)+2a(j)cos(2πin))|⩽limk→∞∏j=1k‍ς=limk→∞ςk=0,
and 1=|λ0|>|λ1|=|λ2|>|λ3|⩾⋯⩾|λ4n-1|=0; thus we have limk→∞λi=0,i≠0.
Now, the proof of Theorem3.4 is completed.


#### 3.2.2.G0 Continuity

Theorem 3.5.
If the kernel functionfj has the convergence rate as Theorem 3.3, then the subdivision surface is continuous.Proof.
Let(3.59)M(k)di=λidi,V(0)=∑i=04n-1‍ai⊗di,
where i=1,2,…,4n-1, ⊗ denotes direct a product, and ai is an undetermined triple coefficient.
Since(3.60)V(k)=M(k)V(0)=λ0(k)(a0⊗d0+∑i=14n-1‍(λi(k)λ0(k))ai⊗di),
where λ0(k)=1,d0(k)=[1,1,…,1]T, and limk→∞λi→0(i≠0). By Theorems 3.3 and 3.4, we have, when k→∞,M(k)V(0) is convergent and ai is unique.
Let(3.61)vl=(000⋯⋯⋯︸l-3010⋯0010⋯0010⋯0),vt=(000⋯⋯⋯︸t-3010⋯0010⋯0010⋯0).
Given any two points whose coordinates arelth, tth, component of V(k), denoted as Vl(k),Vt(k), we have
(3.62)limk→∞∥Vl(k)-Vt(k)∥=∥vl(M(∞)V(0))-vt(M(∞)V(0))∥=(vl-vt)∥∑i=04n-1‍λi(∞)ai⊗di∥=(vl-vt)∥λ0(∞)a0⊗d0∥.
By (3.60), we have
(3.63)limk→∞∥Vl(k)-Vt(k)∥=0.
That is to say that the subdivision surface is G0 continuity.


#### 3.2.3.G1 Continuity

Based on the above result, we analyze the continuity of loop-like subdivision surface.Theorem 3.6.
If the kernel functionf(k) has the convergence rate as Theorem 3.1, then the subdivision surface is tangent plane continuity, that is, G1 continuity.Proof.
We will verify that there exists a common tangent plane around vertexV0(k) so as to ensure that the subdivision surface is G1 continuity.
Given any three points whose coordinates arelth, sth, and tth component of V(k), denoted as Vl(k),Vs(k), and Vt(k), by Theorem 3.4, we have
(3.64)limk→∞(Vl(k)-Vt(k))=(vl-vt)(λ0a0⊗d0+λ1(∞)(a1⊗d1+a2⊗d2+∑i=34n-1‍(ai⊗diλi(∞)λ1(∞))))=(vl-vt)λ1(∞)(a1⊗d1+a2⊗d2).
Let
(3.65)Γlt=limk→∞Vl(k)-Vt(k)∥Vl(k)-Vt(k)∥,
we have
(3.66)Γlt=(vl-vt)(a1⊗d1+a2⊗d2)∥(vl-vt)(a1⊗d1+a2⊗d2)∥=c1a1+c2a2∥c1a1+c2a2∥.
Similarly, we have
(3.67)Γst=(vs-vt)(a1⊗d1+a2⊗d2)∥(vs-vt)(a1⊗d1+a2⊗d2)∥=c3a1+c4a2∥c3a1+c4a2∥.
Then,
(3.68)limk→∞Nlt×st(k)∥Nlt×st(k)∥=Γlt×Γst∥Γlt×Γst∥=(c1a1+c2a2)×(c3a1+c4a2)∥(c1a1+c2a2)×(c3a1+c4a2)∥=a2×a1∥a2×a1∥.
Hence, when k→∞, the vertex around the V0 has a common normal vector. That is to say that the subdivision surface is G1 continuity.


#### 3.2.4.C1 Continuity

According to [18], besides the eigenvalues of M(k) satisfy (3.35), the characteristic maps associated with M(k) should be regular and injective for obtaining global C1 continuity. The characteristic map is defined as the subdivision surface generated by refining an initial mesh whose topological structure is identical with the subdivision stencil [24], just as shown in Figure 2. If both λ1 and λ2 are real, the horizontal and longitudinal coordinates of the ith control point of the initial control mesh come from the corresponding elements of the eigenvectors of λ1 and λ2, and the vertical coordinate is assumed to be zero, respectively.The regularity and injectivity of this map can be judged from the triangulation obtained from the control points by some steps subdivision [25]. Similar to many other studies, this paper only gives numerical evidence to verify the regularity and injectivity of the characteristic map of the loop-like subdivision scheme. The characteristic maps with valences n=3–50 are verified and they all hold a good shape. The obtained results are presented in Figure 3.Visualization of characteristic maps: (a)–(d) control nets from the eigenvectors ofM(k) with valences n=3,5,8,19, and f(k)=1-1/22k-1; (e)–(h) control nets with valences n=3,5,8,19, and f(k)=cos(π/(2kn)); (i)–(p) local regions around the irregular vertex of the characteristic maps after four subdivision steps.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)


## 3.1. Convergence of the Subdivision Scheme

In this subsection, we will analyze the convergence of regular dynamic loop-like subdivision scheme. The subdivision process can be expressed as(3.1)V(k)=S(k)V(k-1)=S(k)S(k-1)V(k-2)=⋯=∏i=1k‍S(i)V(0).
Let
(3.2)M(k)≜∏i=1k‍S(i).
By induction, we can conclude that the sum of each row of M(k) is equal to 1.DefineT(m)=S(m)-S,S=limm→∞S(m), and sumi(m)=∑l=14n|(S(m)-S)i,l|, by (2.7), we have
(3.3)sumi(m)∈limk→∞{2|βn(m)-βn(k)|,2|b(m)-b(k)|,9|β6(m)-β6(k)|,2|a(m)-a(k)|+|b(m)-b(k)|,|a(m)-a(k)|,|β6(m)-β6(k)|,|b(m)-b(k)|,2|β6(m)-β6(k)|},
where i is the row number of the matrix.Whenf=cos(2-kα0), we have
(3.4)max{sumi(m)}⩽C14m,
where C is a constant number.Theorem 3.1.
If subdivision stepk→∞ and the kernel function f(k) converges to 1 with a geometric series rate, then a regular dynamic loop-like subdivision scheme is convergent.Proof.
Under an identical transformation toM(m), we get
(3.5)M(m)=Sm+∑j=1m-1‍Sm-jT(j)M(j-1)+T(m)M(m-1).
For the k dimensional column vector x, the Smx is convergent. Next, we only need to prove that T(m)M(m-1)x and ∑j=1m-1Sm-jT(j)M(j-1)x are convergent.
First of all, let∥x∥≜max1⩽i⩽k∥xi∥, where xi is the ith component of x. Since all elements of the matrix S(j) are nonnegative and the sum of the row element is always equal to 1, we have
(3.6)|(S(j)x)i|⩽∥x∥,i=1,…,k,∥S(j)x∥⩽∥x∥.
Thus, we have
(3.7)∥M(m-1)x∥=∥∏j=1m-1‍S(j)x∥⩽∥x∥.
By (3.4), we get
(3.8)∥T(m)M(m-1)x∥⩽C14m∥M(m-1)x∥⩽C114m∥x∥,
where C1 is a constant.
Secondly, let(3.9)ym=∑j=1m-1‍Sm-jT(j)M(j-1)x.
We claim that {∥y1∥,∥y2∥,…} is Cauchy sequence and prove it as follows.
Form,l⩾1, one has
(3.10)∥ym+l-ym∥⩽∑j=1m-1‍∥Sm+l-jT(j)M(j-1)x-Sm-jT(j)M(j-1)x∥+∑j=mm+l-1‍∥Sm+l-jT(j)M(j-1)x∥.
Denotev(j)=T(j)M(j-1)x, we have v(j)=v1β1+v2β2+⋯+v4nβ4n for some βi∈ℝ, where v1,…,v4n are the eigenvectors of S. Then,
(3.11)∥Sm+l-jv(j)-Sm-jv(j)∥=∥λ2m-j(λ2l-1)v2β2+⋯+λnm-j(λ4nl-1)v4nβ4n∥⩽λ2m-j(4n-1)max2⩽l⩽4n∥vlβl∥.
Using the standard results in a numerical analysis, we get(3.12)max2⩽l⩽4n∥vlβl∥⩽∥T∥∥T-1∥∥v(j)∥,
where ∥T∥ and ∥T-1∥ are row sum norms of T and T-1, respectively. T is the transformation, which transforms the basis {e1,…,e4n} of ℝ4n to the basis {v1t,…,v4nt} of ℝ4n.
Then, by (3.4), (3.8), and (3.11), we have
(3.13)∥Sm+l-jv(j)-Sm-jv(j)∥=(k-1)C2λ2m-j(14)j∥T∥∥T-1∥∥x∥,
where C2 is a constant.
Similarly, we have(3.14)∥Sm+l-jT(j)M(j-1)x∥⩽C3δ1j∥x∥,
where C3 also is a constant.
By Theorem2.2 and (2.7), one obtains
(3.15)38⩽λ2⩽58.
Substituting (2.4), (3.8), and (3.14) into (3.10), we obtain
(3.16)∥ym+l-ym∥⩽∥x∥{C2′(k-1)∑j=1m-1‍{λ2m-j14j}+C3′∑j=mm+l-1‍14j}.
From 4λ2>1, then both ∑j=1∞(1/(4λ2)j) and ∑j=1∞(1/4j) are convergent.
Then we get(3.17)limm→∞∥ym+l-ym∥=0,
that is to say, {∥y1∥,∥y2∥,…} is a Cauchy sequence, that is, ∑j=1m-1Sm-jT(j)M(j-1)x is convergent. Hence, the subdivision scheme is convergent.


## 3.2. Continuity of the Subdivision Surface

### 3.2.1. Subdivision Matrix Analysis

Firstly, we need to prove the following lemma.Lemma 3.2.
Let(3.18)Ξ~(k)=∏k=nt,nt-1,…,n1‍[1-a(k)a(k)b(k)1-b(k)].
Their eigenvalues are
(3.19)∏k=nt,nt-1,…,n1‍(1-a(k)-b(k)).Proof.
Since(3.20)[1-a(k)a(k)b(k)1-b(k)]=I+b(k)[-c(k)c(k)1-1],
where c(k)=a(k)/b(k), and
(3.21)A(k)=b(k)[-c(k)c(k)1-1],
then
(3.22)Ξ~(k)=I+A(nt)+A(nt-1)+⋯+A(n1)+A(nt)A(nt-1)+⋯+A(n2)A(n1)+⋯+∏k=nt,nt-1,…,n1‍A(k).
From
(3.23)A(k2)A(k1)=bk2bk1[c(k2)(c(k1)+1)-c(k2)(c(k1)+1)-(c(k1)+1)c(k1)+1]=-b(k1)(c(k1)+1)A(k2),
we have
(3.24)Ξ~(k)=I+∑1⩽k1⩽t‍A(nk1)+∑1⩽k2⩽t1⩽k1⩽t1k1<k2∏j=nk2,nk1‍A(j)+⋯+∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki∏j=nki,…,nk1‍A(j)+⋯+∑1⩽kt⩽t⋯1⩽k1⩽tk1<⋯<kt‍∏j=nkt,…,nk1‍A(j)=I+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(A(nki)∏j=nki-1,…,nk1‍b(j)(-c(j)-1))=[1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))].
Furthermore, their eigenvalues could be obtained as follows:
(3.25)λ0=1,λ1=1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j))+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j))=1+∑i=1t∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍∏j=nki,…,nk1‍(-a(j)-b(j))=∏k=nt,nt-1,…,n1‍(1-a(k)-b(k)).Theorem 3.3.
The eigenvalues ofM(k) are 1,0, ∏j=1k(b(j)+a(j)(ϖni+ϖn-i)), ∏j=1k(1-nβn(j)-b(j)), ∏j=1kβ6(j), and ∏j=1ka(j), and the last two eigenvalues are the repeated ones.Proof.
SinceS(k) is a block circulant matrix, so is M(k). Let
(3.26)M~=W-1MW,
we know M~ is a block circulant matrix, and
(3.27)M~=bcirc(∏j=1k‍S~0(j),∏j=1k‍S~1(j),…,∏j=1k‍S~n-1(j)).
Denote(3.28)M~(k)≜diag(M~0(k),M~1(k),…,M~n-1(k)),
we have
(3.29)M~i(k)≜∏j=1k‍S~i(j)=[M~i,0(k)0M~i,2(k)M~i,1(k)],
and the eigenvectors of M~i(k) only relate to S~i,0(k),S~i,1(k). The following two cases need to be discussed separately.
(1) Ifi=0, then
(3.30)M~0,0(k)=∏j=1k‍[1-nβn(j)nβn(j)b(j)1-b(j)],M~0,1(k)=[∏j=1k‍β6(j)x0∏j=1k‍a(j)].
By Lemma3.2, we can get the eigenvalues of M~0,0(k):
(3.31)λ0=1,λ1=∏j=1k‍(1-nβn(j)-b(j)).
The eigenvalues of M~0,1(k) are
(3.32)λ2=∏j=1k‍β6(j),λ3=∏j=1k‍a(j).
(2) Ifi≠0, then
(3.33)M~i,0(k)=[00x∏j=1k‍(b(j)+a(j)(ϖni+ϖn-i))],M~i,1(k)=[∏j=1k‍β6(j)y0∏j=1k‍a(j)],
where x, y are real numbers. Their eigenvalues are
(3.34)λ0=∏j=1k‍(b(j)+a(j)(ϖni+ϖn-i)),λ1=0,λ2=∏j=1k‍β6(j),λ3=∏j=1k‍a(j),
respectively.Theorem 3.4.
If the eigenvalues of matrixM(k) are ordered from the greatest to the least, then one has
(3.35)λ0=1>λ1=λ2>λ3⩾⋯⩾λ4n-1=0,(3.36)limk→∞λi=0,i≠0.Proof.
Since each row sum ofM(k) is equal to 1, then (1,1,…,1)T must be one of eigenvectors corresponding to the eigenvalue 1.
(1) We prove the (3.35) firstly.
Let(3.37)λ1=∏j=1k‍(b(j)+2a(j)cos2πn),λ2=∏j=1k‍(b(j)+2a(j)cos2(n-1)πn).
It is easy to derive that
(3.38)λ1=λ2=∏j=1k‍(b(j)+2a(j)cos2πn).
In order to prove that the absolute value ofλ1 is the maximum value among all eigenvalues except for λ0, we need to prove
(3.39)|λ1|⩾∏j=1k‍(b(j)+2a(j)cos(2πin)),i=1,…,n-1,(3.40)|λ1|>|∏j=1k‍(1-nβn(j)-b(j))|,
and then
(3.41)|λ1|⩾∏j=1k‍β6(j)⩾∏j=1k‍a(j)⩾0.
(a) For the inequality (3.39), if n=3, the group has eigenvalues λ1 and λ2, then the inequality is obvious to be obtained. If n≠3, since
(3.42)cos(2π(n-i)n)=cos(2πin),
and according to the monotonicity of the function cos(2πi/n), we have that
(3.43)λ1=λ2=∏j=1k‍(b(j)+2a(j)cos(2πn))
is the maximum value in the group.
(b) For the inequality (3.40), we only need to prove
(3.44)|b(j)+2a(j)cos(2πn)|>|1-nβn(j)-b(j)|,
where
(3.45)nβn(j)=nd2+8fj3+nd=10-(3/2+cos(2π/n))22+8fj3+(10-(3/2+cos(2π/n))2).
Whenn=3, we have
(3.46)1-nβn(j)-b(j)=16fj5+24fj4-14fj2-3fj4fj(11+8fj3)(1+fj),b(j)+2a(j)cos(2πn)=b(j)-a(j)=4fj28fj+8fj2.
Then,
(3.47)(b(j)-a(j))-(1-nβn(j)-b(j))=3fj(1+12fj-8fj3)4fj(11+fj3)(1+fj).
Since 1/2<fj⩽1, the above formula is positive; that is, when n=3, inequality (3.40) holds.
Whenn>3, since
(3.48)10-(3/2+1)22+8fj3+(10-(3/2+1)2)⩽nβn(j)⩽10-(3/2+0)22+8fj3+(10-(3/2+0)2),
that is
(3.49)1523+32fj3⩽nβn(j)⩽3139+32fj3,
then we have
(3.50)1-nβn(j)-b(j)⩽1-1523+32fj3-2fj+4fj28fj+8fj2=9fj-14fj2+96fj4+64fj54fj(23+32fj3)(1+fj),b(j)+2a(j)cos(2πn)⩾b(j)+2a(j)×0=2fj+4fj28fj+8fj2,b(j)-(1-nβn(j)-b(j))=fj(7+30fj-32fj3)2fj(23+32fj3)(1+fj).
By 1/2<fj⩽1 again, the conclusion could be obtained naturally.
To Sum up, we have(3.51)|λ1|>|∏j=1k‍(1-nβn(j)-b(j))|.
(c) For the inequality (3.41), we have
(3.52)λ1=∏j=1k‍(b(j)+2a(j)cos(2πin))⩾∏j=1k‍(b(j)-a(j)).
Since
(3.53)(bj-aj)-β6=(2fj+4fj28fj+8fj2-2fj8fj+8fj2)-18+8fj3=4fj4+3fj-18(1+fj)(1+fj3),
and 1/2<f⩽1, we have
(3.54)λ1>∏j=1k‍β6(j).
From(3.55)(bj-aj)-aj=4fj2-2fj8fj+8fj2=2fj-14+4fj,
we have
(3.56)λ1>∏j=1k‍a(j)>0.
Then, the eigenvalues ofM(k) hold the properties (2). That is to say, λ0=1,λ1=λ2=∏j=1k(b(j)+2a(j)cos(2πi/n)), and 1=|λ0|>|λ1|=|λ2|>|λ3|⩾⋯⩾|λ4n-1|=0.
(2) We verify (3.36).
Since(3.57)|b(j)+2a(j)cos(2πn)|⩽|b(j)+2a(j)|=ς<1,
we have
(3.58)limk→∞|∏j=1k‍(b(j)+2a(j)cos(2πin))|⩽limk→∞∏j=1k‍ς=limk→∞ςk=0,
and 1=|λ0|>|λ1|=|λ2|>|λ3|⩾⋯⩾|λ4n-1|=0; thus we have limk→∞λi=0,i≠0.
Now, the proof of Theorem3.4 is completed.


### 3.2.2.G0 Continuity

Theorem 3.5.
If the kernel functionfj has the convergence rate as Theorem 3.3, then the subdivision surface is continuous.Proof.
Let(3.59)M(k)di=λidi,V(0)=∑i=04n-1‍ai⊗di,
where i=1,2,…,4n-1, ⊗ denotes direct a product, and ai is an undetermined triple coefficient.
Since(3.60)V(k)=M(k)V(0)=λ0(k)(a0⊗d0+∑i=14n-1‍(λi(k)λ0(k))ai⊗di),
where λ0(k)=1,d0(k)=[1,1,…,1]T, and limk→∞λi→0(i≠0). By Theorems 3.3 and 3.4, we have, when k→∞,M(k)V(0) is convergent and ai is unique.
Let(3.61)vl=(000⋯⋯⋯︸l-3010⋯0010⋯0010⋯0),vt=(000⋯⋯⋯︸t-3010⋯0010⋯0010⋯0).
Given any two points whose coordinates arelth, tth, component of V(k), denoted as Vl(k),Vt(k), we have
(3.62)limk→∞∥Vl(k)-Vt(k)∥=∥vl(M(∞)V(0))-vt(M(∞)V(0))∥=(vl-vt)∥∑i=04n-1‍λi(∞)ai⊗di∥=(vl-vt)∥λ0(∞)a0⊗d0∥.
By (3.60), we have
(3.63)limk→∞∥Vl(k)-Vt(k)∥=0.
That is to say that the subdivision surface is G0 continuity.


### 3.2.3.G1 Continuity

Based on the above result, we analyze the continuity of loop-like subdivision surface.Theorem 3.6.
If the kernel functionf(k) has the convergence rate as Theorem 3.1, then the subdivision surface is tangent plane continuity, that is, G1 continuity.Proof.
We will verify that there exists a common tangent plane around vertexV0(k) so as to ensure that the subdivision surface is G1 continuity.
Given any three points whose coordinates arelth, sth, and tth component of V(k), denoted as Vl(k),Vs(k), and Vt(k), by Theorem 3.4, we have
(3.64)limk→∞(Vl(k)-Vt(k))=(vl-vt)(λ0a0⊗d0+λ1(∞)(a1⊗d1+a2⊗d2+∑i=34n-1‍(ai⊗diλi(∞)λ1(∞))))=(vl-vt)λ1(∞)(a1⊗d1+a2⊗d2).
Let
(3.65)Γlt=limk→∞Vl(k)-Vt(k)∥Vl(k)-Vt(k)∥,
we have
(3.66)Γlt=(vl-vt)(a1⊗d1+a2⊗d2)∥(vl-vt)(a1⊗d1+a2⊗d2)∥=c1a1+c2a2∥c1a1+c2a2∥.
Similarly, we have
(3.67)Γst=(vs-vt)(a1⊗d1+a2⊗d2)∥(vs-vt)(a1⊗d1+a2⊗d2)∥=c3a1+c4a2∥c3a1+c4a2∥.
Then,
(3.68)limk→∞Nlt×st(k)∥Nlt×st(k)∥=Γlt×Γst∥Γlt×Γst∥=(c1a1+c2a2)×(c3a1+c4a2)∥(c1a1+c2a2)×(c3a1+c4a2)∥=a2×a1∥a2×a1∥.
Hence, when k→∞, the vertex around the V0 has a common normal vector. That is to say that the subdivision surface is G1 continuity.


### 3.2.4.C1 Continuity

According to [18], besides the eigenvalues of M(k) satisfy (3.35), the characteristic maps associated with M(k) should be regular and injective for obtaining global C1 continuity. The characteristic map is defined as the subdivision surface generated by refining an initial mesh whose topological structure is identical with the subdivision stencil [24], just as shown in Figure 2. If both λ1 and λ2 are real, the horizontal and longitudinal coordinates of the ith control point of the initial control mesh come from the corresponding elements of the eigenvectors of λ1 and λ2, and the vertical coordinate is assumed to be zero, respectively.The regularity and injectivity of this map can be judged from the triangulation obtained from the control points by some steps subdivision [25]. Similar to many other studies, this paper only gives numerical evidence to verify the regularity and injectivity of the characteristic map of the loop-like subdivision scheme. The characteristic maps with valences n=3–50 are verified and they all hold a good shape. The obtained results are presented in Figure 3.Visualization of characteristic maps: (a)–(d) control nets from the eigenvectors ofM(k) with valences n=3,5,8,19, and f(k)=1-1/22k-1; (e)–(h) control nets with valences n=3,5,8,19, and f(k)=cos(π/(2kn)); (i)–(p) local regions around the irregular vertex of the characteristic maps after four subdivision steps.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)


## 3.2.1. Subdivision Matrix Analysis

Firstly, we need to prove the following lemma.Lemma 3.2.
Let(3.18)Ξ~(k)=∏k=nt,nt-1,…,n1‍[1-a(k)a(k)b(k)1-b(k)].
Their eigenvalues are
(3.19)∏k=nt,nt-1,…,n1‍(1-a(k)-b(k)).Proof.
Since(3.20)[1-a(k)a(k)b(k)1-b(k)]=I+b(k)[-c(k)c(k)1-1],
where c(k)=a(k)/b(k), and
(3.21)A(k)=b(k)[-c(k)c(k)1-1],
then
(3.22)Ξ~(k)=I+A(nt)+A(nt-1)+⋯+A(n1)+A(nt)A(nt-1)+⋯+A(n2)A(n1)+⋯+∏k=nt,nt-1,…,n1‍A(k).
From
(3.23)A(k2)A(k1)=bk2bk1[c(k2)(c(k1)+1)-c(k2)(c(k1)+1)-(c(k1)+1)c(k1)+1]=-b(k1)(c(k1)+1)A(k2),
we have
(3.24)Ξ~(k)=I+∑1⩽k1⩽t‍A(nk1)+∑1⩽k2⩽t1⩽k1⩽t1k1<k2∏j=nk2,nk1‍A(j)+⋯+∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki∏j=nki,…,nk1‍A(j)+⋯+∑1⩽kt⩽t⋯1⩽k1⩽tk1<⋯<kt‍∏j=nkt,…,nk1‍A(j)=I+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(A(nki)∏j=nki-1,…,nk1‍b(j)(-c(j)-1))=[1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍((-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j)))].
Furthermore, their eigenvalues could be obtained as follows:
(3.25)λ0=1,λ1=1+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(-a(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j))+∑i=1t‍∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍(-b(nki))∏j=nki-1,…,nk1‍(-a(j)-b(j))=1+∑i=1t∑1⩽ki⩽t⋯1⩽k1⩽tk1<⋯<ki-1<ki‍∏j=nki,…,nk1‍(-a(j)-b(j))=∏k=nt,nt-1,…,n1‍(1-a(k)-b(k)).Theorem 3.3.
The eigenvalues ofM(k) are 1,0, ∏j=1k(b(j)+a(j)(ϖni+ϖn-i)), ∏j=1k(1-nβn(j)-b(j)), ∏j=1kβ6(j), and ∏j=1ka(j), and the last two eigenvalues are the repeated ones.Proof.
SinceS(k) is a block circulant matrix, so is M(k). Let
(3.26)M~=W-1MW,
we know M~ is a block circulant matrix, and
(3.27)M~=bcirc(∏j=1k‍S~0(j),∏j=1k‍S~1(j),…,∏j=1k‍S~n-1(j)).
Denote(3.28)M~(k)≜diag(M~0(k),M~1(k),…,M~n-1(k)),
we have
(3.29)M~i(k)≜∏j=1k‍S~i(j)=[M~i,0(k)0M~i,2(k)M~i,1(k)],
and the eigenvectors of M~i(k) only relate to S~i,0(k),S~i,1(k). The following two cases need to be discussed separately.
(1) Ifi=0, then
(3.30)M~0,0(k)=∏j=1k‍[1-nβn(j)nβn(j)b(j)1-b(j)],M~0,1(k)=[∏j=1k‍β6(j)x0∏j=1k‍a(j)].
By Lemma3.2, we can get the eigenvalues of M~0,0(k):
(3.31)λ0=1,λ1=∏j=1k‍(1-nβn(j)-b(j)).
The eigenvalues of M~0,1(k) are
(3.32)λ2=∏j=1k‍β6(j),λ3=∏j=1k‍a(j).
(2) Ifi≠0, then
(3.33)M~i,0(k)=[00x∏j=1k‍(b(j)+a(j)(ϖni+ϖn-i))],M~i,1(k)=[∏j=1k‍β6(j)y0∏j=1k‍a(j)],
where x, y are real numbers. Their eigenvalues are
(3.34)λ0=∏j=1k‍(b(j)+a(j)(ϖni+ϖn-i)),λ1=0,λ2=∏j=1k‍β6(j),λ3=∏j=1k‍a(j),
respectively.Theorem 3.4.
If the eigenvalues of matrixM(k) are ordered from the greatest to the least, then one has
(3.35)λ0=1>λ1=λ2>λ3⩾⋯⩾λ4n-1=0,(3.36)limk→∞λi=0,i≠0.Proof.
Since each row sum ofM(k) is equal to 1, then (1,1,…,1)T must be one of eigenvectors corresponding to the eigenvalue 1.
(1) We prove the (3.35) firstly.
Let(3.37)λ1=∏j=1k‍(b(j)+2a(j)cos2πn),λ2=∏j=1k‍(b(j)+2a(j)cos2(n-1)πn).
It is easy to derive that
(3.38)λ1=λ2=∏j=1k‍(b(j)+2a(j)cos2πn).
In order to prove that the absolute value ofλ1 is the maximum value among all eigenvalues except for λ0, we need to prove
(3.39)|λ1|⩾∏j=1k‍(b(j)+2a(j)cos(2πin)),i=1,…,n-1,(3.40)|λ1|>|∏j=1k‍(1-nβn(j)-b(j))|,
and then
(3.41)|λ1|⩾∏j=1k‍β6(j)⩾∏j=1k‍a(j)⩾0.
(a) For the inequality (3.39), if n=3, the group has eigenvalues λ1 and λ2, then the inequality is obvious to be obtained. If n≠3, since
(3.42)cos(2π(n-i)n)=cos(2πin),
and according to the monotonicity of the function cos(2πi/n), we have that
(3.43)λ1=λ2=∏j=1k‍(b(j)+2a(j)cos(2πn))
is the maximum value in the group.
(b) For the inequality (3.40), we only need to prove
(3.44)|b(j)+2a(j)cos(2πn)|>|1-nβn(j)-b(j)|,
where
(3.45)nβn(j)=nd2+8fj3+nd=10-(3/2+cos(2π/n))22+8fj3+(10-(3/2+cos(2π/n))2).
Whenn=3, we have
(3.46)1-nβn(j)-b(j)=16fj5+24fj4-14fj2-3fj4fj(11+8fj3)(1+fj),b(j)+2a(j)cos(2πn)=b(j)-a(j)=4fj28fj+8fj2.
Then,
(3.47)(b(j)-a(j))-(1-nβn(j)-b(j))=3fj(1+12fj-8fj3)4fj(11+fj3)(1+fj).
Since 1/2<fj⩽1, the above formula is positive; that is, when n=3, inequality (3.40) holds.
Whenn>3, since
(3.48)10-(3/2+1)22+8fj3+(10-(3/2+1)2)⩽nβn(j)⩽10-(3/2+0)22+8fj3+(10-(3/2+0)2),
that is
(3.49)1523+32fj3⩽nβn(j)⩽3139+32fj3,
then we have
(3.50)1-nβn(j)-b(j)⩽1-1523+32fj3-2fj+4fj28fj+8fj2=9fj-14fj2+96fj4+64fj54fj(23+32fj3)(1+fj),b(j)+2a(j)cos(2πn)⩾b(j)+2a(j)×0=2fj+4fj28fj+8fj2,b(j)-(1-nβn(j)-b(j))=fj(7+30fj-32fj3)2fj(23+32fj3)(1+fj).
By 1/2<fj⩽1 again, the conclusion could be obtained naturally.
To Sum up, we have(3.51)|λ1|>|∏j=1k‍(1-nβn(j)-b(j))|.
(c) For the inequality (3.41), we have
(3.52)λ1=∏j=1k‍(b(j)+2a(j)cos(2πin))⩾∏j=1k‍(b(j)-a(j)).
Since
(3.53)(bj-aj)-β6=(2fj+4fj28fj+8fj2-2fj8fj+8fj2)-18+8fj3=4fj4+3fj-18(1+fj)(1+fj3),
and 1/2<f⩽1, we have
(3.54)λ1>∏j=1k‍β6(j).
From(3.55)(bj-aj)-aj=4fj2-2fj8fj+8fj2=2fj-14+4fj,
we have
(3.56)λ1>∏j=1k‍a(j)>0.
Then, the eigenvalues ofM(k) hold the properties (2). That is to say, λ0=1,λ1=λ2=∏j=1k(b(j)+2a(j)cos(2πi/n)), and 1=|λ0|>|λ1|=|λ2|>|λ3|⩾⋯⩾|λ4n-1|=0.
(2) We verify (3.36).
Since(3.57)|b(j)+2a(j)cos(2πn)|⩽|b(j)+2a(j)|=ς<1,
we have
(3.58)limk→∞|∏j=1k‍(b(j)+2a(j)cos(2πin))|⩽limk→∞∏j=1k‍ς=limk→∞ςk=0,
and 1=|λ0|>|λ1|=|λ2|>|λ3|⩾⋯⩾|λ4n-1|=0; thus we have limk→∞λi=0,i≠0.
Now, the proof of Theorem3.4 is completed.


## 3.2.2.G0 Continuity

Theorem 3.5.
If the kernel functionfj has the convergence rate as Theorem 3.3, then the subdivision surface is continuous.Proof.
Let(3.59)M(k)di=λidi,V(0)=∑i=04n-1‍ai⊗di,
where i=1,2,…,4n-1, ⊗ denotes direct a product, and ai is an undetermined triple coefficient.
Since(3.60)V(k)=M(k)V(0)=λ0(k)(a0⊗d0+∑i=14n-1‍(λi(k)λ0(k))ai⊗di),
where λ0(k)=1,d0(k)=[1,1,…,1]T, and limk→∞λi→0(i≠0). By Theorems 3.3 and 3.4, we have, when k→∞,M(k)V(0) is convergent and ai is unique.
Let(3.61)vl=(000⋯⋯⋯︸l-3010⋯0010⋯0010⋯0),vt=(000⋯⋯⋯︸t-3010⋯0010⋯0010⋯0).
Given any two points whose coordinates arelth, tth, component of V(k), denoted as Vl(k),Vt(k), we have
(3.62)limk→∞∥Vl(k)-Vt(k)∥=∥vl(M(∞)V(0))-vt(M(∞)V(0))∥=(vl-vt)∥∑i=04n-1‍λi(∞)ai⊗di∥=(vl-vt)∥λ0(∞)a0⊗d0∥.
By (3.60), we have
(3.63)limk→∞∥Vl(k)-Vt(k)∥=0.
That is to say that the subdivision surface is G0 continuity.


## 3.2.3.G1 Continuity

Based on the above result, we analyze the continuity of loop-like subdivision surface.Theorem 3.6.
If the kernel functionf(k) has the convergence rate as Theorem 3.1, then the subdivision surface is tangent plane continuity, that is, G1 continuity.Proof.
We will verify that there exists a common tangent plane around vertexV0(k) so as to ensure that the subdivision surface is G1 continuity.
Given any three points whose coordinates arelth, sth, and tth component of V(k), denoted as Vl(k),Vs(k), and Vt(k), by Theorem 3.4, we have
(3.64)limk→∞(Vl(k)-Vt(k))=(vl-vt)(λ0a0⊗d0+λ1(∞)(a1⊗d1+a2⊗d2+∑i=34n-1‍(ai⊗diλi(∞)λ1(∞))))=(vl-vt)λ1(∞)(a1⊗d1+a2⊗d2).
Let
(3.65)Γlt=limk→∞Vl(k)-Vt(k)∥Vl(k)-Vt(k)∥,
we have
(3.66)Γlt=(vl-vt)(a1⊗d1+a2⊗d2)∥(vl-vt)(a1⊗d1+a2⊗d2)∥=c1a1+c2a2∥c1a1+c2a2∥.
Similarly, we have
(3.67)Γst=(vs-vt)(a1⊗d1+a2⊗d2)∥(vs-vt)(a1⊗d1+a2⊗d2)∥=c3a1+c4a2∥c3a1+c4a2∥.
Then,
(3.68)limk→∞Nlt×st(k)∥Nlt×st(k)∥=Γlt×Γst∥Γlt×Γst∥=(c1a1+c2a2)×(c3a1+c4a2)∥(c1a1+c2a2)×(c3a1+c4a2)∥=a2×a1∥a2×a1∥.
Hence, when k→∞, the vertex around the V0 has a common normal vector. That is to say that the subdivision surface is G1 continuity.


## 3.2.4.C1 Continuity

According to [18], besides the eigenvalues of M(k) satisfy (3.35), the characteristic maps associated with M(k) should be regular and injective for obtaining global C1 continuity. The characteristic map is defined as the subdivision surface generated by refining an initial mesh whose topological structure is identical with the subdivision stencil [24], just as shown in Figure 2. If both λ1 and λ2 are real, the horizontal and longitudinal coordinates of the ith control point of the initial control mesh come from the corresponding elements of the eigenvectors of λ1 and λ2, and the vertical coordinate is assumed to be zero, respectively.The regularity and injectivity of this map can be judged from the triangulation obtained from the control points by some steps subdivision [25]. Similar to many other studies, this paper only gives numerical evidence to verify the regularity and injectivity of the characteristic map of the loop-like subdivision scheme. The characteristic maps with valences n=3–50 are verified and they all hold a good shape. The obtained results are presented in Figure 3.Visualization of characteristic maps: (a)–(d) control nets from the eigenvectors ofM(k) with valences n=3,5,8,19, and f(k)=1-1/22k-1; (e)–(h) control nets with valences n=3,5,8,19, and f(k)=cos(π/(2kn)); (i)–(p) local regions around the irregular vertex of the characteristic maps after four subdivision steps.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)


## 4. Experiments

In this section, we show several examples of subdivision surface generated by our schemes. Figure4 depicts three examples. Figures 4(a), 4(c), and 4(e) are control meshes, and Figures 4(b), 4(d), and 4(f) are subdivision surfaces. It is well known that the revolving surface is very important in industrial application. In our schemes, it is easy to create the local revolving part. As shown in Figure 5, a regular control mesh can be constructed for the revolving part. Set α0=2π/n, a=2, b=2+4f, and c=8+8f, an exact revolving surface can be obtained by the subdivision mask as Figure 1 and the compensation mask as Figure 5(b). Certainly, the sweep line direction of the revolving surface should be set interactively. Figure 6 depicts two other examples with the revolving part. Figures 6(a) and 6(e) are control meshes, and Figures 6(b), 6(c), 6(d), and 6(f) are subdivision surfaces. Figures 6(b) and 6(c) show the result surfaces after one and two subdivision step(s), respectively. The subdivision surface with texture is shown in Figure 6(d). Both the vase in Figure 6(d) and the bolt hole in Figure 6(e) are revolving parts. Using our scheme, the exact revolving parts can be generated easily. The results demonstrate that our technique can be an alternative solution for representing the revolving shape exactly.Loop-like subdivision examples.
(a)
(b)
(c)
(d)
(e)
(f)Control net pattern and compensation mask for the revolving surface.
(a)
(b)Modeling examples of the revolving part.
(a)
(b)
(c)
(d)
(e)
(f)


## 5. Conclusions

This paper has presented a regular dynamic loop-like subdivision scheme that can be regarded as an extension of theC-Box-Splines. The scheme adopts a regular dynamic subdivision operator, which is convergent and versatile. The obtained surface is C1 continuity and could meet the requirement of industrial application. In contrast to the traditional Loop subdivision method, the subdivision scheme is more flexible and has a stronger modeling ability. Under reasonable and appropriate adjustments, the method proposed in this paper could generate a revolving surface exactly.In the present paper, we only consider the continuity of the isotropic schemes, and some more general cases should be further investigated. Moreover, only numerical discussions are presented to demonstrate theC1 continuity in this paper, and some more sophisticated analyses are necessary for further considering.



---

*Source: 264137-2012-12-24.xml*