如何修复碰撞响应中的圆和矩形重叠？ [英] How to fix circle and rectangle overlap in collision response?
问题描述
由于在数字世界中几乎不会发生真正的碰撞，我们总会遇到碰撞圆与矩形重叠的情况。
如何在不与重叠的矩形完美碰撞的情况下放回圆圈？
假设矩形停止（零速度）和轴对齐。
我会用，但现在我不知道A和B函数的定律。
经过多年的盯着看这个问题，从来没有提出一个完美的解决方案，我终于做到了！
这几乎是一个简单的算法，不需要循环和近似。 / p>
这是它在更高级别的工作方式：
- 计算交叉时间每一侧的平面如果从当前点到未来点的路径穿过该平面。
- 检查每一侧的象限以获得单侧交叉，返回交叉点。
- 确定圆与之碰撞的角落。
- 解决当前点，角落和相交中心（距离角落的半径）之间的三角形。
- 计算时间，法线和交叉点中心。
现在要了解血腥细节！
函数的输入是边界（有左，上，右，下）和当前点（开始）和未来点（结束） ）。
输出是一个名为Intersection的类，它有x，y，time，nx和ny。
- {x，y}是交叉时间圆的中心。
- 时间是从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）{
返回新的交点（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）{
返回新的交点（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）{
返回新的交点（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）{
返回新的交点（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;
}否则if（rtime！= Float.MAX_VALUE）{
cornerX = R;
}
if（ttime！= Float.MAX_VALUE）{
cornerY = T;
}否则if（btime！= Float.MAX_VALUE）{
cornerY = B;
}
//我们不会越过一边的时间，但我们确实在它的角落
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;
//角度太大，如果（Math.abs（angle1Sin）> 1.0f）{
返回null}，则不能有交叉
;
}
double angle1 = Math.PI - Math.asin（angle1Sin）;
double angle2 = Math.PI - innerAngle - angle1;
double intersectionDistance = radius * Math.sin（angle2）/ innerAngleSin;
现在我们已经解决了所有方面和角度，我们可以确定时间和其他所有内容：
//解决时间
浮点时间=（浮点数）（intersectionDistance / lineLength）;
//如果时间超出边界，则返回null。该算法可以
//返回一个负时间，表示前一个交叉点。
if（时间> 1.0f ||时间< 0.0f）{
返回null;
}
//求解交点并且正常
浮点数ix =时间* dx + start.x;
float iy = time * dy + start.y;
float nx =（float）（（ix-cornerX）* inverseRadius）;
float ny =（float）（（iy - cornerY）* inverseRadius）;
返回新的交点（ix，iy，time，nx，ny）;
喔！这很有趣......就效率而言，这有很大的改进空间。您可以尽可能早地重新排序侧交叉检查以进行转义，同时尽量减少计算。
我希望有一种方法可以在没有三角函数的情况下进行，但我不得不放弃！
这是我调用它并使用它来计算圆的新位置的示例，使用法线反射和交叉时间计算反射的大小：
Intersection inter = handleIntersection（bounds，start，end，radius）;
if（inter！= null）
{
//项目未来位置
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;
//新圈子位置= {newx，newy}
}
我已经在下载代码，否则将其粘贴在您自己的Java2D应用程序中。
编辑：
我修改了pastebin中的代码以包含碰撞点，并且还提高了速度改进。
编辑：
您可以通过使用该矩形的角度来修改旋转矩形，以使用圆的起点和终点取消旋转矩形。您将执行交叉检查，然后旋转结果点和法线。
编辑：
如果边界体积我修改了pastebin上的代码以提前退出圆的路径与矩形不相交。
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 posteriori approach (in two dimensions).
In short I have to solve this equation for 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).
Recently I solved a similar problem for collisions between circles, but now I don't know the law of the functions A and B.
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:
- Calculate intersection times with each side's plane IF the path from current point to future point crosses that plane.
- Check each side's quadrant for single-side intersection, return the intersection.
- Determine the corner that the circle is colliding with.
- Solve the triangle between the current point, the corner, and the intersecting center (radius away from the corner).
- 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.
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.
这篇关于如何修复碰撞响应中的圆和矩形重叠？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
