3D衝突編
その15 8分木空間分割を最適化する！
空間分割はオブジェクト同士の衝突や不必要な描画を除くなどパフォーマンスの最適化に必須の技術です。2D衝突編その８とその９では、2D平面を分割する4分木空間分割の最適化と実装をしました。同じ考え方は3D空間の分割にも十分に活用できます。
3Dの空間を分割する典型が8分木空間分割（Octree）です。空間分割の方法は、4分木とお話がかぶりますが、まず一番大きな空間（ルート空間）を定義します。3Dの場合これは直方体となります。分割は各辺のど真ん中を割ります。縦横高さそれぞれで分けるので、1回の分割で8つの小空間が出来上がります。これで親であるルート空間の下に8つの小空間が所属する事になります。後は空間を分割するたびに樹状に所属が広がっていきます。
オブジェクトは境界図形に包まれて、8分木内にある境界図形をすっぽりと包む空間に登録されます。大きなオブジェクトはそれだけ高いレベル（大きな空間のレベル）に登録されますが、小さな図形でも空間の境界線をまたいでいる場合は大きな空間に登録される事があります。
すべての対象オブジェクトを8分木に登録したら、後は空間を共通するオブジェクト同士を関連させます。例えば衝突に使う場合、空間を小分けにしている段階で同じレベルの別の空間内にあるオブジェクトが衝突することはありません。ですからそれらの衝突がごっそりと省略できます。親空間のオブジェクトとは衝突する可能性がありますのでチェックはしますが、これにより大変なパフォーマンスの最適化が期待できます。
しかし、4分木と同様に8分木も空間分割やオブジェクトの登録・再登録を最適化しないとぜんぜん使い物になりません。そこでこの章では4分木空間分割の時のアルゴリズムを踏襲しながら8分木空間分割を最適化してみます。でも、殆ど4分木のそれと一緒です。
① 8分木のモートン順序
4分木空間分割では、あるレベルの空間に「モートン順序」という方法で番号を付けました。8分木の場合もこれは同様です。X軸方向を1ビット目、Y軸方向を2ビット目、そしてZ軸方向を3ビット目にしますと、ルート空間に所属する8つある親空間は次のように番号が振られます：
例えば6番は2進数で110。X=0,Y=1,Z=1になっていますよね。もっと小さな空間になってもこの振り方は一緒です。モートン順序で空間に番号を振る事により、一番下位のレベルの番号を見れば、どの親空間に所属しているかが全部わかります。例えば、L=3（ルート空間がL=0です）の空間にある512個の空間で、375番の空間の親を調べてみましょう。まず、375を2進数に変換すると「101|110|111」となります。3ビットずつに分割して、これを10進数に戻すと「5|6|7」となります。これより、375番の空間は、
「ルート空間の下にある5番目の親、その親の持つ6番目の子の下の7番目の空間」
である事がわかります。モートン空間はここでも便利さをいかんなく発揮しております。
② 境界図形の範囲から所属するモートン番号をo(1)で割り出す
8分木はツリーであるため、色々な大きさがある境界図形（AABBなど）をすっぽりと包む空間の番号をツリーを辿って決める事はできます。しかし、この場合一番小さい空間に収めるのには分割レベルL回の判定（o(log空間数）オーダー）を要します。4分木空間分割ではここを最適化してo(1)オーダーにしましたが、同じ方法は8分木にも使えます。
何をしたか、おさらいしておきましょう。AABB境界図形の左上奥（なんとも表現しにくい（笑））と右下手前を含む一番下位のレベルの空間番号をまずは割り出します。これはそれほど難しい作業ではありません。
4分木空間分割でやった作業をここでも用います。X軸側の範囲をXs～Xbとします。また点のX成分をxとし、分割空間の幅（単位幅）をWxとします。これを次のように計算すると、どのX位置に来るかたちどころに出てきます：
「？」という方のために例を一つ。空間を3段階（各軸8分割）に分けているとして、Xs=5、Xb=85の範囲でx=28.0が所属する場所を計算します。単位幅Wxは(85-5)/8=10です。ここからxは2番目（0基点：25～35の範囲）である事がイメージできますよね。上の式に値を代入すると、確かに(DWORD)(28.0-5.0)/10=2となります。これはX軸の所属ビットになります。
XYZ軸それぞれについて所属ビットを算出すれば、後はそれを「挟み込んでいく」事でモートン番号が算出されます。挟み込みというのは次のような作業になります。
例えばある点の所属ビットがX=101（5番）、Y=011（3番）、Z=100（4番）だとします（ビット数から空間レベルL=3です）。挟み込みをしたモートン番号は次のようになります：
これにより、ある点はL=3の空間番号339番に所属する事がわかります。この挟み込みをする関数は、4分木の時とまったく同じような作業になります。まず各所属ビットを3ビットごとに広げる関数を用意します：
3バイトごとに間隔を開ける関数 DWORD BitSeparateFor3D( BYTE n )
{
DWORD s = n;
s = ( s | s<<8 ) & 0x0000f00f;
s = ( s | s<<4 ) & 0x000c30c3;
s = ( s | s<<2 ) & 0x00249249;
return s;
}
引数がBYTEになっています。これは1つの軸を256段階（L=8）までできる事を表しています。たぶん、実質これ以上の分割は現状では無理です。例えば分割レベルL=9にすると空間数は1億3千万にもなります。これはポインタだけでも512MBのメモリを占有します。もしそれ以上の環境を使える方は、上の関数を少し改良して下さい。
上の関数があれば、挟み込みをする関数は次のように表現できます：
8分木モートン順序算出関数 DWORD Get3DMortonOrder( BYTE x, BYTE y, BYTE z )
{
return BitSeparateFor3D(x) | BitSeparateFor3D(y)<<1 | BitSeparateFor3D(z)<<2;
}
次に境界図形の範囲に所属する空間のモートン番号を割り出します。これには4分木の時に出てきたアルゴリズムがそのまま使えます。まず境界図形の最小側と最大側の点のモートン番号を割り出します。今分割レベルL=2(各軸4分割)として、最小を16番、最大を23番としましょう･･･と言ってもイメージが難しいので、何とか図を示してみます：
(GIFの限界色数超えてますな･･･）
上の図で黄色い空間が境界図形の端っこを含む空間です。見てお分かりの通り、この境界図形は親空間の2番にすっぽり包まれています。
まずは23と16の排他的論理和を取って、その2進数をチェックします：
上の場合フラグがたっている下位のバイト列から「親空間」が共有空間であると読み取ります。もしルート空間の3bitが0でなければ、これはルート空間の境界をまたいでいるため、ルート空間が境界となります。
共有空間レベルがわかった後、23番でも16番でもどちらでも良いので共有空間の所が無くなるまで右シフトします。上の場合まずレベル値（L=1）を空間分割レベル数（Lm=2）から引き算します。引き算するのは3bit単位で「ルート(L=0)、親(L=1)、子(L=2)、孫(L=3)…」と左から命名しているので、シフト量とLの値が丁度反対になるためです。そうして求めたシフト単位に3を掛けシフトbit数にすればOKです。つまりルート空間番号を抽出するには、
010 111 >> ((Lm-L)*3) → 010
と3bit右シフトすれば良く、結果親空間の2番がちゃんと出てきました。これは分割レベルがもっと進んでも成り立ちます。
（※2022.11.8 上記につきましてシフトの倍数計算が違うとのご報告を頂いたため修正致しました）
③ 線形8分木
4分木同様、8分木もツリーではなく線形配列に並べた方がアクセスが断然よくなります。8分木を線形化したものを線形8分木（Liner Octree）と言います。線形8分木はルート空間を要素0番、次の親空間を1～8番、子空間を9番以降、と並べていきます。
こうすると「空間レベル＋番号」という指定でo(1)オーダーで空間にアクセスできます。②で境界図形が所属する空間レベルと番号をうまく抽出できる事を示しました。これにより任意の大きさの境界図形を適切な空間にo(1)で登録できる事がわかります。
例えば先ほど16-23番の範囲にある境界図形は、「親空間(L=1)の2番」でした。これに該当する線形8分木の要素番号は、次のように算出できます：
これは等比数列の和を用いています。もっとも、分数部分は固定的な値なので最初から計算して置いても良いです。
例としてL=3(512空間),n=236番は、え～と、309番要素です。この要素番号の空間の親空間の要素番号を抽出するには、
という計算で一発です(C言語の場合DWORDは分母分子が整数であれば必要ありません）。つまり、(309-1)/8=38番要素がこの空間の親です。さらに1引いて8で割れば4番。その上がルート空間である0番です。逆に親空間から子空間に移動するには次のように計算します：
38番の親空間が持つ子は38*8+1=304番から311番要素番号までとなります。線形8分木でこの空間移動ができるようになると、例えば衝突判定オブジェクトを辿る事が可能になります。この辿り方については4分木の時とまったく一緒なので詳しくはそちらをご覧下さい。
④ 8分木空間分割のメモリ占有問題
8分木空間分割では3次元の空間を縦横高さそれぞれに分割します。これは1回の分割で空間の数が8倍になる事を示しています。どれだけの空間数になるか列挙してみます：
空間レベルL 空間数 占有メモリ(KB) 占有メモリ(MB) 0 1 0.0 0.0 1 9 0.2 0.0 2 73 1.4 0.0 3 585 11.4 0.0 4 4,681 91.4 0.1 5 37,449 731.4 0.7 6 299,593 5,851.4 5.7 7 2,396,745 46,811.4 45.7 8 19,173,961 374,491.4 365.7
占有メモリは1つの空間を20バイト（CCellクラスのサイズ＋線形8分木へ格納するポインタ4バイト）で計算しています。これを見ると5分割ぐらい細かくした段階では占有メモリが750KB程度ですが、これが8分割（各軸256段階）となると370MBに膨れ上がります。もちろんここには空間に含めるべきオブジェクトの大きさは含まれていません。8分木がいかにメモリを食うかがわかると思います。このことから、最初から線形8分木にすべての空間を用意するのはかなりに無謀な実装となります。
メモリを節約するには1つは空間レベルを高くし過ぎないというのがあるかと思います。ただその場合衝突判定などの判定回数は大分に増えてしまいます。節約の活路はあります。オブジェクトの大きさと空間のランダム分布の度合いによりますが、3次元の場合2次元よりも「オブジェクトが存在しない」空間の割合が圧倒的に多くなります。例えば主に地面を走るようなアクションゲームの場合、空の大部分には衝突を判定すべきオブジェクトは普通ありません。オブジェクトが元から無い部分の空間を積極的に作らなければ、同じ分割レベルの4分木空間分割の数倍程度にメモリが節約されます。この実装はきわめて簡単で、しかも効果的です。
空間のを作らないメモリ節約により、空間レベルを1ランク上げることも可能になると思います。ただ、それでも沢山のメモリを占有しますので、ガーベージコレクタと似たような感じに積極的に空間を「消していく」という最適化も時には必要になるかと思います。消すタイミングとして最適なのは「衝突対応リスト」を取得する時です。ツリーをめぐるのですから一緒にチェックもできてしまいます。
ツリーをめぐる際に、末端空間にオブジェクトが登録されていなければ、その空間は削除してかまわなくなります。1順すればオブジェクトが登録されていない末端空間はすべて削除されます。あまりめまぐるしく生成と削除をするとメモリのフラグメントが起きてしまうのですが、今はあまり気にしないでおきましょう(^-^;。
⑤ サンプルプログラムでクラス公開
ここまでの理屈を組み込んだ線形8分木による衝突判定をするクラスを公開致します。基本は線形4分木と一緒で、空間はCCellクラス、オブジェクトを包むOBJECT_FOR_TREEクラス、そして線形8分木を管理するCLiner8TreeManagerクラスがあります。細かな使い方はサンプルプログラムをご覧下さい。
