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

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

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

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

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

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

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

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

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

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

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

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

12、則集合運算結(jié)果A op* B，只要求出其邊界bA op* B即可。 正則集合運算正則集合運算考察A,B兩物體的交所形成拼合體的邊界，由于A,B為正則點集，它們均可表示為邊界點與體內(nèi)點的集合，即A=bA iA ; B=bB iB A物體的邊界 bA可按其位于B物體內(nèi)、B物體上、B物體外而分別表示為 bA = (bAiB)(bAbB) (bAeB) 同理，bB = (bBiA)(bBbA)(bBeA) A正則集合運算其中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è)正則集合運算 對于A * B ，由交的定義可知： 1A、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è)正則集合運算 同理： b(A*B)=(bA eB) (bB eA)(bAbB)同側(cè) b(A*B)=(bA eB) (b

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

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

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

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

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

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

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

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

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

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

24、個方面。 拓?fù)湫畔⒚枋鲂误w上的頂點、邊、面的連接關(guān)系，拓?fù)湫畔⑿纬晌矬w邊界表示的“骨架”。 形體的幾何信息猶如附著在“骨架上的肌肉。邊界表示 邊界模型表達(dá)形體的基本拓?fù)鋵嶓w包括： 1. 頂點 2. 邊。邊有方向，它由起始頂點和終止頂點來界定。邊的形狀Curve由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點或型值點來描述，也可用顯式、隱式或參數(shù)方程來描述。邊界表示 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)。

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

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

27、1 X1Y1Z1 F1 V1V2V3V4V1 X1Y1Z1 F1 V1V2V3V4 . 3.3.以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以邊以邊/ /頂點，頂點頂點，頂點/ /坐標(biāo)，面坐標(biāo)，面/ /邊三張關(guān)系表邊三張關(guān)系表表示；表示；邊界表示模型 四棱椎邊界表示的例子如右，由4個面組成，且這種表示可以看作是含有體、面、邊、頂點為節(jié)點的有向圖 四棱椎邊界表示也可以基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱四棱柱面節(jié)點面節(jié)點邊節(jié)點邊節(jié)點頂點坐標(biāo)頂點坐標(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作為多面體的表示模式提出。 它用指針記錄了每一邊的兩個鄰面即左外環(huán)和右外環(huán)）、兩個頂點、兩側(cè)各自相鄰的兩個鄰邊即左上邊、左下邊、右上邊和右下邊），用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實體。左下邊右下邊 右上邊左上邊邊左外環(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é)點Solid , Face , edge和Vertex組成的，各結(jié)點描述如下： Solid 構(gòu)成引用的根節(jié)點。 在任意時刻

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

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

31、成多面體的三要素頂點、邊、面中，半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心。一條邊表示成拓?fù)湟饬x上方向相反的兩條“半邊”，所以稱為半邊數(shù)據(jù)結(jié)構(gòu)。 其中各節(jié)點的數(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; /多面體序號 Face *sfaces; /指向多面體的面； Edge *sedges; /指向多面體的邊； Vertex *sverts;/指向多面體的頂點 Solid *nexts; /指向后一個多面體 Solid *prevs; /指向前一個多面體 ；邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 面Struct face ID faceno; /面序號 Solid *fsolid;/指向該面所屬的多面體 Loop *floops; /指向構(gòu)成該面的環(huán) Vector feq; /平面方程

33、 Face *prevf; /指向前一個面； Face *nextf; /指向后一個面； ；邊界表示的數(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; /指向前一個環(huán) Loop *nextl; /指向后一個環(huán) 邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 邊 struct edge ID edgeno; /邊的序號 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; /指向半邊的起始頂點 Loop *wloop; /指向半邊所屬的環(huán) HalEdge *prv; /指向前一條半邊 HalfEdge *nxt; /指向后一條半邊 邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu) 頂點 struct vertex ID vertexno; /頂點序號 HalfEdge *vedge; /指向以該頂點為起 點的半邊 Vector vcoord; /頂點坐標(biāo) Vertex *nextv; /指向前一個頂點 Vertex *prevv;

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

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

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

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

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

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