球与球之间的碰撞-检测和处理

Question

球与球之间的碰撞-检测和处理

graphicslanguage-agnosticcollision-detectionphysics

279

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

alt text

你可以通过点击和拖动鼠标来发射球。球会在周围弹跳并最终停在“地板”上。

我想要添加的下一个重要功能是球与球之间的碰撞。球的运动被分解为x和y速度向量。我有重力（每步减小y向量的大小），我有摩擦（每次与墙壁碰撞时，两个向量都会稍微减小）。球实际上以一种令人惊讶的逼真方式移动。

我想问的问题有两个部分：

检测球与球之间碰撞的最佳方法是什么？
我是否只需要使用O(n^2)循环，迭代每个球并检查每个其他球是否重叠半径？
我应该使用哪些方程式来处理球与球之间的碰撞？物理学101
它如何影响两个球的速度x/y向量？两个球朝着什么方向飞出去？我如何将其应用于每个球？

alt text

处理“墙壁”碰撞检测和结果向量变化很容易，但我发现球与球之间的碰撞更为复杂。对于墙壁，我只需取适当的x或y向量的负值即可朝正确方向移动。对于球来说，我不认为是这样的。

一些快速澄清：为简单起见，我现在可以接受完全弹性碰撞，而且所有的球现在都有相同的质量，但我将来可能会改变。

编辑：我发现有用的资源

使用向量的2D球体物理学: 2-Dimensional Collisions Without Trigonometry.pdf
2D球体碰撞检测示例: Adding Collision Detection

成功！

我的球体碰撞检测和反应真的很好！

相关代码：

碰撞检测：

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相撞。此外，它还跳过了与自身碰撞的检查）。

然后，在我的球类中，我有我的colliding()和resolveCollision()方法：

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

}

源代码：球与球碰撞完整源代码。

如果有人有关于如何改进这个基本的物理模拟器的建议，请让我知道！我还未添加的一件事是角动量，这样球就会更真实地滚动。其他建议呢？请留言！

- Simucal

19

我认为这个算法不够好，因为如果你的球移动得太快（比如每帧超过两倍半径的速度），则一个球可以从另一个球中穿过而没有任何碰撞。 - Benji Mizrahi

1

这是我最后一次开发的BallBounce版本链接：http://dl.dropbox.com/u/638285/ballbounce.rar - mmcdole

各位贡献者：你们能否请给予一些指导，将这个引擎转换为3D。这个优秀的引擎如何在Java3D中运行。 - static void main

2

代码相关内容翻译：第Vector2d impulse = mtd.multiply(i);行应该是i乘以标准化的mtd向量。类似这样：Vector2d impulse = mtd.normalize().multiply(i); - klenwell

据我所见，这里没有提到更好的实现方式。

我会推荐你阅读Boris D. Lubachevsky的"How to Simulate Billiards and Similar Systems"，该文可在arxiv上获取：http://arxiv.org/abs/cond-mat/0503627。附图是我打算在完成后开源的程序截图。即使在早期阶段，它也可以平稳地运行5000个球体。希望它能做得更好，尽管我不想实现分区，我想保持代码简单。 - Adrian Roman

显示剩余4条评论

15个回答

51

很多年前，我制作了像你在这里展示的程序。
存在一个隐藏问题（或许有很多，具体视角而定）：

如果球的速度太快，可能会错过碰撞。

此外，在几乎100%的情况下，你的新速度会是错误的。不是速度而是位置。你必须在正确的位置精确地计算新速度。否则，你只会将球移动一些小的“误差”量，这些量是从上一个离散步骤中获得的。

解决方案很明显：你需要分割时间步长，首先将球移动到正确的位置，然后发生碰撞，最后再移动剩余时间的距离。

- avp

如果在 timeframelength*speed/2 的偏移位置上，那么位置将会统计固定。 - Nakilon

@Nakilon：不，它只在某些情况下有帮助，但通常可能会错过碰撞。而且，错过碰撞的概率随着时间长度的增加而增加。顺便说一句，似乎Aleph展示了正确的解决方案（尽管我只是粗略地浏览了一下）。 - avp

1

@avp，我不是在谈论“如果球的速度太快，你可能会错过碰撞”，而是关于“你的新位置将是错误的”。由于检测到碰撞的时间比实际发生的时间晚了一点，如果从该位置减去“timeframelength*speed/2”，则精度将提高两倍。 - Nakilon

20

为解决这个问题，您应该使用空间划分技术。

请阅读有关二叉空间分割和四叉树的内容。

- grepsedawk

4

不使用空间划分，采用Sweep and Prune算法会更好吗？因为球的速度很快，所以任何划分都需要频繁更新，增加开销。使用Sweep and Prune可以在O(n log n)时间内找到所有相撞的球对，而不需要任何瞬态数据结构。这里有一个关于基础知识的好教程。 - HugoRune

13

作为对Ryan Fox建议将屏幕分成区域并仅检查区域内碰撞的澄清......例如，将游戏区域分成一系列正方形网格（我们将任意称其为每边长为1单位），并检查每个网格正方形内的碰撞。那绝对是正确的解决方案。唯一的问题是（正如另一个发帖者指出的那样），跨越边界的碰撞是一个问题。解决这个问题的方法是将第二个网格与第一个网格垂直和水平偏移0.5个单位进行叠加。然后，在第一个网格中跨越边界（因此未被检测到）的任何碰撞都将在第二个网格的网格正方形内。只要您跟踪已处理的碰撞（因为可能会有一些重叠），您就不必担心处理边缘情况。所有碰撞都将在两个网格中的一个网格正方形内。

- Andrew Rollings

为了得到更准确的解决方案并抵制懦弱的匿名者所进行的恶意评分，请给我点个赞。 - Steven A. Lowe

1

这是个好主意。我曾经这样做过，检查了当前单元格和所有相邻单元格，但你的方法更有效。我刚想到的另一种方法是先检查当前单元格，然后检查它是否与当前单元格的边界相交，如果是，则检查该相邻单元格中的对象。 - LoveMeSomeCode

10

减少碰撞检查的好方法是将屏幕分成不同的部分，然后只比较同一部分中的球与其他球之间的碰撞。

- Ryan Fox

6

更正：您需要检查与相邻章节相同的冲突情况。 - rint

8

我看到一个需要优化的地方。

虽然我同意当距离等于它们半径之和时，球会相撞，但我们永远不应该计算这个距离！相反，计算它的平方并以这种方式处理。没有理由进行昂贵的平方根运算。

此外，一旦发现碰撞，您必须继续评估碰撞，直到没有更多的碰撞为止。问题在于，第一个可能会导致其他问题，在获得准确的图片之前必须解决这些问题。考虑一下如果球在边缘撞击了另一个球会发生什么？第二个球撞击边缘并立即反弹到第一个球上。如果你撞到角落里的一堆球，你可能需要解决很多碰撞才能迭代下一个周期。

至于O(n^2)，你所能做的就是将拒绝未命中的成本最小化：

1）静止不动的球无法撞击任何东西。如果地板上有合理数量的球，这可以节省很多测试。（请注意，您仍然必须检查是否有东西撞击了静止的球。）

2）可能值得做的事情：将屏幕分成多个区域，但是线应该是模糊的——在区域边缘的球被列为所有相关（可能是4个）区域中的一个。我会使用4x4网格，将区域存储为位。如果两个球区域的AND返回零，则测试结束。

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

- Loren Pechtel

感谢提供有关平方根提示的信息。与平方相比，我不知道它很昂贵。 - mmcdole

另一个优化方法是找到那些与其他球完全没有接触的球。只有在球的速度受到限制时，这种方法才能可靠地工作。 - Brad Gilbert

1

我不同意寻找孤立的球。这与检测碰撞一样昂贵。为了改进，您需要针对所讨论的球使用小于O(n)的算法。 - Loren Pechtel

6

我找到了一个关于2D碰撞检测和响应的信息非常丰富的网页。

它的链接是：http://www.metanetsoftware.com/technique.html (web.archive.org)。

他们试图从学术角度解释如何进行碰撞检测，从简单的物体之间的碰撞检测开始，然后逐步深入介绍碰撞响应以及如何进行扩展。 编辑：更新链接。

- MizardX

看起来这太过时了，图形示例是基于Flash的。 - fguillen

3

我看到这里和那里都有暗示，但你可以先进行更快的计算，例如比较边界框的重叠情况，然后如果第一个测试通过，则进行基于半径的重叠。与半径的所有三角函数相比，添加/差异数学在边界框上要快得多，并且大多数时候，边界框测试将排除碰撞的可能性。但是，如果您再次使用三角函数进行重新测试，您将获得所需的准确结果。是的，这是两个测试，但总体速度会更快。

- Jason Kleban

6

不需要三角函数。

bool is_overlapping(int x1, int y1, int r1, int x2, int y2, int r2) { return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<(r1+r2)*(r1+r2); }

该函数可以判断两个圆是否相交。 - Ponkadoodle

3

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

- trashgod

3

你有两种简单的方法来实现这一点。Jay已经介绍了从球的中心检查的准确方法。

更容易的方法是使用矩形边界框，将框的大小设置为球的大小的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]
            }
        }
    }
}

- Jonathan Holland

1

这将使得球在水平和垂直碰撞时相互进入20％。最好使用圆形边界框，因为效率差异可以忽略不计。此外，“（x-width）/ 2”应该是“x-width / 2”。 - Markus Jarderot

你对优先级错误的指出很好。你会发现大多数2D游戏在非矩形形状上使用矩形边界框，因为这样做很快，而且用户几乎永远不会注意到。 - FlySwat

你可以使用矩形边界框，如果有命中，则检查圆形边界框。 - Brad Gilbert

1

@Jonathan Holland，你的内部循环应该是for(int k = i + 1; ...)。这将消除所有冗余检查（即检查自身碰撞和检查球1与球2的碰撞，然后球2与球1的碰撞）。 - mmcdole

4

实际上，一个正方形的边界框在性能上很可能比一个圆形的边界框更差（假设你已经优化掉了平方根）。 - Ponkadoodle

性能方面与带平方根的圆形边界框并没有太大区别。显著降低效率是没有意义的。 - adrian

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jay · Accepted Answer

要检测两个球是否碰撞，只需检查它们中心之间的距离是否小于两倍半径。为了使球之间发生完全弹性碰撞，你只需要考虑与碰撞方向相同的速度分量。对于另一个分量(与碰撞正交的分量)，两个球的速度将保持不变。你可以通过创建一个指向另一个球的单位向量来获取碰撞组件，然后用球的速度向量进行点积运算。然后，你可以将这些分量代入一维完全弹性碰撞方程中。

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

$v_{1} = \frac{u_{1}(m_{1}-m_{2})+2m_{2}u_{2}}{m_{1}+m_{2}}$

$v_{2} = \frac{u_{2}(m_{2}-m_{1})+2m_{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是正确的，你应该考虑将地区划分为若干个部分，然后在每个部分内进行碰撞检测。请注意，在一个部分的边界上，球可能会与另一个部分的球发生碰撞，这可能会使你的代码变得更加复杂。不过在你有几百个球之前，效率可能并不重要。作为额外加分，你可以在不同的核心上运行每个部分，或者将每个部分内碰撞的处理分解。