ch三維形體的表示PPT課件

1、第六章 三維形體的表示 表示形體的兩種模型 實(shí)體的定義 正則集合運(yùn)算 特征表示 空間分割表示 推移表示 邊界表示 構(gòu)造實(shí)體幾何表示 不規(guī)則形體的建模方法 L系統(tǒng)第1頁/共103頁引 言 三維圖形在科學(xué)研究和工程技術(shù)中有著廣泛的應(yīng)用。在CAD中，需要對所設(shè)計(jì)的作品從不同的角度進(jìn)行審視。計(jì)算機(jī)幾何造型就是用計(jì)算機(jī)系統(tǒng)來表示、控制、分析和輸出三維形體。所以幾何造型是計(jì)算機(jī)圖形學(xué)中一個十分重要的應(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ù)的存儲和管理； 圖形控制，如對形體進(jìn)行平

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

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

4、分為內(nèi)環(huán)和外環(huán)。內(nèi)環(huán)是在已知面中的內(nèi)孔或凸臺面邊界的環(huán)，其邊按逆時針方向。外環(huán)是已知面的最大外邊界的環(huán)，其邊按順時針方向，按這種方式定義，在面上沿著邊的方向前進(jìn)，面的內(nèi)部始終在走向的右側(cè)。第6頁/共103頁形 體 邊形體內(nèi)兩個相鄰面的交界稱為邊，一條邊有且僅有兩個相鄰面。兩個端點(diǎn)確定一條邊，這兩個端點(diǎn)分別稱為該邊的起點(diǎn)和終點(diǎn)。假設(shè)Q是一個形體，E(Q)是形體邊的集合，則在Q(形體的邊界)中E(Q)滿足下屬條件的所有線段的集合： 邊e的兩個端點(diǎn)屬于V(Q)； 邊e中沒有一個內(nèi)部點(diǎn)屬于V(Q)（所有頂點(diǎn)的集合） 邊e上每個點(diǎn)，都有兩個不同的面，即存在兩個面fi，fiQ使得邊efifj； 形體Q的邊

5、框線WF(Q)是由有序?qū)?V(Q),E(Q)所組成。v1v2ef1f2第7頁/共103頁形 體 點(diǎn)邊的端點(diǎn)稱為點(diǎn)，點(diǎn)不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于物體內(nèi)、物體外或面內(nèi)，頂點(diǎn)又是F(面邊界)中兩條不共線的線段的交點(diǎn)。v1v2ef1f2第8頁/共103頁形 體 體素具有有限個參數(shù)定義，且簡單的連續(xù)封閉的形體稱為體素，如長方體、圓柱體、圓錐、球、環(huán)等。 半空間集合P|F(P)0成為半空間，其中P為R3中的一點(diǎn)，F(xiàn)為一個平面，當(dāng)F=0時，表示一個平面，這個平面的半空間可以由F(P)=ax+by+cz+d定義的平面加上在平面某一側(cè)的所有點(diǎn)組成。顯然一個長方體可以看成是6個平面半空間的交。 幾何信息

6、用來表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。 拓?fù)湫畔⒂脕肀硎拘误w之間的連接關(guān)系稱為拓?fù)湫畔?。?頁/共103頁表示形體的兩種模型 數(shù)據(jù)模型 完全以數(shù)據(jù)描述 例如 用以8個頂點(diǎn)表示的立方體 以中心點(diǎn)和半徑表示的球 以數(shù)據(jù)文件的形式存在 包括-特征表示、空間分割表示、推移表示、邊界表示、構(gòu)造實(shí)體幾何表示等 進(jìn)一步分為 線框模型 表面模型 實(shí)體模型第10頁/共103頁線框模型線框模型：將形體表示成一組輪廓線的集合。 一般地，畫出了形體的棱線與輪廓線就能唯一地表示出來。如圖，八個頂點(diǎn)可以定義一個長方體，但還不足以識別它，如果定義了棱線，則無論如何放置長方體都能唯一地表示了。對于多面體由于其輪廓線和

7、棱線通常是一致的，所以多面體的線模型更便于識別，且簡單。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4第11頁/共103頁線框模型 優(yōu)點(diǎn)：簡單、處理速度快 缺點(diǎn)：1、對于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察方向的改變而改變，無法用一組固定的輪廓線來表示它們。2、線框模型與形體之間不存在一一對應(yīng)關(guān)系：它僅僅通過給定的輪廓線約束所表示形體的邊界面，而在輪廓線之間的地方，形體的表面可以任意變化。3、沒有形體的表面信息，不適于真實(shí)感顯示，由此導(dǎo)致表示的形體可能產(chǎn)生二義性。第12頁/共103頁表面模型 表面模型 將形體表示成一組表

8、面的集合 如果把線框模型中的棱線包圍的部分定義為面，所形成的模型便是表面模型。其數(shù)據(jù)結(jié)構(gòu)是在線模型的基礎(chǔ)上附加一些指針，有序地連接棱線。下圖中表面編號表示第幾個表面，表面特征表面是平面還是曲面。 形體與其表面一一對應(yīng)，適合于真實(shí)感顯示4頂點(diǎn)個數(shù)1起始指針0表面特征5表面編接指針屬性頂點(diǎn)號14232341第13頁/共103頁表面模型 缺點(diǎn)： 不能有效的用來表示實(shí)體 原因： 1、表面模型中的所有面未必形成一個封閉的邊界 2、各個面的側(cè)向沒有明確定義，即不知道實(shí)體位于面的哪一側(cè)第14頁/共103頁實(shí)體模型 實(shí)體模型 用來描述實(shí)體，主要用于CAD/CAM 包含了描述一個實(shí)體所

9、需的較多信息，如幾何信息、拓?fù)湫畔?，可以支持多種運(yùn)算，如歐拉運(yùn)算等。第15頁/共103頁表示形體的兩種模型 過程模型 以一個過程和相應(yīng)的控制參數(shù)描述 例如 用一些控制參數(shù)和一個生成規(guī)則描述的植物 以一個數(shù)據(jù)文件和一段代碼的形式存在 包括-粒子系統(tǒng)、L系統(tǒng)、迭代函數(shù)系統(tǒng)等第16頁/共103頁表示形體的兩種模型 模型分類第17頁/共103頁實(shí)體的定義 抽象帶來的問題 計(jì)算機(jī)中表示的物體是無效的 不能夠客觀存在 為什么要求客觀存在 CAD/CAM的需求 什么是客觀存在（有效）實(shí)體的定義 具有一定的形狀 具有封閉的邊界（表面) 內(nèi)部連通 占據(jù)有限的空間 經(jīng)過運(yùn)算后，仍然是有效的物體第18頁/共103頁

10、實(shí)體的定義 將三維物體看做一個點(diǎn)集，它由內(nèi)點(diǎn)和邊界點(diǎn)共同組成。 內(nèi)點(diǎn)：具有完全包含于該點(diǎn)集的充分小的鄰域 邊界點(diǎn)：不具有內(nèi)點(diǎn)性質(zhì)的點(diǎn)集第19頁/共103頁實(shí)體的定義 A是一個點(diǎn)集，定義點(diǎn)集的正則運(yùn)算如下： i：取內(nèi)點(diǎn)運(yùn)算 c: 取閉包運(yùn)算 正則運(yùn)算r i A：A的全體內(nèi)點(diǎn)組成的集合，稱為A的內(nèi)部 c i A為A的內(nèi)部的閉包的運(yùn)算，是i A與其邊界點(diǎn)的并集。AicAr第20頁/共103頁實(shí)體的定義 正則點(diǎn)集 稱為A的正則點(diǎn)集 稱A為正則點(diǎn)集，如果它滿足 問題：正則點(diǎn)集是實(shí)體？ArAAr第21頁/共103頁實(shí)體的定義- -舉例說明 陰影部分：物體的內(nèi)部區(qū)域 黑色部分：邊界 (a)圖取內(nèi)點(diǎn)-(b)圖

11、求閉包-(c)圖 正則運(yùn)算：去除與物體維數(shù)不一致的懸掛部分或孤立部分。第22頁/共103頁實(shí)體的定義 實(shí)體的定義可計(jì)算的條件 正則點(diǎn)集 表面是二維流形 二維流形 其上任意一點(diǎn)存在充分小的領(lǐng)域與圓盤同構(gòu)（存在連續(xù)的一一映射）第23頁/共103頁正則集合運(yùn)算 為什么需要正則集合運(yùn)算 正則集合運(yùn)算是構(gòu)造復(fù)雜物體的有效方法 普通的集合運(yùn)算會產(chǎn)生無效物體 (b):AB (c):普通AB (d)：正則AB第24頁/共103頁正則集合運(yùn)算 集合運(yùn)算（并、交、差）是構(gòu)造形體的基本方法。正則形體經(jīng)過集合運(yùn)算后，可能會產(chǎn)生懸邊、懸面等低于三維的形體。 Requicha在引入正則形體概念的同時，還定義了正則集合運(yùn)算

12、的概念。正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個正則形體，即丟棄懸邊、懸面等。第25頁/共103頁正則集合運(yùn)算 正則集合運(yùn)算的定義 正則并 正則交 正則差)(*BopArBopA)(*BArBA)(*BArBA)(*BArBA第26頁/共103頁 任一實(shí)體S可以用它的邊界bS和它的內(nèi)部iS來表示，即 S=bS iS 由實(shí)體的定義可知，bS是封閉的，它將整個三維空間分成了三個區(qū)域： S的內(nèi)部iS , S的邊界bS ,S的外部eS。邊界bS與實(shí)體S是一一對應(yīng)的。確定了邊界，也就唯一確定了一個實(shí)體。 因此，為了求實(shí)體A，B的正則集合運(yùn)算結(jié)果A op* B，只要求出其邊界b（A op* B）即可。 正則

13、集合運(yùn)算第27頁/共103頁正則集合運(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第28頁/共103頁正則集合運(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è)由這樣一些邊界構(gòu)成：A、B位于

14、邊界的異側(cè)第29頁/共103頁正則集合運(yùn)算 對于A * B ，由交的定義可知： 1）A、B兩物體的邊界位于對方內(nèi)部的部分，即bA iB 和bB iA是b(A * B )的組成部分。 2） A、B兩物體的邊界位于對方外部的部分，即bA eB 和bB eA不是b(A * B )的組成部分。 3）對于A、B的重合邊界有： (bA bB)同側(cè)屬于b(A * B ); (bA bB)異側(cè)不屬于b(A * B ) 因此： b(A*B)=(bA iB) (bB iA)(bA bB)同側(cè)第30頁/共103頁正則集合運(yùn)算 同理： b(A*B)=(bA eB) (bB eA)(bAbB)同側(cè) b(A*B)=(bA

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

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

17、表示的空間分割方法作了改進(jìn)：均勻分割 自適應(yīng)分割 八叉樹建立過程八叉樹的根節(jié)點(diǎn)對應(yīng)整個物體空間如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為F(Full)，算法結(jié)束；如果它內(nèi)部沒有物體，將該節(jié)點(diǎn)標(biāo)記為E(Empty)，算法結(jié)束；如果它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為P(Partial)，并將它分割成8個子立方體，對每一個子立方體進(jìn)行同樣的處理第37頁/共103頁分解表示- -八叉樹表示 8叉樹的表示應(yīng)用三維形體的分解，它對一個外接立方體的形體進(jìn)行前后、左右、上下等部分8個小立方體，如果小立方體單元為滿或?yàn)榭?，表示該立方體完全在形體中或完全不在形體中，則其停止分解；對部分形體占有的小立方體需進(jìn)一步分解為8個

18、子立方體，直至所有小立方體單元要么全部滿，要么全部空，或已分解到規(guī)定的分解精度為止。236720131375具有子孫的節(jié)點(diǎn)(P)空節(jié)點(diǎn)(E)實(shí)節(jié)點(diǎn)(F)第38頁/共103頁分解表示- -八叉樹表示 優(yōu)點(diǎn) 可以表示任何物體，且形體表示的數(shù)據(jù)結(jié)構(gòu)簡單 簡化了形體的集合運(yùn)算。只需同時遍歷參加集合運(yùn)算的兩形體相應(yīng)的八叉樹，無需進(jìn)行復(fù)雜的求交運(yùn)算。 簡化了隱藏線（或面）的消除，因?yàn)樵诎瞬鏄浔硎局?，形體上各元素已按空間位置排成了一定的順序。 分析算法適合于并行處理。 缺點(diǎn) 沒有邊界信息，不適于圖形顯示 對物體進(jìn)行幾何變換困難 是物體的非精確表示 占用大量存儲。實(shí)際上，八叉樹表示是以存儲空間換取算法的效率第

19、39頁/共103頁分解表示- -線性八叉樹表示線性八叉樹：用一可變長度的一維數(shù)組來存儲一棵八叉樹。數(shù)組中僅存儲八叉樹的性質(zhì)為FULL的終端結(jié)點(diǎn)。并用一個八進(jìn)制數(shù)表示該結(jié)點(diǎn)在八叉樹中的位置。編碼方式為：Q1Q2Qm,其中Q1表示該結(jié)點(diǎn)所屬的一級父結(jié)點(diǎn)的編號（0-7），以此類推。例右圖為：1X,30X,31X,323X,33X 3 2031 75具有子孫的節(jié)點(diǎn)(P)空節(jié)點(diǎn)(E)實(shí)節(jié)點(diǎn)(F)第40頁/共103頁分解表示- -單元分解表示 單元分解表示 對空間位置枚舉表示的空間分割方法作了改進(jìn)：單一體素 多種體素 三種空間分割方法的比較 空間位置枚舉表示-同樣大小立方體粘合在一起表示物體 八叉樹表示-

20、不同大小的立方體粘合在一起表示物體 單元分解表示-多種體素粘合在一起表示物體第41頁/共103頁分解表示- -單元分解表示 優(yōu)點(diǎn) 表示簡單 容易實(shí)現(xiàn)幾何變換 基本體素可以按需選擇，表示范圍較廣 可以精確表示物體 缺點(diǎn) 物體的表示不唯一 物體的有效性難以保證第42頁/共103頁構(gòu)造表示 掃描表示 構(gòu)造實(shí)體幾何表示（CSG） 特征表示第43頁/共103頁構(gòu)造表示- -推移表示 將物體A沿著軌跡P推移得到物體B，稱B為sweep體 平移sweep-將一個二維區(qū)域沿著一個矢量方向推移第44頁/共103頁構(gòu)造表示- -推移表示 旋轉(zhuǎn)sweep-將一個二維區(qū)域繞旋轉(zhuǎn)軸旋轉(zhuǎn)一周第45頁/共103頁 三維形體

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

22、造表示- -構(gòu)造實(shí)體幾何表示( (CSG)CSG).通過對體素定義運(yùn)算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運(yùn)算為變換或正則集合運(yùn)算并、交、差。CSG表示可以看成是一棵有序的二叉樹。 其終端節(jié)點(diǎn)或是體素、或是形體變換參數(shù)。 非終端結(jié)點(diǎn)或是正則的集合運(yùn)算，或是變換（平移和/或旋轉(zhuǎn)）操作，這種運(yùn)算或變換只對其緊接著的子結(jié)點(diǎn)（子形體）起作用。第49頁/共103頁構(gòu)造表示- -構(gòu)造實(shí)體幾何表示( (CSG)CSG)第50頁/共103頁構(gòu)造表示- -構(gòu)造實(shí)體幾何表示( (CSG)CSG) CSG樹是無二義性的，但不是唯一的.CSG表示的優(yōu)點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)比較簡單，

23、數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易； 物體的有效性自動得到保證； CSG方法表示的形體的形狀，比較容易修改。第51頁/共103頁構(gòu)造表示- -構(gòu)造實(shí)體幾何表示( (CSG)CSG)CSG表示的缺點(diǎn)： 對形體的表示受體素的種類和對體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。 對形體的局部操作不易實(shí)現(xiàn)，例如，不能對基本體素的交線倒圓角； 由于形體的邊界幾何元素（點(diǎn)、邊、面）是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。 表示不唯一 第52頁/共103頁構(gòu)造表示- -特征表示 用一組特征參數(shù)表示一組類似的物體 特征包括形狀特征、材料特征等 適用于

24、工業(yè)上標(biāo)準(zhǔn)件的表示第53頁/共103頁構(gòu)造表示- -特征表示 從應(yīng)用層來定義形體，因而可以較好的表達(dá)設(shè)計(jì)者的意圖。從功能上可分為形狀、精度、材料和技術(shù)特征。 特征是面向應(yīng)用、面向用戶的。特征模型的表示仍然要通過傳統(tǒng)的幾何造型系統(tǒng)來實(shí)現(xiàn)。不同的應(yīng)用領(lǐng)域，具有不同的應(yīng)用特征。 在幾何造型系統(tǒng)中，根據(jù)特征的參數(shù)我們并不能直接得到特征的幾何元素信息，而在對特征及在特征之間進(jìn)行操作時需要這些信息。 特征方法表示形體的覆蓋域受限于特征的種類。第54頁/共103頁構(gòu)造表示的特點(diǎn) 構(gòu)造表示的特點(diǎn)： 構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有限等缺點(diǎn)， 但是，便于用戶輸入形體，在CAD/CAM系

25、統(tǒng)中，通常作為輔助表示方法。第55頁/共103頁邊界表示 邊界表示（BR表示或BRep表示） 按照體面環(huán)邊點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。 邊界表示的一個重要特點(diǎn)是在該表示法中，描述形體的信息包括幾何信息（Geometry）和拓?fù)湫畔ⅲ═opology）兩個方面。 拓?fù)湫畔⒚枋鲂误w上的頂點(diǎn)、邊、面的連接關(guān)系，拓?fù)湫畔⑿纬晌矬w邊界表示的“骨架”。 形體的幾何信息猶如附著在“骨架”上的肌肉。第56頁/共103頁邊界表示 邊界模型表達(dá)形體的基本拓?fù)鋵?shí)體包括： 1. 頂點(diǎn) 2. 邊。邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)來界定。邊的形狀（Curve）由邊的幾何信息

26、來表示，可以是直線或曲線，曲線邊可用一系列控制點(diǎn)或型值點(diǎn)來描述，也可用顯式、隱式或參數(shù)方程來描述。第57頁/共103頁邊界表示 3. 環(huán)。環(huán)（Loop）是有序、有向邊（Edge）組成的封閉邊界。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時針方向排序，內(nèi)環(huán)邊通常按順時針方向排序。 4.面。面（Face）由一個外環(huán)和若干個內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。 若一個面的外法矢向外，稱為正向面；反之，稱為反向面。第58頁/共103頁邊界表示 面的形狀可以是平面或曲面。平面可用平面方程來描述，曲面可用控制多邊形或型值點(diǎn)來描述，也可用曲面方程（隱式、顯式或參數(shù)形式）來描述。對于參數(shù)曲面，通常在其二維

27、參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來表示環(huán)，集合運(yùn)算中對面的分割也可在二維參數(shù)域上進(jìn)行。 5.體。體（Body）是面的并集。第59頁/共103頁邊界表示 邊界表示模型是一種采用描述形體表面的方法來描述的幾何表示模型。一個形體一般可以通過其邊界拆成一些有界的“面”或“小片”的子集來表示，而每一個面又可以通過其邊界的邊和頂點(diǎn)來表示。若面的表示無二義性，則其邊界表示模型也無二義性，但通常不一定只有唯一的表示。第60頁/共103頁邊界表示的數(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)層次

28、組織元素數(shù)據(jù)；如 面 頂點(diǎn)坐標(biāo) F1 (X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4) F2 (X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5) .其中頂點(diǎn)按照外觀順時針順序；第61頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu) 2 2以頂點(diǎn)為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以頂點(diǎn)/坐標(biāo)和面/頂點(diǎn)序列兩張關(guān)系表表示，如： 頂點(diǎn) 坐標(biāo) 面 頂點(diǎn)序列 V1 X1Y1Z1 F1 V1V2V3V4 . 3.3.以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以邊/頂點(diǎn)，頂點(diǎn)/坐標(biāo)，面/邊三張關(guān)系表表示；第62頁/共103頁邊界表示模型 四棱椎邊界表示的例子如右，由4個面組成，且這種表示可以看作是含有體、面、邊、頂點(diǎn)為節(jié)點(diǎn)的有向圖 四棱椎邊界表

29、示也可以基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱面節(jié)點(diǎn)邊節(jié)點(diǎn)頂點(diǎn)坐標(biāo)f1f2f3.e1e2e3e4.v1v2v3.(x1,y1,z1)組合結(jié)構(gòu)坐標(biāo)信息.第63頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -翼邊數(shù)據(jù)結(jié)構(gòu) 翼邊數(shù)據(jù)結(jié)構(gòu)：在1972年，由美國斯坦福大學(xué)Baumgart作為多面體的表示模式提出。 它用指針記錄了每一邊的兩個鄰面（即左外環(huán)和右外環(huán)）、兩個頂點(diǎn)、兩側(cè)各自相鄰的兩個鄰邊（即左上邊、左下邊、右上邊和右下邊），用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實(shí)體。第64頁/共103頁邊

30、界表示的數(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ù)據(jù)結(jié)構(gòu)引用；為了存取其中的任何一個，需要指向其Solid節(jié)點(diǎn)的指針。通過指向三個雙向鏈表的指針，Solid 節(jié)點(diǎn)給出對該模型的面、邊和頂點(diǎn)的訪問。所有實(shí)體被鏈接到一個雙向鏈表中，這個表通過指向該表的后繼和前趨實(shí)體的指針來實(shí)現(xiàn)的。具體包括： 第65頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -翼邊數(shù)據(jù)結(jié)構(gòu) Solid ID; 指向face的鏈表指針； 指向edge的鏈表指針； 指向vertex的鏈表指針； 第66頁/共

31、103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -翼邊數(shù)據(jù)結(jié)構(gòu) Face 表示多面體的一個小平面,包括：Face ID ；指向face的鏈表首元素的指針； 指向face的下一元素的指針； 第67頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -翼邊數(shù)據(jù)結(jié)構(gòu) Edge 由Edge節(jié)點(diǎn)構(gòu)成，是整個數(shù)據(jù)結(jié)構(gòu)的核心，每個Edge結(jié)點(diǎn)代表一條邊，包括：Edge ID ;Edge的起始頂點(diǎn)指針；Edge的終止頂點(diǎn)指針；Edge的右鄰面的指針；Edge的左鄰面的指針；Edge的右方向向前鄰邊指針；Edge的右方向向后鄰邊指針；Edge的左方向向前鄰邊指針；Edge的左方向向后鄰邊指針； 第68頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -翼邊數(shù)

32、據(jù)結(jié)構(gòu) Vertex 由vertex節(jié)點(diǎn)構(gòu)成，包括：Vertex ID ;頂點(diǎn)坐標(biāo)(x,y,z) ;指向與該vertex相連的第一條邊指針；指向下一個Vertex結(jié)點(diǎn)指針； 第69頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) 半邊數(shù)據(jù)結(jié)構(gòu)，是在80年代提出的，作為一種多面體的表示方法。在構(gòu)成多面體的三要素（頂點(diǎn)、邊、面）中，半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心。一條邊表示成拓?fù)湟饬x上方向相反的兩條“半邊”，所以稱為半邊數(shù)據(jù)結(jié)構(gòu)。 其中各節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)及含義如下：第70頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) typedef float vector4; typedef short ID; t

33、ypedef struct solid Solid ; typedef struct face Face ; typedef struct loop Loop ; typedef struct edge Edge ; typedef struct halfedge HalfEdge ; typedef struct vertex Vertex ;第71頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) 多面體struct solid ID solidno; /多面體序號 Face *sfaces; /指向多面體的面； Edge *sedges; /指向多面體的邊； Vertex *sverts

34、;/指向多面體的頂點(diǎn) Solid *nexts; /指向后一個多面體 Solid *prevs; /指向前一個多面體 ；第72頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) 面Struct face ID faceno; /面序號 Solid *fsolid;/指向該面所屬的多面體 Loop *floops; /指向構(gòu)成該面的環(huán) Vector feq; /平面方程 Face *prevf; /指向前一個面； Face *nextf; /指向后一個面； ；第73頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) 環(huán) struct loop HalfEdge *ledge; /指向構(gòu)成環(huán)的半邊

35、 Face *lface ; /指向該環(huán)所屬的面 Loop *prevl; /指向前一個環(huán) Loop *nextl; /指向后一個環(huán) 第74頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) 邊 struct edge ID edgeno; /邊的序號 HalfEdge *he1; /指向左半邊 HalfEdge *he2; /指向右半邊 Edge *preve; /指向前一條邊 Edge *nexte; /指向后一條邊 第75頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) 半邊 struct halfedge Edge *edge; /指向半邊的父邊 Vertex *vtx; /指向半邊

36、的起始頂點(diǎn) Loop *wloop; /指向半邊所屬的環(huán) HalEdge *prv; /指向前一條半邊 HalfEdge *nxt; /指向后一條半邊 第76頁/共103頁邊界表示的數(shù)據(jù)結(jié)構(gòu)- -半邊數(shù)據(jù)結(jié)構(gòu) 頂點(diǎn) struct vertex ID vertexno; /頂點(diǎn)序號 HalfEdge *vedge; /指向以該頂點(diǎn)為起 點(diǎn)的半邊 Vector vcoord; /頂點(diǎn)坐標(biāo) Vertex *nextv; /指向前一個頂點(diǎn) Vertex *prevv; /指向后一個頂點(diǎn) 第77頁/共103頁歐拉運(yùn)算和正則集合運(yùn)算 在邊界表示法中，可以定義一系列運(yùn)算來構(gòu)造或修改三維實(shí)體，常用的這類運(yùn)算有

37、： 歐拉運(yùn)算 正則集合運(yùn)算第78頁/共103頁歐拉運(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)系均要滿足歐拉公式。第79頁/共103頁歐拉運(yùn)算 歐拉公式V：頂點(diǎn)數(shù)E：棱線數(shù)F：面數(shù) 凡是滿足歐拉公式的形體 均稱為歐拉形體 歐拉公式是簡單多面體的必要條件。 附加條件： 每邊連接兩個頂點(diǎn) 每條邊只被兩個面共享等來保證有效性 至少要有三條邊交于一個頂點(diǎn)。V-e+f=2第80頁/共103頁歐拉運(yùn)算 廣義歐拉公式（P204）V-e+f-r=2(s-h)V：頂

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

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

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

41、體的所有表面片一一求交，否則該面片與另一物體的所有表面片都無交。同樣，只有在用邊界盒法無法判斷時才進(jìn)行求交計(jì)算，從而避免許多不必要的復(fù)雜的求交計(jì)算。 第85頁/共103頁正則集合運(yùn)算(2)計(jì)算兩物體各表面之間的交線。 由于物體表面均為有界表面，因此物體表面之間的交線是有界的直線或曲線。計(jì)算兩物體表面之間的交線的一般步驟如下 a.基于兩相交表面的方程，建立交線的方程，確定出初始交線。初始交線可能為無界。 b.分別確定初始交線位于兩相交表面內(nèi)部的部分。 c.計(jì)算位于兩相交表面內(nèi)部的兩相交區(qū)段的重疊部分，即為兩相交表面之間的真正交線。第86頁/共103頁(3)對物體的表面進(jìn)行分類 兩物體之間的交線將

42、它們的表面分割成兩部分，其中一部分落在拼合體的表面上，形成新的邊界，另一部分位于拼合體內(nèi)或拼合體外，應(yīng)在集合運(yùn)算最后一步予以刪除。(4)建立結(jié)果物體的邊界表示。正則集合運(yùn)算第87頁/共103頁邊界表示 Brep表示覆蓋域大，原則上能表示所有的形體，而且易于支持形體的特征表示等，Brep表示已成為當(dāng)前CAD/CAM系統(tǒng)的主要表示方法。 Brep表示的優(yōu)點(diǎn)是： 表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的，使得繪制Brep表示的形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系； 容易支持對物體的各種局部操作，比如進(jìn)行倒角。 便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如精度、表面粗糙度等。第88頁/共103頁邊界表示 Brep表示的缺點(diǎn)是： 數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜； Brep表示不一定對應(yīng)一個有效形體，通常運(yùn)用歐拉操作來保證Brep表示形體的有效性、正則性等。第89頁/共103頁各種表示方法的比較 精確性：能否精確的表示實(shí)體。特征表示-能夠精確表示一個實(shí)體。構(gòu)造實(shí)體幾何表示-依賴于它所采用的基本體素，如果基本體素足夠豐富，則能精確描述較大范圍內(nèi)的