球对球碰撞 – 检测和处理
在Stack Overflow社区的帮助下，我写了一个非常基本的但有趣的物理模拟器。
你点击并拖动鼠标来启动一个球。 它会弹跳，最终停在“地板”上。
我想添加的下一个重要特征是球碰撞。 球的运动被分解成斧和速度vector。 我有重力（y向量的每个步骤的小的减less），我有摩擦（两个向量与墙的每次碰撞的小的减less）。 这些球以一种令人惊讶的现实方式诚实地移动。
我想我的问题有两个部分：
- 检测球对球碰撞的最佳方法是什么？
我只是有一个O（n ^ 2）循环遍历每个球，并检查其他每一个球，看看它是否半径重叠？ - 我用什么方程来处理球碰撞？ 物理101
它如何影响两个球速度x / y向量？ 这两个球头的方向是什么？ 我如何将这个应用到每个球？
处理“墙壁”的碰撞检测和由此产生的vector变化很容易，但是我发现球球碰撞更复杂。 有了墙壁，我只需要取对应的x或yvector的负值，然后按照正确的方向。 用球我不认为这是这样的。
一些快速的澄清：为了简单起见，我现在可以完美的弹性碰撞了，现在我所有的球都有相同的质量，但是我可能会在将来改变这一点。
编辑：我发现有用的资源
2d球物理学与向量： 二维碰撞没有Trigonometry.pdf
二维球碰撞检测示例： 添加碰撞检测
成功！
我有球碰撞检测和响应工作伟大！
相关代码：
碰撞检测：
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.multiply(i); // change in momentum this.velocity = this.velocity.add(impulse.multiply(im1)); ball.velocity = ball.velocity.subtract(impulse.multiply(im2)); }
源代码： 球对撞机的完整源代码。
如果有人对如何改善这个基本的物理模拟器有一些build议让我知道！ 有一件事我还没有添加angular动量，所以球会滚动更逼真。 还有其他build议吗？ 发表评论！
要检测两个球是否碰撞，只要检查它们的中心之间的距离是否小于半径的两倍。 要在球之间进行完美的弹性碰撞，只需要考虑碰撞方向的速度分量。 另一个组件（相撞的切线）将保持相同的两个球。 您可以通过创build一个单位vector指向从一个球到另一个球的方向，然后用球的速度vector获得点积来得到碰撞分量。 然后，您可以将这些组件插入一维完美弹性碰撞方程。
维基百科有一个很好的总结整个过程 。 对于任何质量的球，新的速度可以使用公式计算（其中v1和v2是碰撞后的速度，而u1，u2来自之前）：
如果球具有相同的质量，那么只需切换速度。 这是我写的一些代码，它做了类似的事情：
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; }
至于效率，瑞恩·福克斯是对的，你应该考虑把区域分割成几部分，然后在每一部分内部进行碰撞检测。 请记住，球可以与一个部分的边界上的其他球碰撞，所以这可能会使您的代码更加复杂。 效率可能不会影响，直到你有几百个球。 对于奖励积分，您可以在不同核心上运行每个部分，或者分割每个部分内的冲突处理。
好吧，几年前我做了这个程序就像你在这里介绍的。
有一个隐藏的问题（或许多，取决于观点）：
- 如果球的速度太高，可能会错过碰撞。
而且，几乎在100％的情况下，你的新速度将是错误的。 那么，不是速度 ，而是位置 。 您必须在正确的位置准确计算新的速度。 否则，你只需要把一些小的“错误”量转移到前面的离散步骤。
解决办法是显而易见的：你必须把时间步骤分开，首先你转移到正确的位置，然后碰撞，然后转移到剩下的时间。
你应该使用空间分区来解决这个问题。
阅读二进制空间分区和四叉树
为了澄清Ryan Fox的build议，将屏幕分割成区域，并只检查区域内的碰撞。
例如将游戏区域分割成一个正方形网格（这将任意地说是每边一个单位长度），并检查每个网格正方形内的碰撞。
这绝对是正确的解决scheme。 唯一的问题是（如另一张海报所指出的）跨界碰撞是一个问题。
解决这个问题的方法是将第二个网格以0.5单位垂直和水平偏移量叠加到第一个网格上。
那么，在第一个网格中跨越边界（因此未被检测到）的任何碰撞将在第二个网格中的网格正方形内。 只要你跟踪你已经处理的冲突（因为可能有一些重叠），你不必担心处理边缘情况。 所有的碰撞将在一个网格上的一个方格内。
减less碰撞检查次数的一个好方法是将屏幕分成不同的部分。 然后，您只能将每个球与同一部分的球进行比较。
有一件事我看到在这里优化。
虽然我确实认为，当距离是他们半径的总和时，球应该不会真正计算出这个距离！ 相反，计算它是正方形的，并以这种方式工作。 没有理由昂贵的平方根操作。
而且，一旦发现碰撞，你必须继续评估碰撞，直到不再有任何碰撞。 问题是，第一个可能会导致其他人必须得到解决之前，你得到一个准确的图片。 考虑一下如果球在边缘击球，会发生什么？ 第二球击中边缘，立即回弹到第一球。 如果你在angular落里碰到一堆球，在迭代下一个周期之前，你可能会碰到很多碰撞。
至于O（n ^ 2），你所能做的就是尽量减less错过的成本：
1）不移动的球不能击中任何东西。 如果在地板上有合理数量的球，这可以节省很多testing。 （请注意，您还必须检查是否有东西碰到了固定球。）
2）可能值得做的事情：将屏幕划分成多个区域，但是线条应该模糊 – 区域边缘的球被列为所有相关（可以是4个）区域。 我会使用4×4网格，将区域存储为位。 如果两个球区的区域的AND返回零，则结束testing。
3）正如我所说，不要做平方根。
我发现了一个非常好的页面，其中包含2D中碰撞检测和响应的信息。
http://www.metanetsoftware.com/technique.html
他们试图从学术angular度解释它是如何完成的。 他们从简单的对象到对象的碰撞检测开始，然后转向碰撞响应以及如何扩展它。
编辑：更新的链接
你有两个简单的方法来做到这一点。 周杰伦已经从球的中心覆盖了检查的准确方式。
更简单的方法是使用一个矩形边界框，将您的框的大小设置为球的大小的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] } } } }
我看到它在这里和那里暗示，但你也可以先做一个更快的计算，比如比较边界框的重叠，然后做一个基于半径的重叠，如果第一次testing通过。
边界框的加/减math运算比半径的所有三angular形要快得多，而大多数时候，边界框testing将消除碰撞的可能性。 但是，如果您再用trig进行重新testing，您将得到您正在寻找的准确结果。
是的，这是两个testing，但总体来说会更快。
这个KineticModel是Java中引用方法的一个实现。
我使用HTML Canvas元素在JavaScript中实现了这个代码，它以每秒60帧的速度产生了精彩的模拟效果。 我以随机的位置和速度收集了十几个球，开始了模拟。 我发现，在更高的速度下，一个小球和一个更大的球之间的一次扫射碰撞使得小球出现在大球的边缘，并且在分离之前围绕大球移动了大约90度。 （我想知道是否有人观察到这种行为。）
计算的一些logging表明，在这些情况下的最小平移距离不足以防止相同的球在下一个时间步骤发生碰撞。 我做了一些试验，发现我可以通过根据相对速度放大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值大约是发现碰撞后始终使球分离的最小值。
尽pipe这个修正在系统的确切物理学中引入了less量的误差，但是折中的是，现在可以在浏览器中模拟非常快速的球而不会减小时间步长。
正如我在这里看到的，没有提到一个更好的实现方法。 
我将向您推荐由Boris D. Lubachevsky撰写的“如何模拟台球和类似系统”，可在arxiv上获得： http ://arxiv.org/abs/cond-mat/0503627附图是一个程序的截图我打算在完成时打开源代码。 即使在早期阶段，5000个球体运行也相当顺利。 希望能做的更好，虽然我不想实现扇区化，但我想保持代码容易理解。 该说明将在http://compphys.go.ro上提供;
稍后编辑：代码现在在GitHub上可用： https ： //github.com/aromanro/EventMolecularDynamics描述在博客上： http : //compphys.go.ro/event-driven-molecular-dynamics/
