BSP 트리

컴퓨터 그래픽스 게임 개발 마지막 수정: 2026-08-30 04:27:51

1. 개요[편집]

정렬을 실시간에 하지 않는다. 정렬을 컴파일 타임에 트리 모양으로 구워 둔다.

BSP 트리(Binary Space Partitioning tree, 이진 공간 분할 트리)는 공간을 초평면 하나로 앞/뒤 두 반공간으로 가르고, 각 반공간에서 같은 조작을 재귀 반복해 만든 이진 트리다. 내부 노드마다 분할 초평면 하나가 붙고, 잎 하나가 더 이상 쪼개지지 않은 볼록 셀 하나에 대응한다. 셀이 볼록하다는 것이 이 자료구조가 주는 거의 모든 성질의 뿌리다.

축에 수직인 면만 쓰도록 제한하면 그게 KD-트리이고, 매 레벨 중점에서 모든 축을 한꺼번에 자르면 쿼드트리·옥트리다. 즉 BSP는 이 계열의 가장 일반적인 형태이고, 나머지는 전부 「분할면을 어떻게 제한했는가」로 얻어지는 특수화다. 분할면을 자유롭게 고를 수 있다는 자유는 대가를 부른다 — 후보 초평면이 무한하니 좋은 것을 고르는 것이 어렵고, 비스듬한 면이 입력 다각형들을 조각내며, 결과 트리가 데이터 크기를 넘어 커진다. 이 문서는 그 자유가 무엇을 사 주고 무엇을 비용으로 받아 갔는지를 본다.

2. 트리 순회가 곧 정렬이다[편집]

슈마커 등이 1969년 비행 시뮬레이터용으로 「분리 평면이 있으면 그리는 순서가 시점과 무관하게 결정된다」를 관찰했고, 푹스·케뎀·네일러가 1980년에 이를 재귀 자료구조로 정리한 것이 BSP 트리다.¹ 핵심 관찰은 한 줄이다.

초평면 $h$ 가 공간을 앞/뒤로 가른다면, 시점이 있는 쪽 반공간의 것은 반대쪽 것을 절대 가릴 수 없다.

그러면 후–전(back-to-front) 순서가 재귀 세 줄로 나온다. 노드의 평면에 시점 $\mathbf{e}$ 를 대입해 부호를 보고,

$h(\mathbf{e}) > 0$ (앞쪽에 서 있다) → 뒤 부분트리 → 노드의 다각형들 → 앞 부분트리 순으로 그린다.
$h(\mathbf{e}) < 0$ → 반대로 앞 부분트리부터.

한 번의 순회가 그 시점에 대한 정확한 깊이 정렬을 준다. 비교 정렬이 아니라 트리 순회이므로 $O(n)$ 이고, 시점이 어디로 움직이든 트리는 다시 짓지 않는다. 이것이 화가 알고리즘을 실용화한 물건인데, 여기서 「정확한」이라는 단어가 중요하다. 순진한 화가 알고리즘은 세 다각형이 서로를 물고 도는 순환 겹침에서 정답이 존재하지 않아 무너지는데, BSP는 그런 다각형을 분할면이 지나가면서 조각내 버려 순환 자체를 소멸시킨다. 정렬 불가능한 입력을 정렬 가능하게 만드는 대가가 조각 증가라고 읽으면 정확하다.

역방향 순회를 하면 전–후(front-to-back) 순서가 나오고, 이쪽이 실무에서 더 자주 쓰인다. 이미 칠한 화면 영역을 기록해 두고 그 뒤에 오는 것을 아예 안 그리면 오버드로가 사라지기 때문이다.

3. 트리 짓기 — 분할면 고르기가 전부[편집]

입력이 다각형 집합이라면 관례적으로 입력 다각형 자신의 평면을 후보로 삼는다(자동 분할, auto-partition). 그러면 후보가 유한해지고, 그 평면 위의 다각형들은 조각나지 않고 노드에 그대로 얹힌다.

문제는 어느 것을 고르느냐다. 평면 하나를 고르면 나머지 다각형들이 세 부류로 갈린다 — 완전히 앞, 완전히 뒤, 그리고 걸쳐서 둘로 잘리는 것. 잘린 조각은 각각 양쪽 자식으로 내려가므로 다각형 총수가 늘어난다. 표준 비용함수는 이 둘의 가중합이다.

C(h) \;=\; \alpha \cdot S(h) \;+\; \beta \cdot \bigl| F(h) - B(h) \bigr|

$S$ 는 그 평면이 만들 분할 수, $F, B$ 는 앞·뒤로 가는 다각형 수다. 후보 전체를 훑어 $C$ 가 최소인 것을 고르는데, 후보가 많으면 매 노드가 $O(n^2)$ 이라 실무 컴파일러는 후보를 무작위로 수십 개만 표집한다. 가중치는 경험적으로 정하며, 90년대 레벨 컴파일러들은 분할 억제 쪽에 훨씬 큰 가중치를 뒀다 — 트리가 좀 기울어도 삼각형이 안 늘어나는 쪽이 이득이었기 때문이다.²

조각 증가가 실제로 얼마나 나쁜지는 이론적으로도 답이 나와 있다. 평면 위 서로 겹치지 않는 선분 $n$ 개에 대해서는 무작위 자동 분할이 기대 $O(n \log n)$ 개의 조각을 내고, 패터슨과 야오는 같은 크기의 결정적 구성을 줬다. 3차원에서는 사정이 나빠져서 서로 겹치지 않는 삼각형 $n$ 개에 대해 $O(n^2)$ 크기의 BSP가 항상 존재하지만, $\Omega(n^2)$ 를 요구하는 배치도 존재한다.³ 즉 삼각형 만 개짜리 장면에서 최악이면 조각이 억 단위로 터진다는 뜻이고, 이것이 BSP가 범용 가속 구조 자리를 내준 첫 번째 이유다. 실제 게임 레벨이 그 정도로 악랄하지는 않아서 보통 1.5~3배 정도에 그치지만, 곡면이 많거나 삼각형이 잘게 쪼개진 지오메트리를 넣으면 컴파일러가 몇 시간을 갈아 넣고도 안 끝난다.

4. 자동 분할이냐, 축 정렬이냐[편집]

분할면을 어디까지 자유롭게 둘 것인가는 사실 이 자료구조의 유일한 설계 자유도다. 갈래는 셋이다.

자동 분할. 입력 다각형의 지지 평면만 후보로 쓴다. 그 평면 위의 다각형이 조각나지 않고, 잎 셀의 경계가 곧 실제 형상의 면이라 「고체/공기」 라벨이 정확하다. 레벨 지오메트리와 CSG가 이쪽을 쓰는 이유.
일반 분할. 아무 초평면이나 쓴다. 이론적으로 더 작은 트리를 만들 수 있지만 후보가 무한하고, 잎 경계가 형상과 무관해져 라벨링이 근사가 된다. 실무에서 거의 안 쓴다.
축 정렬 분할. 후보를 좌표축에 수직인 평면으로 제한한다. 이것이 KD-트리이며, BSP의 특수화로 보는 것이 정확한 계보다.

축 정렬로 제한하면 잃는 것이 있다. 비스듬한 벽 하나를 표현하려면 계단처럼 잘게 쪼갠 셀이 잔뜩 필요하고, 볼록체를 딱 맞게 감싸지도 못한다. 그런데 얻는 것이 훨씬 크다.

분할면 저장이 축 인덱스 2비트 + 실수 하나로 끝난다. 일반 평면이면 법선 셋과 상수 하나, 즉 16바이트다. 노드를 8바이트에 욱여넣을 수 있느냐 없느냐가 캐시 성능을 통째로 가른다.
광선-평면 교차가 나눗셈 한 번이다. 일반 평면이면 내적 두 번. 순회 커널의 안쪽 루프에서 이 차이는 크다.
후보가 유한하고 정렬 가능하다. 덕분에 표면적 휴리스틱 같은 비용 모형으로 전 후보를 스윕해 최적 분할을 고를 수 있다. 자동 분할 BSP는 후보가 다각형 수만큼이라 보통 무작위 표집으로 때운다.

그래서 오늘날 「공간을 자르는」 가속 구조는 사실상 전부 축 정렬이다. 자유로운 분할면이 살아남은 자리는 셀 경계가 곧 형상 경계여야 하는 문제들, 즉 충돌 헐과 불리언 연산뿐이다.

5. Doom과 Quake — 전처리로 밀어 넣은 렌더러[편집]

BSP를 대중화한 것은 학계가 아니라 id 소프트웨어다.

Doom(1993)의 BSP는 사실 2차원이다. 레벨을 위에서 본 선분 집합(linedef)을 수직 평면으로 재귀 분할해 볼록한 방 조각(subsector)들을 만들고, 런타임에는 플레이어 위치에서 전–후 순으로 순회하며 화면 열마다 이미 막힌 구간을 기록해 나간다. 벽이 화면을 다 덮으면 나머지 순회를 통째로 끊는다. 깊이 버퍼를 살 메모리도, 픽셀당 비교를 할 CPU도 없던 시절에 은면 제거를 완전히 전처리와 순회로 대체한 설계다. 층을 여러 겹 못 쌓는 Doom의 유명한 제약도 여기서 온다 — 분할이 2차원이니 같은 평면 좌표 위에 방이 둘일 수 없다.

Quake(1996)에서 이것이 진짜 3차원으로 올라가고, 결정적인 부품이 하나 더 붙는다. 잎 볼록 셀들 사이의 뚫린 면을 포털로 보고, 포털을 통해 서로 보일 가능성이 있는 잎들을 전부 훑어 잎마다 「여기서 보일 수 있는 잎 집합」을 비트벡터로 구워 두는 것 — PVS(Potentially Visible Set)다. 런타임에는 자기 잎의 비트벡터를 읽어 나머지 월드를 통째로 버린다. 절두체 안에 있어도 벽 뒤면 안 그린다는, 프러스텀 컬링이 못 하는 오클루전 컬링을 공짜로 얻는 셈이다. 대가는 컴파일 시간이었다. 90년대 맵 제작자에게 qvis를 밤새 돌려놓고 자는 것은 일상이었고, PVS는 월드가 정적이라는 가정 위에서만 성립하므로 문이 열리고 벽이 무너지는 장면에는 쓸 수 없다.

Quake는 BSP를 렌더링에만 쓰지 않았다. 잎이 「고체/공기」 라벨을 들고 있으므로 선분이 벽을 뚫는지를 트리를 따라 내려가며 구간을 잘라 나가는 것으로 판정할 수 있다. 여기에 플레이어 크기만큼 부풀린 별도의 충돌 헐을 미리 구워 두면, 플레이어를 점 하나로 취급한 채 같은 순회를 돌려 충돌을 처리한다. 오늘날까지 BSP가 남아 있는 자리가 대개 이 정적 레벨 지오메트리의 충돌 질의다.

6. 볼록 셀이 사 주는 것 — CSG와 질의[편집]

렌더링을 빼고 나면 BSP의 본질은 「공간을 볼록 조각으로 완전 분해하고, 각 조각에 라벨을 붙이는」 표현이다. 이 관점에서 강력한 응용이 하나 나온다.

구성적 입체 기하의 불리언 연산. 입체 $A$ 를 BSP로 표현하면 잎이 「안/밖」 라벨을 든다. 두 입체 $A, B$ 의 합집합·교집합·차집합은 한쪽 트리를 다른 쪽 트리에 밀어 넣어 병합하는 것으로 계산된다. $B$ 의 다각형들을 $A$ 의 트리에 통과시키면 각 조각이 $A$ 의 안인지 밖인지가 순회만으로 결정되고, 연산 종류에 따라 조각을 취하거나 버린 뒤 트리를 다시 잇는다. 티보와 네일러가 1987년에 정리했고 지금도 메시 불리언 라이브러리의 표준 구현 중 하나다. 다각형이 어느 쪽에 있는지 판정하는 데 광선을 쏘거나 감김수를 세지 않고 트리 순회만 쓴다는 것이 이 방법의 강점이자, 강건성 문제가 부동소수점 오차 하나로 좁혀지는 이유다.⁴

점 위치 질의도 마찬가지다. 「이 점이 입체 안인가」는 루트에서 잎까지 부호 판정 $O(d)$ 번이면 끝난다. 볼록 셀 분해는 내비게이션 메시의 기반이 되기도 하고, 2D 가시성·그림자 계산에서 광원 기준 BSP를 지어 그림자 볼륨을 잘라내는 데도 쓰인다.

7. 왜 밀려났고, 어디에 남았나[편집]

	BSP 트리	깊이 버퍼 + 경계 볼륨 계층
은면 제거	전처리된 정렬 순회	픽셀 단위 깊이 비교
동적 장면	트리 재컴파일 필요	리핏·재삽입으로 흡수
프리미티브 수	분할로 증가	그대로
전처리 시간	분~시간(PVS 포함)	밀리초~초
가리기 판정	PVS로 전처리	오클루전 질의·계층 Z

승부는 사실상 하드웨어가 냈다. 90년대 후반 GPU에 깊이 버퍼가 기본으로 들어가면서 「정렬해서 그린다」는 문제 설정 자체가 사라졌다 — 순서를 몰라도 픽셀마다 깊이를 비교하면 되니까. 동시에 게임 장면이 정적 실내 복도에서 파괴 가능한 오브젝트와 스키닝 캐릭터로 옮겨가면서, 전처리를 무겁게 하고 런타임을 가볍게 한다는 BSP의 거래 조건이 통째로 불리해졌다. 광선 질의 쪽에서도 조각 증가가 없는 경계 볼륨 계층이 표면적 휴리스틱과 함께 표준이 됐다.

그래도 남은 자리가 있다.

정적 레벨 충돌. 소스 엔진 계열은 지금도 맵을 BSP로 컴파일해 충돌 헐과 포털 컬링에 쓴다. 벽이 안 움직인다면 여전히 이보다 싼 「이 캡슐이 벽을 뚫었나」 판정이 없다.
메시 불리언·CSG. 위에서 본 대로, 볼록 분해 자체가 목적인 문제에서는 대체재가 마땅치 않다.
투명 다각형 정렬. 깊이 버퍼가 못 푸는 유일한 문제가 알파 블렌딩 순서인데, 반투명 조각이 많고 정적이면 지금도 작은 BSP로 정렬한다.
2D 가시성·조명. 평면에서는 조각 증가가 $O(n \log n)$ 으로 얌전해서, 타일 기반이 아닌 2D 게임의 시야·그림자 계산에 여전히 실용적이다.

정리하면 BSP 트리는 은면 제거 알고리즘으로서는 은퇴했지만, 공간의 볼록 분해라는 자료구조로서는 은퇴하지 않았다. 은면 제거의 역사에서 이 트리가 차지하는 자리는 「메모리와 트랜지스터가 없을 때 인간이 얼마나 영리해질 수 있는가」의 기록에 가깝다.

8. 관련 문서[편집]

KD-트리 · 쿼드트리 · 옥트리 · 공간 분할 자료구조 · 경계 볼륨 계층
표면적 휴리스틱 · 레이 트레이싱
깊이 버퍼 · 화가 알고리즘 · 은면 제거 · 프러스텀 컬링 · 포털 컬링
충돌 감지 · 내비게이션 메시 · 실시간 렌더링
구성적 입체 기하 · 볼록 껍질 · 계산기하학

Fuchs, Kedem, Naylor (1980), “On visible surface generation by a priori tree structures”, SIGGRAPH ‘80. 제목의 “a priori”가 이 자료구조의 전부다 — 시점을 알기 전에 정렬 정보를 다 만들어 둔다는 뜻. 40년 뒤 GPU가 픽셀마다 깊이를 비교하는 무식한 방법으로 이 우아함을 이겨 버렸다는 것이, 그래픽스 역사에서 반복되는 패턴이다. ↩
Quake 계열 레벨 컴파일러(qbsp)의 기본값은 사실상 「분할을 만들지 않는 평면이 있으면 무조건 그걸 쓴다」에 가까웠다. 그래서 맵 제작자들 사이에는 큰 벽을 축에 정렬시켜 놓으라는 구전 지식이 있었다. 비스듬한 벽 하나가 컴파일 시간을 두 배로 만드는 경험을 다들 한 번씩 해 봤기 때문. ↩
Paterson & Yao (1990). 평면에서는 $O(n \log n)$ , 공간에서는 $\Theta(n^2)$ . 이 $n^2$ 이 “이론적 최악이니 실무와 무관하다”로 넘어가지지 않는 이유는, 최악에 가까운 배치가 격자로 잘게 쪼갠 벽 여러 장이 서로 비스듬히 만나는 흔한 형상이기 때문이다. 즉 병리적 반례가 아니라 그냥 좀 복잡한 방 하나다. ↩
그리고 그 부동소수점 오차 하나가 CSG 라이브러리들의 무덤이다. 다각형을 평면으로 자를 때 「정확히 평면 위」인 정점을 어느 쪽으로 보낼지가 엡실론 하나로 갈리고, 잘못 갈리면 조각 사이에 폭 0의 틈이 생겨 결과 입체가 닫히지 않는다. 그래서 진지한 구현은 유리수 산술이나 정확 술어(exact predicate)로 도망간다. ↩