BSP 分割空间实现

1、BSP:二叉分割树，是一种分割场景的方法，下面代码是BSP树一种实现可运行：运行例子中，将定义的16个空间面，分割为一个深度是3的BSP树，上图显示的是运行结果：#include "stdafx.h"#include <map>#include <vector>#include <iostream>using namespace std;/定义空间的点结构struct pointfloat x,y,z;point():x(0.0f),y(0.0f),z(0.0f);point(float a,float b,float c):x(a),y

2、(b),z(c)void operator += (int n)x += n;y += n;z += n;void operator = (point& p)memcpy(this,(void*)&p,sizeof(*this);/定义空间的面结构struct facepoint P3;void operator +=(int n)P0 += n;P1 += n;P2 += n;/定义包围盒结构struct BBoxpoint Min;point Max;BBox():Min(),Max();enum EAxis/沿的轴枚举Axis_X,Axis_Y,Axis_Z,;/树节点的

3、定义struct TreeNode TreeNode():box(),nDepth(0),pLChild(NULL),pRChild(NULL),Axis(Axis_X),Split(0.0f)vFaceId.reserve(16);int nDepth;TreeNode* pLChild;TreeNode* pRChild;std:vector<int> vFaceId;int Axis;BBox box;float Split;/存储空间的面std:map<int,face> m_mFace;/通过面ID获取面的地址face* GetFaceByID(int nID

4、)std:map<int,face>:iterator itr = m_mFace.find(nID);if (itr != m_mFace.end() )return &(m_mFacenID);return NULL;/BSP类的定义实现class BspTreepublic:BspTree():m_pRoot(NULL);BspTree()if (m_pRoot)DeleteNode(m_pRoot);/初始化树根void InitTreeRoot(TreeNode *pNode);/释放整个树的资源void DeleteNode(TreeNode * pNode);

5、/生成AABB包围盒void BuildAABB(TreeNode * pNode);/切分整个空间void SplitSpace(TreeNode* pRoot,int nAxis,int ndepth);/切分面void SplitFace( int nFaceId, float fSplit, int nAxis, int* pLeftNum, int* pRightNum, int* pBothNum );/遍历整个树void ErgodicTree(TreeNode * pNode);protected:private:TreeNode *m_pRoot;void BspTree:I

6、nitTreeRoot(TreeNode *pNode)if (pNode = NULL)return;m_pRoot = pNode;void BspTree:DeleteNode(TreeNode * pNode)if (pNode = NULL)return;DeleteNode(pNode->pLChild);DeleteNode(pNode->pRChild);delete pNode;/遍历整个树void BspTree:ErgodicTree(TreeNode * pNode)if (pNode = NULL)return;ErgodicTree(pNode->

7、pLChild);cout<<"节点深度: "<<pNode->nDepth<<"含有多少个面: "<<pNode->vFaceId.size();switch (pNode->Axis)case Axis_X:cout<<" 沿X轴分割"<<"分割点是: x ="<<pNode->Split<<endl;break;case Axis_Y:cout<<" 沿Y轴分割&quo

8、t;<<"分割点是: y ="<<pNode->Split<<endl;break;case Axis_Z:cout<<" 沿Z轴分割"<<"分割点是: z ="<<pNode->Split<<endl;break;ErgodicTree(pNode->pRChild);void BspTree:BuildAABB(TreeNode * pNode)if(!pNode)return;point Min(1000000,1000000,

9、1000000);point Max(-1000000,-1000000,-1000000);for(int n = 0; n < pNode->vFaceId.size(); +n)face *pFa = GetFaceByID(n);if (pFa = NULL)continue;for(int m = 0; m < 3; +m)if (pFa->Pm.x > Max.x) Max.x = pFa->Pm.x;if (pFa->Pm.y > Max.y)Max.y = pFa->Pm.y;if (pFa->Pm.z > Ma

10、x.z)Max.z = pFa->Pm.z;if (pFa->Pm.x < Min.x)Min.x = pFa->Pm.x;if (pFa->Pm.y < Min.y)Min.y = pFa->Pm.y;if (pFa->Pm.z < Min.z)Min.z = pFa->Pm.z;pNode->box.Max = Max;pNode->box.Min = Min;int CompareFloat(float a,float b,float fOff)if (abs(a - b) < fOff)return 0;if

11、 ( a > b)return 1;elsereturn -1;void BspTree:SplitFace( int nFaceId, float fSplit, int nAxis, int* pLeftNum, int* pRightNum, int* pBothNum )face* pFace = GetFaceByID(nFaceId);int nLeftCount = 0;int nRightCount = 0;int nBothCount = 0;float t3;switch( nAxis )case Axis_X:t0 = pFace->P0.x;t1 = pFa

12、ce->P1.x;t2 = pFace->P2.x;break;case Axis_Y:t0 = pFace->P0.y;t1 = pFace->P1.y;t2 = pFace->P2.y;break;case Axis_Z:t0 = pFace->P0.z;t1 = pFace->P1.z;t2 = pFace->P2.z;break;for( int i = 0; i < 3; i+ )int c = CompareFloat( ti, fSplit ,0.001f);if( c < 0 )/ 左边nLeftCount+;else

13、 if( c > 0 )/ 右边nRightCount+;else/ 正中间nBothCount+;*pLeftNum = nLeftCount;*pRightNum = nRightCount;*pBothNum = nBothCount;void BspTree:SplitSpace(TreeNode* pRoot,int nAxis,int ndepth)if(!pRoot)return;pRoot->nDepth = ndepth;pRoot->Axis = nAxis;if (pRoot->vFaceId.size() < 3 | ndepth >

14、 2)pRoot->pLChild = NULL;pRoot->pRChild = NULL;return;pRoot->pLChild = new TreeNode;pRoot->pRChild = new TreeNode;pRoot->pLChild->box.Max = pRoot->box.Max;pRoot->pLChild->box.Min = pRoot->box.Min;pRoot->pRChild->box.Max = pRoot->box.Max;pRoot->pRChild->bo

15、x.Min = pRoot->box.Min;nAxis = (int)Axis_X;float XLength = pRoot->box.Max.x - pRoot->box.Min.x;float YLength = pRoot->box.Max.y - pRoot->box.Min.y;float ZLength = pRoot->box.Max.z - pRoot->box.Min.z;if (YLength > XLength)nAxis = Axis_Y;XLength = YLength;if (ZLength > XLeng

16、th)nAxis = Axis_Z;float fslit = 0.0f;switch (nAxis)case Axis_X:fslit = (pRoot->box.Max.x + pRoot->box.Min.x)/2.0;pRoot->pLChild->box.Max.x = fslit;pRoot->pRChild->box.Min.x = fslit;break;case Axis_Y:fslit = (pRoot->box.Max.y + pRoot->box.Min.y)/2.0;pRoot->pLChild->box.M

17、ax.y = fslit;pRoot->pRChild->box.Min.y = fslit;break;case Axis_Z:fslit = (pRoot->box.Max.z + pRoot->box.Min.z)/2.0;pRoot->pLChild->box.Max.z = fslit;pRoot->pRChild->box.Min.z = fslit;break;pRoot->Split = fslit;int nSize = pRoot->vFaceId.size();int nLeftCount,nRightCount

18、,nBothCount;for (int n = 0; n < nSize; +n)SplitFace(pRoot->vFaceId.at(n),fslit,nAxis,&nLeftCount,&nRightCount,&nBothCount);/ 如果左边有if( nLeftCount > 0 | nBothCount > 0 )pRoot->pLChild->vFaceId.push_back( pRoot->vFaceId.at(n) );if( nRightCount > 0 | nBothCount > 0 )pRoot->pRChild->vFaceId.push_back