一类多参数的曲线细分格式· 申立勇黄章进 (中料院数学与系统稀究院，数学机城化重点实验室，北意1000) (北意大学信息料学技术学院，北章100刀) (shenly @ams.ac.cn heja graphics.piueducn) 摘要：构进了一是收纹的多参数差分格式，根据加分格式和差分格式的关系以及连候性条件，可得 到任意阶连续的多参数曲线侧分格式。通过选取合适的参数，可以得到一些经典的由线细分格式， Chaikin格式，三次样条细分格或和四点船值格式等。同时设计了一种C连续的不对称三点衡格 式，可以生成不对体的板限曲线。给出了同阶差分格或线性加合的性质，从而可设计出更多收数的 多泰敏的线相分格式。 关帽词：生成多项式：幅分格式：差分格式 中图法分类号：TP391.41TP391.72 0.引言 细分方法是通过对初始控制多边形/控制网格不断雅化生成光滑曲线/曲面的造型方法。由于具 有算法榜单，易于实现和高效性等优点，雅分方法成为计算机图形学，计算机辅册几何设计和工业 造型设计中的一种重要方法。 ki[1】最早在构透由线中引入离散细分由线的概念：提出的用于生成二次B样条的算法。此 后，可从任意拓扑网格生成光滑曲面的Catu1C1k曲面细分格式[2]的提出标志着阐分方法成为曲 线曲由适里的一件万法。自此，新的细分格式和分析理论不斯棱提出和完善[3)】。在单变量细分格式 的分析和构造上，Dyn等人「4,5,6]和aTen[7们给出了二重格式的一些充分条件和必要条件，图ssan 等人[8,9】给出了三重格式的一些充分条件。Ronani[10]和Huang【11】分析了一般的多重格式的连线 性， 在此之前的单变量闻分格式都是没有参数或单参数的，在应用时，单参数缺乏自由度米设计满足 一定性质的格式.我们通过分析形如D风：)=(a:”+a+…+a,:+4,:+1厂，m之1的生成多项 式对应的矩阵D的特征值。得到了一类收敛的多参数差分格式。继而根据州分格式和差分格式的关系 以及C连续性条件，我们可以设计一系列任意阶连续的多参数曲线细分格式。通过选取合适的参数， 我们得到了经典的Chaikin格式[1】，三次样条格式[5)和四点插值格式[4们等。 以往设计细分格式，控制点的权值是对移的。因而基函数和极限由线呈现一定的对称性。通过速 取不对称的参数，我们可以得到不对移的细分格式。特测电，我们给出了一种不对称的C连续的三 点插值格式，生成的极限曲线呈现有趣的不对称性。另外，根据收敛的同阶差分格式的线性组合仍是 收效的差分格式的性质。可以组合设计出更多收敛的多参数曲线细分格式， 1.预备知识 给定初始控制点向量P={:i,Z为整数集，静态翎分格式按如下方式定义一个控制点向 量序列{p:keZ: g=∑ap 这里，有限个元素不为零的系数构成的集合a={a,:iZ)称为幅分格式的掩模。上面的：分过程用 矩阵形式可表示为p广=Sp,矩阵S称为细分矩阵，其元素满足品4=a,∈Z,eZ。定文掩 模a的生成多项式S)-∑，a为细分矩阵（碳细分格式）S的生成多项式 由[5)知，服分格式一数收敛，则其掩慎：必满足 ”基金项日：国家重点基础研究发展规划项日20C19四)。国家自然科学搭金知573引21)：许国吉博士后工作奖 的基金
一类多参数的曲线细分格式∗ 申立勇1 黄章进2 1 (中科院数学与系统研究院，数学机械化重点实验室，北京 100080) 2 (北京大学信息科学技术学院，北京 100871) (shenly@amss.ac.cn hzj@graphics.pku.edu.cn ) 摘 要：构造了一类收敛的多参数差分格式，根据细分格式和差分格式的关系以及连续性条件，可得 到任意阶连续的多参数曲线细分格式。 通过选取合适的参数，可以得到一些经典的曲线细分格式， 如Chaikin格式，三次样条细分格式和四点插值格式等。同时设计了一种 连续的不对称三点插值格 式，可以生成不对称的极限曲线。 给出了同阶差分格式线性组合的性质，从而可设计出更多收敛的 多参数曲线细分格式。 1 C 关键词： 生成多项式；细分格式；差分格式 中图法分类号： TP391.41 TP391.72 0. 引言 细分方法是通过对初始控制多边形/控制网格不断细化生成光滑曲线/曲面的造型方法。 由于具 有算法简单、易于实现和高效性等优点，细分方法成为计算机图形学， 计算机辅助几何设计和工业 造型设计中的一种重要方法。 Chaikin[1]最早在构造曲线中引入离散细分曲线的概念， 提出的用于生成二次B样条的算法。此 后，可从任意拓扑网格生成光滑曲面的Catmull-Clark曲面细分格式[2]的提出标志着细分方法成为曲 线曲面造型的一种方法。自此，新的细分格式和分析理论不断被提出和完善[3]。在单变量细分格式 的分析和构造上，Dyn等人[4,5，6]和Warren[7]给出了二重格式的一些充分条件和必要条件，Hassan 等人[8,9]给出了三重格式的一些充分条件。Romani[10]和Huang[11]分析了一般的多重格式的连续 性。 在此之前的单变量细分格式都是没有参数或单参数的，在应用时，单参数缺乏自由度来设计满足 一定性质的格式。我们通过分析形如 1 1 10 () ( )( 1) 1 n n m D z a z a z az a z m n n − = + ++ + + , − " ≥ 的生成多项 式对应的矩阵 D 的特征值，得到了一类收敛的多参数差分格式。继而根据细分格式和差分格式的关系 以及 连续性条件，我们可以设计一系列任意阶连续的多参数曲线细分格式。通过选取合适的参数， 我们得到了经典的Chaikin格式[1]，三次B样条格式[5]和四点插值格式[4]等。 k C 以往设计细分格式，控制点的权值是对称的，因而基函数和极限曲线呈现一定的对称性。通过选 取不对称的参数，我们可以得到不对称的细分格式。特别地，我们给出了一种不对称的 连续的三 点插值格式，生成的极限曲线呈现有趣的不对称性。另外，根据收敛的同阶差分格式的线性组合仍是 收敛的差分格式的性质，可以组合设计出更多收敛的多参数曲线细分格式。 1 C 1.预备知识 给定初始控制点向量 , 0 0 { } i p p = :∈i Z Z 为整数集，静态细分格式按如下方式定义一个控制点向 量序列{ }： k p : ∈k Z 1 2 k k i ij j Z j p a p + − ∈ = ∑ . 这里，有限个元素不为零的系数构成的集合 = { : ∈ } i a ai Z 称为细分格式的掩模。上面的细分过程用 矩阵形式可表示为 ，矩阵 k+1 p S = k p S 称为细分矩阵，其元素满足 2 j ij i s ai Zj + , = ,∈ , ∈Z 。定义掩 模 的生成多项式 a ( ) 为细分矩阵(或细分格式) i i i S z az = ∑ S 的生成多项式。 由[5]知，细分格式一致收敛，则其掩模a 必满足 ∗ 基金项目：国家重点基础研究发展规划项目(2004CB719403）；国家自然科学基金(60573121）；许国志博士后工作奖 励基金
∑4=∑a=l (10 记4为后差分算子，差分向量平={(y)=以-，：1EZ。考察差分向量的细分过程， 有 △pH=Dp, 这里D为差分格式的细分矩阵，我们称之为差分矩阵。由p州=Sp,则有△Sp=D△p,表示为 生成多项式形式即为1-：5：)P(:2)=D(:1-:2)P(:2) 从而。细分矩阵S和差分炬阵D对应的生成多项式满足 S=)=(1+=)D=1 2) 注意，文[们中采用的前差分算子，只修得到S()=(1+)D上. 对细分格式的收敛性和连续性分析。文[T门给出了下面的定理 定理1，假定阐分格式S的掩模a满足式(1)，D为其差分矩阵，若存在正整数k及实数 0sa<1,使1D≤位，则细分格式S一数收做. 定理2。若生成多嘎式5(：)定义的细分格式S是收数的。那么（三十y广S(:)定义一个C连续的 细分格式。 2.多参数细分格式 由定理2知，从收效的细分格式可以构造任意阶光滑的细分格式。由定理1，要构造收敛的细分格 式S。需要差分矩阵D为收效矩阵。此时称其对应的差分格式是收效的。这样问题就转化为寻找合 适的多项式D(:),使其对应的差分格式D是收效的，燃面S(:)=(1+:)D(:)对应于收敛的闻分格式， 号见D(:)满足如下两个条件： 1,D八：)的☆数项系数与偶数项系数和均为： 2.D:)对应矩阵D的讲半径\D)<1,这果(D)=ma,I入，入是D的特征值。 往意，收致的差分格式不用于致致的细分格式，对收敛的细分格式S,其细分矩阵的请半径S)=1: 根据上面两个条件客易找到一些合适的多项式D:),如： DD八)=(c+b:+),若|akbk1,a+b=},则D风：)对应于收敛的差分格式 1DD)=(a,+a2++42+a+广，m21，若a20且∑a=÷,号验证 曹D<1,而D)的奇数项系数与俱数项系数和为2×之■士，所以这样的D:)对应于收敛 的差分格式， 但这两个应用是丰常有限的，)中的自由度太少，能得判的格式有限：I)是因为所有的风之0， 所以S(:)=D::+)对应的分矩阵行中不金出现负项，这使得上述罪分格式形式设计非常有限， 例如在这种格式中不可能得到经典的周点插值格式[] 对形知D)=(a,:”+a+…+a:+a:+),m≥1的多项式对应的矩阵D的特征值. 我们有如下引理： 引理1.设D。是生成多项式为D(:)=(任+b(:+1厂，m21的矩阵，则D.的特征值为 {a,b,a+b,…,2-(a+b}. 引理2，设D.是生成多项式为D(:)=(压2+加+c(:+1厂，两21的矩阵，则D.的特征值为 ta,b,c,a+b+c,2(a+b+ch4(a+b+c),2(a+b+c). 引理的正明见附录。有了上述引理，我们可以设计一些收敛的多参数差分格式，再利用关系式（②） 和定理2设计任意阶连续的多参数曲线细分格式。 由引理1，我们可以设计收敛的两参数差分格式。 定理3.D()=(c+bX:+1)°，若k1b水1，a+6=÷,m之1，则D(=)生成收效的差分格 式
2 21 1 i i i i a a ∑ = ∑ + = . (1) 记 Δ 为后差分算子，差分向量 1 {( ) } j j jj iii Δ = Δ = − :∈ p p iZ − p p 。考察差分向量的细分过程， 有 j j +1 Δp Dp =Δ, 这里 D 为差分格式的细分矩阵，我们称之为差分矩阵。由 ，则有 j+1 p S = j p j j Δ =Δ Sp Dp ，表示为 生成多项式形式即为 。 2 2 (1 ) ( ) ( ) ( )(1 ) ( ) j j − =− zSzP z Dz z P z 2 从而，细分矩阵 S 和差分矩阵 D 对应的生成多项式满足 Sz zDz ( ) (1 ) ( ) = + . (2) 注意，文[7]中采用的前差分算子，只能得到 Sz zDz z ( ) (1 ) ( ) = + / 。 对细分格式的收敛性和连续性分析，文[7]给出了下面的定理： 定理1. 假定细分格式 S 的掩模 满足式(1)， a D 为其差分矩阵。若存在正整数 及实数 k 0 1 ≤ < α ，使 k || ||≤ D α ，则细分格式 S 一致收敛。 定理2. 若生成多项式 S z( ) 定义的细分格式 S 是收敛的，那么 1 ( )( 2 z k S z) + 定义一个 连续的 细分格式。 k C 2. 多参数细分格式 由定理2知，从收敛的细分格式可以构造任意阶光滑的细分格式。由定理1，要构造收敛的细分格 式 S ，需要差分矩阵 D 为收敛矩阵，此时称其对应的差分格式是收敛的。这样问题就转化为寻找合 适的多项式 ，使其对应的差分格式 D z( ) D 是收敛的，继而 Sz zDz ( ) (1 ) ( ) = + 对应于收敛的细分格式。 易见 满足如下两个条件： D z( ) 1． D z( )的奇数项系数与偶数项系数和均为 1 2 ； 2． D z( )对应矩阵 D 的谱半径 ρ()1 D < ，这里 ( ) max ρ D = i i | λ |，λi 是 D 的特征值。 注意，收敛的差分格式不同于收敛的细分格式，对收敛的细分格式 S ，其细分矩阵的谱半径 ρ() 1 S = 。 根据上面两个条件容易找到一些合适的多项式 ，如： D z( ) I) D z az b z ( ) ( )( 1) =+ + ，若 1 2 | |< ,| |< , + = a b ab 1 1 ，则 对应于收敛的差分格式。 D z( ) II) ， 若 且 1 1 10 () ( )( 1) 1 n n m D z a z a z az a z m n n − = + ++ + + , − " ≥ 0 i a ≥ 1 2 i m i ∑ a = ，易验证 1 1 2 || ||= < D 1，而 的奇数项系数与偶数项系数和为 D z( ) 1 1 2 2 2 m m− 1 × = ，所以这样的 对应于收敛 的差分格式。 D z( ) 但这两个应用是非常有限的。I)中的自由度太少，能得到的格式有限；II)是因为所有的 ， 所以 对应的细分矩阵行中不会出现负项，这使得上述细分格式形式设计非常有限， 例如在这种格式中不可能得到经典的四点插值格式[4]。 0 i a ≥ Sz Dz z ( ) ( )( 1) = + 对形如 ≥ 的多项式对应的矩阵 1 1 10 () ( )( 1) 1 n n m D z a z a z az a z m n n − = + ++ + + , − " D 的特征值， 我们有如下引理： 引理1. 设 Dm 是生成多项式为 ( ) ( )( 1) 1 m D z az b z m = + + ,≥ 的矩阵，则 Dm 的特征值为 。 1 { 2( m aba b a b − ,, +, , + " )} 引理2. 设 Dm 是生成多项式为 2 ( ) ( )( 1) 1 m D z az bz c z m = + + + ,≥ 的矩阵，则 Dm 的特征值为 。 1 { 2( ) 4( ) 2( m abca b c a b c a b c a b c − ,,, + +, + + , + + , , + + " )} 引理的证明见附录。有了上述引理，我们可以设计一些收敛的多参数差分格式，再利用关系式(2) 和定理2设计任意阶连续的多参数曲线细分格式。 由引理1，我们可以设计收敛的两参数差分格式。 定理3. ( ) ( )( 1) ，若 m D z az b z =+ + 1 2 | a b ab m |< ,| |< , + = , ≥ 1 1 m 1，则 生成收敛的差分格 式。 D z( )
证明：由引理1知，D(g)对应的差分矩库D的特征值为{a,ba+b,2(a+b).…,2-(a+b)月所 以p风D)=axiaLlbl.la+b2a+bl,2(a+b)B=mx图allbb克，六，，}0,B>0,a+B=1. 证明：设D,D2对应的生成多项式分别为(a:+么三+GX:+)°.(a:+b:+G(:+1广，则
证明： 由引理1知， D z( )对应的差分矩阵 D 的特征值为 所 以 1 { 2( ) 2 ( m aba b a b a b − ,, +, + , , + " )} 1 1 11 1 2 2 2 ( ) max{ 2( ) 2 ( ) } max{ m m } 1 m ρ a b ab ab ab a b − − D = | |,| |,| + |,| + |, ,| + | = | |,| |, , , , , >, + = 0 0 β αβ 1。 证明： 设 1 2 D , D 对应的生成多项式分别为 ，则 2 2 1 11 2 2 2 ( )( 1)( )( m m az bz c z a z b z c z ++ +, + + +1)
aD+BD生减多项式为(aa+a)F2+(@6+6E+(aC+c)(:+l)”.由引理2的证明过程 可知，aD+BD的特征值为{aa,+Ba,ab+6,ac,+c,(aa,+点+G)+a3+b+c以 …高(a(a+A+G+4+4+4川·g>0,B>0,a+B=1和a,4,G,4,点，G满足的条作可得 出风aD+BD)<1且行和为号，即aD+BD仍为收效的差分格式。证毕. 根据上述性质，可以进一步通过如权组合不同的差分格式而构造更多的多参数曲战细分格式。 3在定理4中收m=2时的厢分格式，取a=c=一，b=和a=b=c=正时的差分格式分别 为D,D,由性质1可知，D=D+D,也是收效的差分格式，它对应一个至少C连续的通近格式： p=P%+g+意P% =-以+p以+号p以一 国中帽介格式 图3中给出了差分格式D,D,和它们的组合格式D=D+D对逆的曲线细分格式作用在同一初始 网格上的结果。 3.结论 本文通过分析形如D风：）=(a:”+a++a:+:+),m之1的生成多项式对应的矩 阵D的特征值形式，并且根据矩阵牧毁和转征值的关系给出了一类收敛的多参数差分格式。继而根据 细分格式和差分格式的关系以及连续性条件，可以设计一系列任意阶连铁的多参数由线细分格式。多 参数格式和以往的单参数格式相比，可以有更多自由度素设计满足特定性质的细分格式，在本文的给 出的差分格式中，我们不仅可以得到一系列新的收数细分格式，而且通过适当选取差分格式的参数可 以得到了一些经典的细分格式。进一步，通过选取不对称的参数。可以得到不对称的细分格式。作为 例子，我们给出了不对称的C连铁的插值格式，生成的极限曲线显现不对称性。增加了细分方法的 造显能力。另外。我们门证明了牧数的同阶差分格式的线性组合仍是牧数的差分格式。根据这个性质， 可以设计出更多收敛的多参数曲线组分格式， 本文根据分析差分矩阵特汇值的莉号形式，从而得到矩阵的收饮性条件与矩库元意的关系，我们 希望推广这种思路，时论更多的差分矩殊特征值形式，设计更多类型的多参要细分格式。对已有的收 敛细分格式，研究参数选取和细分格式性质的关系也是香要做进一步探时的工作。如对于怎样选取参 数使得细分格式的具有保凸性，参数的这取对细分格式连线性的影响等。 4.附录 我们仅以引理2为例给出证明，引理1证明类拟， 引理2的证阴：用归销法，所■1时，可以求得D的特征值是{a,b,G,(a+b+c)片： 现在假定m=k时愿成立，要证m=k+I时也成立。m=k时，生成多境式为 f人e)=(e2+b+c:+=a.a-2+a42++a+a 从而D,的（体+3）×(k+3)阶中心矩降为
α D1 + β D2 生成多项式为 。由引理2的证明过程 可知， 2 1 2 12 12 (( ) ( ) ( ))( 1)m αβ αβ αβ a az b bz c c z + ++ ++ + α D1 + β D2 的特征值为 1 2 1 2 1 2 111 2 2 2 { ( αa a b b c c abc a bc + βα βα β α β , + , + , ++ + ++ ) ( )), 1 1 111 2 2 2 2 ( ( ) ( ))} m α β abc a bc − ", ++ + + + 。α >, >, + = 0 0 β αβ 1 111 2 2 2 和 abca bc , ,, ,, ) 1 满足的条件可得 出 1 2 ρ(α β D D + < 且行和为 1 2 ，即α D1 + β D2 仍为收敛的差分格式。证毕。 根据上述性质，可以进一步通过加权组合不同的差分格式而构造更多的多参数曲线细分格式。 例3 在定理4中取 m = 2 时的细分格式，取 1 1 8 2 ac b = =− , = 和 1 12 abc = = = 时的差分格式分别 为 1, D D2 。由性质1可知， 1 1 D = + 2 2 D D 1 2 也是收敛的差分格式，它对应一个至少 连续的逼近格式： 1 C 1 5 19 5 21 1 48 24 48 1 49 49 1 1 2 1 96 96 96 96 1 1 j j jj i i ii j jj j i i ii p p pp p p pp ⎧ + ⎪⎪ − + ⎨ ⎪ + − 2 j i p ⎪ + ⎩ − + + = ++ = ++ − 图3 组合格式 图3中给出了差分格式 1, D D2 和它们的组合格式 1 1 D = + 2 2 D D 1 2 对应的曲线细分格式作用在同一初始 网格上的结果。 3. 结论 本文通过分析形如 的生成多项式对应的矩 阵 1 1 10 () ( )( 1) 1 n n m D z a z a z az a z m n n − = + ++ + + , − " ≥ D 的特征值形式，并且根据矩阵收敛和特征值的关系给出了一类收敛的多参数差分格式。继而根据 细分格式和差分格式的关系以及连续性条件，可以设计一系列任意阶连续的多参数曲线细分格式。多 参数格式和以往的单参数格式相比，可以有更多自由度来设计满足特定性质的细分格式。在本文的给 出的差分格式中，我们不仅可以得到一系列新的收敛细分格式，而且通过适当选取差分格式的参数可 以得到了一些经典的细分格式。进一步，通过选取不对称的参数，可以得到不对称的细分格式。作为 例子，我们给出了不对称的 连续的插值格式，生成的极限曲线呈现不对称性，增加了细分方法的 造型能力。另外，我们证明了收敛的同阶差分格式的线性组合仍是收敛的差分格式。根据这个性质， 可以设计出更多收敛的多参数曲线细分格式。 1 C 本文根据分析差分矩阵特征值的符号形式，从而得到矩阵的收敛性条件与矩阵元素的关系。我们 希望推广这种思路，讨论更多的差分矩阵特征值形式，设计更多类型的多参数细分格式。对已有的收 敛细分格式，研究参数选取和细分格式性质的关系也是需要做进一步探讨的工作。如对于怎样选取参 数使得细分格式的具有保凸性，参数的选取对细分格式连续性的影响等。 4. 附录 我们仅以引理2为例给出证明，引理1证明类似。 引理2的证明： 用归纳法， m =1时，可以求得 D1的特征值是{ ( abc a b c , ,, + + )}。 现在假定 时命题成立，要证 m k = m k = +1时也成立。 m k = 时，生成多项式为 2 2 1 21 1 ( ) ( )( 1)kk k k k k 0 f z az bz c z a z a z a z a + + = ++ + = + ++ + + + " 从而 Dk 的( 3 k k +×+ )( 3) 阶中心矩阵为
4284-:4m0000 0 a44-3…0000 0 2… 0000 0 000…44马40 0 0 0 0…4%40 0 000…8a马4 D,的特征值就是行列式de(D,一2)的解， 当m=k+1时。生成多现式为厂()"厂(：X:+),对应的差分矩阵为D1·则D的特狂 值就是行列式cD1一)的解，D1一I的（体+4）x(债+4)阶中心矩群为， a-月au+a 8+8a… 0 0 0 0 a2+0-a+a 0 0 0 0 42 4wtg-人… 0 0 0 偷 0 0 0 0 0 0 0 4+4%8-20 0 0 a+属 品+4属-2 我们只要证明D,的特征值都是D:的特任值，且D:还有另一特径值2(a+b+c),则引理得 证。考察矩阵6)，将所有的列加到最后一列，于是新的行列式最后一列元素都为2(a+b+C)一入。 将它作为一个因子提出去，此时矩库的最后一列元素都为1，再从第一行起，用前一行减后一行，直 到最后一行，则矩阵变为 a2=24-a2+2a-4-4 0 0 0 0 %4-244-a4+2… 0 0 0 0 保过 82-入 0 () 0 0 0 4-马-2-8+20 0 0 0 4-444-4-10 0 0 0 d+a 再对矩阵)右乘矩阵 (1111…1111八 0111…1111 0011…1111 :,日 0000…0111 0000…0011 0000:0001 则可得 D-10 于是我们有de域D-2)=d(D-I(2(a+b+c)-)。由归销假设知，D,的特征值为 a,b.c,a++c,2(a+b+ch4a+b+c.,2(a+b+c)月.正毕
2 2 4 1 1 3 2 2 4 2 0 5 3 1 6 420 0000 0 0000 0 0000 0000 0 0000 0 0000 k kk k k k k k k k a aa a a aa a aa aaa aaa aaaa ⎛ ⎞ ⎜ ⎟ + − − + − − + − ⎝ ⎠ " " " # # # # %# # # # " " " Dk 的特征值就是行列式det( ) Dk − λI 的解。 当 m k = +1时，生成多项式为 1 ( ) ( )( 1) k k f z fzz + = + ，对应的差分矩阵为 Dk +1。则 Dk +1的特征 值就是行列式 1 det( ) Dk + − λI 的解， Dk +1 − λI 的( 4) ( 4 k k + × + ) 阶中心矩阵为， 2 1 1 2 2 1 1 2 1 21 0 3 2 1 0 4 3 21 0 0 0 0 0 0 0 00 0 00 0 00 0 k kk k k k k kk k k k a a a aa a a aa a aa aa a a a aa a a aa a λ λ λ λ λ 0 0 0 0 0 0 0 λ + + − − + + − + + ⎛ ⎞ −+ + ⎜ ⎟ +− + + − + − + +− + + − ⎝ ⎠ " " " # # #%# # " " " # (6) 我们只要证明 Dk 的特征值都是 Dk +1的特征值，且 Dk +1还有另一特征值 ，则引理得 证。考察矩阵(6)，将所有的列加到最后一列，于是新的行列式最后一列元素都为 2( ) k abc + + 2( ) k abc ++ − λ 。 将它作为一个因子提出去，此时矩阵的最后一列元素都为1，再从第一行起，用前一行减后一行，直 到最后一行，则矩阵变为 (7) 2 22 1 11 2 2 13 1 2 4 0 2 4 3 2 1 0 0 0 0 0 0 00 0 00 0 00 0 k kk k k k kk k k k a aa a a a aa a aa aa a a a aa a a aa λ λ λ λ λ λ λ λ + +− + −+ + + ⎛ ⎞ − −+ − ⎜ ⎟ − −+ − − − − −+ − −− ⎝ ⎠ + + " " " # # # %# # " " " 0 0 0 0 0 0 0 1 # 再对矩阵(7)右乘矩阵 ( 4) ( 4) 1111 1111 0111 1111 0011 1111 0000 0111 0000 0011 0000 0001 k k + × + ⎛ ⎞ ⎜ ⎟ ⎝ ⎠ " " " # # # #%# # ## " " " 则可得 ( 4) ( 4) 0 * 1 k k k λ + × + ⎛ ⎞ − ⎜ ⎟ ⎝ ⎠ D I 于是我们有 1 det( ) det( )(2 ( ) ) k k k λ λ abc D I DI + − = − ++ − λ 。由归纳假设知， Dk +1的特征值为 { 2( ) 4( ) 2 ( 。证毕。 k abca b c a b c a b c a b c ,,, + +, + + , + + , , + + " )}
参考文献 1]Chaikin G.An algorithm for high speed curve generation []Compuer Graphics&Image Processing 1974.34 346- 349 ]Catmull E ClarkJ.Recursively generad B-spline surfaces on arbitrary opological meshes ]Computer Aided Design. 198.106:50-355 3]Zorin D,Scheoder P.Subdivision for modeling and amimation (Course notes)[C]N Computer Grphics Proceedings, Annuol Conference Senes.ACM SIGGRAPH New Orleans.Loutsana.2000:1-116 4]Dyn N,Levin D.Gireanry J A.A 4-poir inlerpolory subdivision scheme for curve design []Computer Aided Ccomeric Den1987,4h257-268 5]Dym N.Levin D.Micchelli C A.Using poram ]Compuer Aided Geometric Desig,1990.73)129 14 6]Dyn N.Gregory J A.Levin D.Analysi App0w1mu0m,199L,有2)：127-147 7门Waeen人H.Weimner Subdivision method Kaufeann Puls小hes2Ool Hassan M F.Dodgson N A.Ternary and three-point Sait-Malo 2002 Brentwood:Nashboto Press 2003:199 9]Hanssan M F.Ivnissimnitnis I P.Sahin M A.An interpolating 4- Computer Aid时Gcometric Des到L,20021线1：1一18 110 Romani L Clssitying uiform uniariale refinement schemes and predicting their bchaviour[C]Proceedings of MINGLE Workshop 2003.Cambridge.UK.2003:123-134 11]Huang Zhangin.Concnuiy analysis and construction of uifor sttionary uivariate subdivision schemes [Joumal of Software,2006,173)559-567in Chinesel (黄章退。单变量均匀静老挥分格式的连续性分析和构速门。秋作学报。206：1N3h559一67列 A Class of Curve Subdivision Schemes with Several Parameters Liyong Shen'.Zhangjin Huang" (KLMM,Imstitue ofSysems Scienees,AMSS,Beijing 100080,China) (School of Electronics Engincering and Compukr Science.Peking University.Beijing 10871.Chira) Keywords:gencrating polynomial,subdivision scheme,difference scheme Abstract:A class of convergent difference schemes with several parameters is proposed.According to the relationship between the subdivision scheme and its difference scheme and the sufficient condition for C continuity.we can devise curve subdivision schemes with arbitrary order continuity.By setting appropriate parameters,some classical curve subdivision schemes such as the Chaikin's scheme,the cubic B-spline scheme and 4-point interpolating scheme can be obtained.A C-continuous asymmetric 3-point interpolating scheme is also presented to model asymmetric limit curves.Furthermore.the property of the linear combination of the difference schemes of the same order is analyzed,which can help to devise more comvergent curve subdivision schemes with several parameters
参考文献 [1] Chaikin G. An algorithm for high speed curve generation [J]. Computer Graphics & Image Processing, 1974, 3(4)：346－ 349 [2] Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological meshes [J]. Computer Aided Design, 1978, 10(6)：350－355 [3] Zorin D, Schröder P. Subdivision for modeling and animation (Course notes) [C] // Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, Louisiana, 2000：1－116 [4] Dyn N, Levin D, Gregory J A. A 4-point interpolatory subdivision scheme for curve design [J]. Computer Aided Geometric Design, 1987, 4(4)：257－268 [5] Dyn N, Levin D, Micchelli C A. Using parameters to increase smoothness of curves and surfaces generated by subdivision [J]. Computer Aided Geometric Design, 1990, 7(3)：129－140 [6] Dyn N, Gregory J A, Levin D. Analysis of uniform binary subdivision scheme for curve design [J]. Constructive Approximation, 1991, 7(2) ：127－147 [7] Warren J, H. Weimer. Subdivision method for geometric design : a constructive approach [M]. San Francisco：Morgan Kaufmann Publishers, 2001 [8] Hassan M F, Dodgson N A. Ternary and three-point univariate subdivision schemes [C] // Curve and Surface Fitting: Saint-Malo 2002. Brentwood：Nashboro Press, 2003：199－208 [9] Hassan M F, Ivrissimitzis I P, Sabin M A. An interpolating 4-point ternary stationary subdivision scheme [J]. Computer Aided Geometric Design, 2002, 19(1)：1－18 2 C [10] Romani L. Classifying uniform univariate refinement schemes and predicting their behaviour[C] // Proceedings of MINGLE Workshop 2003. Cambridge, UK, 2003：123－134 [11] Huang Zhangjin. Continuity analysis and construction of uniform stationary univariate subdivision schemes [J]. Journal of Software, 2006, 17(3)：559－567(in Chinese) (黄章进。单变量均匀静态细分格式的连续性分析和构造[J]。软件学报，2006，17(3)：559－567) A Class of Curve Subdivision Schemes with Several Parameters Liyong Shen1 , Zhangjin Huang2 1 (KLMM, Institute of Systems Sciences, AMSS, Beijing 100080, China) 2 (School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China) Keywords: generating polynomial; subdivision scheme; difference scheme Abstract: A class of convergent difference schemes with several parameters is proposed. According to the relationship between the subdivision scheme and its difference scheme and the sufficient condition for continuity, we can devise curve subdivision schemes with arbitrary order continuity. By setting appropriate parameters, some classical curve subdivision schemes such as the Chaikin’s scheme, the cubic B-spline scheme and 4-point interpolating scheme can be obtained. A -continuous asymmetric 3-point interpolating scheme is also presented to model asymmetric limit curves. Furthermore, the property of the linear combination of the difference schemes of the same order is analyzed, which can help to devise more convergent curve subdivision schemes with several parameters. k C 1 C