경계 볼륨 계층

게임 개발 컴퓨터 그래픽스 마지막 수정: 2026-07-13 04:23:44

1. 개요[편집]

백만 개 삼각형끼리 전부 충돌 검사하면 5천억 번. 일단 상자로 감싸고 보자.

경계 볼륨 계층(Bounding Volume Hierarchy, BVH)은 여러 물체(또는 삼각형)를 AABB·구 같은 단순한 경계 볼륨(bounding volume)으로 감싸고, 그것들을 다시 더 큰 볼륨으로 묶어 트리로 계층화한 공간 자료구조다. 충돌 감지와 레이 트레이싱에서 “일단 거를 건 빨리 거르는” 브로드페이즈(broad phase) 가속의 핵심으로, 무식한 $O(n^2)$ 전수 검사를 평균 $O(n \log n)$ 수준으로 끌어내린다.

발상은 단순하다. 복잡한 형상끼리 정밀 교차 판정을 하기 전에, 훨씬 싼 경계 볼륨끼리 먼저 겹치는지 물어본다. 두 상자가 안 겹치면 그 안의 삼각형들은 볼 것도 없이 통과. 이걸 트리로 재귀화하면, 광선 하나가 장면 전체가 아니라 자기가 스쳐 지나가는 가지들만 따라 내려가면 된다. 공간 분할 자료구조의 대표 격이지만, 공간이 아니라 객체를 분할한다는 점이 BSP/옥트리와 갈리는 지점이다.

2. 경계 볼륨의 선택[편집]

트리의 각 노드가 어떤 모양으로 자식을 감싸느냐는 트레이드오프의 문제다. “얼마나 딱 맞게 감싸느냐(tightness)” 대 “교차 판정이 얼마나 싸냐(test cost)“의 줄다리기.

구(sphere): 교차 판정이 가장 싸고 회전에 불변. 대신 헐렁하게 감싸서 헛방(false positive)이 많다.
AABB(축 정렬 경계 상자): 축에 정렬된 상자. 판정이 싸고 갱신이 쉬워 가장 널리 쓰인다. 물체가 회전하면 헐거워지는 게 흠.
OBB(방향 경계 상자): 물체 방향에 맞춰 기운 상자. 훨씬 타이트하지만 판정에 분리축 정리(SAT)가 필요해 비싸다.
k-DOP: $k$ 개 방향으로 자른 볼록 껍질. AABB(6-DOP)와 볼록 껍질 사이의 절충.

실무 대부분은 AABB로 시작한다. GJK 알고리즘 같은 정밀 판정은 BVH가 후보를 좁혀준 뒤에 내로우페이즈(narrow phase)에서 돌린다. BVH는 어디까지나 “볼 필요 없는 쌍을 빠르게 버리는” 1차 필터다.

3. 트리 구축 전략[편집]

같은 삼각형 집합이라도 어떻게 묶느냐에 따라 성능이 몇 배 갈린다. 크게 세 방향.

하향식(top-down): 전체를 하나의 볼륨으로 감싼 뒤, 어떤 축을 기준으로 둘로 쪼개 재귀. 구현이 쉽고 품질이 좋아 오프라인 렌더러의 기본.
상향식(bottom-up): 개별 리프에서 시작해 가까운 것끼리 병합하며 위로 올라감. 품질은 좋지만 느리다.
삽입식(insertion): 물체를 하나씩 트리에 끼워 넣음. 동적 장면에서 증분 갱신에 유리.

품질의 핵심 지표는 표면적 휴리스틱(Surface Area Heuristic, SAH)이다. 광선이 어떤 노드에 부딪힐 확률이 그 노드 표면적에 비례한다는 가정 아래, 분할 비용을 다음으로 추정한다.

C_{\text{SAH}} = C_t + \frac{A_L}{A}\, N_L\, C_i + \frac{A_R}{A}\, N_R\, C_i

여기서 $A$ 는 부모 볼륨 표면적, $A_L, A_R$ 은 좌우 자식 표면적, $N_L, N_R$ 은 각 자식이 품은 프리미티브 수, $C_t$ 는 순회 비용, $C_i$ 는 교차 판정 비용이다. 여러 후보 분할 지점 중 $C_{\text{SAH}}$ 가 최소인 곳을 고른다. SAH로 지은 BVH가 단순 중앙 분할(median split)보다 순회가 훨씬 빠른 이유가 이거다.¹

4. 순회 — 광선과 충돌 질의[편집]

BVH가 지어지면 질의는 재귀적 순회로 끝난다. 레이 트레이싱의 경우, 광선이 루트 AABB와 교차하는지 검사하고, 교차하면 두 자식으로 내려간다. 광선-AABB 교차는 슬래브(slab) 검사로 분기 없이 몇 번의 곱셈이면 된다.²

여기에 최적화 하나가 결정적이다. 광선 진행 방향으로 가까운 자식을 먼저 방문하면, 거기서 이미 교차점을 찾았을 때 그보다 먼 가지는 통째로 가지치기(pruning)할 수 있다. 이 앞-뒤 정렬 순회 덕에 실제 방문 노드 수가 극적으로 줄어든다.

충돌 질의도 똑같다. 한 물체의 AABB로 트리를 훑으며 겹치는 리프만 뽑아 좁은 후보 집합을 만든다. 두 BVH를 동시에 내려가며 교차하는 노드 쌍만 재귀하는 BVH-BVH 순회도 강체-강체 충돌에서 자주 쓴다.

5. 동적 장면과 리프레시[편집]

정적 장면이면 BVH를 한 번 짓고 끝이다. 문제는 물체가 매 프레임 움직이는 게임이다. 매번 다시 짓는 건 사치라서, 몇 가지 편법을 쓴다.

리핏(refit): 트리 구조(위상)는 그대로 두고 리프의 AABB만 실제 위치로 갱신한 뒤 위로 올려 부모 볼륨을 다시 감쌈. $O(n)$ 으로 싸지만, 물체가 크게 흩어지면 트리가 헐거워져 성능이 서서히 썩는다.³
재빌드(rebuild): 트리 품질이 임계치 아래로 떨어지면 그때 통째로 다시 짓기. 리핏과 주기적 재빌드를 섞는 게 실전 국룰.
동적 BVH: 물리 엔진(Bullet의 btDbvt 등)은 여유 마진(fat AABB)을 둔 상자로 삽입/삭제를 $O(\log n)$ 에 처리해 매 프레임 완전 재빌드를 피한다.

정리하면 BVH는 GPU 실시간 레이 트레이싱(RTX의 하드웨어 가속 대상이 바로 BVH다)부터 물리 엔진 브로드페이즈까지, “많은 것 중에서 겹치는 것만 빨리 찾기”라는 문제가 나오면 거의 항상 등장하는 자료구조다. 공간 분할 자료구조의 다른 갈래인 균등 격자·옥트리·들로네 삼각분할 기반 구조와 상황에 맞춰 골라 쓴다.

6. 관련 문서[편집]

SAH는 1987년 Goldsmith와 Salmon이 처음 제안했다. “광선이 어디 부딪힐지는 표면적으로 도박하라”는 발상인데, 놀랍게도 30년 넘게 이걸 이길 범용 휴리스틱이 안 나왔다. 도박이 과학이 된 드문 사례. ↩
슬래브 방법은 AABB를 세 쌍의 평행 평면(슬래브)의 교집합으로 보고, 광선이 각 슬래브에 들어오고 나가는 $t$ 구간을 겹쳐 교차 여부를 판정한다. IEEE 부동소수점의 무한대 처리 덕에 축에 평행한 광선도 분기 없이 처리되는 게 은근한 묘미. 자세한 건 부동소수점 연산 참고. ↩
리핏만 계속 하면 트리가 “부어오른다(bloating)”. 처음엔 딱 맞던 상자들이 물체가 흩어지며 서로 잔뜩 겹쳐, 결국 순회가 전수검사만큼 느려진다. 게을러서 청소 안 한 방 같은 것. ↩