HN 日本語サマリー

← 一覧へ戻る
プログラミング

衝突検出のためのSIMD

SIMD for Collision (box2d.org)

108 pointsby birdculture29 コメント

要約

この記事では、物理エンジンBox3Dにおける衝突検出の高速化のためにSIMD(Single Instruction, Multiple Data)技術、特に「ワイドSIMD」がどのように活用されているかを解説しています。複雑な形状(例: 32頂点の凸包)の衝突判定におけるエッジ間のテストで、SIMDを用いることで大幅なパフォーマンス向上が見られることを、ベンチマーク結果を交えて示しています。この最適化は、特に複雑な形状の衝突検出において効果的であり、Box3Dの性能向上に貢献しています。

全文翻訳

SIMDによる衝突判定

以前の投稿「SIMD Matters」では、コンタクトソルバーを高速化するためにグラフ彩色から得られた大きな成果について議論しました。このアプローチはBox3Dにも存在します。私はこのアプローチを「ワイドSIMD」と呼ぶのが好きです。その考え方は、複数のワークユニットを同時に処理することです。コンタクトソルバーでは、これは4つのコンタクトポイントを同時に解くことを意味します。

これは、「ナローSIMD」とは異なります。ナローSIMDでは、3次元ベクトル(xyz)がSIMDレジスタに格納され、標準的なベクトル演算がSIMDイントリンシックとして表現されます。ナローSIMDは有用ですが、その恩恵はそれほど明白ではありません。

3Dには、2Dには存在しない、ワイドSIMDを使用する機会があります。PEELから移植された凸包ベンチマークを考えてみましょう。このベンチマークは、それぞれ32個の頂点を持つ5120個の凸包を落下させます。

[画像: Convex Pile]

Box3Dはボックスを凸包として扱っており、多くのベンチマークでボックスが使用されます。ボックスでのパフォーマンスは良好であり、通常、コストのほとんどはナローフェーズにありません。しかし、32頂点の凸包は別物です。これを「円石(boulder)」と呼びましょう。下の表は、ボックスと円石の凸包の詳細を示しています。

凸包頂点数面数辺数
ボックス8612
円石325989

Box3Dは分離軸テスト(Separating Axis Test、SAT)を衝突検出に使用します。これはSATと略されます。SATを使用すると、形状を押し離すために使用する最適な特徴を見つけ、さらにそれらをどれだけ離す必要があるかを正確に計算して、重なりを解消できます。さらに、これらの結果を使用して、コンタクト法線とコンタクトポイントを計算します。

他の物理エンジンは、距離アルゴリズムGJKを、Expanding Polytope Algorithm(EPAとしても知られる)のようなオーバーラップフォールバックと組み合わせて使用する場合があります。

私は凸包衝突におけるSATのファンです。なぜなら、衝突マージンを必要としないからです。形状は互いに直接接することができます。GJKとEPAの組み合わせは、通常、GJK領域に留まるように形状をわずかに分離しようとしますが、これはより高速です。これにより、視覚的な隙間が生じることがあります。また、EPAは数値的に脆くなる可能性があり、多くの場合、物理エンジンはEPAが失敗した場合のフォールバックが必要になります。フォールバックのためのフォールバックです。EPAは基本的に凸包を計算するアルゴリズムであり、入力データは平坦なスライバーになる可能性があります。これは凸包計算にとって困難なシナリオです。したがって、2番目のフォールバックが必要になります。

残念ながら、3DにおけるSATは二次的な複雑性を持っています。2つの凸包AとBがあるとすると、衝突アルゴリズムは凸包Aの面を凸包Bの頂点に対して、凸包Bの面を凸包Aの頂点に対して、そして凸包Aの辺を凸包Bの辺に対してテストする必要があります。最悪の場合、すべての組み合わせを評価する必要があります。

組み合わせ面-頂点頂点-面辺-辺
ボックス-ボックス66144
円石-円石59597921

辺-辺の組み合わせの数は二次的に増加します。ガウス写像を使用して、辺-辺テストを高速化するトリックがいくつかあります。詳細については、Improvements to the Separating Axis Testを参照してください。それにもかかわらず、辺-辺テストは、シミュレーション全体を容易に支配する可能性があります。

では、この辺-辺コードはどのようになっているのでしょうか?基本的なレベルでは、次のようになります。

for (Edge edgeA : hullA.edges)
{
    for (Edge edgeB : hullB.edges)
    {
        TestCrossProduct(edgeA, edgeB);
    }
}

各凸包に12個の辺しかない場合、SIMDのセットアップにはある程度の作業が必要なため、これに対するSIMD処理は大きなメリットにはなりません。SIMDがうまく機能するためには、データが構造化配列(SoA)形式である必要があります。

各凸包に89個の辺がある場合、状況は劇的に変わります。7921回のTestCrossProduct呼び出しがあります。ワイドSIMDを使用すると、hullAの1つの辺をhullBの4つの辺と同時にテストできます。これは次のようなものになります。

for (Edge edgeA : hullA.edges)
{
    for (EdgeWide edgeWideB : hullB.edgesWide)
    {
        TestCrossProductWide(edgeA, edgeWideB);
    }
}

このスニペットには多くの隠れた詳細があり、興味のある方はBox3Dのコードを参照してください。しかし、私は質問に答えるためにここにいます。衝突検出のためにSIMDを気にかけるべきでしょうか?さて、結果があります!これらは、500ステップの実行にかかった総ミリ秒数を示す、凸包ベンチマークの結果です。CPUを4.42GHzに固定したAMD 7950xで、1から8スレッドをテストしました。結果は4回の実行のベストです。

スレッド数スカラーSSE2AVX2-Lite
1407061733715762
22079988578131
31378959465471
41032445094084
5835936753361
6695831062843
7600626972477
8529224102277

SSE2はスカラーよりも2倍以上高速です!これらのタイミングは、辺-辺テストだけでなく、シミュレーション全体のものであることに注意してください。スカラー列は、コンタクトソルバーがスカラーモードで実行されていることも示しています。したがって、これはシミュレーションの全体像です。

Box3DはSSE2イントリンシックのみを実装しています。Box2DではAVX2イントリンシックも持っていますが、AVX2対応CPUを持たないユーザーが驚くほど多くいました。それにもかかわらず、Box3DでAVX2アーキテクチャを有効にするだけで、AVX2-Lite列が示すように、かなりのパフォーマンス向上が得られます。無料のパフォーマンス向上は素晴らしいことです。将来的には、8つの辺を同時にテストする、実際のAVX2実装を試すかもしれません。

このベンチマークは、32頂点の凸包と89個の辺を表しています。頂点数が増加すると、SATは間違いなく処理能力を超えてしまうでしょう。幸いなことに、Box3Dには厳格な128辺の制限があります。この制限は、凸包ストレージをコンパクトに保つ(8ビットインデックスと各辺につき2つのハーフエッジ)ために既に存在していました。やや驚くべきことに、複雑な凸包をメッシュに変換することで二次的な成長問題は解決できますが、形状が動的なボディには不向きになります。

SIMD辺テストがボックス-ボックスのパフォーマンスに影響を与えたかどうか疑問に思うかもしれません。残念ながら、ほとんど影響はありません。この最適化は、複雑な凸包にのみメリットがあるようです。このような凸包は、破壊などのいくつかのシナリオで発生する可能性があります。したがって、Box3Dへの価値ある追加です。

最後に、ビデオ比較とフレームタイミングのサイドバイサイドを示します。

[画像: Frame Timings]