基于子圖同構的三維CAD 模型局部匹配探討

李倩

摘要：為了有效解決結構匹配無法精確實施的問題，該文將從子圖同構原理出發對三維CAD模型局部結構匹配算法進行探索。在該算法中通過對CAD模型的B-Rep信息的提取，用以面作為節點的屬性連接圖將其展現出來。局部匹配過程中用子圖表示用戶輸入的局部結構，用大圖表示帶匹配的整體CAD模型。這樣就可以通過尋找大圖中同構子圖解決檢索局部結構的問題。根據CAD模型的面特征細分圖頂點，并利用已匹配點之間的臨界關系對搜索空間進行動態剪裁，這樣同構匹配的迅速就會大大增加。

關鍵詞：子圖同構；三維CAD模型；局部匹配

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2016）13-0179-02

現階段產品設計、產品制造、產品虛擬仿真等機械設計和制造環節中已經廣泛運用了三維建模軟件，這樣企業內容的三維CAD模型數量就會迅速增加。設計人員在工作中常常需要參照企業已有模型進行新產品設計，通過相似形設計或改型設計能夠有效帶動設計效率的提升。然而，對于一些大型制造企業而言，由于具備龐大數量的CAD模型，怎樣讓設計人員從中找到所需要的模型就成為另一個必須解決的問題，本文將嘗試通過三維模型檢索解決這個問題。

1 CAD模型局部匹配總體思路

實際中，完全自動識別出直接給定任意的兩個三維CAD模型相思局部結構還存在一定難度，但是還沒有較好的方法能夠解決這個問題，并且這樣的需求在實際應用CAD領域還相對較少。相反設計人員在設計的過程中，往往非常關注零件上某一個局部結構，進而將具備該局部結構零件從已有產品模型中各發掘出來，并依次為依據和參考。這樣設計人員就能夠檢索自己感興趣的局部結構，一般通過以下兩種方式輸入：將已有CAD模型直接打開，然后拾取局部結構的多個面；利用建模工具對局部結構進行完全自定義。

為了實現局部匹配的目標，首先需要對屬性鄰接圖進行設計，并對CAD模型中B-Rep信息進行提取，這樣就能夠用一個屬性鄰接圖表示CAD模型。通過提取已經輸入的局部結構B-Rep信息，就能夠產生小屬性鄰接圖，該圖作為“子圖”。同時還應當提取待匹配的模型庫中的每一個整體三維CAD模型，這樣就能夠獲得一個大屬性鄰接圖，這樣通過在大圖中尋找子圖就能夠解決在整體三維CAD模型中檢索制定局部結構的問題。

2 構建屬性鄰接圖

由于多媒體可視化模型具有較低的精度要求，所以通過三維網絡模型近似表示即可。但CAD具有較高的精度要求，所以在表示過程中通常運用B-Rep模型。B-Rep模型中的一個三維CAD模型包括n各三維空間曲面，多條邊圍成每個曲面，每個頂點確定每條邊。通過對每個頂點、每條邊、每個曲面的精確描述，整個三維CAD模型就能夠準確的反映出來。通過將三維CAD模型中B-Rep信息轉化為屬性鄰接圖，其中每一個模型的面都存在對應圖頂點，頂點具有面的幾何屬性。頂點之間的關系反映與模型中的面之間的關系，共面、垂直、平行、供邊等是常見的關系。

3 局部匹配

1）圖同構概述

看兩個圖之間是否存在一個映射是判斷兩個圖是否同構的關鍵，這樣兩個圖之間對應的不僅包括點還包括邊。當前圖同構問題計算還較為復雜，但是已經證明子圖同構問題是一個NP問題，實際中包含四種求解方法，其中提出時間最長、且應用最廣泛的就是ullmann算法。由CAD模型轉換得到的一種特定的屬性鄰接圖是本文研究的對象，所以必須充分運用CAD模型自身特征進行子圖同構匹配算法的設計，進而推動算法匹配效率的提升[1]。

2）子圖同構匹配算法思路

為了達到降低搜索空間雜復程度的目的，應當通過先驗知識的運用盡可能增加M元素為0的個數，這樣就需要細分圖的頂點。實際當中從一定規則出發將圖的頂點劃分為若干個子集就是頂點細分，在同構中不可能匹配不同子集的頂點?？梢姴豢赡艿捻旤c對應關系通過有效的定點細分，在一開始就能夠得到有效的排除。本文算法在細分圖的頂點時，主要考慮的是CAD模型的面的特征。CAD模型的面與CAD模型轉換得到的屬性鄰接圖頂點存在一一對應的關系，因此在進行頂點細分時可以運用CAD模型面的特征。

3）算法分析

因為子圖同構的本質是NP完全問題，所以相應的都是復雜度高的求解算法，并且還具有算法性能不穩定的弊端。為了實現提升匹配效率，本文從兩個方面進行了優化：首先在進行細分圖頂點過程中充分的結合和考慮了CAD模型面的特征；在進行快速的剪枝搜索中運用已匹配上的頂點所組成的子圖對應同構這一原理。屬性鄰接圖是本文研究的對象，主要通過轉化三維CAD模型的面后獲得。應當以頂點對應模型的面的類型和面的特征出發，細分圖頂點，這樣初始時矩陣元素等于0的數量就會增加，搜索空間復雜程度相應的就會降低[2]。

4 試驗及結果分析

為了在CAD模型局部檢索中驗證本算法的效果，本文進行了局部結構庫和三維CAD模型庫的構建。其中，三維CAD模型庫中包含四百多個典型CAD模型，例如箱類、軸類、盤類等，這些模型具有不同的復雜程度，所具備的面數也在幾個至幾百個之間。局部結構庫中既包含由幾個面構成的孔、槽，也包括由數十個面構成的用戶自定義結構，共囊括八十個典型結構。本文針對該模型和局部結構庫的試驗包括三個方面。

實驗一。當待檢索局部結構具有一定數量的面時，對待匹配的整體三維CAD模型的面數量進行調整，對匹配所需時間進行測量。研究整體三維CAD模型復雜度的增長匹配時間帶來的影響是進行這項實驗的目的，根據圖1可知實驗結果，其中整體三維CAD模型面的數量通過橫軸表示，匹配所需時間t通過縱軸表示。局部結構面的個數、也就是圖頂點個數表示為m，根據圖1a可知如果整體三維CAD模型面數量控制在一定范圍內，那么匹配時間t和面的數量之間體現為線性關系[3]。

實驗二。當待匹配整體三維CAD模型具有確定數量的面時，對檢索局部結構的面數量記性調整，進而測量匹配時間，研究局部結構復雜度的增長給匹配時間造成的影響是該項試驗的目的。圖1a為實驗結果，其中局部結構面的數量由橫軸表示，匹配所需時間由縱軸表示。整體三維CAD模型面的個數也就是大圖頂點的個數由n表示。根據圖1b可知，如果三維CAD模型面的數量不超過200時，局部結構復雜度和匹配時間存在線性關系。如果三維CAD模型面數量大于400時，局部結構越復雜匹配時間增長幅度越大[4]。

實驗三。以試驗一、二維基礎，對比試驗最著名的Ullmann算法和本文算法，兩種算法的綜合性能比較如下。如圖1c、1d為試驗結果，其中相同條件下Ullmann算法匹配時間與本文算法匹配時間的比表示為縱軸r。通過圖1a、1c可知，本算法和ullmann算法在n和m較小的情況下具有相同的效率，但是本算法在n和m較大的情況下具有比ullmann算法更高的效率。例如在m=40、n=400時，ullmann算法完成一次匹配使用的時間，本文算法能夠實現三百次匹配[5]。

5 結論

本文中的支持局部匹配的三維CAD模型檢索算法，不同于基于統計特征提取的檢索算法，它首先用屬性鄰接圖替代CAD模型，然后用子圖同構問題替代局部結構匹配問題。在對子圖同構匹配算法進行設計時，首先根據CAD模型面的特征預先細分屬性鄰接圖的頂點，這樣初始搜索空間復雜度就會大幅降低。在進行動態搜索的過程中，應當以匹配上的頂點對組成的子圖應對應同構這一原理出發，將不可能對應關系盡早排除掉，搜索進程就能夠大幅提升，最終達到提升匹配迅速的目的。根據實驗結果可知，精確的局部結構匹配能夠通過這種算法得到有效實現，同時實際檢索需求也能夠得到充分滿足。

參考文獻：

[1] 王飛，張樹生，白曉亮，等.基于子圖同構的三維CAD模型局部匹配[J].計算機輔助設計與圖形學學報，2012，20（8）：1078-1084.

[2] 王成，張樹生，張開興等.基于回轉面歸并的CAD模型局部檢索算法[J].微處理機，2011，32（5）：53-57.

[3] 鄭壇光.三維CAD模型檢索技術研究[J].華中科技大學報2011，32（5）：3-7.

[4] 王洪申，張樹生，白曉亮等.三維CAD模型局部結構檢索屬性圖算法[J].計算機輔助設計與圖形學學報，2012，20（3）：316-320.

[5] 陶松橋.面向設計的三維CAD模型搜索技術研究[J].華中科技大學報，2012，20（3）：16-20.