一種面向不等尺寸分塊海量數(shù)據(jù)集的并行體繪制算法

朱小燁 薛 健 呂 科

(中國科學(xué)院大學(xué)工程科學(xué)學(xué)院 北京 100049)

0 引 言

在科學(xué)計算可視化領(lǐng)域，體繪制技術(shù)是使用計算機圖形和圖像處理策略將獲取的三維體數(shù)據(jù)轉(zhuǎn)換為在屏幕上顯示和交互處理的圖形和圖像的一種可視化技術(shù)。體繪制被廣泛用于醫(yī)學(xué)和工業(yè)成像領(lǐng)域，因為它提供了高質(zhì)量的渲染圖像和方便的并行處理模式。研究人員將光線提前終止、空體素跳過等方法應(yīng)用于基于GPU(圖形處理器)的體繪制中，進一步提高了繪制速度。

迅速發(fā)展的成像技術(shù)和應(yīng)用帶來了爆炸性的數(shù)據(jù)量增長，然而傳統(tǒng)的方法受到內(nèi)存和外存訪問速度和數(shù)據(jù)存取的限制，導(dǎo)致渲染速度相當慢。海量數(shù)據(jù)是指數(shù)據(jù)量大到無法完全加載到計算機內(nèi)存中使用的數(shù)據(jù)，這種應(yīng)對海量數(shù)據(jù)的研究方向也反過來促進了三維體數(shù)據(jù)可視化技術(shù)的新發(fā)展。在過去的二十年中，不斷有人提出算法來克服這個問題?；诜謮K的體繪制方法是將原始體數(shù)據(jù)劃分成便于裝入內(nèi)存的子數(shù)據(jù)塊并依次繪制，最后將分塊繪制結(jié)果合成最終結(jié)果。該方法也可以與硬件加速技術(shù)一起使用，以實現(xiàn)更快的渲染速度。

本文提出并實現(xiàn)了一種基于非均勻尺寸分塊策略的體繪制方法，通過分塊間的遮擋關(guān)系構(gòu)建全局遮擋關(guān)系圖，對分塊進行分組并行渲染。與現(xiàn)有方法的對比實驗表明，本文提出的針對Out-of-core數(shù)據(jù)的體繪制方法在海量數(shù)據(jù)集上達到了比現(xiàn)有方法更快的渲染速度。

1 相關(guān)工作

三維可視化的研究始于20世紀70年代中期，并且隨著計算機斷層掃描(CT)技術(shù)的誕生逐漸發(fā)展起來。20世紀80年代，各種影像技術(shù)不斷出現(xiàn)，如磁共振成像、超聲等，極大地促進了三維體可視化技術(shù)的發(fā)展。Levoy等[1]首次提出了光線投射算法，不久之后又相繼出現(xiàn)了許多經(jīng)典的體繪制算法，如Splatting、ShearWarp、CellProjection以及基于3D紋理的方法[2-5]。

然而，隨著近幾年圖像采集硬件的不斷更新，采集圖像的分辨率也越來越高，體數(shù)據(jù)的規(guī)模也變得越來越大，促使體繪制技術(shù)的方向朝著Out-of-core技術(shù)方向發(fā)展。針對海量數(shù)據(jù)的體繪制技術(shù)應(yīng)用十分廣泛，其中一個重要的應(yīng)用領(lǐng)域是工業(yè)超聲無損檢測領(lǐng)域。超聲無損檢測的原理是通過超聲探頭發(fā)射超聲波針對樣品進行掃描，并利用超聲波與樣品的回波進行成像，其優(yōu)勢是能夠穿透檢測物體內(nèi)部，并且可以檢測內(nèi)部缺陷、觀察內(nèi)部結(jié)構(gòu)等。由高頻超聲探頭掃描得到的超聲圖像具有高分辨率的特點(一百兆的超聲探頭的掃描精度最高可達到一百微米)，當掃描的目標器件尺寸達到一定規(guī)模時，就會形成海量的超聲體數(shù)據(jù)，利用傳統(tǒng)的體繪制方法很難在有限內(nèi)存的機器上得到渲染結(jié)果。

目前針對海量數(shù)據(jù)體繪制的研究存在兩個主要的研究方向。一方面，通過經(jīng)典GPGPU語言，基于CPU-GPU組合的異構(gòu)并行計算平臺在PC系統(tǒng)中變得可行，文獻[6-7]描述了使用GPU加速渲染的經(jīng)典方法；另一方面，傳統(tǒng)的體繪制方法對海量數(shù)據(jù)的效果不佳，是因為它們的設(shè)計初衷并沒有考慮到數(shù)據(jù)量超過內(nèi)部存儲器大小的情景?；诖?，文獻[8]提出了一種基于GPU的用于并行架構(gòu)的體繪制算法，可以直接渲染不規(guī)則的海量體數(shù)據(jù)。文獻[9]提出了一種從三角網(wǎng)格構(gòu)造稀疏體素八叉樹的算法，只使用核心算法所需的一小部分內(nèi)存，但運行時間與上述針對海量數(shù)據(jù)的體繪制方法大致相同。文獻[10]采用了新穎的SparseLeap方法使得光線投射階段跳過了大量的空體素區(qū)域，可用于海量數(shù)據(jù)中含有大量背景區(qū)域的體繪制。文獻[12]的方法將整個切片序列分為一個個由相鄰兩張切片組成的Slab，按光線投射方向依次導(dǎo)入所有Slab，在當前Slab中推進在該Slab范圍內(nèi)的光線，最終得到光線投射的繪制結(jié)果?；诜謮K策略的體繪制方法也有了長足的進步，例如：文獻[13]提出的自適應(yīng)分塊方法使得每個分塊數(shù)據(jù)能夠單獨裝入紋理內(nèi)存，并按照從后往前的順序繪制，這種方法能夠最大限度地將背景與非背景部分分離。文獻[14]使用等尺寸分塊策略在單機平臺上實現(xiàn)了體繪制的硬件加速算法。文獻[15]使用統(tǒng)一的海量數(shù)據(jù)可視化框架來處理Out-of-core數(shù)據(jù)集，并提出了一種基于半自適應(yīng)分塊策略的快速體繪制方法。

基于以上研究，在等尺寸分塊策略下，文獻[16]根據(jù)分塊之間的并行關(guān)系對分塊進行并行分組，并通過并行繪制分組實現(xiàn)了良好的體繪制加速效果。將文獻[16]的算法與上述算法進行比較，可以得出這樣的結(jié)論：以分塊方式處理海量數(shù)據(jù)仍有改進的空間。例如，文獻[16]使用的等尺寸分塊策略無法有效地區(qū)分背景區(qū)域。自然地，可以考慮對不等尺寸分塊的大規(guī)模數(shù)據(jù)集使用Out-of-core技術(shù)實現(xiàn)快速的體繪制。我們期望這種方法可用于處理任意尺寸分塊的數(shù)據(jù)集。分塊良好的數(shù)據(jù)集能夠有效地區(qū)分背景區(qū)域且不會產(chǎn)生過多的由于尺寸太小而影響內(nèi)存和外部數(shù)據(jù)的交換效率的“碎片”分塊，例如經(jīng)過文獻[15]的半自適應(yīng)分塊方法得到的體數(shù)據(jù)。本文工作就是針對這種非等尺寸大小的分塊數(shù)據(jù)集，實現(xiàn)類似于Yao的并行加速體繪制方法，并將其應(yīng)用于超聲無損檢測設(shè)備掃描得到的海量超聲數(shù)據(jù)的體繪制當中。

2 基于不等尺寸分塊的并行體繪制算法

首先，原始的海量體數(shù)據(jù)在外存中被任意劃分成不等大小的數(shù)據(jù)作為算法的輸入，我們可以將它們想象成不等尺寸的體數(shù)據(jù)分塊，它們在所占的存儲空間中各自具有相對的空間位置坐標。

算法的整個流程如圖1所示，一次完整的渲染流程(初次渲染)大致可分為以下幾步：1) 設(shè)計數(shù)據(jù)結(jié)構(gòu)來存儲每一個子塊信息，根據(jù)它們之間的空間坐標信息建立不等尺寸分塊之間的相鄰關(guān)系，并將相鄰關(guān)系存儲在分塊數(shù)據(jù)結(jié)構(gòu)中；2) 根據(jù)三維標量場數(shù)據(jù)體繪制的傳遞函數(shù)以及當前視點位置和不等尺寸分塊之間的相鄰關(guān)系，遍歷不等尺寸分塊中的非空分塊，建立三維標量場數(shù)據(jù)中非空分塊的全局遮擋關(guān)系圖；3) 對繪制的全局遮擋關(guān)系圖進行拓撲排序，得到三維標量場數(shù)據(jù)中非空分塊的并行分組隊列；4) 依次對并行分組隊列中每一并行分組的非空分塊進行并行體繪制渲染，得到三維標量場數(shù)據(jù)的并行體繪制渲染結(jié)果。

圖1 算法總體流程圖

2.1 建立分塊數(shù)據(jù)結(jié)構(gòu)

為了建立分塊間的遮擋關(guān)系從而得到分組并行的繪制體數(shù)據(jù)，首先需要得到分塊間的相鄰關(guān)系并將其存儲于分塊數(shù)據(jù)結(jié)構(gòu)中。分塊的數(shù)據(jù)結(jié)構(gòu)設(shè)計如下：

typedef struct _cuboid_block_node{

unsigned long fidx;

//分塊編號

int size[3];

//分塊尺寸

float bbox[6];

//分塊包圍盒的邊界

vector adjBbox[6];

//分塊包圍盒各面上的相鄰分塊

} CuboidBlockNode;

其中，已知信息為分塊編號fidx，分塊尺寸size[3]，分塊包圍盒的邊界bbox[6]。根據(jù)已知的分塊編號及其包圍盒的邊界判斷兩兩分塊是否相鄰的準則如下：

假設(shè)當前不等尺寸分塊為B，其6個邊界值分別為B.bbox[i]，其中，i表示邊界編號，編號順序為左右下上前后。如果有不等尺寸分塊B′，其邊界值滿足：

B.bbox[2]B′.bbox[2]

B.bbox[4]B′.bbox[4]

B.bbox[1]-B′.bbox[0]<1

則不等尺寸分塊B′是不等尺寸分塊B的相鄰不等尺寸分塊，其接觸面為不等尺寸分塊B的左邊界。將不等尺寸分塊B′的編號放入不等尺寸分塊B左邊界面的相鄰塊節(jié)點編號數(shù)組B.adjBbox[0]中。判斷分塊B的包圍盒上其余5個面的準則以此類推。

根據(jù)上述準則，建立所有兩兩分塊間的相鄰關(guān)系，步驟如下：1) 對于每一不等尺寸分塊，根據(jù)建立的數(shù)據(jù)結(jié)構(gòu)，順序遍歷所有其他不等尺寸分塊，建立不等尺寸分塊之間的相鄰關(guān)系；2) 根據(jù)不等尺寸分塊之間的相鄰關(guān)系，將所有不等尺寸分塊的相鄰塊節(jié)點編號數(shù)組存入三維標量場數(shù)據(jù)中不等尺寸分塊的數(shù)據(jù)結(jié)構(gòu)。完成上述步驟后，不等尺寸分塊的數(shù)據(jù)結(jié)構(gòu)應(yīng)包括：分塊編號(外存中的數(shù)據(jù)塊序號)、分塊尺寸、分塊的包圍盒邊界和分塊包圍盒6個面上的相鄰分塊編號。

在完成建立分塊數(shù)據(jù)結(jié)構(gòu)之后，為了加速體繪制，還需要剔除不需繪制的背景區(qū)域，即經(jīng)傳遞函數(shù)映射為完全透明的數(shù)據(jù)塊。這些塊稱為空塊，不需要進入后續(xù)的繪制流程，反之則為非空塊，需要進行后續(xù)處理和繪制。若在渲染過程中由于交互操作，傳遞函數(shù)發(fā)生改變，則需要重新對所有數(shù)據(jù)塊進行空塊和非空塊的分類。

2.2 建立全局遮擋關(guān)系圖

得到分塊間的相鄰關(guān)系之后就可以根據(jù)當前視點位置建立非空分塊的全局遮擋關(guān)系圖，整個過程的流程圖如圖2所示。其大致步驟如下：首先任取一個未訪問的非空分塊B0，在全局遮擋關(guān)系圖中建立一個對應(yīng)結(jié)點，并將其加入隊列。然后從隊列頭取出非空分塊B，依次檢查非空分塊B的6個邊界面，從未訪問的邊界面開始依次檢查與非空分塊B的未訪問邊界面鄰接的所有非空分塊。若還有未訪問的非空分塊，則取出與非空分塊B的未訪問邊界面鄰接的未訪問非空分塊Bi，并將其加入隊列，并標記非空分塊Bi為“已訪問”。在全局遮擋關(guān)系圖中創(chuàng)建一個對應(yīng)非空分塊Bi的結(jié)點，并根據(jù)當前視點位置，判斷非空分塊Bi與非空分塊B之間的遮擋關(guān)系。若非空分塊B遮擋非空分塊Bi，則在全局遮擋關(guān)系圖中創(chuàng)建一條非空分塊B到非空分塊Bi的邊；若非空分塊B沒有遮擋非空分塊Bi，則在全局遮擋關(guān)系圖中創(chuàng)建一條非空分塊Bi到非空分塊B的邊。若沒有未訪問的非空分塊，則返回繼續(xù)檢查下一邊界面。最后判斷是否還有未訪問的非空分塊，若還有未訪問的非空分塊，則將其加入隊列重復(fù)以上步驟；若沒有未訪問的非空分塊，則得到最終的全局遮擋關(guān)系圖。

圖2 建立全局遮擋關(guān)系流程圖

相鄰兩個分塊的遮擋關(guān)系判斷準則如下：如圖3所示，從當前視點到當前非空分塊1的中心構(gòu)成向量I1，垂直于非空分塊1與非空分塊2的接觸面且指向非空分塊2的向量為I2。當I1·I2>0時，非空分塊1遮擋非空分塊2；否則，非空分塊1不遮擋非空分塊2。

圖3 當前視點位置下的相鄰分塊遮擋關(guān)系判斷示意圖

2.3 獲取分塊并行分組并繪制

對上述過程得到的分塊的全局遮擋關(guān)系圖進行拓撲排序所采用的方法與文獻[16]的方法類似，用以得到分塊的并行分組及其繪制順序。

得到并行分組后就可以按繪制順序依次對每個并行分組中的分塊數(shù)據(jù)進行并行體繪制渲染。假設(shè)當前要繪制的分組中有n個非空分塊，其具體過程為：1) 繪制當前并行分組中n個非空分塊的后表面，得到每一非空分塊的光線出點，將其作為三通道顏色值記錄在一二維紋理中，同時，將每一非空分塊的分塊編號作為顏色值寫入另一個二維紋理中；2) 繪制當前并行分組中n個非空分塊的前表面，在片段著色器中并行處理每一條光線，根據(jù)當前片段著色器處理的光線入點在最終投影圖像中的位置，訪問兩個二維紋理，得到當前片段著色器處理的光線出點和非空分塊的分塊編號；3) 根據(jù)非空分塊的分塊編號，在包含當前并行分組中n個非空分塊的子三維紋理中找到當前光線所在非空分塊的位置，得到當前光線對應(yīng)的分塊數(shù)據(jù)場；4) 根據(jù)當前光線對應(yīng)的分塊數(shù)據(jù)場，從當前非空分塊的光線入點和光線出點之間按照預(yù)設(shè)的步長進行采樣，并獲取每一采樣點的顏色值與不透明度值；5) 根據(jù)每一采樣點的顏色值與不透明度值，依次對并行分組隊列中每一并行分組的非空分塊進行并行體繪制渲染，得到三維標量場數(shù)據(jù)的并行體繪制渲染結(jié)果。其中，由于需要在不同批次的分塊繪制間保留每條投射光線的累積不透明度，需采用如下采樣合成公式：

Cn+1=Cn+rn×α(sn)×C(sn)

(1)

式中：αn+1和Cn+1分別表示累加合成的不透明度和顏色值；α(sn)和C(sn)分別表示光線sn處采樣所得三維紋理的不透明度和顏色值；rn=1-α(sn)表示剩余不透明度，將被記錄在渲染結(jié)果紋理中，傳遞到下一批分塊繪制流程。

3 實驗結(jié)果與應(yīng)用

為了驗證所提出的算法，設(shè)計實驗分別對不同數(shù)據(jù)量級的三個數(shù)據(jù)集進行渲染。三個數(shù)據(jù)集均為超聲無損檢測設(shè)備采集獲得的超聲數(shù)據(jù)，第1個數(shù)據(jù)集是一枚普通芯片的掃描數(shù)據(jù)(記為D1)，大小為113.7MB。第2和第3兩個數(shù)據(jù)集(分別記為D2、D3)是掃描用于探傷測試的芯片的結(jié)果，大小分別為9.55GB和25.48GB。所有測試均在配備Intel Core i5-65003.20GHz CPU，8GB物理內(nèi)存和GeForce GTX1060顯卡的普通PC機上運行。D2和D3數(shù)據(jù)集大小已超出實驗機器的內(nèi)存容量限制，在實驗環(huán)境下可認為是Out-of-core數(shù)據(jù)。圖4為本文方法分別在三個數(shù)據(jù)集上關(guān)閉光照與開啟光照的繪制結(jié)果。由圖4可知，本文提出的方法在渲染普通數(shù)據(jù)集與Out-of-core數(shù)據(jù)集時均表現(xiàn)良好。

(a) D1數(shù)據(jù)集(左：關(guān)閉光照，右：開啟光照)

(b) D2數(shù)據(jù)集(左：關(guān)閉光照，右：開啟光照)

(c) D3數(shù)據(jù)集(左：關(guān)閉光照，右：開啟光照)圖4 本文算法在D1、D2、D3數(shù)據(jù)集上的部分繪制結(jié)果

為了測試新算法的效率，分別將它與當前的幾種分塊體繪制算法作對比，包括：A1，一種類似于Novins等[12]提出的，但通過OpenMP進行并行加速的算法；A2，一種基于半自適應(yīng)分塊策略且串行渲染每個分塊的體繪制算法；A3，一種基于等尺寸分塊策略且串行渲染每個分塊的算法；A4，文獻[16]提出的基于等尺寸分塊策略且分組并行渲染分塊的算法。A5為本文所提出的方法。

表1為上述5種算法在不同數(shù)據(jù)集(D1-D3)上的渲染速度表現(xiàn)。渲染速度是指對應(yīng)算法在各自三種不同的數(shù)據(jù)集上渲染一幀所需的時間，每組數(shù)據(jù)都經(jīng)過10組以上的實驗結(jié)果取平均值得到。

表1 渲染速度的對比

續(xù)表1

表2為上述5種算法在不同數(shù)據(jù)集(D1-D3)上的內(nèi)存使用情況。緩沖數(shù)據(jù)占用內(nèi)存是指對應(yīng)算法存放臨時分塊數(shù)據(jù)所需的內(nèi)存緩沖區(qū)大?。惠o助數(shù)據(jù)占用內(nèi)存是指算法執(zhí)行時用到的輔助數(shù)據(jù)結(jié)構(gòu)占用的內(nèi)存，如A5算法所用到的分塊數(shù)據(jù)結(jié)構(gòu)與遮擋關(guān)系圖等；C是指常量，即該項數(shù)據(jù)與數(shù)據(jù)集規(guī)模大小無關(guān)。

表2 內(nèi)存消耗的對比

由表1可以看出，A5算法在渲染速度方面有良好的性能表現(xiàn)。當數(shù)據(jù)量足夠大時，與采取分塊的串行渲染方法A2和A3相比，無論劃分策略如何，A5算法的渲染速度都快50%以上。另外，A5算法也總是比采取等尺寸分塊策略的A4快，且隨著數(shù)據(jù)量的增加，A5算法的速度優(yōu)勢變得更加明顯?？傊?，無論是對于可以一次性裝入內(nèi)存的普通數(shù)據(jù)集還是Out-of-core數(shù)據(jù)集，A5算法均有最快的渲染速度。

就內(nèi)存消耗方面而言，由表2可以看出，A5算法無論是緩沖數(shù)據(jù)還是輔助數(shù)據(jù)占用內(nèi)存都略大于A1-A3算法，但是與原始數(shù)據(jù)集的大小相比兩種數(shù)據(jù)占用的空間都是微不足道的。因此，就運行時的內(nèi)存消耗而言，A5算法也是可以接受的。

本文提出的算法已經(jīng)成功應(yīng)用于海量超聲數(shù)據(jù)的處理和可視化系統(tǒng)中。圖5為用實驗室研制的超聲無損檢測設(shè)備掃描一個約5 cm×5 cm×8 mm大小的芯片得到的一組渲染圖片，渲染芯片所用的超聲數(shù)據(jù)是由超聲信號頻率為50 MHz的超聲探頭采集得到。

圖5 本文算法在超聲數(shù)據(jù)集上的部分繪制結(jié)果(右下為超聲數(shù)據(jù)采集設(shè)備)

4 結(jié) 語

本文提出了一種針對Out-of-core數(shù)據(jù)的并行體繪制算法。該算法可用于處理采用非均勻大小子塊劃分的Out-of-core數(shù)據(jù)集，在最大化背景區(qū)域的同時控制分塊的數(shù)量并減少內(nèi)部和外部數(shù)據(jù)交換開銷；在丟棄不需繪制的空子數(shù)據(jù)塊之后，根據(jù)當前視點下分塊間的遮擋關(guān)系構(gòu)造全局遮擋關(guān)系圖，進一步對有并行關(guān)系的分塊進行分組并行繪制，在GPU上并行渲染非空子塊，以此提升渲染速度。實驗表明，本文算法可以在獲得高分辨率的渲染結(jié)果的同時取得比現(xiàn)有方法更快的渲染速度。

本文算法目前在普通單機環(huán)境下運行良好，未來可以擴展到分布式環(huán)境下，在眾多計算節(jié)點上同時繪制分組并行的非空分塊，進一步提高渲染效率。