首页 > 代码库 > 几种空间分割算法研究之bsp

几种空间分割算法研究之bsp

 

BSP:

二叉分割树,是一种分割场景的方法,下面代码是BSP树一种实现可运行:

运行例子中,将定义的16个空间面,分割为一个深度是3的BSP树,上图显示的是运行结果:

#include "stdafx.h"

#include <map>

#include <vector>

#include <iostream>

using namespace std;

//定义空间的点结构

struct point

{

     float x,y,z;

     point():x(0.0f),y(0.0f),z(0.0f){};

     point(float a,float b,float c):x(a),y(b),z(c){}

     void operator += (int n)

     {

         x += n;

         y += n;

         z += n;

     }

     void operator = (point& p)

     {

         memcpy(this,(void*)&p,sizeof(*this));

     }

};

//定义空间的面结构

struct face

{

     point P[3];

     void operator +=(int n)

     {

         P[0] += n;

         P[1] += n;

         P[2] += n;

     }

};

//定义包围盒结构

struct BBox

{

     point Min;

     point Max;

     BBox():Min(),Max(){}

};

enum EAxis

{//沿的轴枚举

     Axis_X,

     Axis_Y,

     Axis_Z,

};

//树节点的定义

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)

{

     std::map<int,face>::iterator itr = m_mFace.find(nID);

     if (itr != m_mFace.end() )

     {

         return &(m_mFace[nID]);

     }

     return NULL;

}

//BSP类的定义实现

class BspTree

{

public:

     BspTree():m_pRoot(NULL){};

     ~BspTree()

     {

         if (m_pRoot)

         {

              DeleteNode(m_pRoot);

         }

     }

     //初始化树根

     void InitTreeRoot(TreeNode *pNode);

     //释放整个树的资源

     void DeleteNode(TreeNode * pNode);

     //生成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::InitTreeRoot(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->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轴分割"<<"分割点是: 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,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->P[m].x > Max.x)

                    Max.x = pFa->P[m].x;

              if (pFa->P[m].y > Max.y)

                   Max.y = pFa->P[m].y;

              if (pFa->P[m].z > Max.z)

                   Max.z = pFa->P[m].z;

 

              if (pFa->P[m].x < Min.x)

                   Min.x = pFa->P[m].x;

              if (pFa->P[m].y < Min.y)

                   Min.y = pFa->P[m].y;

              if (pFa->P[m].z < Min.z)

                   Min.z = pFa->P[m].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 ( a > b)

         return 1;

     else

         return -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 t[3];

     switch( nAxis )

     {

     case Axis_X:

         t[0] = pFace->P[0].x;

         t[1] = pFace->P[1].x;

         t[2] = pFace->P[2].x;

         break;

     case Axis_Y:

         t[0] = pFace->P[0].y;

         t[1] = pFace->P[1].y;

         t[2] = pFace->P[2].y;

         break;

     case Axis_Z:

         t[0] = pFace->P[0].z;

         t[1] = pFace->P[1].z;

         t[2] = pFace->P[2].z;

         break;

     }

     for( int i = 0; i < 3; i++ )

     {

         int c = CompareFloat( t[i], fSplit ,0.001f);

 

         if( c < 0 )            // 左边

              nLeftCount++;

         else 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 > 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->box.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 > XLength)

     {

         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.Max.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,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( pRoot->vFaceId.at(n) );

     }

     pRoot->vFaceId.clear();

     // 递归

     SplitSpace( pRoot->pLChild, nAxis , ndepth+1);

     SplitSpace( pRoot->pRChild, nAxis , ndepth+1);

}

int _tmain(int argc, _TCHAR* argv[])

{

     BspTree bspTree;

     TreeNode *pRoot = new TreeNode;

     face fa;

     fa.P[0].x = -10;fa.P[0].y = -10;fa.P[0].z = -10;

     fa.P[1].x = 2;fa.P[1].y = 2;fa.P[1].z = 2;

     fa.P[2].x = 5;fa.P[2].y = 5;fa.P[2].z = 5;

     for (int n = 0; n < 16; ++n)

     {

         if (n % 5 == 0)

              fa += 2*(-n);

         else

              fa += 2*n;

         m_mFace[n] = fa;

         pRoot->vFaceId.push_back(n);

     }

     bspTree.InitTreeRoot(pRoot);

     bspTree.BuildAABB(pRoot);

     bspTree.SplitSpace(pRoot,0,0);

     bspTree.ErgodicTree(pRoot);

 

     getchar();

     return 0;}