一種適合于ＭＭＯＧ的快速動態場景軟陰影繪制算法

摘要:為滿足MMOG實時交互的需要，該文在分析了影響動態場景軟陰影算法效率的主要因素之后，提出一種適合于MMOG的快速軟陰影算法。該算法利用包圍盒可以用較少的點描述物體位置信息的特點，快速地計算出遮光物體與光源和接收面之間的距離關系，確定半影區的寬度和位置，避免了求平均深度值的耗時計算。經與使用平均深度值作為遮擋物距離的經典軟陰影算法通過實驗進行比較，本方法可以更好地滿足MMOG對于實時性的要求，同時不產生明顯的視覺失真。

關鍵詞:MMOG;動態場景;實時渲染;軟陰影

中圖分類號:TP301 文獻標識碼:A 文章編號:1009-3044(2009)15-4022-04

A Fast Soft Shadows Algorithm for Dynamic Scene in MMOG

DUAN Yan-chao

(Department of Computer Science and Engineering， Shenyang Institute of Aeronautical Engineering， Shenyang 110136， China)

Abstract: In order to meet the requirements of real-time interaction of MMOG， based on the analysis of the main factors which impact the efficiency of dynamic scene soft shadow algorithm， this paper presents a fast soft shadows algorithm of dynamic scene for MMOG. Using of the characteristics that the bounding box could instead the object in MMOG with the fewest vertices， this method quickly calculates the distance relationship between object and the receive surface， determines the width and location of the penumbra. It can avoid the time-consuming calculation of getting the average value for depth. Compared with the classic Algorithms， the method can better meet the real-time requirements of MMOG， and does not generate serious visual distortion.

Key words: MMOG; Dynamic Scene; Real-time rendering; Soft-Shadow

1 引言

在計算機圖形學領域中，動態場景軟陰影的快速渲染一直是一個富有挑戰性的問題。陰影能有效地表現出不同物體之間的相對位置關系，從而增加圖像的立體感和層次感。按繪制效果，陰影分為硬陰影和軟陰影兩種。軟陰影能真實地表現陰影效果，它由本影區和半影區組成。在軟陰影中半影區的寬度和半影區的位置是由光源、遮擋面以及接收面之間的距離和光源的尺寸決定的。由于在現有的動態場景軟陰影繪制算法中，為了得到準確的半影區寬度和半影區位置需要進行非常繁瑣的計算，不能滿足MMOG實時性的要求，所以我們采用了一種主要提高渲染速度兼顧圖像質量的方法來實現MMOG中的軟陰影繪制。

2 使用包圍盒輔助的軟陰影算法

經過分析我們得出使用平均深度值的方法求遮擋物距離是十分耗時的。平均深度值求得的遮擋物距離只是近似等于該點的真實遮擋物距離[7]。為了求得準確的遮擋物距離，有一種很好的方法就是遍歷遮擋物的邊緣邊，逐個頂點的計算其到光源平面的距離。但是這種方法的缺點和Shadow Volumes方法一樣，有很嚴重的場景依賴性。經過實驗我們發現場景中的軟陰影具有如下的一個特點。如圖1所示，場景中點a、點b和點d是遮擋物在光源平面上投影輪廓邊緣上的點，經過計算點a的半影區寬度是該遮擋物產生的半影區中最大的，點b的半影區寬度最小。點d是遮擋物投影邊緣的一點，它在接收面上的投影為點c。經過計算點d產生的半影區寬度介于點a和點b之間，該半影區的寬度值與點c到點a點b在接收面上投影點的距離比值成比例。利用這一特點，我們設想如果先計算出場景中最大的最小的半影區寬度的產生位置，其余的半影區寬度通過該半影區的所在位置與最大最小值的所在位置的距離關系插值完成，以此來快速地確定每一個需要渲染的點的半影區寬度。但是如果遍歷整個遮擋物來求最大最小值會非常的耗時，所以我們利用MMOG碰撞檢測模塊提供的模型包圍盒可以用最少的點緊密包裹物體的特點，使用模型包圍盒近似代替物體，來快速地確定遮擋物與光源的位置關系。求得物體的最大最小半影區寬度及產生位置。

2.1 遮擋物距離的計算

為了求得遮擋物產生的最大最小半影區寬度，首先需要確定遮擋物的哪個部分會產生最大和最小的半影區，也就是距離光源平面最遠和最近的部分。本方法使用MMOG中用來處理碰撞檢測的包圍盒技術來快速的估計出遮光物體與光源的位置關系。為了保證碰撞檢測的準確性，游戲多采用軸向多層次包圍盒。其特點是可以嚴密的包裹遮光物體。在光源面積較大的情況下，人眼已經很難準確地確定復雜遮光物體的半影區寬度及產生位置。所以我們采用以遮光物體包圍盒的位置近似代替遮光物體本身。快速的找出遮光物體距光源的最大距離和最小距離的近似值。以此作為該遮光物體的遮擋物深度的最大和最小值計算該遮擋物半影區寬度的最大和最小值。詳細步驟如下:

第一步，將遮光物體的包圍盒的所有頂點轉換到光源的眼坐標系下，形成該包圍盒在光源平面的投影區域。如圖3所示，a是模型頭部包圍盒，b和c分別是兩只手臂包圍盒，d是模型軀干和兩條腿的包圍盒。將4個包圍盒的頂點投影到光源平面。設光源在世界坐標系下的位置為{xw，yw，zw}={a，b，c}，光源的方向向量(xl'，yl'，zl')在XwOZw面上的投影向量與世界坐標系中的Z軸夾角為?茲，光源方向向量與XwOZw面的夾角為?漬，見圖2。設M為轉換矩陣，有{xe，ye，ze}={xw，yw，zw}M，得到世界坐標系向光源坐標系的轉換公式。代表了轉換后的點與視點的距離。

第二步，對所有的包圍盒投影區域進行遮擋檢測，來剔除那些對陰影效果不產生影響的包圍盒頂點。因為包圍盒投影后均為凸多邊形，所以過需要判斷的點向可能發生遮擋的包圍盒投影區域的所有頂點作向量，按順或逆時針方向計算所有向量的夾角，如果存在所有夾角均小于180度的情況，則該點被遮擋，剔除該點。圖3中，兩只手臂的包圍盒的全部頂點和頭部與身體包圍盒的部分頂點因為被遮擋，不會對半影區的寬度產生影響，經運算它們被剔除。遮擋檢測之后，剩余頭部包圍盒的點a1、a2和a3，和身體包圍盒的點d1、d2、d3、d4和d5。

第三步，確定遮擋物距離的最大和最小值。因為ze代表了轉換后的點與光源平面的距離。根據所有頂點ze的值，分別對每一個包圍盒剩余的頂點，求出ze最小的兩個頂點所組成的邊的中點位置和ze最大的兩個頂點所組成的邊的中點位置。如圖3所示，點a max代表包圍盒a與光源平面最近的兩個頂點的中點，點a min是最遠的兩個頂點的中點。所有中點中ze最大的為點max，ze最小的為點min。

以上就是利用包圍盒輔助求得場景中遮擋物近似距離的最大和最小值的過程。本方法只在每一幀渲染開始之前增加了處理包圍盒的時間，不需要在渲染每一個點時，為了求平均深度值而遍歷一塊和光源尺寸近似相等的深度圖區域。這使本方法有效地減輕了圖像輸出窗口和光源尺寸對算法執行速度的限制，更加適應MMOG的要求。

2.2 半影區寬度及過濾核尺寸的計算

在遮擋物距離的最大和最小值最后，我們要確定相應的最大和最小半影區寬度，以便渲染。使用點max的ze作為dl的值代入公式中求出點max對應的ws_max。同理求出點min對應的ws_min。用ws_max擴大包圍盒投影區域的范圍，得到一個用來限制渲染的矩形區域(圖3中虛線框圍成的區域)。點max和點min處對應的過濾核尺寸nmax和nmin可以使用η*ws求出，η是一個大于零的，根據希望達到的圖像質量而調整的浮點數。

最后，為場景中的每一個即將渲染的點確定過濾核尺寸，因為本文方法在此處使用插值計算，避免了遍歷深度圖求平均深度值的過程，所以本文方法的效率較高。在從攝像機視角對場景進行渲染時，將需要渲染點轉換到光源坐標下，然后投影到光源平面(深度圖所在的平面)。如圖4，對于轉換后處于限制渲染范圍外的點f不進行處理，以節省渲染時間。處于渲染范圍內的點e，分別計算它與點max和點min的距離，記為dmax和dmin。使用公式(2)確定點e在渲染時應該使用的PCF過濾核尺寸n。執行標準的PCF步驟過濾點e處的陰影比較結果得到一個處于0和1之間的浮點數作為該點處陰影顏色的濃度值，用這個濃度值修改像素著色器中該點的顏色值產生陰影效果。

2.3 算法描述

通過在計算遮擋物的距離、半影區寬度以及過濾核尺寸時很好地節省了時間，有效地提高了動態場景軟陰影算法的效率。本文算法流程如下:

1) 將遮光物體的包圍盒的所有頂點轉換到光源的眼坐標系下，形成該包圍盒在光源平面的投影區域。

2) 對所有的包圍盒投影區域進行遮擋檢測，來剔除那些對陰影效果不產生影響的包圍盒頂點。

3) 根據剩余的包圍盒頂點確定遮擋物距離的最大和最小值。

4) 確定相應的最大和最小半影區寬度。

5) 確定將要渲染的點的過濾核尺寸并渲染場景。

算法描述如下:

包圍盒結構體{包圍盒ID號，所屬對象的ID號，包圍盒頂點鏈表的頭指針，包圍盒組成面鏈表的頭指針};

包圍盒投影區結構體{對應包圍盒的ID號，三元組鏈表的頭指針(記錄組成該投影區域的頂點)，三元組(該投影區域所對應的包圍盒中距離光源最近的點)，三元組(該投影區域所對應的包圍盒中距離光源最遠的點)};

包圍盒頂點結構體{頂點ID號，所屬包圍盒ID號，三元組(記錄頂點位置)，1號所屬面的ID號，2號所屬面的ID號，3號所屬面的ID號};

包圍盒組成面結構體{組成面ID號，所屬包圍盒ID號，1號包含頂點的ID號，2號包含頂點的ID號，3號包含頂點的ID號，4號包含頂點的ID號，三元組(記錄面法向量)};

三元組(頂點或面法向量)結構體{分量x，分量y，分量z};//實現時此處實際為一個四元組

聲明鏈表B為包圍盒結構體的鏈表;

聲明鏈表P為包圍盒投影區結構體的鏈表;

將遮擋物的所有的包圍盒數據記錄到鏈表B;

遍歷鏈表B，循環處理每一個包圍盒的組成面鏈表;

{

如果(面a的法向量與光源的方向向量夾角<90度)

{

記錄面a所包含的全部頂點并記錄每一個頂點被記錄的次數;

如果(一個頂點的記錄次數達到三次)

{從記錄中剔除它;}

對所有記錄下來的頂點，使用公式(3)得到每一個頂點轉換到光源坐標系下的坐標，并且按所屬的包圍盒寫入鏈表P中;

}

} //鏈表P中保存了每一個包圍盒的投影區域

刪除鏈表B并釋放空間;

遍歷鏈表P，記錄每一個包圍盒投影區域中x和y方向的極值;

循環處理每一個包圍盒投影區域;

{

如果(包圍盒投影區域a與包圍盒投影區域b在x軸y軸上的投影發生遮擋)

{

對包圍盒投影區域a的所有頂點與包圍盒投影區域b的所有頂點進行遮擋判斷;

剔除被遮擋的頂點;

如果(包圍盒投影區域a的全部頂點均被剔除)

將包圍盒投影區域a從鏈表P中剔除;

}

} //鏈表P中所有剩余包圍盒投影區域的頂點組成了遮擋物在接收面上近似的投影形狀。

遍歷鏈表P，得到每一個包圍盒投影區域的頂點中分量z最大的兩個，和最小的兩個點的位置;

分別計算該投影域最大和最小的兩點的中點位置，并求得距光源距離;

將光源距離最大和最小的點作為整個遮擋物中的點max和點min;

使用公式(1)確定點max和點min對應的半影寬度ws_max和ws_max;

用ws_max的值擴展鏈表P在光源平面所產生的投影區域作為判斷是否渲染的處理區域;

{

渲染場景，將要渲染的點轉換到光源坐標系下;

如果(該點轉換后位置在處理區域內)

{使用公式(4)確定過濾核的尺寸;

對陰影比較結果執行過濾核大小為n的過濾;

渲染場景;

}

渲染場景;

}

以上為本文算法的描述及偽代碼，本文算法在渲染場景中的每一個點的時候，以插值代替遍歷深度圖，很好地提升了算法的效率，有效地滿足了MMOG實時性的要求。

3 實驗結果及分析

本文算法使用OpenGL及GLSL語言實現，在VC2005編程環境下實現。硬件配置為CPU雙核1.83G，內存1G，顯示卡為Nvidia 9300。為實驗過程中，繪制組成場景的三維模型部分以及場景深度圖的生成均由傳統的OpenGL API實現。陰影比較及PCF過濾由GLSL代碼編寫[10]。

為了滿足實時性的要求，MMOG使用的軟陰影算法必須具備很高的執行效率，本文實驗將比較使用平均深度值作為遮擋物距離的軟陰影算法和本文方法的渲染速度。現代個人微機的顯示器尺寸主流為19寸，玩家在進行游戲時通常會使用全屏顯示的模式，這導致現代游戲的分辨率很少低于800×600(分辨率越低效果越差)。一部分玩家為了追求較高的畫質，會將游戲分辨率設置到1024×768甚至更高。所以游戲分辨率對算法的影響是必須考慮的。另外在游戲中發光物體的種類很多，光源尺寸也會發生變化，不同的光源尺寸會導致半影區寬度的不同，所以光源的尺寸也是必須考慮的條件。根據游戲的特點，本文實驗的條件是在不同的游戲分辨率和不同的光源尺寸下，將本文方法與目前常用的使用平均深度值作為遮擋物距離的軟陰影繪制方法的PCSS方法還有文獻[9]使用方法的渲染速度作比較。實驗使用游戲中常見的機器人模型作為實驗遮擋物(模型來源于網絡)。為得到較精確的最大最小半影區的產生位置，模型包圍盒分為頭部、身體、左臂和右臂，采用OBB六面體包圍盒。為了便于實現，實驗中所有光源的形狀均為正方形。實驗數據見表(1)。

通過表(1)可以看出，由于本文方法避免了在渲染時，為每一個點求遮擋物距離的步驟，在所有條件下與PCSS方法相比運算速度都有優勢，只在游戲分辨率、光源尺寸和深度圖尺寸較小的時候，本文方法的運算速度才低于文獻使用方法。在表(1)中，本文方法的執行速度隨著光源和游戲分辨率的增大而降低。其原因是由于本文方法采用PCF方法過濾陰影比較結果，半影區寬度越寬，需要的PCF過濾核尺寸越大，游戲分辨率越大需要過濾的點越多。這導致了本文方法執行速度的下降。但是這也是所有使用類似PCF這種加大采樣數量來對陰影比較結果進行過濾得到軟陰影的方法的通病。使用平均深度值作為遮擋物距離的方法，由于光源尺寸的增加導致求平均深度值的時候需要搜索的紋素數量增加，游戲分辨率的加大致使每一幀需要求平均深度值的點增多，再加上PCF過濾核增大的原因導致這些方法的運行速度下降的更加明顯。PCSS方法和文獻使用的方法在深度圖和光源尺寸較小時速度提升明顯，甚至超過了本文方法的執行速度，是因為此種情況下求平均深度值的時候需要遍歷的紋素數量較少，節省了計算時間。本方法由于不涉及遍歷深度圖的步驟，所以深度圖的大小對于本算法的影響與普通貼圖紋理的尺寸對渲染速度的影響相同(越大速度越慢)。

圖5A圖7B分別是在游戲分辨率為1280×1024，光源尺寸為4×4，深度圖尺寸為2048×2048的情況下，PCSS方法和文獻[9]使用方法的實驗截圖。圖5C是本文方法在相同條件下的實驗截圖。圖5D和圖5E分別是PCSS方法和文獻使用方法在游戲分辨率為1280×1024，光源尺寸為12×12，深度圖尺寸為2048×2048條件下的實驗截圖，圖5F是本文方法在相同條件下的實驗截圖，右下角的小圖給出了圖像效果差距最大的部分。本方法生成的圖像質量和陰影精度與PCSS方法和文獻使用方法相比存在少許的差距，尤其是在圖5C與圖5B圖5A的對比中，人物左腳邊緣的半影區對比很明顯。本方法的圖像質量和陰影精度方面劣勢的產生原因是本方法得到的最大和最小半影區的位置并不是遮擋物中真正的最大和最小半影區位置。見圖5A，人物的頭頂和右腳外側才是最大和最小半影區的位置，而本方法得到位置分別在后腦和兩腳中間，見圖5C。這導致了其他由公式(1)得出的半影區寬度與真正的半影區寬度相比有誤差。這種誤差在半影區較小的時候最為明顯，這也就是為什么人物的腳部陰影是實驗中陰影精度差距最大的部分。

本文方法存在的另外一個不足是對遮光物體只計算了半影區的最大和最小值的產生位置。在求其他半影區寬度的時候只是簡單的根據距離進行插值，這樣當時物體自身的形狀特殊或者形狀發生變化但卻沒有影響到最大最小半影區的產生位置時，本文方法按照距離插值的方法會產生一定的誤差。這種物體在游戲中是存在的，但是與游戲場景中遮光物體種類的總數相比較是很小的一部分。并且這種物體通常是整體的形狀發生劇烈變化(骨骼動畫的效果)，其軟陰影的范圍本身就是變化的，此外軟陰影的準確位置又很難通過肉眼準確判斷，所以本文方法并不存在類似于shadow maps方法鋸齒狀走樣那種嚴重的視覺失真。但是，本文方法由于使用物體包圍盒來代替物體進行半影區計算，相比于平均深度值方法，本文方法有一定的場景依賴性。當場景中的遮擋物非常多時，本文方法只能通過距離視點較遠的物體，或者對于較遠而相對集中的多個物體采用一個包圍盒，以此來節省計算時間。

4 總結和展望

本文通過分析動態場景軟陰影繪制的瓶頸問題，得出了影響動態場景軟陰影渲染速度的關鍵在于能否快速地確定遮擋物距離。針對通過平均遮擋物表面深度值來確定遮擋物距離的軟陰影算法的缺陷，提出了使用包圍盒輔助的快速軟陰影繪制方法。實驗表明，本方法對圖像質量和陰影位置精度影響不大，卻有效地提高了運行速度，能很好的滿足MMOG實時性的要求。同時，因為包圍盒是由碰撞檢測模塊提供的，而物體包圍盒是很成熟的技術，可以很方便的在主流硬件上實現，所以本方法也能滿足MMOG中存在玩家機器異構的特點的要求。

綜上所述，使用包圍盒輔助的軟陰影算法可以有效地完成動態場景軟陰影的快速渲染，很好的處理游戲中出現的絕大多數遮光物體軟陰影的繪制。下一步的研究重點是在形狀動態變化的區域光源下(如火焰、閃電等)，遮光物體的軟陰影繪制技術。

參考文獻:

[1] Assarsson U， Akenine Moller. A Geometry-Based Soft Shadow Volume Algorithm Using Graphics Hardware[A]. Proceedings of ACM Trans. Graph[C]. 2003，22， 3， 511-520.

[2] Williams. Casting Curved Shadows on Curved Surfaces Computer Graphics[A]. Proceedings of SIGGRAPH'78 (August)[C].270-274.

[3] Soler C， Sillion F. Fast Calculation of Soft Shadow Textures Using Convolution [A]. Proceedings of SIGGRAPH'98[C]. 1998，321-332.

[4] Donnelly W， Lauritzen. Variance Shadow Maps[A]. Proceedings of SI3D'06[C]. 2006，161-165.