[알고리즘] BVH vs Quad/Octree: 차이점, 장단점, 게임엔진 활용 예시

 

지금까지 QuadTree와 BVH 에 대해서 각각 알아보았는데,

그럼 각각은 어떤 차이점이 있고, 또 각각은 어디에서 사용하면 되는건지 정리해보고자 한다.

 

 

Quad/Octree는 공간을 기준으로 나눈다.
BVH는 객체(AABB)를 기준으로 묶는다.

 

 

 

구분	Quad/Octree	BVH
분할 기준	공간을 일정 규칙으로 고정 분할	객체(primitive)의 분포에 따라 적응적 분할
트리 생성 방식	공간 기반	객체 기반
노드 크기	고정된 공간 분할 규칙 기반	객체들의 AABB의 합집합
노드 수	공간 크기·해상도에 영향	객체 배치에 따라 동적으로 결정

 

1. 장점

 

 

BVH의 장점

 

1. 객체 밀도에 따라 자동 적응

• 비어 있는 공간을 거의 생성하지 않음
• 객체 밀집 지역만 세분화 → 트리 깊이가 효율적

 

2. Ray Tracing 에 매우 유리

• 각 노드가 AABB이므로 빠른 교차 테스트 가능
• SAH 기반 빌드 시 최적의 레이 트래싱 성능

Ray Tracing(광선 추적) :
빛이 실제로 움직이는 방식을 시뮬레이션해서 현실 같은 이미지(반사, 굴절, 그림자)를 만드는 기법
(카메라에서 광선을 쏴(scene 안으로) 무엇과 맞는지 계산하고, 맞은 표면에서 다시 반사/굴절/산란시켜 최종 색을 구하는 방식.)

 

 

3. 동적 객체 대응 쉬움

• 리프의 AABB 갱신(Refit)만으로 빠른 업데이트
• 심하게 변한 경우 Reinsert / Rotation 으로 국소 수정 가능함

 

4. 대규모 / 불균일 분포에 강함

• 객체가 한쪽에 몰려 있어도 효율적 구조를 생성할 수 있다.

 

Quad/Octree의 장점

 

1. 공간 기반 규칙이 단순

• 구현이 간단하고 예측 가능
• 격자 기반 공간 알고리즘과 잘 맞음

2. 균일 분포 환경에서 효율적

• 일정한 셀 구조가 시뮬레이션에 적합
• 공간 샘플링, 근접 탐색 시 직관적 처리

3. 정적 장면에서 빠름

• 빌드가 단순하고 초기화 비용이 낮음
• 게임 물리/LOD/셀 기반 culling 등에 적합

 

 

2. 단점

 

BVH의 단점

1. 초기 빌드 비용이 높을 수 있음
   • SAH 기반 BVH 빌드는 O(n log n) 혹은 더 무거움
2. 동적 객체가 많으면 구조가 왜곡될 수 있음
   • 빈번한 움직임이 트리를 non-optimal 상태로 만들고 여러 종류의 재정렬(refit/reinsert/rotation)이 필요
3. 공간 표현이 균일하지 않음
   • grid 기반 알고리즘(예: 보이드 감지, 영역 lookup)에 불리

 

Quad/Octree의 단점

1. 빈 공간이 많이 생김
   • 공간 중심 분할이기 때문에 객체가 특정 지역에 몰려 있을 경우 비효율적
2. 동적 객체에 불리
   • 객체가 셀을 넘어가면 재삽입, 재분할이 빈번
   • 빠르게 움직이는 물체가 많으면 업데이트 비용 증가
3. Ray Tracing에 비효율적
   • 고정 셀 기반이라 레이 탐색 경로가 길어짐
   • AABB 연산 기반인 BVH보다 적중률 낮음

 

3. 유리한 상황

 

BVH가 유리한 상황

• Ray Tracing / Path Tracing
• 불균일한 객체 분포
• 대규모 모델(수십~수백만 폴리곤)
• 객체 중심 충돌 알고리즘
• 삼각형 기반 렌더링 파이프라인(게임/엔진)

⇒ Scene의 실제 '객체 배치'에 따라 구조가 최적화되어야 하는 경우

 

 

Quad/Octree가 유리한 상황

• 정적 Scene + 공간 좌표를 기반으로 무언가 찾는 작업 필요
  • (예: visibility grid, 구역 LOD, 타일 기반 월드)
• 빠른 근접 탐색
  • (근접 오브젝트 찾기, 물리 Broad-phase)
• 좌표 기반으로 영역을 구분하는 것이 자연스러운 환경
  • (예: 지형, 월드 분할, voxel-like 게임)

⇒ ‘좌표 공간’ 중심 계산이 많은 경우

 

항목	BVH	Quad/Octree
분할 기준	객체	공간
초기 빌드 비용	높음	낮음
동적 객체 처리	유연하나 관리 복잡	자주 갈라짐, 비효율적
빈 공간 문제	거의 없음	심함
레이 트레이싱	매우 강력	느림
균일 그리드 기반 처리	부적합	적합