How to find the halfway mark on a bezier curve?

Question

I am trying to calculate where points are on a bezier curve, and I'm using the standard formula for doing so. That is:

x = (1 - t) * (1 - t) * x1 + 2 * (1 - t) * t * cpX + t * t * x2;
y = (1 - t) * (1 - t) * y1 + 2 * (1 - t) * t * cpY + t * t * y2;

However, I am pretty confused by the results. I've developed a demo for what I'm talking about below:

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

let x1 = 25;
let y1 = 25;
let cpX = 35;
let cpY = 35;
let x2 = 200;
let y2 = 25;

let f = 0;

function calcX(t) {
  return (1 - t) * (1 - t) * x1 + 2 * (1 - t) * t * cpX + t * t * x2;
}

function calcY(t) {
  return (1 - t) * (1 - t) * y1 + 2 * (1 - t) * t * cpY + t * t * y2;
}

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

function drawLoop(elapsed) {  
  c.width = 600;
  c.height = 600;
  
  let x = calcX(f);
  let y = calcY(f);

  drawCurve();

  ctx.beginPath();
  ctx.rect(x, y, 3, 3);
  ctx.stroke();
  
  f = f < 1 ? f + 0.001 : 0;

  document.querySelector(".debug").innerHTML = f.toFixed(2);

  requestAnimationFrame(drawLoop);
}

drawLoop(0);

.debug { position: absolute; left: 9px; top: 6px; }

<canvas></canvas>
<div class="debug"></div>

As you can see, the 50% mark seems too far to the left:

I understand that there is a curve but the halfway mark still seems too far to the left. That is, if you asked a group of people where the halfway mark is on that curve, I believe all of them would say further to the right.

This may be a long shot but is there another formula for calculating where points are on bezier curves that is more "close to real world"?

Edit: I just thought of another way to more concretely articulate this phenomenon. You'll notice that if you set the cpX and cpY variable values to any arbitrary number and then run the simulation that the square marker moves at different speeds along different portions of the curve. That is, it may move quickly at the start, then slow down, and then speed up again towards the end of the curve.

What I'm looking for is a formula such that the square marker would more at a constant velocity along the entire curve and never speed up or slow down along the way. Is this possible?

Balcke

Duplicate in C# but with resource links: #23597302 – Myriammyriameter

Oh, does this only work for finding the halfway point? I know that's what my title specifies, but I guess I assumed that the solution would be generic and allow you to find any point along the curve, because I'm going to need that as well eventually. – Balcke

The root cause of the problem is this: i.imgur.com/wDvwiQH.png - give me a few minutes and I'll come up with a solution. – Oubliette

@ChrisG Yes, that picture explains exactly what I mean! I'm glad you were able to make sense of my garbled explanation. – Balcke

Here's a solution: jsfiddle.net/s5cp9t01 (I'm saving the coordinates of 100 points in an array, calculate the lengths of the segments between the points, then walk along the segments till I reach the target length. – Oubliette

Hey, this looks right! Thanks a bunch! Feel free to make this an answer and I'll accept it. – Balcke

If you're not afraid of calculus, this might help you find the exact point: ck12.org/c/calculus/parametric-formula-for-length-of-a-curve/… – Doubleheader

Note that there is nothing wrong here: your graphic is correct. That is simply where t=0.5 is on that curve. Quadratic and higher order Bezier curves are non-linear curves, meaning that linearly increasing t does not travel a point over your curve at linear distance intervals (see pomax.github.io/bezierinfo/#tracing for far more information that fits in a comment). For your chosen coordinates, t=0.5 lies to the left of the "distance" center because the curvature is concentrated on the left, so there are "more" curve points with respect to t on the left side. – Davita

Answer 1

I ended up making a function based on Chris G's comment that precomputes all of these points along the bezier curve. Someone else might be able to find it useful:

function calcPoints() {
  const step = 0.001;
  const 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 = [];
  let l = 0;
  let co = 0;

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

  return result;
}

// Example pseudo-code:
let pointCache = calcPoints();
let co = binarySearch(pointCache, 0.5).co;
let x = this.calcX(co);
let y = this.calcY(co);

I think this works? You just binary search the resulting array for the value you're looking for. The function only needs to be run once if your curve doesn't change afterwards.

Balcke

That is the established way to do this (see pomax.github.io/bezierinfo/#tracing) – Davita