文獻(xiàn)標(biāo)識碼： A
DOI： 10.19358/j.issn.2096-5133.2020.09.004
引用格式： 吳璇，張舉勇. 基于GPU并行優(yōu)化的網(wǎng)格參數(shù)化算法[J].信息技術(shù)與網(wǎng)絡(luò)安全，2020，39(9)：16-23.
0 引言
三維模型是一種使用三維曲面來表述物體的三維數(shù)據(jù)，網(wǎng)格是三維模型中一種應(yīng)用廣泛的表達(dá)方式。隨著數(shù)字幾何處理技術(shù)的發(fā)展以及掃描技術(shù)的進(jìn)步，網(wǎng)格模型得以廣泛應(yīng)用于動(dòng)畫、游戲、建筑、醫(yī)療、工業(yè)設(shè)計(jì)等行業(yè)。網(wǎng)格曲面參數(shù)化是流形曲面和參數(shù)域之間的一一映射，是網(wǎng)格處理領(lǐng)域中不可或缺的基礎(chǔ)工具，在網(wǎng)格變形、紋理映射、網(wǎng)格壓縮中都發(fā)揮著重要作用。通常網(wǎng)格是在3D空間中的二維曲面，直接對于3D模型進(jìn)行網(wǎng)格處理非常復(fù)雜，通過一一映射到簡單的參數(shù)域，得到的參數(shù)化結(jié)果與原始網(wǎng)格有相同的拓?fù)浣Y(jié)構(gòu)以及盡可能小的失真，然后在參數(shù)域上進(jìn)行網(wǎng)格處理，極大地降低了處理難度。
一個(gè)高質(zhì)量的參數(shù)化映射f有以下性質(zhì)：無翻轉(zhuǎn)、低失真度量。無翻轉(zhuǎn)意味著detJ(f)>0，這里J(f)是f的雅各比矩陣。理想中的映射是在映射后網(wǎng)格與初始網(wǎng)格之間沒有形變，但這只是理想情況，一個(gè)高質(zhì)量的網(wǎng)格需要盡量減少形變，而失真度量就是用于衡量映射形變的數(shù)值。
經(jīng)典的參數(shù)化方法主要分為線性方法與非線性方法兩種。線性方法計(jì)算簡單，可擴(kuò)展性強(qiáng)，因?yàn)榫€性方法通過計(jì)算一個(gè)線性系統(tǒng)來得到參數(shù)化結(jié)果。雖然線性方法在計(jì)算效率上占據(jù)優(yōu)勢，但是有許多方法都必須固定邊界，無法獲得自由邊界的參數(shù)化結(jié)果，比如針對拓?fù)鋱A盤，F(xiàn)LOATER M[1-2]通過把邊界固定到一個(gè)凸多邊形上，同時(shí)所有權(quán)重都保證為正數(shù)，得到一個(gè)無翻轉(zhuǎn)的參數(shù)化結(jié)果。自由邊界的方法可以通過虛擬邊界、增添線性方程來實(shí)現(xiàn)。自由邊界方法通常可以減少固定邊界造成大的變形扭曲，卻不一定確保得到的映射是無翻轉(zhuǎn)的。非線性方法通常構(gòu)造出一個(gè)以變形能量為目標(biāo)式，包含無翻轉(zhuǎn)硬約束的全局優(yōu)化問題[3-4]，使用牛頓法、高斯牛頓法等優(yōu)化算法降低參數(shù)化網(wǎng)格的變形能量，這些能量函數(shù)描述了參數(shù)化映射后網(wǎng)格的變形、失真程度，通常是高度非線性、非凸的，所以這些方法計(jì)算效率低，而且在處理大型網(wǎng)格時(shí)，非線性方法通常會(huì)隨著所處理網(wǎng)格的增大，收斂速度極大地降低。
為了解決以往參數(shù)化方法運(yùn)算消耗大、運(yùn)算效率低、非并行、可擴(kuò)展性差的缺陷，本文提出了一種可并行、可擴(kuò)展計(jì)算無翻轉(zhuǎn)、高質(zhì)量參數(shù)化網(wǎng)格的算法。不同于以往算法構(gòu)造出一個(gè)無法并行的全局優(yōu)化問題，本文算法通過引入輔助變量，把參數(shù)化問題分解為每個(gè)面上，每條內(nèi)邊上的局部子問題。該算法的空間復(fù)雜度與網(wǎng)格模型規(guī)模成線性關(guān)系，也就是4N+2|εint|，其中N是網(wǎng)格的面數(shù)，|εint|是網(wǎng)格內(nèi)邊條數(shù)。相比于現(xiàn)存算法不可并行性，本文算法最大創(chuàng)新點(diǎn)在于每次迭代都可以并行處理N個(gè)關(guān)于三角面片上映射的子問題以及|εint|個(gè)關(guān)于內(nèi)邊相容性約束的子問題。實(shí)驗(yàn)顯示相比于現(xiàn)存算法，本文算法最終得到相同甚至更好質(zhì)量網(wǎng)格所需運(yùn)算時(shí)間縮短了至少百倍以上。隨著掃描技術(shù)的飛快發(fā)展，3D網(wǎng)格模型的規(guī)模越來越大，可擴(kuò)展的網(wǎng)格參數(shù)化算法意義重大。但計(jì)算大規(guī)模網(wǎng)格的無翻轉(zhuǎn)映射是一個(gè)具有挑戰(zhàn)性的難題，該算法可擴(kuò)展，長于處理大型網(wǎng)格模型。
本文詳細(xì)內(nèi)容請下載:http://m.jysgc.com/resource/share/2000003087
作者信息:
吳 璇，張舉勇
(中國科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥230026)