内接球を使用した分離軸テストの高速化

内接球 分離軸テスト（SAT）は、接触マニホールドの計算に有効です。 GJKとは異なり、形状が非常に近い場合や形状が重なっている場合でもロバストに動作します。 Box3Dは、凸包（ポリトープ）間の接触マニホールドを計算するためにSATを使用しています。 SATを使用するのが好きなのは、すべての接触点を一度に取得でき、GJKのようにオーバーラップのためのフォールバックアルゴリズムを必要としないからです。 したがって、GJKを呼び出して失敗し、EPAやSATのようなフォールバックアルゴリズムにドロップする時間を無駄にする必要がありません。 また、より安価なGJKレジームで衝突を維持するために形状を縮小する必要もありません。 SATは高価です ポリトープ間のSATは非常に高価になる可能性があります。 注意しないと、頂点の数に対してO(N^3)になる可能性があります。 コストの大部分は、エッジペアの分離テストにあります。 Box3Dには、ポリトープ間のSATを高速化するための多くの異なる方法がすでにあります。 ガウスマップは、エッジペアをテストし、それらがミンコフスキー差の表面上にない場合に迅速に除外するために使用されます。 エッジに隣接する面は、エッジペアテストでのサポートポイントの計算を回避するために使用されます。 SIMDは、一度に4つのエッジペアをテストするために使用されます。 ナローフェーズキャッシュは、ペアをキャッシュし、分離許容値を超えるまで時間ステップ間で再利用します。 コンタクトリサイクリングは、形状間の相対運動が約5cm未満の場合に接触点計算を完全にスキップするために使用されます。 マニホールドがリサイクルされるときに分離値を更新して、スタッキングを安定させます。 ご覧のとおり、SATを高速化するために多大な努力が払われています。 それにもかかわらず、Box3Dは、複雑なポリトープの大きな山を扱う場合、まだ少し遅くなる可能性があります。 Convex Pileベンチマークがこれを示しています。 これはSATに支配されています。 すなわち、エッジペアテストは多くのサイクルを消費するホットループです。 フィーチャーキャッシュとコンタクトリサイクリングは、すべてが急速に移動している初期段階ではあまり役立ちません。 Convex Pile 内接球テクニック 2011年に著名なPierre Terdimanが、SATを高速化するために内部オブジェクトを使用することを提案しました。 主なアイデアは、内接球を使用して、各面と各エッジペアが達成できる分離の安価な上限を計算することです。 ここで説明されている作業は、Pierreが文書化したものよりもさらに進んでいます。 見出しは、私がガウスマップのエッジアークを使用して、エッジペアテストに到達する前にエッジをカリングするスキームを開発したということです。 それに進む前に、2Dを見てウォーミングアップしましょう。 凸多角形と内接円を持つ2Dケースを考えます。 ボックスと内接円 ベクトルdは、AとBに内接する2つの円の中心を結びます。 重要な観察は、ボックス間の分離がこれ以上大きくなることはないということです。 $$\|d\| - (r_A + r_B)$$ これは、これより大きい分離を達成できる分離軸は存在しないことを意味します。 これが分離上限です。 以下の図は、例の軸nを示しています。 実際の分離sep(n)は明らかに上限よりも小さいです。 例の軸 ボックスを削除して円に焦点を当てましょう。 次に、標準的なミンコフスキー等価性を使用して円を結合します。 したがって、円と点の間の分離を見ています。 内接円のミンコフスキー変換（円と点） これはすべて基本的なように見えます。 しかし、Aから出てくる任意の候補単位長分離軸nを考えてみましょう。 分離の上限は次のようになります。 $$n \cdot d - r$$ ここでr = r_A + r_Bです。 この上限は、\|d\|とrを使用した最初の上限よりもタイトであり、単一のドット積を必要とするため、より優れています。 Bの法線は、上限で-dを使用する必要があることに注意してください。 候補軸n この上限はエスケープ距離ではないことに注意してください。 これは、SATが軸nに対して計算できる値の上限です。 エスケープ距離はそれより小さくなる可能性があります。 [1/2, 0]にある単位円内の点を考えます。 すると、d = [1/2, 0]になります。 +y法線方向では、計算された上限分離は次のようになります。 $$n \cdot d - r = [0, 1] \cdot [1/2, 0] - 1 = -1$$ 分離は-1なので、オーバーラップ値は+1です。 エスケープ距離qは約0.866と小さくなります。 しかし、これは問題ありません。 SATはすべての方向でエスケープ距離を与えるわけではありません。 それは軸に沿って形状を投影し、区間のオーバーラップを見つけます。 内接球テクニックは、投影された区間の分離の上限を提供します。 エスケープ距離 これはローカル検索テクニックでもありません。 SATは、形状が重なっている場合、本質的に非凸最適化問題であるため、ローカル検索はローカル最大値にはまる可能性があります。 内接球テクニックは、依然としてグローバル検索を実行しています。 では、これはどのように役立つのでしょうか？ Aの面のベースライン分離軸テストは次のようになります。 int bestIndex = -1; float maxSeparation = -FLT_MAX; for (int i = 0; i < countA; ++i) { // ポリゴンAの面の法線と点。 Vec nA = nAs[i]; Vec vA = vAs[i]; // 法線に沿ってポリゴンBの最も深い頂点を見つける。 float si = FLT_MAX; for (int j = 0; j < countB; ++j) { float sij = Dot(nA, vBs[j] - vA); if (sij < si) { si = sij; } } if (si > maxSeparation) { maxSeparation = si; bestIndex = i; } } 両方のポリゴンがN個の点を持つ場合、この計算はO(N^2)です。 内接球上限を使用すると、次のように書き換えることができます。 int bestIndex = -1; float maxSeparation = -FLT_MAX; for (int i = 0; i < countA; ++i) { // ポリゴンAの面の法線と点。 Vec nA = nAs[i]; // 現在の最大値を上回れない場合は、この面をスキップします。 if (Dot(nA, d) - r < maxSeparation) { continue; } Vec vA = vAs[i]; // 法線に沿ってポリゴンBの最も深い頂点を見つける。 float si = FLT_MAX; for (int j = 0; j < countB; ++j) { float sij = Dot(nA, vBs[j] - vA); if (sij < si) { si = sij; } } if (si > maxSeparation) { maxSeparation = si; bestIndex = i; } } これだけでも非常に驚くべきことです。なぜなら、N個のドット積を1つに交換できるからです。 このカリングは望ましいため、dに最も近い面沿いの分離で初期最大値をシードすることが役立ちます。 ポリトープBについては、ポリトープAからの最大分離を考慮して、-dに最も近い面でシードされた面をテストします。 丸め誤差を防ぐために、上記のrの値はわずかに減らす必要があることに注意してください。 相対許容値と絶対許容値（メートル単位）の組み合わせを使用します。 $$r = r_0 - (0.005 + 0.001 (\|d\| + r_0))$$ エッジカリング 面テストを高速化するのは良いことですが、問題の核心は、衝突するポリトープに必要な3Dエッジペアテストです。 内接球テストは、エッジがペアテストに到達する前に、ポリトープのエッジを考慮から完全に除外するために使用できます。 このようにして、テストされるペアの数を大幅に減らすことができます。 ポリトープのガウスマップは、単位球上の頂点として面を表します。 エッジはそれらの頂点を結ぶアークになります。 シェルが衝突すると、ミンコフスキー差はそれらのガウスマップを結合します（Bは否定されます）。 ポリトープAのアークがポリトープBのアークと交差すると、ガウスマップ上に頂点が生成され、これはミンコフスキー差の面を表します。 この面は、両方のガウスマップアークの範囲内にある法線を持っています。 特定のエッジについて、それが生成する任意の分離軸は、そのガウスマップアークに沿ったどこかにあることがわかっています。これは、隣接する2つの面の間で法線をスイープすることによって定義されます。 下の画像は、エッジのトップダウンビューでこのアークを示しています。 ベクトルwは、n1とn2（エッジに垂直）によって張られる平面へのdの投影です。 エッジのガウスアーク wが面法線の間にある場合、分離の上限は次のようになります。 $$\|w\| - r$$ この上限が最大面分離を超える場合、このエッジはエッジペアテストの候補となります。 wがアークの外にある場合、エッジの上限は隣接する面の С上限によって制限されます。 $$\max(n_1 \cdot d, n_2 \cdot d) - r$$ wがアークの外にある場合でも、上限が最大面分離を超える限り、エッジは最大分離軸を形成できます。 エッジ上限分離を見つけるための数学は概念的には単純ですが、注意深い実装は大幅なパフォーマンス向上をもたらす可能性があります。 考慮すべきもう1つのことは、エッジをカリングすることです。