GPU的對(duì)半剖分體數(shù)據(jù)的光線投射法

于 水，王寬全，夏 勇，張恒貴

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱)

?

GPU的對(duì)半剖分體數(shù)據(jù)的光線投射法

于 水，王寬全，夏 勇，張恒貴

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱)

為解決傳統(tǒng)可視化方法無(wú)法有效跳過(guò)具有空腔結(jié)構(gòu)數(shù)據(jù)集的中空體素的問(wèn)題，提出一種基于GPU的面向中空結(jié)構(gòu)體數(shù)據(jù)的光線投射法.在進(jìn)行光線投射之前，首先把體數(shù)據(jù)對(duì)半剖分成兩部分，對(duì)此兩部分分別使用八叉樹(shù)進(jìn)行重構(gòu)，并同時(shí)剔除空塊，建立起各自新的有效數(shù)據(jù)塊的頂點(diǎn)集合；然后使用GPU對(duì)頂點(diǎn)集合進(jìn)行渲染，生成光線起點(diǎn)和方向等信息；最后利用CUDA對(duì)重構(gòu)后的兩部分體數(shù)據(jù)依次進(jìn)行光線投射和顏色累積，將其結(jié)果合成后得到最終圖像.實(shí)驗(yàn)結(jié)果表明，這種方法生成的圖像質(zhì)量與傳統(tǒng)的可視化方法相比沒(méi)有損失，但對(duì)具有較多空腔結(jié)構(gòu)的體數(shù)據(jù)，則可以快速跳過(guò)中空體素，具有非常明顯的加速效果.

數(shù)據(jù)可視化；光線投射法；GPU渲染；八叉樹(shù)；CUDA ；中空體數(shù)據(jù)

光線投射法是一種直接體繪制算法，最先由Levoy[1]提出，可以生成高質(zhì)量的3D圖像.早期的光線投射法大都在CPU上實(shí)現(xiàn)，因其運(yùn)算量大，導(dǎo)致繪制速度慢，難以滿(mǎn)足實(shí)時(shí)性要求.近年來(lái)隨著GPU硬件的發(fā)展，基于GPU的并行圖形可視化技術(shù)得到迅猛發(fā)展，光線投射法的計(jì)算量瓶頸問(wèn)題也得到極大的緩解.文獻(xiàn)[2]首次提出了基于GPU三線性插值能力的三維紋理體繪制方法.隨后，Cabral等[3]對(duì)此方法進(jìn)行了改進(jìn)，通過(guò)三維紋理映射實(shí)現(xiàn)了交互式體繪制，從而使基于紋理映射的方法一段時(shí)間內(nèi)成為最常用的交互式體繪制方法.然而這種方法仍然存在一些很難解決的問(wèn)題：在三維體數(shù)據(jù)中，通常只有5%～40%的數(shù)據(jù)是有意義或可見(jiàn)的，在體繪制過(guò)程中，會(huì)產(chǎn)生大量的對(duì)最終圖像沒(méi)有貢獻(xiàn)的切片，但是在計(jì)算過(guò)程中對(duì)這些切片仍然需要進(jìn)行采樣、數(shù)值計(jì)算，大大影響了繪制時(shí)間.Westermann等[4]將體數(shù)據(jù)看作三維包圍盒(bounding box)，通過(guò)光線與包圍盒的求交運(yùn)算，得到每條光線與包圍盒的交點(diǎn)，并在GPU上實(shí)現(xiàn)了并行光線投射法，大大提高了圖像質(zhì)量.Hadwiger等[5-6]進(jìn)一步通過(guò)結(jié)合GPU渲染和數(shù)據(jù)分塊算法如KD樹(shù)[7]、八叉樹(shù)[8-9]等，實(shí)現(xiàn)快速剔除有效體數(shù)據(jù)與包圍盒邊界之間的空體素，在保證圖像質(zhì)量的前提下，極大提高了繪制速度，現(xiàn)已成為在GPU上常用的光線投射方法.但這種方法對(duì)于具有較多中空結(jié)構(gòu)的體數(shù)據(jù)則依然無(wú)能為力，仍然浪費(fèi)了大量的空體素計(jì)算時(shí)間，影響可視化速度.

康健超等[10]使用基于八叉樹(shù)編碼的方法，將原始數(shù)據(jù)剔除空體素后重新寫(xiě)入三維紋理中，最后使用CUDA實(shí)現(xiàn)光線投射，提升了繪制效率，但這種方法只是簡(jiǎn)化了部分顏色累積運(yùn)算，并沒(méi)有真正跳過(guò)空體素.自適應(yīng)采樣頻率方法[11-12]可以部分解決中空結(jié)構(gòu)體數(shù)據(jù)的空體素跳過(guò)問(wèn)題，但這種方法需要對(duì)體數(shù)據(jù)進(jìn)行統(tǒng)計(jì)學(xué)預(yù)計(jì)算，如對(duì)體數(shù)據(jù)通過(guò)FFT變換進(jìn)行頻譜分析等，這個(gè)過(guò)程的計(jì)算量非常大，且由于不同的自適應(yīng)采樣規(guī)則采樣頻率不同，對(duì)圖像質(zhì)量的影響也比較明顯.葉良等[13]通過(guò)二級(jí)可變步長(zhǎng)的方法來(lái)解決對(duì)于中空結(jié)構(gòu)數(shù)據(jù)的空體素跳過(guò)問(wèn)題，但是這種方法依然不夠靈活，對(duì)于較大的中空結(jié)構(gòu)，也仍然需要多次重復(fù)跳過(guò)，增加了算法運(yùn)行時(shí)間.

目前針對(duì)具有較多中空體素的體數(shù)據(jù)的可視化問(wèn)題，鮮有文獻(xiàn)專(zhuān)門(mén)提出此類(lèi)解決方法.本文在Westermann方法和八叉樹(shù)剖分方法的基礎(chǔ)上，提出一種基于GPU的面向空腔結(jié)構(gòu)數(shù)據(jù)集的光線投射法.其主要特點(diǎn)是在使用GPU進(jìn)行渲染之前，先把體數(shù)據(jù)剖分成兩部分后利用八叉樹(shù)進(jìn)行重構(gòu)，再分別對(duì)重構(gòu)后的兩部分進(jìn)行光線投射和顏色累積，最后將結(jié)果進(jìn)行合成，得到最終圖像.實(shí)驗(yàn)結(jié)果表明本文方法對(duì)于中空結(jié)構(gòu)的體數(shù)據(jù)，具有非常明顯的加速作用.

1 基于GPU的光線投射法

1.1 光線投射法

光線投射法是指從圖像的每一個(gè)像素，沿視線方向發(fā)射一條光線，光線穿越整個(gè)圖像序列，并在這個(gè)過(guò)程中，對(duì)圖像序列進(jìn)行采樣獲取顏色信息，同時(shí)依據(jù)光線吸收模型將顏色值進(jìn)行累加，直至光線穿越整個(gè)圖像序列，最后得到的顏色值就是渲染圖像的顏色.如圖1所示，是一條典型的光線投射過(guò)程.

圖1 光線投射過(guò)程

在發(fā)射-吸收模型的光線投射法中，圖1在t=d處，由于通常體素對(duì)光線的吸收率不為常量，而是隨著位置變化而發(fā)生變化，因此在t=d處的顏色值計(jì)算公式為

式中：c′為由于存在對(duì)光線的吸收因素而最終發(fā)出的光線顏色;c為體素本來(lái)的光線顏色;k為光線吸收率，且為一個(gè)常量;d為體素與視點(diǎn)間的距離.

提取吸收率的積分公式為

上式也叫光學(xué)深度(optical depth)，基于一個(gè)點(diǎn)的計(jì)算方法，如果要計(jì)算沿光線所有點(diǎn)最終進(jìn)入人眼的顏色值，就要將所有點(diǎn)的發(fā)射和吸收情況計(jì)算在內(nèi)，結(jié)合光學(xué)深度，則其顏色積分公式可變?yōu)?/p>

(1)

由于在實(shí)際的計(jì)算機(jī)處理中，只能使用離散值來(lái)計(jì)算式(1)的積分，本文采用Riemann sum近似計(jì)算積分，因此有

(2)

由式(1)、(2)則有

(3)

定義不透明度A為

(4)

由式(3)、(4)，則有

因此得出光線投射法的離散求值為

(5)

把式(5)寫(xiě)成迭代形式：

(6)

(7)

上述便是發(fā)射-吸收模型的光線投射法的顏色合成公式，其中：C′i為累積到第i個(gè)體素時(shí)的顏色值;A′i為累積到第i個(gè)體素時(shí)的不透明度;Ci為第i個(gè)體素的發(fā)射顏色;Ai為第i個(gè)體素的不透明度.本文使用式(6)和式(7)進(jìn)行顏色合成計(jì)算.

1.2 基于GPU渲染的空體素跳過(guò)

文獻(xiàn)[4]提出的光線投射算法，是將體數(shù)據(jù)保存在3D紋理中，通過(guò)渲染方法，分別得到對(duì)于3D紋理的前向和后向紋理(亦即光線投射的起點(diǎn)和終點(diǎn))，通過(guò)前后向視圖的差值得到光線方向，如圖2所示，然后在GPU中進(jìn)行光線投射的顏色累加操作.

文獻(xiàn)[5-6]使用結(jié)合數(shù)據(jù)剖分的方法，在GPU渲染操作之前，通過(guò)層次化的數(shù)據(jù)結(jié)構(gòu)，如八叉樹(shù)等將體數(shù)據(jù)進(jìn)行剖分，根據(jù)剖分后的結(jié)果進(jìn)行空體素塊的剔除，只保留活躍體素塊.然后再利用GPU的渲染功能對(duì)所有的活躍體素塊分別進(jìn)行前向和后向渲染，生成前向和后向紋理，分別表示距視點(diǎn)最近和最遠(yuǎn)點(diǎn)的集合.這種方法可以快速有效的剔除體數(shù)據(jù)包圍盒外表面與有效體素之間的空體素，如圖3所示的體數(shù)據(jù)，渲染后光線r1-r6的有效起點(diǎn)是s1-s6，有效終點(diǎn)為e1-e6，而光線r0則未經(jīng)過(guò)任何有效體素，圖3中的灰色區(qū)域就可以快速跳過(guò)了.但這種方法對(duì)于具有較多中空結(jié)構(gòu)的體數(shù)據(jù)依然無(wú)效，如圖3中的白色封閉區(qū)域，即光線r2-r5所經(jīng)過(guò)的區(qū)域，以光線r3為例，其有效起點(diǎn)s3至終點(diǎn)e3之間，有大片的空白體素，由于GPU渲染方法的限制，還是無(wú)法進(jìn)行跳過(guò).

圖2 包圍盒渲染結(jié)果

圖3 中空數(shù)據(jù)集的光線投射過(guò)程

2 八叉樹(shù)

八叉樹(shù)可以用于層次性體繪制，也可以作為一種數(shù)據(jù)分塊方法，解決可視化時(shí)由于數(shù)據(jù)規(guī)模過(guò)大而無(wú)法全部裝載進(jìn)顯存的問(wèn)題[14].本文使用八叉樹(shù)除了完成對(duì)體數(shù)據(jù)的剖分，還要在此基礎(chǔ)上，按照每個(gè)子塊的活躍/不活躍性質(zhì)，剔除不活躍子塊，即空體素塊，重新構(gòu)建出一個(gè)新的包含有效體素塊的頂點(diǎn)數(shù)組，以用于進(jìn)行GPU渲染，最終得到前向和后向紋理.

本文所建立的八叉樹(shù)的結(jié)構(gòu)定義如圖4所示.圖4中minValue、maxValue是在八叉樹(shù)的構(gòu)建過(guò)程中，體數(shù)據(jù)包圍盒被剖分為若干個(gè)子數(shù)據(jù)塊，比較每個(gè)子塊內(nèi)所有體素的標(biāo)量值，從而得到該子塊中的所有體素標(biāo)量值的最小-最大值對(duì)，做為每個(gè)子塊的特征之一.除此之外，子塊的位置信息positionX，positionY，positionZ，結(jié)點(diǎn)深度nodeDepth也是特征之一，它們被用來(lái)在建立新的有效體素塊頂點(diǎn)數(shù)組時(shí)計(jì)算每個(gè)頂點(diǎn)坐標(biāo).

八叉樹(shù)創(chuàng)建完成之后，所有相鄰的同質(zhì)子塊會(huì)被合并為一個(gè)大的子塊，從而節(jié)省更多的內(nèi)存資源.

圖4 八叉樹(shù)的結(jié)構(gòu)定義

3 基于體數(shù)據(jù)剖分的GPU渲染

3.1 GPU渲染

在使用GPU進(jìn)行渲染之前，需要建立新的體數(shù)據(jù)頂點(diǎn)集合，遍歷八叉樹(shù)，對(duì)每個(gè)子塊(葉子節(jié)點(diǎn))進(jìn)行檢查，如果為不需要的體素值，即不活躍子塊，則將子塊從八叉樹(shù)中剔除；對(duì)于活躍子塊，則將該子塊的8個(gè)頂點(diǎn)的坐標(biāo)加入到新的頂點(diǎn)數(shù)組中，最后形成一個(gè)新的活躍子塊(包含有效體素)頂點(diǎn)數(shù)組.

本文使用OPENGL對(duì)新的頂點(diǎn)數(shù)組進(jìn)行渲染，為節(jié)省內(nèi)存，提高OPENGL渲染效率，使用了頂點(diǎn)緩沖區(qū)來(lái)存儲(chǔ)生成的頂點(diǎn)數(shù)組數(shù)據(jù).OPENGL渲染時(shí)的空間關(guān)系如圖5所示.

圖5 OPENGL渲染空間關(guān)系

為確保渲染后生成的紋理圖像每一點(diǎn)的顏色值即為體數(shù)據(jù)坐標(biāo)值，從而減少渲染后進(jìn)行坐標(biāo)變換而產(chǎn)生的浮點(diǎn)運(yùn)算，需要將頂點(diǎn)集的坐標(biāo)歸一化到(0，0，0)至(1，1，1)范圍內(nèi)，初始視點(diǎn)坐標(biāo)為(0.5，0.5，2.5).圖6是進(jìn)行八叉樹(shù)重構(gòu)后的渲染結(jié)果，可以看出，進(jìn)行八叉樹(shù)剖分重構(gòu)后的結(jié)果已經(jīng)非常接近物體的實(shí)際形狀了，因此相對(duì)于直接對(duì)包圍盒進(jìn)行渲染，重構(gòu)后的體數(shù)據(jù)可以更快速的進(jìn)行空體素跳過(guò).

圖6 teapot八叉樹(shù)重構(gòu)后的渲染結(jié)果

3.2 體數(shù)據(jù)對(duì)半剖分

GPU通常使用深度緩沖區(qū)的Z值來(lái)進(jìn)行深度檢測(cè)，對(duì)所渲染的體數(shù)據(jù)中每個(gè)體素所對(duì)應(yīng)的Z值進(jìn)行比較，以決定保留還是剔除.對(duì)于未被遮擋的空體素點(diǎn)，由于已經(jīng)不存在于頂點(diǎn)集合中，GPU不再渲染它們，而對(duì)同一視線方向上的2個(gè)有效體素點(diǎn)，在近點(diǎn)渲染中，Z值大的點(diǎn)被拋棄；而在遠(yuǎn)點(diǎn)渲染中，Z值小的被拋棄.一種常用的緩沖區(qū)Z值計(jì)算公式為

(8)

式中：z為視點(diǎn)到頂點(diǎn)的空間距離；f、n分別為視點(diǎn)到遠(yuǎn)裁剪面和近裁剪面的空間距離.

如前所述，傳統(tǒng)的GPU渲染的方法對(duì)于具有中空結(jié)構(gòu)的體數(shù)據(jù)無(wú)能為力，正是因?yàn)镚PU的深度檢測(cè)雖然可以檢測(cè)出部分空體素，但是僅限于那些未被遮擋的空體素，而那些位于中空部分的點(diǎn)則無(wú)法被檢測(cè)到.詳細(xì)分析此問(wèn)題，如圖7所示，設(shè)在當(dāng)前視點(diǎn)的一條光線上有5個(gè)點(diǎn)，其中Sn和Sf分別表示距視點(diǎn)最近和最遠(yuǎn)的非空體素點(diǎn)，而Se1、Se2、Se3則表示3個(gè)空體素點(diǎn)，其中Se2和Se3位于Sn和Sf外側(cè).當(dāng)采用近點(diǎn)渲染時(shí)，由式(8)計(jì)算出每個(gè)點(diǎn)的Z值，很顯然Se2的Z值比Sn更小，但由于其為空體素，因此依然被剔除；反之同理，當(dāng)采用遠(yuǎn)點(diǎn)渲染時(shí)，雖然Se3的Z值比Sf更大，但也會(huì)被剔除.而Se1在兩次渲染過(guò)程中由于遮擋均未能剔除.因此可以想到，如果把Se1點(diǎn)也拿到Sn和Sf之外，則遮擋問(wèn)題也就迎刃而解了.本文提出一種方法，即在GPU渲染前對(duì)體數(shù)據(jù)先進(jìn)行對(duì)半剖分，如圖8所示，設(shè)斷開(kāi)部分為剖分部位，則對(duì)其剖分后的每一部分來(lái)說(shuō)，又產(chǎn)生了新的Sn和Sf，這里記為Sn′和Sf′，可以看到，Se1位于右半部分，且位于原來(lái)的遠(yuǎn)點(diǎn)Sf和新的近點(diǎn)Sn′之外，此時(shí)，再進(jìn)行渲染操作時(shí)，Se1也可以被跳過(guò)了.再比較對(duì)半剖分前后的渲染結(jié)果，可以發(fā)現(xiàn)，對(duì)半剖分前，光線的起點(diǎn)和終點(diǎn)分別是Sn和Sf′，剖分后，其在左半部分的起點(diǎn)和終點(diǎn)變?yōu)镾n和Sf，在右半部分變?yōu)镾n′和Sf，而Sf′和Sn′之間的空體素則被跳過(guò)了，因此，在光線投射過(guò)程中，光線實(shí)際經(jīng)過(guò)的距離大大縮短.

圖7 體數(shù)據(jù)剖分前的狀態(tài)

圖8 對(duì)半剖分后的狀態(tài)

對(duì)于圖3中的體數(shù)據(jù)，進(jìn)行對(duì)半剖分后，由一個(gè)封閉的中空結(jié)構(gòu)，變成了各自開(kāi)放的兩部分，這里稱(chēng)為V1和V2,如圖9所示.由圖9可以看出，剖分后的光線r2-r4均跳過(guò)了大量中空體素，整個(gè)體數(shù)據(jù)的可視化速度自然就加快了.

圖9 原始體數(shù)據(jù)剖分后的兩部分

對(duì)于剖分后的V1和V2兩部分，由于每部分只具有原來(lái)體數(shù)據(jù)的1/2有效體素，亦即其各自的另一半被人為掏空了，在后續(xù)的光線投射與顏色累積過(guò)程中，為保證生成正確的圖像，必須保留每部分的位置關(guān)系，即保證每部分中所有有效體素的坐標(biāo)保持不變.為此，本文對(duì)被剖掉的部分用空體素來(lái)進(jìn)行填充，因此這種方法會(huì)需要增加內(nèi)存使用量，是一種以空間換時(shí)間的方法.

剖分后的V1和V2兩部分還需要分別進(jìn)行建立八叉樹(shù)和剔除空塊、建立新的有效頂點(diǎn)數(shù)組的操作，才可以進(jìn)行前向和后向渲染.

4 CUDA繪制

CUDA核函數(shù)是由多個(gè)線程組成的多個(gè)線程塊的網(wǎng)格，同一個(gè)線程塊中的線程可以方便的進(jìn)行通信.針對(duì)本文實(shí)驗(yàn)所使用的數(shù)據(jù)分辨率、生成圖像大小，以及CUDA設(shè)備的實(shí)際計(jì)算能力，在啟動(dòng)CUDA核函數(shù)前，CUDA線程塊的大小設(shè)置為(16,16)，網(wǎng)格大小為(16,16).

需要注意的是，由于渲染后的前向和后向紋理是由OPENGL生成的，而OPENGL中的紋理在CUDA中無(wú)法直接使用.本文通過(guò)OPENGL和CUDA的互操作方法，使用CUDA的內(nèi)存注冊(cè)和映射機(jī)制將OPENGL紋理映射為CUDA中的數(shù)組，然后在CUDA中再綁定為CUDA紋理，這種方法可以節(jié)省很多數(shù)據(jù)在內(nèi)存中的復(fù)制時(shí)間，提高內(nèi)存使用率和算法效率.同樣的，為接收CUDA核函數(shù)返回的最終結(jié)果，并使用OPENGL進(jìn)行繪制顯示，同樣要將OPENGL中的PBO(pixelbufferobject)映射到CUDA中的數(shù)組中，這樣CUDA核函數(shù)計(jì)算的結(jié)果也就可以被OPENGL實(shí)時(shí)接收并顯示了.

具體算法過(guò)程如下：

1)讀入完整體數(shù)據(jù)，將其從中間部位剖分成兩部分V1和V2.

2)分別對(duì)V1和V2建立八叉樹(shù)，并進(jìn)行空體素塊剔除，建立兩個(gè)新的有效體素塊頂點(diǎn)集合.

3)使用GPU分別對(duì)新建立的V1和V2的頂點(diǎn)集合進(jìn)行前向和后向渲染，并保存到紋理中，最后得到V1的前向和后向紋理，V2的前向和后向紋理共4個(gè)紋理.

4)通過(guò)OPENGL和CUDA互操作，將步驟3)得到的紋理映射到CUDA中，以供CUDA使用.

5)啟動(dòng)CUDA核函數(shù)，依次對(duì)V1和V2進(jìn)行光線投射，兩部分光線投射的起點(diǎn)和終點(diǎn)可以從步驟3)中得到的紋理結(jié)果中讀取.

6)在核函數(shù)中將得到的兩個(gè)結(jié)果進(jìn)行合成，并映射到OPENGL紋理，得到最終圖像.

其中，步驟5)中的CUDA核函數(shù)的具體算法流程如圖10所示，算法包括兩個(gè)相對(duì)獨(dú)立的子過(guò)程，分別獲取V1和V2的光線起止點(diǎn)和光線方向，完成各自的顏色和透明度累積過(guò)程，最后將兩個(gè)過(guò)程的結(jié)果累加，得到最終圖像.

5 結(jié)果與分析

實(shí)驗(yàn)所用的計(jì)算機(jī)配置如下：2.6GHz雙核CPU，4G內(nèi)存，編程環(huán)境為VisualStudio2008，顯卡采用GeForceGT635M，1G顯存，擁有2個(gè)SM(streammultiprocessor)，96個(gè)CUDA核心，CUDA計(jì)算能力2.1，CUDA版本5.5.

共使用了兩組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，分別為腳趾骨(foot)和茶壺(teapot)，CT數(shù)據(jù)尺寸均為256×256×256，為對(duì)本文方法進(jìn)行驗(yàn)證和評(píng)價(jià)，本文實(shí)現(xiàn)了文獻(xiàn)[4]的基于GPU渲染的方法以及文獻(xiàn)[10]中的八叉樹(shù)編碼方法，并將結(jié)果與本文提出的方法進(jìn)行了比較.teapot數(shù)據(jù)集的圖像對(duì)比結(jié)果如圖11(a)～(c)所示，foot數(shù)據(jù)集如圖11(d)～(f)所示.由上至下分別為Westermann方法(簡(jiǎn)稱(chēng)W方法)、八叉樹(shù)方法以及本文方法.

圖10 CUDA核函數(shù)流程

圖11 3種方法生成圖像對(duì)比

3種方法的數(shù)據(jù)預(yù)處理時(shí)間見(jiàn)表1.文獻(xiàn)[4]方法由于無(wú)須創(chuàng)建八叉樹(shù)結(jié)構(gòu)，只需要消耗體數(shù)據(jù)的裝載時(shí)間，因此所需要的預(yù)處理時(shí)間最短.本文方法的預(yù)處理時(shí)間少于八叉樹(shù)編碼方法，這是由于本文剔除空塊操作與構(gòu)造八叉樹(shù)是同時(shí)進(jìn)行的，因此可以節(jié)省更多的預(yù)處理時(shí)間.在實(shí)際可視化應(yīng)用中，圖像在繪制階段的成像時(shí)間更為重要，因此，相對(duì)于獲得更為滿(mǎn)意的加速效果，預(yù)處理時(shí)間的有限增加是可以接受的.

表1 數(shù)據(jù)預(yù)處理時(shí)間比較 ms

3種方法的核函數(shù)運(yùn)行時(shí)間對(duì)比見(jiàn)表2, 3.表中的加速比分別為八叉樹(shù)編碼方法和本文方法相對(duì)于文獻(xiàn)[4]方法的加速百分比.

從成像效果看，3種方法沒(méi)有明顯差異.對(duì)于teapot數(shù)據(jù)集，由于茶壺是中空結(jié)構(gòu)，其內(nèi)部具有較多的空體素，由核函數(shù)運(yùn)行時(shí)間可以看出，因此本文提出的對(duì)半剖分方法相較于另外兩種方法，均有非常顯著的加速效果，且光線投射步長(zhǎng)越小，加速效果越明顯；而對(duì)于foot數(shù)據(jù)集，加速效果則相對(duì)不太明顯，這是因?yàn)槟_趾骨的結(jié)構(gòu)不是中空的，內(nèi)部很少有空體素可以跳過(guò).

表2 foot數(shù)據(jù)集核函數(shù)運(yùn)行時(shí)間對(duì)比

表3 teapot數(shù)據(jù)集核函數(shù)運(yùn)行時(shí)間對(duì)比

6 結(jié) 論

1)通過(guò)改進(jìn)的八叉樹(shù)層次分解方法，將體數(shù)據(jù)進(jìn)行重構(gòu)，使數(shù)據(jù)表達(dá)和存儲(chǔ)更加高效和易于處理.

2)提出一種將原始體數(shù)據(jù)先對(duì)半剖分成兩部分再分別進(jìn)行渲染以跳過(guò)中空部分體素的方法，使得在光線投射過(guò)程中，最大程度的減少因空體素計(jì)算導(dǎo)致的冗余計(jì)算問(wèn)題.

3)結(jié)合使用GPU硬件渲染的方法，快速跳過(guò)在體數(shù)據(jù)包圍盒外部的空體素，節(jié)省了傳統(tǒng)光線投射算法中手動(dòng)計(jì)算光線與包圍盒交點(diǎn)而浪費(fèi)的時(shí)間.

4)實(shí)驗(yàn)結(jié)果表明，本文提出的方法生成的圖像質(zhì)量和傳統(tǒng)的方法沒(méi)有明顯差別，但可以有效的跳過(guò)中空體素，對(duì)于中空結(jié)構(gòu)的體數(shù)據(jù)的可視化具有明顯的加速效果.

[1] LEVOY M. Display of surface from volume data [J]. IEEE Computer Graphics & Application, 1988, 8(3):29-37.

[2] CULLIP T J, NEUMANN U. Accelerating volume reconstruction with 3D texture hardware. Technical report, TR93-027 [R]. NC, USA: University of North Carolina at Chapel Hill, 1994.

[3] CABRAL B, CAM N, FORAN J. Accelerated volume rendering and tomographic reconstruction using texture mapping hardware[C]//Proceedings of the 1994 Symposium on Volume Visualization. York, NY: ACM, 1994:91-98.

[4] KRUGER J,WESTERMANN R. Acceleration techniques for GPU-based volume rendering [C]// Proceedings of the 14thIEEE Visualization 2003 (VIS′03). Washington, DC: IEEE Computer Society, 2003: 38.

[5] SCHARSACH H, HADWIGER M, NEUBAUEr A, et al. Perspective isosurface and direct volume rendering for virtual endoscopy applications [C]//Proceedings of Eurographics/ IEEE-VGTC Symposium on Visualization. Lisbon, Portugal: The Eurographic Association, 2006: 315-322.[6] HADWIGER M, LJUNG P, SALAMA C R, et al. Advanced illumination techniques for GPU volume raycasting [C]//Proceedings of the ACM Special Interest Group on Computer Graphics and Interactive Techniques. New York: ACM, 2008.

[7] QIAN Fengchen, SHAN Ning, YE Yalin. A model of point multiresolution rendering method [C]// International Conference on Structural Engineering, Vibration and Aerospace Engineering (SEVAE 2013). Zhuhai: Trans Tech Publications LTD, 2014, 482: 355-358.

[8] 劉白林, 黃舒舒, 劉云卿. 八叉樹(shù)編碼與GPU加速結(jié)合的光線投射法 [J]. 西安工業(yè)大學(xué)學(xué)報(bào), 2011, 31(1):65-68.[9] LIU B Q, CLAPWORTHY G J, DONG F, et al. Octree rasterization: accelerating high-quality out-of-core GPU volume rendering [J]. IEEE Transaction on Visualization and Computer Graphics, 2013, 19(10):1732-1745.

[10]康健超, 康寶生, 馮筠, 等. 基于八叉樹(shù)編碼的CUDA光線投射算法[J]. 西北大學(xué)學(xué)報(bào):自然科學(xué)版, 2012, 42(1):36-41

[11]BERGNER S, MOLLER T, WEISKOPF D, et al. A spectral analysis of function composition and its implications for sampling in direct volume visualization [C]//IEEE Transactions on Visualization and Computer Graphics. Piscataway, NJ：IEEE Educational Activities，2006, 12(5):1353-1360.

[12]SUWELACK S, HEITZ E, UNTERHINNINGHOFEN R, et al. Adaptive GPU ray casting based on spectral analysis[C]// Proceedings of the 5thInternational Conference on Medical Imaging and Augmented Reality. Berlin, Heidelberg: Springer-Verlag, 2010: 169-178.

[13]葉良, 單桂華, 遲學(xué)斌. 基于CUDA加速的光線投射法研究 [J]. 圖像圖形技術(shù)研究與應(yīng)用, 2010: 235-240.

[14]蘇超軾, 趙明昌, 張向文. GPU加速的八叉樹(shù)體繪制算法 [J]. 計(jì)算機(jī)應(yīng)用, 2008, 28(5):1232-1235.

(編輯 張 紅)

GPU-based ray casting method by half-splitting volume data

YU Shui，WANG Kuanquan，XIA Yong，ZHANG Henggui

(School of Computer Science and Technology, Harbin Institute of Technology, 150001 Harbin, China)

To alleviate the inefficiency of the current visualization methods in skipping the empty voxels located in the hollow part, this paper presents a GPU-based ray casting method for hollow volume data. First, the volume is divided into two equal parts and reconstructed into two octrees before rendering. In this process, the empty blocks are culled synchronously from the original data, and two vertex arrays are generated consisting of valid voxels only. Then, the vertex arrays are rendered into textures which contain the start and direction information of the ray. The final images are obtained by calculating the color and opacity of the two parts with CUDA, respectively. The experimental results show that our method can speed up the rendering speed considerably on the volume data with large hollow structure without any quality loss compared with the traditional visualization methods.

data visualization; ray casting; GPU rendering; octree; CUDA; hollow volume data

10.11918/j.issn.0367-6234.2016.04.012

2014-09-23.

國(guó)家自然科學(xué)基金(61173086)；山東省科技發(fā)展計(jì)劃資助(2012GSF12105).

于 水(1976—)，男，博士研究生；

王寬全(1964—)，男，教授，博士生導(dǎo)師；

王寬全，wangkq@hit.edu.cn.

TP391.41

A

0367-6234(2016)04-0073-06

張恒貴(1964—)，男，教授，博士生導(dǎo)師.