第三節?室內場景中光照運算

關于Radiosity的算法最早是由Goral、Cindy?M、Torrance、Kenneth?E、Greenberg、Donald?P、Battaile和Bennett在論文《Modelling?the?interaction?of?light?between?diffuse?surfaces》提出的。他們使用Radiosity來模擬能量在漫反射表面之間進行傳送，漫反射表面對照到表面上的光線在所有的方向上都進行相同的反射，和它相反的是鏡面反射表面，它只在反射方向上傳播反射光。由于漫反射表面的這個特性，這就意味著對于所有的觀察角度而言看起來表面都是相同的，這樣對于場景中的每一個表面只需要進行一次光照運算，而且可以在場景的預渲染時進行，因此這項技術被大量的3D游戲所采用。
下面我再簡短的講解一下Radiosity是如何工作的，而將主要的精力放在如何使用BSP樹來加速Radiosity的計算，對于Radiosity的詳細介紹請參考前面的章節。Radiosity技術是設計用來使場景中光照看起來更加真實和光滑，如果我們使用一個一直向前傳播而不考慮反射的光照模型，那么當場景中的燈光照亮場景中的物體時，并不會計算遠處經過反射過來的光線，這樣場景中的陰影看起來非常尖銳而物體表面也看起來非常不真實。為了使用radiosity技術我們需要把場景分割成一塊一塊很小的部分，每一部分我們稱它為patch，每一個patch都有一個初始化的能量級別，如果它不是一個燈光這樣的發光體的話通常為0，有許多方法來分配場景中的能量，這里我們將要使用的方法稱為交互式radiosity。這個方法的過程是我們從場景中未發送能量的級別最高的patch開始發送能量，能量經過傳遞后將不再發送能量的patch的等級設為0，重復這個過程直到場景中的每一個patch的能量等級都小于一個預定值為止。
當能量從一個patch（j）開始發送到另一個patch（i）時我們使用下面的公式：
Bi?=?Bi?+?Bj?*?Fij?*?Ai?/?Aj
這里Bi?=?patch（i）的能量級別?????Bj?=?patch（j）的能量級別?
????Ai=?patch（i）的作用區域????Aj?=?patch（j）的作用區域
????Fij?=?patch（i）與patch（j）之間的系數
在公式中系數Fij是由以下公式來確定的：
Fij?=?(cos?qi?*?cos?qj)?/?d2?*?Hij
這里Fij?=?patch（i）與patch（j）之間的系數
qi?=?patch（i）與patch（j）法線之間的夾角
qj?=?patch（i）與patch（j）法線之間的夾角
d?=?patch（i）與patch（j）之間的距離
Hij?=?patch（i）與patch（j）之間的可見性系數。如果在兩個patch之間只有一條光線可以跟蹤，這個值為1，如果沒有光線可以跟蹤為0。一般情況下由于每一個patch都不是一個點而是一個區域，因此光線有很多條。
從上面的公式中我們可以看到在場景中進行radiosity計算是非常耗費時間的。這個函數的復雜度為O(n3)，這里的n為場景中patch的數量。由于對于場景中每一個patch你需要發送最少一條光線到其它patch上，因此需要對場景中的幾乎所有的多邊形都進行光線跟蹤計算。在上面的公式中系數H的計算非常耗費時間，下面我們將看一下如何在BSP樹中對它的計算進行優化。?

????BSP樹中的radiosity計算
在進行場景中的光照計算之前需要把場景中的面分割為patch，一個方法是在開始的時候設定每一個patch為預定的大小，當計算每一個patch的能量時，如果在patch上的能量足夠大，對這個patch進行分割。不過這個方法是非常耗費時間的，因此必須尋找一個更好的方法來通過BSP樹對計算進行優化。
在radiosity的一般算法中場景中的每一個光源都被看作為一個或多個patch，這里我們可以改進一下，將每一個光源放在它所位于的葉節點中，接下來每一個光源都發送自己的能量到場景中所有的patch上，當這個過程完成后radiosity計算也就結束了。為了使最后的結果看起來更好可以使用一種稱為“漸進精選”（progressive?refinement）的技術來對這個方法進行很小的修改。在每一次過程中，葉節點中具有高能量的patch將發送能量到其它低能量的patch上，這樣做的結果是高亮度的patch將發送能量到處于陰影中patch上。這是因為在實際生活中并沒有真正黑暗的地方，它多多少少要獲得一些其它物體反射過來的光亮。
由于計算非常耗費時間需要做一下優化，使用渲染BSP樹時獲得的PVS信息可以在選擇哪些patch將接受能量時剔除一些無用的計算。因為在計算PVS時使用了相同的方法來進行光線跟蹤。
通過場景來分配能量的算法如下：
l?函數RADIOSITY
l?參數：
l?Tree?–?進行radiosity計算的BSP樹。
l?返回值：
l?None
l?功能：
l?在場景中的patch之間發送能量。
RADIOSITY?(Tree)
1?for(each?leaf?L?in?Tree)
2?for(each?light?S?in?L)
3?for(each?leaf?V?that?is?in?L’s?PVS)
4?Send?S’s?energy?to?the?patches?in?V
l?下面語句5是為了讓地圖編輯者在任何時候都可以檢查場景渲染的效果，如果他感到看起來已經足夠好了可以中斷能量的傳播。
5?while(not?looks?good?enough)
6?for(each?leaf?L?in?Tree)
7?for(each?leaf?V?that?is?in?L’s?PVS)
8?Send?energy?from?the?patch?with?the?most?unsent?energy?in?L
to?all?patches?in?V.

復雜度分析
這個函數的運算費用實在是太高昂了，可以稱為時間殺手，在最壞的情況下每一條光線將不得不檢測場景中的每一個多邊形，此時復雜度為O(n3)，這里n為樹中patch的數量。一般情況下由于進行了優化可以減少大量的計算，但是減少多少并不能計算出來，因為這依賴于樹結構的復雜度。
上面的函數給出了一個充分利用BSP樹的優點來加速場景光照運算的方法，尤其是可以顯著的減少光線跟蹤的計算量，而且地圖設計者可以來決定當場景渲染時如果渲染的效果可以接受中斷渲染循環。這對地圖的預渲染實在是太方便了，運行的時間可以根據渲染的效果來決定。

第四節?BSP樹的預渲染
現在我們需要完成一個完整BSP引擎的預處理過程，下面的算法顯示如何將場景渲染到BSP樹中。
l?函數RENDER-SCENE
l?參數：
l?Scene?–?被渲染的場景
l?返回值：
l?一個BSP樹。
l?功能
l?預渲染來獲得一個包含場景信息的BSP樹。

RENDER-SCENE?(Scene)
l?使用描述場景中圖元的物體來渲染BSP樹。
1?GeometryPolygons?=?{}
2?for?(每一個包含場景圖元的物體object?O)
3?GeometryPolygons?=?GeometryPolygons?U?O.PolygonSet
4?GENERATE-BSP-TREE?(Tree.RootNode,?GeometryPolygons)
l?分配葉節點上的取樣點。
5?DISTRIBUTE-SAMPLE-POINTS?(Tree.RootNode,?{})
6?TRACE-VISIBILITY?(Tree)
7?for?每一個場景中的靜態物體object?O
8?for?物體O中每一個多邊形P
9?PUSH-POLYGON?(Node,?P)
l?函數CREATE-PATCHES是一個未定義的函數，由于我們的解決方案效率并不是太好，因此沒有對它進行詳細的介紹。
10?CREATE-PATCHES?(Tree)
11?RADIOSITY?(Tree)

????復雜度分析
函數的復雜度如下：
函數?最壞情況?一般情況?描述
GENERATE-BSP-TREE?O(n2?lg?n)?O(n2)?n為場景中多邊形的數量
DISTRIBUTE-SAMPLE-POINTS?Q?(np?+?xy)?Q?(np?+?xy)?n為樹中多邊形的數量，p為樹中典型點的數量，x和y為分割面的寬度和高度。
TRACE-VISIBILITY?O(n2)?O(n?lg?n),?n為樹中多邊形的數量。
RADIOSITY?O(n3)?O(n2?lg?n)?n為樹中patch的數量

在一般情況這一列中顯示了算法通常所需運行的時間，對算法時間影響最大的是函數RADIOSITY，它使整個算法的復雜度趨向于O(n3)。

總結

以上是生活随笔為你收集整理的BSP技术详解3---有图有真相的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。