姚建強(qiáng)， 何援軍

（上海交通大學(xué)計(jì)算機(jī)系，上海 200240）

3D幾何模型的發(fā)展，使網(wǎng)絡(luò)曲面的參數(shù)化成為近年來圖形學(xué)的研究熱點(diǎn)之一。由于三角網(wǎng)絡(luò)曲面具有簡單，靈活以及受各種圖形硬件的廣泛支持的特點(diǎn)[1]，三角網(wǎng)格曲面的參數(shù)化在娛樂業(yè)、制造業(yè)、醫(yī)學(xué)和科學(xué)可視化等領(lǐng)域中得到廣泛的應(yīng)用。

三角網(wǎng)格曲面參數(shù)化主要是將由三角網(wǎng)格M表示的曲面S與二維流形參數(shù)域之間尋求一個一一對應(yīng)映射? 使得? (M)與M同構(gòu)，并使曲面映射后扭曲失真最小。過去的一段時間里，許多學(xué)者一直在研究如何計(jì)算扭曲失真的程度。并提出了等積映射、調(diào)和映射、保角映射、虛擬邊界等方法來減小失真[2]。

1 前人工作

三角網(wǎng)格曲面的參數(shù)化主要分為曲面網(wǎng)格參數(shù)化和網(wǎng)格內(nèi)部點(diǎn)映射。

1.1 三角網(wǎng)絡(luò)參數(shù)化

根據(jù)參數(shù)域的不同，三角網(wǎng)格參數(shù)化方法主要可以分為平面參數(shù)化和球面參數(shù)化。

平面參數(shù)化是目前研究得最多的參數(shù)化算法，它把一個空間三角網(wǎng)格盡可能均勻地?cái)偲降侥硞€平面區(qū)域中。Tutte[2]在1960提出了凸組合方法， Floater[3-4]在Tutte的基礎(chǔ)上通過給每條邊附加一個與邊長相關(guān)的權(quán)值改進(jìn)了凸組合方法。它們的基本思想是固定邊界點(diǎn)，內(nèi)部點(diǎn)由它的相鄰點(diǎn)的加權(quán)凸組合給出。并提出了保角參數(shù)化和均值參數(shù)化方法。

通常幾何模型都是由虧格為零的封閉網(wǎng)格組成，如變形的球體。對于這樣的模型，將它參數(shù)化到它拓?fù)渫瑯?gòu)的球面更為合理[5]。近些年，人們逐漸把球面參數(shù)化作為研究的重點(diǎn)。

一個最簡單的方法就是先使用一個三角形作為邊界將三角網(wǎng)絡(luò)參數(shù)化到平面上，然后將平面域映射到球面上。這種方法在實(shí)踐中使用得很好，但在理論上沒有什么保證，并且結(jié)果會依賴于三角形邊界的選取[6]。Shapiro等[7]提出了一個基于網(wǎng)格簡化的球面參數(shù)化方法，該方法先將原始網(wǎng)格簡化為四面體，再把這個四面體映射到球面，并通過逆操作把被刪除的頂點(diǎn)添加到球面上。Alexa[8]給出了一種很簡單的球面參數(shù)化算法。首先把網(wǎng)格的所有頂點(diǎn)投影到模型的最小包圍球面上；然后保持球面上6個頂點(diǎn)的位置不動，用離散Laplacian 平均算子來松弛球面的其他頂點(diǎn)，直到球面網(wǎng)格變成星型，達(dá)到球面參數(shù)化的目的。但是，這種先簡單投影后松弛的方法，對形狀比較復(fù)雜的模型需要多次循環(huán)。因此，時間代價很高。

1.2 內(nèi)部點(diǎn)映射

為了得到曲面S的映射?，必須定義對三角網(wǎng)格內(nèi)部點(diǎn)的映射。Arvo[9]提出了一種從平面方形到球面的保積映射，Turk[10]提出了從方形到三角形的保積映射。將兩者結(jié)合起來可以得到一個從三角形到球面的保積映射 Arvo·Turk-1。Buss-Fillmore[11]重新定義了對球面點(diǎn)A1,A2,Ak的重心組合方式。該算法需要多次迭代，但收斂速度較快。Emil[5]等總結(jié)了網(wǎng)格內(nèi)部點(diǎn)映射的方法。

在本文中將凸組合方法應(yīng)用到球面參數(shù)化中，結(jié)合 slerp算法參數(shù)化三角網(wǎng)格曲面。由于需要帶邊界的三角網(wǎng)格，因此先提出了一種快速分割封閉網(wǎng)格的辦法。將得到的帶邊界的三角網(wǎng)格分別參數(shù)化，再利用 2-slerp算法映射三角網(wǎng)格內(nèi)部點(diǎn)。

2 三角網(wǎng)絡(luò)的球面參數(shù)化

凸組合參數(shù)化適用于帶邊界的三角網(wǎng)絡(luò)。對于封閉的網(wǎng)絡(luò)首先需要做切割處理。然后將網(wǎng)絡(luò)邊界映射到參數(shù)區(qū)域的凸邊界上。

2.1 網(wǎng)格分割

尋找切割線，將三角網(wǎng)絡(luò)切割成帶邊界的三角形網(wǎng)格，然后把網(wǎng)格的邊界按邊長比例逆時針映射到球面的凸區(qū)域邊界上.凸組合參數(shù)化方法必須把網(wǎng)格的邊界映射到球面的凸區(qū)域邊界，否則結(jié)果可能無效。網(wǎng)絡(luò)邊界被映射到參數(shù)區(qū)域的凸邊界上后，三角網(wǎng)格內(nèi)部點(diǎn)在球面的對應(yīng)點(diǎn)將由球面區(qū)域邊界唯一表示。

切割線的選取對參數(shù)化的結(jié)果影響很大。為了減小參數(shù)化引起的扭曲和將網(wǎng)格均勻的參數(shù)化，可以通過尋找最長的頂點(diǎn)間最短路徑。

從圖論的角度看，三角網(wǎng)格可以視為帶有權(quán)重的無向圖，它的權(quán)重由邊長來決定。因此，網(wǎng)格上任意兩點(diǎn)間的最短路徑可由Dijkstra算法或Floyd算法來獲得

設(shè)得到的最短路徑為ABCDEF。其中，AB為路徑端點(diǎn)，BCDE為最短路徑的中間點(diǎn)，如圖1所示

圖1 最短路徑

獲得初始切割線之后，需要將切割線展開成一個封閉的環(huán)，以將這個環(huán)作為參數(shù)域的邊。對于最短路徑中的每條邊可以分拆一次得到環(huán)。如可將圖1中的最短路徑展開為

2.2 網(wǎng)格參數(shù)化

凸組合方法是指點(diǎn)的位置由其周圍頂點(diǎn)位置決定。 設(shè)在三角網(wǎng)格中頂點(diǎn)vi相鄰的頂點(diǎn)集為Ni={ ni1… nik}，映射?將vk映射到參數(shù)域中為 ? ( v k )（ v k∈N i )則

Floater[3-4]證明了該方法的保凸性。

選擇映射?，將bi到Sb。Sb為球面區(qū)域S邊界，bi屬于VB。三角網(wǎng)絡(luò)的邊界被映射到球面區(qū)域的邊界上。

其次，對于所有的 vi ∈ V I，找到合適的正值 λij使得

由于方程左邊全是網(wǎng)絡(luò)中的內(nèi)部頂點(diǎn)，右邊點(diǎn)是網(wǎng)格中的外部頂點(diǎn)。所以方程可以寫為

對于ijλ的選取，floater提出利用保角映射，可以減小參數(shù)化帶來的形變。

夾角(δij,γij)與邊權(quán)(lij)的如圖2所示。

圖2 夾角與邊權(quán)

滿足條件(1)的方程組中的矩陣A是非奇異的并且是稀疏的，構(gòu)造了正值集合ijλ，通過解方程(1)，可以得到了網(wǎng)格內(nèi)部頂點(diǎn)的邊界表示?？梢姡瑑?nèi)部點(diǎn)的初始映射位置并不重要，因?yàn)樗蛇吔琰c(diǎn)惟一確定。

Floater[3-4]證明了凸組合方法解的存在性和惟一性。利用凸組合參數(shù)化，可以將由邊界分割得到的網(wǎng)絡(luò)參數(shù)化到對應(yīng)的球面區(qū)域邊界上。封閉的三角網(wǎng)絡(luò)便被全部映射到了球面上。

2.3 網(wǎng)格內(nèi)部點(diǎn)的映射

三角網(wǎng)格被參數(shù)化到球面后，為了得到三角網(wǎng)格曲面的參數(shù)化，需要映射網(wǎng)格的內(nèi)部點(diǎn)。設(shè)三角形的頂點(diǎn)為 { A,B,C}，映射到球面上的對應(yīng)點(diǎn)為A′=?(A),B′=?(B )，C′=?(C)。對三角形中的點(diǎn)P=αA+βB+γC，其中α+β+γ=1，必須定義它在球面上的映射點(diǎn)P′=?(P)。

在本文中，采用2-slerp算法[5]。在球面插值中，P ′ =s lerp(A′,B′,α)指尋找參數(shù)點(diǎn)P′使得

可以看出，slerp算法只能在一維空間中線性插值。為了將 slerp算法應(yīng)用到三角形中，可以兩次迭代slerp得到2-slerp。

三角形內(nèi)部點(diǎn)被映射后，三角網(wǎng)格曲面被完全映射到了球面上。

3 結(jié)果及討論

本文將凸組合方法應(yīng)用到球面參數(shù)化中，結(jié)合 slerp算法，提出了一種參數(shù)化三角網(wǎng)格球面的方法。在AMD雙核2.21G，內(nèi)存1G的PC機(jī)上，VC6.0的編譯環(huán)境下實(shí)現(xiàn)了該方法。圖3給出了一些動物模型參數(shù)化的結(jié)果?？梢钥闯觯谶@4個模型中，三角網(wǎng)格曲面被較均勻的參數(shù)化。該算法在這些模型上應(yīng)用得很好。可以直接將其應(yīng)用到紋理映射、重新網(wǎng)格化、曲面擬合、morphing等技術(shù)中。

但在本文中，作者沒有進(jìn)行失真度量，以及根據(jù)失真分析的結(jié)果來優(yōu)化算法。在以后的工作中，作者將失真分析考慮到模型的建立中，以得到更好的結(jié)果。

圖3 凸組合參數(shù)化

[1]何援軍. 計(jì)算機(jī)圖形學(xué)[M]. 北京: 機(jī)械工業(yè)出版社,2006. 228-234.

[2]Alla Sheffer，Emil Praun, Kenneth Rose. Mesh parameter-ization methods and their applications [C]//Foundations and Trends? in Computer Graphics and Vision, 2006: 105-171.

[3]Floater M S. Parametrization and smoth approximation of surface triangulations [J]. Computer Aided Geometric Design, 1997, 14(3): 231-250.

[4]Floater M S. Mean value cordinates [J]. Computer Aided Geometric Design, 2003, 20(1): 19-27.

[5]Praun E, Hoppe H. Spherical parametrization and remeshing [C]//Computer Graphics Proceedings,Annual Conference Series, ACM SIGGRAPH, San Diego, 2003: 340-349.

[6]Craig Gotsman, Xianfeng Gu, Alla Sheff.Fundamentals of spherical parameterization for 3D meshes [J]. ACM Transactions on Graphics(TOG), 2003, 22(3): 358-363.

[7]Shapiro A， Ayellet T. Polyhed ron realization for shape transformation [J].The Visual Computer, 1998,14(8/9): 429-444.

[8]Alexa M. Merging po lyhed ron shapes with scattered features [J]. The Visual Computer, 2000, 16(1): 26-37.

[9]James Arvo. Stratified sampling of spherical triangles [C]//ACM SIGGRAPH, 1995: 437-438.

[10]TURK G. Generating random points in triangles,Graphics gems [M]. Academic Press, 1990. 649-650.

[11]BUSS S, AND FILLMORE J. Spherical averages and applications to spherical splines and interpolation [J].ACM Transactions on Graphics, 2001, 20(2): 95-126.