이진 공간 분할법
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
이진 공간 분할법(BSP)은 3차원 컴퓨터 그래픽에서 효율적인 렌더링을 위해 공간을 재귀적으로 분할하는 기술이다. 1969년 가상 환경에서 다각형 정렬을 가속화하는 방법으로 처음 제안되었으며, 1980년 헨리 푹스 등에 의해 3D 객체 표현을 위해 확장되었다. BSP 트리는 3D 공간을 다각형과 일치하는 평면으로 분할하여 계층적 다각형 데이터 구조를 자동 생성하며, 실시간 가시 표면 결정, CSG 연산, 충돌 감지 등에 활용된다. 특히 1인칭 슈팅 게임과 같은 3D 컴퓨터 게임에서 널리 사용되며, 둠, 퀘이크 엔진 등에서 정적 지오메트리를 표현하는 데 사용되었다. BSP 트리는 화가 알고리즘의 성능을 개선하고, Z-버퍼링과 함께 움직이는 객체를 배경 장면에 통합하는 데 기여한다. 유사한 공간 분할 구조로 사분 트리, 옥트리, kd 트리가 있다.
더 읽어볼만한 페이지
- 기하 자료 구조 - K-d 트리
K-d 트리는 k차원 점을 노드로 가지는 이진 트리로, 공간을 분할하는 초평면을 생성하며, 구축, 탐색 등 다양한 연산을 지원하지만, 고차원 공간에서는 성능이 저하될 수 있다. - 이진 트리 - 스플레이 트리
스플레이 트리는 스플레이 연산을 통해 자가 균형을 유지하며 최근 접근 노드의 빠른 접근을 가능하게 하는 이진 탐색 트리로, 분할 상환 분석 시 평균적으로 O(log n)의 시간 복잡도를 가진다. - 이진 트리 - 스레드 이진 트리
스레드 이진 트리는 이진 트리의 NULL 포인터를 활용해 중위 순회 순서상 이전 또는 다음 노드를 가리키도록 하여 효율적인 순회를 가능하게 하고, 스레드 방식에 따라 단일 스레드와 이중 스레드로 나뉜다. - 3차원 컴퓨터 그래픽스 - 픽셀 셰이더
픽셀 셰이더는 렌더링 과정에서 픽셀의 색상을 계산하여 최종 모습을 결정하며, 텍스처, 빛, 그림자 등의 시각 효과를 구현하고, 다양한 언어로 프로그래밍되며, 그래픽 카드 및 칩셋은 지원하는 버전을 가진다. - 3차원 컴퓨터 그래픽스 - 모션 캡처
모션 캡처는 물체의 움직임을 디지털 데이터로 변환하는 기술로서, CG 영상 제작에 활용되며, 센서 부착 방식에서 마커리스 방식으로 발전하여 다양한 분야에 응용된다.
| 이진 공간 분할법 | |
|---|---|
| 개요 | |
| 종류 | 공간 분할 |
| 분야 | 컴퓨터 과학 그래픽스 |
| 특징 | |
| 방법 | 공간을 재귀적으로 이분할 |
| 사용 | 가시성 결정 레이 트레이싱 충돌 감지 |
| 장점 | 공간 검색 효율성 향상 |
| 단점 | 트리의 균형에 따라 성능 저하 가능 |
| 응용 | |
| 분야 | 컴퓨터 그래픽스 게임 개발 로봇 공학 |
| 목적 | 3D 모델링 게임 엔진 경로 탐색 최적화 |
| 관련 개념 | |
| 관련 개념 | KD 트리 쿼드 트리 옥트리 |
2. 역사
이진 공간 분할법(Binary Space Partitioning, BSP)은 컴퓨터 그래픽스 분야에서 3차원 장면을 효율적으로 렌더링하기 위한 필요성에서 출발했다. 초기 아이디어는 1969년 Schumacker 등이 제안한 것으로, 특정 평면을 이용해 다각형의 정렬 순서를 빠르게 결정하는 방식이었다.[1] 이는 당시 비행 시뮬레이터 등에서 활용되었으나, 데이터 구성은 수작업으로 이루어졌다.
본격적인 BSP 트리 개념은 1980년 푹스 등에 의해 정립되었다.[4] 이들은 다각형 평면을 기준으로 공간을 재귀적으로 분할하여 3차원 객체를 표현하는 계층적 데이터 구조를 제안했으며, 이를 통해 BSP 트리를 자동으로 생성하는 알고리즘을 개발했다. BSP 트리는 화가의 알고리즘이 가진 정렬 시간 문제와 겹치는 다각형 오류 문제를 해결하는 효과적인 방법을 제공했다.[4] 다만, 트리를 생성하는 데 시간이 소요되므로 주로 정적인 장면에 대해 미리 계산해두는 방식으로 사용된다.
이후 여러 연구자들에 의해 BSP 기술은 꾸준히 발전하여, 가시성 판별, 구성적 솔리드 지오메트리(CSG)를 이용한 모델링[2], 효율적인 충돌 감지 등 다양한 문제 해결에 기여했으며, 특히 둠[4]이나 퀘이크와 같은 초기 3D 게임의 실시간 렌더링 성능 향상에 중요한 역할을 했다. 나아가 이미지 처리 분야 등 다른 영역으로도 응용 범위가 확장되었다.
2. 1. 초기 연구 및 발전
- 1969년: Schumacker 등[1]은 가상 환경에서 특정 평면을 신중하게 배치하여 다각형 정렬 속도를 높이는 방법을 설명하는 보고서를 발표했다. 이 기술은 평면의 반대편에 있는 다각형이 앞쪽 다각형을 가릴 수 없다는 '깊이 일관성' 원리를 활용했다. 이 기술은 GE와 에반스 앤 서덜랜드(eng)에서 제작한 비행 시뮬레이터에 사용되었으나, 다각형 데이터 구성은 장면 디자이너가 수동으로 수행해야 했다.
- 1980년: 푹스 등[4]은 Schumacker의 아이디어를 확장하여, 다각형과 일치하는 평면을 사용하여 3차원 공간을 재귀적으로 분할함으로써 가상 환경에서 3차원 객체를 표현하는 방식을 제안했다. 이를 통해 '이진 공간 분할 트리'(BSP 트리)라고 하는 계층적 다각형 데이터 구조를 완전히 자동화되고 알고리즘적으로 생성할 수 있게 되었다. 이 과정은 환경이나 객체당 한 번 수행되는 오프라인 사전 처리 단계로 진행되었으며, 실제 화면을 그릴 때(런타임)에는 보는 시점에 따라 트리를 순회하여 가시성 정렬을 생성했다.
- 1981년: Naylor는 박사 학위 논문에서 BSP 트리와 함께, 미리 가시성을 계산하기 위해 강하게 연결된 구성 요소(strongly connected components)를 사용하는 그래프 이론적 접근 방식을 개발하고 두 방법 간의 연관성을 밝혔다. BSP 트리는 가시 표면 결정을 위한 응용 프로그램과 함께 차원에 독립적인 공간 검색 구조로 강조되었다. 이 논문에는 또한 우주왕복선 모델을 사용하여 트리의 크기와 새로 생성되는 다각형 수가 합리적임을 보여주는 최초의 실증적 데이터가 포함되었다.
- 1983년: 푹스 등은 Ikonas 프레임버퍼 시스템에서 BSP 트리 알고리즘의 마이크로 코드 구현을 설명했다. 이것은 BSP 트리를 사용하여 실시간으로 가시 표면을 결정하는 기술을 시연한 최초의 사례였다.
2. 2. 게임 산업에서의 활용
BSP 트리 기법은 컴퓨터 그래픽스 분야에서 공간을 효율적으로 렌더링하기 위해 사용되며, 특히 1인칭 슈팅 게임과 같은 3D 컴퓨터 게임에서 실내 환경 등을 표현하는 데 널리 활용된다. BSP 데이터 구조를 게임에 처음으로 도입한 사례는 '''둠'''이다. BSP 트리는 단순히 물체를 그리는 것 외에도 광선 추적이나 충돌 감지 같은 게임 내 다른 계산 처리에도 응용된다.BSP 트리는 화가 알고리즘과 달리 렌더링 순서를 미리 정렬할 필요 없이 트리를 순회하는 것만으로 깊이 순서에 따라 물체를 정확하게 그릴 수 있다는 장점이 있다. 이는 Z 버퍼 없이도 가려진 부분을 올바르게 처리할 수 있게 해주며, Z 버퍼를 사용하는 경우에도 렌더링 효율을 높이는 데 기여한다. 그러나 BSP 트리는 초기에 맵 구조를 분석하고 트리를 생성하는 전처리 과정이 필요하며, 한번 생성된 정적인 구조 내에서 캐릭터나 움직이는 문과 같은 동적인 물체를 처리하기 어렵다는 단점이 있다. 이러한 단점을 보완하기 위해 많은 게임 엔진에서는 BSP 트리를 주로 정적인 배경 구조에 사용하고, 움직이는 물체는 Z축 버퍼링 기법을 함께 사용하여 처리한다.
게임 개발에서의 BSP 트리 활용은 여러 연구를 통해 발전해왔다.
- 1987년, Thibault와 Naylor는 BSP 트리를 사용하여 임의의 다면체를 표현하는 방법을 제시했다.[2] 이는 단순히 표면 정보만 갖는 것이 아니라 부피를 가진 입체(solid)를 표현하는 방식으로, 구성적 솔리드 지오메트리(CSG) 연산을 가능하게 했다. 이 개념은 이후 퀘이크의 레벨 에디터나 언리얼 에디터 등에서 사용된 "브러시"를 이용한 레벨 디자인 방식의 기초가 되었다. 개발자가 기본적인 입체 도형(브러시)들을 조합하고 빼는 방식으로 복잡한 맵 구조를 만드는 데 BSP 연산이 활용된 것이다.
- 1991년, Gordon과 Chen은 BSP 트리에서 기존의 후면-전면 방식 대신 전면-후면 방식으로 효율적인 렌더링을 수행하는 방법을 발표했다.[CHEN91] 이들은 화면의 어떤 부분이 이미 그려졌는지를 효율적으로 관리하는 데이터 구조를 활용했다. 이 알고리즘은 존 카맥이 둠을 개발할 때 직접 참고하여 게임 엔진에 적용한 것으로 유명하다.
- 1992년, 세스 J. 텔러는 박사 학위 논문을 통해 임의의 3D 다각형 환경에서 실시간 가시성 판별을 가속화하는 방법을 제시했다. 이는 '잠재적 가시 집합(Potentially Visible Set, PVS)'이라는 개념을 활용한 것으로, 특정 위치에서 보일 가능성이 있는 영역을 미리 계산해두어 렌더링 시 불필요한 계산을 줄이는 방식이다. 이 기술은 이후 퀘이크 엔진에 적용되어 게임의 성능을 크게 향상시키는 데 기여했다.
2. 3. 추가 발전
1990년 Naylor, Amanatides, Thibault는 두 개의 BSP 트리를 병합하여 새로운 BSP 트리를 형성하는 알고리즘을 제시했다.[2] 이 알고리즘은 BSP 트리로 표현된 움직이는 객체를 정적 환경(역시 BSP 트리로 표현됨)과 결합하거나, 다면체에 대한 매우 효율적인 구성적 솔리드 지오메트리(CSG) 연산을 수행하고, O(log n * log n) 시간 복잡도로 정확한 충돌 감지를 수행하며, 서로 관통하는 두 객체에 포함된 투명 표면을 올바르게 정렬하는 등 다양한 이점을 제공했다. 이는 X선 시각 효과 등에 활용될 수 있다. 같은 해, 텔러와 Séquin은 직교 2D 환경에서 가시 표면 결정을 가속화하기 위해 잠재적으로 가시적인 집합(PVS, Potentially Visible Set)을 미리 계산하여 오프라인으로 생성하는 방법을 제안했다.1991년에는 Gordon과 Chen이 BSP 트리에서 전통적인 후면에서 전면으로의 렌더링 방식 대신, 전면에서 후면으로 렌더링하는 효율적인 방법을 설명했다.[CHEN91] 이들은 화면에서 이미 그려진 부분과 아직 렌더링되지 않은 부분을 효율적으로 기록하기 위해 특별한 데이터 구조를 사용했다. 이 알고리즘은 당시 표준 컴퓨터 그래픽스 교과서(''컴퓨터 그래픽스: 원리와 실제'')에 실린 BSP 트리에 대한 설명과 함께 존 D. 카맥이 ''둠'' 비디오 게임 제작에 활용한 것으로 알려져 있다.
1992년, 텔러는 박사 학위 논문을 통해 임의의 3D 다각형 환경에서 실시간 가시 표면 결정을 가속화하기 위한 사전 처리 단계로서 PVS를 효율적으로 생성하는 방법을 상세히 설명했다. 이 기술은 이후 ''Quake'' 게임에 적용되어 해당 게임의 성능 향상에 크게 기여했다.
1993년에는 Naylor가 좋은 BSP 트리의 특징이 무엇인지에 대한 질문에 답하는 연구를 발표했다. 그는 최악의 경우 분석 대신 기대 사례(expected-case) 모델을 사용하여 트리를 검색하는 데 드는 예상 비용을 수학적으로 측정하고, 이 측정값을 바탕으로 좋은 BSP 트리를 생성하는 방법을 제시했다. 그는 BSP 트리가 객체를 다해상도 방식으로 표현하며(더 정확하게는 근사 트리(approximate tree) 방식), 이는 허프만 코드나 확률적 이진 검색 트리와 유사점이 있다고 설명했다. 같은 해, Hayder Radha는 박사 학위 논문에서 BSP 트리를 사용하여 자연 이미지를 표현하는 방법을 설명했다. 그는 임의의 입력 이미지에 대해 최적의 BSP 트리를 구성하는 프레임워크를 개발했는데, 이는 최소 제곱 오차(LSE) 분할선 변환이라는 새로운 이미지 변환 기법에 기반한다. Radha의 연구는 또한 BSP 트리를 활용하여 최적의 속도-왜곡(rate-distortion) 성능을 가지는 이미지 압축 프레임워크와 이미지 조작 기법을 개발하는 내용도 포함했다.
3. 생성 과정
이진 공간 분할(BSP)은 주어진 공간을 특정 조건을 만족할 때까지 재귀적으로 두 개의 하위 공간으로 나누는 과정이다.[4] 이는 K-d 트리나 사분 트리와 같은 다른 공간 분할 트리 구조의 일반화로 볼 수 있으며, 분할 기준이 되는 초평면이 반드시 좌표축에 정렬될 필요 없이 임의의 방향을 가질 수 있다는 특징이 있다.
BSP 트리를 만드는 목적에 따라 공간을 나누는 기준과 분할을 멈추는 조건이 달라진다. 예를 들어, 컴퓨터 그래픽스에서 렌더링을 목적으로 할 경우, 각 노드에 포함된 다각형들이 화가 알고리즘 등을 이용해 쉽게 렌더링될 수 있도록 공간을 볼록한 형태로 분할한다. 후면 컬링을 사용하면 각 노드는 볼록 다각형 집합을 포함하게 되고, 양면 다각형을 렌더링할 때는 각 노드가 단일 평면 위의 다각형만 포함하도록 분할할 수 있다. 반면, 충돌 감지나 광선 추적에서는 충돌이나 교차 검사가 간단한 기하 기본 도형으로 공간이 나누어질 때까지 분할을 계속한다.
분할 과정에서 분할 평면(3D)이나 분할선(2D)이 기존의 다각형 면이나 선분과 교차하면, 해당 면이나 선분은 두 개로 나뉘어 독립적인 객체가 된다. 이 때문에 최종적으로 생성되는 객체의 수는 원래보다 늘어날 수 있다.[4] 효율적인 BSP 트리 생성을 위해서는 트리의 균형을 고려한 좋은 알고리즘이 중요하며, 이는 구현상의 주요 과제이다. 최적의 트리를 찾는 과정은 계산 비용이 높아, 보통 정적 장면에 대해 미리 계산하는 방식으로 사용된다.
이진 공간 분할은 3차원 장면을 빠르게 렌더링해야 하는 컴퓨터 그래픽스 분야에서 처음 중요하게 활용되었다. 특히 화가 알고리즘의 단점인 렌더링 순서 정렬 시간과 겹치는 다각형 처리 오류 문제를 해결하는 데 효과적이었다.[4] BSP 트리는 시점에 따른 다각형 정렬을 빠르게 하고, 겹치는 다각형을 미리 분할하여 렌더링 오류를 방지한다. 하지만 생성에 시간이 오래 걸려 동적 객체를 직접 다루기는 어렵다는 단점이 있다.
3. 1. 생성 알고리즘 (예시)
2. A는 B와 C로 나뉜다.3. B는 D와 E로 나뉜다.
4. D는 볼록한 다각형 F와 G로 나뉘며, 이들은 트리의 잎(leaf) 노드가 된다.]]
효율적인 BSP 구조는 좋은 알고리즘을 통해 만들어진다. 대부분의 BSP 알고리즘은 분할 과정에서 최적의 트리를 얻기 위해 여러 가지 경우를 시험하며, 때로는 백트래킹을 사용하여 분할을 다시 하기도 한다. 따라서 하나의 트리를 생성하는 과정은 상당한 계산 시간을 필요로 할 수 있다.
BSP 트리의 대표적인 용도 중 하나는 화가 알고리즘을 사용하여 다각형을 렌더링하는 것이다(이때 후면 제거는 고려하지 않는다). 각 다각형에는 앞면과 뒷면이 임의로 지정되며, 이는 트리의 구조에만 영향을 미치고 최종 결과에는 영향을 주지 않는다.[4] 이러한 트리는 정렬되지 않은 다각형 목록으로부터 다음과 같은 재귀 알고리즘을 통해 구성된다.[4]
# 목록에서 다각형 P를 선택한다.
# BSP 트리에 노드 N을 만들고 해당 노드에 P를 추가한다.
# 목록의 다른 각 다각형에 대해 다음을 수행한다:
## 해당 다각형이 P를 포함하는 평면의 앞에 완전히 있으면, 해당 다각형을 P의 앞쪽 자식 노드로 이어질 목록으로 이동시킨다.
## 해당 다각형이 P를 포함하는 평면의 뒤에 완전히 있으면, 해당 다각형을 P의 뒤쪽 자식 노드로 이어질 목록으로 이동시킨다.
## 해당 다각형이 P를 포함하는 평면에 의해 교차되면, 두 개의 다각형으로 분할하여 각각 P의 앞쪽과 뒤쪽 목록으로 이동시킨다.
## 해당 다각형이 P를 포함하는 평면 위에 있으면, 노드 N의 다각형 목록에 추가한다.
# 이 알고리즘을 P의 앞쪽 다각형 목록에 대해 재귀적으로 적용한다.
# 이 알고리즘을 P의 뒤쪽 다각형 목록에 대해 재귀적으로 적용한다.
다음 다이어그램은 위 알고리즘을 사용하여 선 목록을 BSP 트리로 변환하는 과정을 보여준다. 각 단계(i~viii)마다 알고리즘이 적용되어 트리에 새로운 노드가 추가된다.
 | 장면을 구성하는 선(또는 3D에서는 다각형) 목록으로 시작한다. 트리 다이어그램에서 목록은 둥근 사각형으로, BSP 트리의 노드는 원으로 표시된다. 선의 공간 다이어그램에서 선의 앞면으로 선택된 방향은 화살표로 표시된다. |
 | i. 위 알고리즘의 단계를 따른다. |
 | ii. 이제 알고리즘을 A 앞에 있는 선 목록(B2, C2, D2)에 적용한다. 선 B2를 선택하고 노드에 추가한 다음, 나머지 목록을 B2 앞에 있는 선(D2)과 뒤에 있는 선(C2, D3)으로 분할한다. |
 | iii. B2와 A 앞에 있는 선 목록에서 선 D2를 선택한다. 이 목록에 유일한 선이므로 노드에 추가한 후 더 이상 처리할 것이 없다. |
 | iv. B2 앞에 있는 선들을 모두 처리했으므로, B2 뒤에 있는 선(C2, D3)을 고려한다. 이 중 C2를 선택하고 노드에 추가한 다음, 다른 선 D3을 C2 앞에 있는 선 목록에 넣는다. |
 | v. 이제 C2 앞에 있는 선 목록을 본다. 선이 하나(D3)뿐이므로 이를 노드에 추가하고 계속 진행한다. |
 | vi. A 앞에 있는 모든 선을 BSP 트리에 추가했으므로, 이제 A 뒤에 있는 선 목록을 시작한다. 이 목록에서 선 B1을 선택하여 노드에 추가하고, 나머지 목록을 B1 앞에 있는 선(D1)과 뒤에 있는 선(C1)으로 분할한다. |
 | vii. 먼저 B1 앞에 있는 선 목록을 처리한다. D1이 이 목록의 유일한 선이므로 이를 노드에 추가하고 계속 진행한다. |
 | viii. 다음으로 B1 뒤에 있는 선 목록을 본다. 이 목록의 유일한 선은 C1이므로 이를 노드에 추가하면 BSP 트리가 완성된다. |
최종적으로 트리에 포함된 다각형 또는 선의 수는 원래 목록보다 더 많아지는 경우가 많다. 이는 분할 평면을 교차하는 선이나 다각형이 두 개로 분할되기 때문이다.[4] 이러한 객체 수 증가를 최소화하는 것이 바람직하지만, 동시에 생성된 트리의 균형을 적절하게 유지하는 것도 중요하다. 따라서 알고리즘의 첫 단계에서 분할 평면으로 사용할 다각형이나 선을 신중하게 선택하는 것이 효율적인 BSP 트리를 만드는 데 매우 중요하다.
4. 순회(Traversal)
컴퓨터 그래픽스에서 3차원 공간을 화면에 올바르게 표시하기 위해서는 물체를 그리는 순서가 중요하다. 화가 알고리즘은 멀리 있는 물체부터 가까이 있는 물체 순서로 겹쳐 그리는 방식이지만, 모든 경우에 정확한 결과를 보장하지는 못하며 불필요한 렌더링을 수행하기도 한다. Z축 버퍼링은 픽셀별 깊이 정보를 저장하여 정확한 렌더링을 가능하게 하지만, 추가적인 메모리가 필요하다.
BSP 트리는 이러한 문제들을 해결하는 데 도움을 줄 수 있다. BSP 트리를 특정 규칙에 따라 트리 순회하면, 시점을 기준으로 물체(주로 폴리곤)들을 뒤에서부터 앞 순서로, 혹은 앞에서부터 뒤 순서로 정렬할 수 있다. 이 순회 과정은 트리의 구조 덕분에 선형 시간 내에 효율적으로 수행될 수 있다.[4]
특히 화가 알고리즘과 같이 뒤에서부터 앞으로 물체를 그려야 할 때, BSP 트리를 시점을 기준으로 순회하면 Z축 버퍼링이나 별도의 정렬 과정 없이도 올바른 렌더링 순서를 얻을 수 있다. 순회는 현재 노드를 기준으로 시점이 분할 평면의 앞에 있는지 뒤에 있는지 판단하여, 더 먼 쪽의 자식 노드부터 재귀적으로 방문하는 방식으로 이루어진다. 이를 통해 복잡한 장면이라도 각 폴리곤을 올바른 순서로 렌더링하여 정확한 이미지를 생성할 수 있다.
4. 1. 순회 알고리즘 (예시)
BSP 트리는 트리의 특정 함수에 의해 결정된 순서로 선형 시간에 트리 순회된다. 예를 들어 페인터 알고리즘을 사용하여 양면 폴리곤을 렌더링할 때, 특정 폴리곤 ''P''를 올바르게 그리려면 먼저 ''P'' 뒤의 모든 폴리곤을 그리고, 그 다음 ''P''를 그린 후, 마지막으로 ''P'' 앞의 폴리곤을 그려야 한다. 이러한 그리기 순서가 모든 폴리곤에 대해 만족되면 전체 장면이 올바른 순서로 렌더링된다. 이 과정은 다음 알고리즘을 사용하여 BSP 트리를 재귀적으로 순회하여 구현할 수 있다.[4] 주어진 시점 ''V''에서 BSP 트리를 렌더링하는 과정은 다음과 같다.# 현재 노드가 리프 노드(자식 노드가 없는 노드)라면, 해당 노드의 폴리곤을 렌더링한다.
# 리프 노드가 아니고, 시점 ''V''가 현재 노드의 앞에 있다면:
## 현재 노드 뒤에 있는 폴리곤들을 포함하는 자식 BSP 트리를 먼저 렌더링한다.
## 현재 노드의 폴리곤을 렌더링한다.
## 현재 노드 앞에 있는 폴리곤들을 포함하는 자식 BSP 트리를 렌더링한다.
# 리프 노드가 아니고, 시점 ''V''가 현재 노드의 뒤에 있다면:
## 현재 노드 앞에 있는 폴리곤들을 포함하는 자식 BSP 트리를 먼저 렌더링한다.
## 현재 노드의 폴리곤을 렌더링한다.
## 현재 노드 뒤에 있는 폴리곤들을 포함하는 자식 BSP 트리를 렌더링한다.
# 위의 경우에 해당하지 않으면, 시점 ''V''는 현재 노드와 관련된 평면 위에 정확히 위치한다. 이때는:
## 현재 노드 앞에 있는 폴리곤들을 포함하는 자식 BSP 트리를 렌더링한다.
## 현재 노드 뒤에 있는 폴리곤들을 포함하는 자식 BSP 트리를 렌더링한다. (현재 노드의 폴리곤은 시점과 동일 평면에 있으므로 렌더링되지 않거나 다른 방식으로 처리될 수 있다.)
위 그림의 BSP 트리에 이 알고리즘을 재귀적으로 적용하면 다음과 같은 단계로 렌더링이 진행된다. (시점 ''V''는 그림에 표시된 위치에 있다고 가정한다.)
- 알고리즘은 루트 노드 ''A''에서 시작한다. ''V''는 ''A'' 앞에 있으므로, ''A'' 뒤의 자식 트리(루트 ''B1'')를 먼저 처리한다.
- ''B1'' 노드 처리: ''V''는 ''B1'' 뒤에 있으므로, ''B1'' 앞의 자식 트리(리프 ''D1'')를 먼저 처리한다.
- ''D1'' 노드 처리: 리프 노드이므로 폴리곤 ''D1''을 렌더링한다.
- ''B1''의 앞쪽 자식 처리가 끝났으므로, 폴리곤 ''B1''을 렌더링한다.
- 다음으로 ''B1'' 뒤의 자식 트리(리프 ''C1'')를 처리한다.
- ''C1'' 노드 처리: 리프 노드이므로 폴리곤 ''C1''을 렌더링한다.
- ''A''의 뒤쪽 자식 트리 처리가 모두 끝났으므로, 폴리곤 ''A''를 렌더링한다.
- 다음으로 ''A'' 앞의 자식 트리(루트 ''B2'')를 처리한다.
- ''B2'' 노드 처리: ''V''는 ''B2'' 뒤에 있으므로, ''B2'' 앞의 자식 트리(리프 ''D2'')를 먼저 처리한다.
- ''D2'' 노드 처리: 리프 노드이므로 폴리곤 ''D2''를 렌더링한다.
- ''B2''의 앞쪽 자식 처리가 끝났으므로, 폴리곤 ''B2''를 렌더링한다.
- 다음으로 ''B2'' 뒤의 자식 트리(루트 ''C2'')를 처리한다.
- ''C2'' 노드 처리: ''V''는 ''C2'' 앞에 있으므로, ''C2'' 뒤의 자식 트리부터 처리한다. 뒤쪽 자식 트리는 없으므로 다음 단계로 넘어간다.
- 폴리곤 ''C2''를 렌더링한다.
- 다음으로 ''C2'' 앞의 자식 트리(리프 ''D3'')를 처리한다.
- ''D3'' 노드 처리: 리프 노드이므로 폴리곤 ''D3''을 렌더링한다.
이 순회 과정을 통해 트리는 선형 시간 내에 탐색되며, 결과적으로 폴리곤은 페인터 알고리즘에 적합한 원거리에서 근거리 순서(''D1'', ''B1'', ''C1'', ''A'', ''D2'', ''B2'', ''C2'', ''D3'')로 렌더링된다.
다음은 Ada 언어로 작성된, 배경(먼 곳)에서 전경(가까운 곳) 순서로 트리를 순회하며 폴리곤을 그리는 코드 예시이다.[6] 이 코드는 재귀적으로 트리의 가장 깊은 곳(시점에서 가장 먼 폴리곤)까지 탐색한 후, 재귀 호출에서 돌아오면서 폴리곤을 그린다. 이를 통해 시점에 더 가까운 폴리곤이 이전에 그려진 먼 폴리곤 위에 겹쳐 그려지게 된다.
procedure Tree_traverse (tree:bsp_tree, eye:point) is
begin
if not Tree_isEmpty (tree) then
- - 현재 노드를 기준으로 시점(eye)의 상대적 위치를 결정한다.
constant location : integer = Tree_getLocation (tree, eye) ;
- - 시점(eye)이 현재 노드(분할 평면)의 앞에 있는 경우
if 0 < location then
- - 1. 뒤쪽 자식 트리를 먼저 순회한다 (더 먼 폴리곤).
Tree_traverse (tree.back, eye) ;
- - 2. 현재 노드의 폴리곤을 그린다.
display (tree.polygon_list) ;
- - 3. 앞쪽 자식 트리를 순회한다 (더 가까운 폴리곤).
Tree_traverse (tree.front, eye)
- - 시점(eye)이 현재 노드(분할 평면)의 뒤에 있는 경우
else if location < 0 then
- - 1. 앞쪽 자식 트리를 먼저 순회한다 (더 먼 폴리곤).
Tree_traverse (tree.front, eye) ;
- - 2. 현재 노드의 폴리곤을 그린다.
display (tree.polygon_list) ;
- - 3. 뒤쪽 자식 트리를 순회한다 (더 가까운 폴리곤).
Tree_traverse (tree.back, eye)
- - 시점(eye)이 현재 노드의 분할 평면 위에 있는 경우
else
- - 평면 위에 있으므로, 양쪽 자식 트리를 순회한다.
- - (현재 노드의 폴리곤은 시점과 동일 평면에 있어 보이지 않거나, 선으로 표현될 수 있다.)
Tree_traverse (tree.front, eye) ;
Tree_traverse (tree.back, eye)
end if ;
end if ;
end Tree_traverse;
5. 응용 분야
컴퓨터 그래픽 분야에서 BSP 트리는 공간을 빠르고 정확하게 그리는 데 중요한 역할을 한다. 기존의 화가 알고리즘은 뒤쪽부터 앞쪽까지 순서대로 그려나가지만, 불필요한 부분을 겹쳐 그리는 비효율성과 일부 물체가 제대로 그려지지 않는 문제가 있다. Z 버퍼 기법은 물체를 정확히 그릴 수 있지만 추가 메모리가 필요하다는 단점이 있다. 반면, BSP 트리는 Z 버퍼나 별도의 물체 정렬 과정 없이 트리를 정해진 순서대로 순회하는 것만으로 공간을 정확하게 표현할 수 있다. 또한, 시야에 들어오는 물체만 그리도록 돕는 가시 목록과 같은 알고리즘의 기반이 되기도 한다.
BSP 트리의 주요 단점은 공간 구성을 위한 사전 처리 시간이 필요하며, 미리 정의된 구조 때문에 트리 내에서 물체를 직접 움직이기 어렵다는 점이다. 그러나 이러한 단점은 BSP 트리와 Z 버퍼 기법을 함께 사용함으로써 극복할 수 있다. BSP 트리를 이용해 정적인 배경 공간을 구성하고, 문이나 캐릭터처럼 움직이는 물체는 Z 버퍼를 사용하여 장면에 정확하게 통합하는 방식이다.
이러한 특징 덕분에 BSP 트리는 3D 컴퓨터 게임, 특히 실내 환경을 주로 다루는 1인칭 슈팅 게임(FPS)에서 널리 사용된다. BSP 자료 구조를 게임에 처음 도입한 사례는 둠으로 알려져 있다. 이후 둠 (id Tech 1), 퀘이크 (id Tech 2 변형), 골드src, 소스 엔진 등 여러 유명 게임 엔진에서 BSP 트리를 활용하여 장면의 정적 구조를 표현하고, Z 버퍼와 결합하여 동적인 요소들을 처리했다. BSP 트리는 장면에 있는 다각형에 대한 공간 정보를 효율적으로 저장하고 검색하는 방법을 제공하지만, 그 자체로 은면 제거 문제를 완전히 해결하지는 못한다.
이 외에도 BSP 트리는 광선 추적(Ray Tracing)이나 충돌 감지(Collision Detection) 같은 컴퓨터 그래픽스 기법에도 응용된다. 또한, 이미지를 효율적으로 표현하기 위한 이미지 압축 기술에도 적용된 사례가 있다.[5]
6. 기타 공간 분할 구조
이진 공간 분할법은 공간을 각 노드에서 두 개의 부분 영역으로 분할해 나간다. 이와 관련하여 공간을 4개로 분할하는 사분 트리나 8개로 분할하는 옥트리가 있다. 사분 트리와 옥트리는 각각 2차원 공간과 3차원 공간의 분할에 특화되어 있다.
| 이름 | p | s |
|---|---|---|
| 이진 공간 분할법 | 1 | 2 |
| 사분 트리 | 2 | 4 |
| 옥트리 | 3 | 8 |
여기서, ''p''는 사용되는 분할 면의 수, ''s''는 형성되는 부분 영역의 수이다.
이들과 비슷하지만, 임의의 차원에서 사용할 수 있는 공간 분할 구조로는 kd 트리가 있다.
참조
[1]
보고서
Study for Applying Computer-Generated Images to Visual Simulation
https://books.google[...]
U.S. Air Force Human Resources Laboratory
1969
[2]
학회자료
Set operations on polyhedra using binary space partitioning trees
ACM
[3]
학술지
Binary space partitioning generates hierarchical and rectilinear neutral landscape models suitable for human-dominated landscapes
2022
[4]
학회자료
On Visible Surface Generation by A Priori Tree Structures
http://www.cs.unc.ed[...]
ACM
[5]
논문
Image compression using binary space partitioning trees
1996-12
[6]
웹사이트
Binary Space Partition Trees in 3d worlds
http://web.cs.wpi.ed[...]
[7]
보고서
AN INVESTIGATION INTO REAL-TIME 3D POLYGON RENDERING USING BSP TREES
1999-04
[8]
문서
On Visible Surface Generation by A Priori Tree Structures
1980-07
[9]
문서
Front-to-Back Display of BSP Trees
1991-09
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com