볼륨 계층 제한
Bounding volume hierarchy
BVH(Bounding Volume Hierarchy)는 기하학적 객체 집합의 트리 구조입니다.트리의 리프 노드를 구성하는 모든 기하학적 개체는 경계 볼륨으로 래핑됩니다.그런 다음 이러한 노드는 작은 세트로 그룹화되어 더 큰 경계 볼륨 내에 포함됩니다.또한 이들은 재귀적인 방식으로 다른 큰 경계 볼륨 내에 그룹화 및 봉인되어 트리 상단에 단일 경계 볼륨이 있는 트리 구조가 됩니다.경계 볼륨 계층은 충돌 감지 및 광선 추적과 같은 기하학적 객체 세트에 대한 여러 작업을 효율적으로 지원하기 위해 사용됩니다.
객체 지오메트리 자체를 테스트하기 전에 객체를 경계 볼륨으로 래핑하고 충돌 테스트를 수행하지만 테스트가 단순해지고 성능이 크게 향상될 수 있지만 경계 볼륨 간에 동일한 수의 쌍별 테스트가 여전히 수행되고 있습니다.바운딩 볼륨을 바운딩 볼륨 계층에 배치함으로써 시간 복잡도(테스트 실행 횟수)를 오브젝트 수로 로그화할 수 있다.그러한 계층 구조를 갖추면 충돌 테스트 중에 자녀 체적이 부모 체적과 교차하지 않으면 자녀 체적을 검사할 필요가 없다(예를 들어 범퍼 차량 두 대의 경계 체적이 교차하지 않으면 범퍼 자체의 경계 체적 자체를 점검할 필요가 없다).
BVH 설계의 문제
경계량의 선택은 두 가지 목표 사이의 균형에 의해 결정된다.한편으로, 매우 심플한 모양의 바운딩 볼륨을 사용하고 싶다고 생각하고 있습니다.따라서 몇 바이트만 저장하면 되며 교차로 테스트와 거리 계산이 간단하고 빠릅니다.한편, 대응하는 데이터 오브젝트에 딱 맞는 경계 볼륨을 원합니다.가장 일반적으로 사용되는 경계 볼륨 중 하나는 축 정렬된 최소 경계 상자입니다.특정 데이터 개체 세트에 대한 축 정렬 최소 경계 상자는 계산하기 쉽고, 몇 바이트의 스토리지만 필요하며, 강력한 교차 테스트도 구현이 쉽고 매우 빠릅니다.
특정 애플리케이션용으로 [1]BVH를 설계할 때 고려해야 할 BVH에는 다음과 같은 몇 가지 바람직한 속성이 있습니다.
- 지정된 서브트리에 포함된 노드는 서로 가까이 있어야 합니다.트리가 아래로 내려갈수록 노드가 서로 더 가까이 있어야 합니다.
- BVH의 각 노드는 최소 볼륨이어야 합니다.
- 모든 경계 볼륨의 합계는 최소여야 합니다.
- BVH 루트 부근의 노드에는 더욱 주의를 기울여야 합니다.트리의 루트 부근의 노드를 플루닝하면 더 이상 검토할 필요가 없습니다.
- 형제 노드의 중첩 볼륨은 최소여야 합니다.
- BVH는 노드 구조와 내용 양쪽에 대해 균형을 이루어야 합니다.밸런싱을 사용하면 브런치를 통과하지 않을 때마다 가능한 한 많은 BVH를 플루닝할 수 있습니다.
BVH의 구조상 BVH를 나타내는 트리에서 어느 정도(자녀 수)와 키를 사용할지 결정해야 한다.키가 작은 나무는 키가 더 커진다.그러면 루트 투 리프 통과 시간이 늘어납니다.한편, 방문한 각 노드에서 자노드의 중복 여부를 확인하기 위해 소비하는 작업은 줄어듭니다.그 반대는 높은 수준의 트리에 적용됩니다. 트리의 높이는 작아지지만 각 노드에서 더 많은 작업이 소요됩니다.실제로는 이항 트리(도 = 2)가 가장 일반적입니다.주요 이유 중 하나는 이진 트리를 [2]구축하기가 더 쉽기 때문입니다.
건설
트리 구성 방식에는 하향식, 상향식 및 삽입 방식의 세 가지 주요 범주가 있습니다.
하향식 메서드는 입력 세트를 두 개 이상의 서브셋으로 분할하여 선택한 경계 볼륨으로 바인드한 다음 각 서브셋이 단일 프리미티브(리프 노드)로만 구성될 때까지 반복적으로 분할(및 바인딩)을 계속합니다.하향식 방법은 구현이 쉽고, 구축이 빠르며, 가장 인기 있는 방법이지만 일반적으로 가능한 최선의 트리가 되는 것은 아닙니다.
보텀업 메서드는 트리의 리프로 설정된 입력에서 시작하여 그 중 2개(또는 그 이상)를 그룹화하여 새로운(내부) 노드를 형성합니다.모든 것이 단일 노드(트리의 루트)로 그룹화될 때까지 동일한 방식으로 진행됩니다.상향식 방법은 구현하기가 더 어렵지만 전반적으로 더 나은 트리를 만들 가능성이 높습니다.최근 일부 연구(예: )에 따르면 저차원 공간에서는 공간 채우기 곡선을 사용하여 객체를 정렬하고 이 순차적 순서에 따라 대략적인 군집을 적용함으로써 시공 속도를 크게 향상시킬 수 있다(상향식 접근 방식과 일치하거나 능가).
하향식 및 상향식 방식은 모두 구축이 시작되기 전에 모든 기본 요소를 사용할 수 있어야 하므로 오프라인 방식으로 간주됩니다.삽입 메서드는 빈 트리에서 시작하여 한 번에 하나의 개체를 삽입하여 트리를 만듭니다.비용 메트릭에 따라 트리가 최대한 적게 커지는 삽입 위치를 선택해야 합니다.삽입 방식은 구축이 시작되기 전에 모든 기본 요소를 사용할 필요가 없으므로 온라인 방식으로 간주됩니다. 따라서 런타임에 업데이트를 수행할 수 있습니다.
사용.
BVH는 현재 광선과 [4]교차하지 않는 경계 볼륨에 위치한 기하학적 객체를 생략하여 장면 내에서 잠재적 교차 후보를 제거하기 위해 광선 추적에 자주 사용됩니다.또한, 일반적인 성능 최적화로서, 광선의 가장 가까운 교차점만 관심 있는 경우, 광선 추적 통과 알고리즘이 하강 노드이고 여러 개의 자 노드가 광선을 교차하는 경우, 통과 알고리즘은 가장 가까운 볼륨을 먼저 고려하며, 교차점을 발견하면 확실히 광선보다 가까운 교차점을 찾습니다.ny 두 번째(또는 다른) 볼륨에서 가능한 교차점(즉, 볼륨이 중복되지 않음)은 두 번째 볼륨을 안전하게 무시할 수 있습니다.두 번째 볼륨의 하위 볼륨으로 하강할 때 BVH 통과 중에 유사한 최적화를 사용하여 추가 검색 공간을 제한하고 통과 시간을 단축할 수 있습니다.
또한, BVH를 위해 많은 전문화된 방법이 개발되었으며, 특히 평행 빌딩, SIMD 가속 횡단, 양호한 분할 휴리스틱(SAH - 표면적 휴리스틱이 광선 추적에 자주 사용됨), 와이드 트리(4-ary 및 16-ary)와 같은 AAB(축 정렬 경계 박스)를 기반으로 하는 방법이 개발되었으며, 나무 구축에 일부 이점이 있다.실제 장면에 대한 성능 쿼리) 및 빠른 구조 업데이트(실시간 애플리케이션 객체가 공간적으로 상대적으로 느리게 이동하거나 변형되거나 정지되어 있을 수 있으며, 동일한 BVH를 처음부터 완전히 재구축하지 않고도 여전히 유효하도록 업데이트할 수 있습니다.)
BVH는 완전한 재구축 없이 오브젝트 삽입 및 삭제를 자연스럽게 지원하지만 그 결과 BVH는 보통 완전한 재구축에 비해 쿼리 성능이 떨어집니다.이러한 문제를 해결하기 위해(및 신속한 구조 갱신이 최적이라고는 할 수 없는) 충분한 변화가 검출된 후(리프 오버랩이 큰 경우, 삽입과 삭제의 수가 문턱값을 넘은 경우 등), 새로운 BVH를 병렬 또는 동기식으로 구축할 수 있습니다.
BVH는 씬 그래프 메서드 및 지오메트리 인스턴싱과 조합하여 메모리 사용량을 줄이고 구조 업데이트 및 완전한 재구축 성능을 향상시키며 객체 또는 원시 분할을 개선할 수 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Ericson, Christer (2005). "§6.1 Hierarchy Design Issues". Real-Time collision detection. Morgan Kaufmann Series in Interactive 3-D Technology. Morgan Kaufmann. pp. 236–7. ISBN 1-55860-732-3.
- ^ 에릭슨 2005, 페이지 238
- ^ Gu, Yan; He, Yong; Fatahalian, Kayvon; Blelloch, Guy (2013). "Efficient BVH Construction via Approximate Agglomerative Clustering" (PDF). HPG '13: Proceedings of the 5th High-Performance Graphics Conference. ACM. pp. 81–88. CiteSeerX 10.1.1.991.3441. doi:10.1145/2492045.2492054. ISBN 9781450321358. S2CID 2585433.
- ^ Günther, J.; Popov, S.; Seidel, H.-P.; Slusallek, P. (2007). "Realtime Ray Tracing on GPU with BVH-based Packet Traversal". 2007 IEEE Symposium on Interactive Ray Tracing. IEEE. pp. 113–8. CiteSeerX 10.1.1.137.6692. doi:10.1109/RT.2007.4342598. ISBN 978-1-4244-1629-5. S2CID 2840180.
