移動物体の衝突検出

Question

私はいくつかの動く物体があると言います。私は彼らの形状（箱、球、円柱のような単純なもの）と時間外の位置関数（非線形）を知っています。私はいつ、どこで他の特定の移動オブジェクト（特殊オブジェクト）と衝突するのかを検出したいと思います。私は、2つのオブジェクトが衝突する宇宙と時間のポイントを検出したライブラリが存在することを望んでいましたが、見つけられませんでした。

この問題を解決するための効率的なアルゴリズムや、それを解決するライブラリ（あらゆる言語）がありますか？

Answer 1

そこにはたくさんのアルゴリズムがありますが、それらはすべてオブジェクト固有のオブジェクトです。線速度の一般的なパターンは、形状/形状距離の方程式をとり、それを時間上にパラメータ化し（オブジェクトの相対位置と相対速度を考慮して）、距離ゼロを解きます。

たとえば、2つの球があって、最初のものに対する2番目の相対位置がX0で、最初のものに対する2番目の相対速度がVで、球の半径がr1とr2、あなたはD(t) = ||X0 + V*t|| - (r1+r2) = 0を解決します。

ノンリニアモーションでは、基本的にはX（t）を関数として、X(t) = X0+V*tの代わりに使用します。その機能の複雑さによっては、これは簡単かもしれないし、難しいかもしれない。それが難しいと仮定して（おそらく）、あなたはニュートンラフソンのような反復的な解法に行きます。幸運なことに、距離の公式は、派生するのが簡単な傾向があります。

非線形動作のもう1つのオプションは、線形ステップに離散化することです。これは単なる安価で楽しい反復的な方法ですが、この種の方法のほとんどが線速度を想定しているため、おそらく最も簡単な方法です。

もちろん、私はそこで球体を使用しています。ボックスやシリンダーは、特に回転している場合は、距離を見つけるのが面倒です。私はトピックの標準的な本としてEricsonの「リアルタイム衝突検出」を推奨することができます。それは、より複雑な形状のための丈夫な方法と同様に、様々な形状対のための多数のレシピを有する。