采用圖分解的特征識別算法研究

劉曉平， 吳 敏， 金 燦

（合肥工業大學計算機與信息學院，安徽 合肥 230009）

CAD/CAE/CAM從現代工業體系來看是一個密不可分的整體。CAD用于產品的設計，CAE對CAD設計的產品進行優化，CAM根據CAE優化的結果進行制造。其中，CAD是基礎，CAE是保障，CAM是應用，三者密不可分。尤其是CAD跟CAE聯系相當緊密。但是，由CAD建造的模型往往不能夠直接用來進行CAE分析，這是由于CAD建造的模型存在一些諸如細小特征和高曲率特征一類的復雜特征，會顯著增加網格劃分的單元數量，從而消耗大量的計算資源，甚至導致計算結果出錯。在這些復雜特征中，有些特征的存在與否對計算結果影響不大，因此在CAE分析之前，如果識別出CAD模型中的細小特征和高曲率特征，分析這些特征的刪除或替換對計算結果的影響程度，生成一個模型的對應誤差程度的若干模型態[1]，并依此制定特征抑制方案，就可以大量節省計算資源，有效提高計算效率。而特征識別技術是一切工作的技術基礎。

自動特征識別技術從上個世紀80年代首次提出[2]，至今已取得了很大的成果。基于圖的特征識別方法是目前主要的特征識別方法之一，它通過圖結構來描述特征的幾何及拓撲信息，并在零件的圖結構中搜索匹配特征子圖來達到識別特征的目的。文獻[3]提出了一種基于圖的特征識別方法，用包含相關拓撲和幾何屬性的面邊鄰接圖表示用戶定義特征，再在對應的零件鄰接圖中搜索相似子圖。該方法雖然克服了基于圖的特征識別不擅長處理相交特征的弱點，提出了虛相交及多屬性的方法，解決了一些相交特征的識別。文獻[4]結合基于痕跡的和基于圖的特征識別方法，先對屬性鄰接圖進行分解，再將特征圖與每個子圖進行匹配，可以有效地降低子圖匹配的算法復雜度。但是，目前主流的特征識別算法識別出的特征多由面集表示，抑制操作復雜度高。如果以三維實體來表示特征，則可以大大地方便特征的刪除和替換。同時，在面向分析的特征識別中關注的是如何將模型分解為最簡單元，盡量保證同一單元具有相近的網格劃分屬性，如網格直徑等，以方便衡量計算誤差和計算時間。因此，如何可以更好地將模型分解為最簡單元，是CAD/CAE集成系統中特征識別的關鍵問題。

本文提出基于屬性鄰接圖分解的方法實現特征識別，以完成對模型的分解。該方法不再局限于特征類型，只要合理控制頂點的可分解性判斷則可以得到期望的模型分解結果。同時該方法可以將特征識別為實體，方便了特征刪除和替換操作，以完成模型的簡化。

1 圖分解準則

1.1 相關定義

定義1特征是模型分解之后的最小單元，其滿足以下條件之一：

（1）體積小于一定的閾值；

（2）包含曲率大于一定閾值的曲面。

定義2若面f1和f2具有相同曲面方程，但是被劃分為不相鄰的部分，則稱f1和f2為Co-defined面[3]。

如圖1所示，其中面F1、F1′為Co-defined面。

定義3在模型的屬性鄰接圖分解之后，如果有些面所對應的頂點存在于兩個或兩個以上的連通分量中，這樣的面稱為特征分解面。

定義4對于屬性鄰接圖中頂點v及其相鄰的所有頂點集合V_adjacent，v與集合V_adjacent中每個頂點對應的曲面方程的交線集合V_curves。按照鄰接順序將曲線之間求交點，若這些曲線首尾相連，則稱這些曲線集合為環。

基于上述定義，如果一個頂點有兩個或兩個以上的環，那么該頂點所對應的面為特征分解面，該頂點為可分解頂點。本文提出的基于圖分解的特征識別算法均基于此前提。

圖1 Co-defined面

1.2 屬性鄰接圖（AAG）

要進行特征識別，首先要根據將B-Rep表示的三維模型形成面邊鄰接圖，其中模型的面對應圖中的節點，邊對應圖中的弧。在面邊鄰接圖的基礎上，將模型的幾何或拓撲屬性添加到相應的弧和頂點上，則形成屬性鄰接圖，如圖2所示。

圖2 屬性鄰接圖

為了方便頂點的可分解性判斷及體特征生成，在AAG中添加以下屬性。

（1）弧的屬性

· 所對應邊的幾何信息，包括邊的端點及相應曲線方程，用于分解之后連通分量生成體特征。

· 邊的凹凸性，用于輔助判斷邊所在的面的外法向，其判斷方法參考文獻[5]。

（2）頂點的屬性

· 所對應面的幾何信息，即面的方程，用于分解之后連通分量生成體特征。

· 所對應面的環的數目，以判斷頂點是否可以分解。

· 所對應面包含的環的集合，在圖分解時作為依據，根據環的具體情況確定頂點復制數目并完成弧的連接。

· 分解方向，即未分解（0）、正向（1）、負向(-1)。如果某頂點還沒有分解，或者不能夠被分解則記為未分解（0）；如果分解之后，該頂點的拷貝對象對應的環為內環，則記為負向（-1），表示該頂點所相連的面的原法向需要修改；否則記為正向（1），表示面的原法向不必修改。

2 基于圖分解的特征識別算法

2.1 算法流程

基于圖分解的特征識別算法流程為：根據頂點分解準則對屬性鄰接圖進行分解，以完成模型的分解。其步驟如下：

Step 1化簡初始屬性鄰接圖，合并其中Co-defined Faces頂點；

Step 2對化簡后的屬性鄰接圖，判斷每個頂點是否可分解，若可分解則按照分解規則分解每個頂點；

Step 3當所有頂點都分解之后，判斷最終屬性鄰接圖包含連通分量的數量，將每個連通分量生成體單元，對于每個體單元根據設置的特征閾值判斷其是否為特征。

下面將對這3個步驟分開詳細闡述。

2.2 屬性鄰接圖的化簡

在模型中，有些面具有相同的幾何方程，但被特征劃分為不相連的幾個部分，因此具有不同的拓撲結構，即 Co-defined 面。在對屬性鄰接圖進行分解之前，需要將Co-defined面對應的頂點合并。

合并步驟如下：

Step 1找出Co-defined面集合FS；

Step 2對集合FS中的每個面，找出其在面邊鄰接圖中的頂點，在其與原圖中其余頂點鄰接點之間添加一條邊，再刪除其余頂點。圖3為圖1中的槽特征中的Co-defined面處理前后的屬性鄰接圖對比。

圖3 Co-defined面頂點合并

2.3 頂點可分解性判斷及分解

對于每一頂點v按照以下步驟執行：

Step 1求該頂點所包含的環：

（1）對于頂點v，獲得其相鄰頂點集合V_adjacent；

（2）根據鄰接信息查找V_adjacent集合中的所包含的環，并記錄環及環的數目。

Step 2若環的數目大于1，且存在內環，則執行Step 3，否則結束；

Step 3根據環分解頂點：

（1）將頂點v復制m份添加到屬性鄰接圖中，其中m為頂點v所包含的環的數目；

（2）對于v所包含的每一個環，分配一個v的拷貝v′，并將L中邊所對應的弧原先指向頂點v的改為指向v′；

（3）刪除頂點v。

在對屬性鄰接圖中每一定點v執行以上操作后，在將屬性鄰接圖劃分為若干個子連通分量，如圖4所示，是對圖3中化簡之后的槽的屬性鄰接圖頂點分解之后的結果。

圖4 頂點分解示意

2.4 體特征的生成算法

完成屬性鄰接圖的分解之后，獲得了對應每一單元的屬性鄰接圖，在此基礎上生成對應的體特征。文獻[6]中提出通過面延伸生成體特征方法，但是只處理了特征表面為平面的情況，沒有涉及面與面之間的鄰接關系。這里根據屬性鄰接圖，利用面的鄰接關系，通過延伸必要的面生成體，再根據設定的閾值判斷所生成的體是否為特征。對于分解之后的屬性鄰接圖中的每個連通分量進行以下操作：

Step 1找出屬性鄰接圖中分解生成的所有頂點，對其中的每個頂點v，修改其所對應的曲面的邊界。

Step 2確定每個面的方向。

Step 3根據已有的點、線、面生成Brep表示的三維模型。

Step 4判斷所生成的體是否滿足特征的條件（體積閾值和曲率閾值）；若滿足作為特征。

3 實 例

如圖5所示，本節以文獻[7]中給出的計算LOD的模型為例。針對此種模型可分解為13個最簡單元，其中特征1～8（小圓柱）滿足特征條件（1）、體積很小；特征9（中間圓孔）滿足特征條件（2）包含高曲率曲面。模型中其他部分保存在基座中。由于特征識別的目的是為了替換，程序中僅僅是將最后生成的體特征保存，作為模型的屬性，并沒有顯示出來。

4 結 束 語

針對CAD/CAE模型轉換與CAD/CAM轉換的區別，提出了基于圖分解的特征識別算法。依據頂點分解準則，判斷頂點的可分解性，并對屬性鄰接圖進行分解，再針對分解之后的屬性鄰接圖中的每個連通分量生成體特征。該算法不局限于特征類型，可以識別出常見的加工特征，如槽、孔等，只要合理控制頂點的可分解性判斷則可以得到期望的模型分解結果，識別出更多的特征。同時該方法識別出的為體特征，與用面集表示的特征相比，在特征抑制時，可以在特征這一較高層次[6]上方便地進行特征刪除和替換以完成模型的簡化。

該方法依然存在一些問題，如屬性鄰接圖到體映射存在一定的不確定性。同時，對于相交特征的分解進行更深入的思考是下一步工作的目標。

圖5 實例

[1]劉曉平, 金 燦, 李書杰. 有限元仿真軟件中建模的多態機理研究[J]. 系統仿真學報, 2007, 19(3):538-542.

[2]Corney J, Hayes C, Sundararajan V, et al. The CAD/CAM interface: a 25-year retrospective [J].Journal of Computing and Information Science in Engineering (Transactions of the ASME), 2005, 5(33):188-197.

[3]Venkataraman S, Sohoni M, Kulkarni V. A graphbased framework for feature recognition[C]//6th ACM Symposium on Solid Modeling and Applications, 2001:194-205.

[4]Rahmani K, Arezoo B. A hybrid hint-based and graph-based framework for recognition of interacting milling features [J]. Computers in Industry, 2007, 58:44, 304-312.

[5]周 煒. 基于圖的邊界模型的加工特征識別技術[D].南京: 南京航空航天大學, 2006.

[6]Dong X, Wozny M. A method for generating volumetric features from surface features [J].International Journal of Computational Geometry &Applications, 1991, 1(3): 281-297.

[7]Lee Sang Hun. Feature-based multi-resolution modeling of solids [J]. ACM Trans. on Graphics, 2005, 24(4):1417-1441.