当たり判定処理の高速化についてのメモ書きです。

一般に、多数の物体同士との当たり判定を行うにつれ、当たり判定の計算処理が膨大になります。
M個のオブジェクトとN個のオブジェクト同士の当たり判定を行う場合、M×N回の当たり判定が必要になります。
矩形などの単純な図形同士の当たり判定の場合、そこまで計算負荷にはなりませんが、円形のオブジェクトの当たり判定では浮動小数点の乗算が入るため重くなります。

そこで、オブジェクトを大まかな図形で当たり判定を行い、必要ならよりオブジェクトの形状に近い精度の高い図形での当たり判定を行うようにします。
この「大まかな図形」での当たり判定をブロードフェーズ、「精度の高い図形」での当たり判定をナローフェーズと呼びます。

ブロードフェーズに用いる図形は最低限以下の条件を満たす必要があります。

　・計算コストが小さいこと
　・ナローフェーズの図形を包含していること

計算コストが大きければブロードフェーズを使う意味がありません。
ナローフェーズの図形を包含していないと、ナローフェーズで衝突するはずのオブジェクトを「はずれ」と判定してしまう可能性があります。

ブロードフェーズには正方形がよく用いられます。
例えば、以下のような複数の図形から成るオブジェクト同士との当たり判定を例にとります。

オブジェクトAは三角形が3つ、正方形が1つの当たり判定形状を持っています。
オブジェクトBは円形が5つの当たり判定形状を持っています。

フィールドにこの2つのオブジェクトのみ存在している場合はナローフェーズだけでも当たり判定コストは少なくて済みますが、これが1000個とかになった場合は無視できなくなります。

そこで、まず以下の様な矩形を設定します。

そして、この矩形同士の当たり判定を行います。(ブロードフェーズ)

ここで判定結果が「はずれ」なら当たり判定はここで終了です。
判定結果が「当たり」ならナローフェーズの当たり判定を行います。
今回の例では合計(3+1)×5=20回の当たり判定を行う事になります。

ブロードフェーズとナローフェーズを用いた当たり判定は以上のような流れとなります。
結局のところ、フィールド上に存在するオブジェクトの個数が多くなると当たり判定の回数も増加してしまいます。
しかし、例に示したような複雑な形状を持つオブジェクトの当たり判定では大きな効果が見込めます。

オブジェクトの個数が多くなっても判定回数を増やさない方法も存在しますが、それはまた後ほどの機会に書きたいと思います。

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