最近阅读了《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)因此，整个渲染步骤，其实是先标记出所有会被渲染的节点，然后从根节点递归的按序渲染所有可渲染的子节点的过程。

今天就先写到这里吧。
没想到写东西其实挺累的。