中国科学技术大学：单变量均匀静态细分格式的连续性分析和构造 Continuity Analysis and Construction of Uniform Stationary Univariate Subdivision Schemes

单变量均匀静态细分格式的连续性分析和构造 进 《中国科华技术大早数学系，家莹合厘23026 Continuity Analysis and Construction of Uniform Stationary Univariate Subdivision Schemes HANG Zhang-Jn aa

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.17, No.3, March 2006, pp.559−567 http://www.jos.org.cn DOI: 10.1360/jos170559 Tel/Fax: +86-10-62562563 © 2006 by Journal of Software. All rights reserved. 单变量均匀静态细分格式的连续性分析和构造∗ 黄章进+ (中国科学技术大学 数学系,安徽 合肥 230026) Continuity Analysis and Construction of Uniform Stationary Univariate Subdivision Schemes HUANG Zhang-Jin+ (Department of Mathematics, University of Science and Technology of China, Hefei 230026, China) + Corresponding author: Phn: +86-551-3601009, Fax: +86-551-3601005, E-mail: zjh@mail.ustc.edu.cn, http://math.ustc.edu.cn Huang ZJ. Continuity analysis and construction of uniform stationary univariate subdivision schemes. Journal of Software, 2006,17(3):559−567. http://www.jos.org.cn/1000-9825/17/559.htm Abstract: With the necessary and sufficient conditions for Ck -continuity of uniform stationary subdivision schemes, the range of free parameter in several classical interpolating curve schemes is presented. For the first time, this paper points out that the arity-2 interpolating 6-point scheme is C3 -continuous in certain range. A new C3 -continuous arity-3 interpolating 6-point scheme is also proposed. Key words: subdivision; interpolating scheme; continuity analysis 摘 要: 利用单变量均匀稳定细分格式 Ck 连续的充要条件,分析了已有的插值曲线格式各阶连续时参数的取 值范围.首次指出了六点二重插值格式可以达到 C3 连续,并构造了一种新的 C3 连续的六点三重插值细分格式. 关键词: 细分;插值格式;连续性分析 中图法分类号: TP391 文献标识码: A 由于具有算法简单、易于实现和高效性等优点,细分方法在计算机图形学和计算辅助几何设计中越来越受 到关注.最早的单变量细分格式要追溯到 Chaikin 于 1974 年提出的用于生成二次 B-样条的算法[1] .20 世纪 80 年代,Dubuc 以及 Dyn,Gregory 和 Levin 独立地提出了四点二重插值格式,并证明该格式是 C1 连续的[2,3]. Weissman 构造了一种六点二重插值格式,并给出了 C2 连续时参数的取值范围[3] .Deslauriers 和 Debuc 从多项式 插值出发,分析了 2N 点 b 重插值格式[4] . Kobbelt 引入了一种称为 3 格式的曲面细分方法[5] ,该方法在两步细分后得到三重格式.该类细分方法的 边界曲线是单变量三重格式生成的.受此启发,Hassan 和 Dodgson 等人提出了 C1 的三点三重插值格式[6] 和 C2 的四点三重插值格式[7] . ∗ Supported by the National Natural Science Foundation of China under Grant Nos.10201030, 60473132 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2004CB318000 (国家重点基础研究发展计划(973)); the National Science Fund for Distinguished Young Scholars of China under Grant No.60225002 (国家杰出青年科学基金); the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of the MOE (教育部高校优秀青年教师教学 科研奖励计划) Received 2005-04-13; Accepted 2005-08-25

大T东中格装久音把是号 】细分格式C连续充要条件 11单变量细分格式 这里，P是以控制顺点P刊，1cZ为分量的列向量，线性变换师库M称为闻分矩阵 如果每一细分的细分好阵相同，甲4工，释条式是静方的(s0nk杏，称为非静态的 7o说8 列移的整位置登心小落为润分格式的原 宽失上等机同作送季将潮学这好教安 如我幻把掩第】个非零系数的下标取为《有-O,01.今心是最小的校数.使得 -1这样无穷旋模可以筒化成由W个系数构的有限集{网…-小 定义5标志 是指拉制多边形在细分过程中扑不变的顶点 一分轻州新分为个树转新时一 爱治线有车定汉分式生一 当：是数时R给出了下面的结论m

560 Journal of Software 软件学报 Vol.17, No.3, March 2006 在单变量细分格式的收敛性和连续性分析的理论上,Dyn 等人[3,8−10] 给出了关于二重格式的充分条件和必 要条件,Hassan 等人[6,7]给出了关于三重格式的充分条件.Romani [11] 根据细分格式掩模的重数和宽度对单变量 均匀格式进行了统一的分类,并给出了一般的 a 重格式 Ck 连续的充要条件.本文利用该条件分析了一些已知格 式的连续性,指出 Weissman 的六点二重插值格式[3] 可以达到 C3 连续,并构造了一种新的 C3 连续的六点三重插 值细分格式. 本文第 1 节介绍单变量细分的概念,并修正了 Romani[11] 的充要条件.第 2 节利用该充要条件分析了已有的 单变量插值细分格式(如四点二重插值格式[3] 、六点二重插值格式[3] 、三点三重插值格式[6] 、四点三重插值格 式[7] 等),给出各阶连续时参数的取值范围.第 3 节构造了一种新的六点三重插值细分格式,并证明该格式是 C3 连续且有 4 阶精度.最后,给出本文的结论和将来的工作. 1 细分格式 C k 连续充要条件 1.1 单变量细分格式 单变量细分格式通过对初始控制多边形 P0 ={ :i∈Z}不断加细,得到一条光滑的极限曲线.细分过程用公 式可表示为 0 Pi P j =M jP j−1 . 这里,P j 是以控制顶点 ,i∈Z 为分量的列向量,线性变换矩阵 M j Pi j 称为细分矩阵. 如果每一细分步的细分矩阵相同,即 M j ≡M,j∈Z+,则称格式是静态的(stationary);否则,称为非静态的 (non-stationary). 定义 1. 细分矩阵{M j}j≥1 的列(表示一个老控制顶点在第 j 层对新控制顶点的影响系数)称为掩模(masks). 如果每一细分步仅由一个掩模 mj ={ :i∈Z}确定,格式称为均匀的(uniform)(既然在曲线的所有位置用同 样的掩模).这时,双无穷细分矩阵 M j mi j 的所有列是相同的,只是相互偏移了 a 行,即 Mak k +1,k = mi j ,∀k,i∈Z.这样细分 后的点列 Pj 对应于每个老控制顶点有 a 个新点. 定义 2. 均匀细分矩阵的每一列相对于相邻列偏移的整数位置数 a(>1)称为细分格式的重数(arity). 由于均匀细分由一个掩模确定,且相邻列仅偏移 a 个位置,所以细分矩阵 M j 有 a 个不同的行. 定义 3. 均匀细分矩阵不同的 a 行(表示一个新点被老控制顶点影响的系数的集合)称为模板(stencils). 这样,模板是由掩模 mj 的子序列隐式定义的.对一个合理的细分格式,要求模板的系数和为 1 :∀j∈Z+, 1 Z ∑ 1 = ∈ + i j mai ,l=0,…,a−1.事实上,Dyn 等人[8] 指出上述条件是均匀细分格式收敛(C0 )的一个必要条件. 如果我们把掩模第 1 个非零系数的下标取为 0(即有 =0,∀i1)是最小的整数,使得 =0,∀i> j mi j mi w−1.这样,无穷掩模 mj 可以简化成由 w 个系数构成的有限集{ :i=0,…,w−1}. j mi 定义 4. 正整数 w(>1)称为细分格式或掩模的宽度(width). 1.2 C k连续充要条件 定义 5. 标志点(mark points)是指控制多边形在细分过程中拓扑不变的顶点. 我们在进行格式分析时,只需分析标志点的不变邻域(invariant neighborhood)所对应的双无穷细分矩阵 M 的有限阶的子方阵(局部细分矩阵).当细分重数为偶数时,只需分析一个局部细分矩阵;而当重数为奇数时,需要 分析两个不同的局部细分矩阵. 记 m 为宽度为 w(>1)、重数为 a(>1)的掩模,M 为对应的细分矩阵.定义细分格式的生成函数(generating funtion)为 Laurent 多项式 ∑∈ = Z ( ) i i i m z m z . 当重数 a 是偶数时,Romani 给出了下面的结论[11] :

凳章进：草变量均句好态加分移式的遂埃性分析和构选 561 定理1.由掩模围定文的均匀静态细分格式，局部细分电库M的阶数为N a-l 格式是C20选续的， 当且仪当 d)= 0- 2)】 1- 是1a巴t多项式且以其为生成函数的闻分格式的W-k-1阶局那细分矩阵万，的谱举轻滨足 mD)<1 当重数g是奇数封Roa给出了下而的结论： 定理2.由俺模m定文的均匀静药细分格式两个月细分知阵和M的阶数分别为W和从-1，这里 N- 格式是(0)连簇的，当且仅当 a-l d.(=)=a m 是Laurent多项式，且以其为生成函登的细分格式的N-★-1阶同部细分年年D和-★-2阶局部细分矩阵D:的 静半径端足 (D:)c1(D)c1. 注【.Romani在文献[1l中的d(e表达式有误，都速漏了项 有了这两个定理对于含一个自由参数的单麦量均匀德定格式我们可以精雨地给出该格式生成（连装由 线时参数的量大取值范围 2已有格式的分析 已有的偶重数插值格式主要有Dyn等人提出的四点二重插值格式四和Veissman提出的大点二币插值格 式吼奇重数插值格式主要有Hs5等人提出的三点三重括值格式和四点三重插植格式网这些格式都含有 一个自由参数下面，我们首先根据定理1和定理2给出连续性分析的一授步夏然后分析这些格式给出各阶光 滑时参数的取值范田 2.1分析步 由定理I有网)=a 1- 1-) 0-是格式C d或9，可如从生成函数me)中，可分解出+1个- 主候的一个必县条件.向对于抽值格式，该条件表明格式具有阶精度(pr©csio0sc),即如果初始控制点在最次多 项式上采样而得，则极限出找生成该多项式 又根暴文款山]的注3，检查风D)<1等价于检查局部细分矩降夏教模大小排列的N个特征值-0 -1有如下结构 =N- 从而对于一个给定细分规则的口重格式，当a为偶盘时，我们可按下面步限分析其连续性： Sp1.根架细分规则确定梵模思， Sep2.根据m确定V 阶的局部细分矩阵M,并求出其N个特征值；：…N-1

黄章进:单变量均匀静态细分格式的连续性分析和构造 561 定理 1. 由掩模 m 定义的均匀静态细分格式,局部细分矩阵 M 的阶数为       − = a 1 w N .格式是 Ck (k≥0)连续的, 当且仅当 ( ) 1 (1 ) ( ) 1 1 m z z z z d z a k a a k k + −         − − = 是 Laurent 多项式,且以其为生成函数的细分格式的 N−k−1 阶局部细分矩阵 Dk 的谱半径满足 ρ( ) Dk <1. 当重数 a 是奇数时,Romani 给出了下面的结论[11] : 定理 2. 由掩模 m 定义的均匀静态细分格式,两个局部细分矩阵 M 和 M 的阶数分别为 N 和 N−1,这里       − = a 1 w N .格式是 Ck (k≥0)连续的,当且仅当 1 1 (1 ) ( ) ( ) 1 k a k k a z z d z a m z z + −   − =     − 是 Laurent 多项式,且以其为生成函数的细分格式的 N−k−1 阶局部细分矩阵 Dk 和 N−k−2 阶局部细分矩阵 Dk 的 谱半径满足 ρ ρ ( ) D D k k <1, ( ) <1 . 注 1. Romani 在文献[11]中的 dk(z)表达式有误,都遗漏了 z a−1 项. 有了这两个定理,对于含一个自由参数的单变量均匀稳定格式,我们可以精确地给出该格式生成 Ck 连续曲 线时参数的最大取值范围. 2 已有格式的分析 已有的偶重数插值格式主要有 Dyn 等人提出的四点二重插值格式[3] 和 Weissman 提出的六点二重插值格 式[3] ;奇重数插值格式主要有 Hassan 等人提出的三点三重插值格式[6] 和四点三重插值格式[7] .这些格式都含有 一个自由参数.下面,我们首先根据定理 1 和定理 2 给出连续性分析的一般步骤,然后分析这些格式,给出各阶光 滑时参数的取值范围. 2.1 分析步骤 由定理 1 有 ( ) (1 ) 1 ( ) 1 1 d z z z z m z a k k a a k + − −         − − = ,可知:从生成函数 m(z)中,可分解出 k+1 个 1 (1 ) 1 − − − a a z z z 是格式 Ck 连续的一个必要条件.而对于插值格式,该条件表明格式具有 k 阶精度(precision set),即如果初始控制点在 k 次多 项式上采样而得,则极限曲线生成该多项式. 又根据文献[11]的注 3,检查 ρ( ) Dk <1等价于检查局部细分矩阵 M 按模大小排列的 N 个特征值{λi:i=0,…, N−1},有如下结构:        < = + − = = , 1,..., 1 1 , 0,..., 1 i k N a i k a i k i i λ λ . 从而对于一个给定细分规则的 a 重格式,当 a 为偶数时,我们可按下面步骤分析其连续性: Step 1. 根据细分规则确定掩模 m; Step 2. 根据 m 确定       − = a 1 w N 阶的局部细分矩阵 M ,并求出其 N 个特征值{λi:i=0,…,N−1};

562 maf3 ofhrre年争展l.17.No3.Mah2o5 S孔p3.根帮m确定生成函登：以并从中分解尽可途多的阴式1-兰 -可，翔到 mz)-0 1- 0- d(e, 现在我们可知格式至多连架，且有k阶精度： S9tp4,对一0k,检查特征值是香有如下端构： =,2=0一 -Jx-1 若满足测格式是心连线的潍铁检直+1时是否渊足，若不满足则停止，格式是连续的 类地，当a为奇登时，我们按下面步摩分析格式的连续性： Sp1.根帮细分规则角定株模愿， S即2极搭m骑定N-吕 阶和从1阶的两个局部细分处库的局部细分矩降M和M,并求出它门的 特征值20N-1!和{：4-0，N-2 Sp3.根据m确定生成函数m以并从中分解尽可使多的闲式1-兰 1-,将到 1-: oM)=a 1- d(), 现在我们可知格式至多逢线，且有阶精度： Scp4.对0，k,松春特征值是否有如下结构： 1 -1-0 Al<-j+1w-1 不=7=0小 -1-2 若满足测略式是（心连续的，笨狱校童+1时是否满足，若不满足则停止格式是连续的 2,2偶重数格式 四点二重插值格式的细分规则为可 "-以 P-*p+贴)-4+贴 D加等人在文中指曲：当闭兮时格式悬C连续的，即是收致的，当0<0<5一时，格式是C连铁 8 的.R0m1在文献11中作为例子用不同的分析步票给出了与我们相同的结果.考虑到完聚性我们重新分析该 格式： 局部知分矩吓M的阶数=？具体形式为

562 Journal of Software 软件学报 Vol.17, No.3, March 2006 Step 3. 根据 m 确定生成函数 m(z),并从中分解尽可能多的因式 1 (1 ) 1 − − − a a z z z ,得到 ( ) (1 ) 1 ( ) 1 1 d z z z z m z a k k a a k + − −         − − = , 现在我们可知,格式至多 Ck 连续,且有 k 阶精度; Step 4. 对 j=0,…,k,检查特征值是否有如下结构:       < = + − = = , 1,..., 1 1 , 0,..., 1 i j N a i j a i k i i λ λ , 若满足,则格式是 Cj 连续的,继续检查 j+1 时是否满足;若不满足,则停止,格式是 Cj−1 连续的. 类似地,当 a 为奇数时,我们按下面步骤分析格式的连续性: Step 1. 根据细分规则确定掩模 m; Step 2. 根据 m 确定       − = a 1 w N 阶和 N−1 阶的两个局部细分矩阵的局部细分矩阵 M 和 M ,并求出它们的 特征值{λi:i=0,…,N−1}和{ λi : i = 0,...,N − 2 }; Step 3. 根据 m 确定生成函数 m(z),并从中分解尽可能多的因式 1 (1 ) 1 − − − a a z z z ,得到 ( ) (1 ) 1 ( ) 1 1 d z z z z m z a k k a a k + − −         − − = , 现在我们可知,格式至多 Ck 连续,且有 k 阶精度; Step 4. 对 j=0,…,k,检查特征值是否有如下结构:            < = + − = = < = + − = = , 1,..., 2 1 , 0,..., 1 , 1,..., 1 1 , 0,..., 1 i j N a i j a i j N a i j a i k i i i k i i λ λ λ λ , 若满足,则格式是 Cj 连续的,继续检查 j+1 时是否满足;若不满足,则停止,格式是 Cj−1 连续的. 2.2 偶重数格式 四点二重插值格式的细分规则为[3]       + − +      = + = + − + + + + ( ) ( ) 2 1 1 1 2 1 2 1 1 2 j i j i j i j i j i j i j i P P P P P P P θ θ . Dyn 等人在文献[8]中指出:当 2 1 θ < 时,格式是 C0 连续的,即是收敛的;当 8 5 1 0 − < θ < 时,格式是 C1 连续 的.Romani 在文献[11]中作为例子,用不同的分析步骤给出了与我们相同的结果.考虑到完整性,我们重新分析该 格式: 掩模为       = −θ +θ +θ,0,−θ 2 1 ,1, 2 1 m ,0, ,宽度 w=7,重数 a=2. 局部细分矩阵 M 的阶数 N=7,具体形式为

黄车近：单置量均幻导态细分移或的连键性分所和肉造 563 40001 00 0 00 0 D M= 000 10 00 0 0 0 0004411a 这里a=8a=+ 特征值为-{与2868-i16网v16@ 从1am多项式冲分解尽可能多的因武层1：海到-上二 20-: d(:).这里Laurent多 项式d=气-2州4快+143+4化-2化 可见对于一餐的8四点二重格式至多是C的 1心连铁要求1水116惠-宁c0<宁子 2C连续安求4且小26即0c8c 4 于是我们有下面的结论 定理3.对任意的初始控利多边形，四点二重麵值格式生成的楼限由线： 1当-0e兮时，是心连续的 2.当0<0<二时，是C连续的 4 法2.当日=时可以提取出更多的因式侧- 16 此时特征镇为以上1上》 12'4'481616 从而对于一般的初始控制多边形，极限由线不可能是C或C心的只能为 C但此时格式有3阶精度 六点二重桶值格式的细分规则为例 -型 P四-品++-信0pH++a%+4 Weissman说明：当<伙002时格式是的(2连续的因仿照四点二重格式的分析过程，我)有下正的结论： 定理4.对任意的初给控制多边形，六点二震辐值路式生成的极限由线： 1.当-话<0<-1+3时，是线的 2当立6+5<0觉-1)时，是C隆线的 3.当0<六4时，是C连线的 4.当0<庆以时，是C连线的 这甲，吼4分别是四次方程-5+54r+768r2-1618x+26214x0与-1+32x+1536x2-32763x42097152x-0的正 实根

黄章进:单变量均匀静态细分格式的连续性分析和构造 563 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 000 0 0 1 0000 0 0 000 1 0 0 0 0 0 0 0000 1 0 0 000 a a a a a a a a M a a a a a a a a 0           =             . 这里,a0=−θ,a1= 2 1 +θ. 特征值为 ( ) ( )      λ = θ −θ −θ − − θ 1+ 1−16θ 4 1 1 1 16 , 4 1 ,2 , , , 2 1 1 . , 从 Laurent 多项式 m(z)中分解尽可能多的因式 z z z = + − − 1 1 1 2 ,得到 ( ) (1 ) 1 2 1 ( ) 1 2 2 d z z z z m z         − − = .这里,Laurent 多 项式 d1(z)=z 2 (−2θ+4θz+(1−4θ)z 2 +4θz 3 −2θz 4 ). 可见,对于一般的θ,四点二重格式至多是 C1 的: 1. C0 连续:要求λ0=1 且|λi|<1,i=1,…,6,即 2 1 2 1 − <θ < ; 2. C1 连续:要求λ0=1,λ1= 2 1 且 2 1 λi < ,i=2,…,6,即 4 1 0 < θ < . 于是我们有下面的结论: 定理 3. 对任意的初始控制多边形,四点二重插值格式生成的极限曲线: 1. 当 2 1 2 1 − <θ < 时,是 C0 连续的; 2. 当 4 1 0 < θ < 时,是 C1 连续的. 注 2. 当 16 1 θ = 时,m(z)可以提取出更多的因式: ( ) (1 ) 1 2 1 ( ) 3 4 2 3 d z z z z m z         − − = .这里,         = − + − 2 2 2 1 ( ) 2 4 3 z d z z z .但 此时特征值为       − − 16 1 , 16 1 , 8 1 , 4 1 , 4 1 , 2 1 1, .从而对于一般的初始控制多边形,极限曲线不可能是 C2 或 C3 的,只能为 C1 .但此时格式有 3 阶精度. 六点二重插值格式的细分规则为[3]       + + +       + − +      = + = + − + − + + + + 3 ( ) ( ) 16 1 2 ( ) 16 9 1 1 2 2 3 1 2 1 1 2 j i j i j i j i j i j i j i j i j i P P P P P P P P P θ θ θ . Weissman 说明:当 0<θ<0.02 时,格式是的 C2 连续的[3] .仿照四点二重格式的分析过程,我们有下面的结论: 定理 4. 对任意的初始控制多边形,六点二重插值格式生成的极限曲线: 1. 当 ( 1 3 2) 16 1 16 3 − < θ < − + 时,是 C0 连续的; 2. 当 ( 1 19) 32 1 ( 6 3 2) 32 1 − + <θ < − + 时,是 C1 连续的; 3. 当 0<θ<θ0 时,是 C2 连续的; 4. 当 0<θ<θ1 时,是 C3 连续的. 这里,θ0,θ1 分别是四次方程−5+64x+768x2 −16384x3 +262144x4 =0 与−1+32x+1536x2 −32768x3 +2097152x4 =0 的正 实根

564 onnal of Sofhrare款作子报l.I7.No3,Maeh2005 注3.当-3时，对于一般的初始控制多边形，极限曲线是C心的，但北时格式有5阶桔度。 256 23奇重数格式 三点三重插值格式的细分规则为列同 =a%+a+% - B-a:%+4+4 这里，西-国-手业西一rm符人仅说明了当子和号时格武是C的门夫似于臀重数格式的 4 分析过程我们有下面的端论： 定理5.对任意的初娇控制多边形，三点三盖新值格式生成的极限由线： 1.当0ce2时.是C心连线的： 3 9ce时，足C连续的 注4.当：=二时对于一散的初始花制多边形，极限幽线是C的.但此时格式有2哈精度. 9 四点三重播慎格式的细分理则为可 =时 m=a以+a+H+g,k 州-a,%+a,+a%+a0 这里， 13,1 71 1.1 4864风-18i441824品i864 sn等人说明了当 户后口<号时，将式是C的，类似于偶币数格式的分析过程，我们有下面的结记 定理6.对任竞的初给控制多边形，四点三震插值格式生成的极限由线： 1,当-<心1时是连续的 山兮时是C连装舱 2当-1 3 白后c写时是C©选续的 当 9 注5.当r=对，对于一般的初始挖制多边形，成限卧找是C的，但此时格式有3阶枯皮。 27 3六点三重插值格式的构造 定理！和定型2不仅可以用十分析已有的格式，还可以用十指导构造新的细分格式下南，我们构造一种新 的六点三重插值幻分格式 记"F州从生成函数中可分解出因式- 式-可的一个充分条件是棱板系数和为1，即 Smaw=11-0.--1 ) 这时

564 Journal of Software 软件学报 Vol.17, No.3, March 2006 注 3. 当 256 3 θ = 时,对于一般的初始控制多边形,极限曲线是 C2 的,但此时格式有 5 阶精度. 2.3 奇重数格式 三点三重插值格式的细分规则为[6]        = + + = = + + − + + + + − + + − j i j i j i j i j i j i j i j i j i j i P a P a P a P P P P a P a P a P 2 1 1 0 1 1 3 1 1 3 0 1 1 2 1 1 3 1 . 这里, = µ = − µ = − + µ 3 1 2 , 3 4 , a0 a1 a2 .Hassan 等人仅说明了当 9 3 9 2 < µ < 时,格式是 C1 的[6] .类似于偶重数格式的 分析过程,我们有下面的结论: 定理 5. 对任意的初始控制多边形,三点三重插值格式生成的极限曲线: 1. 当 3 2 0 < µ < 时,是 C0 连续的; 2. 当 3 1 9 2 < µ < 时,是 C1 连续的. 注 4. 当 9 2 µ = 时,对于一般的初始控制多边形,极限曲线是 C0 的,但此时格式有 2 阶精度. 四点三重插值格式的细分规则为[7]        = + + + = + + + = − + + + + − + + + + + j i j i j i j i j i j i j i j i j i j i j i j i P a P a P a P a P P a P a P a P a P P P 3 1 2 1 1 0 2 1 3 1 0 1 1 2 1 3 2 1 3 1 1 3 . 这里, µ µ µ µ 6 1 18 1 , 2 1 18 7 , 2 1 18 13 , 6 1 18 1 a0 = − − a1 = + a2 = − a3 = − + . Hassan 等人说明了当 9 1 15 1 < µ < 时,格式是 C2 的[7] .类似于偶重数格式的分析过程,我们有下面的结论: 定理 6. 对任意的初始控制多边形,四点三重插值格式生成的极限曲线: 1. 当−1<µ<1 时,是 C0 连续的; 2. 当 3 1 5 1 − < µ < 时,是 C1 连续的; 3. 当 9 1 15 1 < µ < 时,是 C2 连续的. 注 5. 当 27 1 µ = 时,对于一般的初始控制多边形,极限曲线是 C1 的,但此时格式有 3 阶精度. 3 六点三重插值格式的构造 定理 1 和定理 2 不仅可以用于分析已有的格式,还可以用于指导构造新的细分格式.下面,我们构造一种新 的六点三重插值细分格式. 记 m(0)(z)=m(z),从生成函数 m(z)中可分解出因式 1 (1 ) 1 − − − a a a z z z 的一个充分条件是模板系数和为 1,即 ∑∈ + = Z 1 i mai l ,l=0,...,a−1 (*) 这时

兴章进：单变量均力奇奇细分移式的连续性分析和构造 366 me)-m(e1-兰 1-可 →aw()-wkl(I+=++) →a-女am+t+m →m=em-+m++m台 这样提取因式的多项式操作转化为对数列的操作容易看出，m)与d)关系为d,)-, 0,1 对于重数=3，式()为 -1/-0L2 ( 由对称性，可设六点三重括值格式为 型- P-a+%++,+a4t画，% =a以+a以+a,+m+a+w 这里a,为待定系数。 格式掩模为 m=w-{a0.d4a0:a,1,m.00,a1,0y 为了楼格式是C心连续，即生减两数m可以提取出闲式，1- 0m香要满是式“%即立a=1,则有a 1一一2一从而有 masar-0s.-0atasata-d-as.--0Atortos.1-20:-20-20s t4t.--1ta1-4-的4*.-m.m-.i 为了使格式是C连铁.m"需要澜是式彩有a+20*-2a一，从而有 m=9a.mr2.-2ats.ta4*2.2at0-2a-4.-4a-2a1a4+2a5+4a4+2a 4e-2+0+2a5.2a+1-2m44as.+a+2as,-2a+a54e-2ss} 为了使格式是C连续am”需要澜是式“1测有a-)-3ar如，从而有 oAr-3o-atos.aasa-120 -12a;.300tm+2.-300+3 为了使格式是C心连读，m要满是式*图有一+o从面有 sera4a6a,+7a4o引a247ara6,4raai 81 为了使格式是C连线.“要澜是式测有心-，从而有 a元嘉1s品-，六1s六ai 为了使格式是产连装要满足式“则有心品从面有 mL7,-34,37,-34,-71

黄章进:单变量均匀静态细分格式的连续性分析和构造 565 ( ) ... . ... ( ) ( )(1 ... ) (1 ) 1 ( ) ( ) ( 1) 1 ( 1) 2 ( 1) 1 ( 1) ( ) ( 1) ( 1) 2 ( 1) 1 ( ) 1 ( ) ( 1) 1 1 ( ) ( 1) + − + − + + − + + + + − + + − + − + − − + ⇒ = − + + + ⇒ = + + + ⇒ = + + + − − = k i k i a k i a k i k i k i k i a k i a k i a k k a a a k k m am m m m am m m m az m z m z z z a z z z m z m z 这样,提取因式的多项式操作转化为对数列的操作.容易看出,m(k) (z)与 dk(z)关系为 ( ) 1 ( ) ( 1) m z a d z k k + = , k=0,1,… 对于重数 a=3,式(*)为 2 1, 0,1, (**) Z ∑ 3 = = ∈ + m l i i l 由对称性,可设六点三重插值格式为 1 3 1 3 1 0 2 1 1 2 3 1 4 2 5 3 1 3 2 5 2 4 1 3 2 1 1 2 0 3 j j i i j jjj j j i iii i i j j j j j j i i i i i i P P P a P a P a P a P a P a P P a P a P a P a P a P a P + + j i j i + − − + + + + + − − + +  =   = + + + + +   = + + +++ + . 这里,ai 为待定系数. 格式掩模为 m(0)=m={a5,a0,0,a4,a1,0,a3,a2,1,a2,a3,0,a1,a4,0,a0,a5}. 为了使格式是 C0 连续,即生成函数 m(z)可以提取出因式 2 3 3(1 ) 1 z z z − − ,m(0) 需要满足式(**),即 ,则有 a 5 0 1 i i a = ∑ = 2= 1−a0−a1−a3−a4−a5.从而有 m(1)={a5,a0−a5, −a0,a4+a5,a0+a1−a4−a5, −a0−a1,a3+a4+a5,1−2a3−2a4−2a5, a3+a4+a5, −a0−a1,a0+a1−a4−a5,a4+a5, −a0,a0 −a5,a5}. 为了使格式是 C1 连续,m(1)需要满足式(**),则有 a3= 3 1 +2a0+a1−2a4−3a5.从而有 m(2)=9{a5,a0−2a5, −2a0+a5,a0+a4+2a5,2a0+a1−2a4−4a5, −4a0−2a1+a4+2a5, 3 1 +4a4+2a1, −4a0−2a1+a4+2a5, 2a0+a1−2a4−4a5,a0+a4+2a5,−2a0+a5,a0−2a5,a5}. 为了使格式是 C2 连续,m(2)需要满足式(**),则有 a1= 9 1 − −3a0−a4−3a5.从而有 m(3)=27{a5,a0−3a5, −3a0+3a5,3a0+a4+2a5, 9 1 − −a0−4a4−12a5, 3 1 +6a4+18a5, 9 1 − −a0−4a4−12a5,3a0+a4+2a5, −3a0+3a5,a0−3a5,a5}. 为了使格式是 C3 连续,m(3)需要满足式(**),则有 a4= 81 4 − +a0−4a5.从而有 m(4)=81{a5,a0−4a5, −4a0+6a5, 81 4 − +7a0−4a5, 81 11 −8a0+2a5 81 4 − +7a0−4a5,−4a0+6a5,a0−4a5,a5}. 为了使格式是 C4 连续,m(4)需要满足式(**),则有 a0= 243 3 −a5.从而有 m(5)=243{a5, 243 5 −6a5,− 243 25 +15a5, 243 43 −20a5, 243 25 − +15a5, 243 5 −6a5,a5}. 为了使格式是 C5 连续,m(5)需要满足式(**),则有 a5= 729 7 .从而有 m(6)={7,−34,57,−34,−7}

5话 fowmal of Sofman状件学报al,17,No3,March2006 我们不能厚进一步得到m川 于是我1构造了一种新的六点三重插值格式，它的系数a,为 4=20-H 35 4-9+5业 0-10￥ 70 0,224 +104 嘉 ds=u 此时，生成属数河以提取因式品的5次展即格式至多为心蓬铁 特地一时系数为4一测风”石此时生成数 阳间以提取因式上品的6次器，即格式至多为c选续份照三点三重格式的分析过配，我打有下面的 站论 定理7.对任章的初始控利多边形，六点三承插债路式生成的极限由线： 1.当二601+984 4374 时，是C连铁的， 243 2当二899+48281 37 H安 时是C莲续的： 21s70 1701 3.当-197+4网 19 21870 cMc 1701 时，是C连续的： 4.当37+v3609 21870 - 时，是C心连续的 701 注6.对于一般的：，格式有4阶桔度.当红=了时，对于一毅的初始挖制多边形，极限垫线是C的，但北时 729 格式有5阶精度 4结论 木文利用Romani的充要条件川系统地分析了一些已有的单变量插值细分格式各阶连续时参数的取值范 困指出了smn的六点二重扮值格式可以达到C3连续，另外构地了·冲新的六点三重插值细分格式，与 六点二重捕值格式相比连续性员问为C但高一阶精度 本文构造福值细分格式的方法是一神代数方法，而W5ms等人从几刺的角度研究了纸分格式的构 造叫威然本文中的构造方法对于精度的除数提高是有效的，但对迹实阶的政苦并不是直接而有效的在以后的 工作中，我门将考地晚否通过增如参数个数或从几何角度给出提高连续阶的构造方法另外，如何选择参数来确 定括值细分格式的通近精度，也是·个有特进步研究的问题 References: [1]Chaikis GM.An algorithm for high speed curve peeration.Computer Graphics and Image Processie.1974.3()-519. 2]Dubue S.Imerpolation rough a iterative scheme.Joumal of Maheinalical Analysis and Applicatioss,1986,114(1):185-204

566 Journal of Software 软件学报 Vol.17, No.3, March 2006 我们不能再进一步得到 m(7). 于是,我们构造了一种新的六点三重插值格式,它的系数 ai 为                  = = − − = + = − = − + = − µ µ µ µ µ µ 5 4 3 2 1 0 5 243 7 10 243 70 10 81 70 5 243 35 243 5 a a a a a a . 此时,生成函数 m(z)可以提取因式 2 3 3(1 ) 1 z z z − − 的 5 次幂,即格式至多为 C4 连续. 特别地,当 729 7 µ = 时,系数 ai 为 729 7 , 243 56 , 729 280 , 729 560 , 729 70 , 729 8 a0 = a1 = − a2 = a3 = a4 = − a5 = .此时,生成函数 m(z)可以提取因式 2 3 3(1 ) 1 z z z − − 的 6 次幂,即格式至多为 C5 连续.仿照三点三重格式的分析过程,我们有下面的 结论: 定理 7. 对任意的初始控制多边形,六点三重插值格式生成的极限曲线: 1. 当 243 13 4374 601 189841 < < − + µ 时,是 C0 连续的; 2. 当 1701 37 21870 899 548281 < < − + µ 时,是 C1 连续的; 3. 当 1701 19 21870 197 70489 < < − + µ 时,是 C2 连续的; 4. 当 1701 13 21870 37 13609 < < + µ 时,是 C3 连续的. 注 6. 对于一般的 µ ,格式有 4 阶精度.当 729 7 µ = 时,对于一般的初始控制多边形,极限曲线是 C2 的,但此时 格式有 5 阶精度. 4 结 论 本文利用 Romani 的充要条件[11] ,系统地分析了一些已有的单变量插值细分格式各阶连续时参数的取值范 围.指出了 Weissman 的六点二重插值格式[3] 可以达到 C3 连续.另外,构造了一种新的六点三重插值细分格式,与 六点二重插值格式相比,连续性虽同为 C3 ,但高一阶精度. 本文构造插值细分格式的方法是一种代数方法,而 Ivrissimtzis 等人从几何的角度研究了细分格式的构 造[12].虽然本文中的构造方法对于精度的阶数提高是有效的,但对连续阶的改善并不是直接而有效的.在以后的 工作中,我们将考虑能否通过增加参数个数或从几何角度给出提高连续阶的构造方法.另外,如何选择参数来确 定插值细分格式的逼近精度,也是一个有待进一步研究的问题. References: [1] Chaikin GM. An algorithm for high speed curve generation. Computer Graphics and Image Processing, 1974,3(4):346−349. [2] Dubuc S. Interpolation through an iterative scheme. Journal of Mathematical Analysis and Applications, 1986,114(1):185−204

黄章近：章要老均幻静态州分格瓦的连陵世分析构漫 567 Tyn k.Gireprey IA.Levin D A 4-psint irterpobtory shdvin scheme te crv dedn ampeer Aided Georeme nesg. 197414257-2城 刊darcn,ktcs.Smng起iie islapolalias prceo&Cee由ciie Apprusinirn191k4投k (b:L3-Sabdvaios.In:Papc.ufthe 5GKAPH 200.Nem Yurk:ACM ITex 2000112 llaor MF.Dodgsan NA Terary nd three-pint urianate afddisicon schemes In:Coben A.Nemin II Schundee 1.1.ede Carve ad Fating Sairt-Mal 0.:Nadbem,. Haoar M,Ivriamazis I,Sabn MA.An irterpubting 4-pirtery siry wbdivinn ahare.Corrpulr Aidd g1Dn线，Giepory JA,chmD.A山s6cdn6 m bitary sabeybiee shweme fue curve de.Conrueave Apprusis, 1991.0227-147 lyn Levis D,Micthelli CA Ueng panneler to ien:amataren of carv and uf grerad by subdivicmn. Dyn N。Analyas ef+e过xrxe ard smoodheis与e fermaltime of Laarert polyaortiab.In bke A,Qu域E,Floeler M5.Gds -Veil.3002.5-6 Kamasi L Chofyns triforn urisaral:acfiaenenl xcheres und prediclins their bctaviue.Ludgon NA,Fouler M5,Saben MA.oda Poe of the MINGLE 2006.123-134 [12]Ierisinicas IP.Dodgsen NA,Hoson MF.Sait MA.On the gounerry of recursiv:subdisision.l'l Joutal of Shue Modelng. 2002511123-42 置章进(1D一1.男.发北天门人特十生， 主翼娇究板填为计单明销财儿匀位计，计 草机田B学

黄章进:单变量均匀静态细分格式的连续性分析和构造 567 [3] Dyn N, Gregory JA, Levin D. A 4-point interpolatory subdivision scheme for curve design. Computer Aided Geometric Design, 1987,4(4):257−268. [4] Deslauriers G, Debuc S. Symmetric iterative interpolation processes. Constructive Approximation, 1989,5(1):49−68. [5] Kobbelt L. 3 -Subdivision. In: Proc. of the SIGGRAPH 2000. New York: ACM Press, 2000. 103−112. [6] Hassan MF, Dodgson NA. Ternary and three-point univariate subdivision schemes. In: Cohen A, Merrien JL, Schumaker LL, eds. Curve and Surface Fitting: Saint-Malo 2002. Brentwood: Nashboro Press, 2003. 199−208. [7] Hassan MF, Ivrissimitzis IP, Sabin MA. An interpolating 4-point C2 ternary stationary subdivision scheme. Computer Aided Geometric Design, 2002,19(1):1−18. [8] Dyn N, Gregory JA, Levin D. Analysis of uniform binary subdivision scheme for curve design. Constructive Approximation, 1991,7(2):127−147. [9] Dyn N, Levin D, Micchelli CA. Using parameters to increase smoothness of curves and surfaces generated by subdivision. Computer Aided Geometric Design, 1990,7(2):129−140. [10] Dyn N. Analysis of convergence and smoothness by the formalism of Laurent polynomials. In: Iske A, Quak E, Floater MS, eds. Tutorials on Multiresolution in Geometric Modelling. New York: Springer-Verlag, 2002. 51−64. [11] Romani L. Classifying uniform univariate refinement schemes and predicting their behaviour. In: Dodgson NA, Floater MS, Sabin MA, eds. Proc. of the MINGLE 2003. 123−134. [12] Ivrissimitzis IP, Dodgson NA, Hassan MF, Sabin MA. On the geometry of recursive subdivision. Int’l Journal of Shape Modeling, 2002,8(1):23−42. 黄章进(1980－),男,湖北天门人,博士生, 主要研究领域为计算机辅助几何设计,计 算机图形学