計(jì)算機(jī)圖形學(xué) 第九章 三維形體的表示ppt課件

1、第九章 三維形體的表示 表示形體的兩種模型 實(shí)體的定義 正則集合運(yùn)算 特征表示 空間分割表示 推移表示 邊界表示 構(gòu)造實(shí)體幾何表示 不規(guī)則形體的建模方法 L系統(tǒng)引 言三維圖形在科學(xué)研究和工程技術(shù)中有著廣泛的應(yīng)用。在CAD中，需要對(duì)所設(shè)計(jì)的作品從不同的角度進(jìn)行審視。計(jì)算機(jī)幾何造型就是用計(jì)算機(jī)系統(tǒng)來表示、控制、分析和輸出三維形體。所以幾何造型是計(jì)算機(jī)圖形學(xué)中一個(gè)十分重要的應(yīng)用領(lǐng)域，它是CAD/CAM和CIMS系統(tǒng)的核心技術(shù)，也是用來實(shí)現(xiàn)計(jì)算機(jī)輔助設(shè)計(jì)的基本手段。幾何造型的功能：形體輸入，即把形體從用戶格式轉(zhuǎn)換成計(jì)算機(jī)內(nèi)部格式；圖形數(shù)據(jù)的存儲(chǔ)和管理；圖形控制，如對(duì)形體進(jìn)行平移、縮放、旋轉(zhuǎn)等幾何變換；

2、圖形修改，如應(yīng)用集合運(yùn)算、歐拉運(yùn)算、有理B樣條操作及其交互手段實(shí)現(xiàn)對(duì)形體局部或整體修改；圖形分析，如形體的容差分析，物質(zhì)特性分析等；圖形顯示輸出，如消隱、光照、顏色的控制等；詢問形體的屬性及其有關(guān)參數(shù)形 體 在計(jì)算機(jī)形體一般定義為六層拓?fù)浣Y(jié)構(gòu)，首先介紹在三維空間中基本術(shù)語的定義。形體形體(object)外殼外殼(shell)面面(face)環(huán)環(huán)(loop)邊邊(loop)頂點(diǎn)頂點(diǎn)(vertex) 曲線和直線方程曲線和直線方程 點(diǎn)的點(diǎn)的 幾何坐幾何坐標(biāo)標(biāo)形 體 體由封閉表面圍成的有效空間稱為體；一個(gè)形體Q是R3空間中非空、有界的封閉子集。其 邊境記為Q） 是有限個(gè)面的并集，而外殼是形體的最大邊界

3、。一個(gè)單位立方體可定義為：(x,y,z)R3|0 x1,0y1,0z1其中一個(gè)表面可表示為：(1,y,z)R3|0y1,0z1 必須注意：并沒有規(guī)定形體必須是一個(gè)連續(xù)的封閉集合，目的是用這樣的定義來擴(kuò)大幾何造型的域，使得形體可以由不連續(xù)的體素，或是僅有某些相交的形體組成。xzy形 體 面R3中非空、延續(xù)、共面且封閉的子集稱為面F，其邊界(記為F)是有限條線段的并集，Pt表示含有F的唯一平面。面是形體表面的一部分，且具有方向性.FPt形 體 環(huán)由有序、有向邊組成的面的封閉邊界稱為環(huán)，環(huán)中任意邊都不能自交，相鄰兩條邊共享一個(gè)端點(diǎn)，環(huán)又分為內(nèi)環(huán)和外環(huán)。內(nèi)環(huán)是在已知面中的內(nèi)孔或凸臺(tái)面邊界的環(huán)，其邊按逆

4、時(shí)針方向。外環(huán)是已知面的最大外邊界的環(huán)，其邊按順時(shí)針方向，按這種方式定義，在面上沿著邊的方向前進(jìn)，面的內(nèi)部始終在走向的右側(cè)。形 體邊形體內(nèi)兩個(gè)相鄰面的交界稱為邊，一條邊有且僅有兩個(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)；邊e中沒有一個(gè)內(nèi)部點(diǎn)屬于V(Q)（所有頂點(diǎn)的集合）邊e上每個(gè)點(diǎn)，都有兩個(gè)不同的面，即存在兩個(gè)面fi，fiQ使得邊efifj；形體Q的邊框線WF(Q)是由有序?qū)?V(Q),E(Q)所組成。v1v2ef1f2形 體 點(diǎn)邊的端點(diǎn)稱為

5、點(diǎn)，點(diǎn)不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于物體內(nèi)、物體外或面內(nèi)，頂點(diǎn)又是F(面邊界)中兩條不共線的線段的交點(diǎn)。v1v2ef1f2形 體體素具有有限個(gè)參數(shù)定義，且簡單的連續(xù)封閉的形體稱為體素，如長方體、圓柱體、圓錐、球、環(huán)等。半空間集合P|F(P)0成為半空間，其中P為R3中的一點(diǎn)，F(xiàn)為一個(gè)平面，當(dāng)F=0時(shí)，表示一個(gè)平面，這個(gè)平面的半空間可以由F(P)=ax+by+cz+d定義的平面加上在平面某一側(cè)的所有點(diǎn)組成。顯然一個(gè)長方體可以看成是6個(gè)平面半空間的交。幾何信息用來表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。拓?fù)湫畔⒂脕肀硎拘误w之間的連接關(guān)系稱為拓?fù)湫畔ⅰ１硎拘误w的兩種模型 數(shù)據(jù)模型 完全以數(shù)據(jù)

6、描述 例如 用以8個(gè)頂點(diǎn)表示的立方體 以中心點(diǎn)和半徑表示的球 以數(shù)據(jù)文件的形式存在 包括-特征表示、空間分割表示、推移表示、邊界表示、構(gòu)造實(shí)體幾何表示等 進(jìn)一步分為 線框模型 表面模型 實(shí)體模型線框模型線框模型：將形體表示成一組輪廓線的集合。一般地，畫出了形體的棱線與輪廓線就能唯一地表示出來。如圖，八個(gè)頂點(diǎn)可以定義一個(gè)長方體，但還不足以識(shí)別它，如果定義了棱線，則無論如何放置長方體都能唯一地表示了。對(duì)于多面體由于其輪廓線和棱線通常是一致的，所以多面體的線模型更便于識(shí)別，且簡單。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4線框模型優(yōu)

7、點(diǎn)：簡單、處理速度快缺陷：1、對(duì)于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察方向的改變而改變，無法用一組固定的輪廓線來表示它們。2、線框模型與形體之間不存在一一對(duì)應(yīng)關(guān)系：它僅僅通過給定的輪廓線約束所表示形體的邊界面，而在輪廓線之間的地方，形體的表面可以任意變化。3、沒有形體的表面信息，不適于真實(shí)感顯示，由此導(dǎo)致表示的形體可能產(chǎn)生二義性。表面模型 表面模型 將形體表示成一組表面的集合 如果把線框模型中的棱線包圍的部分定義為面，所形成的模型便是表面模型。其數(shù)據(jù)結(jié)構(gòu)是在線模型的基礎(chǔ)上附加一些指針，有序地連接棱線。下圖中表面編號(hào)表示第幾個(gè)表面，表面特征表面是平面還是曲面。 形體與其表面一一對(duì)應(yīng)，適

8、合于真實(shí)感顯示4頂點(diǎn)個(gè)數(shù)1起始指針0表面特征5表面編接指針屬性頂點(diǎn)號(hào)14232341表面模型 缺陷： 不能有效的用來表示實(shí)體 緣由： 1、表面模型中的所有面未必形成一個(gè)封閉的邊界 2、各個(gè)面的側(cè)向沒有明確定義，即不知道實(shí)體位于面的哪一側(cè)實(shí)體模型 實(shí)體模型 用來描述實(shí)體，主要用于CAD/CAM 包含了描述一個(gè)實(shí)體所需的較多信息，如幾何信息、拓?fù)湫畔?，可以支持多種運(yùn)算，如歐拉運(yùn)算等。表示形體的兩種模型 過程模型 以一個(gè)過程和相應(yīng)的控制參數(shù)描述 例如 用一些控制參數(shù)和一個(gè)生成規(guī)則描述的植物 以一個(gè)數(shù)據(jù)文件和一段代碼的形式存在 包括-粒子系統(tǒng)、L系統(tǒng)、迭代函數(shù)系統(tǒng)等表示形體的

9、兩種模型 模型分類實(shí)體的定義 抽象帶來的問題 計(jì)算機(jī)中表示的物體是無效的 不能夠客觀存在 為什么要求客觀存在 CAD/CAM的需求 什么是客觀存在有效）實(shí)體的定義 具有一定的形狀 具有封閉的邊界外表) 內(nèi)部連通 占據(jù)有限的空間 經(jīng)過運(yùn)算后，仍然是有效的物體實(shí)體的定義 將三維物體看做一個(gè)點(diǎn)集，它由內(nèi)點(diǎn)和邊界點(diǎn)共同組成。 內(nèi)點(diǎn)：具有完全包含于該點(diǎn)集的充分小的鄰域 邊界點(diǎn)：不具有內(nèi)點(diǎn)性質(zhì)的點(diǎn)集實(shí)體的定義 A是一個(gè)點(diǎn)集，定義點(diǎn)集的正則運(yùn)算如下：i：取內(nèi)點(diǎn)運(yùn)算c: 取閉包運(yùn)算正則運(yùn)算ri A：A的全體內(nèi)點(diǎn)組成的集合，稱為A的內(nèi)部c i A為A的內(nèi)部的閉包的運(yùn)算，是i A與其邊界點(diǎn)的并集。AicAr實(shí)體的

10、定義 正則點(diǎn)集 稱為A的正則點(diǎn)集 稱A為正則點(diǎn)集，如果它滿足 問題：正則點(diǎn)集是實(shí)體？ArAAr實(shí)體的定義-舉例說明 陰影部分：物體的內(nèi)部區(qū)域 黑色部分：邊境 (a)圖取內(nèi)點(diǎn)-(b)圖求閉包-(c)圖 正則運(yùn)算：去除與物體維數(shù)不一致的懸掛部分或孤立部分。實(shí)體的定義 實(shí)體的定義可計(jì)算的條件 正則點(diǎn)集 表面是二維流形 二維流形 其上任意一點(diǎn)存在充分小的領(lǐng)域與圓盤同構(gòu)存在連續(xù)的一一映射）正則集合運(yùn)算 為什么需要正則集合運(yùn)算 正則集合運(yùn)算是構(gòu)造復(fù)雜物體的有效方法 普通的集合運(yùn)算會(huì)產(chǎn)生無效物體 (b):AB (c):普通AB (d)：正則AB正則集合運(yùn)算 集合運(yùn)算并、交、差是構(gòu)造形體的基本方法。正則形體經(jīng)

11、過集合運(yùn)算后，可能會(huì)產(chǎn)生懸邊、懸面等低于三維的形體。 Requicha在引入正則形體概念的同時(shí)，還定義了正則集合運(yùn)算的概念。正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個(gè)正則形體，即丟棄懸邊、懸面等。正則集合運(yùn)算 正則集合運(yùn)算的定義 正則并 正則交 正則差)(*BopArBopA)(*BArBA)(*BArBA)(*BArBA 任一實(shí)體S可以用它的邊界bS和它的內(nèi)部iS來表示，即 S=bS iS 由實(shí)體的定義可知，bS是封閉的，它將整個(gè)三維空間分成了三個(gè)區(qū)域： S的內(nèi)部iS , S的邊界bS ,S的外部eS。邊界bS與實(shí)體S是一一對(duì)應(yīng)的。確定了邊界，也就唯一確定了一個(gè)實(shí)體。 因此，為了求實(shí)體A，B的正

12、則集合運(yùn)算結(jié)果A op* B，只要求出其邊界bA op* B即可。 正則集合運(yùn)算正則集合運(yùn)算考察A,B兩物體的交所形成拼合體的邊界，由于A,B為正則點(diǎn)集，它們均可表示為邊界點(diǎn)與體內(nèi)點(diǎn)的集合，即A=bA iA ; B=bB iB A物體的邊界 bA可按其位于B物體內(nèi)、B物體上、B物體外而分別表示為 bA = (bAiB)(bAbB) (bAeB) 同理，bB = (bBiA)(bBbA)(bBeA) A正則集合運(yùn)算其中bA bB = bB bA是A與B的公共邊界，它可以分成兩部分： （bA bB同側(cè)、 (bA bB)異側(cè)(bA bB)同側(cè)由這樣一些邊界構(gòu)成：A、B位于邊界的同側(cè)(bA bB)異側(cè)

13、由這樣一些邊界構(gòu)成：A、B位于邊界的異側(cè)正則集合運(yùn)算 對(duì)于A * B ，由交的定義可知： 1A、B兩物體的邊界位于對(duì)方內(nèi)部的部分，即bA iB 和bB iA是b(A * B )的組成部分。 2） A、B兩物體的邊界位于對(duì)方外部的部分，即bA eB 和bB eA不是b(A * B )的組成部分。 3對(duì)于A、B的重合邊界有： (bA bB)同側(cè)屬于b(A * B ); (bA bB)異側(cè)不屬于b(A * B ) 因此： b(A*B)=(bA iB) (bB iA)(bA bB)同側(cè)正則集合運(yùn)算 同理： b(A*B)=(bA eB) (bB eA)(bAbB)同側(cè) b(A*B)=(bA eB) (b

14、B iA)(bAbB)異側(cè)一些非正則形體的實(shí)例 一些非正則形體的實(shí)例(a)有懸面(b)有懸邊（c）一條邊有兩個(gè)以上 的鄰面（不連通）圖3.2.1 非正則形體實(shí)例 為了能夠處理非正則形體，產(chǎn)生了非正則造型技術(shù)。 九十年代以來，基于約束的參數(shù)化、變量化造型和支持線框、曲面、實(shí)體統(tǒng)一表示的非正則形體造型技術(shù)已成為幾何造型技術(shù)的主流。形體表示模型在實(shí)體模型的表示中，基本上可以分為分解表示、構(gòu)造表示和邊界表示三大類。1、分解表示將形體按某種規(guī)則分解為小的更易于描述的部分，每一小部分又可分為更小的部分，這種分解過程直至每一小部分都能夠直接描述為止。分解表示-空間位置枚舉表示 形體空間細(xì)分為小的均勻的立方體

15、單元。 用三維數(shù)組CIJK表示物體，數(shù)組中的元素與單位小立方體一一對(duì)應(yīng) 當(dāng)CIJK = 1時(shí)，表示對(duì)應(yīng)的小立方體被物體占據(jù) 當(dāng)CIJK = 0時(shí)，表示對(duì)應(yīng)的小立方體沒有被物體占據(jù)分解表示-空間位置枚舉表示 優(yōu)點(diǎn) 簡單，可以表示任何物體 容易實(shí)現(xiàn)物體間的交、并、差集合運(yùn)算 容易計(jì)算物體的整體性質(zhì)，如體積等 缺陷 占用大量的存儲(chǔ)空間，如1024*1024*1024 = 1G bits 物體的邊界面沒有顯式的解析表達(dá)式，不適于圖形顯示 對(duì)物體進(jìn)行幾何變換困難，如非90度的旋轉(zhuǎn)變換 是物體的非精確表示分解表示-八叉樹表示 八叉樹表示 對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：均勻分割 自適應(yīng)分割 八叉

16、樹建立過程八叉樹的根節(jié)點(diǎn)對(duì)應(yīng)整個(gè)物體空間八叉樹的根節(jié)點(diǎn)對(duì)應(yīng)整個(gè)物體空間如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為F(Full)，算法結(jié)束；，算法結(jié)束；如果它內(nèi)部沒有物體，將該節(jié)點(diǎn)標(biāo)記為如果它內(nèi)部沒有物體，將該節(jié)點(diǎn)標(biāo)記為E(Empty)，算法結(jié)束；，算法結(jié)束；如果它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為如果它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為P(Partial)，并將它分割成，并將它分割成8個(gè)子立方體，對(duì)每一個(gè)子立方體進(jìn)行同樣的處理個(gè)子立方體，對(duì)每一個(gè)子立方體進(jìn)行同樣的處理分解表示-八叉樹表示8叉樹的表示應(yīng)用三維形體的分解，它對(duì)一個(gè)外接立方體的形體進(jìn)行前后、左右、上下等部分8個(gè)

17、小立方體，如果小立方體單元為滿或?yàn)榭?，表示該立方體完全在形體中或完全不在形體中，則其停止分解；對(duì)部分形體占有的小立方體需進(jìn)一步分解為8個(gè)子立方體，直至所有小立方體單元要么全部滿，要么全部空，或已分解到規(guī)定的分解精度為止。236720131375具有子孫的節(jié)點(diǎn)具有子孫的節(jié)點(diǎn)(P)(P)空節(jié)點(diǎn)空節(jié)點(diǎn)(E)(E)實(shí)節(jié)點(diǎn)實(shí)節(jié)點(diǎn)(F)(F)分解表示-八叉樹表示 優(yōu)點(diǎn) 可以表示任何物體，且形體表示的數(shù)據(jù)結(jié)構(gòu)簡單 簡化了形體的集合運(yùn)算。只需同時(shí)遍歷參加集合運(yùn)算的兩形體相應(yīng)的八叉樹，無需進(jìn)行復(fù)雜的求交運(yùn)算。 簡化了隱藏線或面的消除，因?yàn)樵诎瞬鏄浔硎局?，形體上各元素已按空間位置排成了一定的順序。 分析算法適合于

18、并行處理。 缺陷 沒有邊界信息，不適于圖形顯示 對(duì)物體進(jìn)行幾何變換困難 是物體的非精確表示 占用大量存儲(chǔ)。實(shí)際上，八叉樹表示是以存儲(chǔ)空間換取算法的效率分解表示-線性八叉樹表示線性八叉樹：用一可變長度的一維數(shù)組來存儲(chǔ)一棵八叉樹。數(shù)組中僅存儲(chǔ)八叉樹的性質(zhì)為FULL的終端結(jié)點(diǎn)。并用一個(gè)八進(jìn)制數(shù)表示該結(jié)點(diǎn)在八叉樹中的位置。編碼方式為：Q1Q2Qm,其中Q1表示該結(jié)點(diǎn)所屬的一級(jí)父結(jié)點(diǎn)的編號(hào)0-7），以此類推。例右圖為：1X,30X,31X,323X,33X236720131375具有子孫的節(jié)點(diǎn)具有子孫的節(jié)點(diǎn)(P)(P)空節(jié)點(diǎn)空節(jié)點(diǎn)(E)(E)實(shí)節(jié)點(diǎn)實(shí)節(jié)點(diǎn)(F)(F)分解表示-單元分解表示 單元分解表示

19、對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：單一體素 多種體素 三種空間分割方法的比較 空間位置枚舉表示-同樣大小立方體粘合在一起表示物體 八叉樹表示-不同大小的立方體粘合在一起表示物體 單元分解表示-多種體素粘合在一起表示物體分解表示-單元分解表示優(yōu)點(diǎn)表示簡單容易實(shí)現(xiàn)幾何變換基本體素可以按需選擇，表示范圍較廣可以精確表示物體缺陷物體的表示不唯一物體的有效性難以保證構(gòu)造表示 掃描表示 構(gòu)造實(shí)體幾何表示CSG） 特征表示構(gòu)造表示-推移表示 將物體A沿著軌跡P推移得到物體B，稱B為sweep體 平移sweep-將一個(gè)二維區(qū)域沿著一個(gè)矢量方向推移構(gòu)造表示-推移表示 旋轉(zhuǎn)sweep-將一個(gè)二維區(qū)域繞旋轉(zhuǎn)

20、軸旋轉(zhuǎn)一周 三維形體也能在空間通過掃描變換生成新的形體：如左圖，一個(gè)圓柱體按指定方向在長方體上運(yùn)動(dòng)生成新的形體，這個(gè)過程猶如長方體與運(yùn)動(dòng)者的圓柱體不斷的作差運(yùn)算操作。有時(shí)經(jīng)過掃描變換所生成的形體可能會(huì)出現(xiàn)維數(shù)不一致問題。掃描線方向掃描線方向U U構(gòu)造表示-推移表示 廣義sweep 任意物體沿著任意軌跡推移 推移過程中物體可以變形構(gòu)造表示-推移表示 優(yōu)點(diǎn) 表示簡單、直觀 適合做圖形輸入手段 缺陷 作幾何變換困難 對(duì)幾何運(yùn)算不封閉 用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問題。 掃描方法不能直接獲取形體的邊界信息，表示形體的覆蓋域非常有限。構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG).通過對(duì)體素定義運(yùn)算而

21、得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運(yùn)算為變換或正則集合運(yùn)算并、交、差。CSG表示可以看成是一棵有序的二叉樹。其終端節(jié)點(diǎn)或是體素、或是形體變換參數(shù)。非終端結(jié)點(diǎn)或是正則的集合運(yùn)算，或是變換平移和/或旋轉(zhuǎn)操作，這種運(yùn)算或變換只對(duì)其緊接著的子結(jié)點(diǎn)子形體起作用。構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG)構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG) CSG樹是無二義性的，但不是唯一的. CSG表示的優(yōu)點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易； 物體的有效性自動(dòng)得到保證； CSG方法表示的形體的形狀，比較容易修改。構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG)CSG表

22、示的缺點(diǎn)：對(duì)形體的表示受體素的種類和對(duì)體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。對(duì)形體的局部操作不易實(shí)現(xiàn)，例如，不能對(duì)基本體素的交線倒圓角；由于形體的邊界幾何元素點(diǎn)、邊、面是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時(shí)間。表示不唯一 構(gòu)造表示-特征表示 用一組特征參數(shù)表示一組類似的物體 特征包括形狀特征、材料特征等 適用于工業(yè)上標(biāo)準(zhǔn)件的表示構(gòu)造表示-特征表示 從應(yīng)用層來定義形體，因而可以較好的表達(dá)設(shè)計(jì)者的意圖。從功能上可分為形狀、精度、材料和技術(shù)特征。 特征是面向應(yīng)用、面向用戶的。特征模型的表示仍然要通過傳統(tǒng)的幾何造型系統(tǒng)來實(shí)現(xiàn)。不同的應(yīng)用領(lǐng)域

23、，具有不同的應(yīng)用特征。 在幾何造型系統(tǒng)中，根據(jù)特征的參數(shù)我們并不能直接得到特征的幾何元素信息，而在對(duì)特征及在特征之間進(jìn)行操作時(shí)需要這些信息。 特征方法表示形體的覆蓋域受限于特征的種類。構(gòu)造表示的特點(diǎn) 構(gòu)造表示的特點(diǎn)： 構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有限等缺點(diǎn)， 但是，便于用戶輸入形體，在CAD/CAM系統(tǒng)中，通常作為輔助表示方法。邊界表示 邊界表示BR表示或BRep表示） 按照體面環(huán)邊點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。 邊界表示的一個(gè)重要特點(diǎn)是在該表示法中，描述形體的信息包括幾何信息Geometry和拓?fù)湫畔opology兩

24、個(gè)方面。 拓?fù)湫畔⒚枋鲂误w上的頂點(diǎn)、邊、面的連接關(guān)系，拓?fù)湫畔⑿纬晌矬w邊界表示的“骨架”。 形體的幾何信息猶如附著在“骨架上的肌肉。邊界表示 邊界模型表達(dá)形體的基本拓?fù)鋵?shí)體包括： 1. 頂點(diǎn) 2. 邊。邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)來界定。邊的形狀Curve由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點(diǎn)或型值點(diǎn)來描述，也可用顯式、隱式或參數(shù)方程來描述。邊界表示 3. 環(huán)。環(huán)Loop是有序、有向邊Edge組成的封閉邊界。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時(shí)針方向排序，內(nèi)環(huán)邊通常按順時(shí)針方向排序。 4.面。面Face由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)可以沒有內(nèi)環(huán)來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。

25、若一個(gè)面的外法矢向外，稱為正向面；反之，稱為反向面。邊界表示 面的形狀可以是平面或曲面。平面可用平面方程來描述，曲面可用控制多邊形或型值點(diǎn)來描述，也可用曲面方程隱式、顯式或參數(shù)形式來描述。對(duì)于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來表示環(huán)，集合運(yùn)算中對(duì)面的分割也可在二維參數(shù)域上進(jìn)行。 5.體。體Body是面的并集。邊界表示 邊界表示模型是一種采用描述形體表面的方法來描述的幾何表示模型。一個(gè)形體一般可以通過其邊界拆成一些有界的“面或“小片的子集來表示，而每一個(gè)面又可以通過其邊界的邊和頂點(diǎn)來表示。若面的表示無二義性，則其邊界表示模型也無二義性，但通常不一定只有唯一的表示。

26、U圖3.2.10 邊界表示邊界表示的數(shù)據(jù)結(jié)構(gòu) 邊界表示法的數(shù)據(jù)結(jié)構(gòu)有四種方法：以面為基礎(chǔ)、以頂點(diǎn)為基礎(chǔ)、以邊為基礎(chǔ)和翼邊結(jié)構(gòu)； 以面為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以面為基礎(chǔ)，按照體、面、頂點(diǎn)坐標(biāo)的樹結(jié)構(gòu)層次組織元素?cái)?shù)據(jù)；如 面 頂點(diǎn)坐標(biāo) F1 (X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4) F2 (X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5) .其中頂點(diǎn)按照外觀順時(shí)針順序；邊界表示的數(shù)據(jù)結(jié)構(gòu) 2 2以頂點(diǎn)為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以頂點(diǎn)為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以頂點(diǎn)以頂點(diǎn)/ /坐標(biāo)和面坐標(biāo)和面/ /頂點(diǎn)序列兩張關(guān)系表表頂點(diǎn)序列兩張關(guān)系表表示，如：示，如： 頂點(diǎn)頂點(diǎn) 坐標(biāo)坐標(biāo) 面面 頂點(diǎn)序列頂點(diǎn)序列 V

27、1 X1Y1Z1 F1 V1V2V3V4V1 X1Y1Z1 F1 V1V2V3V4 . 3.3.以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以邊以邊/ /頂點(diǎn)，頂點(diǎn)頂點(diǎn)，頂點(diǎn)/ /坐標(biāo)，面坐標(biāo)，面/ /邊三張關(guān)系表邊三張關(guān)系表表示；表示；邊界表示模型 四棱椎邊界表示的例子如右，由4個(gè)面組成，且這種表示可以看作是含有體、面、邊、頂點(diǎn)為節(jié)點(diǎn)的有向圖 四棱椎邊界表示也可以基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱四棱柱面節(jié)點(diǎn)面節(jié)點(diǎn)邊節(jié)點(diǎn)邊節(jié)點(diǎn)頂點(diǎn)坐標(biāo)頂點(diǎn)坐標(biāo)f1 f2 f3 .e1e2e3e4 .v1 v2 v3.(x1,

28、y1,z1)組合組合構(gòu)造構(gòu)造坐標(biāo)坐標(biāo)信息信息.邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu) 翼邊數(shù)據(jù)結(jié)構(gòu)：在1972年，由美國斯坦福大學(xué)Baumgart作為多面體的表示模式提出。 它用指針記錄了每一邊的兩個(gè)鄰面即左外環(huán)和右外環(huán)）、兩個(gè)頂點(diǎn)、兩側(cè)各自相鄰的兩個(gè)鄰邊即左上邊、左下邊、右上邊和右下邊），用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實(shí)體。左下邊右下邊 右上邊左上邊邊左外環(huán)右外環(huán)圖3.2.11 翼邊數(shù)據(jù)結(jié)構(gòu)邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu) 翼邊結(jié)構(gòu)由四種結(jié)點(diǎn)Solid , Face , edge和Vertex組成的，各結(jié)點(diǎn)描述如下： Solid 構(gòu)成引用的根節(jié)點(diǎn)。 在任意時(shí)刻

29、，會(huì)存在幾個(gè)數(shù)據(jù)結(jié)構(gòu)引用；為了存取其中的任何一個(gè)，需要指向其Solid節(jié)點(diǎn)的指針。通過指向三個(gè)雙向鏈表的指針，Solid 節(jié)點(diǎn)給出對(duì)該模型的面、邊和頂點(diǎn)的訪問。所有實(shí)體被鏈接到一個(gè)雙向鏈表中，這個(gè)表通過指向該表的后繼和前趨實(shí)體的指針來實(shí)現(xiàn)的。具體包括： 邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu) Solid ID; 指向face的鏈表指針； 指向edge的鏈表指針； 指向vertex的鏈表指針； 邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu) Face 表示多面體的一個(gè)小平面,包括：Face ID ；指向face的鏈表首元素的指針； 指向face的下一元素的指針； 邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu) Edge 由Edg

30、e節(jié)點(diǎn)構(gòu)成，是整個(gè)數(shù)據(jù)結(jié)構(gòu)的核心，每個(gè)Edge結(jié)點(diǎn)代表一條邊，包括：Edge ID ;Edge的起始頂點(diǎn)指針；Edge的終止頂點(diǎn)指針；Edge的右鄰面的指針；Edge的左鄰面的指針；Edge的右方向向前鄰邊指針；Edge的右方向向后鄰邊指針；Edge的左方向向前鄰邊指針；Edge的左方向向后鄰邊指針； 邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu) Vertex 由vertex節(jié)點(diǎn)構(gòu)成，包括：Vertex ID ;頂點(diǎn)坐標(biāo)(x,y,z) ;指向與該vertex相連的第一條邊指針；指向下一個(gè)Vertex結(jié)點(diǎn)指針；邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 半邊數(shù)據(jù)結(jié)構(gòu)，是在80年代提出的，作為一種多面體的表示方法。在構(gòu)

31、成多面體的三要素頂點(diǎn)、邊、面中，半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心。一條邊表示成拓?fù)湟饬x上方向相反的兩條“半邊”，所以稱為半邊數(shù)據(jù)結(jié)構(gòu)。 其中各節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)及含義如下：邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) typedef float vector4; typedef short ID; typedef struct solid Solid ; typedef struct face Face ; typedef struct loop Loop ; typedef struct edge Edge ; typedef struct halfedge HalfEdge ; typedef struct ver

32、tex Vertex ;邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 多面體 struct solid ID solidno; /多面體序號(hào) Face *sfaces; /指向多面體的面； Edge *sedges; /指向多面體的邊； Vertex *sverts;/指向多面體的頂點(diǎn) Solid *nexts; /指向后一個(gè)多面體 Solid *prevs; /指向前一個(gè)多面體 ；邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 面Struct face ID faceno; /面序號(hào) Solid *fsolid;/指向該面所屬的多面體 Loop *floops; /指向構(gòu)成該面的環(huán) Vector feq; /平面方程

33、 Face *prevf; /指向前一個(gè)面； Face *nextf; /指向后一個(gè)面； ；邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 環(huán) struct loop HalfEdge *ledge; /指向構(gòu)成環(huán)的半邊 Face *lface ; /指向該環(huán)所屬的面 Loop *prevl; /指向前一個(gè)環(huán) Loop *nextl; /指向后一個(gè)環(huán) 邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 邊 struct edge ID edgeno; /邊的序號(hào) HalfEdge *he1; /指向左半邊 HalfEdge *he2; /指向右半邊 Edge *preve; /指向前一條邊 Edge *nexte; /指向后

34、一條邊 邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 半邊 struct halfedge Edge *edge; /指向半邊的父邊 Vertex *vtx; /指向半邊的起始頂點(diǎn) Loop *wloop; /指向半邊所屬的環(huán) HalEdge *prv; /指向前一條半邊 HalfEdge *nxt; /指向后一條半邊 邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 頂點(diǎn) struct vertex ID vertexno; /頂點(diǎn)序號(hào) HalfEdge *vedge; /指向以該頂點(diǎn)為起 點(diǎn)的半邊 Vector vcoord; /頂點(diǎn)坐標(biāo) Vertex *nextv; /指向前一個(gè)頂點(diǎn) Vertex *prevv;

35、/指向后一個(gè)頂點(diǎn) 歐拉運(yùn)算和正則集合運(yùn)算 在邊界表示法中，可以定義一系列運(yùn)算來構(gòu)造或修改三維實(shí)體，常用的這類運(yùn)算有： 歐拉運(yùn)算 正則集合運(yùn)算歐拉運(yùn)算歐拉運(yùn)算是三維物體邊界表示數(shù)據(jù)結(jié)構(gòu)的生成操作。運(yùn)用歐拉運(yùn)算，可以正確、有效構(gòu)建三維物體邊界表示中的所有拓?fù)湓睾屯負(fù)潢P(guān)系。該運(yùn)算之所以稱為歐拉運(yùn)算，是因?yàn)槊恳环N運(yùn)算所構(gòu)建的拓?fù)湓睾屯負(fù)潢P(guān)系均要滿足歐拉公式。歐拉運(yùn)算 歐拉公式 V：頂點(diǎn)數(shù) E：棱線數(shù) F：面數(shù) 凡是滿足歐拉公式的形體 均稱為歐拉形體 歐拉公式是簡單多面體 的必要條件。 附加條件：每邊連接兩個(gè)頂點(diǎn) 每條邊只被兩個(gè)面共享等來保證有效性V-e+f=2歐拉運(yùn)算 廣義歐拉公式V-e+f-r=

36、2(s-h)V：頂點(diǎn)數(shù)，E：棱線數(shù)，F(xiàn)：面數(shù)r: 多面體表面上孔的個(gè)數(shù)s: 相互分離的多面體數(shù)h: 貫穿多面體的孔洞個(gè)數(shù)歐拉運(yùn)算 若將廣義歐拉公式 中的v,e,f,h,r,s分別看作獨(dú)立的坐標(biāo)變量，則上式在六維空間中定義了一張平面平面是五維的），該平面通過原點(diǎn)。 由于各坐標(biāo)變量的取值只能是非負(fù)的整數(shù)，所以上式實(shí)際上對(duì)應(yīng)了一張五維平面上的網(wǎng)格，每個(gè)多面體都對(duì)應(yīng)一個(gè)網(wǎng)格點(diǎn)。但并不是每個(gè)網(wǎng)格都對(duì)應(yīng)一個(gè)有效的多面體只是必要條件）。如果要構(gòu)造的多面體對(duì)應(yīng)的網(wǎng)格點(diǎn)的坐標(biāo)是（ v,e,f,h,r,s ），那么構(gòu)造該實(shí)體的過程就是從原點(diǎn)開始沿網(wǎng)格一步一步向這個(gè)坐標(biāo)點(diǎn)前進(jìn)的過程。由于網(wǎng)格上的每點(diǎn)都滿足歐拉公式，

37、最后的多面體也必然滿足它。V-e+f-r=2(s-h)歐拉運(yùn)算 前進(jìn)的“走法是多種多樣的，因?yàn)橹挥形鍌€(gè)自由變量，所以只需五種基本走法就可以了。要求：每一步至多只能使某一坐標(biāo)變量增減一個(gè)單位。每一步行走都有明顯的幾何意義。 歐拉運(yùn)算是對(duì)形體進(jìn)行增加，刪除點(diǎn)、邊、面而生成的一個(gè)新的歐拉形的處理。最基本的五種歐拉運(yùn)算是： 增加一條邊和一個(gè)頂點(diǎn)； 增加一個(gè)面和一條邊； 增加一條邊, 一個(gè)面和一個(gè)頂點(diǎn)； 增加一條邊和一個(gè)頂點(diǎn)； 增加一條邊,且刪除一個(gè)孔穴。歐拉運(yùn)算 相應(yīng)的五種補(bǔ)運(yùn)算是： 刪除一條邊和一個(gè)頂點(diǎn)； 刪除一個(gè)面和一條頂點(diǎn)； 刪除一個(gè)體, 一個(gè)面和一個(gè)頂點(diǎn)； 刪除一個(gè)孔洞和一個(gè)體； 刪除一條邊,

38、且增加一個(gè)孔穴； 任何一種歐拉形體(或歐拉運(yùn)算)都可以用最基本的歐拉運(yùn)算的現(xiàn)行組合來表示。用最基本的歐拉運(yùn)算操作生成的形體必定是一個(gè)歐拉形體。正則集合運(yùn)算通過對(duì)邊界表示的物體做正則集合運(yùn)算可以構(gòu)造新的邊界表示的物體。對(duì)具有平面邊界、曲面邊界的物體進(jìn)行集合運(yùn)算的算法有很多，算法的大致步驟如下： (1)預(yù)檢查兩物體是否相交 第一步：計(jì)算兩個(gè)待求交物體的包圍盒，若兩包圍盒不相交，則兩物體不相交，正則集合運(yùn)算結(jié)束，否則進(jìn)行下一層。 第二步：計(jì)算兩物體每一個(gè)表面片的包圍盒，當(dāng)某個(gè)面片的包圍盒與另一物體的包圍盒相交時(shí)，將該面片與另一物體的所有表面片一一求交，否則該面片與另一物體的所有表面片都無交。同樣，只

39、有在用邊界盒法無法判斷時(shí)才進(jìn)行求交計(jì)算，從而避免許多不必要的復(fù)雜的求交計(jì)算。 正則集合運(yùn)算(2)計(jì)算兩物體各表面之間的交線。 由于物體表面均為有界表面，因此物體表面之間的交線是有界的直線或曲線。計(jì)算兩物體表面之間的交線的一般步驟如下 a.基于兩相交表面的方程，建立交線的方程，確定出初始交線。初始交線可能為無界。 b.分別確定初始交線位于兩相交表面內(nèi)部的部分。 c.計(jì)算位于兩相交表面內(nèi)部的兩相交區(qū)段的重疊部分，即為兩相交表面之間的真正交線。(3)對(duì)物體的表面進(jìn)行分類 兩物體之間的交線將它們的表面分割成兩部分，其中一部分落在拼合體的表面上，形成新的邊界，另一部分位于拼合體內(nèi)或拼合體外，應(yīng)在集合運(yùn)算

40、最后一步予以刪除。(4)建立結(jié)果物體的邊界表示。正則集合運(yùn)算邊界表示 Brep表示覆蓋域大，原則上能表示所有的形體，而且易于支持形體的特征表示等，Brep表示已成為當(dāng)前CAD/CAM系統(tǒng)的主要表示方法。 Brep表示的優(yōu)點(diǎn)是： 表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的，使得繪制Brep表示的形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系； 容易支持對(duì)物體的各種局部操作，比如進(jìn)行倒角。 便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如精度、表面粗糙度等。邊界表示 Brep表示的缺點(diǎn)是： 數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲(chǔ)空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜； Brep表示不一定對(duì)應(yīng)一個(gè)有效形體，通常運(yùn)用歐拉操作來保證Brep表示形體的有效性、正則性等。浙江大學(xué)信息學(xué)院 計(jì)算機(jī)圖形學(xué)各種表示方法的比較 精確性：能否精確的表示實(shí)體。 特征表示-能夠精確表示一個(gè)實(shí)體。 構(gòu)造