轉記：找了不少關于shadow volume原理的資料，還是這個帖子講解的一目了然，轉帖在這里，方便查閱。
引用鏈接：http://blog.donews.com/yyh/archive/2005/05/19/387143.aspx
陰影錐(shadow volume)原理與展望---真實的游戲效果的實現
作者：王浩
前言：真實的游戲效果
shadow volume 這個術語幾乎是隨著 DOOM3 的發布而成為FPS 玩家和圖形學愛好者談論的對象的。雖然這個游戲還沒有上市，但是憑借 John Carmack 的傳奇經歷以及 DOOM3發布的一些讓人驚訝的預覽圖片，我們仍然有理由認為它將會是 2004 年最熱門的 FPS 游戲之一。 id software向來都不吝惜為了達到最好的圖像效果而使用最先進的渲染技術 ,這曾經使得玩家為了玩它開發的游戲而不得不掏光口袋里面的錢來升級電腦，不知道這次我們可以幸免嗎？
自 DX9 發布以來，大家的注意力似乎都被 shader 吸引住了， BBS里面談論的話題也總是離不開 shader based rendering ，前一段時間關于 GPU內部精度的討論大有遮天蔽日之感，但其實和閃閃發光的金屬小球以及波光鱗鱗的水面比較，幾個簡簡單單的影子常常能帶給場景更多的真實感。也許這就是為什么DOOM3 能夠在多如牛毛的 FPS 游戲中脫穎而出的原因之一。
陰影的實現方法有很多種，現在比較流行的主要是 shadow mapping 和shadow volume. 前者實現起來相對簡單，可以發揮現在 GPU 可編程流水線的能力，但是由于先天不足，shadow mapping在處理動態光源/物體的時候開銷過大，經常作為一種靜態場景中的廉價替代物。而 Shadow volume 的強項恰恰是 shadowmapping 的短處，像 DOOM3 這種大量運用動態光源，并且要對時刻都在運動中的物體投射陰影，shadow volume是現階段唯一的選擇。
| Shadow mapping 的原理：
一個物體之所以會處在陰影當中，是由于在它和光源之間存在著遮蔽物，或者說遮蔽物離光源的距離比物體要近，這就是 shadow mapping 算法的基本原理。
Pass1: 以光源為視點，或者說在光源坐標系下面對整個場景進行渲染，目的是要得到一副所有物體相對于光源的 depth map （也就是我們所說的shadow map ） , 也就是這副圖像中每個象素的值代表著場景里面離光源最近的 fragment 的深度值。由于這個 pass中我們感興趣的只是象素的深度值，所以可以把所有的光照計算關掉，打開 z-test 和 z-write 的 render state 。
Pass2: 將視點恢復到原來的正常位置，渲染整個場景，對每個象素計算它和光源的距離，然后將這個值和 depth map中相應的值比較，以確定這個象素點是否處在陰影當中。然后根據比較的結果，對 shadowed fragment 和 lightedfragment 分別進行不同的光照計算，這樣就可以得到陰影的效果了。
|
從上面的分析可以看出來，depth map的渲染只和光源的位置以及場景中物體的位置有關，無論視點怎么運動，只要光源和物體的相互位置關系不變，shadow map就可以被重復使用，因此對于沒有動態光源的場景， shadow mapping 是很明智的一種選擇。
除了上面提到的不能很好應付動態光源場景的限制之外，shadow mapping 還存在著所有使用 texture的場景面臨的共同問題－鋸齒。根據采樣定理，只有紋理分辨率小于或者等于物體的實際分辨率時才不會失真，而當一副很大的紋理被貼到尺寸比它小的物體上時，會出現一個 fragment 覆蓋多個 texel 的情況，這時要準確的再現這個 fragment 的顏色信息，就要綜合考慮所有被它覆蓋的texel 產生的影響，這就是各種紋理濾波方法最基本的原理。但是由于 depth map 是在不斷的變化當中，所以不能像一般的紋理那樣把各個mip -map 事先計算好放到顯存里面。有一種利用 pixel shader 的方法對 depth map 做 bilinearfiltering, 但是開銷很大，在現階段不具備實用意義。同樣的問題在紋理分辨率小于屏幕分辨率的時候仍然存在，這時多個 fragment會被投射到同一個 texel 上面，雖然從再現紋理的角度來說并不存在失真，但是由于多個 fragment共用同一個紋理值，鋸齒問題還是存在。更糟糕的是，沒有一種濾波技術可以從根本上解決這樣的鋸齒，因為從數學上講，人們不可能通過運算來創造出比原始量更多 的信息。近年來，為了解決 shadow mapping 的鋸齒問題，人們做了很多努力，比較有前景的是 adaptive shadowmap(ASM) 和 perspective shadow map(PSM) 。兩者的基本原理都是在可能產生鋸齒的地方人為增加采樣率，使得一個fragment 至少對應一個 texel , 區別是 ASM 增加采樣率的地方是在 shadow 邊緣，而 PSM是在靠近視點的地方。修補一個本身存在缺陷的方法從數學上來說是缺乏美感的，正像 John Carmack 在 2002年8月的一封 email中所說：
“ Shadow buffers makegood looking demos with controlled circumstances, but when you startusing them for a “real” application, you find that you need absolutelymassive resolution to get acceptable results for omni － directionallights, and a lot of the artifacts need to be tweaked on a per-lightbasis. While it is possible to do shadow buffers on GF1/radeon classhardware, without percentage closer filtering they look wretched. If wewere targeting only the newest hardware, shadow buffers would have abetter shot, but even then, they have more drawbacks than are commonlyappreciated. ”
看起來似乎 John Carmack 找到了實現陰影更好的方法？讓我們來看看它究竟是什么。
Shadow volume 的原理：
Shadow volume 這種算法第一次被提出是在Franklin C. Crow 在 1977 年寫的一篇論文 “SHADOW ALGORITHMS FOR COMPUTERGRAPHICS ”里。其基本原理是根據光源和遮蔽物的位置關系計算出場景中會產生陰影的區域（ shadow volume），然后對所有物體進行檢測，以確定其會不會受陰影的影響。
圖中的綠色物體就是所謂的遮蔽物，而灰色的區域就是 shadow volume。
只有處于 shadow volume 里面的物體才會受陰影的影響。
shadow volume的算法
現在清楚了 shadow volume 的基本原理，那么如何確定一個物體或者一個物體的某一部分處于 shadow volume 中呢？這就要用到 stencil buffer 的幫助了。
z-pass 算法：
z-pass 是 shadow volume 一開始的標準算法，用來確定某一個象素是否處于陰影當中。其原理是：
Pass1：eNABlez-buffer write ，渲染整個場景，得到關于所有物體的 depth map 。注意這里的 depth map 和 shadowmapping 里面的區別是 shadow volume 里面的 depth map 是以真實視點作為視點得到的，而 shadowmapping 里面的 depth map 是以光源為視點得到的。
Pass2：disable z-buffer write ， eNABlestencil buffer write, 然后渲染所有的 shadow volume 。對于 shadow volume 的 frontface( 既面對視點的這一面 ) ，如果 depth test 的結果是 pass, 那么和這個象素對應的 stencil 值加一。如果depth test 的結果是 fail, stencil 值不變。而對于 shadow volume 的 back face(遠離視點的一側 ) ，如果 depth test 的結果是 fail, stencil 值減一，否則保持不變。
用一句簡單的話來概括 z-pass的算法就是從視點向物體引一條視線，當這條射線進入 shadow volume 的時候， stencil 值加一，而當這條射線離開 shadowvolume 的時候，stencil 值減一。如果 stencil 值為零，則表示實現進入和離開 shadow volume的次數相等，自然就表示物體不在 shadow volume 內了。
Pass3：第二步完成以后，根據每個象素的 stencil 值判斷其是否處于陰影當中（如果 stencil 的值大于零，則這個象素在 shadow volume 內，否則在 shadow volume 的外面），然后據此繪制陰影效果。
在這副圖里面，視線三進三出 shadow volume, 最后的 stencil 值為零，表示物體在 shadow volume 外，不受陰影的影響。
這副圖里面視線三進一出， stencil 值為 2 ，表示物體在 shadow volume 內，有陰影產生。
這副圖里面從視點到物體的視線中止于 shadow volume 前，也就是說所有的 z-test 都是 fail, 相應的 stencil 值為零，表示物體在陰影外面。
z-pass 算法缺點及補救辦法
以上的討論都是基于視點在 shadow volume 外面的情況。在這個條件可以得到滿足的情況下，z-pass 算法工作的很好，不過一旦視點進入到了 shadow volume 里面，z-pass 算法就會立即失效。
這副圖里面的視線二進二出，按照 z-pass的算法，最后的 stencil 值為 0，表示物體在陰影外，可實際上物體是處于陰影內的。錯誤的原因就在于視點進入到陰影內，使得視線失去了一次進入 shadow volume的機會，讓原本應該是 1 的 stencil 值變成了 0 。
Z-Pass 這種錯誤的行為可以從下圖中看出 :
注意地下的影子
Z-Fail 算法：
Z-Fail 算法是 John Carmack，Bill Bilodeau 和 Mike Songy 各自獨立發明的，其目的就是解決視點進入 shadow volume 后 z-pass 算法失效的問題。
Pass1：eNABle z-write/z-test, 渲染整個場景，得到 depth map 。 ( 這一步和 z-pass 的完全一樣 )
Pass2：disable z-write, eNABlez-test/stencil-write 。渲染 shadow volume, 對于它的 back face ，如果 z-test 的結果是fail, stencil 值加一，如果 z-test 的結果是 pass, stencil 值不變。對于 front face, 如果z-test 的結果是 fail, stencil 值減 一 ，如果結果是 pass, stencil 值不變。
圖中所有的 shadow volume 都處在 z-pass 的位置，因此 stencil 值不會改變。
視點在 shadow volume 內也沒有問題，最后 stencil 的值是 2, 表示物體在陰影內。
上面那個 Z-Pass 無法處理的場景，用 Z-Fail 計算則可以得到正確的結果：
使用 z-Fail 算法的條件
Capping For Z-Fail
由于 Z-Fail 算法依靠計算 shadowvolume 不能通過 Z-test 的部分來確定 stencil buffer 的值，所以要求 shadow volume是閉合的。下面的那張圖里面紅色的實線表示 capping, 可以想象，假如不人為的添加 capping, 那么 shadow object1/2 的 stencil 值都會是 0 ，而實際上正確的 stencil 值應該是 1 ，因為它們都在陰影內。
Z-Pass 和近剪裁面的關系：
在 Z-PASS 算法中，當 shadowvolume 和視圖體 (view frustum) 發生剪切關系的時候，需要附加的 capping 才能保證最后的結果正確。因為經過view frustum 的剪裁作用以后，shadow volume 的一部分有可能變成敞開的，比如在圖中 additionalcapping 的位置，假如不人為的附加一部分多邊形，在渲染 shadow volume 的時候 stencil buffer 就不會發生+1 的操作 ( 因為這里沒有任何多邊形，自然也就不會和原來的 depth map 比較 ) ，最后的結果顯然是不對的。
如何建立 shadow volume?
shadow volume的建立是整個算法里面最重要的部分，在 GPU 出現以前， shadow volume 的建立都是基于 CPU 的。隨著 GPU應用的逐漸開展，人們又將 shadow volume 運算移植到了 GPU上，不過后面一種方法需要對物體的幾何數據進行預處理，下面就對兩種方法分別進行解釋：
CPU based method（基于CPU建立方法）：
想必熟悉 shadow volume 的朋友對silhouette edge 這個詞會很熟悉。它表示從光源的角度看物體所得到的輪廓線。 Shadow volume 就是由silhouette edge 擴展到一定距離以外或者無窮遠處得到的。 silhouette edge的確定方法有很多種，基本思想就是找出那些被朝向相反 ( 一個面向光源，另一個背向光源 ) 的兩個三角形 ( 相對于光源來說 )所共享的邊，因為只有這樣的邊會最終成為 silhouette edge ，其他的邊在光源看來都在物體投影的內部而不是邊緣。
這副圖是一個由 4 個三角形組成的多邊形，假設光源處在讀者頭部的位置，那么外圍的一圈實線就是所謂的 silhouette edge 。我們所要做的就是從原始數據里面將內部多余的 4 條邊 ( 虛線 ) 去掉。具體實現是這樣：
• 遍歷模型的所有三角形
• 計算 dot3( light_direction , triangle_normal ) 。用這個結果判斷三角形是面向光源 (dot3>0) 還是背向光源 (dot<0) 。
• 對于面向光源的三角形，將所有的三條邊壓入一個 棧 ，和里面的邊進行比較，如果發現重復的 (edge1 和 edge2) ，將這些邊刪除
• 檢測過所有三角形的 所有邊 以后， 棧 里面剩下的 邊就是 當前光源 / 物體位置下面的 silhouette edge.
• 根據光源方向 , 利用 CPU 或者 vertex shader 將這些 silhouette edge 投射出去形成 shadow volume.
值得一提的是，這種方法正是 DOOM3所采用的方案，但是其中有一個問題就是 silhouette edge是由光源和物體的相互位置確定的，也就是說這二者之間有一個的位置發生了變化， silhouette edge就要重新計算，更新的數據也要傳回顯卡才能渲染 shadow volume ，這對 CPU 的計算能力以及 AGP的帶寬不能不說是一個不小的考驗。
GPU based method（基于GPU建立方法）：
Vertex shader一出現人們就在思考能不能利用它來加速 shadow volume 的渲染速度。但即使是現在最先進的 vertex shader 3.0也不具備創建新的幾何物體的能力。簡單點說 vertex shader 只能接受一個頂點，修改這個頂點的屬性 ( 位置，顏色，紋理坐標，etc), 之后輸出這個頂點到光柵化部分，繼而進行 pixel shader 運算。碰到需要創建新頂點的地方，就只有依靠 CPU 直接操作vertex buffer 了。
另外一個方法就是事先把 shadow volume需要的空間留出來，然后再通過 vertex shader的運算使之外形達到我們需要的樣子。這就好比我要存儲一串數據，但又不很確定具體的規模是多大，只好事先分配一塊很大的區域，這樣不免會造成很大浪費，但也是不得以而為之。
由于物體上的每條邊都有可能成為 silhouetteedge ，所以我們需要事先插入 degenerate quad( 上圖的紅色三角形 ), 這些 quad的面積為零，不作任何變換的話是不可見的，不會造成視覺瑕疵。但是在需要的地方，可以把這些 quad 拉伸成為 shadow volume 的側壁。
顯然，插入冗余的頂點會造成極大的浪費。因為大部分的邊最終 并不會成為 silhouette edge ，也就是說插入的 degenerate quad是無用的。不過這樣做的好處是幾何數據只需要傳輸到顯卡一次，之后無論光源的位置在哪里，預處理過后的幾何體都可以用來生成 shadowvolume ，不像剛才解釋過的方法那樣一旦光源和物體的相對位置發生變化，就需要重新用 CPU 計算 silhouette edge，之后再把結果 傳送給顯卡。
實際編程的時候，可以做一下改進，由于平坦的表面是不會產生陰影的，所以在這些表面所包含的邊上就沒必要插入 degenerate quad。而且所有的預處理應該在軟件開發過程中完成，用戶啟動程序以后直接調用的就是插入過 quad 的模型，不需要 CPU 再進行計算。
|
建立/渲染 shadow volume 的 shader 代碼：
// c0 : Light position in object space
// c1 : 1, 1, 1, 0
// c2- c5 : Light * View * Proj = LightClip
// c6- c9 : WorldInvLight matrix
// c10 : Color for exposing the shadow volume
vs.2.0
mov oD0, c10 // 輸出特定的顏色使 shadow volume 可見
sub r1, v0, c0 // 光源方向
m4x4 r4, v0, c[6] // 將頂點變換到光源坐標系
nrm r1, r1 // 光源向量歸一化，這是為了 shadow volume 的各個邊一樣長
mov r10, c1
dp3 r10.w, v1, r1 //dp3 頂點法向量和光源向量，確定頂點的朝向
slt r10, c1.w, r10 // 根據 dp3 的結果設置 r10 寄存器的第四個單元
mul r4, r4, r10 // 設定 r4 的 w 位
m4x4 r5, r4, c[2] // 輸出頂點到 clip space
mov oPos , r5
|
Shadow volume 的算法優化（一）
Shadow volume 的基本算法講到這里就基本完成了，下面說一下現在比較常用的一些優化算法。
（一）Z-Pass .VS. Z-Fail
前面提到過，Z-Pass 比 Z-Fail 速度要快，因此我們可以在不會產生問題的場合下適當使用 Z-Pass 來提高性能，但是如何確定何時 Z-Pass 不會帶來問題呢？ Z-Pass 失效主要是由于兩種原因 :
原因一：視點進入 shadow volume 內，比如下圖：
只要能探測出這兩種情況，就能在需要的時候切換到 Z-Fail 算法。條件 A 的判定可以參照下圖，在視點和光源之間做一條連線，如果這條線和遮蔽物相交，那么可以肯定視點在 shadow volume 內，將切換到 Z-Fail 算法。
原因二：shadow volume 與近 剪裁面 相交
至于情況 B 的判定可以利用光源和近 剪裁面 形成的light-pyramid( 紅色陰影部分 ) 與遮蔽物的交匯關系。如果遮蔽物完全在 light-pyramid 之外，則由它生成的shadow volume 不會和近 剪裁面 相交，可以使用 Z-Pass 算法，否則將只能使用 Z-Fail 算法。
Shadow volume 的算法優化（二）
（二）tricks to save fillrate :
前面提到過，shadow volume算法里面兩個最耗時的步驟就是 silhouette edge determination 和 shadow volume rendering。其中 shadow volume rendering 是完全考驗 GPU 填充率的步驟，雖然現在的顯卡動輒就有幾十 G fragment/s的填充率能力，但是遇到復雜的場景，流水線也不免不堪重負。此外，頻繁的 stencil buffer操作也會占據一部分顯存帶寬，如果能夠找出一些辦法盡量減小 shadow volume 的尺寸，將會是效果很明顯的一種優化方法：
限定光照的范圍（Attenuated Light Bounds）：
如果所用的光源有衰減效應，則可以利用 scissortest 將渲染的范圍限定在光源的作用范圍之內，因為超出了這個范圍就不會有陰影存在，自然用不著去渲染那部分的 shadow volume了。所謂 scissor test 就是人為地在屏幕坐標系下面定義一個矩形，只有坐標處在這個矩形范圍內的 fragment才能夠通過測試，其內容才能被寫入 幀 緩存。
NVIDIA的陰影加速技術（ultra shadow）：
ultra shadow這項技術是隨著NV35 的發布而浮出水面的，進而在 NV36/38 中得到了繼承，我們基本上可以在 NVIDIA 今后的產品中，這項技術會得到持續的應用。
id software 的當家程序員 JohnCarmack 曾經說過 NV35 是為 DOOM3 量身打造的 GPU ，我們在這里有理由懷疑 Carmack說這番話的原因很有可能就是由于 NV35 中集成了 ultra shadow 陰影加速技術（近日GeForceFX系列已經成為DOOM3的推薦GPU），那么 ultra shadow 究竟是什么，它如何加速陰影的渲染速度呢？
其實 ultra shadow 技術僅僅利用了一個 NVIDIA 新近提交的 OpenGL 擴展—— EXT_depth_bounds_test，我們先來看一下 NVIDIA 官方在 GDC2003 上對這個擴展的介紹：
首先注意一下名稱的問題，GDC2003在三月舉行，那時這個擴展還只是 NVIDIA 獨家的東西，到了 4 月這個擴展更名為 EXT_depth_bounds_test 。 EXT開頭的擴展表示有多家廠商在開發這項技術，也許不久以后我們就會看到 ultra shadow 在 ATI 的 GPU 上面實現。
Depth bounds test 的作用是比較由當前 fragment 的屏幕坐標（ xw ， yw ）指定的 depth buffer 中的 z 值與用戶通過 glDepthBoundsNV（GLclampd zmin , GLclampd zmax )所指定的 [ zmin,zmax ], 如果 z 值在次范圍之外，則將當前的 fragment 從流水線中剔除掉，不進行此處的 stencilbuffer 操作。注意這里比較的并不是 fragment(shadow volume) 的 z 值，而是前一個 path 中已經渲染過的shadow receiver 的 z 值。具體情況請看下圖：
可以看到，由于 A 點的 z 值在 [ zmin,zmax ] 范圍之外，此點沒有可能被陰影遮住，因此 A1/A2 點處的 fragment 就可以被丟棄。而 B 點的 z 值在 [ zmin,zmax ] 之外，所以 B1 點處的 fragment 就必須進行 stencil buffer 操作。
（詳細的技術介紹請看：《NVIDIA的復仇計劃 GF FX 5900 Ultra》）
陰影渲染實現技術的展望
shadow volume是近階段實現統一光照模型比較好的一種技術，現在主要的問題是基于 CPU 的方法對處理器依賴比較重，在 AI/ 物理運算較多的場景中 CPU的運算能力可能不足，而基于 GPU 的方法效率太低，會產生大量的冗余頂點，其原因還是由于現在的 GPU( 包括即將發布的 NV40/R420)都不具備在芯片內部產生新頂點的能力。 Microsoft 意識到了這一點，在 DirectX Next的發展規劃中將這種能力列為了要實現的目標之一：
從更長遠的角度來說，基于真實物理模型的光照模型（比如spherical harmoniclighting、ray-tracing、radiosity）才是發展的方向，那時我們沒有必要設計單獨的算法來實現陰影，所有的光照/陰影效果都被包擴在了一個統一的光照模型之中，任何效果實現起來都是自然而然的，就像它們在真實世界中的情況一樣。當然，所有這些設想都要基于半導體生產技術的支持才行，我們在近期（5-10年）將不會看到它們在硬件上的實現。