問題タブ [separating-axis-theorem]

分離軸定理 (SAT) に基づいて、凸型 2d ポリゴンと凸型 2d ポリゴンの衝突テストを行っています。

私の質問は、MTV の方向を何らかの形で修正せずにこのアルゴリズムを実装することは可能でしょうか? (巻く順序、外向きの法線、または私が間違っている可能性のあるその他の詳細に注意を払うことによって)。

SAT は最小の翻訳ベクトルを生成します。約半分の時間で間違った方向を指していたため、MTV の方向を正しく取得するのが難しいことがわかりました (ポリゴン A と B が衝突検出機能に渡された場合、MTV は常に A の方向になるはずです)。2 つの投影が重なるかどうかだけでなく、2 つの投影間の重なりの方向をチェックするコードを追加した後にのみ、正しく機能し始めました。

しかし、私が読んだ SAT に関するさまざまな記事やコメントでは、外向きのポリゴン法線について言及されており、MTV 方向のトピックは比較的ほとんど注目されていないため、重要な詳細を見逃している可能性があります、私にとってはそれが最も難しい部分でした）。

私の SAT 実装の中核は、2 回呼び出されるこの関数です。関数が引数の順序を逆にして 2 回目に呼び出されると、MTV の方向に影響しますが、私はこれを十分に認識しています。

これは、分離軸定理を使用して衝突を解決する Lua の LOVE2D エンジン用に私が作成していた小さなライブラリです。

SAT プログラムが動作するようになったときはとてもうれしく、多数のポリゴンでテストを開始しました。これはほとんどの場合に機能し、正しい最小平行移動ベクトルも提供します。奇妙なことに、両方の形状が鋭角である場合、これらの角度によってプログラムが失敗し、形状が接触していないときに衝突が返されます。さらに珍しいことに、奇妙な最小の並進ベクトルが得られます。法線を返す関数を確認しました。これが最初に失敗した可能性があると感じたので、正常に機能しているようです。

これは、衝突を処理するメイン関数です。

私のプロジェクト ファイルは github にあります https://github.com/ToffeeGoat/ToffeeCollision

分離軸定理を使用して衝突をテストするためのコードを C++ で書いていますが、特定の方向では、衝突が発生していることが誤ってトリガーされます。

私はこのチュートリアルに従っていますが、チュートリアルは2Dのみであり、3Dで実装しようとしていますが、それでも同じはずです。

私が今持っているアルゴリズムは衝突を見逃すことはありませんが、2 つのボックスの向きによっては、実際には衝突していないと考えられます。ここに例を示します。これら 2 つのボックスは、以下のコードに従って明らかに衝突しています。

コードはC++で書かれています

BoxCollider.h

BoxCollider.cpp

アルゴリズム:

分離軸定理を使用して、2 つのポリゴン (プレイヤーとオブジェクト) が交差するかどうかを確認しています。プレイヤーをオブジェクトから跳ね返らせたいのですが、これを行うには、プレイヤーが衝突した側 (角度を計算する側) が必要です。

SAT関数からこれを取得するにはどうすればよいですか?

概要

この質問は JavaScript で書かれていますが、任意の言語、疑似コード、または数学だけで答えていただければ幸いです。

次のことを達成するために、分離軸定理を実装しようとしています。

• 凸多角形と円の交点を検出します。
• 交点を解決するために円に適用できる平行移動を見つけて、円が多角形にかろうじて接触し、内側にならないようにします。
• 衝突の軸を決定します（質問の最後に詳細があります）。

最初の箇条書きを正常に完了しました。質問の最後に私の JavaScript コードが表示されます。他の部分で困っています。

交差点の解決

円の重なりが最小/最短の方向で交差点を解決する方法については、オンラインで多くの例があります。最後のコードで、これが既に計算されていることがわかります。

しかし、これは私のニーズには合いません。円の軌道の反対方向で衝突を解決する必要があります (円の軌道が既にあり、それを単位ベクトルまたは角度のいずれか適切な方として関数に渡したいとします)。

下の画像で、最短解像度と意図した解像度の違いを確認できます。

関数内の交点を解決するための最小平行移動ベクトルを計算するにはどうすればよいtest_CIRCLE_POLYですか?ただし、円の軌道とは反対の特定の方向に適用する必要があります。

私のアイデア/試み:

• 私の最初のアイデアは、SAT アルゴリズムでテストする必要がある軸に追加の軸を追加することでした。この軸は、円の軌跡に対して垂直になります。次に、この軸に投影するときにオーバーラップに基づいて解決します。これはある程度機能しますが、ほとんどの状況ではるかに解決されます。最小限の翻訳にはなりません。したがって、これは満足のいくものではありません。
• 私の 2 番目のアイデアは、最短のオーバーラップの大きさを引き続き使用することでしたが、円の軌道の反対になるように方向を変更しました。これは有望に見えますが、おそらく私が説明していない多くのエッジケースがあります. たぶん、これは始めるのに良い場所です。

衝突の側面/軸の決定

円が衝突しているポリゴンの側面を特定する方法を見つけました。多角形のテストされた軸ごとに、オーバーラップをチェックするだけです。重なりがある場合は、その面が衝突しています。

円の軌道に応じて片側だけを把握したいので、この解決策は再び受け入れられません。

私の意図した解決策は、下の例の画像で、軸 A が衝突の軸であり、軸 B ではないことを教えてくれます。これは、交差が解決されると、軸 A がポリゴンの側面に対応する軸になるためです。円にかろうじて触れるだけです。

私のアイデア/試み:

• 現在、衝突の軸は MTV (最小平行移動ベクトル) に垂直であると想定しています。これは現在正しくありませんが、質問の前半で交差解決プロセスを更新すると、正しい軸になるはずです。そのため、その部分を最初に取り組む必要があります。

• または、円の前の位置と現在の位置 + 半径から線を作成し、この線と交差する辺を確認することを検討しました。ただし、場合によっては複数の辺が線と交差することがあるため、あいまいさが残ります。

これまでの私のコード