ポリゴンによる衝突検出

Question

最初にポリゴンを定義するクラスを実装する方法と、このクラスを使用して2つのポリゴン間の衝突を検出する方法について、誰かが私に考えてもらえないかと思いました。私はC/C++でもNDKを使うことができますが、より具体的にはAndroid上のJavaで作業しています。私は多角形を定義すると思います。私はちょうど頂点の配列が必要でしょうか？

私が衝突検出を行うとき、私はSeparation Axis TheoremとGJKアルゴリズムについて読みました。これは正しい方法ですか、これをあまりにも複雑にしていますか？正しい方向から始めようとするだけです。ありがとう！

Answer 1

あなたはこの種のことをかなり慣れているように聞こえますが、これはおそらくもっと大きな疑問です。

私はあなたが最初に解決しようとしている問題を定義し、その問題を解決する解決策を見つけることをお勧めします。

は、私はあなたにいくつかの予選質問をしてみましょう：

あなたは、2Dまたは3Dについて話していますか？

これは物理システム用ですか？

交差する場所や交差する場所を知る必要がありますか？

（交差点やユニオンなどを取得するなど）形状に対してブール演算を行う必要がありますか？

Answer 2

多角形の種類によって異なります。

ポリゴンが凸である場合、頂点の順序付きリストが1つを記述し、分離軸とGJKの両方が適用可能なアルゴリズムになります。

多角形が凹ではあるが単純な場合（つまり、エッジが交差しない場合）、頂点の順序付きリストではまだ十分ですが、分離軸またはGJKは適切ではありません。

ポリゴンが複雑な場合（つまり、エッジが交差する場合）、頂点リストと塗りつぶしルールが必要になります。ルールは、平面のどの部分がポリゴンの内側にあると考えられ、外側にあるかを決定しました。充填ルールの差は中央の5面の穴は、多角形の一部または単に穴であるか否かの違いはある

：

は、例えば、五角形のような多角形を想像します。

もっと複雑な種類のポリゴンは、単純な種類のポリゴンの複数のインスタンスに分解することができます。そのため、地面にフラグを立てて、凸面ポリゴンのみに興味があると宣言してくださいたとえば、GPUが行うことを正確に実行します。

2つのポリゴンが重なっているかどうかを単に衝突と定義していると仮定すると、分離軸の定理は非常に単純であり、確かに行く方法です。たくさんのポリゴンを持つシーンを作成しようとするならば、幅広い段階が必要なのかもしれません。残りの部分は依然として存在する。

明らかな例は、ビンのソートです。スクリーンを16ピクセルの縦のストリップに分割し、次に各ポリゴンに対して（i）どのビンが接触するかを判断することができます。 （ii）それらのビンに既に入っているすべてのポリゴンに対してそれをテストする。 （iii）ビンに追加する。それはおそらく、あなたがテストをかなり多くの時間適用することを決して考えないことを意味します。その特定のスキームには、シーンに応じていくつかの明らかな問題がありますが、よりスマートなアルゴリズムが存在します。