ハクソク

世界を動かす技術を、日本語で。

高速3D衝突検出アルゴリズム

320日前原文(cairno.substack.com)

概要

  • 本記事は 凸多面体の狭義衝突判定 （Separating Axis Test, SAT）を数理最適化の観点から再解説
  • Minkowski差・Gaussマップ の利用によるSAT高速化手法の紹介
  • 2Dから3Dへの一般化と サポート関数評価の最適化 が主題
  • 実装上のポイントや データ構造 にも触れる
  • 詳細な実装例は GitHubリポジトリ を参照

凸多面体のSeparating Axis Testと最適化

  • 本記事は 狭義衝突判定 と Minkowski和・差、 Gaussマップ など幾何学的概念の基礎知識を前提
  • DirkによるSATのプレゼンテーション（The Separating Axis Test between Convex Polyhedra）を参考
    • Gaussマップを重ね合わせてMinkowski差の面を発見
  • Minkowski差の全ての面は以下のいずれか
    • 形状Aの面
    • 形状Bの面
    • AのエッジとBのエッジの外積
  • 特に3つ目の場合は、 サポート関数の全評価を省略可能
  • Gaussマップ上の各点でサポート関数評価をスキップできるか検討
    • 実際に可能であり、SATの評価回数を大幅削減

2つの凸集合A, Bのケース分け

  • 非交差（No overlap）
    • 両集合間の最近傍点ペア探索
    • 問題は凸最適化であり、反復的な凸ソルバーで解決可能
  • 交差（Overlap）
    • 最小平行移動ベクトル（MTV, Minimum Translation Vector）の探索
    • 問題設定は非凸なQCQP（Quadratically Constrained Quadratic Program）となる

Minkowski差とサポート関数による定式化

  • サポート関数：
    • ( f(v) = \max_{z \in C} (z \cdot v) ), ( C = A - B )
  • 目的関数の特徴
    • 微分可能だが、有限個の「キンク点」（一階微分不連続点）が存在
    • 各「頂点領域」ごとに関数は凹型
    • キンク点は多面体の面法線方向に対応

2Dから3Dへの一般化

  • 2Dではキンク点は原点を通る直線と円の交点
  • 3Dではキンク点は原点を通る平面と球面の大円の交線
  • 各頂点領域の境界は面法線で決まる
  • グローバルな最小値は、全ての面法線方向で評価し最小値を選択

SATアルゴリズムの最適化

  • Dirkの手法：Minkowski差の面法線を全て評価
    • 新規面法線（エッジの外積）の場合、サポート関数の全評価不要
  • さらに最適化：球面上の弧をグラフ探索し、各頂点領域のサポート点を追跡
    • 初回のみフル評価、以降は隣接領域を伝播
  • 実装例
    • 半辺データ構造（Half Edge）でトポロジー管理
    • 頂点ごとに接続エッジの配列を保持
    • 各エッジは両側の面情報も持つ

実装のポイント

  • 弧トレースや交差判定のための トポロジカルなエッジ管理
  • 高品質な凸包生成アルゴリズムの利用
  • 詳細な実装はGitHubリポジトリを参照

SATアルゴリズムのまとめ

  • SATは凸多面体同士の衝突判定において 必須のテクニック
  • Minkowski差・サポート関数の性質を活用し、 評価点数の削減 が可能
  • 2Dの考え方を3Dへ拡張することで、グローバル最適化が容易
  • 実装時は データ構造 と トポロジー管理 が重要

参考・補足

  • 本アルゴリズムは COVID 期間中に発見し、記事としてまとめたもの
  • 詳細なコードや実装例は GitHub で公開中

Hackerたちの意見

これってHalo 2のAscensionじゃん。クールなテストケースだね！

└

本物のOGは知ってるよね :) 超バウンドやアウトオブバウンズのトリックが大好きだったけど、Ascensionにはあまり後者がなかった気がするな。

確かに新しいね！非球形の形状はどうなるの？球状の境界を仮定して、そのコストを受け入れる感じ？どちらにしても、三角形レベルになると狭いフェーズがすごく扱いづらくなるよね。単純な形状には簡単だけど、100万頂点をぶつけると、100万頂点相手に悪い時間を過ごすことになるよ。レイテストやクリップを減らす最適化があれば、絶対にプラスになるね。

└

おそらく、空間階層データ構造の枝をテストすることで前処理できると思う。1百万の二乗は、アルゴリズムに関わらず計算するには多すぎるよね。

└

非凸形状のことを言ってるの？凸分解をして、すべてのペアをテストすればいいよ。普通、ゲームではこれをBVHで加速させるんだ。

└

普通は、レンダーモデルと物理モデルがあって、後者は見えているオブジェクトの劣化版なんだ。オブジェクトを拾いやすくしたり、曲がったハンドルを通過させたりするために調整されたオブジェクトもあるし。このアルゴリズムを使っても、その作成パイプラインが必ずしも変わるわけじゃないと思うよ。

└

球状の境界を仮定して、コストを受け入れるの？私たちは、使用ケースに最も適した境界ボリュームを選ぶよ。非球状の境界ボリュームのコストは、純粋な球状のものと比較して、それほど厳しくないことが多いんだ。 https://docs.bepuphysics.com/PerformanceTips.html#shape-opti... 編集: このドキュメントがこの問題に言及していることに気づいたよ: https://github.com/bepu/bepuphysics2/issues/63 記事に関連しているみたいだね。

ここで数学を整理しようとしてるんだけど、これらの二つの命題が同じだと理解できないんだ。1) min_{x,y} |x-y|^2 x ∈ A y ∈ B 2) = min_{x,y} d d ≥ |x-y|^2 x ∈ A y ∈ B 'd'って何？もしdが実際の(x, y)で|x-y|^2よりずっと大きくて、別の(x', y')で|x-y|^2と等しいなら、(2)は違う間違った解を出すことにならない？'d'は何かの測定値で、これを防ぐために制約があるってことが暗に示されてるの？

└

スマホでSubstackが読めないから、記事が見れないんだけど、君が書いたことに最も近い正しい表現は、dがこの不等式を満たす任意の実数であるってことだね。UをAxBxRの部分集合として定義して、U={(a,b,x):x>|a-b|^2}とする。そして、d(a,b,x)=xという三番目の座標関数の下でUの（像の）下限を探しているんだ。

└

でも、なんでdがそんなに大きくなるの？問題はdを最小化することを求めているから、最小の|x-y|^2より大きくなることはないよ。

└

これは問題のエピグラフ形式だね。エピグラフの中で最も低い高さの点を見つけようとするんだ。 https://en.wikipedia.org/wiki/Epigraph_(mathematics)

└

d、x、yが最適化される変数だってことを見落としてると思うよ。1)の解よりも低いdの選択は不可能だし、1)の解より高いdは最適じゃない。編集：今気づいたけど、問題2)の最適化変数の下付きにdが抜けてるね。これはタイプミスだと思う。

余談だけど、学校でSep Axis Theoremを習って、面白いアルゴリズムについて聞かれた時にインタビューでよく使ってるんだ。技術的じゃない人にも説明できるくらいシンプルだよ。「懐中電灯と二つの物体があれば、光を当てることで交差してるかどうか分かるよ」って感じで。そしたら、面のドット積や早期終了の挙動、MTVについて説明できる。

いいね。これは間違いなく最適化問題だね。でも、数値誤差にも目を向けないと。1990年代後半にGJKの凸包距離についてたくさんの作業をしたことがあるよ。特別なケースがある最適化問題なんだ。最も近い点は、頂点対頂点、頂点対辺、頂点対面、辺対辺、辺対面、面対面の組み合わせがある。最後の3つは非一意な解を持つことがある。最も近い頂点を見つけるのは簡単だけど、それだけでは不十分なんだ。物理エンジンでこれを使うと、オブジェクトが接触して、通常は非一意な解の空間に収束するんだ。例えば、立方体の上に立方体がある場合や、小さな立方体が大きな立方体の上にある場合。これは面対面に収束して、一意な最も近い点がないんだ。もう一つの問題は、平面ポリゴンの表面についてどうするかだね。タッセレーションを行うと、長方形の面が2つの共面三角形になる。これがGJKのループを引き起こすことがある。タッセレーションをしない場合、浮動小数点のポリゴンは本当に平坦ではないから、これもGJKのループを引き起こす。面の間に最小のブレーク角を持つ多面体が必要で、これはほとんどの凸包生成器が生成できるものだよ。ランダムな複雑な多面体の単体テストを実行しても、ハードケースにはあまり当たらないけど、物理エンジンは当たるんだ。オックスフォードのスティーブン・キャメロン教授が1990年代にこの問題の解決策を見つけたんだ。[1] 彼のアプローチが時々ループすることに気づいたよ。これに対する安全な終了条件は難しいんだ。彼は最終的にそれを思いついた。私はループを検出するためのブルートフォースアプローチを持っていた。最近、近似凸分解に関する研究があって、凸包の重なりが許可されているものがある。真の凸分解は、ドアや窓のような小さな凹面周りに厄介なジオメトリを生成しがちだけど、近似凸分解はクリーンなジオメトリを生み出すんだ。[2] でも、クリーンで水密なジオメトリ（「単体」）から始めないと、このアルゴリズムは問題を抱えることになるよ。

└

でも、数値誤差にも目を向けないと。うん、同意するよ。誤差分析はそれ自体で多くのブログになるかもしれないね。このブログの終わりにはちょっと疲れたよ。将来的にこれについての投稿を書きたいな。グローバルソルバーや反復的なものについて。 > 最も近い頂点を見つけるのは簡単だけど、それだけでは不十分だよね。君も知っていると思うけど、ほとんどのGJK実装は最も近い特徴を見つけて、その後、特徴同士をクリッピングすることで一回の接触マニフォールドを生成するんだ。GJKがCSOの単体を見つけると、単体の各頂点はAとBの対応する点を追跡するんだ。 > もう一つの問題は、平面ポリゴンの表面についてどうするかだね。現代の物理エンジンや私がアップロードしたデモは、これを処理する面クリッピングを行っているよ。GJKでは、通常、ハル内の点が線形独立であることを確認するんだ。

└

最近、近似凸分解に関する研究が進んでいるみたいで、元の立体を表す凸包同士の重なりが許されるんだって。これを、幾何学的なレベルでの相互侵入ではなく、バウンディングボリュームの重なりを管理するという形で問題を再定義するのが賢いかも。もし全てがバウンディングスフィアに囲まれているなら、ほとんどの場合、衝突検出は簡単だよね。二つのバウンディングスフィアが交差する時は、特定の距離とユニークな角度で交わることになる。そうなると、関連するのは一つの量だけ、つまり許容される重なりの深さで、これはBVの中心間の角度や、二つの囲まれたオブジェクトの向きに依存するだけ。他には何も関係ない感じ。オフラインで事前計算するのに向いてそう… まるでいろんなライティングハックみたい。最終的には凹みの問題にも対処しなきゃいけないけど、そうなると問題がかなり厄介になるね。

└

あなたの知識の深さにはいつも驚かされるよ。食事でもどう？おごるから。今、資金調達のためにアメリカをよく移動してるから、近くにいるかも。プロフィールにメールアドレスあるよ。

HNに投稿されるリンクの数にうんざりしてきた。クッキーのスパムがうざいんだよ。

これを見るのは嬉しい！25年前にこのトピックについて書いてたんだ: https://www.flipcode.com/archives/Theory_Practice-Issue_01_C... そのパート2: https://www.flipcode.com/archives/Theory_Practice-Issue_02_C...

関連ある？これ、数日前に投稿されたやつだよ。 https://news.ycombinator.com/item?id=44334403

└

いや、AVBDはソルバーで、標準の衝突検出ルーチンを使ってるよ。