Archived

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

Time-based Collision Problems

This topic is 5139 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

Hi guys, I am using the classical time-based collision detection/response method like so: For every frame calculate each moving object''s next position, if a collision occured determine the first one that took place which will be a fraction of the total time of the frame, then move all the objects that fraction of the time frame. Now imagine a game similar to pool, let''s say a ball is moving very fast and is going through a narrow channel colliding with the walls as it travels; since it''s going fast a collision occurs at say 0.1 of every frame; since the frames are cut short the other moving objects become very slow and jerky while the fast ball is going through the channel. I was thinking of making the objects independant of one another but that opens up a can of worms. Any ideas ? Thanks.

Share this post


Link to post
Share on other sites
slow and jerky? It should no make a difference. What you also have to do, is to carry on detecting collision s within the remaining of the time frame, after the first collson occured. Don''t just cut short.



float time_remaining = dt;

while (time_remaining > 0.000001f)
{
float time_of_collision;

if (FindCollision(time_of_collision))
{
MoveAllObjects(time_of_collision);
ProcessCollision();
time_remaining -= time_of_collision;
}
else
{
MoveAllObjects(time_remaining);
time_remaining = 0.0f;
}
}



you cannot make the objects move independently. Well, you can, but you''d be mad. What you can do, is cluster the objects together, so they form groups of potentially colliding objects, and then you can treat these groups independently. However, this is a tricky task. To put it simply, surround your objects with a large fixed sphere at each frame (the sphere radius should be the size of the maximum displacement an object can have in one frame, or something similar), and identify the groups of spheres that intersect. As a rule of thumb, You cannot have a reference of an object in two different groups. If this occurs, merge the groups together.

then you treat those groups separately, and run the collision loop for each of them. MoveAllObjects(), FindCollision() will only apply on each cluster of objects.

Share this post


Link to post
Share on other sites
BTW, you have to be careful not to run into an infinite loop, which can be easily achieved with objects with high friction or resting on a plane (like pool balls). You need to look after contacts (when impact velocity is near 0.0f), and treat them as a special case (they are not collisions, but contacts).

Contact velocity is the velocity of the object minus the component along the collision plane normal (the impact velocity).

Vimpact = Coll.Normal * (Coll.Normal.Dot(Vel));
Vcontact = Vel - Vimpact;

if you look after the contacts, and balance the thresholds correctly (velocity, time and distance thresholds), you will avoid infinite or long collision loops. Also, you might have to check for objects overlaps, like when the collision time is 0.0f and the objects overlap each other. You''ll have to push the objects away from each other. You can also limit the numbers of iterations in a collision loop to say, 20.

Share this post


Link to post
Share on other sites
I don''t see how you could really fix that...

when you "rewind" time, do you add the fraction of time lost on to the next frame or not?

So when you cut one frame short... you should add the time you''ve cut off onto the next frame to catch up...

that would stop the other balls from moving slow, i don''t think it would help the jerkyness though :/

Share this post


Link to post
Share on other sites
Hi guys, thanks for the help.

If I don''t cut the frame short and render the objects at the positions of the first collision time things won''t look right.

For example:

Let''s say a ball is moving 10 units per frame and it is 5 units away from a wall so it hits the wall at 0.5 of the frame, if I continue moving the objects the full frame the ball will appear not to have moved like so:

start frame:
|-----O
0.5 of frame:
|O
end of frame:
|-----O

So don''t I have to cut the frame short so I can render the ball at it''s position right next to the wall ?

Also, I was not adding the remainder of the time in the frame to the next frame because I was afraid that if I had many successive frames in which a collision took place the time accumulation would get pretty big and then bam, a ball will disappear and reappear somewhere else because it moved so far.

In theory the method I use would work fine if I was able to have, say, a million frames per second but of course I can''t so I don''t know what to do now.

Share this post


Link to post
Share on other sites
you can always move all objects to the time of collision, and render at the same time, although the frame rate is gonna drop. This is why the collision loops are usually de-coupled with the render loop, so the render loop can run at a fairly steady rate.

It does not matter if the sphere that bounces on the wall does not appear to be moving if moving too fast. In fact, it will be moving too fast so won''t notice it. Unless you want to do motion blur, I guess you could render the time the sphere collided with the wall, as well as moving all objects to that time, into an accumulation buffer, but that''s really pushing it.


Share this post


Link to post
Share on other sites
quote:
Original post by Endemoniada
Hi guys, thanks for the help.

If I don''t cut the frame short and render the objects at the positions of the first collision time things won''t look right.

For example:

Let''s say a ball is moving 10 units per frame and it is 5 units away from a wall so it hits the wall at 0.5 of the frame, if I continue moving the objects the full frame the ball will appear not to have moved like so:

start frame:
|-----O
0.5 of frame:
|O
end of frame:
|-----O

So don''t I have to cut the frame short so I can render the ball at it''s position right next to the wall ?

Also, I was not adding the remainder of the time in the frame to the next frame because I was afraid that if I had many successive frames in which a collision took place the time accumulation would get pretty big and then bam, a ball will disappear and reappear somewhere else because it moved so far.

In theory the method I use would work fine if I was able to have, say, a million frames per second but of course I can''t so I don''t know what to do now.



as oliii said, it doesn''t matter if the ball doesn''t appear to move... nothing you can do about that, you are limited by the power of the PC... its better to have a steady frame rate than one that halts each time a ball hits the wall...

As for when u get a lot of collisions, yeh the time will accumulate. but only if you have more than 1 collision per frame. You could maybe set a cap on it, don''t let the time to go past something like 0.1 seconds or something (corresponds to 5 frames per second)... If your getting less than 5 frames per second, you need to think about speeding things up

Share this post


Link to post
Share on other sites
that's what games do usually, for accurate collision detection (quake and co., unreal, half life, probably all decent platformers under the sun...). Swept volumes, collision loop-recursion, sliding velocity... And in those games, the collision detection / physics overhead is tiny (should be 5-12% of the cpu load). There are ways to make it fast and accurate, if you choose your thresholds wisely, and use other cunning plans.

anyway, have a look at this demo, and especially the docs
Generic Collision Detection for Games Using Ellipsoids




- Oli.




Home

rigid body demo

Simple Z-fail Stencil shadows demo

Sphere/cube/Triangle Collision And Physics demo







[edited by - oliii on November 14, 2003 6:03:47 PM]

[edited by - oliii on November 14, 2003 6:04:46 PM]

Share this post


Link to post
Share on other sites
Hi guys,

Wow oliii, I found that same article this past summer and that''s how I learned how to determine if my objects collide; I was using similar calculations but they never seemed to work perfectly; that article really cleared things up for me.

Now, instead of cutting the frame short like I was I will use a collision loop like you wrote above.

I''m using a throttled game loop like so (pseudo code):

while(true){
cur_time=GetCurTime();
if(cur_time-last_time >= frame_rate){
elapsed_time=cur_time-last_time; // time since last update
last_time=cur_time; // save for next frame

CollisionLoop(elapsed_time); // like yours above
Render();
}
}

Does that look right ? I can''t think of any other way to do it. Thanks for all the help.

Share this post


Link to post
Share on other sites
Create a function of "distance b/w two balls and parameter time" use MaximaMinima to calculate the time when two balls will have a minumum distance.

It is more easy to implement if the balls are not accelerating ie pool balls.

I am talking about Calculus

[edited by - DirectxXx on November 18, 2003 10:01:23 AM]

Share this post


Link to post
Share on other sites