Math Is Fun Forum

mikau

Member

Registered: 2005-08-22

Posts: 1,504

handling collisions in 2d

Gah... i'm confounded.

So here's the problem. I'm trying to apply some basic physics to the collisions in a 2d game but mild inaccuracies in collision detection are causing trouble.

Say you drop a box onto an inclined plane, the box moves (say) 4 units per frame until it penetrates into the plane.  Determine the exact point at which it collides and move the box there. Now determine what edges or corners of the box collided with the ground and modify the velocity, force vectors, rotation, etc.

sounds good even though those alone are no simple task.

But I have found that, for instance, if I have a plane for an object to land on, suppose a box lands on it in such a way that it should slide along the surface. Sliding has proved to be extremely horrible for the following reason. An object is walking the very edge of the collision boundaries, if in any calculation of its motion you are off by the slightest decimal value, (and in computer programs, they often are) the object can cross the boundary and it counts as a collision. Also, slight inaccuracies in the variables can cause it to slide slightly above the surface and float into the air. If there is gravity, it keeps it on the ground but then it looks jumpy and jerky as it lightly bounces across the surface.

One solution i considered was to have the collision boundaries slightly inside the visible surface of the objects. That way if the object is sliding nooooot quite parallel to the surface it won't really hurt. BUT if the surface is long enough, the error will accumulate as it slides along.

How on earth do I they handle this?

Last edited by mikau (2007-11-16 11:09:06)

---

A logarithm is just a misspelled algorithm.

luca-deltodesco

Member

Registered: 2006-05-05

Posts: 1,470

Re: handling collisions in 2d

theres generally two ways that physics engines are built:

one is that time is progressed in a binary search style to each exact time of collisions and impulses are applied.
the problem with this is such as you have described, but mainly what happens when impulses become very small, and numerical innacuracies means the object is constantly colliding and slowing down simulation eventually making it stuck? You get to a point of consistent contacts which have to be treat seperately and for realism involves solving a large number of equations simultaneously, dynamically. I havn't had much experiance in this method for that main reason, it seems too messy.

The other way, the way i tend to use is a penetration method. you time-step your objects however you may be doing it, and you go through each collision and find the minimal distance (along a penetration axis -> in 2D the unique normals of the shapes (for polygons) ) and move the objects apart by this value (dependant on masses for the distribution) and then idealized impulses (i.e. step change impulse)'s are applied with various models of friction, the disadvantage is that for fast moving objects it is not PERFECT, and also that with stacked objects, you require multiple collision passes (ive only ever needed between 2 and 10) for no penetrations to persist.

the problem you seem to be describing is a result of the first method as hinted by your second paragraph.

if your consistent in using this method, myphysicslab has an article on handling resting contacts which is a little above me at the moment, but you may be able to work through it: http://www.myphysicslab.com/contact.html

---

The Beginning Of All Things To End.
The End Of All Things To Come.

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: handling collisions in 2d

thanks for the quick response, luca. I feel a little clever for coming up with the binary search method already. (horray for me!) but the second method you describe, I'm a little fuzzy on that explanation.

Are you talking about the separating axis theorem? I just had an article that talked about dividing the collision into a set of 2d boundary values, and seeing where they overlap, (if at all) and determine a vector by which the two objects can be moved to the original contact point. Again though, i'm not quite sure what happens when you want to simulate a smooth surface, when the collision detection doesn't really work...smoothly!

---

A logarithm is just a misspelled algorithm.

luca-deltodesco

Member

Registered: 2006-05-05

Posts: 1,470

Re: handling collisions in 2d

yes, you use seperating axis theorem for the penetration method.

the most ive ever experimented with no polygonal objects is with circles wherein you can probably imagine what axi you would use, but otherwise you really kind of have to use a good approximation , i mean even proper commercial games will use approximations for smooth surfaces.

---

The Beginning Of All Things To End.
The End Of All Things To Come.