BVH와 BVTT 완전 정복 (AI로 글 쓰고 수정한 글)

1. 왜 필요한가? — O(n²)의 벽

3D 씬에 물체가 1,000개 있다고 해봐요. 매 프레임마다 "이 물체들이 서로 충돌하는가?"를 확인하려면, 단순하게 모든 쌍을 검사하면 되요.

for A in objects:    for B in objects:        if A != B:            check_collision(A, B)

이 브루트포스 방식의 복잡도는 O(n²). 물체 1,000개 → 약 500,000번 검사, 10,000개면 5천만 번. 60fps 게임에서는 프레임당 이 연산을 반복해야 해요. 당연히 실용적이지 않아요.

해결의 핵심 아이디어는 "겹칠 가능성이 없는 물체들은 검사 자체를 하지 않는다." 이에요

여기서 등장하는 것이 바운딩 볼륨(BB)와 BVH에요.

2. 바운딩 볼륨(BB) — 정밀도를 버리고 속도를 얻다

복잡한 메시 형태 그대로 충돌을 검사하는 건 너무 비싸요. 대신 충돌을 확인할 때는 물체를 단순한 기하 형태로 감싸는 바운딩 볼륨을 사용해요.

위 그림이 Bounding Box 모델 예시에요.

가장 흔하게 쓰이는 건 AABB(Axis-Aligned Bounding Box)에요. 세계 좌표축에 정렬된 단순한 직육면체로, 두 AABB의 겹침 검사는 각 축의 구간 비교 6번으로 끝나요. 빠르지만 회전된 물체에는 낭비가 더 많이 생기긴 해요. 그래서 OBB와 같이 축을 틀어서 쓰는 바운딩 박스를 사용할 수 있어요.

3. BVH — 공간을 계층적으로 쪼갠다

바운딩 볼륨만으로는 아직 부족해요. 충돌을 비교하기 더 쉬워졌지만 여전히 모든 물체에 대해서 검사해야해요. 게임에서 씬의 모든 물체를 여전히 순회해야 하는 것과 같아요. BVH(Bounding Volume Hierarchy)는 이 물체들을 이진 트리 구조로 묶어, "부모 박스와 겹치지 않으면 자식 전체를 스킵"할 수 있게 해요.

BVH 노드 구조

struct BVHNode:    aabb:   AABB      // 이 노드를 감싸는 바운딩 박스    left:   BVHNode   // 왼쪽 자식 (null이면 리프)    right:  BVHNode   // 오른쪽 자식 (null이면 리프)    object: Object    // 리프 노드일 때만 유효

BVH 구축 (Top-down, 재귀 분할) - 중간값 분할

function buildBVH(objects):    node.aabb = computeAABB(objects)      // 전체를 감싸는 박스    if len(objects) == 1:        node.object = objects[0]          // 리프 노드        return node    axis   = longestAxis(node.aabb)       // 가장 긴 축으로 분할 (물체가 가장 긴 방향)    sorted = sortByAxis(objects, axis)    mid    = len(sorted) / 2    node.left  = buildBVH(sorted[:mid])    node.right = buildBVH(sorted[mid:])    return node

레이 교차 탐색 - SAH 분할 활용

function rayIntersect(node, ray):    if not intersects(node.aabb, ray):        return null                        // 이 서브트리 전체 스킵    if isLeaf(node):        return preciseIntersect(node.object, ray)    hitLeft  = rayIntersect(node.left,  ray)    hitRight = rayIntersect(node.right, ray)    return closest(hitLeft, hitRight)

> SAH(Surface Area Heuristic): 단순히 중간값으로 분할하는 대신, 각 분할 후보의 표면적 비율로 예상 탐색 비용을 계산해 가장 효율적인 분할축을 선택해요. 레이트레이싱 엔진에서 필수적이라고 해요. 아래 그림이 중간값으로 분할하는 것과 SAH로 분할하는 차이를 보여줘요.

4. BVTT — 두 BVH를 동시에 내려간다

BVH 하나로는 "레이(광선, 빛)이 어떤 물체에 맞는가"를 찾을 수 있어요. 하지만 "캐릭터 A와 캐릭터 B가 충돌하는가?" 처럼 두 복잡한 오브젝트 사이의 충돌을 찾으려면 달라요.

각 오브젝트가 자체 BVH를 갖고 있을 때, BVTT(Bounding Volume Traversal Tree)는 두 BVH를 동시에 재귀 순회하며 충돌 쌍을 좁혀가요.

BVTT 순회

function traverseBVTT(nodeA, nodeB, results):    // 두 노드의 AABB가 겹치지 않으면 이 쌍 전체 스킵    if not overlaps(nodeA.aabb, nodeB.aabb):        return    // 둘 다 리프면 정밀 충돌 검사    if isLeaf(nodeA) and isLeaf(nodeB):        results.add(preciseCheck(nodeA.object, nodeB.object))        return    // 더 큰 노드를 먼저 분할 (비용 최소화)    if volume(nodeA) >= volume(nodeB):        traverseBVTT(nodeA.left,  nodeB, results)        traverseBVTT(nodeA.right, nodeB, results)    else:        traverseBVTT(nodeA, nodeB.left,  results)        traverseBVTT(nodeA, nodeB.right, results)

핵심은 단순해요. 두 노드의 AABB가 겹치지 않으면, 그 아래 자식 쌍은 절대로 충돌할 수 없어요. 그래서 서브트리 전체를 가지치기하는 거에요. 복잡도는 O(log n · log m)가 되요.

5. BVH와 BVTT 요약

실무에서 둘은 보통 함께 쓰여요. 씬 전체 BVH로 "충돌 후보 쌍"을 추려내고(broad phase), 그 쌍에 대해 각 오브젝트의 BVH를 BVTT로 정밀 검사해요(narrow phase)

6. 실제 엔진에서

- Unity Physics / PhysX: 씬 BVH(DBVT)로 broad phase, 각 오브젝트 convex hull BVH로 narrow phase

- Unreal Engine: `FBVHTree` 클래스가 BVH 관리, `FChaosPhysics`에서 BVTT 기반 충돌 쌍 수집

- 레이트레이싱 (DXR, NVIDIA OptiX): GPU 가속 BVH 탐색, RTX BVH 하드웨어 유닛으로 처리

- FCL (Flexible Collision Library): 로보틱스/시뮬레이션용 오픈소스, BVTT 기반 충돌 쿼리 제공

마무리

BVH와 BVTT는 결국 같은 핵심 아이디어의 두 가지 적용이에요. "겹칠 수 없는 공간은 일찍 버린다." BVH가 씬과 레이 사이의 문제를 풀었다면, BVTT는 그 아이디어를 두 복잡한 오브젝트 사이의 문제로 확장한거에요.

위 사진은 저가 VTK로 여러 물체간 Intersection되는 부분을 강조하여 렌더링 하는 사진이에요. vtk를 활용하여 데이터가 바껴도 빠르게 리렌더링 가능하도록 만들었어요. 처음에는 Vertex가 겹치면 되겠지라는 단순한 생각을 했는데, 생각해보니 면(face)가 교차해야만 서로 충돌하는 것이기 때문에 복잡해지더라고요. 그래서 충돌지점을 빠르게 찾는 방법들을 찾다가 BVH와 BVTT까지 공부하게 되었어요.