Jump to content
  • Advertisement
Sign in to follow this  
joekarl

Sequential vs Simultaneous collision detection

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

Just wanting to get some clarification on some collision detection thoughts. This is all 2D to keep things simple and no rotations.

 

In a dynamic impulse based resolution system (ie multiple bodies moving around, when they collide we apply forces to them for the next frame) it seems that there's only a couple of ways that I can go about detecting where/when collisions are going to happen. Say I have a list of bodies, I can either attempt to move them one at a time to their next collision point (ie sequential movement) or I can attempt to find the soonest collision point of all of the bodies, move all of the bodies to that point, and then repeat until the timestep is finished (ie simulataneous movement). 

 

In the first case, ordering of the objects matters as collisions may or may not occur based on which bodies is moved first.

In the second case, this involves multiple iterations over the bodies to do all of the movement and seems more complex but seems much more accurate. 

 

I've seen it mentioned (or at least it seems) that many games use the first case as it's easier to implement, faster, and the ordering effects aren't noticeable. While this seems like it would be just fine I just can't get over the fact that it's not deterministic if the order of objects changes :/

 

It could also be that I'm completely misunderstanding this...

 

Thoughts or resources related to this subject would be greatly appreciated.

Edited by joekarl

Share this post


Link to post
Share on other sites
Advertisement

You would first integrate external and constraint forces. This will yield tentative new positions. Now you have a start and end position for each body. Next you would find the time of impact between each pair and solve those in order (earliest first). Bodies that all collide at the same time time would need be solved simultaneously. Also once you resolved one pair or group this can potentially create new collision events which need to be considered as well while progressing in time.

Share this post


Link to post
Share on other sites

Bodies that all collide at the same time time would need be solved simultaneously. 

 

The "catch" with doing this is that the standard Newtonian law of restitution (separationSpeed = e * approachSpeed) is only valid for pairs of particles. If you use it on more than two bodies at a time then in general you get incorrect results (consider a Newton's Cradle). There may be a collision law that's appropriate for multiple simultaneous collisions (I vaguely recollect reading such a paper many years ago), but in practice processing pairs in sequence (and iterating) will work fine for pretty much any "game" requirement.

Share this post


Link to post
Share on other sites


Also once you resolved one pair or group this can potentially create new collision events which need to be considered as well while progressing in time.

 

So I go through, calculate all of the potential collisions, find the first one, resolve it. Because it can create new collisions after the resolution I should re-calculate all collisions from that point forward, go resolve the first one, and then repeat this process for the rest of the step ya?

Share this post


Link to post
Share on other sites

So I go through, calculate all of the potential collisions, find the first one, resolve it. Because it can create new collisions after the resolution I should re-calculate all collisions from that point forward, go resolve the first one, and then repeat this process for the rest of the step ya?

 

You could do that. However, collision detection is/can be costly, so an alternative is to separate out collision detection and collision resolution stages. Do the collision detection first and make a list of potentially colliding objects (i.e. even if the objects are separated up to some threshold, or currently moving apart, still include them in the list). Then for collision resolution stage, iterate through that list multiple times (either a fixed number, or until everything is resolved), resolving each collision if it's active (i.e. the separating velocity is negative) using the pairwise Newton law of restitution. During this process you'll just be updating velocities, not positions, and that means the iteration can be very fast - since the relationship between impulse and velocity change depends only on positions it can be cached once during/immediately after the collision detection stage.

 

If you want to sort that list by time-to-collision you can, but I don't think it will be noticeable the vast majority of the time (though it might be in artificial test cases!). If you're worried about determinism, them it might be simpler to enforce that through some means other than time-to-impact (for example, sort contacts by (x,y,z) position etc.), since time-to-impact may be expensive to calculate (and not needed for anything else), and of course you'd have to keep recalculating the times to impact as you update the velocities (if you wanted to be accurate).

 

There are lots of ways to do this, though - it's not too difficult to just try a few and see what works best for your particular application.

Edited by MrRowl

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!