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

2025年7月9日原文(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_blog

SATアルゴリズムのまとめ

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

参考・補足

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

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が抜けてるね。これはタイプミスだと思う。

Hacker Newsで議論の続きを見る

ハクソク