B樣條曲線與曲面

會(huì)計(jì)學(xué)1B樣條曲線與曲面樣條的史話(1)1946年的紅皮書

Schoenberg拉開了神話的序幕

從插值的R-K現(xiàn)象說起

樣條－分段連續(xù)多項(xiàng)式第1頁(yè)/共70頁(yè)樣條的史話(2)斷言樣條不可能用于外形設(shè)計(jì)幾何樣條出現(xiàn)，離散計(jì)算，峰回路轉(zhuǎn)

Riesenfield,Gordan,...第2頁(yè)/共70頁(yè)如何理解B-樣條？樣條插值，三對(duì)角方程(函數(shù)、參數(shù))給定分劃，所有的B樣條的全體組成一個(gè)線性空間，線性空間有基函數(shù)，這就是B樣條基函數(shù)由B樣條基函數(shù)代替Bezier曲線中的Bernstein基函數(shù)，即B樣條曲線。第3頁(yè)/共70頁(yè)3.3.1B樣條的遞推定義和性質(zhì)B樣條曲線的方程定義為：

是控制多邊形的頂點(diǎn)

(i=0,1,..,n)稱為k階（k-1次)B樣條基函數(shù)

B樣條基函數(shù)是一個(gè)稱為節(jié)點(diǎn)矢量的非遞減的參數(shù)t的序列所決定的k階分段多項(xiàng)式，也即為k階（k-1次)多項(xiàng)式樣條。第4頁(yè)/共70頁(yè)

deBoor-Cox遞推定義并約定

幾個(gè)問題第5頁(yè)/共70頁(yè)幾個(gè)問題的非零區(qū)間是什么？需要多少個(gè)節(jié)點(diǎn)？定義區(qū)間是什么？第6頁(yè)/共70頁(yè)以k＝4，n=4為例第7頁(yè)/共70頁(yè) 2．性質(zhì)局部支承性。權(quán)性。微分公式。第8頁(yè)/共70頁(yè)B樣條曲線類型的劃分曲線按其首末端點(diǎn)是否重合，區(qū)分為閉曲線和開曲線。B樣條曲線按其節(jié)點(diǎn)矢量中節(jié)點(diǎn)的分布情況，可劃分為四種類型。第9頁(yè)/共70頁(yè)均勻B樣條曲線。

節(jié)點(diǎn)矢量中節(jié)點(diǎn)為沿參數(shù)軸均勻或等距分布，所有節(jié)點(diǎn)區(qū)間長(zhǎng)度為常數(shù)。這樣的節(jié)點(diǎn)矢量定義了均勻的B樣條基。第10頁(yè)/共70頁(yè)準(zhǔn)均勻B樣條與均勻B樣條曲線的差別在于兩端節(jié)點(diǎn)具有重復(fù)度k，這樣的節(jié)點(diǎn)矢量定義了準(zhǔn)均勻的B樣條基。均勻B樣條曲線沒有保留Bezier曲線端點(diǎn)的幾何性質(zhì)，即樣條曲線的首末端點(diǎn)不再是控制多邊形的首末端點(diǎn)。采用準(zhǔn)均勻的B樣條曲線解決了這個(gè)問題第11頁(yè)/共70頁(yè)分段Bezier曲線節(jié)點(diǎn)矢量中兩端節(jié)點(diǎn)具有重復(fù)度k，所有內(nèi)節(jié)點(diǎn)重復(fù)度為k-1，這樣的節(jié)點(diǎn)矢量定義了分段的Bernstein基。第12頁(yè)/共70頁(yè)B樣條曲線用分段Bezier曲線表示后，各曲線段就具有了相對(duì)的獨(dú)立性，移動(dòng)曲線段內(nèi)的一個(gè)控制頂點(diǎn)只影響該曲線段的形狀，對(duì)其它曲線段的形狀沒有影響。并且Bezier曲線一整套簡(jiǎn)單有效的算法都可以原封不動(dòng)地采用。缺點(diǎn)是增加了定義曲線的數(shù)據(jù)，控制頂點(diǎn)數(shù)及節(jié)點(diǎn)數(shù)。 第13頁(yè)/共70頁(yè)非均勻B樣條曲線任意分布的節(jié)點(diǎn)矢量 ，只要在數(shù)學(xué)上成立（節(jié)點(diǎn)序列非遞減，兩端節(jié)點(diǎn)重復(fù)度≤k，內(nèi)節(jié)點(diǎn)重復(fù)度≤k-1）都可選取。這樣的節(jié)點(diǎn)矢量定義了非均勻B樣條基。第14頁(yè)/共70頁(yè)3.3.2B樣條曲線的性質(zhì)局部性。k階B樣條曲線上參數(shù)為的一點(diǎn)至多與k個(gè)控制頂點(diǎn)有關(guān)，與其它控制頂點(diǎn)無(wú)關(guān)；移動(dòng)該曲線的第i個(gè)控制頂點(diǎn)Pi至多影響到定義在區(qū)間上那部分曲線的形狀，對(duì)曲線的其余部分不發(fā)生影響。第15頁(yè)/共70頁(yè)

連續(xù)性

P(t)在r重節(jié)點(diǎn)處的連續(xù)階不低于k-1-r。

凸包性

P(t)在區(qū)間上的部分位于k個(gè)點(diǎn)的凸包內(nèi)，整條曲線則位于各凸包的并集之內(nèi)。第16頁(yè)/共70頁(yè)分段參數(shù)多項(xiàng)式

P(t)在每一區(qū)間上都是次數(shù)不高于k-1的參數(shù)t的多項(xiàng)式導(dǎo)數(shù)公式第17頁(yè)/共70頁(yè)變差縮減性設(shè)平面內(nèi)n+1個(gè)控制頂點(diǎn)構(gòu)成B樣條曲線P(t)的特征多邊形。在該平面內(nèi)的任意一條直線與P(t)的交點(diǎn)個(gè)數(shù)不多于該直線和特征多邊形的交點(diǎn)個(gè)數(shù)。幾何不變性B樣條曲線的形狀和位置與坐標(biāo)系的選擇無(wú)關(guān)。第18頁(yè)/共70頁(yè)仿射不變性即在仿射變換下，的表達(dá)式具有形式不變性。直線保持性控制多邊形退化為一條直線時(shí)，曲線也退化為一條直線。第19頁(yè)/共70頁(yè)

造型的靈活性。用B樣條曲線可以構(gòu)造直線段、尖點(diǎn)、切線等特殊情況.對(duì)于四階（三次）B樣條曲線.若要在其中得到一條直線段，只要四點(diǎn)位于一條直線上第20頁(yè)/共70頁(yè)為了使P(t)能過P(i)點(diǎn)，只要使重合尖點(diǎn)也可通過三重節(jié)點(diǎn)的方法得到為了使曲線和某一直線L相切，只要取位于L上及的重?cái)?shù)不大于2。第21頁(yè)/共70頁(yè)

第22頁(yè)/共70頁(yè)3.3.3deBoor算法欲計(jì)算B樣條曲線上對(duì)應(yīng)一點(diǎn)P(t)，可以利用B樣條曲線方程，但是采用deBoor算法，計(jì)算更加快捷。deBoor算法的導(dǎo)出第23頁(yè)/共70頁(yè)現(xiàn)令則這就是著名的deBoor算法第24頁(yè)/共70頁(yè)deBoor算法的遞推關(guān)系如圖第25頁(yè)/共70頁(yè)DeBoor算法的幾何意義deBoor算法有著直觀的幾何意義割角，即以線段割去角。從多邊形開始，經(jīng)過k-1層割角，最后得到P(t)上的點(diǎn)第26頁(yè)/共70頁(yè)

第27頁(yè)/共70頁(yè)3.3.4節(jié)點(diǎn)插入算法通過插入節(jié)點(diǎn)可以進(jìn)一步改善B樣條曲線的局部性質(zhì)，提高B樣條曲線的形狀控制的靈活性，可以實(shí)現(xiàn)對(duì)曲線的分割等。插入一個(gè)節(jié)點(diǎn)

在定義域某個(gè)節(jié)點(diǎn)區(qū)間內(nèi)插入一個(gè)節(jié)點(diǎn)t，得到新的節(jié)點(diǎn)矢量：重新編號(hào)成為第28頁(yè)/共70頁(yè)這個(gè)新的節(jié)點(diǎn)矢量U1決定了一組新的B樣條基原始的B樣條曲線就可以用這組新的B樣條基與未知新頂點(diǎn)表示第29頁(yè)/共70頁(yè)Boehm給出了這些未知新頂點(diǎn)的計(jì)算公式

r表示所插結(jié)點(diǎn)t在原始節(jié)點(diǎn)矢量T中的重復(fù)度。第30頁(yè)/共70頁(yè)

第31頁(yè)/共70頁(yè)

第32頁(yè)/共70頁(yè)3.3.5B樣條曲面給定參數(shù)軸u和v的節(jié)點(diǎn)矢量

p×q階B樣條曲面定義如下

第33頁(yè)/共70頁(yè)

構(gòu)成一張控制網(wǎng)格，稱為B樣條曲面的特征網(wǎng)格。和是B樣條基，分別由節(jié)點(diǎn)矢量U和V按deBoor-Cox遞推公式?jīng)Q定。第34頁(yè)/共70頁(yè)

第35頁(yè)/共70頁(yè)3.4NURBS曲線與曲面B樣條曲線包括其特例的Bezier曲線都不能精確表示出拋物線外的二次曲線，B樣條曲面包括其特例的Bezier曲面都不能精確表示出拋物面外的二次曲面，而只能給出近似表示。提出NURBS方法，即非均勻有理B樣條方法主要是為了找到與描述自由型曲線曲面的B樣條方法既相統(tǒng)一、又能精確表示二次曲線弧與二次曲面的數(shù)學(xué)方法。第36頁(yè)/共70頁(yè)NURBS太過復(fù)雜，常令人望洋興嘆NURBSBook，走向?qū)嵱没?見下頁(yè))第37頁(yè)/共70頁(yè)

SomeyearsagoafewresearchersjokedaboutNURBS,sayingthattheacronymreallystandsforNOBODYUnderstandsRationalB-Splines,writetheauthorsintheirforeword;theyformulatetheaimofchangingNURBStoEURBS,thatis,Everybody.…Thereisnodoubtthattheyhaveachievedthisgoal....IhighlyrecommendthebooktoanyonewhoisinterestedinadetaileddescriptionofNURBS.Itisextremelyhelpfulforstudents,teachersanddesignersofgeometricmodelingsystems.HelmutPottmann第38頁(yè)/共70頁(yè)NURBS方法的主要優(yōu)點(diǎn) 既為標(biāo)準(zhǔn)解析形狀(即前面提到的初等曲線曲面)，又為自由型曲線曲面的精確表示與設(shè)計(jì)提供了一個(gè)公共的數(shù)學(xué)形式第39頁(yè)/共70頁(yè)B樣條曲線包括其特例的Bezier曲線都不能精確表示出拋物線外的二次曲線，B樣條曲面包括其特例的Bezier曲面都不能精確表示出拋物面外的二次曲面，而只能給出近似表示。提出NURBS方法，即非均勻有理B樣條方法主要是為了找到與描述自由型曲線曲面的B樣條方法既相統(tǒng)一、又能精確表示二次曲線弧與二次曲面的數(shù)學(xué)方法。第40頁(yè)/共70頁(yè)兩類研究問題逼近問題：圓弧的Bezier曲線逼近，挪威Oslo學(xué)派的工作精確表示問題：權(quán)因子、頂點(diǎn)滿足什么條件才能精確表示圓??？第41頁(yè)/共70頁(yè)NURBS方法的主要優(yōu)點(diǎn) 既為標(biāo)準(zhǔn)解析形狀(即前面提到的初等曲線曲面)，又為自由型曲線曲面的精確表示與設(shè)計(jì)提供了一個(gè)公共的數(shù)學(xué)形式修改控制頂點(diǎn)和權(quán)因子，為各種形狀設(shè)計(jì)提供了充分的靈活性。具有明顯的幾何解釋和強(qiáng)有力的幾何配套技術(shù)對(duì)幾何變換和投影變換具有不變性。非有理B樣條、有理與非有理Bezier方法是其特例。第42頁(yè)/共70頁(yè)應(yīng)用NURBS中還有一些難以解決的問題：比傳統(tǒng)的曲線曲面定義方法需要更多的存儲(chǔ)空間權(quán)因子選擇不當(dāng)會(huì)引起畸變對(duì)搭接、重疊形狀的處理很麻煩。反求曲線曲面上點(diǎn)的參數(shù)值的算法，存在數(shù)值不穩(wěn)定問題

(MAF方法)第43頁(yè)/共70頁(yè)在講NURBS的定義前，先回顧一下B樣條的定義：第44頁(yè)/共70頁(yè)3.4.1 NURBS曲線的定義NURBS曲線是由分段有理B樣條多項(xiàng)式基函數(shù)定義的第45頁(yè)/共70頁(yè)Ri,k(t)具有k階B樣條基函數(shù)類似的性質(zhì)：局部支承性：Ri,k(t)=0，t[ti,ti+k]權(quán)性：可微性：如果分母不為零，在節(jié)點(diǎn)區(qū)間內(nèi)是無(wú)限次連續(xù)可微的，在節(jié)點(diǎn)處(k-1-r)次連續(xù)可導(dǎo)，r是該節(jié)點(diǎn)的重復(fù)度。若i=0，則Ri,k(t)=0；若i=+，則Ri,k(t)=1；第46頁(yè)/共70頁(yè)NURBS曲線與B樣條曲線具有類似的幾何性質(zhì)：局部性質(zhì)。變差減小性質(zhì)。凸包性。在仿射與透射變換下的不變性。在曲線定義域內(nèi)有與有理基函數(shù)同樣的可微性。第47頁(yè)/共70頁(yè)如果某個(gè)權(quán)因子為零，那么相應(yīng)控制頂點(diǎn)對(duì)曲線沒有影響。若，則當(dāng)時(shí)，非有理與有理Bezier曲線和非有理B樣條曲線是NURBS曲線的特殊情況第48頁(yè)/共70頁(yè)3.4.2

齊次坐標(biāo)表示齊次坐標(biāo)系xyw中的控制頂點(diǎn)為k階非有理B樣條曲線可表示為：第49頁(yè)/共70頁(yè)以坐標(biāo)原點(diǎn)為投影中心，則得到平面曲線第50頁(yè)/共70頁(yè)三維空間的NURBS曲線可以類似地定義。非有理B樣條的算法可以推廣到NURBS曲線，只不過是在齊次坐標(biāo)下進(jìn)行。第51頁(yè)/共70頁(yè)3.4.3權(quán)因子的幾何意義如果固定曲線的參數(shù)t，而使變化，則NURBS曲線方程變成以為參數(shù)的直線方程，即NURBS曲線上t值相同的點(diǎn)都位于同一直線上。第52頁(yè)/共70頁(yè)

分別是對(duì)應(yīng)曲線上的點(diǎn)，即N，Bi可表示為：

(Pi，Bi，N，B)四點(diǎn)的交比第53頁(yè)/共70頁(yè)（1）若i增大或減小，則也增大或減小，所以曲線被拉向或推離開Pi點(diǎn)；（2）若j增大或減小，曲線被推離或拉向Pj（ji）。第54頁(yè)/共70頁(yè)3.4.4圓錐曲線的NURBS表示取節(jié)點(diǎn)向量為則NURBS曲線退化為二次Bezier曲線，且可以證明，這是圓錐曲線弧方程。稱為形狀因子，

的值確定了圓錐曲線的類型。時(shí)，上式是拋物線弧，

第55頁(yè)/共70頁(yè)

時(shí)，上式是雙曲線弧，時(shí)，上式是橢圓弧。時(shí)，上式退化為一對(duì)直線段P0P1和

P1P2，時(shí)，上式退化為連接兩點(diǎn)P0P2的直線段第56頁(yè)/共70頁(yè)3.4.5NURBS曲線的修改常用的方法有修改權(quán)因子、控制點(diǎn)和反插節(jié)點(diǎn)。修改權(quán)因子當(dāng)保持控制頂點(diǎn)和其它權(quán)因子不變，減少或增加某權(quán)因子時(shí)，曲線被推離或拉向相應(yīng)頂點(diǎn)。第57頁(yè)/共70頁(yè)欲將曲線在該點(diǎn)S拉向或推離控制頂點(diǎn)Pi一個(gè)距離d，以得到新點(diǎn)S’，可由重新確定相應(yīng)的權(quán)因子使之改變?yōu)閬磉_(dá)到修改控制頂點(diǎn)修改控制頂點(diǎn)的位置，曲線隨之變形。第58頁(yè)/共70頁(yè)基于幾何約束的形狀修改問題的提法：求新的控制頂點(diǎn)，使曲線上的點(diǎn)S變到T。

TSP(t)第59頁(yè)/共70頁(yè)將曲線改寫為其中第60頁(yè)/共70頁(yè)約束優(yōu)化方法假設(shè)控制頂點(diǎn)改變，以滿足點(diǎn)約束。我們對(duì)以上每個(gè)點(diǎn)，給一個(gè)擾動(dòng)量，并用約束優(yōu)化方法求之。約