内接球を使用した分離軸テストの高速化
Speeding up the separating axis test using inscribed spheres (box2d.org)
要約
この記事では、3D衝突検出における分離軸テスト(SAT)のパフォーマンスを向上させるための新しい手法について説明しています。特に、凸包(ポリトープ)間の接触判定において、SATはGJKよりもロバストですが計算コストが高いという課題があります。提案手法では、内接球を利用して、各面やエッジペアが達成できる分離の最大値を事前に計算し、不要なテストを枝刈りすることで、SATの計算量を大幅に削減することを目指しています。
全文翻訳
内接球
分離軸テスト(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]Convex Pile
内接球テクニック
2011年に、著名なPierre Terdiman氏がSATを高速化するために内部オブジェクトを使用することを提案しました。主なアイデアは、内接球を使用して、各面および各エッジペアで達成可能な分離の安価な上限を計算することです。ここで説明する作業は、Pierre氏が文書化したものよりもさらに進んでいます。見出しは、ガウス写像のエッジアークを使用して、エッジペアテストに到達する前にエッジを間引くスキームを開発したことです。それに進む前に、2Dを見てウォーミングアップしましょう。
凸多角形と内接円を持つ2Dケースを考えます。
[画像: sat_01]内接円を持つボックス
AとBに内接する2つの円の中心を結ぶベクトルを(d)とします。重要な観察は、ボックス間の分離がこれ以上大きくなることはないということです。
$$|d| - (r_A + r_B)$$
これは、この値を超える分離軸が存在しないことを意味します。これが分離の上限です。次の図は、例としての軸(n)を示しています。実際の分離(\text{sep}(n))は、明らかに上限よりも小さいです。
[画像: sat_01a]例示的な軸
ボックスを削除して円に焦点を当てます。次に、標準的なミンコフスキー等価性を使用して円を結合します。したがって、円と点の間の分離を見ています。
[画像: sat_02]内接円
[画像: sat_03]円と点へのミンコフスキー変換
これらすべては非常に基本的であるように思えます。しかし、Aから出てくる任意の候補単位長分離軸(n)を考えてみましょう。分離の上限は次のようになります。
$$n \cdot d - r$$
ここで、(r = r_A + r_B)です。この上限は、(|d|)を使用した最初の上限よりもタイトであるため優れており、単一のドット積のみを必要とします。多角形B上の法線は、上限で(-d)を使用する必要があることに注意してください。
[画像: sat_04]候補軸 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_05]エスケープ距離
これはローカルサーチテクニックでもありません。SATは本質的に、形状がオーバーラップする場合、非凸最適化問題であるため、ローカルサーチはローカル最大値にはまる可能性があります。内接球テクニックは、依然としてグローバルサーチを実行しています。
では、これはどのように役立つのでしょうか?顔のテストのベースライン分離軸テストは次のようになります。
int bestIndex = -1;
float maxSeparation = -FLT_MAX;
for (int i = 0; i < countA; ++i)
{
// Normal and point for face on polygon A.
Vec nA = nAs[i];
Vec vA = vAs[i];
// Find deepest vertex on polygon B along normal.
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)
{
// Normal and point for face on polygon A.
Vec nA = nAs[i];
// Skip this face if it can't beat the current maximum.
if (Dot(nA, d) - r < maxSeparation)
{
continue;
}
Vec vA = vAs[i];
// Find deepest vertex on polygon B along normal.
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については、(-d)に最も整列した面をシードとしてテストし、ポリトープAからの最大分離を考慮します。
上記で使用される(r)の値は、丸め誤差の問題を防ぐためにわずかに減らす必要があります。相対許容誤差と絶対許容誤差(メートル単位)の組み合わせを使用します。
$$r = r_0 - (0.005 + 0.001 (|d| + r_0))$$
エッジカリング
面テストを高速化するのは良いことですが、問題の核心は、衝突するポリトープに必要な3Dエッジペアテストです。内接球テストを使用して、エッジがペアテストに到達する前に、ポリトープのエッジを完全に除外することができます。これにより、テストされるペアの数を大幅に減らすことができます。
ポリトープのガウス写像は、単位球上の頂点として面を表します。エッジはそれらの頂点を結ぶアークになります。ハルが衝突すると、ミンコフスキー差はそれらのガウス写像を結合します(Bは否定されます)。ポリトープAのアークがポリトープBのアークと交差すると、ガウス写像上に頂点が生成され、これはミンコフスキー差の面を表します。この面は、両方のガウス写像アークの範囲内にある法線を持ちます。
特定のエッジについて、それが生成する任意の分離軸は、そのガウス写像アークのどこかにあることがわかっています。これは、隣接する2つの面の間の法線をスイープすることによって定義されます。下の画像は、エッジのトップダウンビューでのこのアークを示しています。ベクトル(w)は、(n_1)と(n_2)(エッジに垂直)によって張られる平面への(d)の射影です。
[画像: sat_06]エッジのガウスアーク
(w)が面法線の間にある場合、分離の上限は次のようになります。
$$|w| - r$$
この上限が最大面分離を超える場合、このエッジはエッジペアテストの候補となります。(w)がアークの外にある場合、エッジの上限は隣接する面の分離の上限によって制限されます。
$$\max(n_1 \cdot d, n_2 \cdot d) - r$$
(w)がアークの外にある場合でも、上限が最大面分離を超える限り、エッジは最大分離軸を形成できます。
エッジ上限分離を見つけるための数学は概念的には単純ですが、慎重な実装は大幅なパフォーマンス向上をもたらす可能性があります。考慮すべきもう1つの点は、エッジをカリングしても現在の最大分離を更新する必要がないことです。それは、エッジペアが考慮されるときに後で来ます。私たちが望むのは、はい/いいえの結果です。このエッジはエッジステージの候補ですか?
Box3Dコードには、このための多くの詳細なコメントがすでに含まれています。したがって、コードを掘り下げる必要がないように、すべてをここに示します。ハルBをテストするとき、(d)の方向を反転する必要があることに注意してください。
// A hull edge is bounded by two face normals. On the Gauss map the edge becomes an arc between
// those two face normals. An edge can only build the best separating axis if a normal on that arc
// can beat the best separation value seen so far. This function determines if the upper bound
// separation on that arc can possibly beat the current maximum face separation.
//
// This follows the upper bound used for hull faces:
// separation_upper_bound = dot(axis, centerB - centerA) - innerRadiusA - innerRadiusB
//
// Define:
// d = centerB - centerA
//
// Inputs:
// a1 = dot(n1, d)
// a2 = dot(n2, d)
// c = dot(n1, n2)
// bound = maxFaceSeparation + radiusBound
//
// This returns 1 if the edge is a candidate and 0 otherwise.
static inline int b3TestEdgeCandidate( float a1, float a2, float c, float bound )
{
// c = cos(theta), the angle between the normals.
// s = sin(theta)^2 >= 0
float s = 1.0f - c * c;
// This is coincidentally the law of cosines. Break out your protractor.
float t = a1 * a1 + a2 * a2 - 2.0f * a1 * a2 * c;
// Exterior conditions:
// Can either face normal beat the best separation? These cover the case where d
// is outside the arc wedge. Note that d pointing outside the arc wedge does not cull
// this edge. It can still generate the maximum separation (which happens commonly).
int exterior = b3MaxFloat( a1, a2 ) >= bound;
// Project d into the plane that holds both n1 and n2, call that vector w.
// Introduce the coordinates b1 and b2 (these have units of length).
//
// w = b1*n1 + b2*n2
//
// Since w is the projection of d into the plane spanned by n1 and n2:
// dot(n1, w) == dot(n1, d) == a1
// dot(n2, w) == dot(n2, d) == a2
//
// Dot the equation with n1 and n2:
// a1 = b1 + b2*c
// a2 = b1*c + b2
//
// Solve for b1 and b2 using Cramer's Rule
// b1 = (a1 - a2 * c) / s
// b2 = (a2 - a1 * c) / s
//
// s = 1 - c * c is positive, so b1 and b2 must be positive for w to live in
// the arc between n1 and n2.
//
// The peak value of dot(n, d) on the arc is then norm(w):
// dot(w, w) = dot(b1*n1 + b2*n2, d)
// = b1*a1 + b2*a2
// = (a1*a1 - a1*a2*c + a2*a2 - a1*a2*c) / s
// = (a1*a1 + a2*a2 - 2*a1*a2*c) / s
// = t / s
//
// The interior is a candidate if:
// norm(w) >= bound
// sqrt(t / s) >= bound
// If bound < 0 this is always true. Otherwise
// t >= bound^2 * s
//
// Interior conditions:
// b1 and b2 positive (interior arc): a1 >= c * a2 & a2 >= c * a1
// bound <= 0.0: the interior arc is automatically a candidate because it is positive
// s < B3_PARALLEL_TOL : n1 and n2 are nearly parallel so give up and pass the edge to the next stage
// t >= bound * bound * s : bound is positive and the interior normal direction is a candidate
//
// Using bit ops here to avoid branches.
int interior = ( a1 >= c * a2 ) & ( a2 >= c * a1 ) &
( ( bound <= 0.0f ) |
( s < B3_PARALLEL_TOL ) |
( t >= bound * bound * s ) );
return exterior | interior;
}
結果
Box3DのHull Cullingサンプルでは、Convex Pileサンプルのペアのハルに対するカリング結果を示しています。
[画像: hull_culling]Hull culling
各ハルは32個の頂点、59個の面、89個のエッジを持っています。通常、ゲームではより単純なハルで十分ですが、これらのハルはナローフェーズ(以下のベンチマークテーブルのcollide)の優れたストレステストです。
示された構成では、面テストの86%がカリングされ、エッジペアテストの98%がカリングされます。これにより、SATの速度が劇的に向上します。Convex Pileベンチマークはパフォーマンスが約2倍になり、ナローフェーズのパフォーマンスが2倍以上に向上しました。
球状に近い形状以外の形状についても興味があるかと思いますので、64個の頂点を持つ2つの細長い円柱をテストしました。比較的内接球が小さいため、カリングは少なくなります。この場合、エッジペアの76%がカリングされます。これはバックフェイスカリングに似ています。ハルから50%のエッジをカリングできれば、ペアの数は75%削減されます。
[画像: cylinder_cull]Cylinder culling
カリングが完全に失敗するのはいつでしょうか?形状が深く重なっている場合、ほとんど何もカリングされません。深いオーバーラップはゲームではまれであり、通常は短命です。
内接球カリングの有無によるベンチマークデルタを実行しました。これらは徐々に複雑なハルを使用しています。ワッシャーベンチマークはボックスハルでゲインを示しており、単純なハルでのリグレッションはありません。Junkyardは10点の岩形状のハルを使用しており、堅実なゲインを示しています。そして最後に、Convex Pileが最大のゲインを示しています。他のステージを含めて、ベンチマークのノイズレベルを示し、各ステージの相対的なコストを把握できるようにしました。ここでのミリ秒単位のタイミングは、フルランのものです。ワッシャーは1000ステップ、ジャンキヤードは500ステップ、コンベックスパイルは500ステップ実行されます。
| Benchmark | Stage | Before (ms) | After (ms) | Change |
|---|---|---|---|---|
| washer | pairs | 481.2 | 483.5 | +0.5% |
| collide | 2,191.5 | 2,034.8 | -7.1% | |
| solve | 1,892.0 | 1,892.5 | 0.0% | |
| total | 4,573.9 | 4,431.1 | -3.1% | |
| junkyard | pairs | 257.5 | 266.5 | +3.5% |
| collide | 1,699.5 | 1,473.6 | -13.3% | |
| solve | 1,037.2 | 1,031.2 | -0.6% | |
| total | 3,003.9 | 2,779.2 | -7.5% | |
| convex_pile | pairs | 178.0 | 173.7 | -2.4% |
| collide | 2,567.6 | 976.7 | -62.0% | |
| solve | 360.0 | 357.3 | -0.7% | |
| total | 3,109.4 | 1,512.3 | -51.4% |
次に、SATとGJKのパフォーマンスを比較してみましょう。3つの形状の組み合わせ(複雑: 32点、岩: 10点、円柱: 64点)でSATとGJKをベンチマークしました。
[画像: sat_vs_gjk]SAT対GJK
GJKはSATよりも距離をうまく扱いますが、SATはGJKよりもオーバーラップをうまく扱います。そのため、公平な比較のためにベンチマークを慎重に設定しました。各構成は、2番目のハルをランダムに回転および配置し、形状距離を使用して約1cmの距離にスライドさせることによって構築されます。これはBox3Dの投機的バンド内であり、現実的なシナリオです。このレジームでは、SATとGJKには早期アウトはありません。
以下は結果の表です。タイミングは、数千のランダム構成に対する平均マイクロ秒/呼び出しです。SATの場合、これには最大分離軸と分離値を見つけるコストのみが含まれます。GJKの場合、コストには距離と最近接点の計算のみが含まれます。どちらの場合も接触点は計算されません。キャッシュやウォームスタートは使用されません。
| Hull pair | GJK | SAT | SAT (no sphere bound) | SAT / GJK | Sphere bound speedup |
|---|---|---|---|---|---|
| complex / complex | 1.29 | 1.65 | 10.64 | 1.27× | 6.4× |
| complex / rock | 0.98 | 1.01 | 4.37 | 1.03× | 4.3× |
| complex / cylinder | 2.02 | 2.56 | 10.75 | 1.27× | 4.2× |
| rock / rock | 0.53 | 0.44 | 1.66 | 0.84× | 3.7× |
| rock / cylinder | 1.59 | 1.60 | 4.69 | 1.01× | 2.9× |
| cylinder / cylinder | 2.45 | 5.74 | 13.26 | 2.34× | 2.3× |
これは、内接球とSIMD最適化を備えたSATが、最終的にGJKと競争力を持つようになったことを示しています。円柱のような細長い形状はSATにとって依然として課題ですが、Dirk氏には役立つ可能性のあるアイデアがあります(下記参照)。
要約
内接球を使用したエッジカリングは、エッジの多いハルに対してSATを大幅に高速化します。このテクニックはグローバルな最大分離値を提供します。近似ではなく、ローカル最大値にはまることもありません。SATアルゴリズムへの簡単な追加です。数個の小さな関数を使用してこのカリングアプローチをコードに組み込むことで、複雑なハルに対して大きなパフォーマンスゲインを得ることができます。
主なパイプライン要件は、内接球を計算することです。これは最適である必要はありません。Box3Dはハル中心を計算し、次に最も近い面プレーンを見つけて半径を決定します。ハルが構築されている間に(O(N))スキャンするだけです。これは一般的に役立つことが判明しており、すでにCCDに内接球を使用しています。
参考文献
Pierre氏の記事は、内接球テクニックのインスピレーションです。Choiらは、Dirk氏が普及させた高速エッジペアミンコフスキーテストを提供しています。Cairn氏はBox3DでのSIMDエッジペアテストをスケッチしました。最後の3つは、ガウス写像の詳細な説明を提供しています。
- Pierre Terdiman: Faster convex-convex SAT: internal objects
- Choi et al.: Computing the Minimum Directional Distance between Two Convex Polyhedra
- Dirk Gregorius: The Separating Axis Test between Convex Polyhedra
- Cairn Overturf: Improvements to the Separating Axis Test
追加情報
Cairn氏は、微分によって見つかる関数の最大値を使用してエッジの上限を導出することを提案しています。これは上記の幾何学的アプローチとは異なる視点を提供し、より効率的である可能性があります。
Dirk氏は、エッジの上限を計算する際にポリトープ境界を使用することを提案しています。もう一方のポリトープは、依然としてその内接球によって表されます。これは、内接球が比較的小さい細長い形状に対してより良いはずです。