공간 분할 자료구조

게임 개발 컴퓨터 그래픽스 마지막 수정: 2026-07-11 04:24:44

1. 개요[편집]

공간 분할 자료구조(spatial partitioning data structure)는 3차원(또는 2차원) 공간에 흩어진 객체들을 계층적·격자적으로 조직하여, “이 근처에 뭐가 있나?”라는 질문에 모든 객체를 일일이 훑지 않고 답할 수 있게 해 주는 자료구조의 총칭이다. 충돌 감지, 레이 트레이싱, 최근접 이웃 탐색의 성능을 좌우하는 핵심 도구로, 게임 물리 엔진과 렌더러의 성능은 사실상 이 자료구조를 얼마나 잘 짜느냐에 달려 있다.

근본 동기는 조합 폭발이다. $N$ 개의 객체가 서로 충돌하는지 순진하게 다 확인하면 쌍의 수가 $O(N^2)$ 으로 늘어난다. 객체 1000개면 50만 번, 10000개면 5000만 번. 프레임당 16밀리초 안에 이걸 다 하는 것은 불가능에 가깝다.¹ 공간 분할은 “멀리 떨어진 두 객체는 애초에 충돌 검사조차 하지 않는다”는 상식을 자료구조로 못 박아, 이 비용을 평균 $O(N \log N)$ 혹은 그 이하로 끌어내린다.

2. 균일 격자 — 가장 단순한 처방[편집]

가장 직관적인 방법은 공간을 똑같은 크기의 정육면체 격자 셀로 나누고, 각 객체를 자신이 걸친 셀에 등록하는 것이다. 두 객체는 같은 셀(혹은 인접 셀)을 공유할 때만 충돌 후보가 된다.

장점: 구현이 극단적으로 단순하고, 셀 인덱스가 좌표의 나눗셈 한 번으로 나온다. 객체가 공간에 고르게 퍼져 있으면 사실상 상수 시간 조회.
단점: 객체 크기가 제각각이거나 한 곳에 뭉쳐 있으면(teapot-in-a-stadium 문제) 성능이 무너진다. 셀이 너무 크면 후보가 많고, 너무 작으면 큰 객체가 수많은 셀에 중복 등록된다.

동적 장면에서는 공간 해싱(spatial hashing) 변형이 인기다. 무한한 격자를 해시 테이블로 압축해, 실제로 객체가 있는 셀만 메모리에 둔다. 파티클 시스템이나 SPH 유체처럼 수십만 입자의 이웃을 매 프레임 찾아야 하는 경우 균일 격자/공간 해싱이 여전히 왕이다.

3. 트리 계열 — 적응적 분할[편집]

객체 분포가 불균일하면 계층적 트리가 답이다. 공간이나 객체를 재귀적으로 둘로(혹은 여덟로) 쪼개 내려간다.

3.1. 옥트리와 쿼드트리[편집]

옥트리(octree)는 정육면체를 세 축의 중앙에서 잘라 여덟 개의 자식 큐브로 나누고, 객체가 든 셀만 다시 재귀 분할한다(2차원 버전이 쿼드트리). 빈 공간은 얕게, 붐비는 공간은 깊게 나뉘는 적응성이 매력이다. 지형, 복셀 세계(마칭 큐브로 뽑은 표면 포함), 전역 조명의 조도 캐시 등에 두루 쓰인다.

3.2. KD트리[편집]

KD트리(k-d tree)는 한 번에 한 축씩, 축에 수직인 평면으로 공간을 둘로 가른다. 분할 축을 번갈아 바꾸거나(라운드로빈) 가장 넓게 퍼진 축을 고른다. 분할 위치를 잘 잡으면 매우 균형 잡힌 트리가 되어, 정적 장면의 레이 트레이싱과 최근접 이웃 질의에서 최고의 성능을 낸다. 대신 객체가 움직이면 트리를 다시 지어야 해서 동적 장면에는 부담이 크다.

트리를 훑는 비용은 대략 다음을 따른다.

T_{\text{query}} = O(\log N) \quad (\text{균형 잡힌 경우})

물론 이는 트리가 잘 균형 잡혔을 때 이야기고, 한쪽으로 쏠리면 최악 $O(N)$ 까지 퇴화한다.

4. BVH — 객체를 감싸는 계층[편집]

레이 트레이싱과 현대 게임 물리의 사실상 표준은 경계 볼륨 계층(Bounding Volume Hierarchy, BVH)이다. 공간을 자르는 앞의 방법들과 달리, BVH는 객체들을 묶어 경계 볼륨(주로 축 정렬 경계 상자, AABB)으로 감싸고, 그 상자들을 다시 더 큰 상자로 재귀적으로 묶는다.

레이나 질의 객체가 어떤 노드의 상자와 교차하지 않으면, 그 노드 밑의 모든 객체를 통째로 건너뛴다. BVH가 널리 사랑받는 이유는 이렇다.

동적 장면 친화적: 객체가 움직여도 그 객체를 감싸는 상자만 갱신하거나(refit) 국소적으로 재구성하면 된다. 매 프레임 다시 짓지 않아도 된다.
겹침 허용: 공간 분할이 아니라 객체 분할이라 형제 노드의 볼륨이 겹쳐도 되고, 각 객체가 정확히 한 리프에만 속한다(중복 등록 없음).

BVH의 품질은 표면적 휴리스틱(Surface Area Heuristic, SAH)으로 결정한다. 어떤 분할이 좋은지를 자식 볼륨의 표면적에 비례하는 광선 교차 확률로 추정해, 기대 순회 비용을 최소화하는 지점에서 자른다.

C_{\text{SAH}} = C_t + \frac{A_L}{A} N_L C_i + \frac{A_R}{A} N_R C_i

여기서 $A$ 는 부모의 표면적, $A_L, A_R$ 은 두 자식의 표면적, $N_L, N_R$ 은 각 자식의 객체 수다. 오늘날 NVIDIA RTX의 하드웨어 레이 트레이싱 유닛도 결국 BVH를 순회하는 전용 회로다.²

5. 스위프 앤 프룬과 실전 선택[편집]

충돌 감지 계열에서는 트리 없이도 잘 도는 스위프 앤 프룬(Sweep and Prune, SAP)이라는 고전이 있다. 각 축에 대해 객체들의 AABB 시작·끝 좌표를 정렬해 두고, 한 축에서 겹치지 않는 쌍은 후보에서 즉시 쳐낸다. 프레임 간 객체 이동이 작으면 정렬이 거의 갱신되지 않아(temporal coherence) 매우 빠르다.³

그래서 실전에서는 하나만 쓰지 않고 섞는다.

브로드 페이즈(broad phase): SAP나 BVH, 균일 격자로 충돌 “후보 쌍”을 싸게 추린다.
내로 페이즈(narrow phase): 추려진 쌍에만 정밀한 형상 교차 검사(GJK 알고리즘 등)를 돌린다.

Bullet, PhysX, Havok 같은 상용 물리 엔진은 모두 이 2단계 구조를 쓰며, 브로드 페이즈에 동적 BVH(dbvt)를 얹는 것이 국룰이다. 정답은 장면에 따라 다르다 — 균일하게 퍼진 입자 바다엔 격자, 붐비는 정적 실내엔 KD트리, 움직이는 강체 무리엔 BVH. “일단 격자부터 깔아 보고 느리면 트리로 갈아탄다”가 현장의 정서다.⁴

6. 관련 문서[편집]

60FPS는 프레임당 16.7ms가 예산의 전부다. 이 안에 물리·렌더·오디오·AI를 다 넣어야 하니, $O(N^2)$ 충돌 검사에 예산을 통째로 갖다 바치는 것은 사형선고나 다름없다. ↩
“레이 트레이싱 그래픽카드”의 정체를 한 꺼풀 벗기면 결국 BVH 순회와 삼각형 교차를 초당 수십억 번 하는 전용 실리콘이다. 알고리즘은 90년대 그대로, 실리콘만 무식해진 셈. ↩
SAP는 프레임마다 처음부터 정렬하지 않고 이전 정렬을 조금만 고친다(insertion sort). 물체들이 갑자기 순간이동만 안 하면 이 “거의 정렬된 배열 다시 정렬하기”가 사실상 공짜다. ↩
teapot-in-a-stadium — 거대한 경기장 한복판에 찻주전자 하나가 정밀하게 놓인 장면. 균일 격자가 왜 만능이 아닌지 보여주는 계산기하학의 유명한 반례이자, 적응적 트리의 존재 이유를 한 컷으로 설명하는 밈. ↩