BSP 트리란 무엇인가?
컴퓨터 과학에서 이진 공간 분할(Binary Space Partitioning, BSP)은 초평면(hyperplane)을 분할 경계로 활용해 하나의 공간을 두 개의 볼록 집합(convex set)으로 재귀적으로 나누는 기법입니다. 이러한 반복적인 분할 과정을 통해 해당 영역 안의 객체들이 트리 형태의 자료구조로 표현되는데, 이것이 바로 BSP 트리입니다.
BSP는 1969년 3D 컴퓨터 그래픽스 분야에서 처음 고안되었습니다. BSP 트리의 구조 덕분에 특정 위치의 관찰자를 기준으로 장면 내 객체들을 앞뒤 순서로 정렬하는 등, 렌더링에 유용한 공간 정보를 빠르게 조회할 수 있습니다. 그 외에도 BSP는 CAD에서의 형상 연산(construction solid geometry, CSG), 3D 게임과 로보틱스에서의 충돌 감지, 레이 트레이싱 등 복잡한 공간 장면을 다루는 다양한 응용 분야에서 폭넓게 활용되고 있습니다.
BSP 트리 개요
이진 공간 분할은 하나의 장면을 요구 조건이 충족될 때까지 두 부분으로 계속 나누어 가는 일반적인 재귀 분할 과정으로 이해할 수 있습니다. BSP 트리는 k-d 트리나 쿼드트리 같은 공간 트리 구조의 일반화된 형태로 볼 수 있으며, 결정적인 차이는 분할에 사용되는 초평면이 k-d 트리나 쿼드트리처럼 좌표축에 정렬될 필요 없이 임의의 방향을 가질 수 있다는 점입니다.
컴퓨터 그래픽스에서 평면 다각형으로 구성된 장면을 렌더링할 때는 분할 평면이 장면 내 다각형들이 정의하는 평면과 일치하도록 선택되는 경우가 많습니다. 분할 평면의 구체적인 선택 기준과 분할 종료 조건은 BSP 트리의 용도에 따라 달라집니다. 예를 들어 그래픽스 렌더링에서는 BSP 트리의 각 노드가 임의의 순서로 렌더링할 수 있는 다각형만 포함할 때까지 장면을 분할합니다. 후면 제거(back-face culling)를 적용하는 경우 각 노드는 볼록한 다각형 집합이 되고, 양면 다각형을 렌더링하는 경우에는 각 노드가 단일 평면 위의 다각형만 포함하게 됩니다. 충돌 감지나 레이 트레이싱에서는 충돌 검사나 광선 교차 판정이 간단히 수행될 수 있는 기본 요소들 단위로 장면을 나눕니다.
BSP 트리 생성
BSP 트리의 대표적인 구현 사례는 페인터 알고리즘(painter's algorithm)을 이용해 다각형(후면 제거 없이 양면 렌더링)을 렌더링하는 것입니다. 각 다각형에는 앞면과 뒷면이 지정되는데, 이는 임의로 선택할 수 있으며 트리의 구조에만 영향을 줄 뿐 최종 결과에는 영향을 미치지 않습니다. 이러한 트리는 장면 내 모든 다각형의 정렬되지 않은 목록으로부터 구축됩니다. 다각형 목록으로부터 BSP 트리를 만드는 재귀 알고리즘은 다음과 같습니다.
- 목록에서 다각형 A를 하나 선택합니다.
- BSP 트리에 노드 N을 생성하고, A를 해당 노드의 다각형 목록에 추가합니다.
- 목록의 나머지 각 다각형에 대해 아래를 검사합니다.
- 그 다각형이 A가 놓인 평면의 완전히 앞쪽에 있다면, A 앞쪽 노드의 다각형 목록으로 옮깁니다.
- 그 다각형이 A가 놓인 평면의 완전히 뒤쪽에 있다면, A 뒤쪽 노드의 다각형 목록으로 옮깁니다.
- 그 다각형이 A가 이루는 평면과 교차한다면, 두 개의 다각형으로 분할한 뒤 각각 앞쪽 목록과 뒤쪽 목록으로 옮깁니다.
- 그 다각형이 A와 같은 평면 위에 있다면, 노드 N의 다각형 목록에 추가합니다.
- A 앞쪽에 위치한 다각형 목록에 대해 이 알고리즘을 재귀적으로 적용합니다.
- A 뒤쪽에 위치한 다각형 목록에 대해 이 알고리즘을 재귀적으로 적용합니다.