Hi guys, maybe I am having the solution to my problem right in front of me, but right now, I'm just to blind to see... Could you help out, please? I have two spheres moving around (developing a classical pool table game). And I have found nice ways of manually computing collision effects and spins and so on. All's good and well. Now, in the sphere-sphere collision sweep test I found, I can check if two spheres intersect right now, or if they intersect in the next frame, or anywhere in between. I'm sure, you're familar with that stuff. If not, here's the code (copied from gamedev.net, too):

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2)
{
  //Initialize the return value
  *t = 0.0f;

  // Relative velocity
  D3DVECTOR    dv    = obj2->prVelocity - obj1->prVelocity;
  // Relative position
  D3DVECTOR    dp    = obj2->prPosition - obj1->prPosition;
  //Minimal distance squared
  float r = obj1->fRadius + obj2->fRadius;
  //dP^2-r^2
  float pp = dp.x * dp.x + dp.y * dp.y + dp.z * dp.z - r*r;
  //(1)Check if the spheres are already intersecting
  if ( pp < 0 ) return true;

  //dP*dV
  float pv    = dp.x * dv.x + dp.y * dv.y + dp.z * dv.z;
  //(2)Check if the spheres are moving away from each other
  if ( pv >= 0 ) return false;

  //dV^2
  float vv = dv.x * dv.x + dv.y * dv.y + dv.z * dv.z;
  //(3)Check if the spheres can intersect within 1 frame
  if ( (pv + vv) <= 0 && (vv + 2 * pv + pp) >= 0 ) return false;

  //tmin = -dP*dV/dV*2 
  //the time when the distance between the spheres is minimal
  float tmin = -pv/vv;

  //Discriminant/(4*dV^2) = -(dp^2-r^2+dP*dV*tmin)
  return ( pp + pv * tmin > 0 );
}

Question is: If I want to tell exactly _when_ a sphere collides with another, how would I do that? What I'm saying is: The collision will happen, but it won't be in the next couple of frames -- how can I get the exact frame (time/position) of the collision? Obviously, this line: if ( (pv + vv) <= 0 && (vv + 2 * pv + pp) >= 0 ) return false; _will_ return false, since the collision will happen later. So I know that 1) pv + vv > 0 _or_ 2) vv + 2 * pv + pp < 0 But how can I get the time of intersection? See -- it's probably right in front of me, but I can't see it... Do you? Thanks!! Beren

Have you considered using Planes in this situation? I have an idea (it's perhaps a little weird) whereby you can project two planes using the properties (ie. direction, position) of both objects and test for any collisions between them. The idea goes something along these lines:

1) Project two planes using the positional and direction data from each object.

2) Check for an intersection and get its position.

This should provide you:
... a) the confirmation there will be a collision in n-frames, and
... b) the general location where this will happen.

3) Calculate the length of time it will take one of your objects to reach that location. I think in most situations you should be able to do this (and step 2) in 2D.

... dV = difference in position between object and intersection.
... vV = velocity vector (assuming it's travelling at a constant speed).
... num. of frames = [dV/vV]

Obviously in this situation you can have several assumptions (e.g. distance is within the bounds of a table). Apologies if that made little sense, wrote it very quickly - late at night.

First of all: Thanks for the reply.

I think I understand your general idea.

Can we take it to an example, please?

Say I have Sphere 1 with radius 4 at position p1(0, 0, 0) with velocity v1(2, 2, 2) and Sphere 2 with radius 3 at position p2(15, 15, 15) with velocity v2(-1, -1, -1) .<br><br>And now? I'd "project two planes" as you suggest… Err… How?<br><br>I feel a little thick right now, and I have the distinct feeling that I am missing something big here…<br><br>Thanks for any more help! Really appreciate it.<br>

Reduce circle 2 to being a stationary, non-accellerating point at (0,0).

You can do this by adding radius 2 to radius 1, subtracting position/velocity/acceleration 2 from both, and basically changing your frame of reference.

So now we have the question: given a circle with a radius, position, velocity and accelleration, when does it touch (0,0).

f:t->(x,y) := p0 + v0*t + 1/2*a0*t^2

We want to find the point where |f(t)| < |r|

This is equivalent to |f(t)|^2 < |r|^2, which also happens to be easier to calculate!

|f(t)|^2 = (x0 + xv0*t + 1/2*xa0*t^2)^2 + (y0 + yv0*t + 1/2*ya0*t^2)^2
a 4th degree polynomial in t.

It's derivative is a 3rd degree polynomial in t -- there is a closed form equation for it that finds the zeros, which correspond to the minima of |f(t)|^2.

Find each first minima on the positive real line (or near enough, given problems with numeric stability). Odds are there won't be that many. :) Evaluate |f(t)|^2 at those points -- are they < |r|^2? If so, you have a collision candidate.

Find the earliest collision candidate. The actual collision will occur between now and that time when the |r|^2 barrier is actually crossed.

Newton's method!

Or you can do even more evil algebra. Examine |f(t)|^2-|r|^2. It is a 4th degree polynomial! Find the roots of it, and you will have your points of intersection.

Sadly, as the degree of the polynomial rises, so does the annoyance of solving for roots. Luckily, there is a formula for solving 4th degree polynomials:

http://en.wikipedia.org/wiki/Quartic_equation

For this to work, you need sufficient numeric stability that your results aren't garbage.

[Edited by - NotAYakk on April 21, 2008 12:36:20 PM]

This may not be helpful, but i gotta complain about your naming of functions...

first of all the function name doesn't tell me anything about what the function does, it's a test between 2 objects... what kind of test ?

secondly why do you start with a small 'b' ? to know which return value ? (useless), and if so you are wrong... BOOL is a define of an int which will in most compilers give a warning if your are trying to treat it as a bool.

my name for it would be:
bool SphereCollision( CObject3D* obj1, CObject3D* obj2 )
or
bool ObjectOverlap( CObject3D* obj1, CObject3D* obj2 )


i hate to be picky, but i think all code should be written in such a way anyone can understand it instantly without having to open up files and read in a function what it does.



A friend of mine thought it was funny screwing with other people who read his code, so he named a function "BruceLeeMyStuff()", guess what it did? exactly, no one else did either. =)