《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 : noslopforever@yahoo.com.cn
分享到:
相关推荐
A星算法matlab源码及详细注释.pdf
embedded_software_the_works_by_Colin_Walls eBooks
Creating the Side Walls Creating a Cutout Creating Automatic Bends Extracting Drawings from the Sheet Metal Part Basic Tasks Managing the Default Parameters Editing the Sheet and Tool Parameters ...
simple ones, supply the need and thus the motivation and much of the explanation. When learning a new programming language, my first step is to program the game of craps. If I can build a ballistics ...
SpringBoot入门-配置-开发-测试~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
spring 实战是在最先spring版本4.0上基础开发的,把最新的spring技术融入到本书当中
Also we are investigated that with different shapes of EBG on the walls we can reduce S12 more than 4 dB. At 0.94GHz it is shown that this translates into a center to center separation between ...
室内定位算法,有助于研究者认清研究方向,给定位算法一个准确的描述,是很好的参考教材。the possibility for the user to be notified by visible and Waveformof Distance audible warnings using buzzer and ...
Building internet fire walls by visual basic
The document contains step by step java script program to check collision against fours walls of canvas.
Manhattan Associates公司是物流解决方案的领先供应商,它将向Walls Industries服装生产商推广运用“电子程控经理”这样一种RFID解决方案部件。 Walls作为对零售客户,代销点和在线购物等不同群体的销售商,将选用...
量子光学经典教材,是量子计算的基础。物理概念清晰,推导简洁
This is a book about building the network you need. We’ll dip into the topics of fire- walls and related functions, starting from a little theory. You’ll see plenty of examples of filtering and ...
Spring expert Craig Walls uses interesting and practical examples to teach you both how to use the default settings effectively and how to override and customize Spring Boot for your unique ...
Noise calibration delay coherence and SNR walls for signal detection
Spring in Action 3rd Edition Craig Walls ,Spring英文原版,学习英文很不错,欢迎下载
Spring in Action ... 李磊,程立,周悦虹 译, 人民邮电出版社出版, 2006年3月第1版,2006年3月北京第1次印刷
利用密度矩阵重整化群研究畴壁中海森堡自旋链中的纠缠,任杰,朱士群,利用密度矩阵重整化群,我们研究畴壁中海森堡自旋链中的纠缠,畴壁由边缘磁场产生。研究表明成奇数边的纠缠随着磁场的增加而下降
Arab walls 阿拉伯城镇场景.zip模型资源unity模型资源下载Arab walls 阿拉伯城镇场景.zip模型资源unity模型资源下载Arab walls 阿拉伯城镇场景.zip模型资源unity模型资源下载 1.合个人学习技术做项目参考 2.适合学生...
信道容量鲁棒性性折衷,认知无线电,相关检测