Binary Space Partitioning, Quadtree, Octree를 언제 사용합니까?
저는 최근 이진 공간 분할 트리와 3D 그래픽 및 충돌 감지에 대한 적용에 대해 배웠습니다. 또한 쿼드 트리 및 옥트리와 관련된 자료를 간략히 살펴 보았습니다. 언제 bsp 트리보다 쿼드 트리를 사용합니까? 아니면 그 반대의 경우도 마찬가지입니까? 서로 바꿔 사용할 수 있습니까? 다음과 같은 표를 작성하기에 충분한 정보가 있으면 만족할 것입니다.
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
A, B, C는 무엇입니까?
귀하의 질문에 대한 명확한 답변이 없습니다. 데이터 구성 방식에 전적으로 달려 있습니다.
명심해야 할 사항 :
쿼드 트리는 내비게이션 시스템의지도 렌더링과 같이 대부분 2 차원 데이터에 가장 적합합니다. 이 경우 지오메트리에 더 잘 적응하고 노드 구조를 작게 유지하기 때문에 옥트리보다 빠릅니다.
Octrees 및 BVH (Bounding Volume Hierarchies)는 데이터가 3 차원 인 경우 이점이 있습니다. 기하학적 엔티티가 3D 공간에 클러스터 된 경우에도 매우 잘 작동합니다. ( Octree vs BVH 참조 )실물)
Oc- 및 Quadtrees의 장점은 언제든지 트리 생성을 중지 할 수 있다는 것입니다. 그래픽 가속기를 사용하여 그래픽을 렌더링하려는 경우 개체 수준에서 트리를 생성하고 단일 그리기 호출에서 각 개체를 그래픽 API에 보낼 수 있습니다. 이것은 개별 삼각형을 보내는 것보다 훨씬 낫습니다 (BSP- 트리를 최대한 사용한다면해야 할 일).
BSP- 트리는 정말 특별한 경우입니다. 2D 및 3D에서 매우 잘 작동하지만 좋은 BSP- 트리를 생성하는 것은 그 자체로 예술 형식입니다. BSP- 트리에는 지오메트리를 더 작은 조각으로 분할해야 할 수있는 단점이 있습니다. 이는 데이터 세트의 전체 다각형 수를 증가시킬 수 있습니다. 렌더링에는 좋지만 충돌 감지 및 광선 추적에는 훨씬 좋습니다.
BSP- 트리의 좋은 특성은 폴리곤 수프를 실제 정렬을 수행하지 않고 모든 카메라 위치에서 완벽하게 뒤에서 앞으로 (또는 그 반대로) 렌더링 할 수있는 구조로 분해한다는 것입니다. 각 관점의 순서는 데이터 구조의 일부이며 BSP- 트리 컴파일 중에 수행됩니다.
그건 그렇고, 10 년 전에 인기가 있었던 이유입니다. Quake는 그래픽 엔진 / 소프트웨어 래스터 라이저가 값 비싼 z- 버퍼를 사용하지 않도록 허용했기 때문에이를 사용했습니다.
언급 된 모든 나무는 나무의 가족 일뿐입니다. 느슨한 옥트리, kd- 트리 하이브리드 트리 및 기타 관련 구조도 많이 있습니다.
BSP- 트리와 다른 종류의 3d- 트리 간의 가장 큰 실질적인 차이점은 BSP- 트리가 더 최적 일 수 있지만 정적 지오메트리 에서만 작동한다는 것 입니다. 이는 BSP- 트리는 일반적으로 구축 속도가 매우 느리기 때문에 일반적인 정적 도시 게임 수준에서는 종종 몇 시간 또는 며칠이 걸립니다.
BSP-Tree를 구축하는 데 더 오래 걸리는 두 가지 주요 이유는 (a) 최적으로 찾는 데 더 오래 걸리는 비축 정렬 분할 평면을 사용하고 (b) 축 경계에서 지오메트리를 세분화하여 객체가 분할 평면을 교차하지 않도록하기 때문입니다.
다른 유형의 3d- 트리 (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy)는 축 정렬 경계 볼륨을 사용하고 볼륨은 (선택적으로) 겹칠 수 있으므로 포함 된 개체를 볼륨에서 잘라낼 필요가 없습니다. 경계. 이 두 가지 모두 BSP 트리보다 트리를 덜 최적화하지만 빌드 속도가 더 빠르며 동적 개체의 경우 변경하기가 더 쉽습니다.
이러한 요소를 상황으로 외삽 ...
실외 지역은 일반적으로 높이 필드 기반지면 표현 (단순 하이트 맵 또는 ROAM과 같은 더 복잡한 지오 밉 매핑 기술)을 사용합니다. 지면 자체는 3D 공간 분할에 참여하지 않고지면에 놓인 물체 만 사용합니다.
더 간단하고 유사한 지오메트리 (집, 나무, 소행성 등)의 인스턴스가 많은 세계는 종종 비 BSP 트리 (예 : BVH)를 사용합니다. 왜냐하면 지오메트리를 BSP 트리에 넣는 것은 지오메트리를 복제하고 분할하는 것을 의미하기 때문입니다. 모든 인스턴스에 대한 세부 지오메트리.
반대로 도시 장면이나 복잡한 실내 환경과 같이 인스턴스가없는 대형 커스텀 정적 메쉬는 일반적으로 런타임 성능 향상을 위해 BSP- 트리를 사용합니다. BSP- 트리가 노드 경계에서 지오메트리를 분할한다는 사실은 BSP 노드가 미리 구성된 삼각형 렌더링 배치로 사용될 수 있기 때문에 렌더링 성능에 도움이됩니다. BSP- 트리는 또한 오 클루 전을 위해 최적화 될 수 있으므로 다른 지오메트리 뒤에있는 것으로 알려진 BSP- 트리의 일부를 그릴 필요가 없습니다.
참조 : Octree 대 BVH (실물), Bounding Volume Hierarchy Tutorial , BSP Tutorial .
BSP는 도시 환경에 가장 적합합니다.
Quadtree는 지형 등에 높이 맵을 사용할 때 가장 적합합니다.
Octree는 태양계와 같은 3D 공간에 지오메트리 덩어리가있을 때 가장 적합합니다.
BSP는 사용하는 플레이버에 따라 충돌 감지를 가속화하는 좋은 옵션입니다. 특히 포인트 및 라인 또는 광선 테스트에서 빠르며 볼륨이있는 경우에는 다소 덜 빠르며 조금 더 복잡합니다.
그래픽에서의 사용과 관련하여 BSP는 거의 쓸모가 없습니다. Octrees는 AABB 트리처럼 전체 가시성 컬링과 같은 작업에 적합합니다.
BSP에 대한 경험은 많지 않지만 렌더링하는 장면이 크면 쿼드 트리보다 옥트리를 사용해야한다고 말할 수 있습니다. 즉, 높이는 너비와 깊이의 절반 이상입니다. 일반적으로 octree는 쿼드 트리에 비해 막대한 비용을 발생시키지 않으며 적절한 속도를내는 잠재력이 있습니다. YMMV.
일반적으로 이러한 것들은 명확한 답변이 없습니다. 나는 A, B, C가 공간의 크기와 차별화되는 물건의 양에 따른 결과라고 제안합니다.
BSP는 오 클루 전만 수행하려는 더 작고 단순한 공간에 더 좋습니다. 주어진 광선에 대한 모든 교차점을 원하면 쿼드 / 옥트리로 업그레이드해야합니다.
As for quadtree vs. octree - how many dimensions do you care a lot about? Two dimensions means a quadtree, four an octree. As stated, as quadtree can work in three-space, but if you want each dimension given a proper treatment, an octree is the way to go.
참고URL : https://stackoverflow.com/questions/99796/when-to-use-binary-space-partitioning-quadtree-octree
'IT박스' 카테고리의 다른 글
| MongoDB : 배열 필드에 요소가 포함되어 있는지 확인하는 방법은 무엇입니까? (0) | 2020.11.12 |
|---|---|
| 주어진 키가 사전에 없습니다. (0) | 2020.11.12 |
| "정적 컨텍스트에서 비 정적 메서드를 참조 할 수 없습니다."오류 (0) | 2020.11.12 |
| 모의 패치를 사용하여 인스턴스 메서드 모의 (0) | 2020.11.12 |
| 자식이 내가 이름을 변경했다고 생각하는 것을 어떻게 막을 수 있습니까? (0) | 2020.11.12 |