[SOLVED] Interpolating a continuous bezier curve


#1

It’s relatively straightforward interpolating a single bezier curve. What I’m looking for is a way to interpolate a continuous bezier curve. I’m assuming it’s possible, and if I wasn’t pressed for time I’d probably figure it out eventually. But I seek the help of the experts here so I can take a shortcut given my production demands.

So the question is: Given a continuous bezier comprised of an arbitrary number of bezier segments how does one normalize the entire curve to grab an arbitrary interpolated point on it?

Here’s a little test case using arbitrary anchor and control points. Ideally the interp() method will evaluate the entire curve, not just the first bezier segment.

void setup(){
  size(400, 400,P3D);
  background(255);
  myBez mb = new myBez();
  shape(mb.ps);
  mb.interp(20);
}

class myBez{
  PShape ps;
  PVector apt1 = new PVector(100, 100);
  PVector cpt1 = new PVector(-100, 220);
  PVector apt2 = new PVector(200, 100);
  PVector cpt2 = new PVector(200, 100);
  PVector apt3 = new PVector(150, 200);
  PVector cpt3 = new PVector(250, 100);
  
  myBez(){
    ps = createShape();
    ps.beginShape();
    ps.strokeWeight(3);
    ps.vertex(apt1.x, apt1.y);
    ps.bezierVertex(cpt1.x, cpt1.y, cpt2.x, cpt2.y, apt2.x, apt2.y);
    ps.bezierVertex(cpt2.x, cpt2.y, cpt3.x, cpt3.y, apt3.x, apt3.y);
    ps.endShape();
  }
  
  void interp(int segs){
    for (int i=0; i<=segs; i++){
      float t = i / float(segs);
      float x = bezierPoint(apt1.x, cpt1.x, cpt2.x, apt2.x, t);
      float y = bezierPoint(apt1.y, cpt1.y, cpt2.y, apt2.y, t);
      ellipse(x, y, 10, 10);
    }
  }
}

I figure a PShape object would be easier to evaluate a continuous curve since it’s a self-contained object. Unfortunately I don’t know a way to evaluate a point on the curve (using bezierVertex) that doesn’t require arrays of points. (I guess that’s the crux of the problem, isn’t it?) This problem is compounded if the evaluation of the normalized curve isn’t linear (eg: t = pow(i/segs, .75)), which to me would be highly desirable.

Any help appreciated. Thank you.


#2

Does the example in:

Examples > Topics > Curves > ArcLengthParameterization

…do what you are wanting? It is segment based.

If not, there are ways to use a wrapper on lerp() to find a segment from a list, then solve for that segment. This is the general approach:


#3

I continually forget to look in the examples, so thank you for the reminder.

Yes, this looks like a perfect solution.

Thank you – once again! – Jeremy!


#4

I’ve reached the point where I needed to solve this.

Jeremy, once again you’ve saved my life! I am most grateful for the link to your “List-based interpolations” post on the previous forum… it’s tremendously useful! (I had already solved the gradient problem for myself, but your solution is far more elegant!) (…and I’m still not accustomed to using modulus for floats!)

Just for the sake of closure, here is my solution for the continuous bezier curve defined in the first post using your (modified) solution. I didn’t incorporate the ArcLengthParameterization example you informed me about since I don’t need it right now, but it won’t be difficult to implement when the time comes.

void setup(){
  size(400, 400,P3D);
  background(255);
  myBez mb = new myBez();
  shape(mb.ps);
  mb.interp(20);
}

class myBez{
  PShape ps;
  PVector apt1 = new PVector(100, 100);
  PVector cpt1 = new PVector(-100, 220);
  PVector apt2 = new PVector(200, 100);
  PVector cpt2 = new PVector(200, 100);
  PVector apt3 = new PVector(150, 200);
  PVector cpt3 = new PVector(250, 100);
  
  PVector[] anchorPts  = {apt1, apt2, apt3};
  PVector[] controlPts = {cpt1, cpt2, cpt3};
  
  myBez(){
    ps = createShape();
    ps.beginShape();
    ps.strokeWeight(3);
    ps.vertex(apt1.x, apt1.y);
    ps.bezierVertex(cpt1.x, cpt1.y, cpt2.x, cpt2.y, apt2.x, apt2.y);
    ps.bezierVertex(cpt2.x, cpt2.y, cpt3.x, cpt3.y, apt3.x, apt3.y);
    ps.endShape();
  }
  
  void interp(int segs){
    for (int i=0; i<=segs; i++){
      PVector loc = lerpBezVectors(i/float(segs), anchorPts, controlPts);
      ellipse(loc.x, loc.y, 10, 10);
    }
  }
}

PVector lerpBezVectors(float amt, PVector[] apts, PVector[] cpts) {
  // it is assumed that the array sizes of apts & cpts are the same

  float cunit = 1.0/(apts.length-1);
  float t     = amt%cunit/cunit;
  
  int fromIndex = floor(amt/cunit);
  int toIndex   = ceil(amt/cunit);
  
  float x = bezierPoint(apts[fromIndex].x, cpts[fromIndex].x, cpts[toIndex].x, apts[toIndex].x, t);
  float y = bezierPoint(apts[fromIndex].y, cpts[fromIndex].y, cpts[toIndex].y, apts[toIndex].y, t);

  return new PVector(x,y);
}

#5

Glad it was helpful – thank you so much for sharing your solution!

You can also animate your found point – it really takes that sharp curve slowly. Here is your sketch with draw and an animation method added.

Summary
myBez mb;

void setup(){
  size(400, 400,P3D);
  mb = new myBez();
}

void draw(){
  background(255);
  shape(mb.ps);
  mb.lerp(frameCount%60/60.0);
}

class myBez{
  PShape ps;
  PVector apt1 = new PVector(100, 100);
  PVector cpt1 = new PVector(-100, 220);
  PVector apt2 = new PVector(200, 100);
  PVector cpt2 = new PVector(200, 100);
  PVector apt3 = new PVector(150, 200);
  PVector cpt3 = new PVector(250, 100);
  
  PVector[] anchorPts  = {apt1, apt2, apt3};
  PVector[] controlPts = {cpt1, cpt2, cpt3};
  
  myBez(){
    ps = createShape();
    ps.beginShape();
    ps.strokeWeight(3);
    ps.vertex(apt1.x, apt1.y);
    ps.bezierVertex(cpt1.x, cpt1.y, cpt2.x, cpt2.y, apt2.x, apt2.y);
    ps.bezierVertex(cpt2.x, cpt2.y, cpt3.x, cpt3.y, apt3.x, apt3.y);
    ps.endShape();
  }
  
  void interp(int segs){
    for (int i=0; i<=segs; i++){
      PVector loc = lerpBezVectors(i/float(segs), anchorPts, controlPts);
      ellipse(loc.x, loc.y, 10, 10);
    }
  }
  
  void lerp(float amt){
    PVector loc = lerpBezVectors(amt, anchorPts, controlPts);
    ellipse(loc.x, loc.y, 10, 10);
  }
}

PVector lerpBezVectors(float amt, PVector[] apts, PVector[] cpts) {
  // it is assumed that the array sizes of apts & cpts are the same

  float cunit = 1.0/(apts.length-1);
  float t     = amt%cunit/cunit;
  
  int fromIndex = floor(amt/cunit);
  int toIndex   = ceil(amt/cunit);
  
  float x = bezierPoint(apts[fromIndex].x, cpts[fromIndex].x, cpts[toIndex].x, apts[toIndex].x, t);
  float y = bezierPoint(apts[fromIndex].y, cpts[fromIndex].y, cpts[toIndex].y, apts[toIndex].y, t);

  return new PVector(x,y);
}

The main difference when using ArcLengthParameterization is that in that case your ellipses / time slices will be evenly distributed along the curve, rather than spread out and bunched up. It really depends on the effect that you want.


#6

Actually, I just realized this is only partially solved. So long as the anchor points between the terminal points share the same control point the above solution works.

But a continuous bezier curve comprised of multiple segments requires two control points per anchor for the inner anchors, thus increasing the array size of the control points.

Eg:

  PVector[] anchorPts  = {apt1, apt2, apt3};
  PVector[] controlPts = {cpt1, cpt2a, cpt2b, cpt3};

This could be fixed by duplicating the inner anchor points in the anchor array:

  PVector[] anchorPts  = {apt1,  apt2,  apt2, apt3};
  PVector[] controlPts = {cpt1, cpt2a, cpt2b, cpt3};

But that doesn’t seem like an ideal solution.

It seems that a 2D array would be preferable: an array of the bezier’s segments, each segment having its own array of the four points defining it. This maintains parity between anchors and controls:

PVector[][] segs = { {apt1, cpt1, apt2, cpt2a} , {apt2, cpt2b, apt3, cpt3} };

For now my solution a couple of posts ago works for what I need (fortunately). But when time permits I’ll generalize this.


#7

Hi @Aleksi,

Just a thought, you could group an anchor point together with the preceding and succeeding control points in an object; a curve could then store a one-dimensional array of instances of that object. To give an idea of what I mean, here is a p5.js version.