Jump to content
  • Advertisement
Sign in to follow this  

Inacuracies in collision detection - prevent or fight them?

This topic is 4707 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. I'm writing a collision environment for my game. Right now I got spheres with different radii/masses. How do I go about collision detection? I take each sphere and try to move it a bit in its velocity direction. If some other sphere is on the way, then it's a collision. So I got to solve a little quadratic equation. If someone's interested:
float movingsphere_sphere_(const xvec & diffp0p1, const xvec & movement, const float radSum)
  // Let: t = ?? (amount of movement till collision) t betw.[0..1]
  // || (p0 + mov*t) - p1 || == r0+r1
  // || (p0 - p1) + mov*t || == r0+r1
  // Let: A = diffp0p1 = p0 - p1
  //      B = movement
  //      R2 = radSumSq
  // || A + B*t || = R
  // <A,A> + 2<A,B>t + <B,B>t^2 == R2
  const float AA = dot(diffp0p1);
  const float AB = dot(diffp0p1, movement);
  const float BB = dot(movement);

  // BB*t^2 + 2AB*t + (AA-R2) == 0
  // a = BB,  b = 2*AB,  c = (AA-R2).
  // delta = b^2 - 4ac
  const float deltaQuarter = ( AB*AB - (AA-radSum*radSum)*BB );// * 4;
  if (deltaQuarter <= 0.0f)
    return 1.0f;

  // There is a collision. Find out when.
  const float deltaSqrtHalf = sqrtf(deltaQuarter);// * 2;
  // result = (-b +- sqrt(delta)) / 2a
  // a = BB,  b = 2*AB,  c = (AA-R2).
  const float t1 = (-AB + deltaSqrtHalf) / BB ;
  const float t2 = (-AB - deltaSqrtHalf) / BB ;

  // It might be backwards in time, or too far in the future.
  if (is_in_range_01(t1))
    if (is_in_range_01(t2))
      return min(t1, t2);
      return t1;
  else if (is_in_range_01(t2))
    return t2;
    return 1.0f;

Then I move the object by the computed fraction of movement, and handle the collision, if there was one. Other than that I solve the equation for modification of velocities of the two colliding objects, but that is (I suppose) not the case here. The case is: sometimes after the movingsphere_sphere_ the computed fraction gives me the new position for the object, that is too close to the other one. Like a little fraction, resulting from rounding errors, I suppose. The two objects are patilly in eac other. And the invariants of the system are not valid anymore thus plenty of holes in the system open up. How are you handling such things? (Or are you using some other methods of checking for collisions?) I was thinking about always saving some space between the spheres, like a safety buffer. For example, if the collision was at 0.67 of the original movement, I would proces only 0.66, or even 0.669 (but still procede with collision response). Seems very defensive... What do you think?

Share this post

Link to post
Share on other sites
No complete answer, but just a couple of thoughts. First of all you're correct that the end state after such an update is more or less random: maybe the spheres are initially intersecting at the beginning of the next frame, maybe they're not. The 'move to within some small distance of the end position' approach is a somewhat common solution. For example, I believe the various Quake engines maintain such a 'buffer' between the objects and the collision planes.

Another option is to write your coldet functions to handle both the 'swept' and 'static' cases. This can be a good idea anyway, because in some contexts even the 'buffer' might not prevent all interpenetrations. For example, a sphere traveling almost parallel to a triangle may bail on the collision test yet still intersect the triangle, so at the beginning of the next frame you'd have an initial intersection to deal with.

Share this post

Link to post
Share on other sites
Try to divide your problem into two different problems:
1. Collision handling
2. Contact handling.

Collision handling is where to you try to prevent from two non-penetrating bodies to come in contact one with the other during the time step. This is exactly what you are doing already.

Contact handling is where we handle two touching or penetrating bodies by making them come apart and optionally apply friction. In your case we can do the following:

dist = p0 - p1
pen = (r0 + r1) - ||dist||
if ( pen >= 0 )
// Spheres are touching or penetrating

// We can do this
p0 += dist * (pen/||dist||)

// or this
p0 += dist * (pen/||dist||) * 0.5
p1 -= dist * (pen/||dist||) * 0.5

To summarize:

For each pair of spheres:
if (touching or penetrating)
apply contact handling
[apply friction]
apply collision handling

Share this post

Link to post
Share on other sites
Thanks for the responses!

In the meantime, I went with the following approach (for any two objects):

0. Check for collision (static or dynamic). If none, return.
1. Check for initial intersection.
1a. If there's initial intersection, and we're "coming out of it", report no collision at all and move the object normally.
2. Check if the other object is not "moving away" from us at higher velocity (than we're chasing it). If it is, ignore the collision.
1b. If there's initial intersection, and we're "coming into it" even more, don't move, but report collision.
3. Move by a proper fraction (with safety-buffer) and report collision.

The reason I got this so complicated is that I don't want to make situations of double collision, where two objects are colliding two times in two following iterations, resulting in supresssing all velocity modiffications and ending in a state equal to the initial one.

I'm not sure about "making objects come apart" part. As it is not continous process, it might result in creating unspeciffied situations, in which two objects do collide two times in a row. I suppose it would be ruled out by point 2.. But I got to rethink it over to be sure.


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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!