[알고리즘] BVH : 정적/동적 트리 갱신

 

이전에 BVH (Bounding Volume Hierarchy) 에 대해서 간단하게 정리 해봤었는데,

이번에는 BVH를 구현할 때, 오브젝트가 움직였을 때 트리를 어떻게 다시 맞춰서 업데이트할 것인지에 대한 방법에 대해서 알아보고자 한다.

 

 

0. BVH의 트리 품질 (Tree Quality)

BVH는 오브젝트들의 AABB를 이용해 트리(계층적 경계 볼륨)를 만드는 구조이다.
문제는 오브젝트가 움직이면, 트리의 품질이 떨어지기 때문에 ‘트리를 어떻게 갱신할 것인가’ 가 중요해진다.

 

여기서 갱신 방식이 정적(Static) 과 동적(Dynamic) 으로 나뉜다.

 

 

0-1. “오브젝트가 움직이면 트리의 품질이 떨어진다”는 말은

BVH가 더 이상 ‘빠르게 충돌 검사/레이 테스트를 해 줄 수 없는 구조가 되어간다는 뜻.
즉, BVH가 점점 비효율적인 구조로 변한다 → 더 많은 노드를 검사해야 한다 → 성능이 떨어진다 라는 의미.

 

 

이전에 BVH에서 설명할 때, 언급했던 적 있었던 좋은 BVH트리의 조건이 안좋아진다는 것.. 

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

 

 

 

1. 정적 BVH(Static BVH)

정적 BVH는 오브젝트가 움직이지 않을 것을 전제로 한 트리이다.

 

그런데 오브젝트가 가끔씩 움직이면 다음과 같은 문제가 생긴다.

 

문제 1) 부모 AABB가 커짐 

• 리프가 이동하면
  → 부모도 그걸 감싸려고 커짐
  → 부모가 커지면 형제와 겹칠 확률 증가 → 쿼리 비용 증가

 

문제 2) 형제 노드 AABB 간 Overlap 증가

• 겹치면 Pruning(가지치기) 실패가 증가 → 탐색 비용 증가

 

문제 3) 처음 트리를 나눴던 기준이 무의미해짐

• 원래 왼쪽에 있던 물체가 오른쪽으로 넘어갈 수 있음
• 그런데 트리는 여전히 “왼쪽 / 오른쪽” 기준으로 고정되어 있음→ 트리 품질이 점점 떨어짐

 

1-1. 정적 트리가 오브젝트 움직임에 대응하는 3가지 방식

 

방법 0: Full Rebuild (전체 재빌드)

• 그냥 처음부터 다시 다 만든다
• 품질 최고, 비용 최악

 

방법 1: Refit - 트리 구조 그대로 두고 AABB만 다시 계산

• 리프에서 부모까지 AABB만 업데이트  (부모 = 자식 둘의 union)

장점

• 빠르다 O(N)
• 트리 구조는 유지 → 구현 쉬움, 메모리 재배치 필요없음 

단점

• 트리 구조는 그대로 라서 → 품질 급 하락
  1. Surface Area 증가 : 오브젝트가 움직이면 부모는 그 둘을 감싸려고 AABB를 키워야 해서 부모 AABB 영역이 점점 커짐
  2. 형제 오브젝트 간 Overlap 증가 : 가지치기(pruning) 효율 떨어짐 

Refit은 사실 정적 BVH에서 “임시 처방” 정도로만 사용된다.

 

 

방법 2: Subtree Rebuild (부분 재생성)

아예 전체를 재생성하지 않고, “문제가 생긴 서브 트리만 골라서 다시 맞게 만든다.”

 

과정 요약:

1. 리프가 이동 → 리프부터 부모로 올라가며 검사
2. split rule(트리 품질 규칙)이 깨진 부모를 발견
3. 그 부모의 subtree를 트리에서 분리(detach)
4. 해당 subtree가 가진 오브젝트 목록 수집
5. 이 subtree만 다시 static BVH 방식으로 rebuild
6. 기존 위치에 다시 붙임(reattach)

→ 전체 빌드의 비용 없이, 트리 품질을 일정 수준으로 유지 가능

 

 

 

 

 

2. 동적 BVH(Dynamic BVH)

동적 BVH는 오브젝트가 계속 움직이는 것을 전제로 한 트리이다.

게임 엔진, 물리 엔진 등에서 사용하는 방식

 

 

2-1. 동적 BVH(Dynamic BVH) 의 트리 갱신 과정

오브젝트는 매 프레임 위치가 바뀔 수 있으므로, BVH도 매 프레임 트리 품질 유지하기 위한 갱신 작업이 필요하다.

 

동적 BVH는 다음 4가지 단계로 트리를 갱신한다.

Refit → Insert/Remove → Rotation → Partial Rebuild 

 

각 단계는 아래 조건 (Split Rule)을 검사해서 

Split Rule이 유지되면 갱신 종료,

Split Rule이 깨지면 다음 단계로 넘어간다. 

 

 

Split Rule : 트리 품질이 나빠졌는지 확인하는 기준

Refit 이후 아래 조건 중 하나라도 위반되면 트리 품질이 저하되었다고 판단한다.

• 부모 노드 AABB가 불필요하게 커졌는가?
• 형제 노드 간 overlap이 과도하게 증가했는가?
• 원래 분할 시 사용했던 longest axis 기준이 더 이상 적합하지 않은가?
• 초기 분할 기준(균등 분할, median, SAH 등)을 여전히 만족하는가?

Split Rule 유지 → 갱신 종료
Split Rule 위반 → 다음 단계 진행

 

 

1. Refit (leaf→root)

가장 기본이자 가장 빠른 갱신 방식.
오브젝트가 이동하면 트리 구조는 건드리지 않고, 리프에서 루트까지 AABB만 갱신한다.

 

• 트리 구조는 그대로 유지
• 리프의 AABB가 변하면 부모 노드 AABB = union(child) 로 재계산
• 매우 빠름 (O(log N))

 

 

해결하지 못하는 문제 

• 오브젝트가 크게 이동한 경우
  • 기존에 묶여 있던 그룹이 더 이상 적절하지 않은데도 그대로 유지됨
  • AABB가 비정상적으로 커짐 → 충돌 후보 증가 → 성능 저하
• 즉, 노드 재배치(rearrangement)를 전혀 해결하지 못함

Split Rule 위반 시 → Insert/Remove 단계로 이동

 

 

2. Insert/Remove (Reinsert Leaf)

오브젝트가 원래 있던 그룹에서 멀리 이동해 Refit만으로는 정상적인 구조를 유지할 수 없을 때 사용한다.

 

 

Remove : 문제가 되는 리프 노드를 트리에서 제거

Insert : BVH 전체에서 가장 적절한 위치를 찾아 재삽입

 

 

• 리프가 “자리를 옮기는 문제(placement)”를 해결
• 대규모 이동에 효과적
• 트리 전체를 다시 빌드하지 않고도 어느 정도 품질 회복 가능

 

 

해결하지 못하는 문제 

Remove & Insert는 “자리 배치(placement)”만 해결한다.

 

다음은 해결하지 못한다:

• 해당 리프가 들어간 그 subtree 내부 구조가 이미 비효율적인 경우
• 형제 노드 AABB가 크게 어긋나 있는 문제
• 조상 구조 전체가 휘어 있는 문제

즉, local rearrangement 문제는 해결하지 못함

 

Split Rule 위반 시 → Rotation 단계로 이동

 

 

3. Rotation (local optimize)

Insert/Remove로 해결되지 않은 경우,
부모–자식 노드 간의 구조를 부분적으로 교환(rotate) 하여 서브트리의 AABB 배치를 더 효율적으로 만든다.

 

• Full rebuild 없이 local 최적화
• AABB overlap을 크게 줄일 수 있음
• cost 개선이 빠르게 이루어짐

 

해결하지 못하는 문제 

 

• 국지적(local) 조정만 가능
• 서브트리 전체가 크게 왜곡되어 있는 경우 해결 불가
• 오브젝트가 너무 많이 섞여 있는데 구조를 미세 조정하는 것만으로는 부족함

Split Rule 위반 시 → Partial Rebuild 단계로 이동

 

 

4. Partial Rebuild (subtree 재생성)

Rotation으로도 해결되지 않을 정도로 서브트리가 엉망이거나 SAH 비용이 너무 악화된 경우,
해당 서브트리만 부분적으로 통째로 다시 빌드

• 문제된 부모 노드를 루트로 하는 서브트리 분리
• 모든 리프 수집 → 새 BVH 빌드
• 구조적인 붕괴 및 AABB 왜곡 해결

즉, Partial Rebuild 까지 왔다는 것은 "이 서브트리는 완전히 다시 만들어야 한다"는 의미 

 

 

동적 BVH 갱신 전체 흐름 요약

(1) Refit  (Leaf → Root)
    └ AABB 갱신만 수행
    └ Split Rule 유지 → 종료
    └ 깨짐 → Insert/Remove

(2) Insert / Remove (Reinsert Leaf)
    └ 리프를 트리에서 제거 후 재삽입
    └ Split Rule 유지 → 종료
    └ 깨짐 → Rotation

(3) Rotation (Local Optimization)
    └ 부모–자식 구조를 부분적으로 교환
    └ Split Rule 유지 → 종료
    └ 깨짐 → Partial Rebuild

(4) Partial Rebuild (Subtree Rebuild)
    └ 문제된 서브트리를 통째로 재생성
    └ Split Rule 유지 → 종료

 

 

 

2-2. 동적 BVH 갱신 최종 요약

동적 BVH는 오브젝트가 매 프레임 움직이는 상황에서
트리 품질을 유지하기 위해 단계적으로 트리를 갱신한다.

• Refit
  빠름, AABB만 갱신 → 큰 이동은 해결 못함
• Insert/Remove
  리프의 위치 재배치 → 서브트리 내부 구조는 해결 못함
• Rotation
  국지적 최적화 → 큰 구조적인 왜곡은 해결 못함
• Partial Rebuild
  서브트리 전체 재생성 → 가장 비용이 크지만 완전한 해결

이 네 단계를 순서대로 적용하면
오브젝트가 자유롭게 움직이는 환경에서도 BVH 품질을 높은 수준으로 유지할 수 있다.