10

由于在数字世界中几乎不会发生真正的碰撞，因此我们总是会遇到“碰撞”的圆圈与矩形重叠的情况。

如何在与矩形完美碰撞而没有重叠的情况下将圆放回原处？

假设矩形停止（零速度）并且轴对齐。

我会用后验方法（二维）解决这个问题。

简而言之，我必须为 t 求解这个方程：

在此处输入图像描述

在哪里：

  • 吨是一个回答问题的数字：碰撞完美发生在多少帧之前？

  • r是圆的半径。

  • (x, y)是圆的中心

  • (vx, vy)是它的速度。

  • 在）并且乙（吨）是返回圆和矩形碰撞点的 x 和 y 坐标的函数（当圆在(x - t * vx, y - t * vy)位置时，即在与矩形完全碰撞的位置）。

最近我解决了一个类似的圆碰撞问题，但现在我不知道函数A和B的定律。

4

3 回答 3

27

After years of staring at this problem, and never coming up with a perfect solution, I've finally done it!

It's pretty much a straight forward algorithm, no need for looping and approximations.

This is how it works at a higher level:

  1. Calculate intersection times with each side's plane IF the path from current point to future point crosses that plane.
  2. Check each side's quadrant for single-side intersection, return the intersection.
  3. Determine the corner that the circle is colliding with.
  4. Solve the triangle between the current point, the corner, and the intersecting center (radius away from the corner).
  5. Calculate time, normal, and intersection center.

And now to the gory details!

The input to the function is bounds (which has a left, top, right, bottom) and a current point (start) and a future point (end).

The output is a class called Intersection which has x, y, time, nx, and ny.

  • {x, y} is the center of the circle at intersection time.
  • time is a value from 0 to 1 where 0 is at start and 1 is at end
  • {nx, ny} is the normal, used for reflecting the velocity to determine the new velocity of the circle

We start off with caching variables we use often:

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;

And calculating intersection times with each side's plane (if the vector between start and end pass over that plane):

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;
}

Now we try to see if it's strictly a side intersection (and not corner). If the point of collision lies on the side then return the intersection:

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 );
   }
}

We've gotten this far so we know either there's no intersection, or it's collided with a corner. We need to determine the corner:

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);
}

Now we have enough information to solve for the triangle. This uses the distance formula, finding the angle between two vectors, and the law of sines (twice):

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;

Now that we solved for all sides and angles, we can determine time and everything else:

// 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 );

Woo! That was fun... this has plenty of room for improvements as far as efficiency goes. You could reorder the side intersection checking to escape as early as possible while making as few calculations as possible.

I was hoping there would be a way to do it without trigonometric functions, but I had to give in!

Here's an example of me calling it and using it to calculate the new position of the circle using the normal to reflect and the intersection time to calculate the magnitude of reflection:

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}
 }

And I've posted the full code on pastebin with a completely interactive example where you can plot the starting and ending points and it shows you the time and resulting bounce off of the rectangle.

Example

If you want to get it running right away you'll have to download code from my blog, otherwise stick it in your own Java2D application.

EDIT: I've modified the code in pastebin to also include the collision point, and also made some speed improvements.

EDIT: You can modify this for a rotating rectangle by using that rectangle's angle to un-rotate the rectangle with the circle start and end points. You'll perform the intersection check and then rotate the resulting points and normals.

EDIT: I modified the code on pastebin to exit early if the bounding volume of the path of the circle does not intersect with the rectangle.

于 2013-09-13T15:47:18.750 回答
1

找到联系的时刻并不难：

您需要在碰撞前的时间步长 (B) 和后的时间步长 (A) 的圆和矩形的位置。计算圆心到它在A和B时刻碰撞的矩形线的距离（即点到线距离的常用公式），那么碰撞的时间为：

tC = dt*(dB-R)/(dA+dB),

其中 tC 是碰撞时间，dt 是时间步长，dB 是碰撞前到直线的距离，dA 是碰撞后的距离，R 是圆的半径。

这假设一切都是局部线性的，也就是说，您的时间步长相当小，并且速度等在您计算碰撞的时间步长中不会发生太大变化。毕竟，这是时间步长的点：在足够小的时间步长下，非线性问题是局部线性的。在上面的等式中，我利用了这一点：dB-R 是圆到直线的距离，dA+dB 是移动的总距离，所以这个问题只是将距离比等同于时间比，假设一切都是近似线性的时间步长内。（当然，在碰撞时刻，线性近似并不是最好的，但要找到碰撞时刻，问题是它是否在直到碰撞时刻的时间步长内是线性的。）

于 2013-09-10T01:31:29.080 回答
0

这是一个非线性问题，对吧？

您采取一个时间步，并通过使用该步开始时的速度计算的位移来移动球。如果发现重叠，请减小步长并重新计算直到收敛。

您是否假设球和矩形都是刚性的，没有变形？无摩擦接触？接触后你将如何处理球的运动？您是否正在转换到接触的坐标系（法线+切线），计算，然后转换回来？

这不是一个小问题。

也许你应该研究一个物理引擎，比如Box2D，而不是自己编码。

于 2013-09-09T18:59:28.207 回答