Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Calculating event time using gsl_poly_solve_quadratic

  1. Jun 25, 2013 #1
    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: FastFiz

    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:

    pool_1.png

    (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:

    Code (Text):
      //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:

    Code (Text):
      //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:

    Code (Text):
    //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.
     
    Last edited: Jun 25, 2013
  2. jcsd
  3. Jun 25, 2013 #2
    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:

    swpej.png

    and given the equation:

    Code (Text):
     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:

    swpnj.png

    and given the equation:

    Code (Text):
    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?
     
    Last edited: Jun 25, 2013
  4. Jun 25, 2013 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  5. Jun 25, 2013 #4
    Hey mfb,

    Huge thanks for your time!

    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.

    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.

    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)

    Code (Text):
    //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
     
    Last edited: Jun 25, 2013
  6. Jun 26, 2013 #5
    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:

    Code (Text):
    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:

    Code (Text):
    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:

    Code (Text):
    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:

    Code (Text):
    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?
     
  7. Jun 27, 2013 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    What is going wrong?
    Did you try my suggestion to set mu=0?
     
  8. Jun 27, 2013 #7
    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.

    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.
     
  9. Jun 27, 2013 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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?
     
  10. Jun 27, 2013 #9
    I totally understand - it's difficult to describe. Here is an illustration that shows what I was trying to say:

    swpnjx.png

    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.

    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
     
  11. Jun 28, 2013 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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?
     
  12. Jun 30, 2013 #11
    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.

    swpej_x1.png

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

    swpej_x2.png

    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?
     
    Last edited: Jun 30, 2013
  13. Jun 30, 2013 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Looks like some sign errors. I would change them one by one to see the effects.
     
  14. Jun 30, 2013 #13
    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.
     
  15. Jul 2, 2013 #14
    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:

    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?
     
    Last edited: Jul 2, 2013
  16. Jul 5, 2013 #15
    ..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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Calculating event time using gsl_poly_solve_quadratic
Loading...