最近阅读了《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)因此,整个渲染步骤,其实是先标记出所有会被渲染的节点,然后从根节点递归的按序渲染所有可渲染的子节点的过程。
今天就先写到这里吧。
没想到写东西其实挺累的。
posted on 2007-11-24 21:57
LOGOS 阅读(1573)
评论(1) 编辑 收藏 引用 所属分类:
《GAME PROGRAMMING GEMS6》读书笔记