第七章 曲線(xiàn)與曲面

1、2022-4-301第七章第七章 曲線(xiàn)與曲面曲線(xiàn)與曲面重重點(diǎn)：點(diǎn)：掌握自由曲線(xiàn)的兩種擬合方式及兩種曲線(xiàn)的生成算法。難難點(diǎn)：點(diǎn)：理解三次參數(shù)樣條曲線(xiàn)（或者拉格朗日曲線(xiàn)）、貝齊爾曲線(xiàn)（或者B樣條曲線(xiàn)）的算法思想。課時(shí)安排：課時(shí)安排：授課4學(xué)時(shí)；上機(jī)4學(xué)時(shí)。2022-4-302第七章第七章 曲線(xiàn)擬合曲線(xiàn)擬合 曲線(xiàn)擬合是利用假想為曲線(xiàn)（或接近它們的）一組離散點(diǎn)，尋找形式比較簡(jiǎn)單、性能良好的曲線(xiàn)的解析式。 曲線(xiàn)擬合有兩種方式：插值方式與逼近方式。這兩種方式的不同點(diǎn)在于插值方式通過(guò)原先給定的離散點(diǎn)，而逼近方式與所給的離散點(diǎn)相當(dāng)“接近”。2022-4-303第七章第七章 曲線(xiàn)擬合曲線(xiàn)擬合2022-4-304

2、7.1 拉格朗日插值曲線(xiàn) 設(shè)多項(xiàng)式曲線(xiàn)通過(guò)k+1個(gè)控制點(diǎn)（x0,y0,z0）,（x1,y1,z1）,（xk,yk,zk）,拉格朗日插值曲線(xiàn)解析式： 其中 稱(chēng)為混合函數(shù)，它可寫(xiě)成： 2022-4-3057.1 拉格朗日插值曲線(xiàn) = 1 j=i 由定義可知： =i j =0ji 由此可見(jiàn)，當(dāng)t=i 時(shí)，函數(shù) 將對(duì)第i個(gè)控制點(diǎn)具有完全控制權(quán)。實(shí)際上，參數(shù)t的具體值不重要，重要的是正確的次序。例如，可設(shè)計(jì)如下的混合函數(shù)：2022-4-3067.1 拉格朗日插值曲線(xiàn) 設(shè)t0=-1，t1=0，t2=1，t3=2，由此可得四個(gè)混合函數(shù)， 2022-4-3077.1 拉格朗日插值曲線(xiàn) 利用這些函數(shù)及四個(gè)樣本點(diǎn)

3、，可產(chǎn)生通過(guò)這四個(gè)樣本點(diǎn)的曲線(xiàn)： 2022-4-3087.1 拉格朗日插值曲線(xiàn) 由四個(gè)控制點(diǎn)得到的曲線(xiàn)是三次多項(xiàng)式，若想用三次多項(xiàng)式來(lái)得到多于四個(gè)控制點(diǎn)的曲線(xiàn)，整條曲線(xiàn)可重復(fù)這一過(guò)程(見(jiàn)圖示)：先取臨近的樣本點(diǎn)（0，1，2，3）并在中間兩點(diǎn)（1，2）作逼近，然后往前推進(jìn)一個(gè)樣本點(diǎn)，即在這一邊取一個(gè)新的樣本點(diǎn)，而在另一邊丟掉一個(gè)樣本點(diǎn)，于是得到（1，2，3，4），然后再逼近曲線(xiàn)（2，3）部分，如此連續(xù)的移動(dòng)樣本點(diǎn)，一直到整條曲線(xiàn)畫(huà)完為止。曲線(xiàn)的開(kāi)始部分及最后部分需做特殊的處理。 2022-4-3097.1 拉格朗日插值曲線(xiàn) 2022-4-30107.2三次參數(shù)樣條曲線(xiàn) 一條三次參數(shù)曲線(xiàn)是把x，y

4、，z分別表示成某個(gè)參數(shù)t的三次多項(xiàng)式。為了不失一般性，可令0t1。因此： 0t1 用矢量形式表示成： p(t)=at3+bt2+ct+d 0t1 (7-2-1)2022-4-30117.2三次參數(shù)樣條曲線(xiàn) 現(xiàn)在的 任務(wù)是對(duì)給定的一組控制點(diǎn)Q0，Q1，,Qn，找出由n段如式(7-2-1)形式的三次曲線(xiàn)并拼接起來(lái)，且通過(guò)這些控制點(diǎn)的一條三次曲線(xiàn)，該曲線(xiàn)上的任一控制點(diǎn)具有二階導(dǎo)數(shù)的連續(xù)性。 求出n組如式（7-2-1）所示方程系數(shù)思路： 1、找出ai、bi、ci、di與Qi-1、Qi、Qi-1、Qi的關(guān)系式；2022-4-30127.2三次參數(shù)樣條曲線(xiàn) 設(shè)Qi-1至Qi之間的三次曲線(xiàn)段為pi(t)，則

5、在Qi-1和Qi處， (7-2-2)2022-4-30137.2三次參數(shù)樣條曲線(xiàn) 由(7-2-1)和(7-2-2)可得到如下關(guān)系： 解上面聯(lián)立方程組得： (7-2-3) 2022-4-30147.2三次參數(shù)樣條曲線(xiàn) 2、由式Pi(1)=Pi+1(0)得出Q1、Q2、Qn-1； 將(7-2-3)中所得系數(shù)ai、bi、ci、di代入(7-2-1)得： 0t1 0t12022-4-30157.2三次參數(shù)樣條曲線(xiàn) 根據(jù)三次樣條曲線(xiàn)在任一點(diǎn)都有直到二階導(dǎo)數(shù)的連續(xù)性可知，在點(diǎn)Qi處的二階導(dǎo)數(shù)是連續(xù)的，故有：Pi(1)=pi+1(0) 其中： 即得： 2022-4-30167.2三次參數(shù)樣條曲線(xiàn) 整理得方程

6、： 方程中，i=1，2，.，n-1。故可得n-1個(gè)這樣的方程，聯(lián)立這些方程，并用矩陣表示可得下式： (7-2-4)2022-4-30177.2三次參數(shù)樣條曲線(xiàn) 方程(7-2-4 )左邊有n+1個(gè)未知量，但只有n-1個(gè)方程，必須再有兩個(gè)約束條件才能確定這個(gè)方程組。通?？芍付▋啥它c(diǎn)Q0和Qn的切線(xiàn)向量Q0和Qn為已知，則式(7-2-4)可重新排列成下面形式： (7-2-5)2022-4-30187.2三次參數(shù)樣條曲線(xiàn) 3、利用追趕法求出Q1、Q2、Qn-1。 追趕計(jì)算公式是： (i=1,2,n-1) (7-2-6) 其中 ： 為式 (7-2-5)等式右邊列矩陣的各系數(shù)，追趕過(guò)程： (i=n-1,2

7、,1) (7-2-7)2022-4-30197.2三次參數(shù)樣條曲線(xiàn) 其中： 求出切線(xiàn)向量 后，分別將它們代入式（7-2-3）以求出各曲線(xiàn)段的三次多項(xiàng)式系數(shù)。 下圖對(duì)給定的n+1個(gè)離散點(diǎn)、繪制出n段三次參數(shù)樣條曲線(xiàn)，并且連接成一條光滑曲線(xiàn)的實(shí)例。 2022-4-30207.3 貝齊爾（Bezier）曲線(xiàn) 和拉格朗日插值曲線(xiàn)以及三次樣條曲線(xiàn)不同的是，貝齊爾曲線(xiàn)和后面介紹的B樣條曲線(xiàn)，它們并不通過(guò)給定的控制點(diǎn)，而只是利用這些控制點(diǎn)的改變來(lái)變化曲線(xiàn)的形狀。 2022-4-30217.3.1 貝齊爾曲線(xiàn)定義 貝齊爾曲線(xiàn)是由給定的n+1個(gè)控制點(diǎn)Qi來(lái)定義，其形式為： 0t1 (7-3-1) 其中Bi,n(

8、t)是一個(gè)混合函數(shù)： Bi,n(t)=C(n,i)ti(1t)n-i (7-3-2) 而C(n,i)是二項(xiàng)式系數(shù)： 2022-4-30227.3.1 貝齊爾曲線(xiàn)定義 混合函數(shù)對(duì)貝齊爾曲線(xiàn)的狀態(tài)起決定性作用，圖（7-3-1）表示對(duì)應(yīng)于具有四個(gè)控制點(diǎn)的貝齊爾曲線(xiàn)的四個(gè)混合函數(shù)。圖（7-3-2）為由四個(gè)控制點(diǎn)定義的貝齊爾曲線(xiàn)。 圖 7-3-12022-4-30237.3.1 貝齊爾曲線(xiàn)定義 圖 7-3-2 2022-4-30247.3.2 貝齊爾曲線(xiàn)幾何作圖法 一般，我們可直接利用貝齊爾曲線(xiàn)的定義實(shí)現(xiàn)曲線(xiàn)的擬合，由于多項(xiàng)式計(jì)算的快慢會(huì)直接影響繪制相應(yīng)曲線(xiàn)的速度，因此，我們也可采用貝齊爾曲線(xiàn)的幾何作圖

9、法，以避免多項(xiàng)式的計(jì)算。下面先將貝齊爾多項(xiàng)式作一些變換： 2022-4-3025 2022-4-30267.3.2 貝齊爾曲線(xiàn)幾何作圖法 若記 由 Pk, Pk+1, Pl作為控制點(diǎn)的貝齊爾多項(xiàng)式，那么上式可寫(xiě)為： (7-3-3)2022-4-30277.3.2 貝齊爾曲線(xiàn)幾何作圖法 由式(7-3-3)可知，要計(jì)算由 0, 1, m這m+1個(gè)點(diǎn)為控制點(diǎn)的貝齊爾多項(xiàng)式在t時(shí)的值，可以先計(jì)算由 0, 1, m-1為控制點(diǎn)的在t時(shí)的值 0,m-1(t)及由 1, 2, m為控制點(diǎn)的在t時(shí)的值 1,m(t)，然后在這兩個(gè)值所代表的點(diǎn)之間連一條直線(xiàn)段。在直線(xiàn)段上取一點(diǎn)，使它和 0,m-1(t)這一點(diǎn)的距

10、離與該直線(xiàn)段長(zhǎng)度之比為t，該點(diǎn)對(duì)應(yīng)的就是 (t)。圖（7-3-3）說(shuō)明了這一過(guò)程，其中t=1/2。2022-4-30287.3.2 貝齊爾曲線(xiàn)幾何作圖法 圖 7-3-3 實(shí)現(xiàn)過(guò)程可見(jiàn)幾何作圖法的算法。2022-4-30297.3.2 貝齊爾曲線(xiàn)幾何作圖法 幾何作圖法的算法 geometry(m,p,pt,dt) /*p存放m+1個(gè)給定控制點(diǎn)的坐標(biāo)，float *p,*pt,dt;pt存放結(jié)果，dt是t的增量*/ int n; int i,j,k,l,n;float *r,*q,t;l=0;for(t=0;t=1;t=t+dt) for(i=0;i0) for(k=0;kn;k+)qk=rk+t

11、*(rk+1-rk);/* q存放中間結(jié)果 */n=n-1;for(j=0;j=n;j+)rj=qj;ptl=r0; /*t處的值*/l=l+1;2022-4-30317.3.3 三次貝齊爾曲線(xiàn) n=3的貝齊爾多項(xiàng)式，是經(jīng)常被使用的。這時(shí)，多項(xiàng)式將由四個(gè)控制點(diǎn)P0、P1、P2和P3的加權(quán)和組成。按式（7-3-1）和（7-3-2），這個(gè)加權(quán)函數(shù)（混合函數(shù)）組是： Bi,n(t)=C(3,i)ti(1-t)3-i 展開(kāi)就是： B0,n(t) = (1-t)3 = - t3+3t2- 3t+1 B1,n(t) = 3t (1-t)2 = 3 t3 -6t2+3t B2,n(t) = 3t2(1-t)

12、 = -3 t3+3t2 B3,n(t) = t32022-4-30327.3.3 三次貝齊爾曲線(xiàn) 寫(xiě)成矩陣形式為： B0,n(t)B1,n(t)B2,n(t)B3,n(t)=t3t2t1MBze 其中矩陣： 如果把由P0、P1、P2、P3四個(gè)控制點(diǎn)構(gòu)成的三次貝齊爾多項(xiàng)式記為P(t)，0t1,那么： P(t) =t3t2t1MBze P0P1P2P3T 其中P0P1P2 P3T是列向量，T表示轉(zhuǎn)置運(yùn)算。2022-4-30337.3.3 三次貝齊爾曲線(xiàn) B0,n(t)、B1,n(t)、B2,n(t)、B3,n(t)這四個(gè)函數(shù)的圖形如圖(7-3-1)。通常稱(chēng)它們?yōu)槿尾魉固购瘮?shù)。 由于貝齊爾多項(xiàng)

13、式對(duì)應(yīng)的曲線(xiàn)是一整段的n次參數(shù)曲線(xiàn)，為了避免高次多項(xiàng)式運(yùn)算，我們可把一段段的低次貝齊爾曲線(xiàn)在一定的連續(xù)性要求下連接起來(lái)，也就是以各一小段貝齊爾曲線(xiàn)拼成樣條曲線(xiàn)。2022-4-30347.3.3 三次貝齊爾曲線(xiàn) 假定以三次貝齊爾曲線(xiàn)為基礎(chǔ)，我們可設(shè)法得到一階連續(xù)性。因?yàn)閚=3時(shí)，貝齊爾曲線(xiàn)在起點(diǎn)和終點(diǎn)的切向量分別為： P(0) = 3(P1-P0) P(1) = 3(P3-P2) 因此，為了使兩個(gè)曲線(xiàn)段在鄰接點(diǎn)有一階連續(xù)性，只要前一段的最后一個(gè)控制點(diǎn)與后一段的第一個(gè)控制點(diǎn)重合，或記為： P3,i-1 = P0,i 同時(shí)還要求：P2,i-1、P3,i-1(即P0,i)與P1,i這三點(diǎn)共線(xiàn)，即： （

14、P3,i-1-P2,i-1）= C(P1,i-P0,i) 其中C是常數(shù)，以保證它們?cè)诠餐c(diǎn)有相同的切向。2022-4-30357.4 B樣條曲線(xiàn) 貝齊爾曲線(xiàn)可通過(guò)調(diào)整控制點(diǎn)的位置來(lái)改變，但調(diào)整一個(gè)控制點(diǎn)會(huì)影響整條曲線(xiàn)，這正是貝齊爾曲線(xiàn)的不足之處。70年代初研究出的B樣條曲線(xiàn)是在貝齊爾曲線(xiàn)的基礎(chǔ)上發(fā)展而來(lái)，且有更多的優(yōu)勢(shì)。 B樣條曲線(xiàn)的優(yōu)勢(shì)： 1、生成的曲線(xiàn)與控制多邊形的外形更接近； 2、具有局部控制的特征； 3、整體上有一定階數(shù)的連續(xù)性。2022-4-30367.4.1 B樣條曲線(xiàn)定義 B樣條的定義為： k-1階的混合函數(shù) 可遞歸地定義如下： 2022-4-30377.4.1 B樣條曲線(xiàn)定義

15、B樣條曲線(xiàn)與貝齊爾曲線(xiàn)的主要區(qū)別在于它們的混合函數(shù) 的不同。其中n為控制點(diǎn)個(gè)數(shù)減1，k為控制曲線(xiàn)連續(xù)性的階數(shù)。下圖是n=5,k=3,4,5的B樣條曲線(xiàn)。 2022-4-30387.4.1 B樣條曲線(xiàn)定義 由定義可知，B樣條曲線(xiàn)主要由控制點(diǎn)位置、參數(shù)k以及所給定的節(jié)點(diǎn)值ti（i=0,1,n）（又稱(chēng)為節(jié)點(diǎn)向量）來(lái)決定。其中節(jié)點(diǎn)向量有三種分類(lèi)，從而產(chǎn)生不同的B樣條曲線(xiàn)：均勻B樣條曲線(xiàn)(uniform)、開(kāi)放均勻B樣條曲線(xiàn)(open uniform) 和非均勻B樣條曲線(xiàn)(nonuniform)。 2022-4-30397.4.2 均勻周期性B樣條曲線(xiàn) 一旦兩節(jié)點(diǎn)值的距離是常數(shù)，所生成的曲線(xiàn)稱(chēng)為均勻B樣

16、條。如我們可以建立均勻節(jié)點(diǎn)向量為： -1.5, -1.0, -0.5, 0.0, 0.5, 1.0, 1.5, 2.0 通常節(jié)點(diǎn)值的標(biāo)準(zhǔn)取值范圍介于0、1之間，如： 0.0, 0.2, 0.4, 0.6, 0.8, 1.0 在很多應(yīng)用中建立起以0為初始值，1為間距的均勻節(jié)點(diǎn)值是比較方便的，其節(jié)點(diǎn)向量為： 0，1，2，3，4，5，6，72022-4-30407.4.2 均勻周期性B樣條曲線(xiàn) 均勻B樣條有周期性混合函數(shù)。即，給定n和k值，所有混合函數(shù)有相同形狀。每個(gè)后繼混合函數(shù)僅僅是前面函數(shù)的一個(gè)移動(dòng)結(jié)果： Ni,k(t)= Ni+1,k(t+t)=Ni+2,k(t+2t)其中，t是相鄰節(jié)點(diǎn)值間的

17、區(qū)間。下圖表示了一個(gè)二次均勻B樣條混合函數(shù)。2022-4-30417.4.2 均勻周期性B樣條曲線(xiàn) n=k=3的周期B樣條混合函數(shù) 2022-4-30427.4.3 開(kāi)放均勻B樣條曲線(xiàn) 開(kāi)放均勻B樣條曲線(xiàn)，簡(jiǎn)稱(chēng)開(kāi)放B樣條曲線(xiàn)，除在兩端的節(jié)點(diǎn)值重復(fù)k次外，其節(jié)點(diǎn)間距是均勻的。 下面是兩個(gè)開(kāi)放均勻、從0開(kāi)始的整型節(jié)點(diǎn)向量的例子： 0，0，1，2，3，3，當(dāng)k=2, n=3 0，0，0，0，1，2，2，2，2，當(dāng)k=4, n=4。 我們將節(jié)點(diǎn)向量規(guī)范到從0到1的區(qū)間： 0，0，0，0，0.5，1，1，1，1，當(dāng)k=4, n=4。2022-4-30437.4.3 開(kāi)放均勻B樣條曲線(xiàn) 對(duì)任意的參數(shù)值k和

18、n，通過(guò)下列計(jì)算，可以生成開(kāi)放均勻具有整型節(jié)點(diǎn)的向量： j的值從0到n+k，頭k個(gè)節(jié)向量值設(shè)為0，后k個(gè)值為n-k+2。2022-4-30447.4.3 開(kāi)放均勻B樣條曲線(xiàn) 開(kāi)放均勻B樣條具有與貝齊爾樣條非常類(lèi)似的特性。開(kāi)放B樣條多項(xiàng)式曲線(xiàn)通過(guò)第一和最后一個(gè)控制點(diǎn)。參數(shù)曲線(xiàn)在第一個(gè)控制點(diǎn)處的斜率也平行于頭兩個(gè)控制點(diǎn)的連線(xiàn)，最后一個(gè)控制點(diǎn)處的斜率平行于最后二個(gè)控制點(diǎn)的連線(xiàn)。因此，連接曲線(xiàn)段的幾何約束也與貝齊爾曲線(xiàn)相同。2022-4-30457.4.4 非均勻B樣條曲線(xiàn) 對(duì)非均勻B樣條，可以選多個(gè)內(nèi)節(jié)點(diǎn)值并且在節(jié)點(diǎn)值之間選不等的間距。例如： 0，1，2，3，3，4 0，2，2，3，3，6 0，0，0，1，1，3，3，3 0，0.2，0.6，0.9，1.0非均勻B樣條曲線(xiàn)在控制曲線(xiàn)形狀方面提供了更多的便利。通過(guò)節(jié)點(diǎn)向量取不同的間距，