사용자 도구

사이트 도구


kb:spacefillingvolume

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

kb:spacefillingvolume [2014/11/09 20:54] (현재)
줄 1: 줄 1:
 +====== Space Filling Volume ======
 +{{spacefillingvolume_volume2.jpg}}
 +
 +Space Filling Volume은 검색 공간을 표현하는 하나의 방법이다. 위의 그림처럼 공간을 임의의 크기 박스로 채우고, 이 박스들을 일종의 노드로서 길찾기 등에 활용하는 것이다. [[NavigationMesh]]만큼 융통성이 있지는 않으나, 생성 및 이용이 쉽다.
 +
 +
 +====== 데이터 생성 ======
 +일단 3D 환경을 기반으로 한다. 즉 특정 메쉬를 입력받아,​ Space Filling Volume을 생성하는 것이 목표다.
 +
 +생성 방법에는 2가지 방법이 있다. 첫번째는 공간의 임의 지점에다 큐브를 떨어뜨리고,​ 그 큐브의 크기를 충돌이 일어나는 범위까지 늘려가는 방법이다. 두번째는 공간을 일정 크기의 그리드로 쪼갠 후, 충돌이 일어나지 않는 그리드들을 병합하는 방법이다. 첫번째 방법은 임의의 지점을 고르는 게 애매해서,​ 두번째 방법을 선택했다.
 +
 +===== 분할 =====
 +  - 먼저 입력받은 메쉬를 감쌀 수 있는 AABB를 구한다. ​
 +  - 정해진 크기 단위로 AABB를 쪼갠다.
 +    * 이 크기가 작으면 작을수록 원래 메쉬에 좀 더 가까운 Space Filling Volume이 생성되지만,​ 대신 생성 과정에 들어가는 메모리가 3제곱으로 늘어나게 된다. 이 때문에 너무 커다란 메쉬(폴리곤 수와는 상관없이 단순히 큰...)를 처리할 때에는 메모리 문제가 발생할 수 있다.
 +    * 이 쪼갠 육면체들을 셀이라 부르겠다.
 +  - 메쉬를 구성하는 모든 삼각형들과 셀들간의 충돌 체크(Triangle vs AABB)를 수행한다.
 +    * 삼각형과 충돌 가능성이 있는 셀들, 즉 삼각형을 감싸는 AABB 안에 들어가는 셀들만 충돌 체크하는 것은 기본이라고 할 수 있겠다. ​
 +  - 충돌 체크를 수행하고 나면, 갈 수 있는 셀과 갈 수 없는 셀이 분리된다.
 +
 +===== 병합 =====
 +병합은 뭐랄까, 말로 설명하기에는 약간 복잡한 관계로 슈도 코드로 보는 것이 이해가 빠를 것이다.
 +<code cpp>
 +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,​ ...);
 +                }
 +            }
 +        }
 +    }
 +}
 +</​code>​
 +이렇게 하면 병합된 육면체들을 얻어낼 수 있다. 이 육면체들을 노드라고 부르겠다.
 +
 +===== 인접 노드 계산 =====
 +노드만으로는 아직 그래프 형태의 데이터가 아니기 때문에, 길찾기에 써먹으려면,​ 어느 노드에 어느 노드가 붙어있는지를 알아내야한다. 이는 간단한 충돌체크(AABB vs AABB)를 통해 알아낼 수 있다.
 +
 +<​code>​
 +for a in all_nodes ​
 +    for b in all_nodes ​
 +        if collide(a, b)
 +            set a, b as neighbor
 +</​code>​
 +
 +===== 필요없는 노드 제거하기 =====
 +모든 노드가 필요한 것은 아니다. 갈 수 없는 노드들을 추려냄으로서 좀 더 적은 데이터를 만들어낼 수 있다. 다만 어떤 노드가 필요없는가는 애플리케이션마다 틀리다. 예를 들어보자면...
 +
 +  * 이웃 노드가 하나도 없는 노드 같은 경우, 해당 노드로 갈 방법이 없으므로 필요없다.
 +  * Y 축을 제외하고,​ XZ 평면 상으로 봤을 때 완전히 다른 노드에 포함되는 노드의 경우, 게임 상에서 날아다니는 것이 불가능하다면 필요없다.
 +
 +===== 포탈 생성하기 =====
 +이웃 노드까지 계산을 마쳤으므로 그래프 형태의 데이터가 만들어졌으나,​ 아직 이를 [[PathFinding]]에 바로 이용할 수는 없다. 노드와 노드가 이어지는 부분에 포탈을 생성해야,​ 게임 안에서 벽과 충돌하지 않는 움직임을 만들어낼 수 있다. 노드가 육면체이기 때문에 간단히 포탈을 계산할 수 있다. 두 노드 min, max 값을 더해서 2로 나누면 땡이다.
 +
 +<code cpp>
 +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
 +);
 +</​code> ​ 이 포탈들을 ((from+,​to),​portal)의 형식으로 어딘가에 저장해두면 간단히 이용할 수 있다.
 +
 +===== 결과물 =====
 +**Original Mesh**
 +
 +{{spacefillingvolume_o.jpg}}
 +
 +**Generated Volumes**
 +
 +{{spacefillingvolume_n.jpg}}
 +
 +
 +====== 단점 ======
 +단점은 주로 기본 단위가 사각형/​육면체이기 때문에 발생한다.
 +
 +  * 곡면 또는 XYZ축과 어긋난 평면이 많은 지형을 처리하기 어렵다. (상당히 치명적인 단점이다.)
 +  * 실제 움직임을 화면에 그릴 때는 보정을 많이 해줘야한다.
 +  * 눈으로 보기에는 갈 수 있는 곳인데도 불구하고,​ 가지 못하는 경우가 생길 수 있다. (맨 위의 그림에 보면 오른쪽 구석에 보일 것이다.)
 +  * 동적인 지형을 처리하기 어렵다.
 +
 +
 +====== 링크 ======
 +  * [[http://​www.gamasutra.com/​features/​20020405/​smith_01.htm | Gamasutra > Polygon Soup for the Programmer'​s Soul : 3D Pathfinding]]
 +
 +----
 +  * see also [[SearchSpaceRepresentation]]
  
kb/spacefillingvolume.txt · 마지막으로 수정됨: 2014/11/09 20:54 (바깥 편집)