三維實體模型中B-Rep或CSG表示法的一種CC++語言的數(shù)據(jù)結(jié)構(gòu)定義

1、平時作業(yè)B_RepCSGC/C+語言的數(shù)據(jù)結(jié)構(gòu)定義。物體的 CSG 樹表示物體的體素構(gòu)造表示法（Constructive Solid Geometry, CSG）是用兩個物體間的并、交、差正則集合運算操作生成一個新的物體的方法。CSG棱柱等。然后用集合運算并、交、差把體素修改成復(fù)雜形狀的形體。早期的CSG NCCSG實體。邊界表示法邊界表示法（Brep-BoundaryRepresentation）通過描述物體的邊界來表示該物體也就被唯一地定義了。如下圖：幾何信息有面（face、環(huán)（loop、邊（edge）和點（vertex，拓?fù)湫畔⒂心Ｐ停╩odel、 區(qū)域（region、外殼（shell、

2、面引用（face use、環(huán)引用loopuse、邊引用（edgeuse）和點引用（vertexuse示的。頂點頂點（Vertex）的位置用（幾何）點（Point）來表示。點是幾何造型中的儲、管理、輸出形體的實質(zhì)就是對點集及其連接關(guān)系的處理。在正則形體定義中，不允許孤立點存在。邊邊（Edge）是兩個鄰面(對正則形體而言)、或多個鄰面(對非正則形體而言)的交集，邊有方向，它由起始頂點和終止頂點來界定。邊的形狀（Curve）由邊包含其兩個端點和引用它的所有環(huán)邊等信息的拓?fù)湓胤Q為邊。環(huán)環(huán)（Loop）是有序、有向邊（Edge）組成的封閉邊界。環(huán)中的邊不能相交，內(nèi)環(huán)邊通常按順時針方向排序。面面（Face

3、）由一個外環(huán)和若干個內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來表示，內(nèi)環(huán)完全在由面的幾何信息來表示， 體體（Body）是面的并集。在正則幾何造型系統(tǒng)中，要求體是正則的，非正則覆蓋域。 幾何形體是由封閉表面圍成的空間，是歐氏空間中非空、有界的封閉子集，其邊界是有限個面的并集。外殼外殼是一些點、邊、環(huán)、面的集合,其所含的面集有可能圍成封閉的三維區(qū)區(qū)域由一組外殼組成，而模型由區(qū)域組成。正則形體R3形體。在這種表示法中，由于物體的點、邊和表面以獨立對象的形式的存在，所以可以方便地對物體進行各種局部修改。多面體的頂點、邊和表面之間的拓?fù)潢P(guān)系可用 9 種不同的形式予以描述：頂點相鄰性，表示 v-vv-e頂點面相鄰性，表示4

4、邊頂點，e-v5 邊邊e-e6 邊面e-f7 面頂點f-v 8 面邊9 面面f-f邊界表示的數(shù)據(jù)結(jié)構(gòu)兩種典型的邊界表示法數(shù)據(jù)結(jié)構(gòu)主要包括：翼邊結(jié)構(gòu)，雙向邊表 (DCEL Doubly Connected Edge List) ，半邊結(jié)構(gòu)，四邊結(jié)構(gòu)，輻射邊(Radial-Edge) 結(jié)構(gòu)等等。其中半邊結(jié)構(gòu)非常適合表示正則形體。翼邊結(jié)構(gòu)如下圖：struct EdgeVertex P1,P2;Loop *LeftLoop,*RightLoop;struct Edge *ercw,*ercc,*elcc,*elcw;eeP1P2。此外，eLoopLoope的拓?fù)潢P(guān)系。為了能從邊eercw、ercc、e

5、lcc、elcw，ercce時針方向所連接的下一條菱邊，elcwe下一條邊，余類推。由于翼邊結(jié)構(gòu)邊的構(gòu)造和使用比較復(fù)雜，后來在此結(jié)構(gòu)基礎(chǔ)上改進，提出了半邊數(shù)據(jù)結(jié)構(gòu)。半邊結(jié)構(gòu)已成為邊界表示的主流數(shù)據(jù)結(jié)構(gòu)。半邊數(shù)據(jù)結(jié)構(gòu)B-rep分析計算或人機交互過程中，對基本幾何元素的下列操作是必不可少的：增加或刪除體、面、邊或頂點；已知一個體，查找它的所有面、所有邊或所有頂點；已知一個面或一個邊，查找它所屬于的體；已知一個面，順序查找圍成它所有邊；已知一個邊，查找交于該邊的所有面，或著查找該邊的鄰邊，或者查找該邊的兩個端點；已知一個頂點，查找交于該頂點的所有邊或所有面B-repB-rep來也是如此，而半邊數(shù)據(jù)結(jié)

6、構(gòu)就很好的權(quán)衡了空間和時間的問題。在構(gòu)成多面體的三要素（點、邊、面）兩個面。半邊的含義如上圖所示.半邊數(shù)據(jù)結(jié)構(gòu)的優(yōu)點是幾何元素之間的互相查詢非常方便，不足之處是由于結(jié)點多占用空間較大。C指針互相聯(lián)系.這些結(jié)點描述如下：頂點結(jié)點：頂點結(jié)點是半邊數(shù)據(jù)結(jié)構(gòu)中最底層的結(jié)點，實體的幾何位置和尺寸最終都由頂點結(jié)點來定義.所以，頂點結(jié)點必須包含頂點的空間三維坐標(biāo)值半邊起始頂點的指針.邊結(jié)點：邊結(jié)點包含左右兩個半邊的指針，通過這兩個指針可以查找該邊的兩個端點以及交于該邊的兩個面.指向前趨邊和后繼邊的兩個指針實現(xiàn)一個實體內(nèi)邊的雙向鏈表.環(huán)結(jié)點：因為一個環(huán)包含一系列的首尾相接的半邊，故環(huán)結(jié)點是一個指向這些半邊其中

7、之一的指針，通過該指針可以查找構(gòu)成該環(huán)的所有半邊.環(huán)結(jié)點還包含指向前趨和后繼環(huán)的兩個指針，用以實現(xiàn)一個面內(nèi)環(huán)的雙向鏈表.另外，環(huán)結(jié)點還包含指向環(huán)所在面的指針.面結(jié)點：因為面是由若干個環(huán)圍成的內(nèi)部連通的平面多邊形，所以，面結(jié)點包含一個環(huán)的首指針，用來查找圍成它的所有環(huán).因為外環(huán)只有一個，為了區(qū)分內(nèi)環(huán)和外環(huán)，面結(jié)點中包含指向它的外環(huán)的指針.面的前趨指針和后繼指針形成一個實體內(nèi)面的雙向鏈表.面結(jié)點中還包含指向它所屬于的體的指針，用來查詢面所屬于的實體.面所在平面的方程也是定義完整實體的重要內(nèi)容，所以，面結(jié)點中包含一個四個浮點數(shù)的數(shù)組，表示其平面方程.間也是通過前趨指針和后繼指針形成的雙向鏈表來連接。為了表示非正則形體，1986，Weiler（RadialEdge）數(shù)據(jù)結(jié)構(gòu)。輻射邊結(jié)構(gòu)的形體模型由幾何信息（Geometry）和拓?fù)湫畔ⅲ═opology） 兩部分組成。幾何信息有面（face、環(huán)（loop、邊（edge）和點（vertex，拓?fù)湫畔⒂心Ｐ停╩odel。區(qū)域（region、