賈流洋+莊澤民

摘 要：網(wǎng)格模型的簡化要兼顧保持細節(jié)特征和快速這兩個基本原則，而對網(wǎng)格模型進行分割可以有效提高模型簡化效率。提出了一種基于頂點局部特征度的網(wǎng)格模型分割算法。分割時，網(wǎng)格模型要求分割成大小適中、密度差異相對明顯的連續(xù)區(qū)域，區(qū)域邊緣平滑，且所有三角形均屬于某個區(qū)域。通過引入頂點局部特征度的概念對區(qū)域生長算法進行了改進。

關(guān)鍵詞關(guān)鍵詞：網(wǎng)格模型；頂點局部特征度；區(qū)域分割；區(qū)域生長

DOIDOI：10.11907/rjdk.161477

中圖分類號：TP312

文獻標識碼：A ：1672-7800（2016）008-0021-02

0 引言

所謂網(wǎng)格模型區(qū)域分割，就是對網(wǎng)格模型按照拓撲特征或者幾何特征進行分割，獲得一組有一定外觀意義、若干相互連通的子網(wǎng)格的操作，包括區(qū)域生長法、層次聚類法和迭代聚類法等。

區(qū)域生長法可以生成滿足網(wǎng)格某一特征的區(qū)域，實現(xiàn)模型簡化的目的。本文研究了一種改進的區(qū)域生長算法，首先提出了頂點的局部特征度概念，采用一種簡單的計算方法近似估值頂點曲率，設(shè)定頂點局部特征度的閾值作為生長條件對不平滑區(qū)域進行平滑處理。

1 頂點局部特征度

對于大多數(shù)三維網(wǎng)格模型來說，不同細節(jié)部位具有不同的分辨率，因而其復(fù)雜程度也是不同的。例如，模型中的棱邊、凹痕、尖端、褶皺等關(guān)鍵區(qū)域的曲率較大，其它區(qū)域的曲率相對較小。常見的三維網(wǎng)格模型是由點、邊、面分段組合而成的線性曲面，無法用傳統(tǒng)的二次求導(dǎo)方法來計算其曲率，只能人為定義求取某點處曲率的近似估值。本文采用相對簡便的方法計算頂點的局部特征度，作為該點曲率的近似估值來反映網(wǎng)格模型某點位置的不平整程度。在不增加計算復(fù)雜度的前提下，本文將頂點的局部特征度定義如下：

2 區(qū)域預(yù)分割

網(wǎng)格模型的區(qū)域分割要服務(wù)于三角形網(wǎng)格模型簡化需要：首先分割區(qū)域比較大（也不宜過大）， 太小的區(qū)域很難控制簡化過程，太大的區(qū)域使得分割意義大打折扣；分割區(qū)域的邊緣不平滑也給模型的簡化處理帶來麻煩， 所以三角形網(wǎng)模型的區(qū)域分割遵從以下原則[5]：①將網(wǎng)格模型盡可能分割成大小適中且連續(xù)的區(qū)域；②各個區(qū)域的三角形網(wǎng)格稠密程度區(qū)分明顯；③分割區(qū)域的邊緣平滑；④不存在任何三角形不屬于任何區(qū)域問題。

本文采用區(qū)域生長法進行區(qū)域擴展以便分割出連續(xù)區(qū)域。采用區(qū)域生長法進行分割要處理好3個問題：①如何選取種子；②如何設(shè)定生長準則；③如何設(shè)定終止條件。這3個問題處理不好會直接影響到區(qū)域生長效果，進而影響模型簡化質(zhì)量。

如何選擇種子是區(qū)域生長的關(guān)鍵。三角網(wǎng)格模型可以采用頂點、邊或三角形作為種子生長，本文著重研究頂點作為種子的情況。如圖1（a）所示，頂點P1是區(qū)域中正在生長的種子頂點，那么凡是以P1為頂點的三角形都是生長區(qū)域的一部分。然后判斷任意一個與該頂點P1相鄰的頂點Pi是否滿足生長準則條件。若頂點Pi 滿足生長準則條件， 則將以Pi為頂點的生長區(qū)域擴展為區(qū)域生長的一部分， 如圖1（b）所示。

初始種子的選擇決定區(qū)域生長的形狀，本文采用的方法是：重復(fù)選取沒有被分割區(qū)域具有頂點的局部特征度極大值的頂點作為初始種子。這樣可將所有棱邊、凹痕、尖端、褶皺等區(qū)域都按照頂點的局部特征度大小先后進入擴展區(qū)域，以減少這些區(qū)域出現(xiàn)在分割邊緣。

生長準則的選擇會影響區(qū)域生長趨勢，為了對網(wǎng)格模型的三角形疏密程度進行區(qū)域劃分，本文采用頂點局部特征度作為區(qū)域生長的判定條件，對于滿足判定條件的進行區(qū)域生長，不滿足則終止生長。若頂點P1和頂點 Pi的局部特征度滿足生長某個閾值， 便可將Pi 的相鄰三角形擴展到區(qū)域中。生長準則規(guī)定為：

其中， Ri、 R1分別表示頂點Ri和R1的局部特征度， RVthod是生長閾值， 它的大小選擇根據(jù)實際情況而定。對于平滑區(qū)域，RVthod可選擇較小值；對于局部特征度較大的區(qū)域，RVthod可適度增大。

3 區(qū)域平滑處理

經(jīng)過預(yù)分割后的區(qū)域存在不連通及區(qū)域邊緣不平滑，會給后續(xù)簡化帶來很大麻煩，所以在預(yù)分割后，需要進行平滑處理，本文采用區(qū)域填充法處理。邊緣不平滑區(qū)域包含的頂點所在三角形數(shù)目和該頂點所在三角形數(shù)目的比大于1/2，我們將該頂點所在三角形全部填充到這個邊緣不平滑區(qū)域，處理步驟如下：

首先，統(tǒng)計頂點vi所在三角形數(shù)目N，統(tǒng)計這些三角形中屬于區(qū)域As的數(shù)目Ns；然后判斷：如果頂點vi滿足NsN>1/2，就將vi所在的N個三角形全部填充到區(qū)域As中。最后判斷區(qū)域As是否連通，如果不連通就重新執(zhí)行該操作；如果連通，則操作結(jié)束。

4 基于頂點的局部特征度網(wǎng)格分割算法過程

（1）將所有頂點加入頂點數(shù)組Q，并計算網(wǎng)格模型每個頂點的局部特征度值。

（2）遍歷數(shù)組Q， 選擇具有局部特征度極大值的頂點作為初始種子，即若頂點v滿足：對vn∈Nv有∑vi∈S且v≠viUv>∑vi∈SUvn，則v為區(qū)域生長初始種子，將頂點v保存起來以備后續(xù)傳輸使用。從數(shù)組Q中刪除頂點v，將區(qū)域a加入到區(qū)域數(shù)組A。

（3）選擇合適的頂點局部特征度閾值。（4）從初始種子開始，向滿足生長準側(cè)的區(qū)域進行擴張，每擴展一個頂點，從數(shù)組Q中刪除該頂點。如果數(shù)組Q中還有頂點未被擴展， 則轉(zhuǎn)步驟（2），否則繼續(xù)。（5）如果數(shù)組A為空，算法結(jié)束。否則遍歷區(qū)域數(shù)組A找到不連通區(qū)域As，從數(shù)組A中刪除As。

（6）統(tǒng)計頂點vi所在三角形數(shù)目N，統(tǒng)計這些三角形中屬于區(qū)域As的數(shù)目Ns。（7）如果頂點vi滿足：NsN>1/2（5）

則將頂點vi所在的所有三角形都填充到區(qū)域As之中。（8）如果區(qū)域As已經(jīng)連通， 并且邊緣已經(jīng)達到平滑程度， 則轉(zhuǎn)步驟（5），否則， 轉(zhuǎn)步驟（6）。

5 實驗結(jié)果

實驗環(huán)境：CPU Intel（R） Core（TM） 2 Duo，內(nèi)存 2G，代碼在Windows 7系統(tǒng)VS2013和OpenGL下編寫完成。本算法部分實驗結(jié)果如圖2、圖3所示。

從實驗結(jié)果可以看出，模型的分割區(qū)域比較好地保留了局部細節(jié)特征，而且分割區(qū)域中不存在不連通區(qū)域，區(qū)域邊緣基本平滑，證明了本文算法的有效性。

6 結(jié)語

本文提出了一種基于頂點的局部特征度區(qū)域生長算法，算法通過對頂點的局部特征度閾值設(shè)定，作為區(qū)域生長準則的判定條件，決定區(qū)域生長中所需要的區(qū)域形狀，對網(wǎng)格模型進行分割，并對預(yù)分割后產(chǎn)生的不平滑邊界采用區(qū)域填充法進行處理。最后獲得大小適中、密度差異相對明顯的連續(xù)區(qū)域。區(qū)域邊緣平滑，且所有三角形均屬于某個區(qū)域。

參考文獻：

[1] 孫曉鵬，李華.三維網(wǎng)格模型的分割及應(yīng)用技術(shù)綜述[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005，17 （8 ）：1647-1655.

[2] MANGAN A， WHITAKER R. Partitioning 3D surface watershed segmentation[J].IEEE Transactions on Vieualization and Computer Graphics，1999，5（4）：308-321.

[3] GARLAND M.WILLMOTT A， HECKBERT P. Hierarchical face clustering on polygonal surfaces[C].Proceedings of ACM Symposium on Interactive 3D Graphics，New York，2001.

[4] LLOYD S. Least square quantization in PCM[J] .IEEE Transactions on Information Theory，1982，28（2）：129-137.

[5] 全紅艷，張?zhí)镂?，董宇?一種基于區(qū)域分割的幾何模型簡化方法[J].計算機學(xué)報，2006，29（10）： 1834-1842.

（責(zé)任編輯：杜能鋼）