SpaceFillingVolume

UserPreferences

1. 개요
2. 데이터 생성
1. 분할
2. 병합
3. 인접 노드 계산
4. 필요없는 노드 제거하기
5. 포탈 생성하기
6. 결과물
3. 장/단점
1. 장점
2. 단점
4. 링크

1 개요

Space Filling Volume은 검색 공간을 표현하는 하나의 방법이다. 위의 그림처럼 공간을 임의의 크기 박스로 채우고, 이 박스들을 일종의 노드로서 길찾기 등에 활용하는 것이다. NavigationMesh만큼 융통성이 있지는 않으나, 생성 및 이용이 쉽다.

2 데이터 생성

일단 3D 환경을 기반으로 한다. 즉 특정 메쉬를 입력받아, Space Filling Volume을 생성하는 것이 목표다.

생성 방법에는 2가지 방법이 있다. 첫번째는 공간의 임의 지점에다 큐브를 떨어뜨리고, 그 큐브의 크기를 충돌이 일어나는 범위까지 늘려가는 방법이다. 두번째는 공간을 일정 크기의 그리드로 쪼갠 후, 충돌이 일어나지 않는 그리드들을 병합하는 방법이다. 첫번째 방법은 임의의 지점을 고르는 게 애매해서, 두번째 방법을 선택했다.



2.1 분할

1. 먼저 입력받은 메쉬를 감쌀 수 있는 AABB를 구한다.
   
2. 정해진 크기 단위로 AABB를 쪼갠다.
   
• 이 크기가 작으면 작을수록 원래 메쉬에 좀 더 가까운 Space Filling Volume이 생성되지만, 대신 생성 과정에 들어가는 메모리가 3제곱으로 늘어나게 된다. 이 때문에 너무 커다란 메쉬(폴리곤 수와는 상관없이 단순히 큰...)를 처리할 때에는 메모리 문제가 발생할 수 있다.
  
• 이 쪼갠 육면체들을 셀이라 부르겠다.
  
3. 메쉬를 구성하는 모든 삼각형들과 셀들간의 충돌 체크(Triangle vs AABB)를 수행한다.
   
• 삼각형과 충돌 가능성이 있는 셀들, 즉 삼각형을 감싸는 AABB 안에 들어가는 셀들만 충돌 체크하는 것은 기본이라고 할 수 있겠다.
  
4. 충돌 체크를 수행하고 나면, 갈 수 있는 셀과 갈 수 없는 셀이 분리된다.
   
   

2.2 병합

병합은 뭐랄까, 말로 설명하기에는 약간 복잡한 관계로 슈도 코드로 보는 것이 이해가 빠를 것이다.


enum
{
    EXPAND_LEFT,
    EXPAND_RIGHT,
    EXPAND_FORWARD,
    EXPAND_BACKWARD,
    EXPAND_UP,
    EXPAND_DOWN,
    EXPAND_MAX
};

struct REGION
{
    int x0, y0, z0; ///< 영역 최소 좌표
    int x1, y1, z1; ///< 영역 최대 좌표
};

bool GetLargestEmptyRegion(int x, int y, int z, int size, REGION& result)
{
    // 영역을 설정한다.
    result = { x, y, z, x + size, y + size, z + size };

    // 먼저 해당 영역이 모두 비어있는지 체크한다.
    if (IsEmpty(result)) return false;

    REGION test, current;
    int failed = 0;

    // 각 방향을 따라 루프를 돌면서 큐브의 크기를 늘릴 수 있는지 체크한다.
    while (failed < EXPAND_MAX) {
        for (int dir=0; dir<EXPAND_MAX; ++dir) {
            // 이전의 결과값 복사
            current = result;

            // 테스트 영역 계산
            // 현재의 방향에 따라 테스트가 필요한 영역이 정해진다.
            test = current.GetTestRegion(dir);

            if (IsEmpty(test)) {
                // 해당 영역이 비어있는 경우에는 결과 영역을 확장하고, 
                // fail 카운트를 초기화한다.
                failed = 0;
                result = current + test;
            }
            else { 
                failed++; 
            }
        }
    }

    // 여기까지 왔다면 최소한 제일 처음 주어진 영역만큼은 비어있다는 말이다.
    return true;
}

void Merge()
{
    // 맵의 축 중에 가장 작은 축을 기준으로 시작한다.
    int MaxSize = min(MapWidth, MapHeight, MapDepth);

    // 최대 크기를 줄여나가며 모두 테스트한다.
    for (int size=MaxSize; size > 0; size--) {
        for (int x=0; x+size < MapWidth; ++x) {
            for (int y=0; y+size < MapHeight; ++y) {
                for (int z=0; z+size < MapDepth; ++z) {
                    REGION r;
                    
                    // 현재 영역을 포함하는 가장 큰 영역을 계산한다.
                    if (!GetLargestEmptyRegion(x, y, z, size, r))
                        continue;
    
                    // 영역에 포함된 큐브들을 사용된 것으로 표시한다.
                    // 사용된 것으로 포함된 큐브들은 IsEmpty() == false가 된다.
                    SetUsed(r, true);
    
                    // Area 객체를 생성해서 컬렉션에다 추가한다.
                    collection.Add(r, ...);
                }
            }
        }
    }
}

이렇게 하면 병합된 육면체들을 얻어낼 수 있다. 이 육면체들을 노드라고 부르겠다.



2.3 인접 노드 계산

노드만으로는 아직 그래프 형태의 데이터가 아니기 때문에, 길찾기에 써먹으려면, 어느 노드에 어느 노드가 붙어있는지를 알아내야한다. 이는 간단한 충돌체크(AABB vs AABB)를 통해 알아낼 수 있다.



for a in all_nodes  
    for b in all_nodes  
        if collide(a, b) 
            set a, b as neighbor 




2.4 필요없는 노드 제거하기

모든 노드가 필요한 것은 아니다. 갈 수 없는 노드들을 추려냄으로서 좀 더 적은 데이터를 만들어낼 수 있다. 다만 어떤 노드가 필요없는가는 애플리케이션마다 틀리다. 예를 들어보자면...


• 이웃 노드가 하나도 없는 노드 같은 경우, 해당 노드로 갈 방법이 없으므로 필요없다.
  
• Y 축을 제외하고, XZ 평면 상으로 봤을 때 완전히 다른 노드에 포함되는 노드의 경우, 게임 상에서 날아다니는 것이 불가능하다면 필요없다.
  
  

2.5 포탈 생성하기

이웃 노드까지 계산을 마쳤으므로 그래프 형태의 데이터가 만들어졌으나, 아직 이를 PathFinding에 바로 이용할 수는 없다. 노드와 노드가 이어지는 부분에 포탈을 생성해야, 게임 안에서 벽과 충돌하지 않는 움직임을 만들어낼 수 있다. 노드가 육면체이기 때문에 간단히 포탈을 계산할 수 있다. 두 노드 min, max 값을 더해서 2로 나누면 땡이다.


const D3DXVECTOR3* bmin1 = pLHS->GetAABBMinimum();
const D3DXVECTOR3* bmax1 = pLHS->GetAABBMaximum();
const D3DXVECTOR3* bmin2 = pRHS->GetAABBMinimum();
const D3DXVECTOR3* bmax2 = pRHS->GetAABBMaximum();

D3DXVECTOR3 pos(
    (std::max(bmin1->x, bmin2->x) + std::min(bmax1->x, bmax2->x)) * 0.5f,
    (std::max(bmin1->y, bmin2->y) + std::min(bmax1->y, bmax2->y)) * 0.5f,
    (std::max(bmin1->z, bmin2->z) + std::min(bmax1->z, bmax2->z)) * 0.5f
);

이 포탈들을 ((from+,to),portal)의 형식으로 어딘가에 저장해두면 간단히 이용할 수 있다.



2.6 결과물

Original Mesh



Generated Volumes

3 장/단점

일단 애초의 목적이 MMORPG 서버용이었다. 클라이언트에서 사용하기에는 장점보다는 단점이 많을 것이다.



3.1 장점

• 구현이 쉽다.
  
• 메모리가 적게 들어간다.
  
• 뭐 또 없나... -_-;;
  
  

3.2 단점

단점은 주로 기본 단위가 사각형/육면체이기 때문에 발생한다.


• 곡면 또는 XYZ축과 어긋난 평면이 많은 지형을 처리하기 어렵다. (상당히 치명적인 단점이다.)
  
• 실제 움직임을 화면에 그릴 때는 보정을 많이 해줘야한다.
  
• 눈으로 보기에는 갈 수 있는 곳인데도 불구하고, 가지 못하는 경우가 생길 수 있다. (맨 위의 그림에 보면 오른쪽 구석에 보일 것이다.)
  
• 동적인 지형을 처리하기 어렵다.
  
  
  

4 링크

• Gamasutra > Polygon Soup for the Programmer's Soul : 3D Pathfinding
  

• see also SearchSpaceRepresentation
  

• CategoryAiProgramming