옥트리 관하여

 

 

=================================

=================================

=================================

 

 

출처: http://hermet.pe.kr/57456541

 
잠깐 짬을 내어 옥트리에 대해서 글을 써 보겠습니다.

 

옥트리 (팔진 트리); 3차원 공간을 분할하는 기법 중 하나이며 쿼드트리(Quadtree) 가 높이 면에 대한 분할을 하지 않는다는 점에 비해 옥트리는 높이에 대한 분할까지 시도하지요. 따라서 대게 3차원에 대해 모두 활용하는 공간에서 옥트리를 사용하게 됩니다.

 

 

 

 

 

 

 

-좌 :Quadtree   우 : Octree-

 

 

따라서, 넓은 공간( 특히 야외 )에서 높은 빌딩 들이나 심지어 공중을 날 수 있는 그런 환경에서는 옥트리가 유용하지요.

 

자료구조에서 이진 트리에 대해서 배우셨다면 옥트리의 이론은 매우 간단합니다. 하나의 노드를 8개로 분할하여 나가는게 전부이지요.

 

부모 노드는 8개의 자식노드로 분할이 되고 각각의 자식노드들은 다시 8개의 자식노드로 분할되어 가는 이론입니다. 따라서, 각각의 노드는 자신의 부모노드와 연결되어 있어야 하고 8개의 자식 노드들과 연결되어 있으면 되겠죠.

 

그럼 여기까지 이해는 되셨을거라고 생각하겠습니다. 그럼 도대체 분할을 하는 이유가 무엇인가?

 

3D의 기본을 아신다면 금방 깨달을 겁니다. 한가지 예를 들면, 가까이 있는 물체에 비해 멀리 있는 물체는 그 디테일이 떨어질 필요가 있습니다. 이는 단순히 카메라와 물체 사이의 거리를 파악하여 판단할 수도 있지만 옥트리를 이용한다면 더 쉽게 계산이 되기도 합니다.

 

한번 다음 그림을 보도록 하죠.

 

 

 

 

 

 

 빨간 박스 공간 안에 3개의 건물이 존재합니다. 각 건물의 크기는 서로 다르지요. 물론 3차원 공간으로 표현한다면 높이도 존재하겠지만 여기서 그림으로 표현하기 어려우니 그냥 2D로 가정합니다.

 

우리는 빨간 공간을 하나의 노드라고 가정할 수 있으며 그 노드 안에는 3개의 건물이 존재하는 거지요.  따라서, 우리는 현재의 노드에 포함된 모든 오브젝트를 그냥 그려주면 됩니다.

 

그럼 다음 그림을 보도록 합시다.

 

 

 

 

 

 

 

 

역시 동일한 노드에 3개의 다른 크기의 건물이 존재합니다만, 이번엔 카메라의 위치가 달라져서 노드가 전부 보이지는 않습니다. 만약 우리는 빨간 노드에 포함된 모든 건물을 다 그린다면 오른쪽 하단의 가장 큰 건물이 필요없이 렌더링 되겠지요. (엄청난 낭비!)

 

따라서 위의 빨간 노드는 다음과 같이 분할될 수 있습니다. ( 절두체 컬링 결과 빨간 노드가 절두체 공간 상에 완전히 포함되지 않는다면!)

 

 

 

 

 

 

 

이번엔 빨간 노드가 한단계 분할이 되어서 8개가 되었습니다.(물론 그림상에서는 4개.) 그리곤 절두체에 포함되는 노드들(파란색)은 3개로 판정할 수 있으며 포함되지 않는  노드도 구분할 수 있지요. 여기서 우리는 파란색 노드들이 가지고 있는 모든 건물들만 그린다면 우리가 원하지 않았던 오른쪽 하단의 가장 큰 건물은 무시할 수 있을 겁니다. 한 술 더 떠서,

 

 

 

 

 

 

 

다음과 같은 상황도 존재할 수도 있지요.

 

이제, 대강 옥트리의 활용도에 대해서 이해하셨을 거라고 생각합니다.

 

다시 한번 정리하자면, 각 노드를 세분화 할수록 우리는 좀 더 디테일하게 오브젝트들의 렌더링 여부를 판단할 수 있으며 또한 각 노드들의 위치에 따라서 렌더링할 오브젝트의 세밀함 정도도 판단할 수 있을겁니다.

 

 

 

 

파란색 노드와 카메라와의 위치만 판단한다면, 파란색 노드에 포함된 물체들의 세밀함을 한번에 판단할 수 있겠지요. 만약 옥트리를 쓰지 않았다면, 6개의 물체들의 거리를 모두 판단해서 각각의 세밀함 정도를 판단해야 할겁니다. 여기서 세밀함이란 프로그레시브 메시 를 말하는 겁니다.

 

추가로 덧붙이자면, 정적 오브젝트 같은 경우는 맵 제작 시에 옥트리 노드들에 물체들의 포함 여부를 판정해 놓으며 만약 물체가 노드들 사이에 끼어 있을 경우에는 그 물체를 끼인 면에 대해서 분할시켜 버리거나, 느슨한 옥트리 방식을 이용하여 설정을 해놓기도 합니다.

(물체를 분할하는 방식은 여기서 논할 꺼리는 아니고 느슨한 옥트리 같은 경우는 GPG 1권을 참고하세요.)

 

그럼 이제 한번 구현해 보도록 합시다. 일단 노드에 대한 정의부 입니다.

 

 

class OctreeNode {   enum eValue { Depth_Limit = 4,                     //노드의 세부 수준을 4단계로 제한 합니다.                         Width = 1000 };                       //최초 노드의 가로 크기     BoundingBox*                   m_pBoundBox;                          //현재 노드의 바운딩 박스  vector< OctreeNode* >       m_vChildren;                            //자식 노드   list< Object* >                   m_listObjects;                          //현재 노드에 포함되는 정적 오브젝트 목록   BOOL                               m_bCulled;                               // 이 노드가 컬링 되었는지 여부    OctreeNode*                     m_pParent;                                 //부모 노드      VOID AddChildNode( OctreeNode* );                                  // 이 노드에 자식 노드를 추가합니다.   BOOL AddObject( Object* );                                               // 이 노드에 오브젝트를 추가합니다.   VOID CullNode( BOOL );                                                     // 이 노드를 컬링합니다.   OctreeNode* const GetChildNode( size_t );                          //자식 노드를 가져옵니다.   VOID SetParent( OctreeNode* const );                                 //부모 노드를 설정합니다.   OctreeNode* const GetParent();                                          //부모 노드를 반환합니다.  BOOL IsInNode( const GLTVector3 );                                  //현재 노드에 해당 정점이 포함되는지 판단합니다.   VOID Render();                                                                 //이 노드의 물체들을 렌더링합니다.    BOOL IsCulled();                                                             // 이 노드가 컬링됬는지 판단합니다.   };

 

 

 주석만 봐도 대강 이해하실 겁니다.  그럼 다음으로 중요한 옥트리를 구축하는 부분을 보도록 하죠.

 

 

//vCenter : 노드의 중심 위치   fHalfWidth : 노드의 반지름     depthLimit : 현재 노드 진입 단계 OctreeNode* BuildOctree( Vector3 vCenter, FLOAT fHalfWidth,  int depthLimit ) {         //제한된 진입단계에 도달하면 더 이상 자식 노드를 생성하지 않습니다.      if( depthLimit < 0 ) {           return NULL;       }//if         //현재 노드를 생성       OctreeNode* pOctNode = new OctreeNode();        BoundingBox* pBBox = pOctNode->GetBoundingBox();        pOctNode->SetPosition( vCenter );        pBBox->SetRadius( fHalfWidth );         //재귀적으로 8개의 자식 노드들을 생성합니다.        GLTVector3 vOffset;        GLTVector3 vChildCenter;         FLOAT fStep = fHalfWidth * 0.5f;         //8개의 자식 노드들에 대해서 중심 위치를 설정하고 트리를 생성.        for( INT iTree = 0; iTree < OctreeNode ::Child_Node_Count; ++iTree ) {            vOffset[ 0 ] = ( ( iTree & 1 )  ? fStep : -fStep );             vOffset[ 1 ] = ( ( iTree & 4 )  ? fStep: -fStep );             vOffset[ 2 ]= ( ( iTree & 2 )  ? fStep : -fStep );            vChildCenter[ 0 ] = vOffset[ 0 ] + vCenter[ 0 ];             vChildCenter[ 1 ] = vOffset[ 1 ] + vCenter[ 1 ];             vChildCenter[ 2 ] = vOffset[ 2 ] + vCenter[ 2 ];            pOctNode->AddChildNode( BuildOctree( vChildCenter, fStep, depthLimit - 1 ) );       }//for            return pOctNode;   }//VOID BuildOctree( FLOAT fCenter, FLOAT fHalfWidth,  size_t depth )

 

 

 결국 반환되는 건 최초의 부모 노드입니다. 뭐 옥트리를 구축하고 자식노드를 얻어오는 것은 다음과 같이 호출하면 되겠죠.

 

 

OctreeNode* pOctreeNode = BuildOctree( Vector3( 0, 0, 0 ), 1000, 4 );                                             //최상위 노드의 중심 위치, 최상위 노드의 반지름, 자식 노드 생성의 제한 레벨 )   OctreeNode* pSecondNode = pOctreeNode->GetChildrenNode( 2 ); //8개의 자식노드 중 2번의 자식 노드를 가져온다.

 

 

 자, 다음 중요한 것은 정적 오브젝트가 어느 노드에 포함되는 지 판단하는 부분입니다. 만약 어떤 물체가 검색한 노드에 포함이 되면 노드의 물체 소유 목록에 추가해야 겠죠.

 

 

//vObjPos : 판단하고자 하는 물체의 위치           // pNode : 판단하고자 하는 노드 BOOL  FindCurrentPosNode( const Vector3 vObjPos, OctreeNode* const pNode ) {         Vector3* pvNodePos = pNode->GetPosition();          FLOAT fRadius = pNode->GetBoundingBox()->GetRadius();                  fRadius *= LOOSE_FACTOR;                                       // 느슨한 옥트리 같은 경우 반지름에 계수를 곱해줄 수 있습니다.     FLOAT fMin, fMax;        // 이 부분은 현재 물체가 이 노드 안에 완전히 포함되는 지 판단합니다.     for( int index = 0; index < 3; ++index ) {               fMin = ( *pvNodePos )[ index ] - fRadius;                 fMax = ( *pvNodePos )[ index ] + fRadius;                //포함되지 않으면 실패를 반환하죠.              if( vObjPos[ index ] < fMin || vObjPos[ index ] > fMax ) {                      return FALSE;                }//if     } //for         //만약 노드 안에 물체가 완전히 속한다면 해당 노드를 반환         return TRUE;   }//OctreeNode* FindCurrentPosNode( OctreeNode* const pNode )

 

 

 

해당 노드에 물체가 포함된다면 자식 노드들도 판단해 볼 필요가 있습니다. 물론 여기서는 그 부분까진 보여주지 않지만 충분히 이해하실

 

거라고 생각합니다.

 

핵심 구현은 여기까지 입니다. 부족한 감이 없잖아 있지만 다른 사항들은 어렵지 않으니 주석을 보시고 직접 구현해 보시길 바랍니다.

 

 

[출처] Octree ( 옥트리 )|작성자 Hermet

=================================

=================================

=================================