avatar

Derek Zeng

A programmer

浅谈 potential visible set (PVS) in Quake

by coderek

现在一般3D或者2.5D的地图都会有一种划分地图的方式,比如说魔兽地图是将地图划分成小的方块,雷神之锤的用立体的凸面体来划分。这样的做法是整个地图能够更好的被掌控,不然按照一个个多边形划分的话,不仅数量巨大难以掌控,更对电脑性能是一大挑战。

John Carmack在雷神之锤里使用二叉树(BSP)来分割空间。在中间节点里储存分割面,枝头储存空间信息,我们称它为Area。这样搜索地图里一个坐标的Area的位置就非常方便了,只要从树根出发,确定坐标在分割面的那一边,然后到那一边的节点做相同的对比,直到枝头就可以了。自然而然的,Area的连接信息也可以很容易的得到。先找到Area的分割面的节点,然后再找到面的另一边Area。当然这些都是比较费时间的,所以只能在线下处理。而且这些信息都是静止的,所以得到的数据都是不会因为游戏的进行而改变的。

那么计算这些东西有什么用呢?答案是Potential Visible Set,潜在可视集合。这是一个非常有用的东西。它的具体原理很简单,就是为每一个Area计算其他每一个Area的可见度。所以当视角在一个Area的的时候,我们就可以知道周围哪些Area是看得见的了。但这里所谓的PVS是脱离视角的,它只跟Area有关。所以,一个玩家周围360度的Area都可以是在PVS里面。这个东西配合view frustum culling, back surface culling, 和 z-filling/buffering就有完美的quake engine。当年John Carmack绞尽脑汁才想到用这种方法预先计算需要渲染的图像,以达到游戏可运行的帧数。

计算PVS还需要知道Area的虚切面,也就是Area的一个并不存在于多边形集合里的切面。我们叫它Portal。Portal是从一个Area到另一个Area的必经之路,所以要计算从一个Area能不能看到另一Area就要检查它们之间有没有一条直线经过的面都是Portal。 这是我们还需要一个Adjacency Graph 来方便的得到连续的Portal。

stabbing_line

然后我们可以用Depth First Search来进行Stabbing Line Checking。这个在3D里面是一个比较难的问题。 就像上面那个图,在三维空间里给你一连串的多边形,你需要判断是否有一天直线贯穿所有多边形。这个问题据说要用pluker coordinates来解决,但现在我还无法理解,等我理解了在写一篇解释一下吧。

一旦这个问题解决了,PVS就可以得到了。由于Area的数量比较多,PVS是Area数量的平方,所以必须compress 才能在游戏中使用。这里John Carmack用的是bit来表示可见度,然后使用run-length encoding。本来20多兆的数据,只剩下20多K。

在Seth Teller 92年的论文里有更详尽的解释,事实上他的algorithm精确到一个像素,所以不会有像素覆盖的现象。

除了在图像渲染方面的应用之外,PVS也可以用做手机游戏能量节省的算法。他的精确度相当高,所以,在一个密度不是很大的游戏里面,玩家有50%以上的时间是可以关闭网卡的。

(End of article)