【導(dǎo)讀】以通過修改已有的零部件來完成，只有20%的部分需要從草圖開始進(jìn)行全新設(shè)計(jì)。為了尋找合適的參考方案，設(shè)計(jì)者60%的時(shí)間用于查找資料。在制造業(yè)中普遍存在。的資源管理工具。三維CAD系統(tǒng)的推廣應(yīng)用使得設(shè)計(jì)資源的主要形式是三維CAD模型。型文本記錄的信息隨著CAD系統(tǒng)、設(shè)計(jì)者和設(shè)計(jì)時(shí)間的變化具有極大的不確定性，對(duì)復(fù)雜多樣的物體進(jìn)行具有一定工程語義的局部區(qū)域分割，能夠在獲。取突出局部形狀特征的同時(shí)，有效地降低模型結(jié)構(gòu)的復(fù)雜度。提出一種CAD模型區(qū)域分割方法。首先，用面屬性鄰接圖表達(dá)CAD模型；提出基于多級(jí)形狀描述符的CAD模型整體與局部形狀檢索方法。前者用體范圍內(nèi)的面上下文碼和區(qū)域上下文碼相。同時(shí)用實(shí)驗(yàn)驗(yàn)證了研究成果的正確性和有效性。

　　

【正文】 便，需 要 從 CAD 模型中抽象提取簡(jiǎn)潔的形狀描述 符來 表達(dá) 模型 的形狀。為了避免采用復(fù)雜的圖匹配或子圖匹配方法評(píng)估相比較整體或局部形狀的相似性，同時(shí)考慮到編碼易于創(chuàng)建，方便形狀比較，這里將研究基于局部區(qū)域?qū)傩源a的 CAD 模型 多級(jí) 形狀描述符。 (3) 研究基于模型分割的 CAD 模型整體與局部形狀檢索方法 。為了適應(yīng)不同類型的 CAD 模型 形狀比較與檢索，以及不同精準(zhǔn)程度的檢索需求，保證模型檢索在具有較高檢索效率的同時(shí)具有較高的檢索精度，這里將研究 基于 多級(jí) 形狀描述符 的 CAD 模型整體 與局部形狀 檢索 方法。 2 CAD 模型 局部區(qū)域分 割 方法 引言 有研究 表明， 人類對(duì)于物體形狀的認(rèn)識(shí)，部分地基于物體的局部分割 [14,15]。復(fù)雜多樣的物體通常 被 認(rèn)為 是 由一些簡(jiǎn)單的基本體或基本元素通過疊加或切割組合 而成，并且突出的局部形狀特征 屏蔽了其它 形狀 不 突出的部分。對(duì)物體 進(jìn)行具有一定工程語義的局部區(qū)域 分割 ，是 獲取 突出局部形狀特征的一種重要途徑 。三維模型分割是依據(jù)三維模型的表面幾何屬性和拓?fù)涮卣?，將封閉的三維模型分割為一組 形狀簡(jiǎn)單 、具有一定工程語義 、且 相互 連通的三維模型子塊 的集合 [104]。三維 實(shí)體 模型分割在 特征識(shí)別 、 CSG 樹重構(gòu) 和三維模型檢索等 領(lǐng)域得到了廣泛的應(yīng)用。 三維 CAD 系統(tǒng)的模型文件中都保存有 Brep 信息， 其中 包含有模型 的 面、邊、頂點(diǎn)以及 它 們之間的相互關(guān)系 ，用戶能夠 方便地提取這些信息表征模型的形狀。對(duì)于 形狀復(fù)雜的 CAD 模型， 由于 它們的 面 和 邊數(shù)量較多，直接用 面屬性鄰接圖表征模型形狀 時(shí)，存在著 局部形狀不突出、 數(shù)據(jù)量較大和計(jì)算復(fù)雜度較高的問題。 對(duì)于三維模型局部形狀檢索，由于需要確定數(shù)據(jù)模型的哪一部分與查詢模型相匹配，導(dǎo)致局部形狀檢索的計(jì)算通常比整體形狀檢索更為復(fù)雜。為了解決以上問題，可通過某種方式使模型元素的粒度更大來縮減問題的規(guī)模，降低計(jì)算 的復(fù)雜度，改善模型的檢索效率。網(wǎng)格作為網(wǎng)格模型的基本元素，其粒度太小。同樣地，像多邊形面或圓柱面作為復(fù)雜 Brep 模型的基本元素，其粒度也不夠大。因此，我們需要模型分割，將模型劃分為一些具有工程語義的局部區(qū)域集合，用局部區(qū)域來替代網(wǎng)格模型中的網(wǎng)格或 Brep 模型中的面作為模型的基本元素。在本研究中， Brep 模型分割后得到的模型元素是一些具有一致凸性的模型邊界區(qū)域。 然而， Brep 模型的邊界區(qū)域分割與現(xiàn)有的模型區(qū)域分割方法類似，同樣面臨著分割的效率問題和分割結(jié)果的不唯一性問題。區(qū)域生長(zhǎng)法和聚類法是兩種最為 常見的區(qū)域分割方法。區(qū)域生長(zhǎng)法的分割效率一般較高，但選擇生長(zhǎng)的種子面不同，可能產(chǎn)生不同的區(qū)域分割結(jié)果。聚類法由于面聚類是一個(gè)優(yōu)化的過程，通常能夠得到確定性的分割結(jié)果。但是聚類過程需要 遍歷所有可能的組合 ， 顯然其計(jì)算復(fù)雜度 很高。 為了彌補(bǔ)上述缺陷，這里的局部區(qū)域分割問題采用了三個(gè)分割步驟，前兩步是初始分割，首先聚類 Brep 模型中具有明顯凸性的面，接著聚類具有混合凸性的面。通過初始分割，將 Brep 模型分割為凸區(qū)域、凹區(qū)域和平區(qū)域的集合，這個(gè)過程不需要考慮模型分割結(jié)果的確定性和唯一性。最后通過第三個(gè)步驟的區(qū)域融 合優(yōu)化方法，將初始分割得到的局部區(qū)域優(yōu)化組合為區(qū)域數(shù)量最少、具有一定工程語義的局部區(qū)域集合。優(yōu)化后的區(qū)域數(shù)量要比初始分割得到的區(qū)域數(shù)量少，并且優(yōu)化后的分割結(jié)果是確定的和唯一的。明顯地，這里的優(yōu)化組合對(duì)象是初始分割得到的局部區(qū)域，與傳統(tǒng)的聚類方法中的優(yōu)化組合對(duì)象模型面相比較，問題規(guī)模大為縮減。選擇這種方法的理由是基于以下 事實(shí) ： Brep 模型的鄰接面明顯地屬于某個(gè)局部區(qū)域，不存在屬于另一個(gè)局部區(qū)域的可能；前兩步的初始分割過程中沒有種子面的輸入，分割結(jié)果相對(duì)確定，不存在面的優(yōu)化組合；第三步的優(yōu)化步驟就是處理區(qū)域 的優(yōu)化組合，以保證區(qū)域分割結(jié)果的唯一性，以及分割得到的大部分局部區(qū)域具有一定的工程語義。 CAD 模型面屬性鄰接圖 在商業(yè) CAD 系統(tǒng)中， CSG 和 Brep 是最為常用的兩種實(shí)體模型描述方式。由于 CSG 描述實(shí)體模型的不唯一性，以及目前實(shí)際 應(yīng)用中 的 CAD 系統(tǒng)零件的模型文件中都保存有 BRep 信息，不同 CAD 系統(tǒng)的零件模型都 可 方便地轉(zhuǎn)換為 國(guó)際標(biāo)準(zhǔn) STEP 中的 BRep 格式 ，導(dǎo)致 BRep 格式是目前實(shí)體模型描述和分析的首選。因此，本研究中的局部區(qū)域分割對(duì)象是 BRep 格式的 CAD 模型 。 由于能方便地從 CAD 模型 的 Brep 結(jié)構(gòu)中提取 CAD 模型的面屬性 ， 用面屬性鄰接圖表達(dá) CAD 模型是一個(gè)自然而實(shí)用的選擇。在 CAD 模型局部區(qū)域分割前，需要將實(shí)體模型轉(zhuǎn)化為面屬性鄰接圖。 ElMehalawi [75]等 較 早提出了從 STEP文件 信息中生成面屬性鄰接圖的方法，這里用類似的方法生成 CAD 模型的面屬性鄰接圖。在本文中， 面屬性鄰接圖 是一個(gè)有序圖 Gf = (Vf , Ef )， 其中 Vf和 Ef為圖 Gf的頂點(diǎn) 和 鄰接 邊 集合， 分別 對(duì)應(yīng)于 BRep 模型中的面 和邊 集合。 基本概念 和相關(guān)術(shù)語定義 類似于 Fu 等 [104]和 Sonthi 等 [105]提出的 點(diǎn)的分類 方法， 在 本 研究 中，實(shí)體邊界上的點(diǎn) 被分 為凸點(diǎn)、凹點(diǎn)和平點(diǎn)三種類型。 假定 min? 和 max? 是實(shí)體邊界上一個(gè)點(diǎn)的兩個(gè)主曲率，當(dāng) 0min?? , 0max?? ，且 0|||| m a xm in ?? ?? 時(shí)，該點(diǎn)是凸點(diǎn)；當(dāng)0min?? , 0max?? ，且 0|||| m a xm in ?? ?? 時(shí) ， 該點(diǎn)是凹點(diǎn)；當(dāng) 0|||| m a xm in ?? ?? 時(shí)，該點(diǎn)是平點(diǎn)。 為簡(jiǎn)單起見 ，這里 暫 不考慮當(dāng) 0maxmin ??? 時(shí)為鞍點(diǎn)的情形。 然而，基于上述點(diǎn)分類的 局部 區(qū)域分割 方法， 產(chǎn)生的 局部 區(qū)域數(shù)量可能比 實(shí)際 工程應(yīng)用 中所 期望的要多。 因此 ，在 局部 區(qū)域 分割過程中 ，可以采 用 更符合工程實(shí)際的 半凸區(qū)域或半凹區(qū)域 代替比較 嚴(yán)格的凸區(qū)域 或 凹區(qū)域。這里的半凸區(qū)域不僅包含有 凸點(diǎn) ，同時(shí)還可能包含有 平點(diǎn) ； 半凹區(qū)域 在包含有 凹點(diǎn) 的同時(shí)，也可能包含有 平點(diǎn)。 因此 ，平面鄰接凸邊就形成了半凸區(qū)域 ， 平面鄰 接凹邊就形成了半凹區(qū)域。 盡管上面的 局部區(qū)域 定義 方法比較符合工程實(shí)際應(yīng)用 ， 但是在 區(qū)域 類型識(shí)別過程中，需要對(duì)局部區(qū)域中的每個(gè)點(diǎn)進(jìn)行 凸性檢查 。顯然，上述定義中的 逐點(diǎn)凸性檢查 操作起來并不方便 。 于是 ，我們 依據(jù)一個(gè) 區(qū)域中單個(gè)的面凸性和邊凸性 來判斷區(qū)域類型，進(jìn)而對(duì)整個(gè)模型中的局部 區(qū)域 進(jìn)行識(shí)別 分類。類似于文獻(xiàn) [101]提出的面和邊的分類方法， 將模型 面分 類 為半凸 面 、 半凹 面 或平面 三種類型 ； 同時(shí)依據(jù)內(nèi)外邊角 對(duì)模型邊進(jìn)行 分類， 將模型 邊 分 類 為凸邊、凹邊、切邊、凸切邊或凹切邊 五種類型 。為簡(jiǎn)單起見，邊的凸性僅考慮邊的方向曲率。 因此 ，整 個(gè) CAD實(shí)體模型 可以 被分 割 為半凸區(qū)域、半凹區(qū)域和平區(qū)域的集合。 局部 區(qū)域分割能有效降低模型的復(fù)雜度 ，分割產(chǎn)生的局部區(qū)域具有一定的工程語義 。在介紹局部區(qū)域分割方法前， 首先介紹 一些 局部區(qū)域分割的相關(guān) 術(shù)語和 定義 。 定義 平面區(qū)域 (Planar Region, PR)。 假定 局部 區(qū)域中 的 所有面都為平面， 同時(shí)這些 面的 內(nèi) 邊都為切邊，則該區(qū)域?yàn)槠矫鎱^(qū)域 。 定義 半凸區(qū)域 (半凹區(qū)域 )(Semiconvex Region, CvR。 Semiconcave Regions, CcR)。 滿足以下三個(gè)條件 的 局部區(qū)域 ，我們 定義它們 為半凸區(qū)域 (半凹區(qū)域 )。 (1) 區(qū)域中的每一個(gè)面是 半凸 面 (半凹面 )或平面； (2) 區(qū)域中的每一個(gè)內(nèi)邊是凸邊（凹邊）、凸切邊（凹切邊）或切邊； (3) 區(qū)域中至少有一個(gè) 半凸 面 (半凹面 )，或者內(nèi)邊中至少有一個(gè)是凸邊（凹邊）或凸切邊（凹切邊）類型。 為了簡(jiǎn)單 起見 ，下 文 中的半凸區(qū)域或半凹區(qū)域簡(jiǎn)稱為凸區(qū)域和凹區(qū)域。 定義 導(dǎo)出子圖 ( Induced Graph, IG)。 對(duì)于面屬性鄰接圖 FAG g= (Vg, Eg)和 G= (V, E), 如果它們滿足以下兩個(gè)條件，我們稱 g 為 G 的導(dǎo)出子 圖。 (1) ? 。 (2) ={e | for all e∈ , ∈ , i=1,2}. 對(duì)應(yīng)于 PR, CvR 和 CcR, 導(dǎo)出子圖 IG 可分 為平子圖 (Planar Region Graph, PRG)、凸子圖 (Convex Region Graph, CvRG)和凹子圖 (Concave Region Graph, CcRG)。 定義 局部 區(qū)域分割。 如果面屬性鄰接圖 FAG G= (V, E)被 分割為 G 的導(dǎo)出子圖 IGs S={g1, g2 ,? , gn | gi=(Vi, Ei)，同時(shí) 它們 又滿足以下兩個(gè)條件： (1) =∪ … 。 (2) ∩ =? if i≠ j. 這里 gi 是 PRG, CvRG 或 CcRG (i=1, 2,? , n)。 于是 ， 我們定義 S 為 G 的 局部 區(qū)域 分割。 局部區(qū)域分割 局部區(qū)域分割是將一個(gè)實(shí)體模型或網(wǎng)格模型分割為一些具有幾何屬性的局部區(qū)域 的集合 。區(qū)域生長(zhǎng)法 [21~24]和聚類分割 方法 [31~34]是兩種最為常用的區(qū)域分割方法。區(qū)域生 長(zhǎng)法是 通過選取 合適的面或網(wǎng)格 作為種子， 由種子面或種子網(wǎng)格的 生長(zhǎng) 形成局部 區(qū)域 ，同時(shí)引入了生長(zhǎng)規(guī)則來控制 區(qū)域 的生長(zhǎng)過程 。然而，對(duì)于一個(gè)復(fù)雜的實(shí)體模型或稠密的網(wǎng)格模型，種子面或種子網(wǎng)格的生長(zhǎng)是一項(xiàng)非常費(fèi)時(shí)的任務(wù)。如果選擇的種子面或種子網(wǎng)格不合理，可能導(dǎo)致不恰當(dāng)?shù)膮^(qū)域分割結(jié)果。聚類分割 方法是將實(shí)體 模型 中的面或網(wǎng)格模型 中的網(wǎng)格單元 ， 依據(jù)距離函數(shù)度量 ，采用 kmeans 聚類迭代算法或?qū)訝畹拿娼凭垲惙椒ǎ?將距離聚類中心最近的 面或網(wǎng)格 單元進(jìn)行歸類 合并形成局部區(qū)域 。 通常，當(dāng)實(shí)體模型的面數(shù)量較多或網(wǎng)格模型的網(wǎng)格較為稠密， 聚類 分割 方法也是一項(xiàng)比較費(fèi)時(shí)的任務(wù)。 由于 FAG 提供了完整的面鄰接信息，選擇區(qū)域生長(zhǎng)分割方法似乎是一種很自然的選擇。然而，當(dāng)種子面或種子網(wǎng)格的選擇不同或生長(zhǎng)方式不同時(shí)，可能產(chǎn)生不同的局部區(qū)域分割結(jié)果，圖 給出了一個(gè)這樣的實(shí)例。在圖 (a)中，如果以紅色的槽底面作為種子面生長(zhǎng)，橙色 (黃色 )的槽側(cè)面 f 被歸類合并到槽區(qū)域；然而，在圖 (b)中，當(dāng)紅色的長(zhǎng)方體前面作為種子面生長(zhǎng)時(shí)，橙色 (黃色 )的槽側(cè)面 f 被歸類合并到長(zhǎng)方體部分。顯然，圖 (b)中的區(qū)域分割結(jié)果，與工程實(shí)際應(yīng)用不符合，不是我們想要的分 割結(jié)果。產(chǎn)生這種結(jié)果的原因是橙色的面 f 同時(shí)具有凸邊和凹邊， 它 既 可以 與 凸 區(qū)域合并歸類生長(zhǎng)為 凸 區(qū)域的一部分，也 可以與凹區(qū)域合并歸類生長(zhǎng)為凹區(qū)域的一部分 。 (a) 面 f 被歸類合并到槽區(qū)域 (b) 面 f 被歸類合并到長(zhǎng)方體部分 圖 區(qū)域生長(zhǎng)分割方法產(chǎn)生不同分割結(jié)果 局部 區(qū)域 分割的 另一個(gè)難題是區(qū)域中的面存在著特殊約束的情況。如圖 ，假定面 f1, f2, … , f5已經(jīng) 形成了一個(gè)凸區(qū)域 CvRG，面 f6 或 f7也可能被合并到 CvRG中，但由于它 們的鄰接邊與 CvRG 其它邊的凸性不同，不能被合并到 CvRG 中。 圖 區(qū)域中的面存在特殊約束 情形 與現(xiàn)有的區(qū)域分割方法 相 比較，定義 4 所給出的 局部 區(qū)域分割方法應(yīng)該考慮以上的兩種 特殊 情形。 在工程實(shí)際應(yīng)用中 ，我們希望 局部 區(qū)域分割的結(jié)果是確定的 ，同一個(gè)模型不論從哪一個(gè)面開始分割，以什么樣的方式聚類，最后的分割結(jié)果應(yīng)該是相同的 。為了解決這個(gè) 難題 ， 這里 采用了一個(gè)類似于 kmeans 聚類算法的 局部 區(qū)域分割方法 來 實(shí)現(xiàn) CAD 模型 的局部區(qū)域 分割。 優(yōu)化目 標(biāo)函數(shù) 這里，我們 引入 了一個(gè)優(yōu)化目標(biāo)函數(shù) ，來 測(cè)量 局部 區(qū)域中面的平均相關(guān)性 。由 面的平均相關(guān)性函數(shù) 值來控制面聚類的對(duì)象，以保證模型分割過程中面聚類得到的區(qū)域分割結(jié)果是唯一的 。 面 v 的相關(guān)性是 指 v 在其 區(qū)域 gi 中的 所有 鄰接邊數(shù)fseed f fseed f f7 f6 f5 f4 f3 f2 f1 量，即 |),(|)( vgNv ig i ?? ， }.)39。,(|39。{),( iii EgvvevvgN ??? 。 平均相關(guān)性是區(qū)域 gi 中所有面相關(guān)性的平均值，即 ||/).(|| 1 iVj jig VvVi i?? ? ， || iV 是區(qū)域中 的 面數(shù)量。如果 一個(gè) CAD 模型被分割為子圖集 S={g1, g2,…, g|S|}，則 CAD 模型中所有 局部 區(qū)域的面相關(guān)性平均值為： ||}||/]).({[)(||1||1 SVvVSfSi iVj jigii? ?? ?? ?， ||S 是模型中區(qū)域數(shù)量。 () 局部區(qū)域分割規(guī)則是使模型分割得到的所有區(qū)域的面相關(guān)性平均值最大。 圖 給出了圖 和圖 中模型不同區(qū)域分割結(jié)果的 面相關(guān)性平均值 f(