BSP (Binary Space Partitioning)

재귀적으로 유클리드 공간을 초평면상의 볼록 집합으로 분할하는 알고리즘

• 하나의 공간을 두 개씩 나누어 가는 과정을 재귀적으로 실행
• 맵 렌더링, 충돌 감지 등에 최적화를 위해 사용

공간 분할 실행 흐름

1. 하나의 분할 평면을 선택
2. 하나의 분할 평면을 두 개의 하위 공간으로 분할
3. 각 하위 공간에 대해 1~2 과정을 재귀적으로 반복
4. 원하는 기준 (최종 목적)에 도달할 때 까지 해당 과정을 수행

   해당 과정을 거쳐 만들어진 트리를 BSP 트리 라고 부르며, 노드는 분할 평면 정보를 리프노드는 최종적으로 분할이 완료된 공간 정보를 담게된다.

재귀 종료 조건

BSP는 다양한 용도로 사용되고, 용도에 따라 언제까지 재귀를 실행할지 결정해야 한다.

1. 렌더링 최적화

용도
시야에 보이는 부분만 효율적으로 렌더링하기 위해 공간 분할하여 가시성을 판단

종료 조건
각 리프 노드가 시야 계산이 필요없는 수준, 렌더링 퀄리티에 영향을 미치지 않는 수준이 된다면, 더 이상 분할할 필요가 없음

2. 충돌 검출

용도
물리 엔진에서 객체 충돌을 빠르게 판단하기 위해 공간 분할

종료 조건
분할된 리프 공간 내부에 포함된 오브젝트 수가 일정 수준 이하가 되면 더 이상 분할하지 않음

3. 레이 트레이싱

용도
광선을 쏠 때 충돌 가능성이 있는 폴리곤 오브젝트간 빠르게 찾기 위해 BSP 트리를 사용

종료 조건
광선 검출에 필요한 정확도를 만족할 만큼의 분할이 이루어지면 어 이상 분할하지 않음