《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 其他 > 設(shè)計(jì)應(yīng)用 > 基于GPU并行優(yōu)化的網(wǎng)格參數(shù)化算法
基于GPU并行優(yōu)化的網(wǎng)格參數(shù)化算法
2020年信息技術(shù)與網(wǎng)絡(luò)安全第9期
吳 璇，張舉勇
中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥230026
摘要： 網(wǎng)格參數(shù)化是計(jì)算機(jī)圖形學(xué)、數(shù)字幾何處理領(lǐng)域的研究熱點(diǎn)，在動(dòng)畫(huà)、醫(yī)療、工業(yè)設(shè)計(jì)等領(lǐng)域中都發(fā)揮著重要作用?，F(xiàn)有參數(shù)化方法主要思路是構(gòu)造一個(gè)高度非線性的全局優(yōu)化問(wèn)題，因此計(jì)算效率低，難以并行。提出了一種可并行、可擴(kuò)展的參數(shù)化算法。該算法通過(guò)引入輔助變量。然后使用交替方向乘子算法(Alternating Direction Method of Multipliers，ADMM)，迭代優(yōu)化每個(gè)面和每條邊上的子問(wèn)題得到參數(shù)化映射。為了驗(yàn)證算法模型的高效性，使用GPU加速，相比于現(xiàn)存單線程算法，本文算法因?yàn)楦叨炔⑿谢\(yùn)行時(shí)間縮短了至少百倍以上。
中圖分類號(hào)： TP391
文獻(xiàn)標(biāo)識(shí)碼： 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.
Mesh parameterization based on GPU parallel optimization
Wu Xuan，Zhang Juyong
School of Mathematical Sciences, University of Science and Technology of China，Hefei 230026，China
Abstract： Mesh parameterization is a research hotspot in the field of computer graphics and digital geometry processing. It plays an important role in animation, medical treatment, industrial design and other fields. Existing methods formulate this problem as a global optimization problem. Due to its high nonlinearity and global optimization of the model,it is very difficult to solve efficiently and parallelize. This paper presents a parallel and scalable algorithm for mesh parameterization. The proposed method solves this problem by introducing a set of auxiliary variables.Then using ADMM(Alternating Direction Method of Multipliers), this problem can be easily solved by optimizing small problems for each face and each edge iteratively. To verify the efficiency of the proposed method, we implement the proposed algorithm via GPU,reduce the running time by at least 100 times compared with single thread implementation due to the high parallelism of the proposed algorithm.
Key words : parallel computing；ADMM；mesh parameterization；optimization algorithm

0 引言

    三維模型是一種使用三維曲面來(lái)表述物體的三維數(shù)據(jù)，網(wǎng)格是三維模型中一種應(yīng)用廣泛的表達(dá)方式。隨著數(shù)字幾何處理技術(shù)的發(fā)展以及掃描技術(shù)的進(jìn)步，網(wǎng)格模型得以廣泛應(yīng)用于動(dòng)畫(huà)、游戲、建筑、醫(yī)療、工業(yè)設(shè)計(jì)等行業(yè)。網(wǎng)格曲面參數(shù)化是流形曲面和參數(shù)域之間的一一映射，是網(wǎng)格處理領(lǐng)域中不可或缺的基礎(chǔ)工具，在網(wǎng)格變形、紋理映射、網(wǎng)格壓縮中都發(fā)揮著重要作用。通常網(wǎng)格是在3D空間中的二維曲面，直接對(duì)于3D模型進(jìn)行網(wǎng)格處理非常復(fù)雜，通過(guò)一一映射到簡(jiǎn)單的參數(shù)域，得到的參數(shù)化結(jié)果與原始網(wǎng)格有相同的拓?fù)浣Y(jié)構(gòu)以及盡可能小的失真，然后在參數(shù)域上進(jìn)行網(wǎng)格處理，極大地降低了處理難度。

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

    經(jīng)典的參數(shù)化方法主要分為線性方法與非線性方法兩種。線性方法計(jì)算簡(jiǎn)單，可擴(kuò)展性強(qiáng)，因?yàn)榫€性方法通過(guò)計(jì)算一個(gè)線性系統(tǒng)來(lái)得到參數(shù)化結(jié)果。雖然線性方法在計(jì)算效率上占據(jù)優(yōu)勢(shì)，但是有許多方法都必須固定邊界，無(wú)法獲得自由邊界的參數(shù)化結(jié)果，比如針對(duì)拓?fù)鋱A盤(pán)，F(xiàn)LOATER M[1-2]通過(guò)把邊界固定到一個(gè)凸多邊形上，同時(shí)所有權(quán)重都保證為正數(shù)，得到一個(gè)無(wú)翻轉(zhuǎn)的參數(shù)化結(jié)果。自由邊界的方法可以通過(guò)虛擬邊界、增添線性方程來(lái)實(shí)現(xiàn)。自由邊界方法通?？梢詼p少固定邊界造成大的變形扭曲，卻不一定確保得到的映射是無(wú)翻轉(zhuǎn)的。非線性方法通常構(gòu)造出一個(gè)以變形能量為目標(biāo)式，包含無(wú)翻轉(zhuǎn)硬約束的全局優(yōu)化問(wèn)題[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ì)算無(wú)翻轉(zhuǎn)、高質(zhì)量參數(shù)化網(wǎng)格的算法。不同于以往算法構(gòu)造出一個(gè)無(wú)法并行的全局優(yōu)化問(wèn)題，本文算法通過(guò)引入輔助變量，把參數(shù)化問(wèn)題分解為每個(gè)面上，每條內(nèi)邊上的局部子問(wèn)題。該算法的空間復(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)于三角面片上映射的子問(wèn)題以及|εint|個(gè)關(guān)于內(nèi)邊相容性約束的子問(wèn)題。實(shí)驗(yàn)顯示相比于現(xiàn)存算法，本文算法最終得到相同甚至更好質(zhì)量網(wǎng)格所需運(yùn)算時(shí)間縮短了至少百倍以上。隨著掃描技術(shù)的飛快發(fā)展，3D網(wǎng)格模型的規(guī)模越來(lái)越大，可擴(kuò)展的網(wǎng)格參數(shù)化算法意義重大。但計(jì)算大規(guī)模網(wǎng)格的無(wú)翻轉(zhuǎn)映射是一個(gè)具有挑戰(zhàn)性的難題，該算法可擴(kuò)展，長(zhǎng)于處理大型網(wǎng)格模型。




本文詳細(xì)內(nèi)容請(qǐng)下載:http://ihrv.cn/resource/share/2000003087




作者信息:

吳  璇，張舉勇

(中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥230026)

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。