来源：Chinaitlab 收集整理
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 它无法管理循环覆盖的情况，如图所示
[IMG]http://www.chinaitlab.com/www/imgfiles/2005.4.5.10.7.22.bsp101.jpg[/IMG]
BSP原理
建立BSP Trees的最初想法是获得一个图元的集合，这个集合是场景的一部分，然后分割这个图元集合为更小的子集合，这里必须注意子集合必须为“凸多边形”。这意味着子集合中任一个多边形都位于相同集合中其它多边形的“前面”。是不是有点难以理解呢，举一个例子，如果多边形A的每一个顶点都位于由多边形B所组成的一个面的正面，那么可以说多边形A位于多边形B的“前面”，参考左图。我们可以想象一下，一个盒子是由6个面组成的，如果所有的面都朝向盒子的内部，那么我们可以说盒子是一个“凸多边形”，如果不是都朝向盒子的内部，那么盒子就不是“凸多边形”。
[IMG]http://www.chinaitlab.com/www/imgfiles/2005.4.5.10.7.33.bsp102.jpg[/IMG]
下面让我们看一下如何确定一个图元集合是否是一个“凸多边形”，伪算法如下：
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 < Polygon.Distance)
5 then return BEHIND
6 else return INFRONT
l 函数 POLYGON-INFRONT
l 参数:
l Polygon1 – 用来确定其它多边形是否在其“前面”的多边形。
l Polygon2 – 检测是否在第一个多边形“前面”的多边形。
l 返回值:
l 第二个多边形是否在第一个多边形的“前面”
在上面的例子中无论你选择多边形1、6、7还是多边形8进行渲染时都不会分割任何其它的多边形，换句话说也就是所有的其它多边形都位于这些多边形的“正面”。
关于分割时选择产生多边形最少的分割面另外一个不太好的原因是大多数时候它所产生的层次树通常是不平衡的，而一个平衡的层次树在运行的时候通常比不平衡的层次树性能更好。 当获得最佳的分割面后伴随着必然产生一些被分割的多边形，如何对被分割的多边形进行处理呢，这里有两个方法：
1. 建立一个带叶节点的二叉树，这意味着每一个多边形将被放在叶节点中，因此每一个被分割的多边形也将被分开放在二叉树的一边。
2. 另外一个方法是将被分割的多边形保存到公共节点中，对每一个子树重复这个过程直到每一个叶节点都包含了一个“凸”多边形集合为止。
产生带叶节点的BSP树的算法如下：
l 函数GENERATE-BSP-TREE
l 参数:
l Node – 欲建立的类型为BSPTreeNode的子树。
l PolygonSet – 建立BSP-tree的多边形集合。
l 返回值:
l 保存到输入的父节点中的BSP-tree。
l 功能:
l 对一个多边形集合产生一个BSP-tree。
GENERATE-BSP-TREE (Node, PolygonSet)
1 if (IS-CONVEX-SET (PolygonSet))
2 Tree = BSPTreeNode (PolygonSet)
3 Divider = CHOOSE-DIVIDING-POLYGON (PolygonSet)
4 PositiveSet = {}
5 NegativeSet = {}
6 for each polygon P1 in PolygonSet
7 value = CALCULATE-SIDE (Divider, P1)
8 if(value = INFRONT)
9 PositiveSet = PositiveSet U P1
10 else if (value = BEHIND)
11 NegativeSet = NegativeSet U P1
12 else if (value = SPANNING)
13 Split_Polygon10 (P1, Divider, Front, Back)
14 PositiveSet = PositiveSet U Front
15 NegativeSet = NegativeSet U Back
16 GENERATE-BSP-TREE (Tree.RightChild, PositiveSet)
17 GENERATE-BSP-TREE (Tree.LeftChild, NegativeSet)
算法分析
函数CHOOSE-DIVIDING-POLYGON的时间复杂度为O(n2 lg n)，除非出现递归调用否则它将控制其它的函数，如果我们假设对多边形集合的分割是比较公平的话，那么我们可以通过公式来对函数GENERATE-BSP-TREE的复杂度进行表达： T(n) = 2T(n/2) + O(n2 lg n) 通过公式我们可以知道这个函数的复杂度为Q (n2 lg n)。这里n为输入的多边形集合的多边形数量。 下面我要用一个例子来演示如何产生一个BSP-tree。下面的结构是一个多边形的原始集合，为了表示方便对每一个多边形都进行了编号，这个多边形集合将被分割为一个BSP-tree。 [IMG]http://www.chinaitlab.com/www/imgfiles/2005.4.5.10.8.23.bsp106.jpg[/IMG]
为了能够运行这个算法我们必须对常量MINIMUMRELATION和MINRELATIONSCALE进行赋值，在实际运行中我们发现当MINIMUMRELATION=0.8而MINRELATIONSCALE=2时可以获得比较好的结果。但是你也可以对这些数值进行试验来比较一下，通常当常数MINIMUMRELATION比较大时获得的层次树会比较平衡但同时分割产生的多边形也会大量增加。在上图显示的多边形集合并不是一个“凸”的，因此首先我们需要≡褚桓龊鲜实姆指蠲妗Ｔ诳焖俚亩陨厦娴慕峁菇幸幌落篮笪颐强梢灾蓝啾咝危?、2、6、22、28）不能被用来作为分割面，这是因为它们定义了包含所有多边形集合的外形。但是其它的多边形都可以作为候选的分割面。分割产生的多边形最少同时分割为两个子集合的多边形数目之比为最佳的多边形是16与17，它们位于同一条直线上同时并不会分割任何的多边形。而分割后的子集合的多边形数目也是一样的，都是“正面”为13而“反面”为15。让我们选择多边形16作为分割面，那么分割后的的结构如下： [IMG]http://www.chinaitlab.com/www/imgfiles/2005.4.5.10.8.34.bsp107.jpg[/IMG] 现在从图中我们可以看到无论是左子树还是右子树都没有包含“凸”多边形集合，因此需要对两个子树继续进行分割。 在左子树中多边形1、2、6、7作为多边形集合的“凸边”不能用做分割面，而多边形4、10在同一条直线上同时没有分割任何多边形，而分割后的多边形子集合：“正面”为8而“反面”为7非常的平衡，我们选择多边形4为分割面。 在右子树中多边形16、17、22、23、28不能作为分割面，而多边形18、19、26、27虽然没有分割任何多边形但是分割后的多边形子集合：“正面”为11而“反面”为3，3/11这个比值小于最小比值0.5因此我们需要寻找其它更适合的多边形。多边形20、21、24、25都只分割了一个多边形，但是多边形21看起来分割后的结果更合理，在分割过多边形22后多边形子集合的结果为：“正面”为8而“反面”为6。 下图显示了操作后的结果： 非常好，绝对经典！！ 意见同上 ！丁页 ！ 不过太长了都懒得看。 谢了,前辈,我把网页保存下来,回去好好学习. 楼主是抄来的吧，这本书我有～ atlantia什么书呀？？？ 古怪的规矩！
吃葡萄吃葡萄吃葡萄不吐葡萄皮儿，
不吃葡萄不吃葡萄不吃葡萄倒吐葡萄皮儿，
嘴里嘴里嘴里嘴里嘴里嘴里怎么还是不对味儿，
欧，还有俩葡萄籽儿。
有什么意义呀？ 实在是太难 太深懊了 好东西，精品
页:
[1]
