多角形ポリゴン同士の衝突判定をしたいのですが。。。

質問

３次元上に２つの多角形ポリゴンをＣＧで描きました。この２つの物体の衝突判定を
行いたいのですが、数学では、このような問題はどのように解くのでしょうか?

もう少し詳しく述べると、多角形は三角形の集合で描かれています。
２つの多角形をＡ、Ｂとすれば、Ａをなす三角形とＢをなす三角形が
重なる、もしくは、交わらなければＡとＢは衝突していないことになると思うのですが、どうでしょうか？

２つの三角形が衝突していないということを表す式、考え方がありましたら
教えてください。また、それ以外にベストと思われる式、考え方がありましたら
教えてください。

回答No.2

bear-3 · ベストアンサー

こんにちは。

三次元シミュレーションなどで実際によく利用されているのは、
点が面の中に収まっているかを判定、点と面の距離を計算
で接触判定はよく行われています。

上記のような計算を行うには、ベクトルによる計算が用いられます。
参考1: http://hp.vector.co.jp/authors/VA013845/algorithm/index.html
参考2: http://osaka.cool.ne.jp/pevips/rg2.shtml

ベクトルによる計算の詳しい説明については、ここでは割愛させて頂きます。

参考URL：

http://osaka.cool.ne.jp/pevips/rg2.shtml

回答No.1

shige_70

普通に考えると、それぞれの三角形を延長した平面同士が交わる直線を求め、その直線と三角形の共通部分となる線分が存在するかどうか調べ、それがどちらの三角形に対しても存在すればその共通部分それぞれが重なっているか調べればいいでしょう。
三角形と直線が交差するかどうかは、三角形の３つの頂点が直線にからみて同じ側に集まっていないことをたしかめればいいでしょう。

しかし、上記の計算を各ポリゴンを構成するすべての三角形同士でやらなければなりませんね。複雑なポリゴンならとんでもない計算量でしょう。

目的は何でしょう?

ご質問の趣旨と外れますが、ゲームをお作りになるのでしたら、もっと簡易な方法でやることをおすすめします。
特にシューティングゲームの場合は、各ポリゴンの中心となる点を決め、その点同士の距離が一定以下なら衝突、とやるのが一般的です。その判定基準も実際のポリゴンよりかなり小さめにとった方がゲームとしておもしろくなります。