많은 움직이는 물체 (구, 삼각형, 상자, 점 등)를 다루는 데 가장 좋은 데이터 구조가 무엇일까 궁금합니다. Nearest Neighbor 및 Collsion 탐지에 대한 두 가지 질문에 대답하려고합니다.움직이는 물체를위한 공간 데이터 구조?
전통적으로 R 트리와 같은 데이터 구조가 가장 가까운 이웃 쿼리에 사용되고 Oct/Kd/BSP가 정적 객체를 다루는 충돌 탐지 문제 또는 아주 적은 수의 움직이는 객체에 사용된다는 것을 알고 있습니다.
나는 거기에 뭔가가 더 있다는 것을 기대하고 있습니다.
모든 도움에 감사드립니다.
경계 구체는 아마도 많은 움직이는 물체에서 도움이 될 것입니다. 개체의 반경 제곱을 계산하고 중심에서 추적합니다. 두 객체의 중심 사이의 제곱 거리가 두 객체의 제곱 반경의 합보다 작은 경우 충돌 가능성이 있습니다. 모든 것은 제곱 된 거리로 수행됩니다. 제곱근이 없습니다.
개체 사이의 최소 제곱 거리로 가장 가까운 이웃을 정렬 할 수 있습니다. 물론 충돌 감지는 복잡해질 수 있으며 구형이 아닌 오브젝트의 경우 Bounding Spheres가 반드시 충돌 정보를 얻지는 않지만 충돌을 비교할 때 필요한 개체 트리를 정리할 수 있습니다.
물론 개체의 중심을 추적해야합니다. 이상적으로는 각 오브젝트가 고정 된 구 크기를 다시 계산하지 않아도되기를 원합니다. (특히 재 계산이 특히 어렵지는 않습니다. 특히 각 오브젝트의 경계 영역이 구형 인 트리를 사용하는 경우) 비 강체이지만 복잡 해짐).
기본적으로 데이터 구조에 대한 질문에 대답하기 위해 모든 객체를 마스터 배열에 보관할 수 있습니다. 나는 당신이 직교 좌표를 기반으로 객체를 빠르게 정렬 할 수있는 마스터 배열의 객체에 대한 참조로 구성된 "영역"배열을 가질 것입니다. "영역"배열은 마스터 오브젝트 배열에서 가장 큰 오브젝트 반경의 2 배 이상으로 정의 된 겹침을 가져야합니다 (가능한 경우 객체 경계 구형 대 오브젝트 수는 분명히 나타납니다)
1 회 한 지역 내의 모든 물체의 거리를 서로 비교하여 빠른 충돌 테스트를 수행 할 수 있으며, 다시 말하면 영역 정의가 중요 해지는 곳입니다. 그러나 거리 비교가 간단한 빼기 (및 abs() 연산)로 내려 오기 때문에 조금 더 간단합니다.
물론 비 구형 (non-spherical)의 실제 충돌 감지를 수행해야합니다. 객체가 될 수 있으며 non-t 일 수 있습니다. 그러나 그 시점에서 잠재적 인 비교의 수를 극적으로 줄였습니다.
기본적으로 2 계층 시스템입니다. 첫 번째는 영역 배열이므로 장면에서 거친 정렬을 수행합니다. 둘째, 지역 내 거리 비교가 가능합니다. 충돌 한 객체에 대한 기본 충돌 감지 및 충돌 플래그 지정을 수행 할 것입니다.
다이내믹 영역 결정에서 트리를 사용하여 영역 크기가 균일 해 지도록 영역의 크기가 너무 좁아서 "붐비는"영역이 너무 빠르게 생성되지 않도록하려면 알고리즘의 여지가있을 것입니다. 그 종류의 것은, 그러나, 사소한 것입니다. 왜냐하면 다른 크기의 물체들로, 밀도에 대한 당신의 정렬이 복잡해지기 때문입니다.
충돌 감지를 수행하는 흥미로운 방법 중 하나는 특별한 팔진 트리 구조로 구성된 축 정렬 경계 상자 (AABB 's)를 사용하는 것입니다. AABB는 최대 6 번의 비교 만 수행하면되기 때문에 거친 충돌 계산을 매우 빠르게 수행하므로 도움이됩니다.
는 옥트리 구조를 사용해야 트릭의 몇 가지가 있습니다
1) 노드가 (정상 옥트리에 대한 위치를 옥트리 파티션 것보다 두 배 커야한다 차지하는 경계 영역 공간이 겹치지 않음). 각 노드는 인접한 노드의 영역의 절반과 겹쳐 야합니다. AABB는 하나의 노드에만 속할 수 있기 때문에이 여분의 크기와 겹침은 더 긴 시간 동안 하나의 노드에 남아있게합니다.
2) 또한 각 노드 및 계층 구조의 각 수준에서 노드의 인접 노드에 대한 링크를 유지합니다. 여기에는 많은 추가 코드가 필요하지만 O (2logn) 시간보다는 O (1) 시간 가까이에 노드간에 요소를 이동할 수 있습니다.
옥트리가 너무 많은 메모리를 차지하면 스파 스 옥트리 구조를 사용하도록 변경할 수 있습니다. 실제로 엔티티가 포함 된 게임 세계의 부분 만 트리를 유지합니다. 그러나 엔티티가 세계를 이동할 때 각 프레임에 대해 더 많은 계산을 수행해야한다는 것을 의미합니다.
octree 대신 시도해 볼만한 다른 아이디어로는 kd-tree (올바른 이름이라고 생각합니다)를 사용하거나 AABB를 사용하여 구조를 아래에서 위로 빌드하는 것입니다.
KD 나무 (메모리에서)는 축 방향으로 정렬 된 평면을 사용하여 공간을 분할하므로 AABB와 함께 사용하기에 적합합니다.
다른 생각은 위에서 아래로부터 옥트리 생성을 강요하는 대신에 (전체 세계를 불러내는 상자로 시작하는 것) 기본 구성 요소에서 빌드하고 가장 큰 것이 전체를 포함 할 때까지 커지는 AABB를 구성합니다 세계. 나는 그것이 빠르게 움직이는 많은 엔티티와 어떻게 작동하는지 확신 할 수 없지만.
(나는 공간 게임 개발 코딩 이런 종류의 일을 한 이후 잠시되었습니다.)
당신은 옥트리에서 장면을 분할하고 장면 일관성을 활용할 수 있습니다. 테스트중인 이동 객체는 속도에 따라 특정 양의 프레임에 대해 트리의 특정 노드에있게됩니다. 즉, 노드에 있다고 가정 할 수 있으므로 노드에없는 많은 오브젝트를 빠르게 잘라낼 수 있습니다. 물론 까다로운 점은 개체가 파티션의 가장자리에 가까울 때 개체가있는 노드를 업데이트해야한다는 것입니다.
움직이는 개체는 방향과 속도를 가지고 있습니다. 객체의 이동 방향에서 수직 분할을 사용하여 두 섹션으로 장면을 쉽게 나눌 수 있습니다. 이 부문의 반대편에있는 객체는 검사 할 필요가 없습니다. 물론 다른 물체의 속도를 보상합니다. 따라서 다른 대상이 천천히 느리다면 추가 검사에서 쉽게 잘라낼 수 있습니다.
테스트 할 모양을 축 정렬 경계 상자와 같은 것으로 항상 단순화하십시오. 초기 충돌 테스트
오브젝트와 다른 이동 오브젝트 사이의 거리와 속도를 더할 수 있습니다. 다른 움직이는 물체가 더 빠른 속도로 동일한 일반 방향으로 움직이는 경우 수표에서 물체를 제거 할 수 있습니다.
개체의 모양에 따라 다른 많은 최적화가 있습니다. 원이나 사각형 또는보다 복잡한 도형에는 모두 이동 중에 수행 할 수있는 특정 최적화가 있습니다.
일부 개체가 멈추거나 움직일 수없는 것으로 가정하면 중지되는 개체를 추적 할 수 있습니다. 이러한 객체는 정적 객체처럼 취급 될 수 있으므로 검사가 빠르며 정적 최적화 기술을 모두 적용 할 수 있습니다.
나는 더 잘 알고 있지만 내 머리 꼭대기에서 생각할 수는 없다. 한동안이 작업을하지 않았습니다.
물론 이것은 충돌 감지를 수행하는 방법에 따라 다릅니다. 속도에 따라 점차적으로 객체의 위치를 업데이트하고 정적 인 것처럼 검사합니다. 또는 모양을 돌출시키고 초기 충돌 지점을 계산하여 속도를 보정하고 있습니까? 전자는 빠르게 움직이는 물체에 작은 단계가 필요합니다. 후자는 더 복잡하고 비용이 많이 들지만 더 나은 결과를 제공합니다. 또한 회전하는 객체를 가지게되면 상황이 좀 더 까다로워집니다.
청소 및
RDC이 객체가 스파 스 (많은되지 교차로) 특히 경우 유용 할 수 있습니다 다양한 상 + GJK 좁은 상 치기.
영역을 사용하면 충돌 테스트가 조금 더 빨라지고 영역 분할 영역을 사용하면 비교할 수있는 양은 제한되지만이 "영역"을 다시 계산해야한다는 것을 알고 있습니다.이 속도는 느립니까? 빠르게 "영역"을 업데이트 할 수있는 데이터 구조를 찾고 있습니다. – esiegel