点と三角形の当たり判定
今回は点と三角形の当たり判定の計算方法についてです。
基本的な考え方は、下図の様に点Pから三角形の各頂点ABCに向かうベクトル間のなす角を調べることで行います。
(ただし、)
上図の∠AB、∠BC、∠CAは三角形の内部に点Pがある限り180°以上になることは有り得ません。
もし180°以上の角が存在していたら、点Pは三角形の外側にあると判定することが出来ます。
上で示した例は、頂点ABCが反時計回りに配置されているパターンです。
しかし、実際には時計回りになる場合も有り得ます。
この場合、点Pが三角形の内部にある場合は∠AB、∠BC、∠CAがすべて180°より大きくなります。
点Pが三角形の外側にある場合は180°以下の角が存在することになります。
ポイントは、180°以下になる角が存在してもすべての角が180°以下にはならないところです。
頂点が反時計回りの場合も180°以上の角が存在してもすべての角が180°以上にはなりません。
したがって、点Pが三角形の内側にあるための∠AB、∠BC、∠CAの条件は次式のようになります。
この条件式は、以下のようなを用いた式に変換できます。
このを求めるためにはどうすれば良いでしょうか?
答えは外積を使うことです。
ベクトル、
の外積
は、
と
のなす角
を用いて以下の様に表現されます。
また、、
とすると、以下の様に表現できます。
∠AB、∠BC、∠CAの条件式を以下のように変形します。
これはベクトル、
、
の外積で表現できます。
この条件式の結果が真なら「当たり」、そうでなければ「はずれ」となります。
点と三角形の当たり判定は点と円の当たり判定以上に乗算が増えるので処理が重くなります。
AABBを用いたブロードフェーズと組み合わせて使用するのが望ましいかもしれません。