（应用数学专业论文）b样条曲线升阶中差商方法的应用研究.pdf

摘要 b 样条曲线的节点插入和升阶是计算机辅助几何设计( c a g d ) 、计算机图形学( c g ) 中非常重要和最常用的技术曲线升阶是曲面设计和几何造型中的一项重要技术，是 c a g d 系统中的一个基本工具，经常应用于组合曲线、蒙皮曲面或扫掠曲面等几何设计 中论文主要围绕b 样条曲线升阶和节点插入问题，研究工作主要在以下几个方面： 1 b 样条曲线经典的升阶算法共有三种：p r a u t z s c h 升阶算法，c o h e n 升阶算法以及 p i e g i t i l l e r 升阶算法现有的算法大多都是以这三种方法为基础，然后进行改进本文 从讨论曲线曲面的节点插入问题入手，详细讨论了秦开怀节点插入方法 2 在秦开怀节点插入的基础上，使用端点插值法，改进h u a n gq i x i n g 的b 样条曲线 升阶算法，使得节点插入和升阶可以同时进行，达到对b 样条曲线升阶的最终目的，使 之适用于所有均匀和非均匀b 样条曲线 3 论文所给的方法为非端点插值b 样条曲线一次性升多阶提供了一种新途径，克服 了以往的算法只能处理端点插值b 样条曲线的升阶问题。 传统的升阶方法只能处理端点插值b 样条曲线，而本文的方法是一个通用的方法， 可以用于任何曲线的升阶，所以理论意义非常大由于改进后的算法采用的是矩阵运算与 线性运算，所以具有形式简洁、计算简便、编程容易的优点。 关键词：b 样条曲线，升阶。差商，端点插值，节点插入 a b s t r a c t k n o ti n s e r t i o na n dd e g r e ee l e v a t i o no fb s p i i n ec u r v e sa r ev e r yi m p o r t a n ta n dm o s t l y c o m m o nu s e dt e c h n i q u ei nc o m p u t e r - a i d e de n g i n e e r i n g ( c a g d ) a n dc o m p u t e rg r a p h i c s ( c g ) d e g r e ee l e v a t i o no fg u r v ei s s ni m p o r t a n tt e c h n i q u ei ns u r f a c ed e s i g na n dc o m p u t e r a i d e dg e o m e t r i cm o d e l m g i ti saf u n d a m e n t a lt o o l i nc a g d s y s t e m sa n df r e q u e n t l yu s e di n g e o m e t r i cd e s i g no fc o m p o s i t ec u r v e s ，s w e e p i n ga n ds k i n n i n gs u r f a c e s t h i sp a p e rm a i n l y s t u d i e sd e g r e ee l e v a t i o no fb s p l i n ec u r v e sa n dk n o ti n s e r t i o n r e s e a r c hw o r km a i n l yi sg i v e n a sf o l l o w 1 t h e r ea r et h r e et r a d i t i o n a ld e g r e ee l e v a t i o na l g o r i t h m s ，i n c l u d i n gp r a u t z s c ha l g o r i t h m ， c o h e na l g o r r h ma n dp i e g l t i l l e ra l g o r i t h m m o s tp r e s e n ta l g o r i t h m sa r eo nt h eb a s i so f t h e s et h r e em e t h o d s ，t h e nt ob ei m p r o v e d w eb e g i nw i t hk n o ti n s e r t i o n ，a n dt h e nd i s c u s st h e k n o ti n s e r t i o no fq i nk a i h u a ii np a r t i c u l a r 2 t h e nu s i n ge n d p o i n t i n t e r p o l a t i o n ，w ei m p r o v eh u a n go i x i n ga l g o r i t h m f o r s i m u l t a n e o u sd e g r e ee l e v a t i o na n dk n o ti n s 6 r t i o nf o rb - s p l i n ec u r v e s t h ei m p r o v e da l g o r i t h m c a nb eu s e dt oa l lu n i f o r ma n dn o n u n i f o r mb - s p l i n ec u r v e s 3 t h em e t h o dp r o v i d e sad e ww a yf o rn o n - e n d p o i n ti n t e r p o l a t i n gb - s p l i n ec u r v e sw h i l e r a i s i n gt h eo r d e rb ya l la r b i t r a r ym i to v e r c o m e st h ep r o b l e mt h a tp r e v i o u sa l g o r i t h m so n l y c a nh a n d l ee n d p o i n ti n t e r p o l a t i n gb - s p l i n ec u r v e s t r a d i t i o n a ld e g r e ee l e v a t i o nm e t h o do n l yc a nh a n d l ee n d p o i n ti n t e r p o l a t i n gb - s p l i n e c u r v e sa n dt h em e t h o dw h i c hc a nb eu s e di nd e g r e ee l e v a t i o no fa n yc u r v e s ，s u p p l i e db yt h i s p a p e ri sc u r r e n c y a p p l y i n gm a t r i xa n dl i n e a ro p e r a t i o n ，t h ei m p r o v e da l g o r i t h mh a s a d v a n t a g e s ，s u c ha sc o n c i s i o ni nf o r m ，s i m p l ec o m p u t i n g ，e a s yt op r o g r a m k e yw o r d s ：b s p l i n ec a r v e ，d e g r e ee l e v a t i o n ，d i v i d e dd i f f e r e n c e ，e n d p o i n ti n t e r p o l a t i o n ， k n o ti n s e r t i o n i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 研究生签名：蔓秀花 时间： 石一# 年岁月2 驴日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交 论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位 论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名：梭秀彩 时间：刃石年专月2 0 日 导哟糕鼍 时闯：z 纠5 年r 月知日 宁夏大学硕士学位论文 第一章绪论 第一章绪论 1 1b 6 z i e r n u r b s 曲线曲面的发展历史 作为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 i n g ) ，c a e ( c o m p u t e r a i d e d e n g i n e e r i n g ) 系统的国际工业标准之一，n u r b s ( n o n u n i f o r m r a t i o n a l b s p l i n e ) 曲线曲面在计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r yd e s i g n ，简称 c a g d ) 、计算机图形学( c o m p u t e r g r a p h i c s ，简称c g ) 和几何造型( g e o m e t r y m o d e l i n g ， 简称g m ) 等应用领域中具有非常重要的作用，在机械、航空、船舶，汽车、家电制造等 行业均有广泛用途n u r b s 广泛应用于可视艺术如电影、动画、娱乐，艺术、雕塑中的 物体造型，在虚拟现实应用中制作场景等可以预见，n u r b s 将会在越来越广阔的范围 内获得应用 在飞机工厂与造船工厂里，传统上采用模线样板法表示和传递自由型曲线曲面的形 状。模线样板法所表示与传递的形状因人而异，要求设计与制造人员付出繁重的体力劳动， 设计周期长、制造精度低、互换协调性差，不能适应现代航空、汽车等工业的发展。数学 家们试图从数学上寻求模拟由物理样条所形成的曲线，寻求用数学方法唯一地定义自由型 曲线曲面的形状，将形状信息从模拟量传递改变为数值量传递随着计算机的出现，采用 数学方法定义自由型曲线曲面才达到实用的地步，这就是最初的样条曲线 1 9 6 4 年，由s e h o e n b e r g l l i 提出的样条豳数提供了解决连接问题的一种技术用于形 状描述的样条方法是它的参数形式，即参数样条曲线曲面样条方法用于解决插值问题， 构造整体达到某种参数连续阶的插值曲线曲面是狠方便的，但不存在局部形状调整的自由 度，样条曲线曲面的形状难以预测 自由型曲线曲面因不能由癌法几何与机械制图表达清楚，成为摆在工程师面前的首要 向题1 9 6 3 年，美国波音飞机公司的f e r g e s o n 首先提出了将曲线曲面表示为参数的矢函 数方法，最早引入了参数三次曲线，构造了组合曲线和由四角点的位置矢量及两个方向的 切矢定义的f e r g u s o u 双三次曲面片b 6 z i e r 在1 9 7 2 年设计了以逼近为基础的曲线曲面造 型系统u n i s u r f ，其核心思想是用控制网格定义曲线曲面的b 6 z i e r 方法b 6 z i e r 方法简 单易用，又漂亮地解决了整体形状控制问题，在c a g d 学科中占有重要的地位，为c a g d 的进一步发展奠定了坚实的基础但b 6 z i e r 方法仍具有连接问题，还有个局部修改问题 随后，f o r r e s t 2 i ，g o r d o n 和r i e s e n f e l d 等对b 6 z i e r 方法做了深入研究，揭示了b 6 z i e r 方法 与b e m s t e m 多项式之间的联系，从而使其具有更坚实的理论基础1 9 8 3 年，f a r i n p l 更进 一步研究了能统一表示圆锥曲线与自由曲线的有理b 6 z i e r 曲线 b 样条( b s p l i n e ) 的概念最初是由s e h o e n b e r g 1 1 于1 9 6 4 年首先提出来的由于具有局 部性及连续阶可调性，b 样条曲线曲面逐步成为几何造型的核心技术。1 9 7 2 年，d eb o o r 与 c o x 分别独立地给出了关于b 样条计算的标准算法但b 样条曲线曲面作为c a g d 中一 宁夏大学硕士学位论文第一章绪论 个形状数学描述的基本方法，是由美国通用汽车公司的g o r d o n 和r i e s e n f e l d 将b 样条理 论用于形状描述时提出的它几乎继承了b 6 z i e r 方法的一切优点，克服了b 6 z i e r 方法存 在的缺点，较成功地解决了局部控制问题，又轻而易举地在参数连续性基础上解决了连接 问题 与控制多边形和节点相联系，1 9 8 0 年分别由b o e h m 4 , 习和c o h e n 等人给出的节点插 入技术是b 样条方法中最重要的配套技术，其次，有p r a u t z s c h “1 2 l 、c o h e n 1 ”、p i e g l 9 j 等 人的升阶技术在设计自由曲线时往往需要曲线造型的自由度；在生成b 样条组合曲线、 组合曲面，或用蒙皮技术生成b 样条曲面时，要使得不同阶曲线的阶数达到一致，实现 上述操作都要用到( 或可用) b 样条方法中最基本、最重要的技术之一一b 样条曲线的升 阶国内许多学者也一直致力于升阶理论的研究，典型代表是清华大学的秦开怀。从1 9 9 6 年至今。秦开怀在这方面作了大量的工作，将传统的节点插入及升阶理论进行了修改，发 表了大量论著，取得了一系列有效成就 1 9 7 5 年，v e r s p r i l l c 在他的博士论文中首先提出了有理b 样条方法。以后由于p i e 9 1 1 6 、 t i l l e r 刀和f a r i n l 3 等人的功绩，至8 0 年代后期，非均匀有理b 样条( n o n u n i f o r m r a t i o n a lb s p l i n e ，简称n u r b s ) t s 法成为用于曲线曲面描述的最广为流行的技术非有 理与有理b 6 z i e r 和非有理b 样条曲线曲面都被统一在n u r b s 标准形式之中。由于 n u r b s 方法可以用统一的方式表示由一次、二次曲线曲面和其它自由曲线曲面复合成的 复杂曲线曲面，所以它在外形设计方丽具有强大的功能与潜力国际标准化组织 ( i n t e r n a t i o n a l s t a n d a r d i z a t i o n o r g a n i z a t i o n ，简称i s o ) 于1 9 9 1 年颁布了关于工业产品数 据交换的s t e p ( s t a n d a r df o rt h ee x c h a n g eo fp r o d u c tm o d e ld a t a ) 国际标准，把n u r b s 作为定义工业产品几何形状的惟一数学方法1 9 9 2 年n u r b s 又成为规定独立于设备的 交互图形编程的p h i g s ( p r o g r a m m e r s h i e r a r c h i c a l i n t e r a c t i v e g r a p h i c s s y s t e m ) 国际标准 在s t e p 标准中，自由型曲线曲面唯一地用n u r b s 表示，n u r b s 方法在c a d c a m 与 计算机图形学领域获得越来越广泛的应用不难预测，n u r b s 方法将不断取得新的突破， 逐渐进入多学科知识交叉，多种方法取长补短，多个研究领域齐头并举的繁荣发展阶段 1 2 升阶研究的重要性 曲线的升阶就是用更高阶的基函数表示原曲线。作为b 6 z i e r 曲线曲面和n u r b s 曲线 曲面的一种基本运算，升阶方法具有非常重要的意义。其重要性主要体现在： 一、升阶可以增加几何造型的柔性，或者说提高其形状控制的灵活性因为通过升阶， 增加了控制顶点数，从而也就增加了自由度。 二、升阶是表示和设计组合曲线时必不可少的工具和手段。因为两条或多条不同阶次 的b 样条曲线要依次连接成为一条组合b 样条曲线时，必须使用升阶方法 三、升阶是构造蒙皮曲面和扫描曲面的重要工具例如，若截面线的阶次不一致，则 必须通过升阶，使其阶次一致后，才能生成蒙皮曲面。因为相邻曲面截面线的阶数一般是 2 宁夏大学硕士学位记丈第一章绪论 不同的，在曲面设计的顶处理过程中，经常需要通过升阶使之阶数一致。这在表示和生成 蒙皮、扫描曲面时都是非常重要的，也是必不可少的一种技术 四、由于最高阶数不同的几何造型系统之间经常需要进行数据交换，而不同系统中曲 线曲面的最高阶数可能不同，需要通过升阶使它们之间可以相互交换数据 五、升阶公式是理论推导的必要工具 关于b 6 z i e r 曲线曲面的升阶方法，目前已有相对而言较为成熟的理论和算法。早在 1 9 7 2 年。b 6 z i e r 本人就提出过b 6 z i e r 曲线的升阶算法到日前为止，b 6 z i e r 曲线曲面的开 阶已经有较成熟的理论成果了然而作为更重要的参数曲线曲面，由于涉及到复杂的节点 处理，b 样条曲线曲面升阶理论的有效工作还很少在第二章中我们对现有的b 6 z i e r 、 b 样条曲线曲面的升阶方法做了系统的综述，所有这些已有的升阶算法都有一定的不足， 这些不足主要表现在以下三个方面： 一、现有的大多算法每次只能升一阶，若要升多阶，必须多次执行程序来实现，不但 繁琐费时，而且容易产生累积误差 二、绝大多数b 样条曲线曲面的升阶算法都对节点的形式有严格的限制，如经典算 法( 包括p r a u t z s c h 开阶方法，c o h e n 等人的升阶方法，以及p i e g l 等人的升阶方法) 只 能处理节点矢量为端点插值形式的曲线曲面，或者只能处理均匀b 样条曲线曲面。当用 于其它的非端点插值b 样条曲线或非均匀b 样条曲线的升阶时，都将出现错误，不能得 到正确的结果，所以传统的b 样条曲线升阶算法必须修正这都极大地限制了算法的应 用范围 三、多数算法在逃行升阶时都对原有的节点做了较大的改动，这给数据存储和算法实 现带来了一定程度的困难 由此可见，曲线曲面的节点处理、升阶理论的研究仍然是一个重要的课题，对其进行 深入研究有着重要的意义 1 3 论文的结构安排 鉴于升阶算法在计算机辅助几何设计中的重要性以及目前n u r b s 造型系统对升阶 算法要求的迫切性，本文就此开展了专门的研究 首先，在第一章回顾了b 6 z i e r ，n u r b s 曲线曲面的发展历史，分析了曲线曲面升阶 的重要性及存在的问题 接着，在第二章中系统的阐述了现有的b 6 z i e r 曲线曲面和b 样条曲线曲面的升阶方 法，其中重点讨论了b 样条曲线曲面的升阶方法，即p r s u t z s c h 的基于节点插入的升阶方 法，c o h e n 等人的基于离散b 样条的升阶方法，以及集b 样条曲线的分解、b 6 z i e r 曲线 的升阶、b 样条曲线的节点去除运算于一体的p i e g l 等人的升阶方法和秦开怀的矩阵升阶 方法并给出了各种方法的应用领域及其不足之处 在第三章中，从讨论曲线曲面的节点插入问题入手，结合传统的节点插入算法( b o e h m 算法) 和秦开怀节点插入算法，给出了节点插入的通用算法和递推矩阵表示另外，为了 3 宁夏大学硕士学位论文第一章绪论 研究的需要，引进了非均匀b 样条函数的广义差商，给出广义差商的定义及常用性质， 为继续以后的讨论做了必要的准备 本文的第四章在第三章相应结果的基础上，讨论了非端点插值b 样条曲线的升阶问题 首先提出了h u a n gq i x i n gb 样条曲线的升阶算法然后运用端点插入法，结合秦开怀的 节点插入方法，改进了h u a n gq i x i n g 的b 样条曲线升阶算法，克服了以往很多算法只能 处理端点插值b 样条曲线升阶的问题，为非端点插值b 样条曲线的升阶提供了一种方法 另外一个优越性就是节点插入和升阶可以同时进行 最后，总结本文的主要工作，并指出其不足之处，提出以后工作的重点，展望曲线曲 面升阶方法的未来 宁夏大学硕士学位论文 第二章曲线曲面升阶的研究成果综述 第二章曲线曲面升阶的研究成果综述 2 1b 6 z i e r 曲线的升阶方法 保持b 6 z i e r 曲线的形状与定向不变，增加定义它的控制顶点数，怎样从它的老控制 顶点求出新控制顶点，就是b 6 z i e t 曲线的升阶问题。 为什么要升阶? b 6 z i c t 曲线是参数多项式曲线段，具有整体性质。在某些情况下，有 可能无论怎样移动调整顶点都达不到理想的曲线形状例如：一个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 6 z i e r 曲线的升阶是由f o r t e s t t 2 ( 1 9 7 2 年) 首先提出的，目前已有较为成熟的理论和 算法1 9 7 2 年，b 6 z i e r 提出了b e z i e r 曲线的升阶算法虽然他的方法可以增加相应的顶 点达到升阶的目的，但是算法的复杂性限制了其实际应用更为广泛应用的b 6 z i e r 曲线 升阶算法是基于b o r n s t e i n 基函数的升阶方法，也就是： 对于给定控制顶点6 0 ，6 1 ，加的t 次b 6 z i e r 曲线，可以表示成与之等价的尼+ 1 次b 6 z i e t 曲线( 新控制顶点为b o a ) ，6 l ，籼) l 毫掘以) 一矿a + 1 o _ 柚+ l ( f ) ， ， 0 ，1 】 ( 2 ，1 1 ) 为了确定h o ，可以在( 2 1 1 ) 式左端乘“- 0 - t ) ，并比较相应多项式的系数，得 b 0 ) m 阼l _ , - l + - b l _ i i 0 1一南1 渺) i 咀，l + 1阼+订+ 其中b 一1 一如+ 1 0 ( 2 1 2 ) 也可以由b e r n s t e i n 基函数的升阶公式直接推出： 风砸) 一( 1 一击够一，m 等n & “一o )n + 上+ l 显然( 2 1 2 1 式具有很强的几何意义，b l o ) 以比例伽+ 1 - o ：i 分i i - 5 ( 2 1 2 ) ( 2 1 3 ) 即新顶点是 宁夏大学硕士学位论文 第二章曲线曲面升阶的研究成果综述 由以参数值f ：o + 1 ) 按分段线性插值从老控制多边形得出的。由此得出升阶实际上就是 对控制多边形割角，新控制多边形是在老控制多边形的凸包内，新控制多边形比老控制多 边更靠近曲线；多了一个控制顶点，也增加了调整曲线形状的柔韧性，这是其两个优点 但需注意，割角时在每条边上所取内分点的比倒是不一样的 对于b 6 z i e r 曲线的升阶可以无止境地进行下去，从而得到一个控制多边形序列，它 们都定义同条b 6 z i e r 曲线。这个多边形序列将收敛到一个极限，就是所定义的该b 6 z i e r 曲线，且收敛阶为一阶 升阶在构造曲面方面有着重要的作用对于些由曲曲线生成曲面的算法，要求那些 曲线必须是同次的应用升阶方法，我们可以把所有这些曲线中低于最高次数者都提升到 最高次数，丽获得统一的次数 类似的，可以把 次b 6 z i c r 曲线表示成甩+ ，次b 6 z i e r 曲线： 善6 圆 ， o ) 4 磊6 ，曰r ， + r ( f ) 在( 2 1 3 ) 式左端乘善既以) _ 1 并比较多项式的系数，得 b j ( 7 ) 。x 角 f 一0 ，n + r ( 2 1 4 ) ( 2 1 5 ) 如图2 2 1 给出一个例子，是一条三次b 6 z i e r 曲线升一阶的曲线( 实线为老控制多变 形，虚线为新控制多变形) 圉2 1 1b t z i e r 雌线从三次升到四次 宁夏大学硕士学位论文 第二章曲线曲面升阶的研究成果综述 进入8 0 年代，f a r i n t ”，p i e g l l 6 a , 9 1 等人叉对有理b 6 z i e r 曲线曲面的升阶方法做了比较 详尽的研究到目前为止，b 6 z i e r 曲线曲面的升阶理论已经比较成熟了 2 2b 样条曲线的升阶方法 b 样条曲线的次数提升或通常称之为升阶，是b 样条方法配套技术中最重要的技术之 一1 1 ”b 样条曲线的升阶也可以增加曲线的柔性，或者说可以提高其形状控制的潜在灵 活性因为通过升阶，增加了控制顶点数，也就增加了自由度。通过插入节点的分割过程， 可以精确地在某个区域增加形状控制的灵活度但是一旦移动对应于插入节点后生成的新 控制顶点，样条曲线在插入节点处的连续性将遭受损失如果所插节点在老节点矢量里已 有重复度r ，又同时插入f 次，则t 次b 样条曲线在该处的参数连续性将从c ”连续 降为c ”o 连续如采用升阶方法。则不论怎样移动升阶后生成的新控制顶点，样条曲 线的参数连续性将保持不变。 b 样条升阶的主要意义不仅在于此，还在于曲线曲面的表示和设计的需要b 样条曲 线的升阶是表示与设计组合曲线时必不可少的手段之一两条或者若干条不同次的b 样 条曲线要顺次连接成为一条组合b 样条曲线，用一个统一的方程表示，必须使它们的次 数统一起来，才有可能实现这样的连接就像组合b z i e r 曲线那样，其中各b 6 z i e r 曲线 段都应有统一的次数b 样条曲线的升阶在生成曲面时，在表示与设计组合曲面时同样 有重要的用途 ， 设尼+ 1 个控制顶点庙，f o ，1 ，抖定义的一条七次b 样条曲线： 其中，k 次b 样条基函数由节点矢量u - l h o ，u t , ，i i l + t j 所完全确定曲线的定义域为 “l 舭，n + l i 样条曲线在定义域内具有重复度，的节点处具有c h 连续性当我们将 次数提升一次成为七+ 1 次时，原来这k 次b 样条曲线( 2 2 1 ) ，现在将用七+ 1 次b 样 条基来表示如果保持原来的节点重复度，则七+ 1 次b 样条曲线在该节点处将应有 c ”“连续性但事实上，升阶过程中曲线保持不变，因此参数连续性也应保持不变， 仍为c 1 为此，必须提高节点重复度成为r + 1 将原七次b 样条曲线( 2 2 1 ) 的节 点矢量改写成为相异节点与重复度分离的形式，即将节点矢量u 中的节点序列改写为： ， 宁夏大学硕士学位论文 第二章曲线曲面升阶的研究成果综述 即 u - u o , u i , , u n + k + 1 ，。障，警】 这里n 表示节点厶的重复度。所有重复度的总和应等于节点矢量e ，中的节点个数， y n 一甩+ 七+ 2 白 当次数七提升为七+ 1 时，则新的细化节点矢量【，由老的节点矢量u 中所有棚异 馓蜘敢触删n b 讨矶2 】。略，锗j 其中，塞( n + 1 ) r a n + 七+ f + 3 - i + j + 3 故新的未知顶点数减1 应为i 一厅+ z 相 新的节点矢量u 决定了一组k4 - 1 次b 样条基肺，“1 0 ) ，i 一0 ，1 ，* - 0 9n + 1 于是，原k 次 b 样条曲线( 2 2 1 ) 现在可用七+ 1 次b 样条基与未知新顶点西，i 一0 ，1 ，月+ l 表示： 巾) 。善：孤， 亿：埘 现在的问题是怎样确定这些未知新控制顶点7 由于b 样条曲线曲面的升阶存在着节点要进行处理的关系，所以相对b 6 z i e r 曲线曲面 的升阶过程要复杂的多已有的b 样条曲线升阶算法主要有： 1 9 8 4 年，p r a u t z s c h 1 1 j 提出的基于节点插入的b 样条曲线升阶算法；1 9 8 5 年，c o h e n ， l y c h e 和s e h u m a k e r 1 3 1 的基于离散b 样条的递归升阶算法；1 9 9 1 年，p r a u t z s c h 和p i p e r 1 2 j 对p r a u t z s c h1 9 8 4 年的算法进行了改进：1 9 9 4 年，p i e g l 和t i l l e r | 9 1 基于b 6 z i e r 曲线升阶 的方法这些算法主要考虑的都是端点插值b 样条曲线，对节点的要求比较高，具有很 大的局限性1 9 9 6 年，清华大学的秦开怀提出了一种新的b 样条曲线升阶的矩阵方法， 可以处理非端点插值b 样条曲线下面分别对上述的算法进行简单介绍： 2 2 1p r a u t z s e h 的升阶算法 1 9 8 4 年，p r a u t z s c h i “1 首先给出了确定b 样条曲线升阶中未知新顶点的方法其理论 依据是，用做b 样条曲线的基函数的b 样条可以升阶，即七次b 样条可以表示成为 后+ 1 次b 样条的线性组合为了解决这个问题，先把由老节点矢量u 中的部分节点 聃，m + b ，埘+ k + l 决定的k 次b 样条表示成为同样由这些节点，但重复度有所改变的节 8 ! 曼盔堂夔兰堡堡塞一 第= 章曲线曲面升阶的研究成果综述 点序列所决定的k4 - 2 个k4 1 1 次b 样条的线性组合： l ，t ( 口) 。南蒌；l ( “i v ) 这里，k + 1 次b 样条n i ，l + l p 7 ) 由节点矢量r 中部分节点i ，u i + b ，埘1 , u j ， 埘+ b ，蛐+ i + 1 决定，它由决定j ，t 0 ) 的那部分节点中的埘增加重复度1 得到的将 u 中的自节点埘起前后每隔k 个节点的那些节点增加重复度1 而得相对应相应节点 矢量得到u 即有 【，函o “，聊一t b 埘i b ，埘，埘，蛳+ b ，埘+ h 附+ t + b + i + l 】。因此，当j 七 时u i + m u i 以一次( 七一1 ) 为倒说明节点h o ，u l , u 2 决定的一次b 样条n o ，1 ) ，可以表示成为 k + 2 3 个二次b 样条的线性组合： 。) 寻l _ 吣以i u 。) + 。：。i u t ) + 吣( 。p ：) 】 ( z 2 。) 将( 2 2 3 ) 式代入原k 次b 样条曲线方程( 2 2 1 ) 巾卜由弘k 若+ l + i l 川扩几 亿：渤 因【，“- u 7 ，上式中只有k + 1 个相异节点矢量u 7 ，j 一1 , 2 ，女+ 1 于是，上式可 以改写成为k + 1 条k + 1 次b 样条曲线p o ) ，- 1 ，2 ，七+ 1 的算术平均，即 p h 。雨1 磊x + zp7 ( 2 2 6 ) 其中，第j 条k + 1 次b 样条曲线方程为： p ( “) 。善d j + - ( i u ) j - 协，七十1 它的顶点d , i o 1 ，哪由使老顶点，西，d j + “b 西+ 雄+ 仇增加重复度1 得到。即u j 中的节点是将u 中的自节点坼起前后每隔k 个节点的那些节点增加重复度l 而相对 应它们的顶点数( 一聊+ 1 ) 可能不同一般地，节点矢量备不相同，节点数也可能不同， 宁夏大学硕七学位论文第二章曲线曲面升阶的研究成果综述 但其中相异的节点与细化节点矢量万中的完全相同。这七+ 1 条七+ 1 次b 样条曲线 p 0 ) ，- 1 ，2 ，七+ 1 相应由插入节点生成的新控制顶点( 其中包括末改变的老顶 i 点) d i ，f - o ，h + i ，来定义最后，取同下标的算术平均，即得到原七次b 样条曲 线( 2 2 1 ) 升阶成为七+ 1 次b 样条曲线的未知新顶点： 五。彘善x + i 孑? - o 工卅l( 2 2 8 ) 如图2 1 1 所示，运用p r a u t z s c h 方法对b 样条曲线升阶( 三阶升到四阶) 1 9 9 1 年，p r a u t z s c h 和p i p e r l l 2 l 在该算法的基础上提出了改进算法优化了算法结构， 它是原来算法的复杂组织，速度更快从七次升到七+ 1 次，原算法所需的操作数线性 地依赖于节点数二次地依赖于次数k 改进后既线性地依赖于节点数，又线性地依赖于 次数p r a u t z s c h 和p i p e r 算法是经典升阶算法中速度最快的算法，但是只能对端点插值曲 线升阶 囤2 1 1 b 样条曲线从三阶升到四阶( p 1 a u t z s c h 方法) 2 2 。2c 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 c h e 和s c h u m a k e r ”j 利用8 0 年代发展起来的离散b 样条的概念， 提出了b 样条曲线的递归升阶算法给出了较容易实现的伪代码算法它无需调用插入 节点的算法 七次b 样条曲线升阶一次成为七+ 1 次b 样条曲线后，未知新顶点的计算公式为： 夏。击荟d ) a 7 ( i ) h 川) 式中尉o ) 按如下递推关系确定： - l o 宁夏大学硕士学位论文 第二章曲线曲面升阶的研究成果综述 a j 。a ，一 ：巍u i 叭l a ；( f ) - 堕生坐口；+ 1 ( f ) + 旦生尘坠口甜( f )。 h ，一u l 。“+ + l 一+ 1 。( 2 2 ，l o ) a ：( f ) - 坠坐 扎f ) + 堕旦三坠坐a 冰f ) + 口；( f ) h j + t h j “j t t 一搿，+ i 这里的0 称为离散b 样条。 c o h e n 等人提出的递归算法也只能处理端点插值b 样条曲线，而且算法本身复杂难 懂，理论证明也比较复杂，但是它无需调用插入节点的算法，而且实践表明了该方法的 正确性如图4 , 2 2 所示，运用c o h e n 方法对b 样条曲线升阶( 三阶升到四阶) 图2 2 2b 样条曲线从三阶升到四阶( c o h e g 方法) 2 2 3p i e g ll 和t i ! l e rw 的升阶算法 1 9 9 4 年p i e g l 和t i l l e r 9 l 给出了一种基于b e z i e r 曲线升阶的b 样条升阶方法，考虑 了端点插值b 样条曲线升阶问题此算法最大的优点是可以实现b 样条曲线的一次性升 假定具有以下形式的节点矢量 m 叫圹舯叫煮册“灿“鼎 的k 阶b 样条曲线为 c ( f ) 。善。舢( f ) p i e g l t i l l e r 升阶算法： 第1 步：将b 样条曲线分割为b 6 z i e r 曲线段 曲线的分割可以借助节点插值来完成，一个节点( 内节点) 插入，次的算法公式为： fp j ，一研，园，1 + ( 1 一嘶，协一1 ，一l ， 口，暑 跖一， u j + i 一，+ 1 一， ，i k + rsjsi s ，q 2 1 1 ) 这里，h it “i + 1 ，s 是区间左端点舶的节点重数，p l , o 为原始的控制顶点。那 ：! ：! 。 么对于第一段子区问p ，4 ，口，h l o ，只要插入右节点+ l 七次，就可以两端都是 k + 1 重节点的区间b u k + l j ，显然在这个区间上的b 样条曲线退化成为b 6 z i e r 曲线段 一j o j 然后考虑第二子区间【uk + i ，“i + 1 ，u t + l ，球t + 2 ) ，再插入右节点珊+ 2 至七+ 1 重，又可以得到在区问l u i + l ，u k + 2 ) 上的b 6 z i e r 曲线段，如此类推下去，就可以将整条 b 样条曲线通过插入节点的方法分割为分段的b z i e r 曲线段 第2 步：对分割后的每段b 6 z i e r 曲线进行升阶 由于传统的b 6 z i e r 曲线升阶公式一次次升阶的计算复杂度比较高，文中给出了直接 升阶的公式： m 吣k ，o 。 ，幺f ) ) 这里，只表示升t 阶后的控制顶点， ， i 0 ，1 ，七+ f ( 2 2 1 2 ) o t ，+ il i l a x t c 工一，。，。 ：，f ；二：善 第3 步：去除多余的节点 因为在升阶时插入了很多重节点，所以在升阶完毕后需要去除多余的节点本文采 用t t i l l e rw 7 j1 9 9 2 年在c a d 上发表的文章中的方法，去除节点的计算公式如下： - 1 2 - 宁夏大学硕士学位论文第二章曲线曲面升阶的研究成果综述 五t ，芝些巡 舛一生等丛 “一“叮 其中口f 。 “_ + i 1 一口口 r k i ( 2 r 一七一j 一1 ) 2 ( 2 r 一七一s 1 ) 2s ，一s 口一l ，j ( 2 2 1 4 ) 如图2 2 3 所示，运用p i e g l t i l l e r 方法对b 样条曲线升阶( 三阶升到四阶) 但事实上，以上三步并不是按顺序进行的，p i e g l l t i l l e r w 升阶算法的具体步骤是； 插入第一个内节点，次后，将第一段曲线升阶f 一2 次，再插入第二个内节点，次，将 第二段曲线升阶，次，然后再去掉插入的，个第一个内节点，依次再对后面的内节点进 行同样的操作，最终得到新的控制顶点和节点矢量，得到升阶后的，+ f 一1 次b 样条曲 线 特别地，在插入节点的过程中，都是插入旧节点，并且是在前内节点已被插满的情况 下插入的，所以比一般的节点插入要省掉许多存储和运算同样，在去除节点时，由于 去掉的节点恰好就是插入的节点，所以无需求中间过渡的控制点，直接就可以得到所求 控制点 将该方法与上述p r a u t z s c h 和p i p e r ，c o h e n 等的方法相比，简单且易于理解，就计算 的空间复杂度和升高阶时复杂度的上升速度比较，也可以得出该方法比较占优的结论虽 然这种算法是经典的b 样条曲线升阶算法之一，但是由于仅考虑了端点插值b 样条，局限 性也是很显然的 图2 , 2 3b 样条曲线从三阶升到四阶( p i t g l 1 3 1 l e t 方法) 2 2 4 秦开怀的升阶研究 1 9 9 6 年，秦开怀1 1 4 , 1 s , 1 6 , 1 发表了他对b 样条曲线升阶的研究进展，提出了b 样条曲 线升阶的矩阵方法1 9 9 7 年，他 1 7 , 1 1 , 1 9 l 又发表了探讨b 样条曲线升阶经典算法中存在问 题及其解决办法的论文 该方法从b 样条函数的性质着手，证明了用七十1 阶b 样条基函数表示_ | 阶b 样条 1 3 宁夏大学硕士学位论文第二章曲线曲面升阶的研究成果综述 基函数的一个公式，提出了用于b 样条曲线升阶的矩阵方法 文中证明了七阶非均匀b 样条基函数可以用七4 - l 阶非均匀b 样条基函数的线性组 合来表示： n t t + 1 , k ( f ) 一l i ( f ) m ，t ( f ) l 七 口o ) 口们 a o ：( 0 鲫( f ) 口o ， a ) a l ， a k 一嘶) m 一嘶) 缎一i a ) 上式中，对于“- 0 , 1 ，k 一1 ，p m l f o , 1 ，七，有 肺一k , k + l ( 0 她t + 1 ( f ) m 。t + 1 ( t ) f 2 2 i s ) “砸，瞄一舶， 卜”1 ，苫一。再鼢川k ，u “ f 1 ， “- ， 眠卜恒筹篇器舻v f1 “+ 1 一v 鼠卜 酉旨裂高等，u + l v 扮( j ) 。皇二型，5 = q 1 ，七 办+ j t j 此定理清楚的表明了k 阶与k + 1 阶b 样条基函数之问的关系，利用这一关系，容 易得到b 样条曲线的升阶公式和算法。 设k 阶样条曲线的控制顶点为巧( ，一0 ，1 ，阼) ，节点矢量为u - 口膏社，则1 3 样条 曲线的方程为 c ，- i + - ( r ) i 矽，( f ) ， i = k 一1 ，岛；雎一k + l ( 2 2 1 7 ) 其中，