連續物理引擎的碰撞檢測技術

Question

我正在研究純粹連續的物理引擎，我需要選擇廣義和窄相碰撞檢測的算法。 「純連續」意味着我從不進行交叉測試，而是希望找到在發生碰撞之前捕捉每次碰撞的方法，並將其分別放入由TOI定購的「計劃碰撞」堆棧中。

廣泛的階段 我能想到的唯一連續的廣義相位方法是將每個身體包圍在一個圓圈中，並測試每個圓圈是否會與另一個圓圈重疊。這看起來非常低效，而且沒有任何撲殺。

我不知道今天的離散碰撞剔除方法如四叉樹可能存在哪些連續類似物。 如何防止不合適的和毫無意義的廣泛測試，例如分立式引擎呢？

精細階段
我已經成功地在狹窄的SAT適應連續檢查，而不是離散的，但我敢肯定，在報紙或你們可能會遇到網站還有其他更好的算法在那裏。
什麼樣的快速或準確的算法，你建議我使用什麼是每個優點/缺點？

最後請注意：
我說技術而不是算法，因爲我還沒有決定如何，我會存儲不同的多邊形，這可能是凹面，凸面，圓形，甚至有洞。我打算根據算法的要求做出決定（例如，如果我選擇將多邊形分解爲三角形或凸形的算法，我將簡單地以這種形式存儲多邊形數據）。

Answer 1

你說過圓圈，所以我假設你有2D對象。您可以通過添加時間維度將2D對象（或其邊界形狀）擴展爲3D，然後可以使用常規技術來檢查一組3D對象之間的靜態碰撞。例如，如果在（x，y）中有一個以恆定速度向右（+ x）​​移動的圓，那麼當用時間維擴展它時，在（x，y）中有一個對角圓柱體， y，t）。通過在這些3D對象之間進行交集（將時間視爲z），可以看到兩個對象是否會相交。如果P點是一個交點，那麼只要看P.t.就知道該交點的時間。

這也推廣到更高維度，雖然數學變得很難（對我來說）。

如果對象具有複雜路徑，碰撞檢測可能會非常棘手。例如，如果您的圓圈受重力影響，則擠出的時空物體是拋物線球體而不是簡單的圓柱體。您可以稍微填充邊界對象並在較短的時間段內使用線性逼近並迭代，但我不確定這是否違反了連續的意思。

Answer 2

我打算假設你想在你的模擬中使用重力或其他保守力量。如果是這樣的話，你的物體的軌跡很可能不會成爲線條，在這種情況下，就像阿德里安指出的那樣，數學會更難。我想不出一種避免檢查所有可能的碰撞曲線組合的方法，但只要兩者都是線性系統的解決方案（或者一般情況下，如果您有的話），您可以輕鬆計算兩條曲線之間的最小距離曲線的封閉形式解決方案）。如果你知道x1(t) = f(t)和x2(t) = g(t)那麼你想要 做的是計算距離||x1(t) - x2(t)||並將其導數設置爲零。這應該是一個表達式，取決於f(t),g(t)及其衍生物，並會給你一個時間tmin（或可能有幾個可能的），然後評估距離並檢查它是大於還是小於r1+r2 - - 兩個邊界圓的半徑的總和。如果它較小，那麼你在那個時候有一個潛在的碰撞，所以你運行窄相算法。