바이너리 공간 분할: 이진 공간 분할 탐색: 컴퓨터 비전의 기초 및 응용

By Fouad Sabry

이진 공간 분할이란

컴퓨터 과학에서 BSP(이진 공간 분할)는 다음을 사용하여 유클리드 공간을 두 개의 볼록 집합으로 재귀적으로 세분화하는 공간 분할 방법입니다. 파티션으로서의 초평면. 이러한 세분화 과정을 통해 BSP 트리라고 알려진 트리 데이터 구조의 형태로 공간 내의 개체가 표현됩니다.

혜택을 받는 방법

(I) 다음 주제에 대한 통찰 및 검증:

1장: 바이너리 공간 분할

2장: 바이너리 트리

3장: 렌더링(컴퓨터 그래픽)

4장: 스캔라인 렌더링

5장: 은면 결정

6장: 쿼드트리

장 7: 옥트리

8장: 공간 분할

9장: K-d 트리

10장: 클리핑(컴퓨터 그래픽)

( II) 이진 공간 분할에 관한 대중의 주요 질문에 답합니다.

(III) 여러 분야에서 이진 공간 분할을 사용하는 실제 사례.

이 책은 누구입니까?

전문가, 학부 및 대학원생, 매니아, 취미생활자 및 모든 종류의 바이너리 공간 분할에 대한 기본 지식이나 정보를 넘어서고자 하는 사람들을 위한 것입니다.

 

 

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 4, 2024

Book preview

1 장 : 바이너리 공간 분할

이진 공간 분할(BSP)은 초평면을 파티션으로 사용하여 유클리드 공간을 두 개의 볼록 집합으로 재귀적으로 세분화하는 컴퓨터 과학의 공간 분할 방법입니다. 이 절차는 트리와 같은 데이터 구조인 BSP 트리의 형태로 공간 내의 객체 표현을 생성합니다.

1969년에는 3D 컴퓨터 그래픽의 맥락에서 이진 공간 분할이 개발되었습니다. 로봇 공학 및 3D 비디오 게임, 레이 트레이싱 및 복잡한 공간 상황의 조작과 관련된 기타 응용 프로그램의 충돌 감지.

분할이 하나 이상의 요구 사항을 충족할 때까지 장면을 재귀적으로 두 개로 분리하는 일반적인 프로세스를 이진 공간 분할이라고 합니다. 이는 k-d 트리 및 쿼드트리와 같은 다른 공간 트리 구조의 일반화로 볼 수 있으며, 공간을 분할하는 초평면이 좌표축과 정렬되지 않습니다. 컴퓨터 그래픽에서 평면 다각형으로 구성된 풍경을 렌더링할 때 분할 평면은 일반적으로 장면의 다각형에 의해 정의된 평면과 일치하도록 선택됩니다.

파티션 평면의 정확한 선택과 파티션 프로세스를 중지하는 기준은 BSP 트리의 용도에 따라 다릅니다. 예를 들어, 컴퓨터 그래픽 렌더링에서는 BSP 트리의 각 노드에 어떤 순서로든 그릴 수 있는 폴리곤만 포함될 때까지 씬이 세분화됩니다. 뒷면 컬링을 사용할 때, 각 노드에는 볼록한 폴리곤 세트가 있지만, 양면 폴리곤을 렌더링할 때는 BSP 트리의 각 노드에 평면 기반 폴리곤만 포함됩니다. 충돌 감지 또는 레이 트레이싱에서 장면은 충돌 또는 광선 교차 테스트가 간단한 프리미티브로 분할될 수 있습니다.

컴퓨터 그래픽은 다각형으로 구성된 3차원 장면을 빠르게 렌더링하기 위해 이진 공간의 분할이 필요했습니다. 화가의 알고리즘은 관찰자와의 거리 순서대로, 뒤에서 앞쪽으로 다각형을 생성하고, 관객에게 더 가까운 각 물체로 배경과 이전 다각형을 페인팅합니다. 이 방법에는 두 가지 단점이 있는데, 하나는 다각형을 역순으로 정렬하는 데 필요한 시간이고, 다른 하나는 다각형이 겹치는 오류일 가능성입니다. 푹스와 공동 저자들은 BSP 트리를 구성하면 주어진 시점(씬의 폴리곤 수가 선형임)에 따라 폴리곤을 빠르게 정렬할 수 있고, 페인터의 알고리즘 관련 오류를 방지하기 위해 겹치는 폴리곤을 세분화하여 이 두 가지 문제를 모두 해결할 수 있음을 보여주었습니다. 바이너리 공간 분할의 단점은 BSP 트리를 생성하는 데 필요한 시간입니다. 따라서 씬에서 렌더링 또는 기타 실시간 작업을 수행하기 전에 일반적으로 정적 지오메트리에서 사전 계산 단계로 한 번 수행됩니다. 오브젝트를 트리로 직접 옮기는 것은 BSP 트리를 만드는 데 드는 비용 때문에 어렵고 비효율적입니다.

BSP 트리는 3D 비디오 게임, 특히 1인칭 슈팅 게임과 실내 설정이 있는 타이틀에서 자주 사용됩니다. Doom (id Tech 1), Quake (id Tech 2 변형), GoldSrc 및 Source는 BSP 트리를 사용하는 게임 엔진입니다. 씬의 스태틱 지오메트리를 담고 있는 BSP 트리는 문이나 캐릭터와 같은 무버블 엘리먼트를 배경 씬에 올바르게 블렌딩하기 위해 Z 버퍼와 함께 자주 활용됩니다. 이진 공간 분할은 장면의 다각형에 대한 공간 정보의 저장 및 검색을 용이하게 하지만 가시적인 표면 결정 문제를 해결하지는 못합니다.

BSP 트리의 표준 응용 프로그램은 페인터의 방법을 사용하여 뒷면 컬링 없이 양면 폴리곤을 렌더링하는 것입니다. 각 다각형에는 자유롭게 선택할 수 있는 앞면과 뒷면이 있으며 원하는 결과가 아닌 나무의 구조에만 영향을 미칩니다.

P 리스트에서 다각형을 선택합니다.

BSP 트리의 노드 N에 있는 폴리곤 목록에 P를 추가합니다.

목록의 모든 추가 다각형에 대해:

해당 다각형이 P를 포함하는 평면 앞에 있는 경우 P 앞의 노드 목록에 추가합니다.

이 다각형이 P를 포함하는 평면 뒤에 완전히 있는 경우 P 뒤의 노드 목록에 추가합니다.

다각형이 P를 포함하는 평면과 교차하는 경우 두 개의 다각형으로 나누고 각각 P 뒤와 앞에 있는 다각형 목록에 추가합니다.

이 다각형이 P를 포함하는 평면에 있는 경우 노드 N의 다각형 목록에 추가합니다.

이 절차를 P 앞의 다각형 목록에 적용합니다.

이 방법을 P 뒤의 다각형 목록에 적용합니다.

이 다이어그램은 이 접근법을 사용하여 선이나 폴리곤 목록을 BSP 트리로 바꾸는 방법을 보여줍니다. 여덟 단계(i.-viii) 각각에서 앞의 방법이 줄 목록에 적용되고 새 노드가 트리에 추가됩니다.

분할 평면을 가로지르는 선 또는 다각형은 둘로 분할되어야 하기 때문에 트리의 최종 다각형 또는 선 수는 초기 목록보다 더 큰 경우가 많고 때로는 상당히 큽니다. 최종 트리에서 공정한 균형을 유지하면서 이러한 성장을 제한하는 것이 좋습니다. (이 방법의 1단계에서) 분할 평면으로 활용할 폴리곤 또는 라인을 결정하는 것은 BSP 트리를 효과적으로 만드는 데 매우 중요합니다.

BSP 트리는 트리의 특정 함수에 의해 주어진 순서대로 선형 시간으로 순회됩니다. 다각형 P를 적절하게 작성하기 위해서는 화가의 기법을 사용하여 양면 다각형을 렌더링하는 예를 사용하여 평면 P가 있는 모든 다각형을 먼저 그린 다음 다각형 P를 그리고 마지막으로 P 앞에 다각형을 그려야 합니다. 장면의 모든 다각형이 이 그리기 순서를 준수하면 장면이 올바른 순서로 렌더링됩니다. 다음 알고리즘을 사용하여 BSP 트리를 반복적으로 순회하여 이 프로시저를 구현할 수 있습니다. 주어진 유리한 점 V에서 BSP 트리를 렌더링하고, 현재 노드가 리프 노드인 경우 현재 노드의 다각형을 그립니다.

보기 사이트 V가 현재 노드 앞에 있는 경우 알고리즘은 다음을 계속합니다.

폴리곤을 포함하는 자손 BSP 트리를 현재 노드 뒤에 렌더링합니다.

현재 노드에 있는 다각형 렌더링

폴리곤을 포함하는 자손 BSP 트리를 현재 노드 앞에 렌더링합니다.

보기 위치 V가 현재 노드 뒤에 있는 경우:

폴리곤을 포함하는 자손 BSP 트리를 현재 노드 앞에 렌더링합니다.

현재 노드에 있는 다각형 렌더링

폴리곤을 포함하는 자손 BSP 트리를 현재 노드 뒤에 렌더링합니다.

그렇지 않은 경우 보기 위치 V는 현재 노드와 연결된 평면에 정확하게 있어야 합니다. 그러면:

폴리곤을 포함하는 자손 BSP 트리를 현재 노드 앞에 렌더링합니다.

폴리곤을 포함하는 자손 BSP 트리를 현재 노드 뒤에 렌더링합니다.

다음 단계는 이 기법을 이전에 생성된 BSP 트리에 반복 적용한 결과입니다:

이 절차는 처음에 트리의 루트 노드 A에 적용되고, V는 A 앞에 있으므로, 절차는 처음에 A 뒤에 폴리곤을 포함하는 자손 BSP