中国科学技术大学：单变量均匀静态细分格式的连续性分析和构造 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,∀i<0),令 w(>1)是最小的整数,使得 =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 的正 实根