 |
ミンコフスキーポータル改良 衝突検出 アルゴリズムは、2 つの凸形状が重なり合うかどうかを判定する手法です。
このアルゴリズムは、2006 年に Gary Snethen 氏によって作成され、『Game Programming Gems 7』で初めて公開されました。このアルゴリズムは、Crystal DynamicsおよびEidos Interactive内の姉妹スタジオによって作成された Tomb Raider: Underworld などのゲームで使用されました。
MPR は、その兄弟であるGJKと同様に、サポートマッピングを用いて定義される形状に依存します。これにより、このアルゴリズムは、他のアルゴリズムでは問題となるような、無限に多様な形状をサポートできます。サポートマッピングでは、点、線分、円板、円柱、円錐、楕円体、フットボール、弾丸、錐台、その他ほとんどすべての一般的な凸形状を表すために、単一の数学関数のみを必要とします。基本的なプリミティブのセットが作成されると、スイープ、シュリンクラップ、アフィン変換などの操作を使用して、それらを簡単に組み合わせることができます。
GJKとは異なり、MPRは離れた形状間の最短距離を求めません。しかし、作者によると、MPRはより単純で、数値的に堅牢であり、わずかな変更を加えるだけで並進スイープを処理できます。そのため、ゲームやその他のリアルタイムアプリケーションに適しています。
外部リンク
- スネザン、ゲイリー（2008）「複雑な衝突をシンプルに」ゲームプログラミングジェムズ7、165～178
- スネザン、ゲイリー (2008)「XenoCollide ホームページ」
- オープンソース実装: libccd
