毕业论文——Bezier和B-样条曲线的算法研究.doc

1、 本科毕业论文 题 目 ： Bezier 和 B-样条曲线的算法研究 系 别 ： 数学与计算机科学系 班 级 ： 学 号 ： 姓 名 ： 指导教师 ： 职 称 ： 起讫日期 ： 2 Bezier 和 B-样条曲线的算法研究 摘要 ： 样条曲线发展迅速。在基于 PC 系统的 3D Max、 AutoCAD、 Maya 等建模工具中，“样条曲线”以“基本图形对象”的存在形式，实现平面绘图、立体绘图基本功能，是“三维动画”的重要组成元素 ；样条曲线也是几何造型技术的重要内容 。“ Bezier 和 B 样条曲线”在样条曲线的发展史中举足轻重，诸多其他曲线都是由它们发展而来的。本文对 Bezier和

2、B 样条曲线的算法进行全面、系统和深入的研究，重点研究它们的性质和相互的内在关系。 关键词： Bezier 曲线 ； B 样条曲线 ； 3 The Investigation of Curve algorithm on Bezier and B-spline Abstract： Spline curve is developing rapidly. Among PC-based system, 3D Max, AutoCAD, Maya and other modeling tools, spline curve have basic function of dimensional drawi

3、ngs and three-dimensional drawing for its “basic graphic object“ form, spline curve is a vital component of “three-dimensional animation,“ it is also an important content of geometric modeling techniques. “Bezier and B-spline curve“ is important in the development of spline curve, many other curves

4、are evolved based on them. This paper has a comprehensive, systematic and deep research on Bezier and B-spline curve algorithm and focuses on their nature and the intrinsic relationship between them. Key words： Bezier curves; B-spline curve; 4 目 录 第 1 章 绪论 . 1 1.1 研究背景 . 1 1.1.1 样条 曲线的发展历程与研究前沿 . 1

5、1.1.2 样条曲线的应用 . 1 1.2 主要工作 . 2 第 2 章 曲线基础 . 3 2.1 曲线的参数表示 . 3 2.2 插值与逼近 . 4 2.2.1 插值 . 4 2.2.1 逼近 . 4 2.3 连续性 . 5 2.3.1 函数的可微性 . 5 2.3.2 几何连续性 . 5 2.4 样条描述 . 6 2.5 三次样条 . 7 第 3 章 Bezier和 B-样条曲线 . 9 3.1 Bezier 曲线的算法研究 . 9 3.1.1 Bezier 曲线的定义 . 9 3.1.2 Bezier 曲线的性质 . 12 3.1.3 Bezier 曲线的拼接 . 13 3.1.4 用

6、de Casteljau 算法离散生成 Bezier 曲线 . 14 3.1.5 Bezier 曲线的几个 不足 . 16 3.2 B-样条曲线的算法研究 . 16 3.2.1 B-样条曲线的定义 . 16 3.2.2 B-样条曲线的分类 . 17 3.2.3 B-样条曲线的性质 . 21 3.2.4 有理样条和 NURBS 曲线 . 22 3.3 Bezier 曲线和 B-样条曲线的比较与相 互转换 . 24 3.3.1 Bezier 曲线和 B-样条曲线的比较 . 24 3.3.2 Bezier 曲线和 B-样条曲线的相互转换 . 24 3.4 自由曲线是自由曲面的基础 . 25 第 4

7、章 结论 . 26 致 谢 . 27 参考文献 . 28 附 件 . 29 计算机科学与 技术 专业毕业论文 1 第 1 章 绪论 1.1 研究背景 1.1.1 样条曲线的发展历程 与 研究前沿 1964 年，美国麻省理工学院（ MIT）的孔斯（ Coons）用封闭曲线的 4 条边界定义一张曲面。同年，舍恩伯格（ Schoenberg）提出了参数样条曲线、曲面的形式。 1971 年，法国雷诺（ Renault）汽车公司的贝济埃（ Bezier）发表了一种用控制多边形定 义曲线和曲面的方法 。 1972 年 ,德布尔 (de Boor)给出了 B 样条的标准计算方法。 1974 年，美国通用汽车

8、公司的戈登（ Gorden）和里森费尔德（ Riesenfeld）将 B 样条理论用于形状描述，提出了 B 样条曲线和曲面。 1975 年，美国锡拉丘兹（ Syracuse）大学的佛斯普里尔（ Versprill）提出了有理 B 样条曲线。 20 世纪 80 年代后期，皮格尔（ Piegl）和蒂勒（ Tiller）将有理 B 样条曲线发展成非均匀有理 B 样条（ Nonuniform Rational B-Spline， NURBS）曲线 。 NURBS 曲线已成为当前自由曲线和曲面描述的最广为流行的技术，目前国际标准化协会（ ISO）已将 NURBS 曲线方法作为定义工业产品几何形状的唯一数

9、学方法。 04 样条曲线的研究领域涉及诸多内容，主要有各阶次样条曲线的不同扩展（比如 NUAHBs、 C-Bezier曲线、 C-B 样条曲线、 H-Bezier 曲线等 ）、结点插入算法的研究及应用、光顺的新方法研究、求值、升阶降阶方法的研究、造型与形状调整的研究以及实时插补技术的研究 等几个方向。 1.1.2 样条曲线的应用 曲线曲面造型是计算机辅助几何设计和计算机图形学的一项重要内 容，也是 CAD/CAM 系统的最关键的部分之一，其应用除了航空、造船、汽车这三大制造业外，还涉及医疗诊断、生物工程等设计领域。 当前， CAD/CAM 中曲线曲面造型的主流方法为 Bezier 曲线曲面和

10、NURBS 方法。针对工程曲线曲面造型中这两种方法存在的缺陷， 07我们可以对已有的样条函数进行调整或修改，通过改变调和函数的形式，对样条曲线进行传递扩展，从而达到调整和改变曲线形状的目的。生成的新样条曲线不仅具备基础样条函数的性质，还具有自身的优点。例如 ， 对二次均匀 B 样条基函数进行扩展，构造出三次和四次带局部参数 的调和函数，推广后得到了 n 次的调和函数，它们具有二次均匀 B 样条基函数的性质，且用它们生成的分段多项式曲线具有与分段二次均匀 B 样条曲线相同的结构和几何性质；又如，用一种混合基（代数多项式和三角函数的线性组合）代替三次多项式曲线方程中的幂基，并相应地修改基函数而形成

11、的用曲线曲面方程所表示的曲线曲面，这就是一种新颖的曲线曲面造型方法 C 曲线曲面理论 。 07大多数物体的曲线曲面部分，都可以 使用灵活的 B 样条曲线进行拟合。在 基于 PC 系统 的 3D Max、 AutoCAD、 Maya 等建模工具中 ，“样条曲线”以 “ 基本图形对 象 ” 的存在形式，实现平面 绘图 、立体绘图基本功能 ，是 “三维动画”的重要 组成 元素 。 Bezier 和 B-样条曲线的算法研究 2 1.2 主要 工作 本文 主要的工作是 系统 的 研究和 整理 Bezier 和 B 样条曲线的算法 、性质、 作用 以及 样条曲线 的其他 相关 基础知识，并基于 VC+6.

12、0 对这两种样条曲线进行实现 和性质比较 。 论文思路大致如下： 首先讨论 Bezier 曲线。 Bezier 曲线在本质上是由调和函数根据控制点插值生成的，其运算量较大。 de Casteljau 算法的效率则要高得多。 Bernstein 调和函数在 0， 1上都是“活动”的，使得 Bezier 曲线不能作局部 修改；且调和函数的次数与控制点的个数相关，使得高阶次 Bezier 曲线计算较为复杂 ，并且由于对数字取整也给结果带来误差 ；采用 在点集中插入一些点 “拼接”虽然可以满足多段 Bezier 曲线的光滑连接条件，但不方便。 然后 是 寻找到 能灵活控制曲线形状且计算量不大 等更好性

13、质 的调和函数 。 为了获得足够的灵活性，可以试着把几个低次多项式分段“连接”起来。这样在不同的 t 分段区间上用不同多项式定义的曲线称为分段多项式。对曲线形状更自如地控制，并能够指定对哪些控制点插值，把讨论过的所有设计方法都封装进去，组成单个算法。 用 n次 B样条基 函数替换 Bernstein基函数，便获得 B(basis)样条曲线 。 接着 是对 B 样条曲线进行研究。 主要研究 均匀 B 样条曲线 的算法 ， 并介绍 非均匀 B 样条曲线 和开放 B 样条曲线。 Bezier 曲线是 B 样条曲线 的特例， B 样条多项式的阶数增加 1，每个 B 样条 调和函数就支持扩展一个区间，同

14、时降低了一些局部控制能力。当 m 到达边界 n+1 时，就得到了 Bezier曲线，这时的局部控制能力为最小。 Bezier 曲线和 B 样条曲线 之间可以进行 相互转换。 最后点明样条曲线是自由曲面的基础。 另外，结合在 VC+6.0 上实现的 Bezier 和 B 样条曲 线，对其性质进行直观 的 分析 和比较 。 计算机科学与 技术 专业毕业论文 3 第 2 章 曲线基础 2.1 曲线的参数表示 曲线的表示可以分为参数表示和非参数表示两种，其中非参数表示又可分为显式表示和隐式表示两种。对于一个平面曲线，显式表示一般形式是 y=f(x)。在此方程中，一个 x 值与一个 y 值对应，所以显式

15、方程不能表示封闭或多值曲线，例如，不能用显式方程表示一个圆。 如果一个平面曲线方程，表示成 f(x,y)=0 的形式，则称之为隐式表示。隐式表示的优点是易于判断函数 f(x,y)是否大于、小于或等于零，也就易于判断点是落在所表示曲线上或曲线的哪一侧。 非参数 方程 的缺点是：与坐标轴相关；会出现斜率为无穷大的情形（如垂线）；对于非平面曲线，难以用常数系数的非参数化函数表示；不便于计算机编程。 由于参数表示的曲线具有几何不变性等优点，计算机图形学中通常用 参数形式 描述曲线。在几何造型系统中，曲线方程通常表示成参数的形式，即曲线上任一点的坐标均表示成给定参数的函数。假定用 t 表示参数，平面曲线

16、上任一点 P 可表示为 ( ) ( ), ( )P t x t y t (2.1) 空间曲线上任一 三维点 P 可表示为 ( ) ( ), ( ), ( )P t x t y t z t (2.2) 最简单的参数曲线是直线段，端点为 1P 、 2P 的直线段参数方程可表示为 1 2 1( ) ( ) 0 , 1 p t P P P t t (2.3) 圆在计算机图形学中应用十分广泛，其在第一象限内的单位圆弧的非参数显式表示为 21 ( 0 x 1 )yx 其参数形式可表示为 22212( ) , ( t 0,1 )11ttpt (2.4) 在曲线的表示上，参数方程比显式、隐式方程有更多的优越性

17、，主要表现在一下几点。 可以满足几何不变性的要求。 有更大的自由度来控制曲线的形状。 对非参数方程表示的曲线进行变换，必须对曲线上的每个型值点进行几何变换；而对参数表示的曲线可对其参数方程直接进行几何变换。 便于处理斜率为无穷大的情形，不会因此而中断计算。 参数方程中，代数、几何相关和无关的变量是完全分离的，而且对变量个数不限，从而便于 用户把低维空间中曲线扩展到高维空间去。这种变量分离的特点使人们可以用数学公式处理几何分量。 规格化的参数变量 0,1t ，使其相应的几何分量是有界的，而不必用另外的参数去定义边界。 Bezier 和 B-样条曲线的算法研究 4 易于用向量和矩阵表示几何分量，简

18、化了计算。 2.2 插值与逼近 2.2.1 插值 给定一组有序的数据点 iP (i=0,1,2, ,n)，构造一条曲线顺序通过这些数据点，称为对这些数据点进行插值，所构造的曲线称为插值曲线。 (1) 线 性插值 假设给定函数 f(x)在两个不同点 1x 和 2x 的值，用一个线形函数 ()y x ax b ，近似代替f(x)，称 ()x 为 f(x)的线性插值函数。其中线性函数的系数是 a， b，通过条件 ： 1122()()xyxy ()x 可表示为 ： 1 2 11 1 1 22 1 1 2 2 1( ) ( )y y x x y yx y x x y yx x x x y y (2.5)

19、 (2) 抛物线插值 抛物线插值又称为二次插值。设已知 f(x)在 3 个互异点 1x ， 2x ， 3x 的函数值为 1y ， 2y ，3y ，要求构造一个函数： 2()y x ax bx c ，使 () 在 结 点 ( 1,2,3)ixi 处与 ()fx在 ix 处的值相等。由此可构造 ( ) ( ) ( 1 , 2 , 3 )iix f x y i 的线性方程组，求得 a， b， c，即构造了 ()x 的插值函数。 02 2.2.1 逼近 当型值点较多时，构造插值函数通过所有型值点是相当困难的。而测量所得的数据点本身比较粗糙，使得构造精确的插值函数也是没有意义的。这时通常选择一个次数较低

20、的函数，构造一条曲线使之在某种意义下最接近给定的数据点，称为对这些数据点进行逼近，所构造的曲线为逼近曲线。插值和逼近则统称为拟合。 逼近的方法最常用的是最小二乘法 ，假设给定一组数据点 ( , )( 1, 2, , )iix y i n ，要求构造一个逼近函数 ()y f x 。令 ()fx是 m 次多项式，即 图 2-1 曲线的插值 计算机科学与 技术 专业毕业论文 5 0()m jjjf x a x逼近的程度可以通过各点偏差的平方和来度量。最小二乘问题就是要求出各系数 ja ，使偏差的平方和最小，即求解式 (5.6)所示函数的极值问题 ： 221 1 0( ) ( ) n n m jj i

21、 i j i ii i ja f x y a x y (2.6) 如要取到极值，则 102 0 0 , 1 , ,nm jjj k k kkji a x y x i ma (2.7) 这里只有 m+1个系数 ja 是未知量，可通过求解 m+1个方程得出。将系数 ja 带入多项式函数 ()fx即可得到所求的逼近函数。 2.3 连续性 设计一条复杂曲线时，常常通过多段曲线组合而成，这需要解决曲线段之间如何实现光滑连接的问题。曲线间连接的光滑度的度量有以下两 种。 2.3.1 函数的可微性 把组合参数曲线构造成在连接处具有直到 n 阶连续，即 n 阶连续可微，这类光滑度称之为 nC 或n 阶参数连续

22、性。 2.3.2 几何连续性 组合曲线在连接处满足不同于 nC 的某一组约束条件，称为具有 n 阶几何连续性，简记为 nG 。 曲线光滑度的这两种度量方法并不矛盾， nC 连续包含在 nG 连续之中。 图 2-2 曲线的逼近 02 Bezier 和 B-样条曲线的算法研究 6 对于曲线 P(t)和 Q(t)，参数 0,1t 。若要求在接合处达到 0G 连续或 0C 连续，即两曲线在结合处位置连续，有 (1) (0)PQ (2.8) 若要求在结合处达到 1G 连续，就是说两条曲线在结合处在满足 0G 连续的条件下，并有公共的切线向量： (1) (0)PQ (2.9) 当 1 时， 1G 连续就称

23、为 1C 连续。若要求在结合处达到 2G 连续，就是说两条曲线在结合处在满足 1G 连续的条件下，并有公共的曲率： 33(1) (1) ( 0 ) ( 0 )(1) ( 0 )P P Q QPQ(2.10) 将式 (2.9)及式 (2.10)合并整理，得 21(1) (0)PQ(2.11) 这个关系为 2( 0 ) (1) (1)Q P P (2.12) 为任意函数。当 1, 0时， 2G 连续就称为 2C 连续。 2.4 样条描述 样条（ Spline）一词来源于工程绘图人员为了将一些指定点连接成一条光顺曲线所使用的工具，即富有弹性的细木条或薄钢条。 最初， 样条曲线都是借助于物理样条得到的

24、，放样员把富有弹性的细木条（或有机玻璃条），用压铁固定在曲线应该通过的给定型值点处，样条做自然弯曲所绘制出来的曲线就是样条曲线。样条曲线不仅通过各有序型值点，并且在各型值 点处的一阶和二阶导数连续，也即该曲线具有连续的、曲率变化均匀的特点。 在计算机图形学中 ，样条曲线是指由多项式曲线段连接而成的曲线，在每段边界处满足特定的连续性条件。 通常用式 (2.9)来描述 n 次样条参数多项式曲线 ： 212 1 0212 1 0212 1 0()( ) t 0 , 1 ()nnnnnnx t a t a t a t ay t b t b t b t bz t c t c t c t c (2.13) 将式 (2.9)写成矩阵乘积的形式，得