第3章幾何造型技術(shù)

第3章幾何造型技術(shù)本章教學(xué)目標(biāo)1.總體目標(biāo)：掌握幾何造型技術(shù)的基本原理，理解三維圖形的構(gòu)造思想。2.通過本章的學(xué)習(xí)，應(yīng)能做到：掌握下列概念：參數(shù)曲線和曲面、位置矢量、切矢量、法矢量、曲率、撓率、插值、逼近、擬合、光順、參數(shù)化、參數(shù)連續(xù)性、幾何連續(xù)性、Bernstein基函數(shù)、Bezier曲線、B樣條基、B樣條曲線、Nurbs曲線和形體表示模型。。掌握曲線曲面的參數(shù)表示方法和連續(xù)性的基本概念、Bezier曲線的deCasteljau遞推算法、Bezier曲線的升階算法、Bezier曲面的遞推算法和B樣條基及B樣條曲線的DeboorCox遞推算法的基本思想。熟悉參數(shù)曲面的代數(shù)和幾何形式、三邊Bezier曲面片的基本思想、B樣條曲面的定義、Nurbs曲線的定義及齊次坐標(biāo)表示、線與線求交算法的基本思想。了解B樣條曲線的節(jié)點(diǎn)插入算法、Nubrs曲線權(quán)因子的幾何意義、圓錐曲線的Nurbs表示、Nurbs曲面的定義及性質(zhì)、形體的邊界表示模型、線與面及面與面求交的基本思想和實(shí)體造型系統(tǒng)的基本功能。幾何造型技術(shù)是一項(xiàng)研究在計(jì)算機(jī)中，如何表達(dá)物體模型形狀的技術(shù)。描述物體的三維模型有三種:

線框模型、曲面模型和實(shí)體模型。線框模型用頂點(diǎn)和棱邊來表示物體。由于沒有面的信息，它不能表示表面含有曲面的物體；它不能明確地定義給定點(diǎn)與物體之間的關(guān)系（點(diǎn)在物體內(nèi)部、外部或表面上）。曲面模型用面的集合來表示物體，而用環(huán)來定義面的邊界。表面模型能夠滿足面面求交、線面消隱、明暗色彩圖、數(shù)控加工等需要。但在該模型中，只有一張張面的信息，物體究竟存在于表面的哪一側(cè)，并沒有給出明確的定義，無法計(jì)算和分析物體的整體性質(zhì)。如物體的體積、重心等。也不能將這個物體作為一個整體去考察它與其它物體相互關(guān)聯(lián)的性質(zhì)，如是否相交等。實(shí)體模型能完整表示物體的所有形狀信息，可以無歧義地確定一個點(diǎn)是在物體外部、內(nèi)部或表面上。是最高級的模型。這種模型能夠進(jìn)一步滿足物性計(jì)算、有限元分析等應(yīng)用的要求。三維曲面模型表示三維物體的信息并不完整，但它能夠表達(dá)復(fù)雜的雕刻曲面，在幾何造型中具有重要的地位，對于支持曲面的三維實(shí)體模型，曲面模型是它的基礎(chǔ)。3.1參數(shù)曲線和曲面3.1.1曲線曲面參數(shù)表示顯式表示:y=f（x）隱式表示:f（x，y）=0參數(shù)表示:P(t)=[x(t),y(t),z(t)]顯式或隱式表示存在下述問題：1）與坐標(biāo)軸相關(guān)；2）會出現(xiàn)斜率為無窮大的情形(如垂線)；3)不便于計(jì)算機(jī)編程。參數(shù)表示:曲線上任一點(diǎn)的坐標(biāo)均表示成給定參數(shù)的函數(shù)。假定用t表示參數(shù)，平面曲線上任一點(diǎn)P可表示為：

空間曲線上任一三維點(diǎn)P可表示為：如：梁友棟裁剪算法中，一條兩端點(diǎn)為P1（x1，y1）、P2（x2，y2）的線段可以用參數(shù)方程形式表示：參數(shù)表示例子：直線單位圓（1）以滿足幾何不變性的要求。（2）有更大的自由度來控制曲線、曲面的形狀（3）對曲線、曲面進(jìn)行變換，可對其參數(shù)方程直接進(jìn)行幾何變換。（4）便于處理斜率為無窮大的情形，不會因此而中斷計(jì)算。（5）便于用戶把低維空間中曲線、曲面擴(kuò)展到高維空間去。（6）規(guī)格化的參數(shù)變量t∈[0,1]，使其相應(yīng)的幾何分量是有界的，而不必用另外的參數(shù)去定義邊界。（7）易于用矢量和矩陣表示幾何分量，簡化了計(jì)算。參數(shù)表示的優(yōu)點(diǎn)：3.1.2曲線的基本概念位置矢量：曲線上任一點(diǎn)的位置矢量可表示為：P(t)=[x(t),y(t),z(t)]；切向量(切矢量)選擇弧長s作為參數(shù)，則是單位切矢量根據(jù)弧長微分公式有：于是有T=，即為單位切矢量法矢量與平行的法矢稱為曲線在該點(diǎn)的主法矢N矢量積是第三個單位矢量，它垂直于T和N。把平行于矢量B的法矢稱為曲線的副法矢。我們可以推導(dǎo)出：T(切矢)、N(主法矢)和B(副法矢)構(gòu)成了曲線上的活動坐標(biāo)架N、B構(gòu)成的平面稱為法平面，N、T構(gòu)成的平面稱為密切平面，B、T構(gòu)成的平面稱為從切平面。

曲率和撓率即稱為曲率，其幾何意義是曲線的單位切矢對弧長的轉(zhuǎn)動率。曲率k的倒數(shù)稱為曲率半徑。撓率

的絕對值等于副法線方向(或密切平面)對于弧長的轉(zhuǎn)動率.撓率是刻劃曲線彎曲狀況的又一個重要的幾何量，又可稱之為曲線的第二曲率；撓率絕對值度量了曲線上鄰近兩點(diǎn)的次法向量之間的夾角對弧長的變化率。由于撓率體現(xiàn)了密切平面的扭轉(zhuǎn)狀況，通常說它表示了曲線的扭曲程度．撓率大于0、等于0和小于0分別表示曲線為右旋轉(zhuǎn)空間曲線、平面曲線和左旋轉(zhuǎn)空間曲線。.對于一般參數(shù)t，我們可以推導(dǎo)出曲率和撓率的計(jì)算公式如下：3.1.3插值、擬合、逼近和光順給定一組有序的數(shù)據(jù)點(diǎn)Pi，i=0,1,…,n，構(gòu)造一條曲線順序通過這些數(shù)據(jù)點(diǎn)，稱為對這些數(shù)據(jù)點(diǎn)進(jìn)行插值，所構(gòu)造的曲線稱為插值曲線。擬合：構(gòu)造一條曲線使之在某種意義下最接近給定的數(shù)據(jù)點(diǎn)(但未必通過這些點(diǎn))，所構(gòu)造的曲線為擬合曲線。在計(jì)算數(shù)學(xué)中，逼近通常指用一些性質(zhì)較好的函數(shù)近似表示一些性質(zhì)不好的函數(shù)。在計(jì)算機(jī)圖形學(xué)中，逼近繼承了這方面的含義，因此插值和擬合都可以視為逼近。光順(Fairing)指曲線的拐點(diǎn)不能太多。對平面曲線而言，相對光順的條件是：a.具有二階幾何連續(xù)性(G2)；b.不存在多余拐點(diǎn)和奇異點(diǎn)；c.曲率變化較小。3.1.4參數(shù)化參數(shù)化常用方法有：均勻參數(shù)化(等距參數(shù)化)

節(jié)點(diǎn)在參數(shù)軸上呈等距分布，。累加弦長參數(shù)化

這種參數(shù)法如實(shí)反映了型值點(diǎn)按弦長的分布情況，能夠克服型值點(diǎn)按弦長分布不均勻的情況下采用均勻參數(shù)化所出現(xiàn)的問題。向心參數(shù)化法

向心參數(shù)化法假設(shè)在一段曲線弧上的向心力與曲線切矢從該弧段始端至末端的轉(zhuǎn)角成正比，加上一些簡化假設(shè)，得到向心參數(shù)化法。此法尤其適用于非均勻型值點(diǎn)分布。修正弦長參數(shù)化法弦長修正系數(shù)Ki>=1。從公式可知，與前后鄰弦長及相比，若越小，且與前后鄰弦邊夾角的外角qi-1和qi(不超過∏/2時)越大，則修正系數(shù)就Ki就越大。

參數(shù)區(qū)間的規(guī)格化

3.1.5參數(shù)曲線的代數(shù)和幾何形式 我們以三次參數(shù)曲線為例，討論參數(shù)曲線的代數(shù)和幾何形式。代數(shù)形式上述代數(shù)式寫成矢量式是幾何形式對三次參數(shù)曲線，若用其端點(diǎn)位矢P(0)、P(1)和切矢P￠(0)、P￠(1)描述。將P(0)、P(1)、P￠(0)和P￠(1)簡記為P0、P1、P￠0和P￠1，代入

得12

3.1.6連續(xù)性即連續(xù)性條件有兩種：參數(shù)連續(xù)性和幾何連續(xù)性。1.零階參數(shù)連續(xù)性，記作C0，指相鄰兩個曲線段在交點(diǎn)處具有相同的坐標(biāo)。

零階連續(xù)性

參數(shù)連續(xù)性2.一階參數(shù)連續(xù)性，記作C1，指相鄰兩個曲線段在交點(diǎn)處具有相同的一階導(dǎo)數(shù)。一階連續(xù)性

參數(shù)連續(xù)性3.二階參數(shù)連續(xù)性，記作C2，指相鄰兩個曲線段在交點(diǎn)處具有相同的一階和二階導(dǎo)數(shù)。圖7-6二階連續(xù)性

參數(shù)連續(xù)性與參數(shù)連續(xù)性的區(qū)別，幾何連續(xù)性只要求導(dǎo)數(shù)成比例，而不是相等。零階幾何連續(xù)性，記作G0

，與零階參數(shù)連續(xù)性相同，即相鄰兩個曲線段在交點(diǎn)處有相同的坐標(biāo)。幾何連續(xù)性一階幾何連續(xù)性，記作G1

，指相鄰兩個曲線段在交點(diǎn)處的一階導(dǎo)數(shù)成比例，但大小不一定相等。幾何連續(xù)性二階幾何連續(xù)性，記作G2

，指相鄰兩個曲線段在交點(diǎn)處的一階和二階導(dǎo)數(shù)成比例，即曲率一致。幾何連續(xù)性反例：左右導(dǎo)數(shù)不等說明傳統(tǒng)的導(dǎo)數(shù)定義太嚴(yán)格3.1.7參數(shù)曲面基本概念示意圖

參數(shù)曲面的幾個基本概念工程中常常遇到這樣的情況：已知一些計(jì)算值或測試數(shù)據(jù)，要構(gòu)造一條光滑曲線，通過或貼近這些離散點(diǎn)數(shù)據(jù)，這樣構(gòu)造出來的曲線稱為擬合曲線。擬合曲線通常采用二次或三次參數(shù)曲線的形式，我們一般采用三次擬合曲線。(原因低于3次，控制曲線形狀不夠靈活，且光順性受影響，高于3次，計(jì)算量大，且可能增加不必要的擺動（即振蕩））。Bezier曲線是法國數(shù)學(xué)家P.E.Bezier構(gòu)造的一種以逼近為基礎(chǔ)的參數(shù)曲線。3.2Bézier曲線與曲面Bezier曲線的描述方法：通過一組多邊折線的各個頂點(diǎn)唯一定義出來的在這組多邊折線的頂點(diǎn)中，只有第一點(diǎn)和最一點(diǎn)在曲線上且多邊形的第一條和最后一條邊表示了曲線在起點(diǎn)和終點(diǎn)的切線方向其余各頂點(diǎn)用來定義Bezier曲線的階次和形狀。多邊折線也稱為控制多邊形，它的頂點(diǎn)叫做控制點(diǎn)

特點(diǎn)：Bezier曲線的形狀趨近于控制多邊形的形狀改變控制多邊形的頂點(diǎn)位置就會改變曲線的形狀典型的三次Bezier曲線P0P1P2P3P0P1P2P3Bézier曲線P(t)與其控制多邊形的關(guān)系可以這樣認(rèn)為：控制多邊形P0P1…Pn是P(t)的大致形狀的勾畫；P(t)是對多邊形P0P1…Pn的逼近；3.3.1Bézier曲線的定義和性質(zhì)1.一次Bezier曲線當(dāng)n＝1時，Bezier曲線的控制多邊形有二個控制點(diǎn)P0和P1

可以看出，一次Bezier曲線是一次多項(xiàng)式，一段直線。2.二次Bezier曲線當(dāng)n＝2時，Bezier曲線的控制多邊形有三個控制點(diǎn)P0、P1和P2，二次Bezier曲線是二次多項(xiàng)式?？梢宰C明，二次Bezier曲線是一段拋物線。

3.三次Bezier曲線當(dāng)n＝3時，Bezier曲線的控制多邊形有四個控制點(diǎn)P0、P1、P2和P3，Bezier曲線是三次多項(xiàng)式?？梢宰C明，三次Bezier曲線是自由曲線。

2.Bernstein基函數(shù)性質(zhì)2.Bernstein基函數(shù)性質(zhì)2.Bernstein基函數(shù)性質(zhì)3.Bézier曲線的性質(zhì)3.Bézier曲線的性質(zhì)3.Bézier曲線的性質(zhì)3.Bézier曲線的性質(zhì)3.Bézier曲線的性質(zhì)3.Bézier曲線的性質(zhì)3.Bézier曲線的性質(zhì)3.2.2Bézier曲線的遞推算法設(shè)P0、P02、P2是一條拋物線上順序三個不同的點(diǎn)。過P0和P2點(diǎn)的兩切線交于P1點(diǎn)，在P02點(diǎn)的切線交P0P1和P2P1于P01和P11，則如下比例成立：這是所謂拋物線的三切線定理。

當(dāng)P0，P2固定，引入?yún)?shù)t，令上述比值為t:(1-t)，即有：

t從0變到1，第一、二式就分別表示控制二邊形的第一、二條邊，它們是兩條一次Bezier曲線。將一、二式代入第三式得：

3.2.2Bézier曲線的遞推算法當(dāng)t從0變到1時，它表示了由三頂點(diǎn)P0、P1、P2三點(diǎn)定義的一條二次Bezier曲線。并且表明：這二次Bezier曲線P02可以定義為分別由前兩個頂點(diǎn)(P0,P1)和后兩個頂點(diǎn)(P1,P2)決定的一次Bezier曲線的線性組合。依次類推，由(n+1)個控制點(diǎn)Pi(i=0,1,...,n)定義的n次Bezier曲線P0n可被定義為分別由前、后n個控制點(diǎn)定義的兩條(n-1)次Bezier曲線P0n-1與P1n-1的線性組合：3.2.2Bézier曲線的遞推算法由此得到Bezier曲線的遞推計(jì)算公式：這便是著名的deCasteljau算法。用這一遞推公式，在給定參數(shù)下，求Bezier曲線上一點(diǎn)P(t)非常有效。上式中：Pi0=Pi是定義Bezier曲線的控制點(diǎn)，P0n即為曲線P(t)上具有參數(shù)t的點(diǎn)。

3.2.2Bézier曲線的遞推算法舉例分析：以三次Bézier曲線為例，n=3時Pin的遞推關(guān)系如下所示：3.2.2Bézier曲線的遞推算法n=3時，Pin的遞推關(guān)系幾何作圖法求Bezier曲線上一點(diǎn)（n=3，t=1/3）Bézier曲線的遞推算法的幾何意義

（Bezier曲線的可分割性）依次對原始控制多邊形每一邊執(zhí)行同樣的定比分割，所得分割點(diǎn)就是第一級遞推生成的中間頂點(diǎn)，對這些中間頂點(diǎn)構(gòu)成的控制多邊形再執(zhí)行同樣的定比分割，重復(fù)操作，直到得出一個中間頂點(diǎn)，即為所求曲線上的點(diǎn)。根據(jù)該式可以繪制Bezier曲線，比如繪制三次取t=0，t＝1/3，t＝2/3，t=1，點(diǎn)的運(yùn)動軌跡形成Bezier曲線。圖1繪制的是t=1/3的點(diǎn)。例：Bezier曲線的幾何作圖法

（分別取t=0，t＝1/3，t＝2/3，t=1）圖2繪制的是t=2/3的點(diǎn)。例：Bezier曲線的幾何作圖法

（分別取t=0，t＝1/3，t＝2/3，t=1）連接閉區(qū)間（0，1）內(nèi)的所有點(diǎn)，可以繪制Bezier曲線，如圖3所示。例：Bezier曲線的幾何作圖法

（分別取t=0，t＝1/3，t＝2/3，t=1）注意：對于Bezier曲線，在區(qū)間（0,1）范圍內(nèi)，每個基函數(shù)均不為零，說明不能使用控制多邊形對曲線的形狀進(jìn)行局部調(diào)整，如果要改變某一控制點(diǎn)位置，整個曲線都將受到影響。5次Bézier曲線的分割過程：3.2.3Bézier曲線的拼接3.2.3Bézier曲線的拼接3.2.3Bézier曲線的拼接3.2.4Bézier曲線的升階與降階1.Bézier曲線的升階1.Bézier曲線的升階1.Bézier曲線的升階2.Bézier曲線的降階假定Pi是由Pi*升階得到，則由升階公式有：從這個方程可以導(dǎo)出兩個遞推公式：其中第一個遞推公式在靠近P0處趨向生成較好的逼近，而第二個遞推公式在靠近Pn處趨向生成較好的逼近。2.Bézier曲線的降階3.2.5Bézier曲面1.Bézier曲面的定義剩下的4個頂點(diǎn)決定了雙三次Bezier曲面片的形狀12個頂點(diǎn)決定四條邊界曲線,皆為三次Bezier曲線例子2.Bézier曲面的性質(zhì)（1）Bezier曲面特征網(wǎng)格的四個角點(diǎn)正好是Bezier曲面的四個角點(diǎn)，即

P(0,0)=P00，P(1,0)=Pm0，P(0,1)=P0n，P(1,1)=Pmn。（2）Bezier曲面特征網(wǎng)格最外一圈頂點(diǎn)定義Bezier曲面的四條邊界；Bezier曲面邊界的跨界切矢只與定義該邊界的頂點(diǎn)及相鄰一排頂點(diǎn)有關(guān)，且P00P10P01、P0nP1nP0,n-1、PmnPm,n-1Pm-1,n和Pm0Pm-1,0Pm1（圖3.16打上斜線的三角形）；其跨界二階導(dǎo)矢只與定義該邊界的頂點(diǎn)及相鄰兩排頂點(diǎn)有關(guān)。（3）幾何不變性。（4）對稱性。（5）凸包性。圖3.16雙三次Bezier曲面及邊界信息2.Bézier曲面的性質(zhì)3.Bézier曲面片的拼接如右圖所示，設(shè)兩張m×n次Bezier曲面片，分別由控制頂點(diǎn)Pij和Qij定義。兩個曲面片拼接的條件：①它們有公共的邊界：P(1,v)=Q(0,v)②兩曲面片在該邊界上有公共的切平面，即曲面邊界的u向和v向是光滑且連續(xù)的。4.Bézier曲面的遞推算法Bezier曲線的遞推(deCasteljau)算法，可以推廣到Bezier曲面的情形。若給定Bezier曲面特征網(wǎng)格的控制頂點(diǎn)Pij(i=0,1,...,m;j=0,1,...,n)和一對參數(shù)值(u,v)，則：Bezier曲面的離散生成Bézier曲面的離散生成Bézier曲面的離散生成Bézier曲面的離散生成Bézier曲面的離散生成Bézier曲面的離散生成3.2.6三邊Bezier曲面片圖3.18兩類Bezier曲面四邊Bezier曲面片定義在矩形區(qū)域上。三邊Bezier曲面片定義在三邊形域上。3.2.6三邊Bezier曲面片3.2.6三邊Bezier曲面片2．三角域上的Bernstein基

單變量的n次的Bernstein基由的二項(xiàng)式展開各項(xiàng)組成。雙變量張量積的Bernstein基由兩個單變量的Bernstein基各取其一的乘積組成。而定義在三角域上的雙變量n次的Bernstein基由的展開式各項(xiàng)組成。3.3B樣條曲線與曲面Bezier曲線或曲面有許多優(yōu)越性，但有兩點(diǎn)不足：Bezier曲線或曲面不能作局部修改；Bezier曲線或曲面的拼接比較復(fù)雜1972年Gordon、Riesenfeld等人提出了B樣條曲線，對Bezier曲線進(jìn)行改進(jìn)，用B樣條基函數(shù)替代了Bernstein基函數(shù)。B樣條曲線克服了Bezier曲線的不足，同時保留了Bezier曲線的直觀性和凸包性，并且可以做到：①可以進(jìn)行局部修改，②曲線更逼近特征多邊形，③曲線的階次與頂點(diǎn)數(shù)無關(guān)，因而更加靈活方便。從而成了工程設(shè)計(jì)中更常用的一種擬合曲線。3.3.1B樣條的遞推定義和性質(zhì)1.定義例：二次B樣條曲線段二次B樣條曲線的n＝2，i＝0，1，2，控制多邊形有三個控制點(diǎn)P0、P1和P2因此，二次B樣曲線的表達(dá)式可以寫成如下的形式:

所以其分段混合函數(shù)可以寫成如下形式。綜合的二次B樣曲線表達(dá)式可以寫成：二次B樣條曲線段的幾何性質(zhì)起點(diǎn)p(0)位于P0P1邊的中點(diǎn)處終點(diǎn)p(1)位于P1P2邊的中點(diǎn)處起點(diǎn)切矢量沿P0P1邊的走向終點(diǎn)切矢量沿P1P2邊的走向P(1/2)正是P(0)、P1、P(1)這三點(diǎn)所構(gòu)成的三角形的中線P1Pm的中點(diǎn)，而且p(1/2)處的切線平行于兩個端點(diǎn)的連線p(0)p(1)。三個頂點(diǎn)P0P1P2確定一段二次B樣條曲線段，該段曲線是一段拋物線。一般情況下，B樣條曲線不經(jīng)過控制點(diǎn)，曲線起點(diǎn)只與前二個控制點(diǎn)有關(guān)，終點(diǎn)只與后二個控制點(diǎn)有關(guān)。

二次B樣條曲線的起點(diǎn)p(0)位于P0P1邊的中點(diǎn)處終點(diǎn)p(1)位于P1P2邊的中點(diǎn)處起點(diǎn)切矢量沿P0P1邊的走向終點(diǎn)切矢量沿P1P2邊的走向P(1/2)正是P(0)、P1、P(1)這三點(diǎn)所構(gòu)成的三角形的中線P1Pm的中點(diǎn)，而且p(1/2)處的切線平行于兩個端點(diǎn)的連線p(0)p(1)。二次B樣條曲線段的幾何性質(zhì)例：三次B樣條曲線段三次B樣條曲線段的n＝3,控制多邊形有四個控制點(diǎn)P0、P1、P2和P3，B樣條曲線段是三次多項(xiàng)式。幾何性質(zhì)曲線的起點(diǎn)p(0)位于P0P2的中點(diǎn)和P1的連線上，且距P1點(diǎn)三分之一處曲線終點(diǎn)p(1)位于P1P3的中點(diǎn)和P2的連線上，且距P2點(diǎn)三分之一處切矢量p’(0)平行于P0P2，且長度為其二分之一切矢量p’(1)P1P3，且長度為其二分之一二階導(dǎo)數(shù)p”(0)是向量P1P2和P0P1的和二階導(dǎo)數(shù)p”(1)是向量P2P3和P1P2的和p”(0)沿著中線P1Pm方向，長度等于中線的兩倍p”(1)沿著中線P2Pm方向，長度等于中線的兩倍一般情況下，B樣條曲線不經(jīng)過控制點(diǎn)，曲線起點(diǎn)只與前三個控制點(diǎn)有關(guān)，終點(diǎn)只與后三個控制點(diǎn)有關(guān)。實(shí)際上，B樣條曲線都具有這種控制點(diǎn)的鄰近影響性，這正是B樣條曲線局部可調(diào)整性好的原因。

曲線的起點(diǎn)p(0)位于P0P2的中點(diǎn)和P1的連線上，且距P1點(diǎn)三分之一處曲線終點(diǎn)p(1)位于P1P3的中點(diǎn)和P2的連線上，且距P2點(diǎn)三分之一處切矢量p’(0)平行于P0P2，且長度為其二分之一切矢量p’(1)平行于P1P3，且長度為其二分之一二階導(dǎo)數(shù)p”(0)是向量P1P2和P0P1的和二階導(dǎo)數(shù)p”(1)是向量P2P3和P1P2的和三次B樣條曲線段的幾何性質(zhì)B樣條曲線類型的劃分B樣條曲線類型的劃分曲線按其首末端點(diǎn)是否重合，區(qū)分為閉曲線和開曲線。B樣條曲線按其節(jié)點(diǎn)矢量中節(jié)點(diǎn)的分布情況，可劃分為四種類型。B樣條曲線類型的劃分均勻B樣條曲線。

節(jié)點(diǎn)矢量中節(jié)點(diǎn)為沿參數(shù)軸均勻或等距分布，所有節(jié)點(diǎn)區(qū)間長度為常數(shù)。這樣的節(jié)點(diǎn)矢量定義了均勻的B樣條基。B樣條曲線類型的劃分準(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樣條曲線解決了這個問題B樣條曲線類型的劃分分段Bezier曲線節(jié)點(diǎn)矢量中兩端節(jié)點(diǎn)具有重復(fù)度k，所有內(nèi)節(jié)點(diǎn)重復(fù)度為k-1，這樣的節(jié)點(diǎn)矢量定義了分段的Bernstein基。B樣條曲線類型的劃分B樣條曲線用分段Bezier曲線表示后，各曲線段就具有了相對的獨(dú)立性，移動曲線段內(nèi)的一個控制頂點(diǎn)只影響該曲線段的形狀，對其它曲線段的形狀沒有影響。并且Bezier曲線一整套簡單有效的算法都可以原封不動地采用。缺點(diǎn)是增加了定義曲線的數(shù)據(jù)，控制頂點(diǎn)數(shù)及節(jié)點(diǎn)數(shù)。 B樣條曲線類型的劃分B樣條曲線的性質(zhì)局部性質(zhì)在B樣條曲線中，每段B樣條曲線段受n+1個控制點(diǎn)影響，改變一個控制點(diǎn)的位置，最多影響n+1個曲線段，其它部分曲線形狀保持不變，如下圖所示。在工程設(shè)計(jì)中經(jīng)常需要對曲線進(jìn)行局部修改，B樣條曲線能很好地滿足這一要求，這就是B樣條曲線受歡迎的原因之一。

二次B樣條曲線局部頂點(diǎn)修改B樣條曲線的性質(zhì)B樣條曲線的性質(zhì)連續(xù)性B樣條曲線不同于Bezier曲線整體生成，它是分段生成的，B樣條曲線各段之間自然連接。由空間N個控制點(diǎn)生成的n次B樣條曲線是由m+1(m=N-n-1)段n次B樣條曲線段逼近而成，每個曲線段的形狀僅由點(diǎn)列中的n+1個順序排列間距相等的點(diǎn)所控制。曲線段之間自然連續(xù)。例如：空間5個控制點(diǎn)生成的3次B樣條曲線是由m＋1＝2（m＝5－3－1＝1）段3次B樣條曲線逼近而成，每個曲線段的形狀僅由點(diǎn)列中的3＋1＝4個順序排列間距相等的點(diǎn)所控制，曲線段之間自然連續(xù)。P0P1P2P3P49個控制點(diǎn)決定的二次B樣條曲線，由7段二次B樣條曲線段確定B樣條曲線的性質(zhì)B樣條曲線的性質(zhì)分段參數(shù)多項(xiàng)式 P(t)在每一區(qū)間上都是次數(shù)不高于k-1的參數(shù)t的多項(xiàng)式導(dǎo)數(shù)公式B樣條曲線的性質(zhì)變差縮減性設(shè)平面內(nèi)n+1個控制頂點(diǎn)構(gòu)成B樣條曲線P(t)的特征多邊形。在該平面內(nèi)的任意一條直線與P(t)的交點(diǎn)個數(shù)不多于該直線和特征多邊形的交點(diǎn)個數(shù)。幾何不變性B樣條曲線的形狀和位置與坐標(biāo)系的選擇無關(guān)。B樣條曲線的性質(zhì)仿射不變性即在仿射變換下，的表達(dá)式具有形式不變性。直線保持性控制多邊形退化為一條直線時，曲線也退化為一條直線。B樣條曲線的性質(zhì)B樣條曲線的性質(zhì)B樣條曲線的性質(zhì)B樣條曲線的性質(zhì)

三頂點(diǎn)重合，構(gòu)造含有尖點(diǎn)的曲線兩頂點(diǎn)重合，構(gòu)造相切于控制多邊形邊的曲線3.3.3deBoor算法欲計(jì)算B樣條曲線上對應(yīng)一點(diǎn)P(t)，可以利用B樣條曲線方程，但是采用deBoor算法，計(jì)算更加快捷。deBoor算法的導(dǎo)出deBoor算法的遞推關(guān)系如圖deBoor算法的幾何意義

j=5k=63.3.4節(jié)點(diǎn)插入算法節(jié)點(diǎn)插入算法節(jié)點(diǎn)插入算法

節(jié)點(diǎn)插入算法

節(jié)點(diǎn)插入算法3.3.5B樣條曲面

從上圖可以看出，雙三次B樣條曲面是由三次B樣條曲線交織而成。曲面生成時可以通過固定u,變化v得到一簇三次B樣條曲線；固定v，變化u得到另一簇三次B樣條曲線。與三次B樣條曲線相似，雙三次B樣條曲面一般情況下不通過控制網(wǎng)格的任何一個頂點(diǎn)。

3.4NURBS曲線與曲面B樣條曲線包括其特例的Bezier曲線都不能精確表示出拋物線外的二次曲線，B樣條曲面包括其特例的Bezier曲面都不能精確表示出拋物面外的二次曲面，而只能給出近似表示。提出NURBS方法，即非均勻有理B樣條方法主要是為了找到與描述自由型曲線曲面的B樣條方法既相統(tǒng)一、又能精確表示二次曲線弧與二次曲面的數(shù)學(xué)方法。NURBS方法的主要優(yōu)點(diǎn) 既為標(biāo)準(zhǔn)解析形狀(即前面提到的初等曲線曲面)，又為自由型曲線曲面的精確表示與設(shè)計(jì)提供了一個公共的數(shù)學(xué)形式修改控制頂點(diǎn)和權(quán)因子，為各種形狀設(shè)計(jì)提供了充分的靈活性。具有明顯的幾何解釋和強(qiáng)有力的幾何配套技術(shù)對幾何變換和投影變換具有不變性。非有理B樣條、有理與非有理Bezier方法是其特例。應(yīng)用NURBS中還有一些難以解決的問題：比傳統(tǒng)的曲線曲面定義方法需要更多的存儲空間權(quán)因子選擇不當(dāng)會引起畸變對搭接、重疊形狀的處理很麻煩。反求曲線曲面上點(diǎn)的參數(shù)值的算法，存在數(shù)值不穩(wěn)定問題(MAF方法)NURBS的含義NURBS是非均勻有理B樣條曲線（Non-UniformRationalB-Splines）的縮寫。Non-Uniform(非均勻性）：是指一個控制頂點(diǎn)的影響力的范圍能夠改變。當(dāng)創(chuàng)建一個不規(guī)則曲面的時候這一點(diǎn)非常有用。Rational(有理）：是指每個NURBS物體都可以用有理多項(xiàng)式形式表達(dá)式來定義。B-Spline(B樣條）：（參見上一節(jié)）有理樣條曲線定義有理函數(shù)是兩個多項(xiàng)式之比；有理樣條是兩個樣條函數(shù)之比。例如，有理B樣條曲線可用向量描述為：

P(t)=(∑ωiPiBi,k(t))/(∑ωiBi,k(t))。

Pi是n+1個控制點(diǎn)位置，參數(shù)ωi是控制點(diǎn)的權(quán)因子。ωi值越大，曲線越靠近該控制點(diǎn)Pi。當(dāng)所有權(quán)因子都為1時得標(biāo)準(zhǔn)B樣條曲線。構(gòu)造有理B-樣條表達(dá)式與構(gòu)造非有理表達(dá)式的步驟相同：給定控制點(diǎn)集、多項(xiàng)式次數(shù)、權(quán)因子、節(jié)點(diǎn)向量，用遞歸關(guān)系可得混合函數(shù)。通常，圖形包用非均勻節(jié)點(diǎn)向量表示式來構(gòu)造有理B樣條。這些樣條稱作NURBS。有理/非有理樣條比較有理樣條與非有理樣條相比有兩個重要的優(yōu)點(diǎn)：有理樣條提供了二次曲線的精確表達(dá)式；非有理樣條表達(dá)式為多項(xiàng)式，僅能逼近二次曲線。這使圖形包能用一個表達(dá)式(有理樣條)來模擬所有曲線形狀，無需用一個曲線函數(shù)庫去處理不同的形狀。有理樣條對于透視觀察變換是不變的。非有理樣條關(guān)于透視觀察變換是可變的。這意味著可對有理曲線上的控制點(diǎn)應(yīng)用一個透視觀察變換，來得到曲線的正確視圖，一條k次NURBS曲線可表示為一分段有理多項(xiàng)式矢函數(shù)：

參數(shù)ωi是控制頂點(diǎn)權(quán)因子，分別與n+1個控制頂點(diǎn)Pi(i=0,1,2,…,n)相聯(lián)系。首末權(quán)因子ω0,ωn>0，其余ωi≥0，以防止分母為零、保留凸包性質(zhì)及曲線不致于權(quán)因子而退化為一點(diǎn)。恰如非有理B樣條曲線，控制頂點(diǎn)Pi(i=0,1,2,…,n)順序連接成控制多邊形。Ri,k(t)是由節(jié)點(diǎn)向量t={t0,t1,t2,…,tn+k)按遞推公式?jīng)Q定的k次規(guī)范B樣條基函數(shù)。3.4.1 NURBS曲線的定義局部性質(zhì)：k次NURBS曲線上參數(shù)為u∈[ti,ti+1]的一點(diǎn)P(t)至多與k+1個控制頂點(diǎn)Pi及相聯(lián)系的權(quán)因子ωj（j=i-k,i-k+1,…,i）有關(guān)，與其它頂點(diǎn)及權(quán)因子無關(guān)；若移動k次NURBS曲線的一個控制頂點(diǎn)Pi或改變所聯(lián)系的權(quán)因子將僅僅影響定義在區(qū)間[ti,ti+k+1]上那部分曲線的形狀，對NURBS曲線的其它部分不發(fā)生影響。變差減少性質(zhì)：平面內(nèi)任一直線與B樣條曲線的交點(diǎn)個數(shù)不多于該直線與曲線控制多邊形的交點(diǎn)數(shù)目。NURBS曲線與B樣條曲線具有類似的幾何性質(zhì)：凸包性定義在非零節(jié)點(diǎn)區(qū)間[ti,ti+k]上那一曲線段位于它的k+1個控制頂點(diǎn)Pj(j=i-k,i-k+1,…,i)的凸包內(nèi)。整條NURBS曲線位于所有定義各曲線段的控制頂點(diǎn)的凸包的并集內(nèi)。權(quán)因子大于零保證了凸包性質(zhì)成立。在仿射變換和透視變換下的不變性在曲線定義域內(nèi)有與有理基函數(shù)同樣的可微性或參數(shù)連續(xù)性，即在節(jié)點(diǎn)處是k-r次可微的；NURBS曲線與B樣條曲線具有類似的幾何性質(zhì)：如果某個權(quán)因子ωi等于零，那么相應(yīng)的那個控制頂點(diǎn)Pj對曲線根本沒有影響。若ωi=→+∞，則當(dāng)t∈[ti,ti+k+1]時，P(t)=Pi；

即：控制頂點(diǎn)在曲線上。非有理與有理Bézier曲線和非有理B樣條曲線是NURBS的特例。NURBS曲線與B樣條曲線具有類似的幾何性質(zhì)：用帶權(quán)控制點(diǎn)Di(i=0,1,…,n)定義一條三維的k次NURBS非有理B樣條曲線：

將它投影到ω=1平面上，所得透視像即xy平面上一條k次NURBS曲線：3.4.2

齊次坐標(biāo)表示對平面內(nèi)給定控制頂點(diǎn)Pi=[xi

yi](i=0,1,…,n)及相聯(lián)系的權(quán)因子ωi(i=0,1,…,n)，按下列步驟定義k次NURBS曲線：確定所給控制頂點(diǎn)Pi(i=0,1,…,n)的帶權(quán)控制點(diǎn)：

Di=[ωiPi

ωi]=[ωixi

ωiyi

ωi](i=0,1,…,n)ω=1XYD2D3D1D0P2P3P1P0XYω對于三維空間內(nèi)一組給定控制頂點(diǎn)Pi=[xi

yi

zi]及相聯(lián)系的權(quán)因子ωi(i=0,1,…,n)，可用同樣的方法定義。先確定控制頂點(diǎn)Pi(i=0,1,…,n)的帶權(quán)控制點(diǎn)：

Di=[ωiPi

ωi]=[ωixi

ωiyi

ωizi

ωi](i=0,1,…,n)用帶權(quán)控制點(diǎn)Di(i=0,1,…,n)定義一條四維的k次NURBS非有理B樣條曲線：取它ω=1超平面的中心投影，即得三維空間里的一條k次NURBS曲線：3.4.2齊次坐標(biāo)表示3.4.3權(quán)因子的幾何意義權(quán)因子ωi僅影響定義在區(qū)間[ti,ti+k]上那部分曲線的形狀，對其它部分不發(fā)生影響→僅需考察整條曲線中的這部分。給定一個ωi便可得到一條曲線；如果使ωi在某個范圍內(nèi)變化，則得到一簇曲線。如果固定曲線的參數(shù)u，而使ωi變化，則NURBS曲線方程變成為以ωi為參數(shù)的直線方程。這表明：這一簇NURBS曲線上參數(shù)t值相同的點(diǎn)都位于同一直線上。P2P3P1P0P3P3權(quán)因子ωi的幾何意義把曲線與有理基函數(shù)的記號用包含權(quán)因子為變量的記號代替：當(dāng)ωi→+∞時,Ri,k(t;ωi→+∞)=1，故該直線通過控制頂點(diǎn)：

Pi=P(t;ωi→+∞)；當(dāng)ωi=0時，Ri,k(t;ωi=0)=0；這時控制頂點(diǎn)對曲線不起作用，對應(yīng)得到點(diǎn)：B=P(t;ωi=0)；當(dāng)ωi=1時，對應(yīng)得到點(diǎn)：N=P(t;ωi=1)；當(dāng)ωi≠0,1時，相應(yīng)有點(diǎn)：Bi=P(t;ωi≠0,1)?？梢宰C明：Bi點(diǎn)和N點(diǎn)分直線段之比就是權(quán)因子。即：參數(shù)值相同的直線上四點(diǎn)Pi、Bi、

M、B的交比。權(quán)因子的幾何意義3.4.4圓錐曲線的NURBS表示3.4.5NURBS曲線的修改（一）常用的方法有修改權(quán)因子、控制點(diǎn)和反插節(jié)點(diǎn)。（1）修改權(quán)因子當(dāng)保持控制頂點(diǎn)和其它權(quán)因子不變，減少或增加某權(quán)因子時，曲線被推離或拉向相應(yīng)頂點(diǎn)。3.4.5NURBS曲線的修改（二）3.4.5NURBS曲線的修改（三）3.4.5NURBS曲線的修改（四）3.4.5NURBS曲線的修改（四）控制頂點(diǎn)Pi,j(i=0,1,…,m;j=0,1,…,n)呈拓?fù)渚匦侮嚵?，形成一個控制網(wǎng)格。參數(shù)ωi,j是與控制頂點(diǎn)Pi,j聯(lián)系的權(quán)因子，規(guī)定四角頂點(diǎn)處用正權(quán)因子，即ω0,0,ωm,0,ω0,n,ωm,n>0，其余ωi,j≥0，以防止分母為零、保留凸包性質(zhì)及曲線不致因權(quán)因子而退化為一點(diǎn)。Ni,p(u)(i=0,1,…,m)和Nj,q(v)(j=0,1,…,n)分別為u向p階和v向q階B樣條基函數(shù)。1.NURBS曲面的定義：一張p×q次NURBS曲面3.4.6NURBS曲面NURBS基函數(shù)性質(zhì)有理雙變量基函數(shù)Ri,k,j,l(u,v)具有與非有理B樣條基函數(shù)相類似的函數(shù)圖形與解析性質(zhì)：局部支撐性質(zhì)：u不在區(qū)間[ui,ui+p]內(nèi)或v不在區(qū)間[vi,vj+q]內(nèi)時,Ri,k,j,l(u,v)=0；規(guī)范性：∑∑Ri,k,j,l(u,v)=1；可微性：在每個子矩形域內(nèi)所有偏導(dǎo)數(shù)存在。在重復(fù)度為r的u節(jié)點(diǎn)處沿u向是p-r-1次連續(xù)可微的；在重復(fù)度為r的v節(jié)點(diǎn)處沿v向是q-r-1次連續(xù)可微的。極值：若p,q>1時，恒有一個極大值存在。有理雙變量基函數(shù)Ri,k,j,l(u,v)是雙變量B樣條基函數(shù)的推廣，即：當(dāng)所有ωi,j=1時,Ri,k,j,l(u,v)=Ni,p(u)Nj,q(v)。NURBS曲面性質(zhì)NURBS曲線的大多數(shù)性質(zhì)都可以推廣到NURBS曲面：局部性質(zhì)是NURBS曲線局部性質(zhì)的推廣；與非有理B樣條曲面同樣的凸包性質(zhì)；在仿射與透視變換下的不變性；沿u向在重復(fù)度為r的u節(jié)點(diǎn)處沿u向是Ck-r參數(shù)連續(xù)的，沿v向在重復(fù)度為r的v節(jié)點(diǎn)處是Cl-r次參數(shù)連續(xù)的；NURBS曲面是非有理與有理Bézier曲面及非有理B樣條曲面的合適推廣。它們都是NURBS曲面的特例。類似NURBS曲線的情況，權(quán)因子ωi,j是附加的形狀參數(shù)：它們對曲面的局部推拉作用可以精確地定量確定。與非有理B樣條曲面一樣，NURBS曲面也可按所取節(jié)點(diǎn)矢量沿每個參數(shù)方向劃分為四種類型。對于開曲面，甚至于閉曲面，每個節(jié)點(diǎn)矢量的兩端節(jié)點(diǎn)通常都取成重節(jié)點(diǎn)，重復(fù)度等于該方向參數(shù)次數(shù)加1。這樣可使NURBS曲面的四個角點(diǎn)正好就是控制頂點(diǎn)的四角頂點(diǎn)，曲面在角點(diǎn)處的單向偏導(dǎo)矢正好就是邊界曲線在端點(diǎn)處的偏導(dǎo)矢。NURBS曲面權(quán)因子曲面權(quán)因子ωi,j至多影響到子區(qū)域ui<u<ui+p+1，vi<v<vj+q+1上的那部分曲面。固定參數(shù)值u∈[ui,ui+p+1]與v∈[vi,vj+q+1]，當(dāng)依次取為下列右端括號中不同值時，分別得到點(diǎn)：m=P(u,v;ωi,j=0)；n=P(u,v;ωi,j=1)；p=P(u,v;ωi,j≠0,1)?？傻玫?

(Pi,jn/nm)/(Pi,jp/pm)=ωi,jmnpP1,1即：ωi,j等于Pi,j、n、p、m四共線點(diǎn)的交比，且可推斷出：當(dāng)ωi,j增大時，曲面被拉向控制頂點(diǎn)Pi,j；反之，被推離控制頂點(diǎn)Pi,j；當(dāng)ωi,j變化時，相應(yīng)得到沿直線Pi,jm移動的p點(diǎn)；當(dāng)ωi,j趨向無窮大時，p點(diǎn)趨向與控制頂點(diǎn)Pi,j重合。3.6形體在計(jì)算機(jī)內(nèi)的表示幾何造型形體表示邊界表示模型3.6.1引言計(jì)算機(jī)中表示形體，通常用線框、表面和實(shí)體三種模型。幾何造型歷史：早期的線框表示實(shí)體造型與曲面造型70’獨(dú)立發(fā)展到互相溶合NURBS＋邊界表示正則形體對于任一形體，如果它是3維歐氏空間中非空、有界的封閉子集，且其邊界是二維流形（即該形體是連通的），我們稱該形體為正則形體，否則稱為非正則形體。一些非正則形體的實(shí)例正則形體的定義：組成三維物體的點(diǎn)的集合可以分為內(nèi)部點(diǎn)和邊界點(diǎn)兩部分，由內(nèi)部點(diǎn)構(gòu)成的點(diǎn)集閉包就是正則集，三維空間中點(diǎn)集的正則集就是三維正則形體。集合運(yùn)算（并、交、差）是構(gòu)造形體的基本方法。正則形體經(jīng)過集合運(yùn)算后，可能會產(chǎn)生懸邊、懸面等低于三維的形體。Requicha在引入正則形體概念的同時，還定義了正則集合運(yùn)算的概念。正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個正則形體，即丟棄懸邊、懸面等。集合運(yùn)算舉列

為了能夠處理非正則形體，產(chǎn)生了非正則造型技術(shù)。九十年代以來，基于約束的參數(shù)化、變量化造型和支持線框、曲面、實(shí)體統(tǒng)一表示的非正則形體造型技術(shù)已成為幾何造型技術(shù)的主流。3.5.2形體表示模型在實(shí)體模型的表示中，基本上可以分為分解表示、構(gòu)造表示和邊界表示三大類。1.分解表示將形體按某種規(guī)則分解為小的更易于描述的部分，每一小部分又可分為更小的部分，這種分解過程直至每一小部分都能夠直接描述為止。(a)將形體空間細(xì)分為小的立方體單元。

這種表示方法的優(yōu)點(diǎn)是簡單，容易實(shí)現(xiàn)形體的交、并、差計(jì)算，但是占用的存儲量太大，物體的邊界面沒有顯式的解析表達(dá)式，不便于運(yùn)算。(b)八叉樹法表示形體首先對形體定義一個外接立方體，再把它分解成八個子立方體，并對立方體依次編號為0，1，2，…，7。如果子立方體單元已經(jīng)一致，即為滿（該立方體充滿形體）或?yàn)榭眨]有形體在其中），則該子立方體可停止分解；否則，需要對該立方體作進(jìn)一步分解，再一分為八個子立方體。在八叉樹中，非葉結(jié)點(diǎn)的每個結(jié)點(diǎn)都有八個分支。

八叉樹表示法的優(yōu)點(diǎn)主要是：（1）形體表示的數(shù)據(jù)結(jié)構(gòu)簡單。（2）簡化了形體的集合運(yùn)算。只需同時遍歷參加集合運(yùn)算的兩形體相應(yīng)的八叉樹，無需進(jìn)行復(fù)雜的求交運(yùn)算。（3）簡化了隱藏線（或面）的消除，因?yàn)樵诎瞬鏄浔硎局?，形體上各元素已按空間位置排成了一定的順序。（4）分析算法適合于并行處理。八叉樹表示的缺點(diǎn)：占用的存儲多，只能近似表示形體，以及不易獲取形體的邊界信息等。2．構(gòu)造表示通常有掃描表示、構(gòu)造實(shí)體幾何表示和特征表示三種。(a)掃描表示基于一個基體（一般是一個封閉的平面輪廓）沿某一路徑運(yùn)動而產(chǎn)生形體。掃描是生成三維形體的有效方法用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問題。掃描方法不能直接獲取形體的邊界信息，表示形體的覆蓋域非常有限。

(b)構(gòu)造實(shí)體幾何表示(CSG)通過對體素定義運(yùn)算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運(yùn)算為變換或正則集合運(yùn)算并、交、差。CSG表示可以看成是一棵有序的二叉樹。其終端節(jié)點(diǎn)或是體素、或是形體變換參數(shù)。非終端結(jié)點(diǎn)或是正則的集合運(yùn)算，或是變換（平移和/或旋轉(zhuǎn)）操作，這種運(yùn)算或變換只對其緊接著的子結(jié)點(diǎn)（子形體）起作用。

CSG樹是無二義性的，但不是唯一的.CSG表示的優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；CSG表示可方便地轉(zhuǎn)換成邊界（Brep）表示；CSG方法表示的形體的形狀，比較容易修改。CSG表示的缺點(diǎn)：對形體的表示受體素的種類和對體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。對形體的局部操作不易實(shí)現(xiàn)。由于形體的邊界幾何元素（點(diǎn)、邊、面）是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。（c）特征表示從應(yīng)用層來定義形體，因而可以較好的表達(dá)設(shè)計(jì)者的意圖。從功能上可分為形狀、精度、材料和技術(shù)特征。特征是面向應(yīng)用、面向用戶的。特征模型的表示仍然要通過傳統(tǒng)的幾何造型系統(tǒng)來實(shí)現(xiàn)。不同的應(yīng)用領(lǐng)域，具有不同的應(yīng)用特征。在幾何造型系統(tǒng)中，根據(jù)特征的參數(shù)我們并不能直接得到特征的幾何元素信息，而在對特征及在特征之間進(jìn)行操作時需要這些信息。特征方法表示形體的覆蓋域受限于特征的種類。

構(gòu)造表示的特點(diǎn)：構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有限等缺點(diǎn)，但是，便于用戶輸入形體，在CAD/CAM系統(tǒng)中，通常作為輔助表示方法。3．邊界表示（BR表示或BRep表示）按照體－面－環(huán)－邊－點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。邊界表示的一個重要特點(diǎn)是在該表示法中，描述形體的信息包括幾何信息（Geometry）和拓?fù)湫畔ⅲ═opology）兩個方面。拓?fù)湫畔⒚枋鲂误w上的頂點(diǎn)、邊、面的連接關(guān)系，拓?fù)湫畔⑿纬晌矬w邊界表示的“骨架”。形體的幾何信息猶如附著在“骨架”上的肌肉。Brep表示的優(yōu)點(diǎn)是：表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的，使得繪制Brep表示的形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系；容易支持對物體的各種局部操作。便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如精度、表面粗糙度等。Brep表示的缺點(diǎn)是：數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜；Brep表示不一定對應(yīng)一個有效形體，通常運(yùn)用歐拉操作來保證Brep表示形體的有效性、正則性等。Brep表示覆蓋域大，原則上能表示所有的形體，而且易于支持形體的特征表示等，Brep表示已成為當(dāng)前CAD/CAM系統(tǒng)的主要表示方法。3.6.3形體的邊界表示模型1.邊界表示的基本實(shí)體邊界模型表達(dá)形體的基本拓?fù)鋵?shí)體包括：1.點(diǎn)。點(diǎn)是幾何造型中的最基本元素，自由曲線、曲面或其他形體均可用有序的點(diǎn)集來表示。2.邊。邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)來界定。邊的形狀（Curve）由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點(diǎn)或型值點(diǎn)來描述，也可用顯式、隱式或參數(shù)方程來描述。3.環(huán)。環(huán)（Loop）是有序、有向邊（Edge）組成的封閉邊界。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時針方向排序，內(nèi)環(huán)邊通常按順時針方向排序。4.面。面（Face）由一個外環(huán)和若干個內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。若一個面的外法矢向外，稱為正向面；反之，稱為反向面。面的形狀可以是平面或曲面。平面可用平面方程來描述，曲面可用控制多邊形或型值點(diǎn)來描述，也可用曲面方程（隱式、顯式或參數(shù)形式）來描述。對于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來表示環(huán)，集合運(yùn)算中對面的分割也可在二維參數(shù)域上進(jìn)行。5.體。體（Body）是面的并集。2.邊界表示的數(shù)據(jù)結(jié)構(gòu)翼邊數(shù)據(jù)結(jié)構(gòu)：在1972年，由美國斯坦福大學(xué)Baumgart作為多面體的表示模式提出。它用指針記錄了每一邊的兩個鄰面（即左外環(huán)和右外環(huán)）、兩個頂點(diǎn)、兩側(cè)各自相鄰的兩個鄰邊（即左上邊、左下邊、右上邊和右下邊），用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實(shí)體。

輻射邊數(shù)據(jù)結(jié)構(gòu)：為了表示非正則形體，1986年，Weiler提出了輻射邊（RadialEdge）數(shù)據(jù)結(jié)構(gòu)。輻射邊結(jié)構(gòu)的形體模型由幾何信息和拓?fù)湫畔刹糠纸M成。幾何信息有面（face）、環(huán)（loop）、邊（edge）和點(diǎn)（vertex）拓?fù)湫畔⒂心Ｐ停╩odel）、區(qū)域（region）、外殼（shell）、面引用（faceuse）、環(huán)引用（loopuse）、邊引用（edgeuse）和點(diǎn)引用（vertexuse）。點(diǎn)是三維空間的一個位置邊可以是直線邊或曲線邊，邊的端點(diǎn)可以重合。環(huán)是由首尾相接的一些邊組成，而且最后一條邊的終點(diǎn)與第一條邊的起點(diǎn)重合；環(huán)也可以是一個孤立點(diǎn)。外殼是一些點(diǎn)、邊、環(huán)、面的集合；外殼是一些點(diǎn)、邊、環(huán)、面的集合。區(qū)域由一組外殼組成。模型由區(qū)域組成。

清華大學(xué)開發(fā)的幾何造型系統(tǒng)GEMS5.0中，采用的數(shù)據(jù)結(jié)構(gòu)如圖3.歐拉操作對于任意的簡單多面體，其面(f)、邊(e)、頂點(diǎn)(v)的數(shù)目滿足歐拉公式：v-e+f=2對于任意的正則形體，引入形體的其它幾個參數(shù)：形體所有面上的內(nèi)孔總數(shù)(r)、穿透形體的孔洞數(shù)(h)和形體非連通部分總數(shù)(s)，則形體滿足公式：v-e+f=2(s-h)+r修改過程中保證各幾何元素的數(shù)目保持這個關(guān)系式不變，這一套操作就是歐拉操作。最為常用的幾種歐拉操作有：(1)mvsf(v,f)，生成含有一個點(diǎn)的面，并且構(gòu)成一個新的體。(2)kvsf(v,f)，刪除一個體，該體僅含有一個點(diǎn)的面。(3)mev(v1,v2,e)，生成一個新的點(diǎn)v2，連接該點(diǎn)到已有的點(diǎn)v1，構(gòu)成一條新的邊。(4)kev(e,v)，刪除一條邊e和該邊的一個端點(diǎn)v。(5)mef(v1,v2,f1,f2,e)，連接面f1上的兩個點(diǎn)v1、v2，生成一條新的邊e，并產(chǎn)生一個新的面。(6)kef(e)，刪除一條邊e和該邊的一個鄰面f。(7)kemr(e)，刪除一條邊e，生成該邊某一鄰面上的一新的內(nèi)環(huán)。(8)mekr(v1,v2,e)，連接兩個點(diǎn)v1、v2，生成一條新的邊e，并刪除掉v1和v2所在面上的一個內(nèi)環(huán)。(9)kfmrh(f1,f2)，刪除與面f1相接觸的一個面f2，生成面f1上的一個內(nèi)環(huán)，并形成體上的一個通孔。(10)mfkrh(f1,f2)，刪除面f1上的一個內(nèi)環(huán)，生成一個新的面f2，由此也刪除了體上的一個通孔。為了方便對形體的修改，還定義了兩個輔助的操作：公共端點(diǎn)。(11)semv(e1,v,e2)，將邊e1分割成兩段，生成一個新的點(diǎn)v和一條新的邊e2。(12)jekv(e1,e2)，合并兩條相鄰的邊e1、e2，刪除它們的公共端點(diǎn)。以上十種歐拉操作和兩個輔助操作，每兩個一組，構(gòu)成了六組互為可逆的操作?？梢宰C明：歐拉操作是有效的，即用歐拉操作對形體操作的結(jié)果在物理上是可實(shí)現(xiàn)的；歐拉操作是完備的，即任何形體都可用有限步驟的歐拉操作構(gòu)造出來。4.集合運(yùn)算正則集與正則集合運(yùn)算算子規(guī)定正則形體是三維歐氏空間中的正則集合，因此可以將正則幾何形體描述如下：設(shè)G是三維歐氏空間中的一個有界區(qū)域，且G＝bG∪iG，其中bG是G的n－1維邊界，iG是G的內(nèi)部。G的補(bǔ)空間cG稱為G的外部，此時正則形體G需滿足：1）bG將iG和cG分為兩個互不連通的子空間；2）bG中的任意一點(diǎn)可以使iG和bG連通；3）bG中任一點(diǎn)存在切平面，其法矢指向cG子空間4）bG是二維流形。設(shè)<OP>是集合運(yùn)算算子（交、并或差），R3中任意兩個正則形體A、B作集合運(yùn)算： R=A<OP>B運(yùn)算結(jié)果R仍是R3中的正則形體，則稱<OP>為正則集合算子。正則并、正則交、正則差分別記為∪*，∩*、-*。分類Tilove對分類問題的定義為：設(shè)S為待分類元素組成的集合，G為一正則集合，則S相對于G的成員分類函數(shù)為： C(S,G)={SinG，SoutG，SonG}其中， SinG=S∩iG， SoutG=S∩cG，

SonG=S∩bG，集合運(yùn)算算法包括以下幾部分：(1)求交：參與運(yùn)算的一個形體的各拓?fù)湓厍蠼?，求交的順序采用低維元素向高維元素進(jìn)行。用求交結(jié)果產(chǎn)生的新元素（維數(shù)低于參與求交的元素）對求交元素進(jìn)行劃分，形成一些子元素。(2)成環(huán)：由求交得到的交線將原形體的面進(jìn)行分割，形成一些新的面環(huán)。再加上原形體的懸邊、懸點(diǎn)經(jīng)求交后得到的各子拓?fù)湓?，形成一拓?fù)湓厣杉?3)分類：對形成的拓?fù)湓厣杉械拿恳煌負(fù)湓?，取其上的一個代表點(diǎn)，根據(jù)點(diǎn)/體分類的原則，決定該點(diǎn)相對于另一形體的位置關(guān)系，同時考慮該點(diǎn)代表的拓?fù)湓氐念愋停雌渚S數(shù)），來決定該拓?fù)湓叵鄬τ诹硪恍误w的分類關(guān)系。(4)取舍：根據(jù)拓?fù)湓氐念愋图捌湎鄬α硪恍误w的分類關(guān)系，按照集合運(yùn)算的運(yùn)算符要求，決定拓?fù)湓厥潜Ａ暨€是舍去；保留的拓?fù)湓匦纬梢粋€保留集。(5)合并：對保留集中同類型可合并的拓?fù)湓剡M(jìn)行合并，包括面環(huán)的合并和邊的合并。(6)拼接：以拓?fù)湓氐墓蚕磉吔缱鳛槠溥B接標(biāo)志，按照從高維到低維的順序，收集分類后保留的拓?fù)湓?，形成結(jié)果形體的邊界表示數(shù)據(jù)結(jié)構(gòu)。3.7求交分類幾何造型中，通常利用集合運(yùn)算（并、交、差運(yùn)算）實(shí)現(xiàn)復(fù)雜形體的構(gòu)造。集合運(yùn)算需要大量的求交運(yùn)算。如何提高求交的實(shí)用性、穩(wěn)定性、速度、精度等，對幾何造型系統(tǒng)至關(guān)重要。歷史上的觀念變化:簡單體素的精確求交，－>NURBS統(tǒng)一求交->歸類求交3.7.1求交分類簡介多面體模型這種模型的求交計(jì)算主要是線段和平面的求交，求交問題的解決相對簡單。多面體模型的缺點(diǎn)是明顯的。它只能近似表示形體，同時，復(fù)雜形體表面的離散會帶來巨大的數(shù)據(jù)量。CSG模型在這種模型中，形體通過基本體素的組合來實(shí)現(xiàn)。二次曲面的求交是這些造型系統(tǒng)中必不可少的。當(dāng)前的幾何造型系統(tǒng)，大多采用精確的邊界表示模型。在這種表示法中，形體的邊界元素和某類幾何元素相對應(yīng)，它們可以是直線、圓（圓弧）、二次曲線、Bezier曲線、B樣條曲線等，也可以是平面、球面、二次曲面、Bezier曲面、B樣條曲面等，求交情況十分復(fù)雜。二次曲面與各種自由曲面并存的混合表示模型的采用，導(dǎo)致了歸類求交思想的產(chǎn)生?！盁o處不在的求交”：GEMS實(shí)例！實(shí)體建模步驟剖析：草圖拉伸、填“體、面、環(huán)、點(diǎn)”結(jié)構(gòu)打孔，直徑為20cm:圓柱與立方體的所有面求交線，成環(huán)、重填“體面環(huán)點(diǎn)”結(jié)構(gòu)打第二個孔，直徑為18cm:圓柱與立方體的所有面、及第一個圓柱面求交線，成環(huán)、重填“體面環(huán)點(diǎn)”結(jié)構(gòu)3.7.2歸類求交策略幾何造型系統(tǒng)中，用到的幾何元素：(25種)點(diǎn)：3D點(diǎn)。線：3D直線段、二次曲線(包括圓弧和整圓、橢圓弧和橢圓、拋物線段、雙曲線段)、Bezier曲線(有理和非有理)、B樣條曲線、NURBS曲線。面：平面、二次曲面(包括球面、圓柱面、圓錐/臺面、雙曲面、拋物面、橢球面和橢圓柱面)、Bezier曲面(有理和非有理)、B樣條曲面、NURBS曲面。將幾何元素進(jìn)行歸類，利用同一類元素之間的共性來研究求交算法。同時對每一類元素，在具體求交算法中要考慮它們的特性，以提高算法的效率，發(fā)揮混合表示方法的優(yōu)勢。求交方法可分為：點(diǎn)點(diǎn)、點(diǎn)線、點(diǎn)面、線線、線面六種。3.7.3 基本的求交算法一、線與線的求交計(jì)算二次曲線與二次曲線的求交。求交策略是將坐標(biāo)系變換到該圓錐曲線的局部坐標(biāo)系下，一個圓錐曲線用隱式方程的形式表示，而另一圓錐曲線采用參數(shù)方程的形式，代入即可獲得有關(guān)參數(shù)的四次方程，，因而可計(jì)算出二者的交點(diǎn)。二次曲線與NURBS曲線求交將NURBS曲線的參數(shù)方程代入圓錐曲線的隱式方程，得到參數(shù)的一元高次方程，然后，使用一元高次方程的求根方法解出交點(diǎn)參數(shù)?；虬褕A錐曲線也表示為參數(shù)形式，轉(zhuǎn)化為兩個NURBS曲線的求交問題。NURBS曲線與NURBS曲線求交。采用離散法求初始交點(diǎn)，迭代求精確解的辦法，步驟如下：（1）初始化。依據(jù)離散精度，將NURBS曲線形成對應(yīng)的二叉樹表示，葉子結(jié)點(diǎn)是對應(yīng)于該曲線的某一離散子線段及其包圍盒，非葉子結(jié)點(diǎn)是對應(yīng)于該段NURBS曲線的包圍盒。（2）求初始交點(diǎn)。遍歷兩曲線的二叉樹，若其葉子結(jié)點(diǎn)的包圍盒相交，則將兩者的數(shù)據(jù)（曲線段中點(diǎn)的參數(shù)值，二者坐標(biāo)的平均值）存入初始交點(diǎn)隊(duì)列。（3）將初始交點(diǎn)迭代求精確交點(diǎn)。迭代方程可形象地用圖3.56表示。二、線與面的求交計(jì)算二次曲線與二次曲面的求交的求交計(jì)算，可以把二次曲線的參數(shù)形式代入二次曲面的隱式方程，計(jì)算出交點(diǎn)的參數(shù)。NURBS曲線與二次曲面的求交計(jì)算，可以把NURBS曲線的參數(shù)形式代入二次曲面的隱式方程，得到關(guān)于參數(shù)的高次方程，然后求解。NURBS曲線與NURBS曲面的求交計(jì)算（1）初始化。依據(jù)離散精度，將NURBS曲線離散成二叉樹的形（2）求初始交點(diǎn)。遍歷該二叉樹和四叉樹，如果曲線二叉樹葉子結(jié)點(diǎn)的包圍盒與曲面四叉樹的葉子結(jié)點(diǎn)的包圍盒有交點(diǎn)，則將子曲線段中點(diǎn)的參數(shù)值、子曲面片的中心點(diǎn)的坐標(biāo)值與參數(shù)值作為初始交點(diǎn)，記錄到初始交點(diǎn)點(diǎn)列中去。（3）對初始交點(diǎn)進(jìn)行迭代，形成精確交點(diǎn)?？捎门ｎD迭代法求解精確交點(diǎn)。設(shè)NURBS曲線為C(t)，NURBS曲面為S(u,v)，則在交點(diǎn)處應(yīng)滿足：3.7.3 基本的求交算法三、曲面和曲面的求交曲線曲面求交的基本方法主要有:代數(shù)方法幾何方法離散方法跟蹤方法1．代數(shù)方法利用代數(shù)運(yùn)算，特別是求解代數(shù)方程的方法求出曲面的交線。根據(jù)參與求交的兩曲面的表示形式的不同，可以把求交分為三種情況。隱式表示和參數(shù)表示的曲面求交，通過把參數(shù)方程代入隱式方程的方法，可以將交線表示為g(u,v)=0的形式。此時得到的交線方程是平面代數(shù)曲線方程，可根據(jù)平面代數(shù)曲線理論的方法求解交線。兩個曲面都是參數(shù)表示的情形，只需要將其中之一隱式化，然后用前面的方法求解。而參數(shù)多項(xiàng)式或有理多項(xiàng)式曲面的隱式化通過消元來實(shí)現(xiàn)。兩個曲面都是隱式曲面。一種方法是將其中一個曲面參數(shù)化，然后用第一種情況來求解。但是，一般情況下這種參數(shù)化很困難，對于某些情況可以采用另外的方法計(jì)算參數(shù)化的曲面。代數(shù)法的弱點(diǎn)是對誤差很敏感這是因?yàn)榇鷶?shù)法經(jīng)常需要判別某些量是否大于零、等于零或小于零，而在計(jì)算機(jī)中的浮點(diǎn)數(shù)近似表示的誤差常常會使這種判別出現(xiàn)錯誤。代數(shù)法實(shí)例：圓與橢圓求交，化為求解4次方程，有公式解。圓與圓環(huán)求交，化為求解8次方程，迭代求解。8次方程達(dá)到求解，不穩(wěn)定。2．幾何方法利用幾何的方法，對參與求交的曲面的形狀大小、相互位置以及方向等進(jìn)行計(jì)算和判斷，識別出交線的形狀和類型，從而可精確求出交線。幾何求交適應(yīng)性不是很廣，一般僅用于平面以及二次曲面等簡單曲面的求交對于一些交線退化或相切的情形，交線往往是點(diǎn)、直線或圓錐曲線，用幾何方法求交可以更加迅速和可靠。幾何法實(shí)例：平面與圓柱求交1.平面、圓柱參數(shù)的合法性檢查2.平面變換到圓柱的局部坐標(biāo)系3.幾何求交： ①如果平面與圓柱平行，不交或交于兩條直線 ②如果平面與圓柱垂直，不交或交于一個圓

③否則，交于橢圓或橢圓弧先求出平面與無限長圓柱交得的橢圓(在圓柱的局部坐標(biāo)系下)根據(jù)橢圓在長軸上的兩點(diǎn)與圓柱的關(guān)系，確定交于點(diǎn)、橢圓、橢圓弧等3．離散方法離散方法求交是利用分割的方法，將曲面不斷離散成較小的曲面片，直到每一子曲面片均可用比較簡單的面片，然后用這些簡單面片求交得一系列交線段，連接這些交線段即得到精確交線的近似結(jié)果。離散求交一般包括下面的過程：用包圍盒作分離性檢查排除無交區(qū)域；根據(jù)平坦性檢查判斷是否終止離散過程；連接求出的交線段作為求交結(jié)果。由于Bezier曲面，B樣條曲面具有離散性質(zhì)，使得它們最適合于離散法求交。缺點(diǎn)：離散法求出的交線逼近精度不高。如果要求的精度較高，需要增加離散層數(shù)。這將大大增加了數(shù)據(jù)儲存量和計(jì)算量。處于不同離散層數(shù)的相鄰子曲面片，由它們產(chǎn)生的交線段可能會出現(xiàn)裂縫。高度估計(jì)問題H4．跟蹤方法通過先求出初始交點(diǎn)，然后從已知的初始交點(diǎn)出發(fā)，相繼跟蹤計(jì)算出下一交點(diǎn)，從而求出整條交線的方法。跟蹤法的本質(zhì)是構(gòu)造交線滿足的微分方程組，先求出滿足方程組的某個某個初值解，通過數(shù)值求解微分方程組的方法來計(jì)算整個交線。跟蹤方法在計(jì)算相繼交點(diǎn)的時候，利用了曲面的局部微分性質(zhì)，一般采用數(shù)值迭代的方法求解，使得計(jì)算效率較高。跟蹤法求交中考慮的主要問題包括：如何求出初始交點(diǎn)并保證每一交線分支都有初始交點(diǎn)被求出；如何計(jì)算奇異情況下的跟蹤方向以及合理選取跟蹤的前進(jìn)步長；如何處理相切的情況。跟蹤法實(shí)例：MAF方法曲線－曲線求交近似交點(diǎn)，切線求交，投影MAF與Newton法的比較Newton法MAF與Newton法的比較MAF法QP(t)P(t0)3.8實(shí)體造型系統(tǒng)簡介在早期開發(fā)的實(shí)體造型系統(tǒng)中，值得提及的是劍橋大學(xué)的BUILD-1系統(tǒng)。該研究小組的一部分人組建了ShapeData公司，并開發(fā)出實(shí)體造型系統(tǒng)Romulus，Romulus孕育了最著名的兩個實(shí)體造型系統(tǒng)開發(fā)環(huán)境：Parasolid和ACIS。3.7.1Parasolid系統(tǒng)：Solidworks3.7.2ACIS系統(tǒng):Autodesk,Solidedge3.8.1Parasolid的主要功能Parasolid有較強(qiáng)的造型功能，但是只能支持正則實(shí)體造型。主要功能包括：Parasolid采用自由曲面和解析曲面的混合表示，共提供了10種標(biāo)準(zhǔn)的曲面類型和7種標(biāo)準(zhǔn)的曲線類型，并且是完全集成的。Parasolid可用簡單的方法生成復(fù)雜的實(shí)體，實(shí)體之間可有多種方式的操作。用戶可用自己理解的工程特征進(jìn)行設(shè)計(jì)能夠提供非拓?fù)浜头菐缀螖?shù)據(jù)，稱為屬性屬性包括系統(tǒng)定義的屬性和用戶定義的屬性兩種，且依附于模型實(shí)體（Entities）。支持局部操作。包括：改變面幾何、變換面幾何、使面成錐形、擺動面、掃描面及刪除面。提供了多半徑、變半徑的過渡功能。3.8.1Parasolid的模型結(jié)構(gòu)模型實(shí)體包括三種：拓?fù)?、幾何和相關(guān)數(shù)據(jù)1．拓?fù)鋵?shí)體體（Body）：Parasolid模型通常包括一個或多個體（Bodies）殼（Shell）：殼是實(shí)體（Solid）和空氣之間封閉的邊界面（Face）、邊（Edge）和頂點(diǎn)（Vetex）翼（Fin）：翼（Fins）表示一條邊的一側(cè)每一條邊有一個左翼和一個右翼環(huán)（Loop）：由一個面上封閉的翼組成。裝配件（Assembly）和實(shí)例