基于曲率的三角網格模型分割算法

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

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

【關鍵詞】三角網格模型 曲面分割 離散曲率 區域生長

1 引言

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

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

2 三角網格模型介紹

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

點：V={i}∈k

邊：E=（i，j）∈k

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

點的鄰域如圖1所示。

對于任意的頂點V，其領域關系有：

（1）1環鄰域頂點的集合，即與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，Fj+1，...，Fj+m-1}。

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

3 三角網格分割的相關概念

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

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

（1）

（2）

4 算法基本思想

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

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

5 算法的描述

5.1 算法步驟

步驟1：置網格頂點的索引v=1；轉步驟2。

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

步驟3：頂點索引v=v+1；若v小于模型的頂點數，則轉步驟2；否則轉步驟9。

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

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

步驟6：，置j=0；轉步驟7。

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

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

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

5.2 實驗結果

在Windows平臺上，基于OpenGL和VC++實現了本文的三角網格模型分割算法，下面是本文算法的實驗結果。

（1）模型初始化結果。

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

（3）大象模型初始化結果。

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

（指導教師：李群輝）

參考文獻

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

[2]全紅艷，張田文.基于區域生長的網格模型分割技術[J].計算機輔助設計與圖形學學報，2006，18（07）：1011-1016.

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

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

作者單位

長安大學 陜西省西安市 710018