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

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

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

假设矩形停止(零速度)和轴对齐。

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

总之,我必须为t求解这个等式

在此处输入图像描述

哪里:

  • Ť 是一个回答问题的数字:碰撞发生了多少帧之前?

  • [R 是圆的半径。

  • (x,y) 是圆的中心

  • (v.x,v.y) 是它的速度。

  • 在)B(t)的 是返回圆和矩形碰撞的点的x和y坐标的函数(当圆圈处于时 (x  -  t * v.x,y  -  t * v.y) 位置,即处于与矩形完全碰撞的位置)。

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

经过多年的盯着这个问题,从来没有想出一个完美的解决方案,我终于做到了!

它几乎是一个简单的算法,不需要循环和近似。

这是它在更高层次上的工作方式:

  1. 如果从当前点到未来点的路径穿过该平面,则计算每个侧面的交叉时间。
  2. 检查每侧的象限以进行单侧交叉,返回交叉点。
  3. 确定圆圈碰撞的角落。
  4. 求解当前点,拐角和交叉中心(距离拐角的半径)之间的三角形。
  5. 计算时间,法线和交叉点中心。

现在到了血淋淋的细节!

函数的输入是边界(具有左,上,右,下)和当前点(开始)和未来点(结束)。

输出是一个名为Intersection的类,它有x,y,time,nx和ny。

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

现在我们有足够的信息来解决三角形。 这使用距离公式,找到两个向量之间的角度,以及正弦定律(两次):

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

呜! 这很有趣......就效率而言,这有很大的改进空间。 您可以尽可能早地重新排序侧交叉检查以进行转义,同时尽可能少地进行计算。

我希望在没有三角函数的情况下有办法实现它,但我不得不放弃!

这是我调用它并使用它来计算圆的新位置的示例,使用法线reflection和交叉时间来计算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} } 

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

例

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

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

编辑:您可以使用该矩形的角度对旋转的矩形进行修改,以使用圆的起点和终点取消旋转矩形。 您将执行交叉检查,然后旋转结果点和法线。

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

找到联系的时刻并不太难:

在碰撞前的时间步长(B)和(A)后的时间步长需要圆和矩形的位置。 计算从圆心到其与A和B碰撞的矩形线的距离(即从点到线的距离的公式),然后碰撞时间为:

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

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

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

这是一个非线性问题,对吧?

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

你是否假设球和矩形都是刚性的,没有变形? 无摩擦接触? 接触完成后你将如何处理球的运动? 您是否正在转换为接触的坐标系(正常+切向),计算,然后转换回来?

这不是一个小问题。

也许你应该研究像Box2D这样的物理引擎,而不是自己编写代码。