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

首先是GENERAL PROGRAMMING SECTION。

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

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

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

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

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

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

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