오다기리 박의 알고리즘 노트

BSP 트리란? 이진 공간 분할법(Binary Space Partitioning)은 재귀적으로 3차원 공간을 평면으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다. BSP 트리는 컴퓨터 그래픽스에서 렌더링 효율을 높이기 위해서 도입되었지만, CAD에서의 CSG(Constructive Solid Geometry), 충돌 감지(collision detection)에도 쓰기 좋다. 또한 폴리곤 메쉬의 내/외부를 구분하기에도 좋다. BSP 트리는 쿼드트리, 옥트리, k-d 트리와 비슷하지만 보다 더 일반적인 구조이다. 분할하는 공간이 n차원이면 분할 평면은 (n - 1)차원 초평면이다. 초평면은 평면의 일반화된 개념이라 생각하면 된다. 분할하고자하는 공간이 3차원이면 분할 초평..