Morton Code / Z-Order

This explanation is currently available in Japanese.

ひとことで

2 次元や 3 次元の座標を、x・y（・z）のビットを交互に並べて 1 つの整数にしたものです。Z 順序曲線とも呼ばれます。この番号の順に空間をたどると、Z の字が大きさを変えながらくり返す曲線になり、空間で近い点は、一列に並べても近い番号になりやすくなります。多次元のデータを 1 次元に並べ替えたいとき、近さをなるべく保つための簡単な方法です。

ゲームでの使いどころ

• BVH を速く作る：物体をモートン符号の順にソートし、上位のビットから分けていくと、BVH を GPU で一気に作れる（LBVH）。
• メモリの並びを整える：粒子や物体をモートン符号の順に並べ替えると、近くの物体がメモリ上でも近くに並び、近傍探しのキャッシュ効率が上がる。
• 四分木・八分木：モートン符号の上位 2 ビット（3 次元なら 3 ビット）ずつが、木の各段の子の番号になる。木をポインタなしで表せる。
• テクスチャのメモリ配置：GPU はテクスチャを Z 順序に近い並び（スウィズル）で持ち、縦にも横にも近い画素を同時に読みやすくしている。

しくみ

2 次元で 4 ビットずつの座標 $x = x_3x_2x_1x_0$、$y = y_3y_2y_1y_0$ なら、モートン符号は

です（2 進数）。たとえば $x = 5 = 0101$、$y = 6 = 0110$ なら、$m = 00111001 = 57$ になります。

上位のビットほど、空間を大きく分けたときの区画を表します。最上位の 2 ビットで空間を 4 つに分けたどの区画か、次の 2 ビットでその中の 4 つのどれか……と決まるので、番号が近い点は同じ区画に入りやすくなります。ただし、区画の境目では、空間で隣でも番号が大きく飛ぶことがあります（Z の字の折り返し）。より近さを保つ曲線にヒルベルト曲線がありますが、計算が少し複雑です。

ビットを速く交互に並べる：1 ビットずつ並べる代わりに、シフトとマスクで一気に間を広げます。

実装のポイント

• 座標を整数にする：浮動小数点の座標は、世界の範囲を 0〜1023（10 ビット）などに正規化してから整数に変換します。
• ソートと組み合わせる：モートン符号をキーにして、基数ソート（GPU なら並列の基数ソート）で並べ替えます。
• 範囲の検索：ある長方形の中の点を探すとき、モートン符号の順に並べた配列の中では、長方形がいくつかのひと続きの区間に分かれます。行ごとの並びより区間の数が少なくなります。

つまずきやすい点

• ビット数の上限：32 ビットの整数なら、3 次元で 10 ビットずつ（1024 段階）が上限です。細かさが足りなければ 64 ビットを使います。
• 境目での飛び：Z の字の折り返しでは、隣り合うセルでも番号が大きく離れます。近傍探しの際は、番号の近さだけに頼らず、実際の距離も調べます。
• 座標の範囲外：正規化の範囲からはみ出した座標は、上限に丸めないと、符号が壊れておかしな場所に並びます。

デモで試すこと

1. 16 × 16 のセルが、モートン符号の小さい順（紫）から大きい順（黄色）に色分けされ、白い線がたどる順です。Z の字が大きさを変えてくり返しているのがわかります。
2. セルにカーソルを乗せると、右下に x と y のビットと、それを交互に並べた符号が表示されます。
3. 白い枠の範囲のセルが、一列に並べた番号の帯（右）のどこにあるかを見てください。左下の「ひと続きの区間の数」が、範囲の大きさに比べて少ないことを確かめます。
4. 「行ごと（行優先）」に切り替えると、範囲の高さの数だけ区間が分かれます。「範囲の幅」「範囲の高さ」を変えて比べてください。