BSP 分割空間實現(xiàn)

1、BSP:二叉分割樹，是一種分割場景的方法，下面代碼是BSP樹一種實現(xiàn)可運行：運行例子中，將定義的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,;/樹節(jié)點的

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類的定義實現(xiàn)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<<"節(jié)點深度: "<<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