爱华网一、什么是bsp和bsp树的基本原理
Bsp即二叉空间分割，在图形学中我们常说到bsp树，bsp树是最基本的空间排序方法，doom是第一个使用了二叉树的商业游戏。（这个游戏我也不是很清楚）即空间中的任何平面都将整个空间分割成两个半空间，所有位于该平面某一侧的点定义了一个半空间，位于另一侧的点定义了另一个半空间。由于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在图形学中的主要应用
bsp树是典型的空间分割算法。在三维空间中场景的划分用到了bsp树，可视性问题和碰撞检测问题都最终归结为树的遍历和下溯。
1、消隐中的应用
三维场景要在二维屏幕上真实的显示出来，就要生成没有二义性的图形。为了生成没有二义性的具有真实感的图形，一个首要的问题就是在给定的视点和视线方向后，决定场景中哪些物体的表面是可见的，哪些是被遮挡不可见的。这个问题称为物体的消隐或隐藏线/面得消除。
在这里，我们可以用bsp树，bsp树是从远到近往屏幕上覆盖景物的画面，bsp算法在对场景进行消隐之前需建立场景的bsp树。建立bsp树的过程就是对场景所含景物多边形递归地进行二叉类的过程。这个建立bsp树的过程在前面我们讲bsp思想史已说，这里不再赘述了。
这是我们做的游戏中树的渲染，就可以用bsp树，从后到前的渲染，就不会用遮挡的现象了。如下图：
2、碰撞检测问题。在三维场景中物体都是有多边形构成的，所谓的碰撞检测就是让物体在相撞时可以不穿过去。这也就是说当组成的物体的多边形相撞时，我们要进行判断。bsp树的遍历是使用bsp的一个基本技术。Bsp做碰撞检测时是递归地遍历树并判断分割面是否和包围球或包围盒相交。进行这种检测最简单的方法就是测试看看物体的所有部分是否都在分割面的一侧。在建立bsp树，进行碰撞检测室，在碰撞没发生的时候，我们要注意，一个物体（或它的包围盒）必须在分割面的正面或背面。如果在平面的正面和背面都有顶点，说明物体与这个平面相交了。
3、
4、基于BSP树的启发式阴影生成算法
阴影的生成在虚拟现实领域一直是个难题,特别是针对动态光源的大规模场景,目前还没有较成熟的阴影算法.通过对现有阴影生成算法和场景组织算法的研究，提出了基于二维空间分割树(BSP树)的启发式阴影生成算法:首先创建场景BSP树,随着观察者视点的改变,选取视剪裁体内的节点创建以光源为视点的遮挡体BSP树,然后通过对该BSP树的遍历拣选出阴影启发区内的物体,经过处理后BSP树只留下一些生成阴影必要的多边形大大减少了计算量,最后能够快速生成阴影
三、bsp树有很多优点，但是它也有不足。
通常，地形以及地形覆盖物都是静态几何体，这样的几何体相互之间的位置都不变，如果要写一个场景管理器的话，静态物体都是处在根节点的层面上的。BSP等等消隐算法只能对这些物体进行划分，如果你将一个动态几何体划入BSP的话，那么每次该物体移动时，你都要重新生成BSP树，简单地说，这是不可能的。
