Hi, I have my game engine all up and running, with proper collision detection, etc. I have some questions about collision response though. In my particular engine, after a collision is detected, I get back a list of collision planes (a temporary plane is created for edges and corners as well), point of impacts and a relative value between 0 and 1 for each collision point during the timestep. For instance, I can have 1 collision point at 0.25 of the timestep, and another at 0.5 of the timestep. In the past, I simply moved the simulation forward by the smallest fraction of the timestep, and then when the object (in this case a sphere) hit the first collision plane, it simply reflected back and "bounced". The simulation then proceeded from that time position forward again, so what happens is that the simulation is automatically broken down into smaller timesteps as collisions happen. This works pretty well for 95% of the time. The problem I have is that there can be multiple hits with a timestep ratio of 0, meaning I need to change velocity right at the beginning of the timestep. This would happen for instance if the sphere was gliding along the floor and hitting an overhanging wall with less than 90-degree angle (leaning in towards the sphere). In this case, the first impact would be the wall, which would bounce the sphere down into the floor. At the next timestep, since the sphere is already touching the floor, the relative timestep value would be 0. The sphere is then reflected back up, hitting the wall again, and this results in an infinite loop, since the time can never advance again, since all relative hits are at the beginning of the timestep. I have been able to alleviate the problem somewhat by creating a single plane when multiple hits are encountered, by averaging the collision impact and normals of each of the hitplanes (tried various formulas), but it still often results in escape velocities that want to penetrate a wall. Another solution I thought might work was to make the walls "soft", so that penetrating a wall would be acceptable, and instead of simply reflecting the velocity, force is applied to the object based on time and penetration depth. Thus I need to integrate the force over time, and add them up for all walls. This should ultimately result in the object being pushed in the correct direction, and I can avoid 0 timesteps altogether, since integration needs at least some timestep to work. But I have been unsuccessful at creating a realistic "bounce". I believe the problem is because the timesteps going "into" the wall does not match the same as going "out" of the wall, resulting in mismatched velocities after a collision (integration error). I tried simple integration [time *(force-at-time-1 * force-at-time-2) / 2], as well as the velocity version of the Verlet integration method. The Verlet method had better results, actually, but still not perfect. Also, the Verlet method seems to work with a constant depth/force ratio, but I am interested in ultimately making the walls "soft" with a non-linear curve [maybe (1 / (1-d) - 1)], so that it seems as if the sphere is resting slightly inside the wall (because the sphere is soft like a beach ball, for instance), but still has enough resistance to stop a very fast moving object. I should just add that in my engine I can advance the simulation by any fraction of the current timestep, it''s not directly tied to the framerate (this smaller time-step does not apply to the rendering pipeline, only the physics part - the rendering still happens only after the full original timestep). This was done so that very fast moving objects can be handled correctly (like bullets, etc). For instance, if a collision is going to happen at 25% of the next timestep, the simulation can be advanced by that amount so that the collision now starts at the beginning of the next timestep. Also, if it''s determined that the object is going to move too far into the wall, the timestep can be broken down to the point where the object would change direction, and at the next timestep the object would be starting from a velocity of 0 wrt the wall. Might make it easier on the formulas, etc. I''m basically looking for a reliable integrator that can work with relatively large, mismatched timesteps and non-linear curves. Phew! That was a lot of typing! Anyway, what are people''s thoughts on this, and how can one solve this problem? Thanks in advance! SS

when you move to your first "collision" position are you moving
it "out" of the surface by a small fraction? this helps a lot.

also its ok to stop the iterations at some point.

we only do a maximum of 3. yeah you dont get the true final
position, but were talking super small fractions that couldnt
even span a pixel onscreen so why bother with being super precise?
unless you need to be really precise then your method of collision
response probably needs to change..

quote:

---

Original post by Anonymous Poster

when you move to your first "collision" position are you moving
it "out" of the surface by a small fraction? this helps a lot.

also its ok to stop the iterations at some point.

---

Actually, in my case I first calculate the exact time at which the collision would occur (assuming straight-line movement during the timestep), and advance the simulation up until that time. So in practice the first "collision" is just touching the surface, not "in" the surface, so it''s not necessary to first move it "out".

One test I was doing was to, instead of calculating the next position, to calculate the exact time required to get to the point where the object would go from going "in" to going "out" (change direction). This way, I was controlling the timesteps based on position/velocity, instead of controlling the position/velocity based on timestep. It seemed to give reasonable results, but the complexity of the algorithms increased. A simple linear depth/force integrating algo became an algo with a double log() calculation, etc (I use MathCad to solve the variables for me). Anyway, if this calculated time is less than the timestep, the new time is used, else the original timestep is used.

The above worked relatively well, but the exit velocity still seems to be too dependent on how the entry timesteps match the exit timesteps. I need an algorithm that is (relatively) insensitive to the size of the timesteps as it enters/exits the surface. It does not have to be super-accurate, as long as it looks accurate enough - I don''t care if the ball is able to bounce 100 times without losing height, since it''s bounce will we damped anyway. Also, it should be able to work with non-linear depth/force curves, as I said.

SS

Try the Runge-Kutta integrator. Most people start with the 4th order integrator and work in either direction (less or more accuracy) depending on their needs and the results of 4th order tests. There's a nice extension for adaptive time-stepping too.

Cheers,

Timkin

Edited by - Timkin on January 31, 2002 10:09:55 PM

I''ve read a couple of your other posts, and I get the feeling that all these integration questions are to implement this depth based force which is merely a way of sorting out your collision response. If I''ve misunderstood and you''re actually trying to implement some sort of visibly deformable walls or something then please ignore the rest of this post.

If not, this non-linear-depth-based-force-Runge-Kutta-integrating method seems like the most overcomplicated hack ever.
Surely there are much more simple ways to get the right behaviour? The collision response you want depends of course on the objects properties and how realistic you want it to be. But take your overhanging wall for instance - I think you mean like this:

\
0 \
--------

Now I assume here the response you want is the ball rolling back where it came from. I hits the wall, gets "bounced" down and to the left, then immediately hits the floor. Now say you stored the fact that it hit the wall, then when you find it hitting the floor at the same time step, get the collision plane normal there (upwards), and set the balls new velocity to the bounce velocity you already calculated (down and left), minus any component along the floors normal - ie. you remove the down component, leaving just left.
So basically you''re just detecting when you hit two things simultaneously and responding slightly differently.

Sorry if I completely missed the point.

Cameron

Cameron,

Yes, you are correct in your assumption that this is what I''m looking for. Actually, I have tried various methods, similar to what you suggest. The most successful so far is one where I find a third "sliding" plane, based on the two colliding planes. This sliding plane''s normal is calculated based on a weight given to the "intensity" of the collision with each of the different walls.

This actually works well, but the problem is where there''s more than two walls hit at a time. For instance, if I test it with the ball rolling down the inside of a large inverted cone (let''s say 32 sides), all hell breaks loose...

Actually, the "softness" of the walls was just an added benefit, and I don''t really care too much for it. Basically, I''m saying that I''d prefer the solid, instantly reflected bounce method I''m talking about above, because it''s easier to implement, compared to the penalty methods. The penalty methods have the advantage of being able to give the soft wall feel (it''s more the ball that''s supposed to flex, like a beach-ball). But I''ve found in most cases the added "realism" is not worth the additional problems of dealing with instability, etc with penalty methods. Also, in my initial tests, the solid bounce method needs only one step to do a complete bounce, where the penalty method needs many steps to complete a bounce - so it''s much slower.

The latest thing I was thinking off trying was to use my initial method of creating new sliding or bouncing planes when there are multiple hits, but temporarily switch to the penalty method when it''s detected that the ball is going into a multiple-zero step-size loop. I already have a counter that counts successive zero-steps, and before I just forced an exit from the loop, and hope things sorted themselves out later. Of course they didn''t always.

BTW, in my game, you "tilt" the whole world with the mouse. This causes the ball to roll in whatever the direction you want. The idea is to create some sort of 3D 3rd person pinball machine, although it''s not limited to this of course (I’m also going to do large outside levels). For instance, you''d be able to roll along a roller coaster "track" and be required to perform certain jumps, loops, etc. The 3rd sliding plane I mentioned above works great when the ball is on the track, which is made of two rectangular "bars" placed parallel to each other. In my collision detection code, I detect the collisions with the edges of the bars of the track, and for each one I create a temporary plane representing the collision plane. Then In my response code I create the new “sliding” plane from the two collision planes.


SS

Yes, I can imagine it could get a lot more complicated with multiple simultaneous collisions. Actually, as I was writing my last post, I realised that this problem was one that I''ve also got to deal with in my game. I have a ship (bounded by a sphere) inside a polygonal tunnel, and at the moment if it hits the seam of two polygons of the tunnel, it bounces off to one side since all I do at the moment is use one collision plane (random choice if there are multiple simultaneous collisions).

So anyway if I get anywhere with it I''ll let you know.

cheers
Cameron

My engine is similar to yours (2D however), and I''ve had the same kinds of problems. I''ll pull out what I said in another thread and edit it. The *s are my edits.

It comes down to solving multiple body collisions. With pinball (and in my game) there''s generally only one moving object in a collision, but I try to cater for special cases anyway.
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.

* I realise in pinball the collisions are usually fairly elastic (mine were usually inelastic) and that you might not bother with friction. You can leave friction out of everything here, making it simpler.

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.

* (i don''t think I had said this here) At the end of the time-step, you go through all the relevant pairs and see if there are any pairs which are overlapping illegally. It often happens that even though you correct the relative velocities have been corrected but due to the way the rounding works, there is still a slight overlap. In this case I run through the above algorithm again but instead of using impulses (changing velocity), you apply nudges (changing position slightly). You nudge in the normal direction as above, choose the proportion according to the mass ratio as above, and keep doing it until all the positions are good.

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.

* And with the amount it looks like you''ve done, there may not be much in my code which helps a lot.

And I just realised you had another post higher on the list, so hopefully this isn''t irrelevant.

AndyMan,

Actually, a lot of what you say makes sense. In fact, our engines sound a lot similar (although one 2D and one 3D).

I actually thought of a slight variation on what I did before to try out next. Instead of dealing with the penalty (spring) methods at all, I’m going to do the same thing I did before with solid hit surfaces with a simple velocity reflection (and some added math for restitution, friction etc thrown in). I’ll again create the “sliding planes”, as I described above, which worked well whenever the ball didn’t protrude into another object.

Now, I was thinking about this... Why do I sometimes end up with protruding objects if my collision code is supposed to stop objects from protruding in the first place? Well, it’s mostly due to rounding errors, etc, so the conclusion then is that if there are any objects protruding, it will be only by a very small amount (probably less depth than what my EPSILON value is set at). Previously I didn’t want to force movement in a direction that is not exactly on the current path as tested by my collision code. The path with its list of collisions would become “invalid” if I force the ball out of that path.

But, as it turns out, the amount to move the ball by to become non-protruding is small enough that the list of current collisions would still be quite accurate. So, if I detect a protruding object, I can simply move it enough that it isn’t protruding any more. Also, I can maybe enforce a minimum time step, which would be very small. This way, the collision loop can never get into the “zero-step infinite loop” mode.

Let’s say the ball drops down the inside of an inverted cone with 32 sides. Eventually the ball would want to wedge itself between the polygons, and it would at some point start protruding into the polygons. For every collision where it is protruding, I then force the ball away enough to free it from the polygon. Now this will unfortunately force it to go deeper into the opposite polygons, but I figure they will also get their chance to push the ball away, so on average the ball would sit there at the bottom, oscillating between the polygons, but not enough to visually see since the distances involved are very small. Since the average direction the ball would be pushed into over time would be straight up, things should balance out.

But I will test all of this, and see how it works.

SS


Edited by - Axter on February 7, 2002 9:43:14 PM