第八章曲线、曲面生成与逼近 教学目的和要求 要求掌握筒单的数据处理方法、累加弦长法、 Bezier方法、B样条方法 非均匀有理B样条( NURBS) 本章讲述曲线、曲面生成与逼近的一些常用方法原则上讲,本书前面有关 章节介绍的插值与逼近的理论与方法均有用于曲面、曲线的生成与逼近这些内 容本章自然不必重复以下介绍一些其他方法以及与之相关的理论本章所涉及 的领域被称之为计算机几何或计算机辅助几何设计 1.简单的数据处理方法 通常给定的用以生成与逼近曲线、曲面的表列数据,由于观测等各类因素的 影响,蕴含一定的误差,所以人们常常需要对这些给定的数据进行适当的处理 采用样条和最小二乘法技巧,可以较好的处理这些数据本节将介绍比较简 单、使用的处理数据方法 设 l1,l2…,lln u1=l() 是一组观测数据,它们是当自变量取为等距时由观测所得的数据从上列数据的 插分表的不规则性可知它们不能用多项式等来逼近,所以人们需设法对以上数据 进行修改,使修正后的数据 ul 符合我们的要求 Woodhouse公式
第八章 曲线﹑曲面生成与逼近 教学目的和要求: 要求掌握简单的数据处理方法﹑ 累加弦长法﹑ Bézier 方法 ﹑ B-样条方法 ﹑非均匀有理 B-样条（NURBS） 本章讲述曲线﹑曲面生成与逼近的一些常用方法.原则上讲，本书前面有关 章节介绍的插值与逼近的理论与方法均有用于曲面﹑曲线的生成与逼近.这些内 容本章自然不必重复. 以下介绍一些其他方法以及与之相关的理论.本章所涉及 的领域被称之为计算机几何或计算机辅助几何设计. §1. 简单的数据处理方法 通常给定的用以生成与逼近曲线﹑曲面的表列数据，由于观测等各类因素的 影响，蕴含一定的误差，所以人们常常需要对这些给定的数据进行适当的处理. 采用样条和最小二乘法技巧，可以较好的处理这些数据.本节将介绍比较简 单﹑使用的处理数据方法. 设 u u u (u u(i)) 1 , 2 , , n , i = 是一组观测数据，它们是当自变量取为等距时由观测所得的数据.从上列数据的 插分表的不规则性可知它们不能用多项式等来逼近，所以人们需设法对以上数据 进行修改，使修正后的数据 u1 ,u2 , ,un , 符合我们的要求. 1． Woothouse 公式
该方法的基本思想是,为修正u0处的值,须取 l-,u-6;…,ll-1,lo,l1,…,l6,l 分别由u2,2,n3)(u,u1,u)(us,un,u5)(u4,u1,46)和(u3,u2,u2)作5条2 次多项式插值,并取这5条抛物线于x=0处值的算术平均值作为u0=(0)的修正 值即 3u1+7ln-3i 125 (-3+72-3) 125 其中表示所谓的“离中和” 2m+1J 且 G]o]u Lidstone公式 从 Woodhouse公式,可总结出一个普遍原则 △.=ul 需寻求一个恰当的磨光公式,使得 f、p}2=l2+高阶差分, 其中是离中和则磨光值取为 △pp 关键是选取函数f 根据差分算子和位移算子等的定义
该方法的基本思想是，为修正 0 u 处的值，须取 , , , , , , , , . u−7 u−6 u−1 u0 u1 u6 u7 分别由 ( ) ( ) ( ) ( ) 7 2 3 6 1 4 5 0 5 4 1 6 u− ,u− ,u , u− ,u− ,u , u− ,u ,u , u− ,u ,u 和 ( ) 3 2 7 u− ,u ,u 作 5 条 2 次多项式插值，并取这 5 条抛物线于 x=0 处值的算术平均值作为 (0) u0 = u 的修正 值.即 ( 3 7 3 ), 125 1 0 1 3 0 [5] u = − u− + u − u ( 3 7 3 ), 125 [5] 1 1 3 = − − + − + ux ux ux ux （1.1） 其中 • 表示所谓的“离中和”： 2 1 , m + ux = ux−m ++ ux ++ ux+m （1.2） 且 [ ] ([ ] ). 1 u u k k • = • • + 2． Lidstone 公式 从 Woothouse 公式，可总结出一个普遍原则. 记 . ux = ux+1 − ux 需寻求一个恰当的磨光公式，使得 f ,•ux = ux + 高阶差分， 其中 • 是离中和 • 则磨光值取为 , . x ux u = f • 关键是选取函数 f ,•. 根据差分算子和位移算子等的定义
E=1+A 其中E为位移算子,D为微分(求导)算子取φ=D,则得 =E-2+E=-4snφ 2m+ +2cos2p+…+2cos2mp} +1) snφ 所以 小2-1)-n+72-)G2-=3) 即可得 n 由此可推出 P1·P2·P3 24 移项得 Lid stone公式 P1·P2:P 若取P1=P2=5,P3=7,则得到 Spencer公式 557 46 175 其21项公式为
, 2 , 1 , 0 1 0 1 2 0 1 2 1 2 D u = u −u u = u − u + u E = + = e − − 其中 E 为位移算子，D 为微分（求导）算子.取 , 2 1 D i = 则得 2 1 2 = − 2 + = −4sin − E E ， 2m +1u0 = u−m ++ u−1 + u0 + u1 ++ u 0 2 2 2 2 e e 1 e e u mi i i mi = + + + + + + − − 2 0 = 1+ 2cos 2 ++ 2cos m u ( ) 0 sin sin 2 1 u m + = 。 所以 0 0 sin sin u n n u = ( ) ( )( ) 0 4 2 2 2 2 2 2 2 sin 5! 1 3 sin 3! 1 u n n n n n n + − − + − = − 。 即可得 ( ) + − + − = − 0 4 4 2 2 0 2 2 2 2 0 0 2 5! 1 2 3! 1 ! u n u n u u n n 由此可推出 ( ) ( ). 24 1 0 4 0 2 2 0 0 1 2 3 1 2 3 u O u p u u p p p p p p i i + − = + 移项得 Lidstone 公式 ( ) 0. 2 2 1 2 3 1 2 3 0 1 24 1 p u p p p p p p u i i − − = (1.3) 若取 5, 7, p1 = p2 = p3 = 则得到 Spencer 公式 0 2 0 1 4 175 5 5 7 u = − u 。 (1.4) 其 21 项公式为
60u+57u1+u1)+47u2+u2)+…-(u10+u40)}(1.5) 3.最小二乘法 取以u0为中心位置的数据 并按最小二乘法求j次多项式u(x),则取 经常采用的是下述特例 (1)取j=1,则 )+…+(un+un)} (1.6) (2)取j2,3 lo=Pnln+_Pn-1ln-1+……+P2-nln (1.7) 其中 P,=3 2n-1)(2n+1)(2n+3) ,1, 4.二维数据的处理 借助于二维 Taylor展开公式,我们可以处理二维矩形网格点上的数据 设已给定一组二维数据 (h,j)i,j=0±1 则有如下的13点磨光公式 +2∑+∑2∑3 其中 =l10+l0n+l-1.0+l
60 57( ) 47( ) ( ). 360 1 u0 = u0 + u 1 + u1 + u 2 + u2 + − u 1 0 + u1 0 − − − (1.5) 3. 最小二乘法 取以 0 u 为中心位置的数据 , , , , , , , u−n u−n+1 u0 un−1 un 并按最小二乘法求 j 次多项式 u(x) ，则取 ( ) 0 =0 = x u u x . 经常采用的是下述特例. （1） 取 j=1，则 ( ) ( ). 2 1 1 0 u0 u1 u 1 un u n n u + + − + + + − + = (1.6) （2） 取 j=2,3 _ , u0 = pnun + pn−1un−1 + + p−nu−n (1.7) 其中 ( )( )( ) , , ,1, , . 2 1 2 1 2 3 3 3 1 5 3 2 2 s n n n n n n n s ps = − − + + + − − = 4．二维数据的处理 借助于二维 Taylor 展开公式，我们可以处理二维矩形网格点上的数据. 设已给定一组二维数据 ( , ), , 0, 1, . ui, j = u ih jh i j = 则有如下的 13 点磨光公式： 3 2 , 11 1 0,0 = 0,0 + 1 + 2 − 3 u u 其中 , 1 = u1,0 + u0,1 + u−1,0 + u0,−1
u, +u+u +l1-1 l+lo+u 若uo是一个边界点,例如在数据(1.8)中,我们只知 ’,=012 则有如下的9点边界磨光公式 8 其中 lo tlo, +ul l1:+l1-17 =u+la+u 为验证公式(19)和(1.10),只需将公式右端所涉及的诸l1,在0点作 Taylor展开 即可有关细节请读者自行给出。 §2.累加弦长法 如前所述,3次样条插值是一类比较简单而有效的曲线生成和逼近的方法 由于3此样条的力学背景是无限常量在集中荷载作用下的弯曲变形曲线其中 个条件是小挠度,即y1不大。然而实际问题中经常会遇到大挠度曲线的逼近间 题为解决此类问题,人们想出来许多种办法,其中一类最有效的方法是将曲线 参数化例如分段研究3次参数曲线 x=do +at+=a2I Bo +B,t+ 2B+6B 首先遇到的问题时,以什么作为(2.1)中的参数?一个最容易想到的参数是曲线的
, 2 = u1,1 + u−1,1 + u−1,−1 + u1,−1 . 3 = u2,0 + u0,2 + u−2,0 + u0,−2 若 0,0 u 是一个边界点，例如在数据(1.8)中，我们只知 , 0,1,2, , ui , j i = 则有如下的 9 点边界磨光公式： 3 2 , 8 1 0,0 0,0 1 2 3 − + u = u + 其中 1 = 1,0 + 0,1 + 0,−1 u u u ， , 2 = 1,1 + 1,−1 u u . 3 = 2,0 + 0,2 + 0,−2 u u u 为验证公式(1.9)和(1.10)，只需将公式右端所涉及的诸 i j u , 在 0,0 u 点作 Taylor 展开 即可.有关细节请读者自行给出。 §2. 累加弦长法 如前所述，3 次样条插值是一类比较简单而有效的曲线生成和逼近的方法。 由于 3 此样条的力学背景是无限常量在集中荷载作用下的弯曲变形曲线.其中一 个条件是小挠度，即 y 不大。然而实际问题中经常会遇到大挠度曲线的逼近问 题.为解决此类问题，人们想出来许多种办法，其中一类最有效的方法是将曲线 参数化.例如分段研究 3 次参数曲线 = + + + = + + + , 6 1 2 1 , 6 1 2 1 3 3 2 0 1 2 3 3 2 0 1 2 y t t t x t t t (2.1) 首先遇到的问题时，以什么作为(2.1)中的参数？一个最容易想到的参数是曲线的
长度s,遗憾的是,曲线(21)的弧长s不能作为它的参数事实上,假如取t=s, 则由 dx 可知 0 dtdtdt dt 亦即 (a3+B+3 2a3+B2B3 +(a2+B2+a1a3+B1B1+(a1a2+BB2)=0 所以 B2 B3=0 它表明曲线(21)已退化为直线。因此用弧长作为参数时,曲线(21)只能表示直线 所以必须另寻其它参数本节讲述用弧长作为参数的所谓累加弦长法,其大意是 设给定直角坐标系中的n+1个点 P=(x2y)i=0,1…n 记 yin (22) 2,…,n1,o=0 则形成了一个参数轴t的一个剖分△:0=10<1<…<n 对于这样的剖分△,分别以x和y1(=0,1…,n)为数据,构造两个3次插值 样条x()和y()而参数曲线
长度 s，遗憾的是，曲线(2.1)的弧长 s 不能作为它的参数.事实上，假如取 t=s， 则由 1 2 2 + dt dy dt dx 可知 0. 2 2 2 + dt d y dt dy dt d x dt dx 亦即 ( ) ( ) ( ) ( ) 0 2 3 2 1 1 3 1 3 1 2 1 2 2 2 2 2 2 2 3 2 3 2 3 3 2 3 + + + + + + + + + t t t 所以 0. 2 = 2 =3 = 3 = 它表明曲线(2.1)已退化为直线。因此用弧长作为参数时，曲线(2.1)只能表示直线. 所以必须另寻其它参数.本节讲述用弧长作为参数的所谓累加弦长法，其大意是： 设给定直角坐标系中的 n+1 个点 P (x , y ), i 0,1, ,n. i = i i = 记 ( ) ( ) , 1, , , 1 2 2 1 2 l j = x j − x j−1 + y j − y j− j = n (2.2) , 1,2, , , 0. 0 1 = = = = t l i n t i j i j 则形成了一个参数轴 t 的一个剖分 : 0 . 0 1 n = t t t 对于这样的剖分 ，分别以 i x 和 y (i n) i = 0,1, , 为数据，构造两个 3 次插值 样条 x(t) 和 y(t).而参数曲线
P()=(x()y() 称为是累加弦长3次参数样条曲线。该曲线在诸结点处的每个分量均达到C2 连续,即切线和曲率皆连续注意,当人们采用参数t时,按上述参数t的取法可 知,x(t)与yt)对于t的导数值均不大,即符合小挠度的要求利用通常3次样条 插值的算法可以分别求得x(t)和y(t) 若将累加弦长3此样条曲线方程写成向量形式,例如记P1与P间的参数曲 线为 P()=R132+R12+R1+R,t1≤t≤t1 (23) 其中弦长1=PP参数轴上结点的坐标1=∑1,=1…n而 P()=P2P(,)=P 要求在P处保证1阶和2阶向量连续,即要求 (-0)=P(1+0)=m, Pv(2-0)=P℃(2+0)=M1 其中m2与M为待求向量类似于普通3此样条插值的计算方法,在P处的光滑连 接性可推出关系式 lM1=-2(3e1-m--2m) l1M1=-2(3e1-2n 从而得到如下连续性方程 Am21+2m+m1=3(e+He1 i=1,…,n-1 (25) 其中
P(t) = (x(t), y(t)) 称为是累加弦长 3 次参数样条曲线。该曲线在诸结点处的每个分量均达到 2 C 连续，即切线和曲率皆连续.注意，当人们采用参数 t 时，按上述参数 t 的取法可 知，x(t)与 y(t)对于 t 的导数值均不大，即符合小挠度的要求.利用通常 3 次样条 插值的算法可以分别求得 x(t)和 y(t). 若将累加弦长 3 此样条曲线方程写成向量形式，例如记 Pi−1 与 Pi 间的参数曲 线为 ( ) ( ) ( ) ( ) ( ) , , 1 0 1 2 2 3 3 i i i i i i i P t = R t + R t + R t + R t t t − (2.3) 其中弦长 i Pi Pi l = −1 参数轴上结点的坐标 = = = i j t i l i i n 1 , 1,, , 而 ( ) , ( ) . i i 1 i 1 i i Pi P t − = P− P t = 要求在 Pi 处保证 1 阶和 2 阶向量连续，即要求 ( ) ( ) ( 0) ( 0) , 0 0 , i i i i i i P t P t M P t P t m − = + − = + (2.4) 其中 mi 与 Mi 为待求向量.类似于普通 3 此样条插值的计算方法，在 Pi 处的光滑连 接性可推出关系式 2(3 2 ), i i i mi 1 mi l M = − e − − − 2(3 2 ). i+1 i = − i+1 − mi − mi+1 l M e 从而得到如下连续性方程 ( ) 1, , 1. 2 3 , 1 1 1 = − − + + + = + + i n m m m e e i i i i i i i i i (2.5) 其中
1+D, ,e1=;P=P 也可得到关于M的连续性方程 HM1+2M1+1Mn1=6(e1-e)/(2+l1) (25)或(26中分别加上端点的两个条件后,即可求得诸M和m 在求出诸M和m后,介于与间的参数曲线方程为 P0)=-,0--)(-)1291- 其中 P-I P (28) m 0 0 3/123/2-2/1-1 29) 2/13-2/3121 l/11/1-1/3-16 B 1/611/6 而P表示P(x,y)的位置向量(=0,…,n) 从累加弦长3次参数曲线的表达式(27)(2.8)、(2,9)和(210)中不难发现,它们 仅仅依赖于诸型值点P的位置和弦长l这样一批几何量,而与坐标系的选择无
i i i i i i i i i i i i P P l e l l l l l l 1 1 1 1 1 , , − + + + = + = + = . 也可得到关于 M 的连续性方程 ( ) ( ) 1, , 1 2 6 , 1 1 1 1 = − − + + + = + − + + i n M M M e e l l i i i i i i i i i (2.6) (2.5)或(2.6)中分别加上端点的两个条件后，即可求得诸 M 和 m。 在求出诸 M 和 m 后，介于 与 间的参数曲线方程为 ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1, , , 1, , , , , 1 3 2 1 0 3 1 2 1 1 i n P t t t t t t t t t t i i i i i i i i i i = = − − − − − − − (2.7) 其中 ( ) ( ) , (2.10) 0 0 1 6 1 6 0 0 1 2 0 1 1 3 6 1 0 0 0 , (2.9) 2 2 1 1 3 3 2 1 0 0 1 0 1 0 0 0 , (2.8) 3 3 2 2 2 2 1 1 1 1 ( ) 3 2 ( ) 1 0 − − − − = − − − − = = = − − − − i i i i i i i i i i i i i i i i i i i i i i i i i i i i l l l l l l B l l l l l l l l A M M P P B m m P P A 而 Pi 表示 ( ) i i i P x , y 的位置向量 (i = 0, , n). 从累加弦长 3 次参数曲线的表达式(2.7),(2.8),(2,9)和(2.10)中不难发现，它们 仅仅依赖于诸型值点 Pi 的位置和弦长 i l 这样一批几何量，而与坐标系的选择无
有关累加弦长3次参数曲线的进一步讨论此处不拟展开。 类似于本节中的讨论,请读者建立累加弦长2次参数曲线的插值算法(留 做习题)。 §3B6zier方法 n次 Bezier曲线定义为 Cu)=∑Bn()P,0≤u≤1 (3.1) 其中基函数组{Bn(叫)为n次 Bernstein多项式的基函数组 B.(u) (3.2) 而(31)中的几何系数{}称为控制点。注意在(31)中,u∈p 从 bezier曲线定义(31)可知,由它表示的曲线的形状只与{P}。(控制多 边形)的位置有关,而与坐标系的选取无关,即它具有几何不变性这是一条很 重要的性质 例1.当n=1时, Bezier曲线为 Cu=(1-u)Po+uP 它表明1次 Bezier曲线恰为以P和P为两端的直线段 例2.当n=2时, Bezier曲线为 Cu)=(1-a)2P+2(-a)P+u2P 他是一条从P到P2的抛物线(图31)
关。 有关累加弦长 3 次参数曲线的进一步讨论此处不拟展开。 类似于本节中的讨论，请读者建立累加弦长 2 次参数曲线的插值算法（留 做习题）。 §3.Bézier 方法 n 次 Bézier 曲线定义为 ( ) ( ) , 0 1. 0 = , = C u B u Pi u n i i n (3.1) 其中基函数组 Bi,n (u) 为 n 次 Bernstein 多项式的基函数组 ( ) ( ) i n i i n u u i n B u − − , = 1 . (3.2) 而(3.1)中的几何系数 Pi 称为控制点。注意在(3.1)中， u 0,1. 从 Bézier 曲线定义(3.1)可知，由它表示的曲线的形状只与 n Pi i=0 （控制多 边形）的位置有关，而与坐标系的选取无关，即它具有几何不变性.这是一条很 重要的性质. 例1． 当 n=1 时，Bézier 曲线为 ( ) ( ) C u = 1− u P0 + uP1 . 它表明 1 次 Bézier 曲线恰为以 P0 和 P1 为两端的一直线段. 例2． 当 n=2 时，Bézier 曲线为 ( ) ( ) ( ) 2 2 0 1 2 C u = 1−u P + 2u 1−u P + u P . 他是一条从 P0 到 P2 的抛物线(图 3.1)
P2=C(1) 图3.1 图 由{,P,P2组成的多边形称为控制多边形P=C(0),P2=C(1.该曲线的端点 处的切向量分别平行于P-P和P-P不难看出这条曲线含于三角形PPP2中 例3.当n=3时, bezier曲线为图32,图3.3,图34) ()=(1-a)P+3(1-)P+3n2(-a)P2+3P 图3.3
由 P0 ,P1 ,P2 组成的多边形称为控制多边形. (0) P0 = C ， (1) P2 = C . 该曲线的端点 处的切向量分别平行于 P1 − P0 和 P2 − P1 .不难看出这条曲线含于三角形 P0P1P2 中. 例3． 当 n=3 时，Bézier 曲线为(图 3.2,图 3.3，图 3.4) ( ) ( ) ( ) ( ) 3 3 2 2 1 2 0 3 C u = 1−u P + 3u 1−u P + 3u 1−u P + u P