その８ 4分木空間分割を最適化する！

2D衝突編
その８ 4分木空間分割を最適化する！（理屈編）

　ゲーム空間に置いたオブジェクトを総当りで衝突判定する事ははっきりと非効率だと言えます。ちょっと計算してみましょう。60FPSのゲームの1フリップ約16.6ミリ秒の内衝突判定に10%の時間余裕（1.66ミリ秒）を与えられたとします。もし1000回の衝突判定に1ミリ秒かかるなら（1000回/msec）、判定回数は1660回以下に抑えないと間に合いません。総当りだとこれは58オブジェクトくらいで限界です。判定時間が200回/msecならオブジェクトはたった18個で限界。これはどう考えても節約が無いとゲームになりません。

　オブジェクトの全ての位置が決まった時、自分とぶつかる可能性があるのは自分の周りのオブジェクトだけです。遠い所にある物は判定する必要すらありません。そこで「空間をある程度制限してその中にいるオブジェクトとだけ衝突判定をしよう」と考えられたのが空間分割（Spatial Partitioning）です。その中でも2Dの空間を分割する方法の典型か4分木空間分割（Quaternary Spatial Partitioning）です。

　4分木分割の理屈は非常に簡単です。まず空間を正方形（長方形でももちろん可能）とします。衝突対象のオブジェクトはこの空間内に置かれます。この一番大きな空間をルート空間と呼んでおきます。次に、空間を上下左右に4分割し（下図参照）、ルート空間に空間オブジェクトとして登録します。もしその分割線をオブジェクトがまたいでいなければ、オブジェクトは分割されたより小さい空間内にあることがわかります。そこで、その小空間をさらに4分割して同様の登録とチェックを繰り返します。こうしてオブジェクトが分割線をまたぐか、予め定めている分割段階（Partiton Level）に達したら分割を終了します。

　衝突に関して、上の図では一番大きな球と右半分の空間にあるオブジェクトとは空間が異なるので衝突しないことがこの段階でもうわかっています。ですからこの衝突チェックは行いません。一方真ん中の境界線をまたいでいる小さな球は、他の3つとの衝突チェックが必要になります。それでも、総当りで6回の判定が、上の場合は3回と半分に減っています。これはオブジェクトの数が多くなるほどより効果的になります。

　4分木の理屈は以上のように簡単なのですが、いざこの通りにまともに組んでみると、これが激烈に『遅い』ということもすぐにわかります。衝突判定が遅いということではなく、空間にオブジェクトを適切に登録する事、また動いているオブジェクトについては登録削除と再登録をする、これがかなりの手間になるんです。

　本当に何も考えていない場合についてですが、適切な分割空間にオブジェクトを登録する時には樹状なのでo(logs)レベルの手数がかかります。sは分割空間の総数です。動いているオブジェクトの位置を変更する時には、空間内のそれの検索が必要です。これは線形検索となり平均o(s/2)かかります。取り除くのはo(1)で出来ますが、再登録にまたo(logs)かかります。これを全オブジェクトに対して行うと平均でおよそo(n*s/2+nlogs)となります。これは空間の数をs=500くらい、オブジェクトをn=100個とした場合、毎回平均25000回強の力技検索が必要である事を示しています。これでは全然駄目なわけです。

　衝突判定回数を劇的に減らす4分木はパフォーマンス向上に必要です。でもまともに考えると遅い。では4分木をどう最適化すれば良いのか？この章ではその理屈をじっくりと検討してみます。本章で試行錯誤した4分木空間分裂の実装方法については次章に回します。

① オブジェクトが登録されている空間にo(1)でアクセスする

　まともに実装した中で最も遅いのは、木の中からオブジェクトを探す部分です。木のどこにあるかわからないので、ルート空間から丹念に探していくしかありません。これは大変質の悪い線形検索です。

　「木の中からオブジェクトを探す」という考え方に固執してしまうと、どれだけ頑張ってもo(logs)レベルの検索以下にはできません。これ以上の速度o(1)を期待するには、オブジェクトが空間を知っている状態、つまりオブジェクト→空間のハッシュテーブルを作成するしかありません。これは、次のような構造体を設けると実はあっさり実現できます：

4分木に登録される構造体（叩き台）

class CCell; // クラス宣言が必要です tmplate< class T > struct OBJECT_FOR_TREE { CCell *m_pCell; // 登録されている小空間 T *m_pObject; // 任意オブジェクトへのポインタ };

　CCellというのが空間オブジェクトで、m_pObjectが登録するT型のオブジェクトへのポインタです。テンプレートにするのは登録されるオブジェクトが何かわからないためです。逆にこうしておくと分木を使いまわせます。4分木にはオブジェクトではなくてこの構造体を登録することになります。

② オブジェクトの空間登録をo(1)で行う

　オブジェクトを包んだOBJECT_FOR_TREE構造体を木の中に素直に登録するとo(logs)レベルの手間がかかります（sは空間の数）。具体的には、まずルートとなる一番大きな空間の境界線にオブジェクトがまたがっているかををチェックします。もし線をまたいでいるなら、このオブジェクトはルート空間に所属します。またいでいない場合、それを包んでいる小さな空間にレベルを落とします。小空間でも同じ事を繰り返し、オブジェクトを完全に包む一番小さな空間を探していきます：

　「logなら割といいんじゃ？」と思うかもしれません。しかし、1つの空間に所属するか否かを検討するには、オブジェクトと境界線の交差判定をしなければなりません。交差していないとなると今度は4つある空間のどこに所属するかの検討です。これは難しい事はありませんが手間と手数はかかります。メモリの制約などから小空間の分割回数を7～8回くらいにしたとしても、一番小さなオブジェクトはこの作業を最大8回繰り返す事になります。さらにオブジェクトが動いている場合はそれを全オブジェクトで毎回行う必要があり、その作業は十分に体感できるほど遅くなります。

　この節ではこの登録作業をo(1)にしようと目論見ます。つまり、オブジェクトの境界範囲から空間をズバッと指定するハッシュを作ろうというわけです。これは可能なんです！その準備として、まずは「モートン順序」からお話を始めます。

○ モートン順序

　ルート空間は言わずもがなで1つしかありません。それを4分割した親空間には、空間が4つ存在します。さらに親空間1つ1つを4分割すると、子空間が16個、同様な分割で孫空間は64個となります。

　今これら各レベルでの空間に、0から始まる番号を次のように振ります：

　意味深な「Z」が付いていますが、この順序で分割空間に番号を振ることを「モートン序列（モートン順序：Morton Order）」と言います。親空間の1つを分割した子空間も、全く同じように番号を振ります。孫空間も同様です。ルールはそれほど難しくありません。でも、これを見た誰しもが「何でこんな番号の振り方をするのよ？」と疑問に思うと思います。もちろん、私もそう思いました。しかし、この振り方は実に理にかなっているんです。

○ モートン順序にならんだ空間は上位空間の情報を持つ

　この並びの本質は、ある空間番号を見るだけでどの上位空間に所属しているかがわかってしまう点にあります。例えば、上の孫空間の中央下方にある「45番」の空間に注目して下さい。この空間の上位空間のモートン順序は「親空間の2番（2番）、その親空間内の子空間の3番（11番）、子内孫空間の1番（45番）」となっています。下の図で確認してみて下さい：

(それぞれモートン順序で考えてください）

　ここで孫空間45番を2進数で表現してみます：

このように、数値を2つずつに区切って10進数に直すと、上位にある子や親の番号がそのまま出現します！これはどの孫空間番号でも、それどころかどの空間分割レベルであっても引き継がれる性質であり、所属空間を判定するのに持って来いなんです。

○ 点の座標値から所属するモートン空間番号を出す

　上の45番の2bitずつの情報。これは親や子空間の軸の情報も含んでいます。例えば親空間のビット値である「10 (2番)」。この1bit目の0はX軸の情報です。具体的には「X軸で見ると原点の左側にある」という情報を含んでいます。2bit目はY軸情報で、「Y軸は原点の下にある」となっています。ここから45番の空間は親空間単位で見れば左下(2番)にあると判断できるわけです。同じ事は子空間でも確認できます。

　ここから、空間内の点がどの空間番号に属するかを叩き出す事ができます。例として、今ルート空間の辺の長さを100として、孫空間を対象とし点（48,80)の空間番号を算出してみます。

　まず孫空間を構成する小空間の辺の長さ（単位長）を求めます。これはU=100/2³で算出できますね。この単位距離Uで点の座標を割り算すると(3.84, 6.4)となります。この座標をint型でキャストすると、小数部分が切り捨てられて(3, 6)となります。この整数値は「点(48, 80)は64分割されている孫空間の左から3番目、上から6番目に位置する」という事を意味しています。この位置は、実は先ほどの45番の空間に当たります。

　(3, 6)という十進数表現された位置を2進数に変換すると（011, 110）です（3桁あるのは分割回数が3回であるところから来ています）。この2進数と先ほどの45の2進数表示と見比べてみます：

　2bit単位に区切った1bit目がX軸の3に、2bit目が6に対応するという大変にすばらしい関係になっているのがわかります。つまり、先ほどの簡単な変換で求めた各軸ごとの空間番数さえわかれば、上のようにビット値をミックスさせる事で所属する空間をビシッと吐き出す事ができるわけです。

　これを実現するために、ビットを1つ飛びに変換する関数を作ってみます。統一的に扱えるように、最大16bitの数値で考えてみます。1つ飛びにする方法は単純です。具体的な変換の流れを見てみましょう：

　上が入力情報で右16bitが有効です。これを一番下の状態にする過程をここでは示しています。最初の数nを左に8bitシフトして、元の数字とORします。すると、真ん中の状態になります。「*」は任意のビット値ですが、ここは必要無いのでマスクをかませると、一番下のように8ビット飛びに分かれます。これと全く同じような作業を繰り返します。今度は下の結果を4ビットだけ左にずらし、マスクをかけると4bit飛びになります。さらに2bitシフトしてマスク、最後に1bitずらしてマスクすると、1bit飛びの32ビット数値ができあがります。これを行う関数がこちらです：

// ビット分割関数

DWORD BitSeparate32( DWORD n ) { n = (n|(n<<8)) & 0x00ff00ff; n = (n|(n<<4)) & 0x0f0f0f0f; n = (n|(n<<2)) & 0x33333333; return (n|(n<<1)) & 0x55555555; }

この基本的な関数を使い2D空間のモートン番号を算出する関数を作ります：

// 2D空間のモートン番号を算出

DWORD Get2DMortonNumber( WORD x, WORD y ) { return (BitSeparate32(x) | (BitSeparate32(y)<<1)); }

この関数にx=3、y=6を渡すと、45がちゃんとお目見えします(^-^)。これで点の座標からその点が所属する空間を一発で出せるようになりました。

○ オブジェクトの所属空間番号を算出する

　点の所属空間がわかって喜んでいてはいけません。私たちが空間に入れたいのは点ではなくてボリュームのあるオブジェクト、つまり縦横の大きさがある境界図形です。衝突をざっくり判定するのに適している境界図形は「境界円」か「AABB（軸並行境界ボックス）」です。以下で説明する所属空間判定アルゴリズムもこれらの境界図形を対象としています。

　まず、登録時に境界図形のAABBの左上と右下点の所属空間番号を算出します。これは、先ほどの点の座標→空間番号変換関数を使えば瞬時にわかります：

上の例だと左上は19番、右下は31番に含まれています。ここからが面白いところで、色々と試行錯誤し、またJagoon様からのご指摘によって修正されたうれしい法則です。右下の空間番号31と左上空間番号19の排他的論理和を取ると12となります。この12を2進数で表現するとこうなります：

実は、境界図形の所属する分割レベルはこの排他的論理和の結果ビットが0じゃない最上位の区切りに表現されます。上の例だと青色で示した区切りが[11]となっています。所属空間は、上の例のように一番下の区切りを一つ上のレベル（ここでは子になります）、そこから親、ルートと空間レベルを上げていきます。[11]のビットはこの法則に従うと「親空間に所属」と判断されます。

　排他的論理和の結果から空間レベルがわかったら、次は右下の空間番号31（もしくは19）に注目します。だいぶ前の説明になってしまいましたが、モートン空間番号は所属する親や子の空間番号を全部含んでいるのでした。31番の親は5bit目と6bit目（一番左）の「01」、すなわち1番です。ここから、この境界図形は「親空間の1番に所属する」と結論付けられます。

　これをプログラムで表現するのは簡単で、31番を右に4つシフトさせれば良いだけです。「4右シフト」をどう導くかは次の対応をご覧下さい：

　排他的論理和の結果を右から2つずつ見て行きます。0ならば捨て、0じゃ無ければそのシフト数を採用します。これをルート空間まで繰り返し、最後に採用されたシフト数を採択します。上の場合だと、3,4bit目が有効なので4右シフトとなります。これは空間がもっと細かくても同じです。ここで求めたシフト数分だけ右下の番号を右シフトすれば所属番号がビシッと出ます。

　一応もう1問だけやっておきます。境界図形の左上を44番、右下を47番とします。先に答えを言いますと、この境界図形は子空間の11番に所属します。47^44=3です。この2進数は「00|00|11」ですね。つまり子空間所属である事がわかります。シフト数は2です。右下47を右に2だけシフトすると「10|11」。これは、11番ですよね。つまり子空間の11番が導けたわけです。

　くどいのですがもう一問。境界図形の左上は15番、右下が60番とします。15^60=51（排他的論理和はどちらを左辺にしてもOK）。2進数表現は「11|00|11」。最上位の区切りを採用するというルールだったので、ここは一番左の11を採用します。これは「ルート空間所属」です。この段階でもう終了しても良いのですが、一応シフト数6で60番を右シフトすると、やっぱり0になります。ルート空間所属で決定です。もうこれで計算手順はばっちりでしょう。

○ 線形4分木でアクセスを高速化

　ここまでの4分木は、いわゆる樹状でしたが、これは末端の空間にアクセスするには不便過ぎました。そこで、ルート空間から末端の空間まで、1本の線形配列に並べてしまうことにします：

このように線形配列に直した4分木を線形4分木（Liner Quaternary Tree）と言います。これでルートから辿らなくても要素番号さえ指定すればo(1)レベルでどの空間にでもアクセスできます。

　今境界図形の所属レベルとその空間番号はビシッと算出できています。ただ、線形4分木はルート空間から一本に並べていますので、通し番号になっています。その対応が下の図です：

　上は通し番号（要素番号）、下は空間レベルとそのレベル内の通し番号です。先ほど浴びるほどやったビット計算で出てくるのは下の番号と空間レベルLです。

　下の番号を上の要素番号にする法則は簡単です。例えば、ビット計算の結果空間レベルL=2（子空間）の11番に所属する事がわかったとしましょう。それに対応する要素番号は16です。上の要素番号で子空間の最初は5から始まっていますね。ですから11+5=16で変換ができます。つまり結局のところ、「レベルLの最初の要素番号は何か？」がわかればいいだけなんです。

　足し算した「5」という数は、当たり前ですがL=0（ルート空間）とL=1（親空間）の空間の数の合計です。ではL=3とかL=4になると足す数はいくつになるのか？これは、高校の時にきっと皆さん習っている「等比級数の和」を使うと求まります。証明はさて置き、足す数を求める一般式は以下の通りです：

L=2を入れると確かに5になりますし、L=3だと21、L=4だと85である事がわかります。この足す数は固定的ですから、プログラムに埋め込んでもきっとかまいません。これで、ある境界図形をそれが所属する線形4分木要素番号にダイレクトに変換することができてしまいました！これは空間をはみ出さなければどのような大きさのオブジェクトでもo(1)レベルで空間に所属できます！！

③ 動くオブジェクトの空間切り替えをo(1)で行う

　ここまでで1つのオブジェクトが所属する空間へo(1)レベルで登録できるようになりました。また、OBJECT_FOR_TREE構造体を見れば、所属した空間へもo(1)でアクセスできます。これができると、空間内を盛んに動いているオブジェクトの所属する空間番号の切り替えもo(1)でできるようになります。

　所属空間を切り替えるには、オブジェクトが所属していた空間から自分を切り離し、新しい空間のリストに自身をくっつけます。自分を切り離すというのはリストからはずれるということです。リストを構築するためには、OBJECT_FOR_TREE構造体自体が双方向リンクリスト構造になっている必要があります。そこで、構造体内に次の前後の構造体へのポインタを登録するメンバ変数を付け足します：

4分木に登録される構造体

tmplate< class T > struct OBJECT_FOR_TREE { CCell *m_pCell; // 登録されている小空間 T *m_pObject; // 任意オブジェクトへのポインタ OBJECT_FOR_TREE *m_pPre; // 前の構造体へのポインタ OBJECT_FOR_TREE *m_pNext; // 次の構造体へのポインタ };

空間から外れる時には、自分の前の構造体と次の構造体をくっつけます。空間へ登録する時はそのリンクリストにただ加わるだけです。これらの作業は通常o(1)です。また空間を移り変わる代わりに切り離すだけにすると、これは消去作業になります。

　ここまでアルゴリズムを切り詰めると、4分木空間分割に対する登録・変更・消去がすべてo(1)レベルでできるわけです。いやはや、もうお腹いっぱいです。でも、もう少しあるのですよ(^-^;;;

④ 1回の木巡回で衝突判定を終わらせる

　線形4分木に登録した全オブジェクトは、上位の空間から下に向けて衝突判定されます。この時、ツリーを重複して辿らないように工夫する必要があります。

　駄目な例を挙げます。ルート空間にあるオブジェクトは登録された全てのオブジェクトと衝突する可能性があるので、全ての空間を巡って衝突判定をします。この作業を終えた後、一つ下の親空間L=1にあるオブジェクトについて同様に下位のオブジェクトと衝突を検証しようと考えたとします。この段階で、膨大なツリーをもう1度辿る事になってしまいます。これでは先ほどまで一生懸命最適化した意味がまるでなくなってしまいます。木は1回だけ巡りたいんです。

　木を一度通り抜けるだけですべての有効な衝突を終了させるために、衝突オブジェクトリストを導入します。下の図をご覧下さい：

　これは4分木にオブジェクトが登録されている様子を表しています。A～Jがオブジェクトで、天辺がルート空間です。下位空間で生成されていない空間は×印で示しました。衝突判定は①のルート空間から始まります。どの空間でも、まずはその空間内のオブジェクト同士の衝突を行います。判定が終わったら「衝突オブジェクトリスト」に登録されている上位空間のオブジェクトとの衝突判定を行います。ただし①の場合、まだリストには1つもオブジェクトが登録されていませんのでこの処理はスキップされます。一つの空間での衝突判定が終了したら、空間に登録されているオブジェクト（A～D）をリストに追加します。

　①のルート空間での衝突処理がすべて終了したら、次は②の子空間に移動します。ここでも新しい空間に入った最初の処理である空間内のオブジェクトE,Fの衝突をチェックします。その後に衝突オブジェクトリストにある全オブジェクトとの衝突をチェックします。このチェック後は次の空間に移動する予定なのですが、②の場合は子空間を持ちません。この場合、スタックにオブジェクトE,Fを登録せずに親の空間に戻ります。

　順序から次は③のチェックとなります。③でもする事は同様です。自身の空間にはオブジェクトが1つ（G）なので、その衝突チェックは外されますが、衝突オブジェクトリストとの衝突判定は行います。小空間も持ちますので、Gをリストに追加し、④の空間に移動します。

　④でも同様ですが、この空間は子空間を持ちませんので、H,I,Jオブジェクトをリストに追加せずに上に戻ります。戻った③の空間でもう下るべき他の子空間はありません。そこで、リストに登録されているGを除きます。これは最後尾にありますので単純にpopするだけです。一般に戻った時にpopするオブジェクトの数は、その空間に登録されているオブジェクトの数と等しくなります。

　①の空間にさらに戻ります。①ももう辿るべき子空間がありませんので、リストから自身の持つA～Dをpopします。popがオブジェクト登録数4とやはり一緒になる点に注目して下さい。ルート空間で辿る子空間がもう無いとなった時点で、ここまでの再帰的な処理がすべて終了します。そして、気が付けば木を1回辿っただけで衝突処理は適切に終了しており、且つ衝突オブジェクトリストも空っぽになります。

○ 再帰関数を使わない工夫

　この作業、再帰関数を使いたくてたまらなくなるのですが、ちょっと待ってください。再帰関数は関数呼び出しのオーバーヘッドがかかります。またインライン展開もされません。オブジェクトがかなり多くて、これによるパフォーマンス低下が気になってしまう場合は、1つの関数内だけで木を巡る事を検討した方が良いかもしれません。

　以下は1つの関数内で木を巡る擬似プログラムです：

衝突判定関数

CollisionCheck( CQuadTree *pTree ) { // ループの終了条件は現在ルート空間で下るべき子空間が無くなった時 bool FinishFlag = false; bool NewComming = true; CCell **pCurCell = pTree->GetRootTreePtr(); // ルート空間へのポインタを取得 DWORD CurElem = 0; int i,j,s; list<OBJECT_FOR_TREE*> ObjList; list<OBJECT_FOR_TREE*>::iterator it; while( !FinishFlag ) { if( NewComming ) { // 現在の空間内に登録されているオブジェクト同士を衝突 DWORD num = pCurCell[CurElem]->GetObjectNum(); OBJECT_FOR_TREE *pSrcObj = pCurCell[CurElem]->GetObjListPtr(); OBJECT_FOR_TREE *pComp = pSrcObj->m_pNext; for(i=0; i<num; i++) { for(j=i+1;j<num;j++){ pObj->m_pObject.Collision( pComp ); pComp = pComp->m_pNext; } // スタック（リスト）に登録されているオブジェクトとの衝突判定 for(it=ObjList.begin(); it!=ObjList.end();it++) pSrcObj->Collision( (it)->m_pObject ); // 次のオブジェクトへ移行 pSrcObj = pSrcObj->m_pNext; } } // 小空間があるかチェック CheckNum = CurElem & 0x3; for(i=CheckNum; i<4: i++){ if(pCurCell[CurElem<<2+i]!=NULL){ // 小空間があったので移動 CurElem = CurElem<<2+i; NewComming = true; continue; } } // 戻り処理 // スタックからオブジェクトを外す DWORD PopNum = pCurCell[CurElem]->GetObjectNum(); for(i=0; i<PopNum; i++) ObjList.pop_back(); NewComming = false; } }

　再帰関数を用いない実装は、どうしても用いた場合よりも乱雑になりますが、呼び出しオーバーヘッドが無くなるので一般的には再帰関数を使った時よりも高速になります。上の実装では衝突チェックをこの関数内で行っていますが、別にこうしなくても構いません。この部分を分離してもよし、衝突予定オブジェクトリストを作成してこの関数を抜けた後に一気に衝突チェックをしても良しです。

⑤ まとめ

　最適化をする前はn個ある全てのオブジェクトを登録するだけでo(n*(s/2+logs))レベル（nはオブジェクトの数、sは全空間の数）もの手数がかかっていた4分木空間分割は、この章で紹介した最適化アルゴリズムを適用する事で登録作業をo(n*1)レベルまで下げる事ができました。ゲームループでオブジェクトが動く場合には、毎回オブジェクトの更新と空間の移動の再登録が必要になりますが、モートン順序で空間に番号を振り、境界図形を工夫する事でこれもo(n*1)レベルで実現できます。衝突判定もリストをうまく使う事でで木を1回辿るだけで重複無くすべて終了するようにできました。プログラムの組み方にもよりますが、少なくともこのアルゴリズムで4分木空間分割は実用に耐えるレベルになるはずです。

　この章を編纂してつくづく思ったのが、たかが4分木、されど4分木という事でした。ここで紹介した方法がすべてではありませんし、改良の余地はまだあるかもしれませんが、さすがに脳が疲れまして、4分木についてこれ以上突っ込むつもりはありません(^-^;。空間分割についてさらに細かな情報が欲しい方は是非「ゲームプログラミングのためのリアルタイム衝突判定（ボーンデジタル）」及びこの書籍で紹介されている学術論文等をご覧下さい。

⑥ 謝辞

　アルゴリズムの修正に関してJagoon様から大変的確なアドバイスを頂きました。この場を借りてお礼申し上げます。