GJKアルゴリズム: 単純なことを奇妙で美しく解決する方法

 (computerwebsite.net)
2 ポイント 投稿者 GN⁺ 2024-06-13 | 1件のコメント | WhatsAppで共有
  • GJKアルゴリズムは、2つの図形が重なっているかを確認する方法
  • 図形Aと図形Bが重なっているかを確認するには、2つの図形の点のいずれかが重なるかを確認すればよい

Minkowski差集合

  • 2つの図形のすべての点を引いて、新しい集合を作る。
  • この新しい集合に原点が含まれていれば、2つの図形が重なっていることを意味する。
  • これをMinkowski差集合と呼ぶ。

アルゴリズムの基本アイデア

  • AとBのMinkowski差集合が原点を含むかを確認する。
  • 差集合が原点を含めば、2つの図形は重なっている。

アルゴリズムの手順

  1. 初期化: 任意の方向ベクトル d を設定し、最初の点 p を見つける。
  2. 点を探す: d と p の内積を計算し、正であれば続行し、負であれば終了する。
  3. 新しい点を追加: p から原点方向に新しい点を探す。
  4. 単体化: 最初の2点を基準に新しい点を追加して単体化する。
  5. 原点を含むか確認: 単体化した図形が原点を含むかを確認する。
  6. 反復: 原点を含むまで、または含まれないという証拠が見つかるまで繰り返す。

GN⁺の見解

  • 興味深い点: GJKアルゴリズムは、複雑な問題を単純な数学的変換で解決する好例。
  • 役立つ理由: 衝突判定のようなリアルタイムグラフィックスで非常に有用に使われる。
  • 批判的な視点: アルゴリズムの実装は複雑になりうるため、正確な理解が必要。
  • 関連技術: 他の衝突判定アルゴリズムにはSAT(Separating Axis Theorem)などがある。
  • 考慮事項: GJKアルゴリズムを使う際は、図形の複雑さと計算コストを考慮する必要がある。

関連記事

1件のコメント

 
GN⁺ 2024-06-13
Hacker Newsのコメント

  • 1990年代に GJK のせいでほぼ1年苦しんだ
    3D衝突検出に有用で、最近点アルゴリズムとしても使える。基本的な考え方は理解しやすい。2つの凸立体があるとき、それぞれの立体から任意の点を1つずつ取り、2点間の距離を求めたうえで、現在の点から各辺に沿って移動して距離が改善するかを試し、新しい最近点を選ぶ、という処理を繰り返す
    ただし最近点がもはや頂点でなくなるとこの方法は破綻し、そこで 単体(simplex) の概念が必要になる。最近点の組み合わせは、頂点-頂点、頂点-辺、頂点-面、辺-辺、辺-面（一意解なし）、面-面（一意解なし）に分かれ、単体の処理は実質的にこれらのケースを分析する作業に近い
    実際には問題が多く起きる。物理エンジンでは物体が面-面接触の状態で安定することが多く、単一点の衝突モデルは振動や誤った動きを生み出すことがある。また位置が面-面接触へ収束するとき、GJKは大きな値同士の小さな差を扱うことになり、浮動小数点の有効桁を完全に失う可能性がある。終了条件も無限ループを引き起こしうる
    理論的には優雅だが、実際には難しい 数値解析 の問題である。それでもおそらく、この問題に対する最速のアプローチである可能性が高い。一般的な場合は O(log N) で、前回位置に最も近い状況で最後の解を開始点として使えば O(1) に近い
    Oxfordの故Steven Cameron教授は、GJKをきちんと動作させるために多くの作業を行い、1990年代後半の最初の商用3Dラグドールシステム「Falling Bodies」でGJKを使っていた

    • 接触を見つけたら、ほぼ必ずそれを使って何かをしなければならず、たいてい有用な処理をするには実際の 重なり情報 を知る必要がある
      これを求めるほうが数値的にはさらに悪い。GJKが作った単体から始めて外側へ拡張し、その過程で三角形分割をしなければならない。高性能に実装するのはまさに悪夢に近い
    • https://www.youtube.com/watch?v=5lHqEwk7YHs
      特許はもう失効したのか、コードを公開するつもりがあるのか気になる。歴史的に意味があり、Doomのソースを読むような興味深い資料になりそうだ

  • GJK衝突検出アルゴリズム を直感的に説明した記事が見つからなかったので、午後を使って自分でまとめた
    もっと明確で効率的にする方法があれば教えてほしい。もちろん、高校2年生が数学関連の内容を説明した記事だという点は、ほどほどに考慮してもらえるとうれしい

    • 記事はとても明確だ。こういう作業を続ければ、いつか優れた教科書を書けるかもしれないほどの才能が見える
      すでに良いが、さらに完璧にするならいくつか追加できそうだ。最悪の場合の 時間計算量 についての短い説明、終了条件を扱う別セクション、そして説明の随所に疑似コードがあるとよい
      今のように数学的な観点から説明するやり方はよく合っていて、維持する価値がある。ただし各ステップの後に S(•) のような補助関数を定義しつつ、アルゴリズムがどこまで進んだかを示す短い 疑似コード を添えるとさらに良さそうだ
      OpenAIの隠れたモデルについての記事も良かった。印象的な成果物を作った人がほかに何をしているのか探す時間は、ほとんど常に報われる
    • 数学者として言うなら、数学の読者向けに書くならいくつかの表現をほんの少し違うものにしたかもしれない、という程度が最大の批判だ
      タイトルは「as simply as possible」であるべきだ。GJKアルゴリズムは知らなかったが、もし今Calculus IIIを教えていたなら、この内容を授業に入れる方法を探したと思う。それくらい説明が良い
    • このアルゴリズムは 終了が保証 されるのか気になる
      記事の最後にある滑らかに角丸になった長方形の例で、答えにどんどん近づくだけで実際には到達しない、ということを防ぐ仕組みが何なのか分からない。もちろん実際の計算では、実用的な精度限界を超えて続ける理由がないことは分かっている
    • 2枚目の図の3つの集合 A, B, A-B が分かりにくい
      最初は、AとBに何らかの変換を適用するとA-Bの形になるという意味だと受け取った。何度か読み返すと、A-Bは左側にある2つの集合ではなく、別のAとBの共通部分を表しているように見え、その共通部分が原点または0,0と重なることが重要だ、という意味に思える。合っているのか気になる

  • 同じアルゴリズムを扱った動画発表: https://www.youtube.com/watch?v=ajv46BSqcK4

  • 記事は非常に明確で興味深い
    2つの凸集合が交差するかを確認する別の方法として、1つ目の凸集合に属する点と2つ目の凸集合に属する点の差のノルムを最小化する 凸最適化 問題を解く方法がある。最適値が0なら2つの集合は交差している
    GJKアルゴリズムと凸最適化を比較してみると面白そうだ。どちらが有利かはよく分からない

    • 面白い質問だ。重なりが十分大きければ 内点法 が早く終了することもありそうだ。賢い早期終了条件も追加できそうだ

  • 最初の画像が 非凸図形 の交差を示しているが、アルゴリズムが凸図形でのみ動作するという事実はずっと後になってから出てくるので、少し誤解を招くかもしれない

    • 非凸図形は凸図形群に分割して処理すると説明されている

  • openSCADで Minkowski関数 をしばらく使ってきたが、それが実際に何なのか分かってよかった

  • 予想以上に関心を集めることになったので、個人サイトは実質的に凝った 内輪ネタ集 だという点は言っておくべきだと思う
    連絡したいことや用事があれば、返信で知らせてくれればよい

    • 研究プロジェクトのメンタリングに興味があるならメールしてもよい: bersub@cmu.edu
    • サイトが良くて、いい感じの人のように思える。これからもかっこいいものを作り続けてほしい

  • ほぼ10年前にCaseyの優れた説明をもとに GJK を実装した: https://www.youtube.com/watch?v=Qupqu1xe7Io

  • ミンコフスキー幾何 に関する記事を書いたことがある: https://nickp.svbtle.com/asteroid-intersections