Voxel Terrain

1. Voxel Terrain 이란?

복셀(Voxel)은 '부피(Volume)'와 '픽셀(Pixel)'의 합성어로, 3D 공간에서 특정 지점의 데이터를 표현하는 가장 작은 단위입니다. 2D의 픽셀이 x, y 좌표와 색상 값을 가지는 것처럼, 복셀은 x, y, z 좌표와 함께 특정 속성(예: 재질, 밀도, 색상 등)을 가집니다.

복셀 터레인은 이러한 복셀들을 3D 그리드(Grid) 형태로 배열하여 지형을 구성하는 기술입니다. 가장 대표적인 예시는 게임 '마인크래프트(Minecraft)'의 세계로, 모든 것이 정육면체 블록(복셀)으로 이루어져 있습니다.

복셀 터레인의 특징

• 데이터 기반 지형: 폴리곤 메시(Polygon Mesh)가 정점(Vertex)과 면(Face)으로 표면을 정의하는 것과 달리, 복셀 터레인은 3D 공간 전체를 데이터로 채웁니다.
• 동적 수정 용이성: 그리드 내의 복셀 데이터를 변경하는 것만으로 지형을 실시간으로 파괴하거나 생성하기 용이합니다.
• 복잡한 내부 구조 표현: 지형의 표면뿐만 아니라 동굴과 같은 내부 구조나 다양한 재질의 분포를 자연스럽게 표현할 수 있습니다.

---

2. 내부 구조 (Internal Structure)

거대한 복셀 세계를 효율적으로 관리하기 위해 다음과 같은 구조가 일반적으로 사용됩니다.

가. 3D 배열 (3D Array)

가장 단순한 형태는 거대한 3D 배열을 사용하여 월드 전체의 복셀 데이터를 저장하는 것입니다.

BlockType world[width][height][depth];

• 장점: 특정 좌표의 복셀에 O(1) 시간 복잡도로 접근할 수 있어 매우 빠릅니다.
• 단점: 월드가 조금만 커져도 엄청난 메모리를 소모하며, 대부분이 비어있는 '공기' 블록일 경우 심각한 메모리 낭비가 발생합니다.

나. 청크 (Chunks)

메모리 문제를 해결하고 성능을 최적화하기 위해 전체 월드를 일정한 크기(예: 16x256x16)의 청크 단위로 나눕니다.

// Chunk 클래스는 내부에 작은 3D 배열을 가짐
class Chunk {
    BlockType blocks[16][256][16];
};

// 월드는 청크들을 관리
std::map<ChunkCoord, Chunk*> worldChunks;

• 동적 로딩/언로딩: 플레이어 주변의 청크만 메모리에 로드하고, 멀리 있는 청크는 언로드하여 메모리 사용량을 크게 줄일 수 있습니다.
• 병렬 처리: 각 청크의 메시 생성(Meshing)이나 물리 계산을 별도의 스레드에서 병렬로 처리하기 용이합니다.

다. 복셀 데이터 (Voxel Data)

각 복셀은 보통 다음과 같은 데이터를 가집니다.

• 블록 ID (Block ID): 공기, 흙, 돌, 물 등 블록의 종류를 나타내는 정수 값.
• 메타데이터 (Metadata): 블록의 방향, 상태 등 추가적인 정보를 저장하는 값.

라. 옥트리 (Octrees)

월드가 매우 크고 대부분 비어있을 때(예: 우주 공간) 사용되는 고급 자료구조입니다. 공간을 8개의 정육면체 노드로 재귀적으로 분할하여 데이터가 있는 영역만 세분화하고, 비어있는 넓은 공간은 단일 노드로 표현하여 메모리를 절약합니다.

---

3. 구현 방식 (Meshing Algorithms)

복셀 데이터는 그 자체로는 렌더링할 수 없습니다. GPU가 렌더링할 수 있는 폴리곤 메시(삼각형의 집합)로 변환하는 과정이 필요한데, 이를 메시 생성(Meshing)이라고 합니다.

가. 단순 컬링 (Naive Face Culling)

가장 간단한 방법은 모든 복셀을 정육면체로 간주하고, 공기와 맞닿아 있는 면만 렌더링하는 것입니다.

• 로직: 특정 복셀의 6방향(상하좌우앞뒤)을 검사하여 인접한 복셀이 공기(Air) 블록이면 해당 방향의 면(Quad)을 생성합니다.
• 장점: 구현이 매우 간단합니다.
• 단점: 같은 재질의 넓은 평면이라도 각 블록마다 개별적인 면을 생성하므로 정점(Vertex) 수가 불필요하게 많아집니다.

나. 그리디 메시 생성 (Greedy Meshing)

단순 컬링의 단점을 개선한 알고리즘입니다. 인접한 같은 종류의 복셀들의 면을 하나의 큰 사각형(Quad)으로 합칩니다.

• 로직:
  1. 월드를 X, Y, Z 축 중 하나의 축을 기준으로 2D 슬라이스(Slice)로 나눕니다.
  2. 각 슬라이스를 순회하며 아직 처리되지 않은 복셀을 찾습니다.
  3. 해당 복셀을 시작점으로, 같은 재질의 복셀이 이어지는 가장 넓은 사각형을 찾습니다.
  4. 이 사각형을 다음 슬라이스로 이동시키며 같은 형태의 사각형이 얼마나 깊이(Depth) 이어지는지 확인합니다.
  5. 최종적으로 만들어진 거대한 육면체의 겉면들을 생성하고, 여기에 포함된 모든 복셀들을 '처리됨'으로 표시합니다.
• 장점: 정점 수를 극적으로 줄여 렌더링 성능을 크게 향상시킵니다. '마인크래프트'와 같은 블록 스타일의 세계에 매우 적합합니다.
• 단점: 로직이 복잡하고, 부드러운 곡면 지형에는 적합하지 않습니다.

다. 마칭 큐브 (Marching Cubes)

블록 형태가 아닌, 부드럽고 유기적인 지형(예: 동굴, 언덕)을 만들 때 사용되는 고전적인 알고리즘입니다.

• 로직:
  1. 복셀 데이터를 밀도(Density) 값의 스칼라 필드(Scalar Field)로 간주합니다. (예: 0 이상은 땅, 0 미만은 공기)
  2. 8개의 인접한 복셀(하나의 큐브)을 단위로 검사합니다.
  3. 8개 꼭짓점의 밀도 값이 0보다 큰지 작은지에 따라 총 2^8 = 256가지의 케이스가 발생합니다.
  4. 각 케이스에 대해 어떤 모양의 삼각형을 생성해야 하는지 미리 정의된 테이블(Lookup Table)을 참조하여 메시를 생성합니다.
• 장점: 매우 부드럽고 자연스러운 지형을 만들 수 있습니다.
• 단점: 생성되는 폴리곤 수가 많고, 알고리즘의 위상적 문제로 인해 날카로운 경계를 표현하기 어렵다는 단점이 있습니다. (이를 개선한 것이 Dual Contouring 등의 알고리즘입니다.)

---

4. 예제 코드 (Greedy Meshing)

#include <iostream>
#include <vector>
#include <array>

constexpr int CHUNK_WIDTH  = 16;
constexpr int CHUNK_HEIGHT = 16;
constexpr int CHUNK_DEPTH  = 16;

struct Quad
{
    std::array<int, 3> position;
    std::array<int, 3> dimensions;
    std::array<int, 3> normal;
};

// Helper for 3D indexing
inline int index3D(int x, int y, int z, int W, int H, int D)
{
    return x * H * D + y * D + z;
}

std::vector<Quad> greedyMeshing(
    const std::vector<int>& voxels,
    int W, int H, int D
)
{
    std::vector<Quad> quads;
    std::vector<bool> mask(W * H * D, false);

    int dims[3] = { W, H, D };

    // Loop over axes
    for (int d = 0; d < 3; ++d)
    {
        int u = (d + 1) % 3;
        int v = (d + 2) % 3;

        int x[3] = { 0, 0, 0 };
        int q[3] = { 0, 0, 0 };
        q[d] = 1;

        for (x[d] = -1; x[d] < dims[d]; ++x[d])
        {
            for (x[v] = 0; x[v] < dims[v]; ++x[v])
            {
                for (x[u] = 0; x[u] < dims[u]; ++x[u])
                {
                    int idx = index3D(x[0], x[1], x[2], W, H, D);
                    if (mask[idx])
                        continue;

                    int voxelCurrent = (x[d] >= 0 && x[d] < dims[d])
                        ? voxels[idx]
                        : 0;

                    bool behindIdxValid = (x[d] - 1 >= 0 && x[d] - 1 < dims[d]);
                    int voxelBehind = behindIdxValid
                        ? voxels[index3D(
                            x[0] - q[0],
                            x[1] - q[1],
                            x[2] - q[2],
                            W, H, D)]
                        : 0;

                    if (voxelCurrent == voxelBehind)
                        continue;

                    int w = 1;
                    int h = 1;

                    int du[3] = { 0, 0, 0 };
                    du[u] = 1;

                    while (x[u] + w < dims[u])
                    {
                        int nx = x[0] + du[0] * w;
                        int ny = x[1] + du[1] * w;
                        int nz = x[2] + du[2] * w;

                        int nIdx = index3D(nx, ny, nz, W, H, D);
                        if (mask[nIdx])
                            break;

                        int nextCurrent = voxels[nIdx];
                        int nextBehind = behindIdxValid
                            ? voxels[index3D(
                                nx - q[0],
                                ny - q[1],
                                nz - q[2],
                                W, H, D)]
                            : 0;

                        if (nextCurrent == voxelCurrent &&
                            nextBehind == voxelBehind)
                        {
                            ++w;
                        }
                        else
                        {
                            break;
                        }
                    }

                    int dv[3] = { 0, 0, 0 };
                    dv[v] = 1;

                    bool done = false;
                    while (x[v] + h < dims[v] && !done)
                    {
                        for (int k = 0; k < w; ++k)
                        {
                            int nx = x[0] + du[0] * k + dv[0] * h;
                            int ny = x[1] + du[1] * k + dv[1] * h;
                            int nz = x[2] + du[2] * k + dv[2] * h;

                            int nIdx = index3D(nx, ny, nz, W, H, D);
                            if (mask[nIdx])
                            {
                                done = true;
                                break;
                            }

                            int nextCurrent = voxels[nIdx];
                            int nextBehind = behindIdxValid
                                ? voxels[index3D(
                                    nx - q[0],
                                    ny - q[1],
                                    nz - q[2],
                                    W, H, D)]
                                : 0;

                            if (nextCurrent != voxelCurrent ||
                                nextBehind != voxelBehind)
                            {
                                done = true;
                                break;
                            }
                        }

                        if (!done)
                            ++h;
                    }

                    Quad quad{};
                    quad.position = { x[0], x[1], x[2] };
                    quad.dimensions = { 0, 0, 0 };
                    quad.dimensions[u] = w;
                    quad.dimensions[v] = h;

                    quad.normal = { 0, 0, 0 };
                    quad.normal[d] = (voxelCurrent > 0) ? 1 : -1;

                    if (voxelCurrent == 0)
                        quad.position[d] -= 1;

                    quads.push_back(quad);

                    for (int l = 0; l < h; ++l)
                    {
                        for (int k = 0; k < w; ++k)
                        {
                            int mx = x[0] + du[0] * k + dv[0] * l;
                            int my = x[1] + du[1] * k + dv[1] * l;
                            int mz = x[2] + du[2] * k + dv[2] * l;

                            mask[index3D(mx, my, mz, W, H, D)] = true;
                        }
                    }

                    x[u] += w - 1;
                }
            }
        }
    }

    return quads;
}

int main()
{
    std::vector<int> voxels(
        CHUNK_WIDTH * CHUNK_HEIGHT * CHUNK_DEPTH, 0);

    // Ground
    for (int x = 0; x < CHUNK_WIDTH; ++x)
        for (int y = 0; y < 4; ++y)
            for (int z = 0; z < CHUNK_DEPTH; ++z)
                voxels[index3D(x, y, z,
                    CHUNK_WIDTH, CHUNK_HEIGHT, CHUNK_DEPTH)] = 1;

    // Walls
    for (int y = 4; y < 8; ++y)
        for (int z = 0; z < CHUNK_DEPTH; ++z)
        {
            voxels[index3D(0, y, z,
                CHUNK_WIDTH, CHUNK_HEIGHT, CHUNK_DEPTH)] = 2;
            voxels[index3D(CHUNK_WIDTH - 1, y, z,
                CHUNK_WIDTH, CHUNK_HEIGHT, CHUNK_DEPTH)] = 2;
        }

    // Small structure
    for (int x = 5; x < 8; ++x)
        for (int z = 5; z < 8; ++z)
            voxels[index3D(x, 4, z,
                CHUNK_WIDTH, CHUNK_HEIGHT, CHUNK_DEPTH)] = 1;

    auto quads = greedyMeshing(
        voxels, CHUNK_WIDTH, CHUNK_HEIGHT, CHUNK_DEPTH);

    std::cout << "Generated " << quads.size()
              << " quads\n";

    for (const auto& q : quads)
    {
        std::cout
            << "Pos(" << q.position[0] << ", "
                        << q.position[1] << ", "
                        << q.position[2] << ") "
            << "Size(" << q.dimensions[0] << ", "
                         << q.dimensions[1] << ", "
                         << q.dimensions[2] << ") "
            << "Normal(" << q.normal[0] << ", "
                           << q.normal[1] << ", "
                           << q.normal[2] << ")\n";
    }

    return 0;
}