Real-Rime Rendering (7) -加速算法（Acceleration Algorithm）

提要

         計算機的性能一直是大家關心的，即使在一個相對簡單應用中，比如一個打字應用，如果有剩余的性能可以榨取，我們都可以用它來增加新的特性，比如聯想拼寫，語法檢查，抗日鋸齒文字顯示，語音識別輸入等等。

       在實時渲染中沒我們至少有四個表現上可以去追求的目標：提高幀率，提高渲染的分辨率，實現更加真實的光照和材質，實現更多的細節。60-85的FPS算是夠快了。

        一些 imge processing 如抗鋸齒和motion blur 會明顯消耗大量的cpu性能，降低FPS，這種情況下，添加一些加速渲染算法是非常必須的。

空間數據結構   Spatial Data Structures

        空間數據結構指的是將圖形數據存放在n維數組中，其中 n >= 2. 組織空間數據結構通常是層級的(hierarchy)，這意味著它是層級包含的，這樣，空間的物體都集合在一起了，并且是遞歸的，用層級的原因是這對訪問速度的提升很有幫助，可以從o(n)提升到0(logn).但這種結構通常是precomputed的，初始化和修改都會很費勁。

        下面是幾種常見的空間數據結構，包括：

  BVH(bounding volume hierarchies),BSP(binary space partitioning tree),octrees.

BVH

      一個BV是包含一系列物體的volume，而這個volume是一個相對簡單的物體，比如sphere，box等，這樣在進行一些檢測的時候用BV就會快很多。、

      一個BV對渲染上的幫助并不是直接的，它像一個它所包含的物體的代理，用于物體拾取，碰撞檢測中。

      對于3D real time rendering，BVH通常用于的階段是視井剔除（Frustum culling）。場景用一樹狀結構組織，有根，葉子等等。葉子節點就是場景中的物體，沒有有子孫。中間節點包含物體，樹中除葉子節點外的結點都對應于一個bounding volume，所以叫BVH。root節點包含整個場景。

      BVHs字啊查詢中也很好使，例如在Ray tracing算法中，光線和場景中物體求交，假如沒有BVH，則光線每次都要判斷是否與場景中的每個物體相交，使用BVH的話，只有在光線和BV相交的情況下才會進一步對子物體（包含BV）進行求交，而光線與正方體、球體求交的方法會很簡單，這也是BV使用Sphere和Box的原因。

      BVHs也能用于動態場景中，當場景中的一個物體移動了，檢測它是否還在BV中，若還在，則不作任何改變，若物體不完全包含在原BV中 了，則要對父級BV進行哦那個重新計算，這種做法可能會進行遞歸運算，耗費時間，或者把樹變得不平衡，一種方法就是將BV完全包含物體的運動軌跡，比如一個單擺就很好處理，這種方法稱為 temporal bounding volume.

BSP Trees

　　BSP （Binary Space Partition）表示二叉空間分割。使用這種方法可以使我們在運行時使用一個預先計算好的樹來得到多邊形從后向前的列表。

    一個BSP Trees如同它的名字一樣是一個層次樹的結構，這個樹的葉節點保存了分割室內空間所得到的圖元集合。現在隨著硬件加速Z緩沖的出現，我們只需要用很小的代價就可以對空間中的圖元進行排序，但是在90年代初由于硬件的限制，使用BSP的主要原因是因為它可以對空間中的圖元進行排序來保證渲染圖元的順序是按照由后至前進行的，換句話說，Z值最小的物體總是最后被渲染。當然還有其他的算法可以完成這個功能，例如著名的畫家算法，但是它與BSP比較起來速度太慢了，這是因為BSP通常對圖元排序是預先計算好的而不是在運行時進行計算。從某種意義上說BSP技術實際上是畫家算法的擴展，正如同BSP技術的原始設計一樣，畫家算法也是使用由后至前的順序對場景中的物體進行渲染。但是畫家算法有以下的缺點：
l 如果一個物體從另一個物體中穿過時它不能被正確的渲染；
l 在每一幀對被渲染的物體進行排序是非常困難的，同時運算的代價非常大；
l 它無法管理循環覆蓋的情況，如圖所示

        根據切分方法的不同，BSP樹會分為對齊軸 (Axis