五點二重逼近細分法

莊興龍， 檀結慶,

（1. 合肥工業大學數學學院，安徽 合肥 230009；2. 合肥工業大學計算機與信息學院，安徽 合肥 230009）

五點二重逼近細分法

莊興龍1， 檀結慶1,2

（1. 合肥工業大學數學學院，安徽 合肥 230009；2. 合肥工業大學計算機與信息學院，安徽 合肥 230009）

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

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

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

1 預備知識

給定一系列初始控制點 P0= { p0∈ Rd}，

i i∈Z設Pk= { pk∈ Rd}為第 k次細分后的控制點

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

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

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

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

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

2 五點二重逼近細分格式及其收斂性和Ck連續性

首先給出五點二重逼近細分格式的定義。

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

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

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

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

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

則

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

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

則

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

則

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

則

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

則

又6S的生成多項式為

則

3 結論與數值算例

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

圖1 五點二重逼近細分法算例

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

[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] 鄭紅蟬, 葉正麟, 趙紅星. 雙參數四點細分法及其性質[J]. 計算機輔助設計與圖形學學報, 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

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

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