BSP 트리 ( bsp tree ) - 03

 

bsp 트리 ( bsp tree ) - 노드 구성 03

 

일단
BSP 구조체로 생성되어
등록된 값들은

당연히,
추가적인 트리구성에서
제외되어야 합니다.

 

(이렇게 하지 않으면,
하나의 값들이 이중,삼중으로 여러 트리에 포함되게 될 것입니다.)

 

즉,
남아있는 값들만을 가지고,
다시 영역을 쪼개어야 합니다.

 

남아있는 값들은
재귀호출을 통해 다시 분할할 수 있습니다.

02 장에서 설명된 코드에는
재귀호출에 대한 부분이 생략되어 있습니다.

 

재귀호출을 포함하여,
남아있는 값들을 쪼개어 보겠습니다.

 

Vector3 로 테스트 하다가,

w 값을 추가해주기 위해서 Vector4 로 수정하였습니다만,

그냥 Vector3 과 동일하다 생각하시면 될 듯 합니다.

 

//BSP 트리를 생성하는 함수입니다.
void Make_Tree( BSP* _pT, Vector4* _pV, int _iCount )
{

         
   //영역을 구하는 부분
   ....

  

   //x,y,z 축에 대한 정렬
   ....

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

 

 //front
 if( iHalf > 0 )
 {
  //
  BSP* pNew = new BSP();
  pNew->pVal = &(_pV[ iHalf ]);
  _pT->pFront = pNew;

 

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

}

 

 

Make_Tree() 는

인덱스로 배열을 분할해서 재귀호출을
시켜주는 함수입니다.

 

 

front 는

 

pPtr = &(_pV[ iHalf + 1 ]);
Make_Tree( pNew, pPtr, _iCount - iHalf - 1 );

 

-> 포인터연산을 해서 배열에서의 포인팅 위치를 옮깁니다.
-> pVal[0]을 가르키던 포인터가 pVal[ iHalf + 1 ]을 가르키게 옮겼습니다.
-> pVal[ iHalf + 1 ] ~ pVal[ MaxIndex ] 에 해당하는 값들을 다시 분할하려 합니다.
-> 현재로는 이렇게 남습니다.
-> pVal[3], pVal[4]

-> 재귀호출로 다시 분할

 

 

back 은

 

pPtr = &(_pV[0]);
Make_Tree( pNew, pPtr, iHalf - 1 );

-> 포인터연산을 해서 배열에서의 포인팅 위치를 옮깁니다.
-> 포인터는 가장 작은값 pVal[0]을 가르킵니다.
-> pVal[0] ~ pVal[ iHalf - 1 ] 에 해당하는 값들을 다시 분할하려 합니다.
-> 현재로는 이렇게 남습니다.
-> pVal[0]

-> 재귀호출로 다시 분할( 값이 하나이기 때문에, 재귀 호출시 빠져 나옵니다 )

 

 

즉,

 

front 는 이렇게

 

C -> front -> ( Set Value E )
       back -> ( Set Value D )

 

back 에서는 값이 하나밖에 남지 않았습니다.

 

B -> front -> ( Set Value A )
       back -> ( Set Value A )

 

A 는
front 나 back 어느 쪽에 포함시켜도 좋을 듯 합니다만,
저는, 값 확인이 쉽게
leaf 를 하나 더 추가하였습니다.

struct BSP
{
 BSP()
 {
  pFront = NULL;
  pBack = NULL; 
 }

 BSP pFront;
 BSP pBack; 

 Vector3* pVal; //오브젝트 클래스 포인터
                      //지금은 벡터값만 있으므로,,,,

 

 BSP pLeaf;     //값이 하나만 남아, 더 이상 쪼갤수 없을때,,,,
}

 

//BSP 트리를 생성하는 함수입니다.
void Make_Tree( BSP* _pT, Vector4* _pV, int _iCount )
{

         
   //영역을 구하는 부분
   ....

  

   //x,y,z 축에 대한 정렬
   ....

    

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

 //분할할 수 없을때, 그냥 leaf 로 등록....
 //leaf
 if( _iCount == 1 )
 {

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

  return;
 }

 //front
 if( iHalf > 0 )
 {
  //
  BSP* pNew = new BSP();
  pNew->pVal = &(_pV[ iHalf ]);
  _pT->pFront = pNew;

 

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

}

 

 

 

 

D, E 사이가 분할( D | E )되고,

A 는 하나밖에 없으므로, leaf 로 등록됩니다.

 

트리 구성표로 나타낸다면,

C -> front -> ( Set Value E )
       back -> ( Set Value D )

B -> leaf -> ( Set Value A )
    

이렇게 됩니다.

 

5개의 배열값에 대한 전체 트리 구성표는

 
(Top) -> front -> (C) -> front -> (E)
                                 back -> (D)

            back -> (B) -> leaf -> (A)
                     

이렇게 되었습니다.

 

 

트리 구성표에서의 -> 표시는
코드상으로는
BSP 구조체의 pVal 에 값을 할당한 것과
같습니다.