Featured image of post 2016.02 遮挡剔除的低端解决方案

2016.02 遮挡剔除的低端解决方案

Views

这是今天在知乎上的一个回答,原题如下:

问题:求问有哪些合用的遮挡剔除技术?

问题补充:

我们的flash3d的fps游戏 面向的受众 机器性能差的占不少,很多都是很低端的集成显卡。像素填充率很低。目前我们用的遮挡剔除技术是quake的bsp+portal。但是在一些没有明显房间分划的场景就显的几乎没什么用了。
求问 有什么合用的剔除技术适用于室外场景,没有明确房间概念 但是互相之间还是有遮挡关系的
另外umbra3d所用的技术都是公开的么? 如果我要能做到它的程度 有哪些paper可以参考。因为umbra3d没有针对flash的sdk.所以买了也没法用上
另外我对这个领域的知识是很碎片化的 请高手推荐些paper或者书籍能让我对这个领域有些系统的认识 知道哪些问题可以解决 而哪些问题其实目前还解决不了

以下部分是我的答案:


@庞巍伟的方案是比较流行的思路,不过感觉用在题主提到的低端集成显卡上,可能会有些限制。这里我先补充一些实时OC的思路和实践,然后再针对题主这种情况提个离线的方案,看起来可能 low 一点,仅供参考。


先说明一下,遮挡剔除 (Occlusion Culling) 本质上是这样一个过程——消耗一小部分 CPU 来去掉不可见的物体,不改变最终渲染的画面的同时,降低 GPU 的负载。

实时的 OC 已经有题主提到的 umbra 方案,背后的原理是 dPVS (Wikipedia) 以及早先的 PVS (Wikipedia)。这两个页面上有非常简略的介绍,可以作为起点看一下,然而年久失修,上面不少链接已经 404 了。

其中的一篇原理

虽然早了一些 (Oct2000),但内容比较详实,是很好的参考。

此文的作者是 Timo Aila 博士,主页在这里,上面的文章是他的硕士论文,他的博士论文

和这一篇讲 dPVS 的论文

也可供参考。


下面是一些游戏里的具体实践,其中不少思路与上面是一脉相承的:


还有一些补充的材料,可以顺带参考一下:


嗯,列了一堆材料,现在简单说一下我开头提到的离线方案。

简单说,离线方案就是预先在开发阶段生成好所谓的“潜在可见物体集(PVS)”,存下来,消耗一点存储空间,运行时只用付出查表的开销。最大的好处是运行时性能损失几乎为零,是典型的空间换时间。

题主提到 bsp+portal 在没有明显房间分划的场景(室外场景)几乎没什么用,那么室外怎么处理呢?一个土一点的办法,就是空间上划分为较小的子区域,每个子区域生成一个可见列表,只要摄像机位于该区域内,就激活该列表,每帧查表,凡是不在此列表中的就被剔除。

这些区域可以用一个简单的二维数组(棋盘格状),也可以用某种层次树结构(复用你的场景树)去组织。

边界附近怎么办?同时激活两边区域的可见列表就好了。


你可能已经看出来了,这是一个__较保守__的策略,列表容易变得臃肿——只要在该区域内曾被看到过,就会出现在列表里。嗯,没错,保守程度取决于区域划分的大小和场景的布局。但请注意,室外场景的特点是:区域内临近的点往往有很强的空间上的相关性 (spatial coherence) 也就是说,在划分得当的情况下,较大的 occluder 将足够产生较好的遮挡效果。举个例子,山脚下有个小镇,如果小镇本身是一个划定区域,那么这座山所挡住的绝大部分物体对小镇中的任一点均有效。

咱们__抓大放小__,对低端机器只用追求性价比就可以了,追求极致的完全精确的 100% 不可见剔除意义并不大。


空间开销上,通常一个场景内的对象数量在 65535 以内,可以用一个 ushort,假设一张地图的区域数量在 30~50 个,每个区域可见对象在1k~3k之间,那么每张地图所费磁盘尺寸在60k~300k左右,压缩一下到100k以内问题不大。顺便说一句,可以分块压缩,运行时只展开玩家附近的即可,不用全部展开在内存里,这样内存开销可忽略不计。

接下来说一下怎么生成这个对象列表。两种方式,一种是从摄像机所在点发出全视角的射线,凡是 trace 到的对象皆认为可见;另一种是单色渲染到纹理,然后看实际渲染结果是否包含特定颜色来确认对应的物体是否在 framebuffer 可见。摄像机使用某种算法(如 flood-fill)来确保该区域内所有位置都包含在内。

最后说一下透明物体的处理,很显然透明物体是不能做 occluder 只能做 occludee 的,那么分两个阶段把透明物体单独提出来判断即可。

总得来说,这个方案最大的特点是——运行期没啥开销,代码逻辑也足够简单——简单到你会觉得太 low 以至于不好意思在项目里用——在这个讲究逼格的年代,用了都不好意思跟人家说自己是这么干的^_^


嗯,大致如此。今天是农历传统的小年(腊月二十三),跟父亲喝了些酒,写得有点凌乱,见谅。

  • 本文在知乎上的回答页面在这里
  • [2016-02-05] 修复 “Culling the Battlefield” 的失效链接

(全文完)


comments powered by Disqus
Built with Hugo