BSP技术作为室内引擎渲染的主流技术虽然已经存在多年,但是生命力仍然非常顽强,最新的DOOM3,HL2仍然将它作为渲染的主流技术,但是在网上对它介绍文章虽然多却非常浅显,大多是使用Q3的BSP文件进行渲染,而BSP文件如何产生则介绍非常少,盖因为这一部分是场景编辑器的工作,而完成一个这样的BSP编辑器是非常困难的,需要掌握的知识非常多.下面我将对BSP编辑器这一部分需要用到的BSP知识进行一下介绍,这只是一些很初步的知识,如希望了解更多的内容,Q2开源代码中有一个BSP编辑器的代码是你研究的重点,还有就是HL2泄露代码中的编辑器代码,(一个痛苦的研究过程,可能要花费你几个月甚至一年的时间,不过这是值得的,如果你想完成一个主流的射击游戏引擎的话,没有BSP编辑器是不可想象的).
第一节 BSP Trees
BSP Trees英文全称为Binary Space Partioning trees，二维空间分割树，简称为二叉树。它于1969年被Shumacker在文章《Study for Applying Computer-Generated Images to Visual Simulation》首次提出，并被ID公司第一次使用到FPS游戏Doom中，Doom的推出获得了空前的成功，不仅奠定了ID公司在FPS游戏开发的宗师地位，也使BSP技术成为室内渲染的工业标准，从BSP产生到现在已经有30多年了，其间虽然产生了大量的室内渲染的算法，但却无人能撼动它的地位，对于以摩尔定律发展的计算机业来说这不能不是一个奇迹。
为什么使用BSP Trees
一个BSP Trees如同它的名字一样是一个层次树的结构，这个树的叶节点保存了分割室内空间所得到的图元集合。现在随着硬件加速Z缓冲的出现，我们只需要用很小的代价就可以对空间中的图元进行排序，但是在90年代初由于硬件的限制，使用BSP的主要原因是因为它可以对空间中的图元进行排序来保证渲染图元的顺序是按照由后至前进行的，换句话说，Z值最小的物体总是最后被渲染。当然还有其他的算法可以完成这个功能，例如著名的画家算法，但是它与BSP比较起来速度太慢了，这是因为BSP通常对图元排序是预先计算好的而不是在运行时进行计算。从某种意义上说BSP技术实际上是画家算法的扩展，正如同BSP技术的原始设计一样，画家算法也是使用由后至前的顺序对场景中的物体进行渲染。但是画家算法有以下的缺点：
l 如果一个物体从另一个物体中穿过时它不能被正确的渲染；
l 在每一帧对被渲染的物体进行排序是非常困难的，同时运算的代价非常大；
l 它无法管理循环覆盖的情况，如图所示
BSP原理
建立BSP Trees的最初想法是获得一个图元的集合，这个集合是场景的一部分，然后分割这个图元集合为更小的子集合，这里必须注意子集合必须为“凸多边形”。这意味着子集合中任一个多边形都位于相同集合中其它多边形的“前面”。是不是有点难以理解呢，举一个例子，如果多边形A的每一个顶点都位于由多边形B所组成的一个面的正面，那么可以说多边形A位于多边形B的“前面”，参考左图。我们可以想象一下，一个盒子是由6个面组成的，如果所有的面都朝向盒子的内部，那么我们可以说盒子是一个“凸多边形”，如果不是都朝向盒子的内部，那么盒子就不是“凸多边形”。
下面让我们看一下如何确定一个图元集合是否是一个“凸多边形”，伪算法如下：
l 函数CLASSIFY-POINT
l 参数:
l Polygon ? 确定一个3D空间中点相对位置的参考多边形。
l Point ? 待确定的3D空间中的点。
l 返回值:
l 点位于多边形的哪一边。
l 功能:
l 确定一个点位于被多边形定义的面的哪一边。
CLASSIFY-POINT (Polygon, Point)
1 Sidevalue = Polygon.Normal * Point
2 if (Sidevalue == Polygon.Distance)
3 then return COINCIDING
4 else if (Sidevalue
5 then return BEHIND
6 else return INFRONT
l 函数 POLYGON-INFRONT
l 参数:
l Polygon1 ? 用来确定其它多边形是否在其“前面”的多边形。
l Polygon2 ? 检测是否在第一个多边形“前面”的多边形。
l 返回值:
l 第二个多边形是否在第一个多边形的“前面”。
l 功能:
l 检测第二个多边形的每一个顶点是否在第一个多边形的“前面”。
POLYGON-INFRONT (Polygon1, Polygon2)
1 for each point p in Polygon2
2 if (CLASSIFY-POINT (Polygon1, p) INFRONT)
3 then return false
4 return true
l 函数 IS-CONVEX-SET
l 参数:
l PolygonSet ? 用来检测是否为“凸多边形”的图元集合。
l 返回值:
l 集合是否为“凸多边形”。
l 功能:
l 相对于集合中的其它多边形检查每一个多边形，看是否位于其它多边形的“前面”，如果有任意两个多边形不满足这个规则，那么这个集合不为“凸多边形”。
IS-CONVEX-SET (PolygonSet)
1 for i = 0 to PolygonSet.Length ()
2 for j = 0 to PolygonSet.Length ()
3 if(i != j && not POLYGON-INFRONT(PolygonSet[i], PolygonSet[j]))
4 then return false
5 return true
在函数POLYGON-INFRONT中并没有进行对称的比较，这意味着如果多边形A位于多边形B的“前面”你并不能想当然的认为多边形B一定位于多边形B的“前面”。下面的例子简单的显示了这一点。
在上图中我们可以看到多边形1位于多边形2的“前面”，这是因为顶点p3、p4位于多边形2的“前面”，而多边形2却没有位于多边形1的“前面”，因为顶点p2位于多边形1的“后面”。
对于一个BSP层次树来说可以用下面结构来定义：
class BSPTree
{
BSPTreeNode RootNode // 树的根节点
}
class BSPTreeNode
{
BSPTree Tree // 接点所属的层次树
BSPTreePolygon Divider // 位于两个子树之间的多边形
BSPTreeNode *RightChild // 节点的右子树
BSPTreeNode *LeftChild // 节点的左子树
BSPTreePolygon PolygonSet[] // 节点中的多边形集合
}
class BSPTreePolygon
{
3DVector Point1 // 多边形的顶点1
3DVector Point3 // 多边形的顶点2
3DVector Point3 // 多边形的顶点3
}
现在你可以看见每一个多边形由3个顶点来定义，这是因为硬件加速卡使用三角形来对多边形进行渲染。将多边形集合分割为更小的子集合有很多方法，例如你可以任意选择空间中的一个面然后用它来对空间中的多边形进行分割，把位于分割面正面的多边形保存到右子树中而位于反面的多边形保存到左子树中。使用这个方法的缺点非常明显，那就是如果想选择一个将空间中的多边形分割为两个相等的子集合的面非常困难，这是因为在场景中有无数个可选择的面。如何在集合中选择一个最佳的分割面呢？下面我将对这个问题给出一个比较适当的解决方案。
我们现在已经有了一个函数POLYGON-INFRONT，它的功能是确定一个多边形是否位于其它多边形的正面。现在我们要做的是修改这个函数，使它也能够确定一个多边形是否横跨过其它多边形定义的分割面。算法如下：
l 函数 CALCULATE-SIDE
l 参数 :
l Polygon1 ? 确定其它多边形相对位置的多边形。
l Polygon2 ? 确定相对位置的多边形。
l 返回值:
l 多边形2位于多边形1的哪一边
l 功能:
l 通过第一个多边形对第二个多边形上的每一个顶点进行检测。如果所有的顶点位于第二个多边形的正面，那么多边形2被认为位于多边形1的“前面”。如果第二个多边形的所有顶点都位于第一个多边形的反面，那么多边形2被认为位于多边形1的“后面”。如果第二个多边形的所有顶点位于第一个多边形之上，那么多边形2被认为位于多边形1的内部。最后一种可能是所有的顶点即位于正面有位于反面，那么多边形2被认为横跨过多边形1。
CALCULATE-SIDE (Polygon1, Polygon2)
1 NumPositive = 0, NumNegative = 0
2 for each point p in Polygon2
3 if (CLASSIFY-POINT (Polygon1, p) = INFRONT)
4 then NumPositive = NumPositive + 1
5 if (CLASSIFY-POINT (Polygon1, p) = BEHIND)
6 then NumNegative = NumNegative + 1
7 if (NumPositive 0 && NumNegative = 0)
8 then return INFRONT
9 else if(NumPositive = 0 && NumNegative 0)
10 then return BEHIND
11 else if(NumPositive = 0 && NumNegative = 0)
12 then return COINCIDING
13 else return SPANNING
上面的算法也给我们解答了一个问题，当一个多边形横跨过分割面时如何进行处理，上面的算法中将多边形分割为两个多边形，这样就解决了画家算法中的两个问题：循环覆盖和多边形相交。下面的图形显示了多边形如何进行分割的。
如图所示，多边形1为分割面，而多边形2横跨过多边形1，如图右边所示，多边形被分割为2、3两部分，多边形2位于分割面的“前面”而多边形3位于分割面的“后面”。
当建立一个BSP树时，首先需要确定的问题是如何保证二叉树的平衡，这意味着对于每一个叶节点的分割深度而言不能有太大的差异，同时每一个节点的左、右子树需要限制分割的次数。这是因为每一次的分割都会产生新的多边形，如果在建立BSP树时产生
