サンプルスクリーンショット。やはり3Dだとちょっと重たい･･･。
その15 8分木空間分割を最適化する！：サンプルプログラム
衝突判定編3D衝突編その15「8分木空間分割を最適化する！」で説明した内容を踏まえたサンプルプログラムです。実行すると、球形のオブジェクトが出現し画面内で衝突しながら飛び散ります。
サンプルスクリーンショット。やはり3Dだとちょっと重たい･･･。
○ コンパイル方法
必要なファイルはこちらからダウンロードできます(COLSmp_3D_No15.zip)。DirectX9が必要です。ファイルをダウンロードして解凍したら、main.cpp、CollisionAPI.h、SmartPtr.hそしてColTrees.hを空のWin32アプリケーションに追加し、Ball.xとWall.xをプロジェクトフォルダ下にコピーすれば、コンパイルして実行できます。また実行形式も含めておりますので、動作確認だけしたい方はそちらをどうぞ。
実行すると上のような球の衝突がリアルタイムの実行されます。少し重たいのでリリースモードでお楽しみ下さい。終了はESCキーです。環境によってはデフォルトの球の数で余裕がある方もいれば、まともに動かないほどカクカクする人もいるかと思います。球の数はグローバル変数g_SphereNumで変更できます。
○ プログラムのポイント
このプログラムのポイントは衝突･･･ではなくて線形8分木による衝突数の最適化にあります。最適化の度合いは画面左上の「Optimaization」でパーセンテージとして表示されています。上のスクリーンショットの場合8.49%となっています。これは総当り法を100%とした時の最適化衝突回数の割合を表しています。500個の球を総当り法で判定すると約12万回必要になりますが、上の時点ではこれを10,000回くらいに減らしています。
線形8分木関連はすべてColTrees.h内にまとめてあります。このヘッダー内にはOBJECT_FOR_TREEクラス、CCell空間クラスそしてCLiner8TreeManager管理クラスが含まれています。すべてテンプレートクラスです。細かな使用方法は衝突判定編3D衝突編その15「8分木空間分割を最適化する！」にもありますが、まずCLiner8TreeManager::Initメソッドで8分木空間の範囲と分割レベルを決めます。以下に分割レベルと占有メモリのサイズを示します：
CCellクラスのサイズは16バイトですが、線形8分木配列はポインタなので+4で20バイト×空間数です。
Level 空間数 メモリサイズ(kB) 0 1 0.02 1 9 0.18 2 73 1.43 3 585 91.43 4 4681 731.43 5 37449 5851.43 6 299593 46811.43 7 2396745 374491
空間範囲を作成したらCLiner8TreeManager::RegistメソッドでOBJECT_FOR_TREEクラスを登録します。これで空間にオブジェクトが高速配置されます。全部配置したらCLiner8TreeManager::GetAllCollisionListメソッドを呼び出すと衝突対応リストを出力してくれます。後はそれを見て衝突判定をチェックしていけば1回の衝突プロセスが終了します。2回目以降はOBJECT_FOR_TREE::Removeメソッドを呼び出して一度空間からオブジェクトをはずし、位置を変更後に再度登録しなおせば、新しい衝突リストを得る事ができます。
初期化、再登録、リスト出力という流れをつかめば、テンプレート化されているため色々な局面に使いまわせるクラスだと思いますので、お試し下さい。
○ プログラムで遊ぶポイント
8分木空間分割レベル（g_PartitionLevel）を増減させると最適化の度合いが変わるのがわかると思います。あまり分割し過ぎてもメモリを食うだけで大した最適化効率にならない事もわかります。4分木に比べるとレベルに対するメモリの消費が急激なのでレベル5か6くらいが限度かと思います。
このサンプルプログラムは衝突判定もさせていますのでそこそこ遊べます。簡単に触れるパラメータはmain.cppの最初にグローバル変数としてまとめました。球の大きさや初期位置などはメイン関数内の「球オブジェクトの初期位置・速度の設定」というコメント下で触れます。多くは変更しても問題ありませんが、.scaleだけは触らない方が良いです（画像との兼ね合いのため）。
2色の色の球がありますが、これは衝突を見やすくしているだけで意味は特にありません。またあちこちでめり込みが発生しているのですが、これは「1フレームでの2度目の衝突」を無視しているために起こっています。厳密にすればボリュームにめり込まない衝突にもなるのですが、かなり面倒な実装になりここでの主点にならないため省略しております。