Sign in to follow this  
deffer

Inacuracies in collision detection - prevent or fight them?

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);
    else
      return t1;
  }
  else if (is_in_range_01(t2))
  {
    return t2;
  }
  else
  {
    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]
else
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.

Cheers.
~def

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this