ソート、スイープ、枝刈り: 衝突検出アルゴリズム (2023)

 (leanrada.com)
3 ポイント 投稿者 GN⁺ 2024-08-15 | 1件のコメント | WhatsAppで共有
  • ゲーム物理で繰り返し行われる衝突検出をボールシミュレーションで解きながら、全ペア検査から sweep-and-prune へ移行する最適化の流れを説明する
  • 単純な方式では n 個のオブジェクトの全候補ペアに intersects() を呼び出すため、約 (n*(n-1))/2 回の検査が必要になり、O(n²) へと急速に増大する
  • AABB の交差テストは複数の不等式と && で構成されており、短絡評価と不等式の推移性を利用すると、衝突の可能性がない候補を早い段階で捨てられる
  • オブジェクトを左境界である minimum x を基準にソートしたあと、ball2.left > ball1.right になった時点で内部ループを break し、それ以降の候補をまとめて除外する
  • ソートのコスト O(n log n) に x 軸の重なり数 m に応じたループコストが加わり、平均的には O(n log n + m) 程度となって、不要な intersects() 呼び出しを大幅に減らせる

ゲーム衝突検出の出発点

  • 衝突検出はビデオゲームプログラミングにおける多くの動作の前提になる
    • キャラクター同士がすり抜けないようにする
    • Goomba が他のオブジェクトにぶつかったときに向きを変える
    • agar.io で大きな細胞が小さな細胞に接触すると食べる
    • 一般的なゲーム物理を処理する
  • 例では剛体ボールシミュレーションを使って、複数の衝突検出アプローチを比較する
  • 範囲は最も単純な方式から sweep-and-prune へ至るアプローチであり、空間分割や空間木の細分化は扱わない

すべてのペアを検査する単純なアプローチ

  • 最も直接的な方法は、すべてのオブジェクトのペアを候補とみなすやり方である
    • 外側のループは各ボールを走査する
    • 内側のループは i + 1 から始め、A-B と B-A のような重複ペアを避ける
    • 各候補ペアに対して intersects(ball1, ball2) を呼び出し、真なら bounce(ball1, ball2) を実行する
  • この検査は各時間ステップごとに繰り返されるため、ボールは衝突した時点で反射処理される
  • オブジェクト数が少ないうちは十分だが、数が増えると検査量が急速に性能ボトルネックになる

O(n²) が生む限界

  • 単純なアルゴリズムは Big O の観点では O(n²) 時間で実行される
  • n 個のボールに対して検査すべきペアはおおよそ (n*(n-1))/2、つまり 0.5n² - 0.5n 個である
    • n = 5 なら 10 ペア
    • n = 10 なら 45 ペア
    • n = 15 なら 105 ペア
    • n = 20 なら 190 ペア
  • すべてのオブジェクトが同時に重なる最悪の場合には、どの衝突検出アルゴリズムでも O(n²) の衝突処理を避けるのは難しい
  • 実際の比較では、最悪ケースよりも平均ケースや最良ケースのほうが実用的である
  • 単純方式は実際の衝突数に関係なく常に Θ(n²) で動作するため、改善の余地が大きい

intersects() 内の繰り返し作業

  • 最適化の出発点は、すべての候補ペアごとに呼ばれる intersects() 関数である
  • 一般的な AABB の交差テストは、各方向の境界を比較する複数の不等式判定で構成される
function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}
  • この判定は 4 つの条件に分かれる
    • object1.left < object2.right
    • object1.right > object2.left
    • object1.top < object2.bottom
    • object1.bottom > object2.top
  • && の短絡評価により、条件が 1 つでも偽なら交差テスト全体は即座に偽になる
  • 複数のテストにまたがって「少なくとも 1 つの条件が偽」である場合を一般化すれば、intersects() 呼び出し自体を減らせる
  • これは、ある軸上で射影が重ならなければ 2 つのオブジェクトは衝突しないという 分離軸定理 と同じ方向の発想である

不等式の推移性で候補を捨てる

  • object1.right > object2.left という 1 つの条件だけを見ても、最適化の余地がある
  • 3 つのオブジェクト A、B、C が水平方向に A-B-C の順で並んでいるとき、次の判定はすべて偽になりうる
A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false
  • A > B が偽で B > C も偽なら、不等式の推移性により A > C も偽だと分かる
  • したがって intersects(A, C) を呼ばなくても、この 2 つのオブジェクトは衝突しないと判断できる
  • この省略はオブジェクトが特定の順序にあるときにだけ適用できるが、オブジェクトのラベルは任意なので、左のオブジェクトを A、中央を B、右を C のように置けばよい
  • オブジェクトをこのような論理的順序に並べる作業こそがソートである

x 軸の最小値を基準にソートする

  • ソート済みリストにすると、不等式の推移性を複数の候補に一度に適用できる
  • 一般的な高速ソートアルゴリズムは O(n log n) であり、O(n²) より小さい
  • オブジェクトは点ではなく x 軸上の区間を占めるため、x 位置でソートするには左境界である minimum x を使う
  • 単純な O(n²) コードに必要な変更は 2 つだけである
    • ループの前に sortByLeft(balls) でボールを左境界の x 座標でソートする
    • 内部ループで ball2.left > ball1.right なら break する
// sort by min x
sortByLeft(balls);

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];

    // stop when too far away
    if (ball2.left > ball1.right) break;

    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • ソート関数は左境界の差を基準に配列を並べ替える
function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

break が安全な理由

  • リストがソートされていれば、任意の正の整数 c に対して次の関係が成り立つ
balls[j + c].left >= balls[j].left
  • 現在の候補が次の条件を満たすなら、現在のペアは x 軸上で重なっていない
balls[j].left > ball1.right
  • 2 つの不等式を合わせると、次の関係になる
balls[j + c].left >= balls[j].left > ball1.right
  • 推移性により balls[j + c].left > ball1.right も真なので、それ以降のすべての候補も現在の ball1 と x 軸上で重ならない
  • 現在の ball2 が ball1 ともはや重ならない時点で、内部ループの残りの候補は検査せず中断できる
  • この最適化により、実際の intersects() 呼び出しは x 軸上で重なるペアに限定される

改善された時間計算量

  • ソートのコストは mergesort や quicksort のような高速ソートを前提に O(n log n) の項を追加する
  • 早期中断のある二重ループは、平均的には O(n + m) と見なせる
    • m は x 軸上で重なる総数である
    • 最良の場合、重なりがなければ不要な処理はほとんどなく、O(n) に近い
    • 最悪の場合には、依然として O(n²) まで悪化しうる
  • 平均ケースは、オブジェクトがだいたい均等に分布し、各オブジェクトごとの衝突数が少数にとどまる状況を想定している
  • 全体の計算量は、ソートとループを合わせて O(n log n + m) である
  • 単純方式より改善する理由は 2 つある
    • n log n は n² より小さい
    • 重なり数 m に一部依存するため、必要以上に多くを処理しない

実装負荷と次の段階

  • このソートベースの方式は、コード変更が少ない一方で実行時間性能を大きく改善できるバランスのよい手法である
  • 比較デモでは、グローバルな全ペア検査よりもソートベースのペア検査のほうが、1 フレームあたりの intersects() テスト数を目に見えて減らす
  • ソートのコストは比較の可視化には表示されないが、交差テストが十分に高コストであることを前提としている
  • さらに発展した方式と最終コードは Part 2 へ続く

関連記事

1件のコメント

 
GN⁺ 2024-08-15
Hacker News のコメント

  • この手法で興味深いのは、筆者が最高の性能を得るためにマージソート／クイックソートのような「速い」ソートアルゴリズムを使うよう提案している点です。
    しかし実際には、より「悪い」ソートアルゴリズムである挿入ソートのほうが速い場合があります。
    衝突検出システム内のオブジェクトは、フレーム間では通常少しずつしか動かないため、前フレームのほぼソート済みのリストを維持できます。
    こうしたリストでは挿入ソートが O(n) に近づく一方、クイックソートは O(n^2) に近づくことがあります。

    • 筆者は Part 2 でほぼ同じ内容を扱っています。
      「ソート段階は分析上はボトルネックだが、ほとんどの場合ソートは何もしていない。リストはほぼ常に前フレームですでにソートされている。ソート順が崩れても、通常は数回の交換だけで再びソートされる。ここに挿入ソートの動作例がある」といった形で説明しています。
    • 各ステップでソートする代わりに、インデックス構造を少し緩くして、オブジェクトが epsilon 未満しか動いていないときの衝突候補を拾う方法もあります。
      たとえば球の半径を epsilon だけ大きくすれば可能です。
      球が epsilon だけ動いていない間は、インデックスを再計算する必要はありません。
      再計算が必要になったときの遅延ピークを避けるには、毎フレーム 10% ずつソートして、遅れたインデックスを作ることができます。
      10 フレーム後には、10 フレーム前の位置から epsilon 以内にある限り有効なインデックスが得られます。
    • ほぼソート済みのリストでクイックソートが O(n^2) になるのは、ピボットを本当に悪く選んだ場合だけです。
      ピボットをランダムに選べば O(n log n) になり、すでにほぼソート済みのリストなら、リスト中央の要素をピボットに選ぶこともできます。
      ただし最適なピボットを使っても、クイックソートは最良の場合でも O(n log n) です。
      データ内の昇順／降順の run の個数を k とすると、O(n log k) で動作する単純なマージソートの変種があります。
      Haskell 標準ライブラリのデフォルトの sort はその種のアルゴリズムを使っており、Python もそうだと思います。

  • 記事の構成がとてもよかったです。
    90 年代後半から何らかの形でゲーム開発をしてきて、今ではこの大半がエンジンに抽象化されていますが、複雑なシステムシミュレーションがどう動くのかを理解するには、こうした内容が不可欠です。
    筆者が読みやすい記事にしてくれたことに感謝します。

  • 連続衝突検出については、このドキュメントをいつも高く評価しています: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
    ライブラリ自体も性能面で優れています。
    ただし最適化がかなり入っているので、統合するのは少し難しいです。

  • 「この素朴なアルゴリズムはビッグオー表記で O(n2) 時間で実行される」というのが正しいのか気になります。
    外側のループ i は n - 1 回回り、内側のループ j は i + 1 から始まるので、だんだん n - 1 より少なく回るのではないかと思いました。
    専攻者ではないので、n が大きいときにはおおよそ O(n2) と同じと見るのか、それとも見た目どおりそれより小さいのかが気になります。

    • 正確に n^2 ではありません。
      i 番目の要素について比較を (n - i - 1) 回行い、0 始まりのインデックスなら総比較回数は (n - 1) * n / 2 になります。
      https://en.wikipedia.org/wiki/Triangular_number を参照してください。
      結局、ビッグオー解析では違いはありません。
      ビッグオーは n が無限大へ向かうときの振る舞いを表し、このとき二次の項が支配的になるためです。
    • 内側のループを j = i + 1 から始める「最適化」は、すべてのオブジェクトの組を 2 回ずつ検査しないためのものです。
      オブジェクトを自分自身と検査しないようにする効果もあります。
      すべての組を 1 回ずつ検査するので、このアルゴリズムは O(n^2) です。
    • ビッグオーは、入力サイズ、つまり入力リストの長さに応じて抽象的な演算数がどのようにスケールするかを示す複雑度の分類にすぎません。
      一般に、演算数を入力サイズの関数として解析的に表せるなら、ビッグオーでは最大の項だけを残し、すべての係数を捨てます。
      アルゴリズムの実際の性能を必ずしも説明するものではありません。
      20n2^+5n と 2n^2 + 9001n はどちらも O(n^2) です。
    • 1 から n までの和なので n(n+1)/2 になります。
      ビッグオー表記ではすべての係数と、より遅く増加する項を無視するため、二次複雑度に簡約されます。
    • ビッグオーは微積分の極限計算に似たものと考えると、より理解しやすいかもしれません。

  • イラストの使い方がよく、適切な使い方に見えました。
    インタラクティブなイラストがある記事は、格好いいデモを大量に入れるための口実のように感じられることがあり、TED トークのように中身より装飾が多い場合があります。
    しかしこの記事では、イラストが内容を食っていませんでした。

  • Part 2: https://leanrada.com/notes/sweep-and-prune-2/
    ほかの良い記事も読む価値があります: https://leanrada.com/

  • ずっと前に似たようなことをしたことがありますが、ソートの代わりに各方向ごとのインデックスリストを維持し、オブジェクトが自分自身で順序を整えるようにしていました。
    たとえば objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge のような 4 つのリストがあります。
    オブジェクトが水平方向に動くと、leftEdge と rightEdge の配列で自分のインデックスを更新します。
    動いたとしても、たいていは 1〜2 個のインデックスを交換するだけで十分だからです。

    • その方式は、ほとんど静的なシーンに有用そうです。
      動的な要素が多くなるほど、グラフを作り直す方式のほうがよさそうに見えます。

  • 初めて見る手法ですが、潜在的な衝突体の数を減らすために四分木のようなものを使うのと似ていませんか？

    • そのとおりです。
      ただしリアルタイムレンダリングよりも、オフラインレンダリングでk-d ツリーのようなものを目にすることのほうが多いです。

  • 「空間分割や空間木の細分化のような他のアプローチは扱わない」という部分が気になります。
    この記事のアルゴリズムが、一般に空間分割／空間木の細分化より速いのか知っている人はいますか？
    ずっと前に空間木タイプのアプローチを使ったことがあり、素朴に見るとかなり良い方法に思えましたが、当時はインターネット以前の 80 年代だったので、他の人が使っていたアルゴリズムを調べたり比較したりしたことはありません。

    • 空間分割や木の細分化などを維持する複雑さは、特に動くオブジェクトが非常に多い場合、大きな負担になり得ます。
      単一のエンティティリスト 1 つや、各セルがエンティティリストを持つ 256x256 のセルグリッドを管理するほうが、オブジェクトが動くたびにすべての木の不変条件を維持しなければならない複雑な分割構造より、実装・デバッグ・最適化がはるかに簡単です。
      DOOM や Quake の時代には、このような基盤システムの性能が今よりずっと重要だったため、エンジン作者が非常に複雑な分割システムを作ることにはより妥当性があったのでしょう。
      現代の CPU はソート済み配列を走査するのが非常に得意で、パイプライン処理のため、連結リストや木をたどる処理は相対的に昔ほど有利ではありません。
      CPU 時間は、エンティティリストの管理よりも AI やレンダリングのような部分に多く使われるようになっています。