付 鵬 苑偉政

西北工業(yè)大學(xué)陜西省微/納米系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,西安,710072

0 引言

三維CAD系統(tǒng)用實(shí)體模型表示產(chǎn)品,其模型表示由點(diǎn)、邊、面等幾何信息構(gòu)成。CAPP和CAM 系統(tǒng)需要加工信息例如軸、孔、槽等來進(jìn)行工藝推理和加工軌跡的生成。特征識(shí)別技術(shù)[1]從產(chǎn)品的實(shí)體模型出發(fā)自動(dòng)識(shí)別出其中具有一定工程意義的幾何形狀(特征),并將其進(jìn)一步轉(zhuǎn)換為可用于后續(xù)加工的特征。特征識(shí)別技術(shù)已成為一體化CAD/CAM環(huán)境中必不可少的組成部分。

20世紀(jì)80年代以來,國內(nèi)外許多學(xué)者對(duì)特征識(shí)別技術(shù)進(jìn)行了研究,但主要集中在算法研究上,實(shí)現(xiàn)過程的論述較少。從已公開的資料來看,主要存在以下問題：

(1)算法方面,基于圖的特征識(shí)別方法的研究較多,多采用屬性鄰接圖方法[2]和凸殼(convex hull)方法[3]來處理相交特征,并將這些方法與其他方法結(jié)合,產(chǎn)生了多種混合特征識(shí)別算法[4-6]。上述算法的時(shí)間復(fù)雜度與零件復(fù)雜度相關(guān),且難以有效地識(shí)別相交特征并提供相交特征的多重解釋。

(2)研究往往針對(duì)某一特定的CAD系統(tǒng),通過對(duì)該CAD系統(tǒng)的二次開發(fā),實(shí)現(xiàn)特征識(shí)別。

(3)對(duì)特征識(shí)別的研究仍停留在特征的面表示層次。對(duì)于面特征的邊界表示,尤其是特征識(shí)別中的面、邊環(huán)、邊的多態(tài)耦合性很少涉及。

筆者采用基于STEP的特征識(shí)別技術(shù)[7-8]識(shí)別來自不同三維CAD系統(tǒng)的模型,引入面向?qū)ο蟮姆椒?預(yù)定義二維面、邊環(huán)、邊等實(shí)體類以提高特征識(shí)別系統(tǒng)代碼的重用性,并通過基于子圖匹配和基面分解的屬性鄰接圖分解方法來識(shí)別特征。

1 STEP模型的表示與基于STEP的特征識(shí)別過程

STEP模型采用B-Rep法和參數(shù)表示法的混合表示方法來表示。B-Rep法的拓?fù)浔硎疽?guī)則如下：體是B-Rep表示的頂層對(duì)象,由殼包含而成;殼由一系列面連接而成;面由邊界包含而成,邊界具有方向性,其參數(shù)由邊環(huán)給出;邊環(huán)由有向邊按照連接順序構(gòu)成,有向邊的參數(shù)由邊給出;邊由點(diǎn)定義,通過起點(diǎn)和終點(diǎn)確定邊的參數(shù)。高階的較復(fù)雜物體必須建立在基本體基礎(chǔ)上。對(duì)于自由曲線曲面,STEP采用參數(shù)表示法來描述。STEP應(yīng)用NURBS方法來表達(dá)復(fù)雜的自由曲線曲面,該方法允許局部修改曲率,并能準(zhǔn)確地描述幾何基元。

本文所述的基于STEP的特征識(shí)別基于AP203協(xié)議,采用邊界匹配方法來識(shí)別特征。識(shí)別過程由以下4個(gè)步驟組成：

(1)預(yù)定義特征類型,建立特征庫。

(2)生成STEP模型拓?fù)鋷缀谓Y(jié)構(gòu)樹。

(3)識(shí)別STEP面和邊環(huán)的類型并獲取其幾何參數(shù)。

(4)采用基于子圖匹配和基面分解的屬性鄰接圖分解方法識(shí)別預(yù)定義特征。

2 預(yù)定義特征的屬性鄰接圖表示

屬性鄰接圖[2](attributed adjacency graph,AAG)是目前廣泛應(yīng)用的特征識(shí)別方法,可表示用B-Rep法描述的零件的拓?fù)鋷缀侮P(guān)系。在屬性鄰接圖中,頂點(diǎn)表示模型中的面,頂點(diǎn)之間的弧表示兩相交面的共有邊,用頂點(diǎn)和弧的附加屬性表來表示拓?fù)鋷缀螌傩?。采用屬性鄰接圖時(shí),特征定義規(guī)則的表示簡單直觀,便于進(jìn)行特征拓?fù)鋷缀螛?gòu)成的描述。

圖1為4種常見特征的屬性鄰接圖。筆者采用屬性鄰接圖的特征表示方法,但引入面向?qū)ο蠓椒ú捎昧诵碌膶?shí)現(xiàn)方式,可預(yù)定義二維面、邊環(huán)、邊等實(shí)體類,以類成員變量代替屬性鄰接圖中的屬性表。引入面向?qū)ο蟮姆椒?可以顯著提高特征識(shí)別系統(tǒng)的代碼重用性,便于實(shí)現(xiàn)特征識(shí)別系統(tǒng)的組件化,有利于實(shí)現(xiàn)面向不同應(yīng)用的快速開發(fā)。

圖1 常見特征的屬性鄰接圖表示

圖1 a和圖1b所示為圓柱體與圓錐體特征,其組成中都包含兩個(gè)圓形表面;圖1c和圖1d為長方體和開口直槽特征(都是由矩形平面組成)。預(yù)先定義圓形平面、矩形平面類及其低階圖素構(gòu)成的方法,可以提高特征識(shí)別系統(tǒng)代碼的重用性。圖1a和圖1b的圓柱和圓錐體特征的屬性鄰接圖的圖表示完全相同。對(duì)于預(yù)定義的圓柱體和圓錐體類來說,采用相同形式的屬性鄰接圖可準(zhǔn)確描述這兩種特征,并可減少用于表示預(yù)定義特征的屬性鄰接圖數(shù)量。

3 STEP模型拓?fù)鋷缀谓Y(jié)構(gòu)樹生成

STEP模型的拓?fù)鋷缀谓Y(jié)構(gòu)為樹狀解構(gòu),如圖2所示。

圖2 STEP模型拓?fù)鋷缀谓Y(jié)構(gòu)樹示例

特征識(shí)別前需從STEP模型文件中解析數(shù)據(jù),并按照STEP模型拓?fù)鋷缀谓Y(jié)構(gòu)重新組織數(shù)據(jù),生成STEP模型拓?fù)鋷缀谓Y(jié)構(gòu)樹。具體生成過程如下：

(1)建立STEP實(shí)體類型與C++結(jié)構(gòu)的映射關(guān)系。分析STEP實(shí)體類型的數(shù)據(jù)定義,建立與之對(duì)應(yīng)的C++結(jié)構(gòu)。每個(gè)C++結(jié)構(gòu)將定義的ID成員變量作為唯一標(biāo)志,其他成員變量與STEP實(shí)體類型的參數(shù)一一對(duì)應(yīng)。

(2)將STEP實(shí)體解析為對(duì)應(yīng)的C++結(jié)構(gòu)變量。筆者使用VC的CStdioFile∷ReadString函數(shù)讀入STEP文件,解析獲得實(shí)體類型,然后用switch case語句判斷實(shí)體類型并將該實(shí)體的低階實(shí)體行號(hào)和數(shù)據(jù)轉(zhuǎn)換存入對(duì)應(yīng)的C++結(jié)構(gòu)鏈表。由于筆者開發(fā)的原型系統(tǒng)中解析的STEP實(shí)體類型數(shù)量較多,故在此僅給出解析流程,如圖3所示。

圖3 STEP實(shí)體解析流程

(3)生成STEP模型拓?fù)鋷缀谓Y(jié)構(gòu)樹。根據(jù)C++結(jié)構(gòu)變量的ID成員變量,按照STEP模型拓?fù)浣Y(jié)構(gòu)逐層搜索,逐層添加構(gòu)成高階拓?fù)鋵?shí)體的低階拓?fù)鋷缀螌?shí)體元素,生成模型的拓?fù)鋷缀谓Y(jié)構(gòu)樹。

4 STEP面和邊環(huán)的類型識(shí)別及幾何參數(shù)獲取

可用于屬性鄰接圖的面類,如矩形平面、圓形平面在STEP中未定義,面的類型是由邊環(huán)類型和面幾何參數(shù)共同確定的。例如,圓形邊環(huán)與平面位置定位共同確定一個(gè)圓形平面,矩形邊環(huán)與平面位置定位共同確定一個(gè)矩形平面等。邊環(huán)類型,例如矩形邊環(huán)、平行四邊形邊環(huán)、圓形邊環(huán)等在STEP中也未定義,需要通過組成邊環(huán)的邊數(shù)量、邊與邊之間的幾何關(guān)系等組合規(guī)則來識(shí)別。例如,由兩條等半徑半圓構(gòu)成的邊環(huán)即為圓形,由4條直線兩兩垂直構(gòu)成的邊環(huán)即為矩形,由4條直線兩兩平行且互不垂直構(gòu)成的邊環(huán)即為平行四邊形等。因此,必須預(yù)定義邊環(huán)類型的識(shí)別規(guī)則,識(shí)別出邊環(huán)類型并獲取參數(shù)后,結(jié)合面幾何參數(shù)識(shí)別出可用于后續(xù)特征識(shí)別的面類型并獲取其參數(shù)。

按照STEP模型的拓?fù)鋷缀谓Y(jié)構(gòu),自頂向下查找并識(shí)別出低階類型,獲取其幾何參數(shù)后,根據(jù)低階類型的不同組合可實(shí)現(xiàn)高階類型的識(shí)別和幾何參數(shù)的獲取。筆者開發(fā)的原型系統(tǒng)可實(shí)現(xiàn)圓形平面、矩形平面、圓柱面等面類型的識(shí)別,由于具體的識(shí)別算法較為繁雜,筆者在此僅給出識(shí)別算法整體流程：

(1)遍歷STEP模型面鏈表,讀取STEP面結(jié)構(gòu)對(duì)象。

(2)讀取面對(duì)象的面幾何參數(shù)變量,使用switch case語句判斷面的幾何參數(shù)類型,轉(zhuǎn)入對(duì)應(yīng)分支。

(3)讀取面對(duì)象的面邊界參數(shù)變量,獲取構(gòu)成邊界參數(shù)變量的邊環(huán)對(duì)象及邊環(huán)的邊數(shù)量的變量后,使用switch case語句判斷邊環(huán)的邊數(shù)量,轉(zhuǎn)入對(duì)應(yīng)分支。

(4)讀取邊環(huán)對(duì)象的邊類型數(shù)量的變量,使用switch case語句轉(zhuǎn)入對(duì)應(yīng)分支。獲取邊的類型和參數(shù),并結(jié)合邊與邊的幾何關(guān)系識(shí)別邊環(huán)類型,解析邊對(duì)象的參數(shù)獲得邊環(huán)參數(shù)。

(5)根據(jù)面幾何參數(shù)和邊環(huán)類型識(shí)別面的類型,解析獲取幾何參數(shù)。

5 基于子圖匹配和基面分解的屬性鄰接圖分解方法

復(fù)雜零件的屬性鄰接圖中存在與預(yù)定義特征匹配的子圖,通過子圖匹配可以識(shí)別出零件所包含的特征。但是直接在零件屬性鄰接圖中搜索子圖是NP問題,算法復(fù)雜度與零件復(fù)雜度相關(guān),因此在子圖匹配前進(jìn)行屬性鄰接圖分解可降低算法復(fù)雜度。目前屬性鄰接圖分解有多種方法[2-5],但這些方法無法有效解決相交特征的識(shí)別,且算法復(fù)雜、編程實(shí)現(xiàn)工作量較大。

在相交特征識(shí)別中,若一個(gè)面含有內(nèi)環(huán)或者它的外環(huán)上含有凹邊,則稱其為基面,基面是體上連接特征的面即相交特征的相交面[9]。筆者提出了基于基面分解的屬性鄰接圖分解方法,該方法的子圖搜索算法時(shí)間復(fù)雜度僅與特征子圖的復(fù)雜度相關(guān),而與零件復(fù)雜度無關(guān),因此可減少冗余計(jì)算量。算法流程簡述如下：

(1)為面類設(shè)置基面標(biāo)志變量?；鏄?biāo)志變量的設(shè)置規(guī)則由兩部分構(gòu)成：①多環(huán)判定中,多環(huán)為真,其他為假;②混合環(huán)和凹環(huán)判定中,混合環(huán)或凹環(huán)為真,其他為假。

(2)遍歷面鏈表,讀取面對(duì)象的基面標(biāo)志變量,為真則獲取基面。

(3)由基面開始采用深度優(yōu)先算法進(jìn)行圖的遍歷,生成子圖。

(4)將子圖與預(yù)定義屬性鄰接圖匹配,識(shí)別預(yù)定義特征。

(5)解析特征參數(shù),根據(jù)不同的特征與基面的相對(duì)位置,判斷相交特征凸凹性。

圖4為圓柱體與立方體相交而成的零件及其屬性鄰接圖,其中,F3面包含2個(gè)邊環(huán),其基面標(biāo)志為真。遍歷面鏈表獲取F3面,子圖分解后如圖5所示,分別與圖1中圓柱體與立方體的屬性鄰接圖表示匹配,該零件由一個(gè)圓柱體和立方體特征構(gòu)成。

圖4 圓柱立方體零件及其屬性鄰接圖

圖5 子圖分解

筆者使用VC++6.0開發(fā)了基于STEP的特征識(shí)別原型系統(tǒng),可識(shí)別圓柱體、圓孔、矩形槽等常見特征和部分復(fù)雜特征。

6 結(jié)束語

本文闡述了基于STEP的特征識(shí)別技術(shù)及其實(shí)現(xiàn)過程,采用屬性鄰接圖表示預(yù)定義特征。引入面向?qū)ο蠓椒梢院喕瘜傩脏徑訄D的表示,提高特征識(shí)別系統(tǒng)的代碼重用性,便于實(shí)現(xiàn)特征識(shí)別系統(tǒng)的組件化,有利于實(shí)現(xiàn)面向不同應(yīng)用的快速開發(fā)?；谧訄D匹配和基面分解的屬性鄰接圖分解方法,降低子圖搜索算法復(fù)雜度,可識(shí)別多環(huán)相交特征和預(yù)定義混合環(huán)相交特征。今后的研究方向是提高對(duì)混合環(huán)相交特征和過渡特征的處理能力。

[1] 高曙明.自動(dòng)特征識(shí)別技術(shù)綜述[J].計(jì)算機(jī)學(xué)報(bào),1998,21(3)：281-288.

[2] Joshi S,Chang T C.Graph-based Heuristics for Recognition of Machined Features from a 3D Solid Model[J].Computer-aided Design,1988,20(2)：58-66.

[3] Ferreira J C E,Hinduja S.Convex Hull-based Feature-recognition Method for 2.5D Components[J].Compute-aided Design,1990,22(1)：41-49.[4] Gao S,Shah J J.Automatic Recognition of Interacting Machining Features Based on Minimal Condition Sub-graph[J].Computer-aided Design,1998,30(9)：727-739.

[5] Rahmani K,Arezooa B.A Hybrid Hint-based and Graph-based Framework for Recognition of Interacting Milling Features[J].Computers in Industry,2007,58(4)：304-312.

[6] 王飛,張樹生,白曉亮,等.基于子圖同構(gòu)的三維CAD模型局部匹配[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2008,20(8)：1078-1084.

[7] 杜娟,田錫天,朱名銓,等.基于 STEP和 STEPNC的AD/CAPP/CAM/CNC系統(tǒng)集成技術(shù)研究[J].計(jì)算機(jī)集成制造系統(tǒng),2005,4(11)：487-491.

[8] Rameshbabu V,Shunmugam M S.Hybrid Feature Recognition Method for Setup Planning from STEP AP-203[J].Robotics and Computer-integrated Manufacturing.2009,25(2)：393-408.

[9] 徐世新.對(duì)一種特征識(shí)別算法的兩點(diǎn)改進(jìn)[J].北京航空航天大學(xué)學(xué)報(bào),2000,26(4)：454-456.