随笔 - 119  文章 - 290  trackbacks - 0

博客搬家了哦,请移步
叫我abc

常用链接

留言簿(12)

随笔分类

我的博客

搜索

  •  

积分与排名

  • 积分 - 302138
  • 排名 - 84

最新评论

阅读排行榜

最近阅读了《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》读书笔记

FeedBack:
# re: 《GAME PROGRAMMING GEMS6》读书笔记-2 2009-03-30 16:32 饭中淹
用小方格子来拼成六边形,然后通过查表方式来进行坐标转换。
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理