基于面殼封閉的B-rep模型分解方法

1、計算機(jī)學(xué)報2009年6期基于面殼封閉的B-rep模型分解方法基金項目：國家自然科學(xué)基金 (60573178, 50875092)。馬露杰 黃正東 (華中科技大學(xué)國家CAD支撐軟件工程技術(shù)研究中心，武漢 430074)摘要：三維實體B-rep模型分解是B-rep表示轉(zhuǎn)換為CSG表示的關(guān)鍵問題，并且對深入分析CAD模型的幾何形狀以及其結(jié)構(gòu)關(guān)系具有重要意義。本文提出一種基于面殼封閉的方法分解B-rep模型，該方法采用先分割后縫合的策略。首先識別模型中的所有切割環(huán)，然后通過切割環(huán)將B-rep模型分割成多個面殼，最后利用切割環(huán)在面上的收縮將面殼封閉成實體。經(jīng)過上述三個步驟，可以將具有二次曲面的B-rep

2、模型有效地分解為加體和減體的組合，同時實驗表明該方法具有較高的計算效率。關(guān)鍵詞：B-rep模型；模型分解；切割環(huán)；面殼；收縮中圖法分類號： TP391A B-rep model decomposition approach based on face shell shrinkingLujie Ma, Zhengdong Huang(National CAD Support Software Engineering Research Center, Huazhong University of Science and Technology, Wuhan, 430074)Abstract: Dec

3、omposition of 3D solid models with B-rep format is a crucial problem in transforming the models to CSG format, and it also benefits shape and structure analysis of these models. Here, a face-shell shrinking approach for model decomposition is presented. First, cutting loops of a B-rep model are reco

4、gnized through local shape analysis, then the B-rep model is decomposed into multiple face shells along edges in the cutting loops, and finally, the face shells are transformed into solids by shrinking the cutting loops on the faces. With the above three steps, B-rep models with quadric surfaces can

5、 be effectively decomposed into the composition of positive and negative volumes. At the same time, the experimental results show that this approach is efficient.Keywords: B-rep model; model decomposition; cutting loop; face shell; shrinking1 引言三維CAD軟件的廣泛應(yīng)用使得企業(yè)中存在大量三維實體模型，這些模型是企業(yè)的寶貴財富，對它們的分析和利用一直是研究

6、的熱點(diǎn)，譬如特征識別技術(shù)1，特征轉(zhuǎn)換技術(shù)2和模型檢索技術(shù)3。B-rep和CSG是兩種表達(dá)CAD模型的主要方式，由于CSG表達(dá)具有不唯一性，大部分學(xué)者更傾向于采用B-rep表達(dá)的CAD模型進(jìn)行分析和比較 45。然而，B-rep數(shù)據(jù)結(jié)構(gòu)復(fù)雜且缺乏形體信息，并且模型元素與形體功能及制造方法之間缺少明顯的聯(lián)系，這些缺陷成為深入分析實體模型形狀結(jié)構(gòu)關(guān)系以及多模型信息挖掘的一個障礙。然而通過B-rep模型分解，將CAD模型描述為簡單實體的組合則大大有利于形狀結(jié)構(gòu)的分析、比較和理解。另一方面，B-rep模型向CSG模型轉(zhuǎn)換也是一個理論上倍受關(guān)注的研究問題6，而B-rep模型分解是實現(xiàn)這種轉(zhuǎn)換的關(guān)鍵技術(shù)之一。

7、因此，B-rep模型分解具有重要的理論意義和實際應(yīng)用價值。目前已有的分解方法主要包括以下四類：(1)半空間法6，將B-rep模型轉(zhuǎn)化為半空間表達(dá)后利用分割半空間形成半空間的組合進(jìn)行模型分解。(2)交替和差分解法(ASV)7，對模型求凸包并與模型作布爾減運(yùn)算得到差體，然后求差體的凸包再與之做布爾減運(yùn)算。如此反復(fù)循環(huán)，用凸包和差體分解模型。(3)單元分解法8-9，將B-rep模型分解為一組單元體，并將相關(guān)的單元優(yōu)化組合形成最大單元從而實現(xiàn)模型分解。(4)CLoop法，CLoop是指具有相同凹凸性的邊組成的封閉環(huán)10，Lu11 利用CLoop構(gòu)造平面或曲面切割模型實現(xiàn)模型分解過程。在上述方法中，半空

8、間法的計算過程比較復(fù)雜。CLoop法本質(zhì)上是一類半空間方法，雖然它改進(jìn)了單個半空間分割的思想，采用多個半空間的組合分解提高計算效率，然而文獻(xiàn)11中CLoop的種類過多，使得識別CLoop的過程較為繁瑣。半空間法、單元分解法和CLoop法將模型全部分解為子實體之間的正向組合，這從設(shè)計和加工的角度來看并不合理，因為零件的形狀構(gòu)成應(yīng)該同時存在負(fù)向組合。另外，單元分解法由于存在組合爆炸問題而使得效率降低；ASV法則難以對復(fù)雜模型求凸包，同時該方法也不適合曲面模型的分解。上述方法本質(zhì)上都是采用“切模式”的分解方法：半空間法用半空間切割模型，ASV用凸包切割模型，單元分解法和CLoop法用面或面的組合切割

9、模型。切模式分解方法在模型分解過程中往往具有強(qiáng)制性，它會強(qiáng)行切割模型中原本不需要分割的部分而得到不合理的分割體，同時這種強(qiáng)行切割的方式也使分割體失去了原本的設(shè)計意圖，甚至對后續(xù)應(yīng)用產(chǎn)生誤導(dǎo)作用。譬如在單元分解法中，一個面會將模型切成兩半或兩半以上，當(dāng)切割模型的面增加時就會產(chǎn)生大量的分割體，而這些分割體實際上已經(jīng)失去了原本的設(shè)計意義。文獻(xiàn)915采用單元優(yōu)化組合盡量減少單元數(shù)量，避免出現(xiàn)過多的不合理分割體。但這樣做的缺點(diǎn)也很明顯，首先基于經(jīng)驗規(guī)則的優(yōu)化方法并不能保證完全消除不合理的切割體，其次組合優(yōu)化的計算效率很低。切模式分解方法的優(yōu)點(diǎn)在于能夠?qū)⒍嗝骟w模型分割到凸體，然而對曲面體模型卻并不能保持這

10、一特性。但實際上在很多應(yīng)用場合中這種分割要求并不是必需的，譬如在特征識別中并不要求識別的特征都是凸體，又譬如在形狀分析中，當(dāng)面臨復(fù)雜模型無法有效地描述和分析模型形狀時，那么只需要將它適當(dāng)分解降低模型的復(fù)雜程度，而不一定需要將它完全分割到凸體。我們認(rèn)為，通過布爾運(yùn)算將多個模型組合成一個模型的過程是一個信息丟失的過程，即組合后的模型中失去了原有模型的部分信息，譬如面信息、邊信息等，而實體模型分解則是布爾運(yùn)算的逆過程。那么，模型分解過程本質(zhì)上是一個信息恢復(fù)的過程。因此，我們可以采用信息恢復(fù)的思想，基于組合后的模型信息恢復(fù)組合前各個模型中的設(shè)計信息，對于信息丟失嚴(yán)重而不可完全恢復(fù)的模型，我們可以盡量恢

11、復(fù)到可以恢復(fù)的程度。這樣，雖然可能存在分解不徹底的情況，但這種分解是客觀的。因此，本文提出一種“補(bǔ)模式”的方法分解模型，首先找到模型中的切割環(huán)將模型分割成多個面殼，然后通過切割環(huán)沿面殼伸延方向上的收縮將面殼封閉成實體。本文算法只針對具有二次曲面的實體模型，暫時不考慮具有自由曲面的實體模型。2 模型分解方法概述2.1 基本定義B-rep模型中的二次曲面可分為平面、凸曲面和凹曲面12，邊可分為凸邊、凹邊和相切邊13。根據(jù)面和邊的分類定義模型中的面區(qū)域如下： 定義1: B-rep模型中多個相互鄰接的面形成的集合稱為面區(qū)域，并且面區(qū)域可分為四類： (1) 凸區(qū)域是指區(qū)域中的所有面為凸曲面或者平面，且面

12、的邊界中不存在凹邊。(2) 凹區(qū)域是指區(qū)域中的所有面為凹曲面或者平面，且面的邊界中不存在凸邊。(3) 過渡區(qū)域是指構(gòu)成區(qū)域的所有面的邊界僅由相切邊組成。(4) 混合區(qū)域是指區(qū)域中的曲面的凹凸性與邊的凹凸性不一致，或者區(qū)域中的面的邊界同時存在凹邊和凸邊。定義2: 沿著一組封閉環(huán)將B-rep模型分割成多個面殼(Face Shell , FS)，如果封閉環(huán)上的邊通過面殼上的鄰接面的延伸后能夠?qū)⒃撁鏆し忾]成一個實體，那么該封閉環(huán)稱為切割環(huán)，環(huán)上的邊稱為切邊，封閉實體稱為分割體。切割環(huán)需要滿足以下條件：(1) 模型被分割成多個面殼后，切割環(huán)同時存在于兩個面殼FS1和FS2中。(2) 切割環(huán)是一類能夠封閉

13、面殼的閉環(huán)，它至少能夠封閉兩個面殼FS1和FS2中的一個面殼。定義2中，如果切割環(huán)可以同時封閉兩個面殼，那么這類切割環(huán)稱為雙向可收縮切割環(huán)；如果只能封閉其中一個面殼，那么稱為單向可收縮切割環(huán)。圖1舉例說明定義2中的術(shù)語的含義。譬如，圖1(a)中的模型根據(jù)環(huán)L1和L2分割成兩個面殼后，L1僅存在于一個面殼中，因此環(huán)L1不是切割環(huán)。圖1(b)中的模型根據(jù)環(huán)L3 、L4 和L5分割成三個面殼后，任意一個環(huán)都存在于兩個面殼中且都能封閉面殼，因此它們都是切割環(huán)。進(jìn)一步地，L5是雙向可收縮切割環(huán)，而L2 、L3 和L4是單向可收縮切割環(huán)。L1L2L5L3L4(c) 面殼(b) 切割環(huán)(a) 非切割環(huán)(d)

14、 分割體 圖1 切割環(huán)、面殼以及分割體舉例分割體可分為加體和減體，類似正特征和負(fù)特征。但為了避免與一般意義上的特征概念混淆，本文用分割體表述。根據(jù)切邊的凹凸性，文中選擇兩類切割環(huán)進(jìn)行分割：(1) 凸切割環(huán)，指切割環(huán)中的所有切邊都是凸邊。(2) 凹切割環(huán)，指切割環(huán)中的所有切邊都是凹邊。下文中提到的切割環(huán)特指這兩類切割環(huán)，并且將切邊在面殼上的鄰接面簡稱為鄰接面。2.2 實現(xiàn)方法多個實體模型通過布爾運(yùn)算組成一個實體模型時，原有實體模型之間面面交接部分會形成混合區(qū)域。所以，本文選擇實體模型中混合區(qū)域上的切割環(huán)將模型分割為多個面殼，然后利用切割環(huán)的收縮算法將面殼封閉從而完成整個分割過程。模型分割的總體算

15、法如下：輸入B-rep模型 M，輸出分割體集合Vc =vol1, vol2,：1. 在模型M中找到所有的混合區(qū)域，記為HR=R1, R2, .。2. 在HR中識別出所有切割環(huán)。如果模型M中不存在切割環(huán)，那么模型M不可分割，程序結(jié)束。否則，記錄下所有切割環(huán)L=L1, L2, 。3. 根據(jù)識別后的切割環(huán)，將模型劃分為多個面殼FSC=FS1,FS2,.，并執(zhí)行以下循環(huán): 3.1 選擇一個面殼FSi，利用面殼上的切割環(huán)收縮算法將其封閉成體voli。3.2 如果FSi不能通過切割環(huán)收縮來封閉，那么利用切割環(huán)所在另一面殼的封閉面填充封閉。4. 輸出最后分解后的結(jié)果Vc =vol1, vol2,。圖2給出了

16、總體算法的流程，下面對總體算法中的幾個的細(xì)節(jié)問題加以補(bǔ)充說明，但限于篇幅在本文中不詳細(xì)論述：(1) 混合區(qū)域的識別方法。根據(jù)定義1，只要在模型中排除凸區(qū)域、凹區(qū)域和過渡區(qū)域，那么剩下的就是混合區(qū)域。而這三種區(qū)域根據(jù)定義1很容易判別，本文不詳細(xì)說明。(2) 根據(jù)定義2，如果切割環(huán)L是單項可收縮切割環(huán)，那么它只能封閉面殼FS1而無法封閉面殼FS2。盡管此時FS2不能通過切割環(huán)的收縮算法封閉，但它可以通過已封閉面殼FS1上的面裁減實現(xiàn)封閉過程。因此，文中的面殼封閉存在兩種方式：一是根據(jù)切割環(huán)收縮封閉；二是根據(jù)已封閉面殼上的面填充封閉。步驟3中的兩個子步驟分別對應(yīng)這兩種封閉方式，這部分內(nèi)容在第四節(jié)詳細(xì)

17、闡述。(3) 切割環(huán)的識別方法。首先，在HR中識別出所有由相同凹凸性的邊組成環(huán)，并根據(jù)這些環(huán)將模型分割成多個面殼。其中，環(huán)的識別可參考文獻(xiàn)10。其次，檢查每一個環(huán)是否同時存在于兩個面殼中，并排除那些只存在于一個面殼中的環(huán)。最后，通過調(diào)用收縮算法檢驗。如果該環(huán)至少能封閉其中一個面殼，那么它是切割環(huán)，否則不是。因此，實際上步驟3.1的面殼封閉只需要重新調(diào)用前面的結(jié)果，而不需要再重復(fù)執(zhí)行一次封閉算法。B-rep 實體模型M識別實體模型上的所有混合區(qū)域HR=R1, R2, .模型不可分割輸出分割體Vc =vol1, vol2,在混合區(qū)域HR上，識別出所有切割環(huán)L=L1, L2, 根據(jù)所有的切割環(huán)將模型

18、分割成多個面殼并封閉所有面殼L是否為空是否圖2 算法總體流程3 面殼封閉過程3.1 定義定義3 ：假設(shè)ck 是切割環(huán)Ls=E1s E2sEms上的一個角點(diǎn)，它的兩條相鄰切邊為Eks和Ek+1s，其中，Eks =(e, f )且Eks.e和Eks.f分別表示切邊所對應(yīng)的B-rep模型中的邊和面，s表示切割環(huán)鄰接的兩個面殼的下標(biāo)(s=1，2)。如果滿足Eks.f = Ek+1s.f，那么ck 稱為面角點(diǎn)，記為On-F；否則，ck 稱為邊角點(diǎn)，記為On-E。 定義 4：假設(shè)Eks =(e, f )是切割環(huán)Ls=E1s E2sEms上的一條切邊并且sk 表示 Eks.f所在的幾何曲面。那么，該曲面上的

19、幾何區(qū)域f kx =sk -* Eks.f被稱為Eks.f的延伸面，它在曲面sk上并且在Eks.f的外部。如果延伸面fkx與其它的延伸面相交形成一個有界區(qū)域，同時Eks.f上的切邊仍在這個有界區(qū)域的邊界上，那么這個有界區(qū)域稱之為裁剪延伸面。定義5：假設(shè)ck 是切割環(huán) Ls=E1s E2sEms上的一個On-E角點(diǎn)，它的兩條相鄰切邊為 Eks和Ek+1s。那么，面Eks.f和Ek+1s.f延伸求交后的邊ekx=f kx*fk+1x可選為ck上的延伸邊，具體為：(1) 如果與ck相連的Eks.f和Ek+1s.f交線只有一條，則該交線即為延伸邊；(2) 如果與ck相連的Eks.f和Ek+1s.f交線

20、有兩條以上，則選擇其中與Eks.e和Ek+1s.e相連邊最靠近的交線為延伸邊。在實際模型中，ekx=f kx*fk+1x通常只包含一條交線，但對于一些特殊情況，可能存在多條；如在圖3（c）中的c4處f 3x與f4x的交線以及二次曲面相切點(diǎn)附近的交線等。對于這些情況，本文不作深入的探究，只是按定義5中條件(2)選擇其中較為合理的一條作為延伸邊。根據(jù)上述定義，很容易得到以下兩個性質(zhì)：性質(zhì)1：切割環(huán)上的一條切邊只連接一個裁減延伸面。性質(zhì)2：裁減延伸面中至少包含一條切邊。圖3給出上述定義的例子。在圖3(a)中 c2、 c3、 c5 和c6是On-F點(diǎn)，c1 和c4是On-E點(diǎn)；圖3(b)中的陰影部分f

21、1x是圖3(a)中模型的頂面E1s.f的延伸面，它是一個無限的平面區(qū)域；圖3(c)中帶箭頭的線分別表示切割環(huán)上四個On-E點(diǎn)的延伸邊ekx (k=1,2,3,4)，箭頭表示延伸方向。在圖3(c)中, 除了由f3x和f4x相交而形成的e4x之外，其他ekx (k=1,2,3)可以認(rèn)為是在面殼上對應(yīng)的邊的自然延長。這意味著當(dāng)切邊的鄰接面延伸求交后可能會有新邊產(chǎn)生。c1c2c3c4c5c6On-FOn-Ec1c4c3c2(b) 延伸面(a) 切割環(huán)上點(diǎn)的分類(c) 延伸邊圖3 切割環(huán)上的角點(diǎn)、延伸面和延伸邊舉例當(dāng)模型被分割成多個面殼后，切割環(huán)在面殼上形成一個切孔。那么，封閉面殼的過程就是填充切孔的過

22、程。切割環(huán)根據(jù)切邊所在的面可分為兩類：一是切割環(huán)上所有切邊在同一個面內(nèi)；二是切割環(huán)上的切邊在不同的面內(nèi)。由于第一類切割環(huán)在一個面內(nèi)，那么其切孔也在一個面內(nèi)，譬如內(nèi)環(huán)就是典型的第一類切割環(huán)。封閉這類面殼很容易實現(xiàn)，因為它只需用一個確定的填充面即可封閉，而該填充面的邊界就是由切割環(huán)上所有的切邊組成。但是，封閉第二類切割環(huán)引起的面殼則比較復(fù)雜，因為它的填充面數(shù)量超過1個，而且填充面的邊界是不能預(yù)先確定的。因此，本文詳細(xì)討論由第二類切割環(huán)產(chǎn)生的面殼的封閉方法，其主要流程如下：(1) 用切邊的鄰接面通過延伸構(gòu)造面填充切孔。(2) 用填充面上新生成的邊代替原來的切邊，使得切割環(huán)的邊界在面殼上發(fā)生連續(xù)的變化

23、，稱為切割環(huán)收縮。譬如，圖4(a)是一個切割環(huán)，當(dāng)切邊c1c2的鄰接面f 通過延伸構(gòu)造面填充切孔后(見圖4(b)，切割環(huán)收縮成圖4(c)的形式。(3) 當(dāng)切割環(huán)收縮到一個面上時(見圖4(d)，即轉(zhuǎn)化為第一類形式的切割環(huán)，那么直接用切割環(huán)邊界構(gòu)造一個面就可以封閉面殼。填充f 面代替后的切邊f(xié)c1c2c3 fc4c3 fc4c3 f(d) 切割環(huán)收縮到一個面內(nèi)(c) 收縮后的切割環(huán)(a) 切割環(huán)(b) 構(gòu)造面填充切孔起圖4 第二類切割環(huán)收縮過程舉例根據(jù)定義4可知，上述面殼封閉過程中的填充面就是裁剪延伸面，并且它的邊界由切邊和延伸面之間的交邊組成。顯然，切邊是固定的，那么On-F點(diǎn)同樣是固定的，而交

24、邊可認(rèn)為是On-E點(diǎn)在延伸方向的運(yùn)動形成的軌跡，這是由于交邊是延伸面之間相交產(chǎn)生的，并且屬于延伸邊上的線段。因此，切割環(huán)上On-F點(diǎn)是不變動的，但On-E點(diǎn)是可變動的。那么，描述切割環(huán)時可以忽略O(shè)n-F點(diǎn)，而只用On-E點(diǎn)進(jìn)行抽象地一般化表達(dá)。譬如，圖3(a)中的切割環(huán)可以簡單的表示為圖5(a)的形式。圖5(b)則是切割環(huán)的一般表達(dá)形式，圖中封閉圈表示抽象的切割環(huán)，圈上的點(diǎn)都是On-E點(diǎn)，相鄰兩個On-E點(diǎn)之間的弧表示在同一個鄰接面上的所有切邊。圖5(c)則表示用裁剪延伸面填充切孔后的一般化形式。ckck+1c1c4(a) 圖3(a)中切割環(huán)的抽象表達(dá)(c) 切孔的一般填充方式 (b) 切割環(huán)

25、的一般表達(dá)形式 圖5 用On-E點(diǎn)表示的切割環(huán)和切孔的一般填充方式在任意情況下延伸面之間的相交關(guān)系可以很復(fù)雜，這使得裁減延伸面上的交邊難以直接判別，如在圖5(c)中可以看出某些裁剪延伸面上具有多條未知的交邊。因此，填充切孔時需要有一個合理的填充順序處理延伸面之間復(fù)雜的相交關(guān)系。綜上所述，在封閉第二類切割環(huán)產(chǎn)生的面殼的過程中需要解決兩個關(guān)鍵問題：一是構(gòu)造什么類型的填充面；二是面的填充順序。下面，對這兩個問題詳細(xì)討論。3.2 填充面類型選擇以及填充順序確定切孔上存在兩類容易構(gòu)造的裁剪延伸面：一是面上除了切邊外只存在一條交邊，如圖6中點(diǎn)區(qū)域所示；二是面上存在兩條交邊，如圖6中的陰影區(qū)域。文中將前者稱

26、為單邊延伸面(One-edge-extension face)，記為 1EE 面，后者稱為雙邊延伸面(Two-edge-extension face)，記為 2EE 面。構(gòu)造一個1EE面或2EE面填充切孔后，用交邊代替鄰接面上的切邊，這樣就可以保證切割環(huán)收縮。圖6(b)是圖6(a)中切割環(huán)收縮后的邊界，圖6(b)中還可以生成1個1EE面和3個2EE面，那么切割環(huán)進(jìn)一步收縮(見圖6(c)。循環(huán)上述過程，就可以生成所有的裁剪延伸面。顯然，為了保證可封閉的切孔能夠完全用上述操作完成封閉過程，必須保證每一步收縮后的切割環(huán)邊界上都存在1EE 或2EE 面。單延伸邊面 雙延伸邊面(a) 初始切孔(c) 收

27、縮2次后的切孔(b) 收縮1次后的切孔(e) 收縮4次后的切孔(f) 收縮5次后的切孔(d) 收縮3次后的切孔圖6 填充孔時的面生成順序定理1：如果切割環(huán)中至少包含2個On-E 角點(diǎn)，并且用切割環(huán)上的所有切邊對應(yīng)的裁剪延伸面的組合可以填充面殼上的切孔，使得切孔被填充后形成一個單連通區(qū)域R，那么，1、 在單連通區(qū)域內(nèi)部不存在由填充面之間的交邊組成的封閉回路。2、 切割環(huán)中至少存在一個1EE面或2EE面。證明：1、 反證法。如果R的內(nèi)部存在封閉回路L=eiejei, ei是填充面之間的交邊，顯然ei不是切孔上的切邊。那么，L也包圍一個單連通區(qū)域。由于R 內(nèi)部的每一條幾何邊一定連接兩個填充面，根據(jù)性

28、質(zhì)1它們也不是切邊。由性質(zhì)2可知，在區(qū)域R 內(nèi)的填充面不是裁剪延伸面，與用裁剪延伸面填充切孔這一前提條件矛盾。2、 令切孔有m個On-E 角點(diǎn)，記為ci(1im)，將ci根據(jù)下標(biāo)值i從小到大在切孔上順時針排列(見圖7(a)。那么，R內(nèi)部(不包含切孔邊界)填充面的頂點(diǎn)和邊的連接關(guān)系可以用圖G表示。顯然，G的節(jié)點(diǎn)和邊與填充面的頂點(diǎn)和邊具有一一對應(yīng)關(guān)系，即存在一個可逆映射f : vi=f (Vi), ej=f (Ei) vi, ejG，Vi, Ei 分別表示vi和 ej對應(yīng)的幾何頂點(diǎn)和幾何邊。由于R中不存在封閉回路L=eiejei，那么根據(jù)映射f，G中不存在封閉回路L=f(L)=f(ei).f(ej

29、)f(ei)，這說明G是一個森林14，記為，其中Ti表示森林中的樹，D(Ti)表示樹的節(jié)點(diǎn)數(shù)目。顯然Ti的根節(jié)點(diǎn)和葉節(jié)點(diǎn)都是切孔角點(diǎn)ci。對于，將Ti的葉節(jié)點(diǎn)根據(jù)下標(biāo)值大小繞著它們的祖先順時針排列，可以將G中的節(jié)點(diǎn)和邊放在同一個平面上(見圖7(b)?，F(xiàn)在，通過搜索G中Ti的節(jié)點(diǎn)來找到對應(yīng)的1EE 面或2EE 面。顯然，存在一個包含c1頂點(diǎn)的樹Tj：(1) 假設(shè)D(Tj)=2，那么Tj中只有兩個節(jié)點(diǎn)c1,和ct。如果c1、ct的下標(biāo)值是連續(xù)的，那么c1、ct就對應(yīng)一個1EE 面；如果不連續(xù)，由于節(jié)點(diǎn)按下標(biāo)值依次排列，那c1、ct之間一定存在其它樹Tk ，這些樹的根節(jié)點(diǎn)和葉節(jié)點(diǎn)的下標(biāo)值在1和 t之

30、間，那就轉(zhuǎn)換到這些樹中繼續(xù)搜索。(2) 假設(shè)D(Tj)>2。因為填充面上的每一個頂點(diǎn)至少包含3條幾何邊，所以Tj中除了根節(jié)點(diǎn)以外，其它父節(jié)點(diǎn)至少包含2個子節(jié)點(diǎn)。這樣，Tj中具有最長深度的那個葉節(jié)點(diǎn)的父節(jié)點(diǎn)，必定包含另一個葉節(jié)點(diǎn)。如果這兩個葉節(jié)點(diǎn)的下標(biāo)值是連續(xù)的，那這兩個葉節(jié)點(diǎn)和它們的父節(jié)點(diǎn)一起對應(yīng)一個2EE 面。否則，在這兩個不連續(xù)的葉節(jié)點(diǎn)之間同樣存在其它樹Tk。這種情況下，轉(zhuǎn)換到這些樹中繼續(xù)搜索。由于G中的樹是有限的，那么一定可以找到這樣一棵樹Tk，它只有兩個連續(xù)的節(jié)點(diǎn)或者存在兩個連續(xù)的葉節(jié)點(diǎn)共用一個父節(jié)點(diǎn)。因此，所有填充面中一定存在一個1EE 面或2EE 面。證畢。f1xc2cmcm

31、-1c3f2xc4c5c10c9c8f3xf4xc11f6xf5xc7c6c1c3c4c9c8c2cmcm-1c5c6c7c10c11c1(b) 所有填充面構(gòu)成的點(diǎn)邊圖 (a) 切孔上的點(diǎn)的排列順序圖7 1EE 或者2EE 面的存在性基于上述定理可以得到以下推論，它給出了用裁剪延伸面填充切孔的一個合理順序。推論1：如果切割環(huán)中至少包含2個On-E 角點(diǎn)，并且用切割環(huán)上的所有切邊對應(yīng)的裁剪延伸面的組合可以填充面殼上的切孔，使得切孔被填充后形成一個單連通區(qū)域R，那么用來填充的所有裁剪延伸面可以用l 步孔邊界收縮完成，其中每一步包括識別和構(gòu)造一個1EE 或2EE 面，這里lm。4 面殼封閉算法根據(jù)第

32、2節(jié)討論，面殼封閉存在兩種方式，即切割環(huán)收縮的封閉方式和根據(jù)已封閉面殼上的面填充的封閉方式。第3節(jié)給出了第一種封閉方式的實現(xiàn)過程，即每一次通過構(gòu)造1EE 或2EE 面填充切孔使切割環(huán)收縮，通過l次迭代后，最終將面殼封閉。本節(jié)進(jìn)一步介紹如何構(gòu)造1EE 和2EE 面，并給出一個詳細(xì)的切割環(huán)收縮算法。同時，給出第二種封閉方式的實現(xiàn)方法。4.1 構(gòu)造裁剪延伸面 設(shè)ci、ci+1是切割環(huán) Ls=E1s E2sEms上連續(xù)的兩個On-E角點(diǎn)，并且fi-1、fi 和 fi+1 ( fk =Eks.f，k=i-1，i，i+1)分別是切邊ci-1ci、cici+1 和ci+1ci+2的鄰接面。以下是生成1EE和

33、2EE面的兩個基本操作。操作：構(gòu)造1EE面 如果fi-1 和 fi+1具有相同的幾何方程表達(dá)式，則在 fi-1 和 fi+1的合成面f 上連接ci ci+1代替面fi上的切邊，并將ci 和 ci+1類型改為On-F。那么，邊cici+1和fi 上原來的切邊組成一個 1EE面(見圖8(a)。 操作2：構(gòu)造2EE面 如果延伸f i-1x、f ix和 fi+1x彼此相交于點(diǎn)v，則在點(diǎn)v上創(chuàng)建一個點(diǎn)角c，分別在f i-1x 和fi+1x上連接 ci c 和 c ci+1 代替原來的切邊，將角點(diǎn)ci 和ci+1的類型改為On-F，將延伸邊ex = f i-1x*fi+1x上的角點(diǎn)c 的類型改為On-E。

34、那么，邊civ，vci+1以及面fi 上原來的切邊組成一個2EE面 (見圖8(b)。ci+1cici-1ci+2fifi+1fi-1 1EEci-1ci+2f (a) 構(gòu)造1EE面vcifi+1fifi-1ci+1ci+2ci-1 cvfi+12EEfi-1(b) 構(gòu)造2EE面圖8 1EE和2EE面的構(gòu)造方法從操作2的描述上看，創(chuàng)建的頂點(diǎn)只能有三條連接邊，但實際上其他類型的頂點(diǎn)也同樣可以用操作2生成。如圖9，首先用操作2生成2個三條邊頂點(diǎn)，然后刪除連接這兩個頂點(diǎn)的零長度邊，就可以產(chǎn)生一個連接四條邊的頂點(diǎn)。刪除0長度邊vi1vi2vi2vi1 vi圖9 用操作2生成一個超過3條邊連接的頂點(diǎn) 填充

35、切孔的過程中，并不是所有的1EE面或2EE面都必須構(gòu)造的。例如，圖10(a)中c1和c2之間的1EE面，圖10(b)中c1 和c2之間的2EE以及圖10(c)中c2和c3之間的2EE面在孔收縮過程中不能被構(gòu)造。為了確定填充切孔時哪些1EE 面和2EE面可以構(gòu)造，下面給出一個定理，它是選擇合適的1EE 或2EE面的一個充分條件。c3c1c2c3c4c5c6v23v61v561v234c2v12v23c1c3c4c5v51v451v34c1c2c4c5v12v23v125(c) 模型3(a) 模型1(b) 模型2圖10 執(zhí)行基本操作應(yīng)該滿足的幾何條件 定理：設(shè)ci 和ci+1是切割環(huán)上連續(xù)的兩個O

36、n-E角點(diǎn)，eix和ei+1x分別是這兩個角點(diǎn)的延伸邊，切割環(huán)上所有延伸面表示為 f kx (k=1,2,m)。假設(shè)可以填充切孔的所有裁剪延伸面f j ( j =1,2,.m)構(gòu)成的一個面集合C：1. 如果根據(jù)操作1用ci 和ci+1可以構(gòu)造一個1EE面 fe1，并且ci 和ci+1的延伸邊eix上的線段s = eix(ci, ci+1)與延伸面f kx (ki-1, i, i+1)不相交，即 (ki-1, i, i+1)。那么fe1一定屬于集合C中的一個面。2. 如果根據(jù)操作2創(chuàng)建一個頂點(diǎn)vi,i+1連同ci 和 ci+1可以構(gòu)造一個2EE面 fe2，并且cj 和vi,i+1的兩條延伸邊(j

37、=i, i+1)上的線段sj與延伸面(ki-1,i,i+1)不相交，即 (ki-1, i, i+1；j=i , i+1)。那么，那么fe2一定屬于集合C中的一個面。證明：因為集合C上的所有裁剪延伸面可以填充切孔，那么集合中存在一個裁剪延伸面f ，它是延伸面fi x的一部分，并且它的邊界由切邊cici+1、延伸邊上的線段si、si+1以及其他可能的延伸邊上的線段組成(見圖11)。如果在的邊界上存在另一條線段s (ssi) 與si+1相交于點(diǎn)v，那么si+1應(yīng)該與s 相鄰的延伸面(ki-1，i，i+1)相交，即 ，這與前提條件(ki-1, i, i+1；j=i , i+1)矛盾。這就意味著在f 的

38、邊界上除了si 和si+1外沒有其他線段s。因此，面f 是一個1EE 或者2EE 面。因為根據(jù)給定的切邊cici+1只能夠造一個1EE面或2EE面，那么集合C中的裁剪延伸面f 就是1EE 面 fe1 或者2EE 面 fe2。證畢。cici+1ci-1ci+2si+1vffixssifkx圖11 選擇基本操作的充分條件 填充切孔過程中，滿足定理2條件的1EE 或2EE面先被構(gòu)造。當(dāng)一個1EE 或2EE面生成后，其他原先不滿足條件的面就有可能滿足條件，因為它們的干涉面可能不再與更新后的切割環(huán)邊界相連接。例如，在圖10(b) 中用c2c3生成的2EE面在第一次的時候不能被構(gòu)造因為邊c2v23與c1c

39、5的延伸面f 5x相交；但是用c1c5構(gòu)造2EE面后，更新后的切割環(huán)的延伸面不再包括f 5x，因為這時候切割環(huán)上的角點(diǎn)只有c2, c3, c4 和v51。這樣，用c2c3構(gòu)造的2EE面就不再出現(xiàn)干涉情況。 4.2 切割環(huán)收縮算法利用4.1節(jié)的兩個基本操作和定理2給出的構(gòu)造合適1EE或2EE面的條件，下面給出填充孔的收縮算法。1. 在包含切割環(huán)Ls=E1s E2sEms, Eks = (e, f ) (1km)的面殼FS中，找到切孔上的所有On-E角點(diǎn)ck，并且生成所有延伸面fkx、延伸邊ekx。設(shè)置切邊集合，其中是符合操作1或操作2的切邊。2. 令 k=1, 2, , m, 開始以下循環(huán)：2.

40、1 如果=，并且, (ik-1, k, k+1), 那么將切邊放到集合C中。2.2 如果，并且和, (ik-1, k, k+1), 那么將切邊放入到集合C中。3. 如果，進(jìn)行循環(huán)：3.1 令i=1,2,|C|，執(zhí)行： 3.1.1 當(dāng)時，在集合C中，選擇執(zhí)行完第(i-1)步循環(huán)后滿足定理2條件的第i條切邊進(jìn)行操作1或者操作2。3.1.2 更新切孔上的點(diǎn)、延伸面、延伸邊以及m。3.2 設(shè)置 并轉(zhuǎn)2。4. 如果，結(jié)束程序并輸出以下兩個結(jié)果：4.1 如果 m=1, 從FS中刪除切孔收縮后形成的第一類切割環(huán)，直接封閉并返回封閉后的實體，輸出封閉成功信息。4.2 否則，認(rèn)為切孔是不可收縮的，并輸出封閉失敗

41、信息。我們可以對上述算法的復(fù)雜度進(jìn)行下列估計。設(shè)切割環(huán)的起始邊數(shù)為n, 搜索過程中切割環(huán)邊數(shù)m從n逐步減少到1，每次邊-面相交檢查計算量為Ief、面-面相交檢查計算量為Iff、構(gòu)造一個1EE或2EE面的最大計算量為F。在收縮最慢的情況下，每步收縮只一條切割邊；即m每次減1，需要n步收縮。在該算法中邊-面相交檢查次數(shù)較多，但在算法具體實現(xiàn)時可以盡量使用前面已經(jīng)計算過的檢查結(jié)果；這樣，在初始時有n(n-3) 次邊-面相交檢查, 在以后各步中只對新出現(xiàn)的延伸邊進(jìn)行邊-面相交檢查。由此，在切割環(huán)邊數(shù)為m時，收縮一條切割邊，最多需要2m次面-面相交檢查、m-3次針對新產(chǎn)生延伸邊的邊-面相交檢查和1次1E

42、E或2EE面構(gòu)造。所有，總的計算量上界為：用上述算法可以完成圖10中封閉過程。譬如，在圖10（a）中切邊c2c3 和c6c1首先被收縮，然后孔收縮時角點(diǎn)的完成順序是v23，v61v234，v561。同樣地，圖10(b)中的角點(diǎn)完成順序是v15v23，v451；圖10（c）中是v12 ，v34v125。圖12給出了一個更復(fù)雜的例子。首先，在面f1,，f6 和f11上都有可以創(chuàng)建2EE面，但f1 上的2EE面與f10x干涉， f6 上的2EE面與f 12x干涉(見圖12(a), 只有f11上的2EE面是不干涉的。處理完f11后，f10成為唯一可以用操作2且不干涉的面(見圖12 (b)。在圖12（c

43、）中，f9上的2EE面與f 2x干涉。但執(zhí)行完前一次操作后，f1上的2EE面f10成為非干涉面。當(dāng)f1填充后，f12成為唯一可以用操作2且不干涉的面(見圖12 (d)。之后，f6被填充 (見圖12 (e-f)。接著，f7 和f8被填充(見圖12 (g-h)。在圖12(h)中，f9上的2EE面與f 4x相交，那么f5成為唯一可以被填充的面。f5 完成后， f2 和f4 都符合操作2 的要求(見圖12 (i)，直接構(gòu)造(見圖12 (j-k)。然后，在圖12 (k)中，f3 和 f9都符合操作1的要求，但當(dāng)f3的上的1EE面生成后，切孔已經(jīng)收縮到一個面上形成第一類切割環(huán)(見圖12 (m)，那么移除f

44、9上由切孔形成的切割環(huán)后，算法程序就成功地結(jié)束。f1f6f10f12f2f9f11f1f6f10f12f1f6f10f11f12(c) 收縮2次后的切孔(b) 收縮1次后的切孔(a) 初始切孔f1f6f12f2f9f7f5f9f2f6f12f2f9(f) 收縮5次后的切孔(e) 收縮4次后的切孔(d) 收縮3次后的切孔f5f9f2f4f9f2f4f7f5f9f2f8(g) 收縮6次后的切孔(i) 收縮8次后的切孔(h) 收縮7次后的切孔f9f3f9f9f2f3(m) 收縮11次后的切孔(k) 收縮10次后的切孔(j) 收縮9次后的切孔圖12 切孔收縮舉例 4.3單向可收縮切割環(huán)的封閉方法根據(jù)定

45、義2可知，單向可收縮的切割環(huán)只能封閉其對應(yīng)兩個面殼中的一個面殼FS1。出現(xiàn)這種情況的原因在于該切割環(huán)在另一個的面殼FS2上的延伸邊是發(fā)散的(如圖13(a)，導(dǎo)致填充區(qū)域是切割環(huán)外部的一個無限區(qū)域（見圖13(b)），這時我們可以用已封閉面殼FS1上的面封閉面殼FS2。這是因為收縮算法改變的僅僅是B-rep中面的邊界而不產(chǎn)生新面，那么可以用面殼FS1上的收縮后的面與它對應(yīng)的原始面作差運(yùn)算得到裁剪面片，用這些裁減面片就可以封閉面殼FS2。ck+1ck(a) 單向可收縮的切割環(huán)圖13 單向可收縮的切割環(huán)舉例(b) 填充區(qū)域是一個無限區(qū)域 假設(shè)B-rep中所有原始面的集合為 Fold=f1, f2,.，

46、并假設(shè)已經(jīng)封閉的切孔上，經(jīng)過填充后形成的面的集合為Fext=f1, f2, .。那么，封閉不收縮切孔的方法如下：1. 創(chuàng)建一個臨時的面集合，并令。2. 對于每一個在集合Fext中的面f k，在集合Fold中找到對應(yīng)的原始面，作差運(yùn)算，并將差運(yùn)算后形成的面片 放入到 。3. 用集合Ffill中的所有面填充孔。5 實驗結(jié)果與討論為驗證本文提出的方法，我們使用Visual C+和三維實體幾何引擎ACIS實現(xiàn)上述算法，實驗用的微機(jī)配置為Pentium(R) 4CPU 3.00GHz,1.00GB內(nèi)存。圖14反映的是模型分解算法中的部分中間過程。圖14(b)是根據(jù)第一類切割環(huán)分割后形成的一個分割體，該分

47、割體中用紅色表示的面區(qū)域就是該分割體中的部分混合區(qū)域。圖14(c)是在上述混合區(qū)域中找到的第二類切割環(huán)，其中橘黃色的環(huán)表示凸分割環(huán)，根據(jù)這些環(huán)分離出的是減體；紫色表示凹分割環(huán)，根據(jù)這些環(huán)分離出的是加體。圖14(d)則是根據(jù)混合區(qū)域中找到的切割環(huán)進(jìn)行收縮后得到的分割體。為了驗證本文算法的有效性，我們選擇了典型零件進(jìn)行分解。圖15給出了實驗中的六個典型零件模型以及它們分解后的結(jié)果，從圖中可以看出本文的算法能較好的分解模型。(b) 部分混合區(qū)域舉例(c) 混合區(qū)域中的切割環(huán) (a) 模型(d) 根據(jù)切割環(huán)收縮后得到的分割體圖14 模型分解的部分中間過程舉例模型 分解結(jié)果 模型 分解結(jié)果圖15 典型零

48、件的分解舉例為了測試本文算法的效率，我們用模型的面數(shù)量衡量模型規(guī)模大小并作為橫坐標(biāo)，而模型分解時間作為縱坐標(biāo)，形成模型分解時間的曲線圖。實驗中我們選擇了18個典型模型進(jìn)行分解，其中縱坐標(biāo)表示模型中面的數(shù)量。圖16是分解這些模型所需要的時間曲線圖。從圖中可以看到，大部分模型的分解時間低于1秒，即使模型中面數(shù)量超過150個，其分解時間也低于1.5秒，這說明本文方法的效率是比較高的。圖16 算法效率曲線通常，我們希望通過模型分解進(jìn)一步分析模型中存在的典型設(shè)計結(jié)構(gòu)以及它們之間的相互關(guān)系，并且通過多模型之間的比較，發(fā)掘有用的設(shè)計規(guī)律。因此，我們希望模型分解后的分割體能盡量保持其完整的設(shè)計結(jié)構(gòu)而不被破壞。

49、基于切割環(huán)收縮的模型分割方法與切模式分割方法的最大差別在于前者是根據(jù)信息恢復(fù)的思想，通過切割環(huán)的收縮恢復(fù)面殼本身具有的設(shè)計意圖，從而使分割體更加符合原本的設(shè)計意圖；而切模式的分割方法則是一種強(qiáng)制性分割方法，其分割體很難體現(xiàn)原本的設(shè)計意圖。(c) 本文算法的分割結(jié)果(b) 利用文獻(xiàn)15得到的分割結(jié)果及爆炸圖顯示(a) 分割模型 圖17 與文獻(xiàn)15的實驗結(jié)果對比圖17給出了一個例子，體現(xiàn)了本文方法分割結(jié)果與切模式方法分割結(jié)果的差別。該模型中存在兩個U型槽，四周存在三角型支撐面，中間存在一個菱形孔。U型槽的設(shè)計是作為連接結(jié)構(gòu)，同時起到移動副的作用；支撐面是一個夾緊結(jié)構(gòu)，起到定位作用；菱形孔在該模型中

50、既是一個連接結(jié)構(gòu)，同時也具有定位功能。因此，我們希望能從該模型分割中分割出這些設(shè)計結(jié)構(gòu)。我們對文獻(xiàn)15的算法和本文算法的分解結(jié)果進(jìn)行對比，圖17(b)是文獻(xiàn)15的算法的分解結(jié)果，圖17(c)是本文方法的分解結(jié)果。從中可以看到，文獻(xiàn)15的算法由于其強(qiáng)制性的分割策略，其得到的分割體已經(jīng)不具有任何的設(shè)計信息，并且分割體形狀各異且關(guān)系錯綜復(fù)雜；而本文方法得到的各分割體分別對應(yīng)某一局部功能結(jié)構(gòu)從而使得分割結(jié)果更有意義。6總結(jié)實現(xiàn)B-rep模型分解對模型分析和信息挖掘具有重要的意義，本文采用信息恢復(fù)的思想，提出一種補(bǔ)模式的基于切割環(huán)收縮的方法分解模型。通過實驗驗證，該方法能有效地分解大部分的零件模型。本文

51、方法的主要特點(diǎn)有：(1) 本文的方法可以分離出加體和減體，即一般意義上的正特征和負(fù)特征，使得模型分解更合理，有利于進(jìn)一步的分析和比較。(2) 提出一種環(huán)收縮算法封閉面殼。該方法是確定性算法而不是啟發(fā)式算法，因此具有較高的效率。同時，在算法過程中用來填充切孔的1EE面和2EE面構(gòu)造簡單，易于實現(xiàn)。(3) 在面殼封閉過程中，僅用面殼上存在的面進(jìn)行封閉，而不人為的引入新的面封閉。這樣使得封閉結(jié)果具有確定性，符合信息恢復(fù)的原則。 盡管如此，本文方法目前還存在兩點(diǎn)不足需要在今后改進(jìn)：(1) 目前無法給出環(huán)的封閉性充要條件，不能預(yù)先確定環(huán)的可封閉性，而只是通過執(zhí)行收縮算法去判斷環(huán)是否可封閉。(2) 本文方

52、法暫時沒有考慮包含自由曲面的模型?？朔陨蟽牲c(diǎn)不足之處，會有許多頗具挑戰(zhàn)的問題需要解決，這也是今后的研究內(nèi)容。參考文獻(xiàn)1. Gao Shuming. A survey of automatic feature recognition. Journal of Computers, 1998, 21 (3) : 281-288 (in Chinese)(高曙明. 自動特征識別技術(shù)綜述. 計算機(jī)學(xué)報, 1998, 21(3) : 281-288)2. Zhengdong Huang, Bo Xie, Lujie Ma, Xin Wei. Feature conversion based on dec

53、omposition and combination of swept volumes. Computer-Aided Design 2006, 38(8):857-8733. Zheng Bochuan, Peng Wei, Zhang Yin, et al. A survey on 3D model retrieval techniques. Journal of Computer-Aided Design & Computer Graphics, 2004, 16(7): 873-881 (in Chinese)(鄭伯川, 彭維, 張引等. 3D模型檢索技術(shù)綜述. 計算機(jī)輔助設(shè)計

54、與圖形學(xué)學(xué)報, 2004,16(7):873-881)4. Gao S, Shah J J. Automatic recognition of interacting machining features based on minimal condition subgraph. Computer-Aided Design 1998; 30(9): 727-7395. El-Mehalawi M, Allen Miller R. A database system of mechanical components based on geometric and topological simila

55、rity. Part II: indexing, retrieval, matching and similarity assessment. Computer-Aided Design 2003, 35(1): 95-1056. Suzanne F. Buchelea, Richard H. Crawfordb. Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations. Computer-Aided Design. 2004, 36(12): 1063-10737. Woo, T.C. Feature extraction by volume decomposition, Proceedings of the Conference on CA