바이너리 공간

Binary space partitioning
참고 항목: k-d 트리, Octree 및 Quadtree
BSP 트리를 만드는 프로세스

컴퓨터 과학에서, 이진 공간 분할(BSP)은 하이퍼플레인을 파티션으로 사용함으로써 유클리드 공간을 두 개의 볼록한 집합으로 재귀적으로 세분화하는 공간 분할 방법이다.이 세분화 프로세스는 BSP 트리로 알려진 트리 데이터 구조의 형태로 공간 내의 객체를 표현합니다.

바이너리 공간 파티셔닝은 1969년에 [1][2]3D 컴퓨터 그래픽의 맥락에서 개발되었습니다.BSP 트리의 구조는 지정된 위치의 뷰어에 대해 앞뒤로 정렬된 개체와 같은 씬(scene) 내의 개체에 대한 공간 정보를 효율적으로 제공할 수 있으므로 렌더링에 도움이 됩니다.BSP의 다른 응용 프로그램에는 [3]CAD에서 형상을 사용한 기하학적 연산(구성적인 솔리드 지오메트리), 로봇 및 3D 비디오 게임에서의 충돌 감지, 광선 추적 및 복잡한 공간 장면의 처리와 관련된 기타 응용 프로그램이 포함됩니다.

개요

이진 공간 파티셔닝은 파티셔닝이 하나 이상의 요구 사항을 충족할 때까지 장면을 두 개로 재귀적으로 분할하는 일반적인 프로세스입니다.이는 공간을 분할하는 하이퍼플레인이 k-d 트리 또는 쿼드 트리에 있는 것처럼 좌표 축에 정렬되는 것이 아니라 방향을 가질 수 있는 k-d 트리 및 쿼드 트리와 같은 다른 공간 트리 구조의 일반화라고 볼 수 있다.평면 폴리곤으로 구성된 장면을 렌더링하기 위해 컴퓨터 그래픽에서 사용되는 경우 씬(scene)의 폴리곤에 의해 정의된 평면과 일치하도록 분할 평면이 자주 선택됩니다.

파티션 플레인의 구체적인 선택과 파티션프로세스를 종료하기 위한 기준은 BSP 트리의 목적에 따라 다릅니다.예를 들어 컴퓨터 그래픽스 렌더링에서는 BSP 트리의 각 노드가 임의의 순서로 렌더링할 수 있는 폴리곤만을 포함할 때까지 장면이 분할됩니다.따라서 백페이스 컬링을 사용하는 경우 각 노드에는 볼록한 폴리곤 세트가 포함되지만 양면 폴리곤을 렌더링할 경우 BSP 트리의 각 노드에는 단일 평면에 폴리곤만 포함됩니다.충돌 감지 또는 광선 추적에서 장면은 충돌 또는 광선 교차 테스트가 간단한 원시 요소로 나눌 수 있습니다.

바이너리 공간 파티셔닝은 폴리곤으로 구성된 3차원 장면을 빠르게 그려야 하는 컴퓨터 그래픽에서 비롯되었습니다.이러한 장면을 그리는 간단한 방법은 보는 사람으로부터 뒤로, 앞으로, 그리고 배경과 이전의 다각형 위에 각각의 더 가까운 물체로 그리는 다각형들을 그리는 화가의 알고리즘이다.이 방법에는 폴리곤을 백투프런트 순서로 정렬하는 데 필요한 시간과 중복 폴리곤에서 오류가 발생할 수 있다는 두 가지 단점이 있습니다.Fuchs와 공동[2] 저자들은 BSP 트리를 구축하면 주어진 시점(장면 내 폴리곤 수에서 선형)에 대해 폴리곤을 신속하게 정렬할 수 있는 방법을 제공하고 겹치는 폴리곤을 세분화하여 화가의 알고리즘에서 발생할 수 있는 오류를 방지함으로써 이 두 가지 문제를 모두 해결할 수 있음을 보여주었다.바이너리 공간 파티셔닝의 단점은 BSP 트리를 생성하는 데 시간이 많이 걸릴 수 있다는 것입니다.따라서 일반적으로 씬(scene)에서 렌더링 또는 기타 실시간 작업을 수행하기 전에 사전 계산 단계로 정적 지오메트리에서 한 번 수행됩니다.BSP 트리를 구축하는 데 비용이 들기 때문에 트리로 이동하는 개체를 직접 구현하기가 어렵고 비효율적입니다.

BSP 트리는 3D 비디오 게임, 특히 1인칭 슈팅 게임 및 실내 환경에서 자주 사용됩니다.BSP 트리를 사용하는 게임 엔진에는 Doom(id Tech 1), Quake(id Tech 2 변종), GoldSrc 및 Source 엔진이 있습니다.장면의 정적 형상을 포함하는 BSP 트리는 종종 문이나 캐릭터와 같은 이동 가능한 물체를 배경 장면에 올바르게 결합하기 위해 Z 버퍼와 함께 사용됩니다.이진 공간 파티셔닝은 씬(scene)의 폴리곤에 대한 공간 정보를 저장 및 검색하는 편리한 방법을 제공하지만 가시적인 표면 결정 문제를 해결하지는 않습니다.

시대

BSP 트리의 표준 용도는 화가의 알고리즘을 사용하여 폴리곤(양면, 즉 배면 도태 없이)을 렌더링하는 것입니다.각 폴리곤은 임의로 선택할 수 있는 앞면과 뒷면으로 지정되며 트리 구조에만 영향을 줄 뿐 필요한 [2]결과는 아니다.이러한 트리는 씬(scene)에 있는 모든 폴리곤의 정렬되지 않은 목록으로 구성됩니다.폴리곤 목록에서 BSP 트리를 구성하는 재귀 알고리즘은 다음과 같습니다.[2]

  1. 목록에서 폴리곤 P를 선택합니다.
  2. BSP 트리에 노드N을 만들고 해당 노드의 폴리곤 목록에 P를 추가합니다.
  3. 목록의 다른 폴리곤에 대해:
    1. 해당 폴리곤이 P를 포함하는 평면 앞에 있는 경우 해당 폴리곤을 P 앞에 있는 노드 목록으로 이동합니다.
    2. 해당 폴리곤이 P를 포함하는 평면 뒤에 있는 경우 해당 폴리곤을 P 뒤의 노드 목록으로 이동합니다.
    3. 해당 폴리곤이 P를 포함하는 평면에 교차하는 경우 폴리곤을 두 개로 분할하여 P의 앞뒤에 있는 폴리곤의 각 목록으로 이동합니다.
    4. 해당 폴리곤이 P를 포함하는 평면에 있는 경우 노드 N의 폴리곤 목록에 추가합니다.
  4. P 앞에 있는 폴리곤 목록에 이 알고리즘을 적용합니다.
  5. 이 알고리즘을 P 뒤에 있는 폴리곤 목록에 적용합니다.

다음 그림은 이 알고리즘을 사용하여 라인 또는 폴리곤 목록을 BSP 트리로 변환하는 방법을 보여 줍니다.8개의 스텝(즉,-8ii) 각각에서 위의 알고리즘이 라인 리스트에 적용되어 트리에 새로운 노드가 1개 추가된다.

씬(scene)을 구성하는 선 목록(3D, 폴리곤)부터 시작합니다.트리 다이어그램에서 리스트는 둥근 직사각형으로 표시되고 BSP 트리 내의 노드는 원으로 표시됩니다.선의 공간도에서는 선의 '전면'으로 선택된 방향을 화살표로 나타낸다. Example of BSP tree construction - step 1.svg
i. 위의 알고리즘의 절차에 따라
  1. 리스트에서 A라는 행을 선택하고, 그리고...
  2. 노드에 추가합니다.
  3. 리스트의 나머지 행을 A의 앞 행(B2, C2, D2)과 뒤의 행(B1, C1, D1)으로 분할했습니다.
  4. 먼저 A 앞에 있는 행을 처리합니다(스텝 ii~v).
  5. (스텝 vi~12월) 뒷사람에 의해 조정됩니다.
 Example of BSP tree construction - step 2.svg
ii. 이제 알고리즘을 A 앞에 있는 줄 목록(B2, C2, D2)에 적용합니다.라인 B2를 선택하여 노드에 추가하고 나머지 목록을 B2 앞에 있는 라인(D2)과 뒤에 있는 라인(C2, D3)으로 분할합니다. Example of BSP tree construction - step 3.svg
iii. B2와 A 앞에 있는 라인 리스트에서 라인 D2를 선택합니다.이 행은 목록의 유일한 행이므로 노드에 추가한 후에는 더 이상 수행할 필요가 없습니다. Example of BSP tree construction - step 4.svg
iv. B2의 앞줄은 끝났으니 B2의 뒷줄(C2와 D3)을 고려해 주세요.다음 중 하나(C2)를 선택하여 노드에 추가하고 목록(D3)의 다른 행을 C2 앞의 행 목록에 넣습니다. Example of BSP tree construction - step 5.svg
v. 이제 C2 앞에 있는 줄 목록을 보세요.행(D3)은 1개뿐이므로 노드에 추가한 후 계속 진행합니다. Example of BSP tree construction - step 6.svg
vi. BSP 트리에 A 앞의 행을 모두 추가했기 때문에 A 뒤의 행 리스트부터 시작합니다.이 리스트에서 라인(B1)을 선택하면 노드에 B1을 추가하고 나머지 리스트를 B1 앞의 라인(D1)과 B1 뒤의 라인(C1)으로 분할합니다. Example of BSP tree construction - step 7.svg
vii. 먼저 B1 앞에 있는 행 목록을 처리하면 D1이 이 목록의 유일한 행이므로 노드에 추가하여 계속 진행합니다. Example of BSP tree construction - step 8.svg
ivii. 다음으로 B1 뒤의 행 목록을 보면 이 목록의 행은 C1뿐이므로 이 행을 노드에 추가하면 BSP 트리가 완성됩니다. Example of BSP tree construction - step 9.svg

분할 평면을 가로지르는 선이나 폴리곤을 두 개로 분할해야 하므로 트리의 최종 폴리곤 또는 라인 수는 원래 목록보다 더 큰 경우가 많습니다(때로는 훨씬 더 큰 경우도[2] 있습니다).이 증가를 최소화하고 마지막 트리에서 합리적인 균형을 유지하는 것이 바람직합니다.따라서 효율적인 BSP 트리를 작성하려면 분할 평면으로 사용할 폴리곤 또는 선을 선택하는 것이 중요합니다(알고리즘의 스텝1 ） 。

트래버설

BSP 트리는 트리의 특정 함수에 의해 결정된 순서로 선형 시간 내에 통과됩니다.다시 화가의 알고리즘을 사용하여 양면 폴리곤을 렌더링하는 예를 사용하여 폴리곤 P를 올바르게 그리려면 먼저 평면 P 뒤에 있는 모든 폴리곤을 그린 다음 폴리곤 P 앞에 있는 폴리곤을 그려야 합니다.씬(scene)의 모든 폴리곤에 대해 이 도면 순서가 충족되면 전체 씬(scene)이 올바른 순서로 렌더링됩니다.이 순서는 다음 [2]알고리즘을 사용하여 BSP 트리를 재귀적으로 통과함으로써 구현할 수 있습니다.지정된 표시 위치 V에서 BSP 트리를 렌더링하려면

  1. 현재 노드가 리프 노드인 경우 현재 노드에서 폴리곤을 렌더링합니다.
  2. 그렇지 않으면 보기 위치 V이 현재 노드 앞에 있는 경우:
    1. 현재 노드 뒤에 폴리곤을 포함하는 하위 BSP 트리를 렌더링합니다.
    2. 현재 노드에서 폴리곤 렌더링
    3. 현재 노드 앞에 있는 폴리곤을 포함하는 하위 BSP 트리를 렌더링합니다.
  3. 그렇지 않으면 보기 위치 V이 현재 노드 뒤에 있는 경우:
    1. 현재 노드 앞에 있는 폴리곤을 포함하는 하위 BSP 트리를 렌더링합니다.
    2. 현재 노드에서 폴리곤 렌더링
    3. 현재 노드 뒤에 폴리곤을 포함하는 하위 BSP 트리를 렌더링합니다.
  4. 그렇지 않으면 표시 위치 V가 현재 노드와 정확히 연관된 평면에 있어야 합니다.그 후, 다음과 같이 입력합니다.
    1. 현재 노드 앞에 있는 폴리곤을 포함하는 하위 BSP 트리를 렌더링합니다.
    2. 현재 노드 뒤에 폴리곤을 포함하는 하위 BSP 트리를 렌더링합니다.
Example of BSP tree traversal.svg

위에서 생성된 BSP 트리에 이 알고리즘을 재귀적으로 적용하면 다음 절차가 수행됩니다.

  • 이 알고리즘은 먼저 트리 루트노드(노드 A)에 적용됩니다.V는 노드 A 앞에 있으므로 A 뒤에 폴리곤이 포함된 하위 BSP 트리에 알고리즘을 먼저 적용합니다.
    • 이 트리에는 루트 노드 B1이 있습니다.V는 B1의 배후에 있으므로 먼저 알고리즘을 B1의 앞에 있는 폴리곤을 포함하는 하위 BSP 트리에 적용합니다.
      • 이 트리는 리프 노드 D1일 뿐이므로 폴리곤 D1이 렌더링됩니다.
    • 그런 다음 폴리곤 B1을 렌더링합니다.
    • 다음으로 B1의 배후에 폴리곤을 포함한 자 BSP 트리에 알고리즘을 적용합니다.
      • 이 트리는 리프 노드 C1일 뿐이므로 폴리곤 C1이 렌더링됩니다.
  • 그런 다음 A의 다각형을 그립니다.
  • 그런 다음 A 앞에 있는 폴리곤을 포함하는 하위 BSP 트리에 알고리즘을 적용합니다.
    • 이 트리에는 루트 노드 B2가 있습니다.V는 B2의 배후에 있으므로 먼저 알고리즘을 B2의 앞에 있는 폴리곤을 포함하는 하위 BSP 트리에 적용합니다.
      • 이 트리는 리프 노드 D2일 뿐이므로 폴리곤 D2가 렌더링됩니다.
    • 그런 다음 폴리곤 B2를 렌더링합니다.
    • 다음으로 B2의 배후에 폴리곤을 포함한 자 BSP 트리에 알고리즘을 적용합니다.
      • 이 트리에는 루트 노드 C2가 있습니다.V는 C2 앞에 있으므로 먼저 C2 뒤에 폴리곤을 포함하는 하위 BSP 트리에 알고리즘을 적용합니다.하지만 그런 트리가 없어서 계속합니다.
      • 폴리곤 C2를 렌더링합니다.
      • C2 앞에 있는 폴리곤을 포함하는 하위 BSP 트리에 알고리즘을 적용합니다.
        • 이 트리는 리프 노드 D3일 뿐이므로 폴리곤 D3가 렌더링됩니다.

트리는 선형 시간으로 횡단되며 화가 알고리즘에 적합한 폴리곤을 원근순서(D1, B1, C1, A, D2, B2, C2, D3)로 렌더링합니다.

타임라인

  • 1969 Schumacker 등은 [1]가상 환경에서 얼마나 조심스럽게 배치된 평면을 사용하여 폴리곤 순서를 가속화할 수 있는지를 설명하는 보고서를 발표했다.이 기술은 평면 반대편에 있는 폴리곤은 어떤 방식으로든 더 가까운 폴리곤을 방해할 수 없다는 것을 나타내는 깊이 일관성을 이용했다.이것은 에반스와 서덜랜드뿐만 아니라 GE에 의해 만들어진 비행 시뮬레이터에 사용되었다.그러나 다각형 데이터 구성 작성은 장면 설계자가 수동으로 수행했습니다.
  • 1980년 Fuchs [2]등폴리곤과 일치하는 평면을 사용하여 3D 공간을 재귀적으로 분할함으로써 슈마커의 아이디어를 가상 환경에서 3D 객체 표현으로 확장했습니다.이를 통해 BSP 트리(Binary Space Partitioning Tree)로 알려진 계층형 폴리곤 데이터 구조를 완전히 자동화된 알고리즘으로 생성할 수 있었습니다.이 프로세스는 환경/개체별로 한 번씩 수행되는 오프라인 전처리 단계로 진행되었습니다.런타임에는 트리를 통과하여 뷰 의존적 가시성 순서가 생성되었습니다.
  • 1981년 네일러 박사 논문은 BSP 트리의 완전한 개발과 두 방법 간의 연결뿐만 아니라 사전 계산 가시성을 위해 강하게 연결된 구성요소를 사용하는 그래프 이론 접근법을 제공했다.차원 독립 공간 탐색 구조로서의 BSP 트리가 강조되었으며 가시 표면 결정에 적용되었다.이 논문은 또한 나무의 크기와 새로운 폴리곤의 수가 합리적이라는 것을 입증하는 첫 번째 경험적 데이터를 포함했다(우주왕복선의 모델을 사용).
  • 1983 Fuchs 등은 Ikonas 프레임 버퍼 시스템에서 BSP 트리 알고리즘의 마이크로 코드 구현을 설명했습니다.이것은 BSP 트리를 사용한 실시간 가시 표면 결정의 첫 번째 시연이었다.
  • 1987년 Thibault와[3] Naylor는 전통적인 b-rep(경계 표현)과 달리 BSP 트리를 사용하여 임의의 다면체를 표현하는 방법을 설명했다.이는 표면 기반 표현과 비교하여 확실한 표현을 제공하였다.도구를 사용하여 다면체에서의 설정 연산을 설명하여 건설적인 솔리드 지오메트리(CSG)를 실시간으로 구현했습니다.이는 Quake 편집기에서 소개되고 Unreal 편집기에서 채택된 "브러쉬"를 사용한 BSP 레벨 설계의 선구자였습니다.
  • 1990 Naylor, Amanatides 및 Thibault는 두 개의 원래 트리에서 새로운 BSP 트리를 형성하기 위해 두 개의 BSP 트리를 병합하는 알고리즘을 제공했습니다.이를 통해 BSP 트리로 표현되는 이동 객체를 정적 환경(BSP 트리로도 표현됨), 다면체에서의 매우 효율적인 CSG 조작, O(log n * log n)에서의 정확한 충돌 검출, 2개의 인터투과 객체(x 에 사용됨)에 포함된 투명 표면의 적절한 순서 부여 등 많은 이점을 얻을 수 있습니다.-레이 비전 효과).
  • 1990 Teller와 Séquin은 직교 2D 환경에서 가시적인 표면 결정을 가속화하기 위해 잠재적으로 가시적인 세트의 오프라인 생성을 제안했다.
  • 1991년 Gordon과 Chen[CHEN91]은 기존의 전면 대 전면 접근 방식이 아닌 BSP 트리에서 전면 대 후면 렌더링을 수행하는 효율적인 방법을 설명했습니다.이들은 특수 데이터 구조를 이용해 그려진 화면과 렌더링되지 않은 화면을 효율적으로 기록했습니다.이 알고리즘은 당시의 표준 컴퓨터 그래픽스 교과서(컴퓨터 그래픽스: Principle and Practice)의 BSP Tree 설명과 함께 존 카맥이 Doom(비디오 게임)을 제작할 때 사용했습니다.
  • 1992년 Teller 박사 논문은 잠재적으로 가시적인 세트의 효율적인 생성을 임의의 3D 다각형 환경에서 실시간 가시 표면 결정을 가속화하는 전처리 단계로 설명했습니다.이것은 퀘이크에서 사용되었고 그 게임의 성능에 큰 기여를 했다.
  • 1993 Naylor는 좋은 BSP 트리의 특징에 대한 질문에 대답했습니다.그는 나무를 검색하는 예상 비용을 수학적으로 측정하기 위해 (최악의 경우 분석이 아닌) 예상 사례 모형을 사용하고 이 측정값을 사용하여 양호한 BSP 트리를 구축했습니다.직관적으로 트리는 객체를 다중 해상도(더 정확히는 근사 트리)로 나타냅니다.허프만 코드 및 확률론적 이진 검색 트리와 병렬이 그려진다.
  • 1993년 Hayder Radha 박사논문에서는 BSP 트리를 이용한 (자연적인) 이미지 표현 방법을 기술하였다.여기에는 임의의 입력 이미지를 위한 최적의 BSP 트리 구축 프레임워크 개발이 포함됩니다.이 프레임워크는 Lest-Square-Error(LSE; 최소 제곱 오류) Partitioning Line(LPE; 파티션 라인) 변환이라고 하는 새로운 이미지 변환을 기반으로 합니다.H. Radha의 논문은 또한 BSP 트리를 이용한 최적의 RD(속도 왜곡) 이미지 압축 프레임워크와 이미지 조작 방식을 개발했습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Schumacker, R.A.; Brand, B.; Gilliland, M.G.; Sharp, W.H. (1969). Study for Applying Computer-Generated Images to Visual Simulation (Report). U.S. Air Force Human Resources Laboratory. AFHRL-TR-69-14.
  2. ^ a b c d e f g Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). "On Visible Surface Generation by A Priori Tree Structures" (PDF). SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive techniques. ACM. pp. 124–133. doi:10.1145/965105.807481.
  3. ^ a b Thibault, William C.; Naylor, Bruce F. (1987). "Set operations on polyhedra using binary space partitioning trees". SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM. pp. 153–162. doi:10.1145/37402.37421.

기타 참고 자료

외부 링크