vincent1@chollian.net 문 성 원 3D Game Programming QuadTree Culling vincent1@chollian.net 문 성 원 KoreaIT 전문학교 게임학과

Division of Game Development QuadTree 거대한 지형을 빠르게 검색할 수 있다. 1단계 트리 구성 Point 프러스텀 컬링시 전체 데이터 검색이 아니라 큰 덩어리 단위로 필요 없는 데이터를 제거 하여 데이터 량을 줄인다. 2단계 트리 구성 Korea IT Division of Game Development

Division of Game Development QuadTree 생성 n 생성할 지형의 크기는 2 + 1 ( 예 129 x 129 높이 맵을 생성해야 한다) 정사각형의 지형을 단계적으로 트리 형태로 구성한다. 128 Point 정점의 인덱스를 쿼드 트리로만든다. 128 16512 16640 0 64 8250 8320 64 128 8320 8384 8256 8320 16512 16576 8320 8384 16576 16640 8256 8384 8320 129*(128-1) = 16512 129*129 = 16640 Korea IT Division of Game Development

Division of Game Development QuadTree 컬링 n 곙계구를 이용하여 절두체 컬링을 수행하고 절두체에 포함되지 않은 부모 노드를 제거하면 자동으로 자식 노드도 제거된다. 128 Point 쿼드 트리의 특성을 이용하여 상당히 큰 영역을 한꺼번에 그릴때 제외 시킬수 있다. 제거 제거 8256 제거 8384 8320 화면의 프러스템 129*(128-1) = 16512 129*129 = 16640 Korea IT Division of Game Development

Division of Game Development 구현 1) 지형생성을 위한 객체 생성 HRESULT InitObjects() { LPSTR tex[4] = { "tile2.tga", "", "", "" }; D3DXVECTOR3 vScale; vScale.x = vScale.z = 1.0f; vScale.y = 0.1f; g_pLog = new ZFLog( ZF_LOG_TARGET_WINDOW ); g_pCamera = new ZCamera; g_pFrustum = new ZFrustum; g_pTerrain = new ZTerrain; g_pTerrain->Create( g_pd3dDevice, &vScale, BMP_HEIGHTMAP, tex ); return S_OK; } 지형의 격자간 크기, 높이맵 용 이미지, 텍스쳐를 넘긴다. Korea IT Division of Game Development

Division of Game Development 구현 2) 정점을 셋팅하고 쿼드 트리를 생성 HRESULT ZTerrain::Create( LPDIRECT3DDEVICE9 pDev, D3DXVECTOR3* pvfScale, LPSTR lpBMPFilename, LPSTR lpTEXFilename[4] ) { m_pd3dDevice = pDev; m_vfScale = *pvfScale; if( FAILED( _BuildHeightMap( lpBMPFilename ) ) ) { _Destroy(); return E_FAIL; } // 정점 생성 if( FAILED( _LoadTextures( lpTEXFilename ) ) ) { _Destroy(); return E_FAIL; } // 텍스쳐 로드 if( FAILED( _CreateVIB() ) ) { _Destroy(); return E_FAIL; } // 버텍스,인덱스버퍼 m_pQuadTree = new ZQuadTree( m_cxDIB, m_czDIB ); // 정점의 인덱스를 트리로 구성 if( FAILED( _BuildQuadTree() ) ) { _Destroy(); return E_FAIL; } return S_OK; } 하이트 맵용 점점과 인덱스를 구성 인덱스의 경우 버퍼만 생성 쿼드 트리 생성 및 트리 구성 Korea IT Division of Game Development

Division of Game Development QuadTree Class class ZQuadTree { /// 쿼드트리에 보관되는 4개의 코너값에 대한 상수값 enum CornerType { CORNER_TL, CORNER_TR, CORNER_BL, CORNER_BR }; /// 쿼드트리와 프러스텀간의 관계 enum QuadLocation { FRUSTUM_OUT = 0, /// 프러스텀에서 완전벗어남 FRUSTUM_PARTIALLY_IN = 1, /// 프러스텀에 부분포함 FRUSTUM_COMPLETELY_IN = 2, /// 프러스텀에 완전포함 FRUSTUM_UNKNOWN = -1 }; /// 예외 private: ZQuadTree* m_pChild[4]; ///4개의 자식 노드 int m_nCenter; /// 중심값 int m_nCorner[4]; /// 네 귀퉁이 값 BOOL m_bCulled; /// 프러스텀에서 컬링된 노드인가? float m_fRadius; // 노드를 감싸는 경계구(bounding sphere)의 반지름 /// 자식 노드를 추가한다. ZQuadTree* _AddChild( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR ); /// 4개의 코너값을 셋팅한다. BOOL _SetCorners( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR ); Korea IT Division of Game Development

Division of Game Development QuadTree Class /// Quadtree를 4개의 하위 트리로 부분분할(subdivide)한다. BOOL _SubDivide(); // Quadtree를 subdivide한다. /// 현재 노드가 출력이 가능한 노드인가? BOOL _IsVisible() { return ( m_nCorner[CORNER_TR] - m_nCorner[CORNER_TL] <= 1 ); } /// 출력할 폴리곤의 인덱스를 생성한다. int _GenTriIndex( int nTris, LPVOID pIndex ); /// 메모리에서 쿼드트리를 삭제한다. void _Destroy(); // QuadTree를 구축한다. BOOL Build( TERRAINVERTEX* pHeightMap ); int GenerateIndex( LPVOID pIndex, TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum ); /// 현재노드가 프러스텀에 포함되는가? int _IsInFrustum( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum ); /// _IsInFrustum()함수의 결과에 따라 프러스텀 컬링 수행 void _FrustumCull( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum ); }; 컬링에 따른 인덱스 생성 Korea IT Division of Game Development

Division of Game Development 구현 3) 쿼드 트리 생성 – 1 : 귀퉁이 좌표 셋팅 // 최초 루트노드 생성자 ZQuadTree::ZQuadTree( int cx, int cy ) { int i; m_nCenter = 0; for( i = 0 ; i < 4 ; i++ ) m_pChild[i] = NULL; } // 루트노드의 4개 코너값 설정 m_nCorner[CORNER_TL] = 0; m_nCorner[CORNER_TR] = cx - 1; m_nCorner[CORNER_BL] = cx * ( cy - 1 ); m_nCorner[CORNER_BR] = cx * cy - 1; m_nCenter = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] + m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 4; m_fRadius = 0.0f; m_bCulled = FALSE; 쿼드 트리의 네 귀퉁이 값 설정. Korea IT Division of Game Development

Division of Game Development 구현 4) 쿼드 트리 생성 – 2 BOOL ZQuadTree::Build( TERRAINVERTEX* pHeightMap ) { if( _SubDivide() ) // 좌측상단과, 우측 하단의 거리를 구한다. D3DXVECTOR3 v = *((D3DXVECTOR3*)(pHeightMap+m_nCorner[CORNER_TL])) - *((D3DXVECTOR3*)(pHeightMap+m_nCorner[CORNER_BR])); // v의 거리값이 이 노드를 감싸는 경계구의 지름이므로, // 2로 나누어 반지름을 구한다. m_fRadius = D3DXVec3Length( &v ) / 2.0f; m_pChild[CORNER_TL]->Build( pHeightMap ); m_pChild[CORNER_TR]->Build( pHeightMap ); m_pChild[CORNER_BL]->Build( pHeightMap ); m_pChild[CORNER_BR]->Build( pHeightMap ); } return TRUE; 재귀적으로 트리를 구성한다. Korea IT Division of Game Development

Division of Game Development 구현 5) 쿼드 트리 생성 – 3 : 자식 노드로 분할한다. BOOL ZQuadTree::_SubDivide() { int nTopEdgeCenter; int nBottomEdgeCenter; int nLeftEdgeCenter; int nRightEdgeCenter; int nCentralPoint; // 상단변 가운데 nTopEdgeCenter= ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] ) / 2; // 하단변 가운데 nBottomEdgeCenter= ( m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 2; // 좌측변 가운데 nLeftEdgeCenter= ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_BL] ) / 2; // 우측변 가운데 nRightEdgeCenter= ( m_nCorner[CORNER_TR] + m_nCorner[CORNER_BR] ) / 2; // 한가운데 nCentralPoint = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] + m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 4; 네개의 귀퉁이 좌표와 중점을 구한다. Korea IT Division of Game Development

Division of Game Development 구현 // 더이상 분할이 불가능한가? 그렇다면 SubDivide() 종료 if( (m_nCorner[CORNER_TR] - m_nCorner[CORNER_TL]) <= 1 ) { return FALSE; } // 4개의 자식노드 추가 m_pChild[CORNER_TL] = _AddChild( m_nCorner[CORNER_TL], nTopEdgeCenter, nLeftEdgeCenter, nCentralPoint ); m_pChild[CORNER_TR] = _AddChild( nTopEdgeCenter, m_nCorner[CORNER_TR], nCentralPoint, nRightEdgeCenter ); m_pChild[CORNER_BL] = _AddChild( nLeftEdgeCenter, nCentralPoint, m_nCorner[CORNER_BL], nBottomEdgeCenter ); m_pChild[CORNER_BR] = _AddChild( nCentralPoint, nRightEdgeCenter, nBottomEdgeCenter, m_nCorner[CORNER_BR] ); return TRUE; 자식 노드를 추가한다. Korea IT Division of Game Development

Division of Game Development 구현 6) 쿼드 트리 생성 – 4 : 자식노드 추가 // 자식 노드를 추가한다. ZQuadTree* ZQuadTree::_AddChild( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR ) { ZQuadTree* pChild; pChild = new ZQuadTree( this ); pChild->_SetCorners( nCornerTL, nCornerTR, nCornerBL, nCornerBR ); return pChild; } // 4개의 코너값을 셋팅한다. BOOL ZQuadTree::_SetCorners( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR ) m_nCorner[CORNER_TL] = nCornerTL; m_nCorner[CORNER_TR] = nCornerTR; m_nCorner[CORNER_BL] = nCornerBL; m_nCorner[CORNER_BR] = nCornerBR; m_nCenter = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] + m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 4; return TRUE; 자식 노드를 생성하여 값 셋팅 Korea IT Division of Game Development

Division of Game Development 구현 7) 지형 draw시 culling 수행 HRESULT ZTerrain::Draw( ZFrustum* pFrustum ) { 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_pvHeightMap, pFrustum ); m_pIB->Unlock(); //g_pLog->Log( "Triangles=%d", m_nTriangles ); _Render(); return S_OK; } 인덱스 버퍼를 lock걸고 인덱스를 생성한다. 매번 화면 그려줄 때 프러스텀에 의해서 보여지는 부분만 그려준다. Korea IT Division of Game Development

Division of Game Development 구현 8) 컬링을 통한 인덱스 생성 Int ZQuadTree::GenerateIndex( LPVOID pIndex, TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum ) { // 커링을 쿼드 트리별로 하고 _FrustumCull( pHeightMap, pFrustum ); // 컬링된 인덱스 생성 return _GenTriIndex( 0, pIndex ); } 쿼드 트리별 프로스텀 컬링 수행 컬링을 하고 이에 따라서 인덱스를 생성한다. Korea IT Division of Game Development

Division of Game Development 구현 9) 인덱스에 대한 컬링 수행 void ZQuadTree::_FrustumCull( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum ) { int ret; ret = _IsInFrustum( pHeightMap, pFrustum ); switch( ret ) case FRUSTUM_COMPLETELY_IN : // 프러스텀에 완전포함, 하위노드 검색 필요없음 m_bCulled = FALSE; return; case FRUSTUM_PARTIALLY_IN : break; case FRUSTUM_OUT : // 프러스텀에서 완전벗어남, 하위노드 검색 필요없음 m_bCulled = TRUE; } if( m_pChild[0] ) m_pChild[0]->_FrustumCull( pHeightMap, pFrustum ); if( m_pChild[1] ) m_pChild[1]->_FrustumCull( pHeightMap, pFrustum ); if( m_pChild[2] ) m_pChild[2]->_FrustumCull( pHeightMap, pFrustum ); if( m_pChild[3] ) m_pChild[3]->_FrustumCull( pHeightMap, pFrustum ); 프러스텀 포함 유무 판단 m_bCulled = FALSE 되면 쿼드 트리 검색시 제외된다. 재귀적으로 수행 Korea IT Division of Game Development

Division of Game Development 구현 10) 프러스템 내에 속하는 유무 판단 int ZQuadTree::_IsInFrustum( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum ) { BOOL b[4]; BOOL bInSphere; bInSphere = pFrustum->IsInSphere( (D3DXVECTOR3*)(pHeightMap+m_nCenter), m_fRadius ); if( !bInSphere ) return FRUSTUM_OUT; // 쿼드트리의 4군데 경계 프러스텀 테스트 b[0] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[0]) ); b[1] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[1]) ); b[2] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[2]) ); b[3] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[3]) ); // 4개모두 프러스텀 안에 있음 if( (b[0] + b[1] + b[2] + b[3]) == 4 ) return FRUSTUM_COMPLETELY_IN; // 일부분이 프러스텀에 있는 경우 return FRUSTUM_PARTIALLY_IN; } 경계구 안에 없으면 점단위의 프러스텀 테스트 생략. Korea IT Division of Game Development

Division of Game Development 구현 11) 지형의 인덱스 생성 // 출력할 폴리곤의 인덱스를 생성한다. Int ZQuadTree::_GenTriIndex( int nTris, LPVOID pIndex ) { // 컬링된 노드라면 그냥 리턴 if( m_bCulled ) m_bCulled = FALSE; return nTris; } // 현재 노드가 출력 되지 않는가 ? if( _IsVisible() ) #ifdef _USE_INDEX16 LPWORD p = ((LPWORD)pIndex) + nTris * 3; #else LPDWORD p = ((LPDWORD)pIndex) + nTris * 3; #endif // *p++ = m_nCorner[0]; *p++ = m_nCorner[1]; *p++ = m_nCorner[2]; nTris++; 경계구 안에 없으면 점단위의 프러스텀 테스트 생략. 자식 노드는 검색 필요 없다. 인덱스 값 셋팅 Korea IT Division of Game Development

Division of Game Development 구현 *p++ = m_nCorner[2]; *p++ = m_nCorner[1]; *p++ = m_nCorner[3]; nTris++; return nTris; } // 자식 노드들 검색 재귀적으로 if( m_pChild[CORNER_TL] ) nTris = m_pChild[CORNER_TL]->_GenTriIndex( nTris, pIndex ); if( m_pChild[CORNER_TR] ) nTris = m_pChild[CORNER_TR]->_GenTriIndex( nTris, pIndex ); if( m_pChild[CORNER_BL] ) nTris = m_pChild[CORNER_BL]->_GenTriIndex( nTris, pIndex ); if( m_pChild[CORNER_BR] ) nTris = m_pChild[CORNER_BR]->_GenTriIndex( nTris, pIndex ); 자식 노드 재귀적 검색 하여 인덱스 생성 Korea IT Division of Game Development

Division of Game Development 구현 12) 그려주기 HRESULT ZTerrain::_Render() { m_pd3dDevice->SetTexture( 0, m_pTex[0] ); // 0번 텍스쳐 스테이지에 텍스쳐 고정(색깔맵) m_pd3dDevice->SetSamplerState( 0, D3DSAMP_MAGFILTER, D3DTEXF_LINEAR ); m_pd3dDevice->SetTextureStageState( 0, D3DTSS_TEXCOORDINDEX, 0 ); m_pd3dDevice->SetTextureStageState( 0, D3DTSS_COLOROP, D3DTOP_MODULATE); m_pd3dDevice->SetTextureStageState( 0, D3DTSS_COLORARG1, D3DTA_TEXTURE ); m_pd3dDevice->SetTextureStageState( 0, D3DTSS_COLORARG2, D3DTA_DIFFUSE ); m_pd3dDevice->SetStreamSource( 0, m_pVB, 0, sizeof(TERRAINVERTEX) ); m_pd3dDevice->SetFVF( TERRAINVERTEX::FVF ); m_pd3dDevice->SetIndices( m_pIB ); m_pd3dDevice->DrawIndexedPrimitive( D3DPT_TRIANGLELIST, 0, 0, m_cxDIB * m_czDIB, 0, m_nTriangles ); return S_OK; } 인덱스 방식으로 그리기 Korea IT Division of Game Development