第七章 圖形的表示

第7章圖形的表示圖形的表示方法一直是計(jì)算機(jī)圖形學(xué)關(guān)注的主要問(wèn)題。在計(jì)算機(jī)圖形學(xué)發(fā)展的旱期，計(jì)算機(jī)圖形系統(tǒng)的性能較差，線框模型是表示三維物體的主要方法。線框模型僅僅通過(guò)定義物體邊界的直線和曲線來(lái)表示三維物體，其特點(diǎn)是模型簡(jiǎn)單目運(yùn)算速度較快，但由于每一條直線或四線都是單獨(dú)構(gòu)造出來(lái)的，不存在面的信息，因此三維物體信息的表示不全面，在許多場(chǎng)合不能滿足要求。事實(shí)上，研究表示復(fù)雜形體的模型與數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)造型等技術(shù)的關(guān)鍵。經(jīng)過(guò)近20年的發(fā)展，買(mǎi)體的邊界表示法、掃描表示法、構(gòu)造的實(shí)體幾何法及八叉樹(shù)表示法等已經(jīng)發(fā)展成熟。圖形的表示方法是研究如何利用計(jì)算機(jī)圖形系統(tǒng)采表示、控制、分析和輸出三維形體，是計(jì)算機(jī)圖形學(xué)的一個(gè)重要研究領(lǐng)域，它不但是CAD/CAM和CIMS系統(tǒng)的核心技術(shù)，還是實(shí)現(xiàn)計(jì)算機(jī)輔助設(shè)計(jì)的技術(shù)基礎(chǔ)。本章將重點(diǎn)學(xué)習(xí)實(shí)體的邊界表示及其數(shù)據(jù)結(jié)構(gòu)，包括圖形表示的基本概念l掃描表示法、構(gòu)造的實(shí)體幾何法、八叉樹(shù)表示法。7.1、實(shí)體與圖形7.2、實(shí)體表示的三種模型7.3、邊界表示法7.4、掃描表示法7.5、構(gòu)造的實(shí)體幾何法7.6、八叉樹(shù)表示法7.1實(shí)體與圖形實(shí)體的定義圖形的基本元素圖形的幾何信息與拓?fù)湫畔⒅敝?0世紀(jì)70年代末期，關(guān)于三維物體的表示和構(gòu)造并未建立起嚴(yán)密的理論，多數(shù)情況下靠用戶來(lái)檢查物體模型的有效性、惟一性和完備性。隨著模型復(fù)雜程度的提高，以及實(shí)體模型作為計(jì)算機(jī)輔助設(shè)計(jì)中某些應(yīng)用的輸入而加以運(yùn)算和處理，使得通過(guò)人的干預(yù)來(lái)檢查模型的有效性變得越來(lái)越困難。要想通過(guò)計(jì)算機(jī)表示、構(gòu)造一個(gè)實(shí)體，首選必須對(duì)什么是實(shí)體右一個(gè)確切的定義，并據(jù)此檢查所構(gòu)造的實(shí)體的有效性。什么是客觀存在的有效實(shí)體呢？有效實(shí)體一般具有一定的形狀、封閉的邊界或表面，內(nèi)部連通，占據(jù)有限的空間，經(jīng)過(guò)運(yùn)算后，仍是有效的物體。美國(guó)沃爾克爾（H.B.Voelcker）及雷契切（A.A.G.Requicha）等人基于點(diǎn)集拓?fù)涞睦碚?，認(rèn)為三維空間中的物體是空間中點(diǎn)的集合。從點(diǎn)集拓?fù)涞念I(lǐng)域概念出發(fā)，通過(guò)定義點(diǎn)集的閉包給出正則集的定義。組成三維物體的點(diǎn)的集合可以分為內(nèi)部點(diǎn)和邊界點(diǎn)兩部分，即由內(nèi)點(diǎn)和邊界點(diǎn)共同組成。由內(nèi)部點(diǎn)構(gòu)成的點(diǎn)集的閉包就是正則集。三維空間中點(diǎn)集的正則集就是三維正則形體，也就是有效的實(shí)體。數(shù)學(xué)中的點(diǎn)、線、面是其所代表的真實(shí)世界中的對(duì)象中的一種抽象，它們之間存在著一定的差距。例如，數(shù)學(xué)中的平面是二維的，它沒(méi)有厚度，體積為0；而在真實(shí)世界中，一張紙無(wú)論多么薄，它也是一個(gè)三維體具有一定的體積。這種差距造成了在計(jì)算機(jī)中以數(shù)學(xué)方法描述的形體可能是無(wú)效的，即在真實(shí)世界中可能不存在。盡管在有的情況下要構(gòu)造無(wú)效形體，但用于計(jì)算機(jī)輔助設(shè)計(jì)與制造系統(tǒng)設(shè)計(jì)生產(chǎn)的形體必須是有效的，所以在實(shí)體造型中必須保證實(shí)體的有效性，原則上的標(biāo)準(zhǔn)是要求“客觀存在”。7.1.2圖形的基本元素構(gòu)成三維實(shí)體的點(diǎn)、線（邊）、面、環(huán)、體是典型的層次結(jié)構(gòu)，如圖7.1所示。圖7.2（a）是構(gòu)成圖形的基本元素：點(diǎn)、線（邊）、面、環(huán)、體；圖7.2（b）也是構(gòu)成圖形的基本元素：環(huán)。

點(diǎn)是最基本的0維集合元素，分為端點(diǎn)、頂點(diǎn)、交點(diǎn)、切點(diǎn)和孤立點(diǎn)等。邊的端點(diǎn)稱為點(diǎn)，點(diǎn)不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于物體的內(nèi)、物體外或面內(nèi)，頂點(diǎn)是（面邊界）中兩條不共線的線段的交點(diǎn)。在形體定義中一般不允許存在孤立點(diǎn)。點(diǎn)是幾何造型中的基本元素，自由曲線、曲面或其他形體均可用有序的點(diǎn)集表示。用計(jì)算機(jī)存儲(chǔ)、管理、輸出形體的實(shí)質(zhì)就是對(duì)點(diǎn)集及其連接關(guān)系的處理。

邊是一維幾何元素，是兩相鄰面的基本交線，直線由其端點(diǎn)確定，曲線是由一系列數(shù)據(jù)點(diǎn)和控制點(diǎn)表示的，規(guī)則曲線可以由顯示或隱式方程表示。一條邊有且只有兩個(gè)相鄰面。兩個(gè)端點(diǎn)確定一條邊，這兩個(gè)端點(diǎn)分別稱為該邊的起點(diǎn)和終點(diǎn)。假設(shè)Q是一個(gè)形體，E（Q）是形體的邊的集合，則在ЭQ（形體的邊界）中E（Q）是滿足下列條件的所有線段的集合：邊e的兩個(gè)端點(diǎn)屬于V（Q）（所有頂點(diǎn)的集合）；邊e中沒(méi)有一個(gè)內(nèi)部點(diǎn)屬于V（Q）；邊e上每個(gè)點(diǎn)都有兩個(gè)不同的面，即存在兩個(gè)面使得邊形體Q的邊框線WF(Q)是由有序?qū)Γ╒(Q),E(Q)）所組成的。

面是形體上有限非零的區(qū)域，可由一個(gè)外環(huán)河若干個(gè)內(nèi)環(huán)確定其范圍。一個(gè)面可無(wú)內(nèi)環(huán)，但必須有且只有一個(gè)外環(huán)，即R3中非空、連續(xù)、共面切封閉的子集，稱之為面F，其邊界（記為ЭF）是有限條線段的并集，Pt表示含有F的惟一平面。面是形體表面的一部分，切具有方向性。面有正面、反面，一般外法線方向表示該面得正向，若一個(gè)面得外法矢量向外，則此面是正向面；反之，則為反向面。區(qū)分正向面和反向面在面與面求教交、交線分類、真實(shí)圖形顯示等方面都很重要。在幾何造型中常有平面、二次曲面、雙三次參數(shù)曲面等形式。環(huán)是有序的有向邊組成的面得封閉邊界。環(huán)中的邊不能相交，相鄰的邊共享一個(gè)端點(diǎn)。環(huán)有內(nèi)、外之分，確定面的最大外界面得環(huán)稱為外環(huán)，通常其邊按逆時(shí)針?lè)较蚺判颍汛_定面中內(nèi)孔或凸臺(tái)邊界的環(huán)稱為內(nèi)環(huán)，其邊與相應(yīng)外環(huán)排序的方向相反，通常按順時(shí)針?lè)较蚺判?。按這種方式定義，在面上沿著邊的方向前進(jìn)，面得內(nèi)部始終在走向的左側(cè)。

體是由封閉表面圍成的有效空間，是三維幾何元素；一個(gè)形體Q是空間中非空、有界的封閉子集。其邊界（記為ЭQ）是有限個(gè)面得并集，而外殼是形體的最大邊界。一個(gè)單位立方體可以定義為其中一個(gè)表面可表示為必須注意：并沒(méi)有規(guī)定形體必須是一個(gè)連續(xù)的封閉集合，目的是為了擴(kuò)大幾何造型的域，使得形體可以由不連續(xù)的體素組成。具有有限個(gè)參數(shù)，且簡(jiǎn)單的連續(xù)封閉的形體稱為體素，如長(zhǎng)方體、圓柱體、圓錐、球、環(huán)等。集合{P|F(P)<=0}稱為半空間，其中P為R3中的一點(diǎn)，F(xiàn)為一個(gè)平面，當(dāng)F=0時(shí)，表示一個(gè)平面，這個(gè)平面的半空間可以由定義的平面加上在平面某一側(cè)的所有點(diǎn)組成。顯然一個(gè)長(zhǎng)方體可以看成是6個(gè)平面半空間的交（圖7.2（d））。7.1.3圖形的幾何信息與拓?fù)湫畔⒕€框模型在表示三維空間中的物體時(shí)會(huì)出現(xiàn)圖形的幾何信息和拓?fù)湫畔G失等問(wèn)題。圖形對(duì)象中存在大量的圖形信息和非圖形信息，他們是正確表示圖形對(duì)象的基本信息。圖形信息又包括幾何信息和拓?fù)湫畔?，幾何信息是指圖形的幾何分量（如點(diǎn)、邊、面）在三維空間的位置和大小的信息，用來(lái)表示形體的幾何性質(zhì)和度量關(guān)系；拓?fù)湫畔t是指組成形體的基本圖形元素的幾何分量的數(shù)量及其相互之間連接關(guān)系的信息，用來(lái)表示形體之間的連接關(guān)系；非圖形信息是指圖形對(duì)象的線型、顏色、亮度以及與該圖形對(duì)象相對(duì)應(yīng)的體積、比重、質(zhì)量等物理信息。在這里，我們只討論圖形的幾何信息與拓?fù)湫畔ⅰ?.圖形的幾何信息一個(gè)圖形的幾何信息是指構(gòu)成幾何圖形的各幾何分量的數(shù)學(xué)表達(dá)式及各幾何分量間的相互關(guān)系。幾何信息主要包括對(duì)組成圖形的基本圖形元素及其相互關(guān)系的不睡和描述。點(diǎn)是0維圖形基本元素，可不是為三元組（x,y,z）;直線式1維基本圖形元素，可用直線方程表示為平面可用平面方程表示為二次曲面可用二次曲面的一般方程來(lái)描述：對(duì)一般的自由曲面，常用coons曲面、Bezier曲面、B樣條曲面及他們的線性組合來(lái)表示。值得注意的是，僅僅將組成三維形體的各種基本圖形元素表示出來(lái)是不夠的，圖形對(duì)象的幾何信息中還包括限定圖形對(duì)象范圍的各類圖形元素的邊界條件，圖形元素的數(shù)學(xué)表示與邊界條件構(gòu)成圖形對(duì)象的幾何信息，在實(shí)際應(yīng)用中，經(jīng)常要把幾何分量的數(shù)學(xué)表達(dá)式相應(yīng)的邊界條件結(jié)合起來(lái)應(yīng)用。用數(shù)學(xué)方程表示圖形的圖形表示方法，便于計(jì)算機(jī)進(jìn)行處理。在實(shí)際的圖形表示中使用最多的是圖形的參數(shù)方程表示法。對(duì)于不規(guī)則圖形，因無(wú)法用方程描述，常常采用各種近似方法。此外，用方程表示圖形只刻畫(huà)了圖形的形狀，而對(duì)于其他屬性則需要另外的說(shuō)明。一般地，畫(huà)出了形體的棱線與輪廓線就能惟一地將圖形表示出來(lái)。如圖7.3，8個(gè)頂點(diǎn)可以定義一個(gè)長(zhǎng)方體，但還不足以識(shí)別他，如果定義了棱線，則無(wú)論怎樣放置長(zhǎng)方體都能惟一的不是他。這種用一組輪廓線表示形體的模型就是線框模型。對(duì)于多面體，由于其輪廓線和棱線通常是一致的，所以多面體的線框模型更便于識(shí)別（如圖7.4）。但對(duì)于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察角度的改變而改變，無(wú)法用一組固定的輪廓線來(lái)表示他們（如圖7.5）。線框模型與形體之間不存在一一對(duì)應(yīng)關(guān)系，他僅僅通過(guò)給定的輪廓線約束所表示形體之間的邊界面，而在輪廓線之間的部分，形體的表面可以任意變化。沒(méi)有形體的表面信息，是不適合真實(shí)感的現(xiàn)實(shí)的，并且還可能是不是的形體產(chǎn)生二義性。根據(jù)不同的應(yīng)用需要，對(duì)幾何信息的要求也不同。例如，在矢量式輸入輸出設(shè)備中，以描述輪廓線為主，實(shí)體中的頂點(diǎn)的幾何信息最為重要；在光柵掃描式的輸入輸出設(shè)備中，主要是處理明暗度和陰影圖，面的幾何信息較為重要。但是。僅用幾何信息來(lái)描述幾何圖形還不夠充分，常會(huì)出現(xiàn)幾何實(shí)體表示上的二義性或多義性。表示一個(gè)實(shí)體除了需要幾何信息外，還需要提供幾何分量之間的相互連接關(guān)系，即拓?fù)湫畔ⅰ?.圖形的拓?fù)湫畔⑵矫娑嗝骟w是指表面由平面多邊形構(gòu)成的三維物體，是實(shí)體中最常見(jiàn)、應(yīng)用的最廣泛的一種，它也可以用來(lái)近似地表示曲面體。在具有二維流行性質(zhì)的平面多面體中，每一條邊連接兩個(gè)面，且僅連接兩個(gè)面。簡(jiǎn)單多面體指的是那些經(jīng)過(guò)連續(xù)的幾何形變可以變換為一個(gè)球的多面體，也就是與球拓?fù)涞葍r(jià)的那些多面體（如圖7.6）。實(shí)體可以采用詳細(xì)記錄構(gòu)成物體的多有幾何元素——域、殼、體、面、環(huán)、邊、點(diǎn)的幾何信息及其相互連接關(guān)系的拓?fù)湫畔⒌膶哟?、拓?fù)浣Y(jié)構(gòu)方法來(lái)表示。幾何信息形成物體邊界表示的“骨架”，而物體的拓?fù)潢P(guān)系則猶如附著在這“骨架“上的肌肉。通常，多面體在頂點(diǎn)、棱邊和面這三類元素之間共有點(diǎn)-點(diǎn)、點(diǎn)-線、點(diǎn)-面；線-點(diǎn)、線-線、線-面；面-點(diǎn)、面-線、面-面等9種不同類型的拓?fù)潢P(guān)系，如圖7.7所示，即在這里符號(hào)“-->“表示指針，即可以從它的左端求出它的右端。例如，V-->{e}表示由一個(gè)頂點(diǎn)找出相交于此頂點(diǎn)的所有邊，而F-->{e}則表示由一個(gè)面找出該面所有的邊，等等。根據(jù)不同的需要，對(duì)拓?fù)潢P(guān)系的要求也不一樣。對(duì)矢量式圖形系統(tǒng)，可由這些拓?fù)潢P(guān)系知道如何從頂點(diǎn)連接成邊、面等幾何圖元；在線、面消隱算法中，希望知道面得相鄰性，即F

{F};在實(shí)體拼合算法中，需要知道頂點(diǎn)的鄰接面，即V

{F}。7.2實(shí)體表示的三種模型形體在計(jì)算機(jī)中常用線框模型、表面模型和實(shí)體模型三種模型來(lái)表示。線框模型是在計(jì)算機(jī)圖形學(xué)和CAD、CAM領(lǐng)域中最早用來(lái)表示形體的模型，并且至今仍在廣泛應(yīng)用。線框模型是用頂點(diǎn)和棱邊表示形體，其特點(diǎn)是結(jié)構(gòu)簡(jiǎn)單，易于理解，并是表面和實(shí)體模型的基礎(chǔ)。如前所述，用線框模型表示形體時(shí)曲面的輪廓線無(wú)法隨視角的變化而改變；線框模型無(wú)法給出全部連續(xù)的幾何信息，只有頂點(diǎn)和棱邊，不能明確地定義給定的點(diǎn)與形體之間的關(guān)系，以致不能用線框模型處理計(jì)算機(jī)圖形學(xué)和CAD、CAM領(lǐng)域中的多數(shù)問(wèn)題，如圖7.8所示。線框模型的優(yōu)點(diǎn)：（1）結(jié)構(gòu)簡(jiǎn)單，設(shè)計(jì)書(shū)內(nèi)部易于表達(dá)和處理；（2）模型所需要的幾何信息就是線段端點(diǎn)坐標(biāo)。線框模型的缺點(diǎn)是：（1）有二義性，無(wú)深度信息：（2）不便于用作幾何形狀的通用表達(dá)形式（形體內(nèi)部）：（3）不能表達(dá)表面上點(diǎn)的局部屬性。表面模型是用有向棱邊圍成的有限區(qū)域來(lái)定義立體的表面．由面的集合來(lái)定義形體，圖7．9說(shuō)明了用表面模型定義形體的方法。表面模型是在線框模型的基礎(chǔ)上．增加有關(guān)面、邊(環(huán)、邊)信息以及表面特征、棱邊的連接方向等內(nèi)容。從而可以滿足面與面求交、線面消隱、明暗色彩處理、數(shù)控加工等應(yīng)用問(wèn)題的需要。但利用表面模型友示形體時(shí)，存在不能明確形體與表面關(guān)系的問(wèn)題，表面模型沒(méi)有確定形體究竟枉表面的哪一側(cè)。圖7.10為表面模型的一個(gè)例子。在表面模型的基礎(chǔ)上，實(shí)體模型近一步明確定義了面與實(shí)體的關(guān)系。實(shí)體模型和表面模型的主要區(qū)別在于實(shí)體模型定義了表面外環(huán)的額棱邊方向（見(jiàn)圖7.11）.計(jì)算機(jī)中表示形體，通常用線框、表面和實(shí)體三種模型。線框模型和表面模型保存的三維形體信息都不完整，只有實(shí)體模型才能夠完整地、無(wú)歧義地表示三維形體，如表7.1所示。形體表示的線框、表面和實(shí)體模型是抽象的概念模型，并不反映形體在計(jì)算機(jī)內(nèi)部的具體表示方式。在世模型的表示中，出現(xiàn)了許多方法，基本上可以分為空間分解表示（單元枚舉、八叉樹(shù)分解、單元分解等）、構(gòu)造表示（CSG）和邊界表示（B-rep）三大類。構(gòu)造表示是按照生成過(guò)程來(lái)定義形體的方法，包括掃描表示、構(gòu)造實(shí)體幾何表示和特征表示三種。從使用的角度看，形體表示以特征表示和構(gòu)造的實(shí)體幾何表示（CSG）較為方便；從計(jì)算機(jī)對(duì)形體的存儲(chǔ)管理和操作運(yùn)算角度看，以邊界表示（B-rep）最為實(shí)用。在這一節(jié)，我們將介紹邊界表示法、掃描表示法、構(gòu)造的實(shí)體幾何表示法、八叉樹(shù)表示法等4種實(shí)體的表示方法。7.3變界表示法實(shí)體的邊界表示(B-rep)就是按照體、面、環(huán)、邊、點(diǎn)的層次，詳細(xì)記錄構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。該表示法的特點(diǎn)是描述形體的信息既包括幾何信息，又包括拓?fù)湫畔ⅰＳ脤?shí)體的邊界來(lái)表示實(shí)體．在計(jì)算機(jī)內(nèi)是如何實(shí)現(xiàn)的呢？這就是邊界表示的數(shù)據(jù)結(jié)構(gòu)問(wèn)題。我們?nèi)砸云矫娑嗝骟w為例來(lái)討論這一問(wèn)題。1、實(shí)體的邊界表示2、邊界表示的數(shù)據(jù)結(jié)構(gòu)7.3.1實(shí)體的邊界表示邊界模型表示形體的基本幾何元案包括頂點(diǎn)、邊、環(huán)、面、體。在進(jìn)行各種運(yùn)算和操作中．可以直接取得這些信息。用來(lái)定義形體表面的面既可以是平面(稱多面體)．也可以是曲面，形體上的邊既可以是直線段，也可以是的線段。三維物體采用邊界表示最普遍的方式是使用一組包圍物體內(nèi)部的表面多邊形。存儲(chǔ)幾何信息的方法是建立三表結(jié)構(gòu)，即頂點(diǎn)表、邊表和多邊形面表。頂點(diǎn)坐標(biāo)值存放在頂點(diǎn)表中；含有指向頂點(diǎn)表指針的邊表，用來(lái)為多邊形的每條邊標(biāo)識(shí)頂點(diǎn)。同樣．面表會(huì)有指向邊表的指針，出來(lái)為每個(gè)表面標(biāo)識(shí)其組成的邊。邊界表示的概念不僅能用來(lái)表示三維空間的平面多面體，而且可延伸到表示一個(gè)面、一條邊。即—個(gè)平面多面體可用構(gòu)成邊界的一系列平面多邊形表示，一個(gè)多邊形又可用構(gòu)成其邊界的一系列邊來(lái)表示，而—條邊又可用兩個(gè)點(diǎn)來(lái)表示。那么，如何在計(jì)算機(jī)中將面、邊、點(diǎn)信息合理地組織起來(lái)以有效地滿足實(shí)體的構(gòu)造、運(yùn)算及顯示的需要呢？要用實(shí)體的邊界信息表示一個(gè)實(shí)體，必須正確地表示出實(shí)體邊界的拓?fù)湫畔⒓皫缀涡畔?。所謂拓?fù)湫畔ⅲ傅氖敲?、邊、點(diǎn)之間的連接關(guān)系、鄰近關(guān)系及邊界關(guān)系，而幾何信息則指的是面、邊、點(diǎn)的位置及大小等幾何數(shù)據(jù)。由于使用者要頻繁地對(duì)實(shí)體的面、邊、點(diǎn)進(jìn)行查找或修改．并且希望盡快地知道這些操作的影響及結(jié)果．因此，所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)是否便于對(duì)實(shí)體進(jìn)行面、邊、點(diǎn)的存放、查找或修改，是一個(gè)十分關(guān)鍵的問(wèn)題，必須妥善地加以解決。可是，這并不是一個(gè)很容易解決的問(wèn)題。若我們簡(jiǎn)單地用—系列的頂點(diǎn)來(lái)表示一個(gè)多邊形，即而頂點(diǎn)坐標(biāo)是按沿多邊形邊界的順序存放的，相鄰兩頂點(diǎn)之間代表一條邊．那么．對(duì)于一個(gè)簡(jiǎn)單的多邊形．這種表示方法是節(jié)約空間的。但是，對(duì)于一個(gè)多面體邊界上的一系列多邊形來(lái)說(shuō)．這種表示方法使用了過(guò)多的空間，這是由于被多個(gè)多邊形共享的頂點(diǎn)多次重復(fù)存儲(chǔ)的緣故。此外，這種表示方法沒(méi)有表示出共享邊及共享點(diǎn)的信息。如果我們想通過(guò)交互方式拖曳一個(gè)頂點(diǎn)及共享這個(gè)頂點(diǎn)所有的邊，就必須找到共享這個(gè)頂點(diǎn)的全部多邊形．就需要將一個(gè)多邊形的頂點(diǎn)坐標(biāo)與所有其他多邊形的頂點(diǎn)坐標(biāo)相比較．從而使用過(guò)多的計(jì)算時(shí)間。B-rep表示適用范圍大．原則上能表示所有的形體，而且易于支持形體的持征表示，B-rep表示巳成為當(dāng)前CAD／CAM系統(tǒng)的主要表示方法。前面巳經(jīng)提到．實(shí)體的面、邊、點(diǎn)之間存征9種不同類型的拓?fù)潢P(guān)系．在這9種不同類型的拓?fù)潢P(guān)系中．至少必須選擇兩種才能構(gòu)成表示一個(gè)實(shí)體所需的完全的拓?fù)湫畔?。因此，可能采取的?shù)據(jù)結(jié)構(gòu)形式．按所給定的拓?fù)潢P(guān)系來(lái)分，共有等8類．共計(jì)502種如果將此8類數(shù)據(jù)結(jié)構(gòu)形式表示為．那么，當(dāng)m小時(shí)，所存儲(chǔ)的拓?fù)潢P(guān)系少，因此所需的存儲(chǔ)空間小，但查找時(shí)間較長(zhǎng)。當(dāng)m大時(shí)，所存儲(chǔ)的拓?fù)潢P(guān)系多．因而所需的存儲(chǔ)空間大，但查找時(shí)間較短。因此，要根據(jù)對(duì)實(shí)體操作的具體要求及計(jì)算機(jī)系統(tǒng)資源的狀況，妥善選擇一種數(shù)據(jù)結(jié)構(gòu)，求得時(shí)間利空間上的合理折中，以提高整個(gè)系統(tǒng)的效率。在使用邊界表示法表示實(shí)體的過(guò)程中，經(jīng)常會(huì)遇到從一個(gè)點(diǎn)查找與該點(diǎn)相連的所有邊，從一條邊查找該邊的鄰面及鄰邊，從一個(gè)面開(kāi)始查找其上的外環(huán)和內(nèi)環(huán)等。數(shù)據(jù)結(jié)構(gòu)是完成這些操作的基礎(chǔ)。實(shí)體造型中的數(shù)據(jù)結(jié)構(gòu)本質(zhì)上是對(duì)形體表示方式所需信息的存儲(chǔ)管理．B-rep表示就需要定義形體的面、環(huán)、邊、點(diǎn)及其屬性，以便進(jìn)行存取、直接查找、間接查找和逆向查找等操作。邊界表示法的數(shù)據(jù)結(jié)構(gòu)有4種：以面為基礎(chǔ)、以頂點(diǎn)為基礎(chǔ)、以邊為基礎(chǔ)和翼邊結(jié)構(gòu)。7.3.2邊界表示的數(shù)據(jù)結(jié)構(gòu)以面為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)、按照體、面、頂點(diǎn)坐標(biāo)的樹(shù)結(jié)構(gòu)層次織織元素?cái)?shù)據(jù)，以頂點(diǎn)-坐標(biāo)和面-頂點(diǎn)序列兩張關(guān)系表表示，如：{頂點(diǎn)(坐標(biāo))}；{面(頂點(diǎn)序列)}。以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)．以邊-頂點(diǎn)，頂點(diǎn)-坐標(biāo)，面-邊三張關(guān)系表表示，如：{邊(頂點(diǎn))}、{頂點(diǎn)(坐標(biāo))}、{面(邊)}。四棱錐邊界表示的例子如圖7.12，由4個(gè)面組成，且這種表示可以看做是含有體、面、邊、頂點(diǎn)為節(jié)點(diǎn)的有向圖；四棱錐邊界表示也可采用基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。在幾何造型過(guò)程中，通常是把形體的幾何信息和拓?fù)湫畔⒔Y(jié)合在一起進(jìn)行處理的。我們注意到不同尺寸和形狀的形體可能具有相同的拓?fù)潢P(guān)系，從而可以來(lái)用相同的形體生成過(guò)程．并且設(shè)計(jì)一種數(shù)據(jù)記錄結(jié)構(gòu)．使之能分別處理形體的幾何信息與拓?fù)湫畔?，這將提高造型系統(tǒng)的工作效率和質(zhì)量。除了一般的幾何相交性的計(jì)算之外，形體組成元素間的拓?fù)潢P(guān)系的建立、改變與管理是造型過(guò)程中一個(gè)困難的問(wèn)題。在國(guó)際、國(guó)內(nèi)研究開(kāi)發(fā)的三維實(shí)體造型系統(tǒng)中、采用較多的是翼邊數(shù)據(jù)結(jié)構(gòu)及半邊結(jié)構(gòu)。1．邊界表示的翼邊結(jié)構(gòu)翼邊數(shù)據(jù)結(jié)構(gòu)誕生于1972年．由美國(guó)斯坦福大學(xué)的B.G..波姆嘎特(B.G.Baumgart)等人作為多面體的表示模式提出。所謂翼邊，就是當(dāng)我們觀察一個(gè)平面立體時(shí)，每一條棱邊都有左、右兩個(gè)鄰面和與之相鄰的四條鄰邊，好像展開(kāi)的雙翅，故稱翼邊結(jié)構(gòu)(見(jiàn)圖7．13)。通過(guò)翼邊結(jié)構(gòu)，可以方便地查找每個(gè)元素之間的連接關(guān)系。例如，組成一個(gè)面的所有的邊、一條邊的所有鄰邊等。這種結(jié)構(gòu)以每一條邊為核心．分別指向從外面觀察這一多面體時(shí)所見(jiàn)到的這條邊的上、下兩個(gè)頂點(diǎn)、左、右兩個(gè)鄰面以及上下左右四條鄰邊。每一個(gè)頂點(diǎn)都有一個(gè)指針．反過(guò)來(lái)指向以該頂點(diǎn)為端點(diǎn)的某一條邊；每一個(gè)面也有一個(gè)指針，反過(guò)來(lái)指向它的一條邊。翼邊結(jié)構(gòu)由4種節(jié)點(diǎn)Solid，F(xiàn)ace，Edge和Vertex組成．各節(jié)點(diǎn)描述如下：Solid是構(gòu)成引用的根節(jié)點(diǎn)，在任意時(shí)刻，會(huì)存在幾個(gè)數(shù)據(jù)結(jié)構(gòu)引用。為了存取其中的任何一個(gè)．需要有指向其Solid節(jié)點(diǎn)的指針。通過(guò)指向三個(gè)雙向鏈表的指針Solid節(jié)點(diǎn)給出對(duì)該模型的面、邊和頂點(diǎn)的訪問(wèn)。所有實(shí)體被鏈接到一個(gè)雙向鏈表中，這個(gè)表通過(guò)指向該表的后繼和前趨實(shí)體的指針來(lái)實(shí)現(xiàn)。具體包括；指向Face的鏈表指針、指向Edge的鏈表指針、掐向Vertex的鏈表指針。structsolid{ Idsolidno;/*多面體序號(hào)*/ Face*sfaces;/*指向多面體的面*/ Edge*sedges;/*指向多面體的邊*/ Vertex*sverts;/*指向多面體的頂點(diǎn)*/ Solid*nexts;/*指向后一個(gè)多面體*/ Solid*prevs;/*指向前多面體*/}；Face是表示多面體的一個(gè)小平面。包括指向Face的鏈表首元素的指針、指Face的下—元素的指針。structface{ Idfaceno;/*面的序號(hào)*/ Solid*fsolid;/*指向該面所屬的多面體*/ Edge*fedges;/*指向構(gòu)成該面的邊*/ Vectorfeq;/*平面或曲面方程*/ Face*prevf;/*指向前一個(gè)面*/ Face*nextf;/*指向后一個(gè)面*/}；Edge由Edge節(jié)點(diǎn)構(gòu)成，是整個(gè)數(shù)據(jù)結(jié)構(gòu)的核心，每個(gè)Edge節(jié)點(diǎn)代表一條邊．包括Edge的起始頂點(diǎn)指針、Edge的終止頂點(diǎn)指針、Edge的右鄰面的指針、Edge的左鄰面的指針、Edge的右方向向前鄰邊指針、Edge的右方向向后鄰邊指針、Edge的左方向向前鄰邊指針、Edge的左方向向后鄰邊指針。structedge{ Idedgeno/*邊序號(hào)*/Vertex*startv;/*指向邊的起始點(diǎn)*/ Vertex*endv;/*指向邊的終點(diǎn)*/ Face*rface;/*指向右鄰面*/ Face*lface;/*指向左鄰面*/ Edge*nedge;/*指向下一條邊*/ Edge*pedge;/*指向前一條邊*/}Vertex由Vertex節(jié)點(diǎn)構(gòu)成，包括頂點(diǎn)坐標(biāo)(x,y,z)、指向與該Vertex相連的第一條邊指針、指向下一個(gè)Vertex節(jié)點(diǎn)指針。通過(guò)冀邊結(jié)構(gòu)，可以方便地查找各元素之間的連接關(guān)系。冀邊結(jié)構(gòu)存儲(chǔ)的信息量大．顯然存儲(chǔ)內(nèi)容重復(fù)，但卻獲得了較高的查找速度。structvertex{ Idvertexno;/*頂點(diǎn)序號(hào)*/ Vectorvcoord;/*頂點(diǎn)坐標(biāo)*/ Vertex*prevv;/*指向前一個(gè)頂點(diǎn)*/ Vertex*nextv;/*指向后一個(gè)頂點(diǎn)*/}2．邊界表示的半邊結(jié)構(gòu)當(dāng)實(shí)體以邊界模型存儲(chǔ)時(shí)．翼邊結(jié)構(gòu)較好地描述了點(diǎn)、邊、面之間的拓?fù)潢P(guān)系，但它也存在著—些缺陷。半邊數(shù)據(jù)結(jié)構(gòu)是—種更完善的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱半邊結(jié)構(gòu)。半邊數(shù)據(jù)結(jié)構(gòu)與翼邊數(shù)據(jù)結(jié)構(gòu)的主要區(qū)別在于該結(jié)構(gòu)—條物理邊拆分為兩條邊表示，使其中每條邊只與一個(gè)鄰接面相文(如圖7．14)，而從中每條邊亦只表示相應(yīng)物理邊的一半信息．故稱半邊。出于環(huán)的定向已有明確規(guī)定(外環(huán)按逆時(shí)針?lè)较颍瑑?nèi)環(huán)按順時(shí)針?lè)较?．于是就可用標(biāo)志位確定邊與面和環(huán)的關(guān)系。半邊數(shù)據(jù)結(jié)構(gòu)分為5個(gè)層次，即體、面、環(huán)、半邊、頂點(diǎn)．每層拓?fù)湓匕闹饕獙傩匀鐖D7.15所示。定義一個(gè)平面模型是頂點(diǎn)N、邊A和多邊形R的一個(gè)平面有向圖{N，A，R}，如圖7.14所示。為表示{N，A，R}，將使用一種5級(jí)層次數(shù)據(jù)結(jié)構(gòu)(圖7.15)。它是由五種節(jié)點(diǎn)勸Solod，F(xiàn)ace，Loop，HalfEdge和Vertex組成的。structsolid{ Idsolidno;/*多面體序號(hào)*/ Face*sfaces;/*指向多面體的面*/ Edge*sedges;/*指向多面體的邊*/ Vertex*sverts;/*指向多面體的頂點(diǎn)*/ Solid*nexts;/*指向后一個(gè)多面體*/ Solid*prevs;/*指向前多面體*/}；structface{ Idfaceno;/*面的序號(hào)*/ Solid*fsolid;/*指向該面所屬的多面體*/ Loop*floops;/*指向構(gòu)成該面的環(huán)*/ Vectorfeq;/*平面或曲面方程*/ Face*prevf;/*指向前一個(gè)面*/ Face*nextf;/*指向后一個(gè)面*/}；structloop{ HalfEdge*ledge;/*指向構(gòu)成環(huán)的半邊*/ Face*lface;/*指向該環(huán)所屬的面*/ Loop*prevl;/*指向前一個(gè)環(huán)*/ Loop*nextl;/*指向后一個(gè)環(huán)*/}structedge{ Idedgeno;/*邊的序號(hào)*/ HalfEdge*he1;/*指向左半邊*/ HalfEdge*he2;/*指向右半邊*/ Edge*preve;/*指向前一條邊*/ Edge*nexte;/*指向后一條邊*/}；structhalfedge{ Edge*edge;/*指向半邊的父節(jié)點(diǎn)*/ Vertex*vtx;/*指向半邊的起始頂點(diǎn)*/ Loop*wloop;/*指向半邊所屬的環(huán)*/ HalfEdge*prv;/*指向前一條半邊*/ HalfEdge*nxt;/*指向后一條半邊*/}；structvertex{ Idvertexno;/*頂點(diǎn)序號(hào)*/ HalfEdge*vedge;/*指向以該頂點(diǎn)為起點(diǎn)的半邊*/ Vectorvcoord;/*頂點(diǎn)坐標(biāo)*/ Vertex*prevv;/*指向前一個(gè)頂點(diǎn)*/ Vertex*nextv;/*指向后一個(gè)頂點(diǎn)*/}值