2

時間（交差点が始まる時間）を見つけることに重点を置いていますが、位置も重要です。境界ボックス (軸が揃っていない) には、位置、回転、速度、および角速度 (回転速度) があります。加速はありません。これにより、物事が本当に単純化されます...そして、必要に応じて、角速度成分もおそらく削除できます。連続関数または反復関数のいずれかが機能しますが、反復関数がソリューションに向かって積極的に収束しない限り (またはその欠如)、おそらく遅すぎます。

SATを見てみましたが、動いている物体の衝突の実際の時間を見つけるように構築されていないようです。動いていないスナップショットでのみ機能するようで、長方形よりも複雑なオブジェクトで機能するように設計されているため、実際にはこの問題には適していないようです。

私はおそらく8つのポイントのそれぞれから軌道を描き、ポイントが他の形状にあるかどうかの関数を持ち、それが発生する時間範囲を取得することを考えましたが、方法についてはかなり迷っていますそれについて行きます。優れた機能の 1 つは、時間とともに完全に動作し、個別の「ステップ」の概念を無視することですが、非効率的なアプローチだとも思います。

大まかなフェーズ (これら 2 つのバウンディング ボックスが重なる可能性があるかどうかを確認する価値があるかどうかを判断する) について心配する必要はありません。私はすでにそれに取り組んでいます。

4

2 に答える 2

2

正確な衝突時間を見つけることは、基本的には非線形の求根問題です。これは、最終的な衝突時間を決定するために最終的には反復的なアプローチが必要になることを意味しますが、衝突ソルバーを設計する際の巧妙な方法は、実際には必要ない場合に根の解決を避けることです...

SAT は定理であり、アルゴリズムではありません。衝突ソルバーの設計を導くために使用できますが、それ自体はそうではありません。簡単に言えば、分離軸が存在することを実証できれば、オブジェクトは衝突していないということです。逆に、そのような軸がないことを示すことができる場合、オブジェクトは現在重なり合っています。ご指摘のとおり、この原則を多かれ少なかれ直接使用して、特定の位置にある 2 つのオブジェクトが重なるかどうかについて、バイナリの「はい/いいえ」クエリを設計できます。

コリジョン ソルバーとの違いは、問題がアニメーション化されていること、つまり動的であることです。オブジェクトの位置は時間の関数です。この問題を解決する 1 つの方法は、有効な "yes/no" 衝突テストから開始し、すべての不等式を時間の関数として扱い、それに基づいて実際の衝突時間を探す根探索法を使用することです。

公開された学術文献にはさまざまな既存の方法があります。図書館で調べてみることをお勧めします。最適なオプションは、おそらくアプリケーションの詳細によって異なります。

于 2013-04-10T20:38:30.580 に答える
0

まず第一に、2 つの長方形がそれぞれ速度(x1, y1)で動くと考える代わりに(x2, y2)、そのうちの 1 つを固定し (速度を に設定(0, 0))、別の長方形が速度 で動くと考えることができます(x2 - x1, y2 - y1)。

このように、状況は、1 つの長方形が動かないように見え、別の長方形が通り過ぎて、最初の長方形にぶつかる可能性があります。

  • 角速度がないと仮定すると

ここに画像の説明を入力

(x2 - x1, y2 - y1)2 番目の長方形の 4 つの軌跡 (境界ボックスの異なる角から方向に向かって始まる光線) と、静止した最初の長方形の 4 つの側面を交差させることができることを理解するのは難しくありません。次に、逆方向に移動する最初の長方形(-(x2 - x1), -(y2 - y1))と 2 番目の長方形の 4 つの辺の交点を見つけます。見つかったすべての交点 (0 ～ 8 個ある可能性があります) 間の最小距離を選択すると、完了です。

多くの特殊なケースを考慮することを忘れないでください - 両方の長方形の辺が平行である場合、交差点がまったくない場合など。

O(1)計算は非常に複雑ですが、これはすべて時間内に行われることに注意してください-光線とセグメントの32の交差。

  • 長方形をある程度の速度で回転させたい場合は、@comingstorm が言ったことを考慮することをお勧めします。これは非線形方程式の根を見つける問題ですが、そのような場合でも、角速度が制限されている場合四角形の場合、タスクを一連の三項探索サブタスクに分割できますが、これは非線形問題を解決するための可能な方法の 1 つにすぎないと思います。
于 2013-04-10T20:53:21.683 に答える