Calculating event time using gsl_poly_solve_quadratic

[gogreengo]

Hi all,

First off, I apologise if this is the incorrect section for this post and for my lack of maths skills and my ignorance.

I've have been struggling with this issue for a few weeks now without success so I'm turning to you experts for any assistance/guidance you can provide.

I am creating a pool (8 ball/billiards) simulation mostly based on the theory presented in this paper: An event-based pool physics simulator

And as a starting base, I'm extending this implementation: http://www.stanford.edu/group/billiards/FastFiz/main.html

This is working really well except neither the paper nor the FastFiz implementation support or model the jaws of the pockets. Instead a ball is considered 'pocketed' when it enters the opening of the pocket boundary.

I am attempting to include the jaws as shown here:

(I need all the jaws, the image is just to show what I mean by 'jaws')

The event simulation uses gsl_poly_solve_quadratic from the GNU Scientific Library to calculate the time a collision with a rail or pocket will occur given the current state of a ball.

Due to my poor maths skills I can only express the situation in code rather than equations, I hope that is acceptable here.

For example the resulting code for a south rail collision is:

  //South rail: y=0
  numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * u_hat.y, v.y, r.y - ball.getRadius(), &root1, &root2);
  eventTime = calcEventTime(numRoots, root1, root2, curTime);
  if (Utils::fgreater(eventTime, curTime))  //absolute(eventTime) > curTime + EPSILON)
  {
    t = eventTime - curTime;
    collision_x = r.x +(v.x * t - 0.5 * mu * Table::g * u_hat.x * t * t);

    if (collision_x < t_width -cp_width_real && collision_x > cp_width_real)
    {
      futureEvents.push_back(new RailCollisionEvent(eventTime, ball.getID(), Table::S_RAIL));
    }
  }

Where mu is the coefficient of friction, Table::g is gravity, u_hat is the velocity vector normal (when rolling) or "(v + (Vector(0, 0, 1).cross(ball.getSpin()) * ball.getRadius())).norm()" when sliding. v is the velocity vector and r is the current ball position.

And for the south west pocket would be:

  //SW pocket
  numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x + v.y, r.x + r.y - cp_width - ball.getRadius(), &root1, &root2);
  eventTime = calcEventTime(numRoots, root1, root2, curTime);
  if (eventTime >= 0) {
    futureEvents.push_back(new PocketedEvent(eventTime, ball.getID(), Table::SW));
  }

Now it's trivial to move the pocket backwards deeper into the real pocket by removing the "- cp_width" from the quadratic, this works just fine, but I'm having enormous difficulty doing the same for the jaws in the pocket. I can get it to function but the collision events are not occurring anywhere near where the jaws should be.

For example, I've added two jaws to the south west pocket like so:

//SW pocket - N jaw
  numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x + v.y, r.x - r.y + cp_width - ball.getRadius(), &root1, &root2);
  eventTime = calcEventTime(numRoots, root1, root2, curTime);
  if(eventTime >= 0)
  {
    t = eventTime - curTime;
    collision_x = r.x +(v.x * t - 0.5 * mu * Table::g * u_hat.x * t * t);
    if (collision_x < 0)
    {
      collision_y = r.y + v.y * t - 0.5 * mu * Table::g * u_hat.y * t * t;
      futureEvents.push_back(new RailCollisionEvent(eventTime, ball.getID(), Table::SWpNj));
    }
  }

  //SW pocket - E jaw
  numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x + v.y, -r.x - r.y + cp_width - ball.getRadius(), &root1, &root2);
  eventTime = calcEventTime(numRoots, root1, root2, curTime);
  if(eventTime >= 0)
  {
    t = eventTime - curTime;
    collision_x = r.x +(v.x * t - 0.5 * mu * Table::g * u_hat.x * t * t);
    collision_y = r.y + v.y * t - 0.5 * mu * Table::g * u_hat.y * t * t;

    if (collision_x < cp_width && collision_y <= 0)
    {
      futureEvents.push_back(new RailCollisionEvent(eventTime, ball.getID(), Table::SWpEj));
    }
  }

But this just doesn't work, the jaw rail collisions occur well behind the pockets and on the wrong angle.

Does anyone have any idea where I'm going wrong? Does what I'm doing even make sense?

I hope I haven't missed any relevant information here.

Again I apologise for my ignorance here.

Any assistance or guidance will be greatly appreciated.

Regards,
Lark.

 

[gogreengo]

Additional information

I suppose I should also explain how I see my changes working and perhaps someone might see where I've gone wrong.

Note that the diagrams are basically hand drawn illustrations and are not supposed to be to scale or accurate in any way.

Looking at the east jaw:

and given the equation:

 numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x + v.y, -r.x - r.y + cp_width - ball.getRadius(), &root1, &root2);

I'm assuming the only changes I need to make are to the third parameter which I believe is describing the line we want to hit, such that (ignoring the ball radius):
-x - y + cp_width = 0

when x = 0:
-y + cp_width = 0
-y = cp_width
y = -cp_width

when y = 0:
-x + cp_width = 0
-x = -cp_width
x = cp_width

Seems to match the diagram..

Similarly the north jaw:

and given the equation:

numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x + v.y, r.x - r.y + cp_width - ball.getRadius(), &root1, &root2);

x -y +cp_width = 0

when x=0
-y +cp_width = 0
-y = -cp_width
y = cp_width

when y=0
x + cp_width =0
x = -cp_width

This does not work as expected though.

It seems the maths is correct given my diagrams so I'm left suspecting that I need to make changes to one of (or both of) the first two parameters. But I really don't understand what they represent in terms of this equation and I'm totally lost at what I might do to get this to work.

Any ideas or hints?

 

[mfb]

Let's see:
y is horizontal, x is vertical
west is left
south is the upper border (??)

To simplify the analysis, I would set mu=0. This eliminates all friction-related issues. Anyway, here is how I understand numRoots:

A collision with a horizontal line has
numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * u_hat.y, v.y, r.y - ball.getRadius(), &root1, &root2);

u_hat.y is the normalized component perpendicular to and away from the border (how is that different from just a vector (0, 1)?. Therefore, for your eastern yaw, I would expect 1/sqrt(2)*(u_hat.y-u_hat.x).

v.y is the same for the actual velocity. 1/sqrt(2)*(v.y-v.x)

r.y is the same for the distance. 1/sqrt(2)*((r.x-0)-(r.y+pocket_width)) where 0 and pocket_width are the coordinates of a point on the line and the "-" between the two components comes from the orientation of the edge.I don't understand how collision_x is used and where the actual collision takes place.

 

[gogreengo]

Hey mfb,

Huge thanks for your time!

Let's see:
y is horizontal, x is vertical
west is left
south is the upper border (??)

That was slack of me, I was just reusing some art work and the axis are rotated. I've amended the illustrations in my previous post to show the rails and axis.

To simplify the analysis, I would set mu=0. This eliminates all friction-related issues. Anyway, here is how I understand numRoots:

A collision with a horizontal line has
numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * u_hat.y, v.y, r.y - ball.getRadius(), &root1, &root2);

u_hat.y is the normalized component perpendicular to and away from the border (how is that different from just a vector (0, 1)?. Therefore, for your eastern yaw, I would expect 1/sqrt(2)*(u_hat.y-u_hat.x).

I couldn't say how they're different (my maths is embarrassingly poor)..

v.y is the same for the actual velocity. 1/sqrt(2)*(v.y-v.x)

r.y is the same for the distance. 1/sqrt(2)*((r.x-0)-(r.y+pocket_width)) where 0 and pocket_width are the coordinates of a point on the line and the "-" between the two components comes from the orientation of the edge.

Ok, I won't pretend to understand exactly why and what these changes do but I think I get the general gist and I will try to implement what you suggest, though due to my poor illustrations I think you have the rails and axis swapped so I expect I'll need to swap things around a bit.

I don't understand how collision_x is used and where the actual collision takes place.

This is my understanding.

If gsl_poly_solve_quadratic() returns at least one real positive root then it predicts the time of a collision (which may later get culled if a different event occurs first, but that's not overly relevant to the problem here, but does help to explain what collision_x and collision_y are used for). But this does not express where the collision occurs.

Then the event time is used to calculate where on the X axis the collision will occur. I'm using the collision_x to ensure that the collision took place with in the expected range and to avoid adding collision events that don't make sense. (does that make sense?)

The calculate event time magic looks like so (it adds in the curTime)

//Returns the smaller non-negative root plus curTime. If there are no non-negative
//roots, returns -1.
double Shot::calcEventTime(int numRoots, double root1, double root2, double curTime)
{
  switch (numRoots)
  {
  case 0:
    return -1;
  case 1:
    return (root1 >= 0 ? root1 + curTime : -1);
  case 2:
    if (root1 >= 0)
    {
      if (root2 >= 0)
        return (root1 < root2 ? root1 + curTime : root2 + curTime);
      else
        return root1 + curTime;
    }
    else
    {
      if (root2 >= 0)
        return root2 + curTime;
      else
        return -1;
    }
  default:
    LOG("Error: wrong input " << numRoots << " to Shot::calcEventTime");
    return -2;
  }
}

Does that explain things better? Should I provide more information?

Again, thanks for your time, much appreciated.

Edit: I can provide the entire routine that does this work if that helps, but I don't want to just dump a heap of code and expect others to trawl through it :)

Cheers,
Lark

 

[gogreengo]

I haven't had any success with this still. I expect I have not understood what you suggested..

For the SW pocket E jaw I had:

numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x + v.y, -r.x - r.y + cp_width - ball.getRadius(), &root1, &root2);

And after your suggestion I have:

numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (1/sqrt(2.0)*(u_hat.y+u_hat.x)), 1/sqrt(2.0)*(v.y+v.x), 1/sqrt(2.0)*(-r.x - r.y + cp_width - ball.getRadius()), &root1, &root2);

and for the SW pocket N jaw I had:

numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x + v.y, r.x - r.y + cp_width - ball.getRadius(), &root1, &root2);

And now:

numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (1/sqrt(2.0)*(u_hat.y-u_hat.x)), 1/sqrt(2.0)*(v.y-v.x),  1/sqrt(2.0)*(r.x - r.y + cp_width - ball.getRadius()), &root1, &root2);

But it still doesn't work correctly...

Anyone have any ideas?

 

[mfb]

But it still doesn't work correctly...

What is going wrong?
Did you try my suggestion to set mu=0?

 

[gogreengo]

What is going wrong?

I rarely just say "it doesn't work" but in this case it's hard to describe what is happening.

To find those two jaws I need to remove the pockets and move the ball off the table (through the SW pocket) once there I can get a collision to be detected as certain points beyond the pocket (not where the jaws should be though). BUT they move as the ball position moves so they are not in a static position and as such I can't describe where they are well.

In fact the behaviour is not much different than before - it's odd that the collisions seem to occur so far from where we'd expect... They are usually found moving around 2/3 of the table width away from the SW pocket corner.

Did you try my suggestion to set mu=0?

Yep tried with and without, though I'm pretty sure this aspect of the equation is correct (it's used heavily throughout the code and functions as expected in the other cases)..

All rail collisions work perfectly except for the jaws.

 

[mfb]

To find those two jaws I need to remove the pockets and move the ball off the table (through the SW pocket) once there I can get a collision to be detected as certain points beyond the pocket (not where the jaws should be though). BUT they move as the ball position moves so they are not in a static position and as such I can't describe where they are well.

I don't understand anything of that.

The current collision algorithm assumes borders of infinite length - could this cause the problem? Do you use test trajectories where the finite length is important?

 

[gogreengo]

I don't understand anything of that.

I totally understand - it's difficult to describe. Here is an illustration that shows what I was trying to say:

When the cue ball is off the table as shown, I can get collisions to be 'predicted' near where the red lines are.. I understand this is probably not very useful, but I'm describing what I see visually.

The current collision algorithm assumes borders of infinite length - could this cause the problem? Do you use test trajectories where the finite length is important?

Yes, that is what the collision_x and collision_y are being used for (to restrict the collision region that would constitute a jaw collision along the infinite lines)... I'm also doing the same to shorten the N,E,S & W rails (to allow a pocket opening) and this works without issue on the existing rails.

Again, thanks for your time looking at this, it is much appreciated.

Cheers,
Lark

 

[mfb]

Hmm. I wonder what happens if you just make two borders - south rail and north jaw, for example, and those with infinite length. That could help to spot the error. How do the (imaginary) red lines change if you move the borders around?

 

[gogreengo]

Hmm. I wonder what happens if you just make two borders - south rail and north jaw, for example, and those with infinite length. That could help to spot the error. How do the (imaginary) red lines change if you move the borders around?

Excellent suggestion (I have no idea why I didn't simplify the problem initially).

So I've removed all except the South West pocket East jaw - no other rails or pockets. I get this effect:

Note how as I move the cue ball the line also moves. The line is showing where a cue ball collision would occur if I aimed towards the red line.

Now if I move the cue ball towards the NE pocket the line moves 'away' from the cue ball

Obviously this is also no where near where the South West pocket E jaw line should be...

Does that give you any hints on what's going wrong?

 

[mfb]

Looks like some sign errors. I would change them one by one to see the effects.

 

[gogreengo]

Looks like some sign errors. I would change them one by one to see the effects.

And it seems so obvious now that you point it out for me :)

Indeed it was sign error causing the crazy placement of the line and after some trial and error I've now got a SW pocket East jaw that is where I expect it. I still have issues but it is much closer.

Thanks for your help so far.

 

[gogreengo]

So I'm still unable to solve this problem. I am a little closer and I have gained additional understanding but still can not find a suitable solution.

I'll see if I can explain what is now occurring.

For the SWp EJ I am now using the formula:

numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (u_hat.y + u_hat.x), v.x - v.y, r.x - r.y - cp_width + ball.getRadius(), &root1, &root2);

This is to describe the line (ignoring the ball radius for now):

v1 = x=cp_width, y=0, z=0
v2 = x=0, y=-cp_width, z=0

This seems to solve ok with:

x - y - cp_width = 0

So for v1 when y = 0

x - 0 - cp_width = 0
x - cp_width = 0
x = cp_width

For v2 when x = 0

-y - cp_width = 0
-y = cp_width
y = -cp_width

I have followed mfb's advice and tried multiplying a few values by (1*sqrt(2)) but this doesn't seem to have any influence on my current problems (but may be required once the problems are fixed)..

The equation I ended up with for this line is:

numRoots = gsl_poly_solve_quadratic(-0.5 * mu * Table::g * (1/sqrt(2.0))*(u_hat.y + u_hat.x),(1/sqrt(2.0))*(v.x - v.y), (1/sqrt(2.0))*(r.x - r.y - cp_width_real+ball_radius), &root1, &root2);

Which is possibly not correctly interpreted from mfb's advice. But I'm using the former equation without the 1/sqrt(2) to keep things simple until I find the cause of the bigger issue.

So that's the current state for which I am about to describe the effects I see.

The velocity seems to effect the collision point. With a low velocity the line seems to be much closer to the ball than with a high velocity - this suggests to me that the (v.x - v.y) parameter (which appears to describe the velocity) is not correct for a line at this slope (as opposed to the N,E,S & W rails) is that possible?

Is it possible that the (v.x - v.y) and its variants used are only relevant for lines parallel to the x and y axis? And if so, can this be adjusted to work for a line on a 45° angle like I'm trying?

Another issue (which I think is probably best left until my main issue is fixed) is that the paper that describes this mathematics states:

Since the ball’s position vector r (t) refers to its center, when predicting rail collisions the look for the intersection of the ball’s center and a horizontal line parallel to the rail but one ball radius toward the center of the table.

I'm pretty sure this won't work for that jaw line since the line [STRIKE]actually needs to move out one ball radius on the lines normal which is not towards the table centre[/STRIKE] needs to move some other function of the ball radius (I think, and I'm not sure what it would be). This may also give hints on why this whole approach seems to be failing..

Any ideas?

 

[gogreengo]

..bump..

Sorry for bumping this post, but I'm getting really desperate here and any ideas/input that anyone can provide here would be greatly appreciated.

Cheers,
Lark