汪俊輝 陳 興 鄧益民

(寧波大學(xué)機(jī)械工程與力學(xué)學(xué)院 浙江 寧波 315211)

STL三角形網(wǎng)格模型曲面特征邊的提取

汪俊輝 陳 興*鄧益民

(寧波大學(xué)機(jī)械工程與力學(xué)學(xué)院 浙江 寧波 315211)

針對(duì)STL網(wǎng)格模型曲面特征邊識(shí)別困難的問(wèn)題，提出一種基于邊和面的特征邊提取方法。首先遍歷網(wǎng)格模型，自適應(yīng)地獲取二面角閾值并根據(jù)該閾值識(shí)別顯性特征邊；然后利用最小二乘法估算曲面上頂點(diǎn)的平均曲率，由此計(jì)算出三角形面片的近似曲率，并利用相鄰三角形的曲率差值來(lái)判別其公共的隱性特征邊是否為特征邊，最后采用改進(jìn)的斷點(diǎn)處特征邊提取算法形成完整的特征邊界。實(shí)驗(yàn)結(jié)果表明該方法能夠有效地提取STL網(wǎng)格模型曲面網(wǎng)格的特征邊，具有很好的魯棒性。

STL模型 三角形網(wǎng)格 特征提取 二面角 平均曲率

0 引 言

特征邊能夠反映實(shí)體模型的輪廓特征，準(zhǔn)確、高效地提取三角形網(wǎng)格模型的特征邊對(duì)文物碎片的匹配[1]、網(wǎng)格簡(jiǎn)化[2]、曲面重構(gòu)[3]以及網(wǎng)格分割[4]等具有重要意義。隨著CAD/CAM技術(shù)的快速發(fā)展，通過(guò)CAD軟件可輕易獲取具有表面三角形網(wǎng)格的STL實(shí)體模型，而STL模型運(yùn)用于計(jì)算機(jī)輔助制造(CAM)、有限元分析、快速原型制造(RP)、注塑成型模流分析的首要前提條件是能夠準(zhǔn)確地提取STL三角形網(wǎng)格模型的特征邊。因此，如何快速、準(zhǔn)確地提取STL模型的特征邊是關(guān)鍵所在。

當(dāng)今關(guān)于三角形網(wǎng)格特征邊的提取算法有很多，一般將其劃分為兩大類(lèi)：1) 基于面的特征邊提取算法[5-8]，文獻(xiàn)[5]采用張量投票對(duì)三角形網(wǎng)格頂點(diǎn)進(jìn)行分類(lèi)，然后利用區(qū)域生長(zhǎng)合并的遞歸算法實(shí)現(xiàn)特征線的提取，但對(duì)于三角形網(wǎng)格分布不均勻，尤其是含有較多狹長(zhǎng)和面積近乎為零的三角形網(wǎng)格時(shí)，算法無(wú)法準(zhǔn)確地識(shí)別特征點(diǎn)。文獻(xiàn)[6]在此基礎(chǔ)上提出了一種斷點(diǎn)連接的方法來(lái)保證頂點(diǎn)分類(lèi)的正確性，能夠處理網(wǎng)格分布不均勻，以及含有狹長(zhǎng)三角形的模型，但該算法僅對(duì)規(guī)則數(shù)據(jù)模型有效，無(wú)法識(shí)別位于過(guò)渡曲面處曲率漸變的特征點(diǎn)[7-8]。2) 基于邊的特征邊提取算法[9-22]。最初的方法是基于初等幾何的方法，如通過(guò)計(jì)算相鄰面的二面角閾值進(jìn)行模型特征邊的提取，但該方法無(wú)法提取具有較小二面角的過(guò)渡曲面的特征邊[9]，文獻(xiàn)[10]給出了一種自適應(yīng)獲取二面角閾值的方法，并結(jié)合相鄰三角形的周長(zhǎng)比值來(lái)提取網(wǎng)格模型的特征邊，該算法僅適用于由簡(jiǎn)單幾何體組合形成的復(fù)雜模型，對(duì)于自由曲面模型則易失效，尤其是含有過(guò)渡曲面的模型，會(huì)出現(xiàn)周長(zhǎng)比值小于給定閾值的情形而導(dǎo)致這部分特征邊出現(xiàn)中斷現(xiàn)象。為了避免該現(xiàn)象發(fā)生，文獻(xiàn)[11]利用斷點(diǎn)處特征邊提取算法，較好地解決了特征邊中斷現(xiàn)象，但該算法僅適用于“環(huán)狀過(guò)渡邊界[12]”的提取，對(duì)于“帶狀過(guò)渡曲面邊界”提取易失效，并且由于文獻(xiàn)[10]并沒(méi)有給出判定冗余特征邊的算法，僅用二面角和周長(zhǎng)比兩個(gè)判定條件并不能保證所有識(shí)別的邊均為特征邊。因此斷點(diǎn)處特征邊的提取效果的好壞取決于其特征邊提取的準(zhǔn)確性。文獻(xiàn)[13]綜合利用二面角、邊角和頂點(diǎn)法向張量矩陣的特征向量等多個(gè)指標(biāo)來(lái)識(shí)別特征點(diǎn)、特征邊和特征邊方向。文獻(xiàn)[14]在其基礎(chǔ)上，采用局部采樣追蹤算法，依據(jù)三角面-三角面的鄰接關(guān)系進(jìn)行特征邊的檢測(cè)，但不能識(shí)別過(guò)渡曲面的特征邊。文獻(xiàn)[15] 則提出一種基于稀疏性優(yōu)化的網(wǎng)格特征檢測(cè)算法，通過(guò)Laplacian光順前后的頂點(diǎn)距離作為度量來(lái)識(shí)別特征，能夠較好地識(shí)別過(guò)渡特征，但這種算法需要進(jìn)行全局優(yōu)化計(jì)算，效率較低。文獻(xiàn)[16]根據(jù)二面角以及相鄰三角形的面積比值來(lái)識(shí)別特征邊，該算法依賴(lài)于局部幾何特性，易識(shí)錯(cuò)特征邊，需要進(jìn)一步處理。近年來(lái)，一些學(xué)者發(fā)展了微分幾何方法，根據(jù)相鄰三角形的法矢夾角及采用二次曲面擬合得到的各網(wǎng)格頂點(diǎn)的主曲率，分兩次提取特征點(diǎn)，并利用三角頂點(diǎn)加權(quán)和均勻化等方法，減少狹長(zhǎng)三角形對(duì)特征點(diǎn)提取的計(jì)算誤差影響，但該算法僅適用于一般的自由曲面，并且將無(wú)序的特征點(diǎn)連接成特征邊的過(guò)程中會(huì)產(chǎn)生中斷現(xiàn)象[17]。文獻(xiàn)[18]在此基礎(chǔ)上根據(jù)主成分分析法(PCA)識(shí)別出特征邊的主方向，從而實(shí)現(xiàn)了特征線的完整連接。文獻(xiàn)[19]利用網(wǎng)格頂點(diǎn)處的法向和曲率半徑等離散微分幾何工具給出了一個(gè)判別特征點(diǎn)的指標(biāo)，但該判別指標(biāo)僅適用于均勻的三角網(wǎng)格模型。文獻(xiàn)[20]在此基礎(chǔ)上改進(jìn)了其特征點(diǎn)的識(shí)別指標(biāo)，使其同樣適用于不均勻三角網(wǎng)格模型。而文獻(xiàn)[21]利用了二次曲面擬合得到的各網(wǎng)格頂點(diǎn)的平均曲率來(lái)提取特征點(diǎn)，然后采用追蹤投影法獲得了完整的特征線。文獻(xiàn)[22]則采用可展曲面擬合各個(gè)曲面網(wǎng)格，然后利用相鄰曲面的求交獲得了特征線，但該算法無(wú)法提取變半徑的過(guò)渡曲面的邊界線。

綜上所述，三角形網(wǎng)格特征邊的提取算法無(wú)論是基于邊的方法還是基于面的方法主要采用了二面角或者頂點(diǎn)處的曲率作為特征邊或特征點(diǎn)的判定條件，但都存在以下兩個(gè)問(wèn)題：① 二面角閾值均為定值，雖能夠快速、準(zhǔn)確地識(shí)別出某些簡(jiǎn)單模型特征邊，不必采用耗時(shí)的曲率計(jì)算方法。但它無(wú)法識(shí)別平滑過(guò)渡邊界處的特征邊，并且二面角閾值的確定一般是憑借經(jīng)驗(yàn)，不夠精確，從而缺乏普適性；② 曲率極值法[23]的頂點(diǎn)處法矢量以及曲率計(jì)算均存在計(jì)算誤差且耗時(shí)，并且無(wú)法識(shí)別曲率變化較小的特征點(diǎn)，只適合于三角形網(wǎng)格分布較均勻的模型，但在網(wǎng)格分布不均勻的地方或存在狹長(zhǎng)三角形網(wǎng)格時(shí)，該方法對(duì)特征點(diǎn)的識(shí)別不如二面角閾值準(zhǔn)確。本文通過(guò)改進(jìn)文獻(xiàn)[10]特征邊的提取算法以及文獻(xiàn)[11]斷點(diǎn)處提取特征邊算法的不足之處，提出了一種新的采用基于邊和面的特征邊二次提取算法。該算法結(jié)合基于邊和基于面的算法的各自優(yōu)點(diǎn)，不僅能夠根據(jù)STL網(wǎng)格模型的精度進(jìn)行自適應(yīng)調(diào)整二面角閾值，還適用于分布不均勻的三角形網(wǎng)格的過(guò)渡曲面的特征邊提取，并且利用本文改進(jìn)的斷點(diǎn)處的特征邊提取算法能夠形成完整的特征邊界，避免了特征邊的中斷。另外，在第二次基于面的特征邊提取過(guò)程中并不需要遍歷所有的三角形面片來(lái)得到各頂點(diǎn)的曲率，計(jì)算效率有所提高。

1 特征邊提取

本文提出一種基于STL網(wǎng)格模型的特征邊提取算法，該算法結(jié)合基于邊和面的各自優(yōu)點(diǎn)，采取針對(duì)不同類(lèi)型的三角形網(wǎng)格邊應(yīng)用不同方法的思想，通過(guò)對(duì)顯性、隱性特征邊的提取，實(shí)現(xiàn)了所有特征邊的高效、完整地提取。具體的算法流程如圖1所示。

圖1 特征邊的二次提取算法流程示意圖

1.1 三角網(wǎng)格模型

三角網(wǎng)格模型通常由一對(duì)線性表表示，M={V，E}，V={Vi|Vi∈R3,2≤i≤n}為頂點(diǎn)V1周?chē)乃许旤c(diǎn)組成的集合，E={ei|ei=V1-Vi，2≤i≤n}為頂點(diǎn)V1周?chē)羞叺募霞?，ei其中為向量。

圖2 頂點(diǎn)V1的一階鄰域

1.2 第一次邊界特征提取

定義1如圖2所示，含有公共邊ei+1的相鄰三角面片其中一個(gè)面片的面法矢量為ni，另一個(gè)面片的面法矢量為ni+1，它們之間法矢量形成的夾角φ就是三角面片公共邊ei+1的二面角。

相鄰三角形的二面角的計(jì)算式表示為：

cosφ=(ni·ni+1)/(‖ni‖·‖ni+1‖)

(1)

二面角的大小能夠反映出模型三角形網(wǎng)格邊的光滑程度，二面角越小，則表示兩個(gè)相鄰的三角形越平滑，當(dāng)二面角為0°時(shí)，表示兩個(gè)三角形共面；反之，二面角越大，超過(guò)了某個(gè)二面角閾值時(shí)，則就會(huì)出現(xiàn)棱線，可視為特征邊。

1.2.1 三角形網(wǎng)格邊的分類(lèi)

為了能夠識(shí)別對(duì)應(yīng)二面角較小的特征邊，文獻(xiàn)[10]利用擾動(dòng)零度以及特征線閾值將三角形的邊分為平面邊、非平面邊以及特征邊。文獻(xiàn)[20]利用兩個(gè)二面角閾值將三角形邊劃分為特征邊、次特征邊以及非特征邊。本文的算法也將需要用到兩個(gè)二面角閾值φ1和φ2，其中φ1是顯性特征邊閾值，φ2隱性特征邊閾值。根據(jù)這兩個(gè)二面角閾值可將三角形的邊劃分為三類(lèi)：若三角形邊所對(duì)應(yīng)的二面角位于[φ1，180°),則稱(chēng)之為顯性特征邊；若該邊所對(duì)應(yīng)的二面角位于(0，φ2]，則稱(chēng)之為隱性特征邊；否則，稱(chēng)之為非特征邊。

1.2.2 特征閾值的確定

CAD中STL網(wǎng)格模型的精度是由參數(shù)Facetres控制的，其取值為(1,10)，F(xiàn)acetres越大，STL網(wǎng)格模型的精度越高，對(duì)應(yīng)的二面角越小。文獻(xiàn)[24]對(duì)STL網(wǎng)格模型的二面角進(jìn)行了統(tǒng)計(jì)分析，發(fā)現(xiàn)二面角大于20°所對(duì)應(yīng)的三角形網(wǎng)格邊比較能夠反映模型的特征。文獻(xiàn)[20]將20°作為特征邊的判定閾值，由于該特征邊閾值是在精度一定的情況下確定的，而CAD中STL網(wǎng)格模型的精度是隨產(chǎn)品發(fā)生變化的，因此常二面角閾值不具有普適性。文獻(xiàn)[10]在Facetres=5時(shí)，采用二面角大于10°的最小二面角的2倍作為特征邊閾值，該方法雖在同等精度下具有自適應(yīng)性，但并不適用于其他的精度等級(jí)。本文在此基礎(chǔ)上確定了顯性特征邊閾值φ1：首先計(jì)算所有三角形網(wǎng)格邊所對(duì)應(yīng)的二面角的平均值β，若β大于20°，則二面角閾值為20°+β(1+λ1)/4；否則二面角閾值為β+β(1-λ1)/4，具體計(jì)算式表示為：

(2)

式中，φ1—顯性特征邊閾值，β—STL網(wǎng)格模型中所有三角形網(wǎng)格邊所對(duì)應(yīng)的二面角的平均值，其中權(quán)值λ1取值(0, 1)，與STL網(wǎng)格模型的精度成正比，在實(shí)際應(yīng)用中Facetres≥5時(shí)，STL網(wǎng)格模型能夠有效地逼近實(shí)體表面，經(jīng)過(guò)反復(fù)試驗(yàn)確定λ1=log(Facetres)。

為了準(zhǔn)確識(shí)別自由曲面以及過(guò)渡曲面邊界處的特征邊，文獻(xiàn)[10]利用擾動(dòng)零度為0.1°作為隱性特征邊的判定閾值，該閾值雖然能準(zhǔn)確地區(qū)分隱性特征邊與非特征邊，但在不同的STL網(wǎng)格模型精度下，擾動(dòng)零度有可能使隱性特征邊的判定數(shù)量增加而降低特征邊的識(shí)別效率，不具有自適應(yīng)性。本文引入了隱性特征邊閾值作為判定條件，以期對(duì)于不同精度下的STL網(wǎng)格模型具有自適應(yīng)性。隱性特征邊閾值的確定方法如下：

(1) 篩選出二面角φ位于[0,λ2β)的網(wǎng)格邊，其中權(quán)值λ2取值(0, 1)，與STL網(wǎng)格模型的精度成反比，本文取值為λ2=1-λ1可滿足條件。

(2) 計(jì)算出符合(1)條件的二面角的平均值，將其作為隱性特征邊閾值φ2，φ2的計(jì)算式表示為：

(3)

式中，n—STL網(wǎng)格模型中所有二面角位于[0,λ2β)的三角形的邊數(shù)。

通過(guò)φ2，能夠快速、準(zhǔn)確查找到位于過(guò)渡曲面邊界處對(duì)應(yīng)的具有較小二面角的隱性特征邊。

本文將所有的顯性特征邊視為特征邊，而對(duì)于隱性特征邊是否為特征邊需要進(jìn)一步地判定。

1.3 第二次邊界特征邊提取

通過(guò)上述1.2節(jié)第一次邊界特征邊的提取，識(shí)別并提取出所有的具有棱角分明的顯性特征邊以及位于過(guò)渡曲面處對(duì)應(yīng)具有較小二面角的隱性特征邊。顯性特征邊一定是特征邊，但隱性特征邊不一定是特征邊，存在是特征邊的可能。利用單純的二面角無(wú)法準(zhǔn)確判斷二面角較小的隱性特征邊是否為特征邊，本文通過(guò)計(jì)算相鄰三角形的近似平均曲率來(lái)判別。

由曲面論可知，零件的棱線、脊線和曲面交線等處曲面的曲率較大。為了計(jì)算每一頂點(diǎn)的曲率，可在頂點(diǎn)V1處建立曲面S(u，v)=(u，v，h(u，v))，其中h(u，v)=au2+buv+cv2。如圖3所示，原點(diǎn)是點(diǎn)V1，h軸為曲面在點(diǎn)V1處的法矢量N1的方向，u，v相互正交且在V的切平面內(nèi)，局部坐標(biāo)系(V1uvh)由絕對(duì)坐標(biāo)系(Oxyz)經(jīng)坐標(biāo)變換得到，即O平移至V1，再旋轉(zhuǎn)使得z軸與h軸重合，此時(shí)u、v可取x、y軸。建立的曲面在V1點(diǎn)處存在無(wú)數(shù)條主法矢量和曲面的法矢量N1重合的曲線，該曲線族的曲率k是曲面的法曲率。法曲率中的極小值k1和極大值k2稱(chēng)為主曲率，對(duì)應(yīng)的曲線的切線方向分別為m1、m2，稱(chēng)為主方向，兩者總是相互垂直。

圖3 點(diǎn)V1的局部坐標(biāo)系

1.3.1 網(wǎng)格頂點(diǎn)法矢量的計(jì)算

為了獲得曲面在點(diǎn)V1的曲率，需要先估算每個(gè)三角形頂點(diǎn)的法矢量。本文采用基于頂點(diǎn)領(lǐng)域平面擬合的方法來(lái)估算網(wǎng)格頂點(diǎn)法矢量。

(4)

要使得頂點(diǎn)V1的鄰域三角形網(wǎng)格的投影面積最大，必須使每個(gè)三角形與投影平面π的法矢量夾角θi最小，也即是鄰域內(nèi)的每個(gè)頂點(diǎn)V1到投影平面的距離di最小。因此，求解頂點(diǎn)鄰域三角形的投影面積最大的投影平面π轉(zhuǎn)化為求解每個(gè)三角形頂點(diǎn)V1到投影平面的距離di最小值問(wèn)題，對(duì)頂點(diǎn)V1的鄰域頂點(diǎn)Vi(2≤i≤n)進(jìn)行平面擬合。

對(duì)平面c0x+c1y+c2z+c3=0進(jìn)行變換得到：

(5)

則：

z=a0x+a1y+a2

(6)

要使鄰域內(nèi)的頂點(diǎn)Vi(xi，yi，zi)，2≤i≤n到平面π的距離的平方和最小，即滿足：

(7)

要使f(a0,a1,a2)→min，將式(9)對(duì)a0、a1、a2求偏導(dǎo)，并令偏導(dǎo)數(shù)為零，得到：

(8)

將式(8)構(gòu)成線性方程：

Bx=D

(9)

解上述線性方程組，可得a0、a1、a2，進(jìn)而得到投影平面π的參數(shù)c0、c1、c2、c3。

采用基于頂點(diǎn)領(lǐng)域平面擬合的方法來(lái)估算網(wǎng)格頂點(diǎn)法矢量，其估算精度與頂點(diǎn)V1的鄰域內(nèi)的三角形頂點(diǎn)與投影平面的擬合精度有關(guān)，而與鄰域內(nèi)三角形的幾何特性關(guān)系不大，降低了對(duì)其依賴(lài)性。這有別于從力學(xué)角度提出的單位法矢量加權(quán)[17-18,21]及以三角網(wǎng)格頂點(diǎn)一階鄰域三角形的形狀因子與頂點(diǎn)到三角形質(zhì)心距進(jìn)行綜合加權(quán)的方法[26]。

1.3.2 平均曲率的計(jì)算

求得各個(gè)頂點(diǎn)的法矢量后，在頂點(diǎn)V1處建立二次曲面S(u，v)=(u，v，h(u，v))，且V1點(diǎn)的一階鄰域頂點(diǎn)Vj(1≤j≤m)在局部坐標(biāo)系下的坐標(biāo)值為(xj，yj，zj)，由m個(gè)鄰域頂點(diǎn)得到的線性方程組為：

(10)

用最小二乘法[27]解上述方程組，可得到曲面S(u，v)。由此可得到該頂點(diǎn)處的主曲率和相應(yīng)的主曲率方向計(jì)算式表示為：

(11)

曲面上的一點(diǎn)的平均曲率是該點(diǎn)主曲率的平均值，求得每個(gè)網(wǎng)格頂點(diǎn)的主曲率k1、k2后就能求得每個(gè)網(wǎng)格頂點(diǎn)的平均曲率H，由式(11)可得：

(12)

由于曲面的平均曲率能夠反映曲面的彎曲程度，利用平均曲率可識(shí)別隱性特征邊。

1.3.3 特征邊的判定指標(biāo)

頂點(diǎn)的平均曲率的估算首先要確定頂點(diǎn)的鄰域，而頂點(diǎn)鄰域內(nèi)三角形網(wǎng)格的稀疏、不均勻性都將影響頂點(diǎn)的局部二次曲面的擬合精度，特別是含有尖銳的顯性特征邊的頂點(diǎn)鄰域，會(huì)造成估算的曲率精度更低，如不適當(dāng)處理，算法還不如二面角判斷準(zhǔn)確。因此本文在選取三角形的各頂點(diǎn)的鄰域時(shí)，先查找到與三角形各頂點(diǎn)共點(diǎn)的三角形，然后剔除與該三角形所對(duì)應(yīng)的二面角大于顯性特征邊閾值的所有三角形，得到了所需要的頂點(diǎn)鄰域。如圖4所示，圖中的細(xì)虛線表示顯性特征邊，f1與f2為兩個(gè)相鄰的三角形，兩個(gè)三角形的頂點(diǎn)(V1～V4)的鄰域三角形(圖中黑色線圈所包圍的與各頂點(diǎn)相連的三角形)不包含顯性特征邊，而三角形f3與f4中的頂點(diǎn)V6與V7的鄰域包含顯性特征邊，需要舍去與該三角形頂點(diǎn)鄰域中與該三角形所對(duì)應(yīng)的二面角大于顯性特征邊閾值的所有三角形，剔除不符合條件的三角形后，頂點(diǎn)V6與V7的鄰域?yàn)閳D中線圈所示。

圖4 相鄰三角形的各頂點(diǎn)鄰域

(13)

(14)

由式(13)和式(14)相減得：

(15)

由式(15)可知，兩個(gè)相鄰的三角形面片的近似平均曲率的差值轉(zhuǎn)換成了兩個(gè)三角形面片的頂點(diǎn)的平均曲率的差值估算，節(jié)省了識(shí)別特征邊的復(fù)雜度和時(shí)間度。

(16)

由式(16)可得：

|k2-k1|≥|k1·k2|λ1

(17)

2 特征邊界的生成

在上述STL網(wǎng)格特征邊判定的過(guò)程中并不是所有的特征邊都能完整地識(shí)別出來(lái)，有時(shí)也會(huì)出現(xiàn)斷邊現(xiàn)象。文獻(xiàn)[11]根據(jù)頂點(diǎn)的度的定義(與某個(gè)頂點(diǎn)相連的特征邊的條數(shù)稱(chēng)為頂點(diǎn)的度)進(jìn)行斷點(diǎn)處特征邊的連接，但該算法僅適合于環(huán)狀過(guò)渡邊界斷點(diǎn)處特征邊的提取，對(duì)于帶狀過(guò)渡曲面特征邊界則易失效。本文改進(jìn)了文獻(xiàn)[11]的算法，提出一種特征邊界生成算法不僅適合于環(huán)狀過(guò)渡曲面特征邊界，還適合帶狀過(guò)渡曲面特征邊界的生成。具體如算法1所示：

算法1斷點(diǎn)處特征邊的提取算法。

Step1新建一個(gè)特征邊表E1從上述1.2節(jié)和1.3節(jié)所提取的特征邊集合U1中取出第一條邊作為初始特征邊，將該邊作為當(dāng)前特征邊，轉(zhuǎn)到Step2。

Step2判斷U1是否為NULL，若為NULL，則停止操作；若不為NULL，則轉(zhuǎn)到Step3。

Step3在集合U1中查找出首結(jié)點(diǎn)坐標(biāo)與當(dāng)前特征邊的尾結(jié)點(diǎn)坐標(biāo)相同的特征邊：1) 若存在，則判斷該邊的尾結(jié)點(diǎn)坐標(biāo)是否與初始特征邊的首結(jié)點(diǎn)坐標(biāo)相同：①若相同，說(shuō)明特征邊形成了首尾相連的封閉特征邊界，將其從U1刪除加入E1中，轉(zhuǎn)到Step1；②若不相同，則將該邊作為當(dāng)前特征邊，將其從U1刪除加入E1中并繼續(xù)尋找與當(dāng)前特征邊的尾結(jié)點(diǎn)的坐標(biāo)相同的特征邊，方法同上①類(lèi)似，直到形成首尾相連的封閉特征邊界為止，轉(zhuǎn)到Step1。2) 若不存在，則在集合U1中查找出所有首結(jié)點(diǎn)坐標(biāo)與當(dāng)前特征邊尾結(jié)點(diǎn)坐標(biāo)相同并且為隱性特征邊的三角形邊形成集合U2, 記U2中最大面積比為smax并從U2中查找到對(duì)應(yīng)面積比值s(即兩相鄰三角形中面積大的三角形比上面積較小的三角形)滿足smax-s≤1的邊形成集合U3，最后選擇U3中與當(dāng)前特征邊的夾角最小的邊作為特征邊加入到E1中，并將其作為當(dāng)前特征邊，繼續(xù)尋找與當(dāng)前特征邊的尾結(jié)點(diǎn)的坐標(biāo)相同的特征邊，方法同上類(lèi)似，直到形成首尾相連的封閉特征邊界為止，轉(zhuǎn)到Step1。

3 實(shí)例分析

采用Visual C++ 6.0編程及OpenGL圖形函數(shù)庫(kù)在SP3 1.60 GHz CPU和1.60 GB內(nèi)存的PC上實(shí)現(xiàn)了本文的算法，還實(shí)現(xiàn)了文獻(xiàn)[10,14]的特征邊的提取算法，并將其與本文的算法進(jìn)行比較，如圖5-圖8所示，同時(shí)在計(jì)算效率方面對(duì)3種算法進(jìn)行了比較，如表1所示。在特征邊提取效果方面，從圖5中的所標(biāo)記的黑色線圈的比較可以看出，文獻(xiàn)[10]的特征邊提取算法無(wú)法識(shí)別并提取對(duì)應(yīng)周長(zhǎng)比值小于閾值的隱性特征邊，文獻(xiàn)[14]無(wú)法提取過(guò)渡曲面的特征邊界。從圖6和圖7可以看出，文獻(xiàn)[10]的算法無(wú)法提取完整的特征邊，對(duì)過(guò)渡曲面邊界處的二面角較小的隱性特征邊的識(shí)別能力較弱。 從圖8中黑色線圈放可以看出，文獻(xiàn)[10,14]提取的特征邊不準(zhǔn)確，存在冗余特征邊。而在計(jì)算效率方面，由表1可得出本文算法在計(jì)算效率方面有所提高，特別是在網(wǎng)格模型規(guī)模較大的時(shí)候。綜上所述，本文特征邊的提取算法彌補(bǔ)了文獻(xiàn)[10,14]的特征邊提取算法的不足之處，更具有健壯性，同時(shí)計(jì)算效率也有所提高。

圖5 模型1的3種特征邊提取算法的比較

圖6 模型2的3種特征邊提取算法的比較

圖7 模型3的3種特征邊提取算法的比較

圖8 模型4的3種特征邊提取算法的比較

模型三角面片數(shù)文獻(xiàn)[10]文獻(xiàn)[14]本文算法14960.1280.0320.02921080.0290.0140.013313360.4230.0760.06444955014.6743.7422.389

4 結(jié) 語(yǔ)

本文改進(jìn)了文獻(xiàn)[10]基于二面角并結(jié)合周長(zhǎng)比實(shí)現(xiàn)特征邊的提取算法以及文獻(xiàn)[11]斷點(diǎn)處特征邊的提取算法，提出了一種新的采用基于邊和基于面的特征邊二次提取算法。算法不僅能夠準(zhǔn)確地識(shí)別二面角較小的過(guò)渡曲面邊界處的隱性特征邊，還能提取完整的特征邊界，彌補(bǔ)了文獻(xiàn)[10]無(wú)法提取過(guò)渡曲面邊界以及文獻(xiàn)[11]對(duì)于帶狀過(guò)渡曲面特征邊界斷點(diǎn)處提取特征邊易失效等算法的不足，具有很好的魯棒性。另外，在第二次基于面的特征邊提取過(guò)程中并不需要遍歷所有的三角形面片來(lái)得到各頂點(diǎn)的曲率，效率有所提高，程序復(fù)雜度降低。

[1] 李康,李靜,孫家.一種改進(jìn)的薄壁文物碎片特征輪廓線提取技術(shù)[J].圖學(xué)學(xué)報(bào),2015,36(2):251-256.

[2] 董天琪,張志毅.直接精簡(jiǎn)密集點(diǎn)云的三角網(wǎng)格重建[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(6):264-267.

[3] Lin Y B,Wang C,Cheng J.Line Segment Extraction for Large Scale Unorganized Point Clouds[J].ISPRS Journal of Photogrammetry and Remote Sensing,2015,102:172-183.

[4] Shoichi T,Tikara H,Masatake H.High-quality vertex clustering for surface mesh segmentation using Student mixture model[J].Computer-Aided Design,2014,46:69-78.

[5] Kim H S,Choi H K,Lee K H.Feature detection of triangular meshes based on tensor voting theory[J].Computer-Aided Design,2009,41(1):47-58.

[6] 張慧娟,耿博,汪國(guó)平.采用張量投票理論的三角網(wǎng)格特征邊提取算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011,23(1):62-70.

[7] Zhao J B,Liu W J,Xia R B.An method of feature line extraction of triangle mesh surface model[C]//Information and Automation(ICIA),2012 International Conference on EEE,2012:602-606.

[8] Park M K,Lee S J,Lee K H.Multi-scale tensor voting for feature extraction from unstructured point clouds[J].Graphical Models,2012,74(4):197-208.

[9] 袁浩,陳倩云,盧章平.機(jī)械零件3D網(wǎng)格模型的特征線提取[J].機(jī)械設(shè)計(jì)與制造,2015(9):211-214.

[10] 楊晟院,舒適,朱少茗.基于STL文件的三角形表面網(wǎng)格的特征線提取[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(4):14-19.

[11] 楊晟院,舒適.一種基于特征線的曲面網(wǎng)格分割方法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(26):166-168.

[12] 呂震,柯映林,孫慶,等.反求工程中過(guò)渡曲面特征提取算法研究[J].計(jì)算機(jī)集成制造系統(tǒng),2003,9(2):1154-157.

[13] Jiao X M,Bayyana N R.Identification of C1and C2disconti- nuities for surface meshes in CAD[J].Computer-Aided Design,2008,40(2):160-175.

[14] 莫建清,何漢武,李晉芳.三角網(wǎng)格模型特征線的局部采樣追蹤算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2016,28(10):1644-1653.

[15] 王偉明,劉秀平,楊周旺,等.網(wǎng)格曲面特征的稀疏性優(yōu)化檢測(cè)算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2013,25(8):1128-1136.

[16] Peng Y H,Chen Y J,Huang B.Region segmentation for STL triangular mesh of CAD object[J].International Journal of Sensor Networks,2015,19(1):62-68.

[17] 劉勝蘭,周儒榮,張麗艷.三角網(wǎng)格模型的特征線提取[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2003,15(4):445-448.

[18] 上官寧,劉斌.三角網(wǎng)格模型特征線提取方法[J].華僑大學(xué)學(xué)報(bào),2010,31(5):487-490.

[19] Di L,Di S P.C1continuities detection in triangular meshes[J].Computer-Aided Design,2010,42(9):828-839.

[20] 張煒,金濤.三角網(wǎng)格特征邊識(shí)別的一種有效方法[J].圖學(xué)學(xué)報(bào),2014,35(5):709-714.

[21] 葛閃,張麗艷,劉勝蘭.一種新的網(wǎng)格曲面上的特征線提取方法[J].機(jī)械科學(xué)與技術(shù),2015,34(8):1181-1185.

[22] Lee W K,Bo P B.Feature curve extraction from point clouds via developable strip intersection[J].Journal of Computat-ional Design and Engineering,2016,3(2):102-111.

[23] 張雨禾,耿國(guó)華,魏瀟然.散亂點(diǎn)云谷脊特征提取[J].光學(xué)精密工程,2015,23(1):310-318.

[24] 袁浩.基于設(shè)計(jì)草圖的產(chǎn)品三維模型檢索研究[D].南京:東南大學(xué),2012.

[25] 王丹.淺談“無(wú)棱”二面角的解法[J].湖北科技學(xué)院學(xué)報(bào),2015(8):201-204.

[26] 肖和,楊旭靜,鄭娟.離散三角網(wǎng)格模型頂點(diǎn)法矢量估算[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(19):196-200.

[27] 李二濤,張國(guó)煊,曾虹.基于最小二乘的曲面擬合算法研究[J].杭州電子科技大學(xué)學(xué)報(bào),2009,29(2):48-51.

ANALGORITHMFOREXTRACTINGFEATUREEDGEOFSTLTRIANGULARMESHMODEL

Wang Junhui Chen Xing*Deng Yiming

(FacultyofMechanicalEngineeringandMechanics,NingboUniversity,Ningbo315211,Zhejiang,China)

As it is hard to recognize feature edges of the free-form surface from STL model, a method of extraction of feature edges is proposed. At first, using edge-based method, the threshold value of the dihedral angle was computed adaptively, and the explicit feature edge was identified accordingly. Secondly, using the least squares method, the approximate curvatures of triangles were obtained according to the computed average curvatures of vertexes. The feature edges were then determined in terms of the curvature difference of adjacent triangles with the implicit feature edge. Finally, a complete feature edges were generated by using an improved algorithm for extracting feature edges at the breakpoints. Experimental results demonstrate that the proposed method can effectively extract the feature edges of free-form surface from STL model, which has good robustness.

STL model Triangle mesh Feature extraction Dihedral angle Average curvature

TP391.41

A

10.3969/j.issn.1000-386x.2017.10.050

2017-01-10。寧波大學(xué)研究生科研創(chuàng)新基金資助項(xiàng)目(G16069)。汪俊輝，碩士生，主研領(lǐng)域：材料成型CAD/CAE。陳興，副教授。鄧益民，教授。