CS/자료구조, 알고리즘

[알고리즘] 쿼드트리(QuadTree)와 BVH(BoundingVolumeHierarchy)

양양줘 2025. 12. 17. 12:49

쿼드트리(QuadTree)

 

쿼드트리(QuedTree)는 공간을 4 역으로 미리 분할한 뒤, 각 오브젝트를 자신의 위치와 크기에 가장 적합한 노드에 삽입하여 관리하는 구조이다. 이 구조에서 부모 노드의 AABB와 오브젝트의 AABB를 교차 검사하여 해당 오브젝트가 포함될 수 있는 자식 노드로 점진적으로 내려가며 삽입하게 된다.

 

쿼드트리 구조
struct Object { AABB bound;  }

struct QuadNode
{
    AABB bounds;                 	  // 노드가 담당하는 영역
    std::vector<Object*> objects; 	// 여기에 포함된 오브젝트들
    QuadNode* children[4]; 	        // 4개의 자식 (NW, NE, SW, SE)
};

 

1. 트리 구축 단계 (Build)

노드의 AABB와 오브젝트의 AABB를 비교하여 오브젝트가 완전히 속하는 최하위의 노드를 찾아 삽입한다.

  • 노드의 범위 안에 오브젝트가 들어왔을 경우, 자식 노드의 AABB와 비교해서 오브젝트가 완전히 들어가는 자식 노드가 있으면 그쪽으로 내려간다.
  • 자식 노드에 완전히 들어가지 않으면 부모 노드에 삽입한다.

 

2. 조회 단계 (Query/ Collision search)

노드의 AABB와 검사 대상 오브젝트의 AABB를 비교하여 오브젝트가 겹쳐있는 노드들의 오브젝트들과 충돌 검사를 진행한다. 탐색 대상은 가치치기 방식으로 거른다.

  • 노드의 AABB와 오브젝트의 AABB가 겹치지 않으면 그 노드의 서브트리를 배제한다. = 가지치기(pruning)
  • 노드의 AABB와 오브젝트의 AABB가 겹치면, 해당 노드에 속한 오브젝트가 없더라도 서브트리(자식노드들)에는 오브젝트가 있을 수 있으므로 해당 서브트리 전체를 탐색해야한다.
void CullNode(QuadNode* n, const Frustum& F)
{
    if (!n) return;

    // 0) 서브트리에 오브젝트가 하나도 없으면 바로 리턴
    if (n->subtreeCount == 0) return;

    // 1) 부모 노드 AABB vs 프러스텀: 교차 안 하면 서브트리 통째로 스킵
    if (!Intersects(F, n->bounds)) return;

    // 2) 이 노드에 직속된 오브젝트 검사
    for (auto* obj : n->objects)
        if (Intersects(F, obj->aabb)) visible.push_back(obj);

    // 3) 자식 재귀
    for (auto* child : n->children)
        CullNode(child, F);
}

 

 

쿼드트리를 활용하면 근접한 공간에 속한 오브젝트들끼리만 충돌 검사를 수행하므로, 전체 충돌 계산 비용을 O(n log n) 수준까지 줄일 수 있다. 하지만 오브젝트가 좁은 영역에 몰려있을 경우, 트리가 특정 방향으로 깊게 자라고 비어있는 노드가 많아져 메모리 사용량이 증가하고 탐색 비교 횟수도 늘어나는 비효율이 발생한다. 그러므로 쿼드트리는 ‘넓은 공간에 오브젝트가 균일하게 분포된 경우’에 가장 큰 효과를 발휘한다.

 

 

 

 

 

BVH (Bounidng Volume Hierarchy)

 

 BVH(Bounding Volume Hierarchy)는 공간 자체를 균등하게 나누는 쿼드트리와 달리, 오브젝트(또는 프리미티브)를 기준으로 트리를 구성하여 관리하는 구조이다. BVH 트리의 내부 노드들은 자식 노드들의 AABB를 모두 감싸는 최소 경계의 AABB를 가지며, 실제 오브젝트들은 리프노드들에 저장된다.

BVH 요소내용
내부 노드 자식 노드들의 AABB를 모두 감싸는 Bounding Volume (오브젝트 소유 x)
리프 노드 실제 오브젝트들이 저장되는 노드 (1개 이상의 오브젝트 소유)

 

 

BVH 구조

 

 BVH는 개념적으로 다진 트리(N-ary Tree)이지만 실제 구현은 대부분 이진 트리인 BVH2로 구현된다. 

struct AABB {
    Vector3 min;  // (x,y,z)
    Vector3 max;  // (x,y,z)
};

struct BVHNode {
    AABB  bounds;       // 이 노드의 AABB
    int   left;         // 왼쪽 자식 노드 인덱스 (리프면 firstObject)
    int   right;        // 오른쪽 자식 노드 인덱스 (리프면 objectCount와 혼용 가능)
    int   firstObject;  // 리프일 경우 오브젝트 배열 시작 인덱스
    int   objectCount;  // 리프일 경우 오브젝트 개수
    
    // 내부노드면 objectCount==0, left/right는 유효한 노드 인덱스
    // 리프노드면 left/right는 사용하지 않음
};

std::vector<BVHNode>    gNodes;      // 연속 배열로 저장되는 트리
int                     gRoot = 0;   // 루트 노드 인덱스
std::vector<int>        gObjectIdx;  // 리프가 가리키는 오브젝트 인덱스들(연속 저장)
std::vector<AABB>       gObjectAABB; // 원본 오브젝트 AABB

 

 

BVH 배열 트리를 위한 공간

 

 AABB가 N개, Leaf의 소유 최대L(2)개인 BVH2 트리 구성을 위한 배열 공간은?

// N : AABB 개수 
// L : 한 리프노드가 가질 수 있는 최대 오브젝트 수 (L = 2)
// K : 리프노드 개수  (K = N/L)

// 내부노드 수 = 리프노드 수 - 1 (이진트리 속성)
// 전체 노드 수 = 내부노드 + 리프노드
//              = (N/L-1)  + N/L
//              = 2(N/L) - 1

𝑁_total = 𝑁_internal + 𝑁_leaf
        = ([N/L]-1) + [N/L]
        = 2⌈𝑁/𝐿⌉ − 1

 

 BVH 트리 빌드시 최악의 경우 리프 노드에 담는 오브젝트(AABB)가 한개로만 구성될 수 있다. 리프 수의 최악은 오브젝트와 1:1로 대응하는 것으로즉, Kmax = N이 된다. 따라서 분할 알고리즘이 무엇이든 𝑁_max = 2𝑁−1 은 항상 논리적으로 보장된 안전한 상한치가 된다.

 

 

BVH의 트리 품질(Tree Quality)

 

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

  • Surface Area 최소화 :  부모 AABB의 표면적이 작을수록 교차할 확률이 작아져 전체 방문 수가 감소
  • AABB Overlap 최소화 : 형제 노드 AABB가 서로 겹치는 부피(Volume) 가 작을수록 좋음. 작은 부분에서 겹칠 수는 있으나 많으면 비슷한 영역이므로 다른 자식도 방문해야 하는 경우가 많아져 효율이 급감.(가지치기 실패)
  • 균형 잡힌 깊이 (Balanced Depth) : 트리의 좌우 서브 트리 깊이 차이가 너무 크면 노드 방문(교차테스트)증가 한다.
  • 리프당 오브젝트 수 최적화 : 리프에 포함된 오브젝트가 너무 많으면 내부 검사 과다, 너무 적으면 노드 수 폭증하여 교차 테스트 증가


1. 트리 구축 단계 (Build)

 BVH는 공간을 기준으로 쪼개는 것이 아니라, 오브젝트들을 분류하여 트리를 구성한다. 트리 구축 방식은 상향식, 하향식, 추가식 총 3가지가 있다.

[트리 구축 방식]

1. 상향식 (Bottom-Up, Static) : 리프 노드를 만들고, 리프들을 병합하여 부모를 만들어 올라가는 방식
2. 하향식 (Top-Down, Static) : 긴 축을 정렬하면서 분할점에 따라 자식 노드를 추가하는 방식
    - 오브젝트 수 1/2 분할점
    - 중간거리 분할점
    - SAH(Surface Area Huristic) 기반 최적 분할
3. 추가식 (Incremental, Dynamic) : 오브젝트를 하나씩 삽입하며 트리를 점진적으로 구성하는 방식

 

 

하향식 트리 빌딩의 기본적인 아이디어는 다음과 같다.

1. 현재 노드에 들어갈 오브젝트(AABB)집합 S를 받는다.
2. S를 감싸는 AABB를 만들고 노드에 저장한다.
3. S를 둘로 분할한다. -> '분할 방식' : 하향식 빌드 방식의 구분점
4. 분할한 각 부분집합에 대해 재귀적으로 1~3을 반복한다.
5. 종료 조건에 도달하면 리프 노드 만들고 분할된 부분집합들을 담는다.

 

하향식 -  1)  오브젝트 수 분할점 결정 방식

  • 분할방식
    • 오브젝트의 중심점을 기준으로 x, y, z중 가장 긴 축을 기준으로 정렬하여 절반씩(median) 분할한다.
    • 분할된 부분 집합에 오브젝트가 2개 이하라면 리프노드 확정
  • 특징
    • 구현이 매우 쉽고 안정적(트리 깊이 밸런스)이며, 절반씩 분할하기 때문에 한쪽이 비는 경우가 비교적 적다.
    • 하지만, AABB Overlap이 커질 수 있어 트래버셜/ 교차테스트 비용이 증가할 수 있다.
    • 대충 괜찮은 BVH를 빨리 만들어야 할 때 사용한다.

 

하향식 - 2) 중간거리 분할점 결정 방식

  • 분할 방식
    • 오브젝트의 중심점을 기준으로 x, y, z중 가장 긴 축을 기준으로 축의 중간값(mid point)을 기준으로 분할한다.
      splitPos = (minCentroid + maxCentroid) / 2

centroid < splitPos → Left
centroid ≥ splitPos → Right
    • 분할된 부분 집합에 오브젝트가 2개 이하라면 리프노드 확정
  • 특징
    • 정렬이 없어도 구현이 가능하여 빠르고, 축의 중간값을 사용하여 공간을 직관적으로 분할하기 때문에 AABB Overlap을 줄일 수 있다.
    • 하지만, 오브젝트가 씬의 한쪽에 몰려있는 경우 트리가 한쪽으로 몰리게 되기 때문에 fallback(대체 분할)이 필수적이다. → MidPoint로 나눴는데 한쪽이 비면 Median split으로 대체
    • 오브젝트의 분포가 비교적 균일하고 빠른 BVH 구축이 필요할 때 사용한다.

 

하향식 - 3)  SAH (Survace Area Huristic)
  • 분할 방식
    • 오브젝트의 중심점을 기준으로 x, y, z중 더 가장 축을 기준으로 정렬하고 모든 기준점 경우의 수에 대해 SAH 비용을 계산하여 가장 최적의 기준점을 사용하여 분할한다.
    • 분할된 부분 집합에 오브젝트가 2개 이하라면 리프노드 확정
    • SAH 비용 함수
      기호 의미
      Csplit 현재 분할의 예상 탐색 비용
      Sp, Sl, Sr 부모/왼쪽/오른쪽 AABB의 표면적
      Nl, Nr 왼쪽/오른쪽 그룹에 속한 오브젝트 개수
      Ctrav 트리 탐색 비용= 노드 AABB 교차 검사1회 비용
      Cintersect 오브젝트(AABB or other) 교차 테스트 비
  • 특징
    • 가장 좋은 레이 트레이싱 성능을 보여주며, AABB Overap이나 빈공간을 잘 줄여준다.
    • 빌드 비용이 크다. (특히 동적 씬에서는 매우 부담)

 

 

2. 조회 단계 (Query/ Collision search)

 BVH는 쿼드트리와 동일하게 AABB를 사용한 상위→하위 방향의 가지치기 트리 탐색으로 동작한다.

  • 부모 노드 AABB와 쿼리 AABB가 교차하지 않으면
    → 이 부모를 포함한 서브트리 무시 = 가지치기(pruning)
  • 부모 노드 AABB와 쿼리 AABB가 교차하면
    → 서브트리까지 탐색을 진행해야한다
    • 현재 노드가 내부 노드(Internal Node)라면 자식 노드들에 대해 교차 여부를 재귀적으로 검사한다.
    • 현재 노드가 리프 노드(Leaf Node)라면 리프에 저장된 모든 오브젝트들과 실제 교차 테스트를 수행한다.

 

 

충돌 검사나 레이 쿼리 시에는 공간 분할 방식과 동일하게 부모 노드의 AABB부터 교차 여부를 판단하여, 교차하지 않는 서브트리를 통째로 제거하는 가지치기(Pruning)를 수행함으로써 연산량을 크게 줄인다. BVH는 불균일한 오브젝트 분포에서도 안정적인 성능을 제공하며, 레이 트레이싱 및 충돌 감지 시스템에서 가장 널리 사용되는 공간 가속 구조 중 하나이다.

구분 BVH (Bounding Volume Hierarchy) 쿼드트리 (Quadtree)
분할 기준 오브젝트/프리미티브 기반 공간 기반
노드 구성 방식 부모 AABB = 자식 AABB들의 Union 자식도느는 부모노드를 4분할한다
리프 노드 반드시 오브젝트 하나 이상 포함 오브젝트가 속하지 않을 수 있음
장점 (가장 큰 강점) 불균일 분포에서도 성능 좋음 균일한 공간 분포일 때 단순하고 매우 효과적
단점 빌드/업데이트 비용이 큼 오브젝트가 몰리면 깊게 자라고 비효율 발생

 

'CS > 자료구조, 알고리즘' 카테고리의 다른 글

[알고리즘] 정렬 알고리즘 1. 버블정렬, 선택정렬, 삽입정렬  (1) 2025.10.31
[알고리즘] A* 최단 경로 알고리즘  (0) 2025.10.31
[알고리즘] 위상 정렬 알고리즘(Topological Sort Algorithm) - 멀티 스레드를 활용한 Task 스케줄링 병렬 처리  (0) 2025.10.31
[알고리즘] 다익스트라(Dijkstra) 최단 경로 알고리즘  (0) 2025.10.20
[자료구조] 그래프(Graph)  (0) 2025.10.15

'CS/자료구조, 알고리즘'의 다른글

  • 현재글[알고리즘] 쿼드트리(QuadTree)와 BVH(BoundingVolumeHierarchy)

관련글

티스토리툴바