Sign in to follow this  
jiGGaK

2D Spheer-Spheer sweep test problem

Recommended Posts

I apologize for littering this forum with yet another question on collision detection, however, I have been stuck on this problem for weeks now. If someone here could take a few minutes to read over my post, it would be appreciated. I am implementing a spheer-spheer sweep test using this article by Miguel Gomez. I have tripple checked my implementation and yet I still can't get it to work. I suspect I have missunderstood Miquel's article, but I had no problems implementing other algorithms in his article. My Ball class has two Point objects used for the balls previous position (p0) and it's current position (p1). These points are relative to the screen co-ordinates. Each ball is "advanced" at the beginning of the game loop, and then checked for collision against other objects. Each ball has a velocity vector to determine the displacment in a frame. For example a ball traveling 10 pixels in a right-hand direction would have a velocity vector of {10, 0}. A ball traveling 10 pixels in a left-hand direction would have a velocity vector of {-10, 0}. Here is my method that performs the sweep test against another ball:
public boolean collidesWith(Ball B) {
   double uA, uB;
   
   Ball A = this;
   
   Vector2D vA = A.velocity;
   Vector2D vB = B.velocity;
   
   Vector2D AB = new Vector2D(B.p0.sub(A.p0));
   
   Vector2D vAB = vB.sub(vA);
   
   double rAB = A.radius + B.radius;
   double rABsq = rAB*rAB;
   
   //check if balls are overlapping
   if (AB.dot(AB) <= rABsq) {
      return true;
   }
   
   /* Result of quadratic formula
    *   true if yields real roots
    *   false for complex roots
    * 
    * true also means the balls crossed paths durring this frame
    */
   boolean result = false;
   
   double a = vAB.dot(vAB);       //u*u coefficient
   double b = 2*vAB.dot(AB);      //u coefficient
   double c = AB.dot(AB) - rABsq; //constant term
   
   //solve quadratic equation
   double q = b*b - 4*a*c;
   if (q >= 0) {
      double sq = Math.sqrt(q);
      double d = 1/(2*a);
      uA = (-b + sq)*d;
      uB = (-b - sq)*d;

      //smaller value is when spheres began to overlap
      //larger value is when they became disjoint again

      //make uA always the lesser value
      if (uA > uB) {
         double tmp = uA;
         uA = uB;
         uB = tmp;
      }
      
      //adjust ball positions
      //TODO adjust ball positions
      
      result = true;
   }
   
   return result;
}

The method returns true often, even when the two balls being tested are far appart.

Share this post


Link to post
Share on other sites
At first glance, the function looks correct (could be missing something though). However, in what you posted at least you're not checking that the first time of intersection is in any particular range. Are you doing that elsewhere? If not, any intersection in the future (positive uA) or past (negative uA) will count as a hit. Most likely you'll want to reject intersections with uA < 0 and uA > max, where max might be 1, or some other positive value depending on what your velocity vectors represent.

If you already are checking the range, then never mind (maybe there's some other obvious error there that I missed).

Share this post


Link to post
Share on other sites
Can you explain why solving that quadratic tells you if the balls crossed? Firstly, I don't understand, and secondly explaining things often exposes where you may have made a mistake.

Another thing: are your balls moving fast enough that you need to do more than intersection checks? It is obviously much less CPU-intensive just to do the radius check if you can.

Share this post


Link to post
Share on other sites
jyk,

Thank you!!! You are absolutely right... I was not checking that uA was in range. It works fabulously now.

Bob,

To be honest I don't understand 100% the nitty gritty of Miguel's algorithm. However if you take a look at his guide he has derived a formula that is quadratic in u, where u is the normalized time at which the two spheer's crossed paths. Again my math is a bit rusty on this topic, but if you factor the quadratic and the solution yields two values that are real numbers a collision has occured. If two complex numbers are left, no collision has occured.

Yes you are right, an overlap test would be FAR less CPU intensive, but it won't work with fast moving and/or small objects. I might tinker with multisampling which given my constraints might even be less expensive than this sweep test. This will be used in a puzzle type game (remember The Incredible Machine?) that has many types of balls... most don't move quickly with the exception of a cannon ball which moves very quickly a cross the board.

Thank you both for your reply. I am pumped that my balls now bounce (tee hee).

For reference, here is my modified source:

public boolean collidesWith(Ball B) {
double uA, uB;

Ball A = this;

Vector2D vA = A.velocity;
Vector2D vB = B.velocity;

Vector2D AB = new Vector2D(B.p0.sub(A.p0));

Vector2D vAB = vB.sub(vA);

double rAB = A.radius + B.radius;
double rABsq = rAB*rAB;

//check if balls are overlapping
if (AB.dot(AB) <= rABsq) {
return true;
}

/* Result of quadratic formula
* true if yields real roots
* false for complex roots
*
* true also means the balls crossed paths durring this frame
*/

boolean result = false;

double a = vAB.dot(vAB); //u*u coefficient
double b = 2*vAB.dot(AB); //u coefficient
double c = AB.dot(AB) - rABsq; //constant term

//solve quadratic equation
double q = b*b - 4*a*c;
if (q >= 0) {
double sq = Math.sqrt(q);
double d = 1/(2*a);
uA = (-b + sq)*d;
uB = (-b - sq)*d;

//smaller value is when spheres began to overlap
//larger value is when they became disjoint again

//make uA always the lesser value
if (uA > uB) {
double tmp = uA;
uA = uB;
uB = tmp;
}

if (uA >= 0 && uA <= 1) {
result = true;

//TODO adjust ball positions based on moment in time uA
//where balls began to overlap
}
}

return result;
}


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