（应用数学专业论文）b样条曲线和圆域b样条曲线数据缩减的研究.pdf

福建师范大学硕士学位论文 摘要 b 样条曲线曲面是众多计算机辅助设计( c a d ) 系统中形状描述的基本工具， 它在各c a d 系统中的数掘存储、误差表示和数据交换，一直是计算机辅助几何设计 ( c a g d ) 研究的重要内容。本文对b 样条曲线的数据缩减( 包括降阶和节点去除) 以及圆球域曲线曲面造型技术展开深入研究，其主要结果概括为以下几点： 1 对已有的b 样条曲线的降阶算法和节点去除算法进行了总结与分析，指出 这些算法的一个不足之处是无法同时降阶和节点去除，在既需要降阶又需 要去除节点的实践中，只能将降阶和节点去除分开进行，这样就增加了累 积误差。本文将b 样条基转换矩阵理论与最d - - 乘理论相结合给出了一 种降阶和节点去除的统一方法，只需通过简单的矩阵计算即可同时降多阶 和去除多个节点，易于实现，可以减少累积误差。该统一方法还可用于单 独降阶或节点去除。当用于单独降阶时可一次降多阶，当用于单独节点去 除时可一次去除多个内节点。该统一方法可使逼近曲线保两端点值不变。 通过大量的实例验证了算法的正确性，并与以往的降阶和节点去除算法进 行了比较。其结果可望广泛应用于减少曲线存储的信息量以及不同c a d 系 统的数据交换等方面。 2 总结与分析了基于误差表示的曲线曲面造型技术的研究现状，在此基础上， 基于圆域算术，将圆域b 样条曲线的概念引入到c a g d 中来，讨论了它的 些基本| 生质和基本算法。指出圆域b 样条曲线与区间b 样条曲线相比， 除了同样可以表示一条b 样条曲线的误差范围外，还具有存储的信息量小 猷及在旋转变换下保持误差域不变等优点。 3 研究了圆域b 样条曲线的节点去除问题，即用去除一个节点后的圆域b 样 条曲线包住原曲线，采用拟线性规划和最佳逼近两种方法，均给出了该问 题的显式解。给山了相应的计算实例，并比较了两种方法的逼近误差。该 节点去除算法能在节点去除的过程巾保留原曲线的误差信息和逼近误差信 息，其结果有利于随后的几何操作( 如曲线求交等) 。 4 研究了圆域b 样条曲线的降阶问题，即用降一阶后的圆域b 样条曲线包住 原曲线。给出了圆域b 样条曲线可精确降一阶的充要条件和精确降阶公式， 并给出了整体法和分段法这两种降阶逼近算法。通过实例验证了两种算法 的正确性，并刘它们的逼近误差进行了比较分析。该降阶算法能在降阶的 过程中保留原曲线的误差信息和逼近误差信息，其结果有利于随后的几何 操作。 关键词b 样条曲线，数据缩减，降阶，节点去除，b 样条基，圆域b 样条曲线 塑垄堑薹奎兰堡主兰垡笙兰 a b s t r a c t b s p l i n ec u r v e sa n ds u r f a c e s a r eb a s i cf i g u r er e p r e s e n t a t i o nt 0 0 1o fm o s to ft h e c o m p u t e ra i d e dd e s i g n ( c a d ) s y s t e m s t h ed a t as t o r a g e ，e r r o rr e p r e s e n t a t i o na n dd a t a e x c h a n g eo f t h e mi nt h ec a d s y s t e m s ，a r ei m p o r t a n ti nt h er e s e a r c ha r e ao f t h ec 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 a g d ) t h i sp a p e rs t u d i e si n d e p t ht h ed a t ar e d u c t i o no f b s p l i n ec u r v e s ( i n c l u d e sd e g r e e r e d u c t i o na n dk n o t r e m o v a l ) a n dd i s k s p h e r ec u r v e sa n d s u r f a c e sm o d e l i n gt e c h e n o l o g y , t h em a i nr e s u l t sa n da r es u m m e du pa sf o l l o w s ： 1 t h i sp a p e rs u m m a r i z e sa n da n a l y z e st h ee x i s t e dd e g r e e r e d u c t i o na l g o r i t h m sa n d k n o t r e m o v a la l g o r i t h m s p o i n to u to n eo ft h ei n s u f f i c i e n c eo ft h ea l g o r i t h m si s t h a t ，t h e yc a n ts i m u l t a n e o u s l yr e d u c ed e g r e e sa n dr e m o v ek n o t s ，i nt h ep r a c t i c e w h i c ht h e d e g r e e r e d u c t i o n a n dk n o t r e m o v a la r eb o t hn e e d e d ，t h e d e g r e e r e d u c t i o na n dk n o t r e m o v a lc a no n l yb e e x c u t e ds e p a r a t e l y , t h u st h e a c c u m u l a t ee r r o r sw i l lb ei n c r e a s e d t h i sp a d e rc o m b i n et h eb s p l i n et r a n s i t i o n m a t r i xa n dt h e 1 e a s t s q u a r et h e o r y , p r o p o s e au n i f o r n lm e t h o dt o d e g r e e r e d u c t i o na n dk n o t - r e m o v a lo fb - s p l i n ec u r v e s t h i sm e t h o dc a nr e d u c e m u l t i d e g r e ea n dr e m o v es e v e r a lk n o t so f t h eb s p l i n ec u r v e ss i m u l t a n e o u s l yb y s o m ec o m p u t a t i o no fm a t r i x i ti ss i m p l ea n dc a l lb ee a s i l yr e a l i z e da n dc a n r e d u c et h ea c c u m u l a t ee r r o r st h eu n i f o r i l lm e t h o dc a nb eu s e dt os i n g l yr e d u c e t h ed e g r e e so rs i n g l yr e m o v et h ek n o t s w h e nu s e dt od e g r e e r e d u c t i o n i tc a n r e d u c em u l t i d e g r e ew h e nu s e dt ok n o t r e m o v a l ，i tc a nr e m o v es e v e r a lk n o t sa t o n et i m et h ea p p r o x i m a t ec u r v e so ft h eu n i f o r n lm e t h o dc a ni n t e r p o l a t et h e e n d p o i n t so ft h eo r i g i n a lc u r v e s al o to fe x a m p l e sa r ep r o v i d e dt ot e s t i f yt h e f e a s i b i l i t yo ft h em e t h o d ，a n dc o m p a r ew i t hs o m et h ee x i s t e dd e g r e e r e d u c t i o n a n dk n o t r e m o v a ia l g o r i t h m t h i sm e t h o dm a yb eu s e di nt h ed a t ar e d u c t i o no f b s p l i n ec u r v e sa n dt h ed a t ae x c h a n g eo f d i f f e r e n tc a d s y s t e m s 2 t h er e s e a r c ho fc u r v e sa n ds u r f a c e sm o d e l i n gt e c h e n o l o g yb a s eo ne r r o r r e p r e s e n t a t i o na r es u m m a r i z e da n da n a l y z e d b a s eo nt h ed i s ka r i t h m e t i c ，t h i s p a p e rp r o p o s e sd i s kb - s p l i n ec u r v e s ，a n dd i s c u s s e st h e i rs o m eb a s i cp r o p e r t i e s a n da l g o r i t h m s w h e nw ec o m p a r et h ed i s kb - s p l i n ec u r v e sw i t hi n t e r v a l b s p l i n e sc u r v e s ，i ta l s oc a br e p r e s e n tt h ee r r o rr a n g eo fb - s p l i n ec u r v e s ，b e s i d e s ， i th a st h ea d v a n t a g eo fs m a l l e rs t o r a g ei n f o r m a t i o na n dt h ee r r o rr a n g ew o n tb e c h a n g e du n d e r t h er o t a t i o nt r a n s i t i o n 3 t h i sp a p e rs t u d i e st h ek n o t r e m o v a lp r o b l e mo ft h ed i s kb s p l i n ec u r v e s ，t h a ti s ， b o u n d i n gd i s kb s p l i n ec u r v e sw i t ho n e k n o t r e m o v e dd i s kb - s p l i n ec u r v e s t w o m e t h o d sa r ep r o p o s e dt os o l v et h ep r o b l e m ，b o t ho ft h e mc a ng e tt h ea n a l y t i c s o l u t i o nt h ee x a m p l e sa r ep r o v i d e d ，a n dt h ea p p r o x i m a t ee r r o ro ft w om e t h o d s a r ec o m p a r e d t h ek n o t r e m o v a la l g o r i t h mc a nc a r r yt h ee r r o ri n f o r m a t i o no ft h e o r i g i n a lc u r v e sa n dt h ea p p r o x i m a t ee r r o ri n f o r m a t i o n ，t h er e s u l ti su s e f u lf o rt h e s u b s e q u e n tg e o m e t r i co p e r a t i o n ( s u c ha st os e a r c ht h ei n t e r s e c t i o np o i n t so ft h e c u r v e s ) 4 t h i sp a p e ra l s os t u d i e st h ed e g r e e r e d u c t i o np r o b l e mo ft h ed i s kb - s p l i n ec u r v e s ， i i 福建师范大学硕士学位论文 t h a ti s ，b o u n d i n gd i s kb s p l i n ec u r v e sw i t ho n e - d e g r e e r e d u c e dd i s kb s p l i n e c u r v e s w e p r o p o s e t h es u m c i e n ta n d n e c e s s a r yc o n t i d i t i o n o fp r e c i s e o n e d e g r e e - r e d u c t i o na n dt h ef o r m u l a t eo fp r e c i s ed e g r e e r e d u c i o n w ea l s o p r o p o s e t h ei n t e g r a l a p p r o x i m a t ed e g r e e r e d u c t i o na l g o r i t h m a n ds e p a r a t e a p p r o x i m a t ed e g r e e r e d u c t i o na l g o r i t h mt h ee x a m p l e sa r ep r o v i d e d ，a n dt h e a p p r o x i m a t ee r r o ro ft w oa l g o r i t h m s a r ec o m p a r e d t h ed e g r e e r e d u c i o n a l g o r i t h mc a nc a r r y t h ee r r o ri n f o r m a t i o no ft h eo r i g i n a lc u r v e sa n dt h e a p p r o x i m a t ee r r o ri n f o r m a t i o n ，t h er e s u l ti su s e f u lf o rt h es u b s e q u e n tg e o m e t r i c o p e r a t i o n k e y w o r d sb - s p l i n ec u r v e ，d a t ar e d u c t i o n ，d e g r e e r e d u c t i o n ，k n o t r e m o v a l ， b s p l i n eb a s i s ，d i s kb - s p l i n ec h iv e 1 i l 福建师范大学硕士学位论文 中文文摘 计算机辅助几何设计( 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 a g d ) 这门新兴 边缘学科，是建立在计算机技术不断发展与成熟的基础上，并随着汽车制造、航空、 船舶、机械设计和制造等现代工业的蓬勃发展而迅速发展起来的。它与微分几何、 函数逼近论、矩阵论、数值分析、虽优化理论和计算数学都有十分密切的联系。其 主要应用于航空、造船、汽车这三大制造业，还广泛应用于计算机辅助设计a n 工 ( c a d c a m ) 、建筑设计、服装鞋帽模型设计、计算机视觉和动画制作等技术领域。 b 样条曲线曲面是c a g d 的一个主要研究对象，也是众多c a d 系统中形状描述的 基本工具，它在各c a d 系统中的数据存储、误差表示和数据交换，一直是c a g d 研究的重要内容。 本文对b 样条曲线的数据缩减( 包括降阶和节点去除) 和圆球域曲线曲面造型 技术展开深入研究，全文共分五章： 第一章首先简要介绍c a g d 及其主要研究对象，然后，对b 样条曲线数据缩 减( 包括降阶和节点去除) 的研究意义和研究现状进行了总结与分析，简要讨论了 各种降阶算法和节点去除算法的优缺点，并指出这些算法的一个不足之处是无法同 时降阶和节点去除，在既需要降阶又需要去除节点的实践中，只能将降阶和节点去 除分开进行，因此增加了累积误差。随后，介绍了基于误差表示的曲线曲面造型技 术的研究意义和现状，指出区间b 样条曲线虽可描述条b 样条曲线的误差，但在 旋转变换下，误差域会被扩大。最后在上述分析的基础上，扼要地介绍了本文的研 究内容，研究方法和主要结果。 第二章将b 样条基转换矩阵理论与最t l , z 乘理论相结合，给出了种降阶和 节点去除的统一方法。 首先给出b 样条曲线数据缩减的定义，即同时降阶和节点去除。然后给出了数 据缩减后的b 样条曲线的节点向量的构造法则。该统方法的主要思路为：先构造 数据缩减后的节点向量，再计算出数据缩减前后的b 样条基的转换矩阵，然后把数 据缩减归结为解一个线性方程组，由于数据缩减一般不可精确进行，故该线性方程 组一般没有精确解，因此只需求出它的最小二乘解即可得到数据缩减后的逼近曲线， 利用广义逆矩阵的理论，笔者给出了该最小二乘解的矩阵表示。上述方法所得数据 缩减后的曲线一般不再与原曲线有相同的端点值，为插值原曲线的两端点，只需将 相应的约束条件加入到前述的线性方程组即可，此时，仍然可推导出最小二乘解的 矩阵表示。笔者给出了数据缩减的逼近误差的一个上界估计，证明了当按该统一方 法进行计算时，若原曲线可精确数据缩减，则得到精确数据缩减后的曲线，若原曲 线不可精确数据缩减，则得到原曲线的逼近曲线。 该统一方法只需通过简单的矩阵计算即可同时降多阶和去除多个节点，易于实 现，可以减少累积误差的产生，还可用于单独降阶或节点去除。当用于单独降阶时 可一次降多阶，当用于单独节点去除时可一次去除多个内节点。该统一方法可使逼 近曲线保两端点值不变。通过大量的实例验证了算法的正确性，并与以往的降阶和 节点去除算法进行了比较。其结果可望广泛应用于减少曲线存储的信息量以及不同 c a d 系统的数据交换等方面。 第三章在圆域算术的基础上，将圆域b 样条曲线的概念引入到c a g d 中来， 讨论了它的几何不变性、仿射不变性和凸包性等基本性质，以及d eb o o r 算法和 i v 福建师范大学硕士学位论文 b o e h r n 节点插入算法等基本算法。圆域b 样条曲线与区间b 样条曲线相比，除了同 样可以表示一条b 样条曲线的误差范围外，还具有存储的信息量小以及在旋转变换 下保持误差域不变等优点。 研究了圆域b 样条曲线的节点去除问题，即用去除一个节点后的圆域b 样条曲 线包住原曲线。首先给出圆域b 样条曲线的一个节点可精确去除的充要条件，若待 去除的节点满足该充要条件，则可由b o e h m 节点插入算法反算来去除节点。但一般 地，节点去除不可精确进行，此时对圆域控制顶点进行尽可能小的扰动，使其满足 节点可精确去除的充要条件，然后再由b o e h m 节点插入算法反算。先扰动圆域控制 顶点的中一心点，此步骤可由已有的公式直接进行计算，然后扰动每个圆域控制顶点 的半径，本文将其归结为解一个约束优化问题，建立了两种优化模型并分别给出了 拟线性规划和最佳逼近两种解法，均推导出了该优化问题的显式解。随后给出了相 应的计算实例，并比较了两种方法的逼近误差，其中最佳逼近法的逼近效果要好于 拟线性规划法。本章的节点去除算法能在节点去除的过程中保留原曲线的误差信息 和逼近误差信息，其结果有利于随后的几何操作( 如曲线求交等) 。 第四章研究了圆域b 样条曲线的降阶问题，即用降一阶后的圆域b 样条曲线包 住原曲线。给出了圆域b 样条曲线可精确降一阶的充要条件和精确降阶公式，该充 要条件可用于判断一条圆域b 样条曲线能否精确降一阶，若能精确降阶，则可直接 根据精确降阶公式进行降阶，但一般地降阶不可精确进行，本章给出了整体法和分 段法这两种降阶逼近算法。 整体法的主要思想为：先对原b 样条曲线的圆域控制顶点进行尽可能小的扰动， 使新得到的圆域b 样条曲线可精确降阶，并且可包住原来的圆域b 样条曲线，再对 该新曲线按精确降阶公式进行降阶。其中，对圆域控制顶点的扰动可分别对中心和 半径进行，中心曲线的控制顶点的扰动，只要解一个线性方程组即可实现，笔者把 对每个半径的扰动问题转化为一个线性规划问题，可用各种数值方法解该线性规划 问题。 分段降阶的主要思想是：通过插入节点将原圆域b 样条曲线分解为若干段圆域 b 6 z i e r 曲线，然后利用圆域b 6 z i e r 曲线的降阶算法对各段b 6 z i e r 曲线进行降阶，最 后采用第三章给出的节点去除算法除去多余的节点再组合成降阶后的圆域b 样条曲 线。 用实例验证了两种算法的正确性，大量的实验表明整体法的逼近效果要比分段 法好，还指出了对某些圆域b 样条曲线，本章降阶算法的逼近误差较大，此时可通 过插入节点的方法来改善降阶逼近的效果，并给出了相应的实例。本章的降阶算法 能在降阶的过程中保留原曲线的误差信息和逼近误差信息，其结果有利于随后的几 何操作。 第五章总结全文工作，并指出今后进一步的研究方向。 本文的主要创新点可归纳为以下两点： ( 1 ) 二十多年来，b 样条曲线的降阶和节点去除需采用不同的算法且无法同时进 行，本文打破了这一思维上的局限，给出了一种降阶和节点去除的统一方法， 可以同时降多阶和去除多个节点，大量的实验表明，该方法可以减少累积误 差。 ( 2 ) 将圆域b 样条曲线的概念引入到c a g d 中来，并讨论了它的一些性质和算法， 为b 样条曲线的误差表示与分析等方面提供了一种新的思路。 v 第一章绪论 第一章绪论 本章首先简要介绍c a g d 及其主要研究对象，然后介绍本文所要研究的问题的 内容，意义，研究现状，最后扼要地介绍了本文的研究内容，研究方法和主要结果。 1 1c a g d 及其主要研究内容 计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，简称c a g d ) 这一术语 由b a m h i l l 和r i e s e n f e l d t2 1 于1 9 7 4 年在u t a b 大学的一次国际会议上提出。此后，在 计算机技术不断发展与成熟的基础上，c a g d 这门新兴边缘学科，随着汽车制造、 航空、船舶、机械设计和制造等现代工业的蓬勃发展而迅速发展起来。其主要应用 于航空、造船、汽车这三大制造业，还广泛应用于计算机辅助设计3 n t ( c a d c a m l 、 建筑设计、服装鞋帽模型设计、计算机视觉和动画制作等技术领域。 尽管从c a g d 这门学科产生以来，它的研究内容被不断地延伸和充实，但其研 究的核心问题始终是工业产品的几何造型i s 2 。工业产品的形状大致上可分为两大 类：一类仅由平面、圆柱面、圆锥面、球面、圆环面等初等解析曲面组成，大量的 机械零件属于这一类；第二类不能由初等解析曲面组成，而由以复杂方式自由变化 的曲线曲面即所谓自由型曲线曲面组成，例如飞机、汽车、船舶的外型等。 自由曲线曲面造型技术，包括自由曲线曲面的表示、设计、显示、分析和处理( 包 括数据结构、图形的调整方式等) 等问题，是c a g d 的主要研究内容。三十多年来， 自由曲线曲面造型方法主要有：显函数式曲线曲面造型、参数曲线曲面造型、隐式 曲线曲面造型、细分曲线曲面造型、变形曲线曲面造型和基于误差表示的曲线曲面 造型等。 1 2 参数曲线曲面造型技术的研究历程 作为当今c a d c a m 系统中曲线曲面造型主流的参数曲线曲面造型技术，经历 了一个发展过程。 1 9 6 3 年美国波音( b o e i n g ) 飞机公司的f e r g u s o n 首先在飞机外形的设计中使用了 以( 1 ，f ，t 2 , t 3 ) 为基函数的三次参数样条曲线，构造了由四个角点的位置及两个方向切 矢定义的f e r g u s o n 双三次曲面片【2 5 2 “。1 9 6 4 年，美国麻省理工学院( m i t ) 的c o o n s 给出了一个具有一般性的曲面描述方法，给定围成封闭曲线的四条边界就可定义一 块曲面片0 0 l 。1 9 6 7 年，c o o n s 进一步推广了他的这一思想【i ”。在c a g d 实践中应 用广泛的只是它的特殊形式c o o n s 双三次曲面片。它与f e r g u s o n 双三次曲面片 的区别，仅在于将角点扭矢由零矢量改取为非零矢量。两者都存在形状控制与连接 问题。 法国雷诺( r e n a u l t ) 汽车公司的工程师b 6 z i e r 于1 9 6 2 年提出b 6 z i e r 曲线，并据此 建立了著名的u n i s u r f 自由曲线曲面设计系统”。5 l 。当时其定义十分奇特，令人难 以接受，直到1 9 7 2 年，f o r r e s t 才提出如今通用的定义，指出它恰好就是b e m s t e i n 福建师范大学硕士学位论文 基与控制顶点的线性组合【2 ”。b 6 z i e r 曲线曲面是由控制多边形( 网格) 定义的，在进 行外形设计时，设计员只要移动控制顶点就可方便地修改曲线曲面的形状，而且形 状的变化也在预料之中。b 6 z i e r 方法广为人们接受，它在c a g d 学科中占有重要的 地位。但它仍存在连接问题和局部修改问题。 1 9 4 6 年由s c h o e n b e r g 提出的样条函数提供了解决拼接问题的种技术m 】。在 构造整体上达到某种参数连续阶的插值曲线、曲面时，采用样条方法是很方便的， 但该方法不存在局部形状调整的自由度。d eb o o r 和c o x 分别独立地给出了关于b 样条的一套标准算法 1 2 1 4 1 。美国通用汽车公司的g o r d o n 和r i e s e n f e l d 于1 9 7 4 年将b 样条理论应用于形状描述，提出了b 样条曲线曲面1 3 0 1 。它几乎继承了b e z i e r 方法的 一切优点，又拥有形状局部可调及连续阶数可调等特性。随后，b e o h m 和c o h e n 等 人给出了b 样条曲线的节点插入技术心”，p r a u t z s c h 等发展了b 样条曲线的升阶技 虽然b 6 z i e r 曲线和b 样条曲线可用来表示自由曲线，但它们均无法精确描述除 抛物线以外的圆锥曲线。因此，有理形式的参数曲线也受到人们的广泛关注。f o r r e s t 首先给出了表达为有理b 6 z i e r 形式的圆锥截线1 。随后，b a l l t ”，f o r r e s t t ”1 ，f a r i n t ”1 ， p i g e l 4 3 1 等对有理参数曲线进行了广泛的研究。1 9 7 5 年，美国s y r a c u s e 大学的 v e r s p r i l l e 在他的博士论文中首先提出了有理b 样条方法。其后，p i e g l 和t i l l e r 等对其做了大量研究【4 3 - 5 “】。到了2 0 世纪8 0 年代后期，非均匀有理b 样条 ( n o n u n i f o t i nr a t i o n a lb s p l i n e ，简称n u r b s ) 方法已成为用于曲线曲面描述的最广 为流行的数学方法。所以1 9 9 1 年国际标准组织( i s o ) 颁布了关于工业产品设计交换 的国际标准s t e p ( s t a n d a r d f o r t h ee x c h a n g e o f p r o d u c t m o d e ld a t a ) ，把n u r b s 作为定 义工业产品几何形状的唯一数学方法【6 ”。如今，国际上流行的许多c a d 系统都提 供了对n u r b s 曲线曲面建模的支持( 如3 d m a x ，r h i n o c e r o s 等) 。n u r b s 仍在发展 中，一些问题( 如权因子、节点与参数化的关系等) 还有待深入研究。 1 3b 样条曲线数据缩减的研究现状 b 样条曲线曲面数据缩减( d a t ar e d u c t i o n ) 包含降阶和节点去除两个方面的内容， 它们均能减少b 样条曲线曲面在计算机中存储的信息量。 1 3 1b 样条曲线降阶的研究现状 在实际的产品开发过程中，常常需要在不同的c a d 系统之间进行数据交换1 。 第一章绪论 采用不同c a d 系统的公司之问有可能进行合作生产( 比如某家公司设计的产品拿到 另一家公司生产) 。即使在同一家公司里，为提高生产效率，各个生产部门也有可能 采用不同的c a d 系统( 从而可综合利用各c a d 系统的优点) 。但是，不同的c a d 系统中所能支持的多项式的最高次数是不同的，可从3 次到2 0 次不等。因此，在数 据交换之前，常常需要对高次曲线曲面进行降阶处理。与此同时，在对离散点数据 进行拟合逼近时常产生高次曲线曲面，在曲面片求交时产生的交线以及一张曲面片 的t r i m m e d ( 裁剪) 边界曲线也常常会是高次曲线，高次曲线曲面在计算机中存储的信 息量较大，这会增加计算机系统的负担，也不利于数据的网络传输。为尽量减少存 储的信息量，就需要对高次曲线曲面进行降阶处理。在构造组合曲线曲面时，常通 过降阶来使得相邻曲线曲面达到统一次数。此外，曲线的光顺处理也经常需要进行 降阶操作 2 4 1 。 利用齐次坐标”0 1 ，对n 【瓜b s 曲线曲面降阶的研究可以转换为对b 样条曲线曲 面降阶的研究。与升阶不同的是，一般地，b 样条曲线曲面的降阶无法精确进行， 因此降阶通常是一个逼近过程。作为b 样条曲线的特例，b 6 z i e r 曲线是一段多项式 曲线，其降阶相对简单些，已有许多b 6 z i e r 曲线的降阶方法【7 “”。4 15 2 2 2 8 。“”3 “5 6 1 ”一1 。 b 样条曲线是分段多项式曲线，其降阶过程较为复杂，目前已有的降阶方法也相对 较少，主要有如下几种： ( 1 ) 基于b 6 z i e r 曲线的降阶方法。1 9 9 5 年p i e g l 和t i l l e r 先通过插入节点将b 样 条曲线分解为若干段b 6 z i e r 曲线，然后对各段b 6 z i e r 曲线进行降阶，最后除去多余 的节点再组合成降阶后的b 样条曲线h 9 1 。该算法虽具有较明显的几何直观性，但计 算误差较大。 ( 2 ) 基于分段处理的降阶方法。这类算法的主要思想是：先对b 样条曲线分段 降阶逼近，再将产生的多组控制顶点加权平均得到降阶曲线的控制顶点。其中包括： 1 9 9 8 年，w o l t e r s 等的基于b 样条曲线开花( b l o s s o m i n g ) 原理和最小二乘法的降阶 算法 6 6 1 ；2 0 0 2 年，徐卉慧等的基于n u r b s 显示矩阵和广义逆矩阵的降阶方法【8 4 】； 2 0 0 3 年，成敏等的基于n u r b s 显示矩阵和c h e b y s h e v 多项式最佳一致逼近的降阶 算法 6 9 1 。这类算法虽然计算简单，但由于采用加权平均，使得降阶后的曲线相对于 原曲线在端点处的连续性难以控制，因此其应用范围受到一定的限制。 ( 3 ) 基于约束优化的降阶方法。 一种方法是利用b 样条曲线可退化( 精确降阶) 的充要条件。通过扰动控制顶点 求出可精确降阶的b 样条逼近曲线，再对该退化的曲线进行降阶【6 7 8 “8 ”。这种方法 可使降阶后的曲线与原曲线有相同的端点值，其优点是容易计算降阶逼近的误差上 界，还可结合节点插入技术，将降阶后的误差控制在给定的容差范围内，然而节点 插入会造成曲线存储的信息量增大。而且，到目前为止国内外学者仅给出了降一阶 的算法。 福建师范大学硕士学位论文 另一种方法是利用最佳平方逼近建立目标函数，直接求出降阶曲线【8 7 1 。这种方 法可在端点处保指定的连续性降多阶且降阶逼近效果较前一种好，但文献 8 7 1 中没 有给出降阶逼近的误差上界估计，而且在降阶过程中需计算两个b 样条基函数乘积 的积分，该积分尚无法显式计算，故计算量较大。 1 3 2b 样条曲线节点去除的研究现状 节点插入技术是b 样条曲线的一个重要技术，在进行b 样条曲线的交互设计时， 常通过节点插入技术，在保持曲线形状不变的前提下增加控制顶点的数量，从而增 加曲线形状修改的柔性，但是它同时也引入了冗余数据，因此当曲线的形状修改结 束后常需要去除多余的节点。另一方面，在用b 样条曲线曲面对离散数据点进行拟 合时，为达到较好的拟合逼近效果，也常常会产生大量冗余数据，为减少信息的存 储量，也需要去除多余节点。此外，节点去除也可以用于曲线的光顺问题。但是， 与节点插入不同的是，一般地，节点去除会改变原b 样条曲线的形状，因此，节点 去除通常是一个逼近过程。 到目前为止，节点去除方面的工作主要有：l y c h e 等m 1 首先对节点进行评价 ( r a n k i n g ) ，然后再基于整体逼近一次去除多个节点；t i l l e r 给出了在计算机容许 的误差内一次去除多个节点的算法，并给出了该算法的伪代码；e c k t ”1 则基于b 样 条曲线的局部结构研究去除一个节点的算法，首先给出了一个节点可精确去除的充 要条件，然后给出了在离散，逼近、离散k 逼近和连续k 逼近下的结果，其中离 散厶逼近、离散l 逼近可得到解析解，连续l 逼近无解析解，但逼近效果最好； 满家巨等1 基于文献 1 7 给出的充要条件，采用约束优化法去除b 样条曲线的一个 节点，并用于曲线的光顺。此外，k j e l l a n d e r 1 ，f a r i n 1 和s a p i d i s 5 3 1 等，讨论 了三次b 样条曲线的节点去除算法，并用于样条曲线的光顺。 虽然，二十多年来，国内外学者给出了不少降阶和节点去除的算法，为实际应 用提供了丰富的选择。但是这些算法的一个不足之处是无法同时降阶和节点去除， 在既需要降阶又需要去除节点的实际应用中，只能将降阶和节点去除分开进行，这 样就增加了累积误差。本文针对这一实际应用中急待解决的问题展开深入研究，给 出了b 样条曲线降阶和节点去除的一种统一方法。 1 4 基于误差表示的曲线曲面造型技术的研究现状 基于误差表示的曲线曲面造型技术包括区间曲线曲面造型技术和圆球域曲线 曲面造型技术。 1 4 1 区间曲线曲面造型技术 n u r b s 曲线曲面在c a d c a m 系统中是以精确形式表示的，但实际上按图纸加工 4 第章绪论 出来的产品外壳曲线曲面却不可能是唯一的精确形式，只是落在此精确曲面附近的 变动区域之中。如何在数学上来描述这个以精确曲面为中心的变动区域，该课题受 到人们广泛关注。曲线曲面求交问题是c a g d 研究的一个基本问题，在求交过程中当 曲线曲面相切时，由于浮点运算的误差，常常会丢失交点，而交点丢失则会导致几 何实体拓扑结构的改变，从而影响c a d c a m 系统的稳定性。因此，如何提高曲线曲 面求交的鲁棒性，是一个重要且棘手的课题。 1 9 9 2 年s e d e r b e r g 和f a r o u k i ”5 1 在曲线逼近中引入了区间b 6 z i e r 曲线的概念 正式把区间算术”2 1 引入到c a g d 中来。h u 等人m 。3 5 将区间运算应用于曲线、曲面求 交及几何形体的表示之中，提高了曲线曲面求交的鲁棒性，并给出了了几何形体的 可靠表示法及几何运算法。t u o h y 和p a t r i k a l a k i s 【6 2 1 引入了区间b 样条曲线曲面的 概念，并用其逼近测量的数据点。人们发现，区间曲线、曲面作为一种几何误差带， 不失为解决上述问题的好方法。因此，近年来，区间曲线、曲面的研究迅速发展成 为一个热点。寿华好讨论了区间曲线曲面和o f f s e t 曲线曲面之间的关系i s 2 ：陈效 群利用区间曲线逼近o f f s e t 曲线和有理曲线【7 0 l ：刘利刚等引进了区间b 6 z i e r 曲面 的概念，给出了利用区间b 6 z i e r 曲面逼近一般曲面和有理参数曲面的两套算法【7 4 】； 蔺宏伟等研究了区间b 6 z i e r 曲线的边界”。同时，区间曲线曲面的降阶问题也受到 人们的广泛关注，陈发来m 川，杨勤民1 和李涛【7 3 1 等分别讨论了区间b 6 z i e r 曲线 和区间b 样条曲线的降阶，区间三角b 6 z i e r 曲面的降阶以及区间有理b d z i e r 曲线、 曲面的降阶逼近。此外陈发来还提出了区间隐式化的概念并给出了有理b 6 z i e r 曲线 的区间隐式化】；樊旭川则研究了有理b 样条曲线的区间隐式化1 。 1 4 2 圆球域曲线曲面造型技术 由于区间控制顶点包含了误差信息，区间曲线曲面在要求误差控制的稳定几何 造型系统中可发挥重要作用。不过，区间曲线、曲面也有其自身的缺点，即在旋转 变换下，区间控制顶点会被放大 2 0 8 6 。一种改进方法是采用圆域( 球域) 来代替区 间。1 9 9 8 年q l i n 和j r o k n e 【5 2 1 提出了圆域b 6 z i e r 曲线，并讨论了圆域b 6 z i e r 曲 线的一些基本性质和边界表示，球域b 6 z i e r 曲线的概念也被同时提出。圆球域 b 6 z i e r 曲线除了同样可以表示曲线的误差范围，它还具有以下优良性质：( 1 ) 在旋转 等几何变换中误差域保持不变；( 2 ) 仅需一个点和一个表示半径长度的实数即可表示 一个控制顶点：( 3 ) 当所有控制顶点取等半径时，其边界是其中心曲线的等距曲线 面的轨迹。随后，关于圆球域曲线曲面的研究迅速展开：张兴旺等讨论了球域 福建师范大学硕士学位论文 b 6 z i e r 曲线的边界，并给出边界表示的多项式逼近日8 】；陈发来研究了圆域b 6 z i e r 曲 线的降阶逼近，用线性规划方法进行端点不插值的降阶，用最优化方法解决端点插 值的降阶逼近，在只降一阶时两种方法均给出了显式解口o 】：杨武讨论了矩形域和圆 域的误差表示及其在对称变换和旋转变换下的误差传播，并研究了圆域b o z i e r 曲线 的合并【8 5 i ；陈笑等用圆域b 6 z i e r 曲线逼近等距曲线1 6 9 。然而，据笔者所知，另 类重要的曲线一圆域b 样条曲线尚未得到系统地研究。区间b 样条曲线虽可描述误 差，但在旋转变换下，误差域会被扩大。而圆域b 样条曲线作为另一种描述误差的 方法，正好可以克服这个缺点。 1 5 本文的主要研究内容和结果 本文主要对b 样条曲线的数据缩减问题以及圆域b 样条曲线造型技术展开深入 研究。 第一章中我们简要介绍了c a g d 及其主要研究内容，详细讨论了b 样条曲线的 降阶和节点去除以及基于误差表示的曲线曲面造型技术在c a g d 中的重要作用，并 分析了国内外学者在这些方面的工作的优缺点，在此基础上引出本文的研究课题。 第二章利用b 样条基转换矩阵和最小二乘理论，给出了b 样条曲线降阶和节点 去除的一种统一方法。陔方法只需通过简单的矩阵计算即可同时降多阶和去除多个 内节点，可以减少累积误差，还可单独降阶或节点去除，当用于单独降阶时可一次 降多阶，当用于单独节点去除时可一次去除多个内节点。 第三章提出了圆域b 样条曲线的概念，讨论了它的几何不变性、仿射不变性和 凸包性等基本性质，给出了它的求值和节点插入等基本算法。研究了圆域b 样条曲 线的节点去除问题，即用去除一个节点后的圆域b 样条曲线包住原曲线，采用拟线 性规划和最佳逼近两种方法，均给出了该问题的显式解。 第四章在第三章的基础上，讨论圆域b 样条曲线的降阶问题，即用降一阶后的 圆域b 样条曲线包住原曲线。首先给出了可精确降一阶的充要条件和精确降阶公式， 当圆域b 样条曲线不可精确降阶时，我们给出了两种降阶逼近算法，分别是整体降 阶算法和分段降阶算法。 第五章总结全文，并指出今后进一步的研究方向。 第二章