쿼드트리 ( QuadTree )

 

*QuadTree

- 부모의 노드가 4개의 자식 노드를 가진다.

- terrain의 경우 index를 정보로 가진다.

- 1. 전체를 표현할 수 있는 4개의 index를 가진 root노드로 부터 자식 노드가 파생된다.

2. 자신을 4분할 하여 각각의 노드들이 자신의 index를 가진다.

3. 더이상 분할 할 수 없을 때 까지 2.를 재귀적으로 반복한다.

 

 

 

root노드로부터 4개의 자식노드가 파생되어 그 4개의 자식노드들도 각각 4개씩의 자식을 갖는다.

( 더이상 나눌 수 없을 때 까지 )

 

 

 

*terrain에 quadtree만 적용시 속도적 측면에서 오히려 손해를 본다.

quadtree를 활용하려면 FrustumCulling과 함께 사용하자.

 

*의사코드

class CTerQuadTree;

 

private:

//자식노드 멤버변수

CTerQuadTree* m_ar_pChild[4];

//index를 저장할 멤버변수

DWORD m_ar_dwCorner[4];

 

//root 생성 메소드

VOID CTerQuadTree::CreateQuadTree( int _iWidth, int _iHeight )

{

//root index 생성

DWORD ar_dwIndex[4] =

{

0,

_iWidth- 1,

_iWidth* ( _iHeight - 1 ),

_iWidth* _iHeight - 1

};

 

//m_ar_dwCorner배열에 index 저장

CTerQuadTree::_SetupIndex( ar_dwIndex[0], ar_dwIndex[1], ar_dwIndex[2], ar_dwIndex[3] );

 

//quadtree 생성

CTerQuadTree::_Build();

}

 

//build를 재귀호출하여 자식노드를 할당한다.

VOID CTerQuadTree::_Build()

{

//나눌 수 있다면 자식노드 build

if( CTerQuadTree::_SubDivide() )

{

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

m_ar_pChild[i]->_Build();

}

}

 

//더 나눌 수 있는지 검토한 후 index를 생성할수있는 데이터를 인자로 넘겨주며 자식 노드를 생성한다.

BOOL CTerQuadTree::_SubDivide()

{

if( ! CTerQuadTree::_IsDivisible() )

return FALSE;

 

DWORD dwTopCen, dwBotCen, dwLefCen, dwRigCen;

 

dwTopCen = ( m_ar_dwCorner[COR_TR] + m_ar_dwCorner[COR_TL] ) / 2;

dwBotCen = ( m_ar_dwCorner[COR_BR] + m_ar_dwCorner[COR_BL] ) / 2;

dwLefCen = ( m_ar_dwCorner[COR_TL] + m_ar_dwCorner[COR_BL] ) / 2;

dwRigCen = ( m_ar_dwCorner[COR_TR] + m_ar_dwCorner[COR_BR] ) / 2;

 

m_ar_pChild[COR_TL] = CTerQuadTree::_CreateChild( m_ar_dwCorner[COR_TL], dwTopCen, dwLefCen, m_dwCenter );

m_ar_pChild[COR_TR] = CTerQuadTree::_CreateChild( dwTopCen, m_ar_dwCorner[COR_TR], m_dwCenter, dwRigCen );

m_ar_pChild[COR_BL] = CTerQuadTree::_CreateChild( dwLefCen, m_dwCenter, m_ar_dwCorner[COR_BL], dwBotCen );

m_ar_pChild[COR_BR] = CTerQuadTree::_CreateChild( m_dwCenter, dwRigCen, dwBotCen, m_ar_dwCorner[COR_BR] );

 

 

return TRUE;

}