（应用数学专业论文）基于显式矩阵表示的nurbs曲线曲面的升阶和降阶.pdf

浙江人学钡i 学位论殳 摘要 作为c a d 系统国际工业标准之1 的n u r b s 曲线曲面在计算机辅 助几何设计( c a g d ) ，计算机图形学( c g ) 年nj l 何造型( g m ) 等应用领 域中都具有非常重要的作用对这种几何模型升阶和降阶的理论研 究由于关系到设计系统的数据交换和数据压缩而成了当务之急本 文正是研究了对n u r b s 曲线曲而进行快速而有效地升降阶的算法 和应用 作者对国内外在该课题上的进展情况进行了系统详尽的分析，提 i ；了一种基于n u r b s 曲线曲面冠式矩阵表示的升降阶的新方法：首 次导出了n u r b s 曲线曲而一次性升多阶的矩阵变换公式；在这个基 础上，应用广义逆矩阵的最小二乘理论，给出了它们的一种一次性降 多阶逼近方法，并以大量实例加以验证本方法克服了以往算法中每 次只能升降次的弱点，且计算简捷，没有积累误差，可望在图形和 工业设计中获得广泛应用 关键词n u r b s 曲线，n u r b s 曲面，矩阵表示，升阶，降阶，逼近， 广义逆矩阵 儿 勰攫夫学磺 学髓谚文 a b s t r a c t a so n eo fi n t e m a t i o n a li n d u s t r i a ls t a n d a r d so fc a df c o m p u t e ra i d e dd e s i g n ) s y s t e m s 。n u r b sc u r v e s a n ds u r f a c e sh a v e w i d e s p r e a da p p l i c a t i o n s i nc a g d ( c o m p u t e r a i d e dg e o m e t r i cd e s i g n ) c g ( c o m p u t e rg r a p h i c s ) a n dg m ( g e o m e t r i c m o d e l i n g ) i ti su r g e n t t o i n v e s t i g a t ea l g o r i t h m sf o rd e g r e ee l e v a t i o na n dd e g r e e r e d u c t i o no ft h i s g e o m e t r i c a lm o d e lb e c a u s eo fi t si m p o r t a n c ef o rd a t ae x c h a n g e a m o n gd i f f e r e n td e s i g ns y s t e r n sa n dd a t ac o m p r e s s i n g t h i st h e s i s f o c u s e so nn e w e f f i e i e n td 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 na l g o r i t h m sf o rn u r b sc u r v e sa n d n u r b ss u r f a c e sa n dt h e i ra p p l i c a t i o n s 。 f i r s t ，e x i s t i n ga l g o r i t h m s f o rd 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 fn u r b s e u r v c s s u r f a c c sa l ea n a l y z e ds y s t e m a t i c a l l y t h e n t h ea u t h o rp r e s e n t ss o m ee 衢c i e n t a l g o r i t h m sf o rd 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 fm 佩b s c u r v c sa n dn u r b s s u r f a c e sb a s e do nt h e i re x p l i c i tm a t r i c e sr e p r e s e n t a t i o n 。f o rt h ef i r s tt i m e 。搬ea u t h o r d e r i v e sm u l t i d e g r e ee l e v a t i o nt r a n s f e rm a t r i c e so fn u r b sc u r v e sa n dn u r b s s u r f a c e s ，c o m b i n i n g t h e i r 妇n s f e rm a t r i c e sw i t ht h el e a s t s q u a r e st h e o r y o f g e n e r a l i z e di n v e r s em a t r i x ，n 蹦a l g o r i t h m sf o rm u l t i d e g r e er e d u c t i o na p p r o x i m a t i o n o f n u r b sc u r v e sa n ds u r f a c e sa r ep r e s e n t e d t h e y g e ta na d v a n t a g e o v e rt h ee x i s t i n g a l g o r i t h m sf o rd e g r e er e d u c t i o n ，t h a ti s ，m u l t i d e g r e er e d u c t i o nc a nb ed o n ei no n e s t e 口a n df h ea d j u s t m e n to fc o r r e s p o n d i n gk n o tv e c t o r si sr e l a t i v e l yl i t t l e 。al o to f e x a m p l e sa r ep r o v i d e dt ot e s t i f yt h ef e a s i b i l i t yo ft h e s en e wa l g o r i t h m s t h et h e s i s c o n c l u d e sw i t hp e r f o r m a n c ee v a l u a t i o na n dd i s c u s s i o no f p o s s i b l ea p p l i c a t i o n so f t h e i n t r o d u e e dm e t h o d k e y w o r d s n u v , b sc u r v c s ：n u r b ss u r f a c e s ，e x p l i c i tm a t r i xr e p r e s e n t a t i o n ， e l e v a t i o n ，r e d u c t i o n ，a p p r o x i m a t i o n ，g e n e r a l i z e di n v e r s em a t r i x f 锈 王大学蛹| j 学链涪交 致谢 在本论文宽箴之际首克向我姥导师盖国瑾教授表示我素崇高蛞敬意， 在我坟读硕士学覆撼三毒瓣麓垩。童老撵拳学霹囔镑蟾敏锐谰察和盖砖把 蠛爱我能够 捶利地逆行磷毂捌 究王老师期博的专业知识严谨踏实的治学态 度以反不懈努力，锐意蟪取诲人不倦的精神品质令我臻者难忘同时王老师 更在生活中关心我督谯我真藏是我学霹和生游拳方面蛞o - 评点友 感谨汪国禧老捧。拐轴毒霆释鸯本人在嗣 竞建学露糍麓醣关心和支薅，老耱 们实事求是罐益露艟的章i 学态度和扎宾全面盼理论知识给我撼下了深制的印 象在此对他们氟示我深_ ：搴的谢意 感谢本课毂雒晴陈雾同学嶂丞勤民同学，蔺宏讳同学感谢他们富唷创斯性 酶建议和琴耢，和诬栽一起遘蠢镬雄囊酶子是我拳远缓薅纪念酶宝黄瓣害 感瓣本谋嚣组碍究_ 生讨论班和实验室珀其他各位姆兄，师搬，师弟和师昧 们曾经绺予氟的丸私帮助表噼感谢其他在学习和生活中帮助试我的藏师同 学和朋友， 蒋巅威壤我酶壤友江噼霉学表簌学露和圣活孛戆络我酶鼓霸和支薅， 罩蓐要感谢我袖母亲和兄长+ 他们为我所破妈一切是我得“l 宽威学业的 力童源寨和坚强后盾哼薰将此文献给他们 ；零零；牟土月 静卉慧 季$ 是番 滤攫又学碳壹学短论文 第一章绪论 1 1b 6 z i e r n u r b s 赫线叠| l 赢的发展历史 c a d ( c o m p u t e r a i d e d d e s i g n ) c a m ( c o m p u t e r a i d e d m a n u f a c t u r e ) 技术起源予 航空工业由于 s 机的外形复杂，含有大量的曲颈，因此，c a d c a m 技术从一开 始就与髓线兹蕊逵垄技术紧密联系在一麓作为c a d 系统中最鬟要的褥个概念 b 6 z i e r 曲线曲面和n u r b s 曲线曲面理论的发展与完善是国内外无数科研工作者 尼卡年鹃努力鹣结票 秘霉徒秘，f e r g u s o n 黄先在飞穗设诗主痉曩了参数三次麴线f 2 2 】，弓| 入7 参数 方法表示的自由曲线曲筒b 6 z i e r 在1 9 6 2 设计了以逼近为基础的曲线曲丽造型系 统u n i s 潦嚣焚孩心愚想是弱控凝聚臻定义趣线越覆瓣b 6 z i e r 方法【3 】。夔鑫， f o r r e s t 2 3 ，g o r d o n 和r i e s e n f e l d 2 4 ，2 5 等对b 6 z i e r 方法做了深入研究，揭示了 b 6 z i e r 方法与b e r a s t e i n 多顼式之阉的联系，从箍锼其其有更坚实豹理论基破 1 9 8 3 年，f a r i n 2 0 更进一步研究了能统一表示圆锥曲线与自由曲线的有理b 6 z i e r 麴线 另一方面，b 样条( b ，s p l i n e ) l t t j 线曲丽幽于具谢局部性及连续除可调性褥逐步 成为几何造型的核心技术b 样条的概念激初是由s c h o e n b e r g 予1 9 4 6 年黄先提出 来的1 4 3 1 c l a r k 1 0 ，l l 】，d eb o o r 1 6 ，1 7 和c o x 1 4 分别对b 样条曲线做了研究7 0 年代裙，g o r d o n 帮r i e s e n f e l d 等入研究了菲均匀b 样条f 2 5 ，4 1 ，4 2 ，荠萌次将b 样条应用到外型设计 2 5 v e r s p r i t i e 完成了有关有理b 样祭的博士论文 4 7 】在8 0 年健裙麓，l a n e 秘c o h e n 提密了簿散b 样条霸分割技术 1 2 ，3 0 。1 9 8 2 年，b o e t m l 提出了b 样条曲线的节点插入算法【6 】；t i l l e r 论述了有理b 样条曲线曲面的具体 痣蘑f 4 6 】- j | ：嚣，l + p i e g l 秽碱t i l l e r 更系绞缝探索了有理转+ 群条麴线瑟瑟愆构造 和形状调整问题，并系统论述了n u r b s ( n o n u n i t b r mb s p l i n e ) 方法 3 3 ，3 4 ，3 7 ， 3 8 ， 出予n u r b s 方法霹戳爱绞一戆方式表忝杰一次，二次兹线熬蘧裁其宅自出 曲线曲丽复合成的复杂曲线曲面，所以它在外形设计方筒具有强大的功能与潜 力。n u r b s 方法鲍号| 入大大增强了c a d c a m 系绞的越露造型功能，因霹缮到了 浙江人学硕i + 学位论史 日渐广泛的应用目前，产品模型数据交换的国际标准s t e p ( s t a n d a r df o rt h e e 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 作为几何描述的主要方法【5 4 】 n u r b s 已r 益成为众多c a d c a m 系统的基本几何表达形式和数据交换的国际 标准 1 2 多项式曲线曲面升降阶研究的重要性 作为b 6 z i e r 曲线曲面和n u r l 3 s 曲线曲面的两种基本运算，升阶和降阶具有 非常重要的意义其重要性主要体现在： 由于几何图形最高阶数不同的造型系统之间经常需要进行数据交换 1 5 1 ， 而不同系统所允许的曲线曲面的最高阶数可能不同，经常需要通过升降 阶使它们之间可以进行相互交换 升阶或者降阶是构造蒙皮曲面【l ，5 0 和组合曲面 9 】的重要工具，因为相 邻曲面截面线的阶数一般是不同的，因而在曲面设计的预处理过程中， 经常需要通过升降阶使之阶数一致，从而进行后续处理 由于节约了存储空间，降阶对于数据压缩也具有很重要的作用例如， 在工业产品( 如汽车车身，叶片) 的模型设计及仿制过程中，对离散点数 据进行逼近拟和时，往往会产生高阶的曲线或曲面表示几何造型中， 曲面片求交产生的交线及裁剪边界曲线也会产生高次的曲线表示，这些 都导致了大量几何数据信息的存储为了尽量减少信息数据的存储量， 就需要对高次的曲线曲面进行降阶处理 升阶公式同时还是理论推导的必要工具 降阶也经常用于曲线的光顺处理过程中2 1 1 一一 由于上述种种原因的存在，曲线曲面升阶和降阶的理论研究就成了一个紧迫 的课题 1 3 升降阶方法的研究现状及困惑之处 关于b 6 z i e r 曲线曲面的升阶方法，目前已有相对而言较为成熟的理论和算法 早在1 9 7 2 年，b e z i e r 本人就提出过b 6 z i e r 曲线的升阶算法 4 进入8 0 年代 f a r i n 2 0 ，p i e g l 3 2 】又对有理b 6 z i e r 曲线曲面的升阶方法做了较为详尽的研究 2 浙江大学硕1 1 学位论文 可以说，到目前为止，b 6 z i e r 曲线曲面的升阶已经有较成熟的理论成果了 相比较而言，b 6 z i e r 曲线曲面的降阶研究就更加丰富多彩f o r r e s t 2 3 也曾于 1 9 7 2 年对b 6 z i e r 曲线的降阶做过研究8 0 年代，有更多的学者对b 6 z i e r 曲线曲面 的降阶算法做出了贡献，如f a r i n 2 0 ，p i e g l 3 2 对有理b 6 z i e r 曲线曲面降阶的研 究，另外还有d a n n e b e r g 1 5 ，h o s e h e k 2 6 ，w a t k i n s 和w o r s e y 4 8 ，l a c h a n c e 2 9 等 人亦从各个方面对该问题进行了探讨1 9 9 3 年和1 9 9 5 年，e c k 也分别对b 6 z i e r 曲 线降阶的研究取得了一定的进展【1 8 ，1 9 1 9 9 5 年，b o g a c k i 基于c h e b y s h e v 基与 b e m s t e i n 基转换的思想提出了另一种b 6 z i e r 曲线降阶算法 5 1 b r u n n e t t 等分别在 1 9 9 6 年，1 9 9 8 年两次公布了他们对b e z i e r 曲线降阶的研究成果【7 ，8 】国内的学者 对这一领域的研究也做出了相应的贡献，主要成果有：1 9 9 7 ，1 9 9 8 年，胡事民等 人对b 6 z i e r 曲线曲面降阶的研究 2 7 ，2 8 】；2 0 0 1 年，陈国栋和王国瑾利用b 6 z i e r 曲线本身的几何性质结合广义逆矩阵理论给出的一种新的降阶逼近方法，该方 法取得了较好的逼近效果 5 6 然而，时至今日，作为更重要的参数曲线和曲面，有关n u r b s 曲线曲面的升 降阶理论的有效工作却相对较少这主要是因为n u r b s 曲线曲面的升降阶牵涉 到复杂的节点处理，比b 6 z i e r 曲线曲面的升降阶要困难得多 现有的b 样条曲线升阶算法主要包括：p r a u t z s c h 的基于插入节点的算法 3 9 ， 4 0 ，c o h e n ，l y c h e 和s c h u m a k e r 的递归升阶算法 1 3 】以及p i e g l ，t i l l e r 的基于 b 6 z i e r 曲线升阶的方法 3 6 ，4 5 已有的b 样条曲线降阶算法则有：p i e g l ，t i l l e r 的 基于b 6 z i e r 曲线降阶的方法【3 5 ，w o l t e r s ，w u 和f a r i n 的基于b 样条曲线开花 ( b l o s s o m i n g ) 原理和最小二乘法的降阶算法【4 9 】此外，国内的学者对这一领域 的研究进展主要有：清华大学的秦开怀对b 样条曲线升阶 5 7 ，5 8 ，5 9 1 和降阶所做 的工作 6 0 】，胡事民等人对基于退化b 样条曲线充要条件和约束优化的降阶算法 的研究 5 1 ，6 1 1 至于b 样条曲面的升降阶算法，到目前为止不论是在国内还是国 际上都甚为罕见 对于上述升降阶方法的原理和技术细节，在第二章中有更为详细的阐述此 处就不再赘述 所有这些已有的算法都有一定的不足，这些不足主要表现在两个方面 每次只能升降阶一阶，若要升降多阶，必须执行程序多次逐次降阶，不 浙江大学硕士学位论文 但繁琐费时，而且容易产生累积误差 对于b 样条曲线曲面的升降阶算法来说，绝大多数的方法都对节点的形 式具有严格的限制，譬如说只能处理节点矢量为端点插值形式的，或者 只能处理均匀b 样条曲线或曲面这样就极大地限制了算法的应用范围 同时，多数算法在进行升降阶时都对节点做了较大的改动，这样不仅对 算法的实现造成了一定程度的困难，同时亦给算法的使用者( 往往并不是 算法的编制者，而是一些造型设计人员) 对算法的理解造成了不便 由此可见，创造一个简单可行的n u r b s 曲线曲面一次性升降多阶的算法 确是瓜熟蒂落。势在必行 1 4 本文的目的及主要结果 有鉴于目前n u r b s 造型系统对升降阶算法要求的迫切性，本文就此开展了 一项专门的研究作者的目的旨在设计一种容易理解，计算方便，具有普遍性的 n u r b s 曲线曲面一次性升降多阶的算法 本文利用n u r b s 曲线的显式矩阵表示，首次推导了n u r b s 曲线一次性升 多阶的矩阵公式，克服了以往很多升阶算法只能一次升一阶的缺点，可以方便地 实现一次升多阶同时，将广义逆矩阵的最小二乘原理与曲线显式升阶的逆过程 相结合，提出了n u r b s 曲线一次降多阶的逼近新算法而且从该算法经过大量 实例反复验证的结果，可以看到本方法具有预期的效果 因为n u r b s 曲线的表示方法可以方便地向n u r b s 曲面的表示方法扩展 因而上述曲线算法也很容易应用到n u r b s 曲面的升阶和降阶上具体地说。就 是推广上述曲线的升阶和降阶方法：推导了n u r b s 曲面一次性升多阶的矩阵公 式，并将该升阶公式与广义逆结合提出了相应的n u r b s 曲面的降阶方法同样 对于曲面的升降阶情况，也给出了大量的实例予以检验 由于n u r b s 曲线曲面在几何造型和工程实际中的广泛应用，可以预计这种 方便快捷的方法必能给c a d c a m 和几何造型设计注入新的活力 4 浙江大学碗j ：学位论文 第二章多项式曲线曲面升降阶方法的研究现状 2 1b 邑z i e r 曲线曲面升降阶的研究成果综述 关于b 6 z i e r 曲线曲面的升降阶方法，与b 样条曲线曲面对比而言，因为理论 相对已经比较成熟，同时与本论文的课题相差较大，所以对于一般的算法就不仔 细阐述了，但对其中个别重要的将较仔细地说明 2 1 a 升阶算法 b 6 z i e r 曲线曲面的升阶方法，目前已有相对而言较为成熟的理论和算法早 在1 9 7 2 年，b 6 z i e r 本人就提出过b 6 z i e r 曲线的升阶算法【4 】不过他的方法虽然可 以增加相应的顶点达到升阶的目的，但是算法的复杂性限制了其实际应用，更为 广泛应用的升阶算法是基于b e m s t e i n 基函数的升阶方法，也就是： p ( f ) = b 7 ( t ) p i = 彤“( f ) 丘， ( 2 川) 扣0i = 0 宴2 斋暑- l + ( 1 - 斋) 只，只2 只+ l _ o ( 2 2 ) 这里彤( f ) 和钟“( f ) 分别表示n 阶和n + 1 阶b 6 z i e r 基函数，只( j = 0 , 1 ，以) 和 声，( ，= o ，l ，行+ 1 ) 分别表示升阶前后的控制顶点 进入8 0 年代，f a r i n 2 0 ，p i e g l 3 2 x 南j 有理b d z i e r 曲线曲面的升阶方法做了比 较详尽的研究可以说，到目前为止，b 6 z i e r 曲线曲面的升阶理论已经是较成熟 的理论成果了 2 1 b 降阶算法 与升阶相比，在b 6 z i e r 曲线曲面降阶方面的研究因出发点的不同产生了更加 丰富的分支f o r r e s t ，d a n n e b e r g ，f a r i n ，p i e g l ，h o s e h e k ，w a t k i n s & w o r s e y , l a c h a n c e ，e c k ，b o g a e k i ，b r u n n e t t 等都对该课题作了分析，各自取得了不同方面的 研究进展 浙江人学硕上学位论文 这些降阶方法基本可以分为两大类，即 基于控制项点逼近的几何方法： 1 9 7 2 年，f o r r e s l 2 3 弄l j 用升阶与降阶之间的内在联系，取降阶曲线的控制顶 点为： 覃= p i , 0 s i n 2 一1 ； ( 2 1 3 a ) 霉= 掣，l n 2 j + l s i h ； ( 2 1 3 b ) 只，：= ( 彤2 + 彤2 ) 2 ，( 2 1 3 c ) 这里，b j 卜 分别表示小大于或等于x 的最大最小整数，) 昌为原曲线的控 制顶点，点向量由原始控制顶点决定： 覃= ( ( n + 1 ) p i 一皿! 。) “n + 1 一f ) i = 0 , 1 ，一，月；( 2 1 4 a ) 亏”= ( ( 月+ 1 ) 暑一( n + 1 一f ) 只! ，) i ，i = 月+ 1 ，h ，- 一，1 ( 2 1 4 b ) 降阶曲线可以保持端点 0 1 ) 2 】阶插值类似地，f a f i n 2 0 】提出取 霉= ( o f ) 只+ 田”) i n ，但是从实用的角度考虑，这两种方法的降阶精度不够 1 9 8 5 年，d a n n e b e r g n o w a c k i 【1 5 利用原曲线采样点的位矢和导矢，用分段 插值曲线进行降阶逼近随后，h o s c h e k 用离散的方法解决b 6 z i e r 曲线的降阶问 题【2 6 】其方法是首先对原曲线进行离散，然后利用原曲线的几何信息，通过多 段低次曲线来插值逼近原曲线但是由于逼近曲线段数多且需递归调整离散点 参数，这一方法存储量大且费时 基于基转换的代数方法： 利用c h e b y s h e v 多项式 h j ( f ) 晶构成n 次多项式空间的基以及，次多项式 日n l 0 l 。h j ( f ) 的n 1 次最佳一致逼近恰是q h ；( f ) 的性质，可以得到b 6 z i e r 曲线 i = oi = 0 曲面降阶的另一种方法 w a t k i n s 和w o r s e y 4 8 j l 匝过用c h e b y s h e v 多项式表示b 6 z i e r 曲线： n p ( f ) = p b ( t ) = q f h i ( 2 t - 1 ) ， o ，l 】， ( 2 1 5 ) i = oi = o 浙江人学硕i 学位论空 其中，h ，( 2 t 1 ) 是【0 ，l 】上的c h e b y s h e v 多项式然后除去最高项系数 n - 1n - ! 乒( f ) = 霉w 1 ( f ) = g h ，( 2 t 一1 ) t o ，1 ，最后转换回b e m s t e i n 基函数的形式 i ；0k 0 得到降阶曲线的控制顶点 - m ，仲n - i ，但是降阶前后的控制顶点之问的显式表示关 系却无从得知 差不多在同一时f a j ，l a c h a n e e 2 9 】也提出用约束c h e b y s h e v 多项式的概念来 讨论b 6 z i e r 曲线在匕空间内最佳一致逼近的问题：d 。= m 州。a x ”l | ( p ( t ) 一乒( f ) ) 0 ，其 基本原理与w a t k i n s w o r s e y 的算法一致，同样不能得到显式关系式 e c k 【1 8 ，1 9 则利用约束l e g e n d r e 多项式考虑了使距离函数 d ：= “咏i 万而满足最小二乘的问题他综合了f 。r r e s t l a c h a n c e 两 人的技术，首先取降阶曲线i f ( t ) 的顶点覃= ( 1 一九j 只+ 九，只”，再利用 c h e b y s h e v 基与b e m s t e i n 基之间的转换关系通过降阶逼近误差的公式 d ( p ，f ) = 2 “+ l | 硝“e o l( 2 1 6 ) 求解九，从而得到显式表示式b r u n n e t t e ta l 7 ，8 】探讨了这种逼近的几何意义 1 9 9 5 年，b o g a c k i 基于c h e b y s h e v 基与b e m s t e i n 基可以相互转换的思想，用 舍去c h e b y s h e v 多项式中多个高次项的办法可以进行b 6 z i e r 曲线的一次降多阶 逼近，但由于没有充分利用b 6 z i e r 曲线本身的几何性质，在实际运算中有时误差 会较大，同时在端点也只能达到位矢插值 5 】 上述的b 6 z i e r 曲线降阶方法各有长处，但也存在一些局限性有的计算较繁， 有的精度较低，有的缺乏几何直观性，而且绝大多数降阶方法只能一次降一阶， 若需降多阶，则需采用逐次降阶，这不仅导致计算耗时，而且误差很大 为了克服以上的局限性，浙江大学的胡事民等人对b 6 z i e r 曲线曲面降阶开展 了系统的研究 2 7 ，2 8 ，5 3 b 网扰动和约束优化法，具有明显的几何直观性，可同 时适用于曲线曲面的降阶用于曲线降阶时，可给出误差估计，结合离散算法可 以达到高精度，且保持g 1 连续，用于b 6 z i e r 矩形曲面片和三角片降阶时，把降阶 问题转化为求解线性方程组，而降阶的误差同样取决于原曲面的一些内在几何 不变量2 0 0 1 年，陈国栋和王国瑾又利用b 6 z i e r 曲线本身的几何性质巧妙结合广 浙江大学硕i j 学位论文 义逆矩阵理论给出了一种新的降阶逼近方法 5 6 只需要求解一个线性方程组 就可以一次降多阶，计算方便简单，逼近效果好带端点插值条件的b 6 z i e r 曲线 降多阶法，既可一次降多阶，又可在曲线首末端点分别达到，p ( r ，p 0 ) 阶插值， 并实现对原曲线的近似最佳一致逼近，计算简单稳定，易于实现，还可结合分割 算法达到更快速的收敛 因为与本论文所做的工作关系比较密切，这里简要介绍一下上面所说的基于 广义逆矩阵的b 6 z i e r 曲线降阶方法 设a 是m n ( m n ) 阶实矩阵，且有满秩分解a = b c ，其中占，c 分别是m ， 阶列满秩和r xn 阶行满秩矩阵此时，爿的广义逆矩阵为彳+ = c + b + ，因为口，c 为列满秩和行满秩矩阵，所以口b ，c c 7 为r r 阶对称正定方阵，于是 a + = c 7 ( c c7 ) 。( b7 口) - 1 b7 ，这时超定线性方程组a x = b 的最小二乘解 为x = a + b = c 7 ( c c 7 ) - 1 ( b 7 b ) 。1 8 7 b 特别，若矩阵一为列满秩，那么a + 就可简 化为a + = ( 一7 一) - 。a 7 ，相应地，上述超定线性方程组的最小二乘解就可以简化为 x = ( a 7 爿) a r b ，这是下面要用到的相关广义逆矩阵方面的内容 欲降阶的曲线为月次b 6 z i e r 曲线，( f ) = 群( ，) 只，从升阶的反过程考虑， f t 0 一i 设该h 次曲线是由n - 1 次b 6 z i e r 曲线只一。( f ) = 曰( f ) 豆，。经过一次升阶得到的， i = 0 则显然： 只= 爿乏一 其中a 。为o + 1 ) n 阶列满秩矩阵， ( 2 1 7 ) 1 0 一i ) n ，i = _ ， a 。= ( 口u 。) 。：o j 一。，a “。= f n ， i = j + 1 ，( 2 1 8 ) 卢“1 4 。 1 0 ，其它 只= ( e o ，只一，p 。) 7 ，乏一。= ( 瓦，i ，1 ，一，只- i , n - i ) 7 ( 2 1 9 ) 浙江大学顾。i 学位论文 类似地，设肌次b 6 z i e r 曲线瓦( f ) = 纠m l f j - - ，。经过月一川( o m ) 2 ) 次升 i = o 阶得到n 次b 6 z i e r 曲线，则有( 女+ 1 ) k 阶列满秩矩阵4 ( 女= ，l ，n 一1 ，m + 1 ) ，使 得： 只= 爿。只一i = a n a 只一2 = a n a 一m ，+ 。瓦 ( 2 1 1 0 ) 记一= a n a 。a 。= ( ) ，j 易知a 为m + 1 ) ( m + 1 ) 阶列满秩矩阵 j = 0 一m 欲求互= ( p o 。，互卅 一，瓦。) 7 ，使得爿只= 只，由广义逆矩阵理论可知，此超 定线性方程组的最小二乘解可以表示为： 露= ( 豆二，再：，一，乒二) 7 = 爿+ 只= ( 爿7 爿) 。a r 只， ( 2 1 1 1 ) 从而可得原h 次曲线只o ) 的降n m 阶逼近曲线露( f ) = 占八mr j - - * i = o 瓦= 瓦。= 只。，瓦= 己。= 只。， ( 2 1 1 2 ) 爿= 4 。+ m 抽。，= ( 专考0 ，只= ( 蒙 ，只= 爱 c z s ， 这里，a t , a 8 为( h 1 ) x l 阶矩阵，a 。为即一1 ) ( 川一1 ) 阶列满秩矩阵，且 车= ( 只。，最一，只。) 7 ，砰= ( i 。，夏。，瓦。，) 7 分别为( n 1 ) 1 和沏一1 ) 1 阶矩阵由矩阵分块乘法，可知现在的超定线性方程组变为 a 。只：= 只i a 只。一一。只。 ( 2 1 1 4 ) 上面方程组求得的最小二乘解与端点条件相结合可以得到最终的降阶逼近曲线 f 100 1 露= ( 瓦，夏- ，瓦) 7 = j + 只= l 一( 彳。) a ( 爿。) + 一( 爿。) + a 81 1 001 j 误差估计式为e = 4 只( f ) 一露( 叫卜。m 。a x 。i i e , 一e , l l ，这里q i 为降阶逼近曲线升 囊缸太学颤l ：学经抡文 n m 阶髓得到的曲线控制顶点 2 2b 群条鎏线基西舞降险朗婿究戒采综述 然嚣，与b 6 z i e r 麴线整瑟豹舞簿跨褪魄，露毯今曩，俸为更麓蒌戆参数麴线 和曲面，有关n u r b s 曲线曲面的升降阶理论的有效工作却相对较少遮主要是 鞫势n u r b s 夔线照覆的_ 爨降除零涉型复杂熬节点处理，跑b 6 z i e r 趣线麴嚣熬秀 降阶要困难得多 2 2 a 升阶算法 虽然b 6 z i e r 曲线曲丽的升阶过程还算比较简单的，但怒b 样祭曲线曲面的升 除帮困存在羞节建要避褥楚理静关系，撩慰要复杂豹多。已寿夔b 群条麴线舞除 锋法主要有： 1 9 8 4 年，p r a u t z s c h 提出豹b 撵条曲线舞蹬算法；1 9 8 5 年，c o h e n ，l y e h e 积 s c h u m a k e r 的递归升阶算法；1 9 9 1 年，p r a u t z s c h p i p e r 对p r a u t z s c h8 4 年算法的 敬进：1 9 9 4 年，p i e g l t i l l e r 基于b 6 z i e r 热线爨除鹣方法凌这些冀法中，主要考 虑的都是端点插值b 样祭，对节点的要求比较高，具有很大的局限性1 9 9 6 年， 滤华大学敷秦开悔提出了静掰的b 掸条曲线魏输的矩辉方法，可以处理菲端 点插值的b 样条曲线下面分别对上述的算法进行简单回顾 1 9 8 4 年，p r a u t z s c h 翁秀除算法裰攒多元b 棒条矫褥蘩懿公式： c ( f ) = ( c 。( f ) + t 十c 。( f ) ) r r t ，( 2 2 1 ) 这里，c ) = 掣墨。o ) 雎= l ，壳其中，莓。o ) 为b 样条基，z 为整数集合 z = - 一，一1 , 0 ，1 ，。，l ，& ；z u ( 蚌+ 专+ 辫z ) ， 曩”= 孟j ，雪；：；+ + m z ， 掇出了b 撵条些线豹丹酚冀法【3 9 】1 9 9 1 簪，p r a u t z s c h 和p i p e r 又姆此算法进行了 改进 4 0 】优化了算法结构 1 9 8 5 年，c o h e n ，l y c h e & s c h u m a k e r 幂l 霜8 0 年代镪发展麓来静离毅b 稀 浆的概念【1 2 提出了b 样条曲线的递归升阶算法【1 3 】 o 濒江天学续毒学整竣文 设m 徐b 徉条曲线静带点矢蘩形翔 翼 ， 要 、 y l y # + 埘= l ， ，i ， l ， t 这警 + 辨= 强 扛l 升一阶以后的m + 1 阶b 样条曲线的节点矢量形如 ，鬟! 、! 舅鹑+ 捌+ l = 1 一，q ，k ， 遮鼙筇= 朦+ 惫一1 那么霹以出琢始戆b 缮条兹线c = 罢壤。0 ) ( 只为控铡顶点，b i 。 为b f * o i 榉条基函数) 褥蘩舞输焘豹b 榉条莛线c = 嚣爰。 。 卜，巍爹瓤+ f c o h e ne ta 1 提出的这种递归算法不仪只能处理端点播值b 样条曲线，而且 然溃本囊致结构搬毙骚蓉杂。 1 9 9 4 年，p i e # l 秘t i i l e rw 在c a d 上萋文【3 6 l 提出了一种基予b 6 z i e r 曲线升阶的b 样祭升阶方法，考虑了端点插值的b 样条曲线升阶问题 假定麓熹美鬃共有鞋下形式： 笠! ，盟!、 u 攀趣8 ，材。) = 和，盘，一，d ，“。+ l ，u p _ m _ i ，| b ，6 ，b ) 巍拄太学磺j j 学位沦空 # 熟辫除b 样蘩麴线兔c = 鬟毽，) i = 0 算法舱流程可以用如下过程表示： s t e p l 将b 样条曲线分割为b 6 z i e r 曲线段 曲线的分割w 以借助节点插值来完成一个节点插入，次的冀法公式为： 羹，= 伐l ，只，- l + ( 1 理和) 只- ，一， ( 2 ，2 t 3 ) 仅i ，= ! _ 二奠l ，k 一槐+ ，f 七一s ， 2 2 4 ) u i m ，l u i 这里，兰玎 u 。，s 怒区间左端点如的节点熏数，只，。为原始的控制顶点那 竺芝 么对于第一段子区间，a ，a , b l 卅卅) 只要插入右节点u m + im 次，就可以两端都是 撒+ l 重节点的区闯a ，“。) ，显然在这个区间上的b 祥条曲线退亿为b 6 z i e r 曲线 笠! 段，然纛考虑第二段予送麓泌m ，掰。，掰m , l ，u 卅+ 2 ) ，器秀嚣节熹簿。+ ：至辨+ 1 重， 又可以得到在区间m 。，“。+ ：) 上的b 6 z i e r 曲线段，如此类推，就珂以将熬条的b 样条曲线通过加节点的方法分割为分段的b 6 z i e r 曲线段 s t e p 2 砖分裁磊麓每莰b 6 z i e r 麴线进行舞除 b 6 z i e r 曲线的升阶楚比较简单的，这墨需要避明的是：出于传统舞阶公式一 次次升阶的计算复杂度眈较高，所以文中给出了赢接升阶的公式： ( 瓤加 ( 删? 。 i = 0 ，m + t ，( 2 2 5 ) 这里，只表示骨蹬嚣骢控裁顶点，嚣一f ) + = l i 。- ，f t , i f - - 。 s t e p 3 去除多余静摹纛 因为在舞除聪加了缀多重节点，所以在势除突毕君嚣要去除多余节患其方 法借鉴了t i l l e r w1 9 9 2 年在c a d 上发表的文章 4 5 】，文中指出，去除节点的计算 公式如下： 2 苫一 | 只 囊江大学蠖 学篷论文 霉t 。! ! _ = 二g 二! 噬，r 一嘏f s ( 2 ，一拱一s 一1 ) t 2 ； 0 【f 列：茎。盟1 ，f 2 r 一辫一s + 2 ) ，2 蔓，兰r s ， 。 1 d j 。 。 其中，0 【。= 鱼，k ：f ， 甜“m + i 一“ 2 ，2 ( 2 2 7 ) 将该方法与t 述p r a u t z s c h & p i p e r , c o h e ne ta 1 的方法就计髯的时闻笺杂度， 空问复杂度和升高阶时复杂度的上升速度比较，w 以得出该方法比较占优的结 论虽然这种算法是经典的b 样条曲线升阶算法乏，假跫由于仪考虑了端点插 饿b 样条，局限憔也是很屡然的 1 9 9 6 年，豢开爆发表了他对b 样祭曲线拜输的研究进展 5 7 ，5 9 ，提出了 b 样条曲线升阶的矩阵方法1 9 9 7 年，他又发表了探讨b 样条曲线升阶经典算法 巾存在问题及其聪决办法豹论文1 58 】 该方法从b 样条函数的性质着手，证明了用( 詹+ 1 ) 阶b 样条藻函数表示k 阶 b 棒条基涵数熬一个公式，提出了用予b 榉条蘧线舞验约筵终方法。 设女阶b 样条曲线的控制顶点为y ，( ，= 0 , 1 ，h ) ，节点矢量为t = f 朋“，则 b 徉条麴线豹方耩为： c + 1 ( t ) = 【v 】7 b ( f ) ，( 2 2 8 ) 黧中，i = k l ，七，h k + i ， v 。= f 。蠢。n b ( f ) = 【热l + 啦0 零。+ 2 j ) b i 。l ( 0 1 7 文中迸明了饕均匀b 样条基豳数满足以下恒簿式 5 7 】 曩一。( f ) 嚣卜1 1 0 ) 曰f ( r ) l 嚣 k a 0 i ( f ) a ( f ) a l l ( i ) a ( f ) a 。1 1 ( i ) a 女一j i ( i ) 式中，对于“= 0 , 1 ，k l ；v = 0 , 1 ，k ，有 邑吨。( f ) 1 ： i 舢| 囊 - - t t i j , b + i ( t ) i 2 。2 蛰 ) ) o 神洲；“ 口口 吼 浙江人学颂i ：学位论文 其中， a u , v ( f ) = ! 些塑 1 一y ，1 ( i k + u + 1 ) ( 一1 ) “ 坠塑 1 一y 。l ( f k + u + 1 ) i l ，u = v ，m 恒鼍舞高渺v j l ，u + 1 = ” 瓯y 。卜俺篇 y ，( ) ：盟，s ：o 1 ，七 t i + t t i 那么容易得到b 样条曲线的升阶公式： 其中 c i - * - ( f ) = 【矿 7 台( f ) 雪( f ) = 【丑i - k , k + l ( r ) b i h + i ( f ) - b i , k + l o ) 】7 ， i ，r ：三 r k a o ，o a l ，o a o ，i 口i i 0 l l a k i ，oa k i 1i 一1 i f 2 2 1 0 ) ( 2 2 1 1 ) 矿7 即为升阶后的b 样条曲线的控制顶点矢量，升阶后的控制顶点比升阶前的控 制顶点多一个该方法计算方便，易于实现，突破了以往算法仅就端点插值情况 作处理的弊端，是一种相对较好的方法 2 2 b 降阶算法 已有的b 样条曲线