BSP 트리 ( bsp tree ) - 05

 

bsp 트리 ( bsp tree ) - 소스 코드

 

 

Vector4 - float x, y, z, w

 

 

//1. bsp 트리 생성

//재귀호출

void Make_Tree( BSPTree* _pT, Vector4* _pV, int _iCount )
{
 Vector4 vBox[2];

 vBox[0] = vBox[1] = _pV[0];

 //제일 작은 값과 제일 큰 값을 구한다
 for( int i=0; i<_iCount; i++ )
 {
  //min
  if( vBox[0].x > _pV[i].x )
  {
   vBox[0].x = _pV[i].x;
  }
  if( vBox[0].y > _pV[i].y )
  {
   vBox[0].y = _pV[i].y;
  }
  if( vBox[0].z > _pV[i].z )
  {
   vBox[0].z = _pV[i].z;
  }

  //max
  if( vBox[1].x < _pV[i].x )
  {
   vBox[1].x = _pV[i].x;
  }
  if( vBox[1].y < _pV[i].y )
  {
   vBox[1].y = _pV[i].y;
  }
  if( vBox[1].z < _pV[i].z )
  {
   vBox[1].z = _pV[i].z;
  }
 }

 

 //트리 노드에서의 가장 큰 값을 미리 저장 ( 나중, 검색을 위해서 )

 float fRadius = 0.f;

 

 if( _iCount > 1 )
 {
  //가장 값차이가 큰 축( 가장 값 범위가 넓은 )으로 정렬 시킨다
  vBox[1] -= vBox[0];
  if( vBox[1].x > vBox[1].y && vBox[1].x > vBox[1].z )
  {
   qsort( _pV, _iCount, sizeof(Vector4), _sortPos_X );
   fRadius = sqrtf( vBox[1].x * vBox[1].x ) * 0.5f;
  }
  else if( vBox[1].y > vBox[1].z )
  {
   qsort( _pV, _iCount, sizeof(Vector4), _sortPos_Y );
   fRadius = sqrtf( vBox[1].y * vBox[1].y ) * 0.5f;
  }
  else
  {
   qsort( _pV, _iCount, sizeof(Vector4), _sortPos_Z );
   fRadius = sqrtf( vBox[1].z * vBox[1].z ) * 0.5f;
  }
 }

 

 //인덱스
 int iHalf = _iCount/2;
 Vector4* pPtr = NULL;

 //leaf
 if( _iCount == 1 )
 {

  BSPTree* pNew = new BSPTree();
  pNew->pVal = &(_pV[ 0 ]); //재귀호출을 통해, 포인터가 이동하므로,
                                         //배열의 갯수가 1 일때는 항상 [0]번째 요소.
  _pT->pLeaf = pNew;

  return;
 }

 

 //front
 if( iHalf > 0 )
 {
  //
  BSPTree* pNew = new BSPTree();
  pNew->pVal = &(_pV[ iHalf ]);
  pNew->fRad = fRadius;

  //
  _pT->pFront = pNew;

  pPtr = &(_pV[ iHalf + 1 ]);
  Make_Tree( pNew, pPtr, _iCount - iHalf - 1 );
 }
 
 //back
 if( iHalf > 0 )
 {
  BSPTree* pNew = new BSPTree();
  pNew->pVal = &(_pV[ iHalf - 1 ]);
  pNew->fRad = fRadius;

  //
  _pT->pBack = pNew;
  
  pPtr = &(_pV[0]);
  Make_Tree( pNew, pPtr, iHalf - 1 );
 }

 

}

 

 

//sort

static int _sortPos_X( const void *pa, const void *pb )
{
 Vector4 *p1 = (Vector4*)pa;
 Vector4 *p2 = (Vector4*)pb;
 
 if( p1->x < p2->x ) // return -1 : 리스트 맨 왼쪽(앞쪽)에 정렬된다
  return -1;

 if( p1->x > p2->x )
  return 1;
 
 return 0;
}

static int _sortPos_Y( const void *pa, const void *pb )
{
 Vector4 *p1 = (Vector4*)pa;
 Vector4 *p2 = (Vector4*)pb;
 
 if( p1->y < p2->y ) // return -1 : 리스트 맨 왼쪽(앞쪽)에 정렬된다
  return -1;

 if( p1->y > p2->y )
  return 1;
 
 return 0;
}

static int _sortPos_Z( const void *pa, const void *pb )
{
 Vector4 *p1 = (Vector4*)pa;
 Vector4 *p2 = (Vector4*)pb;
 
 if( p1->z < p2->z ) // return -1 : 리스트 맨 왼쪽(앞쪽)에 정렬된다
  return -1;

 if( p1->z > p2->z )
  return 1;
 
 return 0;
}