基于區(qū)域特征分割的CAD模型局部搜索方法

陶松橋 黃正東 馬露杰

1.武漢理工大學，武漢，430070

2.武漢交通職業(yè)學院，武漢，430065

3.華中科技大學，武漢，430074

4.浙江萬向億能動力電池有限公司，杭州，311215

0 引言

三維CAD模型搜索已成為近年來CAD＆CG領域新的研究熱點之一［1－8］。由于能方便地提取B－rep模型的面和邊信息，故用面和邊屬性來表征CAD模型的形狀特征是一個自然而實用的選擇。對于結(jié)構(gòu)復雜的CAD模型，由于其面和邊的數(shù)量一般較多，直接用面和邊屬性作為模型形狀特征進行形狀比較時，存在著模型局部形狀不突出、數(shù)據(jù)量較大和計算復雜度較高的問題。如果能夠?qū)AD模型進行區(qū)域特征分割，依據(jù)其邊界將其分割為具有一定工程意義的局部形狀集合，則能突出模型的局部形狀信息和降低模型的形狀復雜度，方便模型進行形狀比較。

本文提出一種基于區(qū)域特征分割的CAD模型局部搜索方法。首先對搜索輸入CAD模型和數(shù)據(jù)庫CAD模型分別進行區(qū)域特征分割，將它們分割為區(qū)域特征數(shù)量最少的凸區(qū)域、凹區(qū)域和平面區(qū)域等組成的區(qū)域特征集合；接著對分割形成的區(qū)域特征及其鄰接關系屬性進行編碼，由屬性編碼值的相似度度量得到相比較CAD模型的相似度。實驗結(jié)果表明，該方法能夠?qū)崿F(xiàn)CAD模型的局部形狀搜索，搜索效率和精準程度都能滿足實際應用需要。

1 CAD模型區(qū)域特征分割

1.1 相關術語和定義

本文中用面屬性鄰接圖G＝（V，E）表征區(qū)域特征分割前的CAD模型，其中V為圖G的頂點集合，對應于B－rep模型中的面集合。面的類型由面曲率來確定，僅考慮凸面、凹面和平面三種情況，機械零件中較少出現(xiàn)的馬鞍面暫不考慮。E為面屬性鄰接圖G的邊集合，對應于B－rep模型中面的鄰接關系集合。邊的類型由面之間的外夾角來確定，包括凸邊、凸切邊、凹邊、凹切邊和過渡邊。CAD模型區(qū)域特征分割的相關術語和定義如下：

定義1 假定區(qū)域特征中所有面都為平面，面的鄰接邊都為切邊，則該區(qū)域特征為平面區(qū)域。

定義2 假定區(qū)域特征中所有面都為平面或凸面，面的鄰接邊都為凸切邊或凸邊，且該區(qū)域特征不為平面區(qū)域，則該區(qū)域特征為凸區(qū)域。

定義3 假定區(qū)域特征中所有面都為平面或凹面，面的鄰接邊都為凹切邊或凹邊，且該區(qū)域特征不為平面區(qū)域，則該區(qū)域特征為凹區(qū)域。

定義4 對于圖G，如果V是凸面或平面，并且它的鄰接邊不是凹邊或凹切邊，那么V是圖G的凸頂點；如果V是凹面或平面，并且它的鄰接邊不是凸邊或凸切邊，那么V是圖G的凹頂點；如果V是凸（凹）面，并且它的鄰接邊中有凹（凸）邊或凹（凸）切邊，或者G的頂點是平面，并且它的連接邊中有凸邊或凹邊，那么頂點V為圖G的混合頂點。

1.2 區(qū)域特征分割方法

區(qū)域特征分割是在不破壞CAD模型B－rep結(jié)構(gòu)的前提下，將其分割為數(shù)量最少的凸區(qū)域、凹區(qū)域和平面區(qū)域特征的集合，以降低模型的結(jié)構(gòu)復雜度，方便模型形狀比較。常用的基于面合并區(qū)域特征分割方法，存在著分割結(jié)果不確定或計算復雜度較高的問題，為彌補以上缺陷，本文區(qū)域特征分割方法分兩步進行：首先進行粗分割，將CAD實體模型分解為凸區(qū)域、凹區(qū)域和平面區(qū)域三類區(qū)域特征集合的并；接著將粗分割得到的區(qū)域特征集合執(zhí)行優(yōu)化算法，以得到數(shù)量最少的區(qū)域特征集合。

粗分割首先采用圖的深度優(yōu)先搜索算法對面屬性鄰接圖G＝（V，E）中的凸頂點和凹頂點組成的所有子圖進行識別，將圖G分割為多個子圖。接著分析子圖中是否存在混合頂點，如果不存在，粗分割完成；如果存在混合頂點，需要進一步將其分割為凸子圖、凹子圖和平面子圖的集合，方法是刪除混合頂點連接的所有凹邊使之變?yōu)橥鬼旤c或刪除它連接的所有凸邊使之變?yōu)榘柬旤c，具體步驟如下：

（1）識別凹子圖。刪除混合子圖中所有混合頂點連接的凸邊，將其分割為多個子圖。檢查分割得到的子圖是否存在凹子圖，如果不存在，轉(zhuǎn)向步驟（2）；如果存在，將凹子圖直接輸出；同時將剩余的其他非凹子圖被刪除的所有凸邊恢復，將分離出凹子圖以后的混合子圖重新生成一個新的子圖。如果新子圖不存在混合頂點，直接輸出；否則，將其作為混合子圖重復步驟（1）過程。

（2）識別凸子圖。刪除混合子圖中所有混合頂點連接的凹邊，將其分割為多個子圖。檢查分割得到的子圖是否存在凸子圖，如果不存在，刪除混合子圖所有連接的邊，生成平面子圖，直接輸出；如果存在，將凸子圖直接輸出；同時將剩余的其他非凸子圖被刪除的所有凹邊恢復，將分離出凸子圖以后的混合子圖重新生成一個新的子圖。新子圖如果不存在混合頂點，直接輸出；否則，將其作為混合子圖重復步驟（1）過程。

接著進行的區(qū)域特征優(yōu)化是通過遞歸合并相鄰的區(qū)域特征來減少區(qū)域特征數(shù)量。相鄰區(qū)域特征可合并條件是合并后得到的新區(qū)域特征仍是一個凸區(qū)域、凹區(qū)域或平區(qū)域。對于一個區(qū)域特征，可能存在多種可合并操作情況，但只存在一個最大可合并區(qū)域特征。區(qū)域特征優(yōu)化過程中的所有可合并操作可以用樹來表達，為了得到最大可合并區(qū)域特征，需要搜索樹上的每一個分支。但是當樹的分支數(shù)量較多時，其搜索效率將十分低下。為提高計算效率，本文采用貪心搜索算法，從每個分支中選擇最優(yōu)的分支作為下次搜索的起點。圖1中列出了一些典型CAD模型區(qū)域特征分割的結(jié)果。

圖1 一些典型CAD模型區(qū)域特征分割的結(jié)果

2 區(qū)域特征屬性編碼計算

2.1 區(qū)域?qū)傩跃幋a計算

區(qū)域?qū)傩跃幋a由區(qū)域?qū)傩灶^碼rH和區(qū)域中面的上下文碼rf C組成。

（1）區(qū)域?qū)傩灶^碼r H的計算。區(qū)域?qū)傩灶^碼rH是一個2位十進制數(shù)，其計算公式為

其中，rCon和rf T分別表示區(qū)域的凸性和區(qū)域中面幾何類型的編碼值，如平面區(qū)域rCon＝0，凸區(qū)域rCon＝1，凹區(qū)域rCon＝2。rf T的計算公式為

其中，a0～a4分別代表平面、圓柱面、圓錐面、球面和其他面。如果ai（i＝0，1，…，4）對應的面幾何類型在區(qū)域中存在，則ai的值為1；否則ai的值為0。

（2）區(qū)域中面上下文碼rfC的計算。首先將區(qū)域中的面表達為圖Gr＝ （Vr，Er），Vr和Er分別對應于區(qū)域中面和邊的集合；接著根據(jù)vr的左右鄰接位置關系對圖頂點vr進行上下文編碼，如圖2所示。面上文碼由面頭碼f H和邊碼f Adj組成。f H和f Adj都是2位十進制數(shù)，它們的計算公式為：

其中，fT和fCon分別為面的幾何類型和面的凸性編碼，如平面f T＝0，圓柱面f T＝1，圓錐面f T＝2，球面f T＝3，其他面f T＝4，再如平面fCon＝0，凸面f Con＝1，凹面f Con＝2，其他面f Con＝3；f Tmin和f Tmax分別為邊的鄰接面幾何類型編碼的最小值和最大值；eCon為邊的凸性編碼，如直線邊eCon＝0，凸邊eCon＝1，凹邊eCon＝2。

圖2 區(qū)域中面上下文碼

對于圖Gr中任一頂點vr，圍繞vr將頂點集Vr分為m′層，vr本身為第0層，定義與vr最短路徑的頂點為k′，設k′所在的層為L k′（k′＝1，2，…，m′），則vr的上下文編碼為：

其中，Ck′為 6 位 十 進 制 整 數(shù)，f HL k′、fAdj I k′和f AdjO k′都為2位十進制整數(shù)；f H L k′和｜L k′｜分別為處于第k′層頂點編碼平均值和頂點的數(shù)量和；fAdj I k′和｜L k′－1×L k′｜分別為處于第k′－1層頂點與第k′層頂點之間的鄰接邊編碼平均值和鄰接邊數(shù)量和；fAdjOk′和｜Lk′×Lk′｜分別為處于第k′層頂點之間的鄰接邊編碼平均值和鄰接邊數(shù)量和。

圖2中，對于面f2和f4，第0層頂點編碼f H（v）＝00，第1層有2個頂點，它們的編碼值都為00，編碼平均值f HL1＝00，第0層與第1層頂點之間有2條鄰接邊，它們的編碼值都為25，編碼平均值fAdj I1＝25，第1層頂點之間只有1條鄰接邊，其編碼fAdjO1＝25，因此C1＝002525；第2層只有1個頂點，其編碼f HL2＝00，第1層與第2層頂點之間有2條鄰接邊，它們的編碼值都為25，編碼平均值fAdj I2＝25，第1層只有1個頂點，沒有鄰接邊，fAdjO2＝00，因此C2＝002500；沒有第3層，由此可以得到其面上下文碼為00002525002500。

2.2 區(qū)域鄰接關系屬性編碼計算

區(qū)域鄰接關系屬性編碼rAdj是一個2位十進制數(shù)，其計算公式為

其中，rConmax和rConmin分別表示邊的鄰接區(qū)域凸性編碼的最大值和最小值；reCon表示區(qū)域鄰接邊凸性，其計算公式為

其中，b0～b2分別代表直線邊、凸邊和凹邊。如果bi（i＝0～2）對應的邊類型存在，則bi的值為1；否則bi的值為0。

3 CAD模型局部搜索

本文中的CAD模型局部搜索是在模型區(qū)域特征匹配的基礎上進行的。區(qū)域特征匹配是指相比較的兩個CAD模型區(qū)域?qū)傩院蛥^(qū)域鄰接關系同時匹配。為滿足處于不同設計階段的同一用戶或不同用戶的不同模型搜索需求，本文的CAD模型區(qū)域特征匹配有普通和精確兩種模式：普通模式能返回更多不同相似度的相關模型，可滿足擁有搜索目標CAD模型結(jié)構(gòu)信息而沒有詳細幾何信息的用戶需求；精確模式返回的相關模型數(shù)量較少，可快速地定位用戶所需的搜索目標CAD模型，搜索結(jié)果較為準確，搜索效率較高。

3.1 區(qū)域?qū)傩院蛥^(qū)域鄰接關系屬性編碼分類統(tǒng)計

在考查相比較的CAD模型區(qū)域?qū)傩院蛥^(qū)域鄰接關系屬性是否匹配前，需要將搜索輸入和數(shù)據(jù)庫中CAD模型區(qū)域?qū)傩跃幋a和區(qū)域鄰接關系屬性編碼分類統(tǒng)計為如下形式：

其中，1≤a≤i，1≤e≤k，1≤c≤m，i為模型的區(qū)域特征數(shù)量；k和m分別為區(qū)域特征a的面上下文碼類型數(shù)量和區(qū)域鄰接關系屬性編碼類型數(shù)量。

3.2 區(qū)域?qū)傩云ヅ?/h3>

假定rHra為搜索輸入CAD模型pr的第a（1≤a≤i，i為pr的區(qū)域特征數(shù)量）個區(qū)域特征的區(qū)域?qū)傩灶^碼，rHob為搜索目標CAD模型po的第b（1≤b≤j，j為po的區(qū)域特征數(shù)量）個區(qū)域特征的區(qū)域?qū)傩灶^碼，它們對應的區(qū)域特征中面上下文碼分別統(tǒng)計為如下形式：

其中，1≤e≤k，1≤f≤l，k和l分別為區(qū)域特征a和b的 面 上 下 文 碼 類 型 數(shù) 量；rf CNrae和rf CNobf分別為rf Crae和rf Cobf的數(shù)量。

如果r Hra＝r Hob，對于區(qū)域特征a中每一個面上下文碼rf Crae，都能在區(qū)域特征b中找到相等的上下文碼rf Cobf，那么pr中的第a個區(qū)域?qū)傩耘cpo中的第b個區(qū)域?qū)傩栽谄胀Ｊ较缕ヅ?；如果在滿足上述條件的同時，且rf CNrae＝rf CNobf，那么pr中的第a個區(qū)域?qū)傩耘cpo中的第b個區(qū)域?qū)傩栽诰_模式下匹配。

3.3 區(qū)域鄰接關系屬性匹配

假定搜索輸入CAD模型pr的第a（1≤a≤i，i為pr的區(qū)域特征數(shù)量）個和搜索目標CAD模型po的第b（1≤b≤j，j為po的區(qū)域特征數(shù)量）個區(qū)域特征的區(qū)域鄰接關系屬性編碼分別統(tǒng)計為如下形式：

其中，1≤c≤m，1≤d≤n，m和n分別為區(qū)域特征a和b的區(qū)域?qū)傩脏徑雨P系編碼類型數(shù)量；rAdj Nrac和r Adj Nobd分別為r Adjrac和r Adjobd的數(shù)量。

如果對于pr的第a個區(qū)域特征的每一個區(qū)域鄰接關系屬性編碼rAdjrac，都能在po的第b個區(qū)域特征中找到相等的區(qū)域鄰接關系屬性編rAdjobd，那么pr中的第a個區(qū)域鄰接關系屬性與po中的第b個區(qū)域鄰接關系屬性在普通模式下匹配；如果在滿足上述條件的同時，且rAdj Nrac＝rAdj Nobd，那么pr中的第a個區(qū)域鄰接關系屬性與po中的第b個區(qū)域鄰接關系屬性在精確模式下匹配。

3.4 CAD模型區(qū)域特征匹配

如果搜索輸入CAD模型pr的第a個區(qū)域特征的區(qū)域?qū)傩院蛥^(qū)域鄰接關系屬性分別與搜索目標CAD模型po的第b個區(qū)域特征的區(qū)域?qū)傩院蛥^(qū)域鄰接關系屬性在普通模式下相匹配，那么pr的第a個區(qū)域特征與po的第b個區(qū)域特征在普通模式下匹配。相應地，上述屬性如在精確模式下相匹配，那么pr的第a個區(qū)域特征與po的第b個區(qū)域特征在精確模式下匹配。

4 實驗測試結(jié)果與分析

本文在Visual C＋＋，ACIS和 HOOPS環(huán)境下實現(xiàn)了基于區(qū)域特征分割的CAD模型搜索方法。實驗用數(shù)據(jù)庫中存放了450個CAD模型，這些模型大部分來自美國國家設計資源庫（National Design Repository Dataset）。實驗用微機CPU為Intel 3.0GHz，內(nèi)存為1.0GB。

為了驗證本文提出的基于區(qū)域特征分割的CAD模型搜索方法的有效性，隨機選擇了3個模型面數(shù)量分別為26、33和51，以及區(qū)域特征面數(shù)量分別為4、9和11的典型局部結(jié)構(gòu)，與文獻［7］中的CAD模型局部結(jié)構(gòu)搜索方法進行了搜索效果和效率的對比實驗，表1為實驗結(jié)果。從實驗結(jié)果可以看出，本文方法的搜索效率比文獻［7］方法的搜索效率高了很多，同時本文方法的普通模式能搜索到更多的具有不同相似度的相關CAD模型。由此可見，區(qū)域特征表征CAD模型具有較好的模型局部形狀辨識能力，而且搜索效率較高。

?

5 結(jié)語

由于用面屬性表征CAD模型結(jié)構(gòu)時沒有考慮CAD模型的形狀特點，故表達模型形狀時存在著局部形狀不突出、數(shù)據(jù)量較大和計算復雜度較高的問題。由此本文提出一種基于區(qū)域特征分割的CAD模型局部搜索方法。該方法依據(jù)機械零件模型具有形狀特征較為顯著、表面與表面之間分界較為明顯的特點，將其分割為具有一定工程意義的局部形狀集合，用分割得到的區(qū)域?qū)傩院蛥^(qū)域鄰接關系屬性表達模型的形狀特征，表達模型的數(shù)據(jù)量相對于模型的面、環(huán)和邊等信息的數(shù)據(jù)量大為減少。實驗結(jié)果表明，該方法能夠搜索到相關的CAD模型局部形狀，并且搜索效率和精準程度能夠滿足實際需要。其缺點是模型搜索前需要對其進行區(qū)域特征分割預處理。

［1］Tao S Q，Huang Z D，Zuo B Q，et al.Partial Retrieval of CAD Models Based on the Gradient Flows in Lie Group［J］.Pattern Recognition，2012，45（4）：1721－1738.

［2］Zhu K P，Wong Y S，Loh H T，et al.3D CAD Model Retrieval with Perturbed Laplacian Spectra［J］.Computers in Industry，2012，63（1）：1－11.

［3］Zhu K P，Wong Y S，Lu W F，et al.3D CAD Model Matching from 2D Local Invariant Features［J］.Computers in Industry，2012，63（5）：433－439.

［4］Li M，Zhang Y F，F(xiàn)uh J Y H，et al.Design Reusability Assessment for Effective CAD Model Retrieval and Reuse［J］.International Journal of Computer Applications in Technology，2011，40（1/2）：3－12.

［5］Bai J，Gao S M，Tang W H，et al.Design Reuse Oriented Partial Retrieval of CAD Model［J］.Computer－aided Design，2010，42（12）：1069－1084.

［6］Ming L，Zhang Y F，F(xiàn)uh J Y H，et al.Toward Effective Mechanical Design Reuse：CAD Model Retrieval Based on General and Partial Shapes［J］.ASME Journal of Mechanical Design，2009，131（12）：121501.1－121501.8.

［7］王飛，張樹生，白曉亮，等.基于子圖同構(gòu)的三維CAD模型局部匹配［J］.計算機輔助設計與圖形學學報，2008，20（8）：1078－1084.

Wang F，Zhang S S，Bai X L，et al.Local Matching of 3D CAD Models Based on Subgraph Isomorphism［J］.Journal of Computer－aided Design ＆ Computer Graphics，2008，20（8）：1078－1084.

［8］陶松橋，黃正東，鄭壇光.基于屬性鄰接圖匹配的三維CAD模型搜索方法［J］.計算機集成制造系統(tǒng)，2011，17（4）：680－687.

Tao S Q，Huang Z D，Zheng T G.3D CAD Model Retrieval Based on Attributed Adjacency Graph Matching［J］.Computer Integrated Manufacturing Systems，2011，17（4）：680－687.