- GJKアルゴリズムは、2つの図形が重なっているかを確認する方法
- 図形Aと図形Bが重なっているかを確認するには、2つの図形の点のいずれかが重なるかを確認すればよい
Minkowski差集合
- 2つの図形のすべての点を引いて、新しい集合を作る。
- この新しい集合に原点が含まれていれば、2つの図形が重なっていることを意味する。
- これをMinkowski差集合と呼ぶ。
アルゴリズムの基本アイデア
- AとBのMinkowski差集合が原点を含むかを確認する。
- 差集合が原点を含めば、2つの図形は重なっている。
アルゴリズムの手順
- 初期化: 任意の方向ベクトル
d を設定し、最初の点 p を見つける。
- 点を探す:
d と p の内積を計算し、正であれば続行し、負であれば終了する。
- 新しい点を追加:
p から原点方向に新しい点を探す。
- 単体化: 最初の2点を基準に新しい点を追加して単体化する。
- 原点を含むか確認: 単体化した図形が原点を含むかを確認する。
- 反復: 原点を含むまで、または含まれないという証拠が見つかるまで繰り返す。
GN⁺の見解
- 興味深い点: GJKアルゴリズムは、複雑な問題を単純な数学的変換で解決する好例。
- 役立つ理由: 衝突判定のようなリアルタイムグラフィックスで非常に有用に使われる。
- 批判的な視点: アルゴリズムの実装は複雑になりうるため、正確な理解が必要。
- 関連技術: 他の衝突判定アルゴリズムにはSAT(Separating Axis Theorem)などがある。
- 考慮事項: GJKアルゴリズムを使う際は、図形の複雑さと計算コストを考慮する必要がある。
1件のコメント
Hacker Newsの意見
GJKアルゴリズム: 1990年代にGJKアルゴリズムを理解しようとして1年苦労した。衝突検出と最近接点の探索に有用。基本概念は理解しやすい。2つの凸な立体から始めてランダムな点を選び、各点間の距離を改善しようとする。最も近い点を選んで反復する。最も近い点がもはや頂点でなくなったときに「シンプレックス」の概念が必要になる。さまざまなケースを解析するということ。物理エンジンでは、オブジェクトが面同士の接触に落ち着くときに問題が発生する。理論的には優雅な解決策だが、実際には難しい数値解析の問題。それでも最速のアプローチである可能性が高い。一般的な場合は O(log N)、前の位置に近い場合は O(1)。オックスフォード大学の故スティーブン・キャメロン教授は、GJKを正しく実装するために多くの研究を行った。1990年代後半の商用3Dラグドールシステム「Falling Bodies」でGJKを使用した。
GJKの説明執筆: GJK衝突検出アルゴリズムの直感的な説明が見つからなかったので自分で書いた。より明確かつ効率的にする方法があれば教えてほしいと求めている。高校生による数学の説明なので、相応の懐疑心を持って受け取ってほしいとしている。
GJKアルゴリズムの動画: 同じアルゴリズムについての動画プレゼンテーションへのリンクを共有している。動画リンク
記事への称賛: 素晴らしい記事。とても明快で興味深い。
凸最適化との比較: 2つの凸集合の交差を確認する別の方法は、2点間の差のノルムを最小化する凸最適化問題を解くこと。最適値が0なら集合に交点がある。GJKアルゴリズムと凸最適化の手法の比較を見てみたい。どちらが優れているのか確信が持てない。
記事への称賛と誤解: 素晴らしい記事。ただし、最初の画像は非凸形状の交差を示しているが、アルゴリズムが凸形状にしか機能しないことは後で明らかにされている。
GJKアルゴリズムを初めて知る: GJKアルゴリズムについて初めて聞いた。
関連ブログ投稿: Minkowski幾何学に関するブログ記事を書いた。ブログリンク
個人Webサイト: 思いがけず注目を集めていて、個人Webサイトが冗談だらけであることに触れている。連絡を取りたいなら返信で知らせてほしいと頼んでいる。
Minkowski関数の使用: openSCADでMinkowski関数を使ってきたが、それが実際に何なのか分かってうれしい。
アルゴリズムへの称賛: すごいアルゴリズムだ.