untitle_Programming

*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;

}

*Heightmap

- texture를 읽어와 texture의 크기 만큼 지형의 크기를 잡아주고

해당 픽셀의 음영값을 vertex의 높낮이로 정해준해준다.

*D3DCreateTextureFromFileEx()

- Heightmap texture를 LPDIRECT3DTEXTURE9 com객체에 메모리를 할당하여 texture 정보를 읽어온다.

*D3DSURFACE_DESC 구조체

- LPDIRECT3DTEXTURE9의 GetLevelDesc() 함수를 이용하여

D3DSURFACE_DESC구조체에 texture정보를 추출한다.

- texture의 width와 height는 2^n의 수로 변환되며

본래 texture의 크기가 2^n보다 클경우 log_2( size ) = k, 2^(k+1)로 변환한다.

*D3DLOCKED_RECT 구조체

- texture에 lock을 걸어 pixel정보에 접근할 수 있게 한다.

- .pBits : pixel정보를 가지고있는 포인터로 첫 주소를 가리킨다.

- .Pitch : 한 열의 길이

*의사 코드

LPDIRECT3DTEXTURE9 pTex = NULL;

D3DCreateTextureFromFileEx( pDevice, pszPath, D3DX_DEFAULT, D3DX_DEFAULT, D3DX_DEFAULT, 0

, D3DFMT_X8R8G8B8, D3DPOOL_MANAGED, D3DX_DEFAULT, D3DX_DEFAULT, 0, NULL, NULL, &pTex );

D3DSURFACE_DESC ddsd;

pTex->GetLevelDesc( 0, &ddsd );

POINT ptSize;

ptSize.x = ddsd.Width;

ptSize.y = ddsd.Height;

D3DLOCKED_RECT ddlr;

pTex->LockRect( 0, &ddlr, NULL, D3DLOCK_READONLY );

DWORD dwRowPixelSize = ddlr.Pitch / 4;

//반복문을 사용하여 픽셀의 포인터를 갱신한다.

for( int iZ = 0; iZ < ptSize.z; ++iZ )

{

for( int iX = 0; iX < ptSize.x; ++iX )

{

//해당 픽셀의 주소 계산

DWORD dwPixel = *( (LPDWORD)ddlr.pBits + iX + iZ * dwRowPixelSize );

//필요정보는 픽셀의 색상이 아니라 음영값이므로

//0x000000ff와 비트& 연산을 하여 한 byte값(blue value)을 구한다.

float fHeight = (float)( dwPixel & 0x000000ff );

}

}

pTex->UnlockRect( 0 );

pTex->Release();

(1).한 물체의 한 변을 축으로 정한다( 평행하는 변은 제외 )

(2).축 기준으로 축이된 변의 정사영의 길이, 축 기준으로 다른 물체의 변들(평행하는 변은 제외)의 정사영의 길이를 더한다.

(3-1).두 물체간의 거리 * 2 가 구한 모든 정사영의 길이의 합보다 작다면 두 물체는 충돌 가능성이 있다.

(3-1-1). 다른 변을 축으로 (1) ~ (3 -1) 을 반복한다.

(3-2).단 한 변이라도 두 물체간의 거리 * 2 가 구한 모든 정사영의 길이의 합보다 크다면 두 물체는 충돌 하지 않았다.