BVH(Bounding Volume Hierarchy)로 대규모 물리 쿼리 최적화하기: 원리부터 C# 구현까지

TL;DR

BVH(Bounding Volume Hierarchy)는 계층적 경계 볼륨(주로 AABB)을 트리 형태로 구성하여 물리 쿼리 및 레이캐스트의 시간 복잡도를 $O(N)$ 에서 $O(\log N)$ 으로 줄이는 공간 분할 기법입니다.

균일 격자(Grid)나 옥트리(Octree)와 달리 오브젝트 밀집도에 유연하게 대응하며 SAH(Surface Area Heuristic) 분할 기준과 스택 기반 비재귀 탐색을 결합하면 대규모 총알 궤적 계산, 시야 판정, 커스텀 물리 쿼리를 높은 프레임률로 처리할 수 있습니다.

왜 대규모 게임에서 단순 물리 쿼리는 급격한 성능 저하를 일으킬까?

수천 개 이상의 액터나 발사체가 공존하는 MMORPG, 탄막 슈팅, 대규모 RTS 게임에서는 매 프레임 수많은 레이캐스트(Raycast)와 오버랩(Overlap) 검사가 실행됩니다. 공간 분할 없이 모든 오브젝트를 순회하며 충돌을 검사하면 $N$ 개의 레이와 $M$ 개의 타깃에 대해 $O(N \times M)$ 의 브루트포스(Brute-force) 연산이 발생합니다.

오브젝트가 10,000개일 때 레이 100개만 발사해도 1,000,000번의 프리미티브 교차 검정이 발생하여 메인 스레드의 프레임 드롭을 유발합니다. 이를 해결하기 위해 3D 공간을 효율적으로 묶어 불필요한 충돌 계산을 조기에 건너뛰는 공간 분할 기법이 필수적입니다.

공간 분할 기법	분할 기준	밀집도 불균일 대응	동적 객체 갱신 비용	주 활용 영역
단순 그리드 (Grid)	고정 크기 셀	취약 (비어있거나 과밀)	매우 낮음	오픈월드 2D 타일, 균등 분산 환경
옥트리 (Octree)	공간 8등분 재귀 분할	보통 (고정 분할선)	중간	정적 복셀, LOD 렌더링
BVH	객체 중심 계층적 볼륨	매우 우수 (객체 적응형)	중간~높음	광선 추적, 레이캐스트, 물리 엔진
KD-Tree	축 정렬 분할 평면	우수	높음	포인트 클라우드, 정적 지형

공간 분할 방식별 볼륨 구성 비교

BVH(Bounding Volume Hierarchy)의 핵심 구조와 동작 원리

BVH는 기하학적 형상(Mesh, Capsule, Box 등)을 완전히 감싸는 AABB(Axis-Aligned Bounding Box)를 리프(Leaf) 노드로 두고 인접한 볼륨들을 상위 부모 노드가 계층적으로 묶어 최상위 루트 노드까지 연결하는 이진 트리(Binary Tree) 구조입니다.

레이캐스트를 수행할 때 상위 노드의 AABB와 레이가 교차하지 않는다면 해당 노드의 모든 하위 자식 노드는 검사 대상에서 즉시 제외(Early Pruning)됩니다.

flowchart TD
    Root["Root Node (AABB All)"]
    L1["Left Child (AABB Group A)"]
    R1["Right Child (AABB Group B)"]
    L2A["Leaf: Actor 1"]
    L2B["Leaf: Actor 2"]
    R2A["Leaf: Actor 3"]
    R2B["Leaf: Actor 4"]

    Root --> L1
    Root --> R1
    L1 --> L2A
    L1 --> L2B
    R1 --> R2A
    R1 --> R2B

분할 품질을 결정하는 SAH(Surface Area Heuristic)

트리를 어떻게 분할하느냐에 따라 탐색 속도가 크게 달라집니다. 단순히 공간을 절반으로 나누거나 오브젝트 개수를 균등 분할하면 AABB 겹침이 심해져 탐색 가지치기 효율이 떨어집니다. 이를 통계적으로 최적화하는 기준이 SAH(표면적 휴리스틱)입니다.

어떤 노드 $N$ 을 두 자식 $A$ 와 $B$ 로 나눌 때의 예상 순회 비용은 다음과 같습니다.

\text{Cost}(A, B) = C_{trav} + \frac{S_A}{S_N} \cdot N_A \cdot C_{isect} + \frac{S_B}{S_N} \cdot N_B \cdot C_{isect}

$C_{trav}$ : 내부 노드 순회(Traverse) 비용
$C_{isect}$ : 프리미티브 교차 검정(Intersection) 비용
$S_N$ : 부모 노드의 표면적
$S_A, S_B$ : 분할된 자식 노드 $A, B$ 의 표면적
$N_A, N_B$ : 자식 노드에 포함된 프리미티브 개수

표면적이 작을수록 무작위 광선이 해당 볼륨과 충돌할 확률이 낮아지므로 SAH 비용을 최소화하는 분할 축과 위치를 선택하여 최적의 트리를 구성합니다.

C# 기반 커스텀 BVH를 단계별로 어떻게 구현할까?

게임 엔진의 GC(가비지 컬렉션) 오버헤드를 없애고 메모리 캐시 지역성(Cache Locality)을 극대화하기 위해 클래스 참조 트리 대신 연속된 구조체 배열(Flat Array) 형태로 BVH를 구축합니다.

1단계: AABB 구조체 및 고속 Slab 교차 검정

레이와 AABB 간의 교차 검정은 나눗셈을 미리 역수로 변환하여 곱셈으로 처리하는 Kay-Kajiya Slab 알고리즘을 사용합니다.

using System;
using System.Runtime.CompilerServices;
using UnityEngine;

public struct AABB
{
    public Vector3 Min;
    public Vector3 Max;

    public Vector3 Center => (Min + Max) * 0.5f;
    public Vector3 Size => Max - Min;

    public float SurfaceArea
    {
        get
        {
            Vector3 d = Size;
            return 2.0f * (d.x * d.y + d.y * d.z + d.z * d.x);
        }
    }

    public void Encapsulate(AABB other)
    {
        Min = Vector3.Min(Min, other.Min);
        Max = Vector3.Max(Max, other.Max);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool IntersectRay(Vector3 rayOrigin, Vector3 invRayDir, float maxDistance)
    {
        float t0X = (Min.x - rayOrigin.x) * invRayDir.x;
        float t1X = (Max.x - rayOrigin.x) * invRayDir.x;
        float tmin = Mathf.Min(t0X, t1X);
        float tmax = Mathf.Max(t0X, t1X);

        float t0Y = (Min.y - rayOrigin.y) * invRayDir.y;
        float t1Y = (Max.y - rayOrigin.y) * invRayDir.y;
        tmin = Mathf.Max(tmin, Mathf.Min(t0Y, t1Y));
        tmax = Mathf.Min(tmax, Mathf.Max(t0Y, t1Y));

        float t0Z = (Min.z - rayOrigin.z) * invRayDir.z;
        float t1Z = (Max.z - rayOrigin.z) * invRayDir.z;
        tmin = Mathf.Max(tmin, Mathf.Min(t0Z, t1Z));
        tmax = Mathf.Min(tmax, Mathf.Max(t0Z, t1Z));

        return tmax >= Mathf.Max(0.0f, tmin) && tmin <= maxDistance;
    }
}

2단계: 배열 기반 노드 정의 및 재귀 트리 빌드

public struct BVHNode
{
    public AABB Bounds;
    public int LeftChildIndex;   // 리프 노드일 경우 -1
    public int RightChildIndex;
    public int PrimitiveOffset;  // 인덱스 배열 내 시작 위치
    public int PrimitiveCount;   // 0이면 내부 노드, 1 이상이면 리프 노드

    public bool IsLeaf => PrimitiveCount > 0;
}

public class CustomBVH
{
    public BVHNode[] Nodes;
    public int[] PrimitiveIndices;
    public AABB[] PrimitiveBounds;
    private int _nodeCount;

    public void Build(AABB[] bounds)
    {
        PrimitiveBounds = bounds;
        int n = bounds.Length;
        PrimitiveIndices = new int[n];
        for (int i = 0; i < n; i++) PrimitiveIndices[i] = i;

        Nodes = new BVHNode[n * 2 - 1];
        _nodeCount = 0;

        BuildRecursive(0, n);
    }

    private int BuildRecursive(int start, int count)
    {
        int nodeIndex = _nodeCount++;
        AABB totalBounds = PrimitiveBounds[PrimitiveIndices[start]];
        for (int i = start + 1; i < start + count; i++)
        {
            totalBounds.Encapsulate(PrimitiveBounds[PrimitiveIndices[i]]);
        }

        if (count <= 2) // 리프 노드 조건
        {
            Nodes[nodeIndex] = new BVHNode
            {
                Bounds = totalBounds,
                LeftChildIndex = -1,
                RightChildIndex = -1,
                PrimitiveOffset = start,
                PrimitiveCount = count
            };
            return nodeIndex;
        }

        // 가장 긴 축을 기준으로 분할
        Vector3 size = totalBounds.Size;
        int axis = 0;
        if (size.y > size.x) axis = 1;
        if (size.z > (axis == 0 ? size.x : size.y)) axis = 2;

        // 중점 기준 퀵셀렉트 분할
        int mid = start + count / 2;
        Array.Sort(PrimitiveIndices, start, count, new CentroidComparer(PrimitiveBounds, axis));

        int left = BuildRecursive(start, mid - start);
        int right = BuildRecursive(mid, start + count - mid);

        Nodes[nodeIndex] = new BVHNode
        {
            Bounds = totalBounds,
            LeftChildIndex = left,
            RightChildIndex = right,
            PrimitiveOffset = start,
            PrimitiveCount = 0
        };

        return nodeIndex;
    }

    private struct CentroidComparer : System.Collections.Generic.IComparer<int>
    {
        private readonly AABB[] _bounds;
        private readonly int _axis;

        public CentroidComparer(AABB[] bounds, int axis)
        {
            _bounds = bounds;
            _axis = axis;
        }

        public int Compare(int a, int b)
        {
            float ca = _bounds[a].Center[_axis];
            float cb = _bounds[b].Center[_axis];
            return ca.CompareTo(cb);
        }
    }
}

3단계: 스택 기반 비재귀 Raycast 탐색

콜 스택 오버헤드를 방지하기 위해 로컬 배열 기반의 LIFO 스택으로 비재귀 트래버설을 구현합니다.

public bool Raycast(Vector3 origin, Vector3 direction, float maxDistance, out int hitIndex)
{
    hitIndex = -1;
    float closestHit = maxDistance;
    Vector3 invDir = new Vector3(1.0f / direction.x, 1.0f / direction.y, 1.0f / direction.z);

    int[] stack = new int[64];
    int stackPtr = 0;
    stack[stackPtr++] = 0; // 루트 노드 푸시

    while (stackPtr > 0)
    {
        int currentIndex = stack[--stackPtr];
        ref BVHNode node = ref Nodes[currentIndex];

        if (!node.Bounds.IntersectRay(origin, invDir, closestHit))
        {
            continue;
        }

        if (node.IsLeaf)
        {
            for (int i = 0; i < node.PrimitiveCount; i++)
            {
                int primId = PrimitiveIndices[node.PrimitiveOffset + i];
                if (PrimitiveBounds[primId].IntersectRay(origin, invDir, closestHit))
                {
                    hitIndex = primId;
                    // 정밀 지오메트리 교차 검정 후 거리 갱신
                }
            }
        }
        else
        {
            // 자식 노드 순회 스택 푸시
            stack[stackPtr++] = node.RightChildIndex;
            stack[stackPtr++] = node.LeftChildIndex;
        }
    }

    return hitIndex != -1;
}

BVH 스택 기반 순회 및 AABB 컬링 과정

동적 객체(Dynamic Object) 업데이트와 리핏(Refit) 최적화 전략

모든 오브젝트가 매 프레임 이동하는 환경에서 트리를 매번 새로 구축(Full Rebuild)하는 것은 CPU 부담이 큽니다. 동적 갱신은 다음 두 가지 방식을 혼합하여 처리합니다.

바텀업 리핏(Bottom-up Refit): 기존 트리의 계층 구조는 그대로 유지하고 리프 노드의 이동된 AABB로부터 부모 노드의 경계 볼륨만 상향식으로 재계산합니다. 연산 비용은 $O(N)$ 으로 매우 낮지만 시간이 지남에 따라 트리 품질이 저하됩니다.
더블 트리 기법 (Static-Dynamic Partitioning): 움직이지 않는 정적 지형/건물은 SAH로 정밀하게 1회 구축(Static BVH)하고 빠르게 이동하는 탄환/유닛은 팽창된 경계 볼륨(Fat AABB) 기반의 경량 BVH(Dynamic BVH)로 분리 관리합니다.

자주 묻는 질문 (FAQ)

Q1: 옥트리(Octree) 대신 BVH를 선택해야 하는 명확한 기준은 무엇인가요?

오브젝트가 맵 전체에 고르게 분산되어 있지 않고 특정 지점에 과밀하게 몰리는 형태(예: 보스 몬스터 주위의 군중, 함대 전투)라면 BVH가 압도적으로 유리합니다. 옥트리는 고정된 공간 분할선을 사용하므로 특정 서브노드에 수천 개의 객체가 몰릴 때 깊이가 비정상적으로 깊어지거나 분할 효율이 급락하지만 BVH는 객체의 수량을 기준으로 적응형 볼륨을 만들기 때문에 항상 균형 잡힌 트리 깊이를 유지합니다.

Q2: 매 프레임 위치가 변하는 수많은 동적 객체는 어떻게 처리해야 트리 재구축 비용을 줄일 수 있나요?

오브젝트의 실제 크기보다 약간 큰 여유 마진을 둔 Fat AABB를 적용하십시오. 오브젝트가 이동하더라도 Fat AABB 경계 안에 머물러 있다면 BVH 노드를 전혀 갱신하지 않고 스킵할 수 있습니다. 경계를 벗어날 때만 해당 노드를 트리에 재삽입(Re-insertion)하거나 프레임 분할 리핏(Time-sliced Refitting)을 수행하여 갱신 비용을 분산합니다.

Q3: Unity Physics(PhysX)가 내장되어 있는데 커스텀 BVH를 직접 구현하는 이유는 무엇인가요?

PhysX 메인 씬의 물리 월드는 컴포넌트 라이프사이클과 충돌 파이프라인의 오버헤드가 수반됩니다. 서버-클라이언트 공통 결정론적(Deterministic) 탄도 시뮬레이션, GPU 기반 연산 전 단계의 CPU 컬링, 시야 차폐(Visibility/FoW) 판정, 대규모 ECS/Job System 환경에서는 관리되지 않는 네이티브 메모리(NativeArray)와 결합된 순수 C# BVH가 메모리 레이아웃 제어 및 버스트(Burst) 컴파일 최적화 측면에서 훨씬 높은 처리량을 제공합니다.

정리하며

BVH는 3D 그래픽스 레이트레이싱뿐만 아니라 현대 대규모 게임 클라이언트의 물리 쿼리 병목을 해소하는 핵심 자료구조입니다.

연속 배열 기반의 캐시 친화적 메모리 구조, Slab 기반 고속 AABB 교차 검정, 정적/동적 객체 분리 전략을 결합하여 수만 개의 물리 쿼리를 지연 없이 안정적으로 처리해 보시기 바랍니다.