趙云成，王 琳 ，盛步云，趙飛宇

1.武漢理工大學(xué) 機電工程學(xué)院，武漢 430070

2.湖北省數(shù)字制造重點實驗室，武漢 430070

1 引言

近年來，隨著Web 技術(shù)的發(fā)展，計算機輔助設(shè)計與數(shù)字幾何處理均有向Web環(huán)境發(fā)展的趨勢?！叭S掃描+在線重構(gòu)”的逆向建模方式，憑借低門檻和便捷性，逐漸成為在線三維建模軟件的主要建模方式。將三維掃描儀掃描重構(gòu)的三角網(wǎng)格模型轉(zhuǎn)化為可參數(shù)化設(shè)計的實體模型，需要對無法編輯的三角網(wǎng)格模型進(jìn)行分割處理，并分別將每塊分割區(qū)域重構(gòu)為可參數(shù)化驅(qū)動的基本實體特征[1]。從完整的三角網(wǎng)格模型中劃分和識別特征區(qū)域的研究，有助于實現(xiàn)基于三維掃描的逆向?qū)嶓w建模，提升產(chǎn)品逆向設(shè)計效率，對大眾參與的計算機輔助設(shè)計領(lǐng)域發(fā)展具有重要意義[2]。在Web環(huán)境下實現(xiàn)網(wǎng)格分割，不僅要求保證三角網(wǎng)格模型分割的準(zhǔn)確性，而且須確保分割算法具備較低的計算復(fù)雜度以適應(yīng)在線高并發(fā)環(huán)境，從而滿足Web 環(huán)境對數(shù)字幾何處理高效性、實時性的要求。

國內(nèi)外學(xué)者對應(yīng)用于不同幾何處理領(lǐng)域的三維模型分割做了大量的研究，并提出了一系列網(wǎng)格模型分割方法。根據(jù)分割方式的不同，模型分割大致可分為三類：聚類分析法[3-4]、區(qū)域增長法[5]和邊界檢測法[6]?；诰垲惖姆指罘椒ㄖ饕ㄟ^聚類算法，對網(wǎng)格模型中具有相同幾何信號的點和面片進(jìn)行迭代聚類，常用于模型塊分割。文獻(xiàn)[7]將三角網(wǎng)格模型向譜空間映射，進(jìn)而通過K-means聚類實現(xiàn)分割。文獻(xiàn)[8]基于最小主曲率以及特征向量對掃描后自由曲面模型進(jìn)行塊分割，并用于牙齒掃描模型的語義分割。文獻(xiàn)[9]在GPU上基于高斯曲率和平均曲率對面片進(jìn)行頂點聚類，實現(xiàn)了GPU 環(huán)境下網(wǎng)格模型的分割。這類算法基于全局信號的迭代聚類，分割效率較低，且分割結(jié)果難以預(yù)測，不滿足Web環(huán)境下幾何處理應(yīng)具備較低計算復(fù)雜度的要求。基于區(qū)域生長的模型分割方法主要將局部幾何信號作為分割驅(qū)動信號，通過選取種子點和相應(yīng)的生長規(guī)則將滿足條件點和面片合并在同一區(qū)域中。文獻(xiàn)[10]通過計算測地距離選取種子點，基于凹凸信號合并相似區(qū)域，實現(xiàn)對三角網(wǎng)格模型的面分割。這類算法雖然具有較高的分割效率，但是區(qū)域增長易受到驅(qū)動信號的影響，且容易存在過分割等現(xiàn)象。另一類算法則是基于邊界的方法，通過在模型上構(gòu)造符合分割特點的分割線，并以分割線為邊界，將模型分割為多個獨立的特征面。文獻(xiàn)[11]提出了基于分割邊界學(xué)習(xí)的分割線提取算法，該方法通過大量的網(wǎng)格模型人工分割結(jié)果來訓(xùn)練分類器，進(jìn)而獲取網(wǎng)格模型的分割邊界。該類方法雖然能夠獲得較好的分割結(jié)果，但是在前期訓(xùn)練需要繁瑣的數(shù)據(jù)采集，因而算法總體效率不高，不適用于Web環(huán)境下高效分割網(wǎng)格模型。

根據(jù)以上分析，本文提出一種基于凹特征區(qū)域分割線提取的在線三角網(wǎng)格模型分割方法。首先采用微分幾何方法對模型各頂點的離散曲率進(jìn)行計算，然后根據(jù)模型的曲率特性設(shè)定閾值來計算判斷模型的凹特征區(qū)域，在此凹特征區(qū)域提取出分割線并進(jìn)行閉合和光順處理，最后基于分割線將模型分割成不同的區(qū)域。實驗表明，本文方法能夠?qū)崿F(xiàn)Web環(huán)境下高效快速準(zhǔn)確的分割三維模型，且分割的結(jié)果具有可預(yù)測性，適用于工程實踐，便于后期參數(shù)化重建研究。

2 三角網(wǎng)格模型分割流程

傳統(tǒng)的基于曲率的網(wǎng)格分割方法往往依據(jù)單個曲率特征來實現(xiàn)網(wǎng)格模型的分割[12]。或基于曲率信號迭代聚類，或根據(jù)曲率結(jié)合特征信號進(jìn)行輪廓特征提取。同樣是基于曲率分割，不同的方法運用不同的曲率特征，文獻(xiàn)[13]算法利用主曲率，文獻(xiàn)[14]算法利用高斯曲率與平均曲率，有的方法基于最小值準(zhǔn)則分割模型，有的則基于平坦性原則利用二次曲面（如可展曲面）控制分割過程，還有的算法利用語義或人的視覺原理指導(dǎo)網(wǎng)格分割。

本文將平坦性規(guī)則與最小值準(zhǔn)則結(jié)合起來，在滿足Web環(huán)境下計算復(fù)雜度較低的要求的情況下，綜合高斯曲率、平均曲率以及最小主曲率，通過二次提取特征點方法來提取網(wǎng)格模型特征區(qū)域，避免了多次全局信號計算。進(jìn)而在凹特征區(qū)域中獲取優(yōu)化分割邊界線，實現(xiàn)Web環(huán)境下網(wǎng)格模型的高效準(zhǔn)確分割。

如圖1 所示，本文方法的分割大致流程為：首先根據(jù)離散曲率公式計算網(wǎng)格模型各頂點的離散曲率特性；其次根據(jù)平坦性規(guī)則，利用高斯曲率與平均曲率提取模型中凹區(qū)域，在凹區(qū)域中利用最小曲率閾值提取凹特征區(qū)域，并由此特征區(qū)域提取和優(yōu)化形成閉合分割線，實現(xiàn)對網(wǎng)格模型的塊分割。

2.1 網(wǎng)格模型離散曲率估計

在逆向工程中，包含凹形狀的特征區(qū)域是基于特征建模等操作的重要考慮部分，而高斯曲率KG和平均曲率KH是判斷網(wǎng)格模型頂點凸凹特性的重要指標(biāo)。對PSB中人工分割結(jié)果分析可知，分割邊界的頂點一般在負(fù)的最小主曲率處。因此在通過高斯曲率KG和平均曲率KH確定模型凹區(qū)域之后，定義最小曲率閾值KT。將低于最小曲率閾值KT的邊界點視為特征點，提取模型凹特征點集，作為網(wǎng)格劃分邊界線的基礎(chǔ)。

目前離散曲率估計方法有很多。其中文獻(xiàn)[15]提出的Voronoi圖方法比較靈活和準(zhǔn)確地估算了任意三角網(wǎng)格模型頂點的曲率。考慮Web 環(huán)境下計算低復(fù)雜度的要求，在滿足曲率估算盡量準(zhǔn)確的情況下，本文采用頂點的一環(huán)鄰域進(jìn)行計算，得到三角網(wǎng)格模型頂點vi的平均曲率計算公式：

式中，φk、ψk分別為邊的對角，如圖2（a）所示。Amix表示頂點vi鄰域內(nèi)三角面片對應(yīng)的區(qū)域面積，其公式為：

圖1 網(wǎng)格模型分割方法總體流程圖

其中，Svi表示頂點vi鄰域Voronoi圖劃分區(qū)域（灰色部分）的面積[15]，由于vi鄰域三角形夾角θk大小不同，面積取值規(guī)則不同，如圖2（b）、（c），定義三角面片T的三個頂點vi、vj、vj+1，定義邊的夾角為φ，i邊的夾角為ψ。不同角度取值規(guī)則如下：i

根據(jù)微分幾何中GaussBonnet 定理[16]，可以通過下列公式得到高斯曲率：

圖2 網(wǎng)格頂點離散曲率估計示意圖

式中，KG(vi)為頂點vi的高斯曲率，θk表示頂點vi與其鄰域第k個三角面片的夾角，Amix表示頂點vi鄰域內(nèi)三角面片對應(yīng)的區(qū)域面積。

頂點vi處的主曲率可由離散曲率和平均曲率計算得到：

式中，K1(vi)和K2(vi)分別為最大、最小主曲率。

2.2 三維模型凹特征區(qū)域提取

頂點的高斯曲率和平均曲率反映了頂點的凹凸性，由于模型可能存在噪點，僅僅根據(jù)離散頂點本身的曲率特性無法判斷區(qū)域的凹凸性。本文通過微分幾何特性綜合各頂點鄰域的高斯曲率與平均曲率來判斷模型凹區(qū)域，并根據(jù)歸一化最小主曲率閾值在優(yōu)化后的凹區(qū)域中提取出模型的凹特征區(qū)域點集。首先根據(jù)頂點鄰域的高斯曲率和平均曲率篩選出凹點集區(qū)域，在凹區(qū)域劃分中，噪點存在可能導(dǎo)致出現(xiàn)細(xì)碎劃分，影響凹特征點集提取。噪點存在處往往區(qū)域較小且連通性較差，因而本文根據(jù)鄰域面積和曲率分布狀況優(yōu)化和刪除頂點數(shù)量過少凹點集，在此凹區(qū)域中基于最小主曲率篩選出凹特征點集。不同模型的最小主曲率范圍不同，考慮分割邊界盡量在最小主曲率處，本文采用提取凹區(qū)域中頂點主曲率較小點集作為凹特征點集。具體步驟如下：

步驟1 計算網(wǎng)格模型各點離散曲率。計算網(wǎng)格模型中各頂點vi的高斯曲率KG和平均曲率KH。

步驟2 凹點集初提取。遍歷每個頂點vi，獲取頂點vi以及頂點vi的一階鄰域各點的離散曲率特性。判斷該點一環(huán)鄰域中所有點的高斯曲率KG和平均曲率KH是否滿足KG＜0&&KH＜0，將滿足條件的點加入凹點集中。

步驟3 凹點集區(qū)域擴展。計算步驟2 中獲得每個頂點vi一階鄰域頂點在凹點集區(qū)域中所形成的凹三角形面積Sconcave與頂點vi一鄰域所有頂點形成面積Sall的比值M，若M＞threshold1，將頂點vi鄰接點加入凹點集區(qū)域。

步驟4 凹點集區(qū)域刪除。計算步驟3 得到凹點集區(qū)域中所有連通分支頂點數(shù)量N以及平均高斯曲率KH,將滿足N＜threshold2&&KH＞0 的連通分支刪除，得到最終的凹點集區(qū)域。

步驟5 凹特征區(qū)域提取。計算凹區(qū)域點集中點的最小主曲率K2，通過設(shè)定歸一化閾值KT，將凹點集中主曲率較小部分點加入凹特征區(qū)域。

如圖3 所示，在凹特征區(qū)域的提取過程中，凹點集區(qū)域擴展中面積比值M過小易造成點集擴展過多，對區(qū)域優(yōu)化效果不好，在凹點集區(qū)域刪除過程中對擴展后頂點數(shù)量較少以及高斯曲率較大的凸區(qū)域(KH＞0)進(jìn)行刪除。本文結(jié)合實驗測試結(jié)果，最終確定threshold1取值0.8，threshold2取值6，凹區(qū)域特征提取效果較優(yōu)。由于初提取的區(qū)域最小主曲率分布往往不太一致，因而本文采用歸一化閾值。在設(shè)定KT過程中，本文通過對PSB 模型人工分割數(shù)據(jù)集中眾多相同或相似輪廓進(jìn)行閾值估計，并結(jié)合實驗結(jié)果最終設(shè)定歸一化閾值KT為0.5，取得較好的區(qū)域提取結(jié)果。

2.3 分割線獲取和優(yōu)化方法

2.3.1 初始分割線生成

如圖3Teddy 模型凹特征區(qū)域提取所示，特征點在網(wǎng)格邊界附近呈區(qū)域分布，不能作為最終的分割邊界，為了獲取精確的分割線，需要在特征點集中區(qū)域提取出分割線來。在滿足Web環(huán)境低計算復(fù)雜度要求條件下，考慮分割線生成盡可能平滑。對于三維空間的凹特征點集，本文提出一種基于球面半徑搜索方法來連接特征點生成初始分割線，在確定初始種子點后，以最大特征邊長為半徑，搜索鄰域內(nèi)與連接邊夾角最大的特征點，形成分割線。具體步驟如下：

步驟1 移除G中離群點。計算每個特征點vi到其余特征點的平均歐氏距離假定平均歐式距離服從高斯分布，求得的均值μ與方差σ。將分布在±3σ之外的特征點視為離群點并移除。如圖4（a）、（b）所示，紅色離群點被移除。

步驟2 設(shè)定初始種子點。選定凹特征點集中兩鄰邊夾角大于135°的點作為初始種子點，加入到組點序列中。如圖4（c）所示，選定vp作為特征線起點。

步驟3 確定搜索半徑R。遍歷凹特征區(qū)域中所有的邊，找到長度最大的邊，將最大長度記為Rmax，以vp為球心，以Rmax為半徑確定搜索區(qū)域。

步驟4 尋找分割線的連續(xù)點。獲取搜索區(qū)域的特征點集合，計算球心點vp與特征點組成線和球心點與前一點組成邊的夾角ω，選取夾角最大的點加入到組點序列。如圖4（c）所示，夾角最大，選取v b加入組點序列。

步驟5 獲取所有特征點。球心點移動到下一特征點，重復(fù)步驟4，直到遍歷完所有特征點。

步驟6 生成初始分割線。將搜索得到的組點序列進(jìn)行連接得到初步的分割線。如圖4（d）所示。

圖4 初始分割線生成方法圖

2.3.2 分割線閉合及光順

在初始分割線生成之后，往往存在模型分割線不閉合特征，多為一側(cè)具有明顯凹特征，另一側(cè)較為平坦或凸起，大致為L 形狀。如圖3 中圈出區(qū)域所示Teddy 模型腿部與后臀部連接處較為平整，而軀干與腿部處存在凹特征區(qū)域，導(dǎo)致生成的分割線無法確保分割區(qū)域的封閉性。本文提出基于射線的邊界線閉合方法，通過捕獲射線與面片的交點獲得分割線形狀，通過修正交點獲取閉合分割線。

步驟1 構(gòu)造射線。為確保射線由模型內(nèi)部發(fā)出，選擇構(gòu)成邊界線的質(zhì)心點vg為射線起點，通過連接vg與端點va、vb構(gòu)建單位向量es、ee，求得兩向量夾角Φ=arccos(es·ee)，之后構(gòu)造n條單位夾角為φ的射線 (0＜φ ＜Φ)，分別與模型面片交于{P1,P2,…,Pn}。

步驟2 計算交點Pi。通過建立空間Octree搜索結(jié)構(gòu)，并通過矢量分解判斷射線l與三角面片是否相交。構(gòu)造射線參數(shù)方程，計算射線與三角面片交點Pi。

步驟3 修正交點。鑒于Pi位于三角面片T的內(nèi)部，為避免網(wǎng)格細(xì)分而增加計算復(fù)雜度，須對Pi進(jìn)行修正。如圖5（b）所示，即計算Pi與T三個頂點vi、vj、vk的歐氏距離，選取距離最小的頂點作為修正后的交點vc，表示為：

步驟4 邊界閉合。運用Dijsktra最短路徑算法[17]求得從va到vb并經(jīng)過所有修正后交點的最短路徑，形成閉合邊界線Lb。

步驟5 分割線光順。采用主動輪廓模型（Snakes）[18]，定義邊界線上頂點的內(nèi)部能量Eint與外部能量Eext，借助貪心算法[19]，使曲線上的頂點迭代地向局部范圍中能量最小位置偏移，獲得光順分割線。

以圖5為例，通過連接vg與v1、v7確定夾角，發(fā)出7條射線分別與不同三角面片交于Pa、Pb、Pc、Pd、Pe、Pf、Pg。計算出交點坐標(biāo)，Pa、Pb、Pc、Pd、Pf、Pe、Pg經(jīng)過修正得到va、vb、vc、ve、vf、vg、vh。之后運用Dijsktra 最短路徑算法形成閉合線如圖5（c），光順處理后得到分割線如圖5（d）。

圖5 邊界線閉合及光順圖

如圖6所示，最終得到Teddy模型的分割效果。

圖6 Teddy模型最終分割效果圖

3 實驗與結(jié)果分析

為了驗證算法的有效性，本文依托開源數(shù)字幾何處理軟件MeshLabJS，通過開發(fā)網(wǎng)格分割Filter插件實現(xiàn)，并部署于Apache 服務(wù)器，運用WebGL 的幾何處理及圖形渲染功能，實現(xiàn)完全在瀏覽器中的在線網(wǎng)格分割與網(wǎng)格渲染。在軟、硬件方面，采用Windows 7 Ultimate x64操作系統(tǒng)以及WebStorm 2016.3.1開發(fā)環(huán)境，服務(wù)器PC采用Intel Xeon-E5 2620V4 2.1 GHz CPU 與32 GB RAM，客戶端PC采用Intel?i5-7200U 2.5 GHz CPU與8 GB RAM。

目前，評價三維模型分割的優(yōu)劣主要是以下幾方面：

（1）視覺效果

視覺效果主要是指模型在分割之后，基于人類視覺效果最小值準(zhǔn)則，能否將模型分割成具有意義的各個分塊，分割結(jié)果是否存在過分割。

（2）分割一致性

目前普林斯頓大學(xué)提供了一套完整的模型分割評判標(biāo)準(zhǔn)[20]。其中蘭德指數(shù)（Rand Index）衡量各類算法與人工分割數(shù)據(jù)的一致性。本文采用評價指標(biāo)蘭德指數(shù)，對普林斯頓數(shù)據(jù)集進(jìn)行測試，將本文方法與文獻(xiàn)[21]中提供的9種算法進(jìn)行比較。

（3）算法的運行速度

一個良好的網(wǎng)格模型分割算法除了需要在模型分割的視覺效果和結(jié)果精確度兩方面找到最佳平衡外，還需要有較高的處理速度。本文采用相同模型分割處理消耗時間，將本文方法與蘭德指數(shù)平均值較低的3種算法進(jìn)行時效性對比。

圖7 展示了本文算法在PSB 數(shù)據(jù)集中部分具有代表性的三維模型分割效果。圖8 展示了本文算法在COSEG形狀數(shù)據(jù)集中部分具有代表性三維模型的分割效果，將不同分割區(qū)域中的三角面片標(biāo)記為不同顏色。從分割視覺效果上看，絕大多數(shù)三維分割的視覺效果符合人的認(rèn)知要求。

圖7 本文方法對普林斯頓數(shù)據(jù)集部分模型分割效果圖

圖8 本文方法對COSEG數(shù)據(jù)集部分模型分割效果圖

表1 Rand Index評價表

在分割一致性上，分別采用本文算法與文獻(xiàn)[20]中提供的9 種算法進(jìn)行比較。利用蘭德指數(shù)作為評價指標(biāo)，對普林斯頓數(shù)據(jù)集中19種模型進(jìn)行測試。表1展示了本文選擇19種模型在不同評估算法下的Rand Index評價結(jié)果。蘭德指數(shù)越小說明在當(dāng)前分割下效果越好。從表1中可以看出，對于具有明顯分支結(jié)構(gòu)的模型，如Airplane、Chair、Table、Mech、Bearing 等模型，本文算法具有較優(yōu)的分割效果，分割蘭德指數(shù)優(yōu)于大多數(shù)算法。

然而在對Human、Glass、Armadillo 等模型分割時，本文算法雖然能分割出模型大致語義，但是由于模型存在太多模糊細(xì)節(jié)特征，因而分割效果不夠理想。從圖9平均蘭德指數(shù)圖可以看出，本文方法在分割一致性上優(yōu)于大部分算法，但是不如深度學(xué)習(xí)和WCSeg[22]的分割方法。其中深度學(xué)習(xí)方法的分割一致性最高，本文在蘭德指數(shù)平均值上接近WCSeg方法。

圖9 測試模型Rand Index平均值

在算法運行速度方面，表2展示了本文算法與蘭德指數(shù)較低的3種算法在分割6種模型時的時效性。由表2可以看出，本文算法由于沒有費時的迭代聚類過程，也沒有復(fù)雜度較高的計算，相較于WCSeg 算法在分割效率上要高，另外相較于機器學(xué)習(xí)方法，不需要考慮數(shù)據(jù)集采集以及人工訓(xùn)練時間。

表2 算法時效性分析 s

為了綜合評價性能較優(yōu)的4種網(wǎng)格分割算法，采用熵值法，分別從分割時間、分割差異（CD）、漢明距離（HD）、基于缺失率的漢明距離（HD-Rm）、基于誤報率的漢明距離（HD-Rf）、蘭德指數(shù)（RI）、全局一致性誤差（GCE）和局部一致性誤差（LCE）共8個指標(biāo)進(jìn)行綜合評價。熵值法充分考慮指標(biāo)對評價結(jié)果的決定性作用，削弱了主觀因素對評價結(jié)果的影響，有助于獲取更為客觀、真實的評價結(jié)果。將4 種網(wǎng)格分割方法的8 項指標(biāo)值分別統(tǒng)計于表3。

表3 不同網(wǎng)格分割算法指標(biāo)值

在對所有指標(biāo)進(jìn)行負(fù)向歸一化處理后，考慮到在線網(wǎng)格分割要求算法具備較低的時間復(fù)雜度，因此分割時間的主觀權(quán)值均取0.15，其余指標(biāo)主觀權(quán)值取0.10，求得各指標(biāo)熵權(quán)值，并統(tǒng)計于表4。最終，根據(jù)相對權(quán)重向量與歸一化后的指標(biāo)矩陣，求得6 種方案的綜合評分，見表5。由綜合評分結(jié)果可知，在以網(wǎng)格分割快速性為主要導(dǎo)向的前提下，本文方法在算法執(zhí)行效率、快速性方面具備明顯優(yōu)勢的同時，能夠兼顧分割可視化效果與分割快速性，適宜在Web環(huán)境下執(zhí)行。

表4 各指標(biāo)的熵權(quán)值

表5 4種方案綜合評分

4 結(jié)束語

本文提出了一種面向Web的快速網(wǎng)格分割方法，其目的是為解決Web 環(huán)境下網(wǎng)格的在線快速分割。首先綜合離散曲率特性提取出模型的凹特征區(qū)域，利用特征區(qū)域點集提取出模型的閉合分割線，最終實現(xiàn)在具有較好分割效果情況下對網(wǎng)格模型的快速分割，并通過模型數(shù)據(jù)集對分割結(jié)果進(jìn)行分析，驗證了本研究對在Web環(huán)境下實現(xiàn)網(wǎng)格的數(shù)字幾何處理具有一定的意義。

由于本文方法應(yīng)用于Web 環(huán)境下掃描得到網(wǎng)格模型實體建模的區(qū)域分割，因而分割高效準(zhǔn)確性要求較高，未來研究應(yīng)側(cè)重于兩方面：（1）對網(wǎng)格分割算法進(jìn)行優(yōu)化研究；（2）考慮研究基于在線機器學(xué)習(xí)的網(wǎng)格分割方法。