球对球碰撞-检测和处理

在Stack Overflow社区的帮助下，我编写了一个非常基本但有趣的物理模拟器。

alt text

你点击并拖动鼠标来发射一个球。它会到处弹跳，最终停在“地板”上。

我想添加的下一个重要功能是球与球的碰撞。球的运动被分解成x和y速度向量。有重力(每一步y向量都有小幅度的减小)，有摩擦力(每一次与墙碰撞两个向量都有小幅度的减小)。这些球以一种令人惊讶的真实方式移动。

我想我的问题有两部分:

    <李> 检测球与球碰撞的最佳方法是什么? < br / > 我只是有一个O(n²)循环，遍历每个球，并检查每个球的半径是否重叠?李< / > <李> 我用什么方程来处理球与球的碰撞?101年物理 < br / > 它如何影响两个球的速度x/y向量?这两个球最终的方向是什么?我怎么把它应用到每个球上呢?李< / >

alt text

处理“墙”的碰撞检测;由此产生的矢量改变很容易，但我看到球-球碰撞的并发症更多。对于墙，我只需要取适当的x或y向量的负数，它就会朝着正确的方向移动。我可不这么认为。

一些快速的澄清:为了简单起见，我现在对完美弹性碰撞没有问题，而且我所有的球现在都有相同的质量，但未来我可能会改变这一点。

编辑:我发现有用的资源

2d带矢量的球物理:不含三角函数的二维碰撞
2d球碰撞检测示例:添加碰撞检测

成功!

我的球碰撞检测和响应工作得很好!

相关代码:

碰撞检测:

for (int i = 0; i < ballCount; i++)
{
for (int j = i + 1; j < ballCount; j++)
{
if (balls[i].colliding(balls[j]))
{
balls[i].resolveCollision(balls[j]);
}
}
}

这将检查每个球之间的碰撞，但跳过多余的检查(如果你必须检查球1是否与球2碰撞，那么你不需要检查球2是否与球1碰撞。此外，它跳过检查与自身的碰撞)。

然后，在我的球类中，我有我的collision()和resolveccollision()方法:

public boolean colliding(Ball ball)
{
float xd = position.getX() - ball.position.getX();
float yd = position.getY() - ball.position.getY();


float sumRadius = getRadius() + ball.getRadius();
float sqrRadius = sumRadius * sumRadius;


float distSqr = (xd * xd) + (yd * yd);


if (distSqr <= sqrRadius)
{
return true;
}


return false;
}


public void resolveCollision(Ball ball)
{
// get the mtd
Vector2d delta = (position.subtract(ball.position));
float d = delta.getLength();
// minimum translation distance to push balls apart after intersecting
Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d);




// resolve intersection --
// inverse mass quantities
float im1 = 1 / getMass();
float im2 = 1 / ball.getMass();


// push-pull them apart based off their mass
position = position.add(mtd.multiply(im1 / (im1 + im2)));
ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));


// impact speed
Vector2d v = (this.velocity.subtract(ball.velocity));
float vn = v.dot(mtd.normalize());


// sphere intersecting but moving away from each other already
if (vn > 0.0f) return;


// collision impulse
float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
Vector2d impulse = mtd.normalize().multiply(i);


// change in momentum
this.velocity = this.velocity.add(impulse.multiply(im1));
ball.velocity = ball.velocity.subtract(impulse.multiply(im2));


}

源代码:完整的源球到球对撞机。

如果有人对如何改进这个基本物理模拟器有一些建议，请告诉我!我还需要补充的一件事是角动量，这样球就会滚动得更真实。还有其他建议吗?请留下评论!

202643 次浏览
小开

减少碰撞检查数量的一个好方法是将屏幕分割成不同的部分。然后只将每个球与同一区域的球进行比较。

小开

您应该使用空间分区来解决这个问题。

仔细阅读 二进制空间分区 而且 四叉树 < / p >

小开
最佳答案

要检测两个球是否碰撞，只需检查它们中心之间的距离是否小于半径的两倍。要在两个球之间进行完美的弹性碰撞，你只需要考虑碰撞方向上的速度分量。对于两个球，另一个分量(与碰撞相切)保持不变。你可以通过创建一个指向从一个球到另一个球方向的单位向量来得到碰撞分量，然后与两个球的速度向量做点积。然后你可以把这些分量代入一个一维完全弹性碰撞方程。

维基百科有一个很好的整个过程的总结。对于任何质量的球，新的速度可以用以下公式计算(其中v1和v2是碰撞后的速度，u1和u2是碰撞前的速度):

< img src = " https://upload.wikimedia.org/math/a/b/6/ab6645eaf09c6da1ba47b0f662615140.png " alt = " v_{1} = \压裂{u_ {1} (m_ {1} -m_ {2}) + 2 m_ {2} u_ {2}} {m_ {1} + m_ {2}} " >

< img src = " https://upload.wikimedia.org/math/e/0/f/e0fa187fc3065bad45710620be5f7687.png " alt = " v_{2} = \压裂{u_ {2} (m_ {2} -m_ {1}) + 2 m_ {1} u_ {1}} {m_ {1} + m_ {2}} " >

如果两个球质量相同，那么速度只是互换。下面是我写的一些类似的代码:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
// Check whether there actually was a collision
if (a == b)
return;


Vector collision = a.position() - b.position();
double distance = collision.length();
if (distance == 0.0) {              // hack to avoid div by zero
collision = Vector(1.0, 0.0);
distance = 1.0;
}
if (distance > 1.0)
return;


// Get the components of the velocity vectors which are parallel to the collision.
// The perpendicular component remains the same for both fish
collision = collision / distance;
double aci = a.velocity().dot(collision);
double bci = b.velocity().dot(collision);


// Solve for the new velocities using the 1-dimensional elastic collision equations.
// Turns out it's really simple when the masses are the same.
double acf = bci;
double bcf = aci;


// Replace the collision velocity components with the new ones
a.velocity() += (acf - aci) * collision;
b.velocity() += (bcf - bci) * collision;
}

至于效率，Ryan Fox是对的，您应该考虑将区域划分为部分，然后在每个部分中进行碰撞检测。请记住，球可以在一个部分的边界上与其他球碰撞，所以这可能会使您的代码更加复杂。不过，在你有几百个球之前，效率可能并不重要。为了获得额外的奖励，你可以在不同的核心上运行每个部分，或者在每个部分中拆分碰撞处理。

小开

为了澄清Ryan Fox的建议，将屏幕分割成区域，并且只检查区域内的冲突……

例如，将游戏区域分割成一个方格网格(即每边有一个单位长度)，并检查每个方格网格之间的冲突。

这绝对是正确的解决方案。唯一的问题(正如另一个帖子指出的那样)是跨边界的碰撞是一个问题。

解决方案是在第一个网格上以0.5单位的垂直和水平偏移覆盖第二个网格。

然后，任何跨越第一个网格边界的碰撞(因此不会被检测到)将在第二个网格的方格内。只要跟踪已经处理过的碰撞(因为可能会有一些重叠)，就不必担心处理边缘情况。所有的碰撞都将发生在其中一个网格上的方格内。

小开

有两种简单的方法。杰伊已经介绍了从球的中心起跳的准确方法。

更简单的方法是使用矩形包围框，将框的大小设置为球的80%，这样就可以很好地模拟碰撞。

给你的球类添加一个方法:

public Rectangle getBoundingRect()
{
int ballHeight = (int)Ball.Height * 0.80f;
int ballWidth = (int)Ball.Width * 0.80f;
int x = Ball.X - ballWidth / 2;
int y = Ball.Y - ballHeight / 2;


return new Rectangle(x,y,ballHeight,ballWidth);
}

然后，在循环中:

// Checks every ball against every other ball.
// For best results, split it into quadrants like Ryan suggested.
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
Rectangle r1 = balls[i].getBoundingRect();


for (int k = 0; k < balls.count; k++)
{


if (balls[i] != balls[k])
{
Rectangle r2 = balls[k].getBoundingRect();


if (r1.Intersects(r2))
{
// balls[i] collided with balls[k]
}
}
}
}
小开

我在这里看到了一个需要优化的东西。

虽然我同意球的撞击距离是它们的半径之和，但实际上不应该计算这个距离!更确切地说，计算它是方形的，并以这种方式处理它。没有理由进行昂贵的平方根运算。

此外，一旦你发现了碰撞，你必须继续评估碰撞，直到不再有碰撞。问题是，第一个问题可能会导致其他问题在你得到准确的图像之前必须解决。考虑一下如果球在边缘处击中一个球会发生什么?第二个球击中边缘，立即反弹到第一个球。如果你撞到了角落里的一堆球，你可能会有很多碰撞，在你可以迭代下一个循环之前必须解决。

至于O(n²)，你所能做的就是尽量减少拒绝错过的代价:

1)不动的球打不到任何东西。如果有一个合理数量的球躺在地板上，这可以节省很多测试。(注意，你仍然必须检查是否有东西击中了固定球。)

2)可能值得做的事情:将屏幕划分为许多区域，但线条应该是模糊的——区域边缘的球被列为所有相关的区域(可能是4个)。我会使用4x4网格，将区域存储为位。如果两个球的区域的AND返回0，测试结束。

3)正如我提到的，不要做平方根。

小开

我找到了一个很棒的页面，上面有关于2D碰撞检测和响应的信息。

http://www.metanetsoftware.com/technique.html (web.archive.org)

他们试图从学术的角度解释这是如何做到的。他们从简单的对象对对象碰撞检测开始，然后转向碰撞响应以及如何扩展它。

编辑:更新链接

小开
嗯，几年前我做了一个像你在这里展示的程序 这里有一个隐藏的问题(或者很多，取决于观点):

  • 如果球的速度太 高，你可以错过碰撞。

而且，几乎在100%的情况下，你的新速度是错误的。不是速度，而是职位。你必须在正确的地方计算新的速度精确的。否则，你只是在一个小的“错误”量上移动球，这可以从前面的离散步骤中得到。

解决方案是显而易见的:你必须分割时间步长，首先移动到正确的位置，然后碰撞，然后在剩下的时间内移动。

小开

我看到它在这里和那里暗示，但你也可以先做一个更快的计算，比如，比较边界框的重叠，然后做一个基于半径的重叠，如果第一个测试通过。

边界盒的加法/差分数学运算要比半径的所有三角运算快得多，而且大多数情况下，边界盒测试会排除碰撞的可能性。但是如果你用三角函数重新测试，你会得到你想要的准确结果。

是的，这是两个测试，但总体来说会更快。

小开

这个KineticModel是Java中引用方法的实现。

小开

我使用HTML Canvas元素在JavaScript中实现了这段代码，它以每秒60帧的速度生成了出色的模拟。我以随机位置和速度收集一打球开始模拟。我发现，在更高的速度下，一个小球和一个大得多的球之间的掠撞导致小球看起来坚持到大球的边缘，并在分离之前围绕大球移动了大约90度。(我不知道是否有人观察到这种行为。)

一些计算记录显示，在这些情况下，最小平移距离不足以防止相同的球在下一个时间步中发生碰撞。我做了一些实验，发现我可以通过根据相对速度放大MTD来解决这个问题:

dot_velocity = ball_1.velocity.dot(ball_2.velocity);
mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle));
mtd.multplyScalar(mtd_factor);

我验证了在修正之前和之后，每次碰撞的总动能都是守恒的。mtd_factor中的0.5值大约是在碰撞后总是导致球分离的最小值。

虽然这个修复在系统的精确物理中引入了少量的错误，但代价是现在可以在浏览器中模拟非常快的球，而不减少时间步长。

小开

改进问题中给出的圆碰撞检测检测圆的解决方案:

float dx = circle1.x - circle2.x,
dy = circle1.y - circle2.y,
r = circle1.r + circle2.r;
return (dx * dx + dy * dy <= r * r);

它避免了不必要的“如果有两个回报”;以及使用多余的变量。

小开

如果你有很多球，我会考虑使用四叉树。为了确定弹跳的方向，只需使用基于碰撞法向的简单能量守恒公式。弹性，重量和速度会让它更真实一些。

小开

经过一些尝试和错误，我使用了这个文档的2D碰撞方法:https://www.vobarian.com/collisions/2dcollisions2.pdf (OP链接到)

我在一个使用p5js的JavaScript程序中应用了这一点，它工作得很完美。我之前曾尝试使用三角方程，虽然它们确实适用于特定的碰撞，但我无法找到一个适用于每一次碰撞的方程，无论它发生的角度是多少。

本文档中解释的方法没有使用任何三角函数，它只是简单的向量操作，我将此推荐给任何试图实现球与球碰撞的人，以我的经验，三角函数很难推广。我请我大学里的一位物理学家教我怎么做，他告诉我不要用三角函数来麻烦，并向我展示了一个类似于文档中链接的方法。

注:我的质量都是相等的，但这可以推广到不同的质量使用在文件中提出的方程。

下面是我计算碰撞后速度矢量的代码:

    //you just need a ball object with a speed and position vector.
class TBall {
constructor(x, y, vx, vy) {
this.r = [x, y];
this.v = [0, 0];
}
}


//throw two balls into this function and it'll update their speed vectors
//if they collide, you need to call this in your main loop for every pair of
//balls.
function collision(ball1, ball2) {
n = [ (ball1.r)[0] - (ball2.r)[0], (ball1.r)[1] - (ball2.r)[1] ];
un = [n[0] /  vecNorm(n), n[1] / vecNorm(n) ] ;
ut = [ -un[1], un[0] ];
v1n = dotProd(un, (ball1.v));
v1t = dotProd(ut, (ball1.v) );
v2n = dotProd(un, (ball2.v) );
v2t = dotProd(ut, (ball2.v) );
v1t_p = v1t; v2t_p = v2t;
v1n_p = v2n; v2n_p = v1n;
v1n_pvec = [v1n_p * un[0], v1n_p * un[1] ];
v1t_pvec = [v1t_p * ut[0], v1t_p * ut[1] ];
v2n_pvec = [v2n_p * un[0], v2n_p * un[1] ];
v2t_pvec = [v2t_p * ut[0], v2t_p * ut[1] ];
ball1.v = vecSum(v1n_pvec, v1t_pvec); ball2.v = vecSum(v2n_pvec, v2t_pvec);
}
小开

这是一个支持质量的简单例子。

private void CollideBalls(Transform ball1, Transform ball2, ref Vector3 vel1, ref Vector3 vel2, float radius1, float radius2)
{
var vec = ball1.position - ball2.position;
float dis = vec.magnitude;
if (dis < radius1 + radius2)
{
var n = vec.normalized;
ReflectVelocity(ref vel1, ref vel2, ballMass1, ballMass2, n);


var c = Vector3.Lerp(ball1.position, ball2.position, radius1 / (radius1 + radius2));
ball1.position = c + (n * radius1);
ball2.position = c - (n * radius2);
}
}


public static void ReflectVelocity(ref Vector3 vel1, ref Vector3 vel2, float mass1, float mass2, Vector3 intersectionNormal)
{
float velImpact1 = Vector3.Dot(vel1, intersectionNormal);
float velImpact2 = Vector3.Dot(vel2, intersectionNormal);


float totalMass = mass1 + mass2;
float massTransfure1 = mass1 / totalMass;
float massTransfure2 = mass2 / totalMass;


vel1 += ((velImpact2 * massTransfure2) - (velImpact1 * massTransfure2)) * intersectionNormal;
vel2 += ((velImpact1 * massTransfure1) - (velImpact2 * massTransfure1)) * intersectionNormal;
}

提交答案