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

1、3.5形體在計(jì)算機(jī)內(nèi)的表示 幾何外型 形體表示 邊境表示模型3.5.1 引言 計(jì)算機(jī)中表示形體，通常用線框、外表和實(shí)體三種模型。 幾何外型歷史：早期的線框表示 實(shí)體外型與曲面外型70 獨(dú)立開展 到 相互溶合 NURBS 邊境表示正那么形體 對(duì)于任一形體，假設(shè)它是3維歐氏空間中非空、有界的封鎖子集，且其邊境是二維流形即該形體是連通的，我們稱該形體為正那么形體，否那么稱為非正那么形體。 一些非正那么形體的實(shí)例(a)有懸面(b)有懸邊（c）一條邊有兩個(gè)以上 的鄰面（不連通）圖3.2.1 非正則形體實(shí)例 集合運(yùn)算并、交、差是構(gòu)造形體的根本方法。正那么形體經(jīng)過(guò)集合運(yùn)算后，能夠會(huì)產(chǎn)生懸邊、懸面等低于三維的

2、形體。 Requicha在引入正那么形體概念的同時(shí)，還定義了正那么集合運(yùn)算的概念。正那么集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個(gè)正那么形體，即丟棄懸邊、懸面等。集合運(yùn)算舉列 ABabab圖3.2.2 二個(gè)二維圖形的交產(chǎn) 生一個(gè)退化的結(jié)果懸邊ABABC=AB集合論的求交計(jì)算正則集合下的求交運(yùn)算*C=A*B圖3.2.3 集合和正則的交運(yùn)算 為了可以處置非正那么形體，產(chǎn)生了非正那么外型技術(shù)。 九十年代以來(lái)，基于約束的參數(shù)化、變量化外型和支持線框、曲面、實(shí)體一致表示的非正那么形體外型技術(shù)已成為幾何外型技術(shù)的主流。3.5.2 形體表示模型 在實(shí)體模型的表示中，根本上可以分為分解表示、構(gòu)造表示和邊境表示三大類。

3、1、分解表示將形體按某種規(guī)那么分解為小的更易于描畫的部分，每一小部分又可分為更小的部分，這種分解過(guò)程直至每一小部分都可以直接描畫為止。(a)將形體空間細(xì)分為小的立方體單元。這種表示方法的優(yōu)點(diǎn)是簡(jiǎn)單，容易實(shí)現(xiàn)形體的交、并、差計(jì)算，但是占用的存儲(chǔ)量太大，物體的邊境面沒(méi)有顯式的解析表達(dá)式，不便于運(yùn)算。(b)八叉樹法表示形體.首先對(duì)形體定義一個(gè)外接立方體，再把它分解成八個(gè)子立方體，并對(duì)立方體依次編號(hào)為0，1，2，7。假設(shè)子立方體單元曾經(jīng)一致，即為滿該立方體充溢形體或?yàn)榭諞](méi)有形體在其中，那么該子立方體可停頓分解；否那么，需求對(duì)該立方體作進(jìn)一步分解，再一分為八個(gè)子立方體。在八叉樹中，非葉結(jié)點(diǎn)的每個(gè)結(jié)點(diǎn)都有

4、八個(gè)分支。 優(yōu)點(diǎn)主要是：1形體表示的數(shù)據(jù)構(gòu)造簡(jiǎn)單。 2簡(jiǎn)化了形體的集合運(yùn)算。只需同時(shí)遍歷參與集合運(yùn)算的兩形體相應(yīng)的八叉樹，無(wú)需進(jìn)展復(fù)雜的求交運(yùn)算。 3簡(jiǎn)化了隱藏線或面的消除，由于在八叉樹表示中，形體上各元素已按空間位置排成了一定的順序。 4分析算法適宜于并行處置。 八叉樹表示的缺陷：占用的存儲(chǔ)多，只能近似表示形體，以及不易獲取形體的邊境信息等。 012356712337（a）（b）（c）具有子孫的節(jié)點(diǎn)空節(jié)點(diǎn)實(shí)節(jié)點(diǎn)圖3.2.4 用八叉樹表示形體2構(gòu)造表示。通常有掃描表示、構(gòu)造實(shí)體幾何表示和特征表示三種。(a)掃描表示?；谝粋€(gè)基體普通是一個(gè)封鎖的平面輪廓沿某一途徑運(yùn)動(dòng)而產(chǎn)生形體。掃描是生成三維形

5、體的有效方法用掃描變換產(chǎn)生的形體能夠出現(xiàn)維數(shù)不一致的問(wèn)題。掃描方法不能直接獲取形體的邊境信息，表示形體的覆蓋域非常有限。 掃描方向基面回轉(zhuǎn)軸基面基面基面（a）（b）（c）（d）圖3.2.5 生成掃描形體的例子 （a）（b）（c）（d）圖3.2.6 生成掃描體時(shí)維數(shù)不 一致的情況(b)構(gòu)造實(shí)體幾何表示(CSG).經(jīng)過(guò)對(duì)體素定義運(yùn)算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運(yùn)算為變換或正那么集合運(yùn)算并、交、差。CSG表示可以看成是一棵有序的二叉樹。其終端節(jié)點(diǎn)或是體素、或是形體變換參數(shù)。非終端結(jié)點(diǎn)或是正那么的集合運(yùn)算，或是變換平移和/或旋轉(zhuǎn)操作，這種運(yùn)算或變換只

6、對(duì)其緊接著的子結(jié)點(diǎn)子形體起作用。 差（-）差（-）212平移xxx=體素圖3.2.7 CSG表示 CSG樹是無(wú)二義性的，但不是獨(dú)一的. CSG表示的優(yōu)點(diǎn)： 數(shù)據(jù)構(gòu)造比較簡(jiǎn)單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易； CSG表示可方便地轉(zhuǎn)換成邊境Brep表示； CSG方法表示的形體的外形，比較容易修正。 CSG表示的缺陷： 對(duì)形體的表示受體素的種類和對(duì)體素操作的種類的限制，也就是說(shuō)，CSG方法表示形體的覆蓋域有較大的局限性。 對(duì)形體的部分操作不易實(shí)現(xiàn)，例如，不能對(duì)根本體素的交線倒圓角； 由于形體的邊境幾何元素點(diǎn)、邊、面是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需求較長(zhǎng)的時(shí)間。 (c)特征

7、表示從運(yùn)用層來(lái)定義形體，因此可以較好的表達(dá)設(shè)計(jì)者的意圖。從功能上可分為外形、精度、資料和技術(shù)特征。特征是面向運(yùn)用、面向用戶的。特征模型的表示依然要經(jīng)過(guò)傳統(tǒng)的幾何外型系統(tǒng)來(lái)實(shí)現(xiàn)。不同的運(yùn)用領(lǐng)域，具有不同的運(yùn)用特征。在幾何外型系統(tǒng)中，根據(jù)特征的參數(shù)我們并不能直接得到特征的幾何元素信息，而在對(duì)特征及在特征之間進(jìn)展操作時(shí)需求這些信息。特征方法表示形體的覆蓋域受限于特征的種類。 特征造型器幾何造型器特征模型幾何模型用戶應(yīng)用系統(tǒng)圖3.2.8 基于特征的造型系統(tǒng)WLHHRHR（a）方塊（b）圓柱（c）圓錐圖3.2.9 特征形狀表示 構(gòu)造表示的特點(diǎn)： 構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有

8、限等缺陷， 但是，便于用戶輸入形體，在CAD/CAM系統(tǒng)中，通常作為輔助表示方法。3邊境表示BR表示或BRep表示按照體面環(huán)邊點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的一切幾何元素的幾何信息及其相互銜接的拓?fù)潢P(guān)系。邊境表示的一個(gè)重要特點(diǎn)是在該表示法中，描畫形體的信息包括幾何信息Geometry和拓?fù)湫畔opology兩個(gè)方面。拓?fù)湫畔⒚璁嬓误w上的頂點(diǎn)、邊、面的銜接關(guān)系，拓?fù)湫畔?gòu)成物體邊境表示的“骨架。形體的幾何信息猶如附著在“骨架上的肌肉。 U圖3.2.10 邊界表示 Brep表示的優(yōu)點(diǎn)是： 表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的，使得繪制Brep表示的形體的速度較快，而且比較容易確定幾何元素間的

9、銜接關(guān)系； 容易支持對(duì)物體的各種部分操作，比如進(jìn)展倒角。 便于在數(shù)據(jù)構(gòu)造上附加各種非幾何信息，如精度、外表粗糙度等。 Brep表示的缺陷是： 數(shù)據(jù)構(gòu)造復(fù)雜，需求大量的存儲(chǔ)空間，維護(hù)內(nèi)部數(shù)據(jù)構(gòu)造的程序比較復(fù)雜； Brep表示不一定對(duì)應(yīng)一個(gè)有效形體，通常運(yùn)用歐拉操作來(lái)保證Brep表示形體的有效性、正那么性等。 Brep表示覆蓋域大，原那么上能表示一切的形體，而且易于支持形體的特征表示等，Brep表示已成為當(dāng)前CAD/CAM系統(tǒng)的主要表示方法。 CSG 與邊境表示成為兩大主流方法 80 ACM Solid modeling 歐洲CSG會(huì)議 邊境表示 一統(tǒng)天下 歐洲CSG會(huì)議 亞州GMP 3.5.3

10、形體的邊境表示模型3.5.3.1 3.5.3.1 邊境表示的根本實(shí)體邊境表示的根本實(shí)體邊境模型表達(dá)形體的根本拓?fù)鋵?shí)體包括：邊境模型表達(dá)形體的根本拓?fù)鋵?shí)體包括：1. 1. 頂點(diǎn)頂點(diǎn)2. 2. 邊。邊有方向，它由起始頂點(diǎn)和終止頂邊。邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)來(lái)界定。邊的外形點(diǎn)來(lái)界定。邊的外形CurveCurve由邊的幾由邊的幾何信息來(lái)表示，可以是直線或曲線，曲何信息來(lái)表示，可以是直線或曲線，曲線邊可用一系列控制點(diǎn)或型值點(diǎn)來(lái)描畫，線邊可用一系列控制點(diǎn)或型值點(diǎn)來(lái)描畫，也可用顯式、隱式或參數(shù)方程來(lái)描畫。也可用顯式、隱式或參數(shù)方程來(lái)描畫。3. 環(huán)。環(huán)Loop是有序、有向邊Edge組成的封鎖邊境。環(huán)有

11、方向、內(nèi)外之分，外環(huán)邊通常按逆時(shí)針?lè)较蚺判?，?nèi)環(huán)邊通常按順時(shí)針?lè)较蚺判颉?.面。面Face由一個(gè)外環(huán)和假設(shè)干個(gè)內(nèi)環(huán)可以沒(méi)有內(nèi)環(huán)來(lái)表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。假設(shè)一個(gè)面的外法矢向外，稱為正向面；反之，稱為反向面。 面的外形可以是平面或曲面。平面可用平面方程來(lái)描畫，曲面可用控制多邊形或型值點(diǎn)來(lái)描畫，也可用曲面方程隱式、顯式或參數(shù)方式來(lái)描畫。對(duì)于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來(lái)表示環(huán)，集合運(yùn)算中對(duì)面的分割也可在二維參數(shù)域上進(jìn)展。 5.體。體Body是面的并集。3.5.3.2 邊境表示的數(shù)據(jù)構(gòu)造 翼邊數(shù)據(jù)構(gòu)造：在1972年，由美國(guó)斯坦福大學(xué)Baumgart作為多面體的表

12、示方式提出。 它用指針記錄了每一邊的兩個(gè)鄰面即左外環(huán)和右外環(huán)、兩個(gè)頂點(diǎn)、兩側(cè)各自相鄰的兩個(gè)鄰邊即左上邊、左下邊、右上邊和右下邊，用這一數(shù)據(jù)構(gòu)造表示多面體模型是完備的，但它不能表示帶有準(zhǔn)確曲面邊境的實(shí)體。 左下邊右下邊 右上邊左上邊邊左外環(huán)右外環(huán)圖3.2.11 翼邊數(shù)據(jù)結(jié)構(gòu) 輻射邊：為了表示非正那么形體，1986年，Weiler提出了輻射邊Radial Edge數(shù)據(jù)構(gòu)造。 輻射邊構(gòu)造的形體模型由幾何信息和拓?fù)湫畔刹糠纸M成。 幾何信息有面face、環(huán)loop、邊edge和點(diǎn)vertex 拓?fù)湫畔⒂心Ｐ蚼odel、區(qū)域region、外殼shell、面援用face use、環(huán)援用loop use、邊

13、援用edge use和點(diǎn)援用vertex use。 點(diǎn)是三維空間的一個(gè)位置 邊可以是直線邊或曲線邊，邊的端點(diǎn)可以重合。 環(huán)是由首尾相接的一些邊組成，而且最后一條邊的終點(diǎn)與第一條邊的起點(diǎn)重合；環(huán)也可以是一個(gè)孤立點(diǎn)。外殼是一些點(diǎn)、邊、環(huán)、面的集合； 外殼是一些點(diǎn)、邊、環(huán)、面的集合。 區(qū)域由一組外殼組成。 模型由區(qū)域組成。 modelregionface useloop useedge usevertex usefaceloopedgevertex圖3.2.12 輻射邊數(shù)據(jù)結(jié)構(gòu)shellgeometrytopology剖切平面中心線中心線實(shí)體圖3.2.13 一個(gè)用輻射邊結(jié)構(gòu)表示的非正則形體模型清華大

14、學(xué)開發(fā)的幾何外型系統(tǒng)GEMS5.0中，采用的數(shù)據(jù)構(gòu)造如圖體組特征表示單體(零件)面組面線框環(huán)環(huán)邊邊頂點(diǎn)曲 面曲 線點(diǎn)實(shí)體幾何數(shù)據(jù)實(shí)體拓?fù)鋽?shù)據(jù)參數(shù)域曲線 歐拉操作 選讀 集合運(yùn)算 選讀3.5.3.3 歐拉操作 對(duì)于恣意的簡(jiǎn)單多面體，其面(f)、邊(e)、頂點(diǎn)(v)的數(shù)目滿足 歐拉公式 v - e + f = 2 對(duì)于恣意的正那么形體，引入形體的其它幾個(gè)參數(shù)：形體一切面上的內(nèi)孔總數(shù)(r)、穿透形體的孔洞數(shù)(h)和形體非連通部分總數(shù)(s)，那么形體滿足公式： v - e + f = 2(s-h) + r 修正正程中保證各幾何元素的數(shù)目堅(jiān)持這個(gè)關(guān)系式不變，這一套操作就是歐拉操作。 最為常用的幾種歐拉操

15、作有： (1)mvsf(v,f)，生成含有一個(gè)點(diǎn)的面，并且構(gòu)成一個(gè)新的體。 (2)kvsf，刪除一個(gè)體，該體僅含有一個(gè)點(diǎn)的面。 (3)mev(v1,v2,e)，生成一個(gè)新的點(diǎn)v2，銜接該點(diǎn)到已有的點(diǎn)v1，構(gòu)成一條新的邊。 (4)kev(e,v)，刪除一條邊e和該邊的一個(gè)端點(diǎn)v。 (5)mef(v1,v2,f1,f2,e)，銜接面f1上的兩個(gè)點(diǎn)v1、v2，生成一條新的邊e，并產(chǎn)生一個(gè)新的面。(6)kef(e)，刪除一條邊e和該邊的一個(gè)鄰面f。(7)kemr(e)，刪除一條邊e，生成該邊某一鄰面上的一新的內(nèi)環(huán)。(8)mekr(v1,v2,e)，銜接兩個(gè)點(diǎn)v1、v2，生成一條新的邊e，并刪除掉v1和

16、v2所在面上的一個(gè)內(nèi)環(huán)。(9)kfmrh(f1,f2)，刪除與面f1相接觸的一個(gè)面f2，生成面f1上的一個(gè)內(nèi)環(huán)，并構(gòu)成體上的一個(gè)通孔。(10)mfkrh(f1,f2)，刪除面f1上的一個(gè)內(nèi)環(huán)，生成一個(gè)新的面f2，由此也刪除了體上的一個(gè)通孔。為了方便對(duì)形體的修正，還定義了兩個(gè)輔助的操作：公共端點(diǎn)。(11)semv(e1,v,e2)，將邊e1分割成兩段，生成一個(gè)新的點(diǎn)v和一條新的邊e2。(12)jekv(e1,e2)，合并兩條相鄰的邊e1、e2，刪除它們的公共端點(diǎn)。以上十種歐拉操作和兩個(gè)輔助操作，每?jī)蓚€(gè)一組，構(gòu)成了六組互為可逆的操作?？梢宰C明：歐拉操作是有效的，即用歐拉操作對(duì)形體操作的結(jié)果在物理上

17、是可實(shí)現(xiàn)的；歐拉操作是完備的，即任何形體都可用有限步驟的歐拉操作構(gòu)造出來(lái)。3.5.3.4 集合運(yùn)算 正那么集與正那么集合運(yùn)算算子 規(guī)定正那么形體是三維歐氏空間中的正那么集合，因此可以將正那么幾何形體描畫如下： 設(shè)G是三維歐氏空間中的一個(gè)有界區(qū)域，且GbGiG，其中bG是G的n1維邊境，iG是G的內(nèi)部。G的補(bǔ)空間cG稱為G的外部，此時(shí)正那么形體G需滿足： 1bG將iG和cG分為兩個(gè)互不連通的子空間； 2bG中的恣意一點(diǎn)可以使iG和bG連通； 3bG中任一點(diǎn)存在切平面，其法矢指向cG子空間 4bG是二維流形。 設(shè)是集合運(yùn)算算子交、并或差，R3中恣意兩個(gè)正那么形體A、B作集合運(yùn)算：R=AB 運(yùn)算結(jié)果

18、R仍是R3中的正那么形體，那么稱為正那么集合算子。 正那么并、正那么交、正那么差分別記為*，*、-*。 分類 Tilove對(duì)分類問(wèn)題的定義為：設(shè)S為待分類元素組成的集合，G為一正那么集合，那么S相對(duì)于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， 集合運(yùn)算算法 包括以下幾部分： (1)求交：參與運(yùn)算的一個(gè)形體的各拓?fù)湓厍蠼?，求交的順序采用低維元素向高維元素進(jìn)展。用求交結(jié)果產(chǎn)生的新元素維數(shù)低于參與求交的元素對(duì)求交元素進(jìn)展劃分，構(gòu)成一些子元素。 (2)成環(huán)：由求交得到的交線將原形體的面進(jìn)展

19、分割，構(gòu)成一些新的面環(huán)。再加上原形體的懸邊、懸點(diǎn)經(jīng)求交后得到的各子拓?fù)湓兀瑯?gòu)成一拓?fù)湓厣杉?3)分類：對(duì)構(gòu)成的拓?fù)湓厣杉械拿恳煌負(fù)湓?，取其上的一個(gè)代表點(diǎn)，根據(jù)點(diǎn)/體分類的原那么，決議該點(diǎn)相對(duì)于另一形體的位置關(guān)系，同時(shí)思索該點(diǎn)代表的拓?fù)湓氐念愋图雌渚S數(shù)，來(lái)決議該拓?fù)湓叵鄬?duì)于另一形體的分類關(guān)系。(4)取舍：根據(jù)拓?fù)湓氐念愋图捌湎鄬?duì)另一形體的分類關(guān)系，按照集合運(yùn)算的運(yùn)算符要求，決議拓?fù)湓厥潜９苓€是舍去；保管的拓?fù)湓貥?gòu)成一個(gè)保管集。(5)合并：對(duì)保管集中同類型可合并的拓?fù)湓剡M(jìn)展合并，包括面環(huán)的合并和邊的合并。(6)拼接：以拓?fù)湓氐墓蚕磉吘匙鳛槠溷暯訕?biāo)志，按照從高維到低維的

20、順序，搜集分類后保管的拓?fù)湓?，?gòu)成結(jié)果形體的邊境表示數(shù)據(jù)構(gòu)造。3.6歸類求交 幾何外型中，通常利用集合運(yùn)算并、交、差運(yùn)算實(shí)現(xiàn)復(fù)雜形體的構(gòu)造。集合運(yùn)算需求大量的求交運(yùn)算。 如何提高求交的適用性、穩(wěn)定性、速度、精度等，對(duì)幾何外型系統(tǒng)至關(guān)重要。 歷史上的觀念變化:簡(jiǎn)單體素的準(zhǔn)確求交， NURBS一致求交 - 歸類求交3.6.1 求交分類簡(jiǎn)介 多面體模型 這種模型的求交計(jì)算主要是線段和平面的求交，求交問(wèn)題的處理相對(duì)簡(jiǎn)單。 多面體模型的缺陷是明顯的。它只能近似表示形體，同時(shí)，復(fù)雜形體外表的離散會(huì)帶來(lái)宏大的數(shù)據(jù)量。 CSG模型 在這種模型中，形體經(jīng)過(guò)根本體素的組合來(lái)實(shí)現(xiàn)。二次曲面的求交是這些外型系統(tǒng)中必

21、不可少的。 當(dāng)前的幾何外型系統(tǒng)，大多采用準(zhǔn)確的邊境表示模型。 在這種表示法中，形體的邊境元素和某類幾何元素相對(duì)應(yīng)，它們可以是直線、圓圓弧、二次曲線、Bezier曲線、B樣條曲線等，也可以是平面、球面、二次曲面、Bezier曲面、B樣條曲面等，求交情況非常復(fù)雜。 二次曲面與各種自在曲面并存的混合表示模型的采用，導(dǎo)致了歸類求交思想的產(chǎn)生。 “無(wú)處不在的求交：GEMS實(shí)例！ 實(shí)體建模步驟分析： 草圖 拉伸、填“體、面、環(huán)、點(diǎn)構(gòu)造 打孔，直徑為20cm: 圓柱與立方體的一切面求交線，成環(huán)、重填“面子環(huán)點(diǎn)構(gòu)造 打第二個(gè)孔，直徑為18cm: 圓柱與立方體的一切面、及第一個(gè)圓柱面求交線，成環(huán)、重填“面子環(huán)點(diǎn)

22、構(gòu)造3.6.2 歸類求交戰(zhàn)略 幾何外型系統(tǒng)中，用到的幾何元素：(25種) 點(diǎn)：3D點(diǎn)。 線：3D直線段、二次曲線(包括圓弧和整圓、橢圓弧和橢圓、拋物線段、雙曲線段)、 Bezier曲線 (有理和非有理)、B樣條曲線、NURBS曲線。 面：平面、二次曲面(包括球面、圓柱面、圓錐/臺(tái)面、雙曲面、拋物面、橢球面和橢圓柱面)、Bezier曲面 (有理和非有理)、B樣條曲面、NURBS曲面。 將幾何元素進(jìn)展歸類，利用同一類元素之間的共性來(lái)研討求交算法。同時(shí)對(duì)每一類元素，在詳細(xì)求交算法中要思索它們的特性，以提高算法的效率，發(fā)揚(yáng)混合表示方法的優(yōu)勢(shì)。 求交方法可分為：點(diǎn)點(diǎn)、點(diǎn)線、點(diǎn)面、線線、線面六種。 清華大

23、學(xué)的GEMS5.0系統(tǒng)采用 點(diǎn)、直線、平面、二次曲線等簡(jiǎn)單的幾何元素之間的求交 直線、平面、二次曲線等簡(jiǎn)單的幾何元素與二次曲面之間的求交 三維點(diǎn)與二次曲線/曲面之間的求交 三維點(diǎn)與自在曲線、曲面之間的求交 二次曲面與二次曲面之間的求交 直線自在曲線/自在曲面的求交 平面自在曲線/自在曲面的求交 自在曲線自在曲線的求交 自在曲線自在曲面的求交 二次曲線自在曲線的求交 二次曲線自在曲面的求交 自在曲面自在曲面的求交 二次曲面自在曲線的求交 二次曲面自在曲面的求交3.6.3 根本的求交算法 曲線曲面求交的根本方法主要有: 代數(shù)方法 幾何方法 離散方法 跟蹤方法1代數(shù)方法利用代數(shù)運(yùn)算，特別是求解代數(shù)方

24、程的方法求出曲面的交線。根據(jù)參與求交的兩曲面的表示方式的不同，可以把求交分為三種情況。 隱式表示和參數(shù)表示的曲面求交，經(jīng)過(guò)把參數(shù)方程代入隱式方程的方法，可以將交線表示為g(u,v)=0的方式。此時(shí)得到的交線方程是平面代數(shù)曲線方程，可根據(jù)平面代數(shù)曲線實(shí)際的方法求解交線。 兩個(gè)曲面都是參數(shù)表示的情形，只需求將其中之一隱式化，然后用前面的方法求解。而參數(shù)多項(xiàng)式或有理多項(xiàng)式曲面的隱式化經(jīng)過(guò)消元來(lái)實(shí)現(xiàn)。 兩個(gè)曲面都是隱式曲面。一種方法是將其中一個(gè)曲面參數(shù)化，然后用第一種情況來(lái)求解。但是，普通情況下這種參數(shù)化很困難，對(duì)于某些情況可以采用另外的方法計(jì)算參數(shù)化的曲面。 代數(shù)法的弱點(diǎn)是對(duì)誤差很敏感 這是由于代數(shù)

25、法經(jīng)常需求判別某些量能否大于零、等于零或小于零，而在計(jì)算機(jī)中的浮點(diǎn)數(shù)近似表示的誤差經(jīng)常會(huì)使這種判別出現(xiàn)錯(cuò)誤。 代數(shù)法實(shí)例： 園與橢圓求交，化為求解4次方程，有公式解。 園與圓環(huán)求交，化為求解8次方程，迭代求解。 8次方程到達(dá)求解，不穩(wěn)定。2幾何方法利用幾何的方法，對(duì)參與求交的曲面的外形大小、相互位置以及方向等進(jìn)展計(jì)算和判別，識(shí)別出交線的外形和類型，從而可準(zhǔn)確求出交線。幾何求交順應(yīng)性不是很廣，普通僅用于平面以及二次曲面等簡(jiǎn)單曲面的求交 對(duì)于一些交線退化或相切的情形，交線往往是點(diǎn)、直線或圓錐曲線，用幾何方法求交可以更加迅速和可靠。 幾何法實(shí)例：平面與圓柱求交 1. 平面、圓柱參數(shù)的合法性檢查 2.

26、 平面變換到圓柱的部分坐標(biāo)系 3. 幾何求交： 假設(shè)平面與圓柱平行，不交或交于兩條直線 假設(shè)平面與圓柱垂直，不交或交于一個(gè)圓 否那么，交于橢圓或橢圓弧 先求出平面與無(wú)限長(zhǎng)圓柱交得的橢圓 (在圓柱的部分坐標(biāo)系下) 根據(jù)橢圓在長(zhǎng)軸上的兩點(diǎn)與圓柱的 關(guān)系，確定交于點(diǎn)、橢圓、橢圓弧等3離散方法離散方法求交是利用分割的方法，將曲面不斷離散成較小的曲面片，直到每一子曲面片均可用比較簡(jiǎn)單的面片，然后用這些簡(jiǎn)單面片求交得一系列交線段，銜接這些交線段即得到準(zhǔn)確交線的近似結(jié)果。 離散求交普通包括下面的過(guò)程：用包圍盒作分別性檢查排除無(wú)交區(qū)域；根據(jù)平坦性檢查判別能否終止離散過(guò)程；銜接求出的交線段作為求交結(jié)果。 由于B

27、ezier曲面，B樣條曲面具有離散性質(zhì)，使得它們最適宜于離散法求交。 缺陷： 離散法求出的交線逼近精度不高。假設(shè)要求的精度較高，需求添加離散層數(shù)。這將大大添加了數(shù)據(jù)儲(chǔ)存量和計(jì)算量。 處于不同離散層數(shù)的相鄰子曲面片，由它們產(chǎn)生的交線段能夠會(huì)出現(xiàn)裂痕。 高度估計(jì)問(wèn)題 H4跟蹤方法經(jīng)過(guò)先求出初始交點(diǎn)，然后從知的初始交點(diǎn)出發(fā)，相繼跟蹤計(jì)算出下一交點(diǎn)，從而求出整條交線的方法。跟蹤法的本質(zhì)是構(gòu)造交線滿足的微分方程組，先求出滿足方程組的某個(gè)某個(gè)初值解，經(jīng)過(guò)數(shù)值求解微分方程組的方法來(lái)計(jì)算整個(gè)交線。 跟蹤方法在計(jì)算相繼交點(diǎn)的時(shí)候，利用了曲面的部分微分性質(zhì)，普通采用數(shù)值迭代的方法求解，使得計(jì)算效率較高。 跟蹤法求

28、交中思索的主要問(wèn)題包括： 如何求出初始交點(diǎn)并保證每一交線分支都有初始交點(diǎn)被求出； 如何計(jì)算奇特情況下的跟蹤方向以及合理選取跟蹤的前提高長(zhǎng)； 如何處置相切的情況。 跟蹤法實(shí)例：MAF方法 曲線曲線求交 近似交點(diǎn)， 切線求交， 投影MAF與Newton法的比較 Newton法MAF與Newton法的比較 MAF法 假設(shè) 為初始交點(diǎn)， 為兩切線的交點(diǎn)；由于在曲線 在 的切線上，有 于是 由此得到新交點(diǎn) ，如此反復(fù)迭代。)(0tPQ)(tPQ)(0tPttPtPQ)()(00)()()(000tPtPtPQt)(0ttP3.7 實(shí)體外型系統(tǒng)簡(jiǎn)介 在早期開發(fā)的實(shí)體外型系統(tǒng)中，值得提及的是劍橋大學(xué)的BUI

29、LD-1系統(tǒng)。 該研討小組的一部分人組建了Shape Data公司，并開發(fā)出實(shí)體外型系統(tǒng)Romulus，Romulus孕育了最著名的兩個(gè)實(shí)體外型系統(tǒng)開發(fā)環(huán)境：Parasolid和ACIS。 3.7.1 Parasolid系統(tǒng)：Solidworks 3.7.2 ACIS系統(tǒng):Autodesk,Solidedge 3.7.1.1 Parasolid的主要功能 Parasolid有較強(qiáng)的外型功能，但是只能支持正那么實(shí)體外型。主要功能包括： 1Parasolid采用自在曲面和解析曲面的混合表示，共提供了10種規(guī)范的曲面類型和7種規(guī)范的曲線類型，并且是完選集成的。 2Parasolid可用簡(jiǎn)單的方法生成

30、復(fù)雜的實(shí)體，實(shí)體之間可有多種方式的操作。 3.用戶可用本人了解的工程特征進(jìn)展設(shè)計(jì) 4.可以提供非拓?fù)浜头菐缀螖?shù)據(jù)，稱為屬性 屬性包括系統(tǒng)定義的屬性和用戶定義的屬性兩種，且依靠于模型實(shí)體Entities。5.支持部分操作。包括：改動(dòng)面幾何、變換面幾何、使面成錐形、擺動(dòng)面、掃描面及刪除面。提供了多半徑、變半徑的過(guò)渡功能。3.7.1.2 Parasolid的模型構(gòu)造 模型實(shí)體包括三種： 拓?fù)洹缀魏拖嚓P(guān)數(shù)據(jù)世界裝配件實(shí)例體殼面環(huán)翼邊頂點(diǎn)拓?fù)渥儞Q曲面曲線點(diǎn)構(gòu)造幾何幾何相關(guān)數(shù)據(jù)特征表屬性圖3.4.1 核心模型的實(shí)體 1拓?fù)鋵?shí)體 1體Body：Parasolid模型通常包括一個(gè)或多個(gè)體Bodies 2殼S

31、hell：殼是實(shí)體Solid和空氣之間封鎖的邊境 3面Face、邊Edge和頂點(diǎn)Vetex 4翼Fin：翼Fins表示一條邊的一側(cè)每一條邊有一個(gè)左翼和一個(gè)右翼 5環(huán)Loop：由一個(gè)面上封鎖的翼組成。 7裝配件Assembly和實(shí)例Instance：一個(gè)裝配件是一個(gè)對(duì)其它裝配件或體的指針的集合。每一個(gè)指針被稱為一個(gè)實(shí)例。 8世界World：世界是一個(gè)獨(dú)特的實(shí)體Entity，它包含模型中的一切的體Bodies和裝配件Assemblies。2幾何實(shí)體Entities點(diǎn)。主要依靠于頂點(diǎn)，它們也依靠于體和裝配件作為構(gòu)造幾何。曲線。主要依靠于面，但也依靠于體和裝配件作為構(gòu)造幾何。曲面。主要依靠于模型的邊或

32、翼，但也依靠于體和裝配件作為構(gòu)造幾何。變換。變換表示幾何操作：平移、修剪等，主要依靠于實(shí)例。3相關(guān)的數(shù)據(jù)實(shí)體1特征feature：是實(shí)體的集合，依靠于體和裝配件。2表List：提供了構(gòu)造化數(shù)據(jù)的方法，它們普通獨(dú)立運(yùn)用，也可依靠于體和裝配件。表有三種：整數(shù)表Integer、實(shí)數(shù)表Real和標(biāo)志表Tag。3屬性Attribute：是用于附著信息到實(shí)體的數(shù)據(jù)構(gòu)造。3.7.1.3 Parasolid的界面 Parasolid有兩個(gè)界面。 一個(gè)在外型器頂部， 稱 為 中 心 界 面KI，經(jīng)過(guò)KI，用戶可以外型、操作對(duì)象和控制外型器。 另一個(gè)在外型器下部，它包括三個(gè)部分：Frustrum、GOGraphi

33、cs Output和FGForeign Geometry。核心界面（KI）PARASOLOD虛擬存儲(chǔ)分配模式文件日志文件轉(zhuǎn)換文件快照文件返回文件FrustrumGOFG圖形輸出用戶幾何系統(tǒng)調(diào)用程序圖3.4.2 Parasolid界面 Frustrum：Frustrum是用戶寫的函數(shù)集，當(dāng)數(shù)據(jù)被存儲(chǔ)、提取，或進(jìn)展內(nèi)存分配時(shí)，它們被中心調(diào)用。 圖形輸出GO：圖形輸出GO函數(shù)也是被用戶寫的。從這些函數(shù)輸出的通是要求中心Kernel繪圖的指令。 外部幾何FG：Parasolid經(jīng)過(guò)FG模塊界面訪問(wèn)用戶定義的曲線、曲面，使得用戶可以運(yùn)用Parasolid外型出的曲線、曲面及規(guī)范的Parasolid曲線、曲面類型。3.7.2 ACIS系統(tǒng) ACIS是由美國(guó)Spatial Technology于1990年初次推出。 ACIS的重要特點(diǎn)是支持線框、曲面、實(shí)體一致表