Direct X - 쿼드트리

쿼드트리의 정의

사분트리 

자식노드가 4개인 트리

쿼드트리는 공간을 4개의 자식노드로 재귀적 분할하는 방법이다.

한 공간을 1/4로 계속 분할한다.

하나였던 지형이 1/4로 분할, 2단계에서 다시 또 1/4로 분할, 3단계에서 또 1/4로 분할..

이러다가 일정 크기 이하로 줄어들면 분할을 멈추는 것.

쿼드트리의 효과

쿼드트리를 사용하는 가장 큰 이유는 거대한 지형을 빠르게 검색할 수 있기 때문이다.

따라서, 큰 덩어리 단위로 필요없는 데이터를 제거함으로써, 3D엔진이 처리해야할 데이터량을 빠르게 줄일 수 있다. 이를 위해서 반드시 쿼드트리가 절두체 컬링과 결합되어야만 제 성능을 발휘할 수 있으므로, 요고 다음예제에서는 

절두체 컬링 + 쿼드트리를 해보자

이전 지형맵의 코드에 비해 지형관리 클래스도 추가되고 바뀐점이 많다

우선 클래스 위주로 보자

쿼드트리의 구현

class ZQuadTree

{

/// 쿼드트리에 보관되는 4개의 코너값에 대한 상수값

enum CornerType { CORNER_TL, CORNER_TR, CORNER_BL, CORNER_BR };

private:

ZQuadTree* m_pChild[4]; /// QuadTree의 4개의 자식노드

int m_nCenter; /// QuadTree에 보관할 첫번째 값

int m_nCorner[4]; /// QuadTree에 보관할 두번째 값

///    TopLeft(TL)      TopRight(TR)

///              0------1

///              |      |

///              |      |

///              2------3

/// BottomLeft(BL)      BottomRight(BR)

private:

/// 자식 노드를 추가한다.

ZQuadTree* _AddChild( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR );

/// 4개의 코너값을 셋팅한다.

BOOL _SetCorners( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR );

/// Quadtree를 4개의 하위 트리로 부분분할(subdivide)한다.

BOOL _SubDivide();

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

BOOL _IsVisible() { return ( m_nCorner[CORNER_TR] - m_nCorner[CORNER_TL] <= 1 ); }

/// 출력할 폴리곤의 인덱스를 생성한다.

int _GenTriIndex( int nTriangles, LPVOID pIndex );

/// 메모리에서 쿼드트리를 삭제한다.

void _Destroy();

public:

/// 최초 루트노드 생성자

ZQuadTree( int cx, int cy );

/// 하위 자식노드 생성자

ZQuadTree( ZQuadTree* pParent );

/// 소멸자

~ZQuadTree();

/// QuadTree를 구축한다.

BOOL Build();

/// 삼각형의 인덱스를 만들고, 출력할 삼각형의 개수를 반환한다.

int GenerateIndex( LPVOID pIB );

};

현재 쿼드트리 클래스는 쿼드트리가 점유할 지형의 크기를 생성자를 통해서 입력한 뒤 Build()함수를 호출하면 내부적인 재귀호출을 통해서 쿼드트리를 생성하게 되어있다.

이 때, 생성할 지형의 크기는 반드시 2^n+1이어야만 한다, 그 외의 크기는 쿼드트리로 분할이 되지 않으므로 주의해야한다.

현재 쿼드트리를 하위분할하면서 쿼드트리 각각의 노드에 저장하는 값은 정점의 인덱스 정보다. 최종적으로 우리는 정점의 인덱스 정보를 가지고 지형을 그릴 것이기 때문이다, 편의상 4개의 귀퉁이 정보 외에도 중앙 값도 저장하고 있다.

 

129*129크기인 지형일 경우 노드에 저장되는 인덱스 값의 예를 든 것이다.

지형관리 클래스

전에 했던 예제와는 다르게 이제부터 지형을 다루기 위한 전문 클래스를 만들었다

지금까지 우리는 정점버퍼와 인덱스버퍼, 그리고 지형의 높이 맵 정보들을 직접 메인함수에서 가지고 있었지만, 이제부터는 쿼드트리와의 결합의 편리성을 고려해 따로 ZTerrain이라는 클래스로 분리해야만 한다.

class ZTerrain

{

private:

int m_cxDIB; /// DIB의 가로픽셀수

int m_czDIB; /// DIB의 세로픽셀수

int m_cyDIB; /// DIB의 최대높이값(즉 0 ~ 255사이의 값)

D3DXVECTOR3 m_vfScale; /// x scale, y scale, z scale

TERRAINVERTEX* m_pvHeightMap; /// 높이맵의 정점배열

LPDIRECT3DDEVICE9 m_pd3dDevice; /// 출력용 D3D디바이스

LPDIRECT3DTEXTURE9 m_pTex[MAX_TERRAIN_TEX]; /// 텍스처

LPDIRECT3DVERTEXBUFFER9 m_pVB; /// 지형출력용 정점버퍼

LPDIRECT3DINDEXBUFFER9 m_pIB; /// 지형출력용 인덱스버퍼

int m_nTriangles; /// 출력할 삼각형의 개수

ZQuadTree* m_pQuadTree; /// 쿼드트리 객체의 포인터

public:

// 생성과 관련된 함수들

ZTerrain();

~ZTerrain();

/**

 * @brief 지형객체를 초기화한다.

 * @param pDev : 출력용 D3D디바이스 

 * @param pvfScale : 높이맵의 x,y,z값에 곱할 척도값(scale vector)

 * @param lpBMPFilename : 높이맵용 BMP파일명

 * @param lpTexFilename : 출력용 D3D디바이스 

 */

HRESULT Create( LPDIRECT3DDEVICE9 pDev, D3DXVECTOR3* pvfScale, LPSTR lpBMPFilename, LPSTR lpTexFilename[MAX_TERRAIN_TEX] );

// ZTerrain내부에서 사용되는 함수들

private:

/// 지형객체를 메모리에서 소거한다.

HRESULT _Destroy();

/// 지형객체에서 사용할 텍스처를 읽어들인다.

HRESULT _LoadTextures( LPSTR lpTexFilename[MAX_TERRAIN_TEX] );

/// BMP파일을 열어서 높이맵을 생성한다.

HRESULT _BuildHeightMap( LPSTR lpFilename );

/// BMP파일의 크기에 맞춰서 쿼드트리를 생성한다.

HRESULT _BuildQuadTree();

/// 정점, 인덱스 버퍼를 생성한다.

HRESULT _CreateVIB();

/// 화면에 지형을 출력한다.

HRESULT _Render();

public:

/// x, z위치의 정점값을 얻어낸다.

TERRAINVERTEX* GetVertex( int x, int z ) { return (m_pvHeightMap+x+z*m_cxDIB); }

/// x, z위치의 높이(y)값만 얻어내다.

float GetHeight( int x, int z ) { return (GetVertex( x, z ))->p.y; }

/// 높이맵 BMP파일의 가로픽셀수

int GetCXDIB() { return m_cxDIB; }

/// 높이맵 BMP파일의 가로픽셀수

int GetCZDIB() { return m_czDIB; }

/// 높이맵의 실제 x축 폭(column)값

float GetCXTerrain() { return m_cxDIB * m_vfScale.x; }

/// 높이맵의 실제 y축 높이(height)값

float GetCYTerrain() { return m_cyDIB * m_vfScale.y; }

/// 높이맵의 실제 z축 길이(row)값

float GetCZTerrain() { return m_czDIB * m_vfScale.z; }

/// 화면에 지형을 출력한다.

HRESULT Draw();

};

최초로 객체를 생성한 다음 Create()함수에서 높이 맵으로 사용될 BMP 파일과 텍스쳐 정보를 입력받아 지형정보를 생성하게 된다.

_BuildHeightMap() 함수에서 높이맵을 생성하는 소스를 살펴보면 알겠지만, 높이맵의 가로와 세로 크기가 2^n+1이 아닌 경우에는 E_FAIL을 리턴하도록 구성하면 좋을것이다, 

현재 ZTerrain 클래스는 Draw()함수를 호출해서 지형을 그리는데, Draw()함수는 아래와같다.

/// 화면에 지형을 출력한다.

HRESULT ZTerrain::Draw()

{

LPDWORD pI;

    if( FAILED( m_pIB->Lock( 0, (m_cxDIB-1)*(m_czDIB-1)*2 * sizeof(TRIINDEX), (void**)&pI, 0 ) ) )

        return E_FAIL;

m_nTriangles = m_pQuadTree->GenerateIndex( pI );

    m_pIB->Unlock();

// g_pLog->Log( "Triangles=%d", m_nTriangles );

_Render();

return S_OK;

}

Lock()함수로 인덱스 버퍼의 포인터를 얻어 낸 후 쿼드트리로부터 출력할 삼각형의 인덱스 버퍼를 얻어낸다, 그리고 다시 인덱스 버퍼의 Unlock()을 호출 한 뒤, 쿼드트리에서 생성한 인덱스 버퍼의 내용으로 DrawIndexedPrimitive() 함수를 사용하여 지형정보 삼각형을 그려준다. ZTerrain 클래스는 높이 맵을 읽어서 정점버퍼와 인덱스버퍼를 만들고, 쿼드트리를 내부에 갖고있다. 앞으로는 쿼드트리 클래스를 향상시켜 좀 더 다양하면서도 효율적인 지형처리 기법을 사용해보자

Dib.h, Dib.cpp에 대해

이번에는 BMP파일을 사용하기 위해 BMP를 전문으로 다루는 소스를 사용하였다.

BMP파일은 특성상 가장 간단한 구조를 갖고 있음에도 불구하고 몇가지 제한사항 때문에 다루기가 까다로운 것 또한 사실이다. 실제 개발시에는 DevIL처럼 공개되어있는 그래픽 라이브러리, 혹은 LeadTool같은 상용툴을 사용해도 무방하지만, BMP파일을 직접 다루어보는 것도 좋은 경험이 될것이라 생각되어 소개한 소스다.

구현화면은 전과 동일하다

단지 속도향상이 있다는건데 

전 소스나 쿼드트리나 어차피 내 컴에서는 뭐로가도 무리없는 소스이기때문에

특별한 속도향상은 느끼질 못하겠다.

 - 그래도 성능향상을 위해 필요하다는 거