Sweep and Prune

This explanation is currently available in Japanese.

ひとことで

物体の AABB を 1 本の軸（たとえば x 軸）に投影した区間の端点を並べ、左から順に見ていって、重なっている区間の組だけを候補にする広域判定です。区間の始まりに来たら「今開いている区間」と組にし、終わりに来たら閉じます。物体はフレームごとに少ししか動かないので、前のフレームの並びを挿入ソートで直すだけで、ほとんど手間をかけずに並べ替えられるのが強みです。

ゲームでの使いどころ

• 物理エンジンの広域判定：Bullet の 3 軸 SAP、PhysX の Broad Phase SAP など。物体の大きさがばらばらでも使いやすい。
• 横長の世界：横スクロールや、物体が 1 方向に広く散らばる世界では、その方向を軸にすると候補がよく絞れる。
• 重なりの出入りを知らせる：区間が重なり始めた・終わった瞬間がわかるので、トリガー（範囲に入った・出た）のイベントを作りやすい。

しくみ

1. 各物体の AABB の x の区間 $[\min_x, \max_x]$ の端点（始まりと終わり）を、1 本の配列に小さい順に並べます。
2. 配列を先頭から見ていきます。
   • 始まりの端点：今開いている区間（アクティブな物体）すべてと組にして候補に入れ、自分もアクティブに加えます。
   • 終わりの端点：自分をアクティブから外します。
3. 候補の組について、y（と z）でも区間が重なるかを調べ、重なった組を詳細判定へ渡します。

時間的な一貫性：物体の位置はフレームごとに少ししか変わらないので、端点の並びもほとんど変わりません。前のフレームの並びを残しておき、挿入ソートで直すと、交換が必要なのは入れ替わった所だけで、ほぼ $O(N)$ で済みます。交換のたびに、区間の重なりが始まった・終わったこともわかります（増分型 SAP）。

実装のポイント

• 軸の選び方：物体が最も広く散らばっている軸を選ぶと、候補が少なくなります。物体の位置の分散を調べて、フレームごとに軸を選び直す方法もあります。
• 3 軸を同時に：3 本の軸それぞれで並びを保ち、3 軸とも重なった組だけを候補にする方法もあります。
• 端点の値だけ持つ：並べる配列には、端点の値と物体の番号、始まりか終わりかの印だけを入れ、小さくしておくと速くなります。

つまずきやすい点

• 1 軸に物体が集まる：物体が軸の方向に重なって並ぶと（床の上に一列に並ぶなど）、アクティブな区間が多くなり、候補が爆発します。別の軸を選ぶか、格子に切り替えます。
• テレポート：物体が大きく飛ぶと、挿入ソートの交換が大量に発生します。一度に多くの物体が動く場面では、並べ直しを全体のソートに切り替えます。
• 大きな物体：巨大な床のような物体は、ほかのすべての物体と区間が重なります。静的な大きな物体は別に扱います。

デモで試すこと

1. 上の四角い範囲で 30 個の箱が動き回り、その下に、各箱を x 軸に投影した区間が並んでいます。
2. 黄色のスイープ線が左から右へ進み、端点を通過するたびに区間が開いたり閉じたりします。今開いている箱が黄色です。
3. x で重なった組（候補）は青い線、y でも重なった組は赤い線で結ばれます。左下で、全部の組 435 に対して候補がずっと少ないことを確かめてください。
4. 「左から順に見ていく様子を表示」を切ると、毎フレームの結果だけを表示します。「このフレームの並べ替えの交換」が小さいまま保たれることに注目してください。「箱の速さ」を上げると、交換が増えます。