衝突判定
OBB.OBB
SAMPLE https://www.dropbox.com/s/ftinmimmqtstdqr/hit_obb.exe( OBB 同士の衝突判定 )空間分割
SAMPLE https://www.dropbox.com/s/0que55hvwagjp0i/texgen_world.exe( 空間分割 ) 固定サイズの配列を用意して、点の場所ごとに仕分けをする。 各ボックス内にある点同士で判定をする。 総当りの数を減らす。 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 https://www.dropbox.com/s/t6cufez61yxz0fg/hit_2d_box.exe( 箱どうしの衝突判定 ) 矩形どうしが当たる場合は 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 =========== ============ Bbool 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 https://www.dropbox.com/s/wci0rrgpr22ydam/hit_2d_box_response.exe( 衝突結果として動かない ) この場合、斜めに移動をして衝突した場合も動けなくなる。 Y 方向の移動が 重力などの場合は 一切動けなくなる。位置の補正
SAMPLE http://ooo.iiyudana.net/bin/gl/hit_2d_box_response.exe( 位置の補正 ) あたる直前の位置に補正するには、当たった後に重なった長さ分だけ元に戻す。 WARNING XY ２軸同時に移動をする場合は、各軸独立して移動してから２回補正をする必要がある。 そうしないと横、縦方向にはじかれることになる。移動と速度
SAMPLE https://www.dropbox.com/s/xid6zbzbwfh75tn/hit_2d_box_response_jump.exe( 移動と速度 ) 最初に速度を変更して、それから位置を更新する。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 = ---------------
