Bsp分割算法简述

    BSP分割算法也是有不少文章可以借鉴的，就我目前能掌握的资料来看，泛泛而谈者大有人在，实际去作的时候却总是抓瞎。知道是什么永远不如知道怎么做，BSP分割是BSP分析的基础，虽然它很简单，但是，如果连简单的都不会做，又怎么能胜任复杂的工作呢？
    趁这段时间有空，遂埋头钻研BSP，一周之后，分割和自动Portal生成均已解决，遂做此文，希望能对初学者有所帮助，亦希望能抛砖引玉，众位高手能不吝赐教。
    本文先就BSP中相对简单的分割部分做一个简单的介绍，自动Portal生成的资料正在整理，希望能尽快放出。
    BSP的基本原理
    试想我们生活的空间，肯定是由为数众多的天花板、墙壁和地板组成，对于每一个“板”，都将空间分为“板前”和“板后”两个部分。已知人的位置，就可根据人在“板前”还是在“板后”，知道人所能看到的物体的遮挡顺序（e.g.如果人在板前，则板前的物体遮挡所有板后的物体）。
    BSP者，原理很简单：它试图将所有的板（在BSP中叫做平面）组织成一棵树，每个平面均将它所在的空间分割为前后两个部分，这两个部分又分别被另外的平面分割成更小的空间……直到最后，按照前面所说的算法，确定每一个房间（在BSP中叫做叶子）相对于眼睛的遮挡顺序。
    这是一个非常标准的二分法，仅按照“前”和“后”两个逻辑上的概念来切分空间，这使得它在以“房间”为单位组成的室内场景里是不二之选。为什么？请接着看：
    在判断遮挡顺序的时候，BSP空间的算法极为简单：只需要从树根开始，简单判断人的位置与所有平面的前后关系：前则正子树（在平面“前”方的空间）在前，负子树（在平面“后”方的空间）在后；后则正子树在后，负子树在前。以此递归到叶子（叶子总是一个房间），就可以确定人处于哪一个房间之中、其他房间的遮挡关系如何。
    这个其实很简单：因为所有的平面均将其所处的空间分为前后两个部分，所以，每一个房间，均是由若干平面的“前”“后”来决定的，通过人与这些平面前后关系的判断，自然而然就可以直接定位到所需的房间之中了。这就是BSP算法的特别之处。

    如图：空间ABC由A、B、C三个独立的房间组成，首先，分割平面1将空间分成了平面正向的A房间和平面负向的BC空间，BC空间被2紧接着分割为平面2正向的C房间和负向的B房间。注意这里平面的方向一般由墙壁面向的方向而定。
    如果有一个人处于C房间内，那么如何判断所有房间的遮挡顺序呢？从树根开始，由于人处于平面1的“后”面，所以，BC空间应该先于A房间（后：先负后正），然后，由于人处于分割平面2的“前”面，所以，C房间应该先于B房间（前：先正后负）。这样，整个房间离人由近到远的顺序就可以确定了：C－B－A。仅需要通过两次平面的前后判断（总共六次乘法、两次加法、两次大小判断），就可以确定空间的先后顺序，算法的威力可见一斑！
    BSP分割的目标是将空间划分为一个个叶凸体，也就是一个凸面体。一个个凸面体才有排序的可能，很难想象一个非凸面体在空间中如何排序。如图左：从箭头方向看过去，到底凹多面体A是在B的前面？还是B在凹多面体A的前面？而如果是右边的，两个凸多面体，情况就不一样了，A和B方向的前后，根据视点的位置永远是唯一的。这就是BSP的优势，只需要知道视点的位置，空间所有凸体的位置顺序都可以马上确定，但如果是凹体，对不起，那就确定不了了，所以，BSP划分空间结构化面的结果必然是一个个凸面体。

    这里面唯一想强调的一点是，如果您分析过Quake3的BSP格式，那么您会发现过去有时候一个房间会被几个柱子分割得乱七八糟，只是为了少渲染几个面。现在大不必这么兴师动众，一个房间就留外面的6个结构化面，柱子什么的只算作细节Mesh，不参与分割，这样产生的结果，与Portal筛选结合之后，效率未必就差。而且，结构更符合逻辑，在以后自动路点和路径计算的时候，会有一些优势。想想看，被一个很不规则的柱子（或箱子等其他物体）划分得乱七八糟的空间，一个房间就有很多个叶子，到底哪些叶子是人能走到的？哪些叶子是人走不到的？哪些叶子需要在AI中被考虑？哪些叶子可以排除？一个不以逻辑构成的空间，必然在逻辑的处理上要处处碰壁。所以，最好还是一个叶子就是一个房间、或者一个走廊；柱子、箱子啊什么的全都用细节Mesh，就可以了。
    注意，BSP划分出的凸体其实主要是为了后面BSP分析而进行的，而不是渲染。早先的时候硬件很糟糕，没有Z缓冲，那时候省一个三角形比现在重要得多。现在？有时候宁可多画一堆三角形也不会去浪费那个CPU资源进行三角形的逐个筛选。所以，尽量减少结构化面，使结构化面的房间组成凸体，但细节面把房间装点成什么样，那就无所谓了，即便细节面将这个空间又变成了一个凹体，也是无所谓的。

    由于是一个老算法了，因此BSP分割算法早已经不是什么神秘的东西，这个算法有很多例子，推荐《BSP技术详解》（翻译后的名称如此），唯一的遗憾是这篇文章的伪代码需要花点心思。另外，《3D游戏 卷2 动画与高级实时渲染技术》所带的FLY 3D引擎也有很完整的代码，虽然整个看下来比伪代码还难懂，但是每个函数基本上都还算清晰，也是一个难得的备选资料。
    当然，可能大部分人还是倾向于去看Quake和HL2的代码。为了使自己加深印象，我所选择的是自己从零开始，仅按照资料上的观点和流程进行DIY，而没有参考代码。因为经常参考着、参考着就“拿来主义”了，虽然开发效率保证了，但是记性不清，一旦扩展起来，基本抓瞎