自由曲面特征識別的研究

摘 要:由于利用基于區域分割的方法識別曲面往往會造成曲面模型的過度分割，而利用單純的基于邊緣檢測的方法識別曲面有時又不能提供較好的區域結構，基于此給出一種自動識別STL(standard triangulation language)形式的CAD模型自由曲面特征的方法——基于邊和區域的混合分割方法。通過檢測STL三角網格模型的特征邊對模型進行有效的區域分割，再計算這些區域上各點的Gauss(K)和平均曲率(H)來確定區域類型，最終達到識別的目的。經驗證，該方法能夠發揮上述兩種方法的優勢，獲得更好的分割效果，從而識別復雜的自由曲面特征，因而具有較強的實用性。

關鍵詞:三角網格; 特征邊; 過濾; 標準三角形語言

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3587-02

doi:10.3969/j.issn.1001-3695.2009.09.113

Study on recognizing features from freeform surface

SUN Li-juan， ZHENG Hong， ZHAO Qiang

(Dept. of Computer， Institute ofComputer Science Technology ， Harbin University of Science Techbology， Harbin 150080， China)

Abstract:Using method based on region to recognize surface sometimes made it partitioned excessly， but utilizingthe method of detecting edge did not provide good region structure. So this paper gave a new method of automatic recognizing features from freeform surface of CAD models in STL——a hybrid region segmentation algorithm based on edge and region . Through detecting feature edges segmented the STL models effectively， then caculated Gauss(K) and Mean curvature at every point on these region. Much experiments prove that the method has the advantadges of the above-mentioned methods， acquiring better segmentation effection， and recognize the complex features from freeform surface， so it has more practicality.

Key words:triangle mesh; feature edge; filtering; STL

特征識別就是從產品的實體模型出發自動識別出其中具有一定工程意義的幾何形狀，即特征，進而生成產品的特征模型[1]。在許多涉及到自由曲面產品設計和制造的情況下，為了實現自動設計而識別以STL形式表示的自由曲面特征是很有用的。STL文件是通過對CAD實體模型或曲面模型進行表面三角化離散得到的，相當于用一種全由小三角形面片構成的多面體近似原CAD模型。從幾何上看，它是用眾多三角形小平面形成三維形體的表面，每個三角形面片用三個頂點表示[2]。有效的CAD產品模型自由曲面的特征識別技術能使得CAD/CAM產品模型無縫集成，然而有關CAD模型自由曲面特征識別的研究很少。盡管CAD/CAM系統完全支持STL形式，但是幾乎就沒有專門研究以STL形式表示的CAD模型自由曲面特征識別的報道[3]。

在特征識別當中，常將處理的STL模型分割成一些具有特定幾何性質(如曲率、法線)的區域，即所謂的區域分割。而這些特定的區域在CAD系統中又由許多三角形的網格組成。近幾年來，對于分割三角網格算法的開發與研究方興未艾[4]。本文給出一種基于邊和區域的混合分割算法，將CAD模型自由曲面特征自動識別中產生的STL三角網格進行區域分割。此方法通過檢測STL三角網格模型的明顯特征邊和模糊特征邊，確定區域間的明顯邊界和模糊邊界，將分割的區域分成不同的類型，更具普適性。

1 基于邊和區域的分割算法

基于邊和區域的混合分割算法，在分割STL三角網格模型時，同時考慮了明顯特征邊和模糊特征邊，用特征邊和明顯邊界線將區域分離開來，將分割得到的區域分成不同的區域類型。明顯特征邊定義為大于一定閾值的二面角上的公共邊。如果某邊的鄰接三角形面片至少有一個是針或帽三角形面片，且與該邊所對應的角至少有一個小于10°，則稱該邊為模糊特征邊。在該算法中針三角形定義為一個角小于10°的三角形，帽三角形即有一個角大于160°的三角形。邊界邊也被看做是特征邊。圖1顯示了明顯特征邊和模糊特征邊。檢測模糊特征邊使得在區域生成過程中，區域間的分界更為清晰。

1.1 特征邊檢測方法

1)確定特征邊 根據上面所述的標準來確定特征邊，這里不再贅述。有時，在此過程中會生成一些無用的模糊特征邊，需要將其過濾，從而使得區域分界更為清晰。

2)過濾無用的模糊特征邊 過濾無用的特征邊主要用到兩個幾何特性，即三角形高與邊長的比率(H/L比率)和該點兩邊的平均長度Lavg。下面討論過濾無用模糊特征邊的方法。

過濾方法1 大多數無用的特征邊是帽三角形的一部分且附著在鈍角頂點上。 如圖2所示，邊FE1和FE2是特征邊，它們是要過濾的備選特征邊，AT1和AT2是分別與邊FE1和邊FE2相鄰接的三角形;V1、V2是與邊FE1、FE2相對的點。有三種可能過濾的情況:

a)不過濾FE1和FE2。如果AT1和AT2的高長比率 (H/L)小于閾值，且兩者百分比高度差大于閾值時，則不過濾FE1和FE2。該方法說明FE1和FE2將AT1和AT2三角形區域從CT區域分離出來。

b)過濾FE1或者FE2。如果AT1和AT2百分比高度差小于閾值，并且在V1、V2兩點的Lavg 的百分比差大于閾值，那么過濾H/L較小的邊。該方法說明AT1和AT2有不同的三角形結構，且特征邊將結構較好的三角形分離并保存起來。

c)過濾FE1和FE2。如果AT1和AT2的H/L比率小于閾值，則過濾FE1和FE2。該規則說明AT1和AT2與CT具有相同的結構，不需要用特征邊將它們分離。

過濾方法2 過濾單獨特征邊，其鄰接面的高度比小于一個閾值，說明區域在該特征邊的一側，并與鄰接面有相似的三角形結構。

3)延伸特征邊 在特征邊的檢測過程中，并不是所有的特征邊都能被完整地檢測到，但用適當的方法延伸已檢測到的不完整特征邊時卻能將其補充完整，其延伸的方向與相應特征邊的方向一致。方法如下:

a)找初始邊。始邊是一條內部特征邊(即除邊界邊外的特征邊)，且除它本身之外至少有一個不與特征邊相連接的點。初始邊可以從特征邊集合里隨機選擇一條以前沒用過的特征邊。

b)找可延伸的種子特征邊。從初始邊開始，沿著相連接的特征邊延伸直到遇到邊界或交叉，否則沒有未檢測到的特征邊存在。若當前半邊的頂點與初始邊的頂點重合則產生交叉。此時，在該交叉點處任選一條特征邊。倘若有兩條以上的上述特征邊存在，則構成了一個可延伸的種子特征邊。

c)向兩側延伸種子特征邊。如圖3所示， f1是當前考慮的特征邊，v是其頂點。

將以v為頂點的邊投影到過點v的切線平面，得到v點的法線n，即切線平面的法線，將f2投影到切線平面，與f1的投影之間有一個偏移角θ，。如果其角度小于閾值δ，則f1被添加到特征邊列表中。閾值δ計算公式如下[5]:

cos-1((f1-(f1#8226;n^)n^)#8226;(f2-(f2#8226;n^)n^)/(|f1-(f1#8226;n^)n^‖f2-(f2#8226;n^)n^|))<δ

如果不止一條邊滿足上述條件，則選取鄰接面高度比最大的那條邊作為特征邊。延伸過程中如果形成閉環，或者遇到特征邊，或在點v不再有滿足閾角標準的邊，則延伸終止。該過程是向兩端延伸的，即如果種子特征邊的終邊不是死端，則先從終邊開始延伸，然后從種子特征邊的始邊延伸。

d) 重復步驟a)~c)，直到沒有可用的初始邊形成種子特征邊。

1.2 STL三角網格模型中點的幾何特性計算

1.2.1 高斯曲率的計算

STL三角網格模型中某點的幾何特性主要指該點的Gauss(K)和平均曲率H，如圖4所示，P點高斯曲率RP計算如下:

Rp=(1/2)minpi(di#8226;di/(np#8226;di)) for i=0，1，2，…，n-1

其中:di是由P點指向其鄰接三角形上點pi的矢量;n表示由P點定義的三角形個數;np表示P點的單位法線矢量。P點的單位法線矢量np計算如下:

np=∑n-1i=0Niwi/|∑n-1i=0Niwi|

其中:Ni (按逆時針方向依次為N0，N1，…，Nn-1)是用Ti (按逆時針方向依次為T0，T1，…，Tn-1)所標志的三角形面片的單位法線矢量，wi是其相應的加權因數，該因數定義為

wi=1/2(αi/∑n-1j=0αj+lj/∑n-1j=0lj)

其中:αj是如圖4所示的角; lj (按逆時針方向依次為l0，l1，…，ln-1)是點P到對邊中點的距離。

1.2.2 平均曲率的計算

平均曲率H由法向矢量H=n周圍曲面的散度表示，網格曲面的平均法曲率計算如下:

-Hn=1/(4A)∑j∈N(i)(cot αj+cot βj)(pj-pi)

如圖5所示，N(i)表示pi周圍且與pi相鄰的點的集合，αj和βj表示與邊eij相對的兩個角，pj-pi表示邊eij， A表示pi點周圍三角形面積的和。

為了對曲面類型進行分類，還定義了函數T=1+3(1+sgn(H，e))+(1-sgn(R，e))。

其中:sgn(x，e)=+1 if x>e

0 if |x|≤e-1 if x

表1是相對于不同曲面類型，R、H和函數T之間的關系。

如果知道曲面上每點的表面類型，那么STL網格模型可以分割成上述幾種區域類型，確定曲面類型方法如下:

a)確定并生成種子面片。滿足下述條件的面片稱之為種子面片，并根據其相應頂點的類型來分配曲面類型。

(a)最大和最小邊長的比小于一閾值;

(b)該面片沒有分配給任一區域;

(c)至少有一個點不是特征點;

(d)三角形面片的三個頂點有相同的類型。

b)生成區域。在該過程中，鄰接三角形被吸收，它們的公共邊不是特征邊，它沒有被分配任一區域，且其三個點和種子面片有相同的表面類型，則將種子面片的區域類型分配給被吸收的面片。

c)生成終止。當沒有相同表面類型的鄰接面片時，區域生成終止。

d)重復步驟a)~c)，直到沒有種子面片生成。

生成區域的過程中，總有因所處位置關系沒有被分配區域類型的面片存在，可以將孤立點處的面片分配周圍區域類型，或者逐步擴展某一區域，直到遇到沒有被分配類型的區域，從而確定其類型。

2 實驗驗證

上述方法已經在奔騰4 PC機上用VC++和OpenGL實現。經驗證，該方法可以將由標準CAD系統(CATIATM、 SolidWorksTM等系統)生成的STL形式的CAD自由曲面準確地進行分類，并在瞬間識別其特征。如圖6所示，顯示了對工業用金屬薄片的區域識別。

實踐證明，該方法利用曲面模型的局部空間信息對曲面進行區域分割，相對于利用灰度進行區域分割的方法更能夠保證網格模型的三角形密度分布，并且使曲面模型更加完好地保持了細節信息，同時避免了利用灰度進行區域分割受噪聲影響、只能對非復雜曲面進行區域分割的弊端，為識別曲面特征奠定了良好的基礎。

3 結束語

經過對工業金屬薄板零件的大量實踐證明，該系統具有較強的健壯性和一致性。所得到的特征數據被進一步處理后還可應用到不同的CAD/CAM分支，如自動化過程設計、金屬薄板機床設計、產品再造、有限元網孔細分等。目前，在該領域還有很多問題需要進一步研究，如提高區域分割算法的健壯性、完善特征識別規則等。

參考文獻:

[1]高曙明.自動特征識別技術綜述[J]. 計算機學報，1998， 21(3):281-288.

[2]王華僑.結構有限元分析中的網格劃分技術及其應用實例[J]. CAD/CAM與建造業信息化，2005(1):108-123.

[3]SUNIL V B， PANDE S S. Automatic recognition of features from freeform surface CAD models[J]. Computer-Aided Design ， 2008， 40(4):502-517.

[4]CHEN Li-jun，GEORGANAS N D. An efficient and robust algorithm for 3D mesh segmentation[J]. Multimedia Tools and Applications， 2006，29(2):109-125.

[5]OWEN S J， WHITE D R， TAUTGES T J. Facet based surfaces for 3D mesh generation[C]// Proc of the 11th International Meshing Roundtable. 2002.