views:

12552

answers:

10

With the help of the Stack Overflow community I've written a pretty basic-but fun physics simulator.

alt text

You click and drag the mouse to launch a ball. It will bounce around and eventually stop on the "floor".

My next big feature I want to add in is ball to ball collision. The ball's movement is broken up into a x and y speed vector. I have gravity (small reduction of the y vector each step), I have friction (small reduction of both vectors each collision with a wall). The balls honestly move around in a surprisingly realistic way.

I guess my question has two parts:

  1. What is the best method to detect ball to ball collision?
    Do I just have an O(n^2) loop that iterates over each ball and checks every other ball to see if it's radius overlaps?
  2. What equations do I use to handle the ball to ball collisions? Physics 101
    How does it effect the two balls speed x/y vectors? What is the resulting direction the two balls head off in? How do I apply this to each ball?

alt text

Handling the collision detection of the "walls" and the resulting vector changes were easy but I see more complications with ball-ball collisions. With walls I simply had to take the negative of the appropriate x or y vector and off it would go in the correct direction. With balls I don't think it is that way.

Some quick clarifications: for simplicity I'm ok with a perfectly elastic collision for now, also all my balls have the same mass right now, but I might change that in the future.

In case anyone is interested in playing with the simulator I have made so far, I've uploaded the source here (EDIT: Check the updated source below).


Edit: Resources I have found useful

2d Ball physics with vectors: 2-Dimensional Collisions Without Trigonometry.pdf
2d Ball collision detection example: Adding Collision Detection


Success!

I have the ball collision detection and response working great!

Relevant code:

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

This will check for collisions between every ball but skip redundant checks (if you have to check if ball 1 collides with ball 2 then you don't need to check if ball 2 collides with ball 1. Also, it skips checking for collisions with itself).

Then, in my ball class I have my colliding() and resolveCollision() methods:

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

}

alt text

Source Code: Complete source for ball to ball collider.
Binary: Compiled binary in case you just want to try bouncing some balls around.

If anyone has some suggestions for how to improve this basic physics simulator let me know! One thing I have yet to add is angular momentum so the balls will roll more realistically. Any other suggestions? Leave a comment!

+6  A: 

A good way of reducing the number of collision checks is to split the screen into different sections. You then only compare each ball to the balls in the same section.

Ryan Fox
+9  A: 

You should use space partitioning to solve this problem.

Read up on Binary Space Partitioning and Quadtrees

grepsedawk
Thanks for the information, I appreciate it.
Simucal
+32  A: 
Jay Conrod
Lets say masses of the two balls aren't equal. How does that effect the vector change between balls?
Simucal
It's been a while since grade 12, but I think they get a ratio of the momentum corresponding to the ratio of the masses.
Ryan Fox
Edited to include equations from Wikipedia
Jay Conrod
@Jay, just to point out.. that one equation image you added is for a 1 dimensional collision, not 2 dimensional.
Simucal
@simucal. not true... u and v are vectors in that equation. That is, they have x, y (and z) components.
Andrew Rollings
@Simucal, you are right, they are for the one dimensional case. For more dimensions, just use the components of the velocity that are in line with the collision (aci, bci in code). The other components are orthogonal to the collision and will not change, so you don't need to worry about them.
Jay Conrod
+7  A: 

As a clarification to the suggestion by Ryan Fox to split the screen into regions, and only checking for collisions within regions...

e.g. split the play area up into a grid of squares (which will will arbitrarily say are of 1 unit length per side), and check for collisions within each grid square.

That's absolutely the correct solution. The only problem with it (as another poster pointed out) is that collisions across boundaries are a problem.

The solution to this is to overlay a second grid at a 0.5 unit vertical and horizontal offset to the first one.

Then, any collisions that would be across boundaries in the first grid (and hence not detected) will be within grid squares in the second grid. As long as you keep track of the collisions you've already handled (as there is likely to be some overlap) you don't have to worry about handling edge cases. All collisions will be within a grid square on one of the grids.

Andrew Rollings
+1 for a more accurate solution, and to counter the cowardly drive-by downvoter
Steven A. Lowe
thats a good idea. I did this once and i checked the current cell and all neighboring cells, but your method is more efficient. Another way I just thought of is to check the current cell, and then check to see if it intersects with the current cells boundaries, and if so, check objects in THAT neighboring cell.
LoveMeSomeCode
A: 

You have two easy ways to do this. Jay has covered the accurate way of checking from the center of the ball.

The easier way is to use a rectangle bounding box, set the size of your box to be 80% the size of the ball, and you'll simulate collision pretty well.

Add a method to your ball class:

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

Then, in your loop:

// 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]
            }
        }
    }
}
FlySwat
This would make the balls go into each other 20% on horizontal and vertical collisions. Might as well use circular bounding boxes, as the efficiency difference negligible. Also, `(x-width)/2` should be `x-width/2`.
MizardX
Good call on the precedence typo. You'll find that most 2d games use rectangular bounding boxes on non rectangular shapes because it is fast, and the user almost never notices anyway.
FlySwat
You could do rectangular bounding box, then if it has a hit check the circular bounding box.
Brad Gilbert
@Jonathan Holland, your inner loop should be for(int k = i + 1; ...) This will get rid of all the redundant checks. (ie checking with collision of self and checking collision ball1 with ball2 then ball2 with ball1).
Simucal
Actually, a square bounding box is likely to be _worse_ performance-wise than a circular bounding box (assuming you've optimized the square root away)
Wallacoloo
+3  A: 

One thing I see here to optimize.

While I do agree that the balls hit when the distance is the sum of their radii one should never actually calculate this distance! Rather, calculate it's square and work with it that way. There's no reason for that expensive square root operation.

Also, once you have found a collision you have to continue to evaluate collisions until no more remain. The problem is that the first one might cause others that have to be resolved before you get an accurate picture. Consider what happens if the ball hits a ball at the edge? The second ball hits the edge and immediately rebounds into the first ball. If you bang into a pile of balls in the corner you could have quite a few collisions that have to be resolved before you can iterate the next cycle.

As for the O(n^2), all you can do is minimize the cost of rejecting ones that miss:

1) A ball that is not moving can't hit anything. If there are a reasonable number of balls lying around on the floor this could save a lot of tests. (Note that you must still check if something hit the stationary ball.)

2) Something that might be worth doing: Divide the screen into a number of zones but the lines should be fuzzy--balls at the edge of a zone are listed as being in all the relevant (could be 4) zones. I would use a 4x4 grid, store the zones as bits. If an AND of the zones of two balls zones returns zero, end of test.

3) As I mentioned, don't do the square root.

Loren Pechtel
Thank you for the information on the square root tip. Didn't know about its expensive nature when compared to the square.
Simucal
Another optimization would be to find balls which are nowhere near any other balls. This would work reliably only if the velocities of the balls are constrained.
Brad Gilbert
I disagree on looking for isolated balls. That's just as expensive as detecting the collision. To improve things you need something that's less than O(n) for the ball in question.
Loren Pechtel
Excellent post.
DV
+3  A: 

I found an excellent page with information on collision detection and response in 2D.

http://www.metanetsoftware.com/technique.html

They try to explain how it's done from an academic point of view. They start with the simple object-to-object collision detection, and move on to collision response and how to scale it up.

Edit: Updated link

MizardX
+1, good find Mizard.
Simucal
The new link is http://www.metanetsoftware.com/technique.html
DV
+12  A: 

Well, years ago I made the program like you presented here.
There is one hidden problem (or many, depends on point of view):

  • If the speed of the ball is too high, you can miss the collision.

And also, almost in 100% cases your new speeds will be wrong. Well, not speeds, but positions. You have to calculate new speeds precisely in the correct place. Otherwise you just shift balls on some small "error" amount, which is available from the previous discrete step.

The solution is obvious: you have to split the timestep so, that first you shift to correct place, then collide, then shift for the rest of the time you have.

avp
+1, insightful. He's indeed likely to need that insight next.
redtuna
[Here](http://www.a-coding.com/2010/10/predictive-collision-detection.html) is a way of doing the collision detection without this problem.
Aleph
A: 

hey people !

i really like this blog and all the details about collision detection in 2D ! i am working on a project where i have to deal with collision (3D billiard in XNA)

my question is can anyone explain me please how to use this concept to 3D in XNA !

i will appreciate your help !

thanks in advance

Marius

Marius
+1  A: 

I see it hinted here and there, but you could also do a faster calculation first, like, compare the bounding boxes for overlap, and THEN do a radius-based overlap if that first test passes.

The addition/difference math is much faster for a bounding box than all the trig for the radius, and most times, the bounding box test will dismiss the possibility of a collision. But if you then re-test with trig, you're getting the accurate results that you're seeking.

Yes, it's two tests, but it will be faster overall.

uosɐſ
You don't need trig. `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); }`
Wallacoloo