姚建強， 何援軍

（上海交通大學計算機系，上海 200240）

3D幾何模型的發展，使網絡曲面的參數化成為近年來圖形學的研究熱點之一。由于三角網絡曲面具有簡單，靈活以及受各種圖形硬件的廣泛支持的特點[1]，三角網格曲面的參數化在娛樂業、制造業、醫學和科學可視化等領域中得到廣泛的應用。

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

1 前人工作

三角網格曲面的參數化主要分為曲面網格參數化和網格內部點映射。

1.1 三角網絡參數化

根據參數域的不同，三角網格參數化方法主要可以分為平面參數化和球面參數化。

平面參數化是目前研究得最多的參數化算法，它把一個空間三角網格盡可能均勻地攤平到某個平面區域中。Tutte[2]在1960提出了凸組合方法， Floater[3-4]在Tutte的基礎上通過給每條邊附加一個與邊長相關的權值改進了凸組合方法。它們的基本思想是固定邊界點，內部點由它的相鄰點的加權凸組合給出。并提出了保角參數化和均值參數化方法。

通常幾何模型都是由虧格為零的封閉網格組成，如變形的球體。對于這樣的模型，將它參數化到它拓撲同構的球面更為合理[5]。近些年，人們逐漸把球面參數化作為研究的重點。

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

1.2 內部點映射

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

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

2 三角網絡的球面參數化

凸組合參數化適用于帶邊界的三角網絡。對于封閉的網絡首先需要做切割處理。然后將網絡邊界映射到參數區域的凸邊界上。

2.1 網格分割

尋找切割線，將三角網絡切割成帶邊界的三角形網格，然后把網格的邊界按邊長比例逆時針映射到球面的凸區域邊界上.凸組合參數化方法必須把網格的邊界映射到球面的凸區域邊界，否則結果可能無效。網絡邊界被映射到參數區域的凸邊界上后，三角網格內部點在球面的對應點將由球面區域邊界唯一表示。

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

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

設得到的最短路徑為ABCDEF。其中，AB為路徑端點，BCDE為最短路徑的中間點，如圖1所示

圖1 最短路徑

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

2.2 網格參數化

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

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

選擇映射?，將bi到Sb。Sb為球面區域S邊界，bi屬于VB。三角網絡的邊界被映射到球面區域的邊界上。

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

由于方程左邊全是網絡中的內部頂點，右邊點是網格中的外部頂點。所以方程可以寫為

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

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

圖2 夾角與邊權

滿足條件(1)的方程組中的矩陣A是非奇異的并且是稀疏的，構造了正值集合ijλ，通過解方程(1)，可以得到了網格內部頂點的邊界表示。可見，內部點的初始映射位置并不重要，因為它由邊界點惟一確定。

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

2.3 網格內部點的映射

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

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

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

三角形內部點被映射后，三角網格曲面被完全映射到了球面上。

3 結果及討論

本文將凸組合方法應用到球面參數化中，結合 slerp算法，提出了一種參數化三角網格球面的方法。在AMD雙核2.21G，內存1G的PC機上，VC6.0的編譯環境下實現了該方法。圖3給出了一些動物模型參數化的結果。可以看出，在這4個模型中，三角網格曲面被較均勻的參數化。該算法在這些模型上應用得很好。可以直接將其應用到紋理映射、重新網格化、曲面擬合、morphing等技術中。

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

圖3 凸組合參數化

[1]何援軍. 計算機圖形學[M]. 北京: 機械工業出版社,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.