傳統(tǒng)軟陰影算法在GPGPU 構架上的優(yōu)化技術研究

高明磊，趙新燦，詹 云

(鄭州大學 信息工程學院，河南 鄭州450001)

0 引言

近年來，計算機圖形學有著巨大的發(fā)展，隨著應用需求的增加，真實感圖形渲染也越來越受到關注，要生成視覺上十分精確的軟陰影效果需要耗費很多的計算． 近些年，GPU 的運算性能快速增長，其浮點運算能力明顯超越了CPU，使得GPU 擅于進行大規(guī)模密集型數(shù)據(jù)的并行計算［1-2］．GPU 強大的性能優(yōu)勢為高實時性的陰影研究提供了良好的解決思路，對設計虛擬場景中真實感強、實時性高的陰影，特別是對軟陰影效果有著重要的研究意義．

陰影繪制算法主要分為陰影體算法［3］、陰影映射算法［4］和全局光照算法［5］． 在真實感方面，陰影體算法和全局光照算法是以犧牲實時性為代價，換取稍好的真實感;而陰影映射算法雖然存在走樣等現(xiàn)象，通過過濾等方式依然能夠獲得很好的陰影效果［6］． 在實時性方面，陰影體算法和全局光照算法實時性較差;而陰影映射算法基于圖像空間，算法復雜度與場景復雜度無關，且易于GPU 加速，實時性較高． 陰影映射算法根據(jù)半影區(qū)情況分為兩大類:半影區(qū)大小固定和半影區(qū)大小可變的陰影算法． 半影區(qū)大小固定的陰影算法主要有百分比接近濾波PCF 算法、方差陰影映射VSM 算法、卷積陰影映射CSM 算法和指數(shù)陰影映射ESM 算法;半影區(qū)大小可變的陰影算法主要有百分比靠近軟陰影PCSS(Percentage Closer Soft Shadow)算法［7］，算法性能如表1 所示．

1 基于GPGPU 的改進軟陰影映射算法

1．1 算法主要改進思想

由表1 可知，PCSS 算法是相對更好的一種軟陰影生成算法，軟陰影效果更加符合陰影的物理特征．在PCSS 算法的基礎上，提出一種新的軟陰影生成算法，如圖1 所示．

首先，針對PCSS 算法不能硬件預濾波的問題，使用VSM 算法代替PCF 算法進行過濾，這樣在陰影圖中存儲的是深度值和深度值的平方，對陰影圖就可以使用各向異性過濾、區(qū)域求和表等濾波技術，加速濾波效率，提高陰影質(zhì)量．

表1 主要陰影算法特點對比Tab．1 Comparison of shadow algorithm

其次，由于陰影圖濾波中每個像素點的濾波區(qū)域是動態(tài)計算的，生成區(qū)域求和表耗時多，針對此問題，筆者采用DirectCompute 在GPU 上加速生成區(qū)域求和表，提高濾波效率．

最后，使用泊松圓盤采樣代替規(guī)則采樣，無需過多的采樣便能提高陰影質(zhì)量，針對自陰影問題，采用深度梯度法得到可變的深度偏移值來處理．

圖1 本文擬采用方法Fig．1 Research methods of this article

本文軟陰影算法由CPU 端和GPU 端共同完成，其中，在CPU 上主要實現(xiàn)場景初始化、信息更新等任務;算法的大部分工作由GPU 實現(xiàn)，利用DirectX 11 中可編程部分vertex shader、pixel shader 和compute shader，充分利用GPU 的性能優(yōu)勢，加速和優(yōu)化算法的實現(xiàn)，從而獲得更高的質(zhì)量和效率，任務劃分如圖2 所示．

1．2 基于區(qū)域求和表的陰影圖預濾波

利用區(qū)域求和表技術對陰影圖動態(tài)濾波，得到深度值和深度值平方的期望，進而計算相應的均值和方差．再根據(jù)切比雪夫不等式得到像素點的陰影權值．實現(xiàn)時將接受體當前點深度值與區(qū)域求和表求得的濾波區(qū)域均值進行比較． 如果當前點深度值小于區(qū)域均值，則當前點不在陰影中，P=1;如果當前點深度值大于區(qū)域均值，則利用切比雪夫不等式求出當前點在陰影中的概率上限Pmax，以此來渲染陰影效果．

圖2 基于GPGPU 的軟陰影映射算法流程Fig．2 Soft shadow mapping algorithm based on GPGPU

對于具有元素a［i，j］的紋理可按公式(1)建立一個區(qū)域求和表t［i，j］:

區(qū)域求和表中的每個元素為紋理中位于這個元素左側(cè)及上側(cè)所有元素之和，生成區(qū)域求和表后，就可以求得任意一個矩形濾波區(qū)域的和．通過對濾波區(qū)域的4 個角點進行采樣求區(qū)域和值，再將區(qū)域和值除以區(qū)域面積，就可以得到濾波區(qū)域的均值． 如圖3 所示，左圖灰色部分代表濾波區(qū)域，采樣該區(qū)域的4 個角點A、B、C 和D，則該濾波區(qū)域的均值為(A-B-C+D)/4，即為4．5．

圖3 區(qū)域求和表計算過程Fig．3 Summed area table calculation process

1．3 基于泊松圓盤采樣的遮擋物查找

在遮擋物查找過程中，需要多次采樣求遮擋物的平均遮擋深度．采樣數(shù)目越多，軟陰影的質(zhì)量越好，但是過多的采樣數(shù)會降低算法的性能．泊松圓盤采樣模式(poisson disk pattern)［8］就是目前非常好的一種圖像采樣方式． 通常采用擲標法(dart throwing)來生成泊松圓盤序列，所有采樣點分布在半徑為1 的單位圓盤上，得到的所有采樣點之間的距離都大于一個最小距離(記為閾值)，該閾值設置在0．05 ～1．0 最佳．在遮擋物查找過程中，將泊松圓盤采樣點與遮擋物查找區(qū)域半徑相乘作為紋理坐標偏移量，再對處理后的紋理坐標進行采樣得到陰影圖中相應紋理坐標下的深度值．通過上述得到陰影圖中相應坐標下的深度值后與接受體當前點的深度值進行比較，從而計算遮擋物的平均遮擋深度．

1．4 基于深度梯度法的自陰影處理

為了處理自陰影現(xiàn)象，需要動態(tài)計算深度偏移值．深度梯度法能夠有效地處理自陰影問題，消除陰影粉刺或偏離現(xiàn)象． 對于給定的函數(shù)d(x，y)，在位置(x，y)處的梯度矢量如公式(2)．

計算深度偏移值時，必須把屏幕空間轉(zhuǎn)換到紋理空間，轉(zhuǎn)換如公式(3):

其中，gradient 即為轉(zhuǎn)換到紋理空間的深度梯度;G［d(x，y)］是屏幕空間的深度梯度矢量;中間是紋理空間的雅克比矩陣．

將深度梯度值與偏移量uv_offset 進行點乘，就可以得到深度偏移值，從而計算最終的深度值，如公式(4):

將該值與相應紋理坐標下采樣得到的深度值進行比較，就可以有效消除陰影粉刺或偏離現(xiàn)象．

2 基于GPGPU 的區(qū)域求和表生成

2．1 區(qū)域求和表生成方法

區(qū)域求和表生成有兩種方法:逐行方法(lineby-line)和回溯倍增方法(recursive doubling)． 回溯倍增法［9-10］可以在GPU 端并行計算，算法中前綴求和是基于Hillils 和Steele 提出的掃描算法，對于一個二進制運算符⊕和一個n 元數(shù)組A ={a0，a1，…，an，進行前綴求和得到的結果每個元素都是其所有前綴和其自身經(jīng)過⊕運算得到的結果，記為B={a0，(a0⊕a1)，……，(a0⊕a1⊕…an-1)}．

2．2 區(qū)域求和表在GPU 上的實現(xiàn)

(1)將生成的陰影圖分成大小相同的塊，每塊對應GPGPU 的一個線程組，如圖4 所示． 筆者采用的GPU 是NVIDIA GeForce GT440，每個線程組包含的線程數(shù)限制在1 024 內(nèi)． 對于高和寬分別為h 和w 的陰影圖，假設每個分塊大小為16*32 共512 個像素點，則需要分成的線程組數(shù)為(w/16)* (h/32)，如果分塊的尺寸不能被線程組的尺寸整除，則實際分配的線程組數(shù)應該為(w/16 +1)* (h/32 +1)［11］．

圖4 陰影圖分塊Fig．4 Shadow map block

(2)將陰影圖的每個分塊數(shù)據(jù)讀入線程組的共享存儲器中，使得線程組內(nèi)的所有線程可以同時讀取分塊數(shù)據(jù);利用線程對分塊的每一行進行并行前綴求和運算，并利用線程同步機制待所有線程執(zhí)行完畢后再將最終結果寫入類型為RWTexture2D 的全局存儲器中．

(3)將前面計算得到的每個分塊結果的每行最后一個元素值即分塊總和，從全局存儲器讀到共享存儲器中，利用線程對這些分塊總和進行并行前綴求和運算．將對應行分塊總和i 加到分塊i+1 的對應行的所有值上，并將最終結果寫入全局存儲器中，就完成了陰影圖中所有行的前綴求和運算．

(4)對上一步的結果進行轉(zhuǎn)置運算，對轉(zhuǎn)置后的陰影圖數(shù)據(jù)重復上面三步，進行所有列的運算，再將最終結果進行轉(zhuǎn)置便生成了區(qū)域求和表，如圖5 所示．

3 基于GPGPU 的軟陰影算法實驗結果分析

3．1 PCSS 算法規(guī)則采樣效果

軟陰影的渲染速率和陰影質(zhì)量與采樣模式以及采樣數(shù)等因素密切相關． 圖6 所示為場景使用PCSS 算法在規(guī)則采樣模式下，分別利用25，49，81 個不同數(shù)目的采樣點對場景進行陰影渲染的細節(jié)特寫，陰影圖大小為1 024* 1 024．

當采樣數(shù)為25 時，陰影中有明顯的帶狀條紋，隨著采樣數(shù)目的增多，陰影效果越來越好．當采樣數(shù)為81 時，陰影邊緣已經(jīng)比較柔和．但是，隨著采樣數(shù)目的增多，算法的效率卻在降低，如表2所示．

圖5 基于GPGPU 的區(qū)域求和表計算Fig．5 Summed area table calculation based on GPGPU

圖6 不同采樣數(shù)陰影效果細節(jié)對比Fig．6 Detail contrast of different sampling number

表2 PCSS 算法性能分析Tab．2 Performance analysis of PCSS algorithm

3．2 改進算法泊松圓盤采樣效果

為解決陰影質(zhì)量與渲染效率的矛盾，使用泊松圓盤采樣代替規(guī)則采樣模式． 圖7 所示為在兩種不同采樣模式下的軟陰影渲染效果，遮擋物查找階段使用的采樣點數(shù)均為64．

圖7(a)、(b)為PCSS 算法在規(guī)則采樣方式下渲染的軟陰影效果，過濾階段采樣數(shù)分別為64，361;圖7(c)圖為PCSS 算法在泊松圓盤采樣方式下渲染的軟陰影效果，過濾階段采樣數(shù)為64．從圖中可以看出，圖7(a)圖中軟陰影邊緣仍有部分帶狀走樣;(b)圖過濾階段使用較多的采樣點，軟陰影邊緣較柔和;而(c)圖使用泊松圓盤采樣，過濾階段僅使用64 個采樣點，得到的軟陰影與(b)的效果差不多，算法性能如表3 所示．

圖7 不同采樣模式對軟陰影效果的影響Fig．7 Effect of the different sampling patterns

表3 規(guī)則采樣與泊松圓盤采樣效果對比Tab．3 Comparison of two sampling methods

3．3 改進算法自陰影效果處理

針對自陰影現(xiàn)象采用深度梯度法進行處理，效果如圖8 所示． 在圖8(a)中出現(xiàn)了自陰影現(xiàn)象，如模型足部與陰影之間有縫隙，出現(xiàn)了陰影移位，這主要是由于常量深度偏移值選擇不當造成的;而圖8(b)中，采用深度梯度法動態(tài)計算偏移量，有效地消除了自陰影現(xiàn)象，軟陰影效果較好．

圖8 自陰影現(xiàn)象的消除Fig．8 Elimination of self shadow

3．4 改進算法與原算法整體性能的對比

PCSS 算法和本文算法渲染的效果比較如圖9 所示．從圖9 中可以看出，本文算法渲染的軟陰影邊緣柔和，效果更加清晰，完全滿足了軟陰影真實感渲染的需求．

圖9 PCSS 算法與本文改進算法渲染的軟陰影效果Fig．9 Rendering soft shadows of PCSS and improved algonthm

改進算法與原算法性能對比如表4 所示．

表4 PCSS 算法與改進算法性能對比Tab．4 Comparison of PCSS algorithm and improved algorithm

4 結論

鑒于陰影對增強三維場景真實感渲染的重要性，在PCSS 算法的基礎上提出一種改進的軟陰影算法．利用深度梯度法得到動態(tài)的深度偏移值消除陰影粉刺和偏離問題;在過濾階段利用VSM算法代替PCF 算法，并結合區(qū)域求和表對陰影圖進行預先濾波;利用GPU 通用計算的優(yōu)勢生成區(qū)域求和表算法，并和傳統(tǒng)的利用Direct3D 的像素著色器生成區(qū)域求和表算法進行了對比． 結果表明，改進后的軟陰影算法具有更好的陰影質(zhì)量和更高的性能，加速比是原PCSS 算法的3 倍以上，充分體現(xiàn)了本文算法的優(yōu)越性．

［1］ 唐滔．面向CPU-GPU 異構并行系統(tǒng)的編程模型與編譯優(yōu)化關鍵技術研究［D］． 長沙:國防科學技術大學計算機學院，2012．

［2］ 韓博，周秉鋒． GPGPU 性能模型及應用實例分析［J］．計算機輔助設計與圖形學學報，2009，21(9):1219 -1226．

［3］ TIM H． Real shadows，real time［R］． Iris:Iris Universe，1991:23 -31．

［4］ BAVOIL L，CALLAHAN STEVEN P，CLAUDIO T．et al．Robust soft shadow mapping with backprojection and depth peeling［J］． Journal of Graphics Tools，2008，13(1):19 -29．

［5］ APPEL A． Some techniques for shading machine renderings of solids［C］//AFIPS 1968 Spring Joint Computer Conf． San Francisco，California，1968，32:37 -45．

［6］ LIU Lu，XIAO Shuang-jiu．Real-time soft shadows for large-scale virtual environments［C］//2011 International Conference on Multinedia Technology (ICMT)．Hangzhou，China:IEEE Press，2011:5464 -5467．

［7］ FERNANDO R．Percentage-closer soft shadows［C］//ACM SIGGRAPH 2005 Sketches and Applications．New York:ACM Press，2005:35

［8］ DUNBAR D，HUMPHREYS G．A spatial data structure for fast poisson-disk sample generation［J］． ACM Transactions on Graphics，2006，25(3):503 -508．

［9］ NEHAB D，MAXIMO A，RODOLFO LIMA，et al．GPU-efficient recursive filtering and summed-area tables［J］． ACM Transactions on Graphics，2011，30(6):1 -11．

［10］FRANKLIN C C．Summed-area tables for texture mapping［C］//SIGGRAPH 1984:Proceedings of The 11th Annual Conference on Computer Graphics and Interactive Techniques．Minneapolis，Minnesota:ACM Press，1984:207 -202．

［11］孫偉東，馬宗民．一種適合于GPU 計算的并行后綴數(shù)組構造算法［J］． 小型微型計算機系統(tǒng)，2011，32(5):830 -836．