2

衝突検出に分離軸定理を使用する Java で 2D ゲームを作成しようとしています。2 つのポリゴン間の衝突を解決するには、衝突の最小移動ベクトルを知る必要があり、ポリゴンに対してどの方向を指すかを知る必要があります (1 つのポリゴンにその方向に沿ってペナルティ フォースを与え、他の反対方向へのペナルティ力）。参考までに、ここでアルゴリズムを実装しようとしています。

collide(Polygon polygon1, Polygon polygon2)衝突検出関数を呼び出して衝突が検出された場合、返される MTV は常にポリゴン 1 から離れてポリゴン 2 を指すことを保証したいと思います。これを行うには、生成する分離軸 (ポリゴン エッジの法線) が、生成元のポリゴンから常に離れていることを保証する必要があります。(そうすれば、MTV として使用する前に、polygon2 の軸を無効にすることができます)。

残念ながら、ポリゴンのエッジに対して生成する法線がポリゴンの内部または外部を指すかどうかは、ポリゴンのポイントが時計回りまたは反時計回りの順序で宣言されているかどうかに依存するようです。ここで説明するアルゴリズムを使用して法線を生成しています。「垂直」法を選択したと仮定すると(x, y) => (y, -x)、頂点を時計回りに反復処理した場合にのみ、結果の法線がポリゴンから離れた方向を指します。

クライアントに多角形のポイントを時計回りに宣言させることはできないため (x 座標と y 座標の 2 つの配列を公開するだけの java.awt.Polygon を使用しています)、それを保証する数学的な方法はありますか?私が生成する法線ベクトルの方向は、ポリゴンの外側に向かっていますか? 私はベクトル計算が苦手なので、私が見逃している明らかな解決策があるかもしれません。SAT に関するほとんどのインターネット リソースでは、多角形の頂点を常に時計回りに反復できると想定しています。

4

2 に答える 2

2

たとえば、この質問への回答を使用して、各ポリゴンの順序を計算し、2 つのポリゴンの順序が異なる場合は法線に -1 を掛けます。

また、アルゴリズムに渡された各ポリゴンをチェックして、上記のアルゴリズムを再度使用して、順序が間違っていないかどうかを確認し、必要に応じて頂点の順序を逆にすることもできます。

頂点の順序を計算するとき、一部のアルゴリズムはすべてのポリゴンで機能し、一部は凸ポリゴンのみで機能することに注意してください。

于 2012-07-18T19:40:59.090 に答える
1

私は最終的にそれを理解しましたが、投稿された1つの回答は完全な解決策ではなかったので、それを受け入れるつもりはありません. このSOの回答で説明されている基本的なアルゴリズムを使用して、ポリゴンの順序を決定できました（David Normanのリンクでもあまり明確に説明されていません）。

for each edge in polygon:
    sum += (x2 - x1) * (y2 + y1)

ただし、これらの回答のいずれにも言及されていない重要な警告があります。通常、この合計が正の場合はポリゴンの頂点が時計回りであり、合計が負の場合は反時計回りであると判断できます。しかし、 Java の 2D グラフィックス システム、および実際には多くのグラフィックス システムでは、正の y 軸が下向きであるため、この比較は逆になります。したがって、通常の数学的座標系では、次のように言えます。

if sum > 0 then polygon is clockwise

しかし、逆の y 軸を持つグラフィックス座標系では、実際には

if sum < 0 then polygon is clockwise

Java の Polygon を使用した実際のコードは次のようになります。

//First, find the normals as if the polygon was clockwise

int sum = 0;
for(int i = 0; i < polygon.npoints; i++) {
    int nextI = (i + 1 == polygon.npoints ? 0 : i + 1);
    sum += (polygon.xpoints[nextI] - polygon.xpoints[i]) * 
        (polygon.ypoints[nextI] + polygon.ypoints[i]);
}

if(sum > 0) {
    //reverse all the normals (multiply them by -1)
}
于 2012-07-22T00:08:27.667 に答える