湯慧儀+張俊達

摘要：作為一種基于紋理的矢量場可視化方法，線積分卷積算法能夠以紋理圖像的形式展示矢量場全貌，并能夠較好地展現(xiàn)細節(jié)變化，因而是一類行之有效的方法，但計算量巨大，繪制效率較低。針對此問題，提出一種基于CUDA的線積分卷積矢量場并行可視化方法，利用并行計算架構(gòu)的優(yōu)勢以及圖形處理器的快速計算能力，較好地提高矢量場的可視化效率。首先對線積分卷積算法并行化的可行性進行分析，然后針對其中的流線生成和紋理生成兩個關(guān)鍵階段進行并行化改造，將計算密集型的部分轉(zhuǎn)移到圖形處理器中進行快速計算，從而較大幅度提高了繪制效率，最后通過實驗驗證了方法的有效性。

關(guān)鍵詞： 線積分卷積；CUDA；矢量場；可視化

中圖分類號：TP391 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）12-0270-03

Abstract：As a texture based vector field visualization algorithm，LIC algorithm can display the complete picture of vector field in the form of image， and show the details of the changes. Aiming at the problem of low efficiency of LIC algorithm for rendering，a parallel liner integral convolution algorithm for vector field visualization based on CUDA is proposed. The streamline generation and texture value calculation in the traditional LIC algorithm are parallel reconstructed. Using GPU to calculate the streamline of all pixels by numerical integration method，and parallel simultaneously computing all pixel values corresponding to the output image texture. The rendering efficiency is significantly improved. In the end， the experiment validates the effectiveness of proposed algorithm.

Key words：LIC； CUDA； Vector field； Visualization

1 概述

空間數(shù)據(jù)場是一類重要的科學(xué)計算數(shù)據(jù)，廣泛應(yīng)用于海洋、氣象、電磁、醫(yī)學(xué)等領(lǐng)域。矢量場是空間數(shù)據(jù)場的重要組成部分，可同時表征數(shù)據(jù)大?。ㄈ鐖鰪姡┡c方向，如海面風(fēng)場、渦旋、流場等。深刻認(rèn)知并理解矢量場特征，發(fā)現(xiàn)其內(nèi)在規(guī)律，對海洋活動、天氣預(yù)報、軍事指揮等均具有重要意義。

矢量場可視化一直是圖形學(xué)與可視化領(lǐng)域的研究熱點，借助計算機圖形學(xué)的基本理論，可形象直觀地展示研究對象，并在此基礎(chǔ)上進行知識挖掘與知識發(fā)現(xiàn)。經(jīng)典的矢量場可視化方法，如點標(biāo)法、流線法等具有方法簡單、易于實現(xiàn)等優(yōu)點，一直廣泛應(yīng)用。但是由于可視化結(jié)果離散且不連續(xù)，容易造成視覺混疊、圖像雜亂無章、以及關(guān)鍵特征遺漏等問題，因此多用于小范圍矢量場局部特征的可視化。基于紋理的矢量場可視化方法，以圖像形式展示矢量場的全貌，可以表現(xiàn)細節(jié)變化，且較好地展示了矢量場的方向信息，因此是近來的研究熱點。線積分卷積算法[1]（Line Integral Convolution，LIC）是一種典型的基于紋理的矢量場可視化方法。通過將某一時刻矢量場的前后若干幅圖像進行疊加，使得合成圖像中像素的灰度，與當(dāng)前時刻以及前后一段時間在矢量場中所流經(jīng)像素點（即流線）的矢量相關(guān)聯(lián)。該算法利用同一流線上相近像素點的相關(guān)性生成紋理，然后展現(xiàn)矢量場的方向變化趨勢。算法具有表現(xiàn)豐富、信息準(zhǔn)確、前后關(guān)聯(lián)性強等優(yōu)點，但計算量巨大，較大程度制約了其廣泛應(yīng)用。

為了解決計算量大的問題，Stalling和Hege在LIC算法的基礎(chǔ)上提出了Fast LIC算法[1]，將原始算法的效率提升了近一個數(shù)量級；隨后Zockler等人提出了并行LIC[2]，該算法通過挖掘多幀圖像中圖像空間上的并行性來生成動畫序列，使交互式矢量場可視化成為可能。然而，該算法是在大規(guī)模并行計算機上實現(xiàn)的，對硬件的要求過高；Hlawatsch等人提出了分級線積分策略[3]，利用多核架構(gòu)對算法中的積分計算過程進行加速，使得算法的計算時間從原先的線性增長關(guān)系下降到對數(shù)增長關(guān)系。盡管如此，當(dāng)輸入矢量場的分辨率增加時，該算法的計算耗時依然較快增長。國內(nèi)外相關(guān)研究人員在提高算法效率方面已經(jīng)做了大量的理論和方法研究，目前已經(jīng)形成了一些具有代表性的研究成果[4-6]。

隨著計算機技術(shù)的發(fā)展，低成本、高性能計算日益成熟。通用并行計算架構(gòu)（Compute Unified Device Architecture，CUDA）由Nvdia公司提出，較好地利用了圖形處理器（Graphics Processing Unit，GPU）的浮點運算能力，因而能夠較大程度提高計算效率。本文結(jié)合CUDA架構(gòu)，針對LIC算法計算量大的問題，探討LIC算法的并行化改造方法，以期利用GPU的硬件加速來提高矢量場的可視化效率。首先對LIC算法并行化的可行性進行分析，然后針對流線生成和紋理生成兩個關(guān)鍵階段進行并行化改造，將計算密集型的部分轉(zhuǎn)移到GPU中進行快速并行計算，最后通過實驗驗證了方法的有效性。

2 LIC算法的基本思路

LIC算法的基本思路如圖1所示，首先生成一個與矢量場分辨率相同的白噪聲作為輸入紋理，然后將輸入噪聲紋理沿矢量場的中的流線進行線積分卷積低通濾波處理，從而得到能夠展現(xiàn)矢量場方向信息的輸出紋理。

算法的核心步驟為流線生成和紋理生成兩個過程，流線生成過程一般采用線積分卷積法，通過流線終止條件（到達臨界點、邊界點或流線長度上限）的限制，依據(jù)矢量數(shù)據(jù)逐點計算出整條流線對應(yīng)的所有像素點；紋理生成以相應(yīng)流線對應(yīng)像素點的噪聲紋理值作為輸入，按卷積核函數(shù)進行加權(quán)求和，遍歷全部矢量數(shù)據(jù)后得到輸出圖像每一點的輸出紋理值，進而形成能夠展現(xiàn)矢量場方向變化的紋理圖。顯然，影響LIC算法時間復(fù)雜度的因素主要在流線生成和紋理生成兩個階段，計算過程較為繁瑣，耗時較長，如果能夠?qū)⑵洳⑿谢?，則能有效提高算法效率。

3 基于CUDA的LIC并行計算

2007年6月，Nvdia推出了CUDA架構(gòu)，利用GPU進行數(shù)據(jù)的并行計算，其不需要借助圖形學(xué)API，采用類C語言進行開發(fā)，降低了開發(fā)難度[7]，利用CUDA的關(guān)鍵，是找到算法中適合GPU計算的部分。現(xiàn)針對圖1的LIC算法思路，即流線生成和紋理生成兩個過程，基于CUDA進行并行計算，將計算密集型的部分交由GPU進行處理，以提高算法的運算效率。

3.1 流線生成的并行計算

圖2給出了流線生成過程的并行化處理流程，其中左半部分由CPU端執(zhí)行，右半部分由GPU端執(zhí)行。

其中，CPU端的計算任務(wù)主要包括：

1）依據(jù)輸出紋理圖像分辨率，在外部存儲器中分配存儲空間，供流線像素表使用；

2）讀取矢量場數(shù)據(jù)，并載入GPU共享內(nèi)存，使得在流線生成時可以快速獲??；

3）當(dāng)矢量場數(shù)據(jù)量較為龐大時，有時難以一次性載入到顯存，所以在CPU端需要對其進行基于空間位置的分塊，將每一塊數(shù)據(jù)分別載入顯存中進行運算。塊的大小將由顯存的大小決定。

4）對GPU返回的流線表正確性進行判斷，并存儲于外部存儲器。

可以看出，在CPU端進行的大部分都屬于邏輯判斷任務(wù)，并且具有分支。這使得CPU的邏輯運算以及分支預(yù)測能力能夠得到最大限度的運用。與CPU端對應(yīng)，CPU端的計算任務(wù)主要包括：：

1）讀入矢量場數(shù)據(jù)，分塊裝載入顯存，從每一個像素點出發(fā)，采用數(shù)值積分的方式（歐拉法、龍格庫塔法等）并行計算出所有像素對應(yīng)的流線，流線的生成過程要滿足流線終止條件；

2）將所有流線所覆蓋的點按像素存儲為流線對應(yīng)像素表，傳回CPU端。

3.2 紋理生成的并行計算

圖3給出了紋理生成過程的并行化處理流程。

其中，CPU端的計算任務(wù)主要包括：

1）讀取流線像素表，載入共享內(nèi)存，使得在紋理值計算時能夠快速讀取輸入噪聲的紋理值；

2）讀入輸入噪聲圖像并轉(zhuǎn)化為與矢量場相對應(yīng)的數(shù)組，載入顯存；

3）當(dāng)矢量場數(shù)據(jù)量較大時，流線像素表可能無法一次性載入共享內(nèi)存，因此在CPU端同樣需要對數(shù)據(jù)進行分塊。

CPU端的計算任務(wù)主要包括：

1）依據(jù)輸入紋理（白噪聲）數(shù)據(jù)和流線像素表，分別讀取相應(yīng)流線各像素點所對應(yīng)輸入紋理的紋理值，而后并行地依據(jù)卷積核函數(shù)進行加權(quán)求和運算，得到各像素所對應(yīng)的輸出紋理值。

2）將所有輸出紋理像素值合成顯示圖像，經(jīng)過渲染，得到最終輸出紋理圖像。

4 實驗結(jié)果及分析

采用數(shù)值方法得到的模擬渦旋場作為實驗數(shù)據(jù)，其尺寸為[256×256]，與傳統(tǒng)LIC算法進行對比實驗。同時，為了驗證本算法對繪制效率的影響，我們采用雙線性插值和等間距采樣的方式，對實驗數(shù)據(jù)進行處理，構(gòu)造出一組尺寸不同的數(shù)據(jù)，如表1所示。通過對算法運算耗時的統(tǒng)計，綜合驗證本文方法的加速效果。

實驗環(huán)境的硬件配置CPU為Intel Core2 quad 2.33Ghz，內(nèi)存為3G，顯卡為NVIDIA GeForce GTS 250，顯存為1G。

由圖4可以看出，兩種算法的繪制效果并沒有明顯的區(qū)別，這主要是因為將算法并行化后并沒有改變算法的邏輯順序和具體方法，只是將其中計算密集型的程序部分交由GPU進行并行的計算，因此從繪制效果的方面來說，兩種算法的效果是一致的。

（2）繪制效率對比

繪制效率通過算法運算耗時長短來比較，將五組實驗數(shù)據(jù)算法運算時間分別進行統(tǒng)計，結(jié)果如下表所示：

由圖5（a）可以看出，傳統(tǒng)LIC算法的運算時間隨著數(shù)據(jù)規(guī)模的增大迅速增長，不能夠滿足實時性要求較高的應(yīng)用場合。本文算法由于運用GPU并行處理大量的數(shù)值計算，大幅提高了算法的繪制效率。當(dāng)數(shù)據(jù)尺寸較小時，運算效率提高比率在10左右，但由圖5（b）可以看出，隨著數(shù)據(jù)規(guī)模的增大，由于CPU端的數(shù)據(jù)分割處理任務(wù)愈加繁重，CPU與GPU之間數(shù)據(jù)傳輸量不斷增長，導(dǎo)致加速比不斷下降。

通過實驗，本文提出的基于CUDA的線積分卷積矢量場可視化算法不但能夠保持原有的繪制效果，還大大提高了繪制效率，能夠滿足實時性要求較高的應(yīng)用場合。

5 結(jié)論

紋理法作為矢量場可視化的一種較為卓越的表達形式受到廣泛關(guān)注，但算法運算效率問題一直限制其發(fā)展。隨著硬件技術(shù)的不斷發(fā)展，使得低成本高效運算成為了可能。本文把LIC算法與CUDA架構(gòu)相結(jié)合，將傳統(tǒng)LIC算法的流線生成和紋理值計算過程進行并行化改造，實驗結(jié)果表明，算法的運算效率得到了較大幅提升，并能夠適應(yīng)大尺寸矢量數(shù)據(jù)的運算要求。

參考文獻：

[1] Stalling D， Hege H. Fast and resolution independent line integral convolution[C]. New York： Proceedings of the ACM SigGraph95， ACM SIGGRAPH， 1995：249-256.

[2] Zockler M， Stalling D， Hege H. Parallel line integral convolution[J]. Amsterdam： Parallel Computing， 1997， 23（7）：975-989.

[3] Hlawatsch M， Sadlo F， Weishkopf D. Hierarchical line integration[J]. Los Angeles： IEEE Trasactions on Visualization and Computer Graphics， 2011， 17（8）：1148-1163.

[4] S. Bachthaler， D. Weiskopf： Animation of orthogonal texture patterns for vector field visualization[J]. Los Angeles： IEEE Transactions on Visualization and Computer Graphics， 2008， 14（4）：741-755.

[5] G. Karch， F. Sadlo， D. Weiskopf. Visualization of advection-diffusion in unsteady fluid flow[J]. New Jersey： Computer Graphics Forum 3， 2012：1105-1114.

[6] D. Weiskopf. Iterative twofold line integral convolution for texture-based vector field visualization[C]. Berlin： Mathematical Foundations of Scientific Visualization， Computer Graphics， and Massive Data Exploration， 2009：191-211.

[7] 朱琪. C到CUDA編譯架構(gòu)研究與實現(xiàn)[D]. 長沙：國防科學(xué)技術(shù)大學(xué)，2011.