ギルバート・ジョンソン・キールティ距離アルゴリズム

ギルバート・ジョンソン・キールティ距離アルゴリズムは、2 つの凸集合間の最小距離を決定する方法であり、 1988 年にエルマー・G・ギルバート、ダニエル・W・ジョンソン、および S. サティヤ・キールティによって初めて公開されました。他の多くの距離アルゴリズムとは異なり、ジオメトリデータを特定の形式で保存する必要はなく、代わりに、 2 つの凸形状の配置空間障害(CSO) (より一般的にはミンコフスキー差として知られています) を使用して、正しい答えに近い単体を反復的に生成するサポート関数のみに依存します。

「拡張 GJK」アルゴリズムは、エッジ情報を使用して、次の単体を探すときにエッジをたどることでアルゴリズムを高速化します。これにより、多数の頂点を持つ多面体のパフォーマンスが大幅に向上します。

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

GJK アルゴリズムは、シミュレーションシステムやビデオゲームで増分的に使用されることがよくあります。このモードでは、前のソリューションの最終的な単体が、次の反復、つまり「フレーム」の初期推測として使用されます。新しいフレームの位置が古いフレームの位置に近い場合、アルゴリズムは 1 回または 2 回の反復で収束します。これにより、ほぼ一定の時間で動作する衝突検出システムが得られます。

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

概要

GJK は次の 2 つの機能に依存します。

$\mathrm {サポート} (\mathrm {形状} ,{\vec {d}})$ は、とのドット積が最大となる $図形$ 上の点を返します。 ${\vec {d}}$
$\mathrm {NearestSimplex} (s)$ は単体 $s を受け取り、$ $s$ 上の原点に最も近い単体と、新しい単体に垂直な原点に向かう方向を返します。s 自体に原点が含まれている場合 $、$ NearestSimplex $は$ $s$ を受け入れ、2 つの図形が交差すると判断されます。

$NearestSimplex$ によって処理される単体は、それぞれ $R n$ の単体サブスペースになります。たとえば、3D では、単体は点、線分、三角形、または四面体になり、それぞれ 1、2、3、または 4 つの点で定義されます。

擬似コード

関数GJK_intersection(形状 p、形状 q、ベクトル initial_axis):
    ベクトル A = サポート(p, 初期軸) − サポート(q, −初期軸)
    単体 s = {A}
    ベクトルD = −A

    ループ:
        A = サポート(p, D) − サポート(q, −D)
        ドット(A, D) < 0の場合:
            拒否する
        s = s ∪ {A}
        s, D, contains_origin := NearestSimplex(s)
        contains_origin がある場合:
            受け入れる

図

参照

外部リンク

「3次元空間における複雑な物体間の距離を計算するための高速手順」、ギルバート、ジョンソン、キールティ - 最初の出版物
「オブジェクト間の距離の計算」、オックスフォード大学のスティーブン・キャメロン教授による GJK の実装
「驚くほど難しい問題に対する奇妙だがエレガントなアプローチ (GJK アルゴリズム)」
ギルバート・ジョンソン・キールティ法の導入に関する52分間のビデオ講義
「凸オブジェクト間の距離クエリをより高速かつ信頼性の高いものにするための GJK アルゴリズムの改善」、Montanari、Petrinic、Barbieri。
「衝突検出の高速化: 最適化の観点」、Montaut、Le Lidec、Petrik、Sivic、Carpentier。この研究論文では、ネステロフ型加速戦略を活用して元の GJK アルゴリズムを高速化し、GJK の全体的な計算の複雑さを軽減する方法を特に示しています。
「ギルバート・ジョンソン・キールティアルゴリズムをできるだけ簡単に説明」