Morton Codeの計算とLBVH

Morton Code

概要

Z階数曲線(モートン符号)は, Z字型に空間を符号化します.
下図のように左上を原点とした場合にZ字型に空間を１次元に符号化します.

作り方

矩形範囲bminとbmax内の点pの符号計算を順に追っていきます. 正確には, 点pを囲む矩形の符号になります.

プログラムコードで申し訳ないですが, 以下をそれぞれの軸で計算します. $N$は空間を分割する数, 例では$N=2$になります.
bminより小さい場合を考慮していませんが, 必要に応じて処理します.

unsigned int code = (unsigned int)((p-bmin)/(bmax-bmin)*N);
code = min(code, N-1);

それぞれの軸の計算結果は, 2進数表記で
x=0, y=1
となります. この2進数を各軸混ぜ込みます. 2次元の場合, yxyxのようにします.

// 1ビットおきに1ビット間を空ける
unsigned int separateBy1(unsigned int x)
{
    x = (x | (x << 8)) & 0x00FF00FFU;
    x = (x | (x << 4)) & 0x0F0F0F0FU;
    x = (x | (x << 2)) & 0x33333333U;
    x = (x | (x << 1)) & 0x55555555U;
    return x;
}
// 1ビットおきに混ぜる
unsigned int mortonCode2(unsigned int x, unsigned int y)
{
    return separateBy1(x) | (separateBy1(y) << 1);
}

最終結果は以下になります. 概要の例とy軸が逆ですが, 正しい符号になっていると思います.
pのモートン符号=10

符号の意味

下図は空間を各軸4分割して, モートン符号を2進数で示したものです.

青い下位2桁は, 00, 01, 10, 11の並びが連続しています. 次に赤枠内では, 上位2桁は全て同じであることがわかります.
さらに, 赤枠同士で見ると00, 01, 10, 11の並びになっていることがわかります.
つまり, モートン符号の上位桁は大きな構造を表現しています. 青枠4つをまとめた大きな構造が赤枠です.

これは, 符号が4分木を表現しているということでもあります.
根の子4つが赤枠4つ, 根から見た子の赤枠の番号が上位2桁の数字です.
また, 赤枠の子である青枠4つの番号は下位2桁の数字です.

LBVH

近年では構築の速さとトラバース速度のバランスからBVHが, レイトレース高速化のためのデータ構造として使われることが多いです.
そのBVH派生としてLinear BVH(LBVH)があります.

LBVHはGPU向けの空間的データ構造構築手法で, GPUの苦手なソートを1度に減らす手法です.
構築の疑似コードは以下になります.

三角形の中心点のモートン符号を計算
モートン符号で三角形をソート
空間を分割して木構造を構築

モートン符号で三角形をソート, までを図にすると以下のようになります.

きもになるのは最後, モートン符号からどのように空間を分割するか, です.
これはモートン符号の意味が重要です. 上位桁から隣合うコードのビットを比較し,
始めてビットが異なるところを検索すればよいです.
図にすると以下です.

ビットが異なればそこで分割です. この分割過程ではソートがはいらないためGPU向きと主張されているわけです.
念のため, 線形探索をするように説明していますが, 実際は2分探索を行います.

まとめ

モートン符号の計算方法をまとめました. また, モートン符号を利用したGPU向けBVH構築手法を見てみました.
別のモートン符号の利用方法も書こうと思いましたが力尽きました.
要望次第でまとめます.