（计算数学专业论文）参数三次b样条曲线的一种局部光顺方法.pdf

参数三次b 样条曲线的一种局部光顺方法 摘要 曲线曲面光顺研究发展到今天己取得了丰富的理论和应用成果，方法也同益趋 于成熟。但我们知道任何一种算法都有它的长处和短处，如果能有效的结合两种或 多种算法来对参数三次b 样条曲线进行光顺，使它们的优点分别展现出来，以此来 达到更好的光顺效果，这也是本文的主要工作。 本文的主要思想是运用已有的光顺方法，探讨了基于选点法和能量法两者的优 点，并考虑了曲线相对曲率的一种新的光顺方法，使两种方法能够扬长避短，其目 标函数既反映了曲线的应变能，也反映了曲率变化是否均匀，因而可使得参数三次 b 样条曲线光顺效果更好。 本文的方法不仅能一次性修改只对坏点有影响的控制顶点，而且使醢线曲率变 化比较均匀和具有较小的应变能。实验表明，该方法对曲线光顺的效果很好。 关键词 b 样条曲线；曲线光顺；能量法；选点法；相对曲率 an e wk i n do ff a i r i n gm e t h o df o rp a r a m e t r i c c u b i cb s p l i n ec u r v e s a b s t r a c t m a n yr e s u l t si nf a i r i n gr e s e a r c h e sa b o u tc u r v e sa n ds u r f a c e sh a v eb e e na c h i e v e di n b o t ht h e o r ya n da p p l i c a t i o n s n o w , t h em e t h o d sa r ei n c r e a s i n g l ym a t u r e a sw ek n o w , a n ya l g o r i t h mh a si t sa d v a n t a g ea n dd i s a d v a n t a g e i ft w oo rm o r e a l g o r i t h m sa r ec o m b i n e dt od e a lw i t ht h ef a i r i n go fp a r a m e t r i cc u b i eb s p l i n ec u r v e s ， b e t t e rf a i r i n ge f f e c tw i l lb ea c h i e v e d ，w h i c hi st h em a i nj o bo ft h i st h e s i s t h em a i ni d e ai st ou s en e wf a i r i n gm e t h o di n t e g r a t i n gt h em e r i t so ft h em e t h o do f s e l e c t i n gp o i n t sa n de n e r g ym e t h o da n dt a k i n gi n t oa c c o u n to fc u r v e sr e l a t i v ec u r v a t u r e ， s ot h a tt h et w om e t l l o d sa r ea b l et of o s t e rs t r e n g t h sa n dc i r c u m v e n tw e a k n e s s e s t h e o b j e c t i v ef u n c t i o nn o to n l yr e f l e c t st h ec u r v e 。ss t r a i ne n e r g y , b u ta l s or e f l e c t sw h e t h e rt h e o u r v a t u r e sc h a n g ei su n i f o r m ，t h u sm a k i n gt h ef a i r i n ge f f e c t i v e n e s so fp a r a m e t r i cc u b i c b s p l i n ec u r v eb e t t e r t h em e t h o do ft h i st h e s i sc a r ln o to n l ym o d i f yt h ec o n t r o l l i n gp o i n t sa tat i m et h a to n l y h a v ei n f l u e n c e so nb a dp o i n t s 。b u ta l s om a k et h ec u r v e 。sc u r v a t u r ev a r yr e l a t i v e l ye v e n l y a n dt h ec u r v eh a v es m a l l e rs t r a i ne n e r g y t h ee x p e r i m e n t ss h o wt h a tt h em e t h o dh a s q u i t eg o o df a i r i n ge f f e c t so nt h ec u r v e k e y w o r d s ： b s p l i n ec u r v e ；c u r v ef a i r i n g ；e n e r g ym e t h o d ；m e t h o do fs e l e c t i n gp o i n t s ；r e l a t i v ec u r v a t u r e 表格及插图清单 图3 1 能量法模型( 1 3 ) 图4 1 参数三次b 样条拟合曲线及相对曲率图( 2 0 ) 图4 2 口= 1 0 - 5 时能量法、改进的能量法与本文算法所得蓝线比较( 2 1 ) 图4 3 口= 1 0 5 时能量法、改进的能量法与本文算法所得曲线的相对曲率比较( 2 1 ) 图4 4 口= l 0 。3 时能量法、改进的能量法与本文算法所得曲线比较( 2 1 ) 图4 5 口= 1 0 。时能量法、改进的能量法与本文算法所得曲线的相对曲率比较( 2 2 ) 图4 6 口= 1 0 一时能量法、改进的能量法与本文算法所得曲线比较( 2 2 ) 图4 7 口= 1 0 _ 1 时能量法、改进的能量法与本文算法所得曲线的相对曲率比较( 2 2 ) 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得盒日曼王些太堂或其他教育机构的学位或证二 5 而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签字：岛奇签字日期：加产中月停日 学位论文版权使用授权书 本学位论文作者完全了解盒g 曼王些太堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 妲薹些厶堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 尾静 导师签名： f 、 核gc 次 一， 签字日期：如明年年月c 矿日 签字日期：卅年弘侈日 学位论文作者毕业后去向： ：r ：作单位： 通讯地址： 电话： 邮编： 致谢 本文是在檀结庆教授的悉心指导下完成的。在两年半的硕士学习期间，导师始 终给予我精心的爱护和热情的帮助。他的渊博的专业知识，严谨的治学风范，开创 性的思维和敏锐的洞察力，执着地追求真理的科学态度，给我留下了难忘的印象。 导师既教书又育人，其谦和的品格，为我树立了榜样。有关如何更好地适应社会方 面的谆谆教诲将使我终身受益。在此，谨向导师的辛勤培养和亲切关怀表示衷心的 感谢! 同时，要感谢的还有系旱的江平副教授、邢燕博士、刘植博士、张莉博士等。 因为他们在平时的日常事务中给予我的指点帮助，使得我的学习、研究工作得以顺 利完成。在这旱我表示衷心的感谢。 在即将毕业离校之际，我要感谢我的同方向上的王燕，李方和方中海，是他们 平时给我学习上的帮助! 还有同寝室的两个姐妹们在生活上给予我的关心及学业上 的切磋和指点，感谢合肥工业大学数学系2 0 0 6 级硕士生全班同学的帮助和勉励。同 窗之谊和手足之情，我将终生难忘! 最后要感谢的是我的父母。正是由于他们默默无闻的帮助和一贯的支持和鼓 励，才使我顺利完成全部的学业。 感谢我的论文中引用到的文献的作者们的勇于探索和孜孜不倦。我是踩着他们 的足迹节节迈进的。 还要感谢所有的我没有提到的而帮助过我的人们! 我愿在未来的学习和研究过程中，以更加丰厚的成果来发扬我的研究方向、来 答谢曾经关心、帮助和支持过我的所有领导、老师、同学、亲人和朋友。 屠静 二零零九年四月 第一章绪论 计算机辅助何设计( c o m p e 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 与烈e s e n f e l d 【3 在1 9 7 4 年美国u t a h 大学的一次国际会议上提出，以描述计 算机辅助设计( c o m p e e ra i d e dd e s i g n ) 中更多的数学方面，它是借助数学的理论和 方法并融合计算机应用技术解决计算机辅助设计中的种种数学问题，建立数学模 型，使得设计既适合计算机处理，能有效的满足形状描述与几何要求，又便于形状 信息传递和产品数据交换，它是c a d 的理论基础和关键技术。 1 1曲线曲面光顺研究的发展概况 曲线曲面的光顺研究大约始于上世纪6 0 年代初，国内1 9 7 4 年由苏步青教授率先 开辟该研究方向，通过国内外学者的努力，到目前为止己提出了许多光顺方法：通 过“节点删除与插入”对b 样条曲线进行光顺的方法( f a f i n 等n 峨删) ：用三次参数样 条曲线和双三次样条曲面的局部光顺方法( k i e l l a n d e r 等咿引) ；用于空间三次参数样 条曲线光顺和网格光顺的能量法( h o s a k a 等口a 毗) ；b 样条曲面光顺的能量法( l o r 等 国1 ) ；基样条法汹3 0 1 ；曲面网格线光顺方法d 。总的来说这些方法可归为两大类： 1 ) 整体光顺法n8 钉1 ，如能量法等，是将光顺问题转化为包含型值点偏差和光顺 两部分加权平均的目标函数的极小化问题，光顺是要用到全部型值点来修改。 2 ) 局部光顺法d6 8 1 ，如基样条法，节点插入和删除法等都是选点修改法是在假 设大多型值点都是好的或比较好的基础土，把少数坏点挑出逐个予于修改，但当连 续出现多个坏点时，往往不易处理，这些方法都是比较经典的，实质上，它们相差 不大，经过一番沟通，不难发现好几种方法之间有着某种联系。 值得一提的是2 0 0 2 年蔡中义h 川提出的有限元光顺法丌辟了新的研究途径。该 方法采用h e r m i t e 单元极小化目标泛函，再现的曲面全场c 或c 2 连续，这种结合能 量光顺的有限元插值计算方法抑制了输入数据中噪音的影响，曲面的重建的精度 高，光顺性好。于屹h 秘等人给出了基于遗传算法的曲线曲面光顺大大提高了计算的 效率。还有近几年出现的利用多分辨率的小波光顺算法乜l2 巩删效率高，光顺可在线 性时间内完成，在光顺的同时进行数据压缩，但是无法处理边界约束。在众多光顺 方法中能量法仍是一种应用非常广泛的曲线曲面光顺方法，可以处理边界约束，并 适用于大挠度和闭曲线曲面的光顺【。 1 2 曲线光顺技术由来 在飞机、汽车、船舶以及家用电器等的计算机辅助几何设计( c a g d ) 中，人们对 产品外形有很多方面的要求，其中之一就是对产品的外形光顺性( f a i r n e s s ) 的要求。 随着市场竞争的日趋激烈，产品要想在竞争中取胜，新颖的外观、流畅的线条和光 顺的曲面就显得非常重要。另外，从制造加工的角度来说，设计产品的几何光顺性 不好会导致加工困难，使加工成本提高。也即说光顺性对产品质量的高低，产品的 物理性能，尺寸精度，几何美观等，直接产生重要的影响。在计算机动画( 尤其是 人体动画) 技术，虚拟现实技术中，需要“实时性”和“真实感”的显示，入、物、 景的光顺性与逼真处理是关键技术之一。在古文物复原和古文物复制的计算机辅助 几何设计技术中，这也是一个重要课题。实际上，在c a d c 燃和计算机图形学等领 域里，曲线曲面光顺性问题一直很受重视的一个研究课题。也就是说曲线曲面光顺 是计算机辅助几何设计( 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 o m p u t e rg r a p h i c s ) 的一项重要内容，其有强大的理论及实用价值。 国际上对光顺的研究大约始于6 0 年代初，主要应用船体数学放样，最小二乘法 是当时最有影响的一种光顺方法。1 9 6 9 年，h o s a k a m 在能量极值原理的基础上给出 了一种包括光顺空间曲线和大挠度曲线在内的光顺方法，称为能量法，它的基本思 想是同最小二乘法一样，是偏离和光顺两部分的加权综合，不同的是目标函数中的 剪力越度成了样条的能量积分。 1 9 7 8 年浙江大学等单位在船体数学放样的实践中提出了一种新的曲线光顺方 法一“回弹法”。它是手工放样的数学模拟，通过新老两组型值点交替地固定和 回弹，使样条地能量逐渐减少，以达到光顺的目的。 1 9 7 4 年苏步青教授提出了一种基样条方法，对原始数据进行局部选点修改，在 应用中得到了良好的效果。同时山东大学和沪东造船厂协作，在船体数学放样的实 践中首次提到了圆率法光顺的概念，本质是使曲率变化均匀。之后，刘鼎元教授对 此方法进行了改进，提高了曲线光顺的质量。在同一时期，吉林大学等单位提出一 种强调保凸性质的数据拟合法，叫磨光法。以后几年，醢线光顺的研究与前面大同 小异。 1 9 8 7 年，f a r i n 等人提出了一种人机交互光顺的方法，此方法的本质使利用曲线 的曲率图进行人工交互修改，以使曲线曲率变化均匀。与圆率法思想一致，但算法 比较简单。n o w a k i 和l i u 给出了一种广义能量的方法，此方法可同时修改多个点， 并可通过标值来判断曲线是否光顺。所以这些方法，都大大的充实了曲线光顺理论。 目前，曲线光顺的算法同新月异，大量新理论和新算法被不断的提出。各种局 部光顺和整体光顺等一些更加有效、更加快速的曲线光顺算法被广泛的研究。然而， 出于前人的参数三次b 样条曲线光顺曲线的局部光顺和整体光顺算法模型不够理 想，新算法的主要目标是，在局部光顺和整体光顺算法效果之问取得一种折衷，并 且算法容易理解和实现。 1 3 曲线光顺准则 什么样的曲线才是光顺的呢? 直观上看，直线，圆弧等简单几何形状是光顺的。 如果一条曲线拐来拐去，有尖点或许多拐点，则我们认为这样的曲线是不光顺的。 此外，在船体数学放样中，通常认为在插值于给定型值点的所有曲线中，通过这些 型值点的弹性木样条是最光顺的。但很难给光顺下一个定义，光顺性仍然是一个模 糊的概念。这是因为光顺性涉及几何形状的美观性，难免受主观因素的影响。此外， 在不同的实际问题中，对光顺的要求也不同。因此，迄今为止对光顺性还没有一个 统一的标准，在不同的文献中对光顺准则有不同的提法。 但光顺性也有其客观的一面。不同的文献中对光顺准则的提法虽略有差异，但 是有很多共同点。 对于平面曲线，苏步青，刘鼎元给出了以下的光顺准则口： 1 、二阶参数连续( c 2 连续) ；2 、没有多余拐点；3 、曲率变化比较均匀。施法 中又增加了“应变能较小”这一条，其准则为： 1 ) 二阶几何连续( 指位置，切线方向与曲率矢量连续，记为g 2 ) ； 2 ) 不存在奇点与拐点； 3 ) 曲率变化比较均匀： 4 ) 应变能较小。 可以发现，后者前三条准则和苏步青，刘鼎元给出的准则基本一致，已为大家 所普遍接受，其合理性是显而易见的。第四条准则基于“物理样条是光顺的”这一 事实，它是能量法的基础。 至于空问曲线，马利庄和石教英给出了如下的光顺准则别： ( 1 ) 二阶光滑性。 1 ) 曲线的二阶导矢连续，从而曲率连续。 2 ) 低次样条的曲线( 二次) 在节点的曲率可能有一个跳跃，此时要求跃度和尽 可能小，即1 盯( ，+ ) 一r ( f ，一) l 占 ( 2 ) 不存在多余拐点，即不允许出现下述情况。 1 ) 曲线应出现g 个拐点，而拟合( 插值，逼近) 时出现了多于g 个拐点。 2 ) 不应该出现拐点的地方出现了拐点。 ( 3 ) 曲率变化比较均匀。 当曲线上的曲率出现大幅度改变时，尽管没有多余拐点，曲线仍不光顺因此 要求光顺后曲线的曲率变化比较均匀。 ( 4 ) 不存在多余变挠点( 变绕点指挠率为零的点，通常与挠率变号点相关) ，即 不允许出现下述情况。 1 ) 曲线应出现h 个变挠点，而拟合( 插值，逼近) 时出现了多于h 个变挠点。 2 ) 不应该出现变挠点的地方出现了变挠点。 ( 5 ) 挠率变化比较均匀。 1 ) 挠率不连续( 节点处左，右挠率差) 跃度和足够小，p , p z ( t i + ) 一r ( 一) i 。 2 ) 挠率的变化比较均匀，无连续变号。 1 4 曲线光顺的方法 早期，在曲线曲面的设计和表示中主要采用函数样条，光顺的对象主要是函数 样条曲线和曲面，所采用的方法有最d , - 乘法，基样条法，圆率法，回弹法和磨光 法等2 咄m 飘驯们。 在c a d c a m 中，构造参数曲线、曲面的最重要的一种方法是对给定的型值点进 行插值或拟合。生成的曲线不光顺的原因主要有以下几种情况： 1 ) 型值点是光顺的，但由于参数化不合理而导致生成的曲线，曲面不光顺。 2 ) 型值点是光顺的，但由于曲线，曲面的生成方式或采用的曲线，曲面表达式 不理想，因而导致所生成的曲线，曲面不光顺。 3 ) 型值点本身不光顺，而导致插值于型值点的曲线，曲面不光顺。 因此，为使生成的插值曲线，曲面具有良好的光顺性，通常可采用如下方法： ( 1 ) 采用良好的参数化 对于分布极不均匀的数据点，采用均匀参数化插值生成曲线时，弦长较长的那 段曲线显得扁平，而弦长较短的那段曲线则严重鼓起，甚至出现尖点或打圈自交( 二 重点) 。因而，曲线是不光顺的。但采用积累( 累加) 弦长参数化，则生成的曲线是 光顺的。 因此，当型值点分布不均匀时，可以考虑采用积累弦长参数化，向心弦长参数 化，或修j 下弦长参数化来改善曲线的光顺性。 此外，在用参数曲线，曲面对型值点进行最d , - 乘法拟合时，可采用参数化的 方法，通过迭代来确定与各型值点对应的参到。5 1 ( 2 ) 采用优良的曲线曲面生成和表达方式 如可采用几何连续的样条代替参数连续的样条以增加曲线生成的自由度，通过 选择合适的形状控制参数，使生成的插值曲线，曲面更广顺。”矧。此外，与整体插 值方法相比较，在某些情况下采用局部插值方法生成的曲线曲面更光顺。 ( 3 ) 适当调整型值点的空间位置 如果给定的型值点呈锯齿形，则不论采用何种参数化或曲线的生成方式得到的 插值曲线都不光顺。对于这种情况，常用的方法是适当调整型值点或控制点的位置， 是生成的曲线或曲面达到光顺。在本文中，我们讨论的光顺方法都是这种类型。 根据每次修改型值点的多寡以及所采用的光顺准则，现有的光顺方法可以分为 两种类型：局部光顺方法和整体光顺方法。如每次仅修改少数型值点，则称为局部 光顺方法。各种选点修改法m ，嘲都属于这一类型。如每次修改全部型值点，则称 为整体光顺方法。 目前，很多文献中采用优化的方法对曲线，曲面进行光顺，例如最小二乘法， 能量法等都属于这一类型b m 叫9 1 。优化法既可用于曲线，曲面的整体光顺，又可用于 曲线，曲面的局部光顺。当用于整体光顺时，称为整体优化法，否则称为局部优化 法 当然，还有其他一些光顺方法，如1 中提出用小波技术对曲线，曲面进行光顺。 和本文中的讨论相关较远，不作论述。 1 5 本文主要研究内容和安排 曲线曲面光顺研究发展到今天已取得了丰富的理论和应用成果，方法也日益趋 于成熟但我们知道任何一种算法都有它的长处和短处，如果能有效的结合两种或 多种算法来对参数三次b 样条曲线进行光顺，使它们的优点分别展现出来，以此来 达到更好的光顺效果，这也是我们要做的工作。 本文在广泛阅读国内外文献的基础上，运用已有的较有影响的光顺方法和汲取 光顺思想的精华，探讨了基于选点法和能量法两者的优点并考虑了曲线相对曲率的 一种新的光顺方法，使两种方法能够扬长避短，其目标函数既反映了曲线的应变能， 也反映了曲率变化是否均匀，因而可使得参数三次b 样条曲线光顺效果更好。 全文共分五章，各章内容安排如下： 第一章计算机辅助几何设计和曲线光顺方法研究的发展、意义和代表性工作 概述；并介绍相关的背景知识和本文研究内容。 第二章光顺的含义与光顺准则，目前光顺的方法，检测及光顺的共同缺点。 第三章能量法原理，离散能量法，改进的能量法及选点修改法。 第四章针对现有的光顺的方法的不足提出新的算法主要研究基于选点法和 能量法两者的优点并考虑了曲线相对曲率的一种新的光顺方法对参数三次b 样条曲 线进行光顺，一次性只修改对坏点有影响的少数控制顶点，既减少了计算量，也使 得曲线形状改变尽可能小。使它们的优点分别展现出来，以此柬达到更好的光顺效 果。 第五章全文总结，对研究工作的展望。 第二章光顺算法简介 弟一早 尤耿异法间丌 本章主要介绍了光顺的含义，光顺的检测准则和目前主流的曲线光顺算法。最 后探讨了目前光顺算法存在的弊端及本文提出的改进算法的思想。 2 1 光顺的含义 “光顺”包含“光滑”和“顺眼”两方面的含义，既有数学上连续性的要求， 更侧重功能( 如美学，数控加工，力学等) 方面的要求，通常情况下光顺性是没有准 确定义和统一标准的。在早期的手工放样中，人们以“眼观光顺”为标准，这就让 经验决定了一切。而数学放样就相对复杂多了，它必须把手工放样中的经验准则转 化成计算机能识别的数学准则：光顺的不确定性容易使人们产生错觉，以为量化的 数学准则是不存在的，至少是勉强的。殊不知，如果光顺性没有其内在规律可循， 又怎么能够区分曲线( 面) 光顺与否呢? 由此可见，问题的关键并不在于光顺是否具 有客观( 即规律形) ，而是在于如何协调光顺的客观性和不确定性的关系，这正是光 顺定义和光顺准则要解决的难点。 关于曲线、曲面光顺处理，需要解决两个基本问题： 1 ) 什么样的曲线、曲面才是光顺的，即光顺准则； 2 ) 对于不光顺的曲线、曲面，如何进行一定的数学处理使其光顺性得到满足或 改善，即采取何种光顺处理方法。 曲线、曲面的光顺问题涉及到几何外形的美观性，是一个较难界定的概念。同 时针对不同的实际问题其衡量的标准也不尽相同。这里所提出的曲线、曲面的光顺 准则是在参考了大量的相关文献的基础上，针对目前c a d c a m 系统中普遍采用b 样条曲线、曲面的事实下给出一个比较适合和便于进行几何评估的准则。 1 曲线的光顺准则： ( 1 ) 二阶光滑性。它包含两方面的内容：曲线的二阶导矢连续，从而啦率连续； 曲线的曲率连续和低次样条曲线( 二次) 在节点处曲率可能发生跳跃，这时要求其节 点处左、右曲率差的跃度和尽可能的小于某一极小值。即芝弘( r ? ) 一k ( t s ) 占。 ( 2 ) 不存在多余的拐点。 ( 3 ) 曲率的变化应比较均匀。一些曲线即使在不存在多余拐点的情况下，由于 它的曲率出现骤增或骤降时也会造成曲线的不光顺，此时必须增加保证曲线的曲 率变化比较均匀的条件。 ( 4 ) 没有多余变挠点。( 交挠点是指挠率彳：j = 号出现变化的点) ( 5 ) 挠率的变化应比较均匀。 6 2 曲面的光顺准则： 曲面的顺准则通常是通过检验曲面上的甜，v 方向的参数曲线、曲面与一组等间 隔的平行平面的相交截面线、曲面形成时的网格线等x 轴益线的光顺性以及曲面的 主曲率、高斯曲率、平均曲率的变化是否均匀等方法成立，曲面光顺准则的具体内 容为： ( 1 ) 曲面的，1 ，等参线达到光顺。 ( 2 ) 构造曲面时的网格线达到光顺。 ( 3 ) 曲面与某一组等间隔且平行的平面的相交截面线达到光顺。 ( 4 ) 曲面的高斯曲率变化均匀。 ( 5 ) 二次曲面的主曲率在节点处的左、右曲率差的跃度和尽量小。 以上曲线、曲面的光顺准则是针对目前c a d c a m 的发展现状给出的概括，光 顺其实既包括有较严格的数学定义的参数连续性和几何连续性，同时也侧重审美 学、加工制造、力学性能等功能性要求，而且数学定义和功能要求存在不完全一致 性，比如一条在数学上无穷阶连续的曲线，因为其曲率及挠率变化太大而导致并不 光顺。但又存在着当曲线、曲面的曲率比较小时，一般可以通过提高曲线、曲面的 高阶连续来达到光顺曲线、曲面的目的。 2 2 目前光顺的方法 曲线、曲面光顺处理是c a d c a m 中的非常重要的一个课题，因此越来越受到 人们的广泛关注。国内外许多学者对此做了大量的研究，得到了许多有用可行的方 法： l 、最4 , - 乘法 国际上对光顺处理的研究大约始于6 0 年代，主要用于船舶放样，最4 , - 乘法当 时是最有影响的一种光顺方法。它的主要思想大体如下： 在平面上给定了一组用坐标表示的型值只( 一，只) ( 江o ，2 ) ，在x 轴上，在 口，b 】 区i 、日j 内进行相应的分割，在此分割上构造一个三次样条函数曲线使其逼近给定的型 值点，再选取一定的目标函数，比如目标函数采用样条的剪力跃度的平方和。光顺 的目的是使该样条的剪力跃度的平方和最小。由剪力跃度来控制，通过调整目标函 数中的两个权因子，使其达到理想的光顺效果。而剪力跃度的平方和与曲线的曲率 变化相关联，因此最4 , - 乘法可以使曲线的曲率变化均匀化。但是这种方法有一定 的缺陷：比如随着n 的不断增大，所解系数矩阵的病态程度将急剧增大，引起计算 的不稳定。所占内存较大。 2 、能量法 1 9 6 9 年，h o s a k a 口1 在能量极值的基础上最早提出了用于空间三次参数样条曲线 光顺和网格光顺的能量法。他的基本思想方法跟最小二乘法一样，不同之处在于： ( 1 ) 采用累加弦长三次样条作为拟合曲线：( 2 ) 目标函数中的剪力跃度部分改成样条 的能量部分。光顺的目的是使该样条的应变能最小。此方法有相当直观的力学模型， 易推广n - - 维或多维的网格的光顺问题。但是由于应变能与曲线的绝对瞳率相关 联，因此应变能法会使曲线的曲率变小，导致光顺的曲线都将趋于向直线变化，并 不能使曲线的曲率变化均匀。 1 9 8 8 年，l o t t 伸1 等提出了b 样条曲面的光顺的能量法。 2 0 0 2 年，于屹，齐从谦，陈亚洲。峙1 提出基于遗传算法的曲线曲面光顺，以能量 和曲率作为双重条件来考察曲线和曲面的光顺性问题，应用模糊罚函数将有约束多 目标优化问题转化为无约束多目标优化问题，采用遗传算法对曲线进行光顺，得到 了最优解：并进一步将该光顺算法推广到曲面的光顺。它避免了只用能量法带来的 使曲线曲面直线化的缺点，同时遗传算法是一种随机的全局多点搜索算法，具有隐 含并行性的特点。 3 、局部修改法 1 9 7 7 年，忻云龙将三次样条函数的基样条表示应用到网格光顺中，提出了网 格基样条法。是光顺单根曲线的基样条法在二维场合的拓广。是一种“曲线检查， 曲面修改”的方案。它是分别把剪力跃度和一元跃度向量在二元场上拓广，通过求 曲面的跃度平方和最小来光顺。当要求平方和趋与零时，则出现修改的点过多，修 改量过大的缺点。 1 9 8 3 年，k j e l l a n d e r 险7 1 提出了一种三次参数样条曲线和双三次参数样条曲面的 局部光顺方法。 1 9 8 7 年，f a r i n 等n 3 们提出了一种通过“接点删除与插入”对b 样条曲线进行光顺 的方法。节点删除与插入法是：通过判别、修正“瑕点”来光顺曲线的局部光顺法， 它具有局部性、速度快和修正力度大的特点，但是当曲线中出现的“瑕点”较多而 且连续出现时，光顺的效果通常不是很理想。 4 、圆率法 我国学者也在这方面作了很多工作。从1 9 7 4 年起，山东大学和沪东造船厂协作， 在船体数学放样的实践中，在0 1 中提出了圆曲率光顺的概念。平面上给定了型值点 只和两边界切向m 。，川，f ，过相邻三点f p 只，只+ ，所作圆的相对曲率k ，称为在点只 处的圆率。是一种选点修改，它不需要插值曲线，而是从离散型值点分布的几何位 置出发直接判断型值点列的光顺性，再挑出“坏点”进行修改，这种光顺法经过粗、 精光顺两过程。它跟下面要提到的基样条法一样的原理，只是它用圆率和采用圆率 的二次差变成最小作为光顺目标；基样条用导数m ，采用剪力跃度平方和变成最小 作为光顺目标。 5 、基样条法 1 9 7 4 年，苏步青和忻云龙汹3 提出了基样条法这种方法有一个必要的前提，那 就是提供的原始型值点，极大多数是好的，或是比较好的。它跟圆率法一样，都属 于选点修改法。它的基本原理是：对于给定的原始型值点p ( 薯，只) ( 待o ，z ) 和边界 导数，z ，按照基样条表示构造插值三次样条函数s ( x ) ，它是满2 ：c 2 连续条件 的。计算s 在每个节点处的二阶导数m = ( 薯) ，并作导数m 的符号序列 s i g n ( m , ) ，凡使序列连续变号的点挑出，这是粗光顺，再作m 的差分 f 1 m , = m m 一，的符号序列号 s i g n ( a m , ) ，同样找出使其连续变号的点，这为精光 顺。这种方法的优点是：坏点挑得准，好点又不受破坏，修改能力强。缺点就是必 须有个前提。否则，不容易处理好，即使最后也能光顺，但收敛速度就慢了。 6 、磨光法 1 9 7 5 年，齐东旭等提出了一种强调保凸性质的数值拟合方法，称为磨光法( 亦 称盈亏修正法) 。在等距分割的区间a ：口= x o x i 矗= b 间隔为h ，* l ：i n + 1 个型值 点只b ，只) ( f _ o ，l ，z ) 。用线段连接每相邻两个型值点而得到折线函数l ，k 次样条 函数：s ( 工) = 窆t = o 咒坂( 等卜的k - 1 次磨光函数，其中心( 帕k 次b 样条函数。 当k = l 时，便是折线函数l 。实用上经常取k = 2 ，3 。瓯( x ) 在国外的文献中称为k + l 阶样条v d ( v a r i a t i o nd i m i n i s h i n g ) 变差缩减逼近。v d 的意思是说：k 次样条函数s ( x ) 的拐点个数不会超过折线函数l 的凹凸转向次数。由于v d 逼近不满足插值条件， 在每个内节点x ，处出现偏离，磨光法的主要思想就是在接点出现偏离进行“盈亏修 正 补救。一般来说，修正次数越多，磨光函数接近插值函数。优点：附加盈亏 修正法的磨光函数能减少同原型值点的偏移，又保持原型值点的凸性，使用于要求 保凸的数据拟合问题。缺点：磨光法不具备初光顺的功能，他要求原型值点满足初 光顺条件，这是由于磨光函数在“保形”方面过于求全而缺少“平滑”能力的缘故。 此外，磨光法对于精光顺的目标也是缺少考虑。 7 、回弹法 1 9 7 8 年，董光昌。”提出了一种新的光顺方法，称为回弹法。它是手工放样中的 “两借借，自然放”的一种数学模拟：通过新老两组型值点交替的固定和回弹，使 样条的能量渐次减少，以达到光顺的目的。简要的算法是：当平面上给定一组型值 p ( 一，y ，) 以及适当的边界条件后， 9 ( 1 ) 对于给定的分割：a = x 。 毛 x ，= 参及型值点 只( x ，z ) ，作插值三次 样条函数s f x ) ； 1 ( 2 ) 取相邻两个节点的中点考= 妻( t + ”) ( 江o ，n - 1 ) ，这里乒= 口，己= 6 ； 二 ( 3 ) 对于另一个分割：8 = 乒。 彘 幺= 6 ，及型值点 q ，( 缶，s ( 毒) ) ， ( 待一l ，0 ，n ) 同样作插值三次样条函数s ( x ) ； ( 4 ) p 。( ，s ( 葺) ) ( 汪o ，z ) 。称为经过一次回弹的新型值点； ( 5 ) 如此反复，直到某一次回弹后的节点i 处的函数值之差小于定值为止。最 后一次获得的型值点及其插值样条即作为光顺型值点和光顺曲线。后来把( 2 ) 改 进成加权平均的形式。直观地看，经过回弹，样条的能量减少，曲线也就趋向光顺， 回弹法可以看成一种迭代逼近的能量法。优点：力学意义明确，方法简便易行，光 顺质量良好。缺点：迭代次数过多的时候，可能出现光顺型值点与原型值点偏离过 大，而且对平直段小波动往往难以消除。 8 、小波光顺 小波分析是分析的突破性发展，它既是一项强有力的分析技术又是一中快速的 计算工具。兼具重要的理论意义和使用价值。小波是刻画数据内部相关性结构的有 力工具，在数据压缩和逼近方面具有强大威力。小波思想融合了子带编码、c a g d 中 的分割、理论、非线性逼近理论、分形和自相似性、样条、滤波器库、抽样理论、 理论和图像处理中的塔式分解算法等众多领域的具体思想，是处理这些具体思想的 统一框架，是众多应用领域的连接点。小波促进了各门学科的交叉和发展，其应用 领域十分广泛，而且还在不断拓展。 近年来，小波分析在计算机图形学中获得了r 益广泛的应用。特别在曲线曲面 光顺中也得到了很好的应用。由于曲线的多分辨率具有以下特点；逼近曲线能够保 留原曲线的整体形态；逼近曲线可由较少的控制顶点和b 样条基函数表示，因而可 用于曲线的数据压缩：小波分解将曲线分解为低分辨率部分( 低频部分) 和细节部分 ( 高频部分) ，低分辨率部分又称为原曲线的逼近曲线。逼近曲线是由原曲线去除高 频部分得到的，外观比原曲线更顺眼。分解次数越多，得到的逼近曲线越光滑。由 此，为曲线光顺及定量控制光顺误差提供了新的思路；允许用两种不同的编辑方式 在不同的层次上编辑曲线，在保持细节特征不变的情况下改变曲线的整体形状，在 保持整体形状不变的情况下改变曲线的细节特征：可由粗到精地对曲线进行分级传 输和显示。 1 9 9 8 年，孙延奎，朱心雄h 州提出小波光顺法，其原理是通过小波分解后，尽可 能的剔除原曲面的高频部分，使光顺后的逼近曲面比较好的保留原曲丽的低频部 分，因此也就较好的保持了曲面的总体形态。而且利用小波分解进行光顺，可以减 少曲面的控制顶点的个数；同时它对控制顶点的数量不敏感。对存在大量的控制顶 点的曲面特别有效。北京航空航天大学在曲线曲面光顺方面作了大量工作。 2 3 光顺的检测 曲线、曲面是否光顺应该通过什么方法来检测呢? 光顺性的检测也是相对比 较复杂的。到目前为止，有如下几种比较可行的方法： 1 曲线的光顺分析 曲线的分析手段有下面几种： ( 1 ) 显示构造样条曲线的控制多边形和对应的控制顶点。 ( 2 ) 画出曲线的曲率随弧长变化的曲率图。 ( 3 ) 在原曲线上画出表征曲率半径的矢量刷图。 ( 4 ) 在原曲线上显示极值点和最值点。 ( 5 ) 画出挠率随弧长变化的挠率图。 根据以上信息可快速地根据有关光顺准贝i j 进行进一步的分析和修正调整。 2 曲面的光顺分析 曲面的光顺分析相对曲线来说比较复杂，就目前所采用的方法，把它归类为以 下四种： ( 1 ) 基于曲率的分析方法：曲率是曲面几何属性中的重要内容，而且曲面的曲 率与曲面的机械加工制造密切相关，所以曲率分析是曲面光顺分析的重要组成部 分，利用曲率进行曲面的光顺分析有以下几种： 1 ) 曲率的颜色映射曲率云图。该曲率云图把曲面的每一点处的曲率值用可区别 的颜色和亮度值直观地表示出来，并提供不同颜色所对应的曲率值线性柱状对照 表。所以我们可以根据曲率云图的颜色信息较直观地看出曲面的曲率分布情况，进 而得到曲面的总体信息。一般可提供云图的曲率主要有：反映曲面在某一点的最小 法曲率和最大法曲率，即两主曲率：平均曲率：高斯曲率和绝对曲率。 2 ) 绘制出等曲率线。把曲面上具有相同曲率( 如高斯曲率) 的点连接成的线称 之为等曲率线。它同样可以反映出曲面的总体曲率的分白信息。 3 ) 绘制反映曲面每一点处曲率的矢量刷图。在曲面的每点处，以曲面的法 矢为方向、以咳点曲面的曲率( 如高斯曲率) 半径为长度绘制出可反映曲面曲率变化 的矢量刷图。 ( 2 ) 基于曲面的光照模型的方法：如今某些工业产品的外形乃至细微局部的光 顺性的要求十分高，但由于计算机的屏幕和分辨率的限制，很难对其光顺性进行正 确的判断。特别是一些如汽车、船舶、飞机等产品的外覆盖件，尺寸大、要求高， 仅仅利用曲率云图或等曲率线等方法已经很难满足曲面分析的要求。基于曲面的光 照模型的分析方法正是提供了一种比较直观、与工程人员的利用平行光束来分析曲 面光顺性的习惯作法相接近。它主要有以下几种方式： 1 ) 绘制等照度线图。照度是平行光源的单位方向与曲面某一点处的法矢两向 量的内积。将曲面上具有等照度的点连接而成的线叫等照度线。我门可以根据等照 度线的走向和分布来分析曲面的光顺性。 2 ) 绘制反射线图。通过在确定一视点的基础上，一曲面上的某一点为始点， 以该点与视点所成的如射光的方向为方向的射线如果可与以直线型光源相交，则说 明直线型光源发出的一条光线能照射在曲面的该点上，而且可以反射到视点。我们 就把曲面上具有这样性质的点叫做光源在去曲面上的反射点。由曲面上所有反射点 连接而成的线称为光源在该曲面上的反射线。我们便可以利用这反射线的分布是否 均匀、分布的有无规则来分析曲面的光顺性。 3 ) 绘制高亮斑马线图。将一理想化为无限长的光源置于曲面上方，令曲面上 某一点的法矢与光源的垂直距离为d ，我们把曲面上由使d = 0 的点连接而成的线称 为光源在该曲面上的高亮斑马线。如果给定一半径，在曲面上满足d ，的点的集 合称为高亮斑马条纹。绘制的高亮斑马线可以把曲面上的不连续在高亮斑马线上扩 大1 阶次，同时它不依赖视点。因此，我们可以通过观察高亮斑马线来分析曲面的 光顺性。 4 ) 绘制真实感图形。利用图形学技术，通过光源设置、辉度调节、材质性能、 透明处理和背景搭配技巧渲染出十分逼真悦目的实感图形，我们可以根据这种图形 进行曲面的光顺性分析。但这种方法往往需要较高的硬件配置和较长的计算时间。 ( 3 ) 基于绘制曲面等高线的方法：通过评价等高线的光顺性、疏密变化是否均 匀等来分析曲面的光顺性。 上述方法各有其特点，基于曲率的方法可以让我们获取有关曲面的总体或局部 的曲率信息、可以识别出导致曲面出现波动或凹凸的区域、找到曲面的曲率的极大 或极小值的分布、曲面与相邻曲面的连续性等信息。基于光照模型的方法主要反映 了曲面的法矢的变化情况，而且可以克服计算机的一些缺陷，可以从总体上把曲面 的光顺美感、造型风格等信息。实践中，往往几种方法综合起来综合考虑。 第三章蓝线的能量光顺方法及选点修改法 目前，光顺处理的方法中，根据每次修改的型值点( 或控制点) 个数大致可以 分为两种：局部修改法 1 , 8 3 1 】和整体修改法【t 2 3 5 ，2 2 2 6 】。如每次仅修改少数型值点( 或 控制点) ，则称为局部修改法，通常也称为选点修改法i t , s , 3 1 】。如每次修改全部型值 点( 或控制点) ，则称为整体修改法，其中最常用的是能量法( 4 8 1 。 本文提出的光顺算法是基于能量法的，所以下面对能量法做一简单介绍。 3 1 能量法原理 能量法是基于能量极值原理给出的一种包括光顺s 维空间曲线和大挠度曲线在 内的光顺方法，它的力学模型很直观。设给定通过型值点列亏吼( i = o ，栉) 的曲 线为尹= 焉( f ) 倪5 ，光顺后的曲线为尹= f ( s ) 倪，型值点磊贸( f = o ，疗) ，矽，弓 分别为光顺前后的控制顶点。把尹= 尹( s ) 孵5 看作过型值点磊的样条弹性线，在型 值点乒与龟之间挂一条弹性为屈的小弹簧，使磊靠近霉，如图3 1 所示。因此，包 括样条和小弹簧在内的整个系统的能量为： e = 三口霎弦幽+ 吉驯乒耐 ( 3 ) 式中口= ( 彤) 2 ，k 为曲线尹= 尹( s ) 的曲率。式( 3 i 1 ) 即为光顺 的目标函数，求龟使 得e = m i n 即得光顺后的曲线尹= 尹( s ) 贸。 图3 1能量法模型 从以下两个极端情况的分析司以看出这些权因子的具体意义： ( 1 ) 当取所有的屈= o ，口o 时，从e = m i n 立即有f k ? d s = 0 曲线变成一条 直线，表示了一条最光顺的直线。 ( 2 ) 当取所有的口= 0 ，届0 时，从e = m i n 可导出于= 龟，于是问题就变为插 值问题。这表明，所有光顺后的型值点与原型值点相同，没有任何偏差。 当屏取较大数时，光顺后的型值点q 与原型值点只的偏差就比较小，但曲线 应变能可能较大，曲线的光顺性较差。反之，口取较大数时，曲线应变能就比较小， 曲线较光顺，但光顺后的型值点q 与原型值点p 只的偏差可能较大，使曲线的逼近 性较差。因此，称口为光顺权， 屈) 为偏差权。光顺和偏差在这就体现了一种对立 统一的关系。操作者的任务就是根据具体的问题，适当选取光顺权口和偏差权 屈) ， 使光顺和偏差两个方面都得到考虑。 3 2 离散能量法 给定型值点列露( f _ o ，1 ，胛) 锨2 ，将应变能p 2 d s 离散为 寺一那 智f f + + i ”川 其中亏：兰亏垒为单位弦向量，= 峪一霉一。1 1 。 离散能量法的目标函数成为： 善志( 警一半) + ；屈忙龟0 2 ( 3 2 ) 鲁+ t + 。l + ； 7 j