最近閱讀了《GAME PROGRAMMING GEMS6》，頗有收獲，以筆記之。

首先是GENERAL PROGRAMMING SECTION。

1.4Geographic Grid Registration of Game Objects
這篇文章講述的內容主要是用來解決Line-of-Sight（在公司里稱視野表）問題的。原理很簡單，而且在公司內也很普遍了，就簡單的說了。
游戲中有大量的角色，這些角色分布在各處，不斷的移動，每個角色都需要考慮它能看到誰，應該和誰交互，這就是視野表問題。
在沒有任何數據結構的支持下，建立每個對象的視野表需要對所有其他對象進行檢測，因此有N個對象的話，程序復雜度就是O(n^2)。
Geographic Grid是一個正方形。將一個場景劃分出一組grid，每個對象除了自身坐標外，還需要一個grid坐標，并將自己注冊到那個grid上。當對象移動后，需要從原來的grid中刪除，并注冊到新的grid下。
每個對象的視野表，簡單的實現下，也就是周圍9個或25個grid中包含的對象。
在文章里，grid是正方形，一個同事提出了六邊形的想法，六邊形一個最出色的地方就是到各個方向的距離相等。不過比較不好的地方就是grid坐標是非齊次的，并且是3元的，使用起來要轉換，并且挑戰人類本能上熟悉的2元齊次坐標系。

1.5BSP Techniques
把BSP技術放在通用編程這章，看來在quake出現后，BSP已經是一種通用技術了。
文章里介紹了使用BSP的的幾個方面，我會逐一介紹。

(a)Convex Leafy BSP-分割場景
關鍵字是凸包（凸面體）。這種分割方式，要求每個BSP-Node的front-node如果是葉子的話，那么就必須是凸包。
算法過程如下：
(1)從輸入的所有多邊形中挑出一個分割平面，將構造分割平面的多邊形添加到front-list中
(2)根據多邊形和分割平面的前后位置關系，將所有多邊形分別添加到front-list和back-list中。
(3)和分割平面攪和在一起的多邊形，進行split，并將拆分的兩部分分別添加到front-list和back-list中
(4)如果front-list中的所有多邊形構成一個凸包的話，那么front-list中的所有多邊形將添加到當前節點的front-node中，并作為一個葉子節點存在，不在繼續分割。
(5)不滿足上一條件的front-list和back-list（無條件），繼續遞歸的重復這個算法過程。也就是說，如果是front葉子，必然是凸包，否則就只能是中間節點，而back葉子就是solid（書上這么說的，但是不能很好的翻譯出solid的意思）

(b)Convex,Leafy BSP Portal Generation
這里簡單說明了如何自動生成portal：
(1)對每兩片葉子，當然是指凸包的葉子，判斷葉子之間是否相交
(2)如果兩片葉子相交，則找到兩片葉子的第一個共同父節點，此父節點的分割平面就是未經裁剪的portal。
(3)這里不得不說說找兩個節點的共同父節點的算法，因為書里沒提，我也沒想出來，后來問了一個同事，才知道可以根據節點的層次信息向上遞推出結果。
(4)最后，就是計算原始的portal和兩個葉子節點的交集，這個交集也就是最小的portal了。

(c)Convex,Leafy BSP Potentially Visible Sets
生成PVS的第一步是復制portal，接下來是計算兩兩portal之間是否可見，如果可見則意味著從一個portal可以看到另一portal相關聯的葉子。
至于如何判斷兩兩portal之間是否可見，無非就是射線檢測法之類的。
每個葉子都有一個pvs數組，用來標記是否可以看到其他葉子，每個葉子根據編號占據其中1bit。怎么算編號在bit中的位置不用教了吧，一除一模，像quake那樣優化的話，也就是
pvs[ i >> 3 ] & ( 1 << (i&7) )

(d)Render
(1)首先是計算camera當前所在的葉子，如果不是上次camera所在的葉子，則需要更新能渲染到的節點。更新步驟如下：
(2)將渲染幀數值+1，然后對每一個當前葉子能看到其他葉子（用PVS數組判斷），將渲染幀數值設置到每一個可以看見的葉子節點和其所有父節點上，最后才開始執行渲染。
(3)渲染從根節點開始，渲染每個幀值等于系統渲染幀值的節點（當然，少不了可視檢查了）。
(4)如果camera在節點分割平面前，則先渲染front-node，然后渲染back-node，否則反之。
(5)因此，整個渲染步驟，其實是先標記出所有會被渲染的節點，然后從根節點遞歸的按序渲染所有可渲染的子節點的過程。

今天就先寫到這里吧。
沒想到寫東西其實挺累的。