知識驅動的三角網(wǎng)格模型分割

賀 強，張樹生，白曉亮

(西北工業(yè)大學 現(xiàn)代設計與集成制造技術教育部重點實驗室，710072 西安)

逆向工程是根據(jù)已有實物或模型重建計算機輔助設計(computer aided design，CAD)模型的過程.基于特征的逆向工程技術是產(chǎn)品創(chuàng)新設計的有效手段，分割是其中的關鍵技術之一［1］.國內外學者提出了多種分割算法，如區(qū)域生長［2－4］、分水嶺［5－7］、聚類［8－9］、特征線提?。?0－11］等.區(qū)域生長方法通過選取不同類型的種子元素，搜索與種子具有相似性質的點以構成曲面.該類算法的主要缺點是高度依賴初始種子的選取，會產(chǎn)生過分割.分水嶺方法計算頂點的曲率或其他高度函數(shù)來確定子網(wǎng)格之間的分界線(即分水嶺)，然后根據(jù)分界線將模型分割為多個子網(wǎng)格.由于噪聲，高度函數(shù)的估算必然有一定的離散性，因此該方法容易發(fā)生過分割.文獻［7］通過動態(tài)擬合曲面的方式提高了曲率估算的精確性，從而提高了分水嶺算法對噪聲的魯棒性.聚類方法將具有相同屬性的元素聚類，實現(xiàn)網(wǎng)格分割.文獻［8］根據(jù)頂點間的測地線距離，利用模糊聚類的方式實現(xiàn)了網(wǎng)格模型的層次分割.文獻［9］將平面、球面和圓柱面擬合的最小誤差作為聚類準則對模型的三角形進行聚類.這類方法在一定程度上降低了曲率或其他幾何屬性估算的準確性對分割的影響，但常常丟失曲面間的拓撲關系.特征線提取利用法矢和曲率信息識別出模型中尖銳的邊和頂點，連接它們形成分割依據(jù)的特征線.這類方法在處理含過渡面的模型時，特征線的完整性差.文獻［11］在消除了過渡區(qū)域的低分辨率網(wǎng)格上提取特征線，然后將特征線映射到原始模型上，從而得到相對完整的特征線.

綜上，當前的分割算法幾乎不以高層次的特征為目標，因此分割的結果難以體現(xiàn)意義.本文將模型分割成曲面，進而提取模型所含有的、具備一定工程語義的特征，從而從曲面這一基本造型元素和工程語義的角度來體現(xiàn)分割的意義，為基于特征的逆向工程中的關鍵步驟——CAD 模型重建中的特征重建和約束施加奠定了基礎.

1 知識庫的構成

工程領域產(chǎn)品的三角網(wǎng)格模型通常能夠分解成基本的曲面元素，如平面、圓柱面、圓錐面和球面等.這些幾何元素滿足一定拓撲約束關系的有機組合就形成了具有工程語義的、可以更高層次反映設計意圖的基本造型體特征和加工特征.知識庫作為有意義分割的知識先驗，應該能反映該領域具有代表性的幾何結構及其工程語義.因此，知識庫由包含了長方體、圓柱體、圓臺體、孔、臺階、凸塊、型腔和槽等特征的以面為節(jié)點的屬性鄰接圖表示構成.每個特征的屬性鄰接圖的邊的屬性對應為特征的面與面之間的平行、垂直和相交的凹凸性等關系.知識庫可以根據(jù)需要進行種類的擴充.

2 基于二次曲面擬合誤差和曲率的曲面分割

二次曲面頻繁出現(xiàn)在工程產(chǎn)品的外形上，甚至很多產(chǎn)品外形完全由平面、圓柱面、圓錐面和球面組成［12］.因此，逆向工程中，以這幾類曲面的擬合誤差作為分割的準則能體現(xiàn)分割的意義.此外，對復雜模型，提取簡單類型的曲面比復雜類型要可靠得多，因此按照曲面類型的幾何復雜性指定一個分割次序是很有意義的.除二次曲面外，模型中還存在自由曲面，對其分割則需采用基于曲率的方法，本文改進了噪聲魯棒的法向量投票方法［13］來計算曲率.本文曲面分割的整體流程如圖1 所示.

圖1 曲面分割流程

2.1 誤差和曲率的計算

曲面擬合誤差和曲率的計算必須準確且高效才能滿足網(wǎng)格分割效果和時間效率的要求.本文采用如下方式計算曲面的擬合誤差和曲率.

平面待擬合點集的協(xié)方差矩陣為

式中:wi是頂點vi一階鄰接三角形的面積和.n 是擬合點的數(shù)量.矩陣Mc的三個特征值中最小的一個對應的特征向量即為擬合平面的法向，擬合誤差計算如下

球面 球面由球心(x0，y0，z0)和半徑r 確定，將球面方程轉化為如式(3)所示的向量表示，采用線性最小二乘法即可求出球心、半徑.

則擬合誤差為

圓柱面圓柱面由其軸線上任意一點o，軸線的單位矢量n，橫截面圓的半徑r 確定.圓柱面上任意點的法向量都與n 垂直.因此，圓柱面上任意一點的法向量都在過原點，法向為n 的平面上.首先對擬合點的法向量采用上述擬合平面的方式求出圓柱面的軸線方向n.以擬合平面過程的協(xié)方差矩陣的三個特征值對應的特征向量建立坐標系，將點投影到該坐標系下.在二維空間中，以圓方程擬合投影點集，得到圓心和半徑.將圓心變換到原始坐標系下即為o，則圓柱面的擬合誤差為

圓錐面圓錐面由錐頂點p，軸線方向n，圓錐角的一半a 確定.圓錐面上任意一點的法矢與n的夾角為π/2－a，因此圓錐面上點的法向量構成平面(n，－sin a).首先擬合頂點的法矢量求得圓錐的軸線方向和圓錐的錐頂角.然后將獲得的參數(shù)帶入圓錐面方程，通過線性最小二乘擬合剩余的待求參數(shù)，則圓錐面的擬合誤差為

式中:βi是pvi與n 的夾角.

曲率 頂點v 的二階鄰接三角形集合為Mv，由如圖2 所示的標號為1，2 的三角形組成.集合中的三角形Fi的重心為ci，法矢為Nfi，面積為Ai.它在v 上的“投票”Ni定義為

對Mv中每一個三角形計算其對v 的投票，則Mv的投票效應矩陣為

其中，Amax是模型中三角形面積的最大值.σ=gm/3，gm是模型網(wǎng)格邊的平均邊長，gi是ci到v 的測地距離.由于測地距離計算非常耗時，因此本文采用如圖2 所示的方式來近似計算.對標號為1 的三角形直接利用其重心到頂點v 的歐式距離近似，對標號為2 的三角形，若是與一階三角形共邊，則用重心到邊的歐式距離與頂點v 到垂足的歐式距離之和近似;若是與一階三角形共頂點，則用重心到該頂點的距離與頂點v 到該頂點距離之和近似.投票效應矩陣為3×3 的對稱矩陣，特征值為λ0≤λ1≤λ2，兩個主曲率為:k1=3λ1－λ2，k2=3λ2－λ1.

圖2 頂點v 的二階鄰接三角形集合

2.2 初步的分割方法

設M(V，E，T)是三維空間中的二維流形的三角網(wǎng)格模型.V 是模型頂點的集合，E 是連接頂點的邊的集合，T 是模型中的三角面片的集合.M對應的圖G(C，A)定義如下:圖節(jié)點集合C 中每一個節(jié)點對應T 中的一個三角面片，M 中兩個相鄰的三角面片對應的圖節(jié)點構成的邊形成圖邊集合A，如圖3a 所示，虛線網(wǎng)絡即為網(wǎng)格模型對應的圖結構.建立了模型對應的圖后，利用上述曲面擬合誤差和曲率的計算方法來計算圖邊的權值.圖邊的權為該邊兩個節(jié)點對應三角形擬合某種曲面的誤差或曲率差.具體的分割流程如下:

首先以平面的擬合誤差作為圖中邊的權值，分割出模型中所包含的平面，然后分別以球面、圓柱面和圓錐面的擬合誤差作為權值進行對應曲面類型的網(wǎng)格分割，對圖中已經(jīng)確定了曲面類型的節(jié)點，不再分割.最后對剩余的節(jié)點，計算其對應的網(wǎng)格頂點的曲率，圖邊的權值更新為對應節(jié)點所包含三角形頂點的曲率差.本文的曲率差定義為頂點平均曲率的差的絕對值.分割的結果統(tǒng)一標記為“其他”.每類曲面的分割流程如下:

Step 1 根據(jù)邊的權值為所有圖邊構建一個小頂堆，并設置邊折疊的閾值ε1和對應曲面分割完成的閾值ε2.首先獲取堆頂?shù)倪?，以該邊的任意一個節(jié)點作為種子節(jié)點，如圖3(b).

Step 2 折疊與種子節(jié)點直接連接的且邊的權值在ε1之內的所有邊，生成一個新的圖節(jié)點，并更新鄰接關系和邊的權值，如圖3(c)，刪除小頂堆中所有已經(jīng)折疊的邊.

Step 3 以新生成的圖節(jié)點作為種子節(jié)點，進行Step2 的處理，直至所有與種子節(jié)點直接連接的邊的權值均大于閾值ε1，則該節(jié)點對應的三角形集合構成一個曲面，對該節(jié)點進行相應的曲面信息的標記，如圖3(d).

Step 4 從小頂堆中取出堆頂?shù)倪?，以該邊的任意一個節(jié)點作為種子節(jié)點.轉至步驟Step 2，Step 3 直至堆頂?shù)倪叺臋嘀荡笥讦?.

圖3 網(wǎng)格模型對應的圖及其分割示意

完成曲面分割后，會形成如圖4 所示的聚類圖.

圖4 曲面分割結果的示意

圖4 中的邊表示對應曲面類型的兩個子網(wǎng)格擁有相同的邊界.因此曲面分割的結果不僅確定了各個子網(wǎng)格對應的曲面類型，還獲得了曲面間的拓撲連接關系，為后續(xù)的特征分割打下了堅實的基礎.

3 基于知識的特征分割

根據(jù)初步分割的結果，為模型建立以面為節(jié)點的屬性鄰接圖(此處稱為大圖).以知識庫中的屬性鄰接圖作為輸入子圖，這樣從工程語義角度體現(xiàn)分割意義的問題被轉換為在大圖中尋找同構子圖的問題.匹配出大圖中與知識庫中同構的子圖所對應的子網(wǎng)格模型并賦予相應的語義信息就完成了特征分割.

屬性鄰接圖的構建:通過上述初步分割過程，網(wǎng)格模型被分解成平面、球面、圓柱面、圓錐面等曲面的集合(包括曲面的參數(shù)信息和鄰接關系).根據(jù)這些信息，可將模型轉化成一種屬性鄰接圖.在該屬性鄰接圖中，每一個圖節(jié)點對應模型曲面集合中的一個曲面，曲面面的幾何屬性(類型、幾何參數(shù))作為節(jié)點的屬性;節(jié)點與節(jié)點之間的關系對應模型中面與面之間的關系，常見的關系包括相鄰、鄰邊的凹凸性、平行、垂直、同軸和共面等.具體構建步驟如下:

Step 1 遍歷組成網(wǎng)格模型的曲面集合中的每一個面，同時對應地創(chuàng)建一個屬性鄰接圖節(jié)點，將面的幾何屬性作為對應屬性鄰接圖節(jié)點的屬性.

Step 2 對集合中的每兩個面，利用初步分割得到的聚類圖中的圖節(jié)點之間的鄰接關系和面的幾何參數(shù)計算出兩者之間的關系，作為其對應的屬性鄰接圖的節(jié)點之間的關系.

局部匹配算法:在模型的屬性鄰接圖中搜索與知識庫中的圖同構的子圖被證明是一個NP 完全問題［14］.NP 完全問題，即完全多項式復雜程度的非確定性問題，是不存在多項式時間算法問題的一個子類，它的特征是如果它們中的一個是多項式可解的話，那么所有其他問題也是多項式可解的.該類問題求解的時間復雜度較高.文獻［14］的方法被認為能夠代表子圖同構問題當前的技術發(fā)展水平.該算法的關鍵在于增量地建立連接圖并使用方便的剪除規(guī)則和設計了低內存消耗的數(shù)據(jù)結構.本文在此基礎上，充分利用了模型的自身特征，如考慮模型面的類型極其鄰接關系等，來使得模型屬性鄰接圖中所含有的、與知識庫中的圖同構的子圖能夠較快地匹配.具體過程如下:

設知識庫中的某個特征的屬性鄰接圖g(V，E)的鄰接矩陣為MB×B，模型曲面分割構成的屬性鄰接圖G1(V1，E1)的鄰接矩陣為MI×I.圖g 的節(jié)點集合V 中的節(jié)點數(shù)量為B;圖G1的節(jié)點集合V1中的節(jié)點數(shù)量為I;E，E1分別為兩個圖的邊的集合.設置一個映射矩陣MB×I，其中任意一個元素mij(0 ≤i ≤B－1，0 ≤j ≤I－1).若圖g 的第i 個節(jié)點與圖G1中的第j 個節(jié)點屬性相同且與兩個節(jié)點直接連接的邊的數(shù)量一致，則mij=1;否則mij=0.圖g 與圖G1子圖同構就是存在這樣一個映射矩陣，其每一行有且只有一個1，每一列至多只有一個1.

映射矩陣MB×I設置完成后，開始子圖同構匹配搜索.定義兩個集合V2，V3分別用于存儲搜索過程中2 個圖上已匹配的節(jié)點，初始時都置為空.從MB×I的第一行開始，從左到右查找值為1 的列.對第i 行，若其第j 列的值為1，并且該列未被占用，則表示找到一個可能匹配的頂點對:圖g 的第i 個節(jié)點和圖G1的第j 個節(jié)點對應，將這兩個節(jié)點分別加入到V2，V3中.如果新加入的2 個節(jié)點在最終的同構映射中確實是對應匹配的節(jié)點對，則當前圖g 中已匹配上的節(jié)點集合V2與圖G1中已匹配上的節(jié)點集合V3構成的子圖必定也是同構的.根據(jù)這一原理，通過測試V2構成的子圖與V3構成的子圖是否同構來判斷新找到的列是否有效;如果兩個集合構成的圖子圖同構，則該新找到的列是有效的，設置占用標志，進入下一行;反之，在當前行繼續(xù)搜索下一個有效列;如果當前行搜索完成都沒有找到一個有效列，則退回上一行，并且從上一行已經(jīng)占用列的下一列開始搜索.

4 實驗結果

在VS2008 的環(huán)境下，利用C++語言實現(xiàn)了算法，在主頻1.8 G，內存1 G 的PC 機上運行程序.從分割成曲面、分割成特征和算法時間效率三個方面來驗證本文提算法的有效性.

4.1 分割成曲面

為了驗證本文曲面分割的效果，將本文初步分割的結果與文獻［9］進行對比.圖5(a)為待分割的三角網(wǎng)格模型，圖5b 為文獻［9］在聚類數(shù)目為18 下的分割結果(每一種顏色對應一個聚類).圖5(c)為本文的曲面分割的結果(對應各個曲面類型的子網(wǎng)格單獨顯示).圖6 為含有自由曲面類型的模型的分割.圖6(b)為文獻［9］聚類數(shù)目為9 的分割結果.圖5 的結果表明，以平面、圓柱面、球面的擬合誤差為曲面分割準則，本文的初步分割能取得與文獻［9］相當?shù)男Ч?本文曲面分割的各個子網(wǎng)格精確對應相應的曲面，也證明了本文曲面擬合誤差計算的精確性滿足分割的要求.圖6 結果表明，文獻［9］由于缺少對自由曲面的處理，因此不能有效分割出自由曲面類型的網(wǎng)格，而本文的算法則增加了這一能力.此外，文獻［9］的方法不能得到曲面間的鄰接關系和曲面類型信息，因此不能獲得更高層次的分割結果.

圖5 模型1 的分割與比較

圖6 模型2 的分割與比較

4.2 分割成特征

根據(jù)本文初步分割得到的曲面集合及其相互之間的鄰接關系，以知識庫中的屬性鄰接圖作為輸入，匹配出模型中對應知識庫中的特征的子網(wǎng)格.圖7 為模型1 根據(jù)知識庫分割得到對應特征的網(wǎng)格部件.實驗結果表明，分割的結果能顯著地體現(xiàn)工程語義，為逆向工程的特征重建打下了堅實的基礎.

4.3 分割執(zhí)行時間

文獻［9］的算法具有極高的時間效率.本文雖然增加了一類曲面的擬合誤差和曲率的計算，但采用了逐次分割的策略，每次只需要計算一種曲面的擬合誤差并只對部分頂點計算曲率，因而時間效率也較高.表1 為本文初步分割的計算時間與文獻［9］的比較以及本文對模型1 分割出對應特征類型的子網(wǎng)格時，圖同構匹配的時間.

圖7 模型1 的體現(xiàn)工程語義的特征分割

表1 曲面分割和圖匹配的執(zhí)行時間

5 結論

本文針對機械領域的三角網(wǎng)格模型，設計了一種快速的、能從曲面和工程語義兩個角度體現(xiàn)分割意義的分割算法.建立了指導網(wǎng)格有意義分割的先驗知識庫;逐次地分割出模型中的平面、球面、圓柱面、圓錐面，并利用曲率將剩余的模型分割成曲面，同時獲得了曲面的類型信息和拓撲連接關系;利用知識庫的特征的屬性鄰接圖匹配出具有工程語義的網(wǎng)格部件從而完成了網(wǎng)格模型有意義的分割.實驗證明，對不含復雜自由曲面的模型，本文在曲面這一基本造型元素和工程語義兩個層次上取得了有意義的分割結果，為基于特征的CAD 模型重建奠定了基礎.本文主要從加工特征和基本造型特征方面體現(xiàn)工程語義，然而從模型重用的角度而言，機械領域中常見的典型結構的重用粒度更高，因此，如何從模型重用的角度來體現(xiàn)分割的意義是一個有意義的研究方向.

［1］Ye Xiuzi，Liu Hongzheng，Chen Lei，et al.Reverse innovative design—an integrated product design methodology［J］.Computer-Aided Design，2008，40(7):812－827.

［2］LAVOUE G，DUPONT F，BASKURT A.A new CAD mesh segmentation method based on curvature ［J］.Computer-Aided Design，2005，37(1):975－987.

［3］ZUCKERBERGER E，TAL A，SHLAFMAN S.Polyhedral surface decomposition with applications［J］.Computers＆ Graphics，2002，26 (5):733－743.

［4］GUILLAUME L，F(xiàn)LORENT D，ATILLA B.Constant curvature region decomposition of 3D meshes by a mixed approach vertex-triangle［J］.Journal of WSCG，2004，12 (1):245－252.

［5］PAGE D L，KOSCHAN A F，ABIDI M A.Perceptionbased 3D triangle mesh segmentation using fast marching watersheds［C］//Proceeding of Computer Vision and Pattern Recognition.Madison，Washington DC，USA:IEEE，2003:27－32.

［6］ZHOU Yinan，HUANG Zhiyong.Decomposing polygon meshes by means of critical points［C］//Proceedings of the 10thInternational Multimedia Modeling.Washington DC，USA:IEEE，2004:187－196.

［7］錢江，陳志揚，葉修梓，等.噪聲魯棒的分水嶺網(wǎng)格分割算法［J］.計算機輔助設計與圖形學學報，2008，20 (3):310－315.

［8］KATZ S，TAL A.Hierarchical mesh decomposition using fuzzy clustering and cuts［J］.ACM Transactions on Graphics，2003，22(3):954－961.

［9］ATTENE M，F(xiàn)ALCIDIENO B，SPAGNUOLO M.Hierarchical mesh segmentation based on fitting primitives［J］.The Visual Computer，2006，22 (3):181－193.

［10］LEE Y，LEE S，SHAMIR A，et al.Mesh Scissoring with Minima Rule and Part Salience［J］.Computer－Aided Geometric Design，2005，22(5):444－465.

［11］白曉亮，張樹生.多分辨率三角網(wǎng)格基礎上的區(qū)域分割［J］.中國機械工程，2009，20(9):1097－1101.

［12］VANCO M，HAMANN B，BRUNNETT G.Surface reconstruction from unorganized point data with quadrics［J］.Computer Graphic Forum，2008，27(6):1593－1606.

［13］PAGE D L，SUN Y，PAIK J，et al.Normal vector voting:crease detection and curvature estimation on large，noise meshes［J］.Graphical Models，2002，64(1):199－229.

［14］CORDELLA L，F(xiàn)OGGIA P，SANSONE C，et al.Performance evaluation of the VF graph matching algorithm［C］//Proceedings of the 10th international conference on image analysis and processing.Washington DC，USA:IEEE，1999:1172－1177.