五點(diǎn)二重逼近細(xì)分法

莊興龍， 檀結(jié)慶,

（1. 合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽 合肥 230009）

五點(diǎn)二重逼近細(xì)分法

莊興龍1， 檀結(jié)慶1,2

（1. 合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽 合肥 230009）

提出了一種新的構(gòu)造曲線的算法——五點(diǎn)二重逼近細(xì)分法。利用細(xì)分格式的生成多項式討論了該細(xì)分格式的一致收斂性及Ck連續(xù)性。該細(xì)分格式帶有一個張力參數(shù)μ, 通過選取不同的μ值，可以分別生成C1~C5連續(xù)的極限曲線。特別是當(dāng)μ=9/256時， 細(xì)分格式生成的極限曲線可以達(dá)到 C7連續(xù)。最后給出了五點(diǎn)二重逼近曲線細(xì)分的實例，表明了這種細(xì)分格式是有效的。

二重逼近細(xì)分；生成多項式；Ck連續(xù)性；極限曲線

細(xì)分方法是基于網(wǎng)格細(xì)化的離散表示方法，是曲線曲面造型的一項重要技術(shù)。其基本思想是，給定初始控制網(wǎng)格，定義一個細(xì)分算法，在給定的初始網(wǎng)格中不斷地插入新的頂點(diǎn)，使生成的網(wǎng)格序列收斂于一條光滑的曲線或一張光滑的曲面。由于其易在計算機(jī)上表示所以得到廣泛的應(yīng)用。Dyn等[1]利用三次Lagrange插值提出了一種四點(diǎn)二重逼近細(xì)分格式，其生成的極限曲線達(dá)到C2連續(xù)。Hassan等[2-3]第1次引入了三重細(xì)分格式的概念，并得到了三點(diǎn)三重逼近和四點(diǎn)三重插值細(xì)分算法。Siddiqi等[4]利用B樣條基函數(shù)提出了一種能生成C4連續(xù)曲線的五點(diǎn)二重逼近細(xì)分算法（事實上，該算法只能生成C3連續(xù)的極限曲線）。Ko等[5]和Siddiqi等[6]將文獻(xiàn)[1,4]的細(xì)分格式推廣到三重的情形，分別得到四點(diǎn)三重逼近細(xì)分格式和五點(diǎn)三重逼近細(xì)分格式。Hormann等[7]從代數(shù)精度的角度出發(fā)，介紹了一種三點(diǎn)三重細(xì)分算法，其生成的細(xì)分曲線為 C1連續(xù)。Siddiqi等[8-9]引入了一個張力參數(shù)，分別得到改進(jìn)的四點(diǎn)二重和改進(jìn)的三點(diǎn)二重細(xì)分算法。鄭紅蟬等[10]介紹了雙參數(shù)四點(diǎn)細(xì)分法及其性質(zhì)。Daniel等[11]將細(xì)分格式推廣到動態(tài)的情形，得到C2連續(xù)的三點(diǎn)二重動態(tài)細(xì)分格式。Dyn等[12]從理論上分析二重細(xì)分法及其極限曲線的收斂性和連續(xù)性。本文提出了一種構(gòu)造細(xì)分曲線的五點(diǎn)二重逼近細(xì)分格式，并利用生成多項式等方法討論了該算法生成的曲線的收斂性及 Ck連續(xù)性，得到光滑度更高的極限曲線。

1 預(yù)備知識

給定一系列初始控制點(diǎn) P0= { p0∈ Rd}，

i i∈Z設(shè)Pk= { pk∈ Rd}為第 k次細(xì)分后的控制點(diǎn)

i i∈Z集，則二重細(xì)分格式可表示為

其中， a = {ai}i∈Z為該細(xì)分格式的mask。

定理 1[12]若二重細(xì)分格式S一致收斂，則其mask a = {ai}i∈Z滿足

定理 2[12]若二重細(xì)分格式 S 的 mask a = {ai}i∈Z滿足式（2），則必存在一個二重細(xì)分格式 S1（稱為S的一階差分格式），滿足

定理 3[10]若二重細(xì)分格式 S 的 mask a = {ai}i∈Z及其 j階差分格式 Sj( j =1,2,… ,n)的滿足

2 五點(diǎn)二重逼近細(xì)分格式及其收斂性和Ck連續(xù)性

首先給出五點(diǎn)二重逼近細(xì)分格式的定義。

定義1 已知初始控制點(diǎn)集為 P0= {pi0∈Rd}，若 Pk= { pk∈ Rd}為第 k(k ≥0,

i∈Zi i∈Zk∈Z )次細(xì)分后的控制點(diǎn)集，則按下述遞歸定義第k+1次細(xì)分后的控制點(diǎn)

下面利用定理 2和定理 3討論細(xì)分格式(3)的收斂性與 Ck連續(xù)性。

證明：由細(xì)分格式(3)可知該細(xì)分格式的生成多項式為

根據(jù)定理2可得1S的生成多項式為分格式（3）生成的極限曲線是2C 連續(xù)的。

則

從而根據(jù)定理 3可知，細(xì)分格式（3）生成的極限曲線是一致收斂的。

又由定理2可得2S的生成多項式為

則

證明：根據(jù)定理2可得3S的生成多項式為

則

證明：根據(jù)定理 2可得4S的生成多項式為

則

證明：根據(jù)定理2可得 S5的生成多項式為

則

又6S的生成多項式為

則

3 結(jié)論與數(shù)值算例

本文提出了一種構(gòu)造極限曲線的五點(diǎn)二重逼近細(xì)分格式，并討論了該細(xì)分格式的收斂性與Ck連續(xù)性。對于任意給定的初始控制多邊形，可以通過選取不同的μ值得到一系列光滑程度不同的細(xì)分曲線。特別地，當(dāng) μ= 9/256時，細(xì)分格式生成的極限曲線是 C7連續(xù)的。 圖1所示為在初始控制多邊形給定的條件下，分別取μ=- 9/64,μ =- 13/128,μ =- 3/128,μ= 1/128時，基于本文的細(xì)分方法，經(jīng)過5次細(xì)分，所得到的 C1,C2,C3,C5連續(xù)細(xì)分曲線，其中虛線和實線分別表示初始控制多邊形與極限曲線。圖2比較了在相同的初始控制多邊形條件下，利用本文的細(xì)分方法與文獻(xiàn)[1]、[4]、[6]的細(xì)分方法所得到的極限曲線，得出利用本文的方法生成的極限曲線具有更高的光滑度。

圖1 五點(diǎn)二重逼近細(xì)分法算例

圖2 本文的細(xì)分算法與其他幾種細(xì)分算法的比較

[1] Dyn N, Floater M S, Hormann K. A C2four-point subdivision scheme with fourth order accuracy and its extensions [C]// Daehlen M, M?rken K, Schumaker L L(Eds.), Mathematical Methods for Curves and Surfaces: Tromso 2004, Nashboro Press, Brentwood, 2005: 145-156.

[2] Hassan M F, Dodgson N A. Ternary and three-point univariate subdivision schemes [C]//Cohen A, Merrien J L, Schumaker L L(Eds.), Curve and Surface Fitting: Saint-Malo 2002, Nashboro Press, Brentwood, 2003: 199-208.

[3] Hassan M F, Ivrissimitzis I P, Dodgson N A, et al. An interpolating 4-point C2ternary stationary subdivision scheme [J]. Computer Aided Geometric Design, 2002, 19: 1-18.

[4] Siddiqi S S, Ahmad N. A new five-point approximating subdivision scheme [J]. International Journal of Computer Mathematics, 2008, 85(1): 65-72.

[5] Ko K P, Lee B G, Yoon G J. A ternary 4-point approximating subdivision scheme [J]. Applied Mathematics and Computation, 2007, 190: 1563-1573.

[6] Siddiqi S S, Rehan K. A stationary ternary C4scheme for curve sketching [J]. European Journal of Scientific Research, 2009, 30(3): 380-388.

[7] Hormann K, SABIN M A. A family of subdivision schemes with cubic precision [J]. Computer Aided Geometric Design, 2008, 25: 41-52.

[8] Siddiqi S S, Rehan K. Improved binary four point subdivision scheme and new corner cutting scheme [J]. Computers and Mathematics with Applications, 2010, 59: 2647-2657.

[9] Siddiqi S S, Rehan K. Modified form of binary and ternary 3-point subdivision schemes [J]. Applied Mathematics and Computation, 2010, 216: 970- 982.

[10] 鄭紅蟬, 葉正麟, 趙紅星. 雙參數(shù)四點(diǎn)細(xì)分法及其性質(zhì)[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2004, 16(8): 1140-1145.

[11] Daniel S, Shunmugaraj P. An approximating C2non-stationary subdivision scheme [J]. Computer Aided Geometric Design, 2009, 26: 810-821.

[12] Dyn N. Subdivision schemes in CAGD [C]//Light W (Eds.), Advances in Numerical Analysis, Vol. 2, Oxford: Clarendon Press, 1992: 36-104.

A five-point binary approximating subdivision scheme for curve design

Zhuang Xinglong1, Tan Jieqing1,2
( 1. School of Mathematics, Hefei University of Technology, Hefei Anhui 230009, China; 2. School of Computer & Information, Hefei University of Technology, Hefei Anhui 230009, China )

A binary five-point approximating subdivision scheme is described. The generating polynomial method is used to investigate the uniform convergence and Ck-continuity of this subdivision scheme. The subdivision scheme generates a family of Cn(n=1, 2,3,4,5) limiting curves for certain range of tension parameter μ and a C7limiting curves forμ=9/256. Some examples of the subdivision curve design are given to demonstrate the efficiency of the scheme.

binary approximating subdivision; generating polynomial; Ck-continuity; limiting curves

TP 391

A

2095-302X (2012)05-0057-05

2011-11-22；定稿日期：2011-12-09

國家自然科學(xué)基金資助項目（61070227，60773043）；教育部科學(xué)技術(shù)研究重大資助項目（309017）

莊興龍（1985-），男，福建福州人，碩士研究生，主要研究方向為計算機(jī)輔助幾何設(shè)計。E-mail：zhuangxinglong@yeah.net