Quadtree

들어가기에 앞서..

후...상당히 골머리를 싸맸던 파트중 하나.

이것만하면 되겠지!라고 했는데, 이게 아니라 옥트리를 봐야한다고 했을때의 그 짜증은..

여튼 쿼드트리는 상당히 중요한 알고리즘이라고 생각한다. 그렇게 여겨지고 있고 말이다.

제대로 설명할수 있을지 모르겠다. 최선을 다해서 설명하겠다.

1. 쿼드 트리란

쿼드 트리는 재귀적으로 공간을 4개로 분할하는 방식을 말한다.

이렇게 분할을 한다면 거대한 공간을 빠르게 검색할수 있기 때문이다. 사용하지 않는 노드(데이터)를 삭제함으로써, 처리해야할 데이터량을 빠르게 줄일 수 있기 때문이다.

특히 절두체 컬링과 결합한다면, 큰 효과를 볼수 있다.

1. 초기

2. 첫 번째 분할

3. 두 번째 분할

2. 쿼드트리 구현

쿼드 트리를 구현하는데 세 가지 데이터가 필요하다.

4개의 자식 노드를 가리킬 QuadTree*[4]와 노드의 센터값, 노드의 좌표값이 필요하다.

(솔직히 이건 왜 int[4]로 구현했는지 모르겠다. vector4나 plan으로 만들면 안되나??나중에 직접 만들때에는 얘네들을 따로 빼보고 싶다)

쿼드트리를 Build 시켜보자.

빌드를 하기전에, 분할이 계속 이루어져도 충분한지를 검사해야한다.

그것은 여러가지가 있겠지만, 우리는 노드의 우상단에서 좌상단을 뺀 값이 1보다 크다면 통과하는 방식을 쓰겠다.

이 검사를 하지 않지 않는다면, 재귀적 분할로 무한루프에 빠지고 말 것이다.

void QuadTree::QuadTreeBulid()

{

//etc..

//쿼드 트리의 분할이 가능한가?

if(m_corner[TR] - m_corner[TL] >= 1)    

{

//etc..

m_pChild[TL]->QuadTreeBulid();

m_pChild[TR]->QuadTreeBulid();

m_pChild[BL]->QuadTreeBulid();

m_pChild[BR]->QuadTreeBulid();

}

}

이 함수를 무사히 마친다면, '1. 쿼드 트리란'에서의 그림처럼 분할이 된다.

3. 그리기

쿼드트리의 분할을 무사히 마쳤다면, 이제 지형과 연계해서 필요한 인덱스를 그려야한다.

아직까지 컬링을 배우지는 않았기에 모든 인덱스를 그리겠다.

이 함수를 int GenTriIndex(int nTri, LPVOID pIndex)라고 하겠다.

마찮가지로 재귀적으로 추려내고, 렌더링할 버텍스의 수를 반환한다.

pIndex는 여기서 인덱스 버퍼가 된다. 즉, 인덱스 버퍼를 매개변수로 얻어와서 GenTriIndex에서 직접 QuadTree의 노드좌표값을 인덱스 버퍼에 등록한다.

int QuddTree::GenTrilIndex(int nTri, LPVOID pIndex)

{

//현재 노드의 출력이 가능한가?

if( m_corner[TR] - m_corner[TL] <= 1)

{

//좌측 상단 삼각형과 우측 하단 삼각형을 인덱스 버퍼에 등록

//m_cornet[]들을 등록함

nTri += 2;

return nTri;

}

//현재 노드가 출력이 되지 않는다면 출력되는 노드를 찾기 시작한다.

if( m_pChild[] != NULL ) //노드가 있다는 조건을 검사.

nTri = m_pChild->GenTriIndex(nTri, pIndex);

return nTri;

}

반환된 nTri값이 DrawIndexedPrimitive(D3DPT_TRIANGLELIST, 0, 0, m_cxDIB*m_czDIB, 0, nTri)에 전달된다.

참고자료 : 해골책