私はさまざまな衝突検出アルゴリズムを研究しており、そのうちの 1 つがスイープとプルーニングです。私はそれがどのように機能するかをよく理解していると思います。軸ごとに並べ替えられたエンドポイントのリストを保存し、各更新中にリストを並べ替えておく必要があります。以下は、このアルゴリズムを理解するのに役立つ Web ページの 1 つへのリンクです。
http://jitter-physics.com/wordpress/?tag=sweep-and-prune
ただし、一時的な一貫性がコードにどのように実装されているかについては、あまり明確ではありません。オブジェクトが連続した時間枠でほとんど動かないという事実を利用していることは理解していますが、それをどのように実装できるかはよくわかりません。
誰かがこの状況に光を当てることができますか?
質問に対して+1しますが、あなたの答えはおそらく間違っています。時間的コヒーレンスは、ソート (スイープ) フェーズで、1 つのシミュレーション ステップから次のステップまでの間で利用されます。ウィキペディアのSweep and Pruneからの抜粋を次に示します。
ソリッドは 2 つのシミュレーション ステップ間で大きく移動しない可能性が高いため、スイープとプルーニングは時間的な一貫性を利用します。そのため、各ステップで、バウンディング ボリュームの開始点と終了点の並べ替えられたリストを、比較的少ない計算操作で更新できます。挿入ソートなど、ほぼソートされたリストのソートが高速なソートアルゴリズムは、この目的に特に適しています。
タイム ステップ 1、t = 1でn 個のオブジェクトがあるとします。スイープ フェーズでは、すべてのオブジェクトを並べ替え、結果に基づいて狭いフェーズも実行して、実際の衝突オブジェクトを見つけました。ここで、t = 2の場合、シミュレーションにテレポートする (消えて別の場所に再出現する) オブジェクトがない限り、オブジェクトはt = 1の位置からt = 2でわずかに移動します。t = 1と2の間で、 の変化がそれほど大きくない場合 (時間的一貫性)、t = 1に対して作成したソート済みリストは、一般に、 t = 2のソート済みリストに到達するための良いスタートを切ることができます。start.xend.xXt = 2の場合、古いリストは完全にソートされた状態に非常に近いためです。ここで、挿入ソートのようなソートを使用することにより、一般的なケースではコストがかかる可能性がありますが、このほぼソートされたケースではうまく機能し、t = 2の完全にソートされたリストにすばやく到達できます。
私は自分自身の質問に対する答えを見つけたかもしれないと思います。時間的コヒーレンスは、狭いフェーズの衝突検出のために実行する作業の量を減らすだけです。以下のリンクのコードを調べていました。
http://www.koders.com/java/fidB3D3D9D154CE69A671A799D52E7C44C104DF9537.aspx?s=wa
ここで時間的コヒーレンスの出番だと思います。オブジェクト ペアが衝突の対象と見なされ、狭いフェーズの衝突になると、エンドポイントの配列がソートされます。エンドポイントを再度ソートする必要があるまでは、76 行目の if ステートメントが真になることはないため、狭いフェーズの衝突と見なされるオブジェクトのペアを探す必要はありません。その場合、コードは時間的コヒーレンスの原則に従います。小さな時間ステップでは、オブジェクトの構成はほとんど変化しないため、配列の並べ替えは保証されません。配列内では何も再配置されません。したがって、狭位相衝突の量は減少します。