쿼드트리(Quad Tree)

지형 관리 기법으로서의 쿼드 트리

3D게임 월드를 구축하는데 있어서 지형 관리 기법으로 여러 방법이 쓰인다
(무책임하게도 구체적으로 어떠어떠한 것들이 있는지 아직 잘은 모른다 --;;)

이번 강좌에서는 그 중에 하나인 쿼드 트리를 이용한 지형 관리 기법이 쓰이는 이유을 살펴보도록 하겠다.



쿼드 트리의 정의:

쿼드 트리란 자료구조의 하나로서 트리의 일종이다. 트리란 ''인데 쿼드 트리란 자식 노드가 4개라서 쿼드 트리라 부른다.



컬링을 위한 지형 검색에 쿼드 트리를 쓰는 이유:

컬링을 위한 지형 검색에 쿼드 트리를 사용하는 자세한 이유는 여기를 보면 알 수 있다.
(한글 번역판은 spirit3d홈피 article에서 quadtree로 검색하면 볼 수 있다)
위에 링크된 문서에서 알 수 있듯이 쿼드 트리를 이용하게 되면 필요 없는 데이터를 큰 덩어리 단위로 버릴 수 있게 되므로 거대한 지형을 빠르게 검색할 수 있게 된다.

요점을 말하자면 '정석적으로 컬링하는 것보다 쿼드 트리라는 자료구조를 이용하여 컬링하는 쪽이 연산의 횟수가 적어져 빠르기 때문이다'는 것이다.



쿼드 트리를 이용한 지형 관리 소스 분석:

다음은 김용준님이 쓰신 '3D 게임 프로그래밍'에 나오는 쿼드 트리가 적용된 지형 관리 클래스의 소스이다.

class ZQuadTree
{
  enum CornerType { CORNER_TL, CORNER_TR, CORNER_BL, CORNER_BR };
 
private:
  ZQuadTree* m_pChild[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 );


  BOOL _SetCorners( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR );
  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();

  BOOL Build();

  int GenerateIndex( LPVOID pIB );
};


실제 소스상으로 보면 쿼드 트리도 ZQuadTree* m_pChild[4]; 라고 굵은 글씨체로 타이핑해넣은 부분처럼 여타의 자료구조들(링크드 리스트)처럼 포인터를 사용하여 재귀적으로 만들어져 있다.
쿼드 트리의 기본적인 구성은 노드와 링크로 이루어지게 되는데 각 노드의 자식 노드가 4개씩 존재하게 된다.

이 소스상에서는 개념적으로 지형을 2차원 평면상의 입체로 규정하고 관리하기 때문에 4개씩 자식 노드가 생기는 쿼드 트리를 적용하게 된다. 만약 완벽하게 3차원적으로 입체를 관리하고자 한다면 8개씩 자식 노드를 만드는 자료구조인 옥트리를 적용하게 된다.

//=========================================================================================
/// QuadTree를 구축한다.
//=========================================================================================
BOOL ZQuadTree::Build()
{
  if( _SubDivide() )
  {
   m_pChild[CORNER_TL]->Build();
   m_pChild[CORNER_TR]->Build();
   m_pChild[CORNER_BL]->Build();
   m_pChild[CORNER_BR]->Build();
  }
  return TRUE;
}


QuadTree를 만드는 메소드이다.
보시다시피 재귀적인 방법으로 쿼드 트리를 구축한다.

지형을 쪼갤 수 있는지 검사해서 쪼갤 수 있으면 재귀 호출로 계속 쪼개어 나간다. 다음은 실제로 쪼개는 메소드이다.

//=========================================================================================
/// Quadtree를 4개의 자식 트리로 부분분할(subdivide)한다.
//=========================================================================================
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;

  // 더이상 분할이 불가능한가? 그렇다면 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;
}


굵은 글씨체로 적어놓은 부분은 쪼개는 하한선을 정한 것이다. 이것을 트리의 '깊이'라고 부른다.

실제로 노드에 저장되는 정보는 정점들의 인덱스이다.
(정점을 저장하는 것이 아니다. 정점의 인덱스를 저장하는 것이다. 노드에 정점의 인덱스를 저장함으로서 쿼드 트리를 기반으로 LOD의 구현이 쉬워지게 된다)

위의 두가지 요소 즉 '깊이' 와 '인덱스'를 기반으로 쿼드 트리 기반의 LOD가 구현될 수 있다.



결론:

3D세계에서 지형 관리를 위한 여러 방법이 존재하는데 그중에 쿼드 트리를 이용한 방법이 있다.
쿼드 트리를 이용한 지형 관리 방법이 좋은 이유는 컬링시 필요없는 데이터를 큰 단위로 한번에 떼어 버릴 수 있으므로 연산이 적어져 더 빠르게 지형을 검색할 수 있다는 것이다.
게다가 쿼드 트리를 이용하면 LOD의 구현도 비교적 간단히 할 수 있다. 

[출처] 지형 관리 기법으로서의 쿼드 트리|작성자 나뭇잎

- 쿼드트리 클래스(책의 예제)

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];     /// QuadTree의 4개의 자식노드

 int   m_nCenter;                   /// QuadTree에 보관할 첫번째 값
 int   m_nCorner[4];              /// QuadTree에 보관할 두번째 값
                                          ///    TopLeft(TL)      TopRight(TR)
                                          ///              0------1
                                          ///              |         |
                                          ///              |         |
                                          ///              2------3
                                          /// BottomLeft(BL)      BottomRight(BR)
 BOOL  m_bCulled;   /// 프러스텀에서 컬링된 노드인가?
 float  m_fRadius;   /// 노드를 감싸는 경계구(bounding sphere)의 반지름
 
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();  // Quadtree를 subdivide한다.

 /// 현재 노드가 출력이 가능한 노드인가?
 BOOL  _IsVisible() { return ( m_nCorner[CORNER_TR] - m_nCorner[CORNER_TL] <= 1 ); }

 /// 출력할 폴리곤의 인덱스를 생성한다.
 int   _GenTriIndex( int nTris, LPVOID pIndex );

 /// 메모리에서 쿼드트리를 삭제한다.
 void  _Destroy();

 /// 현재노드가 프러스텀에 포함되는가?
 int   _IsInFrustum( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum );

 /// _IsInFrustum()함수의 결과에 따라 프러스텀 컬링 수행
 void  _FrustumCull( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum );
public:

    /// 최초 루트노드 생성자
    ZQuadTree( int cx, int cy );

    /// 하위 자식노드 생성자
    ZQuadTree( ZQuadTree* pParent );

    /// 소멸자
    ~ZQuadTree();

 /// QuadTree를 구축한다.
 BOOL  Build( TERRAINVERTEX* pHeightMap );

 /// 삼각형의 인덱스를 만들고, 출력할 삼각형의 개수를 반환한다.
 int   GenerateIndex( LPVOID pIndex, TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum );
};

 

-  책의 쿼드트리 클래스는 쿼드트리가 점유할 지형의 크기를 생성자를 통해서 입력한 뒤

   Build() 함수를 호출하면 내부적인 재귀호출을 통해 쿼드트리를 생성한다.

   이때 생성할 지형의 크기는 반드시 2n+1 이어야 한다.

   그 이외의 크기는 쿼드트리로 분할되지 않는다.

   현재 쿼드트리를 하위분할(subdivide)하면서 쿼드트리의 각각의 노드에 저장하는 값은

   정점의 인덱스 정보다. 최종적으로 정점의 인덱스 정보를 가지고 지형을 그리기 때문이다.

   편의상 4개의 귀퉁이(corner)정보 이외에도 중앙(center)값도 갖고 있다.

 

< 지형관리 클래스 >

어제 예제까지는 정점버퍼와 인덱스버퍼 또.. 지형의 높이맵 정보를 직접 메인함수에서

갖고있었는데 이제부터는 쿼드트리와 결합하기위해 따로 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 fLODRatio : LOD처리시에 사용될 값
  * @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( ZFrustum* pFrustum );
};

 

- 최초로 객체를 생성한다음 Create()함수에서 높이맵으로 사용될 BMP 파일과 텍스쳐 정보를

   입력받아 지형 정보를 생성한다. _BuildHeightMap() 함수에서 높이맵을 생성하고

   Draw()함수를 호출해서 지형을 그린다.

 

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

- 락걸고 인덱스버퍼 포인터를 얻은다음 쿼드트리로부터 출력할 삼각형의 인덱스 버퍼를

  얻어낸다. 그리고 언락후, 쿼드트리에서 생성한 인덱스 버퍼의 내용으로 _Render()함수내부의

  DrawIndexedPrimitive()함수를 사용하여 지형정보 삼각형을 그린다.

  ZTerrain 클래스는 높이 맵을 읽어서 정점버퍼와 인덱스 버퍼를 만들고, 쿼드트리를 내부에

  갖고 있다.

 

< 쿼드트리 컬링 >

짧게 말하면 프로스텀이 형성된 지역을 제외하곤 모두 그리지 않는다.

프로스텀이 형성된 지역만 그린다.

쿼드트리로 4등분을 또 4등분... 4등분.. 했으니까.. 프로스텀에 걸리지 않는 영역은

부모노드 통째로 제외시키고 만약에 부분만 걸렸다 하면. 그 노드의 4등분 된것을 또 판단하여

프로스텀에 걸리지 않으면 제외시킨다.. 이렇게 프로스텀에 부분적으로 걸려있으면 작게작게

들어가서 프로스텀에 걸리는 지역만 렌더링 한다.

 

쿼드트리의 특성을 잘 이용하면 커다란 덩어리의 영역을 한꺼번에 제외시켜 버릴 수 있다.

 

- 지금 사용하는 모든 프로스텀(절두체) 판정은 경계구 방식이다.

각각의 중앙에서 가장끝점(모서리)까지의 거리를 반지름으로 하는 경계구를 사용하연 판정한다.

 

쿼드트리 클래스 헤더는 위에 있고..

봐야할 함수는..

// 삼각형의 인덱스를 만들고, 출력할 삼각형의 개수를 반환한다.
int  ZQuadTree::GenerateIndex( LPVOID pIndex, TERRAINVERTEX* pHeightMap,

                                                                                                    ZFrustum* pFrustum )
{
 _FrustumCull( pHeightMap, pFrustum );
 return _GenTriIndex( 0, pIndex );
}

 

// _IsInFrustum()함수의 결과에 따라 프러스텀 컬링 수행
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 :  // 프러스텀에 일부포함, 하위노드 검색 필요함
   m_bCulled = FALSE;
   break;
  case FRUSTUM_OUT :    // 프러스텀에서 완전벗어남, 하위노드 검색 필요없음
   m_bCulled = TRUE;
   return;
 }
 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 );
}

 

int ZQuadTree::_IsInFrustum( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum )
{
 BOOL b[4];
 BOOL bInSphere;

 // 경계구안에 있는가?
// if( m_fRadius == 0.0f ) g_pLog->Log( "Index:[%d], Radius:[%f]",m_nCenter, m_fRadius );
 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;
}

 

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

 return nTris;
}

 

BOOL  _IsVisible() //쿼드트리 클래스안의 인라인 함수로 되어있음.// 더이상 나눠질수 있는가?

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

 

_GenTriIndex()함수에서 m_bCulled값이 FALSE인 노드들만을 대상으로 삼각형의

인덱스를 만든다.

 

쿼드트리는 여기까지... 아따.. 힘들다.. 현재 80% 이해.. ㅡㅡ;;

 

* 충돌처리 몇가지 방법.

 

- AABB ( Axis Aligned Bounding Box ) 

   :  바운딩 박스가 정렬이 되어있다.  X,Y,Z 축에 대해 겹쳐진 부분을 검사한다.

      MMORPG 에서 많이 사용..

 

- OBB ( Object Bounding Box )

   :  케릭터(오브젝트)에 주축과 단축이 존재한다. (케릭터가 회전하는 방향에 따라 바뀐다.)

      검사하는 모든 축에 대해 겹쳐지는 부분이 존재하냐?   존재하면 충돌..

      이 기법은 계산량이 많아서 MMORPG 에서는 잘 안 쓴다.

      => 철권같은 대전액션에 쓰인다.

 

- 경계구( Bounding Sphere  )

   :  가장 간단하다. 케릭터(오브젝트)에 경계구를 씌운다.

      두 오브젝트간의 각각의 반지름을 더한것보다 두 오브젝트간의 원점의 거리가 작으면

      충돌이고  크면 충돌이 일어나지 않은 것이다.

 

**

또.. 정확한 명칭이 잊어버렸는데.. 뭐.. 실린더 어쩌고..그건데.. 킁..

    케릭터(오브젝트)에 원통을 씌운다.

         : 검사는 Y축으로는 바운딩 박스로  X,Z 축으로는 반지름을 이용하여 하는 방법..

 

**

또.. 경계구와 바운딩박스를 합쳐서 충돌처리를 하기도한다.

    일단은 경계구로 충돌체크를 하고 충돌이 일어났으면 그다음 바운딩 박스로 체크를 한다.

    좀더 정확하고 좀더 빠르게 처리하기 위해..

 

 

 

* FPS와 MMORPG의 차이점..

  FPS는 맵이 작아야하고 MMO는 넓어야 한다.

  FPS는 맵을 한번에 로드하고, MMO는 프로스텀이 생성되어있는 인근영역을 로드한다.

  결론은 자원을 관리하는 체계가 틀리다는것이다..

 

<< 파일설명 >>

05.QuadTree+Frustum.zip       :       쿼드트리.. 컬링까지..( 책의예제 )

 

[출처] [ 5. 6] D3D(2) 17일차..( 쿼드 트리, 충돌처리)|작성자 교