바이너리 공간 분할, Quadtree, Octree를 언제 사용합니까?

https://stackoverflow.com/questions/99796

01-07-2019
|

문제

저는 최근 이진 공간 분할 트리와 이를 3D 그래픽 및 충돌 감지에 적용하는 방법에 대해 배웠습니다.나는 또한 쿼드트리와 옥트리와 관련된 자료를 간략하게 정독했습니다.BSP 트리 대신 쿼드트리를 사용하거나 그 반대의 경우는 언제입니까?서로 바꿔서 사용할 수 있나요?다음과 같은 표를 작성할 만큼 충분한 정보가 있다면 만족스러울 것입니다.

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

A, B, C는 무엇입니까?

해결책

귀하의 질문에 대한 명확한 답변이 없습니다.이는 전적으로 데이터 구성 방식에 따라 다릅니다.

명심해야 할 사항:

쿼드트리는 내비게이션 시스템의 지도 렌더링과 같이 대부분 2차원인 데이터에 가장 적합합니다.이 경우 기하학에 더 잘 적응하고 노드 구조를 작게 유지하기 때문에 옥트리보다 빠릅니다.

Octree 및 BVH(Bounding Volume Hierarchies)는 데이터가 3차원인 경우 이점을 얻습니다.기하학적 개체가 3D 공간에 클러스터되어 있는 경우에도 매우 잘 작동합니다.(보다 옥트리 대 BVH)

Oc- 및 Quadtrees의 장점은 원할 때 언제든지 트리 생성을 중지할 수 있다는 것입니다.그래픽 가속기를 사용하여 그래픽을 렌더링하려는 경우 개체 수준에서 트리를 생성하고 단일 그리기 호출로 각 개체를 그래픽 API로 보낼 수 있습니다.이 수행 많이 개별 삼각형을 보내는 것보다 낫습니다(BSP-트리를 최대한 사용하는 경우 수행해야 하는 작업).

BSP-트리는 실제로 특별한 경우입니다.2D와 3D에서 매우 잘 작동하지만 좋은 BSP-트리를 생성하는 것은 그 자체로 예술 형식입니다.BSP-트리에는 지오메트리를 더 작은 조각으로 분할해야 할 수도 있다는 단점이 있습니다.이렇게 하면 데이터 세트의 전체 다각형 수가 늘어날 수 있습니다.렌더링에는 좋지만 충돌 감지 및 광선 추적에는 훨씬 좋습니다.

BSP 트리의 좋은 특성은 실제 정렬을 수행하지 않고도 어떤 카메라 위치에서든 뒤에서 앞으로(또는 그 반대로) 완벽하게 렌더링할 수 있는 구조로 다각형 수프를 분해한다는 것입니다.각 관점의 순서는 데이터 구조의 일부이며 BSP-Tree 컴파일 중에 수행됩니다.

그건 그렇고, 그것이 10년 전에 그토록 인기를 끌었던 이유입니다.Quake는 그래픽 엔진/소프트웨어 래스터라이저가 값비싼 z-버퍼를 사용하지 않도록 허용했기 때문에 이를 사용했습니다.

언급된 모든 나무는 나무의 가족일 뿐입니다.느슨한 옥트리, kd-트리, 하이브리드 트리 및 기타 관련 구조도 많이 있습니다.

다른 팁

BSP-트리와 다른 종류의 3D 트리 사이의 가장 큰 실질적인 차이점은 BSP-트리가 더 최적일 수 있지만 다음에서만 작동한다는 것입니다. 공전 기하학.이는 BSP-트리가 일반적으로 빌드 속도가 매우 느리기 때문이며, 전형적인 정적 도시 게임 레벨의 경우 몇 시간 또는 며칠이 걸리는 경우가 많습니다.

BSP-트리를 구축하는 데 시간이 더 오래 걸리는 두 가지 주요 이유는 (a) 최적으로 찾는 데 시간이 더 오래 걸리는 비축 정렬 분할 평면을 사용하고, (b) 축 경계에서 형상을 세분화하여 분할 평면을 교차하는 객체가 없도록 보장하기 때문입니다.

다른 유형의 3D 트리(Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy)는 축 정렬 경계 볼륨을 사용하고 볼륨은 (선택적으로) 겹칠 수 있으므로 포함된 개체를 볼륨에서 잘라낼 필요가 없습니다. 경계.둘 다 BSP 트리보다 트리를 덜 최적으로 만들지 만 빌드가 더 빠르고 동적 객체에 대한 변경이 더 쉽습니다.

이러한 요소를 상황에 맞게 추정하면...

실외 영역은 일반적으로 간단한 하이트맵이나 ROAM과 같은 보다 복잡한 지리 밉 매핑 기술인 하이트 필드 기반 지면 표현을 사용합니다.지면 자체는 3D 공간 분할에 참여하지 않으며 지면에 배치된 객체만 있습니다.

더 단순하고 유사한 기하학(집, 나무, 소행성 등)의 인스턴스가 많은 세계에서는 종종 비BSP 트리(예: BVH)를 사용합니다. 왜냐하면 기하학을 BSP 트리에 넣는 것은 모든 인스턴스에 대한 세부 형상.

반대로 도시 장면이나 복잡한 실내 환경과 같이 인스턴싱이 없는 대규모 사용자 정의 정적 메시는 일반적으로 런타임 성능 향상을 위해 BSP-트리를 사용합니다.BSP-트리가 노드 경계에서 지오메트리를 분할한다는 사실은 BSP 노드를 미리 구성된 삼각형 렌더링 배치로 사용할 수 있기 때문에 렌더링 성능에 도움이 됩니다.BSP-트리는 또한 다른 형상 뒤에 있는 것으로 알려진 BSP-트리 부분을 그릴 필요가 없도록 폐색에 최적화될 수 있습니다.

또한보십시오: 옥트리 대 BVH, 경계 볼륨 계층 구조 튜토리얼, BSP 튜토리얼.

BSP는 도시 환경에 가장 적합합니다.

Quadtree는 지형 등에 대한 높이 맵을 사용할 때 가장 적합합니다.

Octree는 태양계와 같은 3D 공간에 형상 덩어리가 있는 경우에 가장 적합합니다.

BSP는 사용하는 특성에 따라 충돌 감지를 가속화하는 좋은 옵션입니다.점 및 선 또는 광선 테스트에서는 특히 빠르며 볼륨이 있는 작업에서는 다소 덜 빠르며 조금 더 복잡합니다.

그래픽에서의 사용에 관해서 BSP는 거의 쓸모가 없습니다.Octrees는 AABB 트리와 마찬가지로 총 가시성 컬링과 같은 작업에 적합합니다.

나는 BSP에 대한 경험이 많지 않지만 렌더링하는 장면이 길면 쿼드트리보다는 옥트리를 사용해야 한다고 말할 수 있습니다.즉, 높이는 너비와 깊이의 절반 이상입니다. 경험에 따르면 거의 적용되지 않습니다.일반적으로 옥트리는 쿼드트리에 비해 비용이 많이 들지 않으며 작업 속도를 상당히 높일 수 있는 잠재력을 가지고 있습니다.YMMV.

일반적으로 이러한 것에는 명확한 답이 없습니다.나는 A, B, C가 공간의 크기와 차별화하는 물건의 양에 따른 함수의 결과라고 제안합니다.

BSP는 오클루전만 수행하려는 더 작고 단순한 공간에 더 좋습니다.주어진 광선에 대한 모든 교차점을 원한다면 쿼드/옥트리로 업그레이드해야 합니다.

쿼드트리와octree - 얼마나 많은 차원에 관심이 있나요?2차원은 쿼드트리, 4차원은 옥트리를 의미합니다.언급한 바와 같이 쿼드트리는 3공간에서 작동할 수 있지만 각 차원을 적절하게 처리하려면 옥트리를 사용하는 것이 좋습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow