解決圓圈碰撞問題

Question

我正在編寫擴展Circle-Rectangle collision detection (intersection)以包含對碰撞的響應的軟件。圓形邊和圓形矩形相當直接。但是圈子讓我難倒了。

例如，在離散事件模擬中，讓兩個圓形碰撞，一個紅色和一個綠色。我們可能有以下情況：

它們相撞後，我們立即可以有：

這裏RIP和GIP是圓的，在之前的時鐘滴答的位置。在當前的時鐘週期，衝突在RDP和GDP檢測到。然而，當兩個圓圈位於RCP和GCP時，兩個圓圈之間發生衝突。在時鐘刻度上，紅色圓圈向右移動RVy並向右移動RVx;綠色圓圈向下移動GVy，向左移動GVx。 RVy不等於GVy; RVx也不等於GVx。

相撞當圓中心間的距離小於或等於該圈子半徑之和時，也就是，前面的圖中，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，在線Siggraph大會'97課程筆記，特別重要的是幻燈片剛體模擬。

你將不得不接受一些近似 - 貝克曼的視頻，即使是很簡單的情況下，是不可能的分析預測會發生什麼證明，這是更糟糕，因爲你是模擬具有分立步驟的連續系統。

Answer 2

「這就是問題所在：我該如何做出這個舉動。」

您很可能想知道如何「在調整圓的速度分量之前將DP定位回CP」。

因此，如何確定CP（發生碰撞的位置）以及如何調整從該點開始的圓圈運動有兩個問題。第一部分有一個相當簡單的解決方案（允許不同的半徑和速度分量），但第二部分取決於彈性或非彈性響應是否建模。在你寫的評論中：

碰撞將被建模爲彈性。用於交換慣性的數學計算已經就緒。問題是在哪裏定位圈子。

鑑於我只想解決第一個問題，解決碰撞發生的確切位置。假定兩個圓的均勻運動，知道發生碰撞的確切時間就足夠了，即圓的中心之間的距離等於它們的半徑的總和。

通過勻速運動，可以通過從另一個圓圈（綠色）減去一個圓圈（紅色）的速度，將一個圓圈（紅色）視爲靜止。實際上，我們將第一個圓的中心視爲固定，並且只考慮第二個圓進入（均勻）運動。

現在通過求解一個二次方程得到確切的碰撞時間。假設V =（GVx-RVx，GVy-RVy）是圓的相對運動，並且令P =（GIPx-RIPx，GIPy-RIPy）在碰撞之前的「瞬時」中它們的相對位置。我們通過定義「動畫」爲相對位置P的直線路徑：

P（T）= P + T * V

，並要求當該直線相交周圍半徑RR +的Gr的原點的圓，則不執行時：

（PX + T * Vx的）^ 2 +（PY + T * VY）^ 2 =（RR + GR）^ 2

這是未知的時間t的二次方程，所有其他數量都是已知的。情況是這樣的（碰撞發生在位置CP之前或之前）會出現一個積極的實際解決方案（通常有兩個解決方案，一個在CP之前，另一個在後，但可能是放牧接觸給出「雙根」）。你想要的解決方案（根）是較早的解決方案，其中t（在「即時」RIP，GIP位置處爲零）較小。

Answer 3

給定初始位置和速度矢量，實際上可以得到達到碰撞所需時間的表達式。

打電話給你的對象A和B，並說他們有位置向量一個和b和速度矢量ü分別和v。比方說，以每時間步ü單元的速率A移動（因此，在時間= t時，A是在一個;在時間= t + 1的，A是在一個 + Ú）。

我不確定是否要查看派生;它看起來不那麼好......我對LaTeX的瞭解相當有限。 （如果你確實需要我，我可以在以後編輯它）。不過，現在，使用泛型C＃-ish語法，使用聲明Vector2（X，Y）的Vector2類型，並且具有向量加法，標量乘法，點乘積和長度的函數。

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的負值。如果物體在不平行的路徑上，但永遠不會相遇（相互傳遞），則在平方根內會得到負值。拋棄平方根項，你會得到最接近的時間。如果它們以相同的速度平行移動，則分母中的值爲零，而t的值爲未定義的值。

那麼，希望這是有幫助的！我遇到了和你一樣的問題，並決定看看我是否可以在紙上寫出來。

編輯：我應該更仔細地發佈這個...公式的混亂之前閱讀以前的答覆上面確實是解決這一hardmath描述的二次方程。道歉的冗餘職位。

Answer 4

要重新定位兩個重疊的圓以恆定的速度，您需要做的就是找出碰撞發生的時間，並將它們的速度因子添加到它們的位置。

首先，我們將考慮一個半徑與相對位置和速度相結合的圓，而不是兩個圓的移動。讓輸入圓的位置爲P1和P2，速度爲V1和V2，半徑爲r1和r2。讓組合圓的位置爲P = P2 - P1，速度爲V = V2 - V1，半徑爲r = r1 + r2。

我們必須找到在該圓穿過原點，換句話說發現t爲其r = |P + tV|值的時間。應該有0,1或2個值，具體取決於圓不通過原點，飛行與其相切，還是飛過它。

r^2 = ||P + tV||通過平方雙方。

r^2 = (P + tV)*(P + tV) = t^2 V*V + 2tP*V + P*P使用L2範數相當於向量與其自身的點積，然後分佈點積的事實。

t^2 V*V + 2tP*V + P*P - r^2 = 0把它變成一個二次方程。

如果沒有解決方案，則判別式b^2 - 4ac將爲負數。如果它爲零或正數，那麼我們對第一個解決方案感興趣，因此我們將減去該判別式。

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

因此t是碰撞時間。