第五章幾何造型技術(shù)5.1曲線的表示5.2曲面的表示5.3實(shí)體的表示5.4分形

5.1曲線的表示

5.1.1繪制曲線的基本方法

在手工操作繪制曲線時，除了圓弧類曲線可以直接借助于工具（圓規(guī)）來畫出外，其他的曲線一般都需先確定幾個點(diǎn)，然后借用曲線板分段繪出。這也是用計算機(jī)來繪制曲線的基本原理。由于計算機(jī)圖形輸出設(shè)備特有的工作特點(diǎn)，曲線一般是離散成直線再畫出（見圖5.1）。圖5.1由直線段逼近得到曲線參數(shù)法表示對于多值曲線尤為重要。例如對于一個圓，它的標(biāo)準(zhǔn)方程是x2+y2=r2，可寫成：(5.1)圓的參數(shù)方程可表示為(5.2)這兩種表示方法在繪圖的時候存在著明顯的差別，如圖5.2所示。圖5.2兩種繪圖方式5.1.2參數(shù)曲線

1.曲線的分類

曲線和曲面的表示方程有參數(shù)表示和非參數(shù)表示之分，非參數(shù)表示又分為顯式表示和隱式表示。

平面曲線顯式表示的一般形式為

y=f(x)

(5.3)顯式表示的缺點(diǎn)有：

（1）不能表示封閉或多值曲線。

（2）與坐標(biāo)系的選取相關(guān)。

（3）會出現(xiàn)斜率為無窮大的情形，不便于編程。

平面曲線隱式表示的一般形式為

F(x，y)=0

(5.4)隱式表示的優(yōu)點(diǎn)有：

（1）可表示封閉或多值曲線。

（2）便于點(diǎn)和曲線的位置判斷。

隱式表示的缺點(diǎn)有：

（1）求值困難。

（2）與坐標(biāo)系的選取相關(guān)。

（3）會出現(xiàn)斜率為無窮大的情形，不便于編程。平面曲線也可用參數(shù)表示。假定用t表示參數(shù)，則平面曲線上任一點(diǎn)P可表示為

P(t)=［x(t)，y(t)］(5.5)空間曲線上任一點(diǎn)P可表示為

P(t)=［x(t)，y(t)，z(t)］(5.6)

曲線、曲面在表示時，參數(shù)表示比顯式、隱式表示有更多的優(yōu)越性，它主要表現(xiàn)在以下七個方面：（1）可以滿足幾何不變性的要求。

（2）有更大的自由度來控制曲線曲面的形狀。例如一條平面三次曲線可顯式表示為

y=ax3+bx2+cx+d

(5.7)式中有4個系數(shù)控制此曲線的形狀，而平面三次曲線的參數(shù)表達(dá)式則為：(5.8)式中有8個系數(shù)控制此曲線的形狀。（3）對非參數(shù)方程表示的曲線、曲面進(jìn)行變換時，必須對曲線、曲面上的每個型值點(diǎn)進(jìn)行幾何變換，而對參數(shù)表示的曲線、曲面進(jìn)行變換時，可對其參數(shù)方程直接進(jìn)行幾何變換。

（4）便于處理斜率為無窮大的情形，不會因此而中斷計算。

（5）參數(shù)方程中，代數(shù)、幾何相關(guān)和無關(guān)的變量是完全分離的，而且變量個數(shù)沒有限制，從而便于用戶把低維空間中的曲線、曲面擴(kuò)展到高維空間。這種變量分離的特點(diǎn)使得用數(shù)學(xué)公式處理幾何分量變得容易。

（6）規(guī)格化的參數(shù)變量t∈［0，1］，它使得相應(yīng)的幾何分量有界，而不必用另外的參數(shù)去定義邊界。

（7）易于用矢量和矩陣表示幾何分量，可簡化計算。

2.曲線的基本概念

一條用參數(shù)表示的三維曲線是一個有界點(diǎn)集，它可寫成一個帶參數(shù)的、連續(xù)的、單值的數(shù)學(xué)函數(shù)，其形式為(5.9)

1）位置矢量

曲線上任一點(diǎn)的位置矢量可表示為

P(t)=［x(t)，y(t)，z(t)］（5.10）

其一階、二階和k階導(dǎo)數(shù)矢量（如果存在的話）分別表示為（5.11）

2）切矢量

曲線上任一點(diǎn)的切矢量（如果存在的話）表示為（5.12）如果選擇弧長s作為參數(shù)，那么根據(jù)弧長微分公式，有：（5.13）引入?yún)?shù)t，上式可改寫為：（5.14）為了方便，數(shù)學(xué)上一般取s增加的方向?yàn)閠增加的方向?？紤]到矢量的模為非負(fù)，所以有：（5.15）即弧長s是t的單調(diào)增函數(shù)，故其存在反函數(shù)t(s)，且與其一一對應(yīng)。由此得：

P(t)=P(t(s))=P(s)（5.16）于是得：（5.17）即P(t)關(guān)于弧長s的導(dǎo)向矢量是單位矢量。

3）法矢量

對于空間參數(shù)曲線上任一點(diǎn)，所有垂直切矢T的矢量構(gòu)成一平面，該平面成為曲線在該點(diǎn)的法平面。

若曲線上任一點(diǎn)的單位切矢為T，因?yàn)椋跿(s)］2=1，兩邊對s求導(dǎo)矢，可得

2T(s)·T′(s)=0（5.18）對于一般參數(shù)t，有：(5.19)T（切矢）、N（主法矢）和B（副法矢）構(gòu)成了曲線上的活動標(biāo)架。N和B構(gòu)成的平面稱為法平面；N和T構(gòu)成的平面稱為密切平面；

B和T構(gòu)成的平面稱為從切平面。

4）曲率和撓率

由于dT/ds與N平行，若令T′=kN，則(5.20)其中，Δθ為相鄰兩切線的夾角。k為曲線的曲率，其幾何意義是曲線的單位切矢對弧長的轉(zhuǎn)動率，它與主法矢同向。曲率的倒數(shù)ρ=1/k稱為曲率半徑。又因?yàn)锽(s)·T(s)=0，兩邊對s求導(dǎo)，得

B′(s)·T(s)+B(s)·T′(s)=0（5.21）將T′=kN代入上式，并注意到B(s)·N(s)=0，可得到：B′(s)·T(s)=0（5.22）因?yàn)椋跙(s)］2=1，所以兩邊對s求導(dǎo)，可得到B′(s)·B(s)=0，可見B′(s)既垂直于T(s)，又垂直B(s)，故

B′(s)∥N(s)（5.23）

再令B′(s)=－τN(s)，τ稱為撓率。因?yàn)?5.24)其中，Δj為相鄰兩副法矢間的夾角。所以，撓率的絕對值的概念是副法線方向（或密切平面）對于弧長的轉(zhuǎn)動率。撓率τ大于0、等于0和小于0分別表示曲線為右旋空間曲線、平面曲線和左旋空間曲線。

同樣，對N(s)=B(s)×T(s)兩邊求導(dǎo)，可以得到：

N′(s)=－kT(s)+τB(s)（5.25）將T′、

N′、B′和T、N、B的關(guān)系寫成矩陣形式,為（5.26）對于一般參數(shù)t，曲率k和撓率τ的計算公式如下：（5.27）

1)插值、擬合和逼近

給定一組有序數(shù)據(jù)點(diǎn)Pi(i=0，1，…，n），構(gòu)造一條曲線順序通過這些數(shù)據(jù)點(diǎn)，稱為對這些數(shù)據(jù)點(diǎn)的插值，所構(gòu)造的曲線稱為插值曲線。

（1）線性插值。假設(shè)給定函數(shù)f(x)在兩個不同點(diǎn)x1和

x2的值，用一個線性函數(shù)y=f(x)=ax+b

近似代替f(x)，稱f(x)為f(x)的線性插值函數(shù)。其中線性函數(shù)的系數(shù)a，b通過條件f(x1)=y1，f(x2)=y2確定。（2）拋物線插值。拋物線插值又稱為二次插值。設(shè)

已知f(x)在三個互異點(diǎn)x1、x2、

x3的函數(shù)值為y1、y2、y3，

要求構(gòu)造一函數(shù)y=f(x)=ax2+bx+c，使f(x)在節(jié)點(diǎn)xi(i=1，

2，3)處與f(x)在xi處的值相等。由此，可構(gòu)造f(xi)=f(xi)=

yi(i=1，2，3)的線性方程組，求得系數(shù)a，b，c，即構(gòu)造了f(x)的二次插值函數(shù)f(x)。

2）光順（fairing）

光順通常的含義是指曲線的拐點(diǎn)不能太多，因?yàn)榍€拐來拐去就會導(dǎo)致曲線不順。對平面曲線而言，相對光順的條件是：

（1）具有二階幾何連續(xù)（G2）。

（2）不存在多余拐點(diǎn)和奇異點(diǎn)。

（3）曲率變化較小。

4.參數(shù)化

過三個點(diǎn)P0、P1、

P2構(gòu)造參數(shù)表示的插值多項式曲線可以有無數(shù)條，這是因?yàn)閰?shù)t在［0，1］區(qū)間的分割可

以有無數(shù)種，即P0、P1、

P2可對應(yīng)不同的參數(shù)，例如，

t0=0，t1=1/2，t2=1或t0=0，t1=1/3，t2=1，其中，每個參數(shù)值稱為一個節(jié)點(diǎn)（knot）。

1）均勻參數(shù)化（等距參數(shù)化）

使每個節(jié)點(diǎn)區(qū)間長度Δi=ti+1－ti，i=0，1，…，n－1為正常數(shù)d，節(jié)點(diǎn)在參數(shù)軸上呈等距分布：ti+1=ti+d。

2）累加弦長參數(shù)化其中，ΔPi=Pi+1－Pi為向前差分矢量，即弦邊矢量。這種參數(shù)化如實(shí)反映了型值點(diǎn)按弦長的分布情況，能夠克服在型值點(diǎn)按弦長分布的情況下采用均勻參數(shù)化所出現(xiàn)的問題。

3）向心參數(shù)化(5.29)累加弦長參數(shù)化沒有考慮相鄰弦邊的拐折情況，而向心參數(shù)化法假設(shè)在一段曲線弧上的向心力與曲線切矢從該弧段始端至末端的轉(zhuǎn)角成正比，加上一些簡化假設(shè)，可得到向心參數(shù)化法。該參數(shù)化特別適用于非均勻型值點(diǎn)分布的情況。

4）修正弦長參數(shù)化其中：(5.30)(5.31)弦長修正系數(shù)Ki≥1。從上述公式可知，與前后相鄰弦長|ΔPi－2|和|ΔPi|相比，若|ΔPi－1|越小，且與前后相鄰弦邊的夾角的外角θi－1和θi（不超過π/2）越大，則修正系數(shù)Ki就越大。

由上述參數(shù)化方法得到的參數(shù)區(qū)間一般是［t0，tn］≠［0，1］。通常將參數(shù)區(qū)間［t0，tn］規(guī)格化為［0，1］，只需對參數(shù)區(qū)間作如下處理即可：（5.32）

5.參數(shù)曲線的代數(shù)和幾何形式

1）代數(shù)形式

三次參數(shù)曲線的代數(shù)形式是：（5.33）方程組中的12個系數(shù)唯一地確定了三次參數(shù)曲線的空間位置和形狀，上述代數(shù)形式寫成矢量式是：（5.34）

2）幾何形式

描述參數(shù)曲線的條件有端點(diǎn)位矢、端點(diǎn)切矢和曲率等。對三次參數(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，代入式（5.34)可得：（5.35）將式（5.35）代入式（5.34），整理得：(5.36)令(5.37)將F0、F1、G0、G1代入式（5.36），得到：（5.38）式（5.38）是三次Hermite（Ferguson）曲線的幾何形式，幾何系數(shù)是P0、P1、P0′和P1′。F0、F1、G0、G1稱為調(diào)合函數(shù)（或混合函數(shù)），即該形式下的三次Hermite基，它具有如下性質(zhì)：

F0和F1專門控制端點(diǎn)的函數(shù)值對曲線的影響，而同端點(diǎn)的導(dǎo)數(shù)值無關(guān)；G0和G1則專門控制端點(diǎn)的一階導(dǎo)數(shù)值對曲線形狀的影響，同端點(diǎn)的函數(shù)值無關(guān)。也可以說，F(xiàn)0

和G0控制左端點(diǎn)的影響，

F1和G1控制右端點(diǎn)的影響。

6.連續(xù)性

曲線間連接的光滑度量準(zhǔn)則有兩種：一種是函數(shù)的可微性，它使得組合曲線在連接處具有直到n階連續(xù)導(dǎo)矢，

即n階連續(xù)可微，這類光滑度量稱為Cn或n階參數(shù)連續(xù)性；

另一種稱為幾何連續(xù)性，組合曲線在連接處滿足不同于

Cn的某一組約束條件，稱為具有n階幾何連續(xù)性，簡記為

Gn。曲線光滑性的這兩種度量方法并不矛盾，Cn連續(xù)包含在Gn連續(xù)之中。5.1.3

Bézier曲線

1.Bézier曲線的數(shù)學(xué)表達(dá)式

Bézier曲線的形狀是通過一組多邊折線（特征多邊形）的各頂點(diǎn)唯一地定義出來的。在這組頂點(diǎn)中：

（1）只有第一個頂點(diǎn)和最后一個頂點(diǎn)在曲線上。

（2）其余的頂點(diǎn)用于定義曲線的導(dǎo)數(shù)、階次和形狀。

（3）第一條邊和最后一條邊表示了曲線在兩端點(diǎn)處的切線方向。

圖5.3是一些Bézier多邊形折線和相應(yīng)的Bézier曲線。圖5.3

Bézier多邊形折線和Bézier曲線

Bézier曲線是由多項式混合函數(shù)推導(dǎo)出來的，通常n+1個頂點(diǎn)定義一個n次多項式。其數(shù)學(xué)表達(dá)式為(5.40)式中，P0，P1，…，Pn為Bézier曲線的控制頂點(diǎn)，順次相連形成的多邊形叫做Bézier曲線的控制多邊形。Bi，n(t)是n次Bernstein基函數(shù)，其表達(dá)式如下：(5.41)如果約定：00=1，0!=1，則當(dāng)t=0時，B0，

n(t)=1，

Bi，n(t)=0，i≠0；當(dāng)t=1時，Bn，n(t)=1，Bi，n(t)=0，

i≠n。故(5.42)所以說“只有第一個頂點(diǎn)和最后一個頂點(diǎn)在曲線上”，即Bézier曲線只通過多邊折線的起點(diǎn)和終點(diǎn)。下面我們通過對基函數(shù)的求導(dǎo)來分析兩端切矢的情況。由于得(5.43)(5.44)從而有(5.45)Bézier曲線P(t)與它的控制多邊形的關(guān)系如圖5.4所示。其中，控制多邊形P0P1…Pn是P(t)的大致形狀的勾畫，P(t)是對P0P1…Pn的逼近。圖5.4Bézier曲線與控制多邊形的關(guān)系

2.二次和三次Bézier曲線

1)二次Bézier曲線

三個頂點(diǎn)P0，P1，P2可定義一條二次（n=2）Bézier曲線，其相應(yīng)的Bernstein基函數(shù)為(5.46)所以，根據(jù)(5.47)可得二次Bézier曲線的表達(dá)形式為(5.48)將其寫成矩陣形式，則為：(5.49)如圖5.5所示，這說明曲線經(jīng)過其控制三邊形中線的中點(diǎn)，綜合兩端點(diǎn)切矢的性質(zhì)可知，二次Bézier曲線是一條拋物線。圖5.5二次Bézier曲線

2）三次Bézier曲線

四個頂點(diǎn)P0、P1、P2、P3可定義一條三次Bézier曲線：(5.51)

3.Bézier曲線的性質(zhì)

（1）仿射不變性：Bézier曲線在仿射變換下不變。這表明下述兩種操作會產(chǎn)生相同的結(jié)果：①計算P(t)，然后作仿射變換；②對控制多邊形作仿射變換，然后求參數(shù)為t的點(diǎn)。仿射不變性在圖形的生成與變換中非常有用。

(2)仿射參數(shù)變換下的不變性。

(3)凸包性：Bézier曲線P(t)位于控制多邊形的凸包之中。凸包性的一個結(jié)果是平面控制多邊形生成的Bézier曲線是平面曲線；另外的一個重要性在于干涉檢查。

（4）端點(diǎn)性質(zhì)：（5）對稱性：保持曲線各控制頂點(diǎn)位置不變，只把次序完全顛倒所得到的新頂點(diǎn)記為Pi=Pn－i，那么可得到一條與原曲線一樣的Bézier曲線，不同的是新曲線具有與原曲線相反的定向，即(5.53)（6）變差縮減性（VD性質(zhì)）：任一平面與Bézier曲線的交點(diǎn)數(shù)目不多于平面與控制多邊形的交點(diǎn)

數(shù)目。

（7）保形性：Bézier曲線的形狀酷似控制多邊形的形狀，特別的是，若控制多邊形為一平面凸多邊形，則定義的Bézier曲線是一條凸曲線。（8）線性精度：假設(shè)控制頂點(diǎn)Pi

（i=0，1，…，n），均勻分布在連接p和q的直線段上，即那么(5.55)(5.54)

4.Bézier曲線的求值

Bézier曲線是采用最為廣泛的參數(shù)曲線之一。因此，關(guān)于它的快速生成算法也是研究最多的，廣泛采用的生成算法是deCasteljau算法。記為：(5.56)那么

P(t)=Pn0

(5.57)

deCasteljau算法的幾何意義是：按照t:1－t的比例遞歸分割控制多邊形的每一條邊，直至其為一個點(diǎn)，即為曲線上參數(shù)為t的點(diǎn)，如圖5.6所示。圖5.6

deCasteljau算法5.1.4

B樣條曲線

1.從Bézier曲線到B樣條曲線

Bézier曲線在應(yīng)用中的不足有以下幾點(diǎn)：

（1）缺乏靈活性。一旦確定了特征多邊形的頂點(diǎn)數(shù)（m個），也就決定了曲線的階次（m－1次），無法更改。（2）控制性差。當(dāng)頂點(diǎn)數(shù)較多時，曲線的階次會比較高，此時，特征多邊形對曲線形狀的控制將明顯減弱。（3）不易修改。由曲線的混合函數(shù)可看出，其值在開區(qū)間(0，1)內(nèi)均不為零。因此，所定義的曲線在（0<t<1）區(qū)間內(nèi)的任何一點(diǎn)都要受到全部頂點(diǎn)的影響，這使得對曲

線進(jìn)行局部修改不可能實(shí)現(xiàn)(在外形設(shè)計中，局部修改是要隨時進(jìn)行的）。為了克服Bézier曲線存在的不足，Gordon等人對Bézier曲線做了拓展。就外形設(shè)計的需求而言，希望新的曲線具有如下優(yōu)點(diǎn)：

（1）易于進(jìn)行局部修改。

（2）更逼近特征多邊形。

（3）曲線是低階次的。

于是，Gordon等人用n次B樣條基函數(shù)替換了Bernstein基函數(shù)，構(gòu)造了稱為B樣條曲線的新型曲線。

2.B樣條基函數(shù)

由遞推公式定義的函數(shù)Ni，k(u)稱為節(jié)點(diǎn)向量U上的k階（k－1次）B樣條基函數(shù)，遞推公式如下：(5.59)(5.60)

3.B樣條基函數(shù)的性質(zhì)

·局部支撐性。其表示形式為稱區(qū)間［ui，ui+k］為Ni，k(u)的支撐區(qū)間。（5.61）

·權(quán)性（歸一性）。其表示形式為（5.62）（5.63）或者為

·分段多項式。Ni，k(u)在每一長度非零的區(qū)間［uj，uj+1)上都是次數(shù)不超過k－1的多項式。

· 連續(xù)性。Ni，k(u)在區(qū)間(uj，uj+1)上C∞連續(xù)，在節(jié)點(diǎn)uj處Ck－r－1次連續(xù)，其中r為節(jié)點(diǎn)uj的重數(shù)。

·導(dǎo)數(shù)計算公式為

（5.64）

4.B樣條曲線的數(shù)學(xué)表達(dá)式

給定n+1(n≥k)個空間點(diǎn)di（i=0，1，…，n），曲線的參數(shù)多項式為(5.65)稱其為k階k－1次B樣條曲線，折線d0d1…dn稱為P(u)的控制多邊形，di稱作控制頂點(diǎn)或deBoor點(diǎn)。Ni，k(u)為節(jié)點(diǎn)向量U={u0≤u1≤…≤un+k}確定的k階樣條基函數(shù)。

5.均勻B樣條曲線

若uj=j－k+1，則稱相應(yīng)的B樣條基函數(shù)為均勻B樣條基函數(shù)，由其定義的B樣條曲線為均勻B樣條曲線。由于：

Ni，k(u)=N0，

k(u－i)

(5.66)

基于這一性質(zhì)，我們只需建立一個節(jié)點(diǎn)區(qū)間上B樣條基函數(shù)的數(shù)學(xué)表示。k階B樣條基函數(shù)在節(jié)點(diǎn)區(qū)間［uk，uk+1］上的顯式表示為(5.67)

1）三階均勻B樣條曲線三階均勻B樣條基函數(shù)的顯式表示如下：(5.68)給定n+1個空間點(diǎn)di（i=0，1，…，n），定義一條三階均勻B樣條曲線，它由n－1段構(gòu)成。其每一段的顯式表示為曲線Pj(t)的端點(diǎn)性質(zhì)如下：(5.71)且有：(5.73)(5.72)與上述各式所表達(dá)的性質(zhì)相符的曲線如圖5.7所示。圖5.7一段三階B樣條曲線由此可知，三階均勻B樣條曲線的每一段為順序三個控制頂點(diǎn)定義的拋物線，即為一平面曲線，整條曲線相鄰兩段在連接點(diǎn)處C1連續(xù)。由于順序四個控制頂點(diǎn)可以不共面，相鄰兩段曲線可以在不同的平面內(nèi)，因而整條曲線可以為空間曲線。這就突破了二次Bézier曲線只能為平面曲線的限制。

利用每一段曲線的端點(diǎn)性質(zhì)及拋物線的特點(diǎn)，可以由控制多邊形給出三階均勻B樣條曲線的大致圖形，如圖5.8所示。圖5.8分段三階B樣條曲線我們也可以將三階均勻B樣條曲線的每一段表示成Bézier形式。設(shè)Pj(t)的Bézier表示為因?yàn)橥磺€段的兩種不同表示形式可以相互轉(zhuǎn)換，所以有以下關(guān)系：因而有即(5.77)

2）四階均勻B樣條曲線

四階均勻B樣條基函數(shù)的顯式表示如下：(5.78)給定n+1個空間點(diǎn)di（i=0，1，…，n），定義的一條四階均勻B樣條曲線由n－2段構(gòu)成。其每一段的顯式表示為曲線Pj(t)具有的端點(diǎn)性質(zhì)如下：(5.80)根據(jù)以上幾何性質(zhì)，可以大致確定出該曲線段的圖

形，如圖5.9所示。圖5.9一段四階均勻B樣條曲線四階均勻B樣條曲線的每一段由順序四個控制頂點(diǎn)所確定，相鄰兩段曲線在連接點(diǎn)處C2連續(xù)，如圖5.10所示。圖5.10分段四階均勻B樣條曲線

B樣條曲線是一種非常靈活的曲線，曲線的局部形狀受相應(yīng)頂點(diǎn)的控制能很直觀地看出。如果將這些頂點(diǎn)控制技術(shù)運(yùn)用得好，可以使整個B樣條曲線在某些部位滿足一些特殊的技術(shù)要求。這些技術(shù)要求包括：

①可以在曲線中構(gòu)造一段直線；

②使曲線與特征多邊形相切；

③使曲線通過指定點(diǎn)；

④指定曲線的端點(diǎn)；

⑤指定曲線端點(diǎn)的約束條件。

6.deBoor－Cox算法

現(xiàn)討論B樣條曲線P(u)的計算問題，對于給定的參數(shù)

u∈［uj，uj+1)(k－1≤j≤n)，由B樣條基函數(shù)Ni，k(u)的遞推公式：(5.81)將P(u)化簡如下：令則式（5.82）可表示為(5.83)(5.84)運(yùn)用deBoor-Cox算法，由控制頂點(diǎn)：d0，

d1，…，dn求P(u)值的遞推過程的形式如下：

7.B樣條曲線分類

（1）均勻B樣條曲線（UniformBsplineCurve）：

節(jié)點(diǎn)序列中節(jié)點(diǎn)沿參數(shù)軸均勻分布，所有節(jié)點(diǎn)區(qū)間的長度為Δi=ui+1－ui=const>0（i=0，1，…，n+k－1）。這樣的節(jié)點(diǎn)矢量定義了均勻B樣條基函數(shù)，對應(yīng)的B樣條曲線稱為均勻B樣條曲線。（2） 準(zhǔn)均勻B樣條曲線（QuasiUniformBsplineCurve）：節(jié)點(diǎn)序列中兩端節(jié)點(diǎn)為k重，即u0=u1=…=uk－1，un+1=un+2=…=un+k，所有內(nèi)節(jié)點(diǎn)為單節(jié)點(diǎn)且均勻分布。曲線定義域［uk－1，un+1］內(nèi)所有節(jié)點(diǎn)區(qū)間的長度Δi=ui+1－ui=const>0（i=k－1，k，…，n）。它與均勻B樣條曲線定義域內(nèi)節(jié)點(diǎn)的分布相同，差別僅在于兩個端節(jié)點(diǎn)。這樣的節(jié)點(diǎn)矢量定義了準(zhǔn)均勻B樣條基函數(shù)，對應(yīng)的B樣條曲線稱為準(zhǔn)均勻B樣條曲線。（3）分段Bézier曲線（PiecewiseBézierCurve）：

節(jié)點(diǎn)序列中兩端節(jié)點(diǎn)為k重，所有內(nèi)節(jié)點(diǎn)均為k－1重節(jié)點(diǎn)，即u0=u1=…=uk－1，un+1=un+2=…=un+k，且(5.86)（4）一般非均勻B樣條曲線（GeneralNonUniformBsplineCurve）:對于這種類型曲線，任意分布的節(jié)點(diǎn)序列U：u0≤u1≤…≤un+k，只要它在數(shù)學(xué)上成立（節(jié)點(diǎn)序列非遞減、每一內(nèi)節(jié)點(diǎn)的重數(shù)小于k），都是可選的。這樣的節(jié)點(diǎn)矢量定義了一般非均勻B樣條基函數(shù)，對應(yīng)的B樣條曲線稱為一般非均勻B樣條曲線。由此可見，前三種類型的B樣條曲線都可作為特例包括在一般非均勻B樣條曲線中。

8.B樣條曲線與Bézier曲線的比較

B樣條曲線與Bézier曲線的差別如下：

（1）對于Bézier曲線，基函數(shù)的次數(shù)等于控制頂點(diǎn)數(shù)減1；對于B樣條曲線，基函數(shù)的次數(shù)與控制頂點(diǎn)數(shù)無關(guān)。（2）Bézier曲線的基函數(shù)即Bernstein基函數(shù)是多項式函數(shù)，B樣條曲線的基函數(shù)即B樣條基函數(shù)則是多項式樣條。（3）Bézier曲線是一種特殊表示形式的參數(shù)多項式曲線，B樣條曲線則是一種特殊表示形式的參數(shù)樣條曲線。（4）Bézier曲線缺少局部性質(zhì)，B樣條曲線具有局部

性質(zhì)。5.1.5

NURBS曲線

1.NURBS曲線的定義

給定n+1個空間點(diǎn)di（i=0，1，…，n），和非負(fù)實(shí)數(shù)ωi≥0（i=0，1，…，n），其中ω0>0，ωn>0，分段有理參數(shù)k階多項式曲線表示式為(5.87)

2.NURBS曲線的性質(zhì)

若某個權(quán)因子ωj=0，則相應(yīng)的控制頂點(diǎn)dj對曲線不產(chǎn)生影響。若ωj→+∞，則（5.88）· Bézier曲線面、B樣條曲線面以及圓錐曲線和二次曲面都是NURBS曲線面的特例，由此可以看出NURBS既為標(biāo)準(zhǔn)解析形狀，也為自由型曲線面的精確表示與設(shè)計提供了一個統(tǒng)一的數(shù)學(xué)形式。因此一個統(tǒng)一的數(shù)據(jù)庫就能存儲這兩類形狀信息。

3.圓錐曲線的NURBS表示

給定節(jié)點(diǎn)向量U={0，0，0，1，1，1}，由控制頂點(diǎn)d0，

d1，

d2和權(quán)因子ω0，ω1，ω2確定的二次NURBS曲

線為(5.89)它是一條圓錐曲線，其形狀分類如下：(5.90)

4.NURBS曲線的計算

現(xiàn)討論NURBS曲線的計算問題。在齊次坐標(biāo)下，NURBS曲線可看做是四維空間的B樣條曲線在三維空間中的投影變換下的像。其表示式為(5.91)

5.2曲面的表示

5.2.1

Bézier曲面

Bézier曲面是Bézier曲線向曲面的直接推廣。給定三維空間(m+1)×(n+1)個點(diǎn)Pij(xij，yij，zij)（i=0，1，…，m;j=0，1，…，n），其張量積形式的參數(shù)多項式曲面表示式為

P(u，v)的矩陣表示為

1.Bézier曲面的性質(zhì)

類似于Bézier曲線，曲面P(u，v)具有下述性質(zhì)：

（1）角點(diǎn)位置： （2） 邊界線位置：

（3）角點(diǎn)切平面：（4） 角點(diǎn)法向量：

（5）凸包性： （6） 幾何不變性

（7）交互能力：（8）易拼接性：

（9）易離散性：（10）對稱性：(5.97)

2.Bézier曲面的拼接

設(shè)兩張m×n次Bézier曲面如圖5.11所示，分別由控制頂點(diǎn)Pij(0≤i≤m;0≤j≤n)和Qij(0≤i≤m;0≤j≤n)定義為(5.98)(5.99)圖5.11兩張Bézier曲面的拼接如果要求兩曲面片達(dá)到G0連續(xù)，則它們有公共的邊界，即

P(1，v)=Q(0，v)

(5.100)

于是有

Pmj=Q0j，j=0，1，…，n

如果要求沿公共邊界達(dá)到G1連續(xù)，則兩曲面片在該公共邊界上有公共的切平面，因此曲面的法向應(yīng)當(dāng)是跨界連續(xù)的，即

Qu(0，v)×Qv(0，v)=α(v)Pu(1，v)×Pv(1，v)

(5.101)

其中，α(v)為任意非負(fù)連續(xù)函數(shù)。下面討論滿足上式的兩種方法。（1）鑒于G0連續(xù)，式（5.101）最簡單的解是：

Qu(0，v)=α(v)Pu(1，v)

(5.102)

這相當(dāng)于要求合成曲面上v為常數(shù)的所有曲線在跨界時有切向的連續(xù)性。為了保證式（5.102）兩邊關(guān)于v的多項式次數(shù)相同，必須取α(v)=α（正常數(shù)）。于是有：即（2）式（5.102）使得兩張曲面片在公共邊界達(dá)到G1連續(xù)時只涉及曲面P(u，v)和Q(u，v)的兩列控制頂點(diǎn)，比較容易控制。用這種方法匹配合成曲面的邊界時，u向和

v向是光滑且連續(xù)的。但實(shí)際上，式（5.102）的限制比較嚴(yán)格。為了構(gòu)造合成曲面時有更大的靈活性，Bézier在1972年放棄把式（5.102）作為G1連續(xù)的條件，而以式（5.103）來滿足式（5.101），只要求Qu(0，v)位于

Pu(1，

v)和Pv(1，

v)所在的平面內(nèi)，也就是曲面片P(u，

v)邊界上相應(yīng)點(diǎn)處的切平面，這樣就有了大得多的余地，但跨界切矢在跨越曲面片的邊界時就不再連續(xù)了。

Qu(0，v)=α(v)Pu(1，v)+β(v)Pv(1，v)（5.103）

3.deCasteljau算法

Bézier曲線的deCasteljau算法可以推廣到Bézier曲面的情形。若給定Bézier曲面控制網(wǎng)格的控制頂點(diǎn)Pij(i=0，1，…，m;j=0，1，…，n)和一對參數(shù)(u，v)，則(5.104)其中，上式中各控制頂點(diǎn)由下列遞推關(guān)系式：(5.105)(5.106)

4.Bézier曲面的分割

Bézier曲面P(u，

v)可分成四塊小的Bézier曲面片，其分割方法如下：其中，上式中各控制頂點(diǎn)的遞推關(guān)系式如下：5.2.2

B樣條曲面

給定(m+1)×(n+1)(m≥k，n≥l)個空間點(diǎn)dij，i=0，1，…，m;j=0，1，…，n，其張量積參數(shù)曲面表示式為稱之為k×l階的B樣條曲面。dij，i=0，1，…，m;j=0，…，n

叫做曲面的控制頂點(diǎn)，它們順次構(gòu)成的空間四邊網(wǎng)格叫做曲面的控制網(wǎng)格。Ni，k(u)、Nj，l(v)分別是由節(jié)點(diǎn)矢量U={u0，u1，…，um+k}和V={v0，

v1，…，vn+l}定義的B樣條基函數(shù)。B樣條曲面的性質(zhì)

（1）定義域：

（2）強(qiáng)凸包性：

（3）分片參數(shù)多項式：

（4）幾何不變性：

（5）局部性：

（6）對Bézier曲面的包含性。

2.deBoor-Cox算法

B樣條曲線的deBoor-Cox算法可以推廣到B樣條曲

面的情形。若給定B樣條曲面控制網(wǎng)格的控制頂點(diǎn)

dij(i=0，1，…，m;j=0，1，…，n)和一對參數(shù)(u,v)

(u∈［uI，uI+1)］，v∈［vJ，vJ+1)］，k－1≤I≤m;

l－1≤J≤n)，則：(5.112)其中，d0,0

i，j=di，j，其他各控制頂點(diǎn)由下列遞推關(guān)系式

決定：或5.2.3

NURBS曲面

類似于NURBS曲線，一張k×l階NURBS曲面定義

如下：可得表示式：(5.116)稱之為雙變量有理基函數(shù)。

1.權(quán)因子的幾何意義

從形式上看，權(quán)因子是一純數(shù)值的量。實(shí)質(zhì)上，權(quán)因子具有明顯的幾何意義。對于NURBS曲線式：(5.117)若令則有于是由此，我們得到了權(quán)因子ωj的明顯的幾何意義為：權(quán)因子ωj等于過控制頂點(diǎn)dj的一條直線上分別具有權(quán)因子ωj=+∞，0，1和ωj≠0，1的那四個點(diǎn)dj，m，n，R的交比，這四個點(diǎn)中的前三個點(diǎn)是特定的（圖5.12）。因?yàn)镹URBS曲面權(quán)因子的討論過于復(fù)雜，在此不再贅述。圖5.12權(quán)因子的幾何意義

2.NURBS曲面的性質(zhì)

NURBS曲面除具有B樣條曲面的類似性質(zhì)之外，還具有下述的重要性質(zhì)：

· 對B樣條曲面的包含性：當(dāng)所有的權(quán)因子相等時，即ω00=ω01=…=ωmn=const時，NURBS曲面蛻化為B樣條

曲面。

·可精確表示初等二次曲面。

·在仿射變換下的不變性：NURBS曲面在比例、旋轉(zhuǎn)、平移、錯切及投影變換下仍是NURBS曲面。

·權(quán)因子的引入增強(qiáng)了形狀設(shè)計的靈活性。利用權(quán)因子可對曲面形狀進(jìn)行微調(diào)。

3.NURBS曲面的求值算法

在齊次坐標(biāo)下，NURBS曲面可看作是四維空間的B樣條曲面在三維空間的中心投影變換下的像。因此，一張k×l階的NURBS曲面的求值可按以下步驟進(jìn)行：

Step1由控制頂點(diǎn)dij和權(quán)因子ωij確定帶權(quán)控制頂點(diǎn)：

Dij=［ωijdij，ωij］

i=0，1，…，m;j=0，1，…，n(5.123）

Step2用帶權(quán)控制頂點(diǎn)Dij定義k×l階B樣條曲面：（5.124）

Step3用B樣條曲面的deBoor-Cox算法計算曲面D(u，v)。

Step4以坐標(biāo)原點(diǎn)為投影中心、超平面ω=1為投影平面，對D(u，v)做投影變換，即可得NURBS曲面R(u，v)。5.2.4

Coons曲線面

1）雙線性混合Coons曲面片

給定由四條參數(shù)曲線圍成的空間封閉曲邊四邊形，使兩對邊分別定義在u∈［0，1］與v∈［0，1］上，要求構(gòu)造一張以這四條曲線為邊界曲線的曲面：

P(u，v)，0≤u，v≤1（5.125）這個問題有無窮多解，其中的一個解就是雙線性混合Coons曲面。

在每一對邊界曲線間由線性插值構(gòu)造直紋面：（5.126）兩張曲面q(u，

v)與r(u，v)的簡單疊加并減去曲面片四個角點(diǎn)決定的一張雙線性張量積曲面：即得到所求的雙線性混合Coons曲面片：

P(u，v)=q(u，v)+r(u，v)－s(u，v)其矩陣表示如下：

2）局部雙三次混合Coons曲面片

采用兩對三次混合函數(shù)：（5.129）可得到局部雙三次混合Coons曲面片：上式右端的三階方陣包含了曲面的全部邊界信息，稱之為邊界信息矩陣。其右下角二階子塊的4個矢量是曲面邊界的端點(diǎn)，稱之為曲面的角點(diǎn)。

類似雙線性混合中那樣，定義對角點(diǎn)數(shù)據(jù)的插值曲面：：

則雙三次混合Coons曲面片為

P(u，v)=q(u，v)+r(u，v)－s(u，v)(5.134)或者以矩陣形式表示為

5.3實(shí)體的表示

5.3.1三維實(shí)體的定義

三維物體的這種內(nèi)在的層次結(jié)構(gòu)給出了在計算機(jī)內(nèi)定義實(shí)體的拓?fù)浣Y(jié)構(gòu)，即實(shí)體在計算機(jī)內(nèi)通常采用六層拓?fù)浣Y(jié)構(gòu)來定義，如圖5.14所示。圖5.14三維物體的層次結(jié)構(gòu)5.3.2三維實(shí)體建模

1．線框模型（wireframemodel）

線框模型是用頂點(diǎn)和棱邊來表示實(shí)體的模型。為了確切地表示清楚形體的形狀和位置，必須給出頂點(diǎn)集的位置和它們之間的連邊規(guī)則。

2．表面模型（surfacemodel）

表面模型是用有向棱邊圍成的部分來定義形體的表面，再用面的集合來定義形體。表面模型是在線框模型的基礎(chǔ)上，增加了面邊信息以及表面特性、棱邊的連接方向等內(nèi)容。表面模型可以滿足于面面求交線、形成明暗色彩等要求，但對于立體的物性計算和工程分析仍有困難（如有限元分析）。

3．實(shí)體模型（solidmodel）

實(shí)體模型，即是指實(shí)心的立體模型，其主要的幾何特征表現(xiàn)為體，它可以更完整準(zhǔn)確地表達(dá)模型的幾何特征，包含的信息也更多。利用實(shí)體模型可以計算、分析物體的質(zhì)量、體積、重心和慣性矩等物理特性，因此它是計算機(jī)輔助設(shè)計的重要基礎(chǔ)。三種方法來定義：

（1）給出實(shí)體存在側(cè)的一點(diǎn)。

（2）用表面的外法矢直接指明。

（3）用面環(huán)方向表示（隱含了法矢）。實(shí)體即定義為各面負(fù)方向一側(cè)的交。

盡管實(shí)體模型與前面所說的線框模型、表面模型截然不同，但是在圖形顯示時，實(shí)體模型也是以線框圖來表示的，除非對它進(jìn)行了消隱（Hide）、陰影（Shade）或渲染（Render）處理。以下是三種不同模型間的簡單比較，如表5.1所示。5.3.3實(shí)體的表示方法

1.實(shí)體的CSG表示

CSG表示法也稱為體素構(gòu)造法，它是用稱為體素的基本實(shí)體經(jīng)集合運(yùn)算構(gòu)造復(fù)雜實(shí)體的一種實(shí)體表示法。例如，圖5.15給出的三維實(shí)體可以看作是由兩個長方體和一個圓柱體經(jīng)集合運(yùn)算構(gòu)成的，其幾何定義為

Part=Cube1+Cube2－Cylinder1

(5.136)

1）物體間的正則集合運(yùn)算

物體間的并、交、差運(yùn)算是CSG表示法構(gòu)造物體的最基本的手段之一。三維實(shí)體的一個最顯著的特征是：它們可以用一個具有邊界子集和內(nèi)部子集的封閉點(diǎn)集來描述。執(zhí)行物體間的并、交、差操作的結(jié)果也應(yīng)該是具有邊界子集和內(nèi)部子集的封閉點(diǎn)集，并應(yīng)保持初始物體的維數(shù)，而傳統(tǒng)的點(diǎn)集之間的并、交、差運(yùn)算可能會改變點(diǎn)集的正

則性。圖5.15三維實(shí)體的CSG構(gòu)造例如，圖5.16中A、

B兩個物體都具有邊界子集bA、

bB和內(nèi)部子集iA、iB。交運(yùn)算在數(shù)學(xué)上是正確的，但在

幾何上是不正確的，因?yàn)榇藭rC=A∩B不像A、B那樣具有內(nèi)部子集，也不再是二維物體。為此，我們必須對傳統(tǒng)的點(diǎn)的集合運(yùn)算施加一些限制，如引入正則集合和正則集合運(yùn)算。圖5.16二維實(shí)體的交運(yùn)算

·正則集合：三維空間E3中的集合S稱為正則集，如果S=kiS。

· 正則算子：對于E3中的點(diǎn)集A、B，相應(yīng)的正則算子定義如下：

A∪*B=ki(A∪B)，A∩*B=ki(A∩B)，A－*B=ki(A－B)

(5.137)正則算子∪*，∩*，－*具有以下重要性質(zhì)：(5.138)

·正則運(yùn)算：對三維物體進(jìn)行正則運(yùn)算的關(guān)鍵是算法，其最基本的算法步驟有求交、包含性測試、跟蹤邊界、形成回路和重新參數(shù)化回路等。下面我們以二維物體A、

B的正則運(yùn)算為例，對正則運(yùn)算的算法步驟做以下介紹。（1）正則交運(yùn)算∩*。令（5.139）如圖5.17所示。由于Q=bQ∪iQ，所以必須找出bQ和iQ的子集以構(gòu)成封閉的維數(shù)一致的形體Q*，Q*的侯選部分只能從上式四部分求得。圖5.17二維實(shí)體的正則交運(yùn)算圖5.17中形體A和B有兩處明顯的重疊交，這些交的特點(diǎn)是它既不在A的內(nèi)部，也不在B的內(nèi)部，我們通常有兩種區(qū)分方法：一種是在邊界上取一點(diǎn)P，從P的垂直方向沿

左右移動一距離ε產(chǎn)生兩個點(diǎn)PL，PR，然后構(gòu)造一表格來測試PL，PR是否既在A內(nèi)又在B內(nèi)（圖5.18）。圖5.18正則交運(yùn)算下的邊界測試綜合以上討論，兩個形體A和B的正則交運(yùn)算的結(jié)果可表示為注意，式（5.141）并沒有指出物體的維數(shù)，即它可以適用于一維、二維、三維或n維形體。（2）正則并運(yùn)算∪*。令(5.142)據(jù)此來確定bQ*和iQ*，從而確定Q*。二維實(shí)體的正則并運(yùn)算如圖5.19所示。圖5.19二維實(shí)體的正則并運(yùn)算這里，ValidbbA不在iB中，部分在bB上的bA，即：(5.145)(5.146)我們再一次看到在bA∩bB中存在二義性，必須像討論正則交運(yùn)算那樣，通過測試方法來解決，所以有：(5.147)（3）正則差運(yùn)算－*。令(5.149)據(jù)此來確定bQ*和iQ*，從而確定Q*。

圖5.20二維實(shí)體的正則差運(yùn)算由圖5.20可以看出：第一，iQ*=iA－bB－iB，此處為兩個不連接的子集；第二，iQ*≠Q(mào)，因?yàn)閎Q*的某些元素在bQ中丟失了。若在Q中加上iA∩bB，其邊界仍不完整。丟失的線段是bA∩bB的子集，因此必須對bA∩bB做進(jìn)

一步的有效性測試，來決定有效的邊界。對差而言，有效的bA∩bB是那些僅僅與iQ*或iA－iB鄰接的邊界，因此：(5.150)所以，正則差運(yùn)算－*的結(jié)果為(5.151)對于實(shí)際應(yīng)用而言，形體A、B之間的位置關(guān)系是千變?nèi)f化的，圖5.21便是一種，這里的形體A完全包含了形體B。圖5.21二維實(shí)體的正則運(yùn)算實(shí)例

2）物體的CSG樹表示

一般地，物體的CSG表示都可以描述成一棵二叉樹，這棵二叉樹的葉結(jié)點(diǎn)或者是基本元素，或者是坐標(biāo)變換的變換參數(shù)。非葉結(jié)點(diǎn)或者是正則集合運(yùn)算，或者是幾何變換。每棵子樹表示其下面兩個結(jié)點(diǎn)運(yùn)算的結(jié)果，根結(jié)點(diǎn)則表示了最終的復(fù)雜物體。

CSG樹的語義為：

<CSG樹>∷=<體素葉子>|<CSG樹><正則集合運(yùn)算結(jié)

點(diǎn)><CSG樹>|

<CSG樹><坐標(biāo)變換結(jié)點(diǎn)><坐標(biāo)變換參數(shù)>

CSG樹只定義了物體的構(gòu)成體素和構(gòu)造方式，并不反映物體的面、邊、頂點(diǎn)等有關(guān)的邊界信息。因此，這種表示又被稱為物體的隱式模型（UnevaluatedModel）或過程模型（ProceduralModel）。

CSG樹的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如圖5.22所示。圖5.22

CSG樹的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)每個結(jié)點(diǎn)均由操作碼、坐標(biāo)變換指針、基本體素指針、左子樹指針和右子樹指針5個域構(gòu)成。除操作碼外，其余各域都以指針形式存儲。操作碼按約定方式取值，當(dāng)操作碼為零時，表示該結(jié)點(diǎn)為一基本體素，相應(yīng)的左、右子樹指針為空（Null）；對于非葉結(jié)點(diǎn)，操作碼取約定的正整數(shù)，表示左子樹和右子樹結(jié)點(diǎn)間進(jìn)行正則集合運(yùn)算，此時基本體素域?yàn)榭?。變換域存儲該結(jié)點(diǎn)所表示形體在進(jìn)行新的集合運(yùn)算前所做的坐標(biāo)變換信息，即將體素及其局部坐標(biāo)系置于物體的整體坐標(biāo)系中給定位置。

用CSG樹表示一個復(fù)雜物體比較簡潔。它所表示的物體的有效性是由基本體素的有效性和集合運(yùn)算的正則性自動得到保證的。

CSG樹提供了足夠的信息以判斷空間任一點(diǎn)在它所定義的內(nèi)部、外部或體的表面上。因此，它可唯一地定義一個物體，并支持對這個物體的一切幾何性質(zhì)的計算。這里指的物體的幾何性質(zhì)既包括它自身的性質(zhì)，如體積、面積、重心等，也包括它與別的物體相互關(guān)聯(lián)的性質(zhì)，如計算這個物體與一相鄰物體之間的最短距離等。計算物體幾何性質(zhì)的算法和描述一個物體的數(shù)據(jù)結(jié)構(gòu)是密切相關(guān)的，不同的數(shù)據(jù)結(jié)構(gòu)對應(yīng)不同的算法。CSG表示法最適宜采用“分而治之”的算法（divided&conquer）。設(shè)F是關(guān)于一個CSG樹所定義物體的幾何性質(zhì)的函數(shù)，則計算F的算法框架如下：其中，Prim_F為計算基本體素的幾何性質(zhì)F的函數(shù)，Combine為依據(jù)CSG樹非葉結(jié)點(diǎn)進(jìn)行的運(yùn)算對左右子樹的幾何性質(zhì)F進(jìn)行合成的函數(shù)。

雖然CSG樹表示可以支持關(guān)于它所表示物體的多種幾何性質(zhì)的計算及其他應(yīng)用，但它并非適用于一切場合。例如，它不適用于對物體形狀做局部修改，并且生成工程設(shè)計中常用的線框圖效率低，此時常需要將物體的CSG樹表示轉(zhuǎn)化為邊界表示，以便獲取邊界信息。

2.實(shí)體的邊界表示

實(shí)體的邊界表示法就是通過描述物體的邊界來表示一個物體，邊界就是物體內(nèi)部點(diǎn)與外部點(diǎn)的分界面。顯然，定義了物體的邊界，該物體就被唯一地定義了。

1）邊界表示法表示物體的方式

用邊界表示法定義物體有兩種方式：其一是把面組成CSG表示中的體素，再通過裝配體素形成更復(fù)雜的物體；另一種是直接通過適當(dāng)表面的組合和相交產(chǎn)生復(fù)雜的物體。

2）邊界表示法的翼邊結(jié)構(gòu)

在邊界表示法中，表示面、邊和頂點(diǎn)相互鄰接關(guān)系的信息屬于拓?fù)湫畔ⅲ硎具@些鄰接關(guān)系的拓?fù)湫畔⒃诮⑦吔缒Ｐ鸵约皩吔缒Ｐ瓦M(jìn)行處理和交互操作中非常重要。描述面、邊、頂點(diǎn)三種拓?fù)湓氐泥徑雨P(guān)系可分為三組共九種表示方式，如圖5.23所示。圖5.23面、邊、頂點(diǎn)的鄰接關(guān)系在邊界表示法中，沒有必要包含所有九種鄰接拓?fù)湫畔ⅲ环矫媸怯捎谶@些鄰接關(guān)系不全是彼此獨(dú)立的，而是相互相關(guān)的，一些鄰接關(guān)系可由其他鄰接關(guān)系演變而來；另一方面是存儲量太大，過于累贅和煩瑣。

實(shí)驗(yàn)表明，以邊為核心的一組鄰接關(guān)系是最實(shí)用的，這一組鄰接信息的數(shù)據(jù)結(jié)構(gòu)通常稱為翼邊結(jié)構(gòu)（WingededgeStucture）。翼邊結(jié)構(gòu)是描述與一條邊相鄰的兩個頂點(diǎn)、四條鄰邊和兩個鄰面這些拓?fù)湫畔⒌臄?shù)據(jù)結(jié)構(gòu)，當(dāng)我們從外面觀察多面體的一條邊時，可以看到這條邊的上、下兩個頂點(diǎn)

P1、P2，左右兩個鄰面LoopL、LoopR，以及上、下、左、右四條鄰邊Ercc、Ercw、Elcc、Elcw。這四條邊好像是伸展的翅膀（圖5.24），因此將其命名為翼邊。圖5.24翼邊結(jié)構(gòu)通過翼加結(jié)構(gòu)可以方便地查找各元素之間的鄰接關(guān)系。例如，可以迅速列出一面上所有的邊，從一個面出發(fā)遍歷所有的面等。多面體的運(yùn)算中往往以邊作為最基本的運(yùn)算單元來實(shí)現(xiàn)邊與邊求交、邊與面求交、刪除舊邊、增加新邊、生成新的面環(huán)等。因此，將邊作為建立鄰接關(guān)系的中心環(huán)節(jié)在應(yīng)用上最為方便。

翼邊結(jié)構(gòu)的結(jié)點(diǎn)結(jié)構(gòu)如圖5.25所示。圖5.25翼邊結(jié)構(gòu)的結(jié)點(diǎn)結(jié)構(gòu)

3）邊界表示法中的數(shù)據(jù)結(jié)構(gòu)

綜合物體的層次結(jié)構(gòu)和邊界表示的翼邊結(jié)構(gòu)，邊界表示中的數(shù)據(jù)結(jié)構(gòu)如圖5.26所示。用此數(shù)據(jù)結(jié)構(gòu)表示時，物體的幾何模型兼有CSG和B-rep兩種表示形式。此外，該數(shù)據(jù)結(jié)構(gòu)還引入了空間（Space）概念，它類似于二維繪圖系統(tǒng)中層（Layer）的應(yīng)用。物體分屬于不同的空間，每個

空間可以設(shè)定不同的顯示色彩，也可以設(shè)定為不可見。圖5.26邊界表示的數(shù)據(jù)結(jié)構(gòu)

4）Euler運(yùn)算

Euler運(yùn)算提供了直接使用頂點(diǎn)、邊、表面等基本元素構(gòu)造三維物體的手段，構(gòu)造的過程是逐步的：先輸入一個點(diǎn)，作為建立物體的開始；然后輸入第二個點(diǎn)，它與第一點(diǎn)連成一條邊；若干條邊構(gòu)成一個面的邊界，若干個面圍成一個體等。顯然，任意數(shù)目的頂點(diǎn)、邊和面不能構(gòu)成一個體。頂點(diǎn)、邊和面之間一定要滿足一定的關(guān)系，即拓?fù)湟恢滦院蛶缀我恢滦浴ｍ旤c(diǎn)、邊、面之間要滿足的拓?fù)潢P(guān)系由擴(kuò)展的Euler公式表示為

V－E+F－R=2(S－H)

(5.152)

其中，V、E、F分別表示物體上的頂點(diǎn)、邊和面的數(shù)目，而R、S、H則分別表示物體表面邊界的內(nèi)環(huán)數(shù)、不相連接的物體數(shù)以及物體上的通孔數(shù)?；跀U(kuò)展的Euler公式，可設(shè)定一套Euler運(yùn)算來構(gòu)造物體。這些運(yùn)算包括：

①M(fèi)EV：輸入一個頂點(diǎn)，生成一條邊；

②MEF：產(chǎn)生一條邊和一個面；

③MVSF：輸入一個頂點(diǎn)，產(chǎn)生一個體、一個面（構(gòu)造體的開始）；

④MEKR：產(chǎn)生一條邊，刪除一個內(nèi)環(huán)；

⑤MHS：產(chǎn)生一個體和一個孔。上述五種Euler運(yùn)算所對應(yīng)的補(bǔ)運(yùn)算是：

①KEV：刪除一個頂點(diǎn)和一條邊；

②KFE：刪除一個面和一條邊；

③KVSF：刪除一個體、一個面、一個頂點(diǎn)；

④KHS：刪除一個孔和一個體；

⑤KEMR：刪除一條邊，產(chǎn)生一個內(nèi)環(huán)。為了方便對形體的修改，還定義了兩個輔助操作：

①SEMV：將邊分割成兩端，生成一個新的點(diǎn)和一條新的邊；

②JEKV：合并兩條相鄰的邊，并刪除它們的公共端點(diǎn)。

可以證明，Euler操作是有效的，即用Euler操作對形體操作的結(jié)果在物理上是可實(shí)現(xiàn)的；Euler操作也是完備的，即任何形體都可用有限步驟的Euler操作構(gòu)造出來。以上的Euler操作僅適用于正則形體，非正則形體已不再滿足Euler公式，但是，Euler操作中對形體點(diǎn)、邊、面、體幾何元素做局部修改的原理仍然適用。Weiler定義了擴(kuò)展的Euler操作來構(gòu)造非正則形體，我們?nèi)匀话涯且惶撞僮餍酝負(fù)浣Y(jié)構(gòu)的方法叫做Euler操作。

3.實(shí)體的八叉樹表示

物體的八叉樹表示是一種層次數(shù)據(jù)結(jié)構(gòu)。首先對三維物體定義一個外接立方體，立方體的三組棱邊分別與x、

y、z

軸平行，邊長為2N。如果所表示的物體本身就是該立方體，則物體可用該立方體來表示。否則將立方體等分為

8個子立方體，其邊長為原立方體邊長的一半。將八個子立方體依次編號為0，1，…，7，編號規(guī)則如圖5.27所示。圖5.27八叉樹的結(jié)點(diǎn)編號若某一個小立方體完全在物體內(nèi)部，則將此小立方體標(biāo)識為“滿”；若它完全在物體外部，則將其標(biāo)識為“空”；其他情況下，將其標(biāo)識為“部分占有”，并繼續(xù)等分為八塊。依此方式，物體在計算機(jī)內(nèi)可表示為一棵八叉樹，凡標(biāo)識為“滿”或“空”的立方體均為終端結(jié)點(diǎn)，而標(biāo)識為“部分占有”的立方體為非終端結(jié)點(diǎn)。最后，當(dāng)分割生成的每一個小立方體的邊長為單位長時，分割結(jié)束。此時，應(yīng)該將每一個標(biāo)識為“部分占有”的小立方體重新標(biāo)識為“滿”或“空”。這就是物體的八叉樹表示。采用八叉樹表示物體的優(yōu)點(diǎn)有：

(1)物體間的集合運(yùn)算十分簡單，此時只需同時遍歷

表示物體的兩棵八叉樹，對相應(yīng)的小立方體結(jié)點(diǎn)進(jìn)行運(yùn)算即可；（2）計算物體的體積簡便，只要從八叉樹的根結(jié)點(diǎn)開始逐個累加標(biāo)識為“滿”的結(jié)點(diǎn)的立方體的體積，計算精度取決于八叉樹的分割層數(shù)，當(dāng)最下一層的“部分占有”葉結(jié)點(diǎn)都算作“滿”時，算得的體積最大；反之，如果將這些葉結(jié)點(diǎn)都算作“空”時，所求得的體積最小。當(dāng)然，更合理的算法是引入Montacarlor法，即產(chǎn)生隨機(jī)數(shù)，根據(jù)隨機(jī)數(shù)來取一部分“部分占有”的葉結(jié)點(diǎn)作為“滿”結(jié)點(diǎn)。（3）八叉樹的數(shù)據(jù)結(jié)構(gòu)簡化了隱藏線隱藏面的消除算法。由于消隱算法的核心是排序，即將待顯示物體上的點(diǎn)、線、面按它們離觀察點(diǎn)的遠(yuǎn)近排列次序，離觀察點(diǎn)近的元素遮擋遠(yuǎn)的元素，而物體的八叉樹表示中，物體的各元素已按空間位置排列成一定的順序。同一層次的八叉樹結(jié)點(diǎn)組成三維空間中可線性分離的叢，因此很容易建立叢的優(yōu)先級樹。例如，在我們所給的編碼方式下，當(dāng)觀察點(diǎn)處于圖5.28中z軸方向的E點(diǎn)附近時，只要按照0，1，2，3，4，

5，6，7的次序顯示各體元，就可獲得物體的消隱圖。這種消隱算法的時間復(fù)雜度與所要顯示物體的體元數(shù)目n成線性關(guān)系O(n)。圖5.28八叉樹結(jié)點(diǎn)編碼下的消隱八叉樹的缺點(diǎn)有以下幾點(diǎn)：

（1）占用存儲空間大；

（2）物體的坐標(biāo)變換代價高。當(dāng)物體旋轉(zhuǎn)一角度后，整個八叉樹需要重新生成。對于平移而言，物體的八叉樹結(jié)點(diǎn)分割保持不變，但沿平移方向的所有結(jié)點(diǎn)都需要重新編碼；

（3）與B-rep表示或CSG表示難以統(tǒng)一，而B-rep表示或CSG表示可以轉(zhuǎn)化成八叉樹表示。這種單向轉(zhuǎn)換導(dǎo)致八叉樹的表示形式難以集成到已有的基于B-rep表示或CSG表示的系統(tǒng)中。

4.線性八叉樹表示

減少八叉樹表示所需的空間存儲量的一種有效措施是線性八叉樹。線性八叉樹表示與八叉樹表示類似，唯一的區(qū)別是存儲方式不同。線性八叉樹是用一個可變長度的一維數(shù)組存儲一棵八叉樹，數(shù)組中僅存儲八叉樹的終端結(jié)點(diǎn)，即描述一個物體的大大小小的立方體。對于2N×2N×2N

的空間分割，每個結(jié)點(diǎn)在八叉樹中的位置可用一個八進(jìn)制數(shù)表示為（5.153）性質(zhì)1設(shè)P(x，y，z)為空間任一點(diǎn)，其x，y，z的

二進(jìn)制表示如下：（5.154）則點(diǎn)P對應(yīng)的線性八叉樹結(jié)點(diǎn)的編碼為{qn－1qn－2…q0}，其中：性質(zhì)2給定線性八叉樹結(jié)點(diǎn)的編碼{qn－1qn－2…q0}，則對應(yīng)的子立方體的前下角的坐標(biāo)為（5.157）式中［·］表示取整，il，jl，kl為ql的二進(jìn)制表示，即ql=kljlil，l=0，1，…，n－1。例如，對于Q=51，有：q0=1=(001)2，q1=5=(101)2，

則x=(11)2=3，y=(00)2=0，z=(10)2=2，或者有：

5.4分形

5.4.1分形的歷史

1967年法國數(shù)學(xué)家B.B.Mandelbrot提出了“英國的海岸線有多長？”的問題，這個問題看起來好像極其簡單，因?yàn)殚L度依賴于測量單位。以1km為單位測量海岸線，可得到的近似長度將短于1km的迂回曲折都忽略掉了，若以1m為單位測量，則能測出被忽略掉的迂回曲折長度將變大，測量單位進(jìn)一步變小時,測得的長度將愈來愈大，這些愈來愈大的長度將趨近于一個確定值，這個極限值就是海岸線的長度。答案似乎解決了，但Mandelbrot發(fā)現(xiàn)：當(dāng)測量單位變小時，所得的長度是無限增大的。因此，他認(rèn)為海岸線的長度是不確定的，或者說，在一定意義上海岸線是無限長的。答案也許是因?yàn)楹０毒€是極不規(guī)則和極不光滑的。我們知道，經(jīng)典幾何研究光滑的曲線和曲面時，傳統(tǒng)上將自然界大量存在的不規(guī)則形體規(guī)則化后再進(jìn)行處理，我們必須將海岸線折線化才能得出一個有意義的長度。可貴之處是Mandelbrot突破了這一點(diǎn)，長度也許已不能正確概括海岸線這類不規(guī)則圖形的特征。海岸線雖然很復(fù)雜，但卻有一個重要的性質(zhì)——自相似性。從不同比例尺的地形圖上我們可以看出，海岸線的形狀大體相同，其曲折、復(fù)雜程度是相似的。換言之，海岸線的任一小部分都包含有與整體相同的相似的細(xì)節(jié)。要定量地分析像海岸線這樣的圖形，引入分形維數(shù)是很有必要的。分形的研究可以上溯到很久以前。最早的工作可追朔到1875年，德國數(shù)學(xué)家維爾斯特拉斯（K.Weierestrass）構(gòu)造了處處連續(xù)但處處不可微的函數(shù)，集合論創(chuàng)始人康托（G.Cantor，德國數(shù)學(xué)家）構(gòu)造了有許多奇異性質(zhì)的三分康托集。1890年，意大利數(shù)學(xué)家皮亞諾（G.Peano）構(gòu)造了填充空間的曲線。1904年，瑞典數(shù)學(xué)家科赫（H.vonKoch）設(shè)計出類似雪花和島嶼邊緣的一類曲線。

1915年，波蘭數(shù)學(xué)家謝爾賓斯基（W.Sierpinski）設(shè)計了像地毯和海綿一樣的幾何圖形。這些都是為解決分析與拓樸學(xué)中的問題而提出的反例，它們正是分形幾何思想

的源泉。但是，像其他的一些革命性的思想一樣，當(dāng)時分形的研究受到了主流學(xué)術(shù)的譴責(zé)，被人們認(rèn)為是研究一些數(shù)學(xué)中的怪異現(xiàn)象。那個時候著名的數(shù)學(xué)家CharlesHermite

把分形稱為“怪物”，這代表了絕大多數(shù)人的觀點(diǎn)。

1973年美籍法國數(shù)學(xué)家曼德爾布羅特(B.B.Mandelbrot）在法蘭西學(xué)院講課期間提出了分形幾何的思路。1975年，他用拉丁詞根構(gòu)造了單詞“Fractal”。1983年出版的《自然界的分形幾何》使分形概念迅速傳遍全球，這是獨(dú)立于歐幾里德幾何學(xué)之外的數(shù)學(xué)方法。動力系統(tǒng)中的分形集是近年分形幾何中最活躍的一個研究領(lǐng)域。動力系統(tǒng)的奇異吸引子通常都是分形集，它們產(chǎn)生于非線性函數(shù)的迭代和非線性微分方程中。動力系統(tǒng)中另一類分形集來源于復(fù)平面上解析映射的迭代。朱利亞（G.Julia）和法圖（P.Fatou）于1918至1919年間開創(chuàng)了這

一研究領(lǐng)域。他們發(fā)現(xiàn)，解析映射的迭代把復(fù)平面劃分成兩部分：一部分為法圖集；另一部分為朱利亞集（J集）。他們在處理這一問題時還沒有計算機(jī)，完全依賴于他們自身的想象力，因此他們僅憑智力獲得的成就受到限制。隨后50年間，這方面的研究并沒有得到進(jìn)展。隨著機(jī)算機(jī)的發(fā)展和用計算機(jī)來做實(shí)驗(yàn)的普及，這一研究課題又獲得了生機(jī)。5.4.2分?jǐn)?shù)維的計算

1910年，德國數(shù)學(xué)家豪斯道夫（F.Hausdorff）開始了奇異集合性質(zhì)與量的研究，提出分形維概念。之后，這一領(lǐng)域的研究工作并沒有引起更多人的注意，先驅(qū)們的工作只是作為分析與拓?fù)鋵W(xué)教科書中的反例而流傳開來。和相對論發(fā)展了傳統(tǒng)力學(xué)一樣，分維是對傳統(tǒng)維數(shù)概念的進(jìn)一步發(fā)展。雖然自然界里有豐富的歐幾里德物體的例子（如六角形、圓、立方體、四面體、正方形、三角形……）。但許多隨意性的自然現(xiàn)象似乎難以