gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Circle-Circle Collision and Reaction (Frame-Independent)

#118003 - sgeos - Fri Feb 09, 2007 1:28 am

I'm looking for a frame independent circle-circle collison/reaction routine. So far as I can tell, this is expensive. The basic flow goes something like this:
Code:
circle a;
circle b;
float t = timeToCollison(a, b);  // in frames

if (t < 1.0)
{
   scaledMove(a, t);   // x += dx * scale; y += dy * scale;
   scaledMove(b, t);
   react(a, b);
   scaledMove(a, 1.0 - t); // or not, if you want them to touch
   scaledMove(b, 1.0 - t);
}
else
{
   scaledMove(a, 1.0);
   scaledMove(b, 1.0);
}

timeToCollison() seems to boild down to a quadratic equation:
Code:
// terms
pA;                  // circle A
pB;                  // circle B
r  = pA.r  + pB.r;   // distance at collison
x  = pA.x  - pB.x;   // x distance
y  = pA.y  - pB.y;   // y distance
dx = pA.dx - pB.dx;  // delta x distance
dy = pA.dy - pB.dy;  // delta y distance
t;                   // time
SQ(v)   ((v) * (v))  // squared variable

// collide when distance equals sum of radii
// SQ(a) + SQ(b) == SQ(c);
SQ(t * dx + x) + SQ(t * dy + y) == SQ(r);
// expanded
SQ(t) * SQ(dx) + (t * 2 * dx * x) + SQ(x) + SQ(t) * SQ(dy) + (t * 2 * dy * y) + SQ(y) == SQ(r);
// quadratic in terms of t
SQ(t) * (SQ(dx) + SQ(dy)) + t * (2 * (dx * x + dy * y)) + (SQ(x) + SQ(y) - SQ(r)) == 0;

// quadratic terms
a = (SQ(dx) + SQ(dy));
b = (2 * (dx * x + dy * y));
c = (SQ(x) + SQ(y) - SQ(r));

// solve using quadratic equation, return smaller value
t0 = (-b + sqrt(SQ(b) - 4*a*c)) / 2a;
t1 = (-b - sqrt(SQ(b) - 4*a*c)) / 2a;

When the mass of the objects are the same, reaction seems to simplify to exchanging movement along the line of action while leaving alone any movement perpendicular to line of action.

Is there a cheaper way to do all of this?

Reference:
Pool Hall Lessons: Fast, Accurate Collision Detection between Circles or Spheres
Macromedia Flash MX 2004 Demystified

-Brendan

#118082 - Miked0801 - Fri Feb 09, 2007 11:13 pm

Could cheat a touch.

Record last tic's min distance between points.
Record this tic's min distance between points (with collision).
Linear interpolate a position between the 2 using the difference between the two points as weight. Should be very, very close to accurate.

#118093 - keldon - Sat Feb 10, 2007 2:30 am

For time to collision (well I have just calculated distance of collsion) here's something I knocked up with fewer needs for square roots. Also note the obvious constants such as A.radius*B.radius, and that depending on the size of your circles you can simply have a lookup table for y to find the distance as distance = x - lookup[y].

If this is faulty then it is currently 01:22 and I have to sleep; but I cannot see why not and the test cases work fine. This will not tell you if there is a collision without the vector, but instead tells you how far along the vector where you would find A touching B.
Code:
public class CircleCircleCollision {
   public static void main ( String argv [] ) {
      Circle A = new Circle ( 1d, 0,0, new Vector (10d, 1d));
      Circle B = new Circle ( 1d, 10d, 0d, null );
      System.out.println( collisionDistance ( A, B ) );
   }
   
   static double collisionDistance ( Circle A, Circle B ) {
      // nx,ny = B.x, B.y in A.vector's vector space
      double x = B.x - A.x;
      double y = B.y - A.y;
      
      Vector velocity = A.velocity.normalized();
      
      double nx = x * velocity.x + y * velocity.y;
      double ny = x * velocity.cross().x + y * velocity.cross().y;

      // these two cases are non collisions
      if ( nx <= 0d ) return Double.NaN;
      if ( !( ny > B.radius - A.radius | ny < B.radius - A.radius)) return Double.NaN;
         
      double distance = nx - Math.sqrt( (A.radius+B.radius)*(A.radius+B.radius) - (ny * ny));
      return distance;
   }
   
   static class Circle {
      double radius;
      double x,y;
      Vector velocity;
      
      Circle ( double _radius, double _x, double _y, Vector _velocity ) {
         radius = _radius;
         x = _x;
         y = _y;
         velocity = _velocity;
      }
   }
   
   static class Vector {
      double x,y;
      
      Vector ( double _x, double _y ) {
         x = _x;
         y = _y;
      }
      
      Vector cross (){
         return new Vector ( -y, x);
      }
      
      double length (){
         return Math.sqrt(x*x + y*y);
      }
      
      Vector normalized (){
         return new Vector ( x / length(), y / length () );
      }
      
   }
}

#118122 - sgeos - Sat Feb 10, 2007 7:42 am

By linear interpolation, do you mean something like this? As far as I can tell, this will work if the orbs don't move fast enough to cross eachother. If this routine is triggered by a doesCollide() routine, fast moving objects could move through eachother. If delta is calculated with last frame and the frame before that, perhaps this problem will disappear? (So long as the objects were not colliding last frame as well.) Is the distance between center points a linear function of time?

Code:
timeToCollision(pA, pB)
{
   last  = lastFrameDistance(pA, pB);
   this  = thisFrameDistance(pA, pB);
   delta = last - this;
   r     = pA.r + pB.r;

   // distance = last + time * delta;
   // collide at r, solve for time when distance == r
   time  = (r - last) / delta;
   return time;
}

#define SQ(v)   ((v) * (v))

lastFrameDistance(pA, pB)
{
   x = pB.x - pA.x;
   y = pB.y - pA.y;
   return sqrt( SQ(x) + SQ(y) );
}

thisFrameDistance(pA, pB)
{
   x = (pB.x + dx) - (pA.x + dx);
   y = (pB.y + dy) - (pA.y + dy);
   return sqrt( SQ(x) + SQ(y) );
}


EDIT: Distance is not always a linear function of time. In a spreadsheet, most of the cases appear to be parabolas. (I have not graphed them.) If anyone else cares to give it a shot, treating one of the orbs as a stationary object at (0, 0) will simplify the equations.

EDIT: I did graph it.
y = sqrt(x^2 + (m * x + b)^2)
y is distance
x is time
m is distance when the moving circle is directly above that stationary one
b is movement relative to the stationary circle.

The function boils down to a fancy linear absolute value function when b is 0. If b is non-zero, the function curves. This is where accuracy problems will happen. I'm not sure how much of a problem this will actually be. Bigger objects have a higher potential for accuracy problems if the routine is triggered by doesCollide(). I guess this can always be tested on paper given max object sizes.

Another problem is that the function changes direction after it reaches the closest point. Ie crossover. Delta is calculated using lastDist minus currDist, so crossover will give strange results. (In the worst case scenario, delta will be close to zero.)

-Brendan

#118132 - keldon - Sat Feb 10, 2007 10:32 am

Edit: Updated link to pastebin (26 April 2014)

My method works, try this CircleCircleCollision.java. Left mouse draws circle 1, right mouse draws circle 2, ctrl+left mouse draws velocity. This example not only draws where the circle would be when it collides, but using the velocity you give it tells you if it collides using only the code given above. Code is included in the jar file.

Code:
      // nx,ny = B.x, B.y in A.vector's vector space
      double x = B.x - A.x;
      double y = B.y - A.y;
     
      Vector velocity = A.velocity.normalized();
     
      double nx = x * velocity.x + y * velocity.y;
      double ny = x * velocity.cross().x + y * velocity.cross().y;

      // these two cases are non collisions
      if ( nx <= 0d ) return Double.NaN;
      if ( !( ny > B.radius - A.radius | ny < B.radius - A.radius)) return Double.NaN;
         
      double distance = nx - Math.sqrt( (A.radius+B.radius)*(A.radius+B.radius) - (ny * ny));
      return distance;


Last edited by keldon on Sat Apr 26, 2014 9:29 pm; edited 1 time in total

#118133 - sgeos - Sat Feb 10, 2007 10:45 am

Code:
if ( nx <= 0d ) return Double.NaN;

nx is the component of the distance that lies along A's movement vector?
In that case, if (nx <= 0), A is moving away from B. Correct?

Code:
if ( !( ny > B.radius - A.radius | ny < B.radius - A.radius)) return Double.NaN;

Why are you taking the difference of radii? The sum of radii is important, not the difference.
Two circles with radii of 5 and 5 would collide at the same time if instead they had radii of 0 and 10.
If this is the component of the distance that is perpendicular to A's movement vector, shouldn't
this be, if (ABS(A.radius + B.radius) < ny), then they are too far to collide?

EDIT: This:
Code:
if ( !( ny > B.radius - A.radius | ny < B.radius - A.radius)) return Double.NaN;


Is the same as this:
Code:
if (ny == B.radius - A.radius) return Double.NaN;


I don't understand it. What happens when ny == the difference of the radii?

-Brendan

#118145 - keldon - Sat Feb 10, 2007 12:59 pm

Update: Now contains pastebin link

sgeos wrote:
In that case, if (nx <= 0), A is moving away from B. Correct?

Yes. And in that case there is no collision

sgeos wrote:
Code:
if ( !( ny > B.radius - A.radius | ny < B.radius - A.radius)) return Double.NaN;

Why are you taking the difference of radii? The sum of radii is important, not the difference.
Two circles with radii of 5 and 5 would collide at the same time if instead they had radii of 0 and 10.

My mistake, that statement is void; it should have been if ( ABS(ny) > (A.radius + B.radius )) return Double.NaN

It only worked because it then goes on to calculate the distance, which is NaN - oh wait, just noticed you already gave the corrected statement. And yes if that statement is true then they are too far to collide. And like I said before if the range is small you could make use of a lookup table instead of using a square root.

By the way did you try the java file? Has a working gui that allows you to draw your own circle and vector; left mouse + ctrl to make the vector. I also updated it to be more fluid!

Last edited by keldon on Sat Apr 26, 2014 9:30 pm; edited 1 time in total

#118150 - sgeos - Sat Feb 10, 2007 2:14 pm

keldon wrote:
And like I said before if the range is small you could make use of a lookup table instead of using a square root.

I'm not quite sure I follow this. The square root term is:
Code:
sqrt( (A.radius+B.radius)*(A.radius+B.radius) - (ny * ny))

Wouldn't you need a 2D lookup table?
Code:
return nx - lut[ny][r_sum];


Quote:
By the way did you try the jar file?

The jar works well. I have not looked at the source though. I'd be curious to know how innaccurate a fixed point (GBA) implementation would be.

This solution is quite clever. I like it more than the (horrible) quadratic equation solution. Something similar to the distance projection needs to be done during the collision reaction (as opposed to collision detection), so that routine can be reused.

The normalized movement vector... can't easily be queued, because in a real game/demo that value will actually be movement relative to A (or B; it doesn't really matter). You would need a 2D queue.

This test:
Code:
if ( nx <= 0d ) return Double.NaN;

May actually want to come right after nx = ...

-Brendan

#118168 - keldon - Sat Feb 10, 2007 5:01 pm

sgeos wrote:
keldon wrote:
And like I said before if the range is small you could make use of a lookup table instead of using a square root.

I'm not quite sure I follow this. The square root term is:
Code:
sqrt( (A.radius+B.radius)*(A.radius+B.radius) - (ny * ny))

Wouldn't you need a 2D lookup table?
Code:
return nx - lut[ny][r_sum];



Yes and no. If you have many variable sizes then you will need to; but if you know there will only be a few distinct r_sum's then you need only worry about them. All depends on what your case with it is though.

Quote:
May actually want to come right after nx = ...

Good point.

Quote:
The jar works well. I have not looked at the source though. I'd be curious to know how inaccurate a fixed point (GBA) implementation would be.

Inside the jar there is a fixed point circle/line collision that is about as expensive as this and isn't that inaccurate. When I get home I'll see if I can change it.

#118188 - keldon - Sat Feb 10, 2007 10:52 pm

Download IntegerCircleCircleCollision.java

It's ok but maybe needs to sacrifice some more points, it is currently using 16:16 for the vector space transformation.

Edit: Updated to pastebin link (26 April 2014)

Last edited by keldon on Sat Apr 26, 2014 9:26 pm; edited 1 time in total

#118310 - sgeos - Mon Feb 12, 2007 12:52 am

keldon wrote:
Download IntegerCircleCircleCollision.jar

I noticed some round off error. Not necessarily a problem so long as objects bounce properly and don't get stuck together. Currently this is happening with my (unrelated) code. I'm using a force apart routine to compensate, but I'm not sure that is the best approach.

keldon wrote:
It's ok but maybe needs to sacrifice some more points, it is currently using 16:16 for the vector space transformation.

I'm using an 8 bit fractional component, like the GBA rotation/scaling hardware. It would be interesting if your demo could change the fractional component at runtime. (+ add a bit, - subtract a bit, * double bits, / half bits).

-Brendan

#120722 - sirpoonga - Mon Mar 05, 2007 8:13 pm

Interesting thread. Keldon, I haven't looked at the jar yet. Is there info on colliding a circle with a corner and/or rolling off the edge of an incline? I am making an labyrinth game for the DS Motion and the physics is the only part I am stuck on right now.

#120756 - keldon - Mon Mar 05, 2007 11:15 pm

There is little to worry about for an incline. Your balls will already have a velocity before reaching the incline, so all that happens is that there is no longer the upwards force from the ledge/ground/surface that it is on top of.

There is a great document on the soda race physics by Dr Jeckyl which is unfortunately only available from the web archive (so everyone download it now). I of course have kept a copy but read through that (from page 45), and you will probably have a few questions like how this relates to circle/corner collisions if you don't figure it out. I did find many physics documents/articles/web pages last year, but unfortunately I no longer have them or know how or where to find them.