基于CUDA的線積分卷積矢量場并行可視化方法

湯慧儀+張俊達

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

關鍵詞： 線積分卷積；CUDA；矢量場；可視化

中圖分類號：TP391 文獻標識碼：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 概述

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

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

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

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

2 LIC算法的基本思路

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

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

3 基于CUDA的LIC并行計算

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

3.1 流線生成的并行計算

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

其中，CPU端的計算任務主要包括：

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

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

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

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

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

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

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

3.2 紋理生成的并行計算

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

其中，CPU端的計算任務主要包括：

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

2）讀入輸入噪聲圖像并轉化為與矢量場相對應的數組，載入顯存；

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

CPU端的計算任務主要包括：

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

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

4 實驗結果及分析

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

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

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

（2）繪制效率對比

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

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

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

5 結論

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

參考文獻：

[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編譯架構研究與實現[D]. 長沙：國防科學技術大學，2011.