（计算数学专业论文）样条曲线升阶降阶方法中某些问题的研究.pdf

摘要 摘要 b 样条曲线的节点插入、节点消去、升阶、降阶是b 样条方法的最基本和最重要 技术 本文从讨论曲线曲面的节点插入问题入手，给出了节点插入的通用公式和递推舞 表示，应用m o o s e p e n r o s e 广义逆理论，进一步考虑并导出了节点消去的递推矩阵表 在此基础上，使用端点插入法，结合经典的p i e g l & t i l l e r 的b 样条曲线的升阶降阶算 给出了改进的p i e g l & t i l l e r 的b 样条曲线的升阶降阶算法。为非端点插值的b 样条瞄 的升阶降阶提供了一种方法克服了以往的算法只能处理端点插值的b 样条曲线的于| 降阶问题 关键词：b 样条曲线，b 6 z ie r 曲线升阶，降阶端点插值节点插入，节点消去 推矩阵表示 大连理工大学硕士学位论文 a b s t r a c t k n o t i n s e r t i o n ，k n o tr e m o v a l ，d e g r e ee l e v a t i o na n dd e g r e er e d u c t i o no f b s p l i n e c u r v e sa r ei m p o r t a n t t e c h n i q u e i nc a g d w e b e g i nw i t hk n o ti n s e r t i o n ，ak i n do fn e wm e t h o d so fk n o ti n s e r t i o n ( i n c l u d ee n d p o i n l i n t e r p o l a t i n g ) h a sb e e ne s t a b l i s h e d w i t hm o o s e p e n r o s et h e o r y ，w ee s t a b l i s haf o r m u l ao f k n o t r e m o v a l t h e nu s i n ge n d p o i n ti n t e r p o l a t i o n ，w ed i s c u s sp i e g l & t i l l e r a l g o r i t h ma b o u td e g r e e e l e v a t i o na n dd e g r e er e d u c t i o no f b s p l i n e t h ei m p r o v e dp i e g l & t i l l e ra l g o r i t h mc a l lb eu s e d t oa l lu n i f o r i l la n dn o n u n i f o r i l lc u r v e s k e yw o r d s ：b - s p li r ec u r v e ：b 6 z i e rc u r v e ：d e g r e ee i e v a t i o f f ：d e g r e er e d u c t i o n e n d p o i n ti n t e r p o ia t i o n ：k n o t in s e r t i 0 1 1 ：k n o tr e m o v a i i i 第一章绪论 第一章绪论 1 1 n u r b s 曲线曲面发展的历史 作为c a d 系统的国际工业标准之一，n u r b s 曲线曲面在计算机辅助几何设计 ( c a g d ) ，计算机图形学( c g ) 和几何造型( g m ) 等应用领域中具有非常重要的作用 c a d ( c o m p u t e ra i d e dd e s i g n ) c a m ( c o m p u t e ra i d e dm a n u f a c t u r e ) 技术起源子航空工 业由于飞机的外形中含有大量的曲线曲面，c a d c a m 技术从一开始就与曲线曲面造 型技术紧密的联系在一起 自由型曲线曲面因不能由画法几何与机械制图表达清楚，成为摆在工程师面前的首 要问题1 9 6 3 年，美国波音飞机公司的f e r g u s o n 首先提出了将曲线曲面表示为参数的矢 函数方法，最早引入了参数三次曲线，构造了组合曲线和由四角点的位置矢量及两个方 向的切矢定义的f e r g u s o n 双三次曲面片b 6 n e r 在1 9 6 2 年设计了以逼近为基础的曲线曲 面造型系统u n i s u r f ，其核心思想是用控制网格定义曲线曲面的b 6 z i e r 方法b 6 z i e r 方 法简单易用，又漂亮地解决了整体形状控制问题，在c a g e ) 学科中占有重要的地位但 b 6 z i e r 方法仍具有连接问题，还有个局部修改问题随后，f o r r e s t l 2 ”，g o r d o n 和r j e s e n f e l d 等对b 6 z i e r 方法做了深入研究。揭示了b d z i e r 方法与b e m s t e i n 多项式之间的联系，从而 使其具有更坚实的理论基础。1 9 8 3 年，f a r i n 更进一步研究了能统一表示圆锥曲线与自由 曲线的有理b 6 z i e r 曲线 b 样条( b s p l i n e ) 的概念最初是由s c h o e n b e r g 口8 1 于1 9 4 6 年首先提出来的由于具有 局部性及连续阶可调性，b 样条曲线曲面逐步成为几何造型的核心技术1 9 7 2 年，d e b o o r 与c o x 分别独立地给出了关于b 样条计算的标准算法但作为在c a g d 中的个形状 数学描述的基本方法是由g o r d o n 和r i e s e n f e l d 在研究b 6 五e r 方法的基础上引入的它 几乎继承了b 6 z i e r 方法的一切优点，克服了b d z i e r 方法存在的缺点，较成功地解决了局 部控制问题，又轻而易举地在参数连续性基础上解决了连接问题1 9 7 5 年v e r s p r i l l e 在他 的博士论文中首先提出了有理b 样条方法在8 0 年代初期。l a n e 和c o h e n 提出了离散 b 样条和分割技术与控制多边形和节点相联系，1 9 8 0 年b o e h m l l 8 ，1 9 ，2 0 1 和c o h e n 等人分 大连理工大学硕士学位论文 别给出了b 样条益线的节点插入算法，w t i l l e r 4 0 1 论述了有理b 样条曲线曲面的具体应 用此后，l p i e g l 和w t i l l e r 3 4 , 3 4 , 3 5 更深入地研究了有理b 样条曲线曲面的构造和形状 调整问题，并系统论述了n u r b s ( n o n - u n i f o r m r a i o n a l b s p l i n e ) 方法 b 样条方法在表示与设计自由型曲线曲面形状时显示了强大的威力，然而在表示与 设计由二次曲面与平面构成的初等曲面时却遇到了麻烦( b 样条曲线和b e z i e r 曲线不能 精确表示除抛物线外的二次曲线弧，也不能精确表示除抛物线外的二次曲面，而只能给 出近似的表示) 1 9 6 8 年f o r r e s t 首先给出了表达为有理b 6 z i e r 形式的圆锥截线，直到8 0 年代后期，n u r b s 方法成为用于曲线曲面描述的最广为流行的技术非有理与有理 b d z i e r 和非有理b 样条瞌线曲面都被统一在n u r b s 标准形式之中由于n u r b s 方法 可以用统一的方式表示由一次，二次瞌线益面和其它自由曲线曲面复合成的复杂曲线曲 面，所以它在外形设计方面具有强大的功能与潜力n u r b s 方法的引入大大增强了 c a d c a m 系统的瞎面造型功能，因而得到了广泛的应用1 9 9 1 年国际标准组织( i s o ) 正式颁布了工业几何定义的s t e p 标准，作为产品数据交换的国际标准，在s t e p 标准 中，自由型曲线曲面唯一地用n u r b s 表示，n u r b s 方法在c a d c 朋与计算机图形学 领域获得越来越广泛的应用 1 2 升阶降阶研究的重要性 作为b d z i e r 曲线陆面和n u r b s 曲线曲面的两种基本运算，升阶和降阶方法具有非 常重要的意义其重要性主要体现在： 由于最高阶数不同的造型系统之间经常需要进行数据交换，而不同系统中的曲 线曲面的最高阶数可能不同，需要通过升阶降阶使它们之间可以进行相互交换 数据 升阶降阶是构造蒙皮曲面和组合曲面的重要工具因为相邻曲面截面线的阶数 一般是不同的，在曲面设计的预处理过程中，经常需要通过升阶降阶使之阶数 一致 由于节约了存储空间，降阶对于数据压缩也具有很重要的作用例如，对离散点 数据进行逼近拟和时，往往会产生高阶的曲线或曲面表示几何造型中，曲面片 求交产生的交线及裁剪边界曲线也会产生高次的曲线表示，这些都导致了大量 第一章绪论 几何数据信息的存储为了尽量减少信息数据的存储量，就需要对高次的曲线 曲面进行降阶处理 升阶公式是理论推导的必要工具 降阶也经常用于曲线的光顺处理过程中 虽然目前b 6 z i e r 曲线曲面的升阶降阶方法已有较为成熟的理论和算法，然而作为更 重要的参数曲线曲面，由于涉及到复杂的节点处理，n u r b s 曲线曲面的升阶降阶理论的 有效的工作还很少在第二章中我们对现有的曲线曲面的升阶降阶方法做了系统的综 述，所有这些已有的升阶降阶算法都有一定的不足，这些不足主要表现在三个方面： 每次只能升降阶一阶，若要升降多阶，必须多次执行程序来实现，不但繁琐费 时，而且容易产生累积误差 绝大多数b 样条曲线曲面的升阶降阶算法都对节点的形式有严格的限制，如只 能处理节点矢量为端点插值形式的，或者只能处理均匀b 样条曲线曲面这都 极大地限制了算法的应用范围 多数算法在进行升阶降阶时都对原有的节点做了较大的改动，这给算法的实现 带来了一定程度的困难 由此可见，曲线曲面的节点处理，升阶和降阶的理论研究仍然是个重要的课题， 有着重要的意义 1 3 论文的结构安排 鉴于升阶降阶算法在计算机辅助设计中的重要性以及目前n u r b s 造型系统对升阶 降阶算法要求的迫切性，本文就此开展了专门的研究 首先，本文简单的介绍了n u r b s 曲线曲面发展的历史，分析了曲线曲面升阶降阶 的重要性及存在的闯题， 接着，在第二章中详细论述了已有的b d z i e r 曲线曲面和b 样条曲线曲面的升阶降阶 方法，并具体分析了各种方法的应用领域及其不足之处 在第三章中，从讨论曲线曲面的节点插入问题入手，给出了节点插入的通用算法和 递推矩阵表示，结合m o o s e p e m o s e 广义逆理论，进一步考虑并导出了节点消去的递推 矩阵表示 大连理工大学硕士学位论文 本文的第四章在第三章相应结果的基础上，使用端点插入法，给出了改进的p i e g l t i l l e r 的b 样条曲线的升阶降阶算法，克服了以往很多算法只能处理端点插值的b 样条 曲线的升阶降阶问题，为非端点插值的b 样条曲线的升阶降阶提供了一种方法 最后，本文的主要工作的总结与展望 4 第二章曲线曲面升降阶的研究成果综述 第二章曲线曲面升降阶的研究成果综述 2 1 b 岳z i e r 曲线的升阶方法 保持b d z i e r 曲线的形状与定向不变，增加定义它的控制顶点数，怎样扶它的老控制 顶点求出新控制顶点，就是b 6 z i e r 曲线的升阶问题 b 6 z i e r 曲线是参数多项式曲线段，具有整体性质在某些情况下，有可能无论怎样 移动调整顶点都不能得到理想的曲线形状如一个b d z i e r 二边形定义的一条二次b 6 z i e r 曲线，无论怎样调整顶点都不可能使曲线产生拐点显然曲线的“刚性”有余，“柔性”不 足升阶可以降低其“刚性”，增加“柔性”增加控制顶点，就增加了对曲线进行形状控制 的潜在灵活性 b g z i e r 曲线的升阶是由f o r r e s t 2 8 l ( 1 9 7 2 年) 首先提出的，目前已有较为成熟的理论和 算法1 9 7 2 年，b 6 z i e r 提出了b 6 z i e r 曲线的升阶算法虽然他的方法可以增加相应的顶点 达到升阶的耳的，但是算法的复杂性限制了其实际应用更为广泛应用的b 6 z i e r 曲线升 阶算法是基于b e m s t e i n 基函数的升阶方法，也就是： 对于埠次b 6 z i e r 曲线，可以表示成与之等价的n + 1 次b 6 z i e r 曲线： + l 6 i 骂，。o ) = 彰1 皇，。o ) ( 2 1 ，1 ) i-o扫0 为了确定群”，可以在( 2 1 1 ) 式左端乘h 0 + f ) ，比较相应多项式的系数，得 醪= 点( f 6 i 1 + ( ，l f + 1 ) 岛) ，i = 0 ，1 ，n + l ( 2 1 ，2 ) 其中，b i = b 。= 0 ( 2 1 2 ) 式具有很强的几何意义：拼1 ) 以比例g + 1 一班f 分6 。岛，即新顶点是由以参 数值f 0 + 1 ) 按分段线性插值从老控制多边形 导出的，由此得出，于 阶实际上就是对于 控制多边形的割角，新控制多边形是在老控制多边形的凸包内，新控制多边形比老控制 多边形更靠近曲线需要注意的是，割角时在每条途上所取内分点的比例是不一样的 对于b 6 z i e r 曲线的升阶可以无止境地进行下去，从而得到一个控制多边形序列，它 们都定义同一条b d z i e r 曲线这个多边形序列将收敛到一个极限，就是所定义的该 s 大连理工大学硕士学位论文 b d z i e r 曲线，且收敛阶为一阶 类似的，可以把n 次b d z i e r 曲线表示成n + r 次b 6 z i e r 曲线： 6 b 。( f ) = b i , n + r o ) ( 2 1 3 ) f o oi = 0 在( 2 1 3 ) 式左端乘b 。o ) = 1 ，并比较多项式的系数，得 妒= b j ， i = 0 , 1 ，聆+ r ( 2 - 1 4 ) 进入8 0 年代，f a r i n 2 6 ，2 7 ，蝴，p i e g l a 3 ，3 4 ，3 5 1 等人又对有理b d z i e r 曲线曲面的升阶方法做 了比较详尽的研究到目前为止，b 6 z i e r 曲线曲面的升阶理论已经比较成熟了 2 2 b 6 z i o f 曲线的降阶方法 参数曲线曲面的降阶最开始是以升阶的反问题提出的也是f o r r e s t l 2 8 1 ( 1 9 7 2 年) 首先 提出b d z i e r 曲线的降阶问题后来，w a t k i n s 和w o r s e y 通过c h e b y s h e v 多项式给出了 b d z i e r 曲线的最佳逼近降阶方法 一般地，准确的降阶是不可能的，如具有拐点的三次b z i e r 曲线不可能表示成二次 的因此，降阶仅能被看作一条曲线被较低次的曲线逼近的方法与升阶算法相比， b 6 z i e r 曲线曲面降阶方法的研究因出发点的不同产生了更加丰富的分支，其中包括 b 6 z i e r 曲线降阶，b 6 z i e r 曲面降阶，三角b 6 z i e r 曲面降阶，区间b d z i e r 曲线降阶，b a l l 曲 线降阶和有理曲线的降阶等等f o r r c s t ，d a r m e b e r g ，f a r i n ，p i e g l ，h o s c h e k ，w a t l d n s & w o r s e y ，l a c h a n c e ，e e k , b o g a c k i ，b r u n n e t t 等都对该课题作了分析，各自取得了不同方面 的研究进展 b 6 z i e r 曲线的降阶方法基本可以分为两大类，即： 2 2 1 基于控制顶点逼近的几何方法 1 9 7 2 年，f o r r e s t 2 即利用升阶与降阶之间的内在联系，取降阶曲线的控制顶点为 6 第二章曲线曲面升降阶的研究成果综述 只= p 7 ，0 i f 1 2 1 一l ； # = 甲，l n i 2 1 + l _ i k 时，u j “= u - 以次倍= 1 ) 为例说明节点，毡，心决定的一次b 样条0 。( ”) ，可以表示成为七+ 2 = 3 个二次b 样条的线性组合 o ，1 0 ) = n o 2 0 1 u o ) + l ，2 l u l ) + n 2 ，2 l 【，2 ) ( 2 3 4 ) 将( 2 3 3 ) 式代入原k 次b 样条曲线方程( 2 3 1 ) 1 0 第二章曲线曲面升降阶的研究成果综述 p ( “) = 击委n 西k 荟+ l + 虬小心i ) 因u 。“= u ，上式中只有+ 1 个相异的节点矢量u 。，j = l ，2 ，七+ 1 改写成为k + l 条- k + 1 次b 样条曲线p 。( “) ，j = 1 ，2 ，k + l 的算术平均， 砷，= 击缸甜， 其中。 p j o ) = 彰舢l ( “l u 7 ) ，= 1 州2 一，k + l ( 2 3 5 ) 于是，上式可以 即 ( 2 3 6 ) ( 2 3 7 ) 它的顶点卅，i = o ，1 ，由使老顶点，嘭。，t + 2 ( ) ，- 增加重复度l 得到例如若有 老顶点卅，i = o ，1 ，7 ( 即这里有惕= 7 ) ，它们依次为硪= 磊，卅= 破= 匾，磁= d 2 ，硪= 蟊， 觎= 碰= a 4 ，研= 以即与u 。中的节点是将u 中的自节点“，起前后每隔七个节点的那些 节点增加重复度1 而得相对应它们的顶点数( = h ，+ 1 ) 可能不同节点矢量各不相同， 节点数也可能不同，但其中相异的节点与细化节点矢量u 中的完全相同这| j + i 条k + 1 次b 样条曲线p ，( “) ，j = l ，2 ，k + l 相应由插入节点生成的新控制顶点( 其中包括未改 变的老顶点) a ，i = o 州1 一，月+ 1 ，j = l ，2 ，k + 1 来定义最后我们得到原k 次b 样条曲线 升阶成为七+ 1 次b 样条曲线的未知新顶点 虿2 六善彰扣o ，l ，l ( 2 3 8 ) 1 9 9 1 年，p r a u t z s c h & p i p e r t ”1 在该算法的基础上提出了改进算法，优化了算法结构， 它是原来算法的复杂组织，速度更快从k 次升到k + 1 次，原算法所需的操作数线性地 依赖于节点数，二次地依赖于次数晟改进后成为既线性地依赖于节点数，也线性地依 赖于次数 2 3 2 ( o h e n ，l y c h e s c h u m a k e r 的升阶算法 1 9 8 5 年，c o h e n ，l y e h e 和s c h u m a k e r p 3 】利用8 0 年代发展起来的离散b 样条的概念， 提出了b 样条曲线的递归升阶算法，给出了较容易实现的伪代码算法，它无需调用插入 大连理工大学硕士学位论文 节点的算法 设m 阶b 样条曲线的节点矢量形如 望 y l y 2 + 虬+ 。= ，f l ， 这里，n + m = m i i = 1 升一阶以后的m + l 阶b 样条曲线的节点矢量形如： 码+ l怖+ l 一一 ，。一，、- 一 y i y 2 。_ y ；+ ，+ l = f l ，。，l ，。，吒，吒， 这里”= n + k 一1 那么，可以由原始的b 样条曲线c ( r ) = 只骂，( f ) ( p 为控制顶点， f = 0 基函数) 得到升阶后的b 样条曲线c ( r ) = 。西。+ - ( f ) ， 这里 ( 2 3 9 ) r 2 3 1 0 ) b i 。( 力为b 样条 巧= 去喜w ( n 川，2 ，元 删2 案焉纠卅寒考蜊州m 卜，2 畿岽+ 搿诎肋如 b - f 瓣，瓴t q i l l 2 3 3p ie g il t i1 1 6 t w 的升阶算法 1 9 9 4 年，p i e g ll 和t i l l e rw 3 4 】给出了一种基于b 6 z i e r 曲线升阶的b 样条升阶方法， 考虑了端点插值的b 样条曲线升阶问题此算法最大的优点是可以实现b 样条曲线的一 第= 章曲线曲面升降阶的研究成果综述 次性升多阶 假定节点矢量具有以下形式： 型! 鉴! 、 u = u o ，一，z f 。) = a ，口，a ，u m “，u p - m - i b ，b ，b ， 的m 阶b 样条曲线为 c ( r ) = 曰置。( f ) ( 2 3 1 2 ) p i e g l l t ii | e l w 升阶算法： 第1 步将b 样条曲线分割为b d z i e r 曲线段 曲线的分割可以借助节点插值来完成，一个节点( 内节点) 插入r 次的算法公式为： f 只，= ，置，+ ( 1 一，) 最1 ，1 ， 1 q ，：! _ = l ，k m + ，f 七一j ， ( 2 3 1 3 ) i u i + m “一砷 这里，u k “ 清华大学的秦开怀和雍俊海5 l 等分别就端点插值和均匀节点两种情况各自独立 地在2 0 0 0 年的计算机学报上著文，分别提出了一种b 样条曲线的降阶方法文中首先给 出了b 样条曲线退化的充要条件，证明了满足退化形式的k 阶b 样条曲线可以表示为k 一1 阶b 样条曲线，并给出相应的表示方法在此基础上，利用约束优化方法，对b 样条 曲线的控制顶点进行扰动，扰动后的曲线恰好满足退化条件，从而提出一种b 样条曲线 的降阶方法2 0 0 1 年，雍俊海，胡事民【4 3 1 等又在c a g d 上著文，用类似的方法对端点插 值的情况进行了讨论 2 5 小结 本章对国内外曲线曲面升阶降阶的研究成果作了综述对常见的b 6 z i e r 曲线曲面和 b 样条曲线曲面的升阶和降阶方法做了较为系统的综述，对相应算法的优缺点进行了分 析，并对不同算法之间的内在联系做了说明 2 0 第三章非端点插值b 样条曲线的节点插入的讨论 第三章非端点插值8 样条曲线的节点插入的讨论 插入节点算法是b 样条方法配套技术最重要的技术之一，它在理论和曲线曲面设计 中都有着广泛的用途，通过插入节点： ( 1 ) 能简单地证明b 样条曲线的变差减少性质； ( 2 ) 可以改善b 样条曲线的局部性质，灵活的控制b 样条曲线形状； ( 3 ) 可以求出b 样条曲线上的点； ( 4 ) 可以得到b 样条曲线的分段b 6 z i e r 表示； ( 5 ) 可以实现对曲线的分割； ( 6 ) 在生成曲面时，可以使不相同的节点矢量统一起来；等等 节点插入的同时也引入了冗余数据，与之相反的问题是节点消去的问题通过节点 消去可以减少冗余的数据。也可以用于曲线的光顺问题精确的节点消去是节点插入的 逆过程，这里所说的精确的含义是指在节点消去或降阶后，b 样条曲线的形状保持不变， 由于去除节点通常会改变原有样条曲线的形状，因而节点去除问题大都归结为一个逼近 问题节点消去在样条曲线的升阶降阶( 如p i e g l & t i l l e r 的基于b 6 z i e r 曲线升阶降阶的 升降阶方法) 中也有着广泛的应用 3 1 节点插入 记一条分段连续的七阶( k 一1 次) b 样条曲线为 c ( f ) = _ b 卅( f ) ( 3 1 1 ) ，_ o 其中，是控制顶点，日 ( r ) 是归一化的b 样条基函数，其节点矢量为 t = t o ，t t ，- 一，t k 1 ，t k ，o i ，+ ) ，+ l ，i = o ，1 ，n + 七一1 当我们在曲线定义域的某个节点区间插入节点f t k - l , t 。 ，而该节点在原节点矢 量r 中又可能已经具有重复度r ( 这里，若t l f 0 。，则，= 0 ；若0 r 七，则 f = = t i i 一- = 1 ) ，满足，+ 1 _ j ，得到新的节点矢量为 2 l 大连理工大学硕士学位论文 t = t 0 ，f ，。，。 重新编号后成为 t = ( ，0 ，。，t t ：，+ 。) 这个新的节点矢量r 决定了一组新的b 样条基b ：。( f ) ，= o ，l ，n + 1 原来的b 样条基 与未知的新顶点，j = o ，l ，h + 1 表示 c o ) = 巧彰。；( f ) ( 3 1 2 ) 1 = 0 控制顶点增加了一个，曲线形状及连续性都保持不变， 1 9 8 0 年，b o e h mw 【1 8 ，1 吼2 町给出了未知新顶点的计算公式： = 一，j = o ，l ，f k 吁= ( 1 一哆) 巧一t + q 巧，j = i - k + l ，i 一， ( 3 i 3 ) = 一】，j = i r + 1 ，n + 1 其中，口，：二i 。t i t t j 这个算法实际上是德布尔算法求k 次b 样条曲线上一点p ( 0 ，f 【t i , + l 】c t k ，k 。】的 第一级递推b o e h mw 还将一单个节点的算法推广用来插入一个重节点重复插入同一 个节点，次的算法实际上是执行求b 样条曲线一点的德布尔算法的，级递推 i 巧， 归0 巧= ( 1 - 蟛。) 哺1 + 1 巧，j = l ，2 ， 1 1 ， ，= f k + s ，i 一，( 3 1 4 ) 一t 。 口= 。一 。 0 + t + - 一。一0 c o h e n ，l y c h e 和r i e s e n f e l d ( 1 9 8 0 年) 也提出了同时插入多个节点的o s l o 算法它要 用到离散b 样条的理论b o e h m 通过比较指出，o s l o 算法是二维的三角方案，而b o e h m 算法则是一维的线性方案因此b o e h m 算法有着比o s l o 算法更高的效率，丽且b o e h m 算法远比o s l o 算法简单，几何直观，易于为工程实际所接受 b o e h m 算法和o s l o 算法都只适用于在曲线定义域内部插入节点( 即插入”内节点”) ， 因此，只能解决端点插值b 样条曲线的节点插入问题而对于其它的非均匀b 样条曲线 和均匀b 样条曲线，若在节点矢量两端的后任是阶数) 个节点之间插入节点( 即插入”边界 节点”) ，则会出现错误在实际造型过程中，有时候既要插入”内节点”，又要插入”边界 第三章非端点插值b 样条曲线的节点插入的讨论 节点”，如p r a u t z s c h 升阶算法需要通过插入节点的办法，使曲线所有节点( 包含”边界节 点”和”内节点”) 的重复度都提高1 重 秦开怀【9 l 等人根据k 阶差商与b 样条基函数的关系，讨论了节点插入的问题，也给 出了类似的结论根据k 阶差商与b 样条基函数的关系，知 b j t ( f ) = 弓+ 1 1 ( r ) ， 瓦专b m 吐 壶钆m 考暑石专+ 誊百， 眦，+ 考杀， t t j t j t t j 1 t j “蔓，0 + 女一l ( 3 i 5 ) 0 + t i t 0 + t 0 + t 其中，是要被插入的节点，于是插入节点f 之后的节点矢量，b j 。( r ) 是定义在节点 矢量r 上的b 样条基函数，而鸟。( r ) 是定义在节点矢量于上的b 样条基函数 ( 3 1 5 ) 还可统一表示为： b j 。 ( f ) = 瑾，岛，i ( f ) + 岛b j 扎k ( t ) 将( 3 1 5 ) 代入( 3 1 1 ) ，可以按以下三种情况，分别得到计算新的节点矢量和控制顶点 的关系式： 当f n ，+ ，) c ，+ ) 时，于= 岛， ，+ l ，一，f ，。，+ 。) il ， j = o ，1 ，i - k + 1 巧1 = ( 1 一a j ) v j i + q 巧， ，= i - 七+ 2 ，f i 一- l ，= f + l ，l + k 即 巧= 巧，= o ，l ，i - k 。 k m 2 ： 一7 a i k + i 孱m l _ = 巧1 ，= f + l ，n + k 羼一1 口 ( 3 1 3 ) 大连理工大学硕士学位论文 ( 参当f = r 。一。或o ， j j 时，于= 岛，一。，气一。，+ 。，- 一，+ k ) ， _ = 一，= k - i ，k , - - - , 厅 v 0 7 k ： 圪一： 屁0 屈 0 展一2 一1 巧 ： k 一。 当f = t 。或” ，蔓n + 七时，于= 气， ，- ，一l ，& ，0 “，+ 。，+ i _ = 0 ，= o ，1 ，以一k + l 圪m 2 一2 + 3 矿 f 尾m 1 m 2 i 成一2 = l 1 0 其中，由 ；+ l 决定， a i 2 0 c k t + 3 成一。 0，t s 0 等，t t o + i i ， l ，f f 。 一1 0 + t t 一0 。 1 ， f t j m i ( 3 i 4 ) ( 3 1 5 ) 1 1 ，f r 班 篙一一“ 10 ，t f m 递推公式( 3 1 3 ) 考虑的是在内节点处插入节点的情况，新的控制顶点和节点的个 数均比插入节点前多了一个；而公式( 3 1 4 ) ，( 3 1 5 ) 考虑的是在端点处插入节点的情 况，新的控制数和节点的个数均保持不变，且新的节点矢量为 r = 如一l ，t k l ，气，t n ，+ l ，o l ， r 一j 厂一 此时原曲线成为端点插值曲线 在b o e h mw 秦开怀等人的节点插入方法的基础上，我们考虑了重节点插入的通用 + + 咄噶 第三章非端点插值b 样条曲线的节点插入的讨论 算法一般的，当我们在曲线定义域的某个节点区间插入节点f i r k _ ，l 。 1 次，即插入 重节点，而该节点在原节点矢量r 中又可能已经具有重复度，即有 f = r ，= t 一一一f 。满足，+ ，k ，此时可以按以下三种情况，分别得到新的节点矢 量和控制顶点的通用递推公式： 当f r ，+ 1 ) c ( f ，f 。) 时， 哼= 巧，t 。= r f 吁一， j = o ，1 ，i - k + s 巧2 ( 卜嘭。1 ) 嘣+ 嘭。，= f 一七+ s + 1 ，f + j 一1( 3 1 6 ) 1 1 ， _ = f 托，n + 七+ j l = 乇，铲，k 1 ，一，旺，) 当f = t k 一，或o z k 时， 哆= 巧，o = r 吁= 巧，= k 一1 ，七，订 a f 1 群。1 a 一 ，比，一 当f = f 或n ，s n + k 时 哼= 巧，p = 丁 o 是坼s 一- ： 一，乙+ 。) 巧= 哆，= o ，l ，1 ，胛一k + l s - i “6 $ 一- t 1 + 2 一l 雕+ ： 一l l 0 r ”1 = 乇，铲，鹾，一 其中，由 ；+ 。决定， w 。1 巧卜1 ； 嚆1 o 卢= 口：_ 1 ( 3 i 7 ) ( 3 1 8 ) 盯 o k ，。，l ， = 卜、，卧n wj= ，。 肾 ；巧 大连理工大学硕士学位论文 f 0 ， z t j + t l f l ，f