오브젝트 간의 효율적인 충돌 감지를위한 최상의 알고리즘

Question

혼란 스럽습니다. 혼란스럽지 않고, 6 가지 테스트 프로그램을 사용하여 어떤 알고리즘이 가장 적합한 지 알기를 원하지 않습니다. 그래서 나는 내 경험이주는 혜택을주기 위해 여기에있는 나의 전문가 친구에게 물어볼 줄 알았다.

시나리오는 내부에있는 객체의 크기에 비해 상당히 넓은 영역이있는 3D 장면입니다. 장면에는 수천 개의 객체가있을 수 있습니다. 객체의 크기는 단위의 10 분의 1에서 최대 약 10 단위까지 다양하지만 크지는 않습니다. 개체는 함께 클러스터되는 경향이 있지만 이러한 클러스터는 장면의 어느 곳에서나 나타날 수 있습니다. 모든 객체는 동적이며 움직입니다. 클러스터는 함께 움직이는 경향이 있지만, 속도가 항상 동일하지는 않습니다. 또한 고려해야 할 정적 형상이 있습니다. 많은 수의 동적 객체가 있지만 장면에 정적 객체도 있습니다 (정적 객체는 동적 객체보다 한 두 자릿수 큰 경향이 있습니다).

이제 장면의 모든 항목에 대해 효율적으로 충돌 감지를 수행하기위한 공간 데이터 구조가 필요합니다. 알고리즘이 렌더링 파이프 라인에 대해서도 가시성 쿼리를 지원하면 좋을 것입니다. 단순화를 위해, 여기서 충돌 검출은 광역 위상 (즉, 모든 동적 객체는 단지 완벽한 구체 임)이라고 가정한다.

(1) 옥트리 (2) 느슨한 옥트리 (3) 선형 옥트리 (+ 느슨한) (4) KD 트리 (5) BSP :

그래서, 내 연구에 나는 중 하나를 사용할 수 있습니다 트리 (6) 해싱

지금까지 (6) 내가 시도한 유일한 것입니다. 장면의 오브젝트가 균등하게 퍼져 나간다면 실제로는 속도 측면에서 볼 때 매우 뛰어납니다 (시스템에서 1ms 미만의 충돌을 8192 건 체크 인했습니다). 만약 모든 물체가 더 작은 영역으로 뭉치면 좋은 알고리즘은 아닙니다.

누구나 사용할 수있는 통찰력이 있습니까? 아니면 속임수를 쓸 수있는 방법이 있습니까? 어떤 일이 생기더라도 정적 지오메트리에 대해 별도의 BSP 트리를 사용할 수 있다고 생각합니다. 저는 역동적 인 "구체"가 제가 여기에서 가장 염려하는 것 같다고 생각합니다. 참고 : CUDA 없음, 이것은 CPU 전용입니다 : p.

감사

편집 : 좋아, 플로리스 덕분에, 나는 AABB 나무에 대한 자세한 정보를 발견했다. GameDev에 대한 토론은 여기 http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/입니다. 좋은 타협처럼 보입니다.

최종 수정 : 바퀴를 재발 명하지 않기로 결정했습니다. 총알 물리학 라이브러리가이 모든 작업을 수행 할 수 있습니다 (AABB 트리가 포함되어 있으며, 아마도 잘 최적화되어있을 수도 있습니다).

Answer 1

위대한 질문입니다.객체 주위에

나쁜에게 이동 완전한 충돌 감지 단계

업데이트의 오버 헤드/데이터 구조를 유지

1. 속도 :

   당신은 기본적으로 복잡한 트레이드 오프 사이가 뉴스는 이것 때문에 "완벽한"대답이 없다는 것입니다 - 그것은 당신의 상황에 고유 한 많은 다른 요소들에 진정으로 의존 할 것입니다. 예를 들어, BSP는 1. 정적 평면 기하학을 많이 사용하여 사전 계산 된 경우 블리 스터링 속도가 빠릅니다. 이는 초기 FPS 게임에서 왜 그렇게 널리 퍼 졌는지 설명합니다.

   제 개인적인 추측은 적절한 수준의 개체 (5-10?)가있는 느슨한 AABB (Axis Aligned Bounding Box) 트리가 각 하위 수준 경계 상자에서 가장 잘 작동한다는 것입니다. 이유 :

   • 개체 클러스터에는 상당히 넓거나 스파 스 공간이 있습니다. AABB 나무는 당신이 그렇지 않으면 필요로 할 수준을 많이 잘라 버릴 수 있기 때문에 이것을 위해 좋은 경향이 있습니다.
   • 당신은 완벽한 구체를 추측하고 있습니다. Sphere to Sphere 충돌 테스트는 매우 저렴하므로 각 최하위 레벨 노드마다 10-45 개의 테스트를 쉽게 수행 할 수 있습니다. 기본적으로 N^2는 N의 작은 값에 대해서는 괜찮습니다 .-
   • 축 정렬은 트리를 훨씬 간단하게 업데이트하고 교차 테스트는 대부분의 대안보다 훨씬 저렴합니다. 당신이 대략 구형의 객체를 가정하고 있기 때문에, 당신이 지향 경계 상자 (당신이 재미있는 각도에서 길고 얇은 모양을 많이 가지고있는 경우에만 당신에게 이점을 줄 것입니다)로부터 많은 것을 얻지 못할 것이라고 생각합니다.
   • 테두리 상자를 느슨하게하고 합리적인 수의 개체가 포함되도록하면 개별 개체의 동작이 AABB 범위를 벗어나는 경우가 줄어 듭니다. 이 경우가 아니면 트리를 업데이트 할 필요가 없습니다. 이렇게하면 트리를 많이 업데이트하는 시간을 절약 할 수 있습니다. 그런 일이 생기면 약간의 여백을두고 경계를 확장하여 다음 프레임을 즉시 다시 확장 할 필요가 없습니다. 대부분의 동작이 몇 프레임 동안 같은 방향으로 계속되는 경향이 있습니다!

   약간 울퉁불퉁 한 답변을 드려 죄송합니다.하지만이 아이디어를 통해 유용한 아이디어를 얻을 수 있기를 바랍니다.

Answer 2

많은 물리 엔진은 AABBTree (축 정렬 경계 상자 트리)를 사용하여 객체를 작고 작은 조각으로 세분화합니다. 이 알고리즘을 사용하면 아주 좋은 충돌 탐지를 얻을 수 있습니다. 이 나무는 Octree와 다소 비슷합니다.

OOBBTree (Orientated Bounding Box)는 더 좋은 카운터 파트입니다.