形體在計算機內(nèi)的表示ppt課件

1、3.2形體在計算機內(nèi)的表示 3.2.1 引言 計算機中表示形體，通常用線框、外表和實體三種模型。 對于任一形體，假設(shè)它是3維歐氏空間中非空、有界的封鎖子集，且其邊境是二維流形即該形體是連通的，我們稱該形體為正那么形體，否那么稱為非正那么形體。 些非正那么形體的實例(a)有懸面(b)有懸邊（c）一條邊有兩個以上 的鄰面（不連通）圖3.2.1 非正則形體實例 集合運算并、交、差是構(gòu)造形體的根本方法。正那么形體經(jīng)過集合運算后，能夠會產(chǎn)生懸邊、懸面等低于三維的形體。 Requicha在引入正那么形體概念的同時，還定義了正那么集合運算的概念。正那么集合運算保證集合運算的結(jié)果仍是一個正那么形體，即丟棄懸邊

2、、懸面等。ABabab圖3.2.2 二個二維圖形的交產(chǎn) 生一個退化的結(jié)果懸邊ABABC=AB集合論的求交計算正則集合下的求交運算*C=A*B圖3.2.3 集合和正則的交運算 為了可以處置非正那么形體，產(chǎn)生了非正那么外型技術(shù)。 九十年代以來，基于約束的參數(shù)化、變量化外型和支持線框、曲面、實體一致表示的非正那么形體外型技術(shù)已成為幾何外型技術(shù)的主流。3.2.2 形體表示模型在實體模型的表示中，根本上可以分為分解表示、構(gòu)造表示和邊境表示三大類。1、分解表示將形體按某種規(guī)那么分解為小的更易于描畫的部分，每一小部分又可分為更小的部分，這種分解過程直至每一小部分都可以直接描畫為止。(a)將形體空間細(xì)分為小的

3、立方體單元。這種表示方法的優(yōu)點是簡單，容易實現(xiàn)形體的交、并、差計算，但是占用的存儲量太大，物體的邊境面沒有顯式的解析表達(dá)式，不便于運算。(b)八叉樹法表示形體.首先對形體定義一個外接立方體，再把它分解成八個子立方體，并對立方體依次編號為0，1，2，7。假設(shè)子立方體單元曾經(jīng)一致，即為滿該立方體充溢形體或為空沒有形體在其中，那么該子立方體可停頓分解；否那么，需求對該立方體作進(jìn)一步分解，再一分為八個子立方體。在八叉樹中，非葉結(jié)點的每個結(jié)點都有八個分支。優(yōu)點主要是：1形體表示的數(shù)據(jù)構(gòu)造簡單。 2簡化了形體的集合運算。只需同時遍歷參與集合運算的兩形體相應(yīng)的八叉樹，無需進(jìn)展復(fù)雜的求交運算。 3簡化了隱藏線

4、或面的消除，由于在八叉樹表示中，形體上各元素已按空間位置排成了一定的順序。 4分析算法適宜于并行處置。八叉樹表示的缺陷：占用的存儲多，只能近似表示形體，以及不易獲取形體的邊境信息等。012356712337（a）（b）（c）具有子孫的節(jié)點空節(jié)點實節(jié)點圖3.2.4 用八叉樹表示形體 2構(gòu)造表示。通常有掃描表示、構(gòu)造實體幾何表示和特征表示三種。 (a)掃描表示?；谝粋€基體普通是一個封鎖的平面輪廓沿某一途徑運動而產(chǎn)生形體。 掃描是生成三維形體的有效方法 用掃描變換產(chǎn)生的形體能夠出現(xiàn)維數(shù)不一致的問題。 掃描方法不能直接獲取形體的邊境信息，表示形體的覆蓋域非常有限。掃描方向基面回轉(zhuǎn)軸基面基面基面（a）

5、（b）（c）（d）圖3.2.5 生成掃描形體的例子（a）（b）（c）（d）圖3.2.6 生成掃描體時維數(shù)不 一致的情況(b)構(gòu)造實體幾何表示(CSG).經(jīng)過對體素定義運算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運算為變換或正那么集合運算并、交、差。CSG表示可以看成是一棵有序的二叉樹。其終端節(jié)點或是體素、或是形體變換參數(shù)。非終端結(jié)點或是正那么的集合運算，或是變換平移和/或旋轉(zhuǎn)操作，這種運算或變換只對其緊接著的子結(jié)點子形體起作用。差（-）差（-）212平移xxx=體素圖3.2.7 CSG表示 CSG樹是無二義性的，但不是獨一的. CSG表示的優(yōu)點： 數(shù)據(jù)構(gòu)

6、造比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易； CSG表示可方便地轉(zhuǎn)換成邊境Brep表示； CSG方法表示的形體的外形，比較容易修正。 CSG表示的缺陷： 對形體的表示受體素的種類和對體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。 對形體的部分操作不易實現(xiàn)，例如，不能對根本體素的交線倒圓角； 由于形體的邊境幾何元素點、邊、面是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需求較長的時間。 (c)特征表示 從運用層來定義形體，因此可以較好的表達(dá)設(shè)計者的意圖。從功能上可分為外形、精度、資料和技術(shù)特征。特征是面向運用、面向用戶的。特征模型的表示依然要經(jīng)過傳統(tǒng)的幾何

7、外型系統(tǒng)來實現(xiàn)。不同的運用領(lǐng)域，具有不同的運用特征。在幾何外型系統(tǒng)中，根據(jù)特征的參數(shù)我們并不能直接得到特征的幾何元素信息，而在對特征及在特征之間進(jìn)展操作時需求這些信息。特征方法表示形體的覆蓋域受限于特征的種類。特征造型器幾何造型器特征模型幾何模型用戶應(yīng)用系統(tǒng)圖3.2.8 基于特征的造型系統(tǒng)WLHHRHR（a）方塊（b）圓柱（c）圓錐圖3.2.9 特征形狀表示 構(gòu)造表示的特點： 構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有限等缺陷， 但是，便于用戶輸入形體，在CAD/CAM系統(tǒng)中，通常作為輔助表示方法。 3邊境表示BR表示或BRep表示 按照體面環(huán)邊點的層次，詳細(xì)記錄了構(gòu)成形體的一

8、切幾何元素的幾何信息及其相互銜接的拓?fù)潢P(guān)系。 邊境表示的一個重要特點是在該表示法中，描畫形體的信息包括幾何信息Geometry和拓?fù)湫畔opology兩個方面。 拓?fù)湫畔⒚璁嬓误w上的頂點、邊、面的銜接關(guān)系，拓?fù)湫畔?gòu)成物體邊境表示的“骨架。 形體的幾何信息猶如附著在“骨架上的肌肉。U圖3.2.10 邊界表示 Brep表示的優(yōu)點是： 表示形體的點、邊、面等幾何元素是顯式表示的，使得繪制Brep表示的形體的速度較快，而且比較容易確定幾何元素間的銜接關(guān)系； 容易支持對物體的各種部分操作，比如進(jìn)展倒角。 便于在數(shù)據(jù)構(gòu)造上附加各種非幾何信息，如精度、外表粗糙度等。 Brep表示的缺陷是： 數(shù)據(jù)構(gòu)造復(fù)雜

9、，需求大量的存儲空間，維護(hù)內(nèi)部數(shù)據(jù)構(gòu)造的程序比較復(fù)雜； Brep表示不一定對應(yīng)一個有效形體，通常運用歐拉操作來保證Brep表示形體的有效性、正那么性等。 Brep表示覆蓋域大，原那么上能表示一切的形體，而且易于支持形體的特征表示等，Brep表示已成為當(dāng)前CAD/CAM系統(tǒng)的主要表示方法。3.2.3 形體的邊境表示模型 3.2.3.1 邊境表示的根本實體邊境表示的根本實體 邊境模型表達(dá)形體的根本拓?fù)鋵嶓w包括：邊境模型表達(dá)形體的根本拓?fù)鋵嶓w包括： 1. 頂點頂點 2. 邊。邊有方向，它由起始頂點和終止邊。邊有方向，它由起始頂點和終止頂點來界定。邊的外形頂點來界定。邊的外形Curve由邊的由邊的幾何

10、信息來表示，可以是直線或曲線，幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點或型值點來描曲線邊可用一系列控制點或型值點來描畫，也可用顯式、隱式或參數(shù)方程來描畫，也可用顯式、隱式或參數(shù)方程來描畫。畫。3. 環(huán)。環(huán)Loop是有序、有向邊Edge組成的封鎖邊境。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時針方向排序，內(nèi)環(huán)邊通常按順時針方向排序。4.面。面Face由一個外環(huán)和假設(shè)干個內(nèi)環(huán)可以沒有內(nèi)環(huán)來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。假設(shè)一個面的外法矢向外，稱為正向面；反之，稱為反向面。 面的外形可以是平面或曲面。平面可用平面方程來描畫，曲面可用控制多邊形或型值點來描畫，也可用曲面方程隱式、顯式或參數(shù)方式來

11、描畫。對于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來表示環(huán)，集合運算中對面的分割也可在二維參數(shù)域上進(jìn)展。 5.體。體Body是面的并集。3.2.3.2 邊境表示的數(shù)據(jù)構(gòu)造 翼邊數(shù)據(jù)構(gòu)造：在1972年，由美國斯坦福大學(xué)Baumgart作為多面體的表示方式提出。 它用指針記錄了每一邊的兩個鄰面即左外環(huán)和右外環(huán)、兩個頂點、兩側(cè)各自相鄰的兩個鄰邊即左上邊、左下邊、右上邊和右下邊，用這一數(shù)據(jù)構(gòu)造表示多面體模型是完備的，但它不能表示帶有準(zhǔn)確曲面邊境的實體。左下邊右下邊 右上邊左上邊邊左外環(huán)右外環(huán)圖3.2.11 翼邊數(shù)據(jù)結(jié)構(gòu) 輻射邊：為了表示非正那么形體，1986年，Weiler提出

12、了輻射邊Radial Edge數(shù)據(jù)構(gòu)造。 輻射邊構(gòu)造的形體模型由幾何信息和拓?fù)湫畔刹糠纸M成。 幾何信息有面face、環(huán)loop、邊edge和點vertex 拓?fù)湫畔⒂心Ｐ蚼odel、區(qū)域region、外殼shell、面援用face use、環(huán)援用loop use、邊援用edge use和點援用vertex use。 點是三維空間的一個位置 邊可以是直線邊或曲線邊，邊的端點可以重合。 環(huán)是由首尾相接的一些邊組成，而且最后一條邊的終點與第一條邊的起點重合；環(huán)也可以是一個孤立點。外殼是一些點、邊、環(huán)、面的集合； 外殼是一些點、邊、環(huán)、面的集合。 區(qū)域由一組外殼組成。 模型由區(qū)域組成。modelre

13、gionface useloop useedge usevertex usefaceloopedgevertex圖3.2.12 輻射邊數(shù)據(jù)結(jié)構(gòu)shellgeometrytopology剖切平面中心線中心線實體圖3.2.13 一個用輻射邊結(jié)構(gòu)表示的非正則形體模型清華大學(xué)國家CAD工程中心開發(fā)的幾何外型系統(tǒng)GEMS5.0中，采用的數(shù)據(jù)構(gòu)造如圖體組特征表示單體(零件)面組面線框環(huán)環(huán)邊邊頂點曲 面曲 線點實體幾何數(shù)據(jù)實體拓?fù)鋽?shù)據(jù)參數(shù)域曲線 該數(shù)據(jù)構(gòu)造基于線框、外表、實體和特征一致表示，且具有以下特點： 1采用自頂向下的設(shè)計思想。在形體的表示上，遵照了從大到小，分解表示的原那么； 2支持非流形形體的表示

14、； 3實體拓?fù)鋽?shù)據(jù)與幾何數(shù)據(jù)雙鏈表銜接，存放緊湊； 4可以支持特征外型。3.2.3.3 歐拉操作 對于恣意的簡單多面體，其面(f)、邊(e)、頂點(v)的數(shù)目滿足 歐拉公式 v - e + f = 2 對于恣意的正那么形體，引入形體的其它幾個參數(shù)：形體一切面上的內(nèi)孔總數(shù)(r)、穿透形體的孔洞數(shù)(h)和形體非連通部分總數(shù)(s)，那么形體滿足公式： v - e + f = 2(s-h) + r 修正正程中保證各幾何元素的數(shù)目堅持這個關(guān)系式不變，這一套操作就是歐拉操作。 最為常用的幾種歐拉操作有： (1)mvsf(v,f)，生成含有一個點的面，并且構(gòu)成一個新的體。 (2)kvsf，刪除一個體，該體僅

15、含有一個點的面。 (3)mev(v1,v2,e)，生成一個新的點v2，銜接該點到已有的點v1，構(gòu)成一條新的邊。 (4)kev(e,v)，刪除一條邊e和該邊的一個端點v。 (5)mef(v1,v2,f1,f2,e)，銜接面f1上的兩個點v1、v2，生成一條新的邊e，并產(chǎn)生一個新的面。(6)kef(e)，刪除一條邊e和該邊的一個鄰面f。(7)kemr(e)，刪除一條邊e，生成該邊某一鄰面上的一新的內(nèi)環(huán)。(8)mekr(v1,v2,e)，銜接兩個點v1、v2，生成一條新的邊e，并刪除掉v1和v2所在面上的一個內(nèi)環(huán)。(9)kfmrh(f1,f2)，刪除與面f1相接觸的一個面f2，生成面f1上的一個內(nèi)環(huán)

16、，并構(gòu)成體上的一個通孔。(10)mfkrh(f1,f2)，刪除面f1上的一個內(nèi)環(huán)，生成一個新的面f2，由此也刪除了體上的一個通孔。為了方便對形體的修正，還定義了兩個輔助的操作：公共端點。(11)semv(e1,v,e2)，將邊e1分割成兩段，生成一個新的點v和一條新的邊e2。(12)jekv(e1,e2)，合并兩條相鄰的邊e1、e2，刪除它們的公共端點。以上十種歐拉操作和兩個輔助操作，每兩個一組，構(gòu)成了六組互為可逆的操作?？梢宰C明：歐拉操作是有效的，即用歐拉操作對形體操作的結(jié)果在物理上是可實現(xiàn)的；歐拉操作是完備的，即任何形體都可用有限步驟的歐拉操作構(gòu)造出來。3.2.3.4 集合運算 正那么集與

17、正那么集合運算算子 規(guī)定正那么形體是三維歐氏空間中的正那么集合，因此可以將正那么幾何形體描畫如下： 設(shè)G是三維歐氏空間中的一個有界區(qū)域，且GbGiG，其中bG是G的n1維邊境，iG是G的內(nèi)部。G的補空間cG稱為G的外部，此時正那么形體G需滿足： 1bG將iG和cG分為兩個互不連通的子空間； 2bG中的恣意一點可以使iG和bG連通； 3bG中任一點存在切平面，其法矢指向cG子空間 4bG是二維流形。 設(shè)是集合運算算子交、并或差，R3中恣意兩個正那么形體A、B作集合運算：R=AB 運算結(jié)果R仍是R3中的正那么形體，那么稱為正那么集合算子。 正那么并、正那么交、正那么差分別記為*，*、-*。 分類 Tilove對分類問題的定義為：設(shè)S為待分類元素組成的集合，G為一正那么集合，那么S相對于G的成員分類函數(shù)為： C(S,G)=S in G，S out G，S on G 其中，S in G=SiG，S out G=ScG，S on G=SbG， 集合運算算法 包括以下幾部分： (1)求交：參與運算的一個形體的各拓?fù)湓厍蠼唬蠼坏捻樞虿捎玫途S元素向高維元素進(jìn)展。用求交結(jié)果產(chǎn)生的新元素維數(shù)低于參與求交的元素對求交元素進(jìn)展劃分，構(gòu)成一些子元素。 (2)成環(huán)：由求交得到的交線將原形體的面進(jìn)展分割，構(gòu)成一些新的面環(huán)。再加上原形體的懸邊、懸點經(jīng)求交后得到的各子拓?fù)湓兀瑯?gòu)成一拓?fù)湓厣杉?/p>