효율성을 높이려면 매우 저렴한 경계 상자 확인을 사용하여 대상 장치 근처에 있지 않은 “장치”의 99 %를 사소하게 거부하십시오. 그리고 데이터를 공간적으로 구성하지 않고도이 작업을 수행 할 수 있기를 바랍니다. 따라서 모든 단위가 플랫 데이터 구조에 저장되어 있으면 처음부터 끝까지 레이스를 시도하고 먼저 관심 단위의 경계 상자 외부에있는 현재 단위를 확인하십시오.

“가까운”것으로 간주되지 않는 항목을 안전하게 거부 할 수 있도록 관심있는 단위에 대해 대형 경계 상자를 정의하십시오. 바운딩 박스에서 제외 검사는 반경 검사보다 저렴할 수 있습니다. 그러나 이것이 테스트 된 일부 시스템에서는 그렇지 않은 것으로 밝혀졌습니다. 두 사람은 거의 똑같이 수행합니다. 이것은 아래의 많은 토론 후에 편집되었습니다.

첫째 : 2D 경계 상자 클립.

// returns true if the circle supplied is completely OUTSIDE the bounding box, rectClip
bool canTrivialRejectCircle(Vertex2D& vCentre, WorldUnit radius, Rect& rectClip) {
  if (vCentre.x + radius < rectClip.l ||
    vCentre.x - radius > rectClip.r ||
    vCentre.y + radius < rectClip.b ||
    vCentre.y - radius > rectClip.t)
    return true;
  else
    return false;
}

다음과 같은 것과 비교 (3D) :

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  D3DVECTOR relPos = obj1->prPosition - obj2->prPosition;
  float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
  float minDist = obj1->fRadius + obj2->fRadius;
  return dist <= minDist * minDist;
}.

객체가 사소하게 거부되지 않으면 더 비싸고 정확한 충돌 테스트를 수행합니다. 그러나 당신은 단지 근접성을 찾고 있기 때문에 구면 테스트는 그에 적합하지만 사소한 거부에서 살아남은 1 %의 물체에만 적합합니다.

이 기사는 사소한 거부에 대한 상자를 지원합니다.
http://www.h3xed.com/programming/bounding-box-vs-bounding-circle-collision-detection-performance-as3

이 선형 접근 방식으로 필요한 성능을 얻지 못하면 다른 포스터가 말한 것처럼 계층 적 데이터 구조가 필요할 수 있습니다. R- 트리는 고려할 가치가 있습니다. 동적 변경을 지원합니다. 그들은 공간 세계의 BTrees입니다.

나는 당신이 그것을 피할 수 있다면 그러한 복잡성을 도입하는 모든 어려움에 당신이 가기를 원하지 않았습니다. 또한 객체가 초당 여러 번 움직일 때이 복잡한 데이터를 최신 상태로 유지하는 비용은 어떻습니까?

그리드는 한 수준의 심층 공간 데이터 구조입니다. 이 제한은 실제로 확장 할 수 없음을 의미합니다. 세계의 크기가 커짐에 따라 포함해야하는 셀의 수도 커집니다. 결국 해당 셀 수 자체는 성능 문제가됩니다. 그러나 특정 크기의 세계에서는 공간 분할이 아닌 성능을 크게 향상시킬 수 있습니다.

답변