BSP 트리 ( bsp tree ) - 02

 

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

 

 

많은 수의 오브젝트가 있을때

그리고 이 오브젝트들이 각각의 다른 포지션을

가진다고 가정할때,

이 오브젝트들의 집합을 

bsp tree 로 구성하기 위해서
테스트 중입니다.

bsp 노드 구성에는 다양한 방법이 있습니다,
밑에 설명되는 코드들은

GameGems5 권에서
Widget 의 BspTree 부분을 참고하여,
구성해 본 것입니다.

 

테스트 코드이므로,
오브젝트는 심플하게
위치값(x,y,z)만을 가집니다.

 

class Vector3
{
 float x,y,z; //포지션

 ....
}

 

Vector3* pVal = new pVal[5];
for( int i=0; i<5; i++ )
{
 pVal[i] = Vector3( i, 0, 0 );
}

 

x 값만이 다른 오브젝트들이 쭉 있다고 가정합니다.
( 심플하게 ^^ )

밑에 설명되는 이미지의
알파벳들과의 관계는

 

pVal[0] = A,
pVal[1] = B,
pVal[2] = C,
pVal[3] = D,
pVal[4] = E,

 

이렇게 되겠지요.

 

 

 

 

이론상으로는
영역을 나눌때는
항상 최소값과 최고값을 구해서
그 중간값으로 나누어 주게 됩니다.( 이렇게 해야 제외되는 오브젝트가 없겠지요. )

 

코드상으로는
배열의 인덱스를 나누어 줍니다.
(최소값을 가지는 값은 배열의 0번째 요소에,
최고값을 가지는 값은 맨마지막 요소에 들어 있어야 합니다.)

이렇게하면 노드에 오브젝트를 직접 포인팅 해주기 쉬워집니다.

int iHalfIndex = 현재갯수/2;
iHalfIndex = 5/2;

 

pVal 배열 중에서는 중심값이
pVal[ iHalfIndex ] 가 되었습니다.
현재 있는 배열 중에서, 가장 중심값입니다.

이 값을 bsp node 에 지정해 줍니다.

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

 BSP pFront;
 BSP pBack; 

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

 

//최상위 탑노드
BSP* pTop  = new BSP;

 

//front 생성
BSP* pNew  = new BSP;
pNew->pVal = &(pVal[ iHalfIndex ]);

 

//top 에 front 지정
pTop->pFront = pNew;

pVal[ iHalfIndex ] 을 front 노드로 구성하였으므로,
pVal[ iHalfIndex - 1 ] 은
back 노드로 구성하겠습니다.

//back 생성
BSP* pNew  = new BSP;
pNew->pVal = &(pVal[ iHalfIndex - 1 ]);

 

//top 에 back 지정
pTop->pBack = pNew;

pTop 에 front 와 back 노드가 생겼습니다.
front 의 값은 pVal[ 2 ]
back 의 값은 pVal[ 1 ]
이 되었습니다.

노드 구성표 상으로는,

 

Top -> front -> (Set Value C)
      -> back -> (Set Value B) 

 

이렇게 되었습니다.

 

 

 

 

 

 

그림으로는 이렇게 설명이 될 듯합니다.

B 와 C 사이를 구분하는 구분선이 놓여졌습니다만,

 

코드상으로는

특별한 값은 없고,

BSP 트리가 나뉘는 분기점( front 와 back 이 생기는 )이라고

생각하시면 될 듯 합니다.

 

 

그리고,
아직 노드 구성이 되지 않은,

 

pVal[0], pVal[3], pVal[4]

= A, D, E

 

의 값이 남았습니다.

 

 

----------------------------------------------------------------

 

내부지형 알고리즘에 사용하는
bsp tree 의 경우는 평면의 앞쪽, 뒤쪽으로
구분이 명확하니,
front, back 의 뜻이 확실하지만,

 

위 코드에서의
front, back 의 용어는
포지션의 앞,뒤라는 뜻은 아닙니다.( 그냥 편의상 사용 )
포지션에서는 축을 어디에 두는 가에 따라( x, y, z 축 )
front 와 back 의 방향이 계속 바뀌게 됩니다.