基于曲率的三角網(wǎng)格模型分割算法

鐘昌康++成宇珊++李智超++王晶

摘 要本文圍繞三角網(wǎng)格模型分割技術(shù)展開研究，主要針對具有非規(guī)則任意邊界的三維網(wǎng)格模型，以曲面曲率為特征采用區(qū)域生長算法進行三角網(wǎng)格模型的分割。提出了一種基于曲率的網(wǎng)格分割算法。本文所用的分割算法是基于面的方法，把曲率小于某一閾值的頂點視為非曲率突變點，從一組種子點開始，進行區(qū)域生長，即把非曲率突變點的鄰接三角片加入當前正在進行生長的曲面，直到周圍鄰域全是曲率突變點為止，生長結(jié)束。

【關(guān)鍵詞】三角網(wǎng)格模型 曲面分割 離散曲率 區(qū)域生長

1 引言

隨著三維掃描技術(shù)和計算機圖形學的發(fā)展以及三維模型數(shù)量的快速增加，三角網(wǎng)格模型分割技術(shù)已經(jīng)成為近年來的一個熱門研究課題，并廣泛地應用于計算機圖形學的許多領(lǐng)域，如計算機動畫、三維變形、網(wǎng)格壓縮、紋理映射等。

本文主要研究基于離散曲面曲率的三角網(wǎng)格模型的分割技術(shù)。利用離散曲面高斯曲率和平均曲率的計算公式。以頂點的曲率閾值為生長原則，利用區(qū)域生長算法實現(xiàn)了三角網(wǎng)格模型的分割。本文以曲率為分割依據(jù)，利用區(qū)域生長算法進行三角網(wǎng)格模型分割。從一組“種子點”開始，進行“區(qū)域生長”，找出具有相似特征的點，即曲率較小的點，構(gòu)成一個曲面片，直至周圍鄰域沒有特征一致的點“生長”才結(jié)束，即周圍所有的點都是曲率突變點，這些曲率突變點也即面片的邊界點。

2 三角網(wǎng)格模型介紹

三角網(wǎng)格模型是由三維空間中的三角形通過邊和頂點連接而成的分片線性的曲面，其中每條邊最多包含在兩個三角形中。定義三角網(wǎng)格M=（n，k），其中n={V1，V2，...，}，Vi∈R3，表示M中的頂點在三維空間中的位置；k是一單純復合型，包含頂點集{1，2，...，n}及其非空子集，表示頂點間的連接相互關(guān)系。三角網(wǎng)格M中的點、邊、面是k的一組單純形，可分別記作：

點：V={i}∈k

邊：E=（i，j）∈k

面：F={i，j，k}∈k

點的鄰域如圖1所示。

對于任意的頂點V，其領(lǐng)域關(guān)系有：

（1）1環(huán)鄰域頂點的集合，即與V相鄰的m個鄰點，記為NV（i）={Vj，Vj+1，...，Vj+m-1}。

（2）鄰邊集合，即有一個頂點為V的邊的集合，記為NE（i）={Ej，Ej+1，...，Ej+m-1}。

（3）鄰接三角片集合，即有一個頂點為V的三角片的集合，記為NF（i）={Fj，F(xiàn)j+1，...，F(xiàn)j+m-1}。

（4）2環(huán)鄰域頂點集合，即為其1環(huán)領(lǐng)域頂點的1環(huán)領(lǐng)域頂點，其鄰接三角片與V的鄰接三角片有公共邊，但其本身與 無公共邊。記為N2V（i）={Vk，Vk+1，...，Vk+l-1}。

3 三角網(wǎng)格分割的相關(guān)概念

三角網(wǎng)格分割（簡稱網(wǎng)格分割），是指根據(jù)一定的幾何和拓撲特征，分解成一組數(shù)目有限、各自具有簡單形狀意義的、且各自連通的子網(wǎng)格片的工作。

令S為網(wǎng)格的頂點集、邊集或者面片集。對于網(wǎng)格模型M的分割定義：將S分割為k個不相交的子集。即

（1）

（2）

4 算法基本思想

（1）通過擬合三角網(wǎng)格模型任意頂點的局部二次曲面，求出任意頂點的曲率，找出三角網(wǎng)格模型所有的曲率突變點，即曲率絕對值大于某一給定閾值的點。

（2）從三角網(wǎng)格模型的任意一個非曲率突變點（曲率小于給定閾值的點）出發(fā)進行深度優(yōu)先遍歷搜索，若搜索到的網(wǎng)格頂點是非邊界點，則將其鄰接三角片加入到當前正在進行生長的曲面片中，否則訪問下一個鄰接點，直到當前曲面片的所有邊界點都是曲率突變點為止，則當前面片的區(qū)域生長過程完成。再選取另一個未訪問過的非曲率突變點，將其作為種子點生長下一個曲面片。當所有的網(wǎng)格頂點都訪問完畢，則網(wǎng)格模型的分割也就完成。

5 算法的描述

5.1 算法步驟

步驟1：置網(wǎng)格頂點的索引v=1；轉(zhuǎn)步驟2。

步驟2：選取種子點。若索引為v的頂點P（v）未曾被訪問過，即訪問數(shù)組visited[v]==false，則將其作為新的曲面片進行區(qū)域生長的種子點，轉(zhuǎn)步驟4。否則轉(zhuǎn)步驟3。

步驟3：頂點索引v=v+1；若v小于模型的頂點數(shù)，則轉(zhuǎn)步驟2；否則轉(zhuǎn)步驟9。

步驟4：面片初始化。給新的曲面片分配必要的內(nèi)存空間，初始化某些變量。將新的曲面片結(jié)點插入模型的曲面片鏈表中。轉(zhuǎn)步驟5。

步驟5：區(qū)域生長。置索引為v的當前生長點P（v）的訪問標志為真，即 visited[v]=true；將P（v）的鄰接三角片加入到當前曲面片集合中。若P（v）為非曲率突變點，轉(zhuǎn)步驟6。

步驟6：，置j=0；轉(zhuǎn)步驟7。

步驟7：搜索當前生長頂點P（v）的1環(huán)鄰域頂點索引w=ver.vertices_1[j]；若索引為w的頂點P（w）未被訪問過，以P（w）作為新的種子點進行生長，轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟8。

步驟8：j=j+1；若j< P（v）.numvertices_1（生長頂點P（v）的一環(huán)鄰域頂點數(shù)組），轉(zhuǎn)步驟7；否則，當前曲面片生長完畢，轉(zhuǎn)步驟3。

步驟9：模型分割完畢，算法結(jié)束。

5.2 實驗結(jié)果

在Windows平臺上，基于OpenGL和VC++實現(xiàn)了本文的三角網(wǎng)格模型分割算法，下面是本文算法的實驗結(jié)果。

（1）模型初始化結(jié)果。

（2）當曲率閾值為6.25，指定三角片數(shù)目為800，平均法向量夾角為46度時經(jīng)過算法分割以后的結(jié)果如圖3所示。

（3）大象模型初始化結(jié)果。

（4）當曲率閾值為6.25，指定三角片數(shù)目為800，平均法向量夾角為46度時經(jīng)過算法分割以后的結(jié)果如圖5所示。

（指導教師：李群輝）

參考文獻

[1]楊楠，校江超，王明海.基于三角網(wǎng)格模型的法矢及曲率估算[J].現(xiàn)代制造工程，2010（03）：104-107.

[2]全紅艷，張?zhí)镂?基于區(qū)域生長的網(wǎng)格模型分割技術(shù)[J].計算機輔助設計與圖形學學報，2006，18（07）：1011-1016.

[3]汪俊，周來水，安魯陵，譚昌柏.基于網(wǎng)格模型的一種新的區(qū)域分割算法[J].中國機械工程，2005，16（09）：796-800.

[4]曹彩霞，董洪偉，丁金仲.基于區(qū)域生長的網(wǎng)格模型分割[J].計算機工程與應用，2008，44（31）.

作者單位

長安大學 陜西省西安市 710018