개요

BSP 트리(Binary Space Partitioning Tree)는

공간(2D 또는 3D)을 반평면(Half-Space) 으로 재귀적으로 나누는 방식의 트리 구조다.

자식 노드는 그 평면을 기준으로 앞(front), 뒤(back) 공간을 표현한다.

왜 쓸까?

• 3D 렌더링 최적화: 백-페이스 컬링, 페인터 알고리즘 등에서 불필요한 그리기를 피하기 위해
• 충돌 검사 최적화: 쓸데없는 오브젝트들과의 충돌 연산 제거
• 맵 데이터 구조화: 게임 맵이나 환경 데이터를 구조적으로 관리 가능

동작 원리

1. 전체 공간에 대해 하나의 기준 평면(분할 기준) 을 잡는다.
   • 예: 하나의 벽(Polygon)을 기준으로 나눔
2. 그 평면을 기준으로 앞(Front) 과 뒤(Back) 공간을 나눈다.
3. 각 공간에 있는 폴리곤들을 다시 분할 평면으로 사용하여 재귀적으로 분할한다.
4. 리프 노드에는 더 이상 분할되지 않는 작은 공간들이 남는다.

이 트리는 일반적으로 Static Geometry에 대해 미리 생성되어 저장된다.