線分と線分の当たり判定
今回は2次元上での線分と線分の当たり判定について解説していきます。
この記事は『マルペケつくろーどっとコム』さんを参考にさせていただきました。
計算式や結果は下記の記事と同じです。
今回、こちらでは図形から外積と三角関数を使って説明していこうかと思います。
当たり判定の概要
線分同士の当たり判定はそれぞれの線分から直角三角形を作り出して導くことが出来ます。
まず基本はこの図形のようになります。
P1を始点としたV1のベクトルとP2を始点としたV2のベクトルが当たっているか？
そして当たっている場合は交点Pを導きだします。
先ず、V1とV2の外積を取ることでベクトル間の角度(sinθ)を出します。
① V1 x V2 = sinθ |V1||V2|
ここでV1とV2の長さで外積の結果を割るとsinθ以外の|V1||V2|の部分を消せます。
※sinθの結果が0の場合は平行な線分同士なので当たりません。
次にP1からP2へのベクトル(V)とV2の外積からの角度を求めます。
② V x V2 = sinθ |V||V2|
この外積の結果から|V2|の長さを割るとsinθ|V|となります。
この時のsinθ|V|を三角関数に当てはめると
sinθ = a / b
これを下記の図に当てはめるとこのようになります。
sinθ = N / |V|
つまりNについて説く式にすると
③ N = sinθ |V|
となるのでP1からV2に対して垂直な線の長さが出せます。
これが出ると更に下記の図が作れるので t1 を求める式が考えられます。
この図の内容を三角関数で式にすると下記が出ます。
sinθ = N / t1
t1について説く式に置き変えると
④ t1 = N / sinθ
これで t1 の長さが出ます。
この時の長さが 0以上でかつ、V1の長さより短ければ線分の中に納まっていることになります。
後はV2に対しても同じことをすれば両方の線分に対して当たっているかが分かります。
線分と線分の当たり判定の基本はこれで求めることが出来ます。
応用編
このページでは今回の式を応用してプログラムの効率化を考えた実装にしていきます。
参考サイトでは効率化された実装が既に使われていたので
プログラム的にはここからが本番です！
では前のページで出した計算式を元に計算を解いていきます。
計算は主に4つだけですが間に細かな計算が入ってきます。
① V1 x V2 = sinθ |V1||V2|
② V x V2 = sinθ |V||V2|
③ N = sinθ |V|
④ t1 = N / sinθ
これだけでも単純に t1 は出せるので問題なく当たり判定が取れます。
しかし①と②の|V1|と|V2|の長さを消す処理を簡略化することで面白い結果を得ることができます。
では簡略化しない場合とどう違うのか実際に比べてみましょう。
通常の計算手順
①外積によるV1とV2間の sinθ の算出
V1 x V2 = sinθ
※正規化したV1とV2を使うことにより sinθ のみを抽出
②外積によるVとV2間の sinθ の算出
V x V2 = sinθ |V|
※正規化したV2を使うことにより sinθ のみを抽出
③ N = sinθ |V|
直前の②で出した答えがそのままV2に垂直なP1からの直線の長さとなる。
④ t1 = N / sinθ
最初に出した①と③で出した値を使って交点までの長さ t1 を求める。
通常手順時の当たり判定
t1 が出たら後は V1 の長さが t1 の中に入っているかが問題になります。
なので t1 が0以上でかつ、|V1|よりも短ければ当たっていることになります。
t1 が終わったら次に t2 も同じように判定していきます。
これで両方ともが条件に当てはまれば当たっていることになります。
応用版の計算手順
①外積によるV1とV2間の sinθ の算出
V1 x V2 = sinθ|V1||V2|
※|V1|と|V2|の長さを残したままにしておく
②外積によるVとV2巻の sinθ の算出
V x V2 = sinθ |V||V2|
※|V2|の長さを残したままにしておく
③ N|V2| = sinθ |V||V2|
直前の②で出した答えがそのままV2に垂直なP1からの直線の長さとなる。
④ t1 / |V1| = N|V2| / sinθ|V1||V2|
最初に出した①と③で出した値を使って交点までの長さ t1 / |V1| を求める。
応用版では正規化などをしないことにより計算手順を減らして①~④までの計算を行いました。
これにより最終的に|V2|は①と③で相殺されて消えて t1 / |V1|となりました。
ではこの結果を使って当たり判定に入っていきましょう。
応用手順時の当たり判定
先ず、上で出した式はどのような値になるでしょうか？
・t1 / |V1|
実は |V1| が線分の全体の長さになるので
当たり判定を持った全体の長さに対しての割合が求められます。
つまり 0 ~ 1.0 の間に入っているものが当たっているという判定にできます。
応用版の長さを消さない計算で実装をすると間に入っていた長さで割る(正規化)の計算が不要になります。
こうやって式を単純に計算通りに行うのではなくて
再構築して考えていくことでプログラムの最適化が行えるようになります。
当たり判定等の重くなりそうな計算式を実装する場合は
こういった細かい部分にも注目して最適化を考えてみると意外と楽しいので皆も挑戦してみてください！