浅谈 potentially visible set (PVS) in Quake

现在一般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。

然后我们可以用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%以上的时间是可以关闭网卡的。