• Advertisement

Archived

This topic is now archived and is closed to further replies.

Handle _multiple_ collision points

This topic is 5996 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''ve implented a nice physics system in my game and it works well in most cases. I''d like to rewrite the collision handler to enable multiple collision respones since in some situations (e.g. when I get between two walls with my car) a single point response doesn''t work and I''ll end up interpenetrating with some polygons. (Only the "biggest" collision is handled) Right now, I''ve already listed all collision points, but I don''t know how I apply all of them. A simple addition of all collision velocities probably won''t work. That''s why I thought about handling the "biggest" collision (the one with the biggest relative velocity to the normal) first and than handle the next lower one and so on. At this time I think I have to change and reduce the collision velocities of the "later" collision points because some will act nearly like the first and don''t have to be that "strong". Don''t know if you got my problem, it''s hard to explain Is there a formula what to with the update of relative velocities or a site about multiple collision points? Thanks! Robert

Share this post


Link to post
Share on other sites
Advertisement
Handling multiple collisions simultaneously is tricky. I''ve never tried to do it, although it does come up in some cases in games.

I can''t point you directly to any resources, but perhaps you might find something on this list of links:

http://www.codercorner.com/Links.htm

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
I have tried this once!

The way to do this (at least a soluton), is to split your movement into different smaler movements.

find the first of your hits! not first frame, but witch of the hits that would happend first! Then move this part of the movement.

Then you need to flipp the rest of the move vector, and search for its first colide!

if two colides happens at the presice same time, you need to do the same, find that its 0 time until the next colission, move 0, and flipp the movement vector! (flipp = if a ball hitts a wall, it will continue in a diferent dir)

this can create infinate loops betwean two paralel walls! This is prevented by redusing the movement vector each time, and have a treshold on the smalest move!

WRONG:
vector_move_dist = 100
dist_until_colission = 20
new_move_dist = 100 - 20 = 80
(in a 1 dim world)

RIGHT:

vector_move_dist = 100
dist_until_colission = 20
new_move_dist = (100 - 20)*0.9 = 72
if (new_move_dist < 1) dont continue moving!

hope i helped!










-Anders-Oredsson-Norway-

Share this post


Link to post
Share on other sites
I supposed the "physically consistent" way to deal with multiple collisions requires the solution to an implicit set of equations. For example, if 3 balls hit together simultaneously you can no longer in general do just momentum transfer between two objects---now you have a system of objects and the whole momentum transfer system has to be satisfied at once. There may not be a closed form solution except in special cases (Newton''s Cradle?).

Numerically, there are tricks that are played to try and avoid infinite loops or oscillations. In the fluid dynamics world there''s a condition known as the Rankine-Hugoniot condition that limits shock waves to being compressive. The idea is that expansive shock waves are not possible given the second law of thermodynamics and this condition is a way to mathematically enforce the second law of thermodynamics. In numerical methods, the idea of monotonicity, limiters, total variation dimenishing (TVD) and essentially non-oscillatory (ENO) solutions are popular at the very high end of simulation---again most often in fluid dynamics simulation. I know I''m rambling now (my background is fluids), but I suspect there are nice ways of coming up with fake conditions to avoid weird infinite unstable bounces in rigid body simulation as well. I''m not sure anyone has a perfect solution yet...

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Multiple body collisions! I''ve done so much work on this that I wish I had decided from the beginning to do things the easy way. But now that I''ve come as far as I have, I''m going to try to work it all through, and hopefully I''ll be able to help other people with the same problems...

Like GRhodes said, you can get a system of equations with multiple body collisions. Here''s how I see that working: For every colliding pair of objects you usually want the normal speed to become zero. The unknowns which the equations will solve are the size of the impulses between each colliding pair. Normally these impulses will result in one object changing velocity in the normal direction, but it could also be both changing velocity in a certain proportion (mass ratio perhaps). Anyway, if you are only changing speeds in the normal direction, these equations will be linear, and you can solve them using matrix methods - hard to implement, but not impossible.

If you want to implement friction in your collisions (as I do) this would be my method for a two-body collision:
Calculate normal and shear speeds(there may be an offset - see below).
The objects are accelerated away from each other in the normal direction, so that the normal speed will subsequently be zero.
The objects are also accelerated along each other in the shear direction, by the amount of the normal speed * the friction coefficient, in the direction opposite to the current shear speed. But if this will push the shear speed from one side of zero to the other, the shear speed becomes zero. (It is possible to alter this to have different static/kinetic friction coeffs.)

In my game, the character is accelerated constantly by gravity, and often every time through the main loop there is a collision with the ground, with normal speed equal to g (* 1 time unit). When the player is pressing one of the arrow keys, any collisions between the character and the ground will have their shear speed offset, so friction actually accelerates the character in the right directions, in the same way that we use friction to walk.

The problem for the matrix solution of multiple body collisions as above is that the frictional impulse is not directly linear with the starting normal speed in the way that the normal impulse is. Unfortunately the only way to do it is what I think they call numerical methods. So here''s how I do it:
Loop through all of this until no changes are being made any more
{
___ For all of the colliding pairs
___ {
______ If the current normal speed is still substantially positive, apply a small impulse on the pair including friction, as I described earlier. This could be proportional for high speeds [so it''s O(log v)], and constant for smaller speeds. If not, do nothing, and wait for the other pairs to right themselves.
___ }
}

For added accuracy, I have the pairs first work out how much to impulse, and them all of them impulse, so that the order doesn''t have an effect. This method will only be slow if you have lots of complicated collisions happening.

Here''s how the collisions work on the broader scale, so you can see how what I have already described fits in:
From the current velocities, all relevent pairs are checked for possible collisions. All collision notifications (returned by c-detection function) are put in a heap, sorted according to the exact time.
We go through the heap one at a time: The two bodies are moved to the correct position for that exact time and the collision (normally 2 bodies) is resolved as described above.
If an object has changed velocity as a result of this, all notifications involving that object are removed from the heap, and all relevant pairs are checked again.
A record is kept of all pairs which have been resolved. If a collision comes up involving an object from a previous collision, the speeds (and NOT the positions) of the objects involved are reset and it is treated as a multiple body collision in the same way.

There are other problems you will hit when you are implementing something like this, and I feel like I have hit them all. Rounding errors, incorrect calculations of normal angles, and plenty of others. I''m currently having trouble with concave shapes, and I''ve never looked at rotating shapes.

I hope this is helpful! If there''s anything I haven''t explained well enough tell me and I''ll go into more detail. I have C++ code which does all of this but it is probably too difficult to understand small parts of it without reading a large part of it.

Share this post


Link to post
Share on other sites

  • Advertisement