先进的洞穴剔除算法第二部分:遍历可视联通图

译者：张乾光（星际迷航） 审校：崔国军（飞扬971）

原文地址：https://tomcc.github.io/2014/08/31/visibility-2.html

现在我们已经通过立方体块建立了一个可视连通图，我们需要找到一个方法来搜索哪些物体从玩家的角度看是实际上可见的！

也许有很多方法来使用我们现在所拥有的这个可视连通图，但是所有的这些方法都面临相同的性能/准确性方面的权衡。

你可以在这里找到文章的第一部分：《先进的洞穴剔除算法:如何让《我的世》界运行的更快》，地址是https://tomcc.github.io/2014/08/31/visibility-1.html。

光线投射（不，不是真的光线投射，只是打个比方）

如果我们的目的是得到最佳的精确度，最好的方法就是对截头锥体的每个组块的每一个角落进行光线投射。

我们之前计算得出的可视连通图对于投射光线帮助很大，因为我们可以很容易找到光线从哪个面进入/退出组块，然后利用我们的可视连通图的信息来继续投射或是停止。
但是，这种方法的速度可能不是很快-因为在最大的渲染距离上我们将会在玩家附近的区域加载几千个组块（在《我的世界》个人电脑版本的话，17，000个组块都是个常见的情况！）并且每个组块最多会需要7条投射线-即使我们使用最大的剔除比率，在一帧中运行119,000条投射线也没法让游戏的运行快起来，而且根本就没有办法对这种情况进行优化，所以我们需要一种更加聪明的办法，我们不能在一帧中执行这么多次投射测试。

广度优先的搜索方法

与预期的相反，我解决上面的问题是使用一个常规的广度优先搜索方法，只是在里面使用了一些小技巧。
如果组块是被存储在一个连续的三维网格中，访问时间是O(1)并且这种访问在实践中也是相当快的。除此之外，广度优先搜索方法还有一个非常赞的额外的优点：它的运行机制会让对组块的搜索是从先到后进行的，这可以充分发挥显卡的隐面消除能力。
事实上，0.8版本的《我的世界》移动版和《我的世界》个人电脑版在CPU上最消耗时间的三个地方是视锥体剔除、深度排序和重建整个调度顺序。这三个地方在两个版本上大概上占据了大约14%的处理时间。除此之外，《我的世界》个人电脑版的调度任务是出了名的糟糕和反应迟缓（会造成世界穿孔，有人遇到过么？）

广度优先搜索方法解决了这三个问题，让他们的处理时间变得线性，而最重要的是基于这些处理我们得到了我们一直期盼的可视性剔除！

所以，让我们简单描述下可视性搜索是如何工作的，下面用一种相当简略的方式将整个过程简单介绍下：

l  设置一组步骤，在每一步都包括一个我们接下来想要访问的组块以及我们进入到这个组块所经过的面。

l  第一步是找到相机位于其内部的组块并将这个组块放到队列里面。

l  遍历队列里面的组块，直到队列空了为止。

l  在队列前面的组块先被访问，排队等待渲染或重建，并从队列弹出这个组块。

l  对于这个组块的每个邻居组块都要通过一些过滤器进行检测，判断是否需要遍历这个组块。

1.     首先，判断我们是否在往反方向走。我们并不想往回搜索，这是因为如果一个组块只能通过往后走才能到达的话，那么这个组块根本就是不可见的。所以，我们只会搜索面的方向与视野方向相反的面，判断的公式是N·V < 0。

2.     这一步是用关键的过滤器对组块进行检测！现在要处理的一共有3个组块：A，我们过来的那个组块。B，我们现在所在的组块。C，我们接下来会访问的组块。如果我们从组块Ａ出发通过组块Ｂ能够到达组块Ｃ（通过读取组块B的可视连通图进行判断这条路径是否可行，确认是否可以从块Ａ出发通过组块Ｂ到达组块Ｃ），那么组块C就通过了可视化检测！现在要处理的一共有3个组块：A，我们过来的那个组块。B，我们现在所在的组块。C，我们接下来会访问的组块。如果我们从组块Ａ出发通过组块Ｂ能够到达组块Ｃ（通过读取组块B的可视连通图进行判断这条路径是否可行，确认是否可以从块Ａ出发通过组块Ｂ到达组块Ｃ），那么组块C就通过了可视化检测！

3.     判断组块C是否通过了其他更多的检测器（更多的内容会在后面介绍，就在这里简单提及一下，第2步是通过可视化检测，这是最核心的，因为如果是不可见的，根本就不需要渲染，直接否决，但是也不是通过可视化测试的都是需要渲染的，所以才需要这一步）。

4.     组块C的视锥体剔除。视锥体剔除是这里面所有操作中最消耗计算量的，所以在最后一步做这个事情（如果前面的检测就没通过就不会有这一步了，这样就节省了计算量）。

5.     如果以上所有的测试都通过了，那么就会把这个相邻的组块放到队列里面：它会最终成为可视化的物体的一部分！

唷。这里本来应该有大量的文字来说明，但是你可以使用这个javascript开发的小玩具来体验下看看这个算法到底工作的效果是什么样子的：

可以四处移动鼠标来改变搜索的起点，单击并拖动改变方向来改变视线的方向。绿线显示的是到达每个组块的路径，用红色显示的组块表明已经被剔除了！

需要注意的是，在二维空间里面组块的剔除比例比三维空间的剔除比例高，因为可能的路径在二维空间中，会比三维空间少一些。

关于更多的过滤器！

正如你可能已经注意到的那样，我在解释算法的时候都是说这种算法的优点，这个方法也有一个缺点，它会导致不可预测的剔除，因此，帧率在有些时候会突然莫名其妙的下降。

事实上，这个问题就是导致我们在《我的世界》移动版里面去掉沟壑的技术原因，因为沟壑的存在总会导致最坏的一些情况！

之所以会出现这种情况是因为没有什么会阻止广度优先的搜索方法继续的搜索，让我们举个例子来说明一下，先有10个组块排成一排，然后再有7个组块组成一排向下直到沟壑的谷底，这样的话所有的组块都会被渲染出来。

在视觉上这个问题非常的明显，因为搜索的路径和光线投射没有丝毫的相同，这是因为搜索的路径会有一个巨大的弯曲，但是目前实现的算法是不够聪明来判断。。。这到底是一个沟壑还是一个洞穴。所以会导致另外一侧的所有的洞穴在某些角度都是可见的！

计算经过的步骤

为了尝试修补这个问题，我结合了我从《我的世界》游戏性方面获得的帮助看看能不能解决这个问题，主要是提出了哪些物体应该被看到哪些物体不应该被看到的启发性算法。
换句话说，在我们现在的地形生成条件下，”普通的洞穴“会有很多的弯、会存在海平面下面而且除非玩家看到这个洞穴那么它就会是完全暗的没有光照。因为路径的相关性往往意味着因果关系，我们可以在遍历的过程中惩罚具有这些属性的组块，因为显然这些组块会包含洞穴！
我们的想法是在搜索中加入最大的可行走可搜索步数，以便如果分支通过一个”坏“的组块的话会花费更多的步数并更早的结束掉这个分支。

我只选定了两种启发性算法，但就算是这样子，也是相同有效的：第一种启发性算法是当到达海平面以下的时候消耗的步数+1，第二种启发性算法是通过一个完全黑暗的组块的时候消耗的步数+3。

实验表明这些小技巧可以提高5%到15%的组块剔除率，这取决于场景的复杂度，而且它对于那些非常巨大的洞穴有特别好的处理效果，能够很妥善的处理这些巨大的洞穴的可见性问题。

坏消息是这些启发性算法对于表面沟壑的剔除没有太大的帮助，因为它们的形状可以让阳光到达底部。好吧，最后我们也没有找到太好的办法来处理沟壑。所以我们最后就把它们从版本中移除出去了。

最后的效果！

可以从下面的图中看到我们描述的算法确实起作用了！这是没有经过我们算法进行剔除的全景图片：

下面这张图是应用了本文描述的剔除算法以后的结果：

可以从图中看到有多少东西消失了！

当然这个搜索过程仍然可以做非常多可能的优化，特别是在解决沟壑可能引起的问题的方面!

我已经找到了一些优化的方法，但它会是另一篇文章:)

【版权声明】

原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。