___
■ OBB.OBB

  SAMPLE
     OBB 同士の衝突判定 

___
■ 空間分割


  SAMPLE
     空間分割 

    固定サイズの配列を用意して、点の場所ごとに仕分けをする。
    各ボックス内にある点同士で判定をする。

    総当りの数を減らす。

    1000 個ならば 1000 * 1000 で 100 万回の判定をする。

    4 分割して 250 個ならば
    (* 250 250 4) 250.000

    16 分割して 62 個ならば, 6 万回の判定をする。
    (* 62 62 16) 61.500

    1/4  ずつに減っていく 
  

  処理の順番

    当たるなら動かない
      1. 動く予定をしらべる
      1. 当たった場合は動かない

      3. あたる方向の成分をなくして 当たらない方向だけ移動する
        ( これをしないと 斜めに入力したときに, 完全に動かなくなる )
        ( 重力がある場合も同じ )

           ----  
           |  | ---->
        ------------------------------
             | 
             v
 
    直方体どうしのあたり判定では , 斜めの表現はできない

___
■ k-dTree

    均等分割は 一様に分布していないと性能が落ちる。
    k-dTree は２分木で空間を分割する。

    再帰的に空間を２つに分割していく。

___
■ sort

    ソートする場合は 右から左に順番に検索していく。  
    ---------        ----------
        ----------------
                ----


    左側にマッチしたら リストに追加
    右側にマッチしたら リストから削除( 領域から抜けたということ )
    リスト内にあるものを判定する

    動くもの同士の総当りを高速化する。

    N*log(N) * N

___
■ 箱どうし
  
  SAMPLE
     箱どうしの衝突判定 


    矩形どうしが当たる場合は XY 軸ともに重なっている必要がある。

    当たらない条件を考えると
    A                B
    =========        ===========
    A.right    <      B.left
    
    または

    B                A
    =========        ===========
    B.right    <      A.left

    A.right <  B.left  ||  B.right <  A.left

    
    これの偽だから
    A.right >= B.left  &&  B.right >= A.left

                    A
                   ===========
            ============    
            B





    bool testBoxBox( Box &a, Box &b ) ) 
    {
      if ( a.right >= b.left  &&  b.right >= a.left ) {
        if ( a.top >= b.bottom  &&  b.top >= a.bottom ) {
          return true;
        }
      }
      return false;
    }


    当たった場合の処理として 動かないという対応がある。
    この場合、移動するスピードが十分に小さければ、
    隙間も目立たないので補正が不要という考えもある。

    移動速度をあげると隙間が目立つ。
    速度を上下するとわかる。

  SAMPLE
     衝突結果として動かない 
    
    この場合、斜めに移動をして衝突した場合も動けなくなる。
    Y 方向の移動が 重力などの場合は 一切動けなくなる。
  

___
■ 位置の補正

  SAMPLE
     位置の補正 

    あたる直前の位置に補正するには、当たった後に重なった長さ分だけ元に戻す。
    
  WARNING 
    XY ２軸同時に移動をする場合は、各軸独立して移動してから２回補正をする必要がある。
    そうしないと横、縦方向にはじかれることになる。




  






    
___
■ 移動と速度

  SAMPLE
     移動と速度 

    最初に速度を変更して、それから位置を更新する。
    vy += 0.1f;
    ty += vy;





    
___
■ 球球

    2 点の中心の距離をもとめる

___
■ 三角形と線分

    地面などに立つ場合につかう

    POINT
      あるフレームでの移動において使うことがポイント
      こうすることで貫通が起きない

      球と三角形では抜ける可能性がある
      
      線分上のある点と 三角形上のある 点が一致するパラメータを求めればいい

      a + t*b = c + u*X * v*Y

      求めたい 未知数は 3 つ
      ３つの式が必要

      無限平面でかんがえる

      p = a + t*b となる p が平面にあれば

      (p - c) は N と垂直である

      N, c は定数としてもとまるので, パラメータ t だけが求まる

      内積をつかうと
      n.( c - p ) = 0

      n . ( c - a + t*b ) = 0

      n.c - n.a + t*n.b = 0   // 1次方程式

            n.c - n.a
      t = -------------     // t が求まる. 0:1 であるかチェックをする
               n.b
      
      n.b = 0 とならないようにチェックすること

    幾何学的な意味は
      N と b が平行なので当然、 交わらないということ


    p = c + u*d + v*e

    ベクタをスカラに変換するために 内積 を使える

    // 1 次連立方程式
    g.d = u*d.d + v*d.e
    g.e = u*d.e + v*e.e

    地道にとく
    u を消すような 係数を 2 つの式にかける

    v = ---------------