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

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

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

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

4、邊頂點(diǎn)，e-v5 邊邊e-e6 邊面e-f7 面頂點(diǎn)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時(shí)針方向所連接的下一條菱邊，elcwe下一條邊，余類推。由于翼邊結(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分析計(jì)算或人機(jī)交互過程中，對基本幾何元素的下列操作是必不可少的：增加或刪除體、面、邊或頂點(diǎn)；已知一個體，查找它的所有面、所有邊或所有頂點(diǎn)；已知一個面或一個邊，查找它所屬于的體；已知一個面，順序查找圍成它所有邊；已知一個邊，查找交于該邊的所有面，或著查找該邊的鄰邊，或者查找該邊的兩個端點(diǎn)；已知一個頂點(diǎn)，查找交于該頂點(diǎn)的所有邊或所有面B-repB-rep來也是如此，而半邊數(shù)據(jù)結(jié)

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

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