[알고리즘] BVH (Bounding Volume Hierarchy)

 

게임에서는 수천 개의 모델, 총알, 파티클 등.. 많은 오브젝트가 동시에 존재한다.

 

모든 오브젝트를 매 프레임마다 전부 검사한다면....?

CPU는 순식간에 과부화가 될 것이다.

 

그래서 등장한 개념이

AABB (Axis-Aligned Bounding Box) 트리 기반의 공간 분할 및 계층적 충돌 검사이다.  

 

 

 

 

00. AABB 트리가 필요한 이유? 

앞에서 언급 했듯, 

수많은 오브젝트들을 전부 일일이 교차 검사(intersection test) 하거나 카메라 시야에 있는지(culling) 검사한다면?

CPU는 순식간에 과부화 

 

그래서 "필요 없는 건 아예 검사하지 말자" 

-> 공간을 분리하거나, 객체를 묶는 트리 구조를 사용한다.

 

이게 바로 QuadTree 또는 BVH(Bounding Volume Hierarchy) 이다. 

 

 

 

 

01. QuadTree

공간을 나눠서 관리하는 방식 

 

2D 공간을 4등분(3D라면 Octree로 8등분) 해서 공간 자체를 분할하는 구조 

 

1. 공간을 미리 4등분으로 나누고
2. 오브젝트를 자신의 위치에 맞는 노드에 삽입
3. 부모 노드의 AABB와 교차 검사해서 겹치지 않으면 서브트리 전체 스킵

 

장점

• 구현이 간단하고, 균일한 분포에서 효율적
• 프러스텀 컬링(Frustum Culling)에 유용

 

단점

• 오브젝트가 한쪽에 몰려 있으면 트리가 깊어지고, 비어 있는 노드가 많아져 비효율적

 

 

 

 

02. BVH (BoundingVolumeHierarchy)

객체를 묶는 방식

 

BVH는 공간을 나누는 대신, 오브젝트를 묶어서 계층적으로 감싸는 구조

 

 

 

• 리프 노드(Leaf): 실제 오브젝트의 AABB를 포함
• 부모 노드: 자식들의 AABB를 감싸는 합집합(Union)
• 교차 검사 시, 부모 AABB와 교차하지 않으면 자식 전체를 스킵 (Pruning: 가지치기) 가능

 

장점

• 오브젝트가 몰려 있어도 효율적
• 충돌 검사, 레이트레이싱 등에 널리 사용
• QuadTree보다 일반적인 상황에서 더 빠름

 

단점 

• 트리 구축이 복잡함 (특히 SAH 최적화 시)
• 오브젝트가 자주 움직이면 업데이트 비용이 발생

 

 

 

2-1. 좋은 BHV 트리의 조건 

"트리 품질"이 좋을수록 탐색 효율이 올라간다. 

 

BVH의 트리 품질이란?
“주어진 오브젝트 집합을 얼마나 효율적으로 계층 구조로 나누고 오브젝트를 묶어서 불필요한 탐색을 줄이느냐”를 의미

 

항목	설명
1. Surface Area 최소화	부모 AABB의 표면적이 작을수록 교차 확률 ↓
2. Overlap 최소화	형제 노드끼리 겹치지 않게 구성
3. 균형 깊이	트리의 좌우 깊이 차가 작을수록 탐색 효율 ↑
4. 리프당 오브젝트 수 적정화	너무 많으면 검사 과다, 너무 적으면 노드 폭증

 

저 품질 구조

개선된 품질 구조

 

03. BVH 구축 방식

BVH는 만드는 방법에 따라 성능이 달라진다.

 

3-1. 상향식 (Bottom-Up) : 정적 

• 리프 노드부터 생성 → 가까운 것끼리 묶음
• 품질은 좋지만 느림

 

 

3-2. 하향식 (Top-Down) : 정적 

• 모든 오브젝트를 포함한 AABB에서 시작
• 긴 축 기준으로 정렬 후, 기준점에서 분할

 

 

하향식 분할 기준 3가지

방식	설명
1. 개수 분할	오브젝트 개수를 반으로 나눔
2. 거리 분할	공간 좌표 중간값 기준 분할
3. SAH (Surface Area Heuristic)	표면적×오브젝트 수의 합이 최소가 되도록 분할

 

 

 

아래 예시 이미지를 가지고,

각 3가지 방식으로 하향식 분할을 진행하는 예시를 들어보도록 하겠다. 

 

구현이 쉽도록 자식이 2노드인 BVH2트리로 구성 하고, 

리프노드가 포함하는 오브젝트 또는 AABB의 개수는 편의상 최대 2개로 한다. 

예시 이미지

 

3-2-1. 하향식 : 오브젝트 수 분할점 결정 방식 

1. 부분 영역 2개(leaf) 이하인가?
   • 맞으면 AABB index (or ptr) 저장
   • 아니면 합집합 AABB 계산
2. 1에서의 범위를 긴 축 기준 부분 정렬
3. 개수 절반 좌/우 영역 -> 1 시도

 

 

3-2-2. 하향식 : 중간 거리 분할점 결정 방식 

1. 부분 영역 2개(leaf) 이하인가?
   • 맞으면 AABB index (or ptr) 저장
   • 아니면 합집합 AABB 계산
2. 1에서의 범위를 긴 축 기준 부분 정렬
3. 긴 축 중간기준 절반 좌/우 영역 -> 1 시도

 

 

3-2-3. 하향식 : SAH (Surface Area Heuristic)

BVH 품질을 수학적으로 최적화하는 방식

“ (왼쪽 AABB 표면적 × 왼쪽 오브젝트 수) + (오른쪽 AABB 표면적 × 오른쪽 오브젝트 수) ”
값이 가장 작은 분할점을 찾자! 

즉, “SurfaceArea × ObjectCount 합이 가장 작은 분할점을 찾자" 

float cost = S_L * N_L + S_R * N_R;
if (cost < bestCost) 
{
    bestCost = cost;
    bestSplit = i;
}

• 표면적이 작고
• 오브젝트 수가 적은 그룹을 만들수록
• 전체 충돌 검사 비용이 줄어든다. 

 

1. 현재 노드의 AABB(Axis-Aligned Bounding Box)를 계산
2. 긴 축(longest axis)을 선택 → 보통 x, y, z 중 가장 긴 축
3. 해당 축을 기준으로 모든 가능한 분할 위치 를 순회
   • (예: 자식 바운딩 박스에 포함된 프리미티브(삼각형 등)의 중심 기준 정렬 후, 각 경계 위치)
4. 각 분할 위치마다 SAH 비용 계산 
5. 모든 분할 후보 중 SAH 비용이 가장 낮은 분할점을 선택
6. 해당 기준으로 좌/우 자식 생성 → 재귀적으로 반복

 

SAH 비용 계산식은 다음과 같다.

기호	의미
C_"split"	현재 분할의 예상 탐색 비용
S_P , S_L , S_R	부모/왼쪽/오른쪽 AABB의 표면적
N_L , N_R	왼쪽/오른쪽 그룹에 속한 오브젝트 개수
C_"trav"	트리 탐색 비용= 노드 AABB 교차 검사1회 비용
C_"intersect"	오브젝트(AABB or other) 교차 테스트 비용

 

SAH에서 상수항(𝐶_𝑡 , 𝐶_𝑖 , 𝑆_𝑃) 은 모든 후보에서 동일하기 때문에 “비교” 결과에는 영향을 주지않는다.

 

 

즉, 아래와 같이 정리될 수 있는 것. 

float cost = S_L * N_L + S_R * N_R;
if (cost < bestCost) 
{
    bestCost = cost;
    bestSplit = i;
}

 

 

3-3. 추가식 : 동적 

1개씩 추가하면서  트리를 점차 구성하는 방식.

 

 

 

4. 정리 

구분	QuadTree	BVH
기준	공간 기준 분할	오브젝트 기준 묶음
자식 수	4(2D), 8(3D)	보통 2 (BVH2)
효율	균일한 분포에 유리	불균일한 분포에도 강함
용도	지형, 2D 맵	충돌 검사, 레이트레이싱
주요 최적화	없음 (고정 구조)	SAH, 중간거리, 개수 분할

 

QuadTree는 “공간을 먼저 나누는 방식 ”
BVH는 “물체를 묶어서 감싸는 방식 ”

 

 

둘 다 목표는 하나.

“필요 없는 영역은 통째로 스킵해서 연산을 줄이자.”