Can Bézier curves be quickly parameterized by arc-length?

Mike Wang
May 1, 2018

In graphics, organic and natural-looking curves are most commonly produced with Bézier curves. In a Bézier curve, each curve segment is described by a set of 4 points (8 numbers total, since graphics are 2D).

A task that occasionally pops up in web development is to evenly space out dots or letters along a Bézier curve.

Let’s say we have a Bézier curve with two segments, defined like this:

const bezier = [
  {
    A: {x: 62,  y: 63.8},
    B: {x: 62,  y: 260.8},
    C: {x: 438, y: 163.8},
    D: {x: 438, y: 313.8},
  }, {
    A: {x: 438, y: 313.8},
    B: {x: 438, y: 463.8},
    C: {x: 293, y: 474.8},
    D: {x: 293, y: 352.8},
  }
];

where for each segment, A and D are its endpoints, and B and C are their control points respectively. Our curve looks like this:

Our example Bézier curveOur example Bézier curve

We can define functions to calculate the actual xy point corresponding to a certain t value. These functions come from the explicit form of the cubic Bézier curve:

The explicit form of the Bézier equationThe explicit form of the Bézier equation, for 0 ≤ t ≤ 1

We’ll generate one function for each curve segment, and store them in Y:

const Y = bezier.map((seg,i) => {
  return (function(t) {
    return ({
      x: (
        (Math.pow(1-t,3) * seg.A.x) +
        (3 * Math.pow(1-t,2) * t * seg.B.x) +
        (3 * (1-t) * Math.pow(t,2) * seg.C.x) +
        (Math.pow(t,3) * seg.D.x)
      ),
      y: (
        (Math.pow(1-t,3) * seg.A.y) +
        (3 * Math.pow(1-t,2) * t * seg.B.y) +
        (3 * (1-t) * Math.pow(t,2) * seg.C.y) +
        (Math.pow(t,3) * sseg.D.y)
      ),
    });
  });
});

These functions can be used to place m dots along each curve segment, or n dots total. s will hold these dots:

const s = [];
const n = 100;
const m = Array(bezier.length).fill(n / bezier.length);
bezier.forEach((seg, i) => {
  s[i] = [];
  const dt = 1 / m[i];
  for (let t = 0; t < 1; t += dt) {
    s[i].push(Y[i](t));
  }
});

The initial dot spread. Each segment has received 50 dots, distributed according to time parameterizationThe initial dot spread. Each segment has received 50 dots, distributed according to time parameterization

This doesn’t look quite right. Each curve segment received the same number of dots, regardless of how long it was. We can improve things by redistributing the dots according to those segments’ lengths. We’ll first calculate the lengths of each curve segment using mag(), and store them in l. This array will be summed to give us the total length l_total of the entire curve. Then, the n points will be redistributed proportionally:

function mag(a,b) {
  return Math.sqrt(Math.pow(a,2) + Math.pow(b,2));
}

let l = [];
for (let i=0; i<bezier.length; i++) {
  l[i] = 0;
  for (let j=0; j<m[i]-1; j++) {
    l[i] += mag(
      (s[i][j+1].x-s[i][j].x),
      (s[i][j+1].y-s[i][j].y)
    );
  }
  if (i < bezier.length - 1) {
    l[i] += mag(
      (s[i+1][0].x-s[i][m[i]-1].x),
      (s[i+1][0].y-s[i][m[i]-1].y)
    );
  }
}
const l_total = l.reduce((a,c) => {
  return a + c;
});

bezier.forEach((seg, i) => {
  s[i] = [];
  m[i] = Math.floor((l[i] / l_total) * n);
  const dt = 1 / m[i];
  for (let t = 0; t < 1; t += dt) {
    s[i].push(Y[i](t));
  }
});

The dot spread after redistribution. Each segment's dot count now matches its length, but dots are still distributed according to time parameterizationThe dot spread after redistribution. Each segment’s dot count now matches its length, but dots are still distributed according to time parameterization

This looks better, but it’s still not quite right. When the curve’s radius of curvature is small, the points tend to bunch up. This is a feature of time-parameterization, which is intrinsic to the Y functions we used because we defined them in terms of the time variable t.

One way to combat this is to re-parameterize the curve in terms of the arc length variable d. However, this task requires either numeric integration or numeric differentiation of ordinary differential equations, both of which are relatively expensive computations.

Instead, we can use the fact that the average leg length d_avg for any dot distribution is nearly identical to the leg lengths that evenly-spaced dots would produce (this similarity increases as n increases). If we calculate the difference d_err between the actual leg lengths d and the average leg length d_avg, then the time parameter t corresponding to each point can be nudged to reduce this difference. d_err can then be calculated again, and each t nudged again. This nudging can be repeated ad infinitum; here, we’ll do 4 rounds:

const d_avg = l_total / (n - 1);
const step_size = (1 / n) / 10;
for (let i=0; i<bezier.length; i++) {
  let t = [];
  for (let j=0; j<m[i]; j++) {
    t[j] = j / m[i];
  }
  for (let r=0; r<4; r++) {
    let d = [];
    for (let j=0; j<m[i]-1; j++) {
      d[j] = mag(
        (s[i][j+1].x-s[i][j].x),
        (s[i][j+1].y-s[i][j].y)
      );
    }
    const d_err = d.map((segment) => {
      return (segment - d_avg);
    });
    let offset = 0;
    const cutoff = (i === bezier.length - 1) ? 0 : 1;
    for (let j=1; j<m[i]-cutoff; j++) {
      offset += d_err[j-1];
      t[j] -= step_size * offset;
      s[i][j] = Y[i](t[j]);
    }
  }
}

The final dot spread. All dots are now evenly spaced along the entire path according to arc length parameterizationThe final dot spread. All dots are now evenly spaced along the entire path according to arc length parameterization

There! We’ve evenly spaced an arbitrary number of dots along an arbitrary curve. The curve can now have text placed along it, or have a sprite animated to follow it, or animated with streaks of light.

Happy hacking!

 

Solutions Architecture

browse through our blog articles

Blog Archive