이진 공간 분할법
2단 공간 분할법 (영어: Binary Space Partitioning, BSP) 은 재귀적으로 유클리드 공간을 초평면 상의 볼록 집합으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 자료구조가 생성된다.
원래 이러한 기법은 3D 컴퓨터 그래픽 분야에서 렌더링 효율을 높이기 위해서 도입되었지만, CAD에서의 조립식 입체 기하학 (CSG), 로봇 공학에서의 충돌 감지, 3D 컴퓨터 게임에서 복잡한 공간을 렌더링하는 등 여러 분야에서 사용되고 있다.
개요
컴퓨터 그래픽 분야에서는 공간을 빠르고 정확하게 그리는 것이 중요하다. 공간을 정확하게 그리는 방법으로는 뒤에서부터 앞에 있는 공간까지 전부 그리는 페인트공의 알고리즘이 있지만, 덮어씌워질 불필요한 부분까지 그리므로 비효율적일뿐더러 모든 물체가 바르게 그려지지도 않는다.
Z축 버퍼링 기법으로 물체를 정확하게 그릴 수 있지만, 이는 추가적인 메모리 사용을 요구한다. 반면에, BSP 트리 알고리즘으로는 Z축 버퍼링이나 물체를 정렬하는 과정 없이 간단히 트리를 바른 순서로 순회하는 것만으로 공간을 정확하게 그릴 수 있게 된다. BSP는 시야에 들어오는 물체만 그릴 수 있게 해 주는 가시 목록과 같은 알고리즘의 기반 역할도 한다.
BSP의 단점은 미리 공간을 구성하기 위한 전처리 시간을 요구한다는 점이다. 미리 공간을 정의해 놓기 때문에 BSP 트리 내에서 물체를 직접 움직이기가 힘들다. 하지만 이 단점은 BSP와 Z축 버퍼링 기법을 혼용하면 극복 가능하다. BSP 공간을 배경으로 두고, 움직일수 있는 물체는 Z 버퍼를 이용하여 그리면 된다.
BSP 기법은 특히 일인칭 슈팅 게임과 같은 3D 컴퓨터 게임에서 널리 사용되는 기법이다. BSP 자료 구조를 가장 처음 도입한 게임은 둠이었다. 그 외에 광선 추적이나 충돌 감지 등의 기법에서도 쓰인다.
생성 과정
2단 공간 분할법은 하나의 공간을 특정한 최종 목적을 만족할 때까지 공간을 재귀적으로 2개씩 분할하는 과정이다. 예를 들면, 충돌 감지을 목적으로 하는 경우에는 원래 물체가 충분히 충돌 검사를 간단하게 할 수 있도록 공간이 분할되며 렌더링을 목적으로 하는 경우에는 페인트공 알고리즘을 가장 효율적으로 사용할 수 있도록 볼록한 도형으로 공간이 분할된다.
분할선이 가로지르는 평면은 반드시 2개로 나누어져야 하므로 최종 물체의 개수는 필연적으로 증가될 수 밖에 없다. BSP 트리는 균형이 잘 잡혀 있어야 하기 때문에 올바르고 효율적인 BSP 트리를 생성하는 부분은 구현 과정에서 가장 어려운 부분이라고 할 수 있다. 3D 공간에서 평면은 물체의 면을 분할하는데 쓰인다.
아래의 그림은 불규칙한 다각형을 볼록한 다각형 여러개로 분할하는 과정을 묘사한 것이다. 처음부터 G와 F까지 각각의 단계마다 분할된 다각형의 모서리 수가 적어지며, 마지막 단계에는 완전히 볼록한 다각형이 되는 점에 주목하기 바란다. 어떤 경우에는 분할선이 공간상의 정점과 교차되지 않은 선분 사이를 걸치기도 한다. 만약 분할선이 선분 또는 평면과 교차할 경우에는 교차된 선분 또는 평면은 완전히 독립적인 개체가 되도록 2개로 나누어진다.
2. A는 B와 C로 나누어진다.
3. B는 D와 E로 나누어진다.
4. D는 볼록한 다각형 F와 G로 나누어지며, 여기서부터 트리의 말단이 된다.
효율적인 BSP 구조는 전적으로 좋은 알고리즘에 의해서 만들어진다. 대부분의 BSP 알고리즘은 분할 과정에서 최적의 트리를 얻기 위하여 여러 가지 경우를 시험한다. 그러므로 보통 하나의 트리를 생성해 내는 과정은 오랜 계산 과정을 수반한다.
바깥 고리
