Bezier. Solving X,Y

Processing Coding Questions
1

Hello friends,

I’ve been trying to find the Y coordinates of a Bezier Curve given X. I’ve been fairly successful getting approximate values by putting in an array lots of x values corresponding to “t” using the bezierPoint. Then obtaining the closest x values to my requested x values. But that’s only an approximation that requires iterating through at least 4000 values to be reasonably close.

Then I searched the forums for a way to do it mathematically solving cubic roots and the maths is way, way beyond me. There are some solutions out there to be found, but they are mainly written in javascript.

Then I found this equations written by prince_polka that almost do what I want, but unfortunately it all fails at some point because they weren’t really meant to do what I want to do, as illustrated bellow. Please drag the bottom control point to the right, pass the middle point, and you will see that the “t” coordinates suddenly disappear, the ellipse vanishes. I think it’s almost there though, but prince_polka doesn’t seem to be in the forum for me to ask him and use his clever brain:).

Could some kind person who has managed to solve XY mathematically help me with a solution to use with Processing please?

Link to original code:

https://forum.processing.org/two/discussion/23333/using-a-bezier-curve-as-a-boundary

//=======================================

PVector p1= new PVector(50, 200);//bottom anchor
PVector c1= new PVector(200, 340);//bottom control
PVector c2= new PVector(600, 130);//top control
PVector p2= new PVector(750, 200);//top anchor


float x;
float y;

void setup() {
  size(800, 450);
  noFill();
}
void draw() {
  background(255);
  stroke(1);
  noFill();
  rect(50, 50, 700, 330);


  double[] sol = bezierTime(p1.x, c1.x, c2.x, p2.x, mouseX);


  noFill();
  stroke(1);
  bezier(p1.x, p1.y, c1.x, c1.y, c2.x, c2.y, p2.x, p2.y);


  x = bezierPoint(p1.x, c1.x, c2.x, p2.x, (float)sol[1]);
  y = bezierPoint(p1.y, c1.y, c2.y, p2.y, (float)sol[1]);



  fill(1);
  text("t:   "+sol[1], 80, 80);
  text("x:   "+x, 290, 400);
  text("y:   "+y, 420, 400);

  noStroke();
  fill(255, 0, 0);
  ellipse(x, y, 10, 10);
  stroke(1);
  line(400, 50, 400, 80);


  float distance1 = dist(mouseX, mouseY, c1.x, c1.y);    

  if (mousePressed) {
    if (distance1<25) {
      c1.x=mouseX;
      c1.y=mouseY;
    }
  }

  float distance2 = dist(mouseX, mouseY, c2.x, c2.y);    

  if (mousePressed) {
    if (distance2<25) {
      c2.x=mouseX;
      c2.y=mouseY;
    }
  }


  noStroke();
  fill(0, 0, 250);
  ellipse(c1.x, c1.y, 10, 10);
  ellipse(c2.x, c2.y, 10, 10);
}// end draw


//=====FORMULAS===VVVVV=== as calculated by prince_polka and posted in the Processing forum September 2017

double[] bezierTime( double A, double B, double C, double D, double E ) {
  double[] T = new double[3];
  double F, G, H, J, FG, s, r, n, multr;
  final double U, HALF_PI, TWO_PI, SIXTH_PI;

  H =  3*(C-B) + A-D;

  F = 27*((B-C-C)*(B*(B+B+C)-C*(A*3+C))+D*(A*(A+D-3*(B+C))+B*(6*B-3*C))-(H*H*E));

  G =  9 * ( A*(C-D) + B*(D+C-B) - C*C );

  J = ( A + C - B - B )/H;

  U = 1.5874010519681994747517056392723; //2^2/3

  HALF_PI = 1.5707963267948966192313216916397;

  TWO_PI = 6.28318530717958647692528676655;

  SIXTH_PI = 0.5235987755982988730771072305465;

  FG = F*F+4*G*G*G;

  s = Math.sqrt(Math.abs(FG));
  if (FG>=0) {
    r =   Math.cbrt(Math.abs(F+s));
    n = ( Math.atan2(0, F+s) + TWO_PI )/3;
  } else {
    r = Math.cbrt(Math.abs(F)+s);
    n = ( Math.atan2(s, F) + TWO_PI )/3;
  }

  multr = (4*G - r*r *U*U)/(6*H*r*U);

  T[0] = Math.sin( -n - HALF_PI  ) * multr + J;
  T[1] = Math.sin(  n + SIXTH_PI ) * multr + J;
  T[2] = Math.sin( -n + SIXTH_PI ) * multr + J;


  return T;
}
2 Likes
2

please repair your code posting using from editor menu
</> Preformatted text

this above is not usable for copy / paste to PDE

please give link to the code source

are you using

in a FOR loop over that 4000 points?
in a kind of graph?

3

Not bezierVertex, but bezier(), then bezierPoint(), but anyway I don’t want to use approximation if possible.

4

i can’t imagine the
bezier();
with 8000 parameters
( or 4000 bezier() pieces each 8 parameter )

when you have 4000 measuring points,
if you do a line, or curve, bezier between them, THAT IS a approximation.
and doing the bezier math backward to estimate points inbetween not makes it better.

would you share the physical background of that problem?
because if you have a set of data points, but need a
y = f(x) you do spline / regression math

but i like your sketch / and show /
and i learned that obviously t can work also outside of [ 0 … 1 ]

5

Alternatively, I found this Java class that the author claims it does the job, but I don’t know how to adapt it to be used with Processing, or whether it actually works.

https://stackoverflow.com/questions/7348009/y-coordinate-for-a-given-x-cubic-bezier

Here is the Java code, in case someone could adapt it to test it?:

public class CubicBezier {
    private BezierCubic bezier = new BezierCubic();
    public CubicBezier(float x1, float y1, float x2, float y2) {
        bezier.set(new Vector3(0,0,0), new Vector3(x1,y1,0), new Vector3(x2,y2,0), new Vector3(1,1,1));
    }
    public float get(float t) {
        float l=0, u=1, s=(u+l)*0.5f;
        float x = bezier.getValueX(s);
        while (Math.abs(t-x) > 0.0001f) {
            if (t > x)  { l = s; }
            else        { u = s; }
            s = (u+l)*0.5f;
            x = bezier.getValueX(s);
        }
        return bezier.getValueY(s);
    }
};

public class BezierCubic {
private float[][] cpoints = new float[4][3];
private float[][] polinom = new float[4][3];

public BezierCubic() {}

public void set(Vector3 c0, Vector3 c1, Vector3 c2, Vector3 c3) {
    setPoint(0, c0);
    setPoint(1, c1);
    setPoint(2, c2);
    setPoint(3, c3);
    generate();
}

public float getValueX(float u) {
    return getValue(0, u);
}

public float getValueY(float u) {
    return getValue(1, u);
}

public float getValueZ(float u) {
    return getValue(2, u);
}

private float getValue(int i, float u) {
    return ((polinom[0][i]*u + polinom[1][i])*u + polinom[2][i])*u + polinom[3][i];
}

private void generate() {
    for (int i=0; i<3; i++) {
        float c0 = cpoints[0][i], c1 = cpoints[1][i], c2 = cpoints[2][i], c3 = cpoints[3][i];
        polinom[0][i] = c0 + 3*(c1 - c2) + c3;
        polinom[1][i] = 3*(c0 - 2*c1 + c2);
        polinom[2][i] = 3*(-c0 + c1);
        polinom[3][i] = c0;
    }
}

private void setPoint(int i, Vector3 v) {
    cpoints[i][0] = v.x;
    cpoints[i][1] = v.y;
    cpoints[i][2] = v.z;
}
}
1 Like
6

Well, I’ve started to modify the Java class above to what I thought might work with Processing, but I am quite stuck (in other words, I don’t know what I am supposed to be doing, at least it’s not crashing). I am trying, but I need some help to continue please?



CubicBezier myBezier;
BezierCubic bezier; 

float x1=50;
float  y1=200;

float x2=500;
float y2=200;

PVector c0= new PVector(45, 50); 
PVector c1= new PVector(200, 340); 
PVector c2= new PVector(600, 130); 
PVector c3= new PVector(50, 20); 


void setup() {
  size(600, 400); 
  stroke(1);
  myBezier = new  CubicBezier(x1, y1, x2, y2);
  
  BezierCubic bezier = new BezierCubic();
  bezier.set(c0, c1, c2, c3);
}


void draw() {
  background(255);
}//end draw


public class CubicBezier {
  private BezierCubic bezier = new BezierCubic();
  public CubicBezier(float x1, float y1, float x2, float y2) {
    bezier.set(new PVector(0, 0), new PVector(x1, y1), new PVector(x2, y2), new PVector(1, 1));
  }
  public float get(float t) {
    float l=0, u=1, s=(u+l)*0.5f;
    float x = bezier.getValueX(s);
    while (Math.abs(t-x) > 0.0001f) {
      if (t > x) { 
        l = s;
      } else { 
        u = s;
      }
      s = (u+l)*0.5f;
      x = bezier.getValueX(s);
    }
    return bezier.getValueY(s);
  }
};

public class BezierCubic {
  private float[][] cpoints = new float[4][3];
  private float[][] polinom = new float[4][3];

  public BezierCubic() {
  }

  public void set(PVector c0, PVector c1, PVector c2, PVector c3) {
    setPoint(0, c0);
    setPoint(1, c1);
    setPoint(2, c2);
    setPoint(3, c3);
    generate();
  }

  public float getValueX(float u) {
    return getValue(0, u);
  }

  public float getValueY(float u) {
    return getValue(1, u);
  }

  public float getValueZ(float u) {
    return getValue(2, u);
  }

  private float getValue(int i, float u) {
    return ((polinom[0][i]*u + polinom[1][i])*u + polinom[2][i])*u + polinom[3][i];
  }

  private void generate() {
    for (int i=0; i<3; i++) {
      float c0 = cpoints[0][i], c1 = cpoints[1][i], c2 = cpoints[2][i], c3 = cpoints[3][i];
      polinom[0][i] = c0 + 3*(c1 - c2) + c3;
      polinom[1][i] = 3*(c0 - 2*c1 + c2);
      polinom[2][i] = 3*(-c0 + c1);
      polinom[3][i] = c0;
    }
  }

  private void setPoint(int i, PVector v) {
    cpoints[i][0] = v.x;
    cpoints[i][1] = v.y;
    cpoints[i][2] = v.z;
  }
}
7

i failed to get something good, but i tried to understand what you wanted to do??

// https://discourse.processing.org/t/bezier-solving-x-y/14492/6

CubicBezier myBezier;
float  x,      y;
float  x0=0,   y0=200;
float  x1=50,  y1=200;
float  x2=500, y2=200;
float  x3=550, y3=200;

void setup() {
  size(600, 400); 
  myBezier = new  CubicBezier(x0, y0, x1, y1 ,x2, y2, x3, y3);
}

void draw() {
  background(255);
  x = mouseX;
  y = myBezier.get(x);
  show();
}

void show() {
  stroke(0,200,0);
  circle(x0,y0,20);
  circle(x1,y1,20);
  circle(x2,y2,20);
  circle(x3,y3,20);
  stroke(0,0,200);
  circle(x,y,20);
}

public class CubicBezier {
  private BezierCubic bezier = new BezierCubic();
  public CubicBezier(float x0, float y0,float x1, float y1, float x2, float y2,float x3, float y3) {
    bezier.set(new PVector(x0, y0), new PVector(x1, y1), new PVector(x2, y2), new PVector(x3,y3));
  }
  public float get(float t) {
    float l=0, u=1, s=(u+l)*0.5f;
    float x = bezier.getValueX(s);
    while (Math.abs(t-x) > 0.0001f) {
      if (t > x) { 
        l = s;
      } else { 
        u = s;
      }
      s = (u+l)*0.5f;
      x = bezier.getValueX(s);
    }
    return bezier.getValueY(s);
  }
};

public class BezierCubic {
  private float[][] cpoints = new float[4][3];
  private float[][] polinom = new float[4][3];

  public BezierCubic() {
  }

  public void set(PVector c0, PVector c1, PVector c2, PVector c3) {
    setPoint(0, c0);
    setPoint(1, c1);
    setPoint(2, c2);
    setPoint(3, c3);
    generate();
  }

  public float getValueX(float u) {
    return getValue(0, u);
  }

  public float getValueY(float u) {
    return getValue(1, u);
  }

  public float getValueZ(float u) {
    return getValue(2, u);
  }

  private float getValue(int i, float u) {
    return ((polinom[0][i]*u + polinom[1][i])*u + polinom[2][i])*u + polinom[3][i];
  }

  private void generate() {
    for (int i=0; i<3; i++) {
      float c0 = cpoints[0][i], c1 = cpoints[1][i], c2 = cpoints[2][i], c3 = cpoints[3][i];
      polinom[0][i] = c0 + 3*(c1 - c2) + c3;
      polinom[1][i] = 3*(c0 - 2*c1 + c2);
      polinom[2][i] = 3*(-c0 + c1);
      polinom[3][i] = c0;
    }
  }

  private void setPoint(int i, PVector v) {
    cpoints[i][0] = v.x;
    cpoints[i][1] = v.y;
    cpoints[i][2] = v.z;
  }
}

but now i see in the original its not x, its t

public float get(float t)

sorry, just ignore it.

8

All I want is to find values of Y given X values. The ultimate end is to have a timeline (position vs time) using a series of joint bezier curves from which I can send position values to an Arduino to drive a stepper motor. I already have all that done, the only thing missing is a way to get super accurate Y values, from typically 500 equally spaced X values for a 10 second run. The initial code at the top of this post does that up to a point, then it breaks, unfortunately.

The best way, as I understand it, is to solve a cubic equation for the cubic Bezier using Cardano’s algorithm from which you obtain three roots, three “t” values, discarding two of them. From the “t” value, you then derive Y from X. All this has been put to code by a few guys in Javascript and it works. I tried to translate from Javascript to Java, but I don’t yet have the knowledge to do it.

1 Like
9

Using Processing’s own bezierPoint, you can easily get any values XY from ‘t’. The difficult thing is to do the reverse, if I have, say, a value of x=300, I want to know the corresponding and exact Y value.

10

A series of joint bezier curves is in effect a Bezier spline, a smooth continuous line that passes through a series of control points and where the shape of the curve between any two control points is a cubic Bezier curve.

  1. Where do you get your control points from?
  2. Does the position data between any two control points follow a cubic Bezier curve?
  3. What do you mean by exact?
11

Hi Quark,
The joined bezier points are added to PVector array lists, two for the controls and two for the start/end anchors, subsequent in-between points of the path are added (if needed) by splitting the relevant Bezier section based on de Casteljau.
I end up with xy data for each bezier section where t is 0 to 1, and these values are then spliced together in a final array of position values for the whole length . By exact, obviously there’s some rounding of decimals, but I meant something not worked out by the approximate closeness to a point in the Bezier, but by solving an equation.

I think there is a possibility of converting to a Catmull Rom spline at the end of all adjustments, but I like the flexibility and control of the curve that you get with Beziers.

12

A cubic curve has 1, 2 or 3 real solutions and there is a cubic formula that can be used to find them, see below. Unfortunately intermediate stages of the calculations involves using complex numbers. It should be possible to use polar representations of the complex numbers instead, your original code seems to use this approach.

20
20589×511 30.6 KB

Can you provide links?

1 Like
13

Thank you Quark.

This guy, Mike Pomax, seems to know a lot about Beziers. One of his replies in Javascript is here:

https://stackoverflow.com/questions/51879836/cubic-bezier-curves-get-y-for-given-x-special-case-where-x-of-control-points

He also has working examples in his blog: A primer on Bezier Curves.

https://pomax.github.io/bezierinfo/#yforx

Then there are these two posts (last two) here:

Another interesting one here:

1 Like
14

From your first link I have adapted the code for Processing. If you run the code below and move the mouse in the X range of the Bezier curve then it will calculate the ‘t’ value and hence the ‘y’ value and show the position as red ellipse.

final double EPSILON = 1E-10;

PVector cp0 = new PVector( 40, 140);
PVector cp1 = new PVector(100, 200);
PVector cp2 = new PVector(250, 70);
PVector cp3 = new PVector(360, 210);

void setup() {
  size(400, 300);
}

void draw() {
  background(255);
  // Draw Bezier hull
  stroke(200);
  line(cp0.x, cp0.y, cp1.x, cp1.y);
  line(cp1.x, cp1.y, cp2.x, cp2.y);
  line(cp2.x, cp2.y, cp3.x, cp3.y);
  // Draw control points
  noStroke();
  fill(160);
  ellipse(cp0.x, cp0.y, 8, 8);
  ellipse(cp1.x, cp1.y, 8, 8);
  ellipse(cp2.x, cp2.y, 8, 8);
  ellipse(cp3.x, cp3.y, 8, 8);
  // Draw Bezier curve
  stroke(0, 200, 0);
  strokeWeight(1.5);
  noFill();
  bezier(cp0.x, cp0.y, cp1.x, cp1.y, cp2.x, cp2.y, cp3.x, cp3.y);
  // If mouseX is within Bezier range, calculate the parametric
  // value t and from that the corresponding y position on the
  // cubic Bezier curve
  if (mouseX >= cp0.x && mouseX <= cp3.x) {
    float t = (float) findTforX(mouseX, cp0.x, cp1.x, cp2.x, cp3.x);
    float y = bezierPoint(cp0.y, cp1.y, cp2.y, cp3.y, t);
    fill(255, 0, 0, 160);
    noStroke();
    ellipse(mouseX, y, 12, 12);
  }
}


double findTforX(double x, double pa, double pb, double pc, double pd ) {
  double t = 0;
  double[] roots = findRoots(x, pa, pb, pc, pd);
  if (roots.length > 0) {
    for (double _t : roots) {
      if (_t<0 || _t>1) continue;
      t = _t;
      break;
    }
  }
  return t;
}

boolean approximately(double n0, double n1) {
  return Math.abs(n1 - n0) <= EPSILON;
}


// Find the roots for a cubic polynomial with bernstein coefficients
// {pa, pb, pc, pd}. The function will first convert those to the
// standard polynomial coefficients, and then run through Cardano's
// formula for finding the roots of a depressed cubic curve.
double[] findRoots(double x, double pa, double pb, double pc, double pd) {
  double
    pa3 = 3 * pa, 
    pb3 = 3 * pb, 
    pc3 = 3 * pc, 
    a = -pa  +   pb3 - pc3 + pd, 
    b =  pa3 - 2*pb3 + pc3, 
    c = -pa3 +   pb3, 
    d =  pa  -     x;

  // Fun fact: any Bezier curve may (accidentally or on purpose)
  // perfectly model any lower order curve, so we want to test 
  // for that: lower order curves are much easier to root-find.
  if (approximately(a, 0)) {
    // this is not a cubic curve.
    if (approximately(b, 0)) {
      // in fact, this is not a quadratic curve either.
      if (approximately(c, 0)) {
        // in fact in fact, there are no solutions.
        return new double[]{};
      }
      // linear solution:
      return new double[]{-d / c};
    }
    // quadratic solution:
    double
      q = Math.sqrt(c * c - 4 * b * d), 
      b2 = 2 * b;
    return new double[]{
      (q - c) / b2, 
      (-c - q) / b2
    };
  }

  // At this point, we know we need a cubic solution,
  // and the above a/b/c/d values were technically
  // a pre-optimized set because a might be zero and
  // that would cause the following divisions to error.

  b /= a;
  c /= a;
  d /= a;

  double
    b3 = b / 3, 
    p = (3 * c - b*b) / 3, 
    p3 = p / 3, 
    q = (2 * b*b*b - 9 * b * c + 27 * d) / 27, 
    q2 = q / 2, 
    discriminant = q2*q2 + p3*p3*p3, 
    u1, v1;

  // case 1: three real roots, but finding them involves complex
  // maths. Since we don't have a complex data type, we use trig
  // instead, because complex numbers have nice geometric properties.
  if (discriminant < 0) {
    double
      mp3 = -p/3, 
      r = Math.sqrt(mp3*mp3*mp3), 
      t = -q / (2 * r), 
      cosphi = t < -1 ? -1 : t > 1 ? 1 : t, 
      phi = Math.acos(cosphi), 
      crtr = Math.cbrt(r), 
      t1 = 2 * crtr;
    return new double[]{
      t1 * Math.cos(phi / 3) - b3, 
      t1 * Math.cos((phi + TAU) / 3) - b3, 
      t1 * Math.cos((phi + 2 * TAU) / 3) - b3
    };
  }

  // case 2: three real roots, but two form a "double root",
  // and so will have the same resultant value. We only need
  // to return two values in this case.
  else if (discriminant == 0) {
    u1 = q2 < 0 ? Math.cbrt(-q2) : -Math.cbrt(q2);
    return new double[]{
      2 * u1 - b3, 
      -u1 - b3
    };
  }

  // case 3: one real root, 2 complex roots. We don't care about
  // complex results so we just ignore those and directly compute
  // that single real root.
  else {
    double sd = Math.sqrt(discriminant);
    u1 = Math.cbrt(-q2 + sd);
    v1 = Math.cbrt(q2 + sd);
    return new double[]{u1 - v1 - b3};
  }
}
4 Likes
15

Quark, what can I say, you’ve done it! And so quickly too.
I am eternally grateful. Can I contact you from you website, since you are in the UK, like me. I’d like to buy you a book just to say thank you! Amazon will deliver it, please think of a title meanwhile,
Edward

1 Like
16

OK I have replied to your email before I read your last post. Since you made the offer here I will repeat the message here.

Everything I do for Processing and on this forum I do for free. If you or anyone else feels that my efforts are worth financial reward I ask them to make a donation to a charity dedicated to helping children in their country.

Since you are in the UK I suggest NSPCC, you should be able to make a donation on line.

Problems like yours I find challenging and get satisfaction from solving it (if I can :grinning:)

3 Likes
17

https://www.nspcc.org.uk/what-you-can-do/make-a-donation/?utm_source=homepage

18

Just want to thank Edward for his donation to MacMillan nurses, they do an incredible job in very difficult circumstances and they deserve our support. If a donor has a personal preference as to charity that’s great if not then a children’s charity is preferred.

4 Likes