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

首先是GENERAL PROGRAMMING SECTION。

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

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

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

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

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

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

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