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

1、2噪罟眾本科毕业论文题目：beker和b-样条曲线的算法研究系 另u: 数学与计算机科学系班 级：学 号：姓 名：指导教师：职称：起讫日期：bezier和b-样条曲线的算法研究摘要：样条曲线发展迅速。在基于pc系统的3d max. autocad. maya等建模工具中，“样条曲线” 以“基本图形对象”的存在形式，实现平面绘图、立体绘图基本功能，是“三维动画”的重要组成 元素；样条曲线也是几何造型技术的重要内容。“bezier和b样条曲线”在样条曲线的发展史中举 足轻重，诸多其他曲线都是由它们发展而来的。本文对bezier和b样条曲线的算法进行全面、系统 和深入的研究，重点研究它们的性质和相互

2、的内在关系。关键词:bezier曲线；b样条曲线;the investigation of curve algorithm on bezier and b-splineabstract： spline curve is developing rapidly. among pc-based system, 3d max, autocad, maya and other modeling tools, spline curve have basic function of dimensional drawings and three-dime nsional drawi ng for its “b

3、asic graphic objecf form, spline curve is a vital comp orient of hthree-dimensional animation；* it is also an important content of geometric modeling techniques. "bezier and b-spline curve11 is important in the development of spline curve, many other curves are evolved based on them this paper

4、has a comprehensive, systematic and deep research on bezier and b-spline curve algorithm and focuses on their nature and the intrinsic relationship between themkey words： bezier curves; b-spline curve;第1章绪论11.1研究背景11.1.1样条曲线的发展历程与研究前沿 11.1.2样条曲线的应用11.2主要工作2第2章曲线基础32.1曲线的参数表示32. 2插值与逼近42. 2. 1 插值42.

5、2. 1 逼近42. 3连续性52. 3.1函数的可微性52. 3.2儿何连续性52. 4样条描述62. 5三次样条7第3章bezier和b一样条曲线93. 1bezier曲线的算法研究 93. 1. 1 be刁ier*曲线fl勺定义 93. 1. 2 bezier 曲线白勺'性质 123. 1.3 bezier曲线的拼接133. 1. 4用de castel jau算法离散生成bezier曲线 143. 1. 5 bezier曲线的几个不足163.2b-样条曲线的算法研究163. 2.1 b-样条曲线的定义163. 2. 2 b-样条曲线的分类173. 2.3 b-样条曲线的性质21

6、3. 2. 4有理样条和nurbs曲线 223. 3bezier曲线和b-样条曲线的比较与相互转换 243. 3. 1 bezier曲线和b-样条曲线的比较 243. 3. 2 bezier曲线和b-样条曲线的相互转换 243.4自由曲线是自由曲面的基础25第4章结论26致谢27参考文献28附件29第1章绪论1 1研究背景1.1.1样条曲线的发展历程与研究前沿1964年，美国麻省理工学院(mtt)的孔斯(coons)用封闭曲线的4条边界定义一张曲面。同 年，舍恩伯格(schoenberg)提出了参数样条曲线、曲面的形式。1971年，法国雷诺(renault) 汽车公司的贝济埃(bezier)发

7、表了一种用控制多边形定义曲线和曲面的方法。1972年,德布尔(de boor)给出了 b样条的标准计算方法。1974年，美国通用汽车公司的戈登(gorden)和里森费尔德 (riesenfeld)将b样条理论用于形状描述，提出了 b样条曲线和曲面。1975年，美国锡拉丘兹 (syracuse)大学的佛斯普里尔(versprill)提出了有理b样条曲线。20世纪80年代后期,皮格 尔(piegl)和蒂勒(tiller)将有理b样条曲线发展成非均匀有理b样条(nonuniform rational b-spline, nurbs)曲线。nurbs曲线己成为当前口 itl曲线和曲而描述的最广为流行的

8、技术，冃前国 际标准化协会(iso)己将nurbs曲线方法作为定义工业产品几何形状的唯一数学方法。冋样条曲线的研究领域涉及诸多内容，主耍有各阶次样条曲线的不同扩展(比如nuaiibs>c-bezier 曲线、c-b样条曲线、h-bezier曲线等)、结点插入算法的研究及应用、光顺的新方法研究、求值、 升阶降阶方法的研究、造型与形状调整的研允以及实时插补技术的研允等几个方向。1.1.2样条曲线的应用曲线曲面造型是计算机辅助几何设计和计算机图形学的一项重要内容，也是cad/cam系统的最 关键的部分之一，其应用除了航空、造船、汽车这三大制造业外，还涉及医疗诊断、生物工程等设 计领域。当前，c

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

10、项式曲线方程中的幕基, 并相应地修改基函数而形成的用曲线曲面方程所表示的曲线曲面，这就是一种新颖的曲线曲面造型 方法一一c曲线曲面理论。大多数物体的曲线曲面部分，都可以使用灵活的b样条曲线进行拟合。 在基于pc系统的3d max. autocad. maya等建模工具中，“样条曲线”以“基本图形对象”的存在 形式，实现平面绘图、立体绘图基本功能，是“三维动画”的重要组成元素。本文主要的工作是系统的研究和整理bezier和b样条曲线的算法、性质、作用以及样条曲线的 其他相关基础知识，并基于vc+6. 0对这两种样条曲线进行实现和性质比较。论文思路大致如下：首先讨论bezier曲线。bezier曲

11、线在本质上是由调和函数根据控制点插值生成的，其运算量 较大。de casteljau算法的效率则要高得多。bernstein调和函数在0, 1上都是“活动”的，使 得bezier曲线不能作局部修改；且调和两数的次数与控制点的个数相关，使得高阶次bezier曲线 计算较为复杂，并且由于对数字取整也给结果带来误差；采用在点集中插入一些点“拼接”虽然可 以满足多段bezier曲线的光滑连接条件，但不方便°然后是寻找到能灵活控制曲线形状且计算量不大等更好性质的调和函数。为了获得足够的灵活 性，可以试着把几个低次多项式分段“连接”起来。这样在不同的t分段区间上用不同多项式定义 的曲线称为分段多

12、项式。对曲线形状更自如地控制，并能够指定对哪些控制点插值，把讨论过的所 有设计方法都封装进去,组成单个算法°用n次b样条基函数替换bernstein基函数，便获得b(basis) 样条曲线。接着是对b样条曲线进行研究。主要研究均匀b样条曲线的算法，并介绍非均匀b样条曲线和 开放b样条曲线。bezier曲线是b样条曲线的特例，b样条多项式的阶数增加1,每个b样条调和 函数就支持扩展一个区间，同时降低了一些局部控制能力。当m到达边界n+1时，就得到了 bezier 曲线，这时的局部控制能力为最小。bezier曲线和b样条曲线之间可以进行相互转换。最后点明样条曲线是自由曲面的基础。另外，结

13、合在vc+6.0上实现的bezier和b样条曲线，对其性质进行直观的分析和比较。第2章曲线基础2. 1曲线的参数表zf曲线的表示对以分为参数表示和非参数表示两种，其中非参数表示又对分为显式表示和隐式表 示两种。对于一个平面曲线，显式表示一般形式是y二f(x)。在此方程中，一个x值与一个y值对应, 所以显式方程不能表示封闭或多值曲线，例如，不能用显式方程表示一个圆。如果一个平面曲线方程，表示成f(x, y)=0的形式，则称之为隐式表示。隐式表示的优点是易于 判断函数f(x, y)是否大于、小于或等于零，也就易于判断点是落在所表示曲线上或曲线的哪一侧。非参数方程的缺点是：与坐标轴相关；会岀现斜率为

14、无穷大的情形(如垂线)；对于非平面曲线, 难以用常数系数的非参数化函数表示；不便于计算机编程。由于参数表示的曲线具有几何不变性等优点，计算机图形学中通常用参数形式描述曲线。在几 何造型系统中，曲线方程通常表示成参数的形式，即曲线上任一点的坐标均表示成给定参数的两数。 假定用t表示参数，平面曲线上任一点p可表示为(2. 1)(2. 2)(2. 3)(2. 4)%) = xo, w) 空间曲线上任一三维点p可表示为p(t) = x(t)9 y(t z(/)最简单的参数曲线是直线段，端点为片、占的直线段参数方程可表示为“話+(£-斥"t g 0,1圆在计算机图形学中应用十分广泛，

15、其在第一象限内的单位圆弧的非参数显式表示为其参数形式可表示为l-/2 2t i+7,t+?在曲线的表示上，参数方程比显式、隐式方程有更多的优越性，主要表现在一下儿点。 可以满足儿何不变性的要求。 有更大的自由度来控制曲线的形状。 对非参数方程表示的曲线进行变换，必须对曲线上的每个型值点进行儿何变换；而对参数表示的曲线可对其参数方程直接进行儿何变换。 便于处理斜率为无穷大的情形，不会因此而屮断计算。 参数方程屮，代数、儿何相关和无关的变量是完全分离的，而且对变量个数不限，从而便于用户把低维空间屮曲线扩展到高维空间去。这种变量分离的特点使人们可以用数学公式 处理儿何分量。 规格化的参数变量zg0,

16、l,使其相应的儿何分量是有界的，而不必用另外的参数去定义边界。 易于用向量和矩阵表示几何分量，简化了计算。2. 2插值与逼近2.2.1插值给定一组有序的数据点pi (1=0, 1, 2,n),构造一条曲线顺序通过这些数据点，称为对这些数 据点进行插值，所构造的曲线称为插值曲线。(1) 线性插值假设给定函数f(x)在两个不同点西和“2的值，用一个线形函数y =(pm = ax-bf近似代替 f(x),称0(兀)为f(x)的线性插值函数。其中线性函数的系数是a, b,通过条件：j 0(召)=x(p(x2) = y20(兀)可表示为:恥)二必+亠(兀_和=必(25) 勺一西西一兀2力一刃(2) 抛物

17、线插值抛物线插值又称为二次插值。设己知f(x)在3个互异点西，无的函数值为刃，力， %,要求构造一个函数：yuqoror'+bx+c,使©(x)在结点形( =1,2,3)处与/(兀)在兀处 的值相等。由此可构造(x) = /(x.) = x.(/ = l,2,3)的线性方程组，求得a, b, c,即构造了從兀)的 插值函数。02图21曲线的插值2.2. 1逼近当型值点较多时，构造插值函数通过所有型值点是相当困难的。而测量所得的数据点本身比佼 粗糙，使得构造精确的插值函数也是没有意义的。这时通常选择一个次数较低的函数，构造一条曲 线使之在某种意义下最接近给定的数据点，称为对这些

18、数据点进行逼近，所构造的曲线为逼近曲线。 插值和逼近则统称为拟合。逼近的方法最常用的是最小二乘法，假设给定一组数据点(兀j)(i = l,2,n),要求构造一个逼近函数y = /(x) o令/(x)是m次多项式，即/(兀)=工幻0戶0逼近的程度可以通过各点偏差的平方和来度量。最小二乘问题就是要求出各系数d厂使偏差的 平方和最小，即求解式(5. 6)所示函数的极值问题：0(勺)=工心)-订=工工勺兀/ -牙2(2. 6)z=1z=1j=0如要取到极值，则字=2££勺兀/一儿兀/=0 z = 0,l, ,m(2.7)ai k=i y=0这里只有ni+l个系数勺是未知量，可通过求

19、解m+1个方程得出。将系数勺带入多项式函数.f(x) 即可得到所求的逼近函数。2. 3连续性设计一条复杂曲线时，常常通过多段曲线组合而成，这需要解决曲线段之间如何实现光滑连接的问题。曲线间连接的光滑度的度量有以下两种。2.3.1函数的可微性把组合参数曲线构造成在连接处具有直到n阶连续，即n阶连续可微，这类光滑度称之为c"或n阶参数连续性。2. 3. 2几何连续性组合曲线在连接处满足不同于c"的某一组约束条件，称为具有n阶几何连续性，简记为g"。曲线光滑度的这两种度量方法并不矛盾，c"连续包含在g"连续之中。对于曲线p(t)和q(t),参数虫0,

20、1。若要求在接合处达到g°连续或c°连续，即两曲线在结 合处位置连续，有p(l) = 2(0)(2. 8)若要求在结合处达到g连续，就是说两条曲线在结合处在满足g°连续的条件下，并有公共的 切线向量：p'(1) = 0(o)(2.9)当q = 1时，gi连续就称为c连续。若要求在结合处达到g?连续，就是说两条曲线在结合处 在满足g连续的条件下，并有公共的曲率：(2. 10)(2.11)(2. 12)p严 _ 0(0)0(0)33、 |2*(0)|'将式(2. 9)及式(2. 10)合并整理,得p”二 0(0)a这个关系为q”(o) = /p”(1)

21、 + 0p 0为任意函数。当a = ,0 = 0时，g?连续就称为c?连续。2. 4样条描述样条(spline) 一词來源于工程绘图人员为了将一些指定点连接成一条光顺曲线所使用的工具, 即富有弹性的细木条或薄钢条。最初，样条曲线都是借助于物理样条得到的，放样员把富有弹性的细木条(或有机玻璃条)，用 压铁固定在曲线应该通过的给定型值点处，样条做自然弯曲所绘制出来的曲线就是样条曲线。样条 曲线不仅通过各有序型值点，并且在各型值点处的一阶和二阶导数连续，也即该曲线具有连续的、 曲率变化均匀的特点。在计算机图形学中，样条曲线是指由多项式曲线段连接而成的曲线，在每段边界处满足特定的 连续性条件。通常用式

22、(2. 9)來描述n次样条参数多项式曲线：x(f) = antn + a2t2 + a/ +* y(/) = b' + + bjj + b/ + b()t g 0,1(2. 1.3)z(/) = cj” + + ct + c()将式(2. 9)写成矩阵乘积的形式，得卩=w)=严z(0bteo,l(2. 14)其中c为(n+l)x3阶的系数矩阵，t为n+1个幕形式的基函数组成的向量。问2. 5三次样条多项式是一种基本的数学研究对象，在计算机图形学中经常使用多项式，这时因为多项式定义 简介，并且计算起来效率很高。虽然sederberg己经证明了对给定的多项式函数x(t)和y(t),总能找到

23、其隐式形式，但是一般 来说，只有对一次或二次的隐式形式才总能找到其参数方程形式。用一次和二次多项式参数化的曲 线很容易理解。当使用更高次的多项式时，情况就要复杂得多。三次多项式为曲线设计提供了一条功能强大的途径。但是这些方法不是从隐式形式出发寻找其 参数化形式，而是从设计者选定的一组“控制点”出发，应用某个特定的算法生成曲线上的点，如 果满意就接受这条曲线而不去管它的隐式形式。与单纯采用数学手段相比，这种方法在许多方面都 是一种更自然的曲线设计方法。3三次多项式在灵活性和计算速度之间提供了一个合理的这种方案。与更高次的多项式相比，三 次样条只需要较少的计算与存储且较稳定；与低次的多项式相比，三

24、次样条又具有更多的灵活性， 事实上，大多数形状表示与设计都是采用三次多项式来实现的。给定n+1个点，可得到通过每个点的分段三次多项式曲线：(2. 15)x(t) = axt3 + bxt2 + cxt + dx < y(t) = a/ + byt2 + cyt + dyz(r) = azt3 + bzt2 + c.t + d.方程组中12个系数唯一地确定了一条3次参数曲线的位置与形状。将式(2.11)写成向量式，得p(r) = at' +br + ct+ dt e 0,1 (2. 16)其中a, b, c, d是代数系数向量，p(t)是三次参数曲线上任一点的位置向量。描述参数曲线

25、的条件有端点位置向量、端点切线向量及曲率等。对三次参数曲线，可用其端点 向量p(0), p和端点切线向量p (0), p(l)描述,将p(0), p,p(0), p(l)简记为 口，几,p, 则由式(2. 13)可得(2. 17)a = 2po_2p+pl+p 匕=-31入+3卩 - 2pp'、 c = pld =将这些系数代回到原曲线方程，则曲线方程可表示为(2. 18)p(r) = (2尸 一 3尸 +1) a + (-2 尸 + 3 尸)门 +(尸 _ 2尸 + /)”o+(尸一尸)刀tg pi j这时三次参数曲线为三次hermite样条曲线，即其中,p(o= &% s

26、cy d、.azbzczd_itab1cda000r-1 2-211 _b111ia-33-2-1c0010po0010p'od_3210_p_1000_p_是hermite矩阵，它是边界约束矩阵的逆阵,通常为为常数。(2. 19)(2. 20)gh是hermite儿何向量。式(2. 17)为三次hermite样条曲线的方程:p(t) = tmhgh虫0,1(2.21)在上式中只要给定g就可以求出p(t)o对于不同的初始条件是不同的，但t和都是 相同的，将tm称为hermite基函数(也可以称为混合函数或调和函数)。其表达式为 2-211 _t3 t2-33-2-1tmh =t f(2

27、. 22)一-00101000则hermite基函数的各分量可写为/70(/) = 2r3-3r2 + l= -2t3+3t2h2(t) = t3-2t2+th3(t) = t3-t2(2. 23)利用基函数表达的三次hermite样条曲线的方程为p =p.h. + pxh + p.h. (0 + 口 a (2. 24)其屮h()和耳专门控制端点的函数值对曲线的彫响，而同端点的导数值无关；a和比 则专门控制端点的一-阶导数值对曲线形状的影响，而同端点的函数值无关。或者说，h0(t)和h2(t) 控制左端点的彫响，/a)和aa)控制右端点的彫响。三次hermite样条曲线特点是可以局部调整，因为

28、每个曲线段仅依赖于端点约束。基于hermite 样条的变化形式为cardinal样条和kochanek-bartels样条。hermite曲线具有几何不变性第3章bez i er和b-样条曲线bezier和b-样条曲线的算法研究，即由基本运算及规定的运算顺序所构成的完整的解题步骤。3. 1 bezier曲线的算法研究1971年，法国雷诺(renault)汽车公司的贝济埃(bezier)发表了一种用控制多边形定义曲 线和曲面的方法一一bezier曲线。这中方法能够较直观地表示给定的条件与曲线形状的关系，使用 户对以方便地通过修改参数来改变曲线的形状及阶次，而且算法较为简单，易于被用户接受。bez

29、ier曲线是通过一组多边形的顶点来定义的。如果多边形的顶点固定不变，则由其定义的 bezier曲线是唯一的。在多边形的各顶点中，只有第一点和最后一点在曲线上且作为曲线的起点和 中点，其他的点用于控制曲线的形状及阶次。曲线的形状趋向于多边形的形状，要修改曲线，只要 修改多边形的各顶点就可以了。因此，该多边形又称bezier曲线的控制多边形，其顶点称为控制点。 常用的三次bezier曲线如图3-1所示。丽3. 1. 1 bezier曲线的定义bezier曲线在本质上是由调和函数根据控制点插值生成的，其数学表达式为如下的参数方程：p(f) = £piben“ 呵0,1(3. 1)/=()其

30、中pk构成该bezier曲线的特征多边形，benk n(t)是n次bernstein基函数。bernstein基函数具有如下形式：y),、ben. (r)=-r(i- tyi 二c；t( i 一tyir=o, i, , n(3.2)il(n-i)!”这里规定o°=l,o! = l,因此当 t=o 且 i=o 时，benin(t) = l ；当 t=o 且 ih0 时,benitl(t) = o；当 t=l 且 i二n 时，benin(/) = 1 ；当 t=l h i hn 时，benin(r) = 0 o (1) 一次 bezier 曲线(n二 1)一次多项式，有两个控制点，其数学

31、表示及矩阵表示为im2 工£b门=+=(1一/)*+比虫0川(3. 3)-1 r1 0显然，这是一条连接po、p1的直线段，如图3-2所示。06p1图3-2线性内插法获得线性bezier曲线的过程 二次bezier曲线（n二2）二次多项式，有三个控制点，其数学表示如下：2p £耳色2（）二佗bq 2（t） + 片b 2 +2（/）i= （l-z）2 + 2（ （1 /） a + 尸鬥re 0,1=（£-2£ + 人）/2 + 2（£-+ e(3. 4)由上式的结果可知，二次bezier曲线为抛物线,图形如图3-3。将上式改写为矩阵形式卩=r 1

32、-21-2 2 0a©0,11 0 0a.(3. 5)图3-3 do castcljau算法获得二次bezier曲线的过程(3) 三次 bezier 曲线(n二3)三次多项式，有四个控制点，其数学表示如下:3皿)=工朋,3(0 = £().3()+ 片垃3(" + 马32 3(0 + £33.3("/=(1 f )3 £ + 3(1 f )2 a + 3八(1/)£+/迅zgio,1j (3.6)其矩阵形式为-13-3r3-630-3300p21000p-p(t) = t3 r t 1(3. 7)上面式中的bernstein

33、多项式构成了三次bezier曲线的一组基，或称三次beizer曲线的调和函数,即:(3. 8)类似可以得出四次及更高次的bezier曲线函数。通过以上定义可以看出bezier曲线的特点： bezier曲线基函数的次数等于控制点的数目减1； bezier曲线的基函数在整个定义区问内都不为0。血06p图3-5 de castel jau算法获得三次bezier曲线的过程3. 1.2 bezier曲线的性质bezier曲线具有一些重要的性质，这些性质使其特别适合于cagd。（开放b样条曲线也具有这些性质） 端点插值当t二o时，p（o）=代,故p（t=o）决定曲线的起点;当t=i时，p（i）= pn,

34、故p（t=i）决定 曲线的终点。因此，bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。冋 对称性只要保持特征多边形的顶点位置不变，但顺序颠倒，所得新的bezier曲线形状不变，只是 参数变化的方向相反。呦 仿射不变性（几何不变性）常常为了缩放一条bezier曲线，或者改变其方向和位置以备后用，需要对其进行仿射变化。 只须对控制点施加变换（变换一次），然后对这些新的控制点用同样的bernstein式重新生 成任意t值处的变换后的bezier曲线。仙 参数的仿射变换不变性通常，我们定义的参数区i'可为t g 0,1。但是有时使用别的区i'可更方便。比方参数u在a b

35、的区间上变化。为此只须把每个t替换为：随着u从？1变化到b,每个bernstein多项式的变量从0变化到1,这正如f丘0,1。 凸包性（线性精度：曲线上一部分是直线。）由于当tw 0, 1时，bernstein多项式之和为二(1 /) + ""三 1(3. 10)(3. 11)这说明构成了 beizer曲线的一组权函数，所以bezier曲线一定落在其控制多边形 的凸包之中。 波动减小性粗略地说，bezier曲线的“波动”程度不能超过英控制多边形的“波动”。更精确地说， 任何直线与bezier曲线的交点个数不超过其与这条曲线的控制多边形的交点个数。10,1图3-7波动减小性3

36、. 1.3 bezier曲线的拼接儿何设计屮，一条bezier曲线往往难以描述复杂的曲线形状。这是由于增加特征多边形的顶点 数，会引起bezier曲线次数的提高，而高次多项式乂会带来计算上的困难。所以有时采用分段设计, 然后将各段曲线相互连接起来，并在接合处保持一定的连续条件。下面讨论两条bezier曲线达到不 同阶儿何连续的条件。假设给定两条bezier曲线"和q，相应控制点为斥0 = 0,1,，对和0（丿=0,1,，加）， 如图3-8所示。02图38两段三次bezier曲线的连接要使p和q达到g°连续的充分必要条件是:(3. 12)要使p和曲)达到u连续的充分必要条件是

37、：化_、，匕(qjq这3点共线，即(3. 13)qo) = apl)q -q)=ap3-p2)(3) 要使p(f)和q达到g2连续的充分必要条件如下： 在g连续的条件下，与q-q)均不为零且同向，还要求在尤处曲率相等且主法线 的方向一致。如对于三次bezier曲线，要使它达到g?连续即要满足式(3.13),即(3. 14)0(o) = 0p”(1)(q)_2q +2)= 0(片_2£ + 呂)即2，化十此(qo)，q、，q2这5点共面，且久2和q或者同在直线即q上或者位于直线即q的同侧，即他，即此)二 iqqf(3 15)(即2,仃必)丨即麻其中d(q29 和d(£,_2,

38、即分别表示和弘2到直线即必的距离。通常达到二阶几何连 续即可满足要求。"刘3. 1.4用de caste i jau算法离散生成bezier曲线前面讨论的bezier曲线绘制算法完全是按照调和函数的方式写出的，其运算量较大。下面研究 的de castel jau算法的效率则要高得多。de castel jau算法是用下面的迭代公式计算型值点p(t):( pr = 0pr =.i=o, 1, ,n-r(3. 16)'1(1_/比1+比1,2, ,n可以用数学归纳法证明型值点p就是片o对于三次bezier曲线，有03f sp； = p?用=(1t)膚+ r用f =(1_唧+卅f

39、=(1-/)罗+禺° 圧=(1_/)用+记 严=(1_()斤+巴 用=(1一/)厅+比2(3. 17)图3-9 de castel jau算法的计算过程这个计算过程如图3-9所示。其中横向箭头表示权重为1 -f ,斜向下的箭头表示权重为to根据该算法的原理，以三次bezier曲线为例，求取参数t处的型值点。步骤如下：(1) 按照特征多边形各顶点 即仲 的排列顺序，将特征多边形的三条边依次按比值t： 1-t分 为两段，取得分店尺、p；、p；。(2) 对边只耳、片迟分别再按比值t： (1-t)分为两段，取得分点用、用。(3) 对边用p；按比值t： (1-t)分为两段，取得分点用，即为t处

40、的型值点。图3-10使用de casteljau算法绘制bezier曲线上的点冏3. 1.5 bezier曲线的几个不足(1) bernstein多项式的次数与控制点的个数有关。基于n+1个控制点的bezier曲线是若干个n 次多项式的组合，这就导致高次多项式计算起来代价很高，并且由于对数字取整也给结果带來误差。(2) 没有局部控制能力。在bezier曲线中，对任何一个控制点的改变都会导致整条曲线的改变。 这是因为每个bernstein多项式都在整个0, 1区间上有支持，而最后得到的曲线是这些函数的混 合，所以每一个控制点对01之间所有t值处的曲线都有影响。我们要寻找一组控制点具有一定局 部控

41、制能力的调和断数。(3) 虽然可以通过在点集中插入一些点来满足多段bezier曲线的光滑连接条件，但这种方法显 然很不方便。为了克服上述缺点，1972年，de boor和cox分别提出了 b样条的计算方法。1974年，美国通 用汽车公司的gorden和riesenfeld提出了 b样条曲线和曲面。b样条曲线除保持了 bezier曲线的 直观性和凸包性等优点之外，还可以局部修改，曲线形状更趋近于特征多边形。b样条曲线可以连 续光滑拼接，曲线的阶次与顶点数无关。由于这些原因，b样条曲线和曲面得到越來越广泛的应用。3. 2 b-样条曲线的算法研究b样条曲线是低阶次曲线，易于进行局部修改，更逼近特征多

42、边形。b样条曲线用n次b样条基 函数替换了 bernstein基函数。3.2.1 b-样条曲线的定义b样条曲线的方程定义为:(3. 18)虫o,ii=0在式(3.18)，顶点£(= 0,1,2, /)为控制顶点，又称为徳布尔(de boor)点。称折线££ p其他为p(t)的控制多边形，k为b样条曲线的次数。bik(t)为k次b样条基函数。可通过式(3.19)计 算b样条基函数，即(3. 19)b讥=bg+严叮bjg (r)h+k hh+k+ £+1在式(3.19)屮规定0/0 = 0。该递推公式表明，欲确定第i个k次b样条基函数bik(r),需 要用到

43、w,+i，疋+如共k + 2个结点，称区间仏易+如为b讥的支持区问。b样条曲线方程中， n+1个控制点弓(,=0丄 /),要用到n+1个k次b样条基函数0它们支持区间的并集定义 了这一组b样条基函数的结点向量t = (z0,+如)。昭一对分段函数相遇的点称为连结点(joints),发生在相遇时的t值称为结点(knot)。(1) 一次b样条基函数一次b样条基函数b.j(r)可由两个零次基函数b.0(r)和b/>i0(r)递推得到，是这两个零次基函 数的凸线性组合公式为（3. 20）b,i(0 = 為+严丁為，。石+1心几1其中0,其他0,其他将式(3. 20)用分段函数表示,"+

44、i - " i+2 /<-2 £+10,（3.21）其他(2) 二次b样条基函数二次b样条基函数b/ 2(r)是相邻两个一次b样条基函数b-jw的凸线性组合，即(一 £)2，t；<t< t.+（"+1 一 a ）0+2 一 *）（/-4）（耳+2-/）*（/ - 一+1 ）<z+3 -（）f <f<t（4+2 £）（'i+2 一 *+】）（'i+2 一 *+】）4+3 £+】）（/一*+3）2（3. 22）4+3 e+1）（*+3 厶+2）0, 其他类似可以递推出三次及更高次的b样条

45、基函数b讥(f) o通过以上递推定义可以看出b样条曲线基函数的特点： b样条曲线基函数的次数与控制点的个数无关； b样条曲线的基函数具有局部支承性，即其只在其支承区间内非零。3. 2. 2 b-样条曲线的分类b样条曲线按照结点向量中的结点分布情况不同，可分为均匀b样条曲线、开放均匀b样条曲 线和非均匀b样条曲线3类。(1)均匀周期性b样条曲线当结点沿参数轴均匀等距分布，即tk+-tk=常数时，表示该b样条曲线为均匀b样条曲线。例如,结点向量可取为 t=(-2,-l. 5,-1,-0. 5, 0, 0. 5,1,1. 5, 2)或 t=(0, 1, 2, 3, 4, 5, 6, 7)等。4 段二

46、次均 匀b样条曲线的基函数如下图所示。0212345图3-11四段三次均匀b样条基函数从上图nj以看出，均匀b样条的基函数呈周期性，即基函数在定义域内各个结点区间上都具有 相同的形状，即(3. 23)bi*(° = bj+y (t + a/) = bgk (/ + 2 ar)因此可将定义在每个结点区间上用整体参数t表示的b样条基函数换成用局部坐标参数表示。 参数变换公式为t = t(u) = + 况 u g 0,1(3. 24)(3. 25)(3. 26)(3. 27)2 i -2 rk=ot2 t 112-220ll0(3. 28)u = u(t) = t-tf,i = k,k +

47、 , ,n这样变换后使得所有区间上的b样条基函数都具有相同的数学表达式。二次均匀b样条曲线的分段表达式为pi a)=b° 2 a) 斥+bx 2(/) £+i+b2 2 a) £+2其中，t为参数，£,£+, e+2为对应的控制顶点，其基函数为bo12(o = |(1-o2b/) = *(l + 2/ 2尸) re 0,11 9f2表示为矩阵形式如下：其中i二0,1, 2,，n,共n-k段分段曲线，式中为分段曲线的特征多边形的顶点，片,£,片+2为 其中连续的3个顶点。二次均匀b样条曲线如下图所示。曲线的起点和终点值为p($加灯)=亍

48、(£ + 片),p(end) =+ pj(3. 29)均匀二次b样条曲线起点和终点处的导数为pstart)=片一代),pend) = pn - pn_x(3. 30)对于由任意数目的控制点构造的二次周期性b样条曲线来说，曲线的起始点位于头两个控制点 之间，终止点位于最后两个控制点之间。对于高次多项式，起点和终点是k-1个控制点的加权平均 值点。若某一控制点出现多次，样条曲线会更加接近该点。分段二次b样条曲线是一条抛物线；ftl n个顶点定义的二次b样条曲线，其实质上是n-2段抛物线(相邻三点定义)的连接，并在接点处 达到一阶连续。 三次均匀b样条曲线分段三次均匀b样条曲线由相邻的4个

49、顶点定义，其表达式为pi()=b°3 ()£+§ 3 (0 + b23 (r) pi+2+尽3 (r) pm(3.31)可见，由n个顶点定义的完整的三次均匀b样条曲线是由n-3段分段曲线连接而成的。很容易 证明，三次云均b样条曲线在连接处达到二次连续。三次均匀b样条曲线的基函数为盼=；(-广 +3/2 -3/ + 1)6目,3 =2 '一 6/2 + 4)<6虫0,1(3.32)5 3(f) = (3尸 + 2尸 + 3/ +1)， 6o将三次均匀b样条曲线表示为矩阵形式为pi垃3址b/)；：_£+3_-13-3r13630f6-3030行

50、21410tmrgb虫0,1(3. 33)4个控制点的三次均匀b样条的边界条件为p(o)=2(p°+4£ + /p,6卩(0)=扣p°),p(l) = g(pi + 4马+ 厶)opy1)=*3(3. 34)三次均匀b样条曲线如下图所示。03可见，三次均匀b样条曲线从靠近片处开始，在靠近鬥处阶数。且每个曲线段的两个端点处的 导数平行于相邻的控制点的连线。(2) 非均匀b样条曲线：在结点向量中使用多重结点虽然均匀b样条曲线可以得到满意的效果，且算法的效率很高，但它仍存在一些不足，如不能 贴切地反映控制顶点的分布特征；当型值点分布不均匀时，难以获得理想的插值曲线等。非

51、均匀b 样条曲线可以克服上述不足，但由于结点的分布不均匀，因此基函数不再具有平移性，基函数各不 相同，因此，在生成曲线时，每个基函数都要单独计算，其计算量比均匀b样条曲线要大得多。(3) 开放b样条曲线：标准结点向量均匀b样条曲线的首末端点不与控制顶点的首末点重合。当均匀b样条的次数高于二次时，在 端点处也不再与控制多边形相切。开放均匀b样条保留了 bezier曲线的端点几何性质，可以更好的 控制曲线的端点。开放均匀b样条与均匀b样条的结点向量的差别在于两端结点。n次开放均匀b样条的结点向 量中两端结点具有重复度为n+1,所有内结点均匀分布。因此除两端的n-l个结点区间外，n次开放 均匀b样条

52、与均匀b样条基函数具有相同的图形。开放均匀b样条曲线是开放b样条曲线的特殊形式，其在计算和处理上比均匀b样条要复杂得 夕0102弐7 o 3. 2. 3 b-样条曲线的性质总结b-样条曲线及其生成曲线的主耍性质很有用。bezier曲线所具备的许多我们期望的性质 b-样条曲线也具备。 局部支柱性b样条的基惭数是一个分段函数，其重耍特征是在参数变化范围内，每个基函数在到g如 的子区间内函数值不为零，在其余区间内均为零，通常也将该特征称为局部支柱性。即k 次b样条曲线在参数的一段至多与k+1个控制点有关，与其他控制点无关，如 图所示。02p" 4图314b样条的局部支柱性 b样条的凸组合性

53、质(3. 35)工恥）三1ib样条的凸组合性和b样条基函数的数值均大于或等于0保证了 b样条曲线的凸包性，即b 样条曲线必处在控制多边形所形成的凸包之内。b样条曲线的凸包区域比同一组控制顶点 定义的bezier曲线的凸包要小，因此b样条曲线可以更加逼近特征多边形。 连续性若一结点向量中结点均不相同，则m次b样条曲线在结点处为m-1阶连续。b样条曲线基函数的次数与控制顶点个数无关。重结点问题：若在连接点的重复度为则k次b样条曲线在结点处为k-r次连续的。 导数曲线rfl b样条曲线的基函数的微分公式b；m =伙一1)血一如3(3. 36)ji+k-ti+k £+1 _可以得出b样条曲线

54、的导数曲线方程，即p"=伙 一bg (t)te th ,tn+1(3. 37)i=l h+k-i sb样条曲线的导数曲线是一条k-1次的b样条曲线。 儿何不变性 波动减小性肠使用多重控制点可以通过在同一个点上防止儿个控制点来改变b样条曲线的形状，同时产生一个多重控制点， 该点对曲线有更强烈的吸引。"“3. 2.4有理样条和nurbs曲线b样条曲线在表示与设计自由型曲线曲面形状时显式了强大的威力，然而在表示与设计由二次 曲而构成的初等曲而时却遇到了困难。b样条曲线包括其特例的bezier曲线都不能精确表示除抛物 线和抛物而z外的二次曲线曲而，而只能给出近似表示。因此有必要将它们表示方法进行推广。有 理形式是b样条曲线很自然的推广。推广后的形式保留了原来形式的许多特点，又将二次曲面、旋 转而等包含在其川。(1) 有理b样条曲线有理b样条曲线是对b样条曲线的推广。称式()所示曲线是以卷为控制多边形，以 q。® ©为权的m次有理b样条曲线，即fwrbjp=早 (3. 38)k=0其小叫是与人对应的权因子，一个特定控制点£的权因子叫越大，曲线越靠近该控制点。首末权 因子，叫0,其余0,使得p(t)的分母不为0。式(3. 38)屮，b"是m次b样条曲 线基函数。由于