Java 如何修复碰撞响应中的圆形和矩形重叠？

How to fix circle and rectangle overlap in collision response?

提问by VanDir

Since in the digital world a real collision almost never happens, we will always have a situation where the "colliding" circle overlaps the rectangle.

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

How to put back the circle in the situation where it collides perfectly with the rectangle without overlap?

如何在圆与矩形完美碰撞而不重叠的情况下放回圆？

Suppose that the rectangle is stopped (null velocity) and axis-aligned.

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

I would solve this problem with a posterioriapproach (in two dimensions).

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

In short I have to solve this equation for t:

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

Where:

在哪里：

• is a number that answers to the question: how many frames ago did the collision happen perfectly?

• is the radius of the circle.

• is the center of the circle

• is its velocity.

• and are functions that return the x and y coordinates of the point where the circle and the rectangle collide (when the circle is at position, that is in the position in which perfectly collide with the rectangle).

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

• 是圆的半径。

• 是圆的中心

• 是它的速度。

• 和是返回圆和矩形碰撞点的 x 和 y 坐标的函数（当圆处于位置时，即在与矩形完全碰撞的位置）。

Recently I solved a similar problemfor collisions between circles, but now I don't know the law of the functions A and B.

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

采纳答案by ClickerMonkey

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.

1. 如果从当前点到未来点的路径穿过该平面，则计算与每侧平面的相交时间。
2. 检查每一边的象限是否有单边交点，返回交点。
3. 确定圆碰撞的角。
4. 求解当前点、角点和相交中心（远离角点的半径）之间的三角形。
5. 计算时间、法线和交点中心。

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.

输出是一个名为 Intersection 的类，它具有 x、y、时间、nx 和 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

• {x, y} 是相交时刻的圆心。
• time 是一个从 0 到 1 的值，其中 0 表示开始，1 表示结束
• {nx, ny} 为法线，用于反映速度以确定圆的新速度

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 pastebinwith 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.

我已经在pastebin上发布了完整的代码，其中包含一个完全交互式的示例，您可以在其中绘制起点和终点，并显示时间以及由此产生的矩形反弹。

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.

如果您想让它立即运行，您必须从我的博客下载代码，否则将其粘贴在您自己的 Java2D 应用程序中。

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

编辑：我修改了 pastebin 中的代码以包含碰撞点，并且还进行了一些速度改进。

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.

编辑：如果圆路径的边界体积与矩形不相交，我修改了 pastebin 上的代码以提前退出。

回答by duffymo

It's a non-linear problem, right?

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

You take a time step and move the ball by its displacement calculated using velocity at the start of the step. If you find overlap, reduce the step size and recalculate til convergence.

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

Are you assuming that the balls and rectangles are both rigid, no deformation? Frictionless contact? How will you handle the motion of the ball after contact is made? Are you transforming to a coordinate system of the contact (normal + tangential), calculating, then transforming back?

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

It's not a trivial problem.

这不是一个小问题。

Maybe you should look into a physics engine, like Box2D, rather than coding it yourself.

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

回答by tom10

Finding the moment of contact isn't too hard:

找到接触的时刻并不难：

You need the position of the circle and rectangle at the timestep before the collision (B) and the timestep after (A). Calculate the distance from the center of the circle to the line of the rectangle it collides with at times A and B (ie, a common formula for a distance from a point to a line), and then the time of collision is:

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

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

where tC is the time of collision, dt is the timestep, dB is the distance to line before the collision, dA is the distance after the collision, and R is the radius of the circle.

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

This assumes everything is locally linear, that is, that your timesteps are reasonably small, and so that the velocity, etc, don't change much in the timestep where you calculate the collision. This is, after all, the point of timesteps: in that with a small enough timestep, non-linear problems are locally linear. In the equation above I take advantage of that: dB-R is the distance from the circle to the line, and dA+dB is the total distance moved, so this question just equates the distance ratio to the time ratio assuming everything is approximately linear within the timestep. (Of course, at the moment of collision the linear approximation isn't its best, but to find the moment of collision, the question is whether it's linear within a timestep up toto moment of collision.)

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