Collision between multiple objects

Question

I'm writing a simple physics system for fun, and I've run into a problem that has me stuck.

The basic algorithm now is:

1. Move an object
2. Check for collisions
3. If there was a collision
   • Move the object the minimum distance to resolve the collision.
   • Adjust the velocity based on the normals, masses, etc

I have one moving body moving toward two, static, massless, bodies.

The moving object is translated in one step to collide with one of the bodies.

I respond by finding the smallest distance I can move so that they are no longer colliding. In this case, that means moving the dynamic body straight down. However, now it is colliding with another box.

I repeat the same thing with that box, trying to move the dynamic box so that it is no longer colliding, but that pushes it back into the first box. This repeats forever. Is my algorithm fundamentally flawed?

Typical

Answer 1

Instead of moving down once a collision has been detected it would be better to move back in the direction you came from. That way you have a guarantee that eventually you must end up in a state where there are no collisions if we assume that the initial state had no collisions.

We need to find out by how much we need to shrink (scale) v to fit it into the object intersection. The shrunk v will have the right magnitude, so that if we move backwards in the direction of -v by that magnitude, then we will no-longer intersect.

Let's assume an intersection consists of a x_intersection and a y_intersection component. To find out by how much we need to move backwards to no longer intersect we need to scale the original v = (v_x, v_y) vector. If the x_intersection is the smaller intersection then we scale v by x_intersection / v_x and move our object back by -v * x_intersection / v_x. This means we move back by -(x_intersection, x_intersection * v_y/v_x). If the y_intersection is the smaller intersection then we scale v by y_intersection / v_y and move our object backwards by -v * y_intersection / v_y = -(y_intersection * v_x/v_y, y_intersection).

So I would say the steps in your algorithm could be:

1. Move object by some move vector v
2. Check for all collisions

3. If there was a collision

   • For all collision objects find the minimum scaling of v by which we we would need to move back. This scaling can be computed as the minimum of two ratios

     given v = (v_x, v_y)
     min_i = min(x_intersection / v_x, y_intersection / v_y)    
     

   • Find the minimum scaling ration across all objects.

     min_o = min(min_i) for all i
     

   • Move object back in direction of vector obtained by scaling the negative move direction with the minimum ratio. That is v2 = (min_o*-v) where v2 is the vector we use to move back.

4. Go back to step 2

For example: first pick w:

Then pick u2:

Done :

Hushhush

Nice images, but your math for calculating how far to go back seems wrong to me. Since min_o can be a really small value, 1/min_o is potentially really big. Also if you look at units it seems wrong: both v and min_o are distances, so -v / min_o is dimensionless, you cannot assign that to a distance vector v2. I don't totally understand how you define min_o, but you probably should just add or subtract something, or like in my answer, just go back to the previous position and redo the minimum possible step. – Skyrocket

@BasSwinckels Oh crap, yeah your right. What I was going for is to scale the v vector down to the size of the smallest intersection and then subtract it from v. But to do that I have scale by v_x / min_o if the smallest intersection was in the x direction or by v_y / min_o if the intersection was in the y direction. Otherwise it is dimension-less like you said. – Hushhush

@BasSwinckels Ok I've edited and I think I fixed the math issue. The new scaling preserves the units and doesn't suffer if min_o if very small. It should be the correct scaling to shrink v down the to the required size to fit into the object intersection. – Hushhush

I dont think this method would work well. What if I was sliding across a flat surface but kept time stepping backwards because I was colliding with the floor, I would not be able to move. – Maye

Answer 2

One possible solution that might be robust against the problem you described (totally untested):

1. Move your object for a full time-step dt

2. Check for collisions with other objects, this might be more than one object

3. Calculate the 'time of impact' by interpolation, which is some real number that is smaller than the time step. Do this for each object you collided with, and choose the minimum one. This gives you the time to the first collision t_col < dt.

4. Redo the last step, but now move the object only for t_col so that it exactly hits the object and then start flipping velocities and other collision related physics. You can now either finish the step here if you are lazy (probably ok, since dt should be small), or continue to move for another dt - t_col and see if you hit something else.

This is not something I invented just now, but is similar to the zero-cross detection that Simulink uses to simulate exactly this kind of discontinuous problems.

Skyrocket