📐GJKと分離超平面定理

2024年3月22日 05:24

分離超平面定理は、異なる２つの凸集合を分離する超平面が存在することを示す定理です。

Gilbert-Johnson-Keerthi距離アルゴリズムとは、1988年にElmer G. Gilbert、Daniel W. Johnson、S. Sathiya Keerthiによって初めて発表された、2つの凸集合間の最小距離を求める方法である。他の多くの距離アルゴリズムとは異なり、幾何学データが特定のフォーマットで保存されている必要はなく、その代わりに、2つの凸形状の構成空間障害（CSO）、より一般的にはミンコフスキー差として知られているものを用いて、より正解に近いシンプリスを反復的に生成するためのサポート関数にのみ依存している。

"拡張GJK "アルゴリズムは、次のシンプレックスを探すときにエッジをたどることで、アルゴリズムを高速化するためにエッジ情報を使用します。これにより、頂点の数が多いポリトープでは性能が大幅に向上する。

GJKは、原点に最も近い四面体の点を一般的なケースで計算するジョンソンの距離部分アルゴリズムを利用するが、数値的なロバスト性の問題に悩まされることが知られている。2017年にMontanari、Petrinic、Barbieriは、潜在的に小さな量の乗算を回避する符号付き体積に基づく新しいサブアルゴリズムを提案し、15％から30％の高速化を達成した。

GJKアルゴリズムは、シミュレーション・システムやビデオ・ゲームでインクリメンタルに使用されることが多い。このモードでは、前の解の最終的なシンプレックスが、次の反復、つまり「フレーム」の初期推測として使用される。新しいフレームの位置が古いフレームの位置に近ければ、アルゴリズムは1～2回の繰り返しで収束する。これにより、ほぼ一定時間で動作する衝突検出システムが得られる。

このアルゴリズムの安定性、速度、および小さなストレージフットプリントは、リアルタイム衝突検出、特にビデオゲーム用の物理エンジンに人気があります。

ミンコフスキー・ポータル・リファインメント衝突検出アルゴリズムは、2つの凸形状が重なっているかどうかを判定するためのテクニックです。

このアルゴリズムは2006年にGary Snethenによって作成され、Game Programming Gems 7で初めて公開されました。このアルゴリズムはTomb Raider：アンダーワールド』など、クリスタル・ダイナミクス社とその姉妹スタジオであるアイドス・インタラクティブ社が制作したゲームに採用された。

MPRは、GJKと同様に、サポートマッピングを使用して定義された形状に依存します。これにより、このアルゴリズムは、他のアルゴリズムでは問題となる無限の多様な形状をサポートすることができます。サポート・マッピングは、点、線分、円盤、円柱、円錐、楕円体、サッカーボール、弾丸、錐体、その他ほとんどの一般的な凸形状を表現するのに必要な数学関数を1つだけ必要とする。いったん基本プリミティブのセットが作成されれば、スイープ、シュリンクラップ、アフィン変換などの操作を使って、それらを簡単に組み合わせることができる。

GJKとは異なり、MPRは分離された形状間の最短距離を提供しない。しかし、MPRの作者によれば、MPRはより単純で、数値的にロバストであり、並進スイープをほとんど修正することなく扱うことができる。このため、ゲームやその他のリアルタイム・アプリケーションに適している。

Here's the English prompt used for the illustration of the Separating Hyperplane Theorem: "A conceptual illustration of the Separating Hyperplane Theorem, depicting two distinct convex sets in a multidimensional space, separated by a flat hyperplane. One convex set is shown as a cluster of blue spheres, and the other as a cluster of red spheres. The hyperplane is depicted as a smooth, thin, gray plane that clearly divides the two sets without intersecting them. This visualization emphasizes the concept that there exists a hyperplane that can separate two non-overlapping convex sets, highlighting the spatial relationship and mathematical abstraction."

いいなと思ったら応援しよう！

お願い致します