원 - 서클 충돌 해결

Question

Circle-Rectangle collision detection (intersection)을 확장하는 소프트웨어를 작성하여 충돌에 대한 응답을 포함합니다. 원 - 가장자리와 원 - 직사각형은 다소 단순합니다. 그러나 원 - 서클은 나를 곤혹스럽게 만들었다.

예를 들어 이산 이벤트 시뮬레이션에서 두 개의 원이 빨간색과 녹색으로 충돌하게합니다.

들이 충돌 직후 우리가 할 수 : 우리는 다음과 같은 상황이있을 수 있습니다 여기에

가 RIP 및 GIP는 이전의 클럭 틱에서 원의 위치했다. 현재 시계 틱에서 충돌은 RDP와 GDP에서 감지됩니다. 그러나 두 개의 원이 RCP와 GCP에있을 때 시계 틱간에 충돌이 발생했습니다. 시계 틱에서 빨간색 원은 RVy를 아래쪽으로, RVx는 오른쪽으로 이동합니다. 녹색 원이 GVy를 아래쪽으로, GVx가 왼쪽으로 이동합니다. RVy는 GVy와 동일하지 않습니다. RVx는 GVx와 동일하지 않습니다. 원호 중심 사이의 거리가 원 '반경의 합보다 작거나 같은 경우

충돌이 발생, 즉 위의 그림에서,이고, D < = RR (+ 할머니). d < (Rr + Gr)의 충돌이 발생하면 서클의 속도 구성 요소를 조정하기 전에 DP를 CP에 다시 배치해야합니다. d == (Rr + Gr)의 경우 DP가 CP에 있기 때문에 재 위치 지정이 필요하지 않습니다.

다음은 문제입니다. CP로 이동하려면 어떻게해야합니까? 일부 저자는 다음 그림에서 p로 주어진 침투의 절반이 적용될 것을 제안했습니다.

은 나에게 그건 그냥 일반 잘못되었습니다. 두 개의 원의 속도 벡터가 같다고 가정합니다.이 예제에서는 그렇지 않습니다. 나는 침투가 계산과 관련이 있다고 생각하지만, 어떻게하면 나를 피할 수 있을지 생각합니다. 나는이 문제가 Gcdy와 GCdx를 풀기를 원하는 비슷한 삼각형의 문제로 재 작성 될 수 있다는 것을 알고있다.

충돌

자체 탄성으로 모델링되고, 관성 교환 수학 제자리에 이미. 유일한 문제는 충돌시 원을 배치하는 위치입니다.

Answer 1

원형 물체의 비탄성 충돌에 대한 기본 참조를 찾고있는 경우 Joe van den Heuvel 및 Miles Jackson의 Pool Hall Lessons: Fast, Accurate Collision Detection Between Circles or Spheres은 매우 쉽게 따라 할 수 있습니다.

가장 공식적인 것에서 가장 공식적인 것까지, 질문에 대한 해결책을 뒷받침하는 프로그래밍 (충돌 대응)을 구현하는 기술에 대한 후속 참조가 있습니다.

• 브라이언 베크 & 찰스 토레 The Physics in Games - Real-Time Simulation Explained
• 크리스 헤커 Physics, Part 3: Collision Response, 게임 개발자 1997
• 데이비드 Baraff, Physically Based Modeling: Principles and Practice, 강체 시뮬레이션 슬라이드입니다 특히 관련성이 온라인 시그라프 97 코스 노트.당신은 약간의 근사치에 동의 할 겁니다

- 베크도 매우 간단 경우에, 해석 무엇이 일어날 지 예측할 수없는 비디오에서 보여, 이것은 당신이 시뮬레이션하기 때문에 더 악화입니다 이산 단계가있는 연속 시스템.

Answer 2

"문제는 다음과 같습니다. 어떻게 이동합니까?"

서클의 속도 구성 요소를 조정하기 전에 DP를 CP에 다시 배치하는 방법을 알고 싶을 것입니다.

따라서 충돌을 일으키는 CP를 결정하는 방법과 그 지점에서 앞으로 진행하는 원의 동작을 조정하는 방법이라는 두 가지 문제가 있습니다. 첫 번째 부분은 다른 반경 및 속도 구성 요소를 허용하는 다소 쉬운 솔루션이지만, 두 번째 부분은 탄성 응답 또는 비탄성 응답의 모델링 여부에 따라 달라집니다. 당신이 쓰는 코멘트 :

충돌은 탄성으로 모델링됩니다. 관성 교환을위한 수학은 입니다. 문제는 서클을 배치하는 위치입니다.

나는 첫 번째 문제 만 해결할 것이며, 충돌이 발생한 정확한 위치를 해결할 것입니다. 두 동그라미의 균일 한 움직임을 가정하면, 충돌이 일어나는 정확한 시간, 즉 원의 중심 사이의 거리가 그들의 반경의 합과 같은 시간을 알면 충분하다.

균일 한 동작으로 다른 원 (녹색)의 속도에서 해당 속도를 뺀 움직임없이 하나의 원 (빨간색)을 처리 할 수 ​​있습니다. 실제로 우리는 첫 번째 원의 중심을 고정 된 것으로 취급하고 두 번째 원만이 (균일 한) 모션으로 간주합니다.

이제 충돌의 정확한 시간은 2 차 방정식을 풀어서 알 수 있습니다. 충돌 전에 V = (GVx-RVx, GVy-RVy)를 원의 상대 운동이라고하고, P = (GIPx-RIPx, GIPy-RIPy) 상대 위치를 "순간"으로 보자. 우리는 정의하여 상대 위치 P에 대한 직선 경로 "애니메이션"

P (t)를 = P + t의 *의 V

이 직선 반경 Rr의 + 할머니의 원점 주위의 원을 교차 할 때 요구 또는 않는다 :

(PX + t * 내지 Vx)^2 + ((Py)를 +의 t * VY)^2 = RR (+ 할머니)^2

이 알려지지 시간 t의 차 방정식이고, 다른 모든 양은 알려지고있다. 상황은 (위치 CP에서 또는 그 이전에 충돌이 발생하여) 긍정적 인 실제 해결책이 존재할 것입니다 (일반적으로 두 가지 해결책, 하나는 CP 이전에, 다른 하나는 후발이지만 두 번 뿌리를 내릴 수 있습니다). 원하는 솔루션 (루트) t는 이전의 것인데, t ("즉시"RIP, GIP 위치에서 0 임)가 더 작습니다.

Answer 3

초기 위치와 속도 벡터가 주어지면 실제로 충돌에 도달하는 데 필요한 시간에 대한 식을 유도 할 수 있습니다.

호출하여 객체 A와 B, 그리고 그들이 위치 및 B을 벡터와 속도 벡터 각각 U 및 v,이 말한다.이제 시간 단계마다 U 단위의 속도로 이동하는 것을 생각한 (따라서 한번에 = t가, A가 에있다; 시간 =의 t + 1에서, A는 에서 U + 인)를.

파생물을보고 싶은지 확실하지 않습니다. 그것은 너무 좋아 보이지 않을 것입니다 ... LaTeX에 대한 나의 지식은 꽤 제한되어 있습니다. (나를 원한다면 나중에 편집 할 수 있습니다.) 지금은 여기에 Vector2 (X, Y)로 선언되고 벡터 추가, 스칼라 곱셈, 내적 곱, 길이 함수가있는 Vector2 형식의 구문을 사용하여 일반 C# 구문을 사용하고 있습니다. 충돌에 응답으로

double timeToCollision(Vector2 a, Vector2 b, Vector2 u, Vector2 v) 
{ 
    // w is the vector connecting their centers; 
    // z is normal to w and equal in length. 
    Vector2 w = b - a; 
    Vector2 z = new Vector2(-1 * w.Y, w.X); 
    Vector2 s = u - v; 
    // Dot() represents the dot product. 
    double m = Dot(z, s)/Dot(w, s); 

    double t = w.Length()/Dot(w, s) * 
       (w.Length() - sqrt(((2 * r)^2) * (1 + m^2) - (m * w.Length())^2))/
       (1 + m * m) 

    return t; 
} 

: 당신이 빨리 감기를 할 수 있는지 충격의 지점으로, 당신은 교차 원 처리에 대해 걱정할 필요가 없습니다.

관심이 있으시면 은이 충돌하지 않는 멋진 결과를 제공합니다. 두 물체가 서로 멀어 지지만 속도가 반전 된 상태에서 충돌 한 경우 t 값이 음수가됩니다. 객체가 평행하지 않지만 만나는 적이없는 (서로 지나가는) 경로에 있으면 제곱근 내에 음수 값을 갖게됩니다. 제곱근 항을 없애면 서로가 가장 가까운 시간을 갖게됩니다. 그리고 그들이 같은 속도로 평행 이동한다면, 분모에서 0이되고 t에 대해 정의되지 않은 값이 생깁니다.

글쎄, 잘하면이 도움이되었다! 당신과 같은 문제가 생겨서 종이에서 해결할 수 있는지 알아보기로 결정했습니다.

편집 : 나는 위의 사실 설명 hardmath 차 방정식의 해결책이 ... 공식의 엉망이 게시하기 전에 더주의 깊게 이전 응답을 읽을 수 있어야합니다. 중복 게시물에 대해 사과드립니다.

Answer 4

두 개의 겹치는 원을 일정한 속도로 다시 배치하려면 충돌이 발생한 시간을 찾아 속도에 해당하는 요소를 해당 위치에 추가하기 만하면됩니다.

먼저 두 개의 원이 움직이는 대신 반경과 상대 위치와 속도가 결합 된 하나의 원을 고려할 것입니다. 입력 원이 P1 및 P2, 속도가 V1 및 V2이고 반지름이 r1 및 r2 인 것으로 가정합니다. 결합 된 원의 위치는 P = P2 - P1이고 속도는 V = V2 - V1이며 반경은 r = r1 + r2입니다.

우리는 다른 단어 r = |P + tV|에 대한 t의 가치를 찾을 수있는 원이 원점을 통과하는 시간을 찾을 수있다. 원이 원점을 통과하지 않거나 원점을 통과하지 않거나 원을 통과하는지 여부에 따라 0, 1 또는 2 값이 있어야합니다.

r^2 = ||P + tV|| 양쪽에 제곱하여. L2- 놈이 벡터 자체의 내적과 동등하다는 사실을 이용하여 내적을 분배하는 것을 이용하여, L2- 놈이된다.

t^2 V*V + 2tP*V + P*P - r^2 = 0 2 차 방정식으로 바꾼다.어떤 솔루션이없는 경우

, 다음 판별 b^2 - 4ac는 음수가 될 것입니다. 그것이 0 또는 양수이면, 우리는 첫 번째 해에 관심을 가지고 있으므로 판별자를 뺍니다.

a = V*V 
b = 2 P*V 
c = P*P - r^2 
t = (-b - sqrt(b^2 - 4ac))/(2a) 

그래서 t는 충돌시입니다.