컴퓨터 과학에서는 초평면을 파티션으로 구현하여 공간을 두 개의 볼록 세트로 재귀적으로 세분화하기 위해 이진 공간 분할(BSP)로 알려진 방법이 구현됩니다. 이러한 세분화 프로세스는 BSP 트리로 알려진 트리 데이터 구조의 형태로 영역 내의 개체 표현을 제공합니다.
이진 공간 파티셔닝은 1969년 3D 컴퓨터 그래픽의 맥락에서 발명되었습니다. 여기서 BSP 트리의 구조는 렌더링에 유용한 장면의 객체에 대한 공간 정보를 허용합니다. 주어진 위치에 있는 뷰어와 관련하여 빠르게 액세스할 수 있습니다. BSP의 다른 응용 프로그램에는 CAD에서 모양(구조적 입체 기하학)을 사용한 기하학적 작업 수행, 3D 비디오 게임 및 로봇 공학의 충돌 감지, 광선 추적 및 복잡한 공간 장면의 처리와 관련된 기타 응용 프로그램이 포함됩니다.
개요
이진 공간 분할은 분할이 하나 이상의 요구 사항을 충족할 때까지 장면을 두 개로 재귀적으로 분할하는 일반적인 프로세스로 처리됩니다. 공간을 분할하는 초평면이 k-d 트리 또는 쿼드 트리에서와 같이 좌표 축과 정렬되는 대신 임의의 방향을 가질 수 있는 k-d 트리 및 쿼드 트리와 같은 다른 공간 트리 구조의 일반화로 볼 수 있습니다. 평면 다각형으로 구성된 장면을 렌더링하기 위해 컴퓨터 그래픽에서 구현될 때 분할 평면은 장면에서 다각형으로 정의된 평면과 일치하도록 자주 선택됩니다. 파티션 평면의 구체적인 선택과 파티션 프로세스 완료 기준은 BSP 트리의 목적에 따라 다릅니다. 예를 들어, 컴퓨터 그래픽 렌더링에서 장면은 BSP 트리의 각 노드가 임의의 순서로 렌더링할 수 있는 폴리곤으로만 구성될 때까지 분할됩니다. 뒷면 컬링이 구현되면 각 노드는 볼록한 폴리곤 세트로 구성되는 반면 양면 폴리곤을 렌더링할 때 BSP 트리의 각 노드는 단일 평면의 폴리곤으로만 구성됩니다. 충돌 감지 또는 광선 추적에서 장면은 충돌 또는 광선 교차 테스트가 간단한 몇 가지 기본 요소로 나눌 수 있습니다.
세대
BSP 트리의 표준 구현은 페인터 알고리즘의 도움으로 폴리곤(양면, 즉 뒷면 컬링 없음)을 렌더링하는 것입니다. 각 다각형은 임의로 선택할 수 있는 앞면과 뒷면으로 지정되며 필요한 결과가 아닌 트리 구조에만 영향을 줍니다. 이러한 트리는 장면에 있는 모든 다각형의 정렬되지 않은 목록에서 만들어집니다. 해당 폴리곤 목록에서 BSP 트리를 구축하기 위한 재귀 알고리즘은 다음과 같습니다.
- 목록에서 다각형 A를 선택합니다.
- BSP 트리에서 노드 N을 만들고 해당 노드의 폴리곤 목록에 A를 추가합니다.
- 목록의 서로 폴리곤
- 해당 폴리곤이 A를 포함하는 평면 앞에 완전히 위치한 경우 해당 폴리곤을 A 앞의 노드 목록으로 이동합니다.
- 해당 다각형이 A를 포함하는 평면 뒤에 완전히 있는 경우 해당 다각형을 P 뒤의 노드 목록으로 이동합니다.
- 해당 다각형이 A로 구성된 평면과 교차하는 경우 이를 두 개의 다각형으로 분할하고 P의 앞뒤에 있는 각 다각형 목록으로 이동합니다.
- 해당 폴리곤이 A를 포함하는 평면 내에 있는 경우 노드 N의 폴리곤 목록에 추가합니다.
- A 앞에 있는 폴리곤 목록에 이 알고리즘을 적용합니다.
- A 뒤에 위치한 폴리곤 목록에 이 알고리즘을 적용합니다.