首页 > 代码库 > [图形学] 简化的bsp树
[图形学] 简化的bsp树
简介
bsp树是一种空间分割树，它主要用于游戏中的场景管理，尤其是室内场景的管理。
它的本质是二叉树，也就是用一个面把空间分割成两部分，分割出的空间则继续用面分割，以此类推，直到到达特定递归深度，或者空间中不再有物体或只剩下一个物体（得到凸包/凸多面体）。
最终，叶结点对应场景中的物体，内部结点存储分割面。物体被“收纳”到各个包围盒中。
应用
bsp树对应的应用主要有两个方面：
(1) 确定物体的遮挡关系，可视化处理。
(2) 碰撞检测的广阶段。
首先，要明确的一点是，bsp树是在设计地图时自动生成的树，它随之被保存到磁盘，也就是事先进行了预处理。在加载场景的时候，我们直接读入bsp文件，而不是重新生成。
这也就意味着，作为预处理技术，bsp树只能处理静态的场景。
bsp树本身的结构非常简单，但是这并不代表着bsp树的编程非常容易。其复杂性主要体现在：
(1) bsp树不是独立存在的，它需要与前期的地图编辑器和后期的场景剔除/碰撞检测结合在一起。而这两者都是非常复杂的项目。
(2) 选择合适的分割面，使得树尽可能平衡，并且能在恰当的时候停止分割。
对于场景剔除而言，重点就是判断物体的前后关系，而这种空间拓扑关系在bsp树中已有了明显的体现。我们从根结点开始，根据摄像机所在位置和分割平面进行对比，很容易就能判断出结点的两个子空间与视点的前后关系。我们认为与视点在同一侧的为前面，在不同侧的为后面。
对于碰撞检测而言，对所有物体都两两进行碰撞检测十分耗时，我们可以首先对物体进行初步排查，如果不处在同一个叶结点（包围盒），那么一定不会发生碰撞，通过简单的遍历树避免了繁琐的计算。
具体实现
bsp树的编程比较复杂，在这里对bsp树做了最简化。之后的代码仅作为练习用，目的是更好地掌握bsp树。
如果希望学习可用于商业引擎的bsp树，可参考quake3的地图编辑器。
主要参考了《实时渲染》一书中给出的一个BSP结构，如下：
简化部分 ：
(1) 使用二维，而不是三维。
(2) 手工输入包围盒，而不是自动生成。包围盒为AABB包围盒（轴向），不支持上图中的凹多边形。
(3) 叶结点和内部结点共用一个数据结构。其中内部结点存储了方向（水平或竖直）以及分割线；叶结点存储了对应场景为实心还是空心。
(4) 沿着包围盒的边界进行分割（和图中所示相同），选择分割线的方法比较简单：
1.分别选出水平和竖直方向的最优分割线。（判断标准：与空间中心最接近的包围盒边界线）
2.如果最优水平分割线和场景中物体相交，而最优竖直分割线和场景中物体不相交，那么优先选择最优竖直分割线，反之亦然。
如果都相交或都不相交，那么优先选择距离中心点更近的（按相对比例来算）
如果选择的分割线与包围盒相交，那么把这个包围盒根据分割线拆成两个包围盒。
(5) 退出条件（达到之一）：
1.达到最大分割层数，直接生成两个叶结点，返回。
2.空间里没有物体了，返回空叶结点。
3.空间里只剩下一个物体了，返回满叶结点。
详细介绍已在代码注释中体现。
结点数据结构
样例
蓝线：第一次分割 ； 紫线：第二次分割 ； 黄线：第三次分割
包围盒：
（4,10,4,16）
（10,24,4,9）
（7,19,23,27）
（22,28,13,24）
bsp树
代码
bsp.h
#pragma once
#include<vector>
class bspTree
{
private:
struct bspNode {
bspNode* left;
bspNode* right;
bool isLeaf;//是否是叶结点
bool isSolid;//是否实心
bool isHori;//是否水平
float data;//分割线
};//结点数据结构
struct box_t {
float xmin;
float xmax;
float ymin;
float ymax;
box_t();
void set(float x1, float x2, float y1, float y2);
};//包围盒数据结构
bspNode* root;//根节点
std::vector<box_t>box;//包围盒容器
float xmin, xmax, ymin, ymax;//整个场景的轴向包围盒
int boxNum;//包围盒的个数
int layer;//树的最大深度
int layer_count;//记录当前层数
bspNode* createEmptyNode();//生成空叶结点
bspNode* createSolidNode();//生成非空叶结点
void split(float& data_x, float& data_y, float& dis_x, float& dis_y,
float xmin, float xmax, float ymin, float ymax);//寻找最优分割线
bspNode* genNode(bool isFull_1, bool isFull_2, int layer_count,
float xmin, float xmax, float ymin, float ymax, float data,bool isHori);//生成新的结点
bspNode* build(int layer_count, float xmin, float xmax,
float ymin, float ymax);//创建新的结点
bool isIntersect(float xmin, float xmax, float ymin, float ymax, float data, bool isHori,std::vector<int>& id,int& num);
//某一空间中的分割线是否与空间中的一个包围盒相交
void traversal(bspNode* t);//前序遍历
bool inBox(float x1, float x2, float y1, float y2, int id);//包围盒id是否完全处在某个空间中
void checkIsFull(bool& isFull_x_1, bool& isFull_x_2, bool& isFull_y_1, bool& isFull_y_2,
float xmin, float xmax, float ymin, float ymax, float data_x, float data_y);//检测分割出的两个区域是否为满/空
bool isIntersect(float x1, float x2, float y1, float y2, int id);//包围盒id是否与某个空间有交集
public:
bspTree(float x1, float x2, float y1, float y2, int l);//构造
//前四个参数为场景包围盒，l为最大递归深度
void add(float x1, float x2, float y1, float y2);//添加包围盒
void build();//创建bsp树
void print();//前序遍历输出
void levelOrder();//层次遍历输出
};bsp.cpp
#include"bsp.h"
#include<algorithm>
#include<queue>
bspTree::box_t::box_t() { }
void bspTree::box_t::set(float x1, float x2, float y1, float y2)
{
xmin = x1;
xmax = x2;
ymin = y1;
ymax = y2;
}
bspTree::bspTree(float x1, float x2, float y1, float y2, int l)
{
xmin = x1;
xmax = x2;
ymin = y1;
ymax = y2;
layer = l;
boxNum = 0;
layer_count = 0;
root = nullptr;
}
void bspTree::add(float x1, float x2, float y1, float y2)
{
box_t b;
boxNum++;
b.set(x1, x2, y1, y2);
box.push_back(b);
}
//某一空间中的分割线是否与空间中的一个包围盒相交
bool bspTree::isIntersect(float xmin,float xmax,float ymin,float ymax,float data, bool isHori, std::vector<int>& id,int& num)
{
bool flag = false;//记录是否存在交
//分割线是水平的
if (isHori) {
//遍历所有包围盒
for (int i = 0; i < boxNum; i++) {
//如果包围盒完全处在空间中
if (inBox(xmin, xmax, ymin, ymax, i)) {
num++;//记录包围盒个数+1
if (data > box[i].xmin && data < box[i].xmax) { //存在交
id.push_back(i);//记录包围盒id
flag = true;//存在交 为真
}
}
}
}
//分割线是竖直的
else if (!isHori) {
//遍历所有包围盒
for (int i = 0; i < boxNum; i++) {
//如果包围盒完全处在空间中
if (inBox(xmin, xmax, ymin, ymax, i)) {
num++;//记录包围盒个数+1
if(data > box[i].ymin&&data < box[i].ymax) {//存在交
id.push_back(i);//记录包围盒id
flag = true;//存在交 为真
}
}
}
}
return flag;
}
//包围盒id是否完全处在某个空间中
bool bspTree::inBox(float x1, float x2, float y1, float y2,int id)
{
return box[id].xmin >= x1 && box[id].xmax<=x2 &&
box[id].ymin>=y1 && box[id].ymax <= y2;
}
//寻找最优分割线
void bspTree::split(float& data_x, float& data_y, float& dis_x, float& dis_y,
float xmin, float xmax, float ymin, float ymax)
{
float d = 10000;
//先计算竖直方向
//遍历所有包围盒
for (int i = 0; i < boxNum; i++) {
//如果包围盒完全处在空间中
if (inBox(xmin,xmax,ymin,ymax,i)) {
//计算包围盒边界线到中心的距离
d = box[i].xmin - ((xmax - xmin) / 2 + xmin);
if (d < 0)d = -d;
//如果有更小的距离，更新距离和分割线
if (d < dis_x) {
dis_x = d;
data_x = box[i].xmin;
}
//计算包围盒边界线到中心的距离
d = box[i].xmax - ((xmax - xmin) / 2 + xmin);
if (d < 0) d = -d;
//如果有更小的距离，更新距离和分割线
if (d < dis_x) {
dis_x = d;
data_x = box[i].xmax;
}
}
}
//再计算水平方向
//遍历所有包围盒
for (int i = 0; i < boxNum; i++) {
//如果包围盒完全处在空间中
if (inBox(xmin, xmax, ymin, ymax, i)) {
//计算包围盒边界线到中心的距离
d = box[i].ymin - ((ymax - ymin) / 2 + ymin);
if (d < 0)d = -d;
//如果有更小的距离，更新距离和分割线
if (d < dis_y) {
dis_y = d;
data_y = box[i].ymin;
}
//计算包围盒边界线到中心的距离
d = box[i].ymax - ((ymax - ymin) / 2 + ymin);
if (d < 0)d = -d;
//如果有更小的距离，更新距离和分割线
if (d < dis_y) {
dis_y = d ;
data_y = box[i].ymax;
}
}
}
//计算相对距离
dis_x /= xmax - xmin;
dis_y /= ymax - ymin;
}
//创建空叶结点
bspTree::bspNode* bspTree::createEmptyNode()
{
bspNode* node = new bspNode();
node->left = nullptr;
node->right = nullptr;
node->isLeaf = true;
node->isSolid = false;
node->data = http://www.mamicode.com/0.0f;>
main.cpp#include "bsp.h"
#include<stdlib.h>
int main()
{
bspTree* t = new bspTree(1,33,1,33,3);
t->add(4, 10, 4, 16);
t->add(10, 24, 4, 9);
t->add(7, 19, 23, 27);
t->add(22, 28, 13, 24);
t->build();
t->print();
printf("\n");
t->levelOrder();
system("pause");
}
[图形学] 简化的bsp树