（计算数学专业论文）基于双正交非均匀b样条小波的曲面光顺.pdf

i i ? “ 善 一 | 塑茎 a bs t r a c t t h e f a i r i n go fc u r v e sa n ds u r f a c e si st h eb a s i ca n d c o r eo ft h ec a g d ，a n di ti sa l l i m p o r t a n tp r o b l e m i nt h ed e s i g no ft h ec u r v e sa n ds u r f a c e s i nr e c e n ty e a r s ，t h em e t h o do f w a v e l e th a sb e e nw i d e l yu s e di nt h ef a i r i n go fc u r v e sa n ds u r f a c e s t h em e t h o do f w a v e l e th a st h ef e a t u r e so fd a t ac o m p r e s s i o na n dh i g he f f i c i e n c y , b u tm o s to ft h ew a v e l e t f a i r i n ga l g o r i t h m sa r ea i ma tu n i f o r ma n dq u a s i u n i f o r mb s p l i n ec u r v e sa n d s u r f a c e s i t c a n n tb eu s e dd i r e c t l yi nn o n u n i f o r mb s p l i n ec u r v e sa n ds u r f a c e s h o w e v e r , n o n u n i f o r mb s p l i n ei st h eb a s i co fn u r b sa n dt h ei n d u s t r ys t a n d a r do ft h ee x p r e s s i o n o fc u r v e sa n ds u r f a c e s 。t h i st h e s i sm a i n l ys t u d i e st h ef a i r i n gm e t h o do ft h en o n u n i f o r m b s p l i n es u r f a c e s t h em a i nw o r k sa n dc o n t r i b u t i o n sa r es u m m a r i z e da sf o l l o w s ： 1 w eu s et h eb i o r t h o g o n a ln o n u n i f o r mb s p l i n ew a v e l e t sf o rt h ed e c o m p o s i t i o no f b s p l i n e s u r f a c e s o nt h eo n eh a n d ，t h eg l o b a lf a i r i n go fs u r f a c e si sr e a l i z e dt h r o u g h r e m o v i n gs e v e r a ll e v e l so fd e t a i lp a r t sw i t hg i v e np r o p o r t i o nr a t h e rt h a nr e m o v i n gt h e w h o l ed e t a i lp a r t s ，s oi tc a np r e s e r v et h es h a p eo fs u r f a c e sd u r i n gf a i r i n g2 u sm u c ha s p o s s i b l e o nt h eo t h e rh a n d ，t h el o c a lf a r i n gi sr e a l i z e db ym o d i f y i n g t h ec o n t r o lp o i n t so f d e t a i lp a r t s t h em o d i f i e dc o n t r o lp o i n t so fd e t a i lp a r t sa r er e l a t e dt ot h eb a dk n o t sw h i c h a r el o c a t e dt h r o u g ht h ea n a l y s i st ot h ed e t a i lp a r t s 2 t h ew a v e l e tf a i r i n ga l g o r i t h mi se f f i c i e n tw i t hl i n e a rt i m ec o m p l e x i t ya n dc a l l c o m p r e s s ed a t ad u r i n gf a i r i n g ，b u t i tc a n n td e a lw i t hs o m ep r o b l e m so fc o n s t r a i n t s e n e r g yo p t i m i z a t i o ni s s t i l lw i d e l yu s e da m o n gal o to ft h em e t h o d si nt h ef a r i n go f b s p l i n ec u r v e sa n ds u r f a c e s e n e r g yo p t i m i z a t i o n c a r ld e a lw i t ht h ep r o b l e m so f c o n s t r a i n t s ，a n dc a nb eu s e di nl a r g ef l e x i b i l i t ya n dc l o s e b - s p l i n ec u r v e sa n ds u r f a c e s s ow ep r e s e n ta na p p r o a c ht h a tc o m b i n e st h ew a v e l e tf a i r i n gw i t he n e r g yo p t i m i z a t i o n t h es u r f a c ef a i r i n ga p p r o a c hw ep r e s e n t e di s r e a l i z e dt h r o u g ht h ed e c o m p o s i t i o no f b s p l i n es u r f a c ea n de n e r g yo p t i m i z a t i o n t h ee f f i c i e n c yo f t h ea l g o r i t h mi si m p r o v e db y c o m p r e s s i n gd a t at h r o u g h t h ed e c o m p o s i t i o no fb s p l i n es u r f a c e ，a n df a i r i n gd e t a i lp a r t s w i t hb o u n d a r yc o n s t r a i n t si sr e a l i z e dt h r o u g ht h ee n e r g yo p t i m i z a t i o n 3 w es t u d yd e e p l yi n t ot h es u r f a c ef a i r i n gw i t hb o u n d a r yc o n s t r a i n t s t h ea l g o r i t h m 、ep r e s e n tc a l lp r e s e r v et h eb o u n d a r yo ft h es u r f a c ed u r i n gf a i r i n g t h ea l g o r i t h mi s r e a l i z e dt h r o u g ht h ed e c o m p o s i t i o no fb s p l i n e s u r f a c e ，a n ds u r f a c ef a i r i n gw i t h i i i 栅06 舢0 删7，0舢8 ，婶 福建师范大学吴福鸣硕士学位论文 ? b o t m d a r yc o n s t r a i n t si sr e a l i z e dt h r o u g hp r e s e r v i n gt h ec o n t r o lp o i n t so ft h ed e t a i lp a r t s b o u n d a r y k e y w o r d s ：n o n u n i f o r mb s p l i n es u r f a c e ；b i o r t h o g o n a lw a v e l e t s ；e n e r g yo p t i m i z a t i o n ； b o u n d a r yc o n s t r a i n t s ；f a i r i n g i v 裂 ， ：+ 九 q 蜘 中文文摘 中文文摘 在产品外形的设计方面，设计者们常常注重的是产品外形的视觉效果，即在形状 大致相似的情况下，产品的几何外形应看起来美观、柔顺。从计算几何的角度看，即是 几何外形具有良好的光顺性，因此要消除一些不合人意的特征，但是在对物体进行 光顺的时候往往会使原来物体的形状发生改变，这就要求设计者们在光顺的同时又 能t e _ , 很z 好的保持物体的基本形状不变。本文主要针对非均匀的b 样条曲面光顺及曲面 的一些约束问题来尽可能地保持曲面的基本形状进行研究。 绪论中主要介绍了研究光顺的的现实意义及曲线曲面光顺的一般准则。简述了 国内外进行曲线曲面光顺的研究现状，介绍了曲线曲面光顺采用的常见方法，并分 析了各种光顺方法的优缺点及需解决的问题。 第一章主要研究了基于自适应的非均匀b 样条曲面的一种整体光顺方法和局部 光顺方法。首先介绍双正交非均匀小波，对比半正交小波，其在计算上更加简单， 而且其支承区间一般情况下比半正交b 样条小波小。而支承区间越小，在进行局部 修改小波系数时，局部性越好。因此这种双正交非均匀b 样条小波较适用于非均匀 b 样条曲面的光顺。 接着介绍非均匀b 样条曲线的双正交小波分解的方法，并将此方法推广到非均 匀b 样条曲面的双正交小波分解，采用类似经典的小波的节点保留方法，将曲面分 解为低分辨率部分和细节部分。 根据分解出来的低分辨率部分和各层的细节部分，将曲面的若干层的细节部分 按一定的比例适当丢弃后，再与曲面的低分辨率部分进行重构得到曲面的整体光顺。 在传统的小波光顺方法中通常是丢弃整个细节部分实现光顺，不能很好的保持曲面 的基本形状。本文根据误差要求适当的保留一些细节部分，在光顺的同时能较好的 保持曲面的基本形状不变。 根据在实际中可能只有局部不光顺，因此只须对曲面上某一个局部进行光顺， 而曲面的其余部分不改变，提出非均匀b 样条曲面的一种局部光顺方法。首先利用 小波表示的细节部分找出坏的节点，坏的节点是使细节部分的值达到最大的节点， 从而找出与坏节点有关的细节部分的控制顶点，通过对坏的节点有关的控制顶点进 行修改，达到曲面的局部光顺。 v 福建师范大学吴福鸣硕士学位论文 第二章将非均匀b 样条小波光顺与能量法光顺相结合，利用两种方法的优势进 行互补。一方面通过小波光顺压缩了数据，另一方面结合能量法可以处理一些约束 问题。首先介绍了非均匀b 样条曲面的双正交小波分解，将曲面分解为低分辨率部 分和细节部分，并给出细节部分的表示形式。 介绍了用能量法进行曲面光顺时目标函数的设定，主要是通过光顺项和逼近项 两项加权平均得到，以及使能量函数达到最小时的计算方法。同时介绍了用能量法 处理曲面条件约束的方法，并分析能量法光顺的优劣。 结合多分辨率小波和能量法的思想，分别对b 样条曲面进行粗光顺和细光顺。粗 光顺中是在一定误差范围内对原始曲面进行小波分解，通过滤掉细节部分保留低频 部分，这样曲面的控制顶点可以得到压缩。在细光顺中，由于小波光顺后的曲面己 具备一定的光顺效果，直接修改曲面的控制顶点会改变曲面的基本形状，因此只对 曲面的细节部分进行条件约束处理的能量法光顺，这时候数据得到了压缩，克服了 用能量法在处理控制顶点较多时运算效率低的劣势。 给出了非均匀b 样条曲面小波分解时节点向量的选取方法，最后给出了曲面误差 的计算方法及容许误差的分配方法。 第三章提出了一种保持边界约束的非均匀b 样条曲面的小波光顺方法。针对在对 曲面进行小波光顺时要始终保持原曲面的边界不变而提出的方法。首先通过非均匀b 样条小波对曲面进行分解，得到曲面的低分辨率部分和细节部分。 给出保持曲面边界不变的处理方法，将每一层细节部分的最外一层控制顶点保 持不变，其余的控制顶点设为零。再与曲面的低分辨率部分进行重构得到光顺曲面。 这样既可以丢掉曲面的一些细节部分实现曲面的光顺，同时又能保持曲面的边界不 变。这与第二章所采用的能量法保持条件约束不同，且本方法是研究在小波光顺的 时候始终保持与原来曲面的边界不变。 在小波分解时对节点向量的选取所采用的方法与前两章有所不同，在这章的节 点选取方法是通过曲率函数找出坏的节点，并删除这部分坏的节点来实现。最后给 出了曲面误差的计算方法及容许误差的分配方法。 第四章总结了全文的主要创新点及取得的成果，指出今后在本研究方向进一步 开展研究工作的设想、展望、建议以及尚待解决的问题。 v i 0 r 一 目录 九 h “ 目录 中文摘要i a b s t r a c t i i i 中文文摘o 。v 目录 绪论二1 1 岁匕顺准贝! l 。1 。 2 光顺研究现状。2 3b 样条曲线曲面7 4 本文的主要的研究内容。- 9 一 第一章基于自适应的非均匀b 样条小波的曲面光顺1 1 1 1 双正交非均匀b 样条小波一1 1 1 2 非均匀b 样条曲线曲面的双正交小波分解- 1 3 1 3非均匀b 样条曲面的光顺- 1 5 二絮。、? 1 4 实验实例。- 1 9 - 1 5 本章小结- 2 2l ：、，。 第二章基于能量优化与非均匀b 样条小波的曲面光顺- 2 3 - 2 1 非均匀b 样条曲面小波分解：一2 3 2 2 带条件约束的能量法曲面光顺- 2 4 - 2 3 能量优化与非均匀b 样条小波的曲面光顺2 5 - 2 4 实验实例。- 2 8 - 2 5 本章小结- 3 2 一 第三章保持边界约束的非均匀b 样条小波的曲面光顺- 3 3 3 1 非均匀b 样条曲面小波分解一3 3 - 3 2 保持边界约束的曲面光顺一3 4 3 3 实验实例一3 7 3 4 本章小结- 4 0 一 第四章结论。- 4 1 一 v i i 福建师范大学吴福鸣硕士学位论文 _ 一i - _ - _ 一_ 一_ - _ _ _ _ _ _ l - - - _ _ _ l _ - _ - _ _ _ _ i l - - - i - l _ _ l - _ _ _ _ _ - - _ _ _ _ _ _ _ - 一 参考文献- 4 3 - 攻读学位期间承担的科研任务与主要成果- 4 7 一 致谢”- 4 9 - 个人简历。5 卜 v i i i 0 h 绪论 绪论 随着现代工业和计算机的飞速发展，在飞机、船舶、汽车及家用电器等产品的 设计与制造过程中，人们对产品的外形提出了更高的要求。也就是说，产品外形设 计应同时考虑承力合理性和视觉美观性两大因素；它涵盖空气动力学、流体力学、 摩擦学、传热学、几何学以及美学、心理学等多个交叉学科。如果产品的外形不光 顺，则产品就不能满足其实用、实战要求。因此产品的设计与制造过程中，产品的 曲线曲面光顺是一个重要指标。而综合上述各方面要求的一种新技术曲线曲面光顺 技术就这样应运而生的。曲线曲面光顺是消除几何造型中一些不合人意或不合设计 者要求的曲线曲面特征，比如在曲线上存在一些尖点和过多的拐点，在曲面有皱纹 和一些比较粗糙的地方。而且在几何造型中，往往需要通过对一些数据点反算出控 制顶点来构造曲线曲面。但在实际造型中，对实体进行扫描测量出来的数据点难免 存在一些测量误差或精度误差，如果错误存在，这样构造出来的曲线曲面光顺性较 差，得不到设计者想要的理想结果，因此需要对曲线曲面进行进一步的光顺处理。 1 光顺准则 由于曲线曲面光顺性涉及众多学科，并受主观因素和以往设计思路的影响，加 之不同的实际问题又对曲线曲面光顺性有不同的要求，使得人们对曲线曲面光顺性 的认识不尽一致，对光顺性没有一个统一的标准。尽管如此，国内外学者在定义曲 线曲面光顺的准则方面【】还是在一定程度上达成了共识。曲线的光顺准则是曲线是 否是二阶几何连续，是否不存在多余的拐点及奇点，曲率变化是否比较均匀，应变 能是否比较小，而曲面光顺的准则通常是根据曲面上的关键曲线( 如 ，1 ，方向的参 数线，或者曲面与平行于坐标平面的一系列平面的截面线等) 是否光顺以及曲面的 曲率( 主曲率、高斯曲率、平均曲率等) 的变化是否均匀等来判定，具体规定如下： 关键曲线( 如飞机或船舶曲面的骨架线) 光顺； 网格线无多余拐点( 或平点) 及变挠点； 主曲率( 低次曲面) 在节点处的跃度和足够小； 弹性薄板的应变能较小； 高斯曲率变化均匀。 上述光顺准则的规定仍然只是对曲线曲面光顺的一个大概的描述，光顺其实既 福建师范大学吴福鸣硕士学位论文 包括有较严格的数学定义的参数连续性和几何连续性，同时也侧重审美学、加工制 造、力学性能等功能性要求，很难给出一个确切的概念来定义。而且在实际中还要 结合不同的要求采用不同的光顺准则，因此很难给出一个全面的，系统的定义。 2 光顺研究现状 曲线曲面的光顺有两种形式，分为交互式光顺和自适应光顺，一般自适应光顺 可以较快的得到光顺的效果，但是最后得到的效果有些细节部分可能与设计者的要 求仍有些差别，这些差别就需要采用交互式的方法进行修改，但是交互式是一种凭 经验操作的行为，而且时间耗费也较多。 到目前为止已提出了许多光顺方法：最早f a d n 等【5 。l j 提出的通过“节点删除与 插入 对b 样条曲线进行光顺的方法，其中节点删除与插入法是通过找出曲率变化 最大的节点，用节点删除与插入来光顺曲线的局部光顺法，它具有局部性、速度快 和修正力度大的特点，但是当曲线中出现的“瑕点较多而且连续出现时，光顺的 效果通常不是很理想。还有优化节点向量的光顺方法【1 2 1 ，以及一些选点修改法 i l l 4 ， 它是通过修改坏的顶点使得三次参数样条曲线在这些坏的顶点处的三阶左右偏导的 差为零，以此达到光顺。还有k j e l l a n d e r 等 1 5 j 6 提出的用三次参数样条曲线和双三 次样条曲面的局部光顺方法；用曲线曲面的曲率进行光顺的方法【1 7 。18 】；h o s a k a 等【1 9 。4 】 提出的用于空间三次参数样条曲线光顺和网格光顺的能量法；l o t t 等 3 5 - a 8 1 提出的b 样条曲线曲面光顺的能量法；还有基样条法【3 9 】等。总的来说光顺曲线曲面的这些方 法可归为两大类：1 ) 整体光顺法。整体光顺法采用整体光顺准则，光顺的曲线曲面针 对的是整个参数区间的全部型值点。如能量法等，是将光顺目标函数设为包含型值 点逼近项和光顺项两部分加权平均的函数，并求目标函数的极小化问题。2 ) 局部光 顺法。局部光顺法采用局部光顺准则，光顺的曲线曲面针对的是部分参数区间的部 分型值点。如基样条法，节点插入和删除法等都是局部光顺法，是在假设大多型值 点都是好的或比较好的基础上，通过某种方法把少数坏点挑出，并逐个给予修改达 到光顺。但这种方法在坏点比较多的时候，往往不好处理，时间耗费较多。以上都 是比较常用的光顺方法，但是实质上它们相差不是很大，有几种方法之间有类似的 情况或有着某种联系。一些智能算法也相应的用到曲线曲面的光顺上，比如甘屹【4 3 】 等人给出了基于遗传算法的曲线曲面光顺大大提高了计算的效率。还有近几年多分 辨率的小波光顺算法 4 4 4 7 】得到了广泛的应用，曲于小波光顺具有数据压缩的作用， 当控制顶点较多的时候可减少数据量，这样可以大大减少存储空间，提高运算效率， 绪论 但是小波光顺法无法处理边界约束问题。 曲线曲面光顺处理是计算机辅助几何设计中的非常重要的一个课题，多年来受 到人们越来越多的关注。国内外许多专家和学者对这方面做了大量的研究，取得了 很多确实有用的方法，所采用的方法主要有最z j x - 乘法、能量法、圆率法、基样条 法、遗传算法和小波光顺方法等，下面对这几种方法进行概述。 2 1 最小二乘法 对曲线曲面光顺处理的研究最早大约始于6 0 年代，最小二乘法在当时是很有影 响，很常用的一种光顺方法。它的主要思想如下：对于在平面上给定了的一组用坐标 表示的n 个型值点列口，( x p y ，) o = 0 ，1 ，刀) ，首先在x 轴上的b 】区间内进行相应 的分割，在此分割上构造一个三次样条函数曲线p ( t ) 使其逼近给定的型值点，再选 取一定的目标函数，目标函数采用样条的剪力跃度的平方和。光顺的目的是使该样 条的剪力跃度的平方和最小。还应使光顺前后型值点的偏离尽可能的小，因此目标函，釜。o 数定义为： e = 口n = l 刃+ 窆j f p i q j | | 2 嘉， z 垮1 t 挚 式中4 = f 鱼争生一生亏h l ，为曲线p ( r ) 在p i 处的剪力跃度，t ：| fp ，一p 卜j | f 为弦长， i + 1f ： k ，为曲线p ( ，) 在p ，处的曲率，通过调整目标函数中的权因子，使其达到理想的光顺 效果。当甜取较大的数时，剪力跃度就较小，曲线较光顺。但光顺后的曲线上的点办 与原型值点吼的偏离可能较大，曲线的逼近性较差。反之，当取较大的数时，光 顺后的曲线上的点p i 与原型值点吼的偏离可能较小，曲线的逼近性较好，但剪力跃 ( 度 z ) 可能较大，曲线的光顺性较差。 而从式子可以看出剪力跃度的平方和与曲线的曲率变化相关联，因此最小二乘 法可以使曲线的曲率变化均匀化。这是整体光顺的方法，但是这种方法有一定的缺 陷：当型值点过多时，所解系数矩阵的病态程度将急剧增大，会引起计算的不稳定， 得出的曲线不能达到理想的光顺效果。 福建师范大学吴福鸣硕士学位论文 2 2 能量法 能量法【1 9 , 3 5 1 的基本思想方法跟最小二乘法一样，是将曲线曲面的光顺问题转化 为最小化问题进行求解即在光顺时将所有控制顶点均作为未知量，通过求最小化 问题的解来确定。不同之处在于目标函数中的剪力跃度部分改成样条的能量部分。 光顺的目的是使该样条的应变能最小，这是整体的光顺方法。但是由于应变能与曲 线的绝对曲率或者与曲面的主曲率相关联，因此能量法会使曲线的曲率变小，曲面 的主曲率变小。导致光顺的曲线都将趋于向直线变化，曲面将趋于平面化，并不能 使曲线的曲率或曲面的主曲率变化均匀。 ( 1 ) 能量法 能量法【1 9 p 5 1 是基于能量极值原理给出的种包括光顺空间曲线和大挠度曲线 在内的光顺方法，它的力学模型很直观。设给定通过型值点列p 。( f = o ，1 ，船) 的曲 线为阿。( t ) ，光顺后的曲线为吲s ) ，型值点q ，( i = 0 , 1 ，以) ，d o ，d ，分别为光顺前 后的控制顶点。把吲s ) 看作过型值点吼的样条弹性线，在型值点p ，与吼之间挂一 条弹性系数为屈的小弹簧，使q ，靠近a ，因此，包括样条和小弹簧在内的整个系统 的能量为： p 掳i = l 弦幽+ 圭翱陬埘 式中，口e o2 ，盔为曲线吲s ) 的曲率。该式为光顺的目标函数，求吼使得e = r a i n 即得光顺后的曲线开( t ) 。 ( 2 ) 离散能量法 给定型值点列型值点列p ，o = 0 , 1 ，刀) ，将应变能陆2 幽离散为 薯志8 e l + 1 - - e i 0 2 其中：巳：嬖 盟为单位弦向量，爿ip f p h0 为弦长，离散能量法的目标函数 成为： 绪论 p 口崭i _ _ l _ 。i i e i + l - e t 2 嘻砌卅 ( 3 ) 曲面的网格能量法 设p u = 0 ，l ，刀，_ ，= 0 ，l ，聊) 为光顺前曲面so ：开h v ) 的型值点或者控制网 格顶点，吼，( f = 0 , 1 ，力，= o ，1 ，m ) 为光顺后曲面s ：产r ) 的型值点或者控制网 格顶点，网格能量法的目标函数为： e _ 口( 圭弦出+ m 弦出) + 屈，川p 栌8 2 ， l 酬 j 暑0 l ，j 到 t 为v 曲线fr ( u ，v ) 的曲率，尼，为u 曲线阿( u v ) 的曲率。离散的方法类似曲线的 情形。 2 3 选点修改法 选点修改法适用于曲线曲面在大多数型值点处是好的或比较好，而只在少数型 值点处不光顺，这样可以大大节省运算量选点修改法的过程是：先按照某种方法 逐次找出坏点，在对坏点进行修改因此选点修改法是一种局部光顺方法。 - f 舷：t 这边主要介绍两个比较典型的选点修改法，一个是圆率法和基样条法，在文献 【3 】中提出了圆曲率光顺的概念。圆率法的基本思想是为了使曲线的曲率变化均匀而 达到曲面光顺。对于平面上给定的型值点p ，和两边界切向m 。，m 。，过相邻三点b ， p h ，p m 所作圆的相对曲率尼称为在点p ，处的圆率。它与一般的选点修改法不同 的是它不需要先建立插值曲线，而是从离散型值点分布的几何位置出发直接判断型 值点列的光顺性，再找出“坏点”进行修改，这种光顺法经过粗、精光顺两过程。 基样条法【3 9 1 跟圆率法一样，都属于选点修改法。它也包括粗光顺和精光顺两个 阶段，基本思想大致如下：对于给定的平面型值点a ( 一，y ，) ( 待0 , 1 ，挖) ，按照基 样条表示构造插值三次样条函数p ( f ) ，它是满足c2 连续条件的。计算p ( t ) 在每个 节点以处的二阶导数即可看作曲线的曲率向，并作曲率的符号序列 s i 缈( 屯) ) ，凡使 序列连续变号的点，即满足条件毛一。k ， o r k i + 。吃 ，同样找出使其连续变号 的点，即满足条件色。a k , o 且t + 。忽 0 的点为坏的点，这是精光顺阶段。这种 方法挑出来的坏点比较准，好点又不受破坏，修改能力比较强。但是对于坏点较多 的时候，往往不容易处理好，即使最后也能光顺，但耗费时间比较多。 2 4 遗传算法 基于遗传算法的曲线曲面光顺h 叫3 1 ，以能量和曲率作为双重条件来考察曲线和 曲面的光顺性问题所以遗传算法也是基于能量法原理，是一个最优化问题。然而 遗传算法不能直接处理有约束的问题，解决方法之一是应用模糊罚函数将有约束多 目标优化问题转化为无约束多目标优化问题，采用遗传算法对曲线进行光顺，得到 了最优解；并将该光顺算法进一步推广到曲面的光顺。它避免了只用能量法带来的使 曲线曲趋于直线化的，曲面趋于平面化的缺点，同时遗传算法是一种随机的全局多 点搜索算法，具有隐含并行性的特点。但是遗传算法比较复杂，计算量大，所占内 存较大。 2 5 多分辨率的小波光顺算法 近年来小波分析在计算机图形学中获得了越来越广泛的应用，特别在曲线曲面 光顺中也得到了很好的应用。小波光顺方法的原理是通过小波分解将曲线曲面分解 为低分辨率部分( 低频部分) 和细节部分( 高频部分) ，低分辨率部分是由原曲线曲面去 除高频部分得到的，外观上相对原曲线曲面较光顺。而且分解的次数越多，去除的 高频部分越多，得到的曲线曲面越光顺。由于低分辨率部分能够保留原曲线曲面的 整体形态，因此可以通过丢弃曲线曲面小波分解后的细节部分来实现曲线曲面光顺。 多分辨率的小波光顺法还有一个数据压缩的特点，由于低分辨率部分由较少的控制 顶点和b 样条基函数表示，因而可用于数据压缩。 1 9 9 8 年，孙延奎，朱心雄m 】提出小波光顺法，其原理是通过小波分解后，尽可能 的剔除原曲面的高频部分，使光顺后的逼近曲面比较好的保留原曲面的低频部分， 因此也就较好的保持了曲面的总体形态。而且利用小波分解进行光顺，有数据压缩 的作用，当控制顶点较多的时候可减少数据量，这样可以大大减少存储空间，提高 运算效率。文献 4 7 给出了基于准均匀b 样条小波的曲线的整体和局部光顺方法，通 过修改细节部分的全部或部分控制顶点达到曲线的整体或局部光顺。但是目前的小 r r 绪论 、1 ：， 波光顺算法多是对于均匀或准均匀的b 样条曲线曲面的小波光顺，有一定的局限性。 尽管在文献 4 5 中孙延奎，朱心雄着重研究具有任意节点矢量的端点插值b 样条曲线 曲面的多分辨率表示及其在b 样条曲面光顺中的应用。提出了利用准均匀b 样条曲线 曲面逼近具有任意节点矢量的端点插值b 样条曲线曲面的方法，从而将原曲线曲面的 多分辨率表示转化为准均匀b 样条曲线曲面的多分辨率表示，但是这对于非均匀b 样 条曲线曲面光顺就增加了逼近环节，存在逼近误差，对曲线曲面光顺有一定的影响， 因此仍有一定的局限性。 我们可以看出，许多年来，人们不断地探索方便、灵活、实用的曲线曲面光顺 方法。从最早提出的最小二乘算法到至今，曲线曲面光顺的算法日新月异，大量新 理论和新算法被不断的提出。遗传算法、小波分析、模糊理论、规划理论【4 8 。5 0 】等一 些更加有效、更加快速的曲线曲面光顺算法被广泛的研究。但人们并不满足于现状， 仍在继续探索新的光顺方法。目前，这些技术还处于研究阶段，相信在不远的将来， 它们会得到广泛的应用。 3b 样条曲线曲面 b 样条有多种等价定义。在理论上多采用截尾幂函数的差商定义。本文采用标 每 准算法的德布尔和考克斯的递推定义【2 】，又称为德布尔一考克斯递推公式。这个著伊 名的递推公式的发现是b 样条理论最重要的进展之一。它归功于德布尔，考克斯与 曼斯菲尔德。b 样条是由一组称为节点向量的非递减的参数序列u = k 。，甜l ，一，“。诎+ ，j 所决定的k 次的分段多项式。定义如下： j ，。( 甜) = 【1 。, ，若其u 他i z f 甜，+ 1 2 嚣姒) + 瓦d i + k + i 1 一u f + l 规定石0 = o n i k ) 的双下标中第二下标庀表示次数，第一下标f 表示序号。该递推公式表明， 欲确定第f 个七次b 样条m k ) ，需要用到“，“m ，“m + 。共尼+ 2 个节点。称区间 函，甜m + 。】为i 。 ) 的支承区间，而在区间外i k ( u ) y o。m t ) 的第一下标等于其 福建师范大学吴福鸣硕士学位论文 支承区间左端节点的下标。即表示该b 样条在参数“轴上的位置。 给定，z 个控制顶点tu = 0 , i ，z ) ，和参数材的次数七以及节点矢量 u = k ，材1 ，一，甜枞+ 。】就定义了一条b 样条曲线，其方程为 ， ) = 4 m ，。 ) ，甜函。，甜槲】 其中，b 样条基i ，t k ) ( f = 0 , 1 ，船) 是由节点矢量u 按德布尔一考克斯递推公式决 定。 b 样条曲线按节点矢量中节点分布情况不同可以划分成4 种不同类型：均匀、 准均匀、分片贝齐尔与非均匀b 样条曲线。 同样给定沏+ 1 ) + 1 ) 个控制顶点d u ( f = o ，1 ，m ；j = 0 , 1 ，刀) 的阵列，构成 一张控制网格。又分别给定参数材与v 的次数后与，和两个节点矢量 u = k ，甜l ，甜册仇，】与y = k ，1 ，l 一，1 ，枞+ 1 】。就定义一张尼，次张量积b 样条曲面。 其方程为： mn s ( 甜，d = 叱，j 0 厩，0 ) ，“k ，“州l v h ，i n + ，】 i - 0j = o 其中，b 样条基i ，k ( 甜) o = 0 , 1 ，z ) 与j j ( u = 0 , 1 ，刀) 分别由节点矢量u 与v 按德布尔一考克斯递推公式决定。 同样，b 样条曲面沿任意参数方向所取节点矢量不同可以划分成4 种不同类型： 均匀、准均匀、分片贝齐尔与非均匀b 样条曲面。沿两个参数方向也可以选取不同 类型。 对于开曲面，本文节点矢量的两端都取重复度后+ 1 ，以使具有同贝齐尔曲面的 端点几何性质，便于对曲面在边界端点的行为有较好的控制。 对于任意分布的节点矢量，只要其节点系列非递减，两端节点重复度尼+ 1 ， 内节点重复度尼都可选取。这样的节点矢量定义了一般非均匀b 样条基。采用均 匀与准均匀b 样条基定义的b 样条曲面等于放弃定义b 样条曲线中由节点矢量提供 的自由度，放弃了由非均匀节点矢量定义的可供选择的丰富的曲面形状。与此作为 代价换取计算上的某些简单性是不合理的。本文讨论的主要是非均匀b 样条曲面， 绪论 它更具普遍性，而均匀与准均匀b 样条曲面都只是特殊的类型。 4 本文的主要的研究内容 本文对计算机图形学中曲线曲面的光顺问题进行了深入的研究，提出了基于双 正交非均匀b 小波小波的光顺方法，以及结合小波光顺法和能量法两种方法的优点 提出的一种新的光顺方法，最后考虑保持曲面边界不变的情况提出一种保持边界的 小波光顺方法。 本文分为以下几个部分，各章内容安排如下： 绪论：这部分主要介绍本论文研究光顺的的现实意义及曲线曲面光顺的一般准则。 简述了国内外进行曲线曲面光顺的研究现状，介绍了曲线曲面光顺采用的常见方法， 并分析了各种光顺方法的优缺点及需解决的问题。 第一章：本章提出非均匀b 样条曲面的一种整体光顺方法和一种局部光顺方法。首 先利用双正交非均匀b 样条小波，对非均匀b 样条曲面进行小波分解。然后将若干 层细节部分按一定的比例适当丢弃后实现曲面的整体光顺。另一方面，利用小波表 示的细节部分找出坏的节点，从而找出与坏节点有关的细节部分的控制顶点，通过 对这些控制顶点进行修改，达到曲面局部光顺的目的。 第二章：本章结合非均匀b 样条曲面的小波光顺法以及能量法的两者的优点提出对f 曲面进行约束光顺的算法。通过小波分解实现了数据的压缩，减少运算量，提高算 法的效率，同时结合能量法对分解后曲面的细节部分进行条件约束光顺处理：一 第三章：本章提出一种保持边界不变的光顺方法。通过非均匀b 样条曲面的小波分 解，把曲面分解为低频部分和高频部分，然后保存细节部分的边界控制顶点实现对 边界保持不变的曲面光顺。 第四章：对本论文工作进行总结，并提出了进一步的的研究方向。 福建师范大学吴福鸣硕士学位论文 1 0 - 第一章基于自适应的非均匀b 样条小波的曲面光顺 1 ； 1 第一章基于自适应的非均匀b 样条小波的曲面光顺 曲线曲面的光顺处理一直是c a d c a m 中非常重要的问题，特别是在工业设计和 自动化设计领域中有很大的应用。近年来，国内外许多学者对其进行了大量研究， 提出了许多光顺方法。在这些方法中，根据光顺准则和修改型值点的数目，大体可 以分为两类：( 1 ) 局部光顺法，即每次仅修改少数型值点，如各种选点修改法【6 1 3 , 1 4 ， 选点修改法就是逐次找出不光顺的型值点，对其进行修改。( 2 ) 整体光顺法，即每 次修改全部型值点，比如能量法【1 5 , 3 6 ，该方法将光1 , 颐t ；- j 题转化为包含型值点偏差和 光顺两部分加权平均的目标函数的极小化问题。整体光顺法具有较好的整体光顺效 果，但计算量大，速度较慢；而局部光顺法具有计算量小，速度较快的优点。 近几年出现的利用多分辨率的小波光顺算法 4 4 舶】是针对高频噪声主要集中在曲 面小波分解的细节部分时所采用的一种光顺方法，它通过修改小波的细节部分实现 曲面的光顺，能较好地达到曲面的光顺。由于b 样条小波具有局部性的优点，可以 对整张曲面的每一个局部实现光顺，因此将小波用于曲面光顺有着先天的优势。现 有的小波光顺方法中，文献 4 4 - 4 6 利用准均匀b 样条小波分解三次准均匀b 样条曲 线或曲面，通过丢弃整个细节部分实现光顺，是一种整体光顺的方法。实际应用中 可能只对曲面上某一个局部进行光顺，而曲面的其余部分不改变。上述光顺方法都 是针对准均匀b 样条曲线曲面的，不能直接应用于非均匀b 样条曲线曲面。而非均 匀b 样条是n u r b s 的基础，后者是自由曲线曲面表示的工业标准。目前，关于非均 匀b 样条曲线曲面小波光顺方法的研究还很有限。文献 5 1 根据半正交非均匀b 样 条小波，确定光顺方向后通过丢掉全部的细节部分达到整体光顺，以及通过光顺度 量值确定坏的节点对，去除该节点达到局部光顺。本章是在文献 4 7 基础上，利用 文献 5 2 提出的双正交非均匀b 样条小波，给出了非均匀b 样条曲面的一种整体光 顺方法和一种局部光顺方法。通过将曲面的若干层细节部分按一定的比例适当丢弃 后实现曲面的整体光顺。另一方面，利用小波表示的细节部分找出坏的节点，从而 找出与坏节点有关的细节部分的控制顶点，通过对坏节点有关的控制顶点进行修改， 达到曲面的局部光顺。 1 1 双正交非均匀b 样条小波 1 1 1 非均匀b 样条小波分解 福建师范大学吴福鸣硕士学位论文 i _ 一一_ _ - _ _ l _ l _ i _ - l - _ _ _ _ _ l _ _ - l - - _ _ _ _ 目_ _ _ l - - - _ l - _ - l - _ _ _ - - - _ l - l 一 首先给出k 次双正交非均匀b 样条小波的有关结果p z ”j 。给定区间 口，b ，令 t ocr lc 为嵌套的节点向量序列，其中霉= 量咖，l ，f “肿+ 。j ，i = 0 ，l 1 ，满足 下列条件： a = t i 。= = t i ，女 t ，t + l t + 2 s t 一。 i j i ，十l2 = f f 一，+ + l2 b t o 诎+ l ，j = 0 , 1 ，n t ，n j k 设 u b 、1 l - j j l ，= 。是节点向量正上的尼次规范b 样条基，k = 删门，。o ) ，m - o ) ，j ，怫g ) ， i = 0 , 1 ，则有v ockc 。 设形是k 在形+ 上的补空间，即i + l = k + i v , ，u o ) ) 埘二。是形的基，其中 聊，+ = 船川，则沙u o ) 是非均匀b 样条小波。令西，= 【，。，一j ， y ，：眇u ，缈f t 2 帆，嘶j ，待0 , 1 ，则存在( 心f + l + 1 ) ( 刀，+ 1 ) 阶矩阵丑和( 刀j + i + 1 ) m r 阶 矩阵q j 使得 陋，鬈】= 蚝陋q ，】， ( 1 1 ) 其中只，q ，称为b 样条小波的重构矩阵。令阮 q ，- i - 斟 得到 柏引嘲，其帕+ 1 ) ( t + 1 ) 阶矩阵4 概m “) 阶矩阵噩称为b 样条小波的分解矩阵。 对任意z + ，= 咖j + l d j + 1 k ，通过分解矩阵4 和e ，z + 。可以分解为低分辨率部 分z =