三維幾何模型在計算機內(nèi)的表示

1、三維幾何模型在計算機內(nèi)的表示CAD/CAM的核心技術(shù)是幾何造型技術(shù)一項研究在計算機中如何表示物體模型形狀的技術(shù)。在CAD/CAM技術(shù)四十多年的發(fā)展歷程中，經(jīng)歷了四次重大的變革。60年代初期的CAD系統(tǒng)只能處理簡單的線框模型，提供二維的繪圖環(huán)境，用途比較單一。進(jìn)入70年代，根據(jù)汽車造型中的設(shè)計需求，法國人提出了貝塞爾算法，隨之產(chǎn)生了三維曲面造型系統(tǒng)CATIA。它的出現(xiàn)，標(biāo)志著CAD技術(shù)從單純模仿工程圖紙的三視圖模式中解放出來，首次實現(xiàn)以計算機完整描述產(chǎn)品零件的主要信息。這是CAD發(fā)展歷史中的第一次重大飛躍。1979年，SDRC公司發(fā)布了世界上第一個完全基于實體造型技術(shù)的大型CAD/CAE軟件ID

2、EAS。由于實體造型技術(shù)能夠精確表達(dá)零件的全部屬性，在理論上有助于統(tǒng)一CAD、CAE、CAM的模型表達(dá)，給設(shè)計帶來了驚人的方便性。可以說，實體造型技術(shù)的普及應(yīng)用標(biāo)志著CAD發(fā)展史上的第二次技術(shù)革命。但是，在當(dāng)時的硬件條件下，實體造型的計算及顯示速度太慢，限制了它在整個行業(yè)的推廣。90年代初期，參數(shù)化技術(shù)逐漸成熟，標(biāo)志著CAD技術(shù)的第三次革命。參數(shù)化技術(shù)的成功應(yīng)用，使得它在1990年前后幾乎成為CAD業(yè)界的標(biāo)準(zhǔn)。隨后，SDRC攻克了欠約束情況下全參數(shù)的方程組求解問題，形成了一套獨特的變量化造型理論。SDRC將變量化技術(shù)成功的應(yīng)用到CAD系統(tǒng)中，標(biāo)志著CAD技術(shù)的第四次革命。隨著CAD技術(shù)和幾何造

3、型技術(shù)的發(fā)展， 近年來， 市場上出現(xiàn)了一大批優(yōu)秀的幾何造型軟件及工具。例如，PTC公司的產(chǎn)品Pro/E、SDRC的產(chǎn)品I-DEAS Master Series、UGS公司的產(chǎn)品Unigraphics、IBM公司的產(chǎn)品CATIA/CADAM、Autodesk公司的產(chǎn)品MDT、Spatial Tech公司的ACIS、EDS公司的Parasolid等。在國內(nèi)，清華大學(xué)、北京航空航天大學(xué)、華中理工大學(xué)、浙江大學(xué)、上海交通大學(xué)、西北工業(yè)大學(xué)，以及其他一些單位也發(fā)表了一些關(guān)于特征造型技術(shù)研究的論著，并開發(fā)了一些特征造型系統(tǒng)，例如：清華大學(xué)開發(fā)的TiGems造型系統(tǒng)，北京航空航天大學(xué)研制出的微機版“金銀花(

4、LONICERA)”系統(tǒng)，武漢開目信息技術(shù)有限責(zé)任公司開發(fā)的開目三維CAD軟件等等。造型系統(tǒng)簡介Parasolid和ACIS是兩個最有代表性的幾何造型系統(tǒng)的開發(fā)平臺。在早期開發(fā)的實體造型系統(tǒng)中，英國的劍橋大學(xué)研制出了BUILD-1和BUILD-2系統(tǒng)，但都沒有公開使用。80年代初期，研究小組的一部分人組建了Shape Data公司，并開發(fā)了實體造型系統(tǒng)Romulus。1986年，Shape Data并入EDS Unigraphics之后，推出了功能強大的幾何造型核心Parasolid。同時，Shape Data一部分保留人員研制了新的造型核心，就是后來由Spatial Technology公司

5、推出的幾何造型系統(tǒng)核心ACIS。Parasolid和ACIS并不是面向最終用戶的應(yīng)用系統(tǒng)，而是“幾何引擎”，作為應(yīng)用系統(tǒng)的核心。用戶可用它們作為平臺，開發(fā)自己的應(yīng)用系統(tǒng)。當(dāng)今許多流行的商用CAD/CAM軟件，如Unigraphics、Solidedge、Solidwork、MDT等，都是在Parasolid或ACIS的基礎(chǔ)上開發(fā)出來的。Parasolid有較強的造型功能，但是只能支持正則實體造型。它提供的主要功能有：集合運算、特征的創(chuàng)建和編輯、局部操作、數(shù)據(jù)交換文件接口等。Parasolid采用精確的邊界表示，包括拓?fù)洹缀魏完P(guān)聯(lián)三種數(shù)據(jù)類型。ACIS具有和Parasolid相似的形體結(jié)構(gòu)，但

6、在系統(tǒng)結(jié)構(gòu)上采用了核心和外殼相結(jié)合的方式。ACIS支持線框、表面和實體的統(tǒng)一表示，支持非正則形體的造型。在上述幾何實體造型系統(tǒng)中，通常都會提供一些基本的形體輸入方法，以及拉伸，旋轉(zhuǎn)，蒙皮，掃描等直接構(gòu)造形體的方法，通過集合運算對形體進(jìn)行拼合。雖然對這些造型方法的研究取得了一系列新進(jìn)展，但是集合運算仍基本局限在對兩個體進(jìn)行正則運算(交，并，差)上，而且結(jié)果形體的信息都已經(jīng)包含在兩個參加運算的原始形體之中，不能引入新的信息。實際應(yīng)用中，有些機械零件具有特定的形狀特征，不能通過集合運算來直接完成，或者直接實現(xiàn)時操作步驟非常復(fù)雜。但是，它們的生成方法和集合運算非常相似，可以看作是集合運算的擴展。拔模和

7、抽殼都屬于這一類型的造型方法。三維形體的表示三維造型技術(shù)是建立恰當(dāng)?shù)哪Ｐ蛠肀硎咀匀唤缰行螒B(tài)豐富的三維物體的技術(shù)，根據(jù)造型對象將造型技術(shù)分成3類。第一類是曲面造型，主要研究計算機內(nèi)如何描述一張曲面，及曲面的顯示與控制。曲面造型又分成規(guī)則曲面和不規(guī)則曲面兩種。不規(guī)則曲面造型方法主要有貝塞爾曲線曲面、B樣條曲線曲面和孔斯曲面等。（二維曲線：Nurbs（通過擬合點）、三次B樣條（通過控制點）、貝塞爾（控制點和擬合點重合）和波浪線（B樣條）第二類是立體造型方法，主要研究在計算機內(nèi)如何定義、表示一個三維物體，主要有體素構(gòu)造法、邊界表示法和八叉數(shù)法等等。曲面造型和立體造型合稱幾何模型造型。該技術(shù)主要應(yīng)用在機

8、械行業(yè)輔助設(shè)計制造領(lǐng)域（CAD）。第三類是自然景物模擬，主要研究在計算機內(nèi)如何模擬自然景物，如云、流水、樹等。該造型技術(shù)主要應(yīng)用在游戲和藝術(shù)造型等領(lǐng)域。如下主要說說幾何模型的表示。在計算機中，表示幾何形體的方法通常有三種：線框模型、表面模型和實體模型一、線框模型該模型采用三維形體的全部頂點及邊的集合來描述三維形體，即用頂點表和邊表兩個表的數(shù)據(jù)結(jié)構(gòu)來表示三維模型。每條邊由兩個頂點表示。主要優(yōu)點是結(jié)構(gòu)簡單，處理容易。描述二維目標(biāo)十分理想。但對三維物體，存在如下缺點：1）沒有面的信息，它不能表示表面含有曲面的物體。2）不能明確定義點與物體之間的關(guān)系。3）點和邊信息容易出現(xiàn)二義性。二、表面模型在線框模

9、型的基礎(chǔ)上，增加了物體中的面的信息，用面的集合來表示物體，每個面由多條有向邊構(gòu)成，用環(huán)來定義面的邊界，即是用頂點表、邊表和面表來描述模型。表面模型又分為平面模型和曲面模型。前者以多邊形網(wǎng)格為基礎(chǔ)。后者以參數(shù)曲面塊為基礎(chǔ)。表面模型存在的不足就是它只能表示物體的表面邊界，而不能表達(dá)出真實實體的屬性，很難確認(rèn)一個表面模型表示的三維圖形是一個實體還是一個空殼。這個不足，在實體模型中得到了解決。三、實體模型實體模型是最高級的模型，它能完整表示物體的所有形體信息，可以無歧義地確定一個點是在物體外部還是內(nèi)部或表面上。實體模型使用有向邊的右手法則來確定所在面的外法線方向。即用右手沿邊的順序方向握住，大拇指所指

10、向為該面的外法線方向。法線方向指向體外。體外實體模型存在著不同的數(shù)據(jù)結(jié)構(gòu)，在這些結(jié)構(gòu)中存在一個共同點，即數(shù)據(jù)結(jié)構(gòu)不僅記錄了物體全部的幾何信息，而且還記錄了所有的點、線、面、體的拓?fù)湫畔ⅲ纯臻g位置關(guān)系）。實體模型的構(gòu)造通常使用體素（即原始的基本實體），經(jīng)集合論中的交、并、差運算構(gòu)成復(fù)雜形體。1實體的定義實體就是有效的物體，即客觀世界中確實存在的物體，要在計算機內(nèi)表示、構(gòu)造一個實體，就必須給出實體的確切定義（即用最小的數(shù)據(jù)結(jié)構(gòu)唯一地確定實體的形狀和位置。）如下圖帶有懸掛面的立方體就不是實體，在客觀世界中不可能存在這樣的物體。作為實體應(yīng)滿足如下條件：1剛性。一個實體必須具有一定的形狀（流體不屬于實

11、體）2維數(shù)一致性。一個實體的各個部分必須是三維的，不能存在懸掛的、孤立的邊界。3有限性。一個實體必須占有有限的空間。4邊界確定性。根據(jù)實體的邊界，可確定實體的內(nèi)部或外部。5封閉性。經(jīng)過集合運算后，仍然是有效的實體。實體的表面必須具備如下性質(zhì)：1連通性。表面任意兩點都可用表面上的一條路徑連接起來。2邊界性。3非自相交性。一個實體表面不可自相交。4可定向性。一個實體的表面兩則可明確定義出實體的內(nèi)側(cè)和外側(cè)。5封閉性。一個表面的封閉性由多邊形網(wǎng)格各元素的拓?fù)潢P(guān)系確定的。即每條邊連接且僅連接兩個面，每條邊有且僅有兩個端點。 從點集拓?fù)浣嵌冉o出實體的定義。將三維實體看作是空間中點的集合，它由內(nèi)點與邊界點共

12、同組成。 內(nèi)點是指點集中的這樣一些點：它們具有完全包含于該點集的充分小的領(lǐng)域。點集中除內(nèi)點外的所有的點就是邊界點。所以三維物體A可表示為：A= bA，iAbA為物體A的邊界點集；iA為物體A的內(nèi)部點集。定義點集的正則運算r如下:rA = ciAi為取A的內(nèi)點運算；c為取閉包運算；A為一個點集。iA為A的全體內(nèi)點組成的集合，稱為A的內(nèi)部，它是一個開集（“開集”可以理解為沒有邊界值去判斷點是否為內(nèi)點）。ciA為A的內(nèi)部的閉包，是iA與其邊界點的并集。（據(jù)此可以理解“閉包”的含義），它本身是一個閉集，（“閉集”可以理解為可以通過明確的邊界值來判斷點是否在集合中）。正則運算即為：先對物體取內(nèi)點再取閉包

13、的運算。rA稱為物體A的正則點集。如圖：帶有懸邊的二維點集A內(nèi)點集合iA(沒有粗邊界)正則點集ciA(有粗邊界)以上圖中，圖1有懸邊所以點集不是有效實體，圖2沒有邊界，不是滿足“封閉性”所以也不是實體。圖3為正則點集，封閉性，也滿足實體的其他條件，所以為實體。正則點集有時也不一定是實體。如下圖：左圖為正則點集，但它不是有效的物體。由此，就會涉及到另外一個概念“二維流體”。二維流體是指對于實體表面上的任何一點，都可以找到一個圍繞著它的任意小的領(lǐng)域，該領(lǐng)域在拓?fù)洌词强臻g位置）上與平面上的一個圓盤是等價的（也就是在表面上存在著一個領(lǐng)域圍繞著某個點）。這意味著，在領(lǐng)域的點集和圓盤之間存在著連續(xù)的一對

14、一的對應(yīng)關(guān)系。如上右圖，立體表面上任一點都存在與圓盤同構(gòu)的領(lǐng)域。而左圖，兩個立方體共享邊被四個面共享，其上的點不存在這樣的唯一的領(lǐng)域（在上圖中，共享邊的點，存在圍繞它的領(lǐng)域有兩個）。有了上述概念后，實體可以這樣描述為：對于一個占據(jù)有限空間的正則點集，如果其表面是二維流形，則該正則點集為實體（有效物體）。2正則集合運算能產(chǎn)生正則幾何體（有正則點集組成的形體）的集合運算稱為正則集合運算。正則集合運算與傳統(tǒng)集合運算的區(qū)別主要是在對產(chǎn)生結(jié)果的邊界面的處理上，其內(nèi)部點的處理是一致的。正則運算主要是考慮如何消除或不產(chǎn)生懸點、懸邊和懸面。如下圖：上圖，左邊為傳統(tǒng)的交運算結(jié)果，右邊為正則的交運算結(jié)果。在傳統(tǒng)的

15、集合運算符后加“*”號表示正則運算符。實現(xiàn)正則集合運算有兩種方法：間接法和直接法。間接法是先按普通集合運算求出結(jié)果，后用一些規(guī)則判斷，以消除不符合正則幾何定義的部分（即懸邊、懸面等），從而得到正則幾何體。直接法是定義正則集合算子的表達(dá)式，用以直接得出符合正則幾何體定義的結(jié)果。正則幾何運算定義如下：A* B = r( A B ) ;式中表示傳統(tǒng)集合并、交、差算子；*表示相應(yīng)的正則并、交、差算子；r是集合的正則化算子。實體造型是以立方體、圓柱體、球體、錐體、環(huán)狀體等多種基本體素為單位元素，通過集合運算(拼合或布爾運算)，生成所需要的幾何形體。這些形體具有完整的幾何信息，是真實而唯一的三維物體。所以

16、，實體造型包括兩部分內(nèi)容：即體素定義和描述，以及體素之間的布爾運算(并、交、差)。布爾運算是構(gòu)造復(fù)雜實體的有效工具。目前常用的實體表示方法主要有：構(gòu)造實體幾何法(CSG)、邊界表示法(BRep)和掃描法。物體的CSG樹表示物體的體素構(gòu)造表示法（Constructive Solid Geometry, CSG）是用兩個物體間的并、交、差正則集合運算操作生成一個新的物體的方法。CSG表示法：先定義一些形狀比較簡單的常用體素，如方塊、圓柱、圓錐、球、棱柱等。然后用集合運算并、交、差把體素修改成復(fù)雜形狀的形體。早期的CSG模型僅使用代數(shù)方程及半空間的概念，體素只支持多面體與二次曲面體，而不支持表面含有

17、自由曲面的實體。整個模型是棵樹結(jié)構(gòu)，最終形體的表面交線與有效區(qū)域沒有顯式給出，不能直接用于NC加工與有限元分析等后繼處理。集合運算構(gòu)造實體的過程可用二叉樹結(jié)構(gòu)表示，稱該二叉樹為CSG樹。樹的葉節(jié)點表示體素或帶有幾何變換參數(shù)的體素，非葉節(jié)點表示施加于其子節(jié)點的正則集合算子，或稱布爾算子。樹的根節(jié)點表示集合運算的最終結(jié)果，也即希望得到的實體。邊界表示法邊界表示法（Brep-Boundary Representation）通過描述物體的邊界來表示一個物體。所謂的邊界是指物體的內(nèi)部點與外部點的分界面，定義了物體的邊界，該物體也就被唯一地定義了。如下圖：邊界表示法一個重要的特點是：描述物體的信息包括幾何

18、信息與拓?fù)湫畔蓚€方面。幾何信息是指物體在歐氏空間中的位置、形狀和大?。欢?fù)湫畔⑹侵竿負(fù)湓兀旤c、邊和表面）的數(shù)量及其相互間的連接關(guān)系。拓?fù)湫畔?gòu)成物體的“骨架”，而幾何信息則猶如附著在這一“骨架”上的“肌肉”。幾何信息有面（face）、環(huán)（loop）、邊（edge）和點（vertex），拓?fù)湫畔⒂心Ｐ停╩odel）、 區(qū)域（region）、外殼（shell）、面引用（face use）、環(huán)引用（loop use）、邊引用（edge use）和點引用（vertex use）。如下圖是用輻射邊數(shù)據(jù)結(jié)構(gòu)表示的一個形體模型，注意其中實體、面、線是用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)表示的。頂點頂點（Vertex）的

19、位置用（幾何）點（Point）來表示。點是幾何造型中的最基本的元素，自由曲線、曲面或其它形體均可用有序的點集表示。用計算機存儲、管理、輸出形體的實質(zhì)就是對點集及其連接關(guān)系的處理。在正則形體定義中，不允許孤立點存在。邊邊（Edge）是兩個鄰面(對正則形體而言)、或多個鄰面(對非正則形體而言)的交集，邊有方向，它由起始頂點和終止頂點來界定。邊的形狀（Curve）由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點或型值點來描述，也可用顯式、隱式或參數(shù)方程來描述。形體中與一條空間曲線相聯(lián)系，以及包含其兩個端點和引用它的所有環(huán)邊等信息的拓?fù)湓胤Q為邊。環(huán)環(huán)（Loop）是有序、有向邊（Edge

20、）組成的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個端點。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時針方向排序，內(nèi)環(huán)邊通常按順時針方向排序。面面（Face）由一個外環(huán)和若干個內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。根據(jù)環(huán)的定義，在面上沿環(huán)的方向前進(jìn)，左側(cè)總在面內(nèi)，右側(cè)總在面外。面有方向性，一般用其外法矢方向作為該面的正向。若一個面的外法矢向外，稱為正向面；反之，稱為反向面。面的形狀（Surface）由面的幾何信息來表示，可以是平面或曲面，平面可用平面方程來描述，曲面可用控制多邊形或型值點來描述，也可用曲面方程（隱式、顯式或參數(shù)形式）來描述。對于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可

21、由一些二維的有向邊來表示環(huán)，集合運算中對面的分割也可在二維參數(shù)域上進(jìn)行。體體（Body）是面的并集。在正則幾何造型系統(tǒng)中，要求體是正則的，非正則形體的造型技術(shù)將線框、表面和實體模型統(tǒng)一起來，可以存取維數(shù)不一致的幾何元素，并可對維數(shù)不一致的幾何元素進(jìn)行求交分類，從而擴大了幾何造型的形體覆蓋域。 幾何形體是由封閉表面圍成的空間，是歐氏空間中非空、有界的封閉子集，其邊界是有限個面的并集。外殼外殼是一些點、邊、環(huán)、面的集合,其所含的面集有可能圍成封閉的三維區(qū)域，從而構(gòu)成一個實體；外殼還可以表示任意的一張曲面或若干個曲面構(gòu)成的面組；外殼還可以是一條邊或一個孤立點。外殼中的環(huán)和邊有時被稱為“線框環(huán)”和“線

22、框邊”，這是因為它們可以用于表示形體的線框圖。區(qū)域由一組外殼組成，而模型由區(qū)域組成。正則形體對于任一形體，如果它是三維歐氏空間R3中非空、有界的封閉子集，且其邊界是二維流形(即該形體是連通的)，則稱該形體為正則形體，否則稱為非正則形體。在這種表示法中，由于物體的點、邊和表面以獨立對象的形式的存在，所以可以方便地對物體進(jìn)行各種局部修改。多面體的頂點、邊和表面之間的拓?fù)潢P(guān)系可用9種不同的形式予以描述：1頂點相鄰性，表示 v-v2頂點邊相鄰性，表示v-e3頂點面相鄰性，表示v-f4邊頂點， e-v5邊邊 e-e6邊面 e-f7面頂點 f-v8面邊 f-e9面面 f-f邊界表示的數(shù)據(jù)結(jié)構(gòu)兩種典型的邊界

23、表示法數(shù)據(jù)結(jié)構(gòu)主要包括：翼邊結(jié)構(gòu)，雙向邊表(DCELDoubly Connected Edge List) ，半邊結(jié)構(gòu)，四邊結(jié)構(gòu)，輻射邊(Radial-Edge)結(jié)構(gòu)等等。其中半邊結(jié)構(gòu)非常適合表示正則形體。翼邊結(jié)構(gòu)在頂點、邊、表面等組成物體的三要素中，翼邊結(jié)構(gòu)以邊為中心來組織數(shù)據(jù)。如下圖：struct EdgeVertex P1,P2;Loop *LeftLoop,*RightLoop;struct Edge *ercw,*ercc,*elcc,*elcw;上圖菱邊e作為有向線段，其數(shù)據(jù)結(jié)構(gòu)中包含有兩個指針，分別指向e的兩個端點：起點P1和終點P2。此外，e中還設(shè)置有兩個環(huán)指針，分別指向菱邊e

24、所鄰接的兩表面上的環(huán)Loop左和Loop右。這樣就確定了菱邊e與相鄰表面之間的拓?fù)潢P(guān)系。為了能從邊e出發(fā)找到它所在的任一閉合面環(huán)上的其他菱邊，在e中又增加了四個邊指針ercw、ercc、elcc、elcw，ercc表示e在右面環(huán)中沿逆時針方向所連接的下一條菱邊，elcw表示e在左面環(huán)中沿順時針方向所連接的下一條邊，余類推。由于翼邊結(jié)構(gòu)邊的構(gòu)造和使用比較復(fù)雜，后來在此結(jié)構(gòu)基礎(chǔ)上改進(jìn)，提出了半邊數(shù)據(jù)結(jié)構(gòu)。半邊結(jié)構(gòu)已成為邊界表示的主流數(shù)據(jù)結(jié)構(gòu)。半邊數(shù)據(jù)結(jié)構(gòu)實體的B-rep表示模型是一非常復(fù)雜的模型，要求能夠表達(dá)出多面體各幾何元素之間完整的幾何和拓?fù)潢P(guān)系，并且允許對這種幾何和拓?fù)潢P(guān)系進(jìn)行修改.在B-r

25、ep表示中，體、面、邊和頂點是最基本的幾何元素，在實體的拼合、顯示、分析計算或人機交互過程中，對基本幾何元素的下列操作是必不可少的：l 增加或刪除體、面、邊或頂點；l 已知一個體，查找它的所有面、所有邊或所有頂點；l 已知一個面或一個邊，查找它所屬于的體；l 已知一個面，順序查找圍成它所有邊；l 已知一個邊，查找交于該邊的所有面，或著查找該邊的鄰邊，或者查找該邊的兩個端點；l 已知一個頂點，查找交于該頂點的所有邊或所有面。以上這些基本操作的效率直接影響著整個實體造型系統(tǒng)的效率。一個B-rep數(shù)據(jù)結(jié)構(gòu)應(yīng)當(dāng)方便、迅速地實現(xiàn)幾何元素的這些查詢或增刪操作為了查詢或操作方便，必須建立各幾何元素間的拓?fù)潢P(guān)

26、系，且引入其它輔助元素，例如在許多B-rep數(shù)據(jù)結(jié)構(gòu)中具有環(huán)結(jié)點，用來表示面的內(nèi)、外封閉邊界在B-rep的數(shù)據(jù)結(jié)構(gòu)設(shè)計時，除了需要考慮時間的因素外，還要考慮空間的因素，即模型所占計算機內(nèi)存的大小，但往往這兩方面是互相矛盾的要想各個幾何元素之間查詢迅速，必然要在它們之間建立廣泛的聯(lián)系，這樣必然增加存儲空間的占用量。反過來也是如此，而半邊數(shù)據(jù)結(jié)構(gòu)就很好的權(quán)衡了空間和時間的問題。在構(gòu)成多面體的三要素（點、邊、面）中，半邊數(shù)據(jù)結(jié)構(gòu)仍以邊為核心，但為了方便表達(dá)拓?fù)潢P(guān)系，它將一條邊表示成拓?fù)湟饬x上方向相反的兩條“半邊”，所以稱為半邊數(shù)據(jù)結(jié)構(gòu)，其結(jié)構(gòu)入圖：半邊數(shù)據(jù)結(jié)構(gòu)共包含六個結(jié)點：體、面、環(huán)、邊、半邊和頂點.半邊是一連接兩個頂點并具有一固定方向的線段.一系列首尾相連的半邊形成一個環(huán).半邊的關(guān)系