三維工藝設計中的制造特征識別方法

黃豐云，劉小磊，徐勁力，劉偉騰

(武漢理工大學機電工程學院，湖北 武漢 430070)

1 引言

近年來，隨著三維CAD和基于模型定義(Model Based Definition，MBD)數字化制造技術的快速發展，傳統的二維工藝設計方法因其設計效率低、不可視、易出錯、不穩定等問題，已無法適應數字化發展的大環境，而基于MBD的三維工藝設計已成為數字化制造發展的新趨勢[1]。從零件設計MBD模型中提取工藝設計所需的制造特征信息是三維CAPP系統的基礎。制造特征識別是指以零件的設計MBD模型為基礎，自動識別出具有一定工程意義的幾何形狀，并將其轉變為可用于后續制造加工的特征[2]。目前，制造特征識別被廣泛認為是實現CAD/CAPP/CAM集成的關鍵技術。

特征識別方法主要分為四大類：基于屬性鄰接圖的方法，基于體積分解的方法、基于痕跡的方法以及混合識別方法。其中，基于屬性鄰接圖的方法是目前研究和應用較多的一種特征識別方法，其用屬性鄰接圖來表達零件設計模型的幾何/拓撲信息，并對屬性鄰接圖進行一系列的屬性分解，獲得一系列特征子圖，然后進行圖匹配識別。文獻[3-4]提出的基于圖分解的特征識別方法，屬性鄰接圖對零件模型信息表達不全面，特征識別過程中存在“二義性”。另一文獻[5]提出的圖與規則相結合的特征識別方法，能有效識別預定義特征，但其采用子圖同構的特征匹配策略，算法時間復雜度高，識別效率低。還有文獻[6]提出了虛相交的概念及多屬性定義的方法，克服了基于圖的特征識別方法不擅長識別相交特征的缺點，實現了部分相交特征的識別，但是圖分解復雜，不易實現。

針對上述幾種特征識別方法中特征表達二義性及識別效率低下的問題，提出一種基于擴展屬性鄰接圖和圖同構的制造特征識別方法，在對屬性鄰接圖中面、邊屬性進行擴展的基礎上，定義了擴展屬性鄰接圖，接著對其屬性分解得到擴展特征子圖，與預定義特征庫中的特征原型屬性鄰接圖進行圖同構的特征匹配，實現特征識別，并最后進行了示例驗證。

2 制造特征識別流程

首先提取零件設計MBD模型的幾何/拓撲信息，構建擴展屬性鄰接圖，然后將擴展屬性鄰接圖進行屬性分解獲得擴展特征子圖，最后再與預定義特征庫中的特征原型屬性鄰接圖進行同構匹配，匹配成功，完成特征識別，否則將該特征作為孤立特征添加到預定義特征庫中，擴展預定義特征庫。

圖1 制造特征識別流程Fig.1 Process of Manufacturing Feature Recognition

3 擴展屬性鄰接圖EAAG的創建

3.1 幾何/拓撲信息的提取

零件設計MBD模型上幾何/拓撲信息的提取是擴展屬性鄰接圖創建的前提。NX軟件是以基于STEP/AP203協議的擴展邊界表示法(B_Rep)為基礎，對實體模型進行描述的，所以可通過NX軟件提供的二次開發接口NX/Open API所封裝的NX操作函數來直接查詢提取幾何/拓撲信息。

其中，幾何信息描述的是設計MBD模型上點(Point)、線(Curve)、面(Surface)等幾何元素大小、形狀和位置的基本信息，其相關查詢函數，如表1所示。拓撲信息描述的是設計MBD模型上頂點(Vertex)、邊(Edge)、翼(Fin)、環(Loop)、面(Face)、殼(Shell)和體(Solid)等拓撲元素的數量及連接等拓撲關系，這些信息通過詢函數UF_BREP_ask_topology()來提取。最終將幾何/拓撲信息并以Solid-Shell-Face-Loop-Fin-Edge-Vertex的層次關系保存在拓撲信息查詢函數的輸出參數UF_BREP_topology_t結構中[7]。

表1 幾何信息查詢函數Tab.1 Geometry Information Query Function

3.2 屬性鄰接圖AAG及鄰接矩陣AAM的擴展

傳統的屬性鄰接圖(Attributed Adjacency Graph，AAG)中表達了模型中面與邊的拓撲結構以及邊的凹凸性屬性，而這些信息并不能滿足復雜相交特征識別的需求，因此需對AAG進行屬性擴展。在原有AAG的基礎上，對面和邊的屬性進行了擴展，即定義擴展屬性鄰接圖(Extended Attributed Adjacency Graph，EAAG)來全面表達零件模型信息，避免表達的二義性。擴展之后的EAAG中面、邊屬性，如表2所示。

表2 EAAG中面、邊屬性Tab.2 Attributes of Face and Edge in EAAG

同時，傳統的屬性鄰接矩陣(Attribute Adjacency Matrix，AAM)的元素位數只有一位，使得對零件幾何/拓撲特征信息的表達出現歧義。為了解決屬性鄰接矩陣在表達零件信息時的“二義性”，特將其中面的類型，邊的類型及凹凸性等屬性，用屬性鄰接矩陣來表達，即對屬性鄰接矩陣進行擴展，擴展之后的擴展屬性鄰接矩陣(Extended Attributed Adjacency Matrix，EAAM)中的元素A[i，j]將由四位數字組成，定義如下：

式中：Xij—擴展屬性鄰接矩陣中鄰接邊的凹凸性屬性值；Yij—鄰接邊的類型屬性值；Zi、Zj—相鄰面Fi與Fj的類型屬性值。

(1)邊的凹凸性屬性定義。鄰接邊的凹凸性屬性值Xij的計算如式(2)所示。

(2)邊的類型屬性定義。在原屬性鄰接矩陣元素的基礎上增加一位，用A[i，j]十位上的數字來描述相鄰面的公共邊的類型屬性，具體定義，如表3所示。當面Fi與Fj不相鄰或i=j時，A[i，j]=0；當面Fi與Fj相鄰的時候，A[i，j]=YijXij。

表3 EAAM中邊的類型屬性定義Tab.3 Type Attribute Definition of Edge in EAAM

(3)面的類型屬性定義。在原屬性鄰接矩陣元素的基礎上再增加一位，用A[i，j]百位上的數字來描述相鄰面的類型屬性，具體定義，如表4所示。當面Fi與Fj不相鄰時，A[i，j]=0；當i=j時，A[i，j]=Zi；當面Fi與Fj相鄰的時候，A[i，j]=ZiZjYijXij。

表4 EAAM中面的類型屬性定義Tab.4 Type Attribute Definition of Face in EAAM

3.3 擴展屬性鄰接圖EAAG的創建

經過零件設計MBD模型幾何/拓撲信息提取，及其面和邊的屬性判定之后[8]，緊接著進行擴展屬性鄰接圖EAAG的構建。提取出的零件設計MBD模型的幾何/拓撲信息保存在UF_BREP_topology_t結構中。UF_BREP_topology_t結構是一個樹形結構，可采用深度或廣度優先算法遍歷得到任意Solid、Shell、Face、Loop、Fin、Edge、Vertex的幾何/拓撲結構信息和tag_t標識符。因此，建立擴展屬性鄰接圖的過程如下：

(1)從根節點開始遍歷UF_BREP_topology_t結構，根據Solid-Shell-Face的層次順序依次提取每個面Fi，建立頂點數組VertexArray[1...n]與EAAG中的頂點vi對應，同時提取面Fi的屬性值作為其對應EAAG中頂點vi的屬性值；

(2)根據Face-Loop-Edge的層次順序依次提取每個面Fi中的每條邊Ej，建立鄰接邊數組EdgeArray［1...m］與EAAG中的鄰接邊ej對應，同時提取邊Ej的屬性值作為其對應EAAG中鄰接邊ej的屬性值；

(3)搜索包含邊Ej的面Fj和Fj，建立頂點VertexArray［i］、VertexArray［j］與鄰接邊EdgeArray［i］之間的鄰接關聯。重復以上步驟，則可形成完整的擴展屬性鄰接圖EAAG。某機加工零件的擴展屬性鄰接圖EAAG，如圖2所示。

圖2 某機加工零件的三維模型及其擴展屬性鄰接圖Fig.2 3D Model and EAAG of the Machining Part

4 擴展屬性鄰接圖EAAG的屬性分解

零件設計MBD模型的EAAG創建完成之后，就可以對其進行屬性分解，獲得能與預定義特征庫中特征原型屬性鄰接圖(Prototype Attributed Adjacency Graph，PAAG)直接進行圖同構匹配的擴展特征子圖(Extended Feature Subgraph，EFSG)。具體的分解步驟如下：

(1)根據零件設計MBD模型中對各加工面的設計要求，識別出EAAG的非加工面(毛坯面)及過渡特征面，并將這些面的節點及其相鄰邊從EAAG中移除，將零件模型的EAAG第一次分解為m個只包含加工面的節點及其鄰接邊的加工面屬性鄰接圖的集合MFAG［i］(1≤i≤m)。將MFAG集合中的每個子集MFAG［i］與預定義特征庫中的特征原型屬性鄰接圖PAAG進行圖同構的特征匹配，若匹配成功，則表明其為孤立特征，屬性分解結束；若匹配不成功，則表明其為相交特征，MFAG[i]需繼續進行分解，轉步驟(2)。

(2)遍歷子集MFAG[i]中每一個加工面的屬性信息，判斷面內是否存在內環，若某一面內存在，則將該面標記為分解基準面，并將內環(邊)從MFAG[i]中刪除，將MFAG[i]第二次分解為n個新的加工面屬性鄰接圖(New Manufacturing Face Adjacency Graph，NMFAG)的 集 合NMFAG[s](1≤s≤n)。將NMFAG[s]與PAAG進行圖同構的特征匹配，若匹配成功，屬性分解結束；否則，NMFAG[s]需繼續進行分解，轉步驟(3)。

(3)遍歷子集NMFAG[s]中每一個加工面的屬性信息，判斷是否存在凸面，若存在則將該面的相鄰邊從NMFAG［s］中刪除，將NMFAG［s］第三次分解為k個凹面子圖(Concave Face Subgraph，CFSG)的集合CFSG[t](1≤t≤k)。再將CFSG［t］與PAAG進行圖同構的特征匹配，若匹配成功，屬性分解結束；否則，CFSG[t]需繼續進行分解，轉步驟(4)。

(4)遍歷子集CFSG[t]中每一條邊的屬性信息，判斷是否存在凸鄰接(凸邊或凸切邊)，若存在則提取互為凹鄰接的面及其相鄰邊組成p個擴展特征子圖(Extended Feature Subgraph，EFSG)的集合EFSG[q](1≤q≤p)。再將EFSG[q]與PAAG進行圖同構的特征匹配，若匹配成功，屬性分解結束；否則，將EFSG[q]作為某類孤立特征的原型屬性鄰接圖存儲到預定義特征庫中，擴展預定義特征庫以便日后識別。

對圖2所示的機加工零件進行上述的屬性分解，生成的擴展特征子圖EFSG，如圖3所示。

圖3 EAAG的屬性分解結果Fig.3 Decomposition Results of EAAG

5 制造特征匹配

5.1 預定義特征庫的建立

將擴展屬性鄰接圖EAAG經過四次屬性分解，分解為可以與預定義特征庫中特征原型屬性鄰接圖PAAG直接進行特征匹配的擴展特征子圖EFSG，至此，制造特征識別問題就轉變為EFSG與特征原型屬性鄰接圖PAAG匹配的問題。制造特征能否有效地識別出來，很大程度上取決于預定義特征庫中是否包含該類制造特征，即制造特征原型屬性鄰接圖PAAG是否保存至預定義特征數據庫中。因此，需要在特征識別之前創建用于與擴展特征子圖EFSG進行匹配的制造特征原型屬性鄰接圖PAAG，也就是預定義特征庫的建立。通過大量的實例分析，得出機加工零件中幾種典型的制造特征原型，如表5所示。

表5 預定義特征庫中的特征原型Tab.5 Feature Prototype in Predefined Feature Library

5.2 基于圖同構的特征匹配

圖同構的常見定義為：對于給定的兩個圖Gα=(Vα，Eα)和Gβ=(Vβ，Eβ)，其 中Vα={vα1，vα2，…，vαm}是 圖Gα的 頂 點集合，

Eα={(μα，vα)|μα，vα∈Vα}是 圖Gα的 邊 的 集 合 ；Vβ={vβ1，vβ2，…，vβn}是圖Gβ的頂點集合，Eβ={(μβ，vβ)|μβ，vβ∈Vβ}是圖Gβ的邊的集合。對于任意給定的Vαi、Vαj∈Vα，若存在映射f，使 得，Vβs、Vβt∈Vβ，且 若(Vαi、Vαj)∈Eα，(Vβs、Vβt)∈Eβ，那么就定義圖Gα與Gβ是同構的[9]。

假設存在兩個待匹配的圖Gα和Gβ，圖Gα和Gβ的頂點集合、頂點數、擴展屬性鄰接矩陣分別為Vα、m、Mα和Vβ、n、Mβ。根據圖同構的定義，若圖Gα和Gβ同構，則必有頂點數m=n，統一計為m。因此，定義映射矩陣M是m維方陣，映射矩陣M的行表示圖Gα中的頂點，列表示圖Gβ中的頂點，映射矩陣M中的值Mij(0≤i≤m-1，0≤j≤m-1)表示兩圖任意頂點的對應關系，若圖Gα的頂點vαi與Gβ圖的頂點vβj對應，則Mij=1；否則，Mij=0。

其中，圖Gα的頂點vαi與Gβ圖的頂點vβj對應，表示為擴展屬性鄰接矩陣Mα、Mβ的各行元素的對應。因此，映射矩陣M可通過依次遍歷其對應的擴展屬性鄰接矩陣Mα、Mβ的各行元素來確定，若矩陣Mα第i行元素集合Mαis(0≤s≤m-1)和矩陣Mβ第j行元素集合Mβjt(0≤t≤m-1)相等，則Mij=1，否則，Mij=0。根據數學證明，如果Gα和Gβ的映射矩陣M是一個每行和每列均有且只有一個元素“1”，其余均為元素“0”的方陣，則該方陣就是映射方陣f，則可判定圖Gα和Gβ同構。

6 示例驗證

根據上述制造特征識別方法，基于Visual Studio 2012和NX10.0開發平臺，利用NX/Open開發工具及C++語言，開發了一個集成化的制造特征識別功能模塊。該功能模塊可以實現零件設計模型幾何/拓撲信息的提取、制造特征識別及特征關聯的非幾何信息的提取。如圖4所示，首先是設計模型的導入與修改，抑制模型中的過渡特征，接著提取零件設計模型中的幾何/拓撲信息，并根據Solid-Shell-Face-Loop-Fin-Edge-Vertex的層次關系以樹列表的形式展現。然后，根據上述基于擴展屬性鄰接圖及圖同構的特征識別算法，快速真確地識別出模型中的單獨平面、圓通孔、通臺階、盲臺階、鍵槽及其矩形凹槽等特征，并且提取出各特征關聯的非幾何信息(尺寸及公差、表面粗糙度等)，如圖5所示。最終將特征信息以XML文件的形式保存，創建特征信息庫，為以后的三維工藝設計提供制造特征信息。

圖4 幾何/拓撲信息提取界面Fig.4 Interface of Geometric/Topological Information Extraction

圖5 特征識別與信息提取界面Fig.5 Interface of Feature Recognition and Information Extraction

7 結論

針對基于屬性鄰接圖的制造特征識別方法的不足，提出了一種基于擴展屬性鄰接圖和圖同構的制造特征識別方法，該方法全面地表達了零件設計MBD模型信息，并創建了信息表達更為完整的擴展屬性鄰接圖和擴展屬性鄰接矩陣。在此基礎上，對擴展屬性鄰接圖進行屬性分解，分離出可與預定義特征庫中的特征原型屬性鄰接圖進行同構匹配的擴展特征子圖。接著將圖同構的問題轉變為映射矩陣的計算及其特性判定問題，最終實現了各相交特征的識別。該特征識別方法提高了特征識別的準確性，同時大大降低了同構算法的時間復雜度，提高了特征識別效率，為三維工藝設計和CAD/CAPP/CAM的集成打下基礎。