java - 衝突応答で円と長方形のオーバーラップを修正する方法は?

Question

デジタルの世界では実際の衝突はほとんど起こらないので、「衝突する」円が四角形に重なる状況が常に発生します。

重なり合うことなく長方形と完全に衝突する状況で、円を元に戻すにはどうすればよいですか?

長方形が停止しており (ゼロ速度)、軸が整列しているとします。

この問題は事後アプローチ (2 次元) で解決します。

要するに、t についてこの方程式を解かなければなりません。

ここに画像の説明を入力

どこ：

は、衝突が完全に発生したのは何フレーム前ですか?という質問に答える数値です。
円の半径です。
円の中心です
はその速度です。
とは、円と四角形が衝突する点の x 座標と y 座標を返す関数です (円がある位置にある場合、つまり四角形と完全に衝突する位置にあります)。

最近、円同士の衝突について同様の問題を解決しましたが、関数 A と B の法則がわかりません。

score 27 · Accepted Answer

この問題を何年も見つめ続け、完璧な解決策を思い付くことはありませんでしたが、ついに解決しました!

これは非常に単純なアルゴリズムであり、ループや近似は必要ありません。

これは、より高いレベルでどのように機能するかです。

現在のポイントから将来のポイントへのパスがその平面を横切る場合、各側面の平面との交差時間を計算します。
各辺の象限で片側の交差を確認し、交差を返します。
円が衝突している角を特定します。
現在の点、角、および交差する中心 (角から離れた半径) の間の三角形を解きます。
時間、法線、交差点の中心を計算します。

そして今、悲惨な詳細に！

関数への入力は、境界 (左、上、右、下) と現在のポイント (開始) と将来のポイント (終了) です。

出力は、x、y、時間、nx、および ny を持つ Intersection というクラスです。

{x, y} は、交差時間における円の中心です。
time は 0 から 1 の値で、0 は開始時、1 は終了時です。
{nx, ny} は法線で、速度を反映して円の新しい速度を決定するために使用されます

よく使用するキャッシュ変数から始めます。

float L = bounds.left;
float T = bounds.top;
float R = bounds.right;
float B = bounds.bottom;
float dx = end.x - start.x;
float dy = end.y - start.y;

そして、各辺の平面との交差時間を計算します (始点と終点の間のベクトルがその平面を通過する場合):

float ltime = Float.MAX_VALUE;
float rtime = Float.MAX_VALUE;
float ttime = Float.MAX_VALUE;
float btime = Float.MAX_VALUE;

if (start.x - radius < L && end.x + radius > L) {
   ltime = ((L - radius) - start.x) / dx;
}
if (start.x + radius > R && end.x - radius < R) {
   rtime = (start.x - (R + radius)) / -dx;
}
if (start.y - radius < T && end.y + radius > T) {
   ttime = ((T - radius) - start.y) / dy;
}
if (start.y + radius > B && end.y - radius < B) {
   btime = (start.y - (B + radius)) / -dy;
}

ここで、それが厳密に横の交差点 (コーナーではない) であるかどうかを確認しようとします。衝突点が側面にある場合は、交点を返します。

if (ltime >= 0.0f && ltime <= 1.0f) {
   float ly = dy * ltime + start.y;
   if (ly >= T && ly <= B) {
      return new Intersection( dx * ltime + start.x, ly, ltime, -1, 0 );
   }
}
else if (rtime >= 0.0f && rtime <= 1.0f) {
   float ry = dy * rtime + start.y;
   if (ry >= T && ry <= B) {
      return new Intersection( dx * rtime + start.x, ry, rtime, 1, 0 );
   }
}

if (ttime >= 0.0f && ttime <= 1.0f) {
   float tx = dx * ttime + start.x;
   if (tx >= L && tx <= R) {
      return new Intersection( tx, dy * ttime + start.y, ttime, 0, -1 );
   }
}
else if (btime >= 0.0f && btime <= 1.0f) {
   float bx = dx * btime + start.x;
   if (bx >= L && bx <= R) {
      return new Intersection( bx, dy * btime + start.y, btime, 0, 1 );
   }
}

ここまで進んだので、交差点がないか、コーナーに衝突したことがわかります。コーナーを決定する必要があります。

float cornerX = Float.MAX_VALUE;
float cornerY = Float.MAX_VALUE;

if (ltime != Float.MAX_VALUE) {
   cornerX = L;
} else if (rtime != Float.MAX_VALUE) {
   cornerX = R;
}

if (ttime != Float.MAX_VALUE) {
   cornerY = T;
} else if (btime != Float.MAX_VALUE) {
   cornerY = B;
}

// Account for the times where we don't pass over a side but we do hit it's corner
if (cornerX != Float.MAX_VALUE && cornerY == Float.MAX_VALUE) {
   cornerY = (dy > 0.0f ? B : T);
}

if (cornerY != Float.MAX_VALUE && cornerX == Float.MAX_VALUE) {
   cornerX = (dx > 0.0f ? R : L);
}

これで、三角形を解くのに十分な情報が得られました。これは、距離の式を使用して、2 つのベクトル間の角度を求め、正弦の法則 (2 回) を使用します。

double inverseRadius = 1.0 / radius;
double lineLength = Math.sqrt( dx * dx + dy * dy );
double cornerdx = cornerX - start.x;
double cornerdy = cornerY - start.y;
double cornerdist = Math.sqrt( cornerdx * cornerdx + cornerdy * cornerdy );
double innerAngle = Math.acos( (cornerdx * dx + cornerdy * dy) / (lineLength * cornerdist) );
double innerAngleSin = Math.sin( innerAngle );
double angle1Sin = innerAngleSin * cornerdist * inverseRadius;

// The angle is too large, there cannot be an intersection
if (Math.abs( angle1Sin ) > 1.0f) {
   return null;
}

double angle1 = Math.PI - Math.asin( angle1Sin );
double angle2 = Math.PI - innerAngle - angle1;
double intersectionDistance = radius * Math.sin( angle2 ) / innerAngleSin;

すべての側面と角度について解いたので、時間とその他すべてを決定できます。

// Solve for time
float time = (float)(intersectionDistance / lineLength);

// If time is outside the boundaries, return null. This algorithm can 
// return a negative time which indicates the previous intersection. 
if (time > 1.0f || time < 0.0f) {
   return null;
}

// Solve the intersection and normal
float ix = time * dx + start.x;
float iy = time * dy + start.y;
float nx = (float)((ix - cornerX) * inverseRadius);
float ny = (float)((iy - cornerY) * inverseRadius);

return new Intersection( ix, iy, time, nx, ny );

ウー！楽しかったです...これには、効率に関する限り、改善の余地がたくさんあります。可能な限り少ない計算を行いながら、できるだけ早くエスケープするように、側面交差チェックを並べ替えることができます。

三角関数なしでそれを行う方法があることを望んでいましたが、あきらめなければなりませんでした!

これを呼び出して、それを使用して法線を使用して円の新しい位置を計算し、交差時間を使用して反射の大きさを計算する例を次に示します。

Intersection inter = handleIntersection( bounds, start, end, radius );

if (inter != null) 
{
   // Project Future Position
   float remainingTime = 1.0f - inter.time;
   float dx = end.x - start.x;
   float dy = end.y - start.y;
   float dot = dx * inter.nx + dy * inter.ny;
   float ndx = dx - 2 * dot * inter.nx;
   float ndy = dy - 2 * dot * inter.ny;
   float newx = inter.x + ndx * remainingTime;
   float newy = inter.y + ndy * remainingTime;
   // new circle position = {newx, newy}
 }

そして、開始点と終了点をプロットできる完全にインタラクティブな例を含む完全なコードをペーストビンに投稿しました。これにより、時間と結果として長方形から跳ね返ることが示されます。

すぐに実行したい場合は、私のブログからコードをダウンロードする必要があります。それ以外の場合は、独自の Java2D アプリケーションに貼り付けてください。

編集: 衝突ポイントも含めるようにペーストビンのコードを変更し、速度も改善しました。

編集: 長方形の角度を使用して、円の始点と終点で長方形の回転を解除することにより、回転する長方形に対してこれを変更できます。交差チェックを実行してから、結果のポイントと法線を回転させます。

編集:円のパスの境界ボリュームが四角形と交差しない場合、ペーストビンのコードを早期に終了するように変更しました。

score 0 · Accepted Answer

それは非線形の問題ですよね？

時間ステップを取り、ステップの開始時の速度を使用して計算された変位によってボールを動かします。オーバーラップが見つかった場合は、ステップサイズを小さくして収束まで再計算します。

ボールと長方形は両方とも剛体で、変形していないと仮定していますか? 摩擦のない接触？接触した後のボールの動きをどのように処理しますか? 接触の座標系 (法線 + 接線) に変換し、計算してから元に戻していますか?

それは些細な問題ではありません。

自分でコーディングするよりも、 Box2Dのような物理エンジンを調べる必要があるかもしれません。

java - 衝突応答で円と長方形のオーバーラップを修正する方法は?

3 に答える 3

Related

Reference