CAD中几何模型简化技术的研究 PhDthesis_2009_朱平.pdf

《CAD中几何模型简化技术的研究 PhDthesis_2009_朱平.pdf》由会员分享，可在线阅读，更多相关《CAD中几何模型简化技术的研究 PhDthesis_2009_朱平.pdf（109页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 分类号:TP391.72 单位代码:10335 密 级:学 号:10606102 博士学位论文 中文论文题目中文论文题目:CAD 中中几何模型几何模型简化技术的研究简化技术的研究 英文论文题目英文论文题目:Research on geometric modeling simplification technology in CAD 申请人姓名:朱 平 指导教师:汪 国 昭 教授 专业名称:应 用 数 学 研究方向:计算机辅助几何设计与图形学 所在学院:理 学 院 论文提交日期论文提交日期:2009 年 4 月 浙 江 大 学 申请博士学位论文 CAD 中几何模型简化技术的研究 作 者：朱 平

2、 学科专业：计算机辅助几何设计与图形学 指导教师：汪 国 昭 教 授 浙江大学数学系 浙江大学计算机图像图形研究所 2009 年 4 月 Research on geometric modeling simplification technology in CAD Zhu Ping Supervisor:Prof.Wang Guozhao Submitted in total fulfillment of the requirements for the degree of Ph.D.in Applied Mathematics Institute of Computer Graphics a

3、nd Image Processing Department of Mathematics Zhejiang University,Hangzhou,P.R.China April,2009 CAD 中几何模型简化技术的研究中几何模型简化技术的研究 论文作者签名论文作者签名:指导教师签名指导教师签名:论文评阅人 1：(姓名职称单位,下同)评阅人 2：(隐名评阅学位论文省略)评阅人 3：评阅人 4：评阅人 5：答辩委员会主席：(姓名职称单位)委员 1：委员 2：委员 3：委员 4：委员 5：答辩日期：Research on geometric modeling simplification te

4、chnology in CAD Authors signature:Supervisor s signature:External Reviewers:(姓名职称单位,下同)(隐名评阅学位论文省略)Examining Committee Chairperson:(姓名职称单位)Examining Committee Members:Date of oral defence：浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 浙江大学浙江大学

5、或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：签字日期：年 月 日 学位论文版权使用授权书 本学位论文作者完全了解 浙江大学浙江大学 有权保留并向国家有关部门或机构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 浙江大学浙江大学 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名：导师签名：签字日期：年 月 日 签字日期：年 月 日 摘 要 I 摘摘 要要 CAD 等几何造型系

6、统希望建模工具能用更少的数据量表示几何模型，这有利于节省计算时间，提高工作效率，加快网络传输速度。Bzier 曲线曲面和 B-样条是 CAD/CAM 系统中广泛使用的造型工具，简化它们的建模技术对 CAD 系统有着实际的意义。本文对此展开深入研究，主要是两方面：Bzier 曲线曲面的近似合并和变次数 B-样条。主要研究成果及创新点如下：首先，传统的一般性的Bzier曲线近似合并只考虑曲线的参数连续。而我们考虑利用曲线的几何信息来研究合并问题，提出了Bzier曲线在L2范数下保端点G2连续的最佳合并算法，即保持两条原曲线在左右端点的位置、切向和曲率大小。为了避免在两个端点处出现奇异点，我们还对误

7、差定义作了修正，增加了正则项。与传统的保端点C2连续的方法相比，我们的方法能直接合并不同次数的两条曲线，显式地得到合并曲线的控制顶点，并且误差更小，因此逼近效果更好。如果要得到更高次的合并曲线，只需要提高合并次数，无需象以前的方法那样对原曲线进行升阶运算。其次，为了对CAD系统中的几何数据进行压缩，研究了两张相邻张量积Bzier曲面的合并问题。为了能更好地进行曲面合并逼近，利用张量积Bzier曲面细分后的矩阵表示给出了相邻张量积曲面可精确合并的充要条件，并在此基础上通过广义逆矩阵的方法求解出在L2范数下合并逼近后的张量积Bzier曲面，得到了其控制顶点的显示表达式。与此同时，对带角点插值条件的

8、曲面合并逼近也给出了结果。由于广义逆矩阵可以方便地求得最小二乘解，因此得到了能够显式表示，机时最省且逼近效果好的合并逼近算法。接着，我们研究了变次数B-样条。变次数B-样条是一种能够简化几何模型，压缩数据量的新的B-样条形式。本文对此进行了初步探讨，并第一次给出了最大变化次数小于3的变次数B-样条基函数的具体表达式，系统地给出了基函数的性质与曲线构造，并将之应用于样条曲线的升阶与合并，有效地简化了曲线模型。在利用变次数B-样条将代数双曲B-样条的升阶解释为几何割角之后，我们以此为基础得到了代数双曲B-样条的几何生成算法。由于代数双曲B-样条对造型系统有重要的意义，如能够精确表示双曲线、悬链线等

9、常用的工程曲线，此算法有着实II 浙江大学博士学位论文 际的应用价值。同样地，利用变次数样条，也可以将其他样条曲线，如NUAT B-样条的升阶解释为几何割角过程，并得到它的几何构造。最后，鉴于以往的三角或双曲多项式样条模型定义在均匀节点上的缺陷，本文以代数双曲混合B-样条为例，将其推广到非均匀节点上去，并拥有B-基等很多良好的几何性质。关键词：关键词：CAGD；Bzier 曲线；B-样条；近似合并；几何连续；广义逆矩阵；张量积 Bzier 曲面；变次数 B-样条；代数双曲 B-样条；升阶割角；几何构造；代数双曲混合 B-样条；B-基 Abstract III Abstract It is be

10、tter to represent geometric model with less amount of data by modeling tools in CAD modeling systems.This is good for reducing computing time,improving the efficiency of systems,speeding up the network transmission speed.Bzier curves,surfaces and B-spline are widely used as modeling tools in CAD/CAM

11、.Their models simplification technology has practical significance on the CAD systems.In this paper,we have made in-depth studies on simplification technology,mainly two aspects:approximate merging of Bzier curves,surfaces and multi-degree B-spline.The main creative results are as follows.Firstly,in

12、 constrast to traditional methods,which only considered the componen-ts of the curves separately,we used geometric information about the curves to generate the merged curve and proposed optimal approximate merging of a pair of Bzier curves with G2-continuity in L2 norm,where positions,tangents and c

13、urvatures were preserved at the two endpoints.For avoiding singular at the two endpoints,we amended the error definition and added one regularization term.Compared to traditional methods,our method could directly obtain control points of the merged curve,regardless of the degrees of the original cur

14、ves and the approximation error was better.Furthermore,we obtained a higher degree merged curve through raising the merged Bzier curves degree instead of degree elevation of the original Bzier curves.Secondly,approximate merging of two adjacent tensor product Bzier surfaces was investigated to guara

15、ntee the compression of geometric data in CAD systems.Sufficient and necessary condition for precise merging of adjacent tensor product surfaces was obtained by using the matrix representation of subdivided Bzier surface,then merged tensor product Bzier surface was solved by generalized inverse matr

16、ices in L2 norm based on precise merging condition and explicit representation of the merged surfaces control points was also obtained.At the same time,the result of approximate merging with corner interpolation was showed first time.Since theIV 浙江大学博士学位论文 minimal least squares solution could be dir

17、ectly obtained by generalized inverse matrics,an approximate merging algorithm possessing explicit formula,less time consumption and better approximation result was found.After that,multi-degree B-spline(MD-spline)was investigated.Multi-degree B-spline is a new B-spline form to simplify geometric mo

18、del and compress the amount of data.This paper made a preliminary study,and basis function formulae of MD-splines which maximal variational degree was lower than 3 was investigated first time.We gave basis functions properties and curves construction completely,then applied them to degree elevation

19、and mergence of spline curves for simplifing curve model.After degree elevation of algebraic hyperbolic B-spline can be interpreted as corner cutting using multi-degree B-spline successfully,we obtained geometric construction of algebraic hyperbolic B-spline based on above conclusion.Since algebraic

20、 hyperbolic B-spline has important meaning for modeling system,for example,it can represent hyperbola,catenary explicitly etc common engineering curve,this algorithm processes practical application value.Similarly,we can make use of multi-degree spline to obtain geometric construction of other splin

21、es,such as NUAT B-spline.Finally,in view of the previous triangle or hyperbolic polynomial spline model at uniform knots on the definition of the defect,taking a algebraic hyperbolic blending B-spline as an example,this paper extended to non-uniform knots,and the new spline holds a lot of good geome

22、tric properties such as B-basis.Key words:CAGD;Bzier curve;B-spline;approximate merging;geometric continuity;generalized inverse matrics;tensor product Bzier surface;multi-degree B-spline;algebraic hyperbolic B-spline;degree elevation by corner cutting;geometric construction;algebraic hyperbolic ble

23、nding B-spline;B-basis 目 录 V 目 录 摘摘 要要I AbstractIII 目录目录V 第一章第一章 绪论绪论 1 1.1 自由曲线曲面造型技术 2 1.2 曲线曲面的近似合并方法 5 1.3 B-样条的扩展10 1.4 本文的结构16 第二章第二章 Bzier 曲线保端点曲线保端点 G2连续的连续的合并方法合并方法17 2.1 引言17 2.2 几何连续的曲线合并问题19 2.3 G2连续条件20 2.4 G2连续的 Bzier 曲线合并算法20 2.5 带点限制的 G2连续合并算法26 2.6 小结30 第三章第三章 广义逆矩阵在合并算法中的应广义逆矩阵在合并算

24、法中的应用用31 3.1 引言31 3.2 张量积 Bzier 曲面的合并逼近问题33 3.3 精确合并的矩阵表示34 3.4 不带插值条件的合并算法35 3.5 带角点高阶插值的张量积 Bzier 曲面合并36 3.6 误差分析38 3.7 数值实例39 3.8 曲线合并41 3.9 小结43 第四章第四章 变次数变次数 B-样条样条45 4.1 引言45 VI 浙江大学博士毕业论文 4.2 变次数 B-样条46 4.3 代数双曲 B-样条的几何构造57 4.4 小结66 第五章第五章 代数双曲混合代数双曲混合 B-样样条条69 5.1 引言69 5.2 关于双曲函数零点的定理69 5.3

25、代数双曲混合 B-样条基70 5.4 代数双曲混合 B-样条曲线75 5.5 代数双曲混合 B-样条是 B-基79 5.6 小结82 第六章第六章 总结总结与展望与展望83 参考文参考文献献85 发表或录用论发表或录用论文目录文目录95 作者作者简历简历97 致致谢谢99 第一章 绪论 1 第一章第一章 绪论绪论 计算机辅助几何设计(Computer Aided Geometric Design,简称CAGD)是一门以函数逼近论、微分几何以及数据技术为理论基础1,主要研究在计算机图形图像环境下进行几何造型设计、修改、分析及优化的技术。它最早起源于飞机、船舶的外形放样工艺，由 Bzier、Coo

26、ns 等大师于 20 世纪 60 年代奠定其理论基础，并在 1974 年召开的 Utah 会议上由 Barnhill 和 Riesenfeld2正式命名。从此，以几何造型方法为主的 CAGD 以一门崭新的学科出现。而 Computer Aided Design、Computer Aided Geometric Design、Siggraph 以及计算机辅助设计与图形学学报等国内外专业期刊、会议的创办更是显著推动了 CAGD 的进步。CAGD 的出现和发展既是现代工业发展的需要，又对现代工业的发展起到巨大的推动作用，为我国走新型工业化道路奠定了坚实基础。在 CAGD 技术的支持下，用户只需用基本

27、的数学知识，不必构造复杂的几何模型，就能够快速而精确地完成二维或三维几何图形的构建、修改与数据分析，得到需要的设计参数，这将极大地缩短产品的设计周期，提高产品质量，降低生产成本，为增强企业的竞争与创新能力做出了重要贡献。经过几十年的发展，CAGD 的理论不断深化，体系不断完善，方法日益丰富，目前已广泛应用到建筑设计、机械加工、文体影视等各个重要领域。正因为 CAGD 的广泛应用性，注定了它是一个与其他多门学科相互紧密联系，相互促进发展的交叉学科。早期主要是机械设计师为解决 CAD/CAM 中一些棘手的问题，如设计周期长、制造精度低、造型修改困难等，于是探索以数学方法为主，研究曲线曲面分析与设计

28、的 CAGD 技术，以此促进产业的发展。现在如计算机动画设计师也要求利用 CAGD 技术对人物等造型，进行灵活有效地建模和操作，非常好地改善了视觉效果。随着图形软硬件和工业信息化步伐的进步，随着激光扫描仪等三维采样技术的完善，CAGD 的研究领域急剧扩大，并向其他学科不断渗透。CAGD 已经从传统的曲线曲面表示转到曲面重建、变形、压缩等前沿领域，并可直接应用到如医学图像处理、动画仿真等新兴学科。国际上也有越来越多以 CAGD 技术为基础的商用软件，如 AutoCAD、Solidworks 等等，它们对 CAGD 技术的普及与生产生活起到了重要作用。正因为有着如此多的发 2 浙江大学博士学位论文

29、 展源泉和广泛应用，CAGD 一直是计算机学科中一个充满前景和活力的研究方向，其影响日益广泛。它的每一项突破都会对诸如计算机图形学、图像处理、计算机视觉、机器人技术、虚拟现实等学科的发展起到巨大的推动作用。1.1 自由自由曲线曲面造型技术曲线曲面造型技术 曲线曲面的构造表示和逼近是 CAGD 的主要任务。要在计算机内表示某工业产品的几何外形，其形状的描述应尽可能保持原产品的几何特征，从计算机对形状处理、数据分析的角度来看，应满足以下条件3：1.唯一性：既有给定的条件确定的几何外形是唯一的，这是对形状数学描述的首项要求；2.易于定界：形状总是有界的，其数学描述应易于定界；3.易于形状的修改和控制

30、；4.几何直观；5.算法简单易行；6.统一性：能统一表示各种形状及处理各种情况。曲线曲面造型技术起源于二战时汽车、飞机、船舶、叶轮等的外形放样工艺。能用数学方程表示出来的曲线曲面，我们称之为规则的曲线曲面，如椭圆、柱体、锥体等，它们可以用隐函数或二次方程表示。那些不能用二次方程表示出来的曲线曲面就称之为自由曲线曲面。在我们的日常生产生活中，碰到的更多的是自由曲线曲面(Free Form Curves and Surfaces)，因此 CAGD 的重要研究内容之一就是研究它们的几何形状表示与算法。CAGD 中的曲线曲面造型技术诞生于 50 年代，最早由 Schoenberg4于 1946年提出插

31、值样条函数，以解决插值问题，并构造参数连续的插值曲线曲面。但真正奠定理论基础是 Bzier、Coons 等大师在上世纪六十年代完成的。如今经历了超过半个世纪的发展，自由曲线曲面表示和造型技术形成了以非均匀有理 B-样条(NURBS:non-uniform rational B-spline)参数化特征设计(Parameterized and Characteristic Design)和隐式代数曲线曲面表示(Implicit Algebraic Surface Representation)这两类方法为主体，以插值(Interpolation)、拟合(Fitting)、逼近(Approxima

32、tion)这三种手段为骨架的几何理论体系5。第一章 绪论 3 现在就让我们回顾一下它的几个重要发展阶段。1963 年美国波音(Boeing)飞机公司的福格森(Ferguson)首先提出了将曲线曲面表示为参数的矢函数方法。他最早引入了参数三次曲线，使用23(1,)t tt为基函数，构造了由四个角点的位置和两个方向的切矢量定义的 Ferguson 双三次曲面片6-7。在此之前，曲线的描述一直是采用显式的函数()yy x=或隐式方程(,)0F x y=的形式，曲面描述也是采用(,)zz x y=或(,)0F x y z=的形式。福格森采用的自由曲线曲面参数形式的表示方法具有几何不变性、易于坐标变换等

33、优点。从此，曲线曲面的参数形式成为形状数学描述的标准形式。1964 年，美国麻省理工学院(Massachusetts Institute of Technology)的机械工程系教授孔斯(Coons,1912-1979)8在给国防部的技术报告中引进了超限插值这个全新的数学概念，按照一定的连续阶要求把若干个较小的曲面片拼接成所要设计的曲面，其边界线可以是具有一定连续阶的任何曲线。1967 年，孔斯进一步推广了他的思想9。在 CAGD 实践中，应用最多的就是 Coons 双三次曲面片。但是它与 Ferguson 双三次曲面片都存在形状控制与拼接的问题，区别仅在于它将角点扭矢由零矢量改为非零矢量。法

34、国雷诺(Renault)汽车公司的工程师贝塞尔(Bzier)于 1971 年提出了一种由控制多边形定义曲线的方法。贝塞尔方法简单实用，设计人员只要移动控制顶点就可修改几何形状。以此为基础，贝塞尔在雷诺公司建立了自由曲线曲面设计系统(UNISURF CAD)10-12。最初贝塞尔提出的曲线表达式是：01101001()()01 ,()(1)1()1,(),1,2,(1)!,1,2,nnjjjjjnnnjjjjjtA tttdtA tA tjnjdttjn=PaaP aPP 其中,0,1,jjn=a是控制多边形的顶点。这一定义十分奇特，令人难以接受。随后，Gordon 和 Riesenfeld13

35、等对 Bzier 方法进行深入研究。到 1972 年，Forrest14才提出现在通用的定义，指出它恰好就是 Bernstein 基与控制顶点的线性组合，即：0()(),01nniiitB tt=PP 4 浙江大学博士学位论文 其中()(1),0,1,nn iiinB tttini=为n次 Bernstein 基函数。用贝塞尔方法生成的贝塞尔曲线具有几何不变性、凸包性(Convex hull)、保凸性、端点插值等很好的性质，并且它的升降阶、离散、插值、递归求值等算法简单，易于修改、控制，这大大推进了曲线曲面设计。贝塞尔的方法在 CAGD 中占有重要地位，为曲线曲面造型技术的进一步发展奠定了坚实

36、基础，是 CAGD 发展中的重要里程碑。稍早于贝塞尔，法国雪铁龙(Citron)汽车公司的德卡斯特里奥(de Caasteljau)也曾独立地研究发展了同样的方法，但结果从未公开发表。1983 年，Farin15更进一步地研究了能统一表示圆锥曲线与自由曲线的有理 Bzier 曲线。此外，文献16-18对有理参数曲线进行了广泛的研究。从 70 年代中期开始，国内对 Bzier 方法也做了大量的卓有成效的研究19-31。如文献32-33引进几何不变量的方法，彻底解决了平面三次参数曲线的分类和控制问题。他们的工作对 CAGD 作出了重要贡献。B-样条是曲线曲面设计中另一种十分重要的技术。1972 年

37、，de Boor 给出了关于 B-样条的一套标准算法。之后，美国通用(GE)汽车公司的 Gordon 和Riesenfeld34把 Bernstein 基()niBt换成n次 B-样条基，从而将 B-样条基函数推广到矢值形式，并提出了 B-样条曲线曲面。B-样条曲线几乎既拥有 Bzier 曲线的几何特性，又拥有形状局部可调及连续阶数可调等 Bzier 曲线所没有的特性，克服了其由于整体表示带来的不具备局部性质的缺点，具有表示与设计自由型曲线曲面的强大功能。关于 B-样条的理论，早在 1946 年 Schoenberg4就已经提出，但论文直到 1967 年才发表。1972 年 De Boor35

38、和 Cox36分别独立地给出 B-样条计算的标准算法。1980 年，Boehm37和 Cohen38等人给出了 B-样条曲线的节点插入技术。其次，Prautzsch39等人又发展了 B-样条曲线的升阶技术。还有，Lyche和 Morken40-41给出在规定误差范围内的节点消去算法，这在节点过密的情况下，具有实际的工程意义。B-样条曲线的降阶算法也有丰富的成果42-43。但随着生产的发展，B-样条方法显示出明显不足如不能精确表示圆锥截线等等。同时 Bzier 样条和 B-样条两种设计手段并存的局面使工业界很不满意，因 为这容易造成生产管理的混乱。于是，人们希望找到一种统一的数学方法。1975

39、年，美国锡拉丘兹(Syracuse)大学的福斯普里尔(Versprille)44在他的博士论文中 第一章 绪论 5 首先提出有理 B-样条方法。Tiller 论述了有理 B-样条曲线曲面的具体应用45。此后，Piegl、Tiller 等人46-53更系统地研究了有理 B-样条曲线曲面的构造和控制问题。由于他们的出色工作，至 20 世纪 80 年代后期，非均匀有理 B-样条(NURBS)成为用于曲线曲面描述的最为广泛的数学方法。NURBS曲线最突出的优点是既有B-样条曲线形状局部可调及连续阶数可调的优点，又兼有有理 Bzier 曲线可精确表示二次曲线的特性，从而能用统一的数学形式表示规则曲线曲面

40、和自由曲线曲面。由于 NURBS 方法的这些突出优点，在 1991 年国际标准化组织(ISO)正式颁布的工业产品数据交换的 STEP 标准中，把 NURBS 作为自由曲线曲面的唯一定义54。1992 年，NURBS 又成为独立与设备的交互图形编程的 PHIGS(Programmers Hierarchical Interactive Graphics System)55的国际标准。而国际著名的 CAD 软件公司如 Autodesk、UGS 等也把造型系统首先建立在 NURBS 的数学模型上，从而使 NURBS 方法成为曲线曲面造型技术发展趋势中最重要的基础。综上所述，自由曲线曲面造型技术是 C

41、AGD 的核心问题，Bzier 样条和 B-样条则是几何设计的重要手段。NURBS 由于数学形式的统一性成为 CAD/CAM的工业标准。随着计算机技术的不断进步和工业设计的巨大需求，我们这门学科还将继续取得更大的成就。1.2 曲线曲面的近似合并方法曲线曲面的近似合并方法 随着全球化的进一步加深，产品设计的信息化、网络化得到了极大发展，异地设计、异地加工也变得司空见惯。这使得大量的几何模型数据在不同的 CAD系统之间频繁地传输和交换。由于几何模型是由不同基函数表示的，且数据是海量的，这给网络传输造成了很大负担，使得几何信息容易丢失，并极大妨碍了CAD 系统的工作效率。为了在满足信息精度的条件下，

42、加快传输速度、减少传输时间，就需要对几何模型进行简化。于是，Hoschek56在 1987 年提出了样条曲线的近似转化思想，它分为降阶逼近和近似合并两个方面。降阶逼近就是用一条新的低次参数曲线曲面去逼近原来 的高次曲线曲面，并且使误差尽可能的小；而近似合并就是用一整段较低次参数 曲线曲面去逼近两段或多段相邻的曲线曲面，并使几何形状尽可能地接近，但表 6 浙江大学博士学位论文 示的几何数据量更少。这两种运算都能够显著的简化几何模型并压缩数据量，有利于 CAD 系统之间的数据交换与传输。1.2.1 曲线曲面降阶方法 由于 CAGD 的一个主要研究对象是 Bzier 形式，因此这些年来，国内外学者对

43、降阶算法的研究主要围绕 Bzier 曲线曲面进行57-90。总的来说，降阶逼近方法可分为两类。(1)基于控制顶点逼近的几何方法。最初 Hoschek56提出的降阶方法就是其中之一。他考虑的是保端点几何连续的降阶。如n次曲线0()nniiiB t=XV降阶至()m nm次曲线0()mmiiiBt=YW。对 G1连续，他研究的是 Bzier 曲线降至三次的算法；对 G2连续，他研究的是 Bzier 曲线降至五次的算法。这就需要满足：对 G1连续，0010110,()=+WV WVVV，121,()mnmnnn=+WV WVVV；对 G2连续还需有，2211121110()()=+WVVVVV，22

44、1212121()()mnnnnn=+WVVVVV，这里1(1)(1)m nn m=。算法的大致过程就是先对原曲线均匀采样，再找一条曲线插值这些采样点，并逼近原曲线，使得误差最小。这里误差定义为两条曲线对应参数点的最大距离：max|max|()()|jjjtt=XY。jt为对应的采样参数。在使误差最小的过程中，需要对采样参数进行不断地调整，使得误差向量能垂直或接近垂直于()itY。误差向量()()iiitt=YX,()iit=PX。每一次调整，it 是旧参数，it是更新后的参数：/iiittc=+。可以是()tY的弧长，ic 是点iP的映射偏移量（见下图）。第一章 绪论 7 图 1.1 Hos

45、chek 算法的参数调整 Hoschek 只是对降阶逼近做了简单的研究，其算法最大的缺点是需要对采样参数进行调整，这需要浪费大量的时间，且没有降阶曲线的显示表达。其他类似的算法还有，Forrest 的逆升阶算法14、Danneberg 的分段插值逼近算法91、Moore 的面积极小反求降阶曲线算法92等等。(2)基于基转换的代数方法。由于正交函数能很容易的实现在某些pL范数下的最佳逼近，这类方法主要就是将 Bernstein 基转化为一类正交基，降阶，再变为Bernstein 基，最后得到高精度的降阶逼近算法。这些利用的有 Chebyshev 基93、Legendre 基75、Jocabi61

46、基等。1.2.2 曲线曲面合并方法 近似合并是简化 CAD 系统中几何模型的另一种方法。但是相对于降阶来说，目前的成果还比较少，研究还很不充分。在 Hoschek 提出近似合并问题的文献56中，作者仅在末尾提到了应用前面的降阶方法来解决合并问题，没有详细展开。在这之后，Hu94在 2001 年 CAD 期刊上发表的成果可以说是合并问题上的重要进展，是真正完美地解决了近似合并问题。问题描述：两条都是n次的 Bzier 曲线()uP和()vQ，其控制顶点分别是iP和(0,1,)iin=Q。近似合并就是找到一条新的n次 Bzier 曲线()tR，控制顶点为(0,1,)iin=R，使得()tR与()t

47、R的距离(,)d R R在0,1内最小。这里，00()0()()11nniiinniiitBtttBt=PRQ 而是细分参数。8 浙江大学博士学位论文 文中94首先通过证明得到两条原曲线()uP和()vQ能够精确合并的充要条件：0,0,1,iiin iin=PQ。这里是一个与有关的取值。随后，作者分别探求了在1L范数和2L范数下的合并曲线，其误差定义分别为20(),()|niiidtt=RRRR和120(),()()()dttttdt=RRRR。其主要思想就是利用控制顶点扰动法，得到拉格朗日函数并使之最小化，再算出控制顶点的扰动量，最后使用递归算法得到合并后 Bzier 曲线的控制顶点。例如下

48、图，都是两条三次 Bzier 曲线的近似合并。图 1.2(a)1L范数下的合并结果 图 1.2(b)2L范数下的合并结果 从上图，可以看出算法的效果很好。除此之外，保端点高阶插值以及带点限制（即合并曲线插值原曲线的部分点）的近似合并也一并被考虑。图 1.3(a)两端点重合的合并 图 1.3(b)保端点一阶插值的合并 上图是两条四次 Bzier 曲线在1L范数下的合并。第一张 绪论 9 图 1.4(a)插值参数是000.0,1.0uv=图 1.4(b)插值参数是0100.5,1.0,0.5uuv=上图是两条五次 Bzier 曲线带点限制的在2L范数下的合并。Hu94在文中最后指出，如果需要得到更

49、高次的合并曲线可以对原来的两条曲线先升阶再合并，并且得到的误差更小。效果见下图：图 1.5(a)直接合并成四次曲线 图 1.5(b)升阶后合并成五次曲线 上图是两条四次 Bzier 曲线的合并，可以看出升阶的效果更好。这篇文献之后，Hu 的方法还被应用到 B-样条曲线95、区间 Bzier 曲线96、有理 Bzier 曲线97等类型的近似合并上去。在曲面合并方面，目前仅文献98对此作了研究。文 献98研究了将两张相邻同次数的张量积 Bzier 曲面合并成一张次数相同的张量积曲面。主要方法是利用张量积曲面的离散性质，使合并曲面分别逼近两张原曲面，并利用求偏导的方法来得到误差最小的合并张量积 Bz

50、ier 曲面。文章还对保边界高阶插值的近似合并做了研究，分析了合并误差的上下界。同时指出对原曲面进行升阶得到的更高次合并曲面，其误差会更小。其效果如下98：10 浙江大学博士学位论文 图 1.6(a)两张相邻79次原曲面 图 1.6(b)79次不保边界插值合并曲面 图 1.6(c)99次不保边界插值合并曲面 图 1.6(d)79次保边界(2,2)阶插值合并曲面 纵观近似合并的研究，目前的结果还是初步的，不完善的，还没有扩展到所有的曲线曲面类型，方法上大多也是遵循 Hu94的算法，没有大的突破。这首先是由于合并问题实质上是一条曲线分段同时逼近几个曲线段，而不像降阶可以化归为一个曲线函数逼近另一个