胡建平，謝 琪，左 平

(1.東北電力大學(xué)理學(xué)院，吉林 吉林132012;2.空軍航空大學(xué) 基礎(chǔ)部，長春130022)

曲面參數(shù)化是紋理映射、重新網(wǎng)格化、網(wǎng)格變形、網(wǎng)格壓縮、曲面擬合等許多數(shù)字幾何處理算法的基本工具［1］。在這些應(yīng)用背景下，源于表示形式的簡單、靈活以及受各種圖形硬件廣泛支持的優(yōu)點(diǎn)，曲面通常被表示為三角網(wǎng)格，它的參數(shù)化也就是通常所說的三角網(wǎng)格的參數(shù)化。三角網(wǎng)格的參數(shù)化的目標(biāo)是尋求一個(gè)三角網(wǎng)格曲面與同它拓?fù)涞葍r(jià)的簡單區(qū)域(如平面、球面等)的一一映射，通過參數(shù)化映射所得的簡單區(qū)域上的網(wǎng)格稱為參數(shù)網(wǎng)格。從數(shù)學(xué)角度來看，這樣的一一映射是很多的，尋找它并不是一件很難的事情，問題在于如何在這么多映射中找到一個(gè)相對(duì)比較“好”的映射?人們通常使用曲面的一些諸如角度、面積、長度等幾何內(nèi)在的屬性的變形程度來衡量三角網(wǎng)格參數(shù)化的好壞［2］。

由于任意復(fù)雜的模型都可以切割成很多同胚于圓盤的區(qū)域，將它們分別參數(shù)化到平面上即可完成對(duì)整個(gè)模型的參數(shù)化。因此，三角網(wǎng)格平面參數(shù)化是網(wǎng)格參數(shù)化迄今為止研究得最多的話題。曲面參數(shù)化早期被引入到計(jì)算機(jī)圖形學(xué)的應(yīng)用—紋理映射也是以平面參數(shù)化為基礎(chǔ)的。對(duì)于任何同胚于圓盤的可定向的光滑的二維流形曲面來說，黎曼映射定理保證了保角的平面參數(shù)化總是存在的。但是對(duì)于三角網(wǎng)格來說，黎曼映射定理并不一定成立。在實(shí)際計(jì)算中，通常是最小化與網(wǎng)格角度變形相關(guān)的度量來得到保角參數(shù)化?，F(xiàn)有的保角參數(shù)化方法按照最小化與網(wǎng)格角度變形相關(guān)的度量的種類可以分為固定凸邊界的方法、基于圓模式的方法以及基于角度展平的方法等［3］。由于保角參數(shù)化在能量最小化時(shí)沒有考慮到原始網(wǎng)格曲面的面積屬性，因此對(duì)于具有復(fù)雜結(jié)構(gòu)的三角網(wǎng)格通常會(huì)產(chǎn)生比較大的面積變形，一定程度上影響了其在紋理映射、重新網(wǎng)格化等數(shù)字幾何處理的應(yīng)用。

針對(duì)此類問題，本文提出了一種優(yōu)化方法，該方法通過引入保角參數(shù)網(wǎng)格頂點(diǎn)的平均值坐標(biāo)權(quán)和面積變形因子對(duì)保角參數(shù)化進(jìn)行優(yōu)化。通過典型的三角網(wǎng)格模型的實(shí)驗(yàn)比較可以看出，本文方法所得的參數(shù)化的面積變形較保角參數(shù)化有明顯改善，同時(shí)角度變形接近于保角參數(shù)化。

1 優(yōu)化方法

三角網(wǎng)格模型M可以表示為一個(gè)二元組(V，K)，其中V表示網(wǎng)格中頂點(diǎn)的集合{vi∈R3}，K是一個(gè)單純復(fù)型，包含M中所有拓?fù)溥B接關(guān)系的集合。K里面的元素有三種類型:頂點(diǎn){i}，邊{i，j}和面{i，j，k}。我們記K中邊的集合為E，面的集合為F。如果{i，j}∈E，則稱頂點(diǎn){i}和頂點(diǎn){j}是鄰居。頂點(diǎn){i}的1 環(huán)鄰居被定義為 N(i)={j|{i，j}∈ E}，它的星形鄰域被定義為 Star(i)= ∪i∈s，s∈Ks。如果頂點(diǎn){i}的星形鄰域在網(wǎng)格中對(duì)應(yīng)的區(qū)域同胚于圓盤(半圓盤)，則該點(diǎn)稱為內(nèi)部頂點(diǎn)(邊界頂點(diǎn))。

設(shè)M在平面區(qū)域的保角參數(shù)網(wǎng)格為P，可以通過固定凸邊界的方法［4］、基于圓模式的方法［5］等得到(圖1)。本文提出的優(yōu)化方法是將保角參數(shù)網(wǎng)格P的邊界頂點(diǎn)固定，然后通過求解一個(gè)線性方程組得到內(nèi)部頂點(diǎn)在平面上的對(duì)應(yīng)頂點(diǎn)ui。該線性方程組是通過保角參數(shù)網(wǎng)格頂點(diǎn)的平均值坐標(biāo)權(quán)和面積變形因子得到。它的具體形式如下:

式中uj表示頂點(diǎn)vi的一環(huán)鄰點(diǎn)vj在平面上對(duì)應(yīng)的頂點(diǎn)，wij和dj分別表示頂點(diǎn)在保角參數(shù)網(wǎng)格P中對(duì)應(yīng)頂點(diǎn)pj的平均值坐標(biāo)權(quán)和面積變形因子，|Vl|表示三角網(wǎng)格中的內(nèi)部頂點(diǎn)的數(shù)目。

圖1 通過不同的方法得到的保角參數(shù)化網(wǎng)格

平均值坐標(biāo)權(quán)是通過調(diào)和映射滿足平均值定理得出來的［4］。由于調(diào)和映射是通過最小化離散的Dirichlet能量得到的，因此平均值坐標(biāo)權(quán)可以減少參數(shù)化的角度變形。它的計(jì)算公式如下:

其中pi，pj分別表示保角參數(shù)網(wǎng)格P的一條邊的兩個(gè)頂點(diǎn)，γij，δij表示該邊與相鄰頂點(diǎn)形成的角度(圖2)。

保角參數(shù)網(wǎng)格頂點(diǎn)的面積變形因子可通過三角形的面積變形進(jìn)行計(jì)算。對(duì)于保角參數(shù)網(wǎng)格的一個(gè)三角形U，它的面積變形定義為它在原始網(wǎng)格中所對(duì)應(yīng)三角形T同它的面積之比，即:

式中A(·)表示三角形的面積。則每個(gè)頂點(diǎn)pi的面積變形di就可定義為它在原始網(wǎng)格中對(duì)應(yīng)頂點(diǎn)vi的一環(huán)相鄰三角形Tj的面積變形的加權(quán)平均，即為:

圖2 平均值坐標(biāo)權(quán)的計(jì)算

這種優(yōu)化方法的本質(zhì)是通過引入平均值坐標(biāo)權(quán)控制優(yōu)化參數(shù)化角度變形，同時(shí)對(duì)面積變形比較大的頂點(diǎn)對(duì)平均值坐標(biāo)權(quán)進(jìn)行縮放，即采用較小的權(quán)值，使得該頂點(diǎn)朝面積變形較小的區(qū)域移動(dòng)，從而減少保角參數(shù)化的面積變形。優(yōu)化時(shí)以頂點(diǎn)的面積變形的平方根進(jìn)行縮放，控制了面積變形比較大的頂點(diǎn)移動(dòng)的距離，使得優(yōu)化后的參數(shù)化的角度變形不至于發(fā)生太大的變化。

2 實(shí)驗(yàn)結(jié)果分析和討論

通過將原始網(wǎng)格的法向量映射到參數(shù)區(qū)域，或者將參數(shù)區(qū)域上棋盤等紋理映射到原始網(wǎng)格上的視覺效果是衡量參數(shù)化變形的一個(gè)直觀標(biāo)準(zhǔn);除此之外，還可以通過參數(shù)網(wǎng)格與原始網(wǎng)格之間的面積相對(duì)誤差和角度相對(duì)誤差等測度來衡量參數(shù)化的面積和角度變形程度，它們的計(jì)算公式如下:

其中|F|表示原始網(wǎng)格M的三角形數(shù)目，A(Ti)表示網(wǎng)格M的第i個(gè)三角形Ti的面積，A()表示參數(shù)網(wǎng)格中與Ti所對(duì)應(yīng)的三角形的面積，θij表示網(wǎng)格M中三角形Ti的第j個(gè)角度表示參數(shù)網(wǎng)格中θij與對(duì)應(yīng)的角度。

為了檢驗(yàn)本文優(yōu)化方法的有效性，我們選用了幾種典型的三角網(wǎng)格模型如貓、手、人頭、牛頭模型(手和牛頭模型具有細(xì)長的結(jié)構(gòu))進(jìn)行測試，通過固定矩形邊界的方法［4］和基于圓模式的方法［5］所得的保角參數(shù)化作為初始輸入進(jìn)行優(yōu)化，給出了原始網(wǎng)格的法向量映射到優(yōu)化前后的參數(shù)網(wǎng)格的效果圖，以及優(yōu)化前后參數(shù)化的角度和面積變形統(tǒng)計(jì)，如圖3、圖4、表1所示。通過這些比較可以看出，本文方法所得的參數(shù)化的角度變形接近于初始輸入的保角參數(shù)化，但是面積變形明顯減少。

圖3 參數(shù)化結(jié)果比較

表1 一些典型模型參數(shù)化變形統(tǒng)計(jì)比較

圖4 參數(shù)化結(jié)果比較

3 結(jié)論和未來工作

本文通過引入保角參數(shù)網(wǎng)格的平均值坐標(biāo)權(quán)和頂點(diǎn)的面積變形因子對(duì)保角參數(shù)化進(jìn)行優(yōu)化，明顯減少了復(fù)雜結(jié)構(gòu)物體的保角參數(shù)化的面積變形，在紋理映射、重新網(wǎng)格化、網(wǎng)格變形等數(shù)字幾何處理的應(yīng)用中具有重要的價(jià)值。在未來的研究中，我們打算將本文的參數(shù)化方法應(yīng)用在紋理映射、重新網(wǎng)格化、網(wǎng)格變形等數(shù)字幾何處理的應(yīng)用中。

［1］Sheffer，A.，Praun，E.，Rose K.Mesh Parameterization Methods and their Applications［J］.Computer Graphics and Vision，2006，2(2):105-171.

［2］彭群生，胡國飛.三角網(wǎng)格的參數(shù)化［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16(6):731-739.

［3］胡建平.數(shù)字幾何處理中球面參數(shù)化和重新網(wǎng)格化研究［D］.遼寧:大連理工大學(xué)，2009.

［4］Floater，M.S.Mean value coordinates［J］.Computer Aided Geometric Design.2003，20(1):19-27.

［5］Kharevych，L.，Springborn，B.，Schr?der，P.Discrete conformal mappings via circle patterns［J］.ACM Transactions on Graphics.2006，25(2):412-438.