0 引言

    三維模型是一種使用三維曲面來表述物體的三維數據，網格是三維模型中一種應用廣泛的表達方式。隨著數字幾何處理技術的發展以及掃描技術的進步，網格模型得以廣泛應用于動畫、游戲、建筑、醫療、工業設計等行業。網格曲面參數化是流形曲面和參數域之間的一一映射，是網格處理領域中不可或缺的基礎工具，在網格變形、紋理映射、網格壓縮中都發揮著重要作用。通常網格是在3D空間中的二維曲面，直接對于3D模型進行網格處理非常復雜，通過一一映射到簡單的參數域，得到的參數化結果與原始網格有相同的拓撲結構以及盡可能小的失真，然后在參數域上進行網格處理，極大地降低了處理難度。

    一個高質量的參數化映射f有以下性質：無翻轉、低失真度量。無翻轉意味著detJ(f)>0，這里J(f)是f的雅各比矩陣。理想中的映射是在映射后網格與初始網格之間沒有形變，但這只是理想情況，一個高質量的網格需要盡量減少形變，而失真度量就是用于衡量映射形變的數值。

    經典的參數化方法主要分為線性方法與非線性方法兩種。線性方法計算簡單，可擴展性強，因為線性方法通過計算一個線性系統來得到參數化結果。雖然線性方法在計算效率上占據優勢，但是有許多方法都必須固定邊界，無法獲得自由邊界的參數化結果，比如針對拓撲圓盤，FLOATER M^[1-2]通過把邊界固定到一個凸多邊形上，同時所有權重都保證為正數，得到一個無翻轉的參數化結果。自由邊界的方法可以通過虛擬邊界、增添線性方程來實現。自由邊界方法通常可以減少固定邊界造成大的變形扭曲，卻不一定確保得到的映射是無翻轉的。非線性方法通常構造出一個以變形能量為目標式，包含無翻轉硬約束的全局優化問題^[3-4]，使用牛頓法、高斯牛頓法等優化算法降低參數化網格的變形能量，這些能量函數描述了參數化映射后網格的變形、失真程度，通常是高度非線性、非凸的，所以這些方法計算效率低，而且在處理大型網格時，非線性方法通常會隨著所處理網格的增大，收斂速度極大地降低。

    為了解決以往參數化方法運算消耗大、運算效率低、非并行、可擴展性差的缺陷，本文提出了一種可并行、可擴展計算無翻轉、高質量參數化網格的算法。不同于以往算法構造出一個無法并行的全局優化問題，本文算法通過引入輔助變量，把參數化問題分解為每個面上，每條內邊上的局部子問題。該算法的空間復雜度與網格模型規模成線性關系，也就是4N+2|ε_int|，其中N是網格的面數，|ε_int|是網格內邊條數。相比于現存算法不可并行性，本文算法最大創新點在于每次迭代都可以并行處理N個關于三角面片上映射的子問題以及|ε_int|個關于內邊相容性約束的子問題。實驗顯示相比于現存算法，本文算法最終得到相同甚至更好質量網格所需運算時間縮短了至少百倍以上。隨著掃描技術的飛快發展，3D網格模型的規模越來越大，可擴展的網格參數化算法意義重大。但計算大規模網格的無翻轉映射是一個具有挑戰性的難題，該算法可擴展，長于處理大型網格模型。

本文詳細內容請下載:http://www.shi-ke.cn/resource/share/2000003087

作者信息:

吳  璇，張舉勇

(中國科學技術大學 數學科學學院，安徽 合肥230026)