이진 공간 분할
이진 공간 분할(Binary Space Partitioning, BSP)은 공간을 볼록 집합(convex set)으로 재귀적으로 분할하는 방법이다. 이 과정은 BSP 트리(BSP tree)라고 불리는 트리 데이터 구조를 생성한다. 본래 3D 컴퓨터 그래픽스 분야에서 렌더링 효율을 높이기 위해 1969년에 고안되었으나, 1990년대 초 이드 소프트웨어의 존 카맥이 둠과 퀘이크 엔진에 채택하면서 널리 알려졌다.
BSP는 복잡한 3D 공간(게임 레벨 등)을 렌더링하기 전에 미리 연산하여, 어떤 시점에서든 올바른 순서로 폴리곤을 렌더링할 수 있게 해주는 강력한 기술이다. 주로 정적인(움직이지 않는) 구조물로 이루어진 공간을 처리하는 데 매우 효과적이다.
개요
이진 공간 분할의 핵심 아이디어는 하나의 평면(3D의 경우)이나 선(2D의 경우)을 기준으로 공간을 '앞(front)'과 '뒤(back)'라는 두 개의 부분 공간으로 나누는 것이다. 그리고 나뉜 각각의 부분 공간에 대해 또 다른 평면을 기준으로 나누는 작업을 재귀적으로 반복한다. 이 분할 과정은 각 부분 공간이 더 이상 나눌 필요가 없는 하나의 볼록한 공간(leaf)이 될 때까지 계속된다.
- 노드(Node): BSP 트리의 각 노드는 공간을 분할하는 데 사용된 평면(폴리곤)을 나타낸다.
- 자식 노드(Children): 각 노드는 '앞' 부분 공간과 '뒤' 부분 공간에 해당하는 두 개의 자식 노드를 가진다.
- 리프 노드(Leaf Node): 트리의 가장 마지막에 위치하며, 비어 있거나(empty) 꽉 찬(solid) 볼록한 공간을 나타낸다.
렌더링에서의 활용
BSP의 가장 대표적인 용도는 Z-버퍼가 없거나 성능이 부족했던 초기 3D 게임에서 렌더링 순서를 결정하는 것이었다. BSP 트리를 사용하면 카메라(시점)의 위치에 관계없이 항상 올바른 순서로 폴리곤을 그릴 수 있다.
이 방식은 화가 알고리즘과 유사하게 작동하며, 다음과 같은 순서로 렌더링을 수행한다.
- BSP 트리의 루트 노드에서 시작한다.
- 현재 노드의 분할 평면을 기준으로 카메라(시점)가 '앞'에 있는지 '뒤'에 있는지 판단한다.
- 카메라가 '앞'에 있다면:
- '뒤' 쪽 자식 노드를 먼저 재귀적으로 렌더링한다.
- 현재 노드의 폴리곤을 렌더링한다.
- '앞' 쪽 자식 노드를 재귀적으로 렌더링한다.
- 카메라가 '뒤'에 있다면, 위 순서를 반대로 수행한다.
이 과정을 통해 카메라에서 먼 폴리곤부터 그리게 되므로, 가까운 폴리곤이 자연스럽게 먼 폴리곤을 덮어쓰게 되어 정확한 장면이 그려진다.
기타 응용 분야
- 충돌 감지(Collision Detection): 캐릭터나 물체가 맵의 벽과 같은 고체 공간 안에 있는지 밖에 있는지를 BSP 트리를 따라 내려가며 효율적으로 판단할 수 있다.
- 가시성 판단(Visibility Culling): 현재 시점에서 보이지 않는 영역의 폴리곤들을 렌더링 과정에서 아예 제외하여 성능을 향상시키는 데에도 사용된다.
- 레이 캐스팅(Ray Casting): 총알이나 광선이 어떤 물체와 가장 먼저 부딪히는지 판정하는 계산을 가속화할 수 있다.
장점과 단점
- 장점:
- 렌더링 속도가 매우 빠르다. 일단 트리가 구축되면, 렌더링 시점에서는 매우 간단한 탐색만으로 올바른 렌더링 순서를 얻을 수 있다.
- Z-버퍼 하드웨어가 필요 없거나 보조적인 역할로만 사용할 수 있어 저사양 시스템에 유리했다.
- 단점:
- BSP 트리 생성 과정이 매우 복잡하고 연산 비용이 높다. 따라서 맵 로딩 시 한 번만 수행해야 한다.
- 맵의 구조가 바뀌지 않는 정적 환경에만 적용할 수 있다. 문이나 승강기처럼 움직이는 요소는 별도의 처리가 필요하다.
- 분할 과정에서 원래의 폴리곤이 여러 개로 쪼개져 전체 폴리곤 수가 늘어날 수 있다.