羅年猛，殷吉功，劉云華，朱 林

（華中科技大學(xué) 國家CAD支撐軟件工程技術(shù)研究中心，湖北 武漢430074）

0 引 言

由于輕量化模型只有三角面片信息，缺乏幾何特征信息，導(dǎo)致眾多應(yīng)用受到較大的限制，例如標(biāo)注、測量、裝配、工藝制作、模型重建等。為了解決上述問題，需要對(duì)輕量化模型進(jìn)行特征識(shí)別。

目前國內(nèi)外針對(duì)輕量化模型的特征識(shí)別已提出了很多算法，這些算法主要集中在2類模型上，一是通過三維測量點(diǎn)云構(gòu)造的輕量化模型，它的特征識(shí)別算法有區(qū)域生長法、迭代聚類法、骨架抽取法、分水嶺法、層次分解及合并法、譜分析法等，文獻(xiàn) ［1］中對(duì)各種分割算法進(jìn)行了介紹；二是通過三維CAD轉(zhuǎn)換的輕量化模型，它的特征識(shí)別算法有張量投票法［2］、 聚類法［3］、 分水嶺法［4，5］、 混合方法［6，7］等。

針對(duì)CAD轉(zhuǎn)換的輕量化模型，文獻(xiàn) ［3］通過把三角形劃分為稀疏三角形和稠密三角形，針對(duì)這2部分分別運(yùn)用不同的算法進(jìn)行網(wǎng)格分割及特征識(shí)別。文獻(xiàn) ［4］改進(jìn)了傳統(tǒng)的分水嶺分割算法，通過加點(diǎn)很好地解決了分水嶺算法無法有效處理三角化不均勻的CAD網(wǎng)格模型的問題，并且支持過渡面的分割。文獻(xiàn) ［6］提出了一種特征的二次提取及表面分割混合算法，首先采用基于邊的方法把平面和稀疏網(wǎng)格表面提取出來，然后采用基于頂點(diǎn)的方法，通過區(qū)域生長實(shí)現(xiàn)其它表面區(qū)域的分割及特征提取。文獻(xiàn) ［7］提出了一種方法能夠自動(dòng)識(shí)別CAD網(wǎng)格模型中的特征，該方法主要適用于包含自由曲面的鈑金零件。文獻(xiàn) ［8］利用計(jì)算出來的曲率值及平面與二次曲面不同的性質(zhì)逐類識(shí)別，并通過雙三次B樣條曲面擬合技術(shù)識(shí)別自由曲面。

本文針對(duì)CAD系統(tǒng)轉(zhuǎn)換的輕量化模型中特征數(shù)據(jù)連續(xù)性的特點(diǎn)，提出一種新的快速特征識(shí)別算法。輕量化模型中特征數(shù)據(jù)的連續(xù)性是指組成一個(gè)特征的所有三角面片在輕量化文件中是連續(xù)分布的。由于CAD模型大部分是由平面和柱面、錐面、球面等二次曲面特征組成，所以本文首先對(duì)模型中的平面進(jìn)行特征識(shí)別，再對(duì)被分割開的區(qū)域進(jìn)行柱面、錐面、球面以及自由曲面的特征識(shí)別。該算法減少了三角面片的遍歷次數(shù)，因此速度快、效果好。

1 算法概述

CAD輕量化網(wǎng)格模型由一個(gè)一個(gè)的特征組成，一個(gè)特征的所有三角形在輕量化文件中是連續(xù)的、線性的。輕量化文件可以看作以三角形為節(jié)點(diǎn)的鏈表，如圖1所示。

輕量化文件也可以表示成

其中，S表示整個(gè)輕量化文件，Si、Sj（S1…Sn）表示輕量化文件中連續(xù)三角面片的組合，一個(gè)組合就是網(wǎng)格模型中的一個(gè)特征。在輕量化文件中一個(gè)特征最多只與前后兩個(gè)特征相連，當(dāng)在輕量化文件中準(zhǔn)確識(shí)別其中一個(gè)特征后其它特征相應(yīng)的也被準(zhǔn)確的分割，由此可保證特征識(shí)別的準(zhǔn)確性。

CAD系統(tǒng)導(dǎo)出的輕量化文件都可以作為本文的輸入數(shù)據(jù)，文件格式可以是任何輕量化文件格式，如STL、STEP203、STEP214、X＿T等。圖2中的模型是從Solidworks系統(tǒng)中導(dǎo)出的輕量化文件，文件格式為STL（ASCII形式），圖中標(biāo)示了輕量化文件和輕量化模型中的特征對(duì)應(yīng)關(guān)系。

本文對(duì)導(dǎo)入的輕量化數(shù)據(jù)直接根據(jù)面片法向量和平均法向量進(jìn)行平面識(shí)別，無需建立整體拓?fù)浣Y(jié)構(gòu)；然后根據(jù)高斯映射識(shí)別柱面和錐面特征；再對(duì)剩余的區(qū)域建立局部拓?fù)浣Y(jié)構(gòu)，利用最小二乘法進(jìn)行分割；最后對(duì)分割后的區(qū)域根據(jù)高斯曲率識(shí)別球面特征。

2 特征識(shí)別算法

2.1 平面識(shí)別

在進(jìn)行平面識(shí)別之前，先介紹以下基本概念及規(guī)則：

法向量F1：輕量化文件中的面片法向量；

法向量F2：根據(jù)三角面片的頂點(diǎn)計(jì)算出來的法向量，即平均法向量；

規(guī)則1：一個(gè)面片的F1向量與F2向量相等，誤差在ε范圍之內(nèi)；

規(guī)則2：兩三角面片F(xiàn)1向量相等，誤差在ε范圍之內(nèi)；

規(guī)則3：兩三角面片F(xiàn)2向量相等，誤差在ε范圍之內(nèi)；

平面識(shí)別算法具體如下：

（1）從輕量化文件中的第一個(gè)面片開始，記錄此面片為Previous，下一個(gè)面片為Current，依次遍歷所有的面片；

（2）判斷Previous面片是否滿足規(guī)則1。若不滿足轉(zhuǎn)至（3）；否則把Previous面片歸為平面區(qū)域Plane i，判斷Previous與Current是否滿足規(guī)則1、規(guī)則2和規(guī)則3。

1）如果滿足，把Current面片歸為Plane i；

2）否則，平面區(qū)域Plane i在Current面片處斷開，到此一個(gè)平面特征識(shí)別完畢，繼續(xù)查找下一個(gè)平面特征。

（3）若沒有面片，算法結(jié)束；否則令Previous＝Current，繼續(xù)下一個(gè)面片并記為Current，繼續(xù) （2）。

平面的識(shí)別是最簡單的，也是最準(zhǔn)確的。之前的文獻(xiàn)對(duì)平面特征識(shí)別時(shí)只是利用規(guī)則2或者規(guī)則3進(jìn)行識(shí)別，在CAD網(wǎng)格模型中不是很可靠。因?yàn)镃AD模型中有很多的過渡特征，特別是機(jī)械模型，當(dāng)平面與相對(duì)比較小的過渡圓角相連時(shí)，過渡線兩側(cè)的三角形法向量有可能相等（誤差ε）。這種情況下識(shí)別出來的平面就沒有嚴(yán)格的邊界，實(shí)際上就是識(shí)別錯(cuò)誤。而通過以上3條規(guī)則就可以很好地識(shí)別出來平面特征，保證有嚴(yán)格的邊界。本文算法還可以區(qū)別多棱柱面和圓柱面，特別是當(dāng)圓柱面剖分的精度比較粗糙時(shí)，剖分的結(jié)果和多棱柱三角化的結(jié)果完全一樣，如圖3所示。把面片1和面片2的法向量p1和p2單位化并平移到一點(diǎn)。當(dāng)網(wǎng)格模型為多棱柱時(shí)，面片1和面片2的法向量關(guān)系為圖 （a），即重合；當(dāng)網(wǎng)格模型為圓柱時(shí)，面片1和面片2的法向量關(guān)系為圖 （b）。由此即可分割棱柱面和圓柱面。

圖3 圓柱和多棱柱中面片法向量比較圖：左側(cè)圖形為多棱柱及圓柱三角化后的模型，其中多棱柱時(shí)面片1和面片2在一個(gè)側(cè)面上，圖 （a）和圖 （b）為多棱柱和圓柱時(shí)面片1和面片2的法向量平移到一點(diǎn)的結(jié)果

這樣把平面識(shí)別出來，平面的識(shí)別過程實(shí)際上也是分割其它區(qū)域的過程，同樣把輕量化文件分割開。平面識(shí)別出來后其它區(qū)域就是不同的特征區(qū)域，或者是不同特征區(qū)域的組合。

2.2 柱面和錐面特征識(shí)別

對(duì)被平面特征識(shí)別后分割開的各個(gè)子區(qū)域分別進(jìn)行柱面特征識(shí)別，識(shí)別柱面采用高斯映射的方法。把單個(gè)子區(qū)域三角形的面片法向量移動(dòng)到原點(diǎn)，然后由原點(diǎn)和2個(gè)法向量的終點(diǎn)組成小三角形，這樣依次進(jìn)行，最終形成新的三角面片特征。在這些形成的新三角特征中按0中的算法查找平面特征，不同的是判斷條件只有2個(gè)面片的平均法向量。這些平面特征中組成三角形的2個(gè)頂點(diǎn) （3個(gè)點(diǎn)中除了原點(diǎn)）就是柱面特征的一部分。這樣得到的一個(gè)平面特征就是原模型中的柱面特征。由于平面特征較容易識(shí)別，此方法通過轉(zhuǎn)換把對(duì)柱面特征的識(shí)別轉(zhuǎn)換為對(duì)平面特征的識(shí)別。這里的柱面泛指圓柱面、橢圓柱面。

對(duì)已剩下的各個(gè)子區(qū)域分別處理，把子區(qū)域中的三角面片進(jìn)行高斯映射。如果高斯映射落在高斯球的小圓上，則說明這些三角面片組成的是錐面特征［8］。

2.3 其它特征識(shí)別

剩下區(qū)域的三角形比較密集、規(guī)則，可以應(yīng)用曲率估計(jì)算法。首先建立局部區(qū)域的拓?fù)浣Y(jié)構(gòu)，拓?fù)洳捎冒脒吔Y(jié)構(gòu)，然后根據(jù)三角形的所有相鄰三角形利用最小二乘法估算該三角形的曲率值，通過指定曲率值的閾值來進(jìn)行區(qū)域劃分，被劃分的單獨(dú)區(qū)域就是一個(gè)特征。

目前已有很多算法估算離散網(wǎng)格的曲率，但大多數(shù)都是估算三角形頂點(diǎn)的曲率值。而為了分割輕量化文件，要估計(jì)三角形的整個(gè)形態(tài)，然后在三角形之間進(jìn)行分支，所以要計(jì)算三角面片的曲率。文獻(xiàn) ［9］對(duì)面片的曲率值估算的較準(zhǔn)確，但是已知條件比較苛刻，需要知道面片的頂點(diǎn)法向量。文獻(xiàn) ［10］中描述了10多種曲率估計(jì)算法，及各種算法的理論背景、公式意義和適用范圍。這里采用最小二乘法估算三角面片的曲率值。具體做法是，以三角面片的中心O為原點(diǎn)，建立局部二次曲面

如圖4所示，h軸為三角面片在輕量化文件中的法向量方向，u、v相互正交。以三角面片的頂點(diǎn)和頂點(diǎn)的相鄰點(diǎn)來擬合曲面S（u，v），用最小二乘法就可以得到曲面參數(shù)a、b、c、e、f、g。曲面在原點(diǎn)的曲率就是三角面片中心O的曲率，由曲面的第一、第二基本公式，有

再有K ＝k1k2，H ＝ （k1＋k2）／2，得

其中，k1為最大主曲率，k2為最小主曲率。

圖4 局部坐標(biāo)系

根據(jù)上述計(jì)算出的曲率值，通過指定閾值對(duì)區(qū)域進(jìn)行分割，具體分割算法流程如圖5所示。區(qū)域分割后根據(jù)高斯曲率和平均曲率是否為常值來進(jìn)行球面特征的識(shí)別。其它區(qū)域認(rèn)為是自由曲面特征。在實(shí)際情況中，有可能識(shí)別平面、柱面和錐面特征之后整個(gè)輕量化文件就已經(jīng)被完全分割開，無需再對(duì)其進(jìn)行分割。

3 實(shí)驗(yàn)結(jié)果及分析

本文算法已在本課題組開發(fā)的Intevue三維系統(tǒng)中實(shí)現(xiàn)，環(huán)境為Visual C＋＋2005和Hoops。圖6為一簡單的CAD輕量化網(wǎng)格模型，上部為半球面，下部為高度較小的柱面，本文可以很好的對(duì)其進(jìn)行區(qū)域分割。圖6中的圖（a）為輕量化網(wǎng)格模型，圖 （b）為模型面片圖，圖 （c）為特征識(shí)別結(jié)果，其中黃色區(qū)域?yàn)槠矫妫{(lán)色區(qū)域?yàn)橹?，紅色區(qū)域?yàn)榍蛎?。此模型?duì)于文獻(xiàn) ［3］來說，由于柱面三角形和球面三角形在大小、形狀上非常接近，在區(qū)分稠密三角形和稀疏三角形時(shí)無法自動(dòng)把球面和柱面分開，導(dǎo)致此情況無法自動(dòng)識(shí)別。

圖6 零件輕量化網(wǎng)格模型

圖7 （a）是文獻(xiàn) ［7］中的示例，本文對(duì)此模型的識(shí)別結(jié)果如圖7（b）所示。該模型的識(shí)別過程比較簡單，沒有文獻(xiàn) ［7］中的算法那么繁瑣。該模型共有13個(gè)特征：6個(gè)平面、5個(gè)柱面、1個(gè)錐面和1個(gè)環(huán)面，其在輕量化文件中的連接關(guān)系如圖7（c）所示。平面特征識(shí)別之后剩下3個(gè)區(qū)域，再識(shí)別柱面之后就可把整個(gè)輕量化模型分割完畢。該輕量化網(wǎng)格模型只需分割平面和柱面，并不需要再對(duì)其它區(qū)域進(jìn)行分割，只需判定其它區(qū)域具體的特征類型即可。特征識(shí)別結(jié)果：黃色區(qū)域?yàn)槠矫嫣卣鳎t色區(qū)域?yàn)殄F面特征，藍(lán)色區(qū)域?yàn)橹嫣卣?。圖7中的 （b1）和 （b2）為分割后的局部放大圖，從圖中可知各個(gè)特征之間的是有嚴(yán)格邊界的。圖8是本文算法與文獻(xiàn) ［7］中算法的結(jié)果比較，其中圖 （a）為本文算法特征識(shí)別結(jié)果，而圖 （b）為文獻(xiàn) ［7］中的結(jié)果［3］。由結(jié)果可知本文算法比文獻(xiàn) ［7］中算法識(shí)別質(zhì)量高。

圖7 零件輕量化網(wǎng)格模型 （a）原模型；（b）特征識(shí)別結(jié)果，其中 （b1）、（b2）識(shí)別結(jié)果局部放大圖；（c）特征數(shù)據(jù)連接關(guān)系

圖8 零件識(shí)別結(jié)果比較

圖9 為一支架零件模型，圖 （a）為原模型，圖 （b）為特征識(shí)別結(jié)果，各個(gè)特征之間用不同的顏色表示。1）、2）、3）為特征識(shí)別結(jié)果的局部放大圖。圖10展示了多個(gè)輕量化零件模型的特征識(shí)別結(jié)果。

圖9 支架輕量化網(wǎng)格模型 （a）原模型，（b）特征識(shí)別結(jié)果，1）、2）、3）識(shí)別結(jié)果局部放大圖

圖10 輕量化網(wǎng)格模型的特征識(shí)別結(jié)果

本文算法與文獻(xiàn) ［8］中算法比較，本文算法的優(yōu)勢有：①本文算法無需在導(dǎo)入數(shù)據(jù)時(shí)就建立整個(gè)網(wǎng)格模型的三角形拓?fù)浣Y(jié)構(gòu)，只在識(shí)別三角形比較均勻的局部區(qū)域建立拓?fù)浣Y(jié)構(gòu)，此時(shí)三角面片數(shù)量已大幅減少，占用內(nèi)存也較少；②在識(shí)別過程中比較次數(shù)較少，因?yàn)楸疚乃惴ㄖ恍璞容^前后2個(gè)三角形即可，而后者要比較一個(gè)三角形的所有鄰域三角形，增加了識(shí)別時(shí)間；③本文算法在準(zhǔn)確識(shí)別平面特征的基礎(chǔ)上已有完整的特征邊，故跟平面相連的所有特征也有嚴(yán)格的邊界。

4 結(jié)束語

本文利用CAD輕量化文件中特征數(shù)據(jù)的連續(xù)性，逐次分割輕量化文件。首先對(duì)較容易的平面特征進(jìn)行識(shí)別，然后根據(jù)高斯映射和最小二乘法識(shí)別其它特征。通過本文算法可以快速準(zhǔn)確地識(shí)別CAD模型中最常見的基本特征：平面、柱面、錐面、球面等特征。不足之處在于閾值的選擇，不同的閾值區(qū)域分割的結(jié)果可能不同。如果出現(xiàn)閾值選擇不當(dāng)?shù)葐栴}，自動(dòng)識(shí)別結(jié)果就不能滿足要求，本文支持交互式調(diào)整或者交互式識(shí)別。但是交互降低了自動(dòng)化程度，因此，閾值的自動(dòng)化選擇是下一步的重點(diǎn)研究工作。

［1］Alexander Agathos，Ioannis Pratikakis，Stavros Perantonis，et al.3Dmesh segmentation methodologies for CAD applications［J］.Computer Aided Design ＆ Applications，2007，4（6）：827－841.

［2］SHU Zhenyu，WANG Guozhao.Fast mesh segmentation algorithm based on tensor voting ［J］.Journal of Zhejiang University （Engineering Science），2011，45 （6）：999－1005 （in Chinese）.［舒振宇，汪國昭.基于張量投票的快速網(wǎng)格分割算法 ［J］.浙江大學(xué)學(xué)報(bào) （工學(xué)版），2011，45 （6）：999－1005.］

［3］Dong Xiao，Lin Hongwei，Xian Chuhua，et al.CAD mesh model segmentation by clustering ［J］.Computers ＆ Graphics－Uk，2011，35 （3）：685－691.

［4］YANG Fanqin.Research on the approach to CAD mesh model segmentation ［D］.Hangzhou：Zhejiang University，2007（in Chinese）.［楊釩沁.面向CAD應(yīng)用的三維網(wǎng)格分割算法研究 ［D］.杭州：浙江大學(xué)，2007.］

［5］QIAN Jiang，CHEN Zhiyang，YE Xiuzi.Noise robust watershed mesh segmentation algorithm ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2008，20 （3）：310－315（in Chinese）.［錢江，陳志楊，葉修梓.噪聲魯棒的分水嶺網(wǎng)格分割算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)及圖形學(xué)學(xué)報(bào)，2008，20（3）：310－315.］

［6］DONG Fangmin，XIAO Renbin，ZHONG Yifang，et al.A hybrid approach to feature segmentation for triangle meshes of mechanical CAD model ［J］.China Mechanical Engineering，2007，18 （4）：382－387 （in Chinese）.［董方敏，肖人彬，鐘毅芳，等.機(jī)械CAD三角網(wǎng)格模型的特征表面分割混合算法［J］.中國機(jī)械工程，2007，18 （4）：382－387.］

［7］Sunil V B，Pande S S.Automatic recognition of features from freeform surface CAD models ［J］.Compute Aided Design，2008，40 （4）：502－517.

［8］Wang Jun，Yu Zeyun.Surface feature based mesh segmentation［J］.Computers ＆ Graphics－Uk，2011，35 （3）：661－667.

［9］Zhihong M，Guo C，Yanzhao M，et al.Curvature estimation for meshes based on vertex normal triangles ［J］.Compute Aided Design，2011，43 （12）：1561－1566.

［10］QI Baoming.Curvatures estimation and the improvement of Taubin’s method on triangle mesh ［D］.Dalian：Dalian University of Technology，2008 （in Chinese）.［齊寶明.三角網(wǎng)格離散曲率估計(jì)和Taubin方法改進(jìn) ［D］.大連：大連理工大學(xué)，2008.］