독립적으로 움직이는 작은 개체의 대규모 집단을 실시간으로 렌더링 할 수 있기를 원합니다. 개체가 무리처럼 움직일 수 있지만 상대 위치는 일관되지 않습니다. 위치는 무리 내에서 임의로 변경 될 수 있으며 무리는 어느 시점에서든 해체되고 재구성 될 수 있습니다.
경계 볼륨 계층을 구축하는 방법이이 상황에 가장 적합할까요? 차선책이지만 충분히 좋은 계층 구조를 유지하는 방법은 각 프레임에 부분적인 업데이트 만 필요합니까? 아니면 매 프레임마다 처음부터 계층 구조를 구축 할 수있는 방법이 있습니까? p> 객체의 수가 너무 많아 계층없이 렌더링 할 수 없지만 같은 이유로 계층을 구축하는 데 시간이 많이 걸릴 것으로 예상합니다.
바운딩 볼륨 계층에 초점을 맞추는 것은 잘못된 것이며이 상황에 대한 더 나은 공간 분할 접근 방식이 있습니다. 그에 따라 대답하십시오. 생각하지 못했던 내용을 포함하여 내가 설명하는 내용을 처리 할 수있는 내용을 찾고 있습니다.
댓글
- 의도적으로 제한하고 있습니까? 경계 볼륨 계층에 대한 질문입니까, 아니면 다른 형태의 공간 분할에 개방되어 있습니까?
- @JohnCalsbeek I ' 명확하게 편집했습니다. 부주의 한 제한.
- 떼가 병합 될 때 " 스웜 "을 단일 단위로 취급하는 것을 고려하세요. 외톨이가 멀리 방황하면 하나의 " swarm "이됩니다. 이것은 떼가 응집력이 있고 외로움이 드문 경향이있는 경우 가장 잘 작동합니다. " swarm은 단일 유닛으로 " 회원이있을 때만 떼를 전환 할 수 있도록하는 것과 같은 깔끔한 방법이 많이 있습니다. 서로 접촉하면 목록이 계속 이어집니다.
답변
특히 공간 해싱 사용 고려 개체의 크기가 비슷한 경우
기본적으로 세계를 균일 한 크기의 격자 셀로 나눕니다 (2D 및 3D는 수직 움직임의 양에 따라 모두 유효한 가능성). 업데이트 할 때마다 겹치는 각 저장소에 개체를 할당합니다. 셀이 개체에 비해 적절한 크기 인 경우 대부분의 개체는 단일 저장소에 있어야합니다.
각 저장소는 해시 테이블에 삽입됩니다. 키는 빈의 좌표입니다. (동일한 키에 대해 여러 값이있는 해시 테이블로 생각할 수도 있으며 중첩되는 모든 셀에 대해 한 번씩 개체를 삽입합니다.)
이 체계에는 다시 작성할 계층이 없습니다. 따라서 동적 장면에 적합합니다. 셀의 치수를 절두체에 대해 또는 거친 수준에서 폐색기에 대해 테스트하고 한 번에 많은 오브젝트를 버릴 수 있습니다. 또한이 구조를 점진적으로 관리하는 것이 더 쉽습니다. 해시 테이블을 프레임간에 동일하게 유지하고 개체가 셀 경계를 넘을 때 한 저장소에서 다른 저장소로만 이동할 수 있습니다.
답변
객체가 이동할 때마다 경계를 넘지 않도록 경계 볼륨을 필요한 것보다 약간 크게 만들 수 있습니다. 어쨌든 구조를 지금 다시 빌드해야합니다.
또는이 문제를 정확히 해결하려는 경계 간격 계층 이 있습니다. 시나리오.
또는 Ingo Wald, Solomon Boulos 및 Peter Shirley의 Dynamic Bounding Volume Hierarchies를 사용한 변형 가능한 장면 레이 트레이싱 의 논문은 다음과 같습니다.
답변
여기에 실용적인 관점을 추가하고 싶습니다.
여기에서 제한된 정보에 대해 작업하고 있다는 서문 :
- 방법을 모르겠습니다. 당신이 다루는 모든 물체.
- 당신의 가속 구조가 정확히 무엇에 사용되는지 모르겠습니다. 절두체 컬링? 광선 추적? BVH에서 개체 간의 충돌 감지?
앞으로 몇 천 개의 개체를 컬링하는 절두체에 대해 이야기하고 있다고 가정하겠습니다.
객체 수가 너무 많아 계층없이 렌더링 할 수 없지만 같은 이유로 계층을 구축하는 데 시간이 많이 걸릴 것으로 예상합니다.
BVH를 계산하기 위해 매 프레임마다 모든 객체를 방문해야한다면 BVH없이 직접 컬링하는 것이 실제로 더 빠르다고 주장합니다. 이것은 물론 절두체 컬링 구현에 달려 있습니다. 모든 개체의 경계 볼륨은 메모리에 연속적으로 저장되어야합니다. 결과적으로 CPU 캐시 사용률이 더 효율적이고 SIMD 명령어를 사용하여 추가 최적화가 가능합니다. DICE는이 주제에 대한 전체 프레젠테이션을 제공합니다. 전장 만들기 : 실제 데이터 지향 디자인
프레젠테이션에서는 간단한 그리드를 사용하여 더욱 빠르게 컬링하는 방법에 대해서도 언급합니다.
대부분의 3D / 시뮬레이션 / 게임 코드베이스에는 이미 일종의 BVH 클래스와 저는 최상의 컬링 성능을 얻는 것이 얼마나 중요한지 모르겠습니다. BVH를 고수하기위한 몇 가지 주장을 제시하고 싶습니다.
사용하는 방법에 따라 BVH는 빠르고 간단 할 수 있습니다.
현재 구현 된 바이너리 BVH (각 노드에는 0 개 또는 2 개의 하위 항목 만있을 수 있으며 각 리프 노드는 하나의 항목 만 저장함) 구성은 i7-5960X @ 3.89GHz 의 단일 스레드에서 1137 개 개체에 대해 약 0.18ms가 걸립니다. 더 빠를 수 있다고 확신합니다. 구성은 프로세스에서 메모리를 재할 당하지 않고 수행됩니다 (이는 구성 성능을 두 배로 높임).
SAH가 최상의 BVH를 생성 할 수 있지만 시간이 오래 걸립니다. SAH는 좋습니다. 충돌 메시와 같이 미리 계산할 수있는 작업을 위해 런타임에 충돌 메시를 실시간 생성에 더 적합한 BVH에 넣을 수 있습니다.
빠르고 간단한 BVH 생성 접근 방식 (I “m using currently)은 한 축 (예 : 상위 AABB의 가장 긴 축)의 모든 개체를 정렬하고 컬렉션을 가운데로 분할하는 것입니다.
더 빠르게 작업하려면 노드 AABB를 계산합니다. 트리를 구성한 후 상위 노드의 두 하위 노드 AABB를 결합하여 모든 객체를 반복하지 않습니다 (또 다른 2 배 속도 향상). 그러나 이는 분할 기준이 상위의 AABB에 의존하지 않는 경우에만 가능합니다.