非均勻有理B樣條ppt課件

1、3.3 B樣條曲線與曲面,Bezier曲線或曲面有許多優(yōu)越性，但有兩點(diǎn)不足： Bezier曲線或曲面不能作局部修改； Bezier曲線或曲面的拼接比較復(fù)雜,清華大學(xué) 計(jì)算機(jī)圖形學(xué),1972年，Gordon、Riesenfeld等人發(fā)展了1946年Schoenberg提出的樣條方法 , 提出了B樣條方法，在保留Bezier方法全部?jī)?yōu)點(diǎn)的同時(shí)，克服了Bezier方法的弱點(diǎn)。 樣條的史話,清華大學(xué) 計(jì)算機(jī)圖形學(xué),樣條的史話(1) 1946年的紅皮書 Schoenberg拉開(kāi)了神話的序幕 從插值的R-K現(xiàn)象說(shuō)起 樣條分段連續(xù)多項(xiàng)式,清華大學(xué) 計(jì)算機(jī)圖形學(xué),樣條的史話(2) 斷言樣條不可能用于外形設(shè)計(jì)

2、幾何樣條出現(xiàn)，離散計(jì)算，峰回路轉(zhuǎn) Riesenfield, Gordan,清華大學(xué) 計(jì)算機(jī)圖形學(xué),如何理解B-樣條？ 樣條插值，三對(duì)角方程 (函數(shù)、參數(shù)) 給定分劃，所有的B樣條的全體組成一個(gè)線性空間，線性空間有基函數(shù)，這就是B樣條基函數(shù) 由B樣條基函數(shù)代替Bezier曲線中的Bernstein基函數(shù)，即B樣條曲線,清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.3.1 B樣條的遞推定義和性質(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)式樣條,清華大學(xué)

3、 計(jì)算機(jī)圖形學(xué),de Boor-Cox遞推定義 并約定 幾個(gè)問(wèn)題,清華大學(xué) 計(jì)算機(jī)圖形學(xué),幾個(gè)問(wèn)題 的非零區(qū)間是什么？ 需要多少個(gè)節(jié)點(diǎn)？ 定義區(qū)間是什么,清華大學(xué) 計(jì)算機(jī)圖形學(xué),以k4，n=4為例,清華大學(xué) 計(jì)算機(jī)圖形學(xué),2性質(zhì) 局部支承性。 權(quán)性。 微分公式,清華大學(xué) 計(jì)算機(jī)圖形學(xué),B樣條曲線類型的劃分 曲線按其首末端點(diǎn)是否重合，區(qū)分為閉曲線和開(kāi)曲線。 B樣條曲線按其節(jié)點(diǎn)矢量中節(jié)點(diǎn)的分布情況，可劃分為四種類型,清華大學(xué) 計(jì)算機(jī)圖形學(xué),均勻B樣條曲線。 節(jié)點(diǎn)矢量中節(jié)點(diǎn)為沿參數(shù) 軸均勻或等距分布，所有 節(jié)點(diǎn)區(qū)間長(zhǎng)度為常數(shù)。這樣的節(jié)點(diǎn)矢量定義了均勻的B樣條基,清華大學(xué) 計(jì)算機(jī)圖形學(xué),準(zhǔn)均勻B樣條

4、與均勻B樣條曲線的差別在于兩端節(jié)點(diǎn)具有重復(fù)度k，這樣的節(jié)點(diǎn)矢量定義了準(zhǔn)均勻的B樣條基。均勻B樣條曲線沒(méi)有保留Bezier曲線端點(diǎn)的幾何性質(zhì)，即樣條曲線的首末端點(diǎn)不再是控制多邊形的首末端點(diǎn)。采用準(zhǔn)均勻的B樣條曲線解決了這個(gè)問(wèn)題,清華大學(xué) 計(jì)算機(jī)圖形學(xué),分段Bezier曲線 節(jié)點(diǎn)矢量中兩端節(jié)點(diǎn)具有重復(fù)度k，所有內(nèi)節(jié)點(diǎn)重復(fù)度為k-1，這樣的節(jié)點(diǎn)矢量定義了分段的Bernstein基,清華大學(xué) 計(jì)算機(jī)圖形學(xué),B樣條曲線用分段Bezier曲線表示后，各曲線段就具有了相對(duì)的獨(dú)立性，移動(dòng)曲線段內(nèi)的一個(gè)控制頂點(diǎn)只影響該曲線段的形狀，對(duì)其它曲線段的形狀沒(méi)有影響。并且Bezier曲線一整套簡(jiǎn)單有效的算法都可以原封不

5、動(dòng)地采用。缺點(diǎn)是增加了定義曲線的數(shù)據(jù)，控制頂點(diǎn)數(shù)及節(jié)點(diǎn)數(shù),清華大學(xué) 計(jì)算機(jī)圖形學(xué),非均勻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樣條基,清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.3.2 B樣條曲線的性質(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ā)生影響,清華大學(xué) 計(jì)算機(jī)圖形學(xué),連續(xù)性 P(t)在r重節(jié)點(diǎn)處的連續(xù)階不低于 k-1-r。 凸包性 P(t)在區(qū)間 上的部分位于

6、k個(gè)點(diǎn) 的凸包 內(nèi)，整條曲線則位于各凸包 的并集之內(nèi),清華大學(xué) 計(jì)算機(jī)圖形學(xué),分段參數(shù)多項(xiàng)式 P(t)在每一區(qū)間上都是次數(shù)不高于k-1的參數(shù)t的多項(xiàng)式 導(dǎo)數(shù)公式,清華大學(xué) 計(jì)算機(jī)圖形學(xué),變差縮減性 設(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),清華大學(xué) 計(jì)算機(jī)圖形學(xué),仿射不變性 即在仿射變換下，的表達(dá)式具有形式不變性。 直線保持性 控制多邊形退化為一條直線時(shí)， 曲線也退化為一條直線,清華大學(xué) 計(jì)算機(jī)圖形學(xué),造型的靈活性。 用B樣條曲

7、線可以構(gòu)造直線段、尖點(diǎn)、切線等特殊情況.對(duì)于四階（三次）B樣條曲線.若要在其中得到一條直線段，只要四點(diǎn) 位于一條直線上,清華大學(xué) 計(jì)算機(jī)圖形學(xué),為了使P(t)能過(guò)P(i)點(diǎn)，只要使 重合 尖點(diǎn)也可通過(guò)三重節(jié)點(diǎn)的方法得到 為了使曲線和某一直線L相切，只要取 位于L上及 的重?cái)?shù)不大于2,清華大學(xué) 計(jì)算機(jī)圖形學(xué),清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.3.3 de Boor 算法,欲計(jì)算B樣條曲線上對(duì)應(yīng)一點(diǎn)P(t)，可以利用B樣條曲線方程，但是采用de Boor 算法，計(jì)算更加快捷。 de Boor 算法的導(dǎo)出,清華大學(xué) 計(jì)算機(jī)圖形學(xué),現(xiàn)令 則 這就是著名的de Boor 算法,清華大學(xué) 計(jì)算機(jī)圖形學(xué),de B

8、oor 算法的遞推關(guān)系如圖,清華大學(xué) 計(jì)算機(jī)圖形學(xué),De Boor 算法的幾何意義 de Boor算法有著直觀的幾何意義 割角，即以線段 割去角 。從多邊形 開(kāi)始，經(jīng)過(guò) k-1 層割角，最后得到P(t)上的點(diǎn),清華大學(xué) 計(jì)算機(jī)圖形學(xué),清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.3.4 節(jié)點(diǎn)插入算法,通過(guò)插入節(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)成為,清華大學(xué) 計(jì)算機(jī)圖形學(xué),這個(gè)新的節(jié)點(diǎn)矢量U1決定了一組新的B樣條基 原始的B樣條曲線就可以用這組新的B樣條基與未知新頂點(diǎn)

9、 表示,清華大學(xué) 計(jì)算機(jī)圖形學(xué),Boehm給出了這些未知新頂點(diǎn)的計(jì)算公式 r 表示所插結(jié)點(diǎn)t在原始節(jié)點(diǎn)矢量T中的重復(fù)度,清華大學(xué) 計(jì)算機(jī)圖形學(xué),清華大學(xué) 計(jì)算機(jī)圖形學(xué),清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.3.5 B樣條曲面,給定參數(shù)軸u和v的節(jié)點(diǎn)矢量 pq階B樣條曲面定義如下,清華大學(xué) 計(jì)算機(jī)圖形學(xué),構(gòu)成一張控制網(wǎng)格，稱為B樣條曲面的特征網(wǎng)格。 和 是B樣條基，分別由節(jié)點(diǎn)矢量U和V按deBoor-Cox遞推公式?jīng)Q定,清華大學(xué) 計(jì)算機(jī)圖形學(xué),清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.4 NURBS曲線與曲面,B樣條曲線包括其特例的Bezier曲線都不能精確表示出拋物線外的二次曲線，B樣條曲面包括其特例的Bezier曲

10、面都不能精確表示出拋物面外的二次曲面，而只能給出近似表示。 提出NURBS方法，即非均勻有理B樣條方法主要是為了找到與描述自由型曲線曲面的B樣條方法既相統(tǒng)一、又能精確表示二次曲線弧與二次曲面的數(shù)學(xué)方法,清華大學(xué) 計(jì)算機(jī)圖形學(xué),NURBS太過(guò)復(fù)雜，常令人望洋興嘆 NURBS Book， 走向?qū)嵱没?(見(jiàn)下頁(yè),清華大學(xué) 計(jì)算機(jī)圖形學(xué),Some years ago a few researchers joked about NURBS, saying that the acronym really stands for NOBODY Understands Rational B-Splines, w

11、rite the authors in their foreword; they formulate the aim of changing NURBS to EURBS, that is, Everybody. There is no doubt that they have achieved this goal. I highly recommend the book to anyone who is interested in a detailed description of NURBS. It is extremely helpful for students, teachers a

12、nd designers of geometric modeling systems. Helmut Pottmann,清華大學(xué) 計(jì)算機(jī)圖形學(xué),NURBS方法的主要優(yōu)點(diǎn) 既為標(biāo)準(zhǔn)解析形狀(即前面提到的初等曲線曲面)，又為自由型曲線曲面的精確表示與設(shè)計(jì)提供了一個(gè)公共的數(shù)學(xué)形式,清華大學(xué) 計(jì)算機(jī)圖形學(xué),B樣條曲線包括其特例的Bezier曲線都不能精確表示出拋物線外的二次曲線，B樣條曲面包括其特例的Bezier曲面都不能精確表示出拋物面外的二次曲面，而只能給出近似表示。 提出NURBS方法，即非均勻有理B樣條方法主要是為了找到與描述自由型曲線曲面的B樣條方法既相統(tǒng)一、又能精確表示二次曲線弧與二次曲面

13、的數(shù)學(xué)方法,清華大學(xué) 計(jì)算機(jī)圖形學(xué),兩類研究問(wèn)題 逼近問(wèn)題：圓弧的Bezier曲線逼近，挪威Oslo學(xué)派的工作 精確表示問(wèn)題：權(quán)因子、頂點(diǎn)滿足什么條件才能精確表示圓弧,清華大學(xué) 計(jì)算機(jī)圖形學(xué),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方法是其特例,清華大學(xué) 計(jì)算機(jī)圖形學(xué),應(yīng)用NURBS中還有一些難以解決的問(wèn)題： 比傳統(tǒng)的曲線曲面定義方法

14、需要更多的存儲(chǔ)空間 權(quán)因子選擇不當(dāng)會(huì)引起畸變 對(duì)搭接、重疊形狀的處理很麻煩。 反求曲線曲面上點(diǎn)的參數(shù)值的算法，存在數(shù)值不穩(wěn)定問(wèn)題 (MAF方法,清華大學(xué) 計(jì)算機(jī)圖形學(xué),在講NURBS 的定義前，先回顧一下B樣條的定義,清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.4.1NURBS曲線的定義 NURBS曲線是由分段有理B樣條多項(xiàng)式基函數(shù)定義的,清華大學(xué) 計(jì)算機(jī)圖形學(xué),Ri,k(t)具有k階B樣條基函數(shù)類似的性質(zhì)： 局部支承性：Ri,k(t)=0，tti, 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)=

15、0； 若i=+，則Ri,k(t)=1,清華大學(xué) 計(jì)算機(jī)圖形學(xué),NURBS曲線與B樣條曲線具有類似的幾何性質(zhì)： 局部性質(zhì)。 變差減小性質(zhì)。 凸包性。 在仿射與透射變換下的不變性。 在曲線定義域內(nèi)有與有理基函數(shù)同樣的可微性,清華大學(xué) 計(jì)算機(jī)圖形學(xué),如果某個(gè)權(quán)因子為零，那么相應(yīng)控制頂點(diǎn)對(duì)曲線沒(méi)有影響。 若 ，則當(dāng) 時(shí)， 非有理與有理Bezier曲線和非有理B樣條曲線是NURBS曲線的特殊情況,清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.4.2 齊次坐標(biāo)表示 齊次坐標(biāo)系xyw中的控制頂點(diǎn)為 k階非有理B樣條曲線可表示為,清華大學(xué) 計(jì)算機(jī)圖形學(xué),以坐標(biāo)原點(diǎn)為投影中心，則得到平面曲線,清華大學(xué) 計(jì)算機(jī)圖形學(xué),三維空間的N

16、URBS曲線可以類似地定義。 非有理B樣條的算法可以推廣到NURBS曲線，只不過(guò)是在齊次坐標(biāo)下進(jìn)行,清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.4.3 權(quán)因子的幾何意義 如果固定曲線的參數(shù)t，而使 變化，則NURBS曲線方程變成以 為參數(shù)的直線方 程，即NURBS曲線上t值相同的點(diǎn)都位于同一直線上,清華大學(xué) 計(jì)算機(jī)圖形學(xué),分別是 對(duì)應(yīng)曲線上的點(diǎn)，即 N，Bi可表示為： (Pi，Bi，N，B)四點(diǎn)的交比,清華大學(xué) 計(jì)算機(jī)圖形學(xué),1）若i增大或減小，則也增大或減小，所以曲線被拉向或推離開(kāi)Pi點(diǎn)； （2）若j增大或減小，曲線被推離或拉向Pj（ji,清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.4.4圓錐曲線的NURBS表示,取節(jié)點(diǎn)向

17、量為 則NURBS曲線退化為二次Bezier曲線，且可以證明，這是圓錐曲線弧方程。 稱為形狀因子， 的值確定了圓錐曲線的類型。 時(shí)，上式是拋物線弧,清華大學(xué) 計(jì)算機(jī)圖形學(xué),時(shí)，上式是雙曲線弧， 時(shí)，上式是橢圓弧。 時(shí)，上式退化為一對(duì)直線段P0P1和 P1P2， 時(shí)，上式退化為連接兩點(diǎn)P0P2的直線段,清華大學(xué) 計(jì)算機(jī)圖形學(xué),3.4.5 NURBS曲線的修改,常用的方法有修改權(quán)因子、控制點(diǎn)和反插節(jié)點(diǎn)。 修改權(quán)因子 當(dāng)保持控制頂點(diǎn)和其它權(quán)因子不變，減少或增加某權(quán)因子時(shí)，曲線被推離或拉向相應(yīng)頂點(diǎn),清華大學(xué) 計(jì)算機(jī)圖形學(xué),欲將曲線在該點(diǎn)S拉向或推離控制頂點(diǎn)Pi一個(gè)距離d，以得到新點(diǎn)S，可由重新確定相應(yīng)

18、的權(quán)因子 使之改變?yōu)?來(lái)達(dá)到 修改控制頂點(diǎn) 修改控制頂點(diǎn)的位置，曲線隨之變形,清華大學(xué) 計(jì)算機(jī)圖形學(xué),基于幾何約束的形狀修改 問(wèn)題的提法：求新的控制頂點(diǎn)，使曲線上的 點(diǎn)S變到T。 T S P(t,清華大學(xué) 計(jì)算機(jī)圖形學(xué),將曲線改寫為 其中,清華大學(xué) 計(jì)算機(jī)圖形學(xué),約束優(yōu)化方法 假設(shè)控制頂點(diǎn) 改變，以滿足點(diǎn)約束。我們對(duì)以上每個(gè)點(diǎn)，給一個(gè)擾動(dòng)量 ，并用約束優(yōu)化方法求之。 約束條件為,清華大學(xué) 計(jì)算機(jī)圖形學(xué),令 由 Lagrange 函數(shù) 可得方程組,清華大學(xué) 計(jì)算機(jī)圖形學(xué),解方程組可得,清華大學(xué) 計(jì)算機(jī)圖形學(xué),當(dāng)只有一個(gè)控制頂點(diǎn)可動(dòng)時(shí)，即為 此為CAD主編Piegl于1989年提出的公式。 該方法可推廣到其他幾何約束及曲面,清華大學(xué) 計(jì)算機(jī)圖形學(xué),基于能量極小的方