計(jì)算機(jī)圖形學(xué) 課件 第6章 幾何造型

第6章幾何造型6.1幾何造型基礎(chǔ)6.2實(shí)體造型中的數(shù)據(jù)結(jié)構(gòu)6.3三維布爾運(yùn)算的實(shí)現(xiàn)

6.1幾何造型基礎(chǔ)

6.1.1物體的幾何信息和拓?fù)湫畔?.幾何信息幾何信息一般指形體幾何元素的性質(zhì)(如點(diǎn)、直線、曲線、平面、曲面)和度量關(guān)系的描述(如形狀、位置、大小、方向信息)，常用幾何元素的數(shù)學(xué)表示和邊界條件來定義。點(diǎn)、直線、平面、規(guī)則曲線、規(guī)則曲面都有確定的數(shù)學(xué)表示或數(shù)學(xué)表達(dá)式，而對(duì)于擬合曲線和擬合曲面，其數(shù)學(xué)表示常采用Coons、Bézier、B樣條、NURBS等方法。

例如，對(duì)于多面體，其幾何信息可用頂點(diǎn)、邊和面三個(gè)幾何元素來定義，如表6.1所示。

多面體幾何元素點(diǎn)、邊、面之間有一定關(guān)系，如圖6.1所示。這些幾何元素可以相互導(dǎo)出，它是幾何造型中集合運(yùn)算的基礎(chǔ)。

只用幾何信息來表示物體是不充分的，常常會(huì)出現(xiàn)物體表示上的不確定性(或稱為二義性)。如用5個(gè)頂點(diǎn)可定義兩種不同的多面體，如圖6.2所示。

圖6.1多面體幾何元素間的相互關(guān)系圖6.2五個(gè)頂點(diǎn)定義兩種不同的多面體

2.拓?fù)湫畔?/p>

拓?fù)湫畔⑹侵感误w幾何元素之間的連接關(guān)系、鄰近關(guān)系及邊界關(guān)系，它形成物體邊界表示的骨架。拓?fù)湫畔⒅该髁艘粋€(gè)形體由哪些面組成，每個(gè)面上有幾個(gè)環(huán)，每個(gè)環(huán)由哪些邊組成，每條邊又由哪些頂點(diǎn)定義等。

多面體的點(diǎn)、邊、面幾何元素之間一共有9種拓?fù)潢P(guān)系，如圖6.3所示。

圖6.3多面體各幾何元素之間的拓?fù)潢P(guān)系

6.1.2三維形體的表示形式

1.線框模型

線框模型由頂點(diǎn)表示幾何位置，相鄰頂點(diǎn)連線構(gòu)成棱邊表示幾何形狀特征。它將物體看成三維線段的集合，即用物體輪廓邊來描述物體的幾何形狀。對(duì)平面立體來說，物體可以由這些輪廓線直接構(gòu)成，如對(duì)長方體，用12條棱邊表示；對(duì)于曲面物體，可以用一些線框來圍成，圖6.4為圓柱體的線框表示(2個(gè)底面圓和若干條素線)。

圖6.4圓柱體的線框表示

線框模型在建模時(shí)只存儲(chǔ)物體的頂點(diǎn)和邊的信息，由于缺乏面和體的信息，因此用它來表示三維對(duì)象時(shí)會(huì)產(chǎn)生多義性，如圖6.5所示。圖6.5用線框模型表示的有多義性的物體

2.表面模型

表面模型在線框模型的基礎(chǔ)上增加了物體中面的信息，用面的集合來表示物體。例如，長方體可用6個(gè)矩形平面表示。表面模型中的表面可以是平面、規(guī)則曲面(如圓柱面、圓錐面、圓球面、旋轉(zhuǎn)曲面、直紋曲面、掃移曲面等)和自由曲面等。

表面模型在建模時(shí)存儲(chǔ)物體的面、環(huán)、邊和頂點(diǎn)信息，完整地定義了形體的邊界，其表示物體具有確定性。

3.實(shí)體模型

實(shí)體模型在表面模型的基礎(chǔ)上，對(duì)物體實(shí)體(即有材料的部分)存在的一側(cè)給出明確的定義。一般規(guī)定實(shí)體表面外環(huán)邊的走向?yàn)槟鏁r(shí)針方向，以相鄰邊矢量叉乘決定該面的外法線矢量方向，實(shí)體存在于該面外法線矢量方向相反的一側(cè)，這一側(cè)即實(shí)體存在的半空間，如圖6.6所示。

圖6.6實(shí)體表面外法矢方向的決定

6.1.3正則形體與歐拉公式

1.正則形體與非正則形體

如前所述，對(duì)于任意形體，如果它是三維歐氏空間中的非空有界的封閉子集，則其上任意一點(diǎn)的足夠小的鄰域在拓?fù)渖媳仨毷且粋€(gè)等價(jià)的封閉圓，即該點(diǎn)的鄰域展開在二維空間中是一個(gè)單連通域，滿足這種定義的形體稱為正則形體(也稱為流形物體)，否則為非正則形體(即非流形物體)，如圖6.7所示。

圖6.7非正則形體

正則形體的幾何特征如下：

(1)點(diǎn)至少與三個(gè)面(或三條邊)鄰接，不允許存在孤立點(diǎn)；

(2)邊只有兩個(gè)鄰面，不允許存在懸邊；

(3)面是形體表面的一部分，不允許存在懸面；

(4)不存在點(diǎn)接觸或邊接觸的懸體。

2.歐拉公式

在實(shí)體造型中，為保證造型過程中每一步所產(chǎn)生的形體的拓?fù)潢P(guān)系都是正確的，需要用歐拉公式進(jìn)行檢驗(yàn)，歐拉公式為

其中：v為頂點(diǎn)數(shù)，e為棱邊數(shù)，f為面數(shù)。例如，長方體的頂點(diǎn)數(shù)v=8，棱邊數(shù)e=12，表面數(shù)f=6，則v-e+f=8-12+6=2成立。

空間網(wǎng)格劃分屬于多面體分割。如果把三維空間中的一個(gè)多面體分割成s個(gè)多面體，則其頂點(diǎn)數(shù)、邊數(shù)、面數(shù)和多面體數(shù)的歐拉公式將變?yōu)?/p>

圖6.8的物體滿足式(6-2)，其中s=6，v=9，e=20，f＝18，則

式(6-1)僅適用于簡單的多面體及拓?fù)渫瑯?gòu)形體，當(dāng)多面體上有通孔及面上有內(nèi)環(huán)時(shí)，上述關(guān)系不成立。在幾何造型中需要采取修改后的歐拉公式(即廣義歐拉公式)：

其中：r是內(nèi)環(huán)數(shù)，h是通孔數(shù)，s是不連接的形體個(gè)數(shù)(即多面體的個(gè)數(shù))。

驗(yàn)證圖6.9所示的物體，v=24，e=36，f=15，r=3，h=1，s=1，則有

滿足廣義歐拉公式。

圖6.9符合歐拉公式的形體

6.1.4實(shí)體造型中的體素

在幾何造型系統(tǒng)中，復(fù)雜物體的形狀都是由體素經(jīng)過布爾運(yùn)算逐步得到的。體素是實(shí)體造型的基礎(chǔ)。實(shí)體造型中的體素可分為基本體素和擴(kuò)展體素。基本體素一般指人們熟知的長方體、楔形體、圓柱體、圓錐體、圓球體和圓環(huán)體等簡單形體。擴(kuò)展體素是指由一個(gè)二維圖形沿某軸移動(dòng)或繞某軸轉(zhuǎn)動(dòng)形成的構(gòu)造體。二維圖形沿某軸移動(dòng)(移動(dòng)時(shí)截面可以變化)形成的體素稱為拉伸體素，如圖6.10所示。二維圖形繞某軸轉(zhuǎn)動(dòng)形成的體素稱為旋轉(zhuǎn)

體素，如圖6.11所示。

圖6.10拉伸體素

圖6.11旋轉(zhuǎn)體素

圖6.12長方體半空間集合的描述

圖6.13圓柱體半空間集合的描述

6.1.5布爾運(yùn)算與正則布爾運(yùn)算

1.普通布爾運(yùn)算

(1)并集，即邏輯相加。A∪B=｛P｜P∈A

ORP∈B｝，如圖6.14所示。

圖6.13圓柱體半空間集合的描述

(2)交集，即邏輯相乘。A∩B=｛P｜P∈A

AND

P∈B｝，如圖6.15所示。

圖6.15A∩B布爾運(yùn)算

(3)差集，即邏輯相減。A-B=｛P｜P∈A

AND

P?B｝，如圖6.16所示。圖6.16A-B布爾運(yùn)算

(4)補(bǔ)集，即邏輯非。C(A)=｛P｜P?A｝，如圖6.17所示。圖6.17C(A)布爾運(yùn)算

圖6.18和圖6.19是形體求交布爾運(yùn)算的兩個(gè)例子。由此兩圖可見，對(duì)形體進(jìn)行普通布爾運(yùn)算，有時(shí)會(huì)產(chǎn)生懸掛的邊和面，如圖6.18(b)及圖6.19(b)所示，這是非正則集合(對(duì)應(yīng)非正則物體)。為避免這種情況的發(fā)生，需要引入正則布爾運(yùn)算。

圖6.18兩個(gè)平面的交集

圖6.19兩個(gè)形體的交集

2.封閉正則集合與正則布爾運(yùn)算

先引入封閉正則集合的概念：

若對(duì)于形體X，有X＝KiX(i、K為算子，i表示集合的內(nèi)部，K表示封閉)，則稱形體X是三維歐氏空間的一個(gè)封閉正則集合，參見圖6.20的矩形區(qū)域。

圖6.20封閉正則集合的定義

正則布爾運(yùn)算有正則并(∪?)、正則交(∩?)、正則差(-?)及正則補(bǔ)(C?)，分別定義如下：

圖6.18(c)及圖6.19(c)表示了正則交運(yùn)算的情況，由于懸掛邊及懸掛面屬于非封閉正則集合被剔除掉，正則布爾運(yùn)算生成封閉正則集合，從而保證構(gòu)造形體的三維一致性(三維齊性)。

6.1.6實(shí)體模型的表示與造型方法

按照表示物體的方法進(jìn)行分類，實(shí)體模型表示主要分為邊界表示、分解表示和構(gòu)造表示三大類。其中，分解表示是一種離散表示，又分為空間位置枚舉表示、八叉樹表示等；構(gòu)造表示包括掃描表示、構(gòu)造實(shí)體幾何(CSG)表示。

實(shí)體造型的方法大致分為半空間法、幾何元素分類法、降維布爾運(yùn)算法、體元離散法(八叉樹法)、掃描法、構(gòu)造實(shí)體幾何法和局部造型法。

1.邊界表示

邊界表示(BoundaryRepresentation)也稱為BR表示或B?Rep表示，它記錄了體素和每次布爾運(yùn)算或局部造型后的實(shí)體邊界，是幾何造型中最成熟、無二義的表示法。實(shí)體的邊界通常是由面的并集來表示，而每個(gè)面又由它所在曲面的數(shù)學(xué)定義加上其邊界來表示；面的邊界是邊的并集，而邊又是由點(diǎn)來表示的。邊界表示的一個(gè)重要特點(diǎn)是在該表示法中，描述形體的信息包括幾何信息和拓?fù)湫畔煞矫妗?/p>

如圖6.21所示，在邊界表示法中，邊界表示按照體—面—環(huán)—邊—點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。在進(jìn)行各種運(yùn)算和操作中，可以直接取得這些信息。

B?Rep表示的優(yōu)點(diǎn)如下：

(1)表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的，使得繪制B?Rep表示的形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系；

(2)便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如精度、表面粗糙度等；

(3)表示形體幾何形狀的覆蓋面大，表示能力強(qiáng)。

B?Rep表示的缺點(diǎn)如下：

(1)數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲(chǔ)空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜；

(2)修改形體的操作比較難以實(shí)現(xiàn)；

(3)B?Rep表示不一定對(duì)應(yīng)一個(gè)有效形體(如有懸掛面的形體)，通常運(yùn)用歐拉操作來保證B?Rep表示形體的有效性、正則性等。

圖6.21實(shí)體的邊界表示

2.分解表示

1)空間位置枚舉表示

首先在空間中定義一個(gè)能包含所要表示的物體的立方體，立方體的棱邊分別與x、y、z軸平行，然后將其均勻劃分為一些單位小立方體，用三維數(shù)組C[x][y][z]表示分解后的物體，下標(biāo)x、y、z代表的數(shù)組中的元素與單位小立方體一一對(duì)應(yīng)，當(dāng)C[x][y][z]=1時(shí)，表示對(duì)應(yīng)的小立方體被實(shí)體占據(jù)；當(dāng)C[x][y][z]=0時(shí)，對(duì)應(yīng)的小立方體沒有被實(shí)體所占據(jù)；最后由C[x][y][z]=1的小立方體堆積起來近似表示物體，如圖6.22所示。

圖6.22空間位置枚舉表示

2)八叉樹表示

將物體按空間位置枚舉表示法所得的包絡(luò)立方體自適應(yīng)劃分成一些不同大小的立方體，并將劃分過程表達(dá)為一種樹形層次結(jié)構(gòu)，稱為物體的八叉樹表示。

參見圖6.23，深色部分為空間物體。八叉樹表示物體的算法步驟如下：

(1)首先對(duì)物體定義一個(gè)外接的立方體作為八叉樹的根節(jié)點(diǎn)，將其均分為八個(gè)子立方體，分別對(duì)應(yīng)八叉樹的八個(gè)節(jié)點(diǎn)，八個(gè)子立方體按一定規(guī)則進(jìn)行編號(hào)；

(2)如果分解的立方體單元完全被物體占據(jù)，則該節(jié)點(diǎn)標(biāo)記為F(Full，稱為黑結(jié)點(diǎn))，并停止對(duì)該子立方體分解；

(3)如果子立方體單元內(nèi)沒有物體，則將該節(jié)點(diǎn)標(biāo)記為E(Eｍpty，稱為白結(jié)點(diǎn))；

(4)如果子立方體單元部分被物體占據(jù)，則將該節(jié)點(diǎn)標(biāo)記為P(Partial，稱為灰結(jié)點(diǎn))，并對(duì)該子立方體作進(jìn)一步分解，將其均分成八個(gè)更小的子立方體，對(duì)每一個(gè)子立方體進(jìn)行(2)～(4)的處理，這是一個(gè)遞歸劃分的過程。

(5)當(dāng)分割生成的每一個(gè)小立方體均被標(biāo)記為F或E以后，算法結(jié)束；或者，如果標(biāo)記為P的每個(gè)小立方體的邊長小于或等于設(shè)定的結(jié)束精度長度，則這時(shí)應(yīng)將其重新標(biāo)記為F后結(jié)束算法。

物體最終由標(biāo)記為F的若干個(gè)大小不同的子立方體表示。

圖6.23八叉樹表示

八叉樹表示方法的優(yōu)點(diǎn)是可以表示任何物體，數(shù)據(jù)結(jié)構(gòu)簡單；較空間位置枚舉表示法占用的存儲(chǔ)空間少(因其立方體的個(gè)數(shù)少)，計(jì)算量小(遍歷和查找快速)。其缺點(diǎn)是物體的非精確表示；沒有邊界信息，不適于圖形顯示。

(1)體積計(jì)算。

將物體按需要的精度(即最小立方體邊長)離散表示后，遍歷表示物體的八叉樹結(jié)點(diǎn)，計(jì)算每個(gè)F結(jié)點(diǎn)的體積，所有F結(jié)點(diǎn)的體積之和就是物體的體積。

(2)實(shí)體布爾運(yùn)算。

首先求取兩個(gè)實(shí)體的共同包絡(luò)立方體，其次將每個(gè)實(shí)體按共同包絡(luò)立方體進(jìn)行八叉樹表示，并把尺寸大的結(jié)點(diǎn)全部按八叉樹規(guī)則劃分為最小尺寸的結(jié)點(diǎn)，稱之為小結(jié)點(diǎn)。根據(jù)實(shí)體布爾運(yùn)算的類型，從兩個(gè)實(shí)體八叉樹中選取相應(yīng)的小結(jié)點(diǎn)，這些小結(jié)點(diǎn)堆積起來就是實(shí)體布爾運(yùn)算的結(jié)果。

(3)均勻立方體網(wǎng)格劃分。

在一些工程分析中，需要對(duì)分析對(duì)象進(jìn)行均勻立方體網(wǎng)格劃分，這只需將八叉樹表示法適當(dāng)改造便可做到。均勻立方體網(wǎng)格劃分的方法為：求取分析對(duì)象的包絡(luò)立方體，對(duì)包絡(luò)立方體進(jìn)行八叉樹劃分，但每次對(duì)P節(jié)和F結(jié)點(diǎn)都要?jiǎng)澐郑钡竭f歸劃分的小立方體(包括P結(jié)點(diǎn)和F結(jié)點(diǎn))的邊長或幾何逼近精度滿足要求為止，最后由八叉樹的所有P和F葉子結(jié)點(diǎn)構(gòu)成了分析對(duì)象的均勻立方體網(wǎng)格劃分。圖6.24是對(duì)某通信車進(jìn)行FDTD(時(shí)域有限差分法)分析時(shí)的均勻立方體網(wǎng)格劃分。

圖6.24某通信車的均勻立方體網(wǎng)格劃分

3.構(gòu)造表示

1)掃描表示

掃描表示是一個(gè)基體(一般是一個(gè)封閉的平面輪廓)沿著一路徑運(yùn)動(dòng)而產(chǎn)生形體。掃描表示需要兩個(gè)分量：一個(gè)是被運(yùn)動(dòng)的基體，另一個(gè)是基體運(yùn)動(dòng)的路徑。圖6.25、圖6.26分別為平移掃描、旋轉(zhuǎn)掃描生成物體的情況。掃描是生成三維形體的有效方法，其優(yōu)點(diǎn)是表示簡單、直觀，適合做圖形輸入手段。其缺點(diǎn)是不能直接獲取形體的邊界信息，表示形體的覆蓋域非常有限。

圖6.25平移掃描

圖6.26旋轉(zhuǎn)掃描

2)構(gòu)造實(shí)體幾何(ConstructionSolidGeoｍetry，CSG)表示

構(gòu)造實(shí)體幾何CSG表示是體素及中間體以二叉樹結(jié)構(gòu)進(jìn)行并、交、差布爾運(yùn)算獲得實(shí)體幾何模型的建模方法。CSG建模分為兩步：第一步定義形狀簡單的體素，如立方體、棱錐體、圓柱體、圓球體等，第二步根據(jù)需要進(jìn)行體素間的并、交、差布爾運(yùn)算，從而組成實(shí)體幾何模型。圖6.27為CSG構(gòu)造物體的過程。這種二叉樹結(jié)構(gòu)稱之為CSG樹，在一些造型系統(tǒng)中已得到應(yīng)用。可以看出，對(duì)于同一物體，其CSG樹不是唯一的。

圖6.27CSG的樹形結(jié)構(gòu)

CSG表示的優(yōu)點(diǎn)如下：

(1)數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；

(2)CSG方法表示的形體的形狀比較容易修改。

CSG表示的缺點(diǎn)如下：

(1)對(duì)形體的表示受體素的種類和對(duì)體素操作的種類的限制；

(2)CSG樹只定義了它所表示物體的構(gòu)造方式，既不反映物體的面、邊、頂點(diǎn)等邊界信息，也不像半空間法那樣顯式說明物體所占據(jù)空間的約束關(guān)系，它是表示物體的隱式模型或過程模型，故顯示與繪制CSG表示的形體需要較長的時(shí)間進(jìn)行邊界表示形式的轉(zhuǎn)換；

(3)對(duì)形體的局部操作(如倒圓角、切角等)不易實(shí)現(xiàn)；

(4)表示物體的CSG樹不唯一。

以上幾種實(shí)體造型方法各有其優(yōu)缺點(diǎn)，在造型系統(tǒng)中一般不單獨(dú)使用一種方法，而是采用幾種方法混合使用的方式，以發(fā)揮各自的長處。目前在一些系統(tǒng)中應(yīng)用的混合方法主要有以下幾種：

(1)構(gòu)造實(shí)體幾何方法(CSG)和邊界表示方法(B?Rep)的混合使用，如圖6.28所示，其中的CSG運(yùn)算就是布爾運(yùn)算。

(2)構(gòu)造實(shí)體幾何方法(CSG)、掃描方法和邊界表示方法(B?Rep)的混合使用。通過掃描方法可得到掃移、旋轉(zhuǎn)等擴(kuò)展體素，將其加入構(gòu)造實(shí)體幾何方法中可提高生成形體的幾何形狀覆蓋面。

圖6.28CSG與B?Rep的混合方法

6.1.7局部造型與歐拉操作

對(duì)物體做局部形狀改變(如倒角、倒圓角、面拉伸等)稱為局部造型。局部造型可利用歐拉操作實(shí)現(xiàn)，BUILD系統(tǒng)最早采用了歐拉操作。目前的造型系統(tǒng)中幾乎都提供了局部造型的功能。

增加或者刪除面、邊和頂點(diǎn)以生成新的物體的過程稱為歐拉操作(運(yùn)算)。歐拉操作的依據(jù)就是歐拉公式。

1.歐拉操作

最為常用的幾種歐拉操作有：

(1)產(chǎn)生一條邊和一個(gè)環(huán)(MEL)。

(2)刪除一條邊和一個(gè)環(huán)(KEL)。

(3)產(chǎn)生一個(gè)頂點(diǎn)及一條邊(MVE)。

(4)刪除一個(gè)頂點(diǎn)及一條邊(KVE)。

(5)產(chǎn)生一條邊及一個(gè)點(diǎn)(MEV)。

(6)刪除一條邊及一個(gè)點(diǎn)(KEV)。

(7)將子環(huán)變成父環(huán)(KCLMPL)。

(8)將父環(huán)變成子環(huán)(KPLMCL)。

(9)產(chǎn)生一條邊、刪除一個(gè)環(huán)(MEKL)。

(10)刪除一條邊、產(chǎn)生一個(gè)環(huán)(KEML)。

(11)產(chǎn)生一個(gè)點(diǎn)和一條零長度的邊(MVZE)。

(12)刪除一個(gè)點(diǎn)和一條零長度的邊(KVZE)。

以上十二種操作，每兩個(gè)一組，構(gòu)成了六組互為可逆的操作?？梢宰C明：

①歐拉操作是有效的，即用歐拉操作對(duì)形體操作的結(jié)果在物理上是可實(shí)現(xiàn)的；

②歐拉操作是完備的，即任何形體都可用有限步驟的歐拉操作構(gòu)造出來。

2.歐拉操作用于局部造型

可用一棵樹來描述歐拉操作造型的過程。如圖6.29所示，設(shè)A0為一空體，是樹根。

如果A11是被輸入的長方體體素，則用上述歐拉操作生成不同形體的過程如下：

(1)通過MEL操作將環(huán)F1分成兩個(gè)環(huán)F1和F2，生成的形體為A12。

(2)對(duì)F1進(jìn)行拉伸操作產(chǎn)生形體A13，對(duì)A13中的邊E1倒圓角，所產(chǎn)生的形體為A14。

(3)如果在F1和F2中選F2進(jìn)行拉伸操作，則產(chǎn)生A21形體，如果接著對(duì)A21形體的E2

邊進(jìn)行倒圓角，所產(chǎn)生的形體為A22。

(4)如果對(duì)A13形體的F3環(huán)進(jìn)行拉伸，則產(chǎn)生形體A31。

通過對(duì)形體的各部分進(jìn)行拉伸、倒角、倒圓角和切割，可產(chǎn)生各種不同的形體，而這些操作都可以用前面介紹的12種基本歐拉操作的組合來完成。

圖6.29歐拉操作造型過程

6.2實(shí)體造型中的數(shù)據(jù)結(jié)構(gòu)

實(shí)體造型中的數(shù)據(jù)包括原始的體素?cái)?shù)據(jù)、中間運(yùn)算數(shù)據(jù)和造型結(jié)果數(shù)據(jù)。對(duì)這些數(shù)據(jù)正確、方便地組織和管理成為造型成敗的關(guān)鍵，而數(shù)據(jù)結(jié)構(gòu)是保障造型的必須手段。所謂數(shù)據(jù)結(jié)構(gòu)就是在計(jì)算機(jī)內(nèi)存放數(shù)據(jù)及其關(guān)系的一種機(jī)制。數(shù)據(jù)結(jié)構(gòu)有多種，如線性表、樹、圖、串等，它是一門學(xué)科。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。

如圖6.30所示，多面體由面組成，面由環(huán)組成，環(huán)由邊組成，邊由兩個(gè)點(diǎn)構(gòu)成，體、面、環(huán)、邊、點(diǎn)由頂向下形成層次結(jié)構(gòu)，它是數(shù)據(jù)結(jié)構(gòu)中的圖結(jié)構(gòu)，圖的節(jié)點(diǎn)為體、面、環(huán)、邊、點(diǎn)，即多面體數(shù)據(jù)的邏輯結(jié)構(gòu)為圖。圖形數(shù)據(jù)結(jié)構(gòu)主要是指存儲(chǔ)結(jié)構(gòu)，如數(shù)組、鏈表、棧及其綜合等。

圖6.30立體數(shù)據(jù)的邏輯結(jié)構(gòu)?圖

1.單鏈三表數(shù)據(jù)結(jié)構(gòu)

單鏈三表結(jié)構(gòu)同時(shí)存儲(chǔ)了“面含邊的包含性”(或“面含頂點(diǎn)的包含性”)和“邊含頂點(diǎn)的包含性”，它是以面(環(huán))為中心的存儲(chǔ)結(jié)構(gòu)。鏈指的是指針(即地址)，三表是指面表、邊(棱邊)表和頂點(diǎn)表。

圖6.31是一個(gè)帶通孔的長方體，由16個(gè)頂點(diǎn)、10個(gè)面組成，其中面②、④各有一個(gè)內(nèi)環(huán)(孔)。圖6.32是其數(shù)據(jù)結(jié)構(gòu)，可以采用數(shù)組，但使用鏈表更方便。其中，面表的第一列為該面的棱邊總數(shù)；第二列為內(nèi)環(huán)數(shù)，無內(nèi)環(huán)時(shí)為0；第三列為每個(gè)面首邊的指針(地址)。圖6.31帶通孔的長方體

圖6.32單鏈三表數(shù)據(jù)結(jié)構(gòu)

單鏈三表結(jié)構(gòu)由面表的邊指針(即鏈)檢索到該面的邊表，由邊表的指針檢索到形成該邊的頂點(diǎn)。這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)是關(guān)系清楚，節(jié)省存儲(chǔ)空間，繪制和保存結(jié)果方便；其缺點(diǎn)是無鄰接關(guān)系，查找和修改拓?fù)潢P(guān)系不方便。

2.翼邊數(shù)據(jù)結(jié)構(gòu)

如圖6.33所示，所謂翼邊，是指當(dāng)我們從外面(即非材料一側(cè))觀察立體時(shí)，可以看到每一條棱邊都有左右兩個(gè)鄰面(左外環(huán)、右外環(huán))和構(gòu)成這兩個(gè)鄰面周界的四條鄰邊(左上邊LCC、左下邊LCW、右上邊RCW、右下邊RCC)，LCC、LCW、RCW、RCC好像是棱邊長出的翅膀。

圖6.33多面體的翼邊拓?fù)浣Y(jié)構(gòu)

翼邊結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)如圖6.34所示。在該數(shù)據(jù)結(jié)構(gòu)中，每個(gè)立體的信息分五層來存儲(chǔ)，即立體表、面表、環(huán)表、邊表和頂點(diǎn)表。

(1)立體(solid)表。對(duì)每個(gè)體，立體表包括指向面表的鏈表指針、指向邊表的鏈表指針、指向頂點(diǎn)表的鏈表指針、指向變換矩陣的指針。

(2)面(face)表。采用雙向鏈表+結(jié)構(gòu)體，每個(gè)面包括面方程的系數(shù)、后繼指針、前趨指針、外環(huán)指針。每個(gè)面有一個(gè)外環(huán)及若干個(gè)內(nèi)環(huán)，也可能無內(nèi)環(huán)。

(3)環(huán)(loop)表。采用雙向鏈表+結(jié)構(gòu)體，包括環(huán)的始邊號(hào)、所在面的編號(hào)(地址)、內(nèi)環(huán)號(hào)、后繼指針、前趨指針。環(huán)需要利用所在面的編號(hào)、始邊號(hào)和邊表按上述規(guī)則搜索確定。

(4)邊(edge)表。它是整個(gè)數(shù)據(jù)結(jié)構(gòu)的核心，采用雙向鏈表+結(jié)構(gòu)體，包括邊的起始頂點(diǎn)指針、終止頂點(diǎn)指針，邊的右鄰面的外環(huán)指針、左鄰面的外環(huán)指針、右上邊指針、右下邊指針、左上邊指針、左下邊指針，邊的后繼指針、前趨指針。

(5)頂點(diǎn)(vertex)表。采用雙向鏈表+結(jié)構(gòu)體，包括頂點(diǎn)坐標(biāo)(x，y，z)，頂點(diǎn)后繼指針、前趨指針。

翼邊結(jié)構(gòu)的優(yōu)點(diǎn)是存儲(chǔ)信息豐富，查找和修改方便；缺點(diǎn)是花費(fèi)存儲(chǔ)空間較多，數(shù)據(jù)結(jié)構(gòu)及其維護(hù)的程序復(fù)雜。

圖6.34翼邊數(shù)據(jù)結(jié)構(gòu)

3.半邊數(shù)據(jù)結(jié)構(gòu)

半邊即有向邊，ACIS中稱為共邊(coedge)。當(dāng)外環(huán)、內(nèi)環(huán)走向符合前面規(guī)定時(shí)，一條物理邊就可拆成兩個(gè)半邊，每個(gè)半邊只與一個(gè)鄰面相關(guān)，如圖6.35所示。

圖6.35半邊的概念

半邊數(shù)據(jù)結(jié)構(gòu)采用體、面、環(huán)、半邊(有向邊)、頂點(diǎn)五層來存儲(chǔ)立體的信息。圖6.36為半邊數(shù)據(jù)結(jié)構(gòu)的層次關(guān)系。

(1)體(solid)層。此為該結(jié)構(gòu)的頂層(即根結(jié)點(diǎn))，體通過指針sface引用面(face)。

(2)面(face)層。每個(gè)面包括4個(gè)指針，通過指針floop引用環(huán)(loop)(若存在內(nèi)環(huán)時(shí)可采用2個(gè)floop指針，一個(gè)指向外環(huán)，另一個(gè)指向該面的所有內(nèi)環(huán))，指針fsolid指向面所屬的體，指針prevf指向面的前趨，指針nextf指向面的后繼。

(3)環(huán)(loop)層。每個(gè)環(huán)包括4個(gè)指針，通過指針ledg引用半邊(halfedge)，指針lface指向環(huán)所屬的面，指針prevl指向環(huán)的前趨，指針nextl指向環(huán)的后繼。

(4)半邊(halfedge)層。每個(gè)半邊包括4個(gè)指針，通過指針vtx引用頂點(diǎn)(vertex)，指針wloop指向半邊所屬的環(huán)，指針prv指向半邊的前趨，指針nxt指向半邊的后繼。

(5)頂點(diǎn)(vertex)層。每個(gè)頂點(diǎn)用含4個(gè)浮點(diǎn)數(shù)的齊次坐標(biāo)表示，其兩個(gè)指針分別為指向前趨頂點(diǎn)的prevv和指向后繼頂點(diǎn)的nextv。

圖6.36半邊數(shù)據(jù)結(jié)構(gòu)的層次關(guān)系

4.輻射邊數(shù)據(jù)結(jié)構(gòu)

為了表示非正則形體，1986年，Weiler提出了輻射邊(RadialEdge)數(shù)據(jù)結(jié)構(gòu)，如圖6.37所示。

圖6.37輻射邊數(shù)據(jù)結(jié)構(gòu)

頂點(diǎn)是三維空間的一個(gè)位置。

邊可以是直線邊或曲線邊，邊由點(diǎn)組成。邊的端點(diǎn)可以重合(縮為一點(diǎn))。

環(huán)由首尾相接的一些邊組成，而且最后一條邊的終點(diǎn)與第一條邊的起點(diǎn)重合；環(huán)也可以是一個(gè)孤立點(diǎn)。

面由一個(gè)外環(huán)和若干個(gè)(包括零)內(nèi)環(huán)組成；面也可以是一個(gè)孤立點(diǎn)。

外殼是一些點(diǎn)、邊、面的集合，外殼所含的面集有可能圍成封閉的三維區(qū)域，從而構(gòu)成一個(gè)實(shí)體；外殼還可以表示任意的一張曲面或若干個(gè)曲面構(gòu)成的面組；外殼還可以是一條邊或一個(gè)孤立點(diǎn)。

區(qū)域由一組外殼組成。

模型由區(qū)域組成。

ACIS系統(tǒng)采用了輻射邊數(shù)據(jù)結(jié)構(gòu)。

6.3.1三維布爾運(yùn)算算法

1.三維布爾運(yùn)算與降維處理

實(shí)現(xiàn)三維布爾運(yùn)算的出發(fā)點(diǎn)是降維處理。降維處理的過程為：將體與體的三維運(yùn)算先轉(zhuǎn)化為一個(gè)體的每個(gè)平面與另一個(gè)體求交，而平面與體求交的本質(zhì)是平面與這個(gè)物體的所有面求交，求交結(jié)果得到剖面，然后進(jìn)行平面與剖面的二維布爾運(yùn)算，從而將三維問題轉(zhuǎn)化為二維問題來處理。

6.3三維布爾運(yùn)算的實(shí)現(xiàn)

2.三維布爾運(yùn)算的原理

以圖6.38(a)所示兩個(gè)長方體為例，長方體A和B有部分相交，即A物體的前面、左面、底面與B物體的頂面、右面、后面相交，求兩個(gè)物體布爾運(yùn)算的結(jié)果。

圖6.38三維布爾運(yùn)算的原理

1)三維并運(yùn)算

根據(jù)前述并運(yùn)算的數(shù)學(xué)定義，三維并運(yùn)算的基本規(guī)則如下：

(1)如果一個(gè)物體的面完全在另一個(gè)物體的內(nèi)部，則該面不出現(xiàn)在并運(yùn)算結(jié)果中。

(2)如果一個(gè)物體的面完全在另一個(gè)物體的外部，則該面應(yīng)該在并運(yùn)算的結(jié)果中，該面稱為保留面。

(3)如果一個(gè)物體的面和另一個(gè)物體的面相交(包括共面)，則該面將會(huì)根據(jù)相交的情況作出修改，即該面拓?fù)湫畔⑿枰貥?gòu)，稱該面為修改面。

最后，三維并運(yùn)算的結(jié)果將由兩個(gè)物體的保留面和修改面組成。

現(xiàn)在研究第三種情況———兩個(gè)物體的面相交，這里的面為有限平面圖形，即簡單多邊形。

圖6.38(a)所示長方體A中的前面｛1-2-3-4-1｝，稱為原面，記為FA，它與長方體B的頂面｛3′-7′-8′-4′-3′｝及右面｛2′-6′-7′-3′-2′｝相交(交線分別為10-11、11-12)，因此，A中的面FA

將被修改。

參見圖6.38(b)，為了求取面FA

運(yùn)算后得到的修改面，通過該面所在的足夠大平面(記為Π)去截取另一物體B，得到B的一“剖面”｛11-16′-17′-18′-11｝，該剖面記為FB。此時(shí)，在FA所在的大平面Π上有

在這個(gè)大平面Π上執(zhí)行二維布爾運(yùn)算中的差運(yùn)算：

即把原面減去剖面，就可以得到FA的修改面F。

令FA＝F，新的FA就是三維并運(yùn)算的一個(gè)組成面(即修改面)。

按照上述三維并運(yùn)算的規(guī)則，圖6.38(a)所示的兩個(gè)長方體A和B并運(yùn)算的結(jié)果為12個(gè)面，包括6個(gè)保留面和6個(gè)修改面，如表6.2所示。

求物體A的保留面和修改面的三維并運(yùn)算算法要點(diǎn)如下：

(1)當(dāng)大平面Π截取不到物體B的剖面時(shí)，同前面的基本規(guī)則(2)，原面FA

為“保留面”，存放在集合AoutB中(集合可以用鏈表存儲(chǔ)，下同)。

(2)當(dāng)FA與FB相離，F(xiàn)A-FB差運(yùn)算的結(jié)果與原面相同，即F＝FA，同前面的基本規(guī)則

(2)，原面FA為“保留面”，存放在集合AoutB中。

(3)當(dāng)FA與FB

相交或FB

?FA時(shí)(FA與FB

可含有內(nèi)環(huán))，則F=FA-FB

，得到“修改面”，存放在集合AoutB中。

(4)當(dāng)FA?FB時(shí)(內(nèi)含)，此時(shí)F=?，即差運(yùn)算的結(jié)果不存在，同前面的基本規(guī)則(1)，原面FA被舍去。

(5)特殊情況下，當(dāng)兩個(gè)物體共面貼并且共面的兩個(gè)面外法矢量同向時(shí)，將共面的兩個(gè)面進(jìn)行二維布爾并運(yùn)算，其結(jié)果作為新物體的一個(gè)面存放在集合AonB中，共面的兩個(gè)原面被舍去。

2)三維交運(yùn)算

求兩物體公共部分的布爾運(yùn)算稱為交運(yùn)算。三維交運(yùn)算的基本規(guī)則如下：

(1)如果一個(gè)物體的面完全在另一個(gè)物體的外部，則該面不出現(xiàn)在交運(yùn)算結(jié)果中；

(2)如果一個(gè)物體的面完全在另一個(gè)物體的內(nèi)部，則該面應(yīng)該在交運(yùn)算的結(jié)果中，該面成為保留面；

(3)如果一個(gè)物體的面和另一個(gè)物體的面相交(包括共面)，則該面將會(huì)根據(jù)相交的情況作出修改，即該面拓?fù)湫畔⑿枰貥?gòu)，該面成為修改面。此時(shí)，拓?fù)湫畔⒅貥?gòu)的方法是原面與剖面求二維交運(yùn)算。

最后，三維交運(yùn)算的結(jié)果將由兩個(gè)物體的保留面和修改面組成。

設(shè)原面記作FA，剖面記作FB。求物體A的保留面和修改面的三維交運(yùn)算的算法要點(diǎn)如下：

3)三維差運(yùn)算

4)剖面FB的求取

剖面FB的求取方法為：把物體A上的任一面FA所在的足夠大平面Π與待求剖面的物體B的各面依次求交(即前述所講的面與面求交)，再把所得的線段按端點(diǎn)重合連接成環(huán)并使環(huán)面的外法矢量方向與A物體上面FA的外法矢量方向相同，便可得到剖面FB。

如圖6.38(b)所示，通過面FA=｛1-2-3-4-1｝所在的足夠大平面Π去截另一物體B，得到四條交線段連接的環(huán)(即剖面)FB=｛11-16′-17′-18′-11｝，剖面FB的環(huán)的方向與截切面FA的環(huán)的方向相同。

從上面的分析可以看出：兩平面圖形(環(huán))之間的二維布爾運(yùn)算(差運(yùn)算、并運(yùn)算、交運(yùn)算)是算法實(shí)現(xiàn)的關(guān)鍵。

6.3.2二維布爾運(yùn)算算法

1.二維布爾運(yùn)算中的圖形描述

一個(gè)平面圖形由一個(gè)外環(huán)和若干個(gè)(包括零個(gè))內(nèi)環(huán)描述。環(huán)有方向，外環(huán)按逆時(shí)針走向，內(nèi)環(huán)為順時(shí)針走向。圖6.39的數(shù)據(jù)結(jié)構(gòu)描述了由一個(gè)外環(huán)和一個(gè)內(nèi)環(huán)構(gòu)造的平面圖形。

平面圖形的數(shù)據(jù)結(jié)構(gòu)由四部分組成：

(1)頂點(diǎn)表：用二維數(shù)組XY(NV，2)或鏈表存儲(chǔ)各頂點(diǎn)的x、y坐標(biāo)，NV表示頂點(diǎn)數(shù)。

(2)邊表：用一維數(shù)組或鏈表LINE(LIN)存儲(chǔ)，一個(gè)環(huán)一個(gè)邊表，按環(huán)頂點(diǎn)順序存放，即外環(huán)逆時(shí)針點(diǎn)序，內(nèi)環(huán)順時(shí)針點(diǎn)序，相鄰兩個(gè)頂點(diǎn)連接為一條邊。

(3)環(huán)表：用二維數(shù)組LOOP(LOP，2)或鏈表存儲(chǔ)，LOOP(i，1)(第2列)指向本環(huán)首頂點(diǎn)號(hào)在LINE中的位置，LOOP(i，0)(第1列)指向本環(huán)末頂點(diǎn)號(hào)在LINE中的位置。

(4)面表：用二維數(shù)組FACE(FACE，2)或鏈表存儲(chǔ)，F(xiàn)ACE(i，1)(第2列)指向該平面圖形所包含的首環(huán)即外環(huán)的地址，F(xiàn)ACE(i，0)(第1列)指向該平面圖形所包含的終環(huán)的地址。

圖6.39平面圖形的數(shù)據(jù)結(jié)構(gòu)

2.二維布爾運(yùn)算的基本思想

為了說明二維布爾運(yùn)算的算法思想，我們以有交點(diǎn)的兩個(gè)面素(簡單多邊形稱為面素)為例作一說明。

如圖6.40(a)所示，假設(shè)有三角形123和四邊形4567這兩個(gè)面素，分別用A和B表示，它們有兩個(gè)交點(diǎn)P1和P2。A與B求布爾運(yùn)算的結(jié)果如圖6.40(b)所示。由圖可見，兩面素之間的運(yùn)算可歸結(jié)為A環(huán)和B環(huán)之間的運(yùn)算，運(yùn)算后的新環(huán)是由兩面素的一部分老邊界組成的，新環(huán)的走向是在原環(huán)的交點(diǎn)處改