Make balls bounce

Edgar Reynaldo

Does anyone see anything wrong with the following code? There's something wrong with my normals, they don't bounce properly.

EDIT
The highlighted lines are wrong. (Because the DotProduct function was wrong)

#SelectExpand
  1bool MakeCirclesBounce(Circle* c1 , Circle* c2){  2if(!c1 ||!c2){returnfalse;}  3  4/// Normalized normal vectors, these point from one circle towards the other  5   Vec2 N1 = Vec2(c2->cx - c1->cx , c2->cy - c1->cy).Normalize();  6   Vec2 N2 = Vec2(c1->cx - c2->cx , c1->cy - c2->cy).Normalize();  7  8   Vec2 V1(c1->vx , c1->vy);  9   Vec2 V2(c2->vx , c2->vy); 10 11constdouble m1 = c1->mass; 12constdouble m2 = c2->mass; 13 14   Vec2 I1 = V1*m1; 15   Vec2 I2 = V2*m2; 16///   double Itotal = (I1 + I2).Magnitude(); 17 18/// The angle between V and N determines how much energy is transferred 19 20constdouble I1M = I1.Magnitude(); 21constdouble I2M = I2.Magnitude(); 22 23double cosA1 =0.0; 24double cosA2 =0.0; 25 26if(I1M >0.0){ 27      cosA1 = DotProduct(I1 , N1)/I1M;/// Magnitude of N is always 1, they're normalized 28} 29if(I2M >0.0){/// Object has momentum 30      cosA2 = DotProduct(I2 , N2)/I2M;/// Magnitude of N is always 1, they're normalized 31} 32 33/// Momentum of circle one in the normal direction*** 34   Vec2 I1N = N1*cosA1*I1M;
 35/// Momentum of circle two in the normal direction*** 36   Vec2 I2N = N2*cosA2*I2M;
 37 38if(cosA1 >0.0){ 39/// Circle one is moving towards circle two 40/// Give circle ones normal momentum to circle two 41      I1 = I1 - I1N;/// This momentum is lost, transferred to the other circle 42      I1N *= ELASTICITY;/// Energy is lost due to inelasticity 43if(c2->fixed){/// We hit an immovable object 44         I1N *=-1.0;/// Reflection of normal energy 45         I1 += I1N;/// rebound effect 46} 47else{ 48         I2 = I2 + I1N;/// The remaining momentum is gained by the other circle 49} 50} 51 52if(cosA2 >0.0){ 53/// Circle two is moving towards circle one 54/// Give circle twos normal momentum to circle one 55      I2 = I2 - I2N;/// This momentum is lost 56      I2N *= ELASTICITY;/// Energy lost due to inelasticity 57if(c1->fixed){/// We hit an immovable object 58         I2N *=-1.0;/// Reflection of normal energy 59         I2 += I2N;/// rebound effect 60} 61else{ 62         I1 = I1 + I2N;/// The remaining momentum is gained by the other circle 63} 64} 65///   double Itotal2 = (I1 + I2).Magnitude(); 66 67bool changed =false; 68if(!c1->fixed && m1 >0.0){ 69      V1 = I1*(1.0/m1); 70      c1->SetSpeed(V1.x , V1.y); 71      changed =true; 72} 73if(!c2->fixed && m2 >0.0){ 74      V2 = I2*(1.0/m2); 75      c2->SetSpeed(V2.x , V2.y); 76      changed =true; 77} 78return changed; 79}

I would suspect the problem to be here :

if(I1M >0.0){/// Magnitude of N is always 1, they're normalized      cosA1 = DotProduct(I1 , N1)/I1M;
}if(I2M >0.0){/// Object has momentum/// Magnitude of N is always 1, they're normalized      cosA2 = DotProduct(I2 , N2)/I2M;
}/// Momentum of circle one in the normal direction   Vec2 I1N = N1*cosA1*I1M;
/// Momentum of circle two in the normal direction   Vec2 I2N = N2*cosA2*I2M;

Mark Oates

I’m a little thrown by your instance variables starting with capitals. You should consider all class names with capitals and instances with lowercase.

Too drunk to actually think math, but you might consider breaking up parts of your function into smaller parts and testing on them individually. There’s a lot of potential points of failure here and if you can narrow it down with confidence then you can eliminate the guessing and checking.

Edgar Reynaldo

Mark Oates said:

I’m a little thrown by your instance variables starting with capitals. You should consider all class names with capitals and instances with lowercase.

Next time I'll consult a style guide. They're mathematical variables, and constants. Usually I DO use lowercase for variables, but in this case, I felt it made things clearer, not worse.

The real clincher is, does the projection of A unto B really equal ^B*|A|(A.B)?

Ah hah ha hha haahahah hhaaaaaaaa I fixed it.

First, my dot product was wrong. I was doing some bizarre hybrid of a cross product and a dot product.

Second, you don't need to multiply by the |A|.

The projection of A unto B really is as simple as ^B*(A.^B).

Here's a little demo program to play with :

Download win32 binary here (CVC.7z).

{"name":"611744","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/9\/89998192365f296251917fb8ccf783fe.png","w":802,"h":633,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/9\/89998192365f296251917fb8ccf783fe"}

There's a little problem of balls escaping the pen every once in a while, and I have to figure that out next.

If anyone wants to check out the source code, it's on GitHub here :

https://github.com/EdgarReynaldo/Interceptor

Peter Hull

So, for the benefit of others (obviously I know ) which line was incorrect in your original code?

Edgar Reynaldo

So the problem was DotProduct. It returned x1y2 + x2y1, which is nonsense. It should be x1x2 + y1*y2.

The updated code is here :

https://github.com/EdgarReynaldo/Interceptor

https://github.com/EdgarReynaldo/Interceptor/blob/master/Circle.cpp

The collision detection is super easy. Here is the code :

#SelectExpand
  1double CalculateCollision(Circle* c1 , Circle* c2) {
 if (!c1 || !c2) {return -1.0;}
 
 const double dx = c2->cx - c1->cx;
 const double dy = c2->cy - c1->cy;
 const double dvx = c2->vx - c1->vx;
 const double dvy = c2->vy - c1->vy;
 const double rsq = (c1->rad + c2->rad)*(c1->rad + c2->rad);
 
 /// Quadratic equation Ax^2 + Bx + C = 0
 const double A = (dvx*dvx + dvy*dvy);
 const double B = 2.0*(dvx*dx + dvy*dy);
 const double C = dx*dx + dy*dy - rsq;
 14
 if (A == 0.0) {
    return -1.0;/// No relative movement, collision is impossible
 }
 
 /// Overlap check here - if they are already colliding at time 0.0, let them pass undisturbed
 if (C < 0.0) {return -1.0;}
 21
 const double TWOA = 2.0*A;
 const double DISCRIM = B*B - 4.0*A*C;
 if (DISCRIM < 0.0) {return -1.0;}/// no real roots
 else if (DISCRIM == 0.0) {
    return -B/TWOA;
 }
 const double SQRTD = sqrt(DISCRIM);
 const double T1 = (-B - SQRTD)/TWOA;
 const double T2 = (-B + SQRTD)/TWOA;
 if (T1 >= 0.0) {
    return T1;
 }
 34///   else if (T2 >= 0.0) {
 35///      return T2;
 36///   }
 return -1.0;/// No collision possible in the future
 38}

And the new code for bouncing is here :

#SelectExpand
  1bool MakeCirclesBounce2(Circle* c1 , Circle* c2) {
 if (!c1 || !c2) {return false;}
 
 /// Normalized normal vectors, these point from one circle towards the other
 Vec2 N1 = Vec2(c2->cx - c1->cx , c2->cy - c1->cy).Normalize();
 Vec2 N2 = Vec2(c1->cx - c2->cx , c1->cy - c2->cy).Normalize();
 
 Vec2 V1(c1->vx , c1->vy);
 Vec2 V2(c2->vx , c2->vy);
 
 const double m1 = c1->mass;
 const double m2 = c2->mass;
 13
 Vec2 I1 = V1*m1;
 Vec2 I2 = V2*m2;
 16///   double Itotal = (I1 + I2).Magnitude();
 
 /// The angle between V and N determines how much energy is transferred
 
 const double I1M = I1.Magnitude();
 const double I2M = I2.Magnitude();
 22
 Vec2 I1N(0,0);/// Momentum of circle one in the normal direction
 Vec2 I2N(0,0);/// Momentum of circle two in the normal direction
 25
 if (I1M > 0.0) {
    I1N = ScalarProjection(I1 , N1);/// Magnitude of N is always 1, they're normalized
 }
 if (I2M > 0.0) {/// Object has momentum
    I2N = ScalarProjection(I2 , N2);/// Magnitude of N is always 1, they're normalized
 }
 32
 if (DotProduct(I1,N1) > 0.0) {
    /// Circle one is moving towards circle two
    /// Give circle ones normal momentum to circle two
    I1 = I1 - I1N;/// This momentum is lost, transferred to the other circle
    I1N *= ELASTICITY;/// Energy is lost due to inelasticity
    if (c2->fixed) {/// We hit an immovable object
       I1N *= -1.0;/// Reflection of normal energy
       I1 += I1N;/// rebound effect
    }
    else {
       I2 = I2 + I1N;/// The remaining momentum is gained by the other circle
    }
 }
 46
 if (DotProduct(I2,N2) > 0.0) {
    /// Circle two is moving towards circle one
    /// Give circle twos normal momentum to circle one
    I2 = I2 - I2N;/// This momentum is lost
    I2N *= ELASTICITY;/// Energy lost due to inelasticity
    if (c1->fixed) {/// We hit an immovable object
       I2N *= -1.0;/// Reflection of normal energy
       I2 += I2N;/// rebound effect
    }
    else {
       I1 = I1 + I2N;/// The remaining momentum is gained by the other circle
    }
 }
 60///   double Itotal2 = (I1 + I2).Magnitude();
 
 bool changed = false;
 if (!c1->fixed && m1 > 0.0) {
    V1 = I1*(1.0/m1);
    c1->SetSpeed(V1.x , V1.y);
    changed = true;
 }
 if (!c2->fixed && m2 > 0.0) {
    V2 = I2*(1.0/m2);
    c2->SetSpeed(V2.x , V2.y);
    changed = true;
 }
 return changed;
 74}

The code for ScalarProjection is here :

Vec2 ScalarProjection(Vec2 A , Vec2 B) {
   B.Normalize();
   return B*DotProduct(A,B);
}

And the code for DotProduct is here :

inline double DotProduct(const Vec2& v1 , const Vec2& v2) {
   return v1.x*v2.x + v1.y*v2.y;
}

What's really interesting though, is the collision table. Check it out :

https://github.com/EdgarReynaldo/Interceptor/blob/master/CollTable.cpp
https://github.com/EdgarReynaldo/Interceptor/blob/master/CollTable.hpp

It is a vector of pairs of circles, representing each possible combination of N circles. It is exactly (N*(N-1))/2 in size. If you're doing a 1000 circle collision resolution, it will make 499,500 pairs. But the beauty is you only have to recalculate it if the velocity of one of the circles changes. This eliminates 99% of the wasted calculations of doing a frame by frame overlap check.

EDIT
{"name":"611747","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/3\/635673b9af24f3c2c81797b18d2333ee.png","w":1027,"h":800,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/3\/635673b9af24f3c2c81797b18d2333ee"}

You'll notice that balls 13 and 14 are missing. They escaped.

{"name":"611748","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/9\/c9d7ea71f2e32e14391e295f5548be94.png","w":1027,"h":800,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/9\/c9d7ea71f2e32e14391e295f5548be94"}

The fuller it is the more often they escape.

It's really quite stable, except for the escaping bit.

Aha! I fixed it. No more escape for you my pretties.

{"name":"611749","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/a\/aab5277509ad27b99a5096f0cd412ec9.png","w":1026,"h":801,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/a\/aab5277509ad27b99a5096f0cd412ec9"}

The problem was in CollTable.cpp on line 114 :

#SelectExpand
 102std::vector<CollInfo*> CollTable::GetFirstCollisionsEarlierThanDT(double dt) {
 std::vector<CollInfo*> clist;
 const unsigned int N = ctable.size();
 double first = -1.0;
 for (unsigned int n = 0 ; n < N ; ++n) {
    CollInfo& info = ctable[n];
    if (info.dt < 0.0) {continue;}
    if (info.dt > dt) {continue;}
    if (first < 0.0) {
       first = info.dt;
    }
    if (info.dt > first) {
 114-         break;
 115+         continue;
    }
    clist.push_back(&ctable[n]);
 }
 std::sort(clist.begin() , clist.end() , CompareCInfo);
 return clist;
 121}

https://github.com/EdgarReynaldo/Interceptor/commit/2e72f6c26576b87a82db4c0acbe8d992a658a051#diff-c7e697629af47a878a6163ae0d115670L114

Thread #617610. Printed from Allegro.cc