图形学_04_曲线生成之2.ppt

1、第四讲 曲线的生成算法（之二）,一、自由曲线的生成的两种方法 （1）插值的方法：曲线过型值点，多项式插值、分段多项式插值和样条函数插值等。 （2）拟合的方法：曲线靠近型值点，最小二乘法、贝塞尔方法和B样条方法等。 主要介绍：三次样条插值曲线、贝塞尔曲线、B样条曲线和最小二乘法曲线拟合等。,本节研究平面自由曲线的表示、生成。 平面自由曲线不能用一个标准代数方程精确表示。实际中应用很多，如：轮船船身放样。 将放样过程抽象为：平面上给定若干点（型值点），找一个代数方程，逼近或插值上述型值点。 理论上，n个点，可以找到一个n-1次多项式来逼近，但n太大时，多项式次数太高，计算复杂，难以控制。 工程上，

2、降低次数，且分段定义。,二、三次样条曲线生成算法,力学上已证明，在小绕度|y|1时，两压铁之间的木条近似于三次多项式曲线。 每一段为三次多项式，整体为三次样条。 设平面上有n个型值点，Vi(xi ,yi) i=1,2,n-1,n, 且 x1x2xn-1Xn-1Xn ,又:Si(x)为 Xi,Xi+1区间的三次多项式，记 Si(xi)=yi, Si(xi+1)=yi+1, 求 Si(x) 。 设Si(x)= ai + mi(x-xi)+ci(x-xi)2+di(x-xi)3 x xi,xi+1 i=1,2,n-1,其中，ai,mi,ci,di为待定系数(分四步走-)： 由样条曲线，须满足： Si

3、(xi+1)=Si+1(xi+1) Si(xi+1)=Si+1(xi+1) 由已知： Si(xi)=yi, Si(xi+1)=yi+1 ai=yi ai+mi(xi+1-xi)+ci(xi+1-xi)2+di(xi+1-xi)3=yi+1 记 hi=xi+1-xi 上式转化为：ai+mihi+cihi2+dihi3=yi+1 又记 Si(xi)= yi 所以 Si(x)= mi+2ci(xi-x)+3di(x-xi)2 yi=mi yi+1=mi+2cihi+3dihi2,三次样条曲线生成算法,得方程组： ai=yi （1） ai+mihi+cihi2+dihi3=yi+1 （2） mi=yi

4、 （3） mi+2cihi+3dihi2=yi+1 （4） 先将 yi，yi+1视为已知，求解后得： ai=yi mi=yi ci=,三次样条曲线生成算法,di= 直接用mi,mi+1 表示yi，yi+1，则： ci= di= 若求出mi,mi+1，则ci, di, ai 即求得,三次样条曲线生成算法, 为了求mi，利用Si(xi+1)=Si+1(xi+1)或Si-1(xi)=Si(xi) 又： Si(x)=2ci+6di(x-xi) Si-1(x)=2ci-1+6di-1(x-xi-1) Si(xi)=2ci Si-1(xi)=2ci-1+6di-1hi-1 2ci-1+6di-1hi-1=

5、2ci 将ci-1,di-1,ci 分别用mi-1 ,mi, mi+1 表示： himi-1+2(hi-1+hi)mi+hi-1mi+1=,三次样条曲线生成算法,令 代入上式 即：,三次样条曲线生成算法,此方程称为“三转角”或小m连续性方程: n-2个方程,n个未知数，如需唯一解，需增加两个条件，加连界条件 （1）限定两端切线方向，即已知m1=R1,mn=Rn称为夹持端。 （2）认定第1段和最后一段为抛物线称抛物端，此时，第一段和最后一段二阶导数为常数。 S1(x1)=S1(x2) S1(x)=2c1+6d1(x-x1) 2c1=2c1+6d1h1 d1=0,三次样条曲线生成算法,三次样条曲线

6、生成算法,对于（1）、（2）、（3）可以统一表示： 2m1+u1m2=R1 n.mn-1+2mn=Rn 对于（1）：令1=0, n =0，R1=2k1,Rn=2k2 对于（2）：令1=2, n =2, R1= , Rn= 对于（3）： 令1=1, n =1, R1= , Rn=,三次样条曲线生成算法,将这二个方程与前面n-2个方程联立求解 2 1 m1 R1 2 2 2 m2 R2 3 2 3 m R3 。 。 。 . = . 。 。 . . n-1 2 n-1 mn-1 Rn-1 n 2 mn R n 所以 + =12 主对角线元素严格占优势，,三次样条曲线生成算法,可用“追赶法”解： 令

7、Vi= i=2,3,n-1 V1= Wi= i=2,3,n W1= 则 mn=Wn mi=-Vimi+1+Wi (i=n-1,n-2,1) 至此，所有mi求出，则ci,di 即求得。 现计算曲线上任一点X*,判断X* 即用Si(x*) 求得，将所有相邻的点用线段连接即可。如先用二阶导数Mi 表示ci,di ，则可得Mi连续性方程，自行推导,三次样条曲线生成算法,以上推导的条件为 |y|1 则与实际曲线相差很大, 解决办法：向量参数法，型值点（向量表示），两点之间的距离（弦长）为参变量三次参数样条曲线 设已知点用向量Ai 表示，（i=1,2,n-1,n),Pi(t)为第i段三次参数方程 Pi(t

8、)=V0+V1t+V2t2+V3t3 0 t Li Li=|Ai+1i|,现在求i(i=0,1,2,3) 先假定i,Ai+1 已知，则有i(0)=Ai , Pi(Li)=Ai+1,Pi(0)= Ai Pi(Li)=Ai+1 得 V0=A1 V0+V1Li+V22Li2+V3Li3=Ai+1 V1=Ai V1+2V2L1+3V3Li2=Ai+1 其解法与三次样条曲线求解类似。,三、 Bezier曲线生成算法,分析：三次样条曲线：插值 实际中，型值点本身并不精确，不必插值 主要要求：良好的几何性质，光滑，美观，实时修 改方便 画家思想：先画轮廓，后逐渐逼近 引入：Bezier：法国雷诺汽车公司工程

9、师，折线 曲线 优 点：外型设计，交互式，应用广泛 参数曲线生成的数学基础知识：（见WORD文档描述） 1. 定 义 已知n+1个型值点，用向量Vi（i=0，1，.，n） 表示,称: P(t)= t 0,1 为n次Bezier曲线（Vi构成曲线的特征多边形） 其中： Bi,n (t)=Cni ti(1-t)n-i= ti(1-t)n-i (i=0,1,n-1,n) 称为Bernstein基函数； Bezier特征多边形：用线段连接相邻的Vi。 例：n=3，有4个特征点 P(t)= 分量形式：x(t)= y(t)=,Bezier曲线生成算法,如图所示。 又: B0,3(t)=C30 t0(1-t

10、)3=(1-t)3 B1,3(t)=C31 t(1-t)2=3t(1-t)2 B2,3(t)=C32 t2(1-t)=3t2(1-t) B3,3(t)=C33 t3(1-t)0=t3,Bezier曲线生成算法,2 Bezier曲线的几何性质 端点性质（端点的位置矢量、切矢量、曲率） B0,n(0)=Bn,n(1)=1 Bi,n(0)=0 (i 0) Bi,n(1)=0 (i n) P(0)= =V0 P(1)= =V n 表明：P(t)以V 0为起点，Vn为终点 由Bi,n(t)=nBi-1,n-1(t)-Bi,n-1(t) 记P(t)=n,Bezier曲线生成算法,记 ：i-1,n-1(t)

11、=0,Bn,n-1(t)=0 P(t)=n =n P(0)=n(V1-V0) P(1)=n(Vn-Vn-1) 表明： 起点切向量仅与有关，为n(V1-V0) 终点切向量仅与有关，为n(Vn-Vn-1),Bezier曲线生成算法,P(t)=n =n(n-1) =n(n-1) =n(n-1) =n(n-1),P(0)=n(n1)(V2-2V1+V0) P(1)=n(n1)(Vn-2Vn-1+Vn-2) 表明：起点二阶导数仅与 V2,V1,V0有关 终点二介导数仅与Vn,Vn-1,Vn-2有关 一般地：P(t)在起点处的m阶导数仅与离起点最近的 m+1个向量V0,V1,Vm有关 P(t)在终点处的m

12、阶导数仅与离终点最近的 m+1个向量Vn-m,Vn-m+1,Vn有关,(2) 凸包性 由 Bi,n(t)0, 知： P(t)为Bi,n(t)对Vi加权平均，故得证 ： min(Vi)i=0n P(t) maxVii=0n (3) 几何不变性 由其定义知，仅与向量有关，与具体坐标无关 （注：p(t)可作为各点vi处重量为Bi,n(t)的力学系统的重心）,3矩阵表示法（考虑n=1,2,3） (1) n=1,（2）n=2,(3) n=3,一般地，n次Bezier样条曲线可表示为： 其中T(n+1)*(n+1)的第i 列为Bi,n(t)按降幂排列的系数,4三次Bezier样条曲线示例 n=3为应用最广

13、泛的，但只有四个点，P0,P1,P2,P3，称为特征顶点。 Bezier曲线的手工作图（几何作图法） 在特征多边形的各边取相同比例的分割点，依次连接后，继续取分割点，直至不可再分割为止。（举例说明：清华教材图6.2.5） Bezier曲线的计算（计算各点坐标作图）,P163第7小题答案：,P163第7小题答案图示：,5Bezier样条曲线的光滑连接 对于形状复杂的曲线（高次Bezier曲线），可以考虑用分段三次Bezier曲线来解决， 只是：用若干段三次Bezier曲线相连，需要保证光滑连接，即C0 、 C1 、 C2连续。考虑两段相邻的三次Bezier曲线： n次P(t): P0, P1, P2, P