空間充填曲線②

モートン オーダー　(Morton-Order, Z-order)

モートンキーの算出方法

モートンキーは、XYの位置情報を１ビットずつを交互に並べたものである

空間分割レベル２であり、空間数が16個ある場合の例が下記である

2進数表記

10進数表記

XY方向の位置情報を1ビットずつ交互に並べることによって、16個の空間を

Zを描くように辿ることができる

三次元空間の場合は、Z方向が加わるため、

ZYX ZYX ZYXとビットを並べることでモートンキーを算出することができる

モートンキーの計算をコードに起こしてみる

二次元用

7行目から10行目では、X方向の位置情報をモートンキー算出用にビットセパレートする
12行目から15行目では、Y方向の位置情報をモートンキー算出用にビットセパレートする
ビットセパレートしたものを、17行目で結合することで、
XYの位置情報を1ビットずつ交互に並べている

// MortonKey from x, y
unsigned int GetMortonKey2D(unsigned int x, unsigned int y){
  unsigned int bitx, bity;
  bitx = x;
  bity = y;

  // 0x00ff00ff : 0000 0000 1111 1111 0000 0000 1111 1111
  // 0x0f0f0f0f : 0000 1111 0000 1111 0000 1111 0000 1111
  // 0x33333333 : 0011 0011 0011 0011 0011 0011 0011 0011
  // 0x55555555 : 0101 0101 0101 0101 0101 0101 0101 0101
  bitx = (bitx|(bitx<<8)) & 0x00ff00ff;
  bitx = (bitx|(bitx<<4)) & 0x0f0f0f0f;
  bitx = (bitx|(bitx<<2)) & 0x33333333;
  bitx = (bitx|(bitx<<1)) & 0x55555555;

  bity = (bity|(bity<<8)) & 0x00ff00ff;
  bity = (bity|(bity<<4)) & 0x0f0f0f0f;
  bity = (bity|(bity<<2)) & 0x33333333;
  bity = (bity|(bity<<1)) & 0x55555555;

  return bitx | bity<<1;
}

三次元用

// MortonKey from x, y, z
unsigned int GetMortonKey3D(unsigned int x, unsigned int y, unsigned int z){
  unsigned int bitx, bity, bitz;
  bitx = x;
  bity = y;
  bitz = z;

  // 0x030000ff : 0011 0000 0000 0000 0000 1111 1111
  // 0x0300f00f : 0011 0000 0000 1111 0000 0000 1111
  // 0x030c30c3 : 0011 0000 1100 0011 0000 1100 0011
  // 0x09249249 : 1001 0010 0100 1001 0010 0100 1001
  bitx = (bitx|(bitx<<16)) & 0x030000ff;
  bitx = (bitx|(bitx<< 8)) & 0x0300f00f;
  bitx = (bitx|(bitx<< 4)) & 0x030c30c3;
  bitx = (bitx|(bitx<< 2)) & 0x09249249;

  bity = (bity|(bity<<16)) & 0x030000ff;
  bity = (bity|(bity<< 8)) & 0x0300f00f;
  bity = (bity|(bity<< 4)) & 0x030c30c3;
  bity = (bity|(bity<< 2)) & 0x09249249;

  bitz = (bitz|(bitz<<16)) & 0x030000ff;
  bitz = (bitz|(bitz<< 8)) & 0x0300f00f;
  bitz = (bitz|(bitz<< 4)) & 0x030c30c3;
  bitz = (bitz|(bitz<< 2)) & 0x09249249;

  return bitx | bity<<1 | bitz<<2;
}

ヒルベルト曲線　( Hilbert Curve )

ヒルベルトキー算出方法

二次元用

// HilbertKey from x, y, n
unsigned int GetHilbertKey2D(unsigned int x, unsigned int y, unsigned int n){
  int i, ix, iy;
  unsigned int s, temp;

  s = 0;
  for( i=n-1; i>=0; i-- ){
    ix = (x >> i) &1;
    iy = (y >> i) &1;

    if( iy == 0 ){
      temp = x;
      x = y^(-ix);
      y = temp^(-ix);
    }
    s = 4*s + 2*ix + (ix^iy);
  }
  return s;
}