今回はスイープ＆プルーンを用いた当たり判定の高速化手法についてのメモ書きです。

このスイープ＆プルーンは多数のオブジェクト同士の当たり判定回数を減らす方法の一種です。
AABB木を用いた当たり判定高速化とは違い、このスイープ＆プルーンを用いた方法は動的なオブジェクト同士の比較に有効です。
ただし、動的といってもランダムな位置にワープするような場面では不利になり、オブジェクトが徐々に移動する場面において効果を発揮します。

以下のオブジェクト同士の当たり判定を考えます。

ここでまず各オブジェクトのAABBを求めます。

求めたAABBの端点をx,y軸それぞれに投影します。

射影した端点はx,y軸に対しそれぞれ座標値の配列として保持します。
この配列はソートしておきます。
ソートには処理コストがかかりますが、フレーム毎に行う必要はありません。
オブジェクトが徐々に動いていくことを考えると、端点の順序が入れ替わるタイミングは時々です。

ソートした端点の配列には以下のような性質があります。

・オブジェクトAの始点の次に終点が存在したらオブジェクトAは誰とも衝突していない
・オブジェクトAの始点の次に別オブジェクトBの始点または終点が存在したらオブジェクトAとBは衝突している可能性がある

これは図で見たほうが早いと思います。

まず、先の例に挙げた図のx軸についてみてみましょう。
オブジェクト1は始点→終点の順に並んでいるため衝突していません。

オブジェクト2の始点の次にはオブジェクト3の始点があるので、オブジェクト2、3は衝突している可能性があります。

最後のオブジェクト4は始点→終点の順に並んでいるため衝突していません。

続いて、y軸についても同様に見てみましょう。
オブジェクト1の始点の次にオブジェクト4の始点が続いています。

したがって、オブジェクト1と4は衝突している可能性があります。

オブジェクト2の始点の次にオブジェクト3の始点が続いています。

したがって、オブジェクト2と3も衝突している可能性があります。

上記x,y軸で調べた衝突の可能性のあるオブジェクトのペアを列挙します。

・x軸
　オブジェクト2と3
・y軸
　オブジェクト1と4、オブジェクト2と3

このうち、オブジェクト2と3はx,yともに衝突の可能性があることが分かります。
このようにすべての軸で衝突の可能性ありと判定されたオブジェクト同士はAABBが衝突していることになります。
したがって、今回の例ではオブジェクト2と3のAABBが衝突していることになります。

AABBが衝突しているオブジェクトのペアに対しては、詳細な当たり判定を実行して衝突の有無を確かめます。

今回は2次元の例で示しましたが、3次元になるとz軸のチェックが加わり、x,y,z軸すべてで衝突の可能性ありと判定されたオブジェクトのペアは衝突していると判定できます。

■参考書籍
藤澤 誠(2013)『CGのための物理シミュレーションの基礎』マイナビ