A non-uniform subdivision scheme with variable parameters for curve design

(1)

A non-uniform subdivision scheme with variable parameters for curve design

Mei-e Fang

^a

, Byeongseon Jeong

^b

, Jungho Yoon

^c

aSchool of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou, China

bInstitute of Mathematical Sciences, Ewha W. University, Seoul, South Korea

cDepartment of Mathematics, Ewha W. University, Seoul, South Korea

Abstract

In this paper, we present a non-uniform subdivision scheme of arbitrary degree with a variable parameter sequence. By this scheme, blending curves which are composing of different types of generalized B-spline curves including many analytic curves can be successfully reproduced. Generalized subdivision and the classical B-spline subdivision are all special cases of the proposed variable parameter subdivision. We prove the smoothness of the proposed scheme. Also, as an application, we propose a chamfering algorithm which can be used in designing automobile and mechanical products.

Key words: Variable parameter subdivision; Blending curves; Arbitrary degree;

C^d−1-continuous; Chamfering algorithm.

1 Introduction

In recent years, generalized B-splines have been studied in many literatures (Koch and Lyche 1993, Kvasov and Sttayatham 1999, Mainar and Pena 2001, Costantini al et 2005, Schumaker 2007, Wang and Fang 2008, Fang et al 2010, Carla et al 2010). They possess all fundamental properties of polynomial B- splines and NURBS, while avoiding some drawbacks of NURBS, such as com- plicated rational form, necessity of ”weights”, imprecise description of commonly used transcendental curves in applications. Generalized B-splines can

∗ Corresponding author.

Email address: fme@hdu.edu.cn, yoon@ewha.ac.kr (Mei-e Fang^a, Byeongseon Jeong^b, Jungho Yoon^c).

(2)

exactly produce not only free-form curves and conics (NURBS can do), but also many transcendental curves such as Lissajous, catenary, trigonometric function and hyperbolic function curves etc. (NURBS can not do). That is to say, geometric models represented by generalized B-splines completely include those which can be generated by NURBS. So generalized B-splines provide a possible alternative to NURBS.

Furthermore, recursively generating smooth curves from an initial control polygon is a standard method in geometric modelling due to its numerical stability and simplicity for implementation. A lot of work has been done in the area of subdivision-based modelling since 1970s. Today one can find fam- ilies of subdivision schemes for geometric design and graphics applications (Zorin and Schr¨oder 2000, Sabin 2004, Ma 2005). But its application is lim- ited in animation in current because it can not include those geometric models generated by NURBS. So it is meaningful to generate generalized B-splines by subdivision, which is advantageous for both efficiently generating generalized B-splines and applying subdivision scheme in CAD/CAM.

In the paper (Fang et al 2010), a generalized subdivision scheme with a tension parameter for curve design has been proposed, which can reproduce generalized B-splines. Generalized B-splines unify classic B-splines, the algebraic- trigonometric B-splines and algebraic-hyperbolic B-splines (Fang et al 2010).

They can represent exactly many analytic curves such as Lissajous curves, conics, trigonometric function curves, hyperbolic function curves, catenary curves and helixes. which are important shapes in geometric modeling. While in engi- neering applications, blending curves in which some aforementioned analytic curves are inserted are more commonly used. For example, a torque spring is usually composed of a piece of helix, a piece of arc and others. A tool path in NC ???is usually composed of several pieces of arcs with different radii and lines etc. In this regards, the aim of this paper to further develope a family of non-stationary subdivision schemes of arbitrary degree with a variable- parameter sequence based on generalized subdivision scheme with a tension parameter proposed in paper (Fang et al 2010). By this scheme, blending curves composed of different types of curves, which can be respectively generated by generalized subdivision scheme with different tension parameters, can be successfully reproduced in whole by the proposed subdivision scheme. We show that the proposed scheme of degree d produces C^d−1-continuous limit curves. Lastly, as an application, we also proposed an chamfering algorithm which can be used in designing automobile and mechanical products.

The article is organized as follows. In Section 2, we define the rules and the steps of our variable parameter subdivision scheme for updating both vertexes and parameters. Some examples of producing blending curves by the proposed variable-parameter subdivision scheme are given in Section 3. We especially design a chamfering algorithm for application. In Section 4, we ana-

(3)

lyze convergence and continuity of our variable parameter subdivision scheme.

Conclusion and future work are described in Section 5.

2 Subdivision Schemes

2.1 Subdivision Rule

From a given set of control points P⁰ = {P_j⁰ : j ∈ Z} at level zero a binary stationary uniform subdivision scheme defines recursively new sets of points P^k+1 = {p^k+1_j : j ∈ Z} at level k > 0 formally by

P^k+1 = SP^k, k = 0, 1, . . . .

A point of P^k is defined by a finite linear combination of points of P_i^k, i.e., P_n^k+1 =^X

i∈Z

an−2iP_i^k,

with a fixed rule a = {an : n ∈ Z}. The sequence a of coefficients is called the subdivision mask. It is usual to assume that only finitely many numbers of an are non-zero so that changes in a control point affect only its local neighborhood. which is indeed the same as the proposed scheme. One should note that only even (and odd) indices of the mask are involved to evaluate new values P_j^k for even (and odd) j respectively.

To simplify the presentation of a subdivision scheme and its analysis, it is convenient to represent the subdivision rule in terms of the symbol

a(z) := ^X

i∈Z

anzⁿ.

Since the mask a is finitely supported, a(z) becomes a Laurent polynomial.

For instance, the Laurent polynomial of the B-spline of degree d is of the form a(z) := 2s^d+1(z)

where s(z) indicates the smoothness factor given as s(z) = (1 + z)

2 .

A non-uniform subdivision, which is the case of the proposed scheme, may apply a different mask for any newly defined value. The mask defining the new value at level k and location j is denoted by a^k,j := {a^k,j_i : i ∈ Z}, whence

(4)

the scheme is defined by

P_j^k+1 =^X

i∈Z

a^k,j_j−2iP_i^k. (1)

If a^k,j is independent of k and j, i.e., a^k,j = a, the corresponding scheme is said to be stationary.

2.2 Non-uniform Variable Parameter Subdivision Scheme

In this subsection, we introduce a variable parameter curve subdivision scheme (NVPS) of arbitrary degree d (hereafter, denoted by Sd with d ≥ 2). The proposed scheme is non-uniform since the subdivision rules are defined by applying tension parameters which may vary for any newly defined value. More specifically, for the purpose of generating blending curves which are composed of different types of generalized B-spline curves, we extend the generalized subdivision proposed in the paper (Fang et al 2010) to the case of variable parameters. The proposed scheme sets a tension parameter for each edge of the initial control polygon. Each parameter can be used to control locally the shape of the resulting subdivision curve. The number of parameters and their specific values may vary with the process of subdivision, whence the scheme is non- uniform. The degree of the scheme determines the continuity and smoothness of the limit curve. When all parameters are equal, the proposed scheme is reduced to a generalized subdivision. In fact, this scheme is the variant of those subdivision schemes for classical B-splines (Lane and Riesenfeld 1980, Dyn 1992) by introducing variable (for different edges of the control polygon) and non-uniform (for different levels of subdivision) weights in its first step as illustrated in the formula (1). Certainly, the classical B-spline subdivision are special cases of the proposed subdivision.

A detailed algorithm of the proposed non-uniform subdivision scheme is given below. We first consider the NVPS scheme of degree d = 2 and then discuss the scheme of higher degree d > 2.

• The NVPS Rule for d = 2.

Let P⁰ = {P_i⁰ : i = 0, . . . , n} be a set of (finite) initial control points with tension parameters U⁰ = {u⁰_i > 0 : i = 0, . . . , n}. Put N = n − 1 for open P and N = n for close P . For convenience, we assume P⁰ is open in the subsequent description in this paper. Then the proposed univariate NVPS of degree 2 first uptate the tension parameters u^k_j iteratively, at each subdivision

(5)

level k, by the rule

u^k+1_2i =

s1 + u^k_i

2 , i = 0, 1, · · · , n − 1 u^k+1_2i+1 =

s1 + u^k_i+1

2 , i = 0, 1, · · · , n − 2,

(2)

Here, u^k_j is the value, at refinement level k, attached to the dyadic point j2^−k. With the updated sequence U^k of tension parameters at hand, a set of the new control points P^k+1 is defined by

P_2i^k+1 = 1 + 2u^k_i

2(1 + u^k_i)P_i^k+ 1

2(1 + u^k_i)P_i+1^k , P_2i+1^k+1 = 1

2(1 + u^k_i)P_i^k+ 1 + 2u^k_i 2(1 + u^k_i)P_i+1^k .

(3)

When all the values of u^j_i are 1, the above scheme becomes stationary and it is the well-known Chaikin’s algorithm. In fact, in view of (1), the mask of NVPS of degree 2 for Pk,i can be written as

a^k,j₂ =ⁿ 1

2(1 + u^k_j), 1 + 2u^k_j

2(1 + u^k_k), 1 + 2u^k_j

2(1 + u^k_j), 1 2(1 + u^k_j)

o. (4)

Since u⁰_n > 0, it is clear that u^k_n > 0 for every i ∈ Z. The following lemma treats the convergence of u^k_i as k tends to ∞ and boundedness of the sequence {kU^kk∞}^∞_k=0 where kU^kk∞= maxiu^k_i.

Lemma 2.1 Let U⁰ = {u⁰_n : n ∈ Z} be a given initial tension parameter sequence, and assume that the sequence U^k = {u^k_n : n ∈ Z} at level k is updated as in (2). Then, u^k_n converges to 1, as k → ∞, uniformly in terms of n. Moreover, for any k ≥ 1,

kU^kk∞ ≤ C max(1, kU⁰k∞). (5)

Proof. For the given initial (finite) tension parameter U⁰, let u⁰_α = maxiu⁰_i and u⁰_β = min u⁰_i. By mathematical induction, it is clear that for each refinement level k ≥ 0, u^k₂^k_α = max u^k_i and u^k₂^k_β = min u^k_i. Since u⁰_n > 0, by construction, u^k₂kα > 0. Moreover, the sequence {u^k₂kα}_k≥0 is monotone and bounded so that it converges to 1 as k tends to ∞. Also, the sequence {u^k₂^k_β}k≥0 converges to 1 monotonically, as k tends to ∞. Then, we can deduce that u^k_i converges to 1, as k → ∞, uniformly in terms of i.

Next, to prove (5), consider the sequence {u^k₂kα : k ∈ N} where u^k₂kα = kU^kk∞. If u⁰_α > 1, u^k₂^k_α decreases monotonically to 1 as k → ∞. Hence, kU^kk∞ ≤

(6)

kU⁰k∞. If u⁰_α ≤ 1, it is clear by induction that kU^kk∞≤ 1 for any k. It proves

the lemma’s claim.

• The NVPS Rule for d > 2.

Based on the rule of the NVPS of degree 2 in (3), the subdivision scheme Sd

for higher degree d > 2 is defined recursively by (SdP^k)i = 1

2

(Sd−1P^k)i + (Sd−1P^k)i+1

. (6)

Algorithm 1 The NVPS scheme of degree d can be performed as below.

(1) Given an initial control polygon P⁰ = {P_i⁰}ⁿ_i=0, set an initial tension parameter sequence U⁰ = {ui}ⁿ⁻¹_i=0 and choose a NVPS of degree d;

(2) Generate new control points by apply the rule Sdfrom the control points P^k: P^k+1 = Sd(P^k);

(3) Update the tension parameter sequence U^k for the next subdivision as follows. The rule for defining the new tension parameter Us = {u^d_j}^2n−d_j=0 , is divided into two cases: (i) d is odd and (ii) d is even.

Case 1: d is odd.

u³₀ = u0, u³_2n−3 = un−1,

u³_2i+1 = u³_2i+2 = ui+1, i = 0, · · · , n − 3, u^d_j = u^d−2_j+1, j = 0, 1, . . . , 2n − d, d > 3 Case 1: d is even.

u^d_j = u^d−2_j+1, j = 0, 1, · · · , 2n − d, d > 2;

(4) Continue this process up to the desired subdivision level.

Remark 1. When all parameters in the parameter sequence are equal, the NVPS is reduced to a generalized subdivision scheme in (Fang et al 2010).

Naturally, NVPS inherits the most important merits of the scheme in (Fang et al 2010). It can reproduce the curves such as conics, trigonometric curves and helix. Further, it can generate blending curves because different parameters can be set for different edges of the control polygon. Certainly, many of existing subdivision schemes, such as Doo-Sabin scheme, Catmull-Clark scheme (Catmull and Clark 1978) and the scheme proposed in (Stam 2001) for curve subdivision, are all its special cases.

Remark 2. As we will see in the section 3, the degree of NVPS effects the smoothness of subdivision results. Naturally, a higher degree scheme provides smoother curves. On the other side, the parameters also effects the shape of subdivision result, both locally and globally. In Figure 1 (a), three subdivision

(7)

results are generated by NVPS of degree 4 from the same control polygon.

The parameters are common except u4 marked in the figure. We can see the shapes of subdivision results are locally effected. In fact, only d pieces of subdivision curves are effected when one parameter is changed for NVPS of degree d and only two pieces of subdivision curves beside the control polygon corresponding to that changed parameter are greatly changed. The effect is similar to that of changing a control point. Thus the NVPS adjusts locally the shape of subdivision results without changing control points. Certainly, the shapes of subdivision results will be globally effected if we change the whole parameter sequence. In Figure 1 (b), all subdivision curves are generated by NVPS of the same degree from the same control polygon, but with different parameter sequences. When taking all parameters as a certain constant, the subdivision results arrange in layers if we change the value of this constant as illustrated in Figure 1 (b), respectively marked with green, purple and black lines, where the parameters of the red line are generated at random. We can see this curve intersect with other three subdivision results in a convex domain.

This is impossible to be implemented by exsiting generalized subdivision.

3 Smoothness of the NVPS

3.1 Asymptotical equivalence

The analysis of a subdivision scheme can be reduced to the case of initial control points in R since each component of the curve is a scalar function generated by the same subdivision scheme. Therefore, starting with values f⁰ = {f_n⁰ : n ∈ Z}, we consider f⁰ = {f_n⁰ : n ∈ Z}, generated by

f_n^k+1 =^X

i∈Z

an−2if_i^k,

A binary subdivision scheme is said to be C^m if the sequence of piecewise linear interpolants {f^k(·)}^∞_k=0,

f^k(t) =^X

j

f_j^kB1(2^k· −j), (7)

converges uniformly to a C^mfunction f^∞and f^∞is not identically zero, where B1 is the standard hat function on [−1, 1]. Note that the uniform convergence of {f^k(·)}^∞_k=0 implies that the limit is a C⁰ function.

For the analysis of the convergence and smoothness of the proposed non- uniform scheme, we employ the concept of aymptotical equivalence between two schemes in (N. Dyn, D. Levin and J. Yoon, 2014).

(8)

Definition 3.1 A non-uniform subdivision scheme with the masks {a^k,j} is said to be asymptotically equivalent to a scheme with the masks {˜a^k,j}, denoted by {a^k,j} ∼ {˜a^k,j}, if

∞

X

k=0

sup

j∈Z

{ka^k,j− ˜a^k,jk} < ∞. (8)

A similar definition for the case of non-stationary schemes can be found in Dyn (1995).

For a given initial data f⁰, we will prove, by using the concept of aymptotical equivalence, that the sequence of control points f^k obtained by the NVPS of degree d converges to a C^d−1 limit function. To this end, we cite the following result from Lemma 2.5 in (Dyn, N., D. Levin and J. Yoon, 2007).

Lemma 3.2 Assume that {a^k,j} ∼ {˜a^k,j} and the scheme defined by the masks {˜a^k,j} is stable and C⁰, then the non-uniform scheme with the mask {a^k,j} is also C⁰ and stable.

In this study, we shall see that the mask {a^k,j} of the NVPS of degree d is asymptotically equivalent to the B-spline scheme of order d. In particular, as we have observed in (4), the mask of the NVPS of degree 2 at level k and location j is given as

a^k,j₂ =ⁿ 1

2(1 + u^k_j), 1 + 2u^k_j

2(1 + u^k_k), 1 + 2u^k_j

2(1 + u^k_j), 1 2(1 + u^k_j)

o. (9)

Here, by Lemma 2.1, lim

k→∞u^j_k= 1. Hence, it clearly follows that the mask a^k,j₂ converges to

a₂ =ⁿ1 4,3

4,3 4,1

4

o (10)

which is the mask of B2-spline. The following lemma is useful for our further analysis.

Lemma 3.3 Let a^k,j₂ be the mask of NVPS of degree 2 and a₂ be the mask of the B-spline of order 2, Then,

X

k∈Z

2^kmax

j {ka^k,j₂ − a2k∞} < ∞

(9)

Proof. In view of (4) and (5), it is immediate that

E_j^k:= 2^kka^k,j₂ − ak∞ (11)

= 2^kmax 1

2(1 + u^k_j)− 1 4

, 1 + 2u^k_j 2(1 + u^k_j)− 3

4

= 2^k−21 − u^k_j 1 + u^k_j

. (12) Since only finit numbers of u^k_j are non-zero, there exists j⁰ such

ka^k,j₂ ⁰ − ak∞= sup{ka^k,j₂ − ak∞}.

Here, write j⁰ = 2n + ν with a suitable n ∈ Z and ν ∈ {0, 1}. Then, by the construction of U^k in (2), it is clear that 1 + u^k−1_2n = 2(u^k_2n+ν)² . Thus, some elementary calculation leads to

E_2n+ν^k E_n+ν^k−1 = 2

1 − u^k_2n+ν 1 + u^k_2n

1 + u^k−1_n+ν 1 − u^k−1_n+ν

= 2

1 − u^k_2n+ν 1 + u^k_2n

(u^k_2n+ν)² 1 − (u^k_2n+ν)²

= 2

u^k_2n+ν 1 + u^k_2n+ν

2

.

As we have disscussed in Lemma 2.1, u^k+1_2n+ν converges to 1 such that the last term on the above equation converges to 1/2. Thus, it readily holds that

lim sup sup_j{E_j^k}

sup_j{E_j^k−1} ≤ lim

k→∞

E_2n+ν^k+1 E_n+ν^k = 1

2

Following the D’Alembert criteria for convergence of positive series and it

finishes the proof.

Corollary 3.4 Let a^k,j₂ be the mask of NVPS of degree 2 and a₂ be the mask of the B-spline of order 2, Then,

maxj {ka^k,j₂ − a2k∞} < c2^−k. with a constant c > 0 independent of k and j.

3.2 Sufficient conditions for the Smoothness of the NVPS

In this section, we prove that the proposed NVPS scheme of order d has the smoothness C^d−1. As in the uniform case, to simplify the presentation of a subdivision scheme and its analysis, we use Laurent polynomial a^k,j(z) defined

(10)

by the non-uniform mask a^k,j, that is, a^k,j(z) := ^X

n∈Z

a^k,j_n zⁿ.

Since only finitely many numbers of the coefficients a^k,j_n are non-zero, the Laurent polynomial a^k,j(z) has a finite degree.

Our approaches to prove the smoothness of NVPS uses the following asymp- totic conditions in (N. Dyn, D. Levin and J. Yoon, 2014).

Property A. Consider a non-uniform binary scheme S defined by masks {a^j,k}. We say that the scheme S satisfies Property A of order m if

d^r

dz^rd^j,k_a (±1) = ¯o(2^−k(m−r)), 0 ≤ r < m, (13) as k → ∞, where

d^j,k_m(z) ≡

m

X

i=0

(−1)ⁱ m i

!

zⁱp^j−i,k(z). (14)

Furthermore, we cite the following result from (N. Dyn, D. Levin and J. Yoon, 2014).

Theorem 3.5 Consider a non-uniform binary scheme S defined by masks {a^k,j}, satisfying

{a^k,j} ∼ a, (15)

where m is the mask of a stationary binary scheme Sa. Further assume that S satisfies Property A of orders 1 ≤ ℓ ≤ m. If Sa is a C^m scheme with a stable basic limit function, then also S is a C^m scheme.

3.3 Analysis of Smoothness

Following the construction of higher degree NVPS Sd in (??), its symbol to the mask a^k,j = {a^k,j_n } of the NVPS of degree d, is defined by

a^k,j_d (z) :=z + 1 2

d−2

a^k,j₂ (z). (16)

where a^k,j₂ (z) is the symbol of the NVPS of degree 2, that is, a^k,j₂ (z) = 1

2(1 + u^k_j)z

1 + (1 + 2u^k_j)z + (1 + 2u^k_j)z²+ z³.

(11)

Then, we find that for any location j ∈ Z, a^k,j₂ (1) = 1, d

dza^k,j₂ (1) = 2, d²

dz²a^j,k₂ (1) = 1. (17) It is obvious that the mask of the proposed scheme has the support as one of the B-spline of degree n, i.e.,

supp(a^k,j) = Z ∩ [0, n] − ⌈n/2⌉

which is indeed the same as the B-spline of degree n. We find it convenient to work in the following setting. Corresponding to each non-negative integer α, we define the monomial function qα by qα(x) = x^α. Given the tension parameter u^k_j, we set

hk(j) = 1

2(1 + u^k_j). (18)

Then we realize that the the mask of a^k,j₂ can be written as a^k,j_2,−1 = a^k,j_2,0 = hk(j), a^k,j_2,1 = a^k,j_2,2 = 1 − hk(j).

We are now in a position to state the main result of this section.

Theorem 3.6 (Smoothness of NVPS of degree d) The NVPS scheme of degree d with d > 1 generates C^d−1-continuous limit curves.

Proof. In order prove this thoerem, we need to show that the NVPS of degree d satisfies the Property A of order 1 ≤ m ≤ d − 1, that is, as k → ∞,

d^ℓ dz^ℓd^j,k_m

z=±1 = O(2^{−k(n−ℓ)}), 0 ≤ ℓ < m. (19) In what follows, we shall verify this convergence property for z = −1 and 1 separately.

Case 1: z = 1.

First, consider the case ℓ = 0. Since a^j,k(1) = 2 for any j ∈ Z and k ∈ N, it is obvious that d^j,k_m(1) = ∇^m(a^j,k(1)) = 0 where ∇^mf indicates the mth order backward difference operator. Next, for the case 1 ≤ ℓ ≤ m, we see that

d^ℓ

dz^ℓd^j,k_m(z) =

m

X

i=0

(−1)ⁱ m i

! d^ℓ dz^ℓ

(·)ⁱa^k,j−i(z) (20)

Recalling the Laurent polynomial a^k,j_d (z) is of the form a^k,j_d (z) = s^d−2(z)a^k,j₂ (z),

(12)

we find by Leibnitz rule that for 1 ≤ ℓ ≤ r, d^ℓ

dz^ℓ

(·)ⁱa^k,j−i(z) =

ℓ

X

α=0

d^ℓ−α

dz^ℓ−αs^d−2(z) d^α dz^α

(·)ⁱa^k,j−i₂ (z). (21)

Combiniing it with (20) yields that d^ℓ

dz^ℓd^j,k_m(1) =

ℓ

X

α=0 m

X

i=0

(−1)ⁱ m i

! d^α dz^α

(·)ⁱa^k,j−i₂ (1)

with cα = (_dz^d^ℓℓ⁻−^ααs^d−2(1). Here, using the function hk in (18), we can write the Laurent polynomial a^k,n₂ (z) as

a^k,n₂ (z) = h^k(j)z⁻¹+ (1 − hk(j)) + h^k(j)z + (1 − h^k(j))z²

with h^k in (18). Accordingly, to prove (20) at z = 1, it suffices to show that the term

∇^m(qℓhk(j − ·)) =

m

X

i=0

(−1)ⁱ m i

!

i^ℓhk(j − i)

converges to zero with the rate O(2^{−k(d−1−ℓ)}) as k → ∞. In fact, by the (discrete version) Leibnitz rule, we have

∇^m(qℓh^k(j − ·)) = 2^kℓ∇^m(qℓ(2^−k·)h^k(j − ·))

= 2^kℓ

m

X

n=0

∇ⁿ_nhk(j − ·)(∇^m−n_m qℓ(2^−k·)).

Here, note that ∇ⁿ_nhk(j − ·) is nth order (backward) undivided difference of hk on u^k_j−i with i = 0, . . . , n. By Lemma ??, u^k_n → 1, as k → ∞, with the convergence rate (at least) O(2^−k) uniformly with respect to n. Then,

∇ⁿ_nhk(j − ·) converges to zero with the rate O(2^−kn) as k → ∞. Consequently, it implies that ∇^m(qℓh^k(j − ·)) = O(2^{−k(m−ℓ)}).

Case 2: z = −1.

From the explicit formula of the mask a^k,j₂ of the NVPS of degree 2, it is obvious that a^k,j₂ (−1) = 0. Thus, the Laurent polynomial a^k,j₂ (z) is of the form a^k,j₂ (z) = 2⁻¹(1 + z)b^k,j(z) and accordingly, a^k,j_d (z) in (16) can be represented as

a^k,j_d (z) =z + 1 2

d−1

b^k,j(z).

Some elementary calculation reveals that the Laurent polynomial b^k,j(z) is of the form

b^k,j(z) = 1

z(1 + u^k_j)(1 + 2u^k_jz + z²).

(13)

u₄ = 0 u₄ = 1 u₄ = 10

(a)

u_i ≡ 0 ui ≡ 1 u_i ≡ 10 ui random

(b)

Fig. 1. The results of the NVPS: (a) one parameter u₄, (b) the whole parameter sequence is changed for the NVPS of degree 4.

Then, we obtain from (11) and Corollary 3.4 that

|b^k,j(−1)| =

2(1 − u^k_j) 1 + u^k_j

= 8ka^k,j− ak∞≤ c2^−k.

Consequently, it claims that (^d_dz^ℓa^k,j_d )(−1) is zero for 0 ≤ ℓ < d − 1, and it is O(2^−k) as k → ∞. when ℓ = d − 1, It indeed verifies that the convergence property in (19) holds for z = −1. Hence, it completes the proof. ✷

4 Numerical Examples

Our NVPS aims to generate blending curves and insert analytic curves through introducing a parameter sequence based on existing generalized subdivision scheme. This is of broad application value as described in Section 1. Here we give some examples. In Figure 2 (a), a blending curve similar to that in Figure 5 in paper (Wang and Fang 2008) is generated by NVPS of degree 2. It includes a piece of trigonometric B-spline curve, a piece of hyperbolic B-spline curve and a piece of polynomial B-spline curve, which are marked with red.

The whole subdivision curve is marked with black and its control polygon is marked with blue. In Figure 2 (b), a torque spring curve is generated by NVPS of degree 4 in which a piece of helix and a piece of arc are inserted. In Figure 2 (c), a sketch of swan is generated by NVPS of degree 5, in which four pieces

(14)

(a) (b)

c4

c1

c3

c2

(c)

Fig. 2. These examples of blending curves marked with black are respectively generated by NVPS of (a) degree 2, (b) degree 4, (c) degree 5, in which some special curves marked with red are inserted. These special curves are (a) a piece of hyper- bola, a piece of polynomial B-spline curve and a quarter of a circle; (b) a helix and a piece of arc; (c) four pieces of curves in (22).

of special curves with general parametric equations are inserted.

c1 : x(t) = 14 + 1.25 cos t, y(t) = 4.5 + 1.25 sin t, t ∈ [0, 2π];

c₂ : x(t) = t, y(t) = −11.2 − .74t + .036t², t ∈ [−π, 5π/2];

c3 : x(t) = 1.2t + .08t − .1 sinh 2t, y(t) = t + 2 cosh 2t, t ∈ [−2π, −π/4];

c4 : x(t) = 1 − t − 2 sinh 2t, y(t) = t + cosh 2t, t ∈ [−4π, −11π/4].

(22)

In applications of designing automobile and mechanical products, chamfering is a commonly used process in order to make mellow shapes of products or avoid harming operators because of sharp angles of products. Here we design a chamfering algorithm for a sharp angle.

Algorithm 2. Let c be a variable parameter subdivision curve with control polygon Pc and a sharp angle ∠BAC be a section of c. Giving a radius rA in a suitable domain, we generate a piece of arc tangent to both edges of this angle with radius rA by generalized subdivision scheme. Then inserting the control polygon \P1AP2 and corresponding parameters of the arc into Pc and its parameter sequence respectively, we can generate c after chamfering by NVPS in whole. The main procedures of solving \P1AP2 and the corresponding parameter uA are listed in the following.

• As illustrated in Figure 3 (a), let AB, AC be two edges of the sharp angle ∠BAC. We respectively choose two points on AB, AC so that |AB1| =

|AC1| = min(|AB|, |AC|).

(15)

• Taking B1, A, C1 as control points, we compute the radius rmax of the arc which can be generated from B1AC1 by generalized subdivision scheme according to the algorithm proposed in section 5.3 in paper (Fang et al 2010).

Then one can choose any rA ∈ (0, rmax] as the chamfering radius.

• As we see in Figure 3 (b), \P1AP2 is the control polygon from which a piece of arc with radius rA can be generated by generalized subdivision. Here,

|AE| = |P1E|, |AF | = |P2F |, OE⊥AB, OF ⊥AC, |OE| = |OF | = rA. With the given coordinate values of A(xA, yA), B(xB, yB), C(xC, yC) are known, the coordinate values of P₁(x₁, y₁), P₂(x₂, y₂) are obtained as

xi = xA+ sign(xC/xB− xA) · 2rA| cot(θ/2)|/^q1 + k_i² yi = kixi+ bi, i = 1, 2,

where θ = ∠BAC, kⁱ = _x^yⁱ_i^−y_−x^A_A, b1 = yB− k1xB, and b2 = yA− k2xC.

• According to the algorithm proposed in Section 5.2 in paper (Fang et al 2010), we compute the tension parameter uAwith which a piece of arc with radius rA can be generated by generalized subdivision from control polygon P\1AP1.

In Figure 3 (c), the quadrangle ABCD has four sharp angles and the coordinate values of four vertexes are respectively A(−6.3825, 1.6082), B(3.2028, 4.2398), C(10, −6.7544), D(−8.4101, −6.7544). It can be seen as a variable- parameter subdivision curve with each vertex being triple control point in its control polygon ABCDA and with a constant parameter sequence {u\ i ≡ 1}¹³_i=0. Now we chamfer them according to their respective appointed radii rA = 3.650669, rB = 2, rC = 1, rD = 1.691966. By Algorithm 2, we respectively solve the control points and the tension parameter for each sharp angle at first. Then we insert them into the original control polygon and the original parameter sequence. By our NVPS, the curve after chamfering is generated as illustrated in Figure 3 (d).

5 Conclusion and future work

In this paper, we extend generalized subdivision with a tension parameter to the case of curve subdivision scheme with a variable-parameter sequence.

Then those curves blended by different types of generalized B-spline curves can be generated by subdivision, which is of very important application value.

In fact, it can be extended to the case of surface subdivision of arbitrary topology. This is one of our further research work. In addition, we will try to find basic functions of NVPS, just like generalized B-spline functions being basic functions of generalized subdivision.

(16)

A

B

C

rA

(a)

A

P1

P2

rA O

E F

B

C

(b)

A

D C

B

rA

rC

rB

rD

(c)

A

A2

A1

B1

B B2

C1

C C D 2

D 1

(d)

Fig. 3. (a)(b): the illustration figures of chamfering a sharp angle ∠BAC to get a piece of arc EF ; (b)(c): an example of chamfering four sharp angles of quadrangle ABCD according to pointed radii r_A, r_B, r_C, r_D and generating the curve after chamfering by NVPS.

Acknowledgements

The work described in this article was supported by National Science Founda- tion of China (Grant No. 60904070, 61272032) and Zhejiang Provincial Natural Science Foundation of China (Grant No. LY12F02002).

References

Carla M., Francesca P., M. Lucia Sampoli, 2011. Generalized B-splines as a tool in Isogeometric Analysis. Computer Methods in Applied Mechanics and Engrgeering, 200(2011):867-881.

Catmull E., Clark J., 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10(1978): 350-355.

Costantini P., Lyche T., Manni C., 2005. On a class of weak Tchebycheff systems. Numerical Mathematics, 101(2005):333-354.

Chaikin G. M., 1974. An algorithm for high speed curve genertion, Computer Graphics and Image Processing, 3 (1974): 346-349.

(17)

Doo D., Sabin M., 1978. Behaviour of recursive subdivision surfaces near ex- traoridinay points. Computer-Aided Design, 10(1978): 356-360.

Dyn, N., 1992. Subdivision schemes in computer-aided geometric design. In:

Light, W. (Ed.), Advances in Numerical Analysis C Volume II, Wavelets, Subdivision Algorithms and Radial Basis Functions. Clarendon Press, Ox- ford, pp. 36C104.

Dyn, N., D. Levin, 1995. Analysis of asymptotically equivalent binary subdivision schemes. Journal of Mathematicl Analysis and Application. 193(1995):

594-621.

Dyn, N., D. Levin and J. Yoon, 2007. Analysis of Univariate Non-stationary Subdivision Schemes with Application to Gaussian-Based Interpolatory Schemes. SIAM Journal on Mathematical Analysis, 39(2007): 470-488.

Dyn, N., D. Levin and J. Yoon, 2014. Some tolls for analyzing univariate non-uniform subdivision Schemes. http://math.ewha.ac.kr/ yoon/ Constr.

Approx., to appear.

Fang M., Ma W., Wang G., 2010. A generalized curve subdivision scheme of arbitrary order with a tension parameter. Computer Aided Geometric Design, 27(2010): 720-733.

Koch P.E., Lyche T., 1993. Interpolation with exponetial B-splines in tension, in Geometric modelling, G. Farin et al.(eds), Springer-Verlag. Comuting Supplement, 8(1993):173-190.

Kvasov B.I., 1999. Sattayatham P., GB-splines of arbitrary order. Journal of Computer and Applied Mathematics, 104(1999):63-88.

Lane, J.M., Riesenfeld, R.F., 1980. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 2(1980): 35C46.

Ma W., 2005. Subdivision surfaces for CAD - an overview, Computer-Aided Design, 37(2005): 693-709.

Mainar E., Pena J.M., Sanchez-Reyes J., 2001. Shape preserving alterna- tives to the rational Bezier model. Computer Aided Geometric Design, 18(2001):37-60.

Sabin M. A., Recent progress in subdivision: a survey. In N. Dodgson, M.S.

Floaterand and M. A. Sabin (eds.), Advances in Multiresolution for Geo- metric Modelling, Springer, 2004.

Sabin M. A., Analysis and design of univariate subdivision schemes, Springer- Verlag Berlin Heidelberg, 2010.

Schumaker L.L., 2007. Spline Functions: Basic Theory, third edition, Cam- bridge U.P..

Stam J., 2001. On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree. Computer Aided Geometric Design, 18(2001): 383-396.

Wang G., Fang M., 2008. Unified and extended form of three types of splines.

Journal of Computational and Applied Mathematics. 216(2008):498-508.

Zorin D., P. Schr¨oder, 2000. Subdivision for modeling and animation, ACM SIGGRAPH 2000 Course Notes, New Orleans, July 23-28, 2000.