概要
この質問は JavaScript で書かれていますが、任意の言語、疑似コード、または数学だけで答えていただければ幸いです。
次のことを達成するために、分離軸定理を実装しようとしています。
- 凸多角形と円の交点を検出します。
- 交点を解決するために円に適用できる平行移動を見つけて、円が多角形にかろうじて接触し、内側にならないようにします。
- 衝突の軸を決定します（質問の最後に詳細があります）。
最初の箇条書きを正常に完了しました。質問の最後に私の JavaScript コードが表示されます。他の部分で困っています。
交差点の解決
円の重なりが最小/最短の方向で交差点を解決する方法については、オンラインで多くの例があります。最後のコードで、これが既に計算されていることがわかります。
しかし、これは私のニーズには合いません。円の軌道の反対方向で衝突を解決する必要があります (円の軌道が既にあり、それを単位ベクトルまたは角度のいずれか適切な方として関数に渡したいとします)。
下の画像で、最短解像度と意図した解像度の違いを確認できます。
関数内の交点を解決するための最小平行移動ベクトルを計算するにはどうすればよいtest_CIRCLE_POLYですか?ただし、円の軌道とは反対の特定の方向に適用する必要があります。
私のアイデア/試み:
- 私の最初のアイデアは、SAT アルゴリズムでテストする必要がある軸に追加の軸を追加することでした。この軸は、円の軌跡に対して垂直になります。次に、この軸に投影するときにオーバーラップに基づいて解決します。これはある程度機能しますが、ほとんどの状況ではるかに解決されます。最小限の翻訳にはなりません。したがって、これは満足のいくものではありません。
- 私の 2 番目のアイデアは、最短のオーバーラップの大きさを引き続き使用することでしたが、円の軌道の反対になるように方向を変更しました。これは有望に見えますが、おそらく私が説明していない多くのエッジケースがあります. たぶん、これは始めるのに良い場所です。
衝突の側面/軸の決定
円が衝突しているポリゴンの側面を特定する方法を見つけました。多角形のテストされた軸ごとに、オーバーラップをチェックするだけです。重なりがある場合は、その面が衝突しています。
円の軌道に応じて片側だけを把握したいので、この解決策は再び受け入れられません。
私の意図した解決策は、下の例の画像で、軸 A が衝突の軸であり、軸 B ではないことを教えてくれます。これは、交差が解決されると、軸 A がポリゴンの側面に対応する軸になるためです。円にかろうじて触れるだけです。
私のアイデア/試み:
現在、衝突の軸は MTV (最小平行移動ベクトル) に垂直であると想定しています。これは現在正しくありませんが、質問の前半で交差解決プロセスを更新すると、正しい軸になるはずです。そのため、その部分を最初に取り組む必要があります。
または、円の前の位置と現在の位置 + 半径から線を作成し、この線と交差する辺を確認することを検討しました。ただし、場合によっては複数の辺が線と交差することがあるため、あいまいさが残ります。
これまでの私のコード
function test_CIRCLE_POLY(circle, poly, circleTrajectory) {
// circleTrajectory is currently not being used
let axesToTest = [];
let shortestOverlap = +Infinity;
let shortestOverlapAxis;
// Figure out polygon axes that must be checked
for (let i = 0; i < poly.vertices.length; i++) {
let vertex1 = poly.vertices[i];
let vertex2 = poly.vertices[i + 1] || poly.vertices[0]; // neighbouring vertex
let axis = vertex1.sub(vertex2).perp_norm();
axesToTest.push(axis);
}
// Figure out circle axis that must be checked
let closestVertex;
let closestVertexDistSqr = +Infinity;
for (let vertex of poly.vertices) {
let distSqr = circle.center.sub(vertex).magSqr();
if (distSqr < closestVertexDistSqr) {
closestVertexDistSqr = distSqr;
closestVertex = vertex;
}
}
let axis = closestVertex.sub(circle.center).norm();
axesToTest.push(axis);
// Test for overlap
for (let axis of axesToTest) {
let circleProj = proj_CIRCLE(circle, axis);
let polyProj = proj_POLY(poly, axis);
let overlap = getLineOverlap(circleProj.min, circleProj.max, polyProj.min, polyProj.max);
if (overlap === 0) {
// guaranteed no intersection
return { intersecting: false };
}
if (Math.abs(overlap) < Math.abs(shortestOverlap)) {
shortestOverlap = overlap;
shortestOverlapAxis = axis;
}
}
return {
intersecting: true,
resolutionVector: shortestOverlapAxis.mul(-shortestOverlap),
// this resolution vector is not satisfactory, I need the shortest resolution with a given direction, which would be an angle passed into this function from the trajectory of the circle
collisionAxis: shortestOverlapAxis.perp(),
// this axis is incorrect, I need the axis to be based on the trajectory of the circle which I would pass into this function as an angle
};
}
function proj_POLY(poly, axis) {
let min = +Infinity;
let max = -Infinity;
for (let vertex of poly.vertices) {
let proj = vertex.projNorm_mag(axis);
min = Math.min(proj, min);
max = Math.max(proj, max);
}
return { min, max };
}
function proj_CIRCLE(circle, axis) {
let proj = circle.center.projNorm_mag(axis);
let min = proj - circle.radius;
let max = proj + circle.radius;
return { min, max };
}
// Check for overlap of two 1 dimensional lines
function getLineOverlap(min1, max1, min2, max2) {
let min = Math.max(min1, min2);
let max = Math.min(max1, max2);
// if negative, no overlap
let result = Math.max(max - min, 0);
// add positive/negative sign depending on direction of overlap
return result * ((min1 < min2) ? 1 : -1);
};