Home > 程序/算法 > 基于patch的地形PVS数据预处理(上)

基于patch的地形PVS数据预处理(上)

PVS:Potentially Visible Set(潜在可见集)的缩写,方便起见以下可能会用小写

这里说的不是传统意义上的室内基于portal的pvs,而是存储室外地形块相互可见性的一张二维表,也许叫pvs不太准确但我不知道该叫什么。我们的地形目前是基于patch的,也就是如果1号patch看不到3号patch,那么pvsData[1][3] = false;反之就为true。当然这张表的每个元素只占用1个bit。

计算一下,数据量基本是可以接受的,例如内存中维护32 * 32 = 1024个patch,那么最终的数据量就是1024 * 1024 / 8 = 128k。如果每个patch要维护多个高度级别的pvs数据(也就是说摄像机处于不同高度时采用不同的pvs数据,这样更精确,效果更好),那么这个数字再乘以n,以当前pc的内存来说不会有什么问题。

但是预先生成这些数据却需要极大的计算量。粗略估计一下,这个问题的算法复杂度基本是O(n^6)!如果n代表地图的边长尺度的话。因为总共的patch数量是n^2的,而且要计算他们两两见的可见情况,n^4了,而计算是否可见时,又要考察其它所有patch是否成为中间的阻挡,于是就n^6了。当然,可以比较快的剔除不可能阻挡的patch,但至少也有n^5的复杂度。也就是说地图尺寸增大一倍,预处理pvs数据的开销就会是原来的32倍以上。

哦,好像还没有说为什么需要pvs剔除,这里插播一下。从两方面考虑:对于cpu来说,目前的地形是基于patch的LOD的,每帧需要动态生成vertex buffer和index buffer提交渲染(之前考虑过始终用一个静态VB,但是顶点太多,超过了一些比较老的显卡index值的64k上限),如果能抛弃大量的不可见顶点和三角形,能减轻不少CPU填充VB和IB的负担;从GPU方面考虑,虽然顶点和三角形的数量一般不是问题(已经LOD过了),显卡的瓶颈一般都在象素处理上,如果所有地形patch没有按从近到远排序的话,象素的重复绘制将造成显卡工作量不小的浪费,如果对地表使用了象素shader那浪费就更大了;而如果对patch进行距离排序也会增加CPU的负担。这时候,对完全不可见patch的pvs剔除就显得价廉物美,因为只需要根据当前摄像机所在patch,在表里一查马上就可以扔掉数量相当可观的地形块。具体效果要看地形的起伏程度,起伏越大,剔除的效果就越好。最坏情况是面对一片一览无遗的平原,但是地势较平的话基于视差的LOD分级已经能十分有效的缩减顶点和三角形数量,而且对于显卡的象素处理也基本没有浪费。另一种情况,如果摄像机的高度超出了patch的控制范围,那么pvs剔除也不能起作用了,这就是为什么需要前面说的每patch维护多高度级别的pvs数据。patch作为源patch时的高度最好要充分考虑到在正常游戏中摄像机可能达到的最大高度(主角千万不要跳太高啊!什么?还能飞!¥%※×◎……)

具体算法我大概是这么做的:比如要计算patchSrc是否能看到patchDest,注意patchSrc对patchDest的可见性不能反推patchDest到patchSrc的可见性,因为patch作为Src的包围合必须留有摄像机活动的空间(不能要求摄像机紧贴地面),而patch作为Dest的包围合只要精确的包围所有顶点即可。现在我们有src和dest两个包围盒,我取了从src的上表面4个角落以及中心到dest的上表面相应位置的5条射线,然后逐一判这5条射线是否和其它patch中的三角形有相交,如果5条全部都有相交(也就是说被遮挡),那就基本上可以判定从src到dest是不可见的。这样的算法是不精确的,因为只取了5条射线进行判定,实际上是存在无穷多条射线的,但为了效率考虑先这样了(虽然是预处理,但是别忘了是n^6的复杂度啊!)。实际上运行结果发现确实有不少错误,将来投入实用的话一定会提供手工修改pvs数据的方法的。对了解释一下为什么用包围合的上表面来判断,因为上表面是最不容易被遮挡的,如果上表面之间都不可见,那么整个patch肯定不可见了。另外一个细节是射线途中的patch需要提交它们所有的三角形参与与射线的相交判定(我用的是D3DXIntersectTri),如果觉得太慢,可以改为提交一定LOD级别下的三角形以节省计算量,代价仍然是:不精确。

最终的效率(还没有优化)是512的地图,边长16的patch(一共1024个patch),分两层。采用1级LOD(就是取一半的顶点组成三角形)进行射线相交判定,P4 2.53G CPU需要4.7小时。对比不同尺寸的地图的开销时间,大约地图增大一倍,开销就增大到48倍。

也可以考虑用GPU来计算可见性,比如每个patch设定一种唯一颜色,不要纹理,在一个特定摄像机位置对整个场景渲染一次(视锥如果不能涵盖所有patch就朝不同角度渲染多次),这样从结果表面含有哪些颜色就知道哪些patch是可见的了,可能比用CPU算要快而且精确一些。由于本人对D3D的接口还不是很熟,GPU处理的方案还没有实施。

在公司的机器上搞的,没法贴图片上来,各位见谅:)

Categories: 程序/算法 Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

 

Spam Protection by WP-SpamFree