連続物理エンジンの衝突検出技術

Question

私は物理エンジンで連続的にという物理エンジンで作業しています。幅広い狭い位相の衝突検出アルゴリズムを選択する必要があります。 「純粋に連続」とは、私が交差点テストをしないことを意味しますが、衝突が発生する前にすべての衝突をキャッチし、それぞれをTOIによって注文された「計画された衝突」スタックに配置する方法を探したいとします。

幅広いフェーズ 私はサークル内の各身体を包むと、各サークルが今まで重なっする場合はテストしていると考えることができる唯一の連続幅広い相法。これはひどく非効率的だと思われ、どんな淘汰も欠けている。

クワッドツリーのような今日の離散コリジョン除去法では、どのような連続アナログが存在するかわかりません。 ディスクリートエンジンのような不適切で無意味な広範なテストの防止について、どうすればよいでしょうか？

狭いフェーズ
私はむしろ、離散より連続チェックに狭いSATを適応させることができたが、私は、他のより良いアルゴリズムが君たちは全体来ているかもしれない論文やサイトでそこに出だと確信しています。
どのようなさまざまな高速または正確なアルゴリズムを使用することを提案し、それぞれの利点/不利点は何ですか？

最後の注意：
私はまだ私は別の凹かもしれない多角形、凸、ラウンドを保存し、あるいは穴がありますどのように決めていないので、私は技術ないアルゴリズムを言います。私はアルゴリズムに必要なものに基づいてこれを決定する予定です（たとえば、ポリゴンを三角形または凸形に分解するアルゴリズムを選択した場合、この形式でポリゴンデータを格納するだけです）。

Answer 1

あなたはサークルを言ったので、私はあなたには2Dオブジェクトがあると仮定しています。時間ディメンションを追加して2Dオブジェクト（またはその境界線の形状）を3Dに拡張し、通常の手法を使用して3Dオブジェクトのセット間の静的な衝突をチェックすることができます。

たとえば、一定の速度で右（+ x）​​に移動する（x、y）の円がある場合、時間次元でそれを拡張すると、（x、 y、t）。これらの3Dオブジェクト間の交差を行うことによって（時間をzとして扱うだけで）、2つのオブジェクトが交差するかどうかを確認することができます。点Pが交差点である場合、単に交差点の時刻を知ることができます。

これは、数学が難しくなっても（これはとにかく）、より高い次元にも一般化します。

オブジェクトに複雑なパスがあると、衝突検出が難しくなることがあります。例えば、あなたの円が重力の影響を受けている場合、押し出された時空間オブジェクトは単純な円柱ではなく放物球である。境界のあるオブジェクトを少し埋めることができ、短時間で線形近似を使用して反復することができますが、それが連続的であることを違反するかどうかはわかりません。

Answer 2

私は、あなたのシミュレーションで重力または他の控えめな力が欲しいと思っています。その場合、あなたのオブジェクトの軌跡は線にならない可能性が最も高いです。この場合、Adrianが指摘したように、数学はやや難しくなります。私は、衝突の可能性のあるすべての曲線の組み合わせをチェックすることを避ける方法は考えていませんが、2つの曲線の最小距離は、どちらも線形システムの解であれば簡単に計算できます曲線のための閉じた形式の解）。 x1(t) = f(t)とx2(t) = g(t)を知っている場合、 に何をしたいのですか？距離||x1(t) - x2(t)||を計算し、その導関数をゼロに設定します。これはf(t)とg(t)とその派生語に依存する式である必要があります。距離を評価し、それがr1+r2より大きいか小さいかを確認するときにtmin（または多分可能なもの） - 2つの境界円の半径の合計。それが小さい場合は、その時点で潜在的な衝突があり、狭い位相アルゴリズムを実行します。