モートン順序を利用した空間分割による衝突判定

リアルタイムに移動する大量のオブジェクトを表示するゲームをAndroidで制作しておりますが、そのオブジェクト同士を単純に全てを判定すると処理が重くなり過ぎます。

そこで

こんな本を買ってみました。

各所で絶賛されていた本でしたが、かなり高額です。

しかし今後のためにも読んでおいた方がいいと判断したので購入したのですが、この内容をコードに落とし込むところまで考えるとかなり時間が掛かります。

というわけでこの本の内容をまとめた上でDirectXのサンプルコードを提供されているこちらのサイトを参考にしました。

4分木空間分割を最適化する！（理屈編）

4分木空間分割を最適化する！（実装編）

非常に分かりやすくまとめてあるので、大変参考になりました。理屈編のリンク先を見てもらえばやりたいことが理解していただけるはずです。それと同時にモートン順序の凄さも理解できます。

いきなりAndroidで作成してみても良かったのですが、デバッグするのが面倒なのでFlashで作成してみました。

リンクリストの部分などでポインタの扱いがどうかと思いましたが、AS3.0はクラスは参照で渡されるはずなので、問題ないと思います。

AndroidではC++で組んでいるので、本番ではその辺りは改善されるはずです。

というわけで、サンプルです。（※要FlashPlayer）

500オブジェクトほど表示しており、衝突が発生した場合は、衝突したオブジェクトが赤くなります。

続いてサンプルコードです。

コード量がいつもより多いので、ファイル毎に分けます。

Main.as

package net.n2works.collision
{
  import flash.display.Bitmap;
  import flash.display.Sprite;
  import flash.events.Event;
  import flash.events.MouseEvent;
  
  /**
  /* @func  ： エントランス
  /* @author  ： N.Nishimura
  /* @update  ： 2013/02/04 N.Nishimura 作成
  **/
  public class Main extends Sprite 
  {
    // スタートボタン
    public var mBtn_start:Sprite;
    
    // 円
    public var mCircles:Array;
    
    // OFTオブジェクト
    public var mOfts:Array;
    
    /**
    /*  @brief  : コンストラクタ
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Main():void 
    {
      // ステージ領域の更新
      Global.STAGE_WIDTH = this.stage.stageWidth;
      Global.STAGE_HEIGHT = this.stage.stageHeight;
      
      // スタートボタン
      var img_btn_start:Bitmap = new Global.ImageBtnStart() as Bitmap;
      mBtn_start = new Sprite();
      mBtn_start.addChild(img_btn_start);
      mBtn_start.x = Global.STAGE_WIDTH / 2 - img_btn_start.width / 2;
      mBtn_start.y = Global.STAGE_HEIGHT / 2 - img_btn_start.height / 2;
      mBtn_start.addEventListener(MouseEvent.CLICK, this.OnMouseClick);
      this.addChild(mBtn_start);
    }
    
    /**
    /*  @brief  : 初期化
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/08 N.Nishimura 作成
    **/
    public function Initialize():void 
    {
      // 円配列
      mCircles = new Array(Global.CIRCLE_NUM);
      
      // OFT配列
      mOfts = new Array(Global.CIRCLE_NUM);
      
      // 円とOFTを設定
      for (var i:int = 0; i < Global.CIRCLE_NUM; i++) {
        // 円を作成して表示
        mCircles[i] = new Circle();
        var c:Circle = mCircles[i];
        this.addChild(c);
        
        // OFTを作成
        mOfts[i] = new OFT(c);
      }
      
      // 線形4分木管理クラスを作成
      Global.CM = new Liner4TreeManager();
      Global.CM.Initialize(3, 0.0, 0.0, Global.STAGE_WIDTH, Global.STAGE_HEIGHT);
      
      // 60fpsのリスナ
      this.addEventListener(Event.ENTER_FRAME, this.OnEnterFrame);
    }
    
    /**
    /*  @brief  : リスナ
    /* 
    /*  @li    : MouseEvent.CLICK
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/08 N.Nishimura 作成
    **/
    public function OnMouseClick(e:MouseEvent):void 
    {
      // スタートボタンを無効化
      this.removeChild(mBtn_start);
      mBtn_start = null;
      
      // 処理開始
      this.Initialize();
    }
    
    /**
    /*  @brief  : リスナ
    /* 
    /*  @li    : Event.Enter_FRAME
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function OnEnterFrame(e:Event):void 
    {
      var i:uint;
      var cm:Liner4TreeManager = Global.CM;
      var c:Circle;
      var c2:Circle;
      var oft:OFT;
      
      // 円の更新
      for (i = 0; i < Global.CIRCLE_NUM; i++) {
        c = mCircles[i];
        c.Update();
        
        // 空間から全てオブジェクトを削除
        oft = mOfts[i];
        oft.Remove();
      }
      
      // OFTを空間に登録
      for (i = 0; i < mOfts.length; i++) {
        oft = mOfts[i];
        c = oft.mCircle;
        var flg:Boolean = cm.Regist(
          c.x - c.mRadius,
          c.y - c.mRadius,
          c.x + c.mRadius,
          c.y + c.mRadius,
          oft
        );
      }
      
      // 衝突リストを作成
      var list:Array = new Array();
      cm.GetAllCollisionList(list);
      
      // 衝突対象が２つずつになっているはず
      if (list.length > 0) {
        i = 0;
        var line1:uint = 0;
        var line2:uint = 0;
        while (i <= list.length) {
          c = list[i++];
          c2 = list[i++];
          if (c == null) {
            continue;
          }
          line1 = (c.x - c2.x);
          line2 = (c.y - c2.y);
          if (line1 * line1 + line2 * line2 < (c.mRadius * 2) * (c.mRadius * 2)) {
            c.TransformColor(0xff0000);
            c.mIs_base_color = false;
            c2.TransformColor(0xff0000);
            c2.mIs_base_color = false;
          }
        }
      }
      list = null;
    }
  }
}

Global.as

package net.n2works.collision 
{
  /**
  /* @func  ： グローバルクラス
  /* @author  ： N.Nishimura
  /* @update  ： 2013/02/04 N.Nishimura 作成
  **/
  public class Global 
  {
    // 円の数
    public static var CIRCLE_NUM:int = 500;
    
    // 円の半径
    public static var RADIUS:Number = 5.0;
    
    // 空間レベル
    public static var DEPTH_LEVEL:uint = 9;
    
    // ステージ領域
    public static var STAGE_WIDTH:Number = 300.0;
    public static var STAGE_HEIGHT:Number = 300.0;
    
    // 線形4分木管理クラス
    public static var CM:Liner4TreeManager = null;
    
    // スタートボタン画像
    [Embed(source='btn_start.png')]
    public static var ImageBtnStart:Class;
  }
}

Vector2D.as

package net.n2works.collision 
{
  /**
  /* @func  ： ベクトルクラス
  /* @author  ： N.Nishimura
  /* @update  ： 2013/02/04 N.Nishimura 作成
  **/
  public class Vector2D
  {
    // X軸
    public var mX:Number;
    
    // Y軸
    public var mY:Number;
    
    /**
    /*  @brief  : コンストラクタ
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Vector2D() 
    {
      mX = 0.0;
      mY = 0.0;
    }
  }
}

Circle.as

package net.n2works.collision
{
  import flash.display.Sprite;
  import flash.display.Graphics;
  import flash.geom.ColorTransform;
  
  /**
  /* @func  ： 円クラス
  /* @author  ： N.Nishimura
  /* @update  ： 2013/02/04 N.Nishimura 作成
  **/
  public class Circle extends Sprite
  {
    // ベクトル
    public var mVector:Vector2D;
    
    // 半径
    public var mRadius:Number;
    
    // 色を戻すフラグ
    public var mIs_base_color:Boolean;
    
    /**
    /*  @brief  : コンストラクタ
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Circle():void
    {
      // 初期化
      mVector = new Vector2D();
      mRadius = Global.RADIUS;
      
      // 描画
      this.Draw(0xffffff);
      mIs_base_color = true;
      
      // 位置をランダムで決定
      var w:Number = Global.STAGE_WIDTH;
      var h:Number = Global.STAGE_HEIGHT;
      this.x = Math.floor(Math.random() * w / 2) + w / 4;
      this.y = Math.floor(Math.random() * h / 2) + h / 4;
      
      // ベクトルをランダム決定
      mVector.mX = Math.random() * 4.0 - 2.0;
      mVector.mY = Math.random() * 4.0 - 2.0;
    }
    
    /**
    /*  @brief  : 描画
    /* 
    /*  @li    : 
    /*  @param  : uint  :  色
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Draw(color:uint):void
    {
      // 自分自身を描画
      var g:Graphics = this.graphics;
      g.beginFill(color, 1.0);
      g.drawCircle(0.0, 0.0, mRadius);
    }
    
    /**
    /*  @brief  : 更新
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Update():void
    {
      // 移動処理
      this.x += mVector.mX;
      this.y += mVector.mY;
      
      // 壁との衝突判定
      var w:Number = Global.STAGE_WIDTH;
      var h:Number = Global.STAGE_HEIGHT;
      if ((this.x - mRadius) < 0.0) {
        this.x = mRadius;
        mVector.mX = -mVector.mX;
      }
      if ((this.x + mRadius) > w) {
        this.x = w - mRadius;
        mVector.mX = -mVector.mX;
      }
      if ((this.y - mRadius) < 0.0) {
        this.y = mRadius;
        mVector.mY = -mVector.mY;
      }
      if ((this.y + mRadius) > h) {
        this.y = h - mRadius;
        mVector.mY = -mVector.mY;
      }
      
      // 色を戻す
      if (mIs_base_color == false) {
        this.TransformColor(0xffffff);
      }
    }
    
    /**
    /*  @brief  : オブジェクトの色を変更
    /* 
    /*  @li    : 
    /*  @param  : uint  :  変更カラー
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/07 N.Nishimura 作成
    **/
    public function TransformColor(color:uint):void
    {
      var transform:ColorTransform = new ColorTransform();
      transform.color = color;
      this.transform.colorTransform = transform;
    }
  }
}

Cell.as

package net.n2works.collision 
{
  /**
  /* @func  ： 空間クラス
  /* @author  ： N.Nishimura
  /* @update  ： 2013/02/04 N.Nishimura 作成
  **/
  public class Cell 
  {
    // 先頭のOFTへの参照
    public var mLatestOFT:OFT;
    
    /**
    /*  @brief  : コンストラクタ
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Cell():void
    {
      mLatestOFT = null;
    }
    
    /**
    /*  @brief  : スタックへPUSH
    /* 
    /*  @li    : 
    /*  @param  : OFT  :  OFTの参照
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function Push(oft:OFT):Boolean 
    {
      // 無効なオブジェクトは登録しない
      if (oft == null) {
        return false;
      }
      
      // 二重登録チェック
      if (oft.mCell == this) {
        return false;
      }
      
      // 新規登録
      if (mLatestOFT == null) {
        mLatestOFT = oft;
      }
      // 更新
      else {
        oft.mNext = mLatestOFT;
        mLatestOFT.mPrev = oft;
        mLatestOFT = oft;
      }
      
      // OFTが所属する空間を登録
      oft.mCell = this;
      
      return true;
    }
    
    /**
    /*  @brief  : OFTからの削除通知
    /* 
    /*  @li    : 
    /*  @param  : OFT  :  OFTの参照
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function OnRemove(oft:OFT):Boolean 
    {
      // 最新のOFTオブジェクトが削除するOFTオブジェクトの場合
      if (mLatestOFT == oft) {
        // 次のOFTオブジェクトを登録
        if (mLatestOFT != null) {
          mLatestOFT = mLatestOFT.mNext;
        }
      }
      return true;
    }
  }
}

OFT.as

package net.n2works.collision 
{
  /**
  /* @func  ： 空間オブジェクトクラス
  /* @author  ： N.Nishimura
  /* @update  ： 2013/02/04 N.Nishimura 作成
  **/
  public class OFT 
  {
    // 所属空間の参照
    public var mCell:Cell;
    
    // 円オブジェクトの参照
    public var mCircle:Circle;
    
    // 前のオブジェクトへの参照(双方向リンクリスト)
    public var mPrev:OFT;
    
    // 後ろのオブジェクトへの参照(双方向リンクリスト)
    public var mNext:OFT;
    
    /**
    /*  @brief  : コンストラクタ
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function OFT(circle:Circle):void 
    {
      mCell = null;
      mCircle = circle;
      mPrev = null;
      mNext = null;
    }
    
    /**
    /*  @brief  : 空間から削除
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Remove():Boolean
    {
      // すでに削除されているまたは未登録の場合は終了
      if (mCell == null) {
        return false;
      }
      
      // 空間へ削除通知
      if (!mCell.OnRemove(this)) {
        return false;
      }
      
      // 前後のオブジェクトを結びつける
      if (mPrev != null) {
        mPrev.mNext = mNext;
      }
      if (mNext != null) {
        mNext.mPrev = mPrev;
      }
      
      // 参照を削除
      mPrev = null;
      mNext = null;
      
      // 所属空間から抜ける
      mCell = null;
      
      return true;
    }
  }
}

Liner4TreeManager.as

package net.n2works.collision 
{
  /**
  /* @func  ： 線形4分木管理クラス
  /* @author  ： N.Nishimura
  /* @update  ： 2013/02/04 N.Nishimura 作成
  **/
  public class Liner4TreeManager 
  {
    // 各レベルの空間数
    public var mCell_num_by_level:Array;
    
    // 設定されたレベルの空間数
    public var mCell_num:uint;
    
    // 空間配列
    public var mCells:Array;
    
    // 有効領域
    public var mLeft:Number;
    public var mTop:Number;
    public var mWidth:Number;
    public var mHeight:Number;
    
    // 空間単位の幅・高さ
    public var mUnit_w:Number;
    public var mUnit_h:Number;
    
    // 空間レベル
    public var mLevel:uint;
    
    /**
    /*  @brief  : コンストラクタ
    /* 
    /*  @li    : 
    /*  @param  : 
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/04 N.Nishimura 作成
    **/
    public function Liner4TreeManager():void
    {
      mCell_num_by_level = new Array(Global.DEPTH_LEVEL + 1);
      mCell_num = 0;
      mCells = null;
      mLeft = mTop = mWidth = mHeight = mUnit_w = mUnit_h = 0;
      
      // 各レベルでの空間数を算出
      mCell_num_by_level[0] = 1;
      for (var i:uint = 1; i < Global.DEPTH_LEVEL + 1; i++) {
        mCell_num_by_level[i] = mCell_num_by_level[i - 1] * 4;
      }
    }
    
    /**
    /*  @brief  : 初期化
    /* 
    /*  @li    : 
    /*  @param  : uint    :  空間レベル
    /*  @param  : Number  :  空間左
    /*  @param  : Number  :  空間上
    /*  @param  : Number  :  空間右
    /*  @param  : Number  :  空間下
    /*  @return  : Boolean
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function Initialize(level:uint, left:Number, top:Number, right:Number, bottom:Number):Boolean
    {
      // 設定最高レベル以上の空間は作れない
      if (level > Global.DEPTH_LEVEL + 1) {
        return false;
      }
      
      // 指定レベルの配列作成
      mCell_num = (mCell_num_by_level[level + 1] - 1) / 3;  // 等比級数の和
      mCells = new Array(mCell_num);
      for (var i:uint = 0; i < mCells.length; i++) {
        mCells[i] = null;
      }
      
      // 有効領域の設定
      mLeft = left;
      mTop = top;
      mWidth = right - left;
      mHeight = bottom - top;
      mUnit_w = mWidth / (1 << level);
      mUnit_h = mHeight / (1 << level);
      
      // 最深空間レベルの保持
      mLevel = level;
      return true;
    }
    
    /**
    /*  @brief  : オブジェクトを空間へ登録
    /* 
    /*  @li    : 
    /*  @param  : Number  :  空間左
    /*  @param  : Number  :  空間上
    /*  @param  : Number  :  空間右
    /*  @param  : Number  :  空間下
    /*  @param  : OFT    :  OFTオブジェクト
    /*  @return  : Boolean
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function Regist(left:Number, top:Number, right:Number, bottom:Number, oft:OFT):Boolean
    {
      // オブジェクトの境界範囲から登録モートン番号を算出
      var element:uint = this.GetMortonNumber(left, top, right, bottom);
      
      if (element < mCell_num){
        // 空間が無い場合は新規作成
        if (mCells[element] == null) {
          this.CreateNewCell(element);
        }
        var cell:Cell = mCells[element];
        return cell.Push(oft);
      }
      return false;
    }
    
    /**
    /*  @brief  : 空間を作成
    /* 
    /*  @li    : 
    /*  @param  : uint  :  モートン番号
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function CreateNewCell(element:uint):void
    {
      // 引数のモートン番号の空間だけでなくその親も作成
      while (mCells[element] == null) {
        // 指定のモートン番号の空間を作成
        mCells[element] = new Cell();
        
        // ルート空間を作成の場合は親がいないので終了
        if (element == 0) {
          break;
        }
        
        // 親のモートン番号へ移動
        element = (element - 1) >> 2;
        
        // フェイルセーフ
        if (element >= mCell_num) {
          break;
        }
      }
    }
    
    /**
    /*  @brief  : モートン順序番号を取得
    /* 
    /*  @li    : 
    /*  @param  : Number  :  空間左
    /*  @param  : Number  :  空間上
    /*  @param  : Number  :  空間右
    /*  @param  : Number  :  空間下
    /*  @return  : uint    :  モートン順序番号
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function GetMortonNumber(left:Number, top:Number, right:Number, bottom:Number):uint
    {
      // 最深レベルにおける各軸位置を算出
      var lt:uint = this.GetPointToElementNumber(left, top);
      var rb:uint = this.GetPointToElementNumber(right, bottom );
      
      // 空間番号の排他的論理和から所属レベルを算出(何ビットシフトするか)
      var def:uint = rb ^ lt;
      var hi_level:uint = 0;
      for(var i:uint = 0; i < mLevel; i++) {
        var check:uint = (def >> (i * 2)) & 0x3;
        if(check != 0) {
          hi_level = i + 1;
        }
      }
      
      // 最深レベルにおけるモートン番号(右下座標のモートン番号に直前で算出したシフト実行)
      var space_num:uint = rb >> (hi_level * 2);
      
      // 上位レベルのモートン番号合計値
      var add_num:uint = (mCell_num_by_level[mLevel - hi_level] - 1) / 3;
      
      // 線形配列番号のためにルートからの通算モートン番号に変換
      space_num += add_num;
      
      // フェイルセーフ
      if(space_num > mCell_num) {
        return 0xffffffff;
      }
      
      return space_num;      
    }
    
    /**
    /*  @brief  : 衝突判定オブジェクトリスト取得
    /* 
    /*  @li    : 全部
    /*  @param  : 
    /*  @return  : Array    :  衝突判定オブジェクトリスト
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/06 N.Nishimura 作成
    **/
    public function GetAllCollisionList(list:Array):void
    {
      // ルート空間の存在をチェック
      if (mCells[0] == null) {
        return;
      }
      
      // ルート空間から衝突チェック開始
      var stack:Array = new Array();
      this.GetCollisionList(0, list, stack);
      stack = null;
    }
    
    /**
    /*  @brief  : 衝突判定オブジェクトリストを取得
    /* 
    /*  @li    : 再起関数
    /*  @param  : uint  :  開始モートン番号
    /*  @param  : Array  :  リスト
    /*  @param  : Array  :  スタック
    /*  @return  : 
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/06 N.Nishimura 作成
    **/
    public function GetCollisionList(element:uint, list:Array, stack:Array):void
    {
      // 空間内でオブジェクト同士の衝突リストを作成
      var i:uint;
      var cell:Cell = mCells[element];
      var oft1:OFT = cell.mLatestOFT;
      while (oft1 != null) {
        var oft2:OFT = oft1.mNext;
        while (oft2 != null) {
          // 衝突リストを作成
          list.push(oft1.mCircle);
          list.push(oft2.mCircle);
          oft2 = oft2.mNext;
        }
        
        // 衝突スタックとの衝突リスト作成
        for (i = 0; i < stack.length; i++) {
          list.push(oft1.mCircle);
          list.push(stack[i]);
        }
        
        // 次のオブジェクト
        oft1 = oft1.mNext;
      }
      
      // 子空間へ移動
      var is_child:Boolean = false;
      var obj_num:int = 0;
      var next_element:int = 0;
      for (i = 0; i < 4; i++) {
        next_element = element * 4 + 1 + i;
        if (next_element < mCell_num && mCells[next_element]) {
          if (!is_child) {
            // 登録オブジェクトをスタックに追加
            oft1 = cell.mLatestOFT;
            while (oft1 != null) {
              stack.push(oft1.mCircle);
              obj_num++;
              oft1 = oft1.mNext;
            }
          }
          is_child = true;
          this.GetCollisionList(next_element, list, stack);
        }
      }
      
      // スタックからオブジェクトを外す
      if (is_child) {
        for (i = 0; i < obj_num; i++) {
          stack.pop();
        }
      }
    }
    
    /**
    /*  @brief  : ビット分割
    /* 
    /*  @li    : 
    /*  @param  : int    :  指定整数
    /*  @return  : int    :  分割後整数
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function BitSeparate32(n:int):int
    {
      n = (n|(n<<8)) & 0x00ff00ff;
      n = (n|(n<<4)) & 0x0f0f0f0f;
      n = (n|(n<<2)) & 0x33333333;
      return (n|(n<<1)) & 0x55555555;
    }
    
    /**
    /*  @brief  : モートン空間番号取得
    /* 
    /*  @li    : 2D用
    /*  @param  : uint    :  モートン番号(X軸)
    /*  @param  : uint    :  モートン番号(Y軸)
    /*  @return  : uint    :  モートン番号
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function Get2DMortonNumber(x:uint, y:uint):uint
    {
      return (this.BitSeparate32(x) | (this.BitSeparate32(y)<<1));
    }
    
    /**
    /*  @brief  : 座標から線形4分木要素番号変換
    /* 
    /*  @li    : 2D用
    /*  @param  : Number  :  オブジェクトの左上
    /*  @param  : Number  :  オブジェクトの右下
    /*  @return  : uint    :  モートン番号
    /*  @author  : N.Nishimura
    /*  @note  :
    /*  @update  : 2013/02/05 N.Nishimura 作成
    **/
    public function GetPointToElementNumber(x:Number, y:Number):uint
    {
      return this.Get2DMortonNumber((uint)((x - mLeft) / mUnit_w), (uint)((y - mTop) / mUnit_h));
    }
  }
}