三角形網(wǎng)格模型頂點(diǎn)曲率的求解算法

摘 要：推導(dǎo)了一般三角形網(wǎng)格模型頂點(diǎn)的平均曲率、高斯曲率和主曲率的計(jì)算方法，考慮到經(jīng)常遇到粗糙三角形網(wǎng)格模型，為提高其曲率計(jì)算方法的精度，結(jié)合Loop細(xì)分曲面算法，進(jìn)一步拓展了該曲率計(jì)算方法。該算法用于具有特征保持的網(wǎng)格模型簡(jiǎn)化取得了良好的效果。

關(guān)鍵詞：平均曲率； 高斯曲率； 主曲率； 網(wǎng)格簡(jiǎn)化； 虛擬現(xiàn)實(shí)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)06-0107-02

在計(jì)算機(jī)圖形學(xué)、圖像分析處理和幾何建模等研究領(lǐng)域中，如自由曲面、反求工程、圖像識(shí)別、三維醫(yī)療圖像重構(gòu)，以及人臉識(shí)別等，經(jīng)常需要計(jì)算主曲率、平均曲率和高斯曲率等值，用于折痕、棱邊、隆起、溝壑等關(guān)鍵特征的提取、噪聲的過濾和曲面的修補(bǔ)等，因此曲率計(jì)算受到了廣泛關(guān)注。對(duì)于曲面，目前已經(jīng)有多種數(shù)字計(jì)算方法，這些方法基本上是基于參數(shù)化曲面［1］，以隱函數(shù)［2，3］或者四邊形網(wǎng)格函數(shù)［4，5］計(jì)算得到，這些方法都十分復(fù)雜，運(yùn)算量很大。由于三角形網(wǎng)格計(jì)算簡(jiǎn)單，并且可以通過硬件加速，三角形網(wǎng)格模型在計(jì)算機(jī)圖形學(xué)和幾何建模中十分常用，有必要建立一種能快速方便計(jì)算主曲率、平均曲率和高斯曲率的方法。圖1中的部分關(guān)鍵特

征，就是通過曲率計(jì)算識(shí)別出來的。

1 網(wǎng)格描述及算法基本思想

1.1 網(wǎng)格描述

直觀上，三角形網(wǎng)格模型是由三維空間中的三角形通過邊和頂點(diǎn)相互連接而成的分段線性曲面。其中每條邊最多包含在兩個(gè)三角形中。嚴(yán)格意義上，網(wǎng)格是一個(gè)二元組M=(K，V)。其中V={v1，v2，…，vm}，vi∈R3表示網(wǎng)格M中的頂點(diǎn)在空間中的位置，K是一個(gè)單純復(fù)形，包含頂點(diǎn)集{1，2，…，m}及其非空子集，一個(gè)單純復(fù)形包含了一組單純形，特別地，把{i}∈K，{i， j}∈K，{i， j，k}∈K分別稱作點(diǎn)、邊和面［6］。

1.2 曲線曲率的含義

要知道一條曲線在這一點(diǎn)的彎曲程度，只要知道多條曲線在這一點(diǎn)的曲率大小即可，分析如下［7］：曲線r(s)上任意一點(diǎn)，有一個(gè)單位法向量N(s)，將N(s)的起點(diǎn)平移到平面的原點(diǎn)，N(s)的終點(diǎn)就落到了單位圓周S1（圖2），這樣就定義了一個(gè)映射（Gauss映射）：

所以，當(dāng)s變化時(shí)，r(s)的速度是|(s)|=1，而N(s)在S1上轉(zhuǎn)動(dòng)的速度是|k(s)|。從圖2可以看出，在A－B區(qū)間，N(s)的轉(zhuǎn)動(dòng)速度較快，|k(s)|較大，因此比較彎曲；而在C－D區(qū)間，N(s)的轉(zhuǎn)動(dòng)速度較慢，|k(s)|較小，因此比較平坦。從上面的分析可見曲線曲率反映了曲線的彎曲程度。

2 算法的具體描述

如圖3所示，與v相連的邊為vvi(i=1，2，3，…，n)，過法矢量Nv和邊vvi構(gòu)造一個(gè)平面P，設(shè)平面P與原光滑曲面相交所得的曲線為r(s)。一般地，曲線r(s)上任意一點(diǎn)，有單位切向量T(s)和單位法向量N(s)，則曲線r(s)上任意一點(diǎn)都有沿曲線r(s)的Frenet標(biāo)架{r(s);T(s);N(s)}，則點(diǎn)v=r(sv)處的Frenet標(biāo)架為{r(sv);T(sv);N(sv)}。由于網(wǎng)格模型不是連續(xù)曲面，無法直接求得曲線r(s)在頂點(diǎn)v處的曲率，必須建立其近似求解方法。

3 應(yīng)用舉例

網(wǎng)格模型是對(duì)曲面的逼近，對(duì)于較平坦的區(qū)域，部分三角形可以刪除，以減少三角形總數(shù)；但對(duì)于棱邊、棱角和邊界等能充分反映模型特征信息和尺寸的區(qū)域，曲面起伏較大，則希望保留更多細(xì)節(jié)，也就是三角形應(yīng)該密集分布的地方。該區(qū)域的三角形應(yīng)推遲刪除或不刪除。也就是說，可以根據(jù)曲面各個(gè)區(qū)域的起伏情況來刪減三角形。

利用前面得到的曲率公式，根據(jù)曲率的大小，很容易判斷出網(wǎng)格模型的關(guān)鍵特征。現(xiàn)代三維掃描設(shè)備得到的三維模型往往由幾萬個(gè)，甚至上百萬個(gè)三角片組成，而計(jì)算機(jī)性能有限，因此龐大的數(shù)據(jù)給后續(xù)的顯示、存儲(chǔ)和處理等帶來了很大的困難，對(duì)于實(shí)時(shí)顯示要求較高的場(chǎng)合，如虛擬現(xiàn)實(shí)和增強(qiáng)現(xiàn)實(shí)，過多的面片會(huì)導(dǎo)致渲染速度過慢，嚴(yán)重影響了沉浸效果，有必要在滿足精度的情況下，盡量減少面片的數(shù)量。由于關(guān)鍵特征對(duì)于保持模型的外觀形狀，保證良好的視覺效果顯得十分重要，利用曲率能很好反映關(guān)鍵特征這一特點(diǎn)，建立基于曲率的邊折疊［6］代價(jià)函數(shù)，由代價(jià)函數(shù)來指導(dǎo)邊折疊順序，推遲與關(guān)鍵特征相關(guān)的邊的折疊，也就推遲了與關(guān)鍵特征相關(guān)的三角片的刪減，起到了既能減少三角片總數(shù)，又能保持關(guān)鍵特征的效果。基于曲率的網(wǎng)格模型簡(jiǎn)化算法與本文的主題無關(guān)，在此不作具體介紹。圖7就是基于曲率的網(wǎng)格模型的簡(jiǎn)化效果。可以看出，在對(duì)網(wǎng)格模型大幅度簡(jiǎn)化后，所有關(guān)鍵特征均較好地保持下來，如三條凹槽沒有粘連，軸孔依然是圓形，邊緣凸出。

4 結(jié)束語

本文給出了三角形網(wǎng)格模型的曲率計(jì)算公式，為了提高粗糙網(wǎng)格模型曲率的計(jì)算精度，結(jié)合網(wǎng)格模型的細(xì)分算法，進(jìn)一步給出了粗糙網(wǎng)格模型的曲率計(jì)算公式。其計(jì)算方便、運(yùn)算速度快。作為例子，簡(jiǎn)要介紹了曲率在具有特征保持特性的網(wǎng)格模型簡(jiǎn)化上的應(yīng)用。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。