How to move along a bezier curve with a constant velocity without a costly precomputation?

Question

Forgive me for the long code example, but I couldn't figure out how to properly explain my question with any less code:

let c = document.querySelector("canvas");
let ctx = c.getContext("2d");

class BezierCurve {
  constructor(x1, y1, cpX, cpY, x2, y2) {
    this.f = 0;

    this.x1 = x1;
    this.y1 = y1;
    this.cpX = cpX;
    this.cpY = cpY;
    this.x2 = x2;
    this.y2 = y2;
    this.pointCache = this.calcPoints();
  }

  calcX(t) { return (1 - t) * (1 - t) * this.x1 + 2 * (1 - t) * t * this.cpX + t * t * this.x2; }
  calcY(t) { return (1 - t) * (1 - t) * this.y1 + 2 * (1 - t) * t * this.cpY + t * t * this.y2; }

  calcPoints() {
    const step = 0.001, segments = [];
  
    for (let i = 0; i <= 1 - step; i += step) {
      let dx = this.calcX(i) - this.calcX(i + step);
      let dy = this.calcY(i) - this.calcY(i + step);
  
      segments.push(Math.sqrt(dx * dx + dy * dy));
    }
  
    const len = segments.reduce((a, c) => a + c, 0);

    let result = [], l = 0, co = 0;
  
    for (let i = 0; i < segments.length; i++) {
      l += segments[i];
      co += step;
      result.push({ t: l / len, co });
    }
  
    return result;
  }

  draw() {
    ctx.beginPath();
    ctx.moveTo(this.x1, this.y1);
    ctx.quadraticCurveTo(this.cpX, this.cpY, this.x2, this.y2);
    ctx.stroke();
  }

  tick(amount = 0.001) {
    this.f = this.f < 1 ? this.f + amount : 0;
  }
}

function drawCircle(x, y, r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, 2 * Math.PI);
  ctx.fill();
}

let a = new BezierCurve(25, 25, 80, 250, 100, 50);
let b = new BezierCurve(225, 25, 280, 250, 300, 50);

function draw(curve, fraction) {
  let x = curve.calcX(fraction);
  let y = curve.calcY(fraction);

  curve.draw();
  drawCircle(x, y, 5);

  curve.tick();
}

// Inefficient but using this instead of binary search just to save space in code example
function findClosestNumInArray(arr, goal) {
  return arr.reduce((prev, cur) => Math.abs(cur.t - goal) < Math.abs(prev.t - goal) ? cur : prev);
}

function drawLoop(elapsed) {  
  c.width = 600;
  c.height = 600;
  
  draw(a, a.f);

  let closest = findClosestNumInArray(b.pointCache, b.f).co;

  draw(b, closest);

  requestAnimationFrame(drawLoop);
}

drawLoop(0);

<canvas></canvas>

Okay, so, to explain what's going on: if you hit Run code snippet you'll see that there are two curves, which I'll refer to as a (left one) and b (right one).

You may notice that the dot moving along a's curve starts off fast, then slows down around the curve, and then speeds up again. This is despite the fractional part being incremented by a constant 0.001 each frame.

The dot for b on the other hand moves at a constant velocity throughout the entire iteration. This is because for b I use the pointCache mapping that I precompute for the curve. This function calcPoints generates a mapping such that the input fractional component t is associated with the "proper" actual percentage along the curve co.

Anyways, this all works, but my issue is that the precomputation calcPoints is expensive, and referencing a lookup table to find the actual fractional part along the line for a percentage is inexact and requires significant memory usage. I was wondering if there was a better way.

What I'm looking for is a way to do something like curve.calcX(0.5) and actually get the 50% mark along the curve. Because currently the existing equation does not do this, and I instead have to do this costly workaround.

Answer 1

We can try to modify your method to be a bit more efficient. It is still not the exact solution you hope for but it might do the trick.

Instead of repeatedly evaluating the Bézier curve at parameter values differing by 0.001 (where you do not reuse the computation from the previous step) we could use the idea of subdivision. Do you know De Casteljau's algorithm? It not only evaluates the Bézier curve at a given parameter t, it also provides you with means to subdivide the curve in two: one Bézier curve that equals the original curve on the interval [0, t] and another one that equals the original curve on [t, 1]. Their control polygons are a much better approximation of the curves than the original control polygon.

So, you would proceed as follows:

1. Use De Casteljau's algorithm to subdivide the curve at t=0.5.
2. Use De Casteljau's algorithm to subdivide the first segment at t=0.25.
3. Use De Casteljau's algorithm to subdivide the second segment at t=0.75.
4. Proceed recursively in the same manner until prescribed depth. This depends on the precision you would like to achieve.

The control polygons of these segments will be your (piecewise linear) approximation of the original Bézier curve. Either use them to precompute the parameters as you have done so far; or plot this approximation directly instead of using quadraticCurveTo with the original curve. Generating this approximation should be much faster than your procedure.

You can read more about this idea in Sections 3.3, 3.4 and 3.5 of Prautzsch, Boehm and Paluszny: Bézier and B-spline techniques. They also provide an estimate how quickly does this procedure converge to the original curve.

Answer 2

Not totally sure this will work, but are you aware of Horner's Scheme for plotting Bezier points?

        /***************************************************************************
        //
        //   This routine plots out a bezier curve, with multiple calls to hornbez()
        //
        //***************************************************************************
        function bezierCalculate(context, NumberOfDots, color, dotSize) {
            // This routine uses Horner's Scheme to draw entire Bezier Line...

            for (var t = 0.0; t < 1.0001; t = t + 1.0 / NumberOfDots) {
                xTemp = hornbez(numberOfControlPoints - 1, "x", t);
                yTemp = hornbez(numberOfControlPoints - 1, "y", t);
                drawDot(context, xTemp, yTemp, dotSize, color);
            }
        }

        //***************************************************************************
        //
        //   This routine uses  Horner's scheme to compute one coordinate
        //   value of a  Bezier curve. Has to be called
        //   for each coordinate  (x,y, and/or z) of a control polygon.
        //   See Farin, pg 59,60.  Note:  This technique is also called
        //   "nested multiplication".
        //   Input:   degree: degree of curve.
        //            coeff:  array with coefficients of curve.
        //            t:      parameter value.
        //            Output: coordinate value.
        //
        //***************************************************************************
        function hornbez(degree, xORy, t) {
            var i;
            var n_choose_i; /* shouldn't be too large! */
            var fact, t1, aux;

            t1 = 1 - t;
            fact = 1;
            n_choose_i = 1;

            var aux = FrameControlPt[0][xORy] * t1;
            /* starting the evaluation loop */
            for (i = 1; i < degree; i++) {
                fact = fact * t;
                n_choose_i = n_choose_i * (degree - i + 1) / i; /* always int! */
                aux = (aux + fact * n_choose_i * FrameControlPt[i][xORy]) * t1;
            }
            aux = aux + fact * t * FrameControlPt[degree][xORy];

            return aux;
        }

Not sure exactly where you are going here, but here's a reference of something I wrote a while ago... And for the contents of just the Bezier iframe, see this... My implied question? Is Bezier the right curve for you?