衝突検出のためのSIMD

衝突検出のためのSIMD 以前の記事「SIMD Matters」で、接触ソルバーを高速化するためにグラフ彩色から得られた大きな成果について議論しました。このアプローチはBox3Dにも存在します。私はこのアプローチを「ワイドSIMD」と呼ぶのが好きです。その考え方は、複数の作業単位を同時に処理することです。接触ソルバーでは、これは4つの接触点を同時に解決することを意味します。これは、3次元ベクトル（xyz）をSIMDレジスタに入れ、標準的なベクトル演算をSIMD組み込み関数として表現する「ナローSIMD」とは異なります。ナローSIMDは有用かもしれませんが、その利点はそれほど明白ではありません。 3次元では、2次元には存在しないワイドSIMDを使用する機会があります。PEELから移植された凸包パイルベンチマークを考えてみましょう。このベンチマークでは、それぞれ32個の頂点を持つ5120個の凸包を落下させます。Box3Dはボックスを凸包として扱っており、多くのベンチマークでボックスが使用されます。ボックスでのパフォーマンスは良好であり、通常、コストのほとんどはナローフェーズにありません。しかし、32頂点の凸包は別の問題です。これを「ボルダー」と呼びましょう。以下の表は、ボックスとボルダーの凸包の詳細を示しています。 凸包 頂点 面 辺 ボックス 8 6 12 ボルダー 32 59 89 Box3Dは分離軸テスト（Separating Axis Test、SAT）を衝突検出に使用します。SATを使用すると、形状を分離するために使用する最適な特徴を見つけ、重なりを解消するためにどれだけ離す必要があるかを正確に把握できます。さらに、これらの結果を使用して接触法線と接触点を計算します。他の物理エンジンでは、距離アルゴリズムGJKを使用し、拡張ポリトープアルゴリズム（Expanding Polytope Algorithm、EPA）としても知られるオーバーラップフォールバックを使用する場合があります。私は凸包衝突に対してSATを高く評価しています。なぜなら、衝突マージンを必要としないからです。形状は互いに直接接触できます。GJKとEPAの組み合わせは、通常、GJK領域内に留まるために形状をわずかに分離しようとしますが、これはより高速です。これにより、視覚的なギャップが生じる可能性があります。また、EPAは数値的に脆く、EPAが失敗した場合、物理エンジンはフォールバックを必要とすることがよくあります。フォールバックのためのフォールバックです。EPAは基本的に凸包を計算するアルゴリズムであり、入力データは平坦なスライバーになる可能性があります。これは凸包計算にとって困難なシナリオです。したがって、2番目のフォールバックが必要になります。 残念ながら、3次元でのSATは二次的な複雑性を持っています。2つの凸包AとBがある場合、衝突アルゴリズムは、凸包Aの面と凸包Bの頂点、凸包Bの面と凸包Aの頂点、凸包Aの辺と凸包Bの辺をテストする必要があります。最悪の場合、すべての組み合わせを評価する必要があります。 組み合わせ 面-頂点 頂点-面 辺-辺 ボックス-ボックス 6 6 144 ボルダー-ボルダー 59 59 7921 辺-辺の組み合わせの数は二次的に増加します。ガウスマップを使用して辺テストを高速化するトリックがいくつかあります。詳細については、「Improvements to the Separating Axis Test」を参照してください。それにもかかわらず、辺-辺テストは簡単にシミュレーション全体を支配する可能性があります。 では、この辺-辺コードはどのようなものになるでしょうか？基本的なレベルでは、次のようになります。 for (Edge edgeA : hullA.edges) { for (Edge edgeB : hullB.edges) { TestCrossProduct(edgeA, edgeB); } } 各凸包に12個の辺しかない場合、SIMDを使用しても大きな利点はありません。SIMDにはある程度のセットアップ作業が必要だからです。SIMDがうまく機能するには、データを配列構造（Structure of Arrays、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回の実行のベストです。 スレッド スカラー SSE2 AVX2-Lite 1 40706 17337 15762 2 20799 8857 8131 3 13789 5946 5471 4 10324 4509 4084 5 8359 3675 3361 6 6958 3106 2843 7 6006 2697 2477 8 5292 2410 2277 SSE2はスカラーよりも2倍以上高速です！これらのタイミングは、辺-辺テストだけでなく、シミュレーション全体のものであることに注意してください。スカラー列は、接触ソルバーがスカラーモードで実行されていることも示しています。したがって、これはシミュレーションの全体像です。Box3DはSSE2組み込み関数のみを実装しています。Box2DにはAVX2組み込み関数もありますが、AVX2対応CPUを持たないユーザーが驚くほど多くいました。それにもかかわらず、Box3DでAVX2アーキテクチャを有効にするだけで、AVX2-Lite列に示されているように、かなりのパフォーマンス向上が得られます。無料のパフォーマンス向上は素晴らしいことです。将来的には、一度に8つの辺をテストする実際のAVX2実装を試すかもしれません。 このベンチマークは、89個の辺を持つ32頂点の凸包を表しています。頂点数が増えれば、SATは間違いなく処理能力を超えます。幸いなことに、Box3Dには厳格な128辺の制限があります。この制限は、凸包ストレージをコンパクトに保つ（8ビットインデックスと辺あたりの2つのハーフエッジ）ことに関連して、すでに存在していました。やや驚くべきことに、複雑な凸包をメッシュに変換すると、二次的な成長の問題を解決できますが、形状が動的ボディに適さなくなります。 SIMD辺テストがボックス-ボックスのパフォーマンスに影響を与えたかどうか疑問に思うかもしれません。残念ながら、ほとんど影響はありません。この最適化は、複雑な凸包にのみメリットがあるようです。このような凸包は、破壊などのいくつかのシナリオで発生する可能性があります。したがって、Box3Dへの価値ある追加です。最後に、ビデオ比較とフレームタイミングのサイドバイサイドを示します。