《Breaking The Walls》算法的第一印象和空间分割杂论

《Breaking The Walls》算法的第一印象和空间分割杂论

这个算法来自于国外的一篇论文《Breaking the Walls: Scene Partitioning and Portal Creation》（以下简称论文，为虾米不是国内滴？ -_-b），全名在这个Blog转载Dreams_wu的那篇文章里，大家可以去下来看。

当处理室外场景的时候，四叉和八叉毫无疑问，室内场景的时候，Bsp和室内八叉也是挺不错的，其中以Bsp为最好。但是有一种场景，四叉和八叉显得力不从心，Bsp又显得有点过分，这就是传说中的“城市场景”。

城市场景的特点是：数据量异乎寻常的巨大，具有大量不规则的平面，八叉分割很容易就将场景划分得过于细致而丧失了八叉本身的优势。而Bsp则由于不规则平面的存在，易将场景切分得毫无规则可言，如一团乱麻（图片来自论文）：

注意，白色的部分是建筑物。

这样的分割本身或许不是什么错误，但是，大空间的分割将直接导致大BSP树的产生，从而最终导致BSP算法效率的下降，同时，建筑物的外表面往往极为复杂（拜那些变态设计师所赐），没必要发生的BSP分割也因此增多了起来，最终的结果就是上图左：也就是我常说的诡异的空间～～ ^_^。

而相对而言，右边的算法：也就是所谓的Breaking The Wall （BW）算法，看起来就好很多。

BW算法基于这样一个理论：我们将3D的摩天大楼投影到2D平面（地面），那么，凡角落处，必有Portal，Portal和墙面围出的区域，必为Cell。这应该很好理解，建筑的外墙与另一栋相邻建筑的外墙之间，大凡就是街道和小巷，人能在其中穿行以跨越不同的区域，所以，这些地方肯定是要诞生Portal和Cell的。只是论文似乎忽略了一个问题（或者是我忽略了）：天桥怎么办呢？还有连接两栋楼的那种天桥，他们是悬空的，投影时怎么投影呢？这个目前还没有想到解决方案。

BW算法的核心是一个2D平面的蔓延算法，这和我现在工作中所作的蔓延算法有点相似，但他是2D空间中发生的，而我所作的是3D的蔓延。蔓延和BSP一样，最后的结果都是Cell和Portal，Cell组成空间，Portal连接Cell。唯一的不同是，Bsp以平面划分空间，以分出Cell和Portal，它所依据的是“平面等分空间为正反”的真理，因此，凡分割必要求将上级空间切分完全，完全切分成正负两个半空间。

而BW蔓延法虽然也是以墙面（平面）作为基础，但它只是以墙面延伸而不是平面作为分割基础，因此不必要受平面无限延展的限制，可以看作特别优化过的BSP。对于一些划分过小的空间，BSP是无法忽略的，因为平面必须跨越整个分割空间，而蔓延法会直接将之忽略，因为延伸不必考虑全空间的问题，只需要尽可能延展就可以，灵活很多。因此最后的结果看起来就比BSP规则很多。我们可以想象一下，BSP类如切西瓜，每刀下去，西瓜必定一刀两断。而BW就不会那么冲动，它只要求尽可能分割，就如同雕冰雕，适可而止，决不容许一刀两断的事情发生——太浪费了。

最近上了上Gameres，发现OGRE社群在批判BSP方面很有一手，或者说，他们主要批判的是传统经典BSP分割算法。关于这个问题，我是这样认为的：首先，作为自动空间分割的方案，我们不可能要求太高，相对于让美工一个个Portal去摆的方案而言，任何自动算法肯定都是傻而又蛮的。开发的高效性和运行的高效性总是反比。BW在处理这类问题的时候，其性能已经很不错了，你当然不能拿他来跟手动摆Portal的方案相比，但是，也没必要这样比，因为手动Portal的话，BSP其实就表现得很不错了，开发效率又高，运行效率也不低。放着成熟的技术不用，总是在开发新的技术和概念，很没必要的。

空间分割的首要原则应该是：没有普适分割法，只有最适分割法。只有知道自己要分割什么，目标是什么，才能得到最好的分割法和最好的空间。在这一点上，我的想法是：什么都不用批判，什么也都不需要批判，一切都是恩典，懂得感恩，才能获得一切。大家认为呢？

关于BW，简单说到这里，论文写得最全，大家可以下来看看。原文正在翻译，不过遇到点麻烦，有些句子实在有点难懂，我尽量快点吧，大家有什么内外结合或者城市场景分割的更好方案，请麻烦告诉我一声啊～

李巍[ noslopforever（天堂里的死神） ] 原作，转载请注明出处：http://blog.csdn.net/noslopforever

email : [e-mail]