---
title: "공간이 아니라 물체를 나눈다"
description: "격자도 쿼드트리도 KD 트리도 공간을 잘라 왔습니다. BVH(bounding volume hierarchy)는 물체를 둘로 갈라 각 무리를 상자로 감쌉니다. 크기가 있는 물체가 왜 여기에만 온전히 담기는지, 상자끼리 겹쳐도 괜찮은 이유를 실측으로 봅니다."
author: "유니얼"
pubDate: 2026-09-20
category: "programming/algorithm/spatial"
tags: ["최적화", "자료구조"]
canonical: https://blog.unialgames.com/posts/algo-bvh/
---
지금까지 세 번 같은 자리에서 걸렸습니다.

균일 격자에서는 물체가 칸 경계에 걸치면 양쪽에 다 넣어야 했습니다.
쿼드트리에서는 부모에 남길지, 걸친 자식마다 중복해서 넣을지, 칸을 느슨하게 잡을지를 골라야 했습니다.
KD 트리는 아예 **점만** 담을 수 있어서 크기가 있는 것은 넣지 못했습니다.

공통점이 있습니다. 셋 다 **공간을 먼저 자르고** 물체를 그 칸에 끼워 넣습니다.
자르는 선이 물체를 관통하는 것은 막을 방법이 없습니다. 물체에게 물어보고 자른 게 아니니까요.

## 물체 하나가 몇 칸에 들어가나

얼마나 심각한지부터 재 봤습니다. 1000 × 1000 맵에 크기가 제각각인 물체 1000개를 뿌리고,
격자에 담을 때 물체 하나가 몇 칸에 등록되는지 셌습니다.

| 칸 크기 | 칸 수 | 등록 횟수 | 물체당 | 가장 많이 걸친 물체 |
| --- | --- | --- | --- | --- |
| 10 | 6,100 | 10,163 | 10.16 | 72칸 |
| 25 | 1,358 | 3,356 | 3.36 | 16칸 |
| 50 | 395 | 1,965 | 1.97 | 9칸 |
| 100 | 100 | 1,415 | 1.42 | 4칸 |
| **BVH** | **1,000** | **1,000** | **1.00** | **1칸** |

칸을 잘게 잡을수록 나빠집니다. 칸 10이면 물체 하나가 평균 10칸에 들어가고, 가장 큰 물체는 **72칸**에 등록됩니다.

이건 메모리만의 문제가 아닙니다.

- 그 물체가 한 칸 움직이면 **72개 목록에서 빼고 새 칸들에 다시 넣어야** 합니다
- 질의 한 번에 같은 물체가 여러 번 나오니 **중복 제거**를 해야 합니다
- 칸을 키워서 중복을 줄이면 이번엔 한 칸에 담기는 물체가 늘어납니다

칸 크기를 어디에 맞춰도 한쪽이 나빠집니다. 1편에서 본 것과 같은 모양의 딜레마입니다.

## 물체를 둘로 가른다

발상을 뒤집습니다. **공간을 자르지 말고 물체를 나눕니다.**

물체 전부를 감싸는 상자 하나로 시작합니다. 그 물체들을 두 무리로 가르고,
각 무리를 감싸는 상자를 하나씩 만듭니다. 각 무리 안에서 같은 일을 반복합니다.
무리에 몇 개 안 남으면 거기서 멈춥니다.

이것이 **BVH(bounding volume hierarchy, 경계 볼륨 계층)** 입니다.
감싸는 도형으로는 축에 나란한 상자(AABB)를 가장 많이 쓰고, 구나 기울어진 상자를 쓰기도 합니다.

<x-bvh>
<script type="application/json">
{
  "label": "물체를 둘로 나누기",
  "size": 16,
  "leaf": 2,
  "boxes": [[7.4, 9.9, 2.8, 1.0], [10.4, 4.4, 1.0, 2.2], [11.6, 11.1, 1.0, 2.2], [7.5, 11.3, 2.8, 1.2], [9.9, 6.9, 2.2, 1.0], [13.1, 9.8, 1.4, 1.4], [13.0, 4.4, 1.4, 2.2], [2.2, 3.6, 1.4, 2.2], [0.8, 12.4, 1.2, 1.4], [6.7, 12.9, 2.2, 1.2], [5.3, 4.5, 1.0, 1.2], [4.6, 8.7, 1.0, 2.2]],
  "ray": [0.2, 7.4, 1, 0.18],
  "note": "넓은 축으로 늘어놓고 가운데에서 가르는 가장 단순한 규칙입니다"
}
</script>
</x-bvh>

앞의 셋과 다른 점이 눈에 보입니다.

- 상자가 **물체에 딱 붙어 있습니다.** 빈 공간을 감싸는 칸이 없습니다
- 물체는 **정확히 한 잎에만** 들어갑니다. 쪼개지도, 중복되지도 않습니다
- 대신 **형제 상자끼리 겹칩니다**

## 겹쳐도 되는 이유

공간 분할에서 칸이 겹치면 그건 버그입니다. "이 점이 어느 칸인가" 에 답이 둘이 되어 버리니까요.

BVH는 그 질문을 하지 않습니다. 묻는 것은 **"이 상자를 지나가는가"** 하나뿐입니다.
지나가면 들어가 보고, 안 지나가면 그 아래를 통째로 건너뜁니다. 답이 둘이어도 아무 문제가 없습니다.
양쪽 다 들어가 보면 그만입니다.

그래서 겹침은 **틀린 게 아니라 낭비**입니다. 겹친 만큼 양쪽을 다 들어가 보게 되니 느려질 뿐입니다.
그리고 낭비라서, 줄이려고 애쓸 대상이 됩니다.

## 어떻게 가를까

두 무리로 가르는 방법이 성능을 정합니다. 세 가지를 같은 장면, 같은 레이로 재 봤습니다.

- **가운데 자르기**: 상자의 한가운데를 기준으로 물체 중심이 어느 쪽인지 본다
- **중앙값 자르기**: 물체 중심으로 줄 세워 딱 절반씩 가른다 (KD 트리와 같은 발상)
- **넓이로 고르기**: 자를 자리 후보를 여럿 놓고, 각각에 대해 `양쪽 상자 겉넓이 × 그 안의 물체 수` 를 재서 가장 작은 것을 고른다

| 묶는 규칙 | 내부 노드 | 깊이 | 형제 겹침 | 노드 방문 | 물체 판정 | 합 |
| --- | --- | --- | --- | --- | --- | --- |
| 가운데 자르기 | 343 | 11 | 5.8% | 23,068 | 8,418 | 31,486 |
| 중앙값 자르기 | 255 | 8 | 6.9% | 22,689 | 11,993 | 34,682 |
| 넓이로 고르기 | 340 | 10 | **4.2%** | 22,319 | 7,649 | **30,040** |

중앙값 자르기는 트리가 가장 얕고 예쁘게 균형이 잡히는데 **가장 느립니다.**
KD 트리에서 값어치였던 균형이 여기서는 값어치가 아닙니다.
개수를 반씩 맞추느라 상자가 커지고, 커진 상자에 레이가 더 자주 걸립니다.

**중요한 건 개수가 아니라 넓이입니다.** 레이가 상자를 맞힐 확률이 넓이에 비례하니까요.
세 번째 규칙이 그것을 직접 계산합니다. **표면적 휴리스틱(SAH, surface area heuristic)** 이라고 부릅니다.
이름 그대로 겉넓이를 씁니다. 2차원이면 둘레가 그 자리를 대신합니다.

SAH는 짓는 값이 비쌉니다. 자를 자리 후보마다 양쪽 상자를 다시 계산해야 하니까요.
그래서 보통 축마다 열두 칸쯤으로 나눠 그 경계에서만 재 보는 식으로 후보를 줄입니다. 위 측정도 그렇게 했습니다.

## 레이를 쏜다

BVH가 가장 잘하는 일이 이것입니다.

각 노드에서 하는 일은 **상자와 선이 만나는지** 보는 것뿐입니다.
축에 나란한 상자라면 x 구간과 y 구간을 각각 잘라서 겹치는 구간이 남는지만 보면 됩니다.
나눗셈 몇 번이면 끝나는 **슬랩 판정(slab test)** 입니다.

- 상자를 **안 맞히면** 그 아래 물체는 하나도 안 재봅니다
- 맞히면 **가까운 자식부터** 들어갑니다
- 들어가기 전에 그 상자까지의 거리가 **이미 맞힌 것보다 멀면** 건너뜁니다

마지막 줄이 핵심입니다. 가까운 쪽을 먼저 봐서 답을 일찍 쥐면, 그 뒤로는 거의 다 걷어 낼 수 있습니다.

<x-bvh>
<script type="application/json">
{
  "label": "레이 쏘기",
  "size": 16,
  "leaf": 2,
  "mode": 1,
  "boxes": [[7.4, 9.9, 2.8, 1.0], [10.4, 4.4, 1.0, 2.2], [11.6, 11.1, 1.0, 2.2], [7.5, 11.3, 2.8, 1.2], [9.9, 6.9, 2.2, 1.0], [13.1, 9.8, 1.4, 1.4], [13.0, 4.4, 1.4, 2.2], [2.2, 3.6, 1.4, 2.2], [0.8, 12.4, 1.2, 1.4], [6.7, 12.9, 2.2, 1.2], [5.3, 4.5, 1.0, 1.2], [4.6, 8.7, 1.0, 2.2]],
  "ray": [0.2, 7.4, 1, 0.18],
  "note": "상자를 안 맞히면 그 아래는 열어 보지도 않습니다"
}
</script>
</x-bvh>

12개 중 4개만 실제로 재봅니다. 큰 장면에서는 차이가 훨씬 벌어집니다.
물체 1000개에 레이 2000개를 쏘면 물체 판정이 **7,649번**입니다.
전부 다 재보면 2,000,000번이니 **0.4퍼센트**입니다.

## 잎에 몇 개를 담을까

KD 트리에서는 2에서 4 사이가 가장 좋았습니다. BVH에서 같은 것을 재 봤습니다.

| 잎 크기 | 내부 노드 | 깊이 | 노드 방문 | 물체 판정 | 합 |
| --- | --- | --- | --- | --- | --- |
| 1 | 999 | 13 | 25,675 | 2,016 | **27,691** |
| 2 | 613 | 12 | 24,193 | 3,873 | 28,066 |
| 4 | 340 | 10 | 22,319 | 7,721 | 30,040 |
| 8 | 180 | 9 | 19,926 | 15,413 | 35,339 |
| 16 | 90 | 8 | 17,308 | 29,959 | 47,267 |

여기서는 **잎 1이 가장 낫게 나옵니다.** KD 트리와 다릅니다.
이유는 셈법에 있습니다. 이 표는 상자 판정과 물체 판정을 그냥 한 번씩으로 세었는데,
BVH의 물체는 그 자체가 상자라서 두 판정의 값이 거의 같습니다. 그러면 잎을 키울 이유가 없습니다.

실제 엔진에서는 잎에 든 것이 삼각형이고, **삼각형 판정이 상자 판정보다 몇 배 비쌉니다.**
그러면 곡선이 KD 트리 때처럼 U 자로 돌아오고, 최적점도 2에서 8 사이로 옮겨 갑니다.
표를 그대로 믿지 말고 **자기 잎에 든 것이 얼마나 비싼지**로 다시 재세요.

## 격자와 붙여 보면

같은 레이 2000개를 격자에도 쏴 봤습니다. 격자 쪽은 DDA로 칸을 하나씩 밟아 가면서,
지금까지 맞힌 것보다 다음 칸이 멀면 멈추는 방식입니다.

| 장면 | 격자 (칸 25) | 격자 (칸 50) | 격자 (칸 100) | BVH (잎 2) |
| --- | --- | --- | --- | --- |
| 고르게 흩어진 1000개 | **11,550** | 17,146 | 37,428 | 28,066 |
| 네 덩어리에 뭉친 1000개 | 44,058 | 37,726 | 83,119 | **10,052** |
| 성기게 흩어진 100개 | 29,213 | 19,102 | **17,539** | 20,432 |

또 갈립니다. **고르게 흩어져 있으면 격자가 두 배 넘게 빠르고, 뭉쳐 있으면 BVH가 네 배 가까이 빠릅니다.**
성긴 장면에서는 비슷합니다.

그런데 표에서 더 중요한 것은 굵은 글씨의 **자리**입니다.
격자가 이기는 칸 크기가 장면마다 25, 50, 100으로 옮겨 다닙니다.
장면이 바뀌면 그 값을 다시 찾아야 하고, 틀리면 두 배씩 손해를 봅니다.

**BVH에는 고를 값이 없습니다.** 물체가 어떻게 놓여 있든 자기가 알아서 그 모양을 따라갑니다.
성능의 최고점이 아니라 **최악을 얕게 만드는 쪽**이 BVH의 자리입니다.

## 움직이면 상자만 키울까, 다시 지을까

물체가 움직이면 상자가 안 맞습니다. 두 가지 길이 있습니다.

- **상자만 다시 맞춘다(refit).** 잎부터 뿌리까지 올라오며 상자 크기만 고칩니다. 트리 구조는 그대로입니다. 빠릅니다
- **처음부터 다시 짓는다.** 느리지만 품질이 돌아옵니다

refit만 계속하면 어떻게 되는지 재 봤습니다. 물체 1000개를 전부 조금씩 움직이면서,
20프레임마다 형제 상자 겹침과 레이 비용을 봤습니다.

| 프레임 | 형제 겹침 | 레이 비용 | 처음 대비 |
| --- | --- | --- | --- |
| 0 | 4.5% | 14,087 | 1.00배 |
| 20 | 13.2% | 20,020 | 1.42배 |
| 40 | 21.1% | 32,831 | 2.33배 |
| 60 | 25.5% | 50,663 | 3.60배 |
| 80 | 28.0% | 71,924 | 5.11배 |
| 100 | 29.4% | 97,082 | 6.89배 |
| 120 | 30.3% | 124,638 | **8.85배** |

120프레임 만에 **아홉 배**가 됩니다. 같은 자리에서 처음부터 다시 지으면 겹침 2.3%, 비용 15,380으로 돌아옵니다.

구조가 안 바뀌니까요. 처음에 가까이 있어서 한 무리로 묶인 물체들이 서로 반대 방향으로 흩어져도
계속 같은 상자 안에 있습니다. 상자는 그만큼 커지고, 겹침이 늘고, 레이가 양쪽을 다 들어가게 됩니다.

그래서 실제로는 이렇게 씁니다.

- **매 프레임 refit, 가끔 다시 짓기.** 위 표라면 20~40프레임마다 한 번이 타협점입니다
- **안 움직이는 것과 움직이는 것을 나눠서** 트리를 둘로 둡니다.
  지형은 한 번 짓고 손대지 않고, 움직이는 것만 작은 트리에 담아 매 프레임 다시 짓습니다.
  질의는 두 트리에 각각 던집니다
- 겹침 비율을 **직접 재서** 임계값을 넘으면 그때 다시 짓는 방법도 씁니다. 위 표가 바로 그 계기판입니다

## 어디에 쓰나

BVH가 가장 잘 맞는 자리는 **선이나 원뿔을 쏘는** 일입니다.

- **레이캐스트.** 총알 판정, 바닥 감지, 마우스로 물체 집기, 시야 확인
- **절두체 컬링.** 카메라 절두체가 상자를 안 맞히면 그 아래 전부 안 그립니다. 상자 하나로 수백 개를 걷어 냅니다
- **충돌 브로드페이즈.** "겹칠 가능성이 있는 쌍" 만 추려서 정밀 판정으로 넘깁니다
- **오프라인 렌더링.** 레이 트레이싱에서는 사실상 BVH밖에 안 씁니다. 지금 GPU의 레이 트레이싱 전용 회로도 BVH를 타고 내려가는 일을 합니다

반대로 **"내 주변 반경 5미터 안"** 같은 질의는 BVH가 잘하는 일이 아닙니다.
그건 1편의 격자가 훨씬 낫습니다. 상자 판정이 아무리 싸도 칸 아홉 개 훑는 것보다 쌀 수는 없습니다.

## 정리

BVH는 **공간이 아니라 물체를 나누는** 구조입니다.

- 물체를 두 무리로 갈라 각 무리를 상자로 감쌉니다. **물체는 정확히 한 잎에만** 들어갑니다
- 격자에서는 물체 하나가 평균 열 칸, 최악 일흔두 칸에 등록됐습니다. BVH는 1.00입니다
- **형제 상자가 겹칩니다.** 묻는 것이 "어느 칸인가" 가 아니라 "지나가는가" 라서 틀린 게 아니라 낭비일 뿐입니다
- 가르는 규칙은 개수가 아니라 **넓이**로 골라야 합니다. 개수를 반씩 맞추는 규칙이 가장 느렸습니다
- 레이를 쏘면 물체 판정이 전체의 **0.4퍼센트**까지 줄었습니다
- 고른 분포에서는 격자가 두 배 빠릅니다. **BVH의 자리는 최고점이 아니라 얕은 최악**입니다
- 상자만 고치면 120프레임 만에 **아홉 배** 느려집니다. 주기적으로 다시 짓거나, 정적과 동적을 나눠 담으세요