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

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

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

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

4、ms造型系統(tǒng)，北京航空航天大學(xué)研制出的微機(jī)版金銀花（LONICERA）”系統(tǒng)，武漢開(kāi)目信息技術(shù)有限責(zé)任公司開(kāi)發(fā)的開(kāi)目三維CAD軟件等等。造型系統(tǒng)簡(jiǎn)介Parasolid和ACIS是兩個(gè)最有代表性的幾何造型系統(tǒng)的開(kāi)發(fā)平臺(tái)。在早期開(kāi)發(fā)的實(shí)體 造型系統(tǒng)中，英國(guó)的劍橋大學(xué)研制出了BUILD-1和BUILD-2系統(tǒng)，但都沒(méi)有公開(kāi)使用。80年代初期，研究小組的一部分人組建了Shape Data公司，并開(kāi)發(fā)了實(shí)體造型系統(tǒng)Romulus。1986年，Shape Data 并入EDS Unigraphics 之后，推出了功能強(qiáng)大的幾何造型核心1 / 13Parasolid 。同時(shí)，Shape Data 一部分保留

5、人員研制了新的造型核心，就是后來(lái)由 Spatial Technology公司推出的幾何造型系統(tǒng)核心ACIS。Parasolid和ACIS并不是面向最終用戶的應(yīng)用系統(tǒng)， 而是 幾何引擎”，作為應(yīng)用系統(tǒng)的 核心。用戶可用它們作為平臺(tái)，開(kāi)發(fā)自己的應(yīng)用系統(tǒng)。當(dāng)今許多流行的商用CAD/CAM軟件，如 Unigraphics、Solidedge、Solidwork、MDT 等，都是在 Parasolid 或 ACIS 的基礎(chǔ) 上開(kāi)發(fā)出來(lái)的。Parasolid有較強(qiáng)的造型功能，但是只能支持正則實(shí)體造型。它提供的主要功能有：集 合運(yùn)算、特征的創(chuàng)建和編輯、局部操作、數(shù)據(jù)交換文件接口等。Parasolid采用精確

6、的邊界表示，包括拓?fù)洹缀魏完P(guān)聯(lián)三種數(shù)據(jù)類型。ACIS具有和Parasolid相似的形體結(jié)構(gòu)，但在系統(tǒng)結(jié)構(gòu)上采用了核心和外殼相結(jié)合的 方式。ACIS支持線框、表面和實(shí)體的統(tǒng)一表示，支持非正則形體的造型。在上述幾何實(shí)體造型系統(tǒng)中，通常都會(huì)提供一些基本的形體輸入方法，以及拉伸，旋轉(zhuǎn)，蒙皮，掃描等直接構(gòu)造形體的方法，通過(guò)集合運(yùn)算對(duì)形體進(jìn)行拼合。雖然對(duì)這些造型方法的 研究取得了一系列新進(jìn)展，但是集合運(yùn)算仍基本局限在對(duì)兩個(gè)體進(jìn)行正則運(yùn)算（交，并，差）上，而且結(jié)果形體的信息都已經(jīng)包含在兩個(gè)參加運(yùn)算的原始形體之中，不能引入新的信息。實(shí)際應(yīng)用中，有些機(jī)械零件具有特定的形狀特征， 不能通過(guò)集合運(yùn)算來(lái)直接完成，

7、或者直接 實(shí)現(xiàn)時(shí)操作步驟非常復(fù)雜。但是，它們的生成方法和集合運(yùn)算非常相似， 可以看作是集合運(yùn) 算的擴(kuò)展。拔模和抽殼都屬于這一類型的造型方法。三維形體的表示三維造型技術(shù)是建立恰當(dāng)?shù)哪Ｐ蛠?lái)表示自然界中形態(tài)豐富的三維物體的技 術(shù)，根據(jù)造型對(duì)象將造型技術(shù)分成3類。第一類是曲面造型，主要研究計(jì)算機(jī)內(nèi)如何描述一張曲面，及曲面的顯示與 控制。曲面造型又分成規(guī)則曲面和不規(guī)則曲面兩種。不規(guī)則曲面造型方法主要有貝塞爾曲線曲面、B樣條曲線曲面和孔斯曲面等。（二維曲線：Nurbs （通過(guò)擬 合點(diǎn)）、三次B樣條（通過(guò)控制點(diǎn)）、貝塞爾（控制點(diǎn)和擬合點(diǎn)重合）和波浪 線（B樣條）第二類是立體造型方法，主要研究在計(jì)算機(jī)內(nèi)如何定

8、義、表示一個(gè)三維物體， 主要有體素構(gòu)造法、邊界表示法和八叉數(shù)法等等。曲面告型和立體告型合稱幾何 模型造型。該技術(shù)主要應(yīng)用在機(jī)械行業(yè)輔助設(shè)計(jì)制造領(lǐng)域（ CAD）。第三類是自然景物模擬，主要研究在計(jì)算機(jī)內(nèi)如何模擬自然景物，如云、流 水、樹(shù)等。該造型技術(shù)主要應(yīng)用在游戲和藝術(shù)造型等領(lǐng)域。如下主要說(shuō)說(shuō)幾何模型的表示。2 / 13 在計(jì)算機(jī)中，表示幾何形體的方法通常有三種： 線框模型、表面模型和實(shí)體模型 一、線框模型該模型采用三維形體的全部頂點(diǎn)及邊的集合來(lái)描述三維形體，即用頂點(diǎn)表和邊表兩個(gè)表的數(shù)據(jù)結(jié)構(gòu)來(lái)表示三維模型。每條邊由兩個(gè)頂點(diǎn)表示。主要優(yōu)點(diǎn)是結(jié)構(gòu)簡(jiǎn)單，處理容易。描述二維目標(biāo)十分理想。但對(duì)三維物體，存

9、在如下缺點(diǎn)：1）沒(méi)有面的信息，它不能表示表面含有曲面的物體。2）不能明確定義點(diǎn)與物體之間的關(guān)系。3）點(diǎn)和邊信息容易出現(xiàn)二義性。二、表面模型在線框模型的基礎(chǔ)上，增加了物體中的面的信息，用面的集合來(lái)表示物體， 每個(gè)面由多條有向邊構(gòu)成，用環(huán)來(lái)定義面的邊界，即是用頂點(diǎn)表、邊表和面表來(lái) 描述模型。表面模型又分為平面模型和曲面模型。 前者以多邊形網(wǎng)格為基礎(chǔ)。后 者以參數(shù)曲面塊為基礎(chǔ)。表面模型存在的不足就是它只能表示物體的表面邊界， 而不能表達(dá)出真實(shí)實(shí) 體的屬性，很難確認(rèn)一個(gè)表面模型表示的三維圖形是一個(gè)實(shí)體還是一個(gè)空殼。 這 個(gè)不足，在實(shí)體模型中得到了解決。三、實(shí)體模型實(shí)體模型是最高級(jí)的模型，它能完整表示物

10、體的所有形體信息，可以無(wú)歧義 地確定一個(gè)點(diǎn)是在物體外部還是內(nèi)部或表面上。實(shí)體模型使用有向邊的右手法則來(lái)確定所在面的外法線方向。即用右手沿邊的順序方向握住，大拇指所指向?yàn)樵撁娴耐夥ň€方向。法線方向指向體外。體外實(shí)體模型存在著不同的數(shù)據(jù)結(jié)構(gòu)，在這些結(jié)構(gòu)中存在一個(gè)共同點(diǎn)，即數(shù)據(jù)結(jié)3 / 13 構(gòu)不僅記錄了物體全部的幾何信息，而且還記錄了所有的點(diǎn)、線、面、體的 拓?fù)湫畔ⅲ纯臻g位置關(guān)系）。實(shí)體模型的構(gòu)造通常使用體素（即原始的基 本實(shí)體），經(jīng)集合論中的交、并、差運(yùn)算構(gòu)成復(fù)雜形體。1.實(shí)體的定義實(shí)體就是有效的物體，即客觀世界中確實(shí)存在的物體，要在計(jì)算機(jī)內(nèi)表示、 構(gòu)造一個(gè)實(shí)體，就必須給出實(shí)體的確切定義（即用

11、最小的數(shù)據(jù)結(jié)構(gòu)唯一地確 定實(shí)體的形狀和位置。）如下圖帶有懸掛面的立方體就不是實(shí)體，在客觀世 界中不可能存在這樣的物體。1 .剛性。一個(gè)實(shí)體必須具有一定的形狀（流體不屬于實(shí)體）2 .維數(shù)一致性。一個(gè)實(shí)體的各個(gè)部分必須是三維的，不能存在懸掛的、孤立 的邊界。3 .有限性。一個(gè)實(shí)體必須占有有限的空間。4 .邊界確定性。根據(jù)實(shí)體的邊界，可確定實(shí)體的內(nèi)部或外部。5 .封閉性。經(jīng)過(guò)集合運(yùn)算后，仍然是有效的實(shí)體。實(shí)體的表面必須具備如下性質(zhì)：1 .連通性。表面任意兩點(diǎn)都可用表面上的一條路徑連接起來(lái)。2 .邊界性。3 .非自相交性。一個(gè)實(shí)體表面不可自相交。4 .可定向性。一個(gè)實(shí)體的表面兩則可明確定義出實(shí)體的內(nèi)側(cè)

12、和外側(cè)。5 .封閉性。一個(gè)表面的封閉性由多邊形網(wǎng)格各元素的拓?fù)潢P(guān)系確定的。即每條邊連接且僅連接兩個(gè)面，每條邊有且僅有兩個(gè)端點(diǎn)。從點(diǎn)集拓?fù)浣嵌冉o出實(shí)體的定義。將三維實(shí)體看作是空間中點(diǎn)的集合，它由內(nèi)點(diǎn)與邊界點(diǎn)共同組成。內(nèi)點(diǎn)是指點(diǎn)集中的這樣一些點(diǎn)：它們具有完全包含于該點(diǎn)集的充分小的 領(lǐng)域。點(diǎn)集中除內(nèi)點(diǎn)外的所有的點(diǎn)就是邊界點(diǎn)。4 / 13所以三Zt物體A可表示為：A= bA , iAbA為物體A的邊界點(diǎn)集；iA為物體A的內(nèi)部點(diǎn)集。定義點(diǎn)集的正則運(yùn)算r如下：rA = ciAi為取A的內(nèi)點(diǎn)運(yùn)算；c為取閉包運(yùn)算；A為一個(gè)點(diǎn)集。iA為A的全體內(nèi)點(diǎn)組成的集合，稱為 A的內(nèi)部，它是一個(gè)開(kāi)集（“開(kāi)集” 可以理解為沒(méi)

13、有邊界值去判斷點(diǎn)是否為內(nèi)點(diǎn)）。ciA為A的內(nèi)部的閉包，是iA與其邊界點(diǎn)的并集。（據(jù)此可以理解“閉包” 的含義），它本身是一個(gè)閉集，（“閉集”可以理解為可以通過(guò)明確的邊界 值來(lái)判斷點(diǎn)是否在集合中）。正則運(yùn)算即為：先對(duì)物體取內(nèi)點(diǎn)再取閉包的運(yùn)算。rA稱為物體A的正則點(diǎn)集, 如圖：。一 ©髓懸漫段二建內(nèi)點(diǎn)重合超正幅蠹總和點(diǎn)最公（沒(méi)有粗邊界A（意和地黑州帶有懸邊的二維點(diǎn)集A 內(nèi)點(diǎn)集合iA （沒(méi)有粗邊界） 正則點(diǎn)集ciA （有粗邊界）以上圖中，圖1有懸邊所以點(diǎn)集不是有效實(shí)體，圖2沒(méi)有邊界，不是滿足“封閉 性”所以也不是實(shí)體。圖3為正則點(diǎn)集，封閉性，也滿足實(shí)體的其他條件，所以 為實(shí)體。正則點(diǎn)集有時(shí)

14、也不一定是實(shí)體。如下圖：5 / 13二維篇體左圖為正則點(diǎn)集，但它不是有效的物體。由此，就會(huì)涉及到另外一個(gè)概念“二維流體”。二維流體是指對(duì)于實(shí)體表面上的任何一點(diǎn)，都可以找到一個(gè)圍繞著它的任意小 的領(lǐng)域，該領(lǐng)域在拓?fù)洌词强臻g位置）上與平面上的一個(gè)圓盤是等價(jià)的（也 就是在表面上存在著一個(gè)領(lǐng)域圍繞著某個(gè)點(diǎn)）。這意味著，在領(lǐng)域的點(diǎn)集和圓 盤之間存在著連續(xù)的一對(duì)一的對(duì)應(yīng)關(guān)系。如上右圖,立體表面上任一點(diǎn)都存在與 圓盤同構(gòu)的領(lǐng)域。而左圖，兩個(gè)立方體共享邊被四個(gè)面共享， 其上的點(diǎn)不存在這 樣的唯一的領(lǐng)域（在上圖中，共享邊的點(diǎn)，存在圍繞它的領(lǐng)域有兩個(gè)）。有了上述概念后，實(shí)體可以這樣描述為：對(duì)于一個(gè)占據(jù)有限空間的

15、正則點(diǎn)集， 如果其表面是二維流形，則該正則點(diǎn)集為實(shí) 體（有效物體）。2.正則集合運(yùn)算能產(chǎn)生正則幾何體（有正則點(diǎn)集組成的形體）的集合運(yùn)算稱為正則集合運(yùn)算。正則集合運(yùn)算與傳統(tǒng)集合運(yùn)算的區(qū)別主要是在對(duì)產(chǎn)生結(jié)果的邊界面的處理上，其內(nèi)部點(diǎn)的處理是一致的。正則運(yùn)算主要是考慮如何消除或不產(chǎn)生懸點(diǎn)、懸邊和懸面。如下圖：6 / 13OAClB （傳統(tǒng)交IC=ACi+ B（正則交）上圖，左邊為傳統(tǒng)的交運(yùn)算結(jié)果，右邊為正則的交運(yùn)算結(jié)果。在傳統(tǒng)的集合運(yùn)算符后加“號(hào)表示正則運(yùn)算符。實(shí)現(xiàn)正則集合運(yùn)算有兩種方法：間接法和直接法。間接法是先按普通集合運(yùn)算求出結(jié)果， 后用一些規(guī)則判斷，以消除不符合正則幾何定義的部分（即懸邊、懸

16、面等），從而得到正則 幾何體。直接法是定義正則集合算子的表達(dá)式，用以直接得出符合正則幾何體定義的結(jié)果。正則幾何運(yùn)算定義如下：A<OP>* B = r （ A <OP> B ）;式中<OP>表示傳統(tǒng)集合并、交、差算子；<OP>*表示相應(yīng)的正則并、交、差算子；r是集合的正則化算子。實(shí)體造型是以立方體、圓柱體、球體、錐體、環(huán)狀體等多種基本體素為單位元素，通過(guò) 集合運(yùn)算（拼合或布爾運(yùn)算），生成所需要的幾何形體。這些形體具有完整的幾何信息，是真 實(shí)而唯一的三維物體。所以，實(shí)體造型包括兩部分內(nèi)容：即體素定義和描述，以及體素之間的布爾運(yùn)算（并、交、差）。布爾運(yùn)

17、算是構(gòu)造復(fù)雜實(shí)體的有效工具。目前常用的實(shí)體表示方法 主要有：構(gòu)造實(shí)體幾何法 （CSG）、邊界表示法（BRep）和掃描法。物體的CSG樹(shù)表示物體的體素構(gòu)造表示法（Constructive Solid Geometry, CSG ）是用兩個(gè)物體間的并、 交、差正則集合運(yùn)算操作生成一個(gè)新的物體的方法。CSG表示法：先定義一些形狀比較簡(jiǎn)單的常用體素，如方塊、圓柱、圓錐、球、棱柱等。然后用集合運(yùn)算并、交、差把體素修改成復(fù)雜形狀的形體。早期的 CSG模型僅使用代 數(shù)方程及半空間的概念， 體素只支持多面體與二次曲面體，而不支持表面含有自由曲面的實(shí)體。整個(gè)模型是棵樹(shù)結(jié)構(gòu)，最終形體的表面交線與有效區(qū)域沒(méi)有顯式給

18、出，不能直接用于 NC加工與有限元分析等后繼處理。7 / 13集合運(yùn)算構(gòu)造實(shí)體的過(guò)程可用二叉樹(shù)結(jié)構(gòu)表示，稱該二叉樹(shù)為CSG樹(shù)。樹(shù)的葉節(jié)點(diǎn)表示體素或帶有幾何變換參數(shù)的體素，非葉節(jié)點(diǎn)表示施加于其子節(jié)點(diǎn)的正則集合算子，或稱布爾算子。樹(shù)的根節(jié)點(diǎn)表示集合運(yùn)算的最終結(jié)果，也即希望得到的實(shí)體。邊界表不法邊界表示法(Brep-Boundary Representation )通過(guò)描述物體的邊界來(lái)表示一個(gè)物體。 所謂的邊界是指物體的內(nèi)部點(diǎn)與外部點(diǎn)的分界面，定義了物體的邊界，該物體也就被唯一地定義了。如下圖：邊界表示法一個(gè)重要的特點(diǎn)是：描述物體的信息包括幾何信息與拓?fù)湫畔蓚€(gè)方面。幾何信息是指物體在歐氏空間中的位

19、置、形狀和大?。欢?fù)湫畔⑹侵竿負(fù)湓?頂點(diǎn)、邊和表面)的數(shù)量及其相互間的連接關(guān)系。拓?fù)湫畔?gòu)成物體的骨架：而幾何信息則猶如附著在這一 骨架”上的 肌肉”。幾何信息有面(face )、環(huán)(loop )、邊(edge )和點(diǎn)(vertex ),拓?fù)湫畔⒂心Ｐ?model )、 區(qū)域(region )、外殼(shell)、面引用(face use )、環(huán)引用(loop use )、邊引用(edge use)和點(diǎn)引用(vertex use )。如下圖是用輻射邊數(shù)據(jù)結(jié)構(gòu)表示的一個(gè)形體模型，注意其 中實(shí)體、面、線是用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)表示的。topok）第gcoinetry8 / 13頂點(diǎn)頂點(diǎn)（Vertex

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

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

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

23、。外殼中的環(huán)和邊有時(shí)被稱為線框環(huán)”和 線框邊”，這是因?yàn)樗鼈兛梢杂糜诒硎拘误w的線框圖。區(qū)域由一組外殼組成，而模型由區(qū)域組成。正則形體對(duì)于任一形體，如果它是三維歐氏空間R3中非空、有界的封閉子集，且其邊界是二維流形（即該形體是連通的），則稱該形體為正則形體，否則稱為非正則形體。在這種表示法中，由于物體的點(diǎn)、邊和表面以獨(dú)立對(duì)象的形式的存在，所以可以方便地對(duì)物體進(jìn)行各種局部修改。多面體的頂點(diǎn)、邊和表面之間的拓?fù)潢P(guān)系可用9種不同的形式予以描述：1 .頂點(diǎn)相鄰性，表示 v->v2 .頂點(diǎn)一邊相鄰性，表示 v->e3 .頂點(diǎn)一面相鄰性，表示 v->f4 .邊一頂點(diǎn)，e->v5 .邊

24、一邊e->e6 .邊一面e->f7 .面一頂點(diǎn)f->v8 .面一邊f(xié)->e9 .面一面f->f邊界表示的數(shù)據(jù)結(jié)構(gòu)10 / 13兩種典型的邊界表示法數(shù)據(jù)結(jié)構(gòu)主要包括：翼邊結(jié)構(gòu)，雙向邊表(DCE DoublyConnected Edge List) ,半邊結(jié)構(gòu)，四邊結(jié)構(gòu)，輻射邊 (Radial-Edge)結(jié)構(gòu)等等。其中半邊 結(jié)構(gòu)非常適合表示正則形體。翼邊結(jié)構(gòu)在頂點(diǎn)、邊、表面等組成物體的三要素中，翼邊結(jié)構(gòu)以邊為中心來(lái)組織數(shù)據(jù)。如下圖：struct Edge Vertex P1,P2; Loop *LeftLoop,*RightLoop;struct Edge *ercw

25、,*ercc,*elcc,*elcw; 上圖菱邊e作為有向線段，其數(shù)據(jù)結(jié)構(gòu)中包含有兩個(gè)指針，分別指向e的兩個(gè)端點(diǎn)：起點(diǎn)P1和終點(diǎn)P2。此外，e中還設(shè)置有兩個(gè)環(huán)指針，分別指向菱邊 e所鄰接的兩表面上 的環(huán)Loop左和Loop右。這樣就確定了菱邊e與相鄰表面之間的拓?fù)潢P(guān)系。為了能從邊e出發(fā)找到它所在的任一閉合面環(huán)上的其他菱邊，在e中又增加了四個(gè)邊指針ercw、ercc、elcc、elcw , ercc表示e在右面環(huán)中沿逆時(shí)針?lè)较蛩B接的下一條菱邊，elcw表示e在左面環(huán)中沿順時(shí)針?lè)较蛩B接的下一條邊，余類推。由于翼邊結(jié)構(gòu)邊的構(gòu)造和使用比較復(fù)雜，后來(lái)在此結(jié)構(gòu)基礎(chǔ)上改進(jìn)，提出了半邊數(shù)據(jù)結(jié)構(gòu)。半邊結(jié)構(gòu)已

26、成為邊界表示的主流數(shù)據(jù)結(jié)構(gòu)。半邊數(shù)據(jù)結(jié)構(gòu)實(shí)體的B-rep表示模型是一非常復(fù)雜的模型，要求能夠表達(dá)出多面體各幾何元素之間完 整的幾何和拓?fù)潢P(guān)系，并且允許對(duì)這種幾何和拓?fù)潢P(guān)系進(jìn)行修改.在B-rep表示中，體、面、邊和頂點(diǎn)是最基本的幾何元素，在實(shí)體的拼合、顯示、分析計(jì)算或人機(jī)交互過(guò)程中，對(duì)基本幾何元素的下列操作是必不可少的：增加或刪除體、面、邊或頂點(diǎn)；已知一個(gè)體，查找它的所有面、所有邊或所有頂點(diǎn)； 已知一個(gè)面或一個(gè)邊，查找它所屬于的體；11 / 13已知一個(gè)面，順序查找圍成它所有邊；已知一個(gè)邊，查找交于該邊的所有面，或著查找該邊的鄰邊，或者查找該邊的兩個(gè) 端點(diǎn)；已知一個(gè)頂點(diǎn)，查找交于該頂點(diǎn)的所有邊或

27、所有面。以上這些基本操作的效率直接影響著整個(gè)實(shí)體造型系統(tǒng)的效率。一個(gè)B-rep數(shù)據(jù)結(jié)構(gòu)應(yīng)當(dāng)方便、迅速地實(shí)現(xiàn)幾何元素的這些查詢或增刪操作.為了查詢或操作方便，必須建立各幾何元素間的拓?fù)潢P(guān)系，且引入其它輔助元素，例如在許多 B-rep數(shù)據(jù)結(jié)構(gòu)中具有環(huán)結(jié)點(diǎn)，用來(lái)表示面的內(nèi)、外封閉邊界.在 B-rep的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)時(shí)，除了需要考慮時(shí)間的因素外， 還要考慮空間的因素，即模型所占計(jì)算機(jī)內(nèi)存的大小，但往往這兩方面是互相矛盾的.要想各個(gè)幾何元素之間查詢迅速，必然要在它們之間建立廣泛的聯(lián)系，這樣必然增加存儲(chǔ)空間的占用量。反過(guò)來(lái)也是如此，而半邊數(shù)據(jù)結(jié)構(gòu)就很好的權(quán)衡了空間和時(shí)間的問(wèn)題。在構(gòu)成多面體的三要素（點(diǎn)、邊、面）中，半邊數(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)共包含六個(gè)結(jié)點(diǎn)：體、面、環(huán)、邊、半邊和頂點(diǎn).半邊是一連接兩個(gè)頂點(diǎn)并具有一固定方向的線段.一系列首尾相連的半