浙江大学硕士学位论文.pdf

硕士学位论文 硕士学位论文 论文题目论文题目 NUAT B 样条曲线的升阶与割角关系的研究 样条曲线的升阶与割角关系的研究 作者姓名作者姓名 于静静于静静 指导教师指导教师 汪国昭汪国昭 教授教授 学科学科 专业专业 计算机辅助几何设计与计算机图形学计算机辅助几何设计与计算机图形学 所在学院所在学院 理理 学学 院院 提交日期提交日期 2007 年年 5 月月 浙 江 大 学 硕 士 学 位 论 文 浙江大学 申请硕士学位论文 NUAT B 样条曲线的升阶与割角关系的研究样条曲线的升阶与割角关系的研究 作作 者 于静静者 于静静 学科专业 计算机辅助几何设计与计算机图形学学科专业 计算机辅助几何设计与计算机图形学 指导教师 汪指导教师 汪 国国 昭昭 教教 授授 浙江大学数学系浙江大学数学系 浙江大学图象图形研究所浙江大学图象图形研究所 2007 年 5 月 浙 江 大 学 硕 士 学 位 论 文 The research on relationship between degree elevation of NUAT B spline curves and corner cutting By Jingjing Yu Computer Aided Geometric Design and Computer Graphics A Thesis Presented to The Graduated School of Zhejiang University in Partial Fulfillment of the Requirements for the Degree of Master of Sciense Thesis Supervisor Professor Guozhao Wang Department of Mathematics Institute of Computer Graphics and Image Processing Zhejiang University Hangzhou P R China May 2007 浙 江 大 学 硕 士 学 位 论 文 目目 录录 摘摘 要要 1 Abstract 2 第一章第一章 绪论绪论 3 1 1 CAGD中参数曲线的发展 3 1 2 CAGD中曲线的升阶问题 6 1 3 本文的主要内容 8 第二章第二章 NUAT B 样条曲线的升阶问题样条曲线的升阶问题 9 2 1 引言 9 2 2 NUAT B 样条的定义及性质 10 2 3 NUAT B 样条曲线的升阶问题的描述 12 2 4 本章小结 13 第三章第三章 NUAT B 样条曲线的升阶的割角算法样条曲线的升阶的割角算法 14 3 1 引言 14 3 2 双阶NUAT B 样条理论 15 3 3 NUAT B 样条曲线的升阶的割角算法 21 3 4 例子与小结 22 第四章第四章 NUAT B 样条曲线的割角控制多边形序列的收敛性样条曲线的割角控制多边形序列的收敛性 24 4 1 引言 24 4 2 NUAT B 样条基与C B zier基之间的关系 24 4 3 NUAT B 样条曲线控制多边形序列的收敛性 28 4 4 本章小结 31 第五章第五章 总结与展望总结与展望 32 参考文献参考文献 33 致谢致谢 39 摘摘 要要 在计算机辅助几何设计和几何造型等许多领域中 自由曲线和曲面都起着重 要作用 曲线升阶是自由曲线和曲面造型中最重要 也是最常用的关键技术之一 本文提出了 non uniform algebraic trigonometric B 样条曲线 NUAT B 样条 曲线 的升阶算法 证明其几何意义就是割角算法 并且证明了割角控制多边形 序列的收敛性 本文升阶的主要思想是对 NUAT B 样条曲线一个区间一个区间 地进行升阶 最后建立了一类新的基函数 称之为双阶 NUAT B 样条基函数 本文主要内容如下 本文在第一章给出了研究背景 本文在第二章描述了 NUAT B 样条曲线的升阶问题 本文第三章给出了双阶 NUAT B 样条的理论 证明 NUAT B 样条曲线的升 阶的割角算法 本文在第四章证明了 NUAT B 样条曲线的割角控制多边形序列的收敛性 本文第五章给出了结论和展望 关键词 关键词 NUAT B 样条 双阶 NUAT B 样条 升阶 割角 收敛 1 浙 江 大 学 硕 士 学 位 论 文 Abstract In the fields such as Computer Aided Geometric Design CAGD and geometric modeling free form curves and surfaces play an important role degree elevation is one of the most important technique in the modeling method of free form curves and surfaces This paper presents the degree elevation of non uniform algebraic trigonometric B spline NUAT B spline curve proves that the geometric meaning of the algorithm is corner cutting and also proves the convergence of the control polygons series of NUAT B spline curves Our main idea is elevating the degree of NUAT B spline curves one knot interval by one knot interval In the end a new class of basis functions to be called bi order NUAT B spline basis funtions is constructed This thesis focuses on the problems as follows Firstly the research background is introduced in the chapter one Secondly the problem of degree elevation of NUAT B spline curves and the main idea are described in the chapter two Thirdly a new class of basis functions to be called bi order NUAT B spline basis funtions is constructed in the chaper three and the corner cutting algorithm of the degree elevation is proved Fourthly the convergence of the control polygons series of NUAT B spline curves is proved in the chapter four Finally in the chaper five this thesis draws the conclusions and talks about some prospects Keywords NUAT B spline bi order NUAT B spline degree elevation corner cutting convergence 2 浙 江 大 学 硕 士 学 位 论 文 第一章第一章 绪论绪论 1 1 CAGD 中参数曲线的发展中参数曲线的发展 计算机辅助几何设计 Computer Aided Geometric Design 简称 CAGD 最 初是在1974年美国召开的第一届CAGD国际会议上由Barnhill和Riesenfeld提 出的 自此 计算机辅助几何设计开始以一门独立的学科出现 计算机辅助几何 设计的出现与发展是与航空 汽车等现代工业的发展及计算机的不断升级密切相 关的 它主要研究在计算机图形系统下对曲线曲面信息的表示 逼近 分析 和 综合 现在已与微分几何 代数几何 函数逼近论 拓扑学 抽象代数 矩阵论 微分方程 最优化 数值分析等数学分支以及计算机辅助设计 加工 数据结构 数控 NC 程序设计 计算机动画等有紧密联系 应用范围还涉及 CAD CAM 建筑 生物工程 医疗 电子工程 机器人等等许多行业 可以说 计算机辅助 几何设计是当今的热门研究领域之一 1 计算机辅助几何设计始兴于上世纪 60 年代 最初始于飞机 船舶的外形放 样 Lofting 工艺 在当时计算机发展的影响下 为了利用计算机更高效地进行 设计 人们开始寻找研究曲线曲面的各种表示方法 其中最著名 最实用的技术 是由法国雷诺 Renault 汽车公司的工程师提出的 B zier 技术和美国机械工 程师教授 Coons 提出的 Coons 技术 在大多数情况下 描述产品外形的曲线 或曲面只有大概形状或者只知道它所通过的一系列空间点列 这些点称为型值 点 这类曲线或曲面叫自由曲线或自由曲面 而计算机辅助几何设计就是研究自 由曲线曲面的表示 设计 显示 分析与综合以及处理等问题 2 4 3 随着 CAGD 研究的深入 各种方法被广泛采用 包括 B zier 方法 B 样条 方法 NURBS 方法 有理 B zier 方法 混合曲线方法等 1962 年 法国雷诺汽车公司工程师 B zier 提出一种通过控制多边形设计曲 线的新方法 并以此为基础建立了著名的 UNIRURF 自由曲线曲面设计系统 由 B zier 技术生成的曲线曲面具有一系列很好的性质 如几何与放射不变性 凸包 性 保凸性 对称性 端点插值性等 而且具有各种简单易用的计算方法 如 3 浙 江 大 学 硕 士 学 位 论 文 de Casteljau 求值 离散 升阶 插值 包络生成算法等 这些曲线曲面可以很 好地控制整体形状 设计人员通过移动控制顶点方便地修改曲线 并且可以预料 曲线的大致形状 但是 B zier 曲线曲面缺乏局部调整性 在拼接方面也存在问 题 在 B zier 技术的基础上 美国通用汽车公司的 Gordon 和 Riesenfeld于 1974 年通过变 Bernstein 基为 B 样条基 构造了等距节点 B 样条曲线 它不但拥 有 B zier 曲线的所有优点 而且具有局部调整性等优点 从而进一步解决了自 由曲线曲面形状的描述问题 早在 1946 年 Schoenberg就提出样条函数作为 解决拼接问题的一种技术 但他的文章直到 1967 年才发表 de Boor 和 Cox 两 人分别独立地给出了关于 B 样条计算的标准算法 1980 年 Boehm 和 Cohen 等人给出了 B 样条曲线的节点插入技术 1984 年 Prautzsch 等人又发展了 B 样条曲线的升阶算法 但是随着制造业的发展 一些二次曲线弧被广泛采 用 例如圆弧 椭圆弧 抛物线弧等 这时候 B 样条方法就不适用了 显然要 对 B 样条方法再进行改造 6 5 8 7 10 9 12 11 14 13 为了解决 B zier 曲线不能精确表示圆锥曲线的问题 波音公司的 Rowin 和 麻省理工学院的 Coons 等首先用有理参数曲线来构造圆锥曲线模型 而后许 多学者也对之进行了广泛的研究 美国 Syracuse 大学的 Versprille 在他 1975 年的博士论文中首次提出有理 B 样条方法 其后 24 32 作了大量研究 而 33 38 为 NURBS 系数的矩阵表示做出了贡献 现在 NURBS 方法成为现代曲面造型中 最为流行的技术 这些有理方法能解决很多问题 但它们还是有缺点的 例如 NURBS 方法 不能精确表示螺旋线 摆线等工程上很有用的超越曲线 有理因 子没有明确的几何意义 选取不直观 随着有理多项式次数的增高 容易导致数 值计算不稳定 15 4 2316 为了克服这一局限 很多文献中提出了许多新的模型 例如 Pottmann和 张纪文在空间上构造一种新型曲线三次 C 曲线 张 纪文在三次 C 曲线的基础上构造了三次 C B zier 曲线 三次 C B 样条曲线等 39 4240 cos sin 1 3 tttspan 4 浙 江 大 学 硕 士 学 位 论 文 也能够用控制多边形来作形状控制 Pottmann 和 Wagner 将其看作是扩展 Chebyshev 空间的特例 并考虑了螺旋线的构造 叶正麟 汪国昭等人对平面低 阶C B zier曲 线 的 奇 异 点 进 行 了 分 析 Mainar等 人 在 空 间 中给出了正规 B 基 4443 cos sin 1 24 ttttspan cos sin cos sin 1 5 tttttttspan 但是这些模型都是针对低阶的情况 因此陈秦玉和汪国昭考虑更一般的情 况 在代数和三角多项式混合空间中构造混合 曲线 巧妙地利用积分法构造了一组 C B zier 基函数 该函数具有与 Bernstein 基相似的良好的性质 如端点性质 零点阶数 正性 权性 对称性 升阶性质 等 利用该函数构造的 C B zier 曲线和 B zier 曲线一样 具有几何与仿射不变 性 凸包性 对称性 端点插值性 保凸性以及变差缩减性等性质 而且 C B zier 曲线具有形状参数因子 cos sin 1 22 tttttspan nn 45 能够方便地控制曲线的形状 C B zier 曲线能够方便 简洁 精确地构造二次曲线 如摆线 螺旋线 正弦曲线以及高阶的圆弧等 随 后 董辰世和汪国昭又进一步说明了 C B zier 曲线割角升阶得到的控制多边形 序列具有一致收敛性 和 B zier 曲线一样 C B zier 曲线也没有局部调整性 因此很自然的可以考虑空间中样条曲线的构造 此后吕勇刚 汪国昭等人又 进一步构造了中的均匀 C B 样条曲线 和非均匀样条曲线 NUAT B 样条 曲线 这类曲线具有和传统的 B 样条曲线类似的性质 而利用 C B zier 曲线 黄钰等人构造了中的一组标准正交基 林上华等人考虑参数因子 46 n n 48 47 n 49 的取值范围 将 C B zier 曲线参数 的取值区间从 0 拓展到 2 0 将均匀 C B 样条曲线参数 的取值范围逐阶扩大 并论证了基的正性 所得结果提高了 C 曲线的造型能力 51 50 在代数和双曲多项式混合区间中构造的 混合曲线也有类似的结论 例如均匀样条的构造 奇异点的分析等等 并且把 1 232 chtshtttttspanH nn n H 中构造的曲线称为 H 曲线 5 浙 江 大 学 硕 士 学 位 论 文 H 曲线利用了双曲函数的优点 C 曲线利用了三角函数的优点 但是这两个 系统似乎并没有什么关系 而且 C 曲线和 H 曲线的形状参数 也没有明显的几 何意义 张纪文找到了 C 曲线和 H 曲线的相似性 构造了 F 曲线 F 曲线 提供了新的形状参数c来取代 C 曲线和 H 曲线的形状参数 53 52 对 F 曲线而言 当c为时 是 C 曲线 为 1 时 是多项式曲线 为其他值时 是 H 曲 线 这样 F 曲线找到了 C 曲线和 H 曲线之间的联系 而且权因子也有明显的几 何意义 1 1 cc 我们把混合空间中构造的曲线称为混合曲线 各种混合曲线的不同 归根于 其考虑的空间不同 混合曲线有许多优点 能精确表示螺旋线 摆线等工程上很 有用的超越曲线 数值计算稳定等 混合曲线方面的研究总是在不断进步的 例如 丁敏考虑了在空间 中构造的混合曲线 Morin 等 人考虑了利用 C 曲线来构造旋转曲线 樊建华等人考虑了 C 曲线的拼接与分 割问题 杨建等人利用 C 曲线描述及生成汉字轮廓 韩旭日 陆立正 王文涛和汪国昭等人考虑了 C 曲线和 H 曲线中加入形状因子 2cos 2sin cos sin 1 42 tttttttspanQ mm 54 55 56 57 58 63 59 在控制顶 点不变的情况下 可以通过对 的调节修改曲线 但是 没有明显的几何意义 满 家巨和汪国昭利用 C 曲线和 H 曲线 考虑了两类极小曲面的表示与构造 64 1 2 CAGD 中曲线的升阶问题中曲线的升阶问题 在计算机辅助设计 几何造型以及工程曲面的计算机辅助几何设计等许多领 域中 自由曲线和曲面都起着重要作用 曲线升阶是自由曲线和曲面造型中最重 要 也是最常用的关键技术之一 其重要性主要表现在三方面 其一 升阶可以 增加几何造型的柔性 或者说提高其形状控制的灵活性 因为通过升阶 增加了 控制顶点数 从而也就增加了自由度 其二 升阶是表示和设计组合曲线时必不 可少的工具和手段 因为两条或多条不同阶次的样条曲线要依次连接成为一条样 条曲线时 必须使用升阶方法 第三 升阶是构造蒙皮 扫描曲面和组合曲 65 6 浙 江 大 学 硕 士 学 位 论 文 面的重要工具 例如 若截面线的阶次不一致 则必须通过升阶 使其阶次 一致后 才能生成蒙皮曲面 这在表示和生成蒙皮曲面 扫描曲面和组合曲面时 都是非常重要的 也是必不可少的一种技术 66 在 CAGD 中 B zier 曲线由其控制多边形所完全决定 并且可以通过移动 其控制顶点来灵活地控制曲线的形状 因此为了增加对 B zier 曲线进行形状控 制的灵活性 利用 Bernstein 基函数的升阶公式 可以得到 B zier 曲线的升阶算 法 B zier 曲线的升阶算法比较简单 并且其几何意义非常明显 可以解释为对 控制多边形的割角 即用升阶算子 A 作用一次得到割角多边形 它产生 了对原曲线更紧的界定和逼近 多一个控制顶点 也增加了调整曲线形状的柔韧 性 当升阶不断进行时 B zier 网被密化 最后它的升阶序列 当时收敛到原始 B zier 网 n n A n 0 A n 1 A n k A k n 所定义的 B zier 曲线 魏永伟 汪国昭 和杨勤民给出了区间 B zier 曲线曲面的升阶算法 翁彬 潘日晶给出球域 B zier 曲线的升阶并证明了其收敛性 另外 缪永伟给出了 Poisson 曲线的升 阶算法 67 68 69 B 样条曲线是 CAGD 中应用最广泛的曲线之一 因此 B 样条曲线的升阶也 就成为 CAGD 中常用的关键技术之一 利用 B 样条曲线的升阶可以解决不同曲 线的连接 同时它还可以提高几何造型控制的灵活性 B 样条曲线的升阶比 B zier 曲线的升阶要复杂得多 其方法主要有三种 1 基于插入节点的 Prautzsch 升阶算法 2 Cohen 等的递归升阶方法 3 Piegl 与 Tiller 的基于 B zier 曲线升阶的方法 经过实践发现 Prautzsch 方法运算速度最快 但算法复杂 难懂 Piegl 与 Tiller 方法虽然运算速度稍慢 但程序简单直观 并可以同时升阶 任意次 因此对该方法进行改进尤为重要 许多学者对此进行了研究 但是所有 这些升阶算法都没有明确的几何意义 汪国昭和邓重阳于 2007 年提出了 B 样条 曲线的升阶的割角算法 此算法的几何意义可以理解为对曲线控制多边形的 割角 70 71 72 73 74 随着对混合曲线的深入研究 混合曲线的升阶问题也逐渐被提出 例如单开 7 浙 江 大 学 硕 士 学 位 论 文 佳和汪国昭于 2002 年给出了低阶 C B zier 曲线的升阶方法 而本文则证明了 NUAT B 样条曲线的升阶的割角算法及其割角控制多边形序列的收敛性 75 1 3 本文的主要内容本文的主要内容 本论文共分五章 各章内容安排如下 第一章 综述了 CAGD 中参数曲线曲面的发展历史 给出 NUAT B 样条 曲线产生的背景以及 CAGD 中曲线的升阶研究 第二章 描述了 NUAT B 样条曲线的升阶问题 第三章 给出了双阶 NUAT B 样条的理论 证明 NUAT B 样条曲线的升 阶的割角算法 第四章 证明了 NUAT B 样条曲线的割角控制多边形序列的收敛性 第五章 全文工作的总结 并展望今后的工作 8 浙 江 大 学 硕 士 学 位 论 文 第二章第二章 NUAT B 样条曲线的升阶问题样条曲线的升阶问题 2 1 引言引言 B zier 曲线和 B 样条曲线是 CAGD 中最基本的两大造型 它们的升阶也是 CAGD 中的基本问题 升阶可以在保持曲线形状不变的前提下增加控制顶点 从 而增加对曲线进行形状控制的潜在的灵活性 B zier 曲线的升阶就是在保持 B zier 曲线的形状不变的前提下 增加它的 控制顶点数 如何从它的原控制顶点求出新控制顶点 就是 B zier 曲线的升阶 问题 B zier 曲线是参数多项式曲线 具有整体性质 增加控制顶点 就增加了 对曲线进行形状控制的潜在的灵活性 早在 1972 年 B zier 本人就提出过 B zier 曲线的升阶算法 不过他的方法虽然可以增加相应的顶点达到升阶的目的 但是 算法的复杂性限制了其实际应用 更为广泛应用的升阶算法是基于 Bernstein 基 函数的升阶方法 也就是 2 1 1 n i n i i n ii n i PtBPtBtP 0 1 0 1 1 1 1 1 iii P n i P n i P 0 11 n PP 2 1 2 其中和分别表示阶和 tB n i 1 tB n i n1 n阶 B zier 基函数 和分别表示升阶 前后的控制顶点 进入 80 年代后 Farin Piegl 又对有理 B zier 曲线的升阶方法作了比较详尽的研究 i P i P 1 0 ni B 样条是表示和设计自由曲线和曲面的最重要技术之一 在设计自由曲线时 往往需要增加曲线造型的自由度 在生成 B 样条组合曲线 组合曲面 或用蒙 皮技术生成 B 样条曲面时 要使得不同阶曲线的阶数达到一致 实现上述操作 都要用到 B 样条方法中最基本最重要的技术之一 即 B 样条曲线的升阶 B zier 曲线的升阶过程比较简单 B 样条曲线的升阶相对比较复杂 因为它存在处理节 点的问题 设任给节点向量 10 110010 s m ss mm kn tttT 其中kmi 1 si 0 s 10 是由向量T确定的阶 B tN ki k 9 浙 江 大 学 硕 士 学 位 论 文 样条基 给定k阶 B 样条曲线 n i iki PtNtP 0 11 nk ttt 2 1 3 B 样条曲线的升阶是指提高曲线的阶数 以升一阶为例 即将式 2 1 3 中由阶 B 样条基表示的阶曲线表示为由 k k1 k阶 B 样条基表示的1 k阶曲线 根据 B 样条理论 B 样条曲线在r重节点处为1 rk次连续 所以为了保证升阶可实 现 必须使各相异节点的重数增加 1 为此得到如下节点向量 11 11 1 001 10 10 s m ss mm kn ttt T 其中snn 设 是由节点向量T确定的 1 tN ki ni 0 1 k阶 B 样条基 则曲线可以表示成 tP n i iki QtNtP 0 1 11 nk ttt 2 1 4 其中新的控制顶点 可由原控制顶点表出 i Qni 0 n ii P 0 由此想到定义在代数三角空间中的 NUAT B 样条曲线是否也可以升阶呢 因为在代数多项式空间里 子空间可以由其高维 空间表示 因此低阶曲线可以由高阶曲线表示 NUAT B 样条曲线可以升阶 在 第三章中将具体讨论 NUAT B 样条曲线是如何实现升阶的 cos sin 1 32 tttttspan nn 2 2 NUAT B 样条的定义及性质样条的定义及性质 2 2 1 NUAT B 样条基的定义 样条基的定义 设是给定的节点序列 是定义在T上的k阶 NUAT B 样条基函数 其中 先给出初始函数的定义 规定 0 1 iii tttT tN ki 3k 00 0 其他0 sin sin sin sin 21122 11 2 iiiii iiiii i ttttttt ttttttt tN 2 2 1 当时 3k 10 浙 江 大 学 硕 士 学 位 论 文 2 2 2 1 0 3 1 11 11 1 ikdssNsNtN t kikikikiki 其中 1 dttN kiki 2 2 2 NUAT B 样条曲线的定义 样条曲线的定义 任意给定节点序列及控制顶点序列 参 数曲线 0 1 tN ki kii ttt 2 局部支柱性 当0 tN ki kii ttt 3 权性 当 i ki tN1 3k 4 导数 1 11 11 1 tNtNtN kikikikiki 5 连续阶性 在节点处的连续阶为 tN kii t i rk 1 其中是节点的重数 i r i t 6 零函数 当且仅当0 tN kikiii ttt 1 7 与 C B zier 基的关系 当 kiiikiki ttttt 121 1 tN kki 2 tN kki 就是上的阶 C B zier 基 tN ki 1 ii ttk 11 浙 江 大 学 硕 士 学 位 论 文 2 3 NUAT B 样条曲线的升阶问题的描述样条曲线的升阶问题的描述 NUAT B 样条曲线是定义在空间中的样条 曲 线 设 给 定 任 意 节 点 向 量 cos sin 1 32 tttttspan nn 1 1110 n r nn r km ttttuuuT kri 1 ni 1 n ttt 21 是由向量定义在 tN ki T上的阶 NUAT B 样条基函数 给定阶 NUAT B 样条曲线 k k m i iki PtNtP 0 11 mk utu 2 3 1 其中是控制顶点 其中表示节点的重数 1 0 miPi n rr 1 n tt 1 krr n 1 NUAT B 样条曲线的升阶是指提高曲线的阶数 考虑升一阶的情况 要将式 2 3 1 中由k阶 NUAT B 样条基表示的阶曲线表示成由k1 k阶 NUAT B 样条 基表示的k阶曲线 根据 NUAT B 样条理论 NUAT B 样条在1 r重节点处为 次连续 曲线升高一阶 在节点处的连续阶就升高一阶 为了保证升阶 后曲线的连续阶不变 必须使各相异节点的重数增加 1 因此将每个相异节点嵌 入新的节点 使其重数增加 1 得到如下节点向量 1 rk 11 11 10 1 n r nn r km ttttuuuT 其中 则曲线可以表示成 nmm tP 1 0 1 nm i iki PtNtP 11 mk utu 2 3 2 其中 是由节点向量T确定的 1 tN ki 1 0 nmi 1 k阶 NUAT B 样条基 i P 1 0 nmi 是新的控制顶点 它可以由原控制顶点线性表出 现在问题的关键就是如何找出控制顶点 使其满足式 2 3 2 在下章中 将具体讨论这个问题 i P 12 浙 江 大 学 硕 士 学 位 论 文 2 4 本章小结本章小结 本章回顾了 B zier 曲线和 B 样条曲线这两大类曲线的升阶问题 对于定义在 代数三角混合空间中的代数三角 B 样条曲线 NUAT B 样条曲线 结合其定义及性质 说明 NUAT B 样条曲线也能够升阶 并对其升阶问题进行了描述 cos sin 1 32 tttttspan nn 13 浙 江 大 学 硕 士 学 位 论 文 第三章第三章 NUAT B 样条曲线的升阶的割角算 法 样条曲线的升阶的割角算 法 3 1 引言引言 根据 2 3 的描述 给定k阶 NUAT B 样条曲线 m i iki PtNtP 0 11 mk utu 其中是定义在节点向量 tN ki 1 1110 n r nn r km ttttuuuT 上的k阶 NUAT B 样条基 要将阶 NUAT B 样条曲线升阶到k tP1k 阶 应找到控制 顶点 使其满足 i P 1 0 1 nm i iki PtNtPtP 11 mk utu 其中 1 tN ki 1 0 nmi 是由节点向量确定的 阶 NUAT B 样条基 显然 推导出k阶 NUAT B 样条基函数和阶 NUAT B 样条基函数之间的转换关系后 就可以很容易推出新的控制顶点 11 11 1 n r nn r ttttT 1 k1k i P 1 0 nmi 为保证曲线升阶前后连续性不变 必须使各节点重数增加 1 如果同时将所 有节点重数增加 1 那么升阶过程将很复杂 不容易理解 其升阶的几何意义也 不明显 本文采用每次只嵌入一个节点的方法 即只增加一个节点的重数 同时 只在一个相应的区间上进行升阶 由于是一个节点一个节点的嵌入 产生不同阶 的基函数 因此本文定义了一种新的样条基函数 双阶 NUAT B 样条基 在每一步中只嵌入一个节点 把嵌入第 j 个节点后的节点向量记为 在 1 1 11 1 1 11 n jj r nn r jj r jj r j ttttttttT j T 上定义双阶 NUAT B 样 14 浙 江 大 学 硕 士 学 位 论 文 条基函数 在上是 tN j ki tN j ki 11 j tt1k 阶 在上是k阶 进而给出 1nj tt j T 上的双阶 NUAT B 样条曲线的定义 注意到T 也就是只 在 tP j j t 1jj T 1 j T的基础上插入一个节点 中的每一个函数可以由中的至 多两个函数线性表出 则的控制顶点可以由的控制顶点表示 而且 可以看作是对曲线的控制多边形的割角 嵌入第 1 tN j ki tN j ki tP j 1 tP j 1 tP j j 个节点 只将曲线在区 间上升阶 重复这个过程 一个节点一个节点地嵌入 最后就可以将曲 线在所有定义区间上进行升阶 而且其几何意义非常明显 就是对控制多边 形的割角 1 jj tt tP 本章首先给出双阶 NUAT B 样条理论 然后证明 NUAT B 样条曲线的升阶 的割角算法 3 2 双阶双阶 NUAT B 样条理论样条理论 3 2 1 双阶双阶 NUAT B 样条基函数的定义样条基函数的定义 首先在上定义初始函数 11 2 1 122 1 11 1 1 21 d r nn rr tttttttttT n 其它0 cos 1 cos 1 sin sin 1 3 1 2 1 2 1 3 1 3 1 100 1 10 1 2 0 ttttttt ttttttt tN 其它0 cos 1 1 cos cos cos 1 3 1 2 1 2 1 3 1 2 1 3 1 2 1 31 2 1 ttttttttttt tN 其它0 sin sin cos 1 cos 1 1 4 1 3 1 3 1 4 1 4 1 3 1 2 1 2 1 3 1 2 1 2 2 ttttttt ttttttt tN 其它0 sin sin sin sin 1 2 1 1 1 1 1 2 1 2 1 1 111 1 1 1 2 iiiii iiiii i ttttttt ttttttt tN 3i 基于上述初始函数 时定义 2 j 15 浙 江 大 学 硕 士 学 位 论 文 2 1 2 2 j j i j i litNtN 3 2 1 其它0 cos 1 cos 1 111 12 1 2 2 2 2 j l j l j l j l j l j l j l j l j l jjjjj jjj j ttttttt ttttN tN 其它0 cos 1 1 cos cos cos 1111 2 1 j l j l j l j l j l j l j l j l j l jjjjjjjj j ttttttttttt tN 其中 jrrrl jj 21 jrrrd nj 21 当时 定义 3 k 1 11 11 1 t j ki j ki j ki j ki j ki dssNsNtN kdi j 2 1 3 2 2 其中 1 dttN j ki j ki 3 2 3 若 我们定义 0 tN j ki 0 1 1 1 klittklitt klittklitt dttN j j kij j ki j j kij j ki t j ki j ki 或若 或若 注注 由于是最后一个节点 最后同时插入和 即 n t 1 n t n t 11 11 1 1 n r nn r n ttttTT 从上述定义可以看出 tN j ki 2 1 nj 在上的阶数是阶 在 11 j tt1k 1nj tt 上是阶 故称之为双阶 NUAT B 样条基函数 同时 也可以知道 和分别是阶和阶基函数 于是得到下面的定理 k 0 tN ki 1 tN n ki k1k 16 浙 江 大 学 硕 士 学 位 论 文 定理 1定理 1 设 是分别定义在 tN ki 1 tN ki 1 11 n r nn r ttttT 和 11 11 1 n r nn r ttttT上的 NUAT B 样条基函数 是分别 定义在 0 tN ki 1 tN n ki TT 0 和上的基函数 则 TT n 1 0 tNtN kiki 1 1 tNtN ki n ki 证明 1 证明 0 tNtN kiki 当时 显然成立 假设时 下面考虑的情况 由 假设可得 则 2k 2k 0 tNtN kiki 1k kiki 0 0 1 tN ki t kikikiki dssNsN 0 1 0 1 0 0 t kikikiki dssNsN 1 1 1 tN ki 2 证明 1 1 tNtN ki n ki 由 2 2 1 式很容易证明 假设时成立 则有 因 此 3 1 2 tNtN i n i 3k 1 1 ki n ki 1 1 tN n ki t n ki n ki n ki n ki dssNsN 1 1 1 1 1 1 t kikikiki dssNsN 1 11 11 1 2 tN ki 3 2 2 变换公式变换公式 根据 很容易得到 由 3 2 1 式中 和的定义可得 1 j jj tTT j j i j j i j i lit lit t 1 1 1 1 1 2 tN j i 2 tN j i 17 浙 江 大 学 硕 士 学 位 论 文 tN j ki j ki j i ttt j i j kij ttkli 且 1 j ki j i ttt 1 j i j kij ttkli 且 证明 假设对于一切时成立 当i 满足条件时 由 3 2 3 和 3 2 6 可 分别得到 最后由 3 2 5 可以得到 1 njt 0 j ki 0 j ki a0 1 tN j ki 3 导数 1 11 11 1 tNtNtN j ki j ki j ki j ki j ki 3 2 7 4 权性 i j ki tN1 证明 假设此性质对于时成立 则1jn i j ki tN1 由 3 2 5 i j ki tN 1 1 1 j li j ki tN i j ki tN 1 5 线性无关性 若中没有零函数 则线性无关 tN j ki tN j ki 证明 假设此性质对于时成立 设对于一切1 nj 1n ttt 有 h l j kil tNt 1 1 0 把 3 2 5 代入上式得 h l j ki j ki j ki j kil tNatNat 1 1 1 0 1 根据假设 有 由于 0 1 1 1 12 11 1 j khh j ki j ki j ki aaaa tN j ki 中无零函数 因此0 l 1 hl 20 浙 江 大 学 硕 士 学 位 论 文 3 2 4 双阶双阶NUAT B 样条曲线的定义样条曲线的定义 定义在 j T 上的曲线 1 0 kd i j i j ki j j PtNtP n ttt 1 3 2 8 称为双阶 NUAT B 样条曲线 其中是控制顶点 是定义在 j i P tN j ki j T 上的双阶 NUAT B 样条基函数 从双阶 NUAT B 样条基函数的性质可以直接推出曲线的一条有趣性 质 在上它是阶曲线 在上是阶曲线 tP j 11 j tt1k 1nj tt k 3 3 NUAT B 样条曲线的升阶的割角算法 样条曲线的升阶的割角算法 定理 3定理 3 若 是分别定义在 1 tP j tP j1 j T j T 上的双阶 NUAT B 样条曲线 且它们是相同的曲线 则它们的控制顶点 满足以下关系 1 j i P j i P j j i jj j i j ki j i j ki j j i j i liP liklPaPa kliP P 1 1 1 1 1 1 1 1 3 3 1 其中定义如 3 2 6 j ki a 证明 将 3 2 5 式代入 根据的线性无关性可 以很容易得到 3 3 1 式 1 0 11 1 1 kd i j i j ki j j PtNtP tN j ki 从 3 3 1 式知可以看作是通过对的割角得到的 当一个区间接一 个区间地应用这个方法时 就通过割角在所有区间上对进行了升阶 j i P 1 j i P tP 定理 4定理 4 NUAT B 样条曲线的升阶过程就是割角算法 证明 给定由 2 2 3 定义的 NUAT B 样条曲线 将和 tP tPT分别写成 和 0 tP 0 T 则对于每一个1 2 1 nj 把插入到 j t 1 j T 根据定理 3 将的 1 tP j 21 浙 江 大 学 硕 士 学 位 论 文 控制顶点更新到的控制顶点 从定理 3 知的控制顶点可 通过割角得到 tP j tP 1 tPtP n 图 2 NUAT B 样条曲线升阶的割角过程 最后指出割角过程中辅助控制顶点的几何意义 辅助控制顶点就是定 义在 j i P j T 上的双阶 NUAT B 样条曲线的控制顶点 3 4 例子与小结例子与小结 3 4 1 例子例子 为了便于理解 NUAT B 样条曲线升阶算法的割角过程 下面给出一个 例子 tP 例 给定四阶 NUAT B 样条曲线 其控制顶点为 tP i P 4 1 0 i 节点向量 下图是曲线升阶一次的割角过程 1 1 1 1 3 0 0 0 0 0 tP 22 浙 江 大 学 硕 士 学 位 论 文 图 3 图是初始控制顶点 图 分别是和的控 制顶点 图是整个割角过程 a b c 1 tP 2 tP d 3 4 2 小结小结 本章建立了一类新的基函数 双阶 NUAT B 样条基函数 给出双阶 NUAT B 样条基的性质以及双阶 NUAT B 样条曲线的定义 证明了 NUAT B 样条曲线 的升阶的割角算法 同时指出割角过程中辅助控制顶点就是定义在 j i P j T 上的 双阶 NUAT B 样条曲线的控制顶点 另外需要指出 无论用哪种算法 对同一条 NUAT B 样条曲线进行升阶 根据基的线性无关性 其系数是惟一的 因此都可以理解为割角 只是其割角过 程不明显 23 浙 江 大 学 硕 士 学 位 论 文 第四章第四章 NUAT B 样条曲线的割角控制多边 形序列的收敛性 样条曲线的割角控制多边 形序列的收敛性 4 1 引言引言 从 2 1 节中 B zier 曲线的升阶公式可以看出 升阶后 B zier 曲线的新控制 顶点可从原控制多边形得出 由此得出新控制多边形在原控制多边形的凸包内 新控制多边形比原控制多边形更靠近曲线 对于 B zier 曲线的升阶可以无止境 地进行下去 从而得到一个控制多边形序列 它们都定义同一条 B zier 曲线 这 个多边形序列收敛到一个极限 就是所定义的该 B zier 曲线 B zier 曲线的升阶 多边形序列收敛到曲线本身 这一重要性质把容易控制的特征多边形与不易控制 的 B zier 曲线紧密连接起来 从而获得许多实用性质 那么 由第三章的升阶割角算法 NUAT B 样条曲线的割角控制多边形序列 是否收敛呢 若收敛 收敛到什么曲线呢 本章将给出证明 4 2 NUAT B 样条基与样条基与 C B zier 基之间的关系基之间的关系 很难直接给出 NUAT B 样条基有关运算的有效简单的估计 如 NUAT B 样 条基函数的积分 为了证明收敛性 我们必须估计出 NUAT B 样条基的积分及 和 因此我们借助于 C B zier 基 希望 C B zier 基能够帮助我们避免直接估算 NUAT B 样条基 在这节里 首先用 C B zier 基表示 NUAT B 样条基 然后估 计 NUAT B 样条基的积分 4 2 1用用C B zier基表示基表示NUAT B 样条基样条基 在下面的定理中 我们将发现每一个 NUAT B 样条基都可以由有限个 C B zier 基线性表出 定理定理5 是给定的节点序列 和分别是定义在T上的阶 C B zier 基函数和 NUAT B 样条基函数 则对于每个 NUAT B 样条基 i tT tB ki tN ki k tN ki 24 浙 江 大 学 硕 士 学 位 论 文 可由 个 C B zier 基线性表出 其中 为有限的正整数 证明 C B zier 基是空间的一组基 因此 NUAT B 样条基可以由 C B zier 基线性表出 1 01 k iki tB sin cos 1 3 ttttspan kk tN ki 由第三章证明的 NUAT B 样条曲线升阶的割角算法可以推得 将K阶 NUAT B 样条曲线升阶到阶后 定义区间的每个节点增加的重数相同 都是重 有限重 而且 NUAT B 样条基至多跨越两个非零区间 因此我们分两种情况讨 论 1 基函数跨越一个非零区间 2 基函数跨越两个非零区间 kKk 证明过程中主要用到 NUAT B 样条基和 C B zier 基的以下性质 0 i l ki tN i rkl 其中是节点的重数 i r i t 0 ki l ki tN 其中是节点的重数 ki rkl ki r ki t 0 0 l ki Bil 0 l ki B ikl 情况 1 基函数跨越一个非零区间 图 4 的定义区间 是 tN ki kii tt i t r重节点 是 ki t rk 1重 NUAT B 样条基可由个 C B zier 基线性表示 因此可以表示成 tN ki k 4 2 1 1 0 1 k j kjjiki tBbtN 由性质 知 0 i l ki tNrkl 0 ki l ki tN1 rl 25 浙 江 大 学 硕 士 学 位 论 文 对 4 2 1 式两边求导 次 并令l i tt 得 0 1 0 1 k j i l kjjii l ki tBbtNrkl 由性质 当时 所以由基的线性无关性得 lj 0 1 i l kj tB 0 ji b rkj 4 2 2 对 4 2 1 式两边求导 次 并令l ki tt 得 0 1 0 1 k j ki l kjjiki l ki tBbtN 1 10 1 ki l kj tB 0 ji b