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

分类号 TP391 72 单位代码 10335 密 级 学 号 10606102 博士学位论文 中文论文题目中文论文题目 CAD 中中几何模型几何模型简化技术的研究简化技术的研究 英文论文题目英文论文题目 Research on geometric modeling simplification technology in CAD 申请人姓名 朱 平 指导教师 汪 国 昭 教授 专业名称 应 用 数 学 研究方向 计算机辅助几何设计与图形学 所在学院 理 学 院 论文提交日期论文提交日期 2009 年 4 月 浙 江 大 学 申请博士学位论文 CAD 中几何模型简化技术的研究 作 者 朱 平 学科专业 计算机辅助几何设计与图形学 指导教师 汪 国 昭 教 授 浙江大学数学系 浙江大学计算机图像图形研究所 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 and 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 technology in CAD Author s signature Supervisor s signature External Reviewers 姓名 职称 单位 下同 隐名评阅学位论文省略 Examining Committee Chairperson 姓名 职称 单位 Examining Committee Members Date of oral defence 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发 表或撰写过的研究成果 也不包含为获得 浙江大学浙江大学 或其他教育机构的学位或 证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文作者签名 签字日期 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解 浙江大学浙江大学 有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘 允许论文被查阅和借阅 本人授权 浙江大学浙江大学 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播 可以采用影 印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 导师签名 签字日期 年 月 日 签字日期 年 月 日 摘 要 I 摘摘 要要 CAD 等几何造型系统希望建模工具能用更少的数据量表示几何模型 这有 利于节省计算时间 提高工作效率 加快网络传输速度 B zier 曲线曲面和 B 样条是 CAD CAM 系统中广泛使用的造型工具 简化它们的建模技术对 CAD 系 统有着实际的意义 本文对此展开深入研究 主要是两方面 B zier 曲线曲面的 近似合并和变次数 B 样条 主要研究成果及创新点如下 首先 传统的一般性的B zier曲线近似合并只考虑曲线的参数连续 而我们 考虑利用曲线的几何信息来研究合并问题 提出了B zier曲线在L2范数下保端点 G2连续的最佳合并算法 即保持两条原曲线在左右端点的位置 切向和曲率大小 为了避免在两个端点处出现奇异点 我们还对误差定义作了修正 增加了正则项 与传统的保端点C2连续的方法相比 我们的方法能直接合并不同次数的两条曲 线 显式地得到合并曲线的控制顶点 并且误差更小 因此逼近效果更好 如果 要得到更高次的合并曲线 只需要提高合并次数 无需象以前的方法那样对原曲 线进行升阶运算 其次 为了对CAD系统中的几何数据进行压缩 研究了两张相邻张量积 B zier曲面的合并问题 为了能更好地进行曲面合并逼近 利用张量积B zier曲 面细分后的矩阵表示给出了相邻张量积曲面可精确合并的充要条件 并在此基础 上通过广义逆矩阵的方法求解出在L2范数下合并逼近后的张量积B zier曲面 得 到了其控制顶点的显示表达式 与此同时 对带角点插值条件的曲面合并逼近也 给出了结果 由于广义逆矩阵可以方便地求得最小二乘解 因此得到了能够显式 表示 机时最省且逼近效果好的合并逼近算法 接着 我们研究了变次数B 样条 变次数B 样条是一种能够简化几何模型 压缩数据量的新的B 样条形式 本文对此进行了初步探讨 并第一次给出了最大 变化次数小于3的变次数B 样条基函数的具体表达式 系统地给出了基函数的性 质与曲线构造 并将之应用于样条曲线的升阶与合并 有效地简化了曲线模型 在利用变次数B 样条将代数双曲B 样条的升阶解释为几何割角之后 我们以此为 基础得到了代数双曲B 样条的几何生成算法 由于代数双曲B 样条对造型系统有 重要的意义 如能够精确表示双曲线 悬链线等常用的工程曲线 此算法有着实 II 浙江大学博士学位论文 际的应用价值 同样地 利用变次数样条 也可以将其他样条曲线 如NUAT B 样条的升阶解释为几何割角过程 并得到它的几何构造 最后 鉴于以往的三角或双曲多项式样条模型定义在均匀节点上的缺陷 本 文以代数双曲混合B 样条为例 将其推广到非均匀节点上去 并拥有B 基等很多 良好的几何性质 关键词 关键词 CAGD B zier 曲线 B 样条 近似合并 几何连续 广义逆矩阵 张 量积 B zier 曲面 变次数 B 样条 代数双曲 B 样条 升阶割角 几何构造 代 数双曲混合 B 样条 B 基 Abstract III Abstract It is better 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 B zier curves surfaces and B spline are widely used as modeling tools in CAD CAM 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 B zier curves surfaces and multi degree B spline The main creative results are as follows Firstly in 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 B zier curves with G2 continuity in L2 norm where positions tangents and curvatures 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 curves and the approximation error was better Furthermore we obtained a higher degree merged curve through raising the merged B zier curve s degree instead of degree elevation of the original B zier curves Secondly approximate merging of two adjacent tensor product B zier surfaces was investigated to guarantee 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 B zier surface then merged tensor product B zier surface was solved by generalized inverse matrices in L2 norm based on precise merging condition and explicit representation of the merged surface s control points was also obtained At the same time the result of approximate merging with corner interpolation was showed first time Since the IV 浙江大学博士学位论文 minimal least squares solution could be directly 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 model 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 function s properties and curve s construction completely then applied them to degree elevation 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 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 splines 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 geometric properties such as B basis Key words CAGD B zier curve B spline approximate merging geometric continuity generalized inverse matrics tensor product B zier surface multi degree B spline algebraic hyperbolic B spline degree elevation by corner cutting geometric construction algebraic hyperbolic blending B spline B basis 目 录 V 目 录 摘摘 要要 I Abstract III 目录目录 V 第一章第一章 绪论绪论 1 1 1 自由曲线曲面造型技术 2 1 2 曲线曲面的近似合并方法 5 1 3 B 样条的扩展 10 1 4 本文的结构 16 第二章第二章 B zier 曲线保端点曲线保端点 G2连续的连续的合并方法合并方法 17 2 1 引言 17 2 2 几何连续的曲线合并问题 19 2 3 G2连续条件 20 2 4 G2连续的 B zier 曲线合并算法 20 2 5 带点限制的 G2连续合并算法 26 2 6 小结 30 第三章第三章 广义逆矩阵在合并算法中的应广义逆矩阵在合并算法中的应用用 31 3 1 引言 31 3 2 张量积 B zier 曲面的合并逼近问题 33 3 3 精确合并的矩阵表示 34 3 4 不带插值条件的合并算法 35 3 5 带角点高阶插值的张量积 B zier 曲面合并 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 代数双曲混合 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 主要研究在计算机图形图 像环境下进行几何造型设计 修改 分析及优化的技术 它最早起源于飞机 船 舶的外形放样工艺 由 B zier Coons 等大师于 20 世纪 60 年代奠定其理论基础 并在 1974 年召开的 Utah 会议上由 Barnhill 和 Riesenfeld 2 正式命名 从此 以几 何造型方法为主的 CAGD 以一门崭新的学科出现 而 Computer Aided Design Computer Aided Geometric Design Siggraph 以及 计算机辅助设计与图形学 学报 等国内外专业期刊 会议的创办更是显著推动了 CAGD 的进步 CAGD 的出现和发展既是现代工业发展的需要 又对现代工业的发展起到巨 大的推动作用 为我国走新型工业化道路奠定了坚实基础 在 CAGD 技术的支 持下 用户只需用基本的数学知识 不必构造复杂的几何模型 就能够快速而精 确地完成二维或三维几何图形的构建 修改与数据分析 得到需要的设计参数 这将极大地缩短产品的设计周期 提高产品质量 降低生产成本 为增强企业的 竞争与创新能力做出了重要贡献 经过几十年的发展 CAGD 的理论不断深化 体系不断完善 方法日益丰富 目前已广泛应用到建筑设计 机械加工 文体影 视等各个重要领域 正因为 CAGD 的广泛应用性 注定了它是一个与其他多门学科相互紧密联 系 相互促进发展的交叉学科 早期主要是机械设计师为解决 CAD CAM 中一 些棘手的问题 如设计周期长 制造精度低 造型修改困难等 于是探索以数学 方法为主 研究曲线曲面分析与设计的 CAGD 技术 以此促进产业的发展 现 在如计算机动画设计师也要求利用 CAGD 技术对人物等造型 进行灵活有效地 建模和操作 非常好地改善了视觉效果 随着图形软硬件和工业信息化步伐的进 步 随着激光扫描仪等三维采样技术的完善 CAGD 的研究领域急剧扩大 并向 其他学科不断渗透 CAGD 已经从传统的曲线曲面表示转到曲面重建 变形 压 缩等前沿领域 并可直接应用到如医学图像处理 动画仿真等新兴学科 国际上 也有越来越多以 CAGD 技术为基础的商用软件 如 AutoCAD Solidworks 等等 它们对 CAGD 技术的普及与生产生活起到了重要作用 正因为有着如此多的发 2 浙江大学博士学位论文 展源泉和广泛应用 CAGD 一直是计算机学科中一个充满前景和活力的研究方 向 其影响日益广泛 它的每一项突破都会对诸如计算机图形学 图像处理 计 算机视觉 机器人技术 虚拟现实等学科的发展起到巨大的推动作用 1 1 自由自由曲线曲面造型技术曲线曲面造型技术 曲线曲面的构造表示和逼近是 CAGD 的主要任务 要在计算机内表示某工 业产品的几何外形 其形状的描述应尽可能保持原产品的几何特征 从计算机对 形状处理 数据分析的角度来看 应满足以下条件 3 1 唯一性 既有给定的条件确定的几何外形是唯一的 这是对形状数学描 述的首项要求 2 易于定界 形状总是有界的 其数学描述应易于定界 3 易于形状的修改和控制 4 几何直观 5 算法简单易行 6 统一性 能统一表示各种形状及处理各种情况 曲线曲面造型技术起源于二战时汽车 飞机 船舶 叶轮等的外形放样工艺 能用数学方程表示出来的曲线曲面 我们称之为规则的曲线曲面 如椭圆 柱体 锥体等 它们可以用隐函数或二次方程表示 那些不能用二次方程表示出来的曲 线曲面就称之为自由曲线曲面 在我们的日常生产生活中 碰到的更多的是自由 曲线曲面 Free Form Curves and Surfaces 因此 CAGD 的重要研究内容之一就 是研究它们的几何形状表示与算法 CAGD 中的曲线曲面造型技术诞生于 50 年代 最早由 Schoenberg 4 于 1946 年提出插值样条函数 以解决插值问题 并构造参数连续的插值曲线曲面 但真 正奠定理论基础是 B zier Coons 等大师在上世纪六十年代完成的 如今经历了 超过半个世纪的发展 自由曲线曲面表示和造型技术形成了以非均匀有理 B 样 条 NURBS non uniform rational B spline 参数化特征设计 Parameterized and Characteristic Design 和隐式代数曲线曲面表示 Implicit Algebraic Surface Representation 这两类方法为主体 以插值 Interpolation 拟合 Fitting 逼近 Approximation 这三种手段为骨架的几何理论体系 5 第一章 绪论 3 现在就让我们回顾一下它的几个重要发展阶段 1963 年美国波音 Boeing 飞机公司的福格森 Ferguson 首先提出了将曲线 曲面表示为参数的矢函数方法 他最早引入了参数三次曲线 使用 23 1 t tt为 基函数 构造了由四个角点的位置和两个方向的切矢量定义的 Ferguson 双三次 曲面片 6 7 在此之前 曲线的描述一直是采用显式的函数 yy x 或隐式方程 0F x y 的形式 曲面描述也是采用 zz x y 或 0F x y z 的形式 福格森 采用的自由曲线曲面参数形式的表示方法具有几何不变性 易于坐标变换等优 点 从此 曲线曲面的参数形式成为形状数学描述的标准形式 1964 年 美国麻省理工学院 Massachusetts Institute of Technology 的机械工 程系教授孔斯 Coons 1912 1979 8 在给国防部的技术报告中引进了超限插值这 个全新的数学概念 按照一定的连续阶要求把若干个较小的曲面片拼接成所要设 计的曲面 其边界线可以是具有一定连续阶的任何曲线 1967 年 孔斯进一步 推广了他的思想 9 在 CAGD 实践中 应用最多的就是 Coons 双三次曲面片 但是它与 Ferguson 双三次曲面片都存在形状控制与拼接的问题 区别仅在于它 将角点扭矢由零矢量改为非零矢量 法国雷诺 Renault 汽车公司的工程师贝塞尔 B zier 于 1971 年提出了一种 由控制多边形定义曲线的方法 贝塞尔方法简单实用 设计人员只要移动控制顶 点就可修改几何形状 以此为基础 贝塞尔在雷诺公司建立了自由曲线曲面设计 系统 UNISURF CAD 10 12 最初贝塞尔提出的曲线表达式是 0 11 0 1 001 01 1 1 1 1 2 1 1 2 n n jj j jjn nn j j jjj tA tt tdt A tA tjn jdtt jn Pa aP aPP 其中 0 1 j jn a是控制多边形的顶点 这一定义十分奇特 令人难以接受 随后 Gordon 和 Riesenfeld 13 等对 B zier 方法进行深入研究 到 1972 年 Forrest 14 才提出现在通用的定义 指出它恰好就是 Bernstein 基与控制顶点的线性组合 即 0 01 n n ii i tB tt PP 4 浙江大学博士学位论文 其中 1 0 1 nn ii i n B tttin i 为n次 Bernstein 基函数 用贝塞尔方法生 成的贝塞尔曲线具有几何不变性 凸包性 Convex hull 保凸性 端点插值等很 好的性质 并且它的升降阶 离散 插值 递归求值等算法简单 易于修改 控 制 这大大推进了曲线曲面设计 贝塞尔的方法在 CAGD 中占有重要地位 为曲线曲面造型技术的进一步发 展奠定了坚实基础 是 CAGD 发展中的重要里程碑 稍早于贝塞尔 法国雪铁 龙 Citron 汽车公司的德卡斯特里奥 de Caasteljau 也曾独立地研究发展了同样 的方法 但结果从未公开发表 1983 年 Farin 15 更进一步地研究了能统一表示 圆锥曲线与自由曲线的有理 B zier 曲线 此外 文献 16 18 对有理参数曲线进行了 广泛的研究 从 70 年代中期开始 国内对 B zier 方法也做了大量的卓有成效的 研究 19 31 如文献 32 33 引进几何不变量的方法 彻底解决了平面三次参数曲线的 分类和控制问题 他们的工作对 CAGD 作出了重要贡献 B 样条是曲线曲面设计中另一种十分重要的技术 1972 年 de Boor 给出了 关于 B 样条的一套标准算法 之后 美国通用 GE 汽车公司的 Gordon 和 Riesenfeld 34 把 Bernstein 基 n i Bt换成n次 B 样条基 从而将 B 样条基函数推广 到矢值形式 并提出了 B 样条曲线曲面 B 样条曲线几乎既拥有 B zier 曲线的 几何特性 又拥有形状局部可调及连续阶数可调等 B zier 曲线所没有的特性 克 服了其由于整体表示带来的不具备局部性质的缺点 具有表示与设计自由型曲线 曲面的强大功能 关于 B 样条的理论 早在 1946 年 Schoenberg 4 就已经提出 但论文直到 1967 年才发表 1972 年 De Boor 35 和 Cox 36 分别独立地给出 B 样条 计算的标准算法 1980 年 Boehm 37 和 Cohen 38 等人给出了 B 样条曲线的节点 插入技术 其次 Prautzsch 39 等人又发展了 B 样条曲线的升阶技术 还有 Lyche 和 Morken 40 41 给出在规定误差范围内的节点消去算法 这在节点过密的情况下 具有实际的工程意义 B 样条曲线的降阶算法也有丰富的成果 42 43 但随着生产的发展 B 样条方法显示出明显不足如不能精确表示圆锥截线等 等 同时 B zier 样条和 B 样条两种设计手段并存的局面使工业界很不满意 因 为这容易造成生产管理的混乱 于是 人们希望找到一种统一的数学方法 1975 年 美国锡拉丘兹 Syracuse 大学的福斯普里尔 Versprille 44 在他的博士论文中 第一章 绪论 5 首先提出有理 B 样条方法 Tiller 论述了有理 B 样条曲线曲面的具体应用 45 此 后 Piegl Tiller 等人 46 53 更系统地研究了有理 B 样条曲线曲面的构造和控制问 题 由于他们的出色工作 至 20 世纪 80 年代后期 非均匀有理 B 样条 NURBS 成为用于曲线曲面描述的最为广泛的数学方法 NURBS曲线最突出的优点是既有B 样条曲线形状局部可调及连续阶数可调 的优点 又兼有有理 B zier 曲线可精确表示二次曲线的特性 从而能用统一的数 学形式表示规则曲线曲面和自由曲线曲面 由于 NURBS 方法的这些突出优点 在 1991 年国际标准化组织 ISO 正式颁布的工业产品数据交换的 STEP 标准中 把 NURBS 作为自由曲线曲面的唯一定义 54 1992 年 NURBS 又成为独立与设 备的交互图形编程的 PHIGS Programmer s Hierarchical Interactive Graphics System 55 的国际标准 而国际著名的 CAD 软件公司如 Autodesk UGS 等也把 造型系统首先建立在 NURBS 的数学模型上 从而使 NURBS 方法成为曲线曲面 造型技术发展趋势中最重要的基础 综上所述 自由曲线曲面造型技术是 CAGD 的核心问题 B zier 样条和 B 样条则是几何设计的重要手段 NURBS 由于数学形式的统一性成为 CAD CAM 的工业标准 随着计算机技术的不断进步和工业设计的巨大需求 我们这门学科 还将继续取得更大的成就 1 2 曲线曲面的近似合并方法曲线曲面的近似合并方法 随着全球化的进一步加深 产品设计的信息化 网络化得到了极大发展 异 地设计 异地加工也变得司空见惯 这使得大量的几何模型数据在不同的 CAD 系统之间频繁地传输和交换 由于几何模型是由不同基函数表示的 且数据是海 量的 这给网络传输造成了很大负担 使得几何信息容易丢失 并极大妨碍了 CAD 系统的工作效率 为了在满足信息精度的条件下 加快传输速度 减少传 输时间 就需要对几何模型进行简化 于是 Hoschek 56 在 1987 年提出了样条曲线的近似转化思想 它分为降阶逼 近和近似合并两个方面 降阶逼近就是用一条新的低次参数曲线曲面去逼近原来 的高次曲线曲面 并且使误差尽可能的小 而近似合并就是用一整段较低次参数 曲线曲面去逼近两段或多段相邻的曲线曲面 并使几何形状尽可能地接近 但表 6 浙江大学博士学位论文 示的几何数据量更少 这两种运算都能够显著的简化几何模型并压缩数据量 有 利于 CAD 系统之间的数据交换与传输 1 2 1 曲线曲面降阶方法 由于 CAGD 的一个主要研究对象是 B zier 形式 因此这些年来 国内外学 者对降阶算法的研究主要围绕 B zier 曲线曲面进行 57 90 总的来说 降阶逼近方 法可分为两类 1 基于控制顶点逼近的几何方法 最初 Hoschek 56 提出的降阶方法就是其中之 一 他考虑的是保端点几何连续的降阶 如n次曲线 0 n n ii i B t XV降阶至 m nm 次曲线 0 m m ii i Bt YW 对 G1连续 他研究的是 B zier 曲线降至三次 的算法 对 G2连续 他研究的是 B zier 曲线降至五次的算法 这就需要满足 对 G1连续 0010110 WV WVVV 121 mnmnnn WV WVVV 对 G2连续还需有 2 211121110 WVVVVV 2 21212121 mnnnnn WVVVVV 这里 1 1 1 m n n m 算法的大致过程就是先对原曲线均匀采样 再找一条曲线插值这些采样点 并逼近原曲线 使得误差最小 这里误差定义为两条曲线对应参数点的最大距离 max max jjj tt XY j t为对应的采样参数 在使误差最小的过程中 需要对采样参数进行不断地调整 使得误差向量能 垂直或接近垂直于 i tY 误差向量 iii tt YX ii t PX 每一次调整 i t 是旧参数 i t 是更新后的参数 iii ttc 可以是 tY 的弧长 i c 是点 i P的映射偏移量 见下图 第一章 绪论 7 图 1 1 Hoschek 算法的参数调整 Hoschek 只是对降阶逼近做了简单的研究 其算法最大的缺点是需要对采样 参数进行调整 这需要浪费大量的时间 且没有降阶曲线的显示表达 其他类似的算法还有 Forrest 的逆升阶算法 14 Danneberg 的分段插值逼近 算法 91 Moore 的面积极小反求降阶曲线算法 92 等等 2 基于基转换的代数方法 由于正交函数能很容易的实现在某些 p L范数下的最 佳逼近 这类方法主要就是将 Bernstein 基转化为一类正交基 降阶 再变为 Bernstein 基 最后得到高精度的降阶逼近算法 这些利用的有 Chebyshev 基 93 Legendre 基 75 Jocabi 61 基等 1 2 2 曲线曲面合并方法 近似合并是简化 CAD 系统中几何模型的另一种方法 但是相对于降阶来说 目前的成果还比较少 研究还很不充分 在 Hoschek 提出近似合并问题的文献 56 中 作者仅在末尾提到了应用前面的降阶方法来解决合并问题 没有详细展开 在这之后 Hu 94 在 2001 年 CAD 期刊上发表的成果可以说是合并问题上的重要 进展 是真正完美地解决了近似合并问题 问题描述 两条都是n次的 B zier 曲线 uP和 vQ 其控制顶点分别是 i P和 0 1 i in Q 近似合并就是找到一条新的n次 B zier 曲线 tR 控制顶点为 0 1 i in R 使得 tR与 tR的距离 d R R在 0 1 内最小 这里 0 0 0 1 1 n n ii i n n ii i t Bt t t Bt P R Q 而 是细分参数 8 浙江大学博士学位论文 文中 94 首先通过证明得到两条原曲线 uP和 vQ能够精确合并的充要条 件 0 0 1 iii n i in PQ 这里 是一个与 有关的取值 随后 作者分别探求了在 1 L范数和 2 L范数下的合并曲线 其误差定义分别 为 2 0 n ii i dtt RRRR和 1 2 0 dttttdt RRRR 其主要思想 就是利用控制顶点扰动法 得到拉格朗日函数并使之最小化 再算出控制顶点的 扰动量 最后使用递归算法得到合并后 B zier 曲线的控制顶点 例如下图 都是 两条三次 B zier 曲线的近似合并 图 1 2 a 1 L范数下的合并结果 图 1 2 b 2 L范数下的合并结果 从上图 可以看出算法的效果很好 除此之外 保端点高阶插值以及带点限制 即合并曲线插值原曲线的部分点 的近似合并也一并被考虑 图 1 3 a 两端点重合的合并 图 1 3 b 保端点一阶插值的合并 上图是两条四次 B zier 曲线在 1 L范数下的合并 第一张 绪论 9 图 1 4 a 插值参数是 00 0 0 1 0uv 图 1 4 b 插值参数是 010 0 5 1 0 0 5uuv 上图是两条五次 B zier 曲线带点限制的在 2 L范数下的合并 Hu 94 在文中最后指出 如果需要得到更高次的合并曲线可以对原来的两条 曲线先升阶再合并 并且得到的误差更小 效果见下图 图 1 5 a 直接合并成四次曲线 图 1 5 b 升阶后合并成五次曲线 上图是两条四次 B zier 曲线的合并 可以看出升阶的效果更好 这篇文献之后 Hu 的方法还被应用到 B 样条曲线 95 区间 B zier 曲线 96 有理 B zier 曲线 97 等类型的近似合并上去 在曲面合并方面 目前仅文献 98 对此 作了研究 文 献 98 研究了将两张相邻同次数的张量积 B zier 曲面合并成一张次数 相同的张量积曲面 主要方法是利用张量积曲面的离散性质 使合并曲面分别逼 近两张原曲面 并利用求偏导的方法来得到误差最小的合并张量积 B zier 曲面 文章还对保边界高阶插值的近似合并做了研究 分析了合并误差的上下界 同时 指出对原曲面进行升阶得到的更高次合并曲面 其误差会更小 其效果如下 98 10 浙江大学博士学位论文 图 1 6 a 两张相邻79 次原曲面 图 1 6 b 79 次不保边界插值合并曲面 图 1 6 c 99 次不保边界插值合并曲面 图 1 6 d 79 次保边界 2 2 阶插值合并曲面 纵观近似合并的研究 目前的结果还是初步的 不完善的 还没有扩展到所 有的曲线曲面类型 方法上大多也是遵循 Hu 94 的算法 没有大的突破 这首先 是由于合并问题实质上是一条曲线分段同时逼近几个曲线段 而不像降阶可以化 归为一个曲线函数逼近另一个函数 也就是说问题的难度上升了 但目前数学上 还没有很好的办法来解决 比如 有理 B zier 曲线的合并 97 因为分式函数不易处 理 就得不到有理曲线精确合并的充分必要条件 其得到的结果在理论上也是不 充分的 因此 这需要我们必须对曲线曲面的近似合并加大力气研究 对目前遇 到的困难 另辟蹊径寻求更好的结果 1 3 B 样条的扩展样条的扩展 关于 B 样条理论早在 1946 年就已提出 B 样条方法具有表示设计自由型曲 线曲面的强大功能 是几何形状数学描述的主流方法之一 由 Gordon 和 Riesenfeld 于 1974 年引入 第一章 绪论 11 k阶 B 样条基函数由 Cox De Boor 递推公式可定义为 1 1 11 1 11 1 0 2 ii i ii k i ki kik i kii ki tt t Nt tttt NtNtNtk tttt 其它 这里规定 凡出现 0 0 的项均为 0 i i t T 称为节点序列 i t 称为节点 为了适应几何造型系统的不断发展 B 样条的形式也在不断地发展中 新的 造型方法有有理化 几何化 参数化 空间扩大化等等 如几何化就是将连续发 展成切向连续 曲率连续 其代表就是 样条 99 如空间扩大化就是在原有的 空间中加入新的函数类型 其代表是在参数多项式空间中加入频率序列 100 101 其中非均匀有理 B 样条 NURBS 是最成功的一个 并已经成为工业产品设 计的标准 它兼有 B 样条形状局部可调及连续接可调的优点 又兼有有理 B zier 曲线可精确表示圆锥曲线的特性 然而 正如 Piegl 50 等人指出由于采用有理形 式来代替多项式形式 NURBS 模型在几何设计中也存在一些局限性 例如 1 NURBS 模型的微分积分运算困难 曲线求导后次数会升高 这对数值计 算是不利的 2 在表示不同次数的分段曲线时 必须用高次样条表示低次曲线 这大大 增加计算量 3 不能精确表示超越曲线 如 CAD CAM 系统中常用的摆线 螺旋线等 4 虽然 NURBS 可以精确表示圆弧 但是其参数并不是它的弧长参数 NURBS 模型更多的局限性 请参考 102 104 正因为 NURBS 模型有这么多的局限性 我们希望对 B 样条作进一步研究和 扩展 得到新的造型方法以适应 CAD CAM 的发展 1 3 1 可变次数多项式 B 样条 CAD 等几何造型系统对建模工具的要求 一是数据量少 二是计算省时 如何减少存储量和提高计算效率一直是 CAD 系统发展的不懈追求 例如 Sederberg 105 在 2003 年提出的新的建模工具 T 样条 这种样条能够突破传统的 12 浙江大学博士学位论文 张量积 B 样条曲面对控制网格的拓扑限制 允许在控制网格内部出现度数为 3 的控制顶点 从而极大的简化几何模型 减少曲面的控制顶点数 使建模的操作 速度和渲染速度都得到提升 为了进一步提高 CAD 系统处理数据的效率 我们提出了可变次数的多项式 B 样条 我们知道 B 样条是 CAD 的主要建模工具 其特点之一是在各个节点 区间上次数都相同 这就决定了它在表示不同次数的分段多项式构成的曲线时 必须要用高次多项式表示低次曲线 这就会产生冗余数据 并增加计算量 例如 直线段的表示用一次式只需要起点和终点的数据 而用三次式表示却要四个点 数据量增加了一倍 而计算量远不止于此 要避免这种情况 就应该是几次就用 几次多项式表示 这就使变次数 B 样条的研究提上日程 变次数 B 样条是一个新的造型方法 但其实它并不是一个新问题 106 107 1996 年意大利的 Castantini P 108 109 就提出了变次数样条的概念 并且在 2000 年 CAGD 上利用变次数的多项式来构造曲线曲面 110 2001 年法国的几何造型专家 Mazure M 111 证明了变次数的多项式样条的存在性 2003 年 Sederberg 112 等人在 CAGD 上发表了关于用变次数样条 MD spline 进行曲线设计的论文 表明了 MD 样条具有许多和一般 B 样条类似的性质 如局部支撑性 保凸性 变差缩 减性等 并且是 1n C 次连续 这里n是两曲线段较低的次数 图 1 7 a 字母 U 图 1 7 b 用 B zier 曲线表示 第一章 绪论 13 图 1 7 c 用 B 样条表示 图 1 7 d 用 MD 样条表示 上图引自 Sederberg 112 以说明变次数样条能明显的简化模型 减少控制顶 点 达到压缩数据 简化计算的目的 上面的空心点是曲线的控制顶点 然而以上的研究仍有局限性 主要是两方面 一低次 二无基函数 低次指 的是以上讨论仅限于以一次 二次的低次分段多项式构造曲线曲面的情况 无基 函数指的是没有为低次的变次数样条构造一组具有权性 局部支撑性和正性的基 函数 然后以它们表示曲线曲面 所以 文献 112 就提出今后的问题要解决包括 变次数 B 样条基的构造 变次数样条的一般形式以及它的开花和升阶算法等一 系列问题 从 B 样条过渡到变次数 B 样条并不是一件容易的事情 研究也不能简单套 用 B 样条的模式 这需要我们进行创造性 原始性的研究 才能为变次数 B 样 条的性质和应用奠定坚实的理论基础 其中基函数的构造是关键的一步 遵循先 易后难的过程 在第四章中 作者将给出自己研究的初步结果 所构造的变次数 B 样条保持了 B 样条基的许多本质特性 这样得出的变次数 B 样条不仅能实际 应用于 CAD 系统 而且能充分发挥其简化模型 减少计算量的特点 1 3 2 双曲或三角多项式 B 样条 我们希望找到另外一种曲线曲面造型 既避免有理形式 又具备多项式 B 样条类似的性质 这样就必须把 B 样条的多项式项用非多项式来代替 于是 有人提出了几种新的样条曲线曲面方案 下面将简单介绍一下 将代数多项式和三角或双曲多项式结合起来 构造出的新样条能够克服 NURBS 的缺点 精确表示如圆锥螺线 悬链线等工程上应用广泛的超越曲线 这个想法最初是文献 113 提出来的 他以sin cos 1 tt t为基底构造曲线 称之为 14 浙江大学博士学位论文 C B 样条 其定义如下 令 0121 3 inn b b bbbb n 是给定的顶点 任意实数 0 则曲线为 0112233 1 2 3 12 2 1 2 0 1 sin cos 1 1