概要

シミュレーションの様子

だいぶ昔に行ったビットマップによる衝突判定実験の再検証です。

前提として、この衝突判定は2DSTGに用いることを想定しています。

ビットマップによる衝突判定

2DSTGにおいて、物体の衝突判定を愚直に行うと $O(N^2)$ の探索が必要になります。 そこで、予め物体の衝突判定領域をビットマップに描画しておき、衝突判定時に衝突相手の領域をそのビットマップから取得することで改善を図ります。

ビットマップはGPUを用いて描画します。 GPUを用いることで、高い並列性を得られるだけでなく、テクスチャマッピングが容易になるため、複雑な衝突判定領域も描画できるようになります。 さらに、GPUが非同期に描画を行う都合上、垂直同期を取るのであれば、描画時間が16ミリ秒を超えない限り、その描画時間は無視できます。

描画時間を無視できるということは、衝突判定のアルゴリズムの良し悪しでパフォーマンスが決まるということになります。 RGBAビットマップからは衝突相手の存在性という情報しか得られません。 そのため、正確な領域交差判定を行うためには、自身の領域を全探索する必要があります。 ここで、結局 $O(N^2)$ の計算が発生します。 特に、複雑な領域を探索する場合、自身の領域の内外判定が必要になり、それを嫌うならば各物体が自身の領域のビットマップを持つことになり、何かしらの効率が落ちます。

ということで、conservativityを完全に無視して、自身の領域を座標点あるいは枠線とみなすことでパフォーマンス向上を図ります。 点とみなせば1回のビットマップ参照で衝突判定ができます。 この場合、大きな物体と小さな物体が衝突したとき、小さな物体のみが衝突したと判定されます。 しかし、例えば、自機と敵弾、敵とレーザー、弾消しボムと弾などはこのアルゴリズムを使えます。 また、枠線とみなせば比較的少ない回数のビットマップ参照で衝突判定ができます。 この場合、大きな物体の内部に小さな物体が入り込んだとき、衝突判定が行われません。 しかし、よほど大小差がない限りはそこまで問題にはなりません。 慎重に衝突判定アルゴリズムを決めることが重要です。

結果と考察

GPUに描画を命令するAPIとしてDirect3D12、衝突判定領域として円、ビットマップ参照領域として円周を採用しました。 それぞれ $100, 500, 1000, 2000, 3000, 4000, 5000$ 個の物体を2種類分作り、それぞれ1000フレーム間物理演算を行った結果を次に示します。

結果(全体)

随分と高速化されていることが分かります。 物体の数が5000個あるとき、ビットマップを用いない愚直な衝突判定では1フレームあたり25ミリ秒かかっているのに対し、ビットマップを用いた衝突判定では1.4ミリ秒程度です。

2線の交差点付近を拡大した図を次に示します。

結果(部分)

物体の数が500から750個の間に交差点があります。 このことから、弾が600個程度ある状態でなければ実用的ではないと言うこともできる……というわけではありません。 前述の通り、描画時間は無視できるので、次の図のように見積もれます。

描画時間を除いた結果(部分)

このことから、弾の数が少なくとも十分有用であることがわかります。

雑記

• std::powf()が遅過ぎてビビった。
• std::vector(100)ってreserveではなくてfillなんですねぇ。
• PIXがなければもう少し実装時間がかかっていたことだろう。感謝。
• ブレゼンハムのアルゴリズム。ぶれぜんはむのあるごりずむ。

■