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

陶松橋 黃正東 馬露杰

1.武漢理工大學(xué)，武漢，430070

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

3.華中科技大學(xué)，武漢，430074

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

0 引言

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

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

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

1.1 相關(guān)術(shù)語和定義

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

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

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

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

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

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

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

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

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

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

接著進(jìn)行的區(qū)域特征優(yōu)化是通過遞歸合并相鄰的區(qū)域特征來減少區(qū)域特征數(shù)量。相鄰區(qū)域特征可合并條件是合并后得到的新區(qū)域特征仍是一個凸區(qū)域、凹區(qū)域或平區(qū)域。對于一個區(qū)域特征，可能存在多種可合并操作情況，但只存在一個最大可合并區(qū)域特征。區(qū)域特征優(yōu)化過程中的所有可合并操作可以用樹來表達(dá)，為了得到最大可合并區(qū)域特征，需要搜索樹上的每一個分支。但是當(dāng)樹的分支數(shù)量較多時，其搜索效率將十分低下。為提高計算效率，本文采用貪心搜索算法，從每個分支中選擇最優(yōu)的分支作為下次搜索的起點(diǎn)。圖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位十進(jìn)制數(shù)，其計算公式為

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

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

（2）區(qū)域中面上下文碼rfC的計算。首先將區(qū)域中的面表達(dá)為圖Gr＝ （Vr，Er），Vr和Er分別對應(yīng)于區(qū)域中面和邊的集合；接著根據(jù)vr的左右鄰接位置關(guān)系對圖頂點(diǎn)vr進(jìn)行上下文編碼，如圖2所示。面上文碼由面頭碼f H和邊碼f Adj組成。f H和f Adj都是2位十進(jìn)制數(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中任一頂點(diǎn)vr，圍繞vr將頂點(diǎn)集Vr分為m′層，vr本身為第0層，定義與vr最短路徑的頂點(diǎn)為k′，設(shè)k′所在的層為L k′（k′＝1，2，…，m′），則vr的上下文編碼為：

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

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

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

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

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

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

3 CAD模型局部搜索

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

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

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

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

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

假定rHra為搜索輸入CAD模型pr的第a（1≤a≤i，i為pr的區(qū)域特征數(shù)量）個區(qū)域特征的區(qū)域?qū)傩灶^碼，rHob為搜索目標(biāo)CAD模型po的第b（1≤b≤j，j為po的區(qū)域特征數(shù)量）個區(qū)域特征的區(qū)域?qū)傩灶^碼，它們對應(yīng)的區(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ū)傩栽谄胀Ｊ较缕ヅ洌蝗绻跐M足上述條件的同時，且rf CNrae＝rf CNobf，那么pr中的第a個區(qū)域?qū)傩耘cpo中的第b個區(qū)域?qū)傩栽诰_模式下匹配。

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

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

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

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

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

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

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

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

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

?

5 結(jié)語

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

［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］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，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］.計算機(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.